Аппаратные и программные реализации DES


Об эффективных аппаратных и программных реализациях алгоритма много писалось [997, 81, 533, 534, 437, 738, 1573, 176, 271, 1572]. Утверждается, что самой быстрой является микросхема DES, разработанная в Digital Equipment Corporation [512]. Она поддерживает режимы ECB и CBC и основана на вентильной матрице GaAs, состоящей из 50000 транзисторов. Данные могут зашифровываться и дешифрироваться со скоростью 1 гигабит в секунду, обрабатывая 16.8 миллионов блоков в секунду. Это впечатляет. Параметры ряда коммерческих микросхем DES приведены в Табл. 12-9. Кажущиеся противоречия между тактовой частотой и скоростью обработки данных обусловлены конвейеризацией внутри микросхемы, в которой может быть реализовано несколько работающих параллельно DES-механизмов.

Наиболее выдающейся микросхемой DES является 6868 VLSI (ранее называвшаяся "Gatekeeper'' - Вратарь). Она не только может выполнять шифрование DES за 8 тактов (лабораторные прототипы могут делать это за 4 такта), но также выполнять троекратный DES в режиме ECB за 25 тактов, а троекратный DES в режимах OFB или CBC - за 35 актов. Мне это кажется невозможным, но уверяю вас, она именно так и работает.

Программная реализация DES на мэйнфрейме IBM 3090 может выполнить 32000 шифрований DES в секунду. На других платформах скорость ниже, но все равно достаточно велика. В Табл. 12-10 [603, 793] приведены действительные результаты и оценки для различных микропроцессоров Intel и Motorola.

Табл. 12-9.
Коммерческие микросхемы DES

Производитель Микросхема Год Тактовая частота Скорость данных Доступность
AMD Am9518 3 МГц l.3 Мбайт/с Н
AMD Am9568 ? 4 МГц l.5 Мбайт/с Н
AMD AmZ8068 4 МГц l.7 Мбайт/с Н
AT&T T7000A ? l.9 Мбайт/с Н
CE-Infosys SuperCrypt CE99C003 20 МГц 12.5 Мбайт/с Д
CE-Infosys SuperCrypt CE99C003A 30 МГц 20.0 Мбайт/с Д
Cryptech Cry12C102 20 МГц 2.8 Мбайт/с Д
Newbridge CA20C03A 25 МГц 3.85 Мбайт/с Д
Newbridge CA20C03W 8 МГц 0.64 Мбайт/с Д
Newbridge CA95C68/18/09 33 МГц 14.67 Мбайт/с Д
Pijnenburg PCC100 ? ? 2.5 Мбайт/с Д
Semaphore Communications Roadrunner284 ? 40 МГц 35.5 Мбайт/с Д
VLSI Technology VM007 32 МГц 200.0 Мбайт/с Д
VLSI Technology VM009 33 МГц 14.0 Д
VLSI Technology 32 МГц 64.0 Мбайт/с Д
Western Digital WD2001/2002 3 МГц 0.23 Мбайт/с Н

 

Табл. 12-10.
Скорости DES на различных микропроцессорах и компьютерах

Процессор Скорость (в МГц) Блоки DES (в с)
4.7
7.6
Sun ELC  
HyperSparc  
RS6000-350  
Sparc 10/52  
DEC Alpha 4000/610  
HP9000/887 196,000

 

Безопасность DES

Люди давно интересуются безопасностью DES [458]. Было много рассуждений о длине ключа, количестве итераций и схеме S-блоков. S-блоки были наиболее таинственными - какие-то константы, без видимого объяснения для чего и зачем они нужны. Хотя IBM утверждала, что работа алгоритма была результатом 17 человеко-лет интенсивного криптоанализа, некоторые люди опасались, что NSA вставило в алгоритм лазейку, которая позволит агентству легко дешифрировать перехваченные сообщения.

Комитет по разведке Сената США чрезвычайно тщательно расследовал этот вопрос в 1978 году. Результаты работы комитета были засекречены, но в открытых итогах этого расследования с NSA были сняты все обвинения в неуместном вмешательстве в проектирование алгоритма [1552]. "Было сказано, что NSA убедило IBM в достаточности более короткого ключа, косвенно помогло разработать структуры S-блоков и подтвердило, что в окончательном варианте DES, с учетом всех знаний NSA, отсутствовали статистические или математические бреши " [435]. Однако, так как правительство не опубликовало подробности расследования, многих людей убедить не удалось.

Тачмен (Tuchman) и Майер (Meyer), разработавшие DES криптографы IBM, заявили, что NSA не изменяло проект [841]:

Их основным подходом был поиск сильных подстановок, перестановок и функций планирования ключей. . . . IBM по просьбе NSA засекретило информацию, касающуюся критериев выбора. ... "NSA сообщило нам, что мы самостоятельно заново открыли ряд секретов, используемых для создания их собственных алгоритмов", - объясняет Тачмен.

Позже в одной из статей Тачмен писал: "Алгоритм DES был полностью разработан внутри IBM ее сотрудниками. NSA не продиктовало ни единой связи!" Тачмен подтвердил это утверждение в своем докладе по истории DES на Национальной конференции по компьютерной безопасности (National Computer Security Conference) в 1992 году.

С другой стороны, Копперсмит писал [373, 374]: "Агентство национальной безопасности (NSA) также помогало IBM техническими советами." А Конхейм (Konheim) утверждал: "Мы послали S-блоки в Вашингтон. Они вернулись полностью переработанными. Мы проверили их, и они прошли нашу проверку." На этот факт и ссылаются как на доказательство, что NSA вставило лазейку в DES. По вопросу о каком-либо преднамеренном ослаблении DES NSA заявило [363]:

Относительно Стандарта шифрования данных (DES) мы считаем, что ответ на ваш вопрос о роли NSA в разработке DES содержится в опубликованных итогах расследования Комитета Сената по разведке, проведенного в 1978 году. В сообщении Комитета указывается, что NSA никоим образом не искажало алгоритм, и что безопасность, предоставляемая DES для несекретных данных, с целью защиты которых он и был разработан, была более чем адекватна в течение по крайней мере 5-10 лет. Короче говоря, NSA не вносило и не пыталось вносить никаких ослаблений в алгоритм DES.

Тогда почему они изменили S-блоки? Может быть, чтобы гарантировать, что лазейка не будет встроена в DES самой IBM. У NSA не было причин доверять исследователям IBM, и оно могло решить, что не до конца исполнит свой долг, если не обеспечит отсутствие лазеек в DES. Задание S-блоков и могло быть одним из способов гарантировать это.

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

Слабые ключи

Из-за того, что первоначальный ключ изменяется при получении подключа для каждого этапа алгоритма, определенные первоначальные ключи являются слабыми [721, 427]. Вспомните, первоначальное значение расщепляется на две половины, каждая из которых сдвигается независимо. Если все биты каждой половины равны 0 или 1, то для всех этапов алгоритма используется один и тот же ключ. Это может произойти, если ключ состоит из одних 1, из одних 0, или если одна половина ключа состоит из одних 1, а другая - из одних 0. Кроме того, у два слабых ключа обладают другими свойствами, снижающими их безопасность [427].

Четыре слабых ключа показаны в шестнадцатиричном виде в Табл. 12-11. (Не забывайте, что каждый восьмой бит - это бит четности.)

Табл. 12-11.
Слабые ключи DES

Значение слабого ключа (с битами четности) Действительный ключ
0000000 0000000
1F1F 1F1F 0E0E 0E0E 0000000 FFFFFFF
E0E0 E0E0 F1F1 F1F1 FFFFFFF 0000000
FEFE FEFE FEFE FEFE FFFFFFF FFFFFFF

 

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

Табл. 12-12.
Полуслабые пары ключей DES

01FE 01FE 01FE 01FE и FE01 FE01 FE01 FE01
1FE0 1FE0 0EF1 0EF1 и E01F E01F F10E F10E
01E0 01E0 01F1 01F1 и E001 E001 F101 F101
1FFE 1EEE 0EFE 0EFE и FE1F FE1F FE0E FE0E
011F 011F 010E 010E и 1F01 1F01 0E01 0E01
E0FE E0FE F1FE F1FE и FEE0 FEE0 FEE1 FEE1

 

Ряд ключей генерирует только четыре подключа, каждый из которых четыре раза используется в алгоритме. Эти возможно слабые ключи перечислены в Табл. 12-13.

Табл. 12-13.
Возможно слабые ключи DES

                                 
1F 1F 0E 0E   E0 E0 F1 F1
1F 1F 0E 0E   FE 1F E0 FE 0E F1
1F 1F 0E 0E   FE 1F E0 FE 0E F1
1F 1F 0E 0E   E0 1F 1F E0 F1 0E 0E F1
E0 E0 F1 F1   FE FE FE FE
FE FE FE FE   E0 1F FE F1 0E FE
FE E0 1F FE F1 0E   E0 1F FE F1 0E FE
E0 FE 1F F1 FE 0E   FE 1F 1F FE FE 0E 0E FE
FE E0 1F FE F1 0E   1F FE E0 0E FE F1
E0 FE 1F F1 FE 0E   FE 1F E0 FE 0E F1
E0 E0 1F 1F F1 F1 0E 0E   1F E0 FE 0E F1 FE
FE FE 1F 1F FE FE 0E 0E   E0 1F FE F1 0E FE
FE 1F E0 FE 0E F1   E0 E0 F1 F1
E0 1F FE F1 0E FE   1F 1F E0 E0 0E 0E F1 F1
FE E0 1F FE F1 0E   1F FE E0 0E FE F1
E0 FE 1F F1 FE 0E   1F FE E0 0E FE F1
E0 E0 F1 F1   1F E0 FE 0E F1 FE
1F FE E0 0E FE F0   1F E0 FE 0E F1 FE
1F E0 FE 0E F1 FE   FE FE FE FE
FE FE FE FE   1F 1F FE FE 0E 0E FE FE
1F E0 E0 1F 0E F1 F1 0E   FE FE E0 E0 FE FE F1 F1
FE E0 1F FE F1 0E   E0 FE FE E0 F1 FE FE F1
E0 FE 1F F1 FE 0E   FE E0 E0 FE FE F1 F1 FE
1F FE FE 1F 0E FE FE 0E   E0 E0 FE FE F1 F1 FE FE

 

Прежде, чем порицать DES слабые ключи, обратите внимание на то, что эти 64 ключа - это крошечная часть полного набора из 72057594037927936 возможных ключей. Если вы выбираете ключ случайно, вероятность выбрать один из слабых ключей пренебрежимо мала. Если вы настоящий параноик, можете всегда проверять "на слабость" сгенерированный ключ. Некоторые думают, что нечего и беспокоиться на этот счет. Другие утверждают, что проверка очень легка, почему бы ее и не выполнить.

Дальнейший анализ слабых и полуслабых ключей приведен в [1116]. Других слабых ключей в процессе исследований найдено не было.

Ключи-дополнения

Выполним побитное дополнение ключа, заменяя все 0 на 1 и все 1 - на 0. Теперь, если блок открытого текста зашифрован оригинальным ключом, то дополнение ключа при шифровании превратит дополнение блока открытого текста в дополнение блока шифротекста. Если x' обозначает дополнение x, то следующее верно:

EK(P) = C

EK'(P') = C'

В этом нет ничего таинственного. На каждом этапе после перестановки с расширением подключи подвергаются операции XOR с правой половиной. Прямым следствием этого факта и является приведенное свойство комплиментарности.

Это означает, что при выполнении вскрытия DES с выбранным открытым текстом нужно проверять только половину возможных ключей: 255 вместо 256 [1080]. Эли Бихам (Eli Biham) и Ади Шамир показали [172], что существует вскрытие с известным открытым текстом, имеющее ту же сложность, для которого нужно не меньше 233 известных открытых текстов.

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



Дата добавления: 2021-01-26; просмотров: 352;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.014 сек.