240
ларов. В 1999 году испытание DES было пройдено всего за 22 часа совместными
усилиями Deep Crack и distributed.net. Сегодня самым ультрасовременным взла-
мывателем DES является DES cracking box от компании PICO Computing, который
использует 48 FPGA и может найти ключ DES за приблизительно 23 часа.
Компромиссы пространства/времени, описанные в Разделе 5.4.3 показывают, что
атаки с полным перебором могут быть ускорены предварительной обработкой и до-
полнительной памятью. Из-за короткой длины ключа DES компромиссы пространства/
времени могут быть особенно эффективны. В частности, используя предварительную
обработку, можно генерировать таблицу размером в несколько терабайт, которая затем
сможет извлечь ключ DES с высокой вероятностью из одной входной/выходной пары,
использовав приблизительно 238 вычислений DES (на это могут уйти буквально ми-
нуты). Нижняя грань - это то, что DES имеет ключ, который очень и очень короток и не
может сегодня считаться защищенным для любого серьезного применения.
Вторая причина для беспокойства - это относительно короткая длина блока DES.
Короткая длина блока является проблемой, потому что конкретная защита многих кон-
струкций на основе блочного шифра зависит от длины блока, даже если используемый
шифр является «безупречным.» Например, доказательство защиты для режима CTR
(сравните С Теоремой 3.32) показывает, что даже когда полностью случайная функция
используется, атакующий может взломать защиту такой схемы шифрования с вероят-
ностью 2q2/2A , если он получит q пар открытого текста/шифротекста. В случае с DES,
где A = 64, это означает, что, если атакующий получит только лишь q = 230 пар откры-
того текста/шифротекста, защита будет взломана с высокой вероятностью.
Получить
пары открытого текста/шифротекста довольно легко, если злоумышленник перехваты-
вает
шифрование сообщений ,
содержащее известные заголовки, избыточности и пр.
Незащищенность DES не имеет по сути ничего общего со своей конструкцией,
но все дело в его короткой длине ключа (и в меньшей степени, короткой длине бло-
ка). Нужно отдать должное разработчикам DES, которые, казалось, смогли создать
почти безупречный блочный шифр (несмотря на его слишком короткий ключ). Так
как DES сама по себе не имеет существенных структурных слабостей, есть смысл
использовать DES в качестве структурного элемента при создании блочных шиф-
ров с более длинными ключами. Мы рассмотрим это позже в Разделе 6.2.4.
Замена DES, Advanced Encryption Standard (AES), о котором
речь пойдет да-
лее в этой главе, был четко разработан с учетом проблем, касающихся короткой
длины ключа и короткой дляны блока DES. AES поддерживает 128-, 192- или
256-битные ключи, а также длину блока 128 бит.
_________________________________________________________
4В 1977 году компьютер, который мог бы взломать DES за один день, был оценен в 20 мил-
лионов долларов.
241
Атаки, которые были более продвинуты, чем применение «грубой силы» к
DES впервые были продемонстрированы в начале 1990-х Бигамом (Biham) и
Шамиром (Shamir), которые разработали метод под названием дифференци-
альный криптоанализ. Их атака продолжалась по времени 237 и требовала 247
подобранных открыты текстов. В то время, как атака была прорывом с теорети-
ческой точки зрения, на практике же она не мела никакого смысла, поскольку
трудно представить себе реалистичный сценарий, когда злоумышленник может
получить настолько много шифрований подобранного открытого текста.
Интересно отметить, что работа Бигама и Шамира
указала на то, что S-блоки
DES были разработаны исключительно для того, чтобы выдерживать дифферен-
циальный криптоанализ, как будто дифференциальный
криптоанализ был из-
вестен разработчиками DES (хотя они в этом не признавались). После того, как
Бигам и Шамир обнародовали свои результаты, подозрения были подтверждены.
Линейный криптоанализ был разработан Мацуи (Matsui) в середине 90-х
годов и также успешно применялся к DES. Преимущество такой атаки в том,
чтобы скорее использовать известные открытые тексты, чем подобранные от-
крытые тексты. Тем не менее, количество необходимых пар открытого текста/
шифртекста, около 243, все еще велико.
Мы кратко описали дифференциальный и линейный криптоанализы в Раз-
деле 6.2.6.
Достарыңызбен бөлісу: