MD5CRK

В криптографии MD5CRK был добровольным вычислительным усилием (похожим на distributed.net ), запущенным Жаном-Люком Куком и его компанией CertainKey Cryptosystems, чтобы продемонстрировать, что алгоритм дайджеста сообщений MD5 небезопасен, путем нахождения коллизии  — двух сообщений, которые производят один и тот же хэш MD5. Проект был запущен 1 марта 2004 года. Проект завершился 24 августа 2004 года после того, как исследователи независимо продемонстрировали технику генерации коллизий в MD5 с использованием аналитических методов Сяоюнь Вангом , Фэном, Сюэцзя Лаем и Юем. ^[1] CertainKey вручила премию в размере 10 000 канадских долларов Вану, Фэну, Лаю и Юю за их открытие. ^[2]

Метод, называемый алгоритмом поиска цикла Флойда, использовался для поиска коллизии для MD5. Алгоритм можно описать по аналогии со случайным блужданием . Используя принцип, согласно которому любая функция с конечным числом возможных выходов, помещенная в петлю обратной связи, будет цикличной, можно использовать относительно небольшой объем памяти для хранения выходов с определенными структурами и использовать их в качестве «маркеров», чтобы лучше определять, когда маркер был «пройден» ранее. Эти маркеры называются выделенными точками , точка, в которой два входа производят одинаковый выход, называется точкой столкновения . MD5CRK считал любую точку, первые 32 бита которой были нулями, выделенной точкой.

Ожидаемое время поиска коллизии не равно , где — количество битов в выходном дайджесте. Фактически , оно равно , где — количество собранных выходных данных функции.${\displaystyle 2^{N}}$${\displaystyle N}$${\displaystyle 2^{N}! \over {(2^{N}-K)!\times {2^{N}}^{K}}}$${\displaystyle К}$

Для этого проекта вероятность успеха после вычислений MD5 можно приблизительно оценить по формуле: .${\displaystyle К}$${\displaystyle 1 \over {1-e^{K\times (1-K) \over 2^{N+1}}}}$

Ожидаемое количество вычислений, необходимых для возникновения коллизии в 128-битной функции дайджеста сообщения MD5, составляет:${\displaystyle {1,17741\times 2^{N/2}}={1,17741\times 2^{64}}}$

Чтобы дать некоторую перспективу, используя System X от Virginia Tech с максимальной производительностью 12,25 Терафлопс, это заняло бы примерно секунды или около 3 недель. Или для массовых процессоров с 2 Гигафлопс это заняло бы 6000 машин примерно то же самое время.${\displaystyle {2,17\times 10^{19}/12,25\times 10^{12}\приблизительно 1 770 000}}$

• Список добровольных вычислительных проектов
• Атака методом грубой силы

• Пол К. ван Ооршот ; Майкл Дж. Винер. Параллельный поиск коллизий с применением к хэш-функциям и дискретным логарифмам (PDF) . Конференция ACM по компьютерной и коммуникационной безопасности 1994. стр. 210–218.