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

Понятие дифференциального криптоанализа впервые было введено в 1990 году Эли Бихамом и Ади Шамиром. Используя этот метод, Бихам и Шамир нашли способ атаки алгоритма DES с использованием подобранного открытого текста, который оказался эффективнее атаки «в лоб».

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

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

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

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

Несходство различных пар открытых текстов приводит к несходству получаемых шифртекстов с определенной вероятностью. Эти вероятности можно определить, построив таблицы для каждого из блоков замены. Таблицы сроятся по следующему принципу: по вертикали располагаются все возможные комбинации DA, по горизонтали – все возможные комбинации DС, а на пересечении – число соответствий данного DС данному DA.

Число наибольших совпадений указывает нам пару DA и DС, с помощью которой можно определить секретный ключ. Пара открытых текстов, соответствующих данным DA и DС называется правильной парой, а пара открытых текстов, не соответствующих данным DA и DС – неправильной парой. Правильная пара подскажет правильный ключ цикла, а неправильная пара – случайный.

Чтобы найти правильный ключ, необходимо просто собрать достаточное число предположений. Один из подключей будет встречаться чаще, чем все остальные. Фактически правильный подключ появляется из всех возможных случайных подключей. Очевидно, что для успешного раскрытия необходимо достаточно большое количество данных.

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

Таблица 4.1