Какая самая короткая пара строк вызывает коллизию MD5?

Обновлять

По иронии судьбы, через несколько недель после того, как я опубликовал предыдущий ответ, два китайских исследователя, Тао Се и Дэнгуо Фэн, опубликовали новый одноблочная коллизия для MD5. До сих пор я не знал об этой статье. Один блок MD5 означает, что размер ввода составляет 64 байта или 512 бит. Обратите внимание, что входные данные в основном одинаковы, отличаются только 2 битами.

Их методология не будет опубликована до января 2013 года, но их коллизию можно проверить сейчас, используя цифры из статьи:

>>> from array import array
>>> from hashlib import md5
>>> input1 = array('I',  [0x6165300e,0x87a79a55,0xf7c60bd0,0x34febd0b,0x6503cf04,
    0x854f709e,0xfb0fc034,0x874c9c65,0x2f94cc40,0x15a12deb,0x5c15f4a3,0x490786bb,
    0x6d658673,0xa4341f7d,0x8fd75920,0xefd18d5a])
>>> input2 = array('I', [x^y for x,y in zip(input1,
    [0, 0, 0, 0, 0, 1<<10, 0, 0, 0, 0, 1<<31, 0, 0, 0, 0, 0])])
>>> input1 == input2
False
>>> md5(input1).hexdigest()
'cee9a457e790cf20d4bdaa6d69f01e41'
>>> md5(input2).hexdigest()
'cee9a457e790cf20d4bdaa6d69f01e41'

Обновление: статья была опубликована в марте 2013 г .: Тао Се и Фанбао Лю и Дэнго Фэн - Fast Collision Attack на MD5

Однако, если у вас есть больше места для игры, столкновения в несколько килобайт вычисляются НАМНОГО быстрее - их можно рассчитать в течение нескольких часов на ЛЮБОМ обычном компьютере.

Старый ответ

Предыдущая самая короткая коллизия использовала как минимум два входных блока MD5 - это 128 байтов, 1024 бит. Префикс в первом блоке может быть выбран злоумышленником произвольно, остальные будут вычислены и отображаться как тарабарщина.

Вот пример двух разных сталкивающихся входов, вы можете попробовать это сами на Python:

>>> from binascii import unhexlify
>>> from hashlib import md5
>>> input1 = 'Oded Goldreich\nOded Goldreich\nOded Goldreich\nOded Go' + unhexlify(
... 'd8050d0019bb9318924caa96dce35cb835b349e144e98c50c22cf461244a4064bf1afaecc582'
... '0d428ad38d6bec89a5ad51e29063dd79b16cf67c12978647f5af123de3acf844085cd025b956')
>>> len(input1)
128
>>> md5(input1).hexdigest()
'd320b6433d8ebc1ac65711705721c2e1'
>>> input2 = 'Neal Koblitz\nNeal Koblitz\nNeal Koblitz\nNeal Koblitz\n' + unhexlify(
... '75b80e0035f3d2c909af1baddce35cb835b349e144e88c50c22cf461244a40e4bf1afaecc582'
... '0d428ad38d6bec89a5ad51e29063dd79b16cf6fc11978647f5af123de3acf84408dcd025b956')
>>> md5(input2).hexdigest()
'd320b6433d8ebc1ac65711705721c2e1'

Создание этих двух конкретных входных данных заняло 2 дня в кластере Playstation 3 с 215 узлами, Марк Стивенс :)

Математика парадокса дня рождения делает точку перегиба вероятности столкновения примерно около sqrt (N), где N - количество отдельных ячеек в хеш-функции, поэтому для 128-битного хеша, когда вы получаете около 64 бит, у вас умеренная вероятность иметь 1 коллизию. Таким образом, я предполагаю, что для полного набора из 8-байтовых строк это скорее всего будет коллизия, а для 9-байтовых строк это очень вероятно.

edit: предполагается, что алгоритм хеширования MD5 вызывает сопоставление входной байтовой строки с выходным хешем, близкое к "случайному". (по сравнению с тем, который распределяет строки более равномерно среди набора возможных хешей, и в этом случае он будет ближе к 16 байтам.)

Также для получения более конкретного числового ответа, если вы посмотрите одно из приближений для расчета столкновения вероятность, вы получите

p (k) 1 - e ^{-k (k-1) / (2 * 2 128)}, где k = размер пространства возможных входов = 2 ^m, где длина входной байтовой строки составляет m бит.

набор из 8-ми байтовых строк: p (2 ⁶⁴) 1 - e ^-0,5 0,3935

набор из 9 байтовых строк: p (2 ⁷²) 1 - e ^{-2 144 / (2 * 2 128) < / sup> = 1 - e -2 15 = 1 - e -32768 1}

Также обратите внимание, что они предполагают полный набор строк байтов m / 8. Если вы используете только буквенно-цифровые символы, вам понадобится больше байтов, чтобы получить вероятную коллизию.

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