MD5CRK - MD5CRK

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

Ро столкновения Полларда ищет единственный путь

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

Сложность

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

Для этого проекта вероятность успеха после ${\displaystyle K}$ Расчеты MD5 могут быть аппроксимированы следующим образом: ${\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}}}$

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

Смотрите также

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

Рекомендации

1. Сяоюнь Ван; Дэнго Фэн; Сюэцзя Лай; Хунбо Ю (17 августа 2004 г.). «Коллизии для хеш-функций MD4, MD5, HAVAL-128 и RIPEMD».
2. «Популярный, но устаревший, банковский алгоритм сломан». CertainKey Новости (Пресс-релиз). 17 февраля 2005 г. Архивировано с оригинал 13 мая 2011 г.

дальнейшее чтение

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