Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Безопасность DES
После почти 30 лет интенсивного изучения наилучшей известной практической атаки , на DES все еще остается полный перебор его пространства ключей. (Мы обсудим кое-какие важные теоретические атаки в Разделе 6.2.6 Эти атаки требуют большого количества входных/выходных пар, которые было бы тяжело получить для атаки на настоящую систему, которая использует DES.) К несчастью, 56-бит- ная длина ключа DES достаточно коротка, чтобы полный перебор всех 256 вари- антов ключей был осуществим в наше время. Уже в конце 1970-х существовали сильные возражения касательно выбора такого короткого ключа для DES. В те времена возражение было теоретическим, так как вычислительная мощность, не- обходимая, чтобы перебрать такое количество ключей была, в общем, недоступна. 4 Целесообразность атаки с применением «грубой силы» на DES, однако, была про- демонстрирована в 1997, когда первый набор испытаний DES, установленный RSA Security, был пройден группой DESCHALL Project с использованием нескольких тысяч компьютеров координированных по интернету; вычисление заняло 96 дней. Второе испытание было пройдено в следующем году всего за 41 день участниками проекта distributed.net. Серьезный прорыв случился в 1998, когда третье испытание было пройдено всего за 56 часов. Этот впечатляющий подвиг был осуществлен по- средством узкоспециализированной машины для взлома DES под названием Deep Crack , которая была построена Electronic Frontier Foundation и стоила 250000 дол- 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. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|