DES с измененными S-блоками
Другие модификации DES связаны с S-блоками. В некоторых проектах используется переменный порядок S-блоков. Другие разработчики меняют содержание самих S-блоков. Бихам и Шамир показали [170,172], что построение S-блоков и даже их порядок оптимальны с точки зрения устойчивости к дифференциальному криптоанализу:
Изменение порядка восьми S-блоков DES (без изменения их значений) также значительно ослабляет DES: DES с 16 этапами и конкретным измененным порядком вскрывается примерно за 238 шагов. ... Доказано, что DES со случайными S-блоками вскрыть очень легко. Даже минимальное изменение одного из элементов S_блоков DES может снизить устойчивость DES к вскрытию.
S-блоки DES не были оптимизированы против линейного криптоанализа. Существуют и лучшие S-блоки, чем предлагаемые в DES, но бездумная замена S-блоков новыми - не самая лучшая идея.
В Табл. 12-15 [167, 169] перечислены некоторые модификации DES и количество выбранных открытых текстов, нужное для выполнения дифференциального криптоанализа. В таблицу не включена одна из модификаций, объединяющая левую и правую половины с помощью сложения по модулю 24 вместо XOR, ее в 217 раз труднее вскрыть, чем DES [689].
RDES
RDES - это модификация, в которой в конце каждого этапа обмениваются местами правая и левая половины с использованием зависимой от ключа перестановки [893]. Обмены местами фиксированы и зависят только от ключа. Это означает, что может быть 15 обменов, зависимых от ключа, и 215 возможных вариантов, а также что эта модификация не устойчива по отношению к дифференциальному криптоанализу [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-блоки |
|
|
Случайные |
218 - 220 |
|
Случайные перестановки |
233 - 241 |
|
Одноэлементные |
233 |
|
Однородные таблицы |
226 |
|
Удаление E-расширения |
226 |
|
Порядок E-расширения и XOR подключа |
244 |
|
GDES (ширина q=8) |
|
|
16 этапов |
6, 16 |
|
64 этапа |
249 (независимый ключ) |
snDES
Группа корейских исследователей под руководством Кванджо Кима (Kwangjo Kim) попыталась найти набор S-блоков, оптимально устойчивых и против дифференциального, и против линейного криптоанализа. Их первая попытка, известная как s2DES, представленная в [834], оказалась, как было показано в [855, 858], менее устойчивой, чем DES, против дифференциального криптоанализа. Следующий вариант, s3DES, был представлен в [839] и оказался менее устойчив, чем DES, к линейному криптоанализу [856, 1491, 1527, 858, 838]. Бихам предложил незначительно изменить алгоритм, чтобы сделать s3DES безопасным по отношению и к дифференциальному, и к линейному криптоанализу [165]. Исследователи вернулись к своим компьютерам и разработали улучшенную технику проектирования S-блоков [835, 837]. Они предложили s4DES [836], а затем s5DES [838, 944].
В Табл. 12-16 приведены для s3DES (с обращенными S-блоками 1 и 2), которые безопасны по отношению к обоим видам криптоанализа. Использование этого варианта вместе с трехкратным DES наверняка помешает криптоанализу.
DES с S-блоками, зависящими от ключа
Линейный и дифференциальный криптоанализ работают только, если аналитику известно строение S-блоков. Если S-блоки зависят от ключа и выбираются криптографически сильным методом, то линейный и дифференциальный криптоанализ значительно усложнятся. Хотя надо помнить, что даже у хранящихся в секрете случайно созданных S-блоков очень плохие дифференциальные и линейные характеристики.
Табл. 12-16.
S-блоки s3DES (с обращенными S-блоками 1 и 2)
S-блок 1:
|
13 |
14 |
0 |
3 |
10 |
4 |
7 |
9 |
11 |
8 |
12 |
6 |
1 |
15 |
2 |
5 |
|
8 |
2 |
11 |
13 |
4 |
1 |
14 |
7 |
5 |
15 |
0 |
3 |
10 |
6 |
9 |
12 |
|
14 |
9 |
3 |
10 |
0 |
7 |
13 |
4 |
8 |
5 |
6 |
15 |
11 |
12 |
1 |
2 |
|
1 |
4 |
14 |
7 |
11 |
13 |
8 |
2 |
6 |
3 |
5 |
10 |
12 |
0 |
15 |
9 |
S-блок 2:
|
15 |
8 |
3 |
14 |
4 |
2 |
9 |
5 |
0 |
11 |
10 |
1 |
13 |
7 |
6 |
12 |
|
6 |
15 |
9 |
5 |
3 |
12 |
10 |
0 |
13 |
8 |
4 |
11 |
14 |
2 |
1 |
7 |
|
9 |
14 |
5 |
8 |
2, |
4 |
15 |
3 |
10 |
7 |
6 |
13 |
1 |
11 |
12 |
0 |
|
10 |
5 |
3 |
15 |
12 |
9 |
0 |
6 |
1 |
2 |
8 |
4 |
11 |
14 |
7 |
13 |
S-блок 3:
|
13 |
3 |
11 |
5 |
14 |
8 |
0 |
6 |
4 |
15 |
1 |
12 |
7 |
2 |
10 |
9 |
|
4 |
13 |
1 |
8 |
7 |
2 |
14 |
11 |
15 |
10 |
12 |
3 |
9 |
5 |
0 |
6 |
|
6 |
5 |
8 |
11 |
13 |
14 |
3 |
0 |
9 |
2 |
4 |
1 |
10 |
7 |
15 |
12 |
|
1 |
11 |
7 |
2 |
8 |
13 |
4 |
14 |
6 |
12 |
10 |
15 |
3 |
0 |
9 |
5 |
S-блок 4:
|
9 |
0 |
7 |
11 |
12, |
5 |
10 |
6 |
15 |
3 |
1 |
14 |
2 |
8 |
4 |
13 |
|
5 |
10 |
12 |
6 |
0 |
15 |
3 |
9 |
8 |
13 |
11 |
1 |
7 |
2 |
14 |
4 |
|
10 |
7 |
9 |
12 |
5 |
0 |
6 |
11 |
3 |
14 |
4 |
2 |
8 |
13 |
15 |
1 |
|
3 |
9 |
15 |
0 |
6 |
10 |
5 |
12 |
14 |
2 |
1 |
7 |
13 |
4 |
8 |
11 |
S-блок 5:
|
5 |
15 |
9 |
10 |
0 |
3 |
14 |
4 |
2 |
12 |
7 |
1 |
13 |
6 |
8 |
11 |
|
6 |
9 |
3 |
15 |
5 |
12 |
0 |
10 |
8 |
7 |
13 |
4 |
2 |
11 |
14 |
1 |
|
15 |
0 |
10 |
9 |
3 |
5 |
4 |
14 |
8 |
11 |
1 |
7 |
6 |
12 |
13 |
2 |
|
12 |
5 |
0 |
6 |
15 |
10 |
9 |
3 |
7 |
2 |
14 |
11 |
8 |
1 |
4 |
13 |
S-блок 6:
|
4 |
3 |
7 |
10 |
9 |
0 |
14 |
13 |
15 |
5 |
12 |
6 |
2 |
11 |
1 |
8 |
|
14 |
13 |
11 |
4 |
2 |
7 |
1 |
8 |
9 |
10 |
5 |
3 |
15 |
0 |
12 |
6 |
|
13 |
0 |
10 |
9 |
4 |
3 |
7 |
14 |
1 |
15 |
6 |
12 |
8 |
5 |
11 |
2 |
|
1 |
7 |
4 |
14 |
11 |
8 |
13 |
2 |
10 |
12 |
3 |
5 |
6 |
15 |
0 |
9 |
S-блок 7:
|
4 |
10 |
15 |
12 |
2 |
9 |
1 |
6 |
11 |
5 |
0 |
3 |
7 |
14 |
13 |
8 |
|
10 |
15 |
6 |
0 |
5 |
3 |
12 |
9 |
1 |
8 |
11 |
13 |
14 |
4 |
7 |
2 |
|
2 |
12 |
9 |
6 |
15 |
10 |
4 |
1 |
5 |
11 |
3 |
0 |
8 |
7 |
14 |
13 |
|
12 |
6 |
3 |
9 |
0 |
5 |
10 |
15 |
2 |
13 |
4 |
14 |
7 |
11 |
1 |
8 |
S-блок 8:
|
13 |
10 |
0 |
7 |
3 |
9 |
14 |
4 |
2 |
15 |
12 |
1 |
5 |
6 |
11 |
8 |
|
2 |
7 |
13 |
1 |
4 |
14 |
11 |
8 |
15 |
12 |
6 |
10 |
9 |
5 |
0 |
3 |
|
4 |
13 |
14 |
0 |
9 |
3 |
7 |
10 |
1 |
8 |
2 |
11 |
15 |
5 |
12 |
6 |
|
8 |
11 |
7 |
14 |
2 |
4 |
13 |
1 |
6 |
5 |
9 |
0 |
12 |
15 |
3 |
10 |
Вот как можно использовать 48 дополнительных битов ключа для создания S-блоков, устойчивых как к линейному, так и к дифференциальному криптоанализу [165].
-
Изменить порядок S-блоков DES: 24673158.
-
Выбрать 16 из оставшихся битов ключа. Если первый бит 1, обменять местами первые и последние два ряда S-блока 1. Если второй бит 1, обменять местами первые и последние восемь столбцов S-блока 1. Повторить то же самое для третьего и четвертого битов и S-блока 2. Повторить то же самое для S-блоков с 3 по 8.
-
Взять оставшиеся 32 бита ключа. Выполнить XOR первых четырех битов с каждым элементом S-блока 1, XOR следующих четырех битов с каждым элементом S-блока 2, и так далее.
Сложность вскрытия такой системы с помощью дифференциального криптоанализа составит 251, с помощью линейного криптоанализа - 253. Сложность исчерпывающего перебора составит 2102.
Что хорошо в этом варианте DES так это то, что он может быть реализован в существующей аппаратуре. Различные поставщики микросхем DES продают микросхемы DES с возможностью загрузки S-блоков. Можно реализовать любой способ генерации S-блоков вне микросхемы и затем загрузить их в нее. Для дифференциального и линейного криптоанализа нужно так много известных или выбранных открытых текстов, что эти способы вскрытия становятся неосуществимыми. Вскрытие грубой силой также трудно себе представить, не поможет никакое увеличение скорости.