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

Для множества даже миллиардов активов вероятность случайных столкновений пренебрежимо мала – ничего, о чем вам следует беспокоиться. Учитывая парадокс дня рождения , учитывая набор из 2 ^ 64 (или 18 446 744 073 709 551 616) активов, вероятность одного столкновения MD5 в этом наборе составляет 50%. В этом масштабе вы, вероятно, будете бить Google с точки зрения емкости хранилища.

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

Кроме того, рассмотрите разветвления, если злоумышленник может создать столкновение с существующим активом в вашей базе данных. Хотя таких известных атак ( preimage-атак ) против MD5 (по состоянию на 2011 год) не существует, это может стать возможным благодаря расширению текущих исследований по атакам на столкновение.

Если это окажется проблемой, я предлагаю посмотреть на hash-функции SHA-2 (SHA-256, SHA-384 и SHA-512). Недостатком является то, что он немного медленнее и имеет более длинный выходной сигнал.

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

В частности, обратите внимание, что коды MD5 имеют фиксированную длину, поэтому возможное количество кодов MD5 ограничено. Количество строк (любой длины), однако, определенно неограниченно, поэтому логически следует, что должны быть столкновения.

Да, это возможно. Это на самом деле проблема дня рождения . Однако вероятность двух случайно выбранных строк, имеющих один и тот же MD5-hash, очень мала.

См. Этот и эти вопросы для примера.

Да, конечно: хеши MD5 имеют конечную длину, но существует бесконечное количество возможных строк символов, которые могут быть хешированы MD5.

Да, возможно, что две разные строки могут генерировать один и тот же hash-код 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-hash.

Разница в одном байте:

 $ 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: Construct MD5 Collisions, используя только один блок сообщений , 2010.

Связанный:

• Существуют ли две известные строки, которые имеют одно и то же значение хеша MD5? на Crypto.SE

Да, это возможно. Это называется столкновением Хэша .

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

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

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

Биекция по википедии

РЕДАКТИРОВАТЬ: быть полными инъективными хеш-функциями: это называется идеальным hashированием .

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

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 

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

Я понимаю, что это старо, но я думал, что внесет свое решение. Есть 2 ^ 128 возможных комбинаций hashей. И, таким образом, вероятность того, что парадокс дня рождения будет 2 ^ 64. Хотя нижеприведенное решение не устранит вероятность столкновений, оно, безусловно, уменьшит риск на очень существенную сумму.

 2^64 = 18,446,744,073,709,500,000 possible combinations 

То, что я сделал, – это положить несколько hashей на основе входной строки, чтобы получить гораздо более длинную результирующую строку, которую вы считаете своим хешем …

Поэтому мой псевдокод для этого:

 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