MADRYGA

FDES

RDES

К,

Обобщенный DES

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

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


в2

к2


УптпУпУп f !

tt? tb4 щ У< —^- к,

кп

 

вГ   еп(2)   еп(3)   вУ]   в>>
       
   
  Шифротекст  
                   

Рис. 12-11. GDES.

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

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

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

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

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

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

S-блоки

218 - 220 233 - 241 ?33 ^44

Случайные

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

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

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

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

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

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

16 этапов 6, 16

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

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


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

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

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

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

Табл. 12-16. S-блоки S3DES (с обращенными S-блоками 1 и 2)

 

S-блок 1:                            
13 14 И
8 2 И
14 9 И
И
S-блок 2:                            
15 8 И
6 15 И
9 14 2, И
10 5 И
S-блок З:                            
13 3 И
4 13 и
И
1 И
S-блок 4:                            
И 12,
5 10 И
10 7 И
3 9 И
S-блок 5:                            
5 15 И
6 9 И
15 0 И
12 5 И
S-блок 6:                            
43 И
14 13 И
13 0 И
1 7 И

S-блок 7:                            
4 10 И
10 15 И
2 12 И
12 6 И
S-блок 8:                            
13 10 И
И
4 13 И
8 И

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

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

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

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

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

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

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

Ответ одновременно и прост, и труден. При простом ответе учитывается только длина ключа (см. раздел 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]. По крайней мере одна такая машина была построена в Harris Corp. С и с-пользованием Cray Y-MP. Предположительно существует ряд алгоритмов, которые на несколько порядков уменьшают сложность вскрытия DES грубой силой. Контекстные алгоритмы, основанные на внутренней работе DES, позволяют отбросить ряд ключей, используя частичные решения. Статистические алгоритмы уменьшают эффективную длину ключа еще сильнее. Другие алгоритмы также проверяют вероятные ключи - слова, печ а-таемые последовательности ASCII, и т.д. (см. раздел 8.1). По слухам NSA может вскрыть DES за время от 3 до 15 минут, в зависимости от того коков будет выполненный объем предварительной обработки. И каждая такая машина стоит порядка 50000 долларов.

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


И то, что это только слухи, не дает мне чувство уверенности в DES. Этот алгоритм очень долго был очень большой мишенью. Почти любое изменение DES послужит дополнительной защитой, может быть получивши й-ся шифр и будет менее устойчив к вскрытию, но у NSA может не оказаться средств решения этой конкретной задачи.

Я рекомендую использовать схему Бихама для зависящих от ключа S-блоков. Она может быть легко реал и-зована программно или аппаратно (с помощью микросхем с загружаемыми S-блоками), и не приводит к потере эффективности по сравнению с DES. Эта схема повышает устойчивость алгоритма к вскрытию грубой силой, усложняет дифференциальный и линейный криптоанализ и заставляет NSA столкнуться с алгоритмом, по кра й-ней мере таким же сильным как DES, но другим.


Глава 13 Другие блочные шифры 13.1 LUCIFER

В конце 60-х IBM начала выполнение исследовательской программы по компьютерной криптографии, наз ы-анной Люцифером (Lucifer) и руководимой сначала Хорстом Фейстелем (Horst Feistel), а затем Уолтом Тачм е-ном (Walt Tuchman). Это же название - Lucifer - получил блочный алгоритм, появившийся в результате этой программыв начале 70-х [1482, 1484]. В действительности существует по меньшей мере два различных алг о-ритма с таким именем [552, 1492]. [552] содержит ряд пробелов в спецификации алгоритма. Все это привело к заметной путанице.

Lucifer - это набор перестановок и подстановок, его блоки похожи на блоки DES. В DES результат функции f объединяется с помощью XOR со входом предыдущего этапа, образуя вход следующего этапа. У S-блоков алг о-ритма Lucifer 4-битовые входы и 4-битовые выходы, вход S-блоков представляет собой перетасованный выход 8_блоков предыдущего этапа, входом S-блоков первого этапа является открытый текст. Для выбора использу е-мого S-блока из двух возможных применяется бит ключа. (Lucifer реализует это, как один Т-блок с 9 битами на входе и 8 битами на выходе.) В отличие от DES половины блока между этапами не переставляются и вообще понятие половины блока не используется в алгоритме Lucifer. У этого алгоритма 16 этапов, 128-битовые блоки и более простое, чем в DES, распределение ключей.

Применив дифференциальный криптоанализ к первой реализации Lucifer'a, Бихам и Шамир [170, 172] пок а-зали, что Lucifer с 32-битовыми блоками и 8 этапами может быть взломан с помощью 40 выбранных открытых текстов за 239 шагов, тот же способ позволит вскрыть Lucifer с 128-битовыми блоками и 8 этапами с помощью 60 выбранных открытых текстов за 253 шагов. 18-этапный, 128-битовый Lucifer вскрывается дифференциаль­ным криптоанализом с помощью 24 выбранных открытых текстов за 2 21 шагов. Все эти вскрытия использовали сильные S-блоки DES. Применив дифференциальный криптоанализ против второй реализации Lucifer, Бихам и Шамир обнаружили, что S-блоки намного слабее, чем в DES. Дальнейший анализ показал, что более половины возможных ключей не являются безопасными [112]. Криптоанализ со связанными ключами может взломать 128-битовый Lucifer с любым числом этапов с помощью 233 выбранных открытых текстов для выбранных клю­чей или 265 известных открытых текстов для выбранных ключей [158]. Вторая реализация Lucifer еще слабее [170, 172, 112].

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

Lucifer является объектом нескольких патентов США: [553, 554, 555, 1483]. Сроки действия всех этих п а-тентов истекли.

В.Е. Мадрига (W. E. Madryga) предложил этот блочный алгоритм в 1984 году [999]. Он может быть эффе к-тивно реализован как программа: в нем нет надоедливых перестановок, и все операции выполняются над ба й-тами. Стоит перечислить задачи, которые решал автор при проектировании алгоритма:

1. Открытый текст нельзя получить из шифротекста без помощи ключа. (Это означает только то, что а л-горитм безопасен.)

2. Количество операций, нужное для определения ключа по имеющимся шифротексту и открытому те к-сту, должно быть статистически равно произведению количества операций при шифровании на число возможных ключей. (Это означает, что никакое вскрытие с открытым текстом не может быть лучше, чем вскрытие грубой силой.)

3. Известность алгоритма не влияет на силу шифра. (Безопасность полностью опр еделяется ключом.)

4. Изменение одного бита ключа должно вызывать для того же открытого текста радикальное изменение шифротекста, и Изменение одного бита открытого текста должно вызывать для того же ключа рад и-кальное изменение шифротекста. (Это лавинный э ффект.)

5. Алгоритм должен содержать некоммутативную комбинацию подстановок и перестан овок.

6. Подстановки и перестановки, используемые в алгоритме, должны определяться и входными данными, и ключом.

7. Избыточные группы битов открытого текста должны быть полностью замаскированы в шифротексте.

8. Длина шифротекста должна равняться длине открытого текста.


9. Не должно быть простых взаимосвязей между любыми возможными ключами и особенностями ши ф-ротекста.

10. Все возможные ключи должны давать сильный шифр. (Не должно быть слабых кл ючей.)

11. Длина ключа и текста могут регулироваться для реализации различных требований к безопасности.

12. Алгоритм должен позволять эффективную программную реализацию на больших мэйнфреймах, м и-никомпьютерах, микрокомпьютерах и с помощью дискретной логики. (По сути используемые в алг о-ритме функции ограничены XOR и битовым сдвигом.)

DES удовлетворял первым девяти требованиям, но последние три были новыми. В предположении, что лу ч-шим способом вскрытия алгоритма является грубая сила, переменная длина ключа, конечно же, заставит з а-молчать тех, кто считает, что 56 битов - это слишком мало. Такие люди могут реализовать этот алгоритм с л го­бой нужной им длиной ключа. А любой, кто когда-нибудь пытался реализовать DES программно, обрадуется алгоритму, который учитывает возможности программных реал изаций.