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

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

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

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

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

RDES

RDES - это модификация, в которой в конце каждого этапа обмениваются местами правая и левая половины с использованием зависимой от ключа перестановки [893]. Обмены местами фиксированы и зависят только от ключа. Это означает, что может быть 15 обменов, зависимых от ключа, и 2¹⁵ возможных вариантов, а также что эта модификация не устойчива по отношению к дифференциальному криптоанализу [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 с помощью дифференциального криптоанализа

sⁿDES

Группа корейских исследователей под руководством Кванджо Кима (Kwangjo Kim) попыталась найти набор S‑блоков, оптимально устойчивых и против дифференциального, и против линейного криптоанализа. Их первая попытка, известная как s²DES, представленная в [834], оказалась, как было показано в [855, 858], менее устойчивой, чем DES, против дифференциального криптоанализа. Следующий вариант, s³DES, был представлен в [839] и оказался менее устойчив, чем DES, к линейному криптоанализу [856, 1491, 1527, 858, 838]. Бихам предложил незначительно изменить алгоритм, чтобы сделать s³DES безопасным по отношению и к дифференциальному, и к линейному криптоанализу [165]. Исследователи вернулись к своим компьютерам и разработали улучшенную технику проектирования S-блоков [835, 837]. Они предложили s⁴DES [836], а затем s⁵DES [838, 944].

В Табл. 12-16 приведены для s3DES (с обращенными S‑блоками 1 и 2), которые безопасны по отношению к обоим видам криптоанализа. Использование этого варианта вместе с трехкратным DES наверняка помешает криптоанализу.