Могут ли две разные строки генерировать один и тот же хэш-код MD5?
Для каждого из наших двоичных активов мы генерируем хеш MD5. Это используется для проверки, есть ли определенный бинарный актив в нашем приложении. Но возможно ли, что два разных бинарных ресурса генерируют один и тот же хеш MD5. Так возможно ли, что две разные строки генерируют один и тот же хэш MD5?
12 ответов
Для набора из даже миллиардов активов вероятность случайных коллизий ничтожно мала - вам не о чем беспокоиться. Учитывая парадокс дня рождения, учитывая набор из 2^64 (или 18 446 744 073 709 551 616) активов, вероятность одного коллизии MD5 в этом наборе составляет 50%. При таком масштабе вы, вероятно, обыграете Google по объему памяти.
Однако из-за того, что хеш-функция MD5 была нарушена (она уязвима для атаки коллизий), любой решительный злоумышленник может создать 2 сталкивающихся ресурса за считанные секунды мощности процессора. Поэтому, если вы хотите использовать MD5, убедитесь, что такой злоумышленник не поставит под угрозу безопасность вашего приложения!
Также рассмотрите возможные последствия, если злоумышленник может создать конфликт с существующим ресурсом в вашей базе данных. Хотя таких известных атак (атак с прообразом) на MD5 нет (по состоянию на 2011 год), это может стать возможным благодаря расширению текущих исследований атак на столкновения.
Если это окажется проблемой, я предлагаю рассмотреть серию хеш-функций SHA-2 (SHA-256, SHA-384 и SHA-512). Недостатком является то, что он немного медленнее и имеет более длинный хэш-вывод.
MD5 - это хеш-функция - так что да, две разные строки могут абсолютно генерировать конфликтующие коды MD5.
В частности, обратите внимание, что коды MD5 имеют фиксированную длину, поэтому возможное количество кодов MD5 ограничено. Количество строк (любой длины), однако, определенно не ограничено, поэтому логически следует, что должны быть столкновения.
Да, возможно, что две разные строки могут генерировать один и тот же хэш-код MD5.
Вот простой тест с использованием очень похожего двоичного сообщения в шестнадцатеричной строке:
$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c6b384c4968b28812b676b49d40c09f8af4ed4cc -
008ee33a9d58b51cfeb425b0959121c9
$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c728d8d93091e9c7b87b43d9e33829379231d7ca -
008ee33a9d58b51cfeb425b0959121c9
Они генерируют различную сумму SHA-1, но одинаковое хеш-значение MD5. Во-вторых, строки очень похожи, поэтому трудно найти разницу между ними.
Разницу можно найти с помощью следующей команды:
$ diff -u <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2 | fold -w2) <(echo 4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2 | fold -w2)
--- /dev/fd/63 2016-02-05 12:55:04.000000000 +0000
+++ /dev/fd/62 2016-02-05 12:55:04.000000000 +0000
@@ -33,7 +33,7 @@
af
bf
a2
-00
+02
a8
28
4b
@@ -53,7 +53,7 @@
6d
a0
d1
-55
+d5
5d
83
60
Вышеупомянутый пример столкновения взят из Marc Stevens: столкновение с одним блоком для MD5, 2012; он объясняет свой метод с помощью исходного кода ( альтернативная ссылка на статью).
Еще один тест:
$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
756f3044edf52611a51a8fa7ec8f95e273f21f82 -
cee9a457e790cf20d4bdaa6d69f01e41
$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
6d5294e385f50c12745a4d901285ddbffd3842cb -
cee9a457e790cf20d4bdaa6d69f01e41
Разная сумма SHA-1, тот же хеш MD5.
Разница в одном байте:
$ diff -u <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2) <(echo 0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef | fold -w2)
--- /dev/fd/63 2016-02-05 12:56:43.000000000 +0000
+++ /dev/fd/62 2016-02-05 12:56:43.000000000 +0000
@@ -19,7 +19,7 @@
03
65
9e
-70
+74
4f
85
34
@@ -41,7 +41,7 @@
a3
f4
15
-5c
+dc
bb
86
07
Приведенный выше пример адаптирован из Tao Xie и Dengguo Feng. Построение коллизий MD5 с использованием всего лишь одного блока сообщения, 2010.
Связанные с:
Да, это возможно. Это на самом деле проблема дня рождения. Однако вероятность того, что две случайно выбранные строки имеют одинаковый хэш MD5, очень мала.
Да, конечно: MD5-хэши имеют конечную длину, но существует бесконечное количество возможных символьных строк, которые могут быть MD5-хэшированными.
Просто чтобы быть более информативным. С математической точки зрения хэш-функции не являются инъективными.
Это означает, что между начальным набором и полученным не существует отношения 1 к 1 (но в одну сторону).
РЕДАКТИРОВАТЬ: чтобы быть полным инъективные хэш-функции существуют: это называется идеальным хешированием.
Да, это возможно. Это называется хэш-столкновением.
Сказав это, алгоритмы, такие как MD5, предназначены для минимизации вероятности столкновения.
Запись в Википедии о MD5 объясняет некоторые уязвимости в MD5, о которых вам следует знать.
Я думаю, что мы должны быть осторожны при выборе алгоритма хеширования в соответствии с нашим требованием, поскольку коллизии хэшей не так редки, как я ожидал. Недавно я обнаружил очень простой случай коллизии хэшей в моем проекте. Я использую оболочку Python из xxhash для хеширования. Ссылка: https://github.com/ewencp/pyhashxx
s1 = 'mdsAnalysisResult105588'
s2 = 'mdsAlertCompleteResult360224'
pyhashxx.hashxx(s1) # Out: 2535747266
pyhashxx.hashxx(s2) # Out: 2535747266
Это вызвало очень сложную проблему с кэшированием в системе, а потом я обнаружил, что это коллизия хешей.
Как говорили другие люди, да, могут быть столкновения между двумя разными входами. Однако, в вашем случае использования, я не вижу в этом проблемы. Я очень сомневаюсь, что вы столкнетесь с коллизиями - я использовал MD5 для снятия отпечатков сотен тысяч файлов изображений с несколькими форматами изображений (JPG, растровые изображения, PNG, raw) на предыдущей работе, и у меня не было коллизий,
Однако, если вы пытаетесь отследить какие-то данные, возможно, вы могли бы использовать два алгоритма хеширования - вероятность одного входа, приводящего к одинаковому результату двух разных алгоритмов, практически невозможна.
Да, это! Возможна коллизия (хотя риск очень мал). Если нет, то у вас будет довольно эффективный метод сжатия!
РЕДАКТИРОВАТЬ: Как говорит Конрад Рудольф: Потенциально неограниченный набор входных данных, преобразованный в конечный набор выходных данных (32 шестнадцатеричных символа), приведет к бесконечному количеству столкновений.
Я понимаю, что это старо, но думал, что внесу свое решение. Есть 2 ^ 128 возможных комбинаций хешей. И, следовательно, 2 ^ 64 вероятность парадокса дня рождения. Хотя приведенное ниже решение не исключает возможность столкновений, оно, несомненно, значительно снизит риск.
2^64 = 18,446,744,073,709,500,000 possible combinations
Я сделал несколько хешей на основе входной строки, чтобы получить более длинную результирующую строку, которую вы считаете своим хешем...
Итак, мой псевдокод для этого:
Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string))
То есть практической невероятности столкновения. Но если вы хотите быть супер параноиком и не можете этого добиться, и место для хранения не является проблемой (равно как и вычислительные циклы)...
Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string))
& Hash(Reverse(SpellOutLengthWithWords(Length(string))))
& Hash(Rotate13(string)) Hash(Hash(string)) & Hash(Reverse(Hash(string)))
Ладно, это не самое чистое решение, но теперь это дает вам гораздо больше шансов на то, как редко вы столкнетесь с столкновением. Кстати, я могу предположить невозможность во всех реалистических смыслах этого термина.
Ради меня, я думаю, что вероятность столкновения достаточно редка, так что я буду считать это не "верным", но настолько маловероятным, чтобы это произошло, поскольку это соответствует потребностям.
Теперь возможные комбинации значительно возрастают. Хотя вы могли бы потратить много времени на то, сколько комбинаций вы могли бы получить, я скажу, что теоретически это принесет вам ЗНАЧИТЕЛЬНО больше, чем приведенное выше число
2^64 (or 18,446,744,073,709,551,616)
Вероятно, еще на сто цифр или около того. Теоретический максимум, который это может дать вам, был бы
Возможное количество результирующих строк:
528294531135665246352339784916516606518847326036121522127960709026673902556724859474417255887657187894674394993257128678882347559502685537250538978462939576908386683999005084168731517676426441053024232908211188404148028292751561738838396898767036476489538580897737998336
Похоже, что понимание теории не помогает, когда речь идет о теории на практике, и нужно знать, что означают только 2 числа 1 и 0, это означает 1111111111, поэтому 100 означает 10 раз больше этого.
Чтобы использовать все хэши, вам нужно в одной файловой системе или в системе с одним днем рождения, каждому человеку в мире необходимо иметь 18446744073709551616/8000000000 = 2305843009,21 файлов для каждого человека, а если его размер 1 МБ, то это 2305843009 МБ или 2305843 ГБ или 2305 ТБ или 153722. Google диски бесплатно 15 ГБ на человека.
Если мы делаем файлы больше, то больше используемого места и меньшее количество файлов означает меньшее количество хэшей. Таким образом, у нас по-прежнему не будет файлов меньшего размера, а только больше.
Подсчитайте кто-нибудь, насколько большими должны быть файлы, чтобы мы могли заполнить все хэши MD5.
Если средний размер файла в 2002 г. составлял 3,22 МБ, то в 2005 г. — 8,92 МБ, и мы можем предположить, что мы по-прежнему используем то же качество размера файла. так что даже в файловой системе Google никогда не будет так много файлов в одной системе, поскольку, если 15 ГБ бесплатного диска Google заполнены в среднем множеством маленьких файлов размером 3 МБ для каждых 8 миллиардов человек в мире, получится 40000000000000, это из всех хэшей MD5 0,0000021684% от всех возможных хэшей размеры файлов.
Говоря о несвязанных вещах, таких как день рождения 100 года рождения двух человек, мы сравниваем 2 дня или 0,02, а в 365 из двух человек сравниваем 0,00547% файлов MD5 2/18446744073709551616=0,000000000000000000000108420217% всех файлов, если бы их было так много. все.
Это как спросить в мире Адама и Евы, у них один и тот же хеш-день рождения, когда в мире нет 365 человек, или в файлах файловой системы, или вообще столько паролей.
Таким образом, коллизий при попытке взлома так много, что в реальной жизни защищенный сервер невозможен.
Если полный лимит MD5 составляет 18446744073709551616, то у вас никогда не будет столько файлов во всем мире.
MD5 является примером того, что все мировые строки подсчитываются в хэши, которые никогда не будут существовать так долго, так что это просто проблема короткого MD5, но будет ли у нас триллион строк огромной длины, имеющих действительно один и тот же хеш?
На самом деле это было бы похоже на сравнение 365 младенцев, родившихся в разные дни, с 366 младенцами, чтобы выяснить, у кого из них день рождения совпадает.
Как вы видите, все ответы теоретически отвечают «да», но не могут доказать примеры из реальной жизни. Если это пароль, то только очень длинная строка может совпадать с короткой.
Если это хеширование идентификации файла, используйте другое хеширование или их комбинацию.
Проблема дня рождения заключается в том, что слово «abcd» одного человека состоит из 4 букв, в то время как ДНК другого человека может быть такой же, только если это «abcdfijdfj».
Если вы читаете википедию о проблеме дня рождения, это не только дата рождения, но и дата рождения, час, секунда, мс и многое другое, похожее на проблему ДНК.
С гашишем у вас может быть одинаковая ДНК и день рождения с близнецами? Неа. С кем-то еще иногда.
Парадокс дня рождения, безусловно, вероятность результата математический трюк вероятность 365 вариантов или дней, в то время как хэш от сколько? Намного больше. Поэтому, если у вас есть 2 разные совпадающие строки, это просто потому, что хэш MD5 слишком короткий для слишком большого количества файлов, поэтому используйте что-то более длинное, чем MD5.
Это не сравнение 50 детей за 365 дней, это сравнение 2 хэшей, если они одинаковы из строк разной длины, которые были хешированы, например, abcd так же, как 25-буквенный abcdef...zdgdege и 150-буквенный sadiasdjsadijfsdf.sdaidjsad.dfijsdf.
Так что, если его пароль, то его родной брат по дню рождения будет намного длиннее, которого даже не существует, поскольку никто не создает 25-буквенный пароль.
Для сравнения размера файла я не уверен, насколько велика вероятность, но это не 97% и даже не 0,0000001%.
Хорошо, давайте будем более конкретными.
Если его файл может возникнуть в огромной системе, поскольку файлы будут разными, но на практике это не должно быть проблемой, поскольку 5 квадриллионов или 5 000 000 000 000 000 файлов должны быть в одной системе для UUID и для MD5.
А если это пароль, то 10 лет пробовать каждую секунду, а можно было пробовать каждую миллисекунду, но тогда за 3 неверных подбора блокировка ip на 1минуту сделает угадывание миллионы лет.
Когда я вижу что-то не так, я знаю, что это неправильно. Теория обещает против реальности.