Криптостойкость алгоритма DES

С самого начала использования алгоритма DES криптоаналитики всего мира прилагали множество усилий по его взлому. Фактически DES дал невиданный доселе толчок развитию криптоанализа. Вышли сотни трудов, посвященных различным методам криптоанализа именно в приложении к алгоритму DES, а также деталям самого алгоритма и их влиянию на криптостойкость DES. Можно утверждать, что именно благодаря DES появились целые направления криптоанализа, такие как:

?      линейный криптоанализ (см. разд. 1.5);

?      дифференциальный криптоанализ (см. разд. /.5);

?      криптоанализ на связанных ключах (см. разд. 1.9); стоит сказать, что в работе [56] было доказано, что DES неуязвим к данному виду атак благодаря тому, что в описанной выше процедуре расширения ключа циклический сдвиг выполняется на различное число битов в разных раундах.

«DES стойко выдержал 20 лет массового всемирного криптоанализа» [123] — десятилетия криптоанализа не привели к обнаружению серьезных уязвимо- стей в алгоритме. Основными результатами усилий по взлому DES можно считать следущие.

?      Японский специалист Мицуру Мацуи (Mitsuru Matsui), изобретатель линейного криптоанализа, в 1993 г. доказал возможность вычисления ключа шифрования DES методом линейного криптоанализа при наличии у атакующего 247 пар известных открытых текстов [256].

?      Криптологи из Израиля — изобретатели дифференциального криптоанализа Эли Бихам и Эди Шамир (считается, что дифференциальный криптоанализ был известен АНБ США еще в 1970-х гг. [28], однако, имённо Бихам и Шамир сформулировали данный вид атак и сделали его доступным всему криптологическому сообществу)— в 1991 г. представили атаку, в которой ключ шифрования вычисляется методом дифференциального криптоанализа при наличии у атакующего возможности генерации 247 пар выбранных открытых текстов [78].

?     В 1994 г. Эли Бихам и Алекс Бирюков усилили известный с 1987 г. метод вычисления ключа DES — метод Дэвиса (Davies), основанный на специфических свойствах таблиц замен DES [59]. Усиленный метод позволяет вычислить 6 битов ключа DES (остальные 50 битов — полным перебором возможных вариантов) при наличии 250 пар известных открытых текстов и шифртекстов или вычислить 24 бита ключа при наличии 2 пар.

В дальнейшем эти атаки были несколько усилены (например, атака линейным криптоанализом при наличии 243 пар известных открытых текстов вместо 247 [263]), появлялись также новые виды атак на DES (например, атака, позволяющая вычислить ключ высокоточным облучением аппаратного шифратора и последующим анализом ошибок шифрования [81]). Однако стоит сказать, что все эти атаки требуют наличия огромного количества пар «открытый текст— шифртекст», получение которых на практике является настолько трудоемкой операцией, что наиболее простой атакой на DES считается полный перебор возможных вариантов ключа шифрования [263].

Кроме того, практически сразу после появления DES были обнаружены следующие проблемы с ключами шифрования DES [28].

?     4 ключа из возможных 256 ключей алгоритма являются слабыми (т. е. не обеспечивают требуемой стойкости при зашифровывании). Это ключи, в которых все биты какой-либо из половин расширяемого ключа (С или D на рис. 3.59) являются нулевыми или единичными. В этом случае все ключи раундов будут одинаковыми.

?     6 пар ключей являются эквивалентными (т. е. информация, зашифрованная одним ключом из пары, расшифровывается другим ключом той же пары), например, пара ключей E0FEE0FEF1FEF1FE и FEE0FEE0FEE1 FEE 1 (шестнадцатеричные значения). Процедура расширения такого ключа вместо 16 ключей раундов вырабатывает всего 2 различных ключа.

?     48 ключей являются «возможно слабыми», их полный список приведен в [28]. Возможно слабые ключи при их расширении дают только 4 различных ключа раундов, каждый из которых используется при шифровании по 4 раза.

? Существует свойство комплементарности ключей: если   где:

•                     — зашифровывание алгоритмом DES блока открытого текста М\

•                  С — полученный в результате шифртекст; то:

