The inversion of cryptographic hash functions using unbalanced approximations of round functions.pdf Хеш-функция MD4 [1] представляет собой один из первых примеров криптографических хеш-функций, построенных на основе конструкции Меркля - Дамгарда [2, 3]. В [4] данная функция была полностью скомпрометирована по отношению к атаке поиска коллизий. Однако для задачи обращения полнораундовой MD4 эффективных алгоритмов не предложено до сих пор. Насколько нам известно, все результаты по обращению неполнораундовых версий MD4 так или иначе основываются на идеях, высказанных Г. Доббертином [5]. В данной работе показано, что двухраундовый вариант MD4 (то есть вариант, включающий 32 шага базового алгоритма) не является стойким к атаке поиска прообраза известного хеша. Основная идея работы [5] состоит в использовании дополнительных условий, связывающих переменные сцепления на определённых шагах. Далее для условий данного типа мы применяем термин «условия Доббертина». Насколько можно судить из открытых источников, наилучший на данный момент результат для рассматриваемой задачи - это нахождение за разумное время прообразов хешей, порождаемых 39-шаговой версией MD4, которую далее будем обозначать MD4-39. Впервые этот результат приведён в [6], где для решения задачи использован SAT-подход. Некоторый вариант условий Доббертина добавлялся в пропозициональную кодировку алгоритма в виде дополнительных ограничений. По утверждению авторов [6], на решение одной задачи уходит около 8 часов работы SAT-решателя minisat на ПК с весьма мощным на тот момент процессором. В работе [7] результаты по обращению 39-шагового варианта MD4 улучшены и описан процесс автоматического синтеза условий Доббертина при помощи параллельного алгоритма решения задачи о булевой выполнимости. В настоящей работе представлены результаты по обращению неполнораундовых версий MD4 с использованием новой техники. Суть этой техники состоит в замене некоторых подфункций несбалансированными булевыми функциями, использование которых, по нашему мнению, должно делать задачу обращения соответствующего варианта рассматриваемой хеш-функции проще для SAT-решателя. Это предположение полностью подтверждается на практике. Будем называть проблему обращения варианта рассматриваемой хеш-функции, в котором подфункции некоторых раундовых функций заменены несбалансированными булевыми функциями, интерполированной задачей обращения. Кратко опишем принцип построения несбалансированных булевых функций. Везде далее процесс перехода от исходной сбалансированной булевой функции к несбалансированной будем называть модификацией. Напомним, что в MD4 вычисление значения переменной сцепления на i-м шаге описывается формулой Qi = (Qi-4 + Фг(ф-1,фг-2,фг-з) + mp(i) + ki)

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