Preimage attack on MD4 hash function as a problem of parallel sat-based cryptanalysis

В статье исследуется задача обращения криптографической хеш-функции MD4, разработанной Р. Ривестом в 1990 году. Через MD4-k обозначается вариант данной функции, в которой параметр k обозначает количество шагов используемых для вычисления хеш-значения (при k=48 имеем полнораундовую версию MD4). В работах Г. Доббертина было показано, что хеш-функция MD4-32 не является односторонней, т.е. для нее может быть решена задача обращения. С этой целью к уравнениям, описывающим конкретные шаги алгоритма вычисления данной функции, были добавлены дополнительные условия на значения некоторых переменных сцепления (chaining variables). Эти дополнительные условия позволили за приемлемое время решить задачу обращения хеш-функции MD4-32 путем решения соответствующей системы уравнений. Основным результатом представляемой статьи является автоматический вывод условий подобных условиям Доббертина (“Dobbertin’s conditions”) при помощи параллельных алгоритмов решения проблемы булевой выполнимости (SAT). Также с использованием данных алгоритмов были решены некоторые задачи обращения функции MD4-k для значений параметра k от 31 до 39 включительно. Стоит отметить, что предложенный метод существенно превосходит по эффективности описанные ранее подходы к решению данной проблемы.