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

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

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

RDES

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

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

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

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

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

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

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

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

S-блоки

Случайные 218 - 220

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

0дноэлементные 233

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

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

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

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

16 этапов 6, 16

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

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

ложил незначительно изменить алгоритм, чтобы сделать s3DES безопасным по отношению и к дифференциал ь-ному, и к линейному криптоанализу [165]. Исследователи вернулись к своим компьютерам и разработали улу ч-шенную технику проектирования S-блоков [835, 837]. Они предложили s4DES [836], а затем s5DES [838, 944].

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

DES с S-блоками, зависящими от ключа

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

Табл. 12-16.

S-блоки s3DES (с обращенными S-блоками 1 и 2)

S-блок 7:

Вот как можно использовать 48 дополнительных битов ключа для создания S-блоков, устойчивых как к л и-нейному, так и к дифференциальному криптоанализу [165].

(1) Изменить порядок S-блоков DES: 24673158.

(2) Выбрать 16 из оставшихся битов ключа. Если первый бит 1, обменять местами первые и последние два ряда S-блока 1. Если второй бит 1, обменять местами первые и последние восемь столбцов S-блока 1. П о-вторить то же самое для третьего и четвертого битов и S-блока 2. Повторить то же самое для S-блоков с 3

по 8.

(3) Взять оставшиеся 32 бита ключа. Выполнить XOR первых четырех битов с каждым элементом S-блока 1, XOR следующих четырех битов с каждым элементом S-блока 2, и так далее.

Сложность вскрытия такой системы с помощью дифференциального криптоанализа составит 251, с пом о-щью линейного криптоанализа - 2 53. Сложность исчерпывающего перебора составит 2102.

Что хорошо в этом варианте DES так это то, что он может быть реализован в существующей аппаратуре. Различные поставщики микросхем DES продают микросхемы DES с возможностью загрузки S-блоков. Можно реализовать любой способ генерации S-блоков вне микросхемы и затем загрузить их в нее. Для дифференц и-ального и линейного криптоанализа нужно так много известных или выбранных открытых текстов, что эти сп особы вскрытия становятся неосуществимыми. Вскрытие грубой силой также трудно себе представить, не пом о-жет никакое увеличение скорости.

12.7 Насколько безопасен сегодня DES?

0твет одновременно и прост, и труден. При простом ответе учитывается только длина ключа (см. раздел 7.1). Машина для вскрытия DES грубой силой, способная найти ключ в среднем за 3.5 часа, в 1993 году стоила 1 миллион долларов [1597, 1598]. DES используется очень широко, и наивно было бы предполагать, что NSA и аналогичные организации в других странах не построили по такому устройству. И не забывайте, что стоимость уменьшается в 5 раз каждые 10 лет. С течением времени DES будет становиться все менее и менее безопасным.

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

Винн Шварцтау (Winn Schwartau) пишет, что NSA построило огромную параллельную машину для вскр ы-тия DES уже в середине 80-х [1404]. По крайней мере одна такая машина б1ла построена в Harris Corp. С и с-пользованием Cray Y-MP. Предположительно существует ряд алгоритмов, которые на несколько порядков уменьшают сложность вскрытия DES грубой силой. Контекстные алгоритмы, основанные на внутренней работе DES, позволяют отбросить ряд ключей, используя частичные решения. Статистические алгоритмы уменьшают эффективную длину ключа еще сильнее. Другие алгоритмы также проверяют вероятные ключи - слова, печ а-таемые последовательности ASCII, и т.д. (см. раздел 8.1). По слухам NSA может вскрыть DES за время от 3 до 15 минут, в зависимости от того коков будет выполненный объем предварительной обработки. И каждая такая машина стоит порядка 50000 долларов.

Согласно другим слухам, если у NSA есть большое количество открытых текстов и шифротекстов, его эк сперты могут выполнить некоторые статистические расчеты и затем считать ключ из архива на оптических ди с-ках.