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

Нахождение прообраза пяти раундов криптографической хеш-функции JH-256 при помощи параллельного SAT-решателя

О. С. Заикин


Аннотация: В 2010 г. криптографическая хеш-функция JH-256 вышла в финал конкурса SHA-3 в составе семейства JH. Основным компонентом JH-256 является 42-раундовая функция сжатия. Рассматривается задача нахождения прообраза нулевого хеша, вычисленного ослабленным вариантом JH-256, в котором используются только первые пять раундов функции сжатия. Данная задача была сведена к экземпляру проблемы булевой выполнимости (SAT). На построенной КНФ были запущены все параллельные SAT-решатели, принявшие участие в конкурсе SAT Competition 2024. В результате экспериментов один из решателей смог найти прообраз за разумное время. Ранее на практике прообраз был найден максимум для первых четырёх раундов JH-256.

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

УДК: 004.8

DOI: 10.17223/2226308X/18/56