Задачи поиска коллизий для криптографических хеш-функций семейства MD как варианты задачи о булевой выполнимости
Богачкова И.А., Заикин О.С., Кочемазов С.Е., Отпущенников И.В., Семенов А.А., Хамисов О.О.

Рассмотрена реализация разностной атаки на криптографические хеш-функции MD4 (Message Digest 4) и MD5 (Message Digest 5) через сведение задачи поиска коллизий для этих хеш-функций к задаче о булевой выполнимости (SAT, SATisfiability). Новизна полученных результатов заключается в том, что предложены существенно более экономные (в сравнении с известными) SAT-кодировки рассматриваемых алгоритмов, а также в использовании для решения полученных SAT-задач современных многопоточных и параллельных SAT-решателей. Задачи поиска одноблоковых коллизий для MD4 в данной постановке оказались чрезвычайно простыми. Кроме того, найдены несколько десятков двухблоковых коллизий для MD5. В процессе соответствующих вычислительных экспериментов определен некоторый класс сообщений, дающих коллизии: построено множество пар дающих коллизии сообщений, у которых первые 10 байтов нулевые.

Ключевые слова: криптографические хеш-функции, коллизии, разностные атаки, задача о булевой выполнимости (SAT), CDCL (Conflict-Driven Clause Learning), параллельные SAT-решатели.

Название статьи, аннотация и ключевые слова на английском языке

  • Богачкова И.А. – Иркутский государственный университет, Институт математики, экономики и информатики, бульвар Гагарина, 20, 664003, г. Иркутск; cтудент, e-mail: the42dimension@gmail.com
  • Заикин О.С. – Институт динамики систем и теории управления имени В.М. Матросова, ул. Лермонтова, 134, 664033, г. Иркутск; науч. сотр., e-mail: zaikin.icc@gmail.com
  • Кочемазов С.Е. – Институт динамики систем и теории управления имени В.М. Матросова, ул. Лермонтова, 134, 664033, г. Иркутск; программист, e-mail: veinamond@gmail.com
  • Отпущенников И.В. – Институт динамики систем и теории управления имени В.М. Матросова, ул. Лермонтова, 134, 664033, г. Иркутск; науч. сотр., e-mail: otilya@yandex.ru
  • Семенов А.А. – Институт динамики систем и теории управления имени В.М. Матросова, ул. Лермонтова, 134, 664033, г. Иркутск; зав. лабораторией, e-mail: biclop.rambler@yandex.ru
  • Хамисов О.О. – Иркутский государственный университет, Институт математики, экономики и информатики, бульвар Гагарина, 20, 664003, г. Иркутск; cтудент, e-mail: cygx151@gmail.com