Шифрование

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

-*{ DES У

DES-1 }«-( DES }<*-[ DES-1 ]«

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

Шифротекст

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

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

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

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

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

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 операций при n известных открытых текстах. Также повышается устойчивость к дифференциальному и линейному криптоанализу, для вскрытия потребуется 261 выбранных и 260 известных открытых текстов, соответственно [1338].

CRYPT(3)

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

Обобщенный DES

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

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

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

Шифротекст

Рис. 12-11. GDES.

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

Бихам и Шамир [167, 168] показали, что дифференциальный криптоанализ вскрывает GDES с q = 8 и п = 16 с помощью всего шести выбранных открытых текстов. При использовании независимых подключей требуется 16 выбранных открытых текстов. GDES с q = 8 и п = 22 вскрывается с помощью всего 48 выбранных открытых текстов, а для вскрытия GDES с q = 8 и п = 31 требуется всего 500000 выбранных открытых текстов. Даже GDES с q = 8 и п = 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 может снизить устойч и-

вость DES к вскрытию.

S-блоки DES не были оптимизированы против линейного криптоанализа. Существуют и лучшие S-блоки, чем предлагаемые в DES, но бездумная замена S-блоков новыми - не самая лучшая идея.

В -3-й [167, 169] перечислены некоторые модификации DES и количество выбранных открытых текстов, нужное для выполнения дифференциального криптоанализа. В таблицу не включена одна из модификаций, об ъ-единяющая левую и правую половины с помощью сложения по модулю 24 вместо XOR, ее в 2 17 раз труднее вскрыть, чем DES [689].

RDES - это модификация, в которой в конце каждого этапа обмениваются местами правая и левая половины с использованием зависимой от ключа перестановки [893]. Обмены местами фиксированы и зависят только от ключа. Это означает, что может быть 15 обменов, зависимых от ключа, и 2 15 возможных вариантов, а также что эта модификация не устойчива по отношению к дифференциальному криптоанализу [816, 894, 112]. У RDES большое количество слабых ключей. Действительно, почти каждый ключ слабее, чем типичный ключ DES. И с-пользовать эту модификацию нельзя.

Лучшей является идея выполнять обмен местами только в пределах правой половины и в начале каждого этапа. Другой хорошей идеей является выполнение обмена в зависимости от входных данных, а не как статич е-ской функции ключа. Существует множество возможных вариантов [813, 815]. В RDES-1 используется завис я-щая от данных перестановка 16-битовых слов в начале каждого этапа. В RDES-2 применяется зависящая от данных перестановка байтов в начале каждого этапа после 16-битовых перестановок, аналогичных RDES-1. Развитием этой идеи является RDES-4, и т.д. RDES-1 устойчив и к дифференциальному [815], и к линейному криптоанализу [1136]. По видимому, RDES-2 и последующие варианты достаточно хороши.

Табл. 12-15.

Вскрытия вариантов DES с помощью дифференциального криптоанализа

Изменение работыКоличество выбранных

открытых текстов

Полный DES (без изменений)247

P-перестановкаНе может усилить

Тождественная перестановка219

Порядок S-блоков238

Замена XOR сложениями239, 231

S-блоки

Случайные

Случайные перестановки

Одноэлементные

Однородные таблицы

Удаление E-расширения

Порядок E-расширения и XOR подключа

GDES (ширина q=8)

16 этапов6, 16

64 этапа249 (независимый ключ)

s"DES

Группа корейских исследователей под руководством Кванджо Кима (Kwangjo Kim) попыталась найти набор S-блоков, оптимально устойчивых и против дифференциального, и против линейного криптоанализа. Их первая попытка, известная как s2DES, представленная в [834], оказалась, как было показано в [855, 858], менее усто й-чивой, чем DES, против дифференциального криптоанализа. Следующий вариант, s3DES, был представлен в [839] и оказался менее устойчив, чем DES, к линейному криптоанализу [856, 1491, 1527, 858, 838]. Бихам пре д-

218 - 220

233 - 241 233