Können zwei verschiedene Zeichenfolgen denselben MD5-Hashcode generieren?

Für jedes unserer binären Assets generieren wir einen MD5-Hash. Hiermit wird überprüft, ob sich bereits ein bestimmtes binäres Asset in unserer Anwendung befindet. Es ist jedoch möglich, dass zwei verschiedene binäre Assets denselben MD5-Hash generieren. Ist es also möglich, dass zwei verschiedene Zeichenfolgen denselben MD5-Hash generieren?

Bei einer Reihe von Milliarden von Vermögenswerten ist die Wahrscheinlichkeit zufälliger Kollisionen vernachlässigbar gering - nichts, worüber Sie sich Sorgen machen sollten. In Anbetracht des Geburtstagsparadoxons ergibt sich bei einem Satz von 2 ^ 64 (oder 18.446.744.073.709.551.616) Vermögenswerten die Wahrscheinlichkeit eines einzelnen Vermögens MD5-Kollision innerhalb dieses Satzes 50%. In dieser Größenordnung würden Sie Google wahrscheinlich in Bezug auf die Speicherkapazität übertreffen.

Da die MD5-Hash-Funktion jedoch unterbrochen wurde (sie ist anfällig für Kollisionsangriffe ), kann jeder entschlossene Angreifer innerhalb von Sekunden 2 kollidierende Assets im Wert von CPU-Leistung erzeugen. Wenn Sie also MD5 verwenden möchten, stellen Sie sicher, dass ein solcher Angreifer die Sicherheit Ihrer Anwendung nicht beeinträchtigt!

Berücksichtigen Sie auch die Auswirkungen, wenn ein Angreifer eine Kollision mit einem vorhandenen Asset in Ihrer Datenbank fälschen könnte . Zwar sind keine derartigen Angriffe ( Preimage-Angriffe ) gegen MD5 (Stand 2011) bekannt, doch könnte dies durch die Ausweitung der aktuellen Forschung zu Kollisionsangriffen möglich werden.

Wenn sich herausstellt, dass dies ein Problem darstellt, empfehle ich einen Blick auf die SHA-2-Reihe von Hash-Funktionen (SHA-256, SHA-384 und SHA-512). Der Nachteil ist, dass es etwas langsamer ist und eine längere Hash-Ausgabe hat.

MD5 ist eine Hash-Funktion - also können zwei verschiedene Zeichenfolgen absolut kollidierende MD5-Codes erzeugen.

Beachten Sie insbesondere, dass MD5-Codes eine feste Länge haben, sodass die mögliche Anzahl von MD5-Codes begrenzt ist. Die Anzahl der Zeichenfolgen (beliebiger Länge) ist jedoch definitiv unbegrenzt, sodass logischerweise Folgerungen auftreten müssen .

Ja, es ist möglich. Dies ist in der Tat ein Geburtstagsproblem . Die Wahrscheinlichkeit, dass zwei zufällig ausgewählte Zeichenfolgen denselben MD5-Hash haben, ist jedoch sehr gering.

Beispiele hierfür finden Sie in dieser und dieser Frage.

Ja, natürlich: MD5-Hashes haben eine endliche Länge, aber es gibt unendlich viele mögliche Zeichenfolgen, die mit MD5 gehasht werden können.

Ja, es ist möglich, dass zwei verschiedene Zeichenfolgen denselben MD5-Hashcode generieren.

Hier ist ein einfacher Test mit einer sehr ähnlichen Binärnachricht in hexadezimaler Zeichenfolge:

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

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

Sie erzeugen unterschiedliche SHA-1-Summen, aber denselben MD5-Hashwert. Zweitens sind die Saiten sehr ähnlich, so dass es schwierig ist, den Unterschied zwischen ihnen zu finden.

Der Unterschied kann durch den folgenden Befehl festgestellt werden:

$ 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

Das obige Kollisionsbeispiel stammt von Marc Stevens: Einzelblockkollision für MD5 , 2012; Er erklärt seine Methode mit Quellcode ( alternativer Link zum Papier ).

Ein weiterer 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

Unterschiedliche SHA-1-Summe, der gleiche MD5-Hash.

Der Unterschied liegt in einem Byte:

$ 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

Das obige Beispiel stammt aus Tao Xie und Dengguo Feng: Konstruieren Sie MD5-Kollisionen mit nur einem einzigen Nachrichtenblock , 2010.

Verbunden:

• Gibt es zwei bekannte Zeichenfolgen mit demselben MD5-Hashwert? bei Crypto.SE

Ja, es ist möglich. Es wird eine Hash-Kollision genannt .

Algorithmen wie MD5 sollen jedoch die Wahrscheinlichkeit einer Kollision minimieren.

