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

Для каждого из наших бинарных активов мы генерируем хеш MD5. Это используется, чтобы проверить, есть ли определенный двоичный актив уже в нашем приложении. Но возможно ли, что два разных бинарных актива генерируют один и тот же хеш MD5? Возможно ли, что две разные строки генерируют один и тот же хэш MD5?

Для набора даже миллиардов активов вероятность случайных столкновений ничтожно мала - вам не о чем беспокоиться. Учитывая парадокс дня рождения , учитывая набор из 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, очень мала.

См. Примеры в этом и этом вопросах.

Да, конечно: хеши 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: Single-block collision для 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 and Dengguo Feng: Construct MD5 Collisions Using Just A Single Block of Message , 2010.

Связанный:

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

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

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

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

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

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

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

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

РЕДАКТИРОВАТЬ : Как говорит Конрад Рудольф: потенциально неограниченный набор входных данных, преобразованный в конечный набор выходных данных (32 шестнадцатеричных символа), приведет к бесконечному количеству столкновений.

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

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

Я понимаю, что это устарело, но думал, что внесу свое решение. Есть 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

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

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

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