Вычислительные методы в дискретной математике

Исследование влияния Доббертиновских ограничений на поиск прообразов неполнораундовой функции сжатия MD4 при помощи SAT-подхода

С. Е. Кочемазов, О. С. Заикин


Аннотация: MD4 — одна из первых криптографических хеш-функций. В силу ряда архитектурных особенностей функция сжатия MD4 крайне уязвима для поиска коллизий и в меньшей степени — для поиска прообразов. Ключевую роль в демонстрации слабости MD4 сыграли исследования Г. Доббертина. Им предложены специальные ограничения, которые позволили быстро обращать 32 раунда данной функции. Позднее эти ограничения уже в контексте SAT-подхода позволили решить задачу обращения функции сжатия MD4 до 43 шагов включительно. Мы рассматриваем, как влияют Доббертиновские ограничения на эту задачу в контексте SAT-подхода, и предлагаем новую оценку времени криптоанализа MD4-44.

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

УДК: 004.8

DOI: 10.17223/2226308X/18/57