RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Южно-Уральского государственного университета. Серия «Вычислительная математика и информатика» // Архив

Вестн. ЮУрГУ. Сер. Выч. матем. информ., 2017, том 6, выпуск 3, страницы 16–27 (Mi vyurv169)

Эта публикация цитируется в 1 статье

Дискретная математика и математическая кибернетика

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

[Поиск прообразов хеш-функции MD4 как проблема параллельного логического криптоанализа]

I. A. Gribanova, O. S. Zaikin, I. V. Otpushchennikov, A. A. Semenov

Matrosov Institute for System Dynamics and Control Theory SB RAS (Lermontova st. 134, Irkutsk, 664033, Russia)

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

Ключевые слова: криптоанализ, хеш-функции, задача обращения, параллельные вычисления.

УДК: 004.056.55, 003.26

Поступила в редакцию: 04.05.2017

Язык публикации: английский

DOI: 10.14529/cmse170302



Реферативные базы данных:


© МИАН, 2024