Der Wikipedia-Eintrag zu MD5 erklärt einige Schwachstellen in MD5, die Sie beachten sollten.

Nur um informativer zu sein. Aus mathematischer Sicht sind Hash-Funktionen nicht injektiv .
Dies bedeutet, dass zwischen dem Startsatz und dem resultierenden Satz keine 1: 1-Beziehung (sondern eine Einwegbeziehung) besteht.

Bijection auf Wikipedia

EDIT: Um vollständig zu sein, gibt es injektive Hash-Funktionen: Es heißt Perfect Hashing .

Ja, so ist es! Kollision wird eine Möglichkeit sein (obwohl das Risiko sehr gering ist). Wenn nicht, hätten Sie eine ziemlich effektive Komprimierungsmethode!

BEARBEITEN : Wie Konrad Rudolph sagt: Ein potenziell unbegrenzter Satz von Eingaben, der in einen endlichen Satz von Ausgaben (32 Hexadezimalzeichen) umgewandelt wird, führt zu einer endlosen Anzahl von Kollisionen.

Wie andere Leute gesagt haben, kann es zu Kollisionen zwischen zwei verschiedenen Eingaben kommen. In Ihrem Anwendungsfall sehe ich dies jedoch nicht als Problem. Ich bezweifle sehr, dass Sie auf Kollisionen stoßen werden. Ich habe MD5 zum Fingerabdruck von Hunderttausenden von Bilddateien in einer Reihe von Bildformaten (JPG, Bitmap, PNG, RAW) bei einem früheren Auftrag verwendet und hatte keine Kollision .

Wenn Sie jedoch versuchen, Daten per Fingerabdruck zu erfassen, können Sie möglicherweise zwei Hash-Algorithmen verwenden. Die Wahrscheinlichkeit, dass eine Eingabe zur gleichen Ausgabe von zwei verschiedenen Algorithmen führt, ist nahezu unmöglich.

Mir ist klar, dass dies alt ist, aber ich dachte, ich würde meine Lösung beitragen. Es gibt 2 ^ 128 mögliche Hash-Kombinationen. Und damit eine 2 ^ 64 Wahrscheinlichkeit eines Geburtstagsparadoxons. Während die unten stehende Lösung die Möglichkeit von Kollisionen nicht ausschließt, wird sie das Risiko sicherlich um einen sehr erheblichen Betrag reduzieren.

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

Was ich getan habe, ist, dass ich ein paar Hashes basierend auf der Eingabezeichenfolge zusammengestellt habe, um eine viel längere resultierende Zeichenfolge zu erhalten, die Sie als Ihren Hash betrachten ...

Mein Pseudocode dafür ist also:

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

Das ist zur praktischen Unwahrscheinlichkeit einer Kollision. Aber wenn Sie super paranoid sein wollen und es nicht passieren lassen können und Speicherplatz kein Problem ist (und auch keine Rechenzyklen) ...

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

Okay, nicht die sauberste Lösung, aber jetzt können Sie viel mehr damit spielen, wie selten Sie auf eine Kollision stoßen. Bis zu dem Punkt könnte ich Unmöglichkeit im wahrsten Sinne des Wortes annehmen.

Meiner Meinung nach ist die Möglichkeit einer Kollision selten genug, so dass ich dies als nicht "todsicher" betrachten werde, aber so unwahrscheinlich, dass es der Notwendigkeit entspricht.

Jetzt steigen die möglichen Kombinationen deutlich an. Während Sie eine lange Zeit damit verbringen könnten, wie viele Kombinationen Sie erhalten könnten, werde ich theoretisch sagen, dass es Sie BEDEUTEND mehr als die oben angegebene Zahl von landet

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

Wahrscheinlich um hundert weitere Ziffern oder so. Das theoretische Maximum, das dies Ihnen geben könnte, wäre

Mögliche Anzahl der resultierenden Zeichenfolgen:

528294531135665246352339784916516606518847326036121522127960709026673902556724859474417255887657187894674394993257128678882347559502685537250538978462939576908386683999005084168731517676426441053024232908211188404148028292751561738838396898767036476489538580897737998336

Ich denke, wir müssen vorsichtig sein, wenn wir den Hashing-Algorithmus gemäß unserer Anforderung auswählen, da Hash-Kollisionen nicht so selten sind, wie ich erwartet hatte. Ich habe kürzlich in meinem Projekt einen sehr einfachen Fall von Hash-Kollision gefunden. Ich benutze Python-Wrapper von xxhash zum Hashing. Link: https://github.com/ewencp/pyhashxx

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

Es verursachte ein sehr kniffliges Caching-Problem im System, dann stellte ich schließlich fest, dass es sich um eine Hash-Kollision handelt.