id: Гость   вход   регистрация
текущее время 10:07 23/11/2017
Владелец: unknown (создано 14/09/2006 22:50), редакция от 10/03/2007 16:08 (автор: SATtva) Печать
Категории: криптография, криптоанализ, алгоритмы, хэширование, сайт проекта, статьи, атаки, разное, события
https://www.pgpru.com/Библиотека/Статьи/КриптоанализХэшФункцийПрогрессВнушаетОпасения
создать
просмотр
редакции
ссылки

Криптоанализ хэш-функций – прогресс внушает опасения

Предыстория


Хэш-функции ялвляются важной частью криптографических протоколов. Их используют и для проверки подлинности открытых ключей, сертификатов, подписанных документов, данных в сеансах связи (HMAC-аутентификация), для проверки введенных паролей в операционных системах и для генерации случайных чисел и сеансовых ключей и т.д. Поэтому они сразу стали предметом множества исследований. Самый простой тип уязвимости хэшей – коллизия (возможность подобрать два одинаковых выходных значения для неодинаковых входных). Если для функции с выходом n бит это удасться сделать быстрее, чем за n/2 бит – она уязвима к коллизиям.


  • 1992 – Berson находит дифференциальные характеристики, достаточные для поиска коллизий на каждом отдельном раунде хэш-функции MD5 (но бесполезные для нескольких раундов вместе).
  • 1993 – Boer и Bosselers находят псевдоколлизии на отдельном раунде MD5 с "подогнанным" под конкретный случай значением внутреннего вектора инициализации – переменной сцепления.
  • 1996 – Dobbertin находит коллизии для функции сжатия без использования вектора инициализации.

Обратите внимание на тенденцию: от чисто теоретических атак движение идет к более практическим взломам, но это все еще искусственно созданные примеры.


В 1993г. выходит алгоритм SHA, разработанный совместно NIST и АНБ. В 1995г. его пересматривают: добавляют циклический сдвиг в функцию раунда без объяснения причины (!) – напоминает историю алгоритма DES.


Тем временем в Европе совместно с упомянутым выше Доббертином разрабатывают хэш-функцию RIPEMD. Ее делают не совсем похожей на MD5 или SHA – две ветви сети обрабатываются двумя разными функциями для большей защищенности.


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

Наши дни

01.04.2004

Длина хэш функции MD5 – 128 бит. Недостаточно для защиты от простого перебора. Чтобы доказать, что простой перебор 264 вариантов возможен, запускается проект www.md5crk.com. (Основан компанией Certainkey.)

15.07.2004

Обещан символический приз $10.000 за нахождение коллизии MD5.

22.07.2004

Известный криптограф Эли Бихам совместно с Рафи Ченом публикуют сенсационную работу "Предколлизии в SHA-0" ("Near-Collisions of SHA-0"). Удается "протащить" коллизию через множество раундов SHA-0, предшественника SHA-1 c меньшим количеством раундов.

12.08.2004

Найдена полная коллизия SHA-0. Потребовалось 50.000 часов машинного времени!

16.08.2004

Китайские исследователи утверждают, что нашли способ быстрого подбора коллизий для HAVAL, RIPEMD и MD5. Сначала в их примерах были ошибки, затем они исправляют свою статью и... в Сети появляются файлы, которых до этого официально не мог видеть ни один человек на Земле (ну разве что тайно) – два разных файла, создающих одинаковое хэш-значение MD5! Удивленные пользователи скачивают файлы с примерами и убеждаются, что это все правда.


На подбор коллизии по "китайскому методу" (его подробности, кстати, китайцы не хотят публиковать целиком) уходит от 15 секунд до пары часов на персональном компьютере! Взлом старой версии MD4 возможен вообще без вычислительных средств – по определенному правилу все можно посчитать "в уме" или на бумаге.


На специальной конференции CRYPTO'2004 в Санта-Барбаре идут доклады на тему последних событий. Впервые за двадцать с лишним лет это все транслируется в Интернете.

18.08.2004

На конференции CRYPTO'2004 сразу после доклада Эли Бихама и Рафи Чена идет выступление Антуана Жу "Мультиколлизии в итеративных хэш-функциях. Применение к каскадным конструкциям" ("Multicollisions in iterated hash functions. Application to cascaded constructions"). Это тот самый исследователь, который руководил практической атакой на SHA-0 за 251 операций. Он утверждает, что дизайн всех хэш-функций потенциально ненадежен. Он рассматривает модель идеальной случайной функции и сравнивает ее с реальными хэш-аналогами. В реальной хэш-функции сообщение после дополнений итеративно проходит через функцию сжатия в каждом раунде. Это позволяет использовать так называемые мультиколлизии. Нужно только подгонять коллизии отдельных блоков входного сообщения к внутренним коллизиям раундов.


Чтобы не вдаваться в сложности теории, которая еще требует проверки и осмысления, перейдем сразу к предварительным выводам:


  1. Работа на поиск коллизий значительно меньше, чем считалась ранее.
  2. Увеличение числа раундов не спасает.
  3. Потенциально возможно создание не только коллизий, но и целенаправленных "подделок" – но это пока еще чистая спекуляция.
  4. Самое интересное: комбинирование хэш-функций не увеличивает их стойкости! Выражение H(x) = SHA1(x) || RIPEMD160(x) дает нам в сумме не 320-битную хэш-функцию, а все еще 160-битную. Это чувствительный удар по протоколам разворачивания ключевого материала в SSL и расчета аутентификационных значений в HMAC. Единственная практическая польза от конкатенации в протоколе SSL – если будет взломана одна хэш-функция, то вторая будет работать.

22.08.2004

По материалам конференции выпускается работа "Пути исправления функций семейства SHA-2" ("On Corrective Patterns for the SHA-2 Family", Philip Hawkes, Michael Paddon, Gregory G. Rose). Работа довольно сложная и обширная, несмотря на предварительный характер (и когда ее только успели доделать? Наверное, авторам пришлось провести бессонные ночи). Идея в следующем: в стандарте SHA-2 использована слишком простая схема увеличения выходного значения хэш-функции. Самые стойкие на сегодня SHA-224, 256, 384, 512 могут быть успешно атакованы по новым методикам. Авторы предупреждают – практических путей им неизвестно, но начальные предпосылки уже достаточно серьезны.

Предварительные выводы


Пока полученные результаты все еще не критичны – на практике их невозможно применить для подмены ключей, подделки контрактов. Но это только то, что общеизвестно на данный момент. Отсутствие криптостойкости MD5 можно считать доказанным. SHA-1 – держится, но вероятно, что после атаки на SHA-0 она не сможет держатся очень долго. SHA-256 и SHA-512 пока защищены очень большим выходным значением, но это уже не будет иметь серьезного значения, если подтвердятся выводы исследователей от 22 августа. Комбинировать хэш-функции между собой тоже не выход.


Целый класс хэш-функций оказался потенциально нестоек. Для экономии в них применяли иные методы "создания нелинейности", чем в блочных шифрах. И, кажется, этот подход себя отчасти не оправдал.


Удивительно, что комбинация линейных операций считалась достаточной для создания стойкой функции, а методы криптоанализа, применимые к функциям шифрования, считались неприменимыми к функциям сжатия.


Более точные выводы делать пока рано.

Альтернативы и поиски выхода


В проходившем в Европе конкурсе крипто NESSI (который, к сожалению, не вызвал такого интереса, как американский AES) была предложена хэш-функция WHIRLPOOL; возможно, использованные в ней более новые подходы окажутся и более адекватными современным требованиям. Она похожа на Rijndael (или Square) – с активным применением вычислений в конечных полях. Но пока у этой функции нет такого авторитета по количеству исследований. Вполне может оказаться, что токого рода конструкции уязвимы к специально подобранным алгебраическим атакам.


В качестве хэш-функций можно использовать и блочные шифры – схема Дэвиса-Майера (в том чиле AES-HASH), российский стандарт ГОСТ. Правда, до недавнего момента эти схемы считались менее стойкими, чем сами хэш-функции.


Возможно будут созданы новые хэш-функции с улучшенными свойствами.

... История продолжается...


© 2004 unknown

 
Комментариев нет [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3