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

Режимы DES

Дешифрирование DES

Заключительная перестановка

Заключительная перестановка является обратной по отношению к начальной перестановки и описана в 4-й. Обратите внимание, что левая и правая половины не меняются местами после последнего этапа DES, вместо этого объединенный блок R_l6L\e используется как вход заключительной перестановки. В этом нет ничего ос о-бенного, перестановка половинок с последующим циклическим сдвигом привела бы к точно такому же резул ь-тату. Это сделано для того, чтобы алгоритм можно было использовать как для шифрования, так и для дешифр и-рования.

Табл. 12-8. Заключительная перестановка

40, 8^ 48^ \6, 56^ 24^ М, 32^ 39^ Т, 47^ 1Д 55^ 23^ 63^ зТ7

38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29,

36, 4, 44, 12, 52, 20, 60, 28, 35, 3, 43, И, 51, 19, 59, 27,

34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25

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

рирования используется один и тот же алгоритм.

DES позволяет использовать для шифрования или дешифрирования блока одну и ту же функцию. Единс т-венное отличие состоит в том, что ключи должны использоваться в обратном порядке. То есть, если на этапах шифрования использовались ключи К_ъ К₂, К₃,..., К₁₆, то ключами дешифрирования будут К₁₆, К₁₅, К₁₄,..., К_г. Алгоритм, который создает ключ для каждого этапа, также цикличен. Ключ сдвигается направо, а число поз и-ций сдвига равно 0, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1.

FIPS PUB 81 определяет четыре режима работы: ЕСВ, СВС, OFB и CFB (см. главу 9) [1143]. Банковские стандарты ANSI определяют для шифрования ЕСВ и СВС, а для проверки подлинности - СВС и n-битовый CFB

[52].

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

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

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

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

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

Производитель	Микросхема	Год	Тактовая частота	Скорость данных	Доступность
AMD	Am9518		3 МГц	1.3 Мбайт/с	Н
AMD	Am9568	?	4 МГц	1.5 Мбайт/с	Н
AMD	AmZ8068		4 МГц	1.7 Мбайт/с	Н
AT&T	T7000A		?	1.9 Мбайт/с	Н
CE-Infosys	SuperCrypt CE99C003		20 МГц	12.5 Мбайт/с	д
CE-Infosys	SuperCrypt CE99C003A		30 МГц	20.0 Мбайт/с	д
Cryptech	Cryl2C102		20 МГц	2.8 Мбайт/с	д
Newbridge	CA20C03A		25 МГц	3.85 Мбайт/с	д
Newbridge	CA20C03W		8 МГц	0.64 Мбайт/с	д
Newbridge	CA95C68/18/0		33 МГц	14.67 Мбайт/с	д
Pijnenburg	PCC100	?	?	2.5 Мбайт/с	д
Semaphore	Roadranner284	?	40 МГц	35.5 Мбайт/с	д
Communications

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 ELC26000
HyperSparc 32000

RS6000-350 53000

Sparc 10/52 84000

DEC Alpha 4000/610 154000

HP9000/887 125 196,000

12.3 Безопасность 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].

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

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

0101 1F1F E0E0 FEFE

Значение слабого ключа (с битами четности) Действительный ключ

0101 0101 0101 0000000 0000000

IF IF 0E0E 0E0E 0000000 FFFFFFF

E0E0 F1F1 F1F1 FFFFFFF 0000000

FEFE FEFE FEFE FFFFFFF FFFFFFF

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

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

01FE 1FE0 01Е0 1FFE 011F E0FE

01FE	01FE	01FE	и	FE01	FE01	FE01	FE01
1FE0	0EF1	0EF1	и	E01F	E01F	F10E	F10E
01Е0	01F1	01F1	и	Е001	Е001	F101	F101
IEEE	0EFE	0EFE	и	FE1F	FE1F	FE0E	FE0E
011F	010Е	010E	и	1F01	1F01	0Е01	0Е01
E0FE	FIFE	FIFE	и	FEE0	FEE0	FEE1	FEE1

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

Эти возможно слабые ключи перечислены в -1-й.

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

IF

IF

OE

OE

EO

EO

Fl

Fl

IF

IF

OE

OE

FE

IF

EO

FE

OE

Fl

IF

IF

OE

OE

FE

IF

EO

FE

OE

Fl

IF

IF

OE

OE

EO

IF

IF

EO

Fl

OE

OE

Fl

Е0

EO

Fl

Fl

FE

FE

FE

FE

FE

FE

FE

FE

EO

IF

FE

Fl

OE

FE

FE

EO

IF

FE

Fl

OE

EO

IF

FE

Fl

OE

FE

Е0

FE

IF

Fl

FE

OE

FE

IF

IF

FE

FE

OE

OE

FE

FE

EO

IF

FE

Fl

OE

IF

FE

EO

OE

FE

Fl

Е0

FE

IF

Fl

FE

OE

FE

IF

EO

FE

OE

Fl

ЕО

EO

IF

IF

Fl

Fl

OE

OE

IF

EO

FE

OE

Fl

FE

FE

FE

IF

IF

FE

FE

OE

OE

EO

IF

FE

Fl

OE

FE

FE

IF

EO

FE

OE

Fl

EO

EO

Fl

Fl

ЕО

IF

FE

Fl

OE

FE

IF

IF

EO

EO

OE

OE

Fl

Fl

FE

EO

IF

FE

Fl

OE

IF

FE

EO

OE

FE

Fl

ЕО

FE

IF

Fl

FE

OE

IF

FE

EO

OE

FE

Fl

EO

EO

Fl

Fl

IF

EO

FE

OE

Fl

FE

IF

FE

EO

OE

FE

FO

IF

EO

FE

OE

Fl

FE

IF

EO

FE

OE

Fl

FE

FE

FE

FE

FE

FE

FE

FE

FE

IF

IF

FE

FE

OE

OE

FE

FE

IF

EO

EO

IF

OE

Fl

Fl

OE

FE

FE

EO

EO

FE

FE

Fl

Fl

FE

EO

IF

FE

Fl

OE

EO

FE

FE

EO

Fl

FE

FE

Fl

EO

FE

IF

Fl

FE

OE

FE

EO

EO

FE

FE

Fl

Fl

FE

IF

FE

FE

IF

OE

FE

FE

OE

EO

EO

FE

FE

Fl

Fl

FE

FE

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

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

Дата добавления: 2014-11-29