Создайте свои собственные коллизии MD5

Question

Я делаю презентацию о столкновениях MD5 и хочу дать людям представление о вероятности столкновения.

Было бы хорошо иметь два блока текста, которые хэшируют одну и ту же вещь, и объяснить, сколько комбинаций [a-zA-Z] было необходимо, прежде чем я столкнусь с коллизией.

Очевидный ответ - хэшировать каждую возможную комбинацию, пока два хэша не попадут в одно и то же. Итак, как бы вы пошли о кодировании этого. В качестве быстрого эксперимента я попытался хэшировать каждую комбинацию из 5 столбцов [A-Z], сохраняя ее в хеш-таблице .net и перехватывая исключение коллизий. Две проблемы с этим - хэш-таблица в конце концов истекает, и я почти уверен, что мне понадобится ОЧЕНЬ больше символов.

Очевидно, что эта структура данных слишком велика, чтобы обрабатывать ее в памяти, поэтому теперь мне нужно подключить базу данных. Также звучит как хороший проект для тестирования лазури - немного похоже на этих парней .

Может ли кто-нибудь направить меня в направлении эффективного способа сделать это?

Answer 1

Эти следующие две разные 128-байтовые последовательности хэшируют к одному и тому же:

MD5 Hash : 79054025255fb1a26e4bc422aef54eb4

Различия ниже выделены жирным шрифтом. Извините, это довольно трудно увидеть.

d131dd02c5e6eec4693d9a0698aff95c 2fcab5<strong>8</strong>712467eab4004583eb8fb7f89 
55ad340609f4b30283e4888325<strong>7</strong>1415a 085125e8f7cdc99fd91dbd<strong>f</strong>280373c5b 
d8823e3156348f5bae6dacd436c919c6 dd53e2<strong>b</strong>487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080<strong>a</strong>80d1e c69821bcb6a8839396f965<strong>2</strong>b6ff72a70

и

d131dd02c5e6eec4693d9a0698aff95c 2fcab5<strong>0</strong>712467eab4004583eb8fb7f89 
55ad340609f4b30283e4888325<strong>f</strong>1415a 085125e8f7cdc99fd91dbd<strong>7</strong>280373c5b 
d8823e3156348f5bae6dacd436c919c6 dd53e2<strong>3</strong>487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080<strong>2</strong>80d1e c69821bcb6a8839396f965<strong>a</strong>b6ff72a70

Визуализация столкновения / блока1 (Источник: Links.Org )

Визуализация столкновения / блока2 (Источник: Links.Org )

Answer 2

Трудно сделать это только с помощью текстовых файлов, AFAIK. Вы можете получить несколько столкновений, но иметь их также из [a-zA-Z] нелегко (пока).

С другой стороны, если вам нужны только два «значимых» файла с одинаковым хеш-кодом, вы можете сделать это с помощью, скажем, PostScript: иметь разные двоичные двоичные объекты, вызывающие конфликт, и использовать условное выражение отображать другой вывод соответственно.

См. Например эта проблема (часть H2) и решение . Например, этот PS-файл и этот имеют одинаковую сумму MD5, но оба они представляют собой правильно сформированные файлы PostScript, которые содержат совершенно другой текст при их открытии.

Answer 3

Если вы говорите о том, насколько вероятна прямая коллизия - та, в которой нет преднамеренной попытки вызвать ее - тогда вы будете разочарованы: вам нужно будет генерировать в среднем 2 ^ 64 открытых текста перед вами может ожидать столкновения, и это значительно больше, чем вы сможете сделать за разумное (или даже даже необоснованное) время.

Если вы хотите продемонстрировать сложность преднамеренного создания столкновения, другие ответы уже продемонстрировали это. Дополнительное ограничение требования того, чтобы строки были полностью текстовыми, делает даже эти подходы практически непрактичными.

Answer 4

Я бы посмотрел на Hashcash . С эффективным алгоритмом хеширования, таким как md5, время для вычисления столкновения экспоненциально с количеством битов. Что делает Hashcash, так это вычисляет частичные столкновения. То есть совпадение, скажем, младших 16 бит хеша. Чтобы получить соответствие младших 16 битов, нужно в среднем попытаться хэшировать 2 ^ 15 различных комбинаций. Если вы знаете, сколько времени потребуется для создания коллизии 16, 24 или 32 бита, вы можете легко рассчитать время для большего числа бит.

Answer 5

Весь смысл таких хэшей в том, что столкновения крайне маловероятны. Вы не будете генерировать один случайно - ваша машина почти наверняка умрет от старости, прежде чем вы добьетесь успеха. Весь смысл использования хэша исчезнет, ​​если вы сможете разумно генерировать коллизии!