Могут ли две разные строки генерировать один и тот же хэш-код MD5?

MD5-это хэш-функция - Так что да, две разные строки могут абсолютно генерировать сталкивающиеся коды MD5.

в частности, обратите внимание, что коды MD5 имеют фиксированную длину, поэтому возможное количество кодов 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

выше коллизии пример взят от Марка Стивенса:одноблочное столкновение для 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? at Crypto.SE

Да, это возможно. Это называется Hash collision.

сказав это, алгоритмы, такие как MD5 предназначены для минимизации вероятности столкновения.

запись "Википедии" о MD5 объясняет некоторые уязвимости в MD5, о которых вы должны знать.

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

биекция в Википедии

EDIT: чтобы быть полными инъективными хэш-функциями, существуют: это называется идеальное хеширование.

Да, это так! Столкновение будет быть возможность (хотя риск очень небольшой). Если нет, то у вас будет довольно эффективный метод сжатия!

EDIT: как говорит Конрад Рудольф: потенциально неограниченный набор входных данных, преобразованный в конечный набор выходных данных (32 шестнадцатеричных символа) будет приводит к бесконечному количеству столкновений.

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

однако, если вы пытаетесь отпечатать какие-то данные, возможно, вы могли бы использовать два хэша алгоритмы-вероятность того, что один вход приведет к одному и тому же выходу двух разных алгоритмов, почти невозможна.

Я думаю, что мы должны быть осторожны, выбирая алгоритм хэширования в соответствии с нашим требованием, так как хэш-коллизии не так редки, как я ожидал. Недавно я нашел очень простой случай столкновения хэшей в моем проекте. Я использую Python обертку xxhash для хэширования. Ссылка:https://github.com/ewencp/pyhashxx

s1 = 'mdsAnalysisResult105588'
s2 = 'mdsAlertCompleteResult360224'
pyhashxx.hashxx(s1) # Out: 2535747266
pyhashxx.hashxx(s2) # Out: 2535747266

это вызвало очень сложную проблему кэширования в системе, а затем я, наконец, обнаружил, что это хэш-коллизия.

Я понимаю, что это старый, но думал, что я внесу свой вклад в мое решение. Существует 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