Application of algorithms solving sat problem to cryptanalysis of hash functions of MD family.pdf Хэш-функциями называются отображения вида х : {0,1}* ^ {0,1}c, где c - некоторая натуральная константа. Хэш-функции используются в целом ряде разделов Computer Science для ускорения работы с данными. В криптографии хэш-функции являются основой большого числа различных криптосистем и протоколов. В отличие от «обычных» хэш-функций, к криптографическим хэш-функциям предъявляются дополнительные условия, требующие, чтобы задачи, связанные с обращением этих функций, были вычислительно трудными. Более точно, трудной должна быть собственно задача обращения: по известному значению хэша y найти вход x (обычно некоторой фиксированной длины), такой, что х(х) = у. Стандартным является также требование сложности задачи поиска коллизий. Поскольку константа c фиксирована, то для произвольного n > c отображение х : {0,1}n ^ {0,1}c не может быть биективным. Если при этом х определена всюду на {0,1}n, то существуют такие различные x1,x2 G {0,1}n, что х(х1) = х(х2). В этом случае говорят, что пара сообщений x1,x2 образует коллизию. Итак, еще одно требование к криптографическим хэш-функциям состоит в том, что задача поиска коллизий должна быть вычислительно трудной. Одной из наиболее распространённых основ для криптографических хэш-функций является конструкция Меркля - Дамгарда [1, 2]. В соответствии с данной конструкцией двоичный вход x разбивается на блоки фиксированной длины n (этот параметр задаётся в спецификации алгоритма). При необходимости исходное сообщение дополняется незначащей информацией для получения слова, длина которого кратна n. Пусть х - входное слово, разбитое на N блоков, каждый из которых имеет длину n: х = Mi| ... |Mn (подразумевается конкатенация блоков). Процесс построения хэша y = х(х) -это итеративная процедура вычисления «функции сжатия» (compression function): Xi = f (Xi-i,Mj), i G {1,..., N}, XN = y. Для произвольного i G {1,..., N} слово Xi имеет длину c, которая задаётся в спецификации алгоритма; там же задаётся начальное значение (Initial Value) Xo. Функция сжатия f - это обычно сложная функция, представляемая в виде суперпозиции «ра-ундовых» функций. Наиболее известными криптографическими хэш-функции, базирующимися на конструкции Меркля - Дамгарда, являются представители семейств MD [3] и SHA. В хэш-функциях MD4 и MD5 c = 128, а длина одного блока входного сообщения равна 512 битам. На сегодняшний день, насколько можно судить из открытых источников, даже задача обращения MD4 не имеет эффективного решения для случайных 512-битных входов. Мы не рассматриваем здесь ситуации, связанные с подбором паролей, когда относительно короткий пароль или его «дубликат» можно восстановить по хэшу полным перебором или с использованием различных стратегий пространственно-временного компромисса, таких, например, как Rainbow-метод. С другой стороны, хорошо известны примеры успешного построения коллизий для функций MD4 и MD5. Первыми работами, в которых продемонстрирован метод, позволяющий устойчиво порождать коллизии для этих функций, являются X. Wang с соавторами [4, 5]. В дальнейшем «метод Wang» неоднократно совершенствовался и модифицировался. К сожалению, мы не можем здесь перечислить все соответствующие ссылки, так как это займёт слишком много места. Метод Wang представляет собой разновидность разностной атаки и может рассматриваться как развитие идей дифференциального криптоанализа [6] (по крайней мере, именно так его позиционирует сама X. Wang). Суть метода Wang заключается в случайном выборе некоторого сообщения с последующей его модификацией, цель которой состоит в «подгонке» получаемой пары сообщений под дифференциальный путь. В [7] предложено использовать алгоритмы решения проблемы булевой выполнимости (SAT) для автоматизации этапа подгонки. С использованием SAT-решателя minisat в [7] довольно эффективно удавалось находить одноблоковые коллизии для хэш-функции MD4. Задача поиска двухблоко-вых коллизий для MD5 оказалась тем не менее весьма сложной (текст работы [7] не позволяет точно определить ни время, за которое удавалось находить коллизии для MD5, ни число найденных коллизий). Как это ни странно, но результаты работы [7] не получили дальнейшего развития. Это особенно удивительно в свете интенсивного развития технологий решения SAT-задач, наблюдаемого в последние годы [8]. Следующий шаг в использовании SAT-подхода для поиска коллизий хэш-функций семейства MD был сделан, по всей видимости, только в 2014 г. авторами настоящей работы. Полученные в этом направлении результаты опубликованы в [9]. Дадим краткое их описание. Во-первых, отметим основной недостаток работы [7], который состоит в том, что для построения SAT-кодировок использовались узкоспециальные средства кодирования схемных представлений булевых функций. В [9] для этой цели использована система Transalg [10] автоматической трансляции в SAT алгоритмов вычисления дискретных функций. Полученные кодировки оказались существенно экономнее кодировок, построенных в [7]. Время поиска одноблоковых коллизий для MD4 составило менее 1 с в среднем в сравнении с 10 мин в [7]. При помощи параллельных SAT-решателей в [9] построены семейства двухблоковых коллизий для хэш-функции MD5. Более того, были выделены коллизии специального вида, а именно начинающиеся с 10 нулевых байт (10 примеров таких коллизий приведены в приложении к [9]). Помимо перечисленного, рассмотрена задача обращения хэш-функции MD4. Ранее к этой задаче также применялся SAT-подход [11]. Однако, как уже отмечалось, до сих пор никому не удалось осуществить успешное обращение полнораундовой версии MD4. В этом смысле рекордное значение равно 39 шагам алгоритма (число шагов в неослабленной версии MD4 равно 48). Атака на версию MD4 с 39 шагами, описанная в [11], требовала около 8 часов работы решателя minisat. При этом в SAT-кодиров-ку добавлялись дополнительные ограничения на некоторые переменные сцепления. Эти ограничения выбирались похожими на ограничения, описанные в [12]. Мы разработали новую технику генерации дополнительных ограничений такого рода. Основная идея состоит в следующем. Пусть C - КНФ, кодирующая задачу обращения некоторой функции х, и X - множество переменных, фигурирующих в C. Предположим, что к C требуется добавить ограничения, задающие некоторый предикат над переменными из множества XX, XX С X. Пусть R(X) -формула, задающая данный предикат. Введём в рассмотрение новую переменную u G X. Рассмотрим формулу C Л (u V R(X). Очевидно, что ограничение R(X) учитывается, когда переменная u принимает значение 1. При u = 0 ограничение R(X) не активно. Переменные типа u называются переменными переключения. В результате варьирования различных значений переменных переключения можно найти набор дополнительных ограничений, учёт которых позволит существенно повысить скорость решения SAT-задачи, кодирующей обращение рассматриваемой функции. При этом для работы с переменными переключения можно использовать различные техники «обучения», встроенные в современные SAT-ре-шатели. В частности, можно рассматривать значения переменных переключения как «assumptions» [13]. На данном этапе мы применили довольно простой механизм перебора значений переменных переключения. В результате найдены ограничения, отличающиеся от приведённых в [11]. Использование новых ограничений сократило время обращения 39-шаговой версии MD4 с нескольких часов до нескольких секунд. В ближайшем будущем мы планируем развивать технику работы с переменными переключения в направлении перебора существенно более широких (чем на текущий момент) множеств дополнительных ограничений.

Скачать электронную версию публикации