Дальнейшие направления

Был предпринят ряд попыток расширить концепцию дифференциального криптоанализа на дифференциалы более высоких порядков [702, 161, 927, 858, 860]. Ларс Кнудсен (Lars Knudsen) использует нечто, называемое частичными дифференциалами для вскрытия 6-этапного DES. Этот метод требует 32 выбранных открытых те к-ста и 20000 шифрований [860]. Но этот метод слишком нов, чтобы можно было утверждать, что он облегчит вскрытие полного 16-этапного DES.

Другим способом вскрытия является дифференциально-линейный криптоанализ - объединение дифференц и-ального и линейного криптоанализа. Сьюзен Лангфорд (Susan Langford) и Хеллман предлагают вскрытие 8-этапного DES, которое раскрывает 10 битов ключа с вероятностью успеха 80 процентов, используя 512 в ы-бранных открытых текстов, и с вероятностью успеха 95 процентов, используя 768 выбранных открытых текстов [938]. После вскрытия необходим поиск грубой силой в оставшемся пространстве ключей (2 46 возможных ключей). Хотя по времени это вскрытие сравнимо с предыдущими способами, для него требуется намного меньше открытых текстов. Однако расширение этого метода на большее количество этапов легким не кажется.

Но этот метод нов, и работа продолжается. В ближайшие годы возможны заметные успехи. Может быть у спеха добьется сочетание этого вскрытия с дифференциальным криптоанализом более высоких порядков. Кто знает?

12.5 Реальные критерии проектирования

После появления публикаций о дифференциальном криптоанализе IBM раскрыла критерии проектирования S-блоков и P-блока [373, 374]. Критериями проектирования S-блоков являлись:

- У каждого S-блока 6 входных битов и 4 выходных бита. (Это самый большой размер, который мог быть реализован в одной микросхеме по технологии 1974 года.)

- Ни один выходной бит S-блока не должен быть слишком близок к линейной функции входных битов.

- Если зафиксировать крайние левый и правый биты S-блока, изменяя 4 средних бита, то каждый возмо ж-ный 4-битовый результат получается только один раз.

- Если два входа S-блока отличаются только одним битом, результаты должны отличаться по крайней мере на 2 бита.

- Если два входа S-блока отличаются только двумя центральными битами, результаты должны отличаться по крайней мере на 2 бита.

- Если два входа S-блока отличаются двумя первыми битами, а последние их последние 2 бита совпадают, результаты не должны быть одинаковыми.

- Для любого ненулевого 6-битового отличия между входами, не более, чем 8 из 32 пар входов могут пр и-водить на выходе к одинаковому различию.

- Аналогичный предыдущему критерий, но для случая трех активных S-блоков. Критериями проектирования P-блока являлись:

- 4 выходных бита каждого S-блока на этапе i распределены так, чтобы 2 из них влияют на средние биты S-блоков на этапе i + 1, а другие 2 бита влияют на п оследние биты.

- 4 выходных бита каждого S-блока влияют на шесть различных S-блоков, никакие 2 не влияют на один и тот же S-блок.

- Если выходной бит одного S-блока влияет на средние биты другого S-блока, то выходной бит этого др у-гого S-блока не может влиять на средние биты первого S-блока.

Эта работа продолжала обсуждение критериев. Сегодня совсем нетрудно генерировать S-блоки, но в начале 70-х это б1ло нелегкой задачей. Тачмен говорил, что программы, готовившие S-блоки, работали месяцами.

12.6 Варианты DES

Многократный DES

В ряде реализаций DES используется трехкратный DES (см. 2-й) [55]. Так как DES е является группой, полученный шифротекст гораздо сложнее вскрыть, используя исчерпывающий поиск: 2 112 попыток вместо 256. Подробности можно найти в разделе 15.2.

Шифрование

DE-►TdES-►( DES

Открытый текст

Шифротекст

( DES-[ DE -[ DES-1 У

Дешифрирование

Рис. 12-10. Трехкратный DES.

DES с независимыми подключами

Другой возможностью является использование различных подключей на каждом этапе, не создавая их из одного 56-битового ключа [851]. Так как на каждом из 16 этапов используется 48 битов ключа, то длина ключа для такого варианта составит 768 битов. Такой вариант резко увеличивает сложность вскрытия алгоритма гр убой силой, сложность такого вскрытия составит 2 768.

0днако возможно использование вскрытия "встреча посередине" (см. раздел 15.1). Сложность такого вскр ы-тия уменьшается до 2384, что, тем не менее, вполне достаточно для обеспечения любой мыслимой безопасн ости.

Хотя независимые подключи мешают линейному криптоанализу, этот вариант чувствителен к дифференц и-альному криптоанализу и может быть вскрыт с помощью 2 61 выбранных открытых текстов (см. -3-й) [167, 172]. По видимому, никакая модификация распределения ключей не сможет н амного усилить DES.

DESX

DESX - это вариант DES, разработанный RSA Data Security, Inc., и включенный в 1986 году в программу обеспечения безопасности электронной почты MailSafe, а в 1987 году в набор BSAFE. DESX использует метод, называемый отбеливанием (см. раздел 15.6), для маскировки входов и выходов DES. Кроме 56-битового ключа DES в DESX используется дополнительный 64-битовый ключ отбеливания. Эти 64 бита используются для в ы-полнения операции XOR с блоком открытого текста перед первым этапом DES. Дополнительные 64 бита, я в-ляющиеся результатом применения однонаправленной функции к полному 120-битовому ключу DESX, испол ь-зуются для выполнения XOR с шифротекстом, полученным в результате последнего этапа [155]. По сравнению с DES отбеливание значительно повышает устойчивость DESX к вскрытию грубой силой, вскрытие требует (2120)/й операций при n известных открытых текстах. Также повышается устойчивость к дифференциальному и линейному криптоанализу, для вскрытия потребуется 2 61 выбранных и 260 известных открытых текстов, соответственно [1338].

CRYPT(3)

CRYPT(3) представляет собой вариант DES, используемый в системах UNIX. 0н в основном используется в качестве однонаправленной функции для паролей, но иногда может быть использован и для шифрования. Ра з-личие между CRYPT(3) и DES состоит в том, что в CRYPT(3) включена независимая от ключа перестановка с расширением с 212 вариантами. Это сделано для того, чтобы для создания аппаратного устройства вскрытия паролей нельзя было использовать промышленные микросхемы DES.

Обобщенный DES

0бобщенный DES (Generalized DES, GDES) б1л спроектирован для ускорения DES и повышения устойч и-вости алгоритма [1381, 1382]. 0бщий размер блока увеличился, а количество вычислений осталось неизме н-ным.

На 1-й показана поблочная диаграмма GDES. GDES работает с блоками открытого текста переменной дл и-ны. Блоки шифрования делятся на q 32-битовых подблоков, точное число которых зависит от полного размера блока (который по идее может меняться, но фиксирован для конкретной реализации). В общем случае q равно размеру блока, деленному на 32.

4 4 4

--Ki

Шифротекст

Рис. 12-11. GDES.

Функция f для каждого этапа рассчитывается один раз для крайнего правого блока. Результат при помощи операции XOR объединяется со всеми остальными частям, которые затем циклически смещаются направо. GDES использует переменное число этапов n. В последний этап внесено незначительное изменение, чтобы пр о-цессы шифрования и дешифрирования отличались только порядком подключей (точно также, как в DES). Де й-ствительно, если q = 2 и n = 16, то описанный алгоритм превращается в DES.

Бихам и Шамир [167, 168] показали, что дифференциальный криптоанализ вскрывает GDES с q = 8 и n = 16 с помощью всего шести выбранных открытых текстов. При использовании независимых подключей требуется 16 выбранных открытых текстов. GDES с q = 8 и n = 22 вскрывается с помощью всего 48 выбранных открытых текстов, а для вскрытия GDES с q = 8 и n = 31 требуется всего 500000 выбранных открытых текстов. Даже GDES с q = 8 и n = 64 слабее, чем DES - для его вскрытия нужно только 249 выбранных открытых текстов. Действительно, любая более быстрая, чем DES, схема GDES является также и менее безопасной (см. -3-й).

Недавно появился еще один вариант этой схемы [1591]. Возможно он не более безопасен, чем оригинальный GDES. Общем случае любой вариант DES с большими блоками, который быстрее DES, скорее всего менее безопасен по сравнению с DES.

DES с измененными S-блоками

Другие модификации DES связаны с S-блоками. В некоторых проектах используется переменный порядок S-блоков. Другие разработчики меняют содержание самих S-блоков. Бихам и Шамир показали [170,172], что построение S-блоков и даже их порядок оптимальны с точки зрения устойчивости к дифференциальному кри п-тоанализу:

Изменение порядка восьми S-блоков DES (без изменения их значений) также значительно ослабляет DES: DES с 16 эт а-пами и конкретным измененным порядком вскрывается примерно за 2 38 шагов. ... Доказано, что DES со случайными S-блоками вскрыть очень легко. Даже минимальное изменение одного из элементов S блоков DES может снизить устойч и-