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

До какой длины строки можно использовать MD5 как хеш, не беспокоясь о возможности столкновения?

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

Было ли это уже проверено на MD5, SHA1 и т.д.

Ответ 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 ¹²⁸)} где k = размер пространства возможных входов = 2 ^m где длина байта ввода - это длина m бит.

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

набор из 9 байтовых строк: p (2 ⁷²) & асимп; 1 - e ^{-2 ¹⁴⁴/(2 * 2 ¹²⁸)}= 1 - e ^{-2 ¹⁵}= 1 - e ^-32768 & асимп. 1

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

Ответ 3

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