MD5CRK - MD5CRK

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

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

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

Сложность

Ожидаемое время обнаружения столкновения не равно куда - количество бит в выводе дайджеста. Это на самом деле , куда - количество собранных выходных данных функции.

Для этого проекта вероятность успеха после Расчеты MD5 могут быть аппроксимированы следующим образом: .

Ожидаемое количество вычислений, необходимых для создания коллизии в 128-битной функции дайджеста сообщения MD5, таким образом:

Чтобы дать некоторую перспективу этому, используя Virginia Tech Система X с максимальной производительностью 12,25 терафлопс потребуется примерно секунд или около 3 недель. Или для массовых процессоров на 2 гигафлопса потребуется 6000 машин примерно столько же времени.

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

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

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

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