Для каждого из наших двоичных активов мы генерируем хеш MD5. Это используется для проверки того, что определенный бинарный актив уже присутствует в нашем приложении. Но возможно ли, что два разных бинарных актива генерируют один и тот же MD5-хэш. Возможно ли, что две разные строки генерируют один и тот же MD5-хэш?
Может ли две разные строки генерировать один и тот же MD5-хэш-код?
Ответ 1
Для набора четных миллиардов активов вероятность случайных столкновений пренебрежимо мала - ничего, о чем вам следует беспокоиться. Учитывая парадокс дня учитывая набор из 2 ^ 64 (или 18 446 744 073 709 551 616) активов, вероятность одного столкновения MD5 в этом наборе составляет 50%, В этом масштабе вы, вероятно, будете бить Google с точки зрения емкости хранилища.
Однако, поскольку хеш-функция MD5 была повреждена (она уязвима для атаки , любой атакующий может произвести 2 сталкивающихся активов в течение нескольких секунд стоит мощности процессора. Поэтому, если вы хотите использовать MD5, убедитесь, что такой злоумышленник не поставит под угрозу безопасность вашего приложения!
Кроме того, рассмотрите разветвления, если атакующий злоумышленник может создать столкновение с существующим активом в вашей базе данных. Хотя таких известных атак нет (preimage attack) против MD5 (по состоянию на 2011 год), это может стать возможным, распространяя текущие исследования на столкновение атак.
Если это окажется проблемой, я предлагаю посмотреть на хэш-функции SHA-2 (SHA-256, SHA-384 и SHA-512). Недостатком является то, что он немного медленнее и имеет более длинный выход хеширования.
Ответ 2
MD5 является хеш-функцией - так что да, две разные строки могут полностью генерировать встречные коды MD5.
В частности, обратите внимание, что коды MD5 имеют фиксированную длину, поэтому возможное количество кодов MD5 ограничено. Число строк (любой длины), однако, определенно неограничено, поэтому логически следует, что должны быть столкновения.
Ответ 3
Да, это возможно. Это фактически проблема с днем рождения. Однако вероятность двух случайно выбранных строк, имеющих один и тот же MD5-хэш, очень мала.
Ответ 4
Да, конечно: хеши MD5 имеют конечную длину, но существует бесконечное количество возможных строк символов, которые могут быть хешированы MD5.
Ответ 5
Да, это возможно. Он называется Hash collision.
Сказав это, алгоритмы, такие как MD5, предназначены для минимизации вероятности столкновения.
Википедия в MD5 объясняет некоторые уязвимости в MD5, о которых вы должны знать.
Ответ 6
Просто быть более информативным.
С математической точки зрения функции Хэша не инъективные.
Это означает, что между стартовым набором и полученным результатом нет отношения 1 к 1 (но одностороннему).
EDIT: существуют полные инъективные хэш-функции: он называется Идеальное хеширование.
Ответ 7
Да, возможно, что две разные строки могут генерировать один и тот же хэш-код 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: Construct MD5 Collisions, используя только один блок сообщений, 2010.
по теме:
Ответ 8
Да, это так! Столкновение будет возможно (хотя риск очень мал). Если нет, у вас будет довольно эффективный метод сжатия!
EDIT. Как говорит Конрад Рудольф: потенциально неограниченный набор входных данных, преобразованный в конечный набор результатов (32 шестнадцатеричных символа), приведет к бесконечному количеству столкновений.
Ответ 9
Как говорили другие люди, да, могут быть столкновения между двумя разными входами. Однако, в вашем случае использования, я не вижу, что это проблема. Я очень сомневаюсь, что вы столкнетесь с конфликтами - я использовал MD5 для снятия отпечатков пальцев сотен тысяч файлов изображений из нескольких изображений (JPG, bitmap, PNG, raw) на предыдущем задании, и у меня не было столкновения.
Однако, если вы пытаетесь отпечатать какие-либо данные, возможно, вы можете использовать два алгоритма хеширования - вероятность одного входа, приводящая к тому же выходу двух разных алгоритмов, практически невозможна.
Ответ 10
Я думаю, нам нужно тщательно выбирать алгоритм хэширования согласно нашему требованию, поскольку хеш-коллизии не так редки, как я ожидал. Недавно я нашел очень простой случай хеш-коллизии в моем проекте. Я использую Python-оболочку xxhash для хеширования. Ссылка: https://github.com/ewencp/pyhashxx
s1 = 'mdsAnalysisResult105588'
s2 = 'mdsAlertCompleteResult360224'
pyhashxx.hashxx(s1) # Out: 2535747266
pyhashxx.hashxx(s2) # Out: 2535747266
Это вызвало очень сложную проблему кэширования в системе, и я наконец обнаружил, что это столкновение хэшей.
Ответ 11
Я понимаю, что это старо, но я думал, что внесет свое решение. Есть 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