Интернет магазин китайских планшетных компьютеров

Компьютеры - Дифференциальный криптоанализ - Дифференциальный криптоанализ DES

В 1990 году Эли Бихам и Ади Шамир используя метод дифференциального криптоанализа нашли способ вскрытия DES, более эффективный, чем вскрытие методом грубой силы. Работая с парами шифротекстов, открытые тексты которых имеют определенные отличия, ученые анализировали эволюцию этих отличий при прохождении открытых текстов через этапы DES.

Схема взлома

Рис.1 Схема взлома

На схеме представлено прохождение одного из этапов DES. Пусть X и X' - пара входов, различающихся на ΔX. Соответствующие им выходы известны и равны Y и Y', разница между ними - ΔY. Также известны перестановка с расширением и P-блок, поэтому известны ΔA и ΔC. B и B' неизвестны, но мы знаем, что их разность равна ΔA, т.к. различия XOR K_i c A и A' нейтрализуются. Вскрытие ключа основано на том факте, что для заданного ΔA не все значения ΔC равновероятны, а комбинация ΔA и ΔC позволяет предположить значения A XOR K_i и A' XOR K_i. При известных A и A' это дает нам информацию о K_i.

Таким образом, определенные отличия пар открытых текстов с высокой вероятностью вызывают определенные отличия получаемых шифротекстов. Такие различия называют характеристиками. Для нахождения характеристик составляется таблица, в которой строкам соответствуют возможные ΔX, столбцам - возможные ΔY, а на пересечении строки и столбца пишется, сколько раз заданное ΔY встречается для заданного ΔX. Различные характеристики можно объединять, и, при условии, что рассматриваемые этапы независимы, перемножать их вероятности.

Пара открытых текстов, которая соответствует характеристике называется правильной парой, а пара, не соответствующая характеристике - неправильной парой. Правильная пара указывает на правильный ключ рассматриваемого этапа, неправильная - на случайный ключ. Для нахождения правильного ключа этапа нужно собрать достаточное количество предположений - один из ключей будет встречаться среди правильных чаще, чем остальные. Зная вероятное значение K_i мы получаем 48 битов ключа шифрования K. Остальные 8 битов можно определить с помощью перебора.

Эффективность взлома

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

Бихам и Шамир предложили вместо 15-этапной характеристики 16-этапного DES использовать 13-этапную характеристику и с помощью ряда приемов получать данные для последних этапов. Кроме того, они использовали специальные оптимизации для получения вероятных 56-битовых ключей, что позволяло проверять их немедленно. Это решало проблему с пороговым характером взлома и устраняло необходимость в хранении счетчиков.

Наилучший разработанный алгоритм дифференциального вскрытия полного 16-этапного DES требует 2 выбранных открытых текстов. При этом временнная сложность составляет 2 операций DES.

Дифференциальный криптоанализ применим для взлома алгоритмов с постоянными S-блоками, таких как DES. При этом его эффективность сильно зависит от структуры S-блоков. Оказалось, что S-блоки DES оптимизированы против дифференциального криптоанализа. Предполагается, что создатели DES знали об этом методе. По словам Дона Копперсмита из IBM:

Повышение устойчивости к взлому

Устойчивость DES к дифференциальному криптоанализу может быть повышена путем увеличения количества этапов. Дифференциальный криптоанализ для DES с 17 или 18 этапами потребует столько же времени, сколько и полный перебор, а при 19 или более этапах дифференциальный криптоанализ невозможен.

Недостатки метода

Отмечается, что метод дифференциального криптоанализа в большей степени является теоретическим достижением. Его применение на практике ограничено высокими требованиями к времени и объему данных. Кроме того, этот метод в первую очередь применим для вскрытия с выбранным открытым текстом. Он может быть использован для вскрытия с известным открытым текстом, но в случае полного 16-этапного DES это делает его даже менее эффективным, чем вскрытие грубой силой.

Таким образом, правильно реализованный алгоритм DES сохраняет устойчивость к дифференциальному криптоанализу.

Сравнение с другими методами

См. Известные атаки на DES