Обратная идентичность MD5: существует ли (X, Y) такая, что md5 (X) = Y и md5 (Y) = X - PullRequest
Новая
       18

Обратная идентичность MD5: существует ли (X, Y) такая, что md5 (X) = Y и md5 (Y) = X

15 голосов
/ 03 июня 2009

Существуют ли два 128-битных значения, которые хэшируются друг с другом? 

Find (X,Y) such that md5(X) = Y and md5(Y) = X

можно ли их найти без грубой силы?

Для дополнительного кредита: Могу ли я составить термин «обратная идентичность md5-itive?»

Набор решений будет редким, если не пустым.

Для вашего LOL сегодня, вот вам:

https://github.com/flipmcf/playground/tree/master/md5-inverse-search

Связанный:

фиксированная точка MD5
MD5 Hash Collisions

Ответы [ 2 ]

4 голосов
/ 13 ноября 2009

(Оба ответа были найдены при чтении этой ссылки ) ...

Чтобы ответить на вопрос (1), рассмотрите следующее:

Перебор всех md5 (x) = x означает проверку значений 2.4x10 ^ 38. Моя быстрая реализация теста может тестировать около 2.3x10 ^ 9 значений в час, а это означает, что для полного перебора потребуется почти 10 ^ 29 часов. Скажем, у меня есть миллион людей, которые мне помогают, тогда у нас осталось 10 ^ 23 лет ... И скажем, алгоритм работает в миллион раз быстрее с некоторой умной оптимизацией, а у нас осталось 10 ^ 17 лет. И давайте представим, что компьютеры работают в миллион раз быстрее за ночь, и у нас осталось 10 ^ 11 лет, что значительно дольше, чем существовала вселенная.

Я полагаю, что вышеперечисленное можно было бы быстрее отбросить с помощью некоторого интеллектуального алгоритма силы & dagger;.

Чтобы ответить на вопрос (2), следующие два блока имеют одинаковый хэш md5: 

d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70

и 

d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70

6 байтов различаются между двумя блоками (байты 39, 91, 119, 167, 219 и 247), а хэш равен 79054025255fb1a26e4bc422aef54eb4. Я бы предположил, что блоки были обнаружены с помощью какого-то умного алгоритма силы, но я точно не знаю.

& dagger ;: грубая сила с учетом проанализированных слабостей md5

3 голосов
/ 18 июня 2009

Это не то же самое, что поиск идентификатора Kember.

Рассмотрим различия следующих случаев: 

md5(X) == X

Чтобы это было правдой, X должно быть 128-битным значением.

Это не то же самое, что следующее: 

bin2hex(md5('string')) == 'string'

Вот что на самом деле ищет Идентификационный поиск Кембера. Если вы посмотрите на любую из реализаций поиска на их сайте, вы легко увидите, что они работают с 32-символьными строками, а не с 128-битными числами, как входные данные для функции md5, и, следовательно, не ищут md5 (X) == X.

Я тоже не первый, кто на это указывает, вы можете найти Эта статья, непосредственно нацеленная на «идентичность Кембера» Криса Томпсона просвещающая.

...