MD5CRK

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

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

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

Сложность

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

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

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

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

См. также

Ссылки

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

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

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

[collisions2004-1] Сяоюнь Ван; Дэнго Фэн; Сюэцзя Лай; Хунбо Ю (17 августа 2004 г.). «Коллизии хэш-функций MD4, MD5, HAVAL-128 и RIPEMD» . Архив электронной печати по криптологии .

[2] «Популярный, но устаревший банковский алгоритм сломан» . Определенные ключевые новости (пресс-релиз). 17 февраля 2005 г. Архивировано из оригинала 13 мая 2011 г.

[1]

[2]