Оптимизации криптоанализа SHA-1 позволили просчитать коллизии до 73 раундов

В 2007 году исследователи Christophe De Canni`re, Florian Mendel и Christian Rechberger опубликовали в своей работе Collisions for 70-step SHA-1: On the Full Cost of Collision Search методику автоматизированного поиска коллизий в SHA-1 для усечённой 70-раундовой версии этой хэш-функции соответственно.

Автор Е.А.Гречников из Московского Государственного Университета предложил некоторые улучшения данного метода, которые позволили получить лучшие на сегодняшний момент результаты для 72 и 73 раундов. Небольшой отчёт приведен в работе "Collisions for 72-step and 73-step SHA-1: Improvements in the Method of Characteristics".

Интересной является сравнительная лёгкость получения коллизий на вычислительном кластере "Ломоносов", который принадлежит МГУ. Для первоначального нахождения 72-раундовой коллизии вычислительные затраты оценивались в 2^52.9 узлов обхода или эквивалентно 2^47.6 оценок функций сжатия (не считая влияния дополнительных операций для формирования входных значений и тестирования выходных данных). После всех оптимизаций итоговый поиск коллизий во втором блоке занял 13748 секунд (менее 4 часов) на 8192 работающих ядрах процессоров. Поиск не был приостановлен, и в течение 8 часов удалось найти ещё две коллизии.

После успеха в четырёхчасовом поиске для 72-раундовых коллизий стало ясно, что возможно нахождение и 73-раундовых коллизий без создания помех другим пользователям кластера. На самом деле увеличение количества раундов с 72 до 73 потребовало восьмикратного увеличения затрат на работу с L-характеристикой (это часть алгоритма, описанного автором в работе). Новые оценки вычислительных затрат составляли 2^56.0 узлов обхода (2^50.7 проверок функций сжатия). Фактическое время поиска второго блока оказалось значительно ниже ожидаемого, всего лишь 2693 секунды (меньше часа) на 16384 ядрах процессоров просто за счёт некоторой доли везения.

Данные результаты служат очередной иллюстрацией прогресса в области приближения практического взлома алгоритма SHA-1, который состоит из 80 раундов. Полный теоретический взлом 80-раундовой версии был впервые представлен в 2005 году исследователями из Шандонгского университета в Китае Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu.

В настоящее время НИСТ (Национальный Институт Стандартов и Технологий США) рекомендует вывести из употребления SHA-1 во всех системах в течение 2010 года и временно использовать алгоритмы семейства SHA-2 до принятия стандарта SHS SHA-3.

Источник