В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 4. Блочные шифры Небольшая тавтология, не так ли? Теперь необходимо определить, что такое атака на блочный шифр. Определение 2 Атака на блочный шифр — это нетривиальный метод об- наружения различия между блочным шифром и идеальным блочным шифром. Что же подразумевается под обнаружением такого различия? Речь идет о сравнении некоторого блочного шифра X с идеальным блочным шифром, имеющим такой же размер блока и такой же размер ключа. Различитель — это алгоритм, которому свойственна функция “черного ящика”, вычисляю- щая для заданного открытого текста блочный шифр X либо идеальный блоч- ный шифр. (Функция “черного ящика” — это функция, которую можно оце- нить, однако точная внутренняя структура которой неизвестна.) Алгоритму- различителю доступны и функция шифрования, и функция дешифрования. Кроме того, для каждой операции шифрования или дешифрования разли- читель может применять любой выбранный им ключ. Задача различителя состоит в том, чтобы определить, что именно реализует функция “черного ящика”: блочный шифр X или же идеальный блочный шифр. Различителю необязательно быть совершенным — достаточно лишь, чтобы правильные от- веты давались значительно чаще неправильных. Описанная выше задача, конечно же, имеет тривиальные решения. Мож- но зашифровать открытый текст 0 с помощью ключа 0 и посмотреть, соответ- ствует ли результат шифрования тому, что мы ожидаем получить от блочно- го шифра X . Данный алгоритм также подходит под определение различите- ля, однако, чтобы осуществить реальное нападение на систему, различитель должен быть нетривиальным. Именно этот аспект и затрудняет определе- ние безопасности блочного шифра. Мы не можем формализовать понятия “тривиальный” и “нетривиальный”. Это все равно что пытаться определить непристойное поведение: мы сможем понять, непристойно себя ведет человек или нет, только непосредственно столкнувшись с его поведением 2 . Различи- тель является тривиальным, если мы можем найти аналогичный различитель практически для каждого блочного шифра. В описанном случае различитель является тривиальным, потому что мы можем построить такой же различи- тель для каждого блочного шифра, даже для идеального. Можно построить и более совершенный тривиальный различитель. Да- вайте зашифруем открытый текст 0 с помощью всех ключей в диапазоне 1 , . . . , 2 32 и подсчитаем, как часто среди полученных результатов будет по- вторяться каждое конкретное значение первых 32 бит шифрованного текста. 2 В 1964 году верховный судья США Поттер Стюарт (Potter Stewart) использовал это выражение для определения того, что следует считать непристойным поведением: “Сегодня я больше не буду пытаться определить данный тип события. . . но я пойму, оно это или нет, когда его увижу”. 4.4. Определение безопасности блочного шифра 67 Пусть для шифра X оказалось, что значение t встречается пять раз вместо ожидаемого одного. Это свойство вряд ли характеризует идеальный шифр. Данный алгоритм также является тривиальным различителем, поскольку аналогичный метод можно применить к любому шифру X . (Маловероятно, чтобы для конкретного блочного шифра не нашлось подходящего значения t .) Ситуация усложняется, если построить различитель следующим образом. Составим список из 1000 различных статистических показателей, которые мы можем подсчитать для шифра. Затем подсчитаем все эти показатели для шифра X и построим различитель на основе того показателя, который даст наиболее значимый результат. Мы ожидаем найти показатель с уровнем зна- чимости, примерно равным 0,001. Разумеется, с помощью этого алгоритма можно построить различитель для любого конкретного шифра, поэтому дан- ный метод является тривиальным, однако теперь эта тривиальность зависит не только от самого различителя, но и от того, как он был построен. Вот почему еще никому не удалось формализовать определение тривиальности и безопасности блочного шифра. Криптографическое сообщество еще не на- столько хорошо знает криптографию, чтобы корректно сформулировать дан- ное определение. Использование более формального определения, которое не учитывает целый ряд типов атак, никак не поможет в построении безопас- ных систем. Допустимое количество вычислений, выполняемых различителем, долж- но быть ограничено. Мы не упомянули об этом в самом определении, чтобы не усложнять его. Если блочный шифр обладает явно заданным уровнем без- опасности в n бит, различитель должен быть более эффективен, чем поиск путем полного перебора n -битовых значений. Если же уровень безопасности явно не указан, он принимается равным размеру ключа. Данная формули- ровка несколько расплывчата, однако на то есть причина. Во многих источ- никах просто отмечается, что различитель должен выполнить свою работу менее чем за 2 n шагов. Это, безусловно, верно, однако некоторые типы раз- личителей дают только вероятностный результат, более похожий на поиск ключа с частичным перебором вариантов. Атака не всегда обладает прямой зависимостью между количеством проделанной работы и вероятностью об- наружить различие между шифром и идеальным шифром. Взять хотя бы такой пример: поиск путем полного перебора на половине пространства клю- чей требует выполнения 2 n − 1 шагов и дает правильный ответ в 75% случаев. (Если злоумышленник находит ключ, он уже знает ответ. Если же он не на- ходит ключ, у него все еще есть 50%-ная вероятность правильно угадать этот ключ. Таким образом, общая вероятность получить правильный ответ равна 0 , 5 + 0 , 5 · 0 , 5 = 0 , 75 .) Сравнивая различитель с подобным частичным поиском на пространстве ключей, мы учитываем эту особенность и не рассматриваем частичный поиск как атаку. |