где— побитовое дополнение к х (т. е. величина, полученная путем замены всех битовых нулей значения х на единицы, и наоборот). Считается, что свойство комплементарности ключей не является слабостью, однако оно приводит к тому факту, что для полного перебора ключей DES требуется 255, а не 256 попыток.

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

Достаточно много криптоаналитических исследований было посвящено алгоритму DES с уменьшенным количеством раундов. Считается, что количество раундов любого многораундового алгоритма шифрования можно уменьшать до определенных пределов, достигая оптимального для конкретных применений соотношения «скорость шифрования/криптостойкость». Однако алгоритм DES (как и многие другие алгоритмы шифрования) подвержен существенному снижению криптостойкости при уменьшении количества раундов — исследования DES с различным количеством раундов, меньшим 16 (например [75, 165, 249, 309]), показали: «Атаки на алгоритмы с уменьшенным количеством раундов доказывают, что не стоит уменьшать количество раундов алгоритма с целью увеличения производительности» [309].

Криптоанализ алгоритма DES, как полного, так и с уменьшенным количеством раундов, активно ведется и в XXI веке, несмотря на то, что DES уже не является стандартом шифрования (например, [122, 123, 165, 315]). Все-таки вряд ли будет преувеличением утверждение, что DES по-прежнему остается самым используемым из алгоритмов симметричного шифрования в мире (особенно с учетом распространенности описанного далее Triple DES). Поэтому криптоанализ DES и его вариантов, как сказано в [123], будет актуален еще 10-20 лет.

В своей работе [27], адресованной начинающим криптоаналитикам, Брюс Шнайер рекомендует тренироваться или оттачивать мастерство криптоанализа, в том числе на алгоритме DES и некоторых его вариантах.

Продолжение истории алгоритма

Как было сказано выше, несмотря на массированный криптоанализ, не было изобретено достаточно практичного алгоритма вскрытия DES быстрее, чем полным перебором 255 (с учетом свойства комплементарности) возможных вариантов ключа. Причем с развитием компьютерной техники полный перебор ключа становился все более реальным. В 1993 г. Майкл Винер (Michael Wiener) разработал принципы конструкции специализированного компьютера стоимостью порядка 1 ООО ООО долларов, способного перебрать ключи DES за 3,5 часа. Причем такой компьютер имел возможность наращивания — при не фантастических для крупной организации или спецслужбы затратах порядка 10 ООО ООО долларов полный перебор ключа DES должен был занять не более 21 минуты [394]. Абсолютно ясно, что сейчас такой компьютер стоил бы в десятки раз дешевле [315].

С другой стороны, при принятии DES в качестве стандарта планировался его пересмотр каждые 5 лет. Поэтому данный стандарт пересматривался в 1983, 1988, 1993 и 1999 гг. Последний пересмотр происходил уже после старта конкурса AES, целью которого был выбор нового стандарта шифрования США вместо DES (см. разд. 2.1). В 1999 г. уже невозможно было использовать DES для серьезной защиты из-за его короткого ключа, к этому времени уже были прецеденты вскрытия DES полным перебором ключа с использованием распределенных вычислений. Поэтому текущая версия стандарта [150] устанавливает в качестве стандарта шифрования Triple DES, а собственно DES разрешалось использовать только в целях совместимости с действующими DES-шифраторами, причем везде, где это возможно, рекомендовалось осуществить переход на Triple DES.

Стоит сказать и о том, что все время использования алгоритма DES существовал слух о том, что при его доработке АНБ США внедрило в алгоритм некую лазейку, с помощью которой АНБ могло бы вскрывать каким-либо методом зашифрованные алгоритмом DES сообщения [28, 241, 330]. Особенное подозрение у криптологического сообщества вызывали таблицы замен. Однако за все время использования DES никому не удалось полностью доказать как наличие, так и отсутствие подобных лазеек, хотя различных утверждений на данную тему было великое множество (например, в [249]). Кроме того, авторитетные эксперты высказали мнение, что, не считая уменьшения размера ключа, доработка алгоритма Lucifer серьезно усилила полученный алгоритм DES против дифференциального криптоанализа [48].

Короткий ключ алгоритма DES и описанные выше некритичные уязвимости алгоритма подтолкнули специалистов по криптологии на изобретение множества вариантов алгоритма DES, причем некоторые из них оказались достаточно успешными. «Потомки» алгоритма DES заслуживают отдельного рассмотрения.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100