Грибанова И.А.   Заикин О.С.   Кочемазов С.Е.   Отпущенников И.В.   Семёнов А.А.  

Исследование задач обращения криптографических хеш-функций семейства MD при помощи алгоритмов решения проблемы булевой выполнимости

Докладчик: Заикин О.С.

В статье будут представлены результаты применения современных SAT решателей к задачам обращения криптографических хеш-функций семейства MD. В частности, будут рассмотрены задачи поиска прообразов и поиска коллизий для хеш-функций MD4 и MD5. Хеш-функцией называется тотальная алгоритмически вычислимая дискретная функция вида \chi:{0,1}^*\rightarrow{0,1}^C, где C– некоторая константа, называемая длиной хеша. При n>C в {0,1}^* обязательно найдутся такие x_1,x_2\in{0,1}^n, x_1\neq x_2, что имеет место \chi(x_1 )=\chi(x_2). В этом случае говорят, что сообщения x_1,x_2 образуют коллизию. К криптографическим хеш-функциям предъявляется ряд дополнительных требований, заключающиеся в том, что задачи, так или иначе связанные с обращением хеш-функции, должны быть вычислительно трудными. Иными словами, трудной должна быть как задача поиска по известному хешу его прообраза (собственно задача обращения), так и задача поиска коллизий.

Мы рассмотрим задачи обращения и поиска коллизий для известных хеш-функций MD4 и MD5. Для решения этих задач мы используем подход, основанный на их сведении к проблеме булевой выполнимости (SAT) с последующим применением современных SAT-решателей. Пропозициональные кодировки алгоритмов, задающих рассматриваемые функции, реализуется с использованием системы пропозиционального кодирования Transalg. Данная система позволяет эффективно добавлять к пропозициональным кодам алгоритмов MD4 и MD5 дополнительные условия в виде дифференциальных путей X.Wang (для задачи поиска коллизий) или условий H.Dobbertin (для задачи обращения). Предложенные нами алгоритмы по эффективности решения соответствующих задач превосходят близкие по смыслу, изложенные в статьях других авторов. Кроме этого, используя разработанные алгоритмы, нам удалось построить новые семейства двухблоковых коллизий для MD5, а также построить новые дифференциальные пути в задаче поиска одноблоковых коллизий MD4.