Дифференциальный криптоанализ

Атаки на блочные шифры

Метод дифференциального криптоанализа впервые был применен для атаки на блочный шифр FEAL-4 [169]. Впоследствии метод был усовершенствован и успешно применен для криптоанализа DES [170,258-260). Метод дифференциального криптоанализа позволил по­лучить ответ на вопрос о числе циклов криптографического преобразования стандарта DES. Этот ответ важен с точки зрения разработки эффективных методов криптоанализа произ­вольных итерированных блочных шифров конструкции Фейстеля. Вопрос формулировался следующим образом: почему число циклов преобразования равно шестнадцати, не больше и не меньше? Известно, что после пяти циклов каждый бит шифротекста является функци­ей всех битов открытого текста и ключа [196,261]. После восьми циклов наблюдается пик лавинного эффекта — шифротекст представляет собой случайную функцию всех битов от­крытого текста и ключа [262]. Успешные атаки на DES с тремя, четырьмя и шестью циклами подтвердили результаты исследований лавинного эффекта [263]. На первый взгляд, крипто­графическое преобразование с большим числом циклов (> 8) представляется необоснованным с точки зрения эффективности реализации. Однако успешный дифференциальный крипто­анализ DES доказал: трудоемкость (объем перебора) атаки на открытом тексте для DES с любым количеством циклов, меньшим шестнадцати, ниже, чем трудоемкость силовой ата­ки. При этом необходимо отметить, что вероятность успеха при силовой атаке выше, чем при атаке методом дифференциального криптоанализа. Тот факт, что метод дифференци­ального криптоанализа был известен в момент разработки DES, но засекречен по очевидным соображениям, подтвержден публичными заявлениями самих разработчиков [264,265].

Ядро метода составляет атака на основе выборочного открытого текста. Идея заключается в анализе процесса изменения несходства для пары открытых текстов, имеющих определен­ные исходные различия, в процессе прохождения через циклы шифрования с одним и тем же ключом. Не существует каких-либо ограничений на выбор открытых текстов. Достаточ­но различия в некоторых позициях. В качестве меры несходства, как правило, используют расстояние Хэмминга.

Исходя из различий в получившихся шифротекстах ключам присваиваются различные вероятности. Истинный ключ определяется в процессе дальнейшего анализа пар шифротекстов — это наиболее вероятный ключ среди множества претендентов. Для пояснения рассмо­трим один цикл криптографического преобразования DES (рис. 11.22).

Рисунок 11.22 – Один цикл DES-преобразования для двух входных блоков X и X¢

Пусть задана пара входов, X и X¢, с несходством DХ.. Вы­ходы, Y и Y¢, — известны, сле­довательно, известно и несход­ство DY. Известны перестанов­ка с расширением Е и Р-блок, следовательно, известны DА и DС. Значения на выходе сум­матора по модулю 2 не извест­ны, однако их несходство DВ известно и равно DА. Доказано, что для любого заданного DА не все значения DС равноверо­ятны. Комбинация DА и DС позволяет предположить значе­ния битов для Е(Х) Å К_i, и Е(Х') Å К_i . To, что Е(X) и Е(Х') известны, дает нам ин­формацию о К_i .

На каждом цикле в преобразовании участвует 48-битный подключ исходного 56-битного секретного ключа. Таким образом, раскрытие К₁₆ позволяет восстановить 48 бит ключа. Остальные восемь можно восстановить при помощи силовой атаки.

Несходство различных пар открытых текстов приводит к несходству получаемых шифротекстов с определенной вероятностью. Вероятности можно оценить, построив таблицу, строки которой представляют собой возможные входы сумматора по модулю 2 (XOR двух различ­ных наборов входных битов), столбцы — возможные результаты операции XOR, а элемент на пересечении строк и столбцов — частота появления конкретного результата суммирова­ния для заданного входа. Таблицу можно построить для каждого из восьми S-блоков DES. Различные несходства на отдельных циклах можно объединять. Кроме того, при условии, что циклы независимы, вероятности могут перемножаться.

Пара открытых текстов, соответствующих несходству с более высокой вероятностью, под­сказывает правильный ключ последнего цикла. Правильный ключ цикла определяется ста­тистически — один из подключей будет встречаться чаще, чем все остальные. Очевидно, что для успешного раскрытия необходимо достаточное количество данных — помимо статистиче­ского материала необходимо хранить частотную таблицу; для этого понадобится не более 253 бит памяти. В ходе дифференциального криптоанализа DES был использован ряд приемов, позволивших сократить объем памяти и оптимизировать некоторые вычисления.

Таблица 11.18. Дифференциальный криптоанализ: результаты атаки на DES

В табл. 11.18 приводится обзор наилучших результатов успешного дифференциальною криптоанализа DES с различным количеством циклов [260]. Первый столбец содержит ко­личество циклов. Два следующих столбца содержат нижнюю оценку числа выборочных или заданных (известных) открытых текстов, необходимых для осуществления атаки. Четвер­тый столбец содержит количество действительно проанализированных открытых текстов. В последнем столбце приведена оценка трудоемкости атаки после обнаружения требуемой пары.

Наилучший известный результат успешного дифференциального криптоанализа DES с шестнадцатью циклами требует 247 выборочных открытых текстов. Можно воспользоваться атакой на известном открытом тексте, но для этого потребуется уже 255 известных образцов. Трудоемкость атаки — 237 DES-шифрований. Дифференциальный криптоанализ эффекти­вен против DES и аналогичных алгоритмов с постоянными S-блоками. Трудоемкость атаки зависит от структуры S-блоков. Для всех режимов шифрования ЕСВ, СВС, CFB и OFB атака имеет одинаковую трудоемкость [260]. Криптостойкость DES может быть повышена путем увеличения числа циклов. Трудоемкость дифференциального криптоанализа DES с семнадцатью или восемнадцатью циклами эквивалентна трудоемкости силовой атаки. При девятнадцати и более циклах дифференциальный криптоанализ невозможен в принципе - для его реализации потребуется более 264 выборочных открытых текстов (DES оперирует блоками по 64 бита, следовательно, существует 2 различных открытых текстов). В общем случае доказательство криптостойкости по отношению к атаке методом дифференциальною криптоанализа заключается в оценке числа открытых текстов, необходимых для выполнения атаки. Атака невозможна, если полученная оценка превышает 2^b, где b - разрядность блока в битах.