Czy dwa różne ciągi mogą wygenerować ten sam kod skrótu MD5?

Dla każdego z naszych aktywów binarnych generujemy hash MD5. Służy to do sprawdzenia, czy określony zasób binarny jest już w naszej aplikacji. Ale czy jest możliwe, że dwa różne zasoby binarne generują ten sam skrót MD5. Czy jest więc możliwe, że dwa różne ciągi generują ten sam skrót MD5?

W przypadku zestawu równych miliardów aktywów szanse przypadkowych kolizji są pomijalnie małe - nie ma się czym martwić. Biorąc pod uwagę paradoks urodzin , biorąc pod uwagę zestaw 2 ^ 64 (lub 18 446 744 073 709 551 616) aktywów, prawdopodobieństwo pojedynczej kolizji MD5 w tym zestawie wynosi 50%. W tej skali prawdopodobnie pokonałbyś Google pod względem pojemności.

Jednak ponieważ funkcja skrótu MD5 została zepsuta (jest podatna na atak kolizyjny ), każdy zdeterminowany atakujący może wyprodukować 2 kolidujące zasoby w ciągu kilku sekund mocy procesora. Jeśli więc chcesz korzystać z MD5, upewnij się, że taka osoba atakująca nie naruszy bezpieczeństwa Twojej aplikacji!

Weź również pod uwagę konsekwencje, jeśli osoba atakująca może sfałszować kolizję z istniejącym zasobem w bazie danych. Chociaż nie ma takich znanych ataków (ataków przedobrazowych ) na MD5 (stan na 2011 r.), Mogłoby to stać się możliwe dzięki rozszerzeniu obecnych badań nad atakami kolizyjnymi.

Jeśli okażą się one problemem, proponuję przyjrzeć się serii funkcji skrótu SHA-2 (SHA-256, SHA-384 i SHA-512). Wadą jest to, że jest nieco wolniejszy i ma dłuższą wydajność mieszania.

MD5 to funkcja skrótu - tak, dwa różne ciągi znaków mogą absolutnie generować kolidujące kody MD5.

W szczególności należy zwrócić uwagę, że kody MD5 mają stałą długość, więc możliwa liczba kodów MD5 jest ograniczona. Liczba łańcuchów (dowolnej długości) jest jednak zdecydowanie nieograniczona, więc logicznie wynika, że muszą wystąpić kolizje.

Tak to mozliwe. W rzeczywistości jest to problem z urodzinami . Jednak prawdopodobieństwo, że dwa losowo wybrane ciągi mają ten sam skrót MD5, jest bardzo niskie.

Przykłady można znaleźć w tym i tym pytaniu.

Tak, oczywiście: skróty MD5 mają skończoną długość, ale istnieje nieskończona liczba możliwych ciągów znaków, które można zaszyfrować MD5.

Tak, jest możliwe, że dwa różne ciągi mogą generować ten sam kod skrótu MD5.

Oto prosty test wykorzystujący bardzo podobną wiadomość binarną w postaci ciągu szesnastkowego:

$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c6b384c4968b28812b676b49d40c09f8af4ed4cc  -
008ee33a9d58b51cfeb425b0959121c9

$ echo '4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
c728d8d93091e9c7b87b43d9e33829379231d7ca  -
008ee33a9d58b51cfeb425b0959121c9

Generują inną sumę SHA-1, ale tę samą wartość skrótu MD5. Po drugie struny są bardzo podobne, więc trudno znaleźć między nimi różnicę.

Różnicę można znaleźć za pomocą następującego polecenia:

$ 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

Powyższy przykład kolizji pochodzi z Marc Stevens: Kolizja pojedynczego bloku dla MD5 , 2012; wyjaśnia swoją metodę za pomocą kodu źródłowego ( alternatywny link do artykułu ).

Kolejny test:

$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
756f3044edf52611a51a8fa7ec8f95e273f21f82  -
cee9a457e790cf20d4bdaa6d69f01e41

$ echo '0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef' | xxd -r -p | tee >/dev/null >(md5) >(sha1sum)
6d5294e385f50c12745a4d901285ddbffd3842cb  -
cee9a457e790cf20d4bdaa6d69f01e41

Różne sumy SHA-1, ten sam skrót MD5.

Różnica jest w jednym bajcie:

$ 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

Powyższy przykład jest zaadaptowany z Tao Xie i Dengguo Feng: Construct MD5 Collisions using Just A Single Block Of Message , 2010.

Związane z:

• Czy istnieją dwa znane ciągi, które mają tę samą wartość skrótu MD5? w Crypto.SE

Tak to mozliwe. Nazywa się to kolizją Hash .

Mimo to algorytmy takie jak MD5 są zaprojektowane tak, aby zminimalizować prawdopodobieństwo kolizji.

Wpis Wikipedii na temat MD5 wyjaśnia pewne luki w MD5, o których powinieneś wiedzieć.

Żeby być bardziej pouczającym. Z matematycznego punktu widzenia funkcje skrótu nie są iniekcyjne .
Oznacza to, że nie istnieje relacja 1 do 1 (ale jednokierunkowa) między zbiorem początkowym a wynikiem wynikowym.

Bijection na Wikipedii

EDYCJA: aby być kompletnym, istnieją iniekcyjne funkcje skrótu: nazywa się to Perfect haszowaniem .

Tak to jest! Kolizja będzie możliwa (choć ryzyko jest bardzo małe). Jeśli nie, miałbyś całkiem skuteczną metodę kompresji!

EDYCJA : Jak mówi Konrad Rudolph: Potencjalnie nieograniczony zestaw danych wejściowych przekonwertowanych na skończony zestaw danych wyjściowych (32 znaki szesnastkowe) spowoduje nieskończoną liczbę kolizji.

Jak powiedzieli inni ludzie, tak, mogą wystąpić kolizje między dwoma różnymi wejściami. Jednak w twoim przypadku użycia nie widzę w tym problemu. Bardzo wątpię, że będziesz miał kolizje - użyłem MD5 do odcisków palców setek tysięcy plików graficznych z wielu formatów obrazu (JPG, bitmapa, PNG, raw) w poprzedniej pracy i nie miałem kolizji .

Jeśli jednak próbujesz odcisnąć jakiś rodzaj danych, być może przydałyby się dwa algorytmy haszujące - prawdopodobieństwo, że jedno wejście skutkuje tym samym wyjściem dwóch różnych algorytmów, jest prawie niemożliwe.

Zdaję sobie sprawę, że to stare, ale pomyślałem, że wniesie do mnie moje rozwiązanie. Istnieje 2 ^ 128 możliwych kombinacji skrótów. A zatem prawdopodobieństwo wystąpienia paradoksu urodzin wynosi 2 ^ 64. O ile poniższe rozwiązanie nie wyeliminuje możliwości kolizji, to z pewnością znacznie zmniejszy to ryzyko.

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

To, co zrobiłem, to zestawienie kilku skrótów na podstawie ciągu wejściowego, aby uzyskać znacznie dłuższy ciąg wynikowy, który uważasz za swój hash ...

Więc mój pseudokod do tego to:

Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string))

Oznacza to praktyczne nieprawdopodobieństwo zderzenia. Ale jeśli chcesz być super paranoikiem i nie możesz tego zrobić, a przestrzeń dyskowa nie jest problemem (ani cykle obliczeniowe) ...

Result = Hash(string) & Hash(Reverse(string)) & Hash(Length(string)) 
         & Hash(Reverse(SpellOutLengthWithWords(Length(string)))) 
         & Hash(Rotate13(string)) Hash(Hash(string)) & Hash(Reverse(Hash(string)))

Okej, nie jest to najczystsze rozwiązanie, ale teraz dużo więcej bawisz się tym, jak rzadko zderzasz się z kolizją. Do tego stopnia, że ​​mogę założyć niemożliwość we wszystkich realistycznych znaczeniach tego terminu.

Ze względu na mnie myślę, że możliwość kolizji jest na tyle rzadka, że ​​uznam to za nie „pewne”, ale tak mało prawdopodobne, że będzie to odpowiadało potrzebom.

Teraz liczba możliwych kombinacji znacznie wzrasta. Chociaż mógłbyś spędzić dużo czasu na tym, ile kombinacji to może ci dać, powiem teoretycznie, że daje ci to ZNACZĄCO więcej niż cytowana powyżej liczba

2^64 (or 18,446,744,073,709,551,616) 

Prawdopodobnie o sto cyfr więcej. Teoretyczne maksimum, jakie mogłoby to dać, byłoby

Możliwa liczba wynikowych ciągów:

528294531135665246352339784916516606518847326036121522127960709026673902556724859474417255887657187894674394993257128678882347559502685537250538978462939576908386683999005084168731517676426441053024232908211188404148028292751561738838396898767036476489538580897737998336

Myślę, że musimy ostrożnie wybierać algorytm haszowania zgodnie z naszymi wymaganiami, ponieważ kolizje haszowania nie są tak rzadkie, jak się spodziewałem. Niedawno znalazłem w moim projekcie bardzo prosty przypadek kolizji hash. Używam opakowania Pythona xxhash do mieszania. Link: https://github.com/ewencp/pyhashxx

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

Spowodowało to bardzo trudny problem z buforowaniem w systemie, a potem w końcu odkryłem, że jest to kolizja hash.