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

Ответ 1

Update

По иронии судьбы, через несколько недель после того, как я опубликовал предыдущий ответ, два китайских исследователя, Tao Xie и Dengguo Feng, опубликовали новое одноблочное столкновение для 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 года: Тао Се и Фанбао Лю и Дэнго Фэн - Быстрая атака на столкновение с 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 дня в 215- node кластере Playstation 3, Марк Стивенс:)

Ответ 2

Математика парадоксальности дня делает точку перегиба вероятности столкновения примерно вокруг 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)}= 1 - e ^{-2 15}= 1 - e ^-32768 & асимп. 1

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

Ответ 3

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