Невозможные дифференциалы

В 1998 г. изобретателями дифференциального криптоанализа Эли Бихамом и Эди Шамиром совместно с упоминавшимся выше Алексом Бирюковым были опубликованы две работы, в которых был предложен принципиально новый вариант дифференциального криптоанализа, использующий невозможные дифференциалы (impossible differentials).

Если сравнивать невозможные дифференциалы с классическим дифференциальным криптоанализом, то видно, что использование невозможных дифференциалов представляет собой дифференциальный криптоанализ «от противного»:
данный метод использует дифференциалы с нулевой вероятностью.

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

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

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

Невозможные дифференциалы могут быть применены для вскрытия усеченных (по количеству раундов) версий таких известных алгоритмов шифрования, как IDEA, Khufu и Khafre, Skipjack, MISTY и KASUMI.

По материалам книги Сергея Панасенко «Алгоритмы шифрования»