Голландский исследователь Марк Стивенс (Marc Stevens) обнародовал подробности успешной атаки на MD5 (PDF) и выложил программу на C++ для поиска коллизий в пределах одного 512-битного блока данных.Программа под Windows
Исходники скоро появятся здесь.
Пример коллизии
Сообщение 1
4d c9 68 ff 0e e3 5c 20 95 72 d4 77 7b 72 15 87
d3 6f a7 b2 1b dc 56 b7 4a 3d c0 78 3e 7b 95 18
af bf a2[00]a8 28 4b f3 6e 8e 4b 55 b3 5f 42 75
93 d8 49 67 6d a0 d1[55]5d 83 60 fb 5f 07 fe a2
Сообщение 2
4d c9 68 ff 0e e3 5c 20 95 72 d4 77 7b 72 15 87
d3 6f a7 b2 1b dc 56 b7 4a 3d c0 78 3e 7b 95 18
af bf a2[02]a8 28 4b f3 6e 8e 4b 55 b3 5f 42 75
93 d8 49 67 6d a0 d1[d5]5d 83 60 fb 5f 07 fe a2
Общий хеш MD5
008ee33a9d58b51cfeb425b0959121c9
Хеши SHA1 для этих сообщений:
> sha1sum message1.bin message2.bin
c6b384c4968b28812b676b49d40c09f8af4ed4cc message1.bin
c728d8d93091e9c7b87b43d9e33829379231d7ca message2.bin
На процессоре Core2 Q9550 коллизия нашлась за три недели. По оценке Марка Стивенса, расчётное время составляет около пяти недель. Вполне возможно, что при использовании CUDA на GPU эту задачу можно решить за часы. Автор говорит, что программа легко распараллеливается.
Классические методы обнаружения коллизий в MD5 публиковались с 2004 года, некоторые из них требовали минимальной сложности до 210, то есть могли быть проведены за секунду на обычном домашнем ПК, но на практике эти методы имели мало значения, потому что классические методы сфокусированы только на поиске разных документов, которые имеют одинаковые хэши (identical-prefix collision attacks). Это так называемые коллизии второго рода.
Особый вид атак на хеш-функции — атаки типа chosen-prefix, когда атакующий берёт два случайных документа и может показать, какие биты нужно изменить в одном документе, чтобы получить требуемую хеш-функцию. Это коллизии первого рода: для заданного сообщения M становится возможным подобрать другое сообщение N, для которого H(N) = H(M). Атака такого типа на MD5 была впервые проведена в 2007 году, сложность поиска коллизии составила около 250 вызовов к функции MD5Compress. С тех пор алгоритмы ускорились до 239 вызовов, а в 2009 году группа исследователей продемонстрировала коллизии chosen-prefix, требующие всего 596 бит и с вычислительной сложностью 253,2 вызовов. После этого слабость MD5 стала всем очевидна, и с помощью этого метода начали делать даже поддельные сертификаты уровня Certication Authority.
Как объясняет Марк Стивенс, в 2010 году китайские исследователи впервые продемонстрировали коллизии типа identical-prefix для одинарных 512-битных блоков MD5, но они не сообщили подробностей своего алгоритма «по причинам безопасности». Вместо этого они объявили своеобразный конкурс среди криптографов на то, чтобы повторить эту атаку для MD5. Работа Марка Стивенса претендует на победу в этом «конкурсе». Атака основана на новом алгоритме поиска коллизий, основанного на малом количестве вариантов в первом раунде вычисления хеша (MD5 работает в четыре раунда), а также метод Марка Стивенса использует ранее обнаруженные техники туннелирования. По оценке Стивенса, сложность поиска коллизии в одном 512-битном блоке по его алгоритму оценивается в 249,81 вызовов к функции MD5Compress.
