Estimates of collision resistance complexity for the hash function RIPEMD.pdf Хэш-функция RIPEMD [1] была разработана в 1992 г. в рамках европейского про-екта RIPE (RACE Integrity Primitives Evaluation) как альтернатива популярной нато время хэш-функции MD4 [2]. Фактически, функция сжатия RIPEMD представля-ет собой две работающие параллельно функции сжатия MD4 (левая и правая вет-ки RIPEMD), отличающиеся друг от друга аддитивными константами. Уже в 1997г.Х. Доббертин [3] нашел коллизии для урезанной до двух раундов версии RIPEMD, ав 2001 г. К. Дебарт и Г. Гилберт [4] показали, что по отдельности и левая и правая вет-ки RIPEMD не устойчивы к коллизиям. Для полной версии RIPEMD коллизии былипостроены лишь в 2004 г. и предъявлены в знаменитой заметке К. Вонг и др. [5], чутьпозднее те же авторы в [6] опубликовали детали своего алгоритма поиска коллизийи привели оценку средней трудоёмкости, которая является наилучшей на сегодняш-ний день. Однако корректность этой оценки вызывает сомнения в силу краткого инедетального изложения алгоритма.К текущему моменту разработаны усиленные варианты хэш-функции RIPEMD:RIPEMD-128, RIPEMD-160, RIPEMD-256, RIPEMD-320 [7, 8], которые рекомендуют-ся к использованию во многих международных и национальных стандартах, в част-ности ISO/IEC 10118-3:2004. Хэш-функции семейства RIPEMD-x получили широкоераспространение и на практике, например RIPEMD-160 используется для генерацииключа шифрования на основе пароля в популярном программном комплексе созданияшифрованных дисков TrueCrypt [9]. Поскольку все усиленные варианты наследуютидеологию первой конструкции RIPEMD, её подробный криптоанализ и получениеточных оценок стойкости по-прежнему остается актуальным.В настоящей работе восстанавливаются опущенные детали алгоритма [6] поискаколлизий для RIPEMD и проводится экспериментальная проверка заявленной в [6]трудоёмкости этого алгоритма. Такая необходимость возникает в силу того, что в [6]отсутствует полное обоснование оценок трудоёмкости, а приводятся лишь основныеидеи алгоритма, которые состоят в следующем. Строится приводящая к коллизии диф-ференциальная характеристика (AM, AQ), где AM - набор разностей между сооб-щениями, а AQ - набор разностей между промежуточными переменными сцепления.Выписывается некоторый набор достаточных условий на промежуточные переменныесцепления Q и неявно утверждается, что если для одного сообщения M все промежу-точные значения переменныхсцепления удовлетворяют этим условиям, то автомати-чески другое сообщение M + AM образует коллизию с M. Затем используются дветехники для подбора такого сообщения M, что при вычислении его хэш-значения всепеременные сцепления удовлетворяют набору достаточных условий. Первая техниканазывается однократной модификацией сообщения и позволяет добиться выполнениядостаточных условий на первых 16 шагах функции сжатия. Сложность этого этапа,как неявно предполагают авторы [6], составляет от 1 до 4 условных операций, гдеза одну условную операцию принимается одно вычисление функции сжатия. Однаков отличие от случая хэш-функции MD4, для которой это неявное предположение спра-ведливо, сложность этого этапа для RIPEMD при нашей экспериментальной проверкеоказалась равной в среднем 2i6,49. Вторая техника называется многократной модифи-кацией сообщения. Она, по заверению авторов [6], позволяет добиться выполнения наостальных шагах всех оставшихся условий, за исключением «примерно 16», что да-ёт вероятность успеха второго этапа около 2- i 6 . При этом сложность второго этапаполагается равной от 1 до 4 условных операций.Таким образом, по полученным экспериментальным данным можно вывести ниж-нюю оценку средней трудоёмкости алгоритма [6]. Она составляет не менее 232,49 услов-ных операций, что примерно в квадрат раз больше заявленной в [6].Косвенным доказательством как наличия проблем при восстановлении деталейалгоритма [6], так и его высокой средней трудоёмкости (гораздо выше заявленнойв [6]) служит тот факт, что, насколько известно авторам, в Интернете отсутству-ют программные реализации данного алгоритма поиска коллизий для хэш-функцииRIPEMD, в то время как для хэш-функций MD4 и MD5 они есть [10].

Скачать электронную версию публикации