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

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

Метод дифференциального криптоанализа впервые был применен для атаки на блочный шифр FEAL-4. Впоследствии метод был усовершенствован и успешно применен для криптоанализа DES. Метод дифференциального криптоанализа позволил получить ответ на вопрос о числе циклов криптографического преобразования стандарта DES. Этот ответ важен с точки зрения разработки эффективных методов криптоанализа произвольных итерированных блочных шифров конструкции Фейстеля.

Вопрос формулировался следующим образом: почему число циклов преобразования равно шестнадцати, не больше и не меньше? Известно, что после пяти циклов каждый бит шифртекста является функцией всех битов открытого текста и ключа. После восьми циклов наблюдается пик лавинного эффекта — шифртекст представляет собой случайную функцию всех битов открытого текста и ключа.

Успешные атаки на DES с тремя, четырьмя и шестью циклами подт­вердили результаты исследований лавинного эффекта. На первый взгляд, криптографическое преобразование с большим числом циклов (>8) представляется необоснованным с точки зрения эффективности ре­ализации. Однако успешный дифференциальный криптоанализ DES доказал: трудоемкость (объем перебора) атаки на открытом тексте для DES с любым количеством циклов, меньшим шестнадцати, ниже, чем трудоемкость силовой атаки. При этом необходимо отметить, что веро­ятность успеха при силовой атаке выше, чем при атаке методом диффе­ренциального криптоанализа. Тот факт, что метод дифференци­ального криптоанализа был известен в момент разработки DES, но засекречен по очевидным соображениям, подтвержден публичными заявлениями самих разработчиков.

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

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

Наилучший известный результат успешного дифференциального криптоанализа DES с шестнадцатью циклами требует 2⁴⁷ выборочных открытых текстов. Можно воспользоваться атакой на известном отк­ры­том тексте, но для этого потребуется уже 2⁵⁵ известных образцов.

Трудоемкость атаки — 2³⁷ DES-шифрований. Дифференциальный криптоанализ эффективен против DES и аналогичных алгоритмов с постоянными S-блоками. Трудоемкость атаки зависит от структуры S-блоков. Для всех режимов шифрования — ЕСВ, СВС, СРВ и OFB — атака имеет одинаковую трудоемкость.

Криптостойкость DES может быть повышена путем увеличения чис­ла циклов. Трудоемкость дифференциального криптоанализа DES c сем­надцатью или восемнадцатью циклами эквивалентна трудоемкости си­ловой атаки. При девятнадцати и более циклах дифференциальный кри­птоанализ невозможен в принципе — для его реализации потребуется более 2⁶⁴ выборочных открытых текстов (DES оперирует блоками по 64 бита, следовательно, существует 2⁶⁴ различных открытых текстов).

В общем случае доказательство криптостойкости по отношению к атаке методом дифференциального криптоанализа заключается в оценке числа открытых текстов, необходимых для выполнения атаки. Атака не­возможна, если полученная оценка превышает 2^b, где b — разряд­ность блока в битах.

Линейный криптоанализ

Метод линейного криптоанализа впервые был применен для атаки блочною шифра FEA L и затем DES. Данный метод исполь­зует линейные приближения. Это озна­чает, что, если выполнить опе­рацию Å над некоторыми битами открытого текста, затем над некото­рыми битами шифртекста, а затем выполнить Å результатов предыду­щего суммирования, можно получить бит, который равен сумме некото­рых бит ключа. Это назы­вается линейным приближением, которое мо­жет быть верным с некоторой вероятностью р. Если р ¹ 1/2, то этот факт можно использовать для раскрытия бит ключа.