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

Question

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

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

Это уже было проверено на MD5, SHA1 и т. Д.?

Answer 1

Обновить

По иронии судьбы, спустя несколько недель после того, как я опубликовал предыдущий ответ, два китайских исследователя, Тао Се и Дэнго Фэн, опубликовали новое столкновение с одним блоком для 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 дня на кластере Playstation 3 с 215 узлами, автор Mark Stevens:)

Answer 2

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

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

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

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

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

набор 9-байтовых строк: p (2⁷²) ≈ 1 - e^{-2144/ (2 * 2128)} = 1 - e^-215 = 1 - e^-32768 ≈ 1

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

Answer 3

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