Wie viele zufällige Elemente, bevor MD5 Kollisionen erzeugt?

164

Ich habe eine Bildbibliothek auf Amazon S3. Für jedes Bild md5 ich die Quell-URL auf meinem Server plus einen Zeitstempel, um einen eindeutigen Dateinamen zu erhalten. Da S3 keine Unterverzeichnisse haben kann, muss ich alle diese Bilder in einem einzigen flachen Ordner speichern.

Muss ich mir Gedanken über Kollisionen im MD5-Hashwert machen, die erzeugt werden?

Bonus: Wie viele Dateien könnte ich haben, bevor Kollisionen im von MD5 erzeugten Hashwert auftreten?

random md5 hash Ben Throop
quelle
1
Verwandte: Gibt es zwei bekannte Zeichenfolgen mit demselben MD5-Hashwert?
Kenorb
2
Die wörtliche Antwort lautet, dass die zweite Datei dieselbe MD5 wie die erste haben könnte. Die Chancen sind jedoch äußerst gering.
Rick James

Antworten:

306

Die Wahrscheinlichkeit, dass nur zwei Hashes versehentlich kollidieren, beträgt 1/2 128, was 1 zu 340 Undecillion 282 Decillion 366 Nonillion 920 Octillion 938 Septillion 463 Sextillion 463 Billionen 374 Billiarden 607 Billionen 431 Milliarden 768 Millionen 211 Tausend 456 entspricht.

Wenn Sie jedoch alle Hashes behalten, ist die Wahrscheinlichkeit dank des Geburtstagsparadoxons etwas höher . Um eine 50% ige Chance zu haben, dass ein Hash mit einem anderen Hash kollidiert, benötigen Sie 2 64 Hashes. Dies bedeutet, dass Sie für eine Kollision im Durchschnitt 100 Jahre lang 6 Milliarden Dateien pro Sekunde hashen müssen .

Kornel
quelle
20
"Kollisionswahrscheinlichkeit ist 1/2 ^ 64" - was? Die Wahrscheinlichkeit einer Kollision hängt von der Anzahl der bereits gehashten Elemente ab. Es handelt sich nicht um eine feste Anzahl. Tatsächlich ist es genau gleich 1 - sPn/s^n, wo sdie Größe des Suchraums ( 2^128in diesem Fall) und ndie Anzahl der gehashten Elemente ist. Was Sie wahrscheinlich denken 2^64, ist die ungefähre Anzahl von Elementen, die Sie für MD5-Hash benötigen, um eine 50% ige Kollisionswahrscheinlichkeit zu haben.
BlueRaja - Danny Pflughoeft
19
+1, weil ich schon immer wissen wollte, wie man über 999 Billionen lol hinaus zählt (und oh ja, Ihre Antwort war informativ)
Kmeixner
7
Leider bist du immer noch nicht korrekt. Sie gehen davon aus, dass die Hash-Funktion wirklich zufällig ist. Es ist nicht. Dies bedeutet, dass die Kollisionswahrscheinlichkeit höher ist.
Jørgen Fogh
22
JørgenFogh: Und alle Gesetze der Physik sind auch "nicht korrekt". Ein solches Maß an Pedantismus ist unnötig, da es die Antwort in keiner sinnvollen Weise ändert.
Kornel
20
Sie sagen also, es gibt eine Chance!
Vargonian
27

S3 kann Unterverzeichnisse haben. Geben Sie einfach ein "/" in den Schlüsselnamen ein, und Sie können auf die Dateien zugreifen, als wären sie in separaten Verzeichnissen. Ich verwende dies, um Benutzerdateien in separaten Ordnern basierend auf ihrer Benutzer-ID in S3 zu speichern.

Zum Beispiel: "mybucket / users / 1234 / somefile.jpg". Es ist nicht genau das gleiche wie ein Verzeichnis in einem Dateisystem, aber die S3-API verfügt über einige Funktionen, mit denen es fast gleich funktioniert. Ich kann ihn bitten, alle Dateien aufzulisten, die mit "users / 1234 /" beginnen, und es werden mir alle Dateien in diesem "Verzeichnis" angezeigt.

davr
quelle
7
Dies sollte ein Inhalt sein, den ich denke, da er die Frage nach der Wahrscheinlichkeit einer Kollision nicht wirklich beantwortet
Ian Clark
18

Also warte, ist es:

md5(filename) + timestamp

oder:

md5(filename + timestamp)

Wenn erstere, sind Sie meistens auf dem Weg zu einer GUID, und ich würde mir darüber keine Sorgen machen. Wenn letzteres der Fall ist, lesen Sie Kargs Beitrag darüber, wie Sie schließlich auf Kollisionen stoßen werden.

Ryan
quelle
1
Bitte erläutern Sie, wie das Einfügen des Zeitstempels die Wahrscheinlichkeit einer Kollision erhöht
Brad Thomas
14
@BradThomas: Das tut es nicht. Das MD5-Kollisionsrisiko ist das gleiche, unabhängig davon, ob es sich um den Dateinamen oder die Kombination aus Dateiname und Zeitstempel handelt. Im ersten Szenario müssten Sie jedoch sowohl eine MD5-Kollision als auch eine Zeitstempelkollision haben.
Vincent Hubert
2
Dies lässt immer noch eine 2 ^ (128 ^ 60) Chance auf eine Kollision mit zwei Benutzern pro Minute. Buchstäblich unbrauchbar.
Berry M.
2
@BradThomas Um es klarer zu machen: md5(filename) + timestampReduziert das Kollisionsrisiko massiv, da Sie eine MD5-Kollision benötigen würden, damit genau derselbe Zeitstempel eine Kollision insgesamt hat. md5(filename + timestamp)ist dasselbe wie md5(filename)unter der Annahme, dass der Dateiname zunächst zufällig ist (da das Hinzufügen von mehr Zufälligkeit zu etwas Zufälligem nur das individuelle md5-Ergebnis ändert und das Geburtstagsproblem immer noch in allen md5-Hashes besteht).
Robocat
10

Eine grobe Faustregel für Kollisionen ist die Quadratwurzel des Wertebereichs. Ihr MD5-Sig ist vermutlich 128 Bit lang, sodass Sie wahrscheinlich Kollisionen über 2 ^ 64 Bilder hinaus sehen werden.

Will Dean
quelle
1
Sie meinen wahrscheinlich 128 Bit, nicht 2 ^ 128. :-)
JesperE
5
en.wikipedia.org/wiki/Birthday_Problem Weitere Informationen zum Problem.
Georg Schölly
7

Obwohl zufällige MD5-Kollisionen äußerst selten sind, können Ihre Benutzer Kollisionen entwickeln, wenn sie Dateien bereitstellen können (die wörtlich gespeichert werden). Das heißt, sie können absichtlich zwei Dateien mit derselben MD5-Summe, aber unterschiedlichen Daten erstellen. Stellen Sie sicher, dass Ihre Anwendung diesen Fall auf vernünftige Weise behandeln kann, oder verwenden Sie möglicherweise einen stärkeren Hash wie SHA-256.

bdonlan
quelle
Die Verwendung eines Salzes würde das User-Engineering-Problem lösen, nicht wahr?
StackOverflowed
Es hängt davon ab, wie das Salz angewendet wird. Es müsste ein Präfix der vom Benutzer bereitgestellten Daten sein, oder besser noch der Schlüssel für eine HMAC. Es ist wahrscheinlich immer noch eine gute Idee, die Verteidigung gründlich zu üben.
Bdonlan
Beachten Sie, dass SHA256 zwar 256 Bit lang ist, Sie jedoch das Risiko von Kollisionen mit der Länge des gespeicherten Schlüssels abwägen können, indem Sie den SHA256 auf weniger Bit kürzen, z. B. SHA256 verwenden, aber auf 128 Bit kürzen (was sicherer ist als die Verwendung von MD5 sogar obwohl sie die gleiche Anzahl von Bits haben).
Robocat
5

Während es aufgrund von Kollisionen gut bekannt gewordene Probleme mit MD5 gab, sind unbeabsichtigte Kollisionen zwischen zufälligen Daten äußerst selten . Auf der anderen Seite, wenn Sie den Dateinamen hashen, sind das keine zufälligen Daten, und ich würde Kollisionen schnell erwarten.

Akrosman
quelle
Das einzige Problem, das ich mit Taylor Beispiel habe, ist, dass jemand, der eine Kopie Ihrer Datenbank erhält, die Kreditkartennummern wahrscheinlich anhand einer Regenbogentabelle herausfinden könnte ...
Sam Saffron
1
Obwohl ich MD5 nicht für Kreditkarten verwenden würde, ist eine Rainbow-Tabelle aller gültigen Kreditkartennummern zwischen 10.000.000 (8 Ziffern sind die kleinste Kreditkarte, die ich je gesehen habe) und 9.999.999.999.999.999 (größte 16-stellige Zahl) immer noch groß Tabelle zu generieren. Es gibt wahrscheinlich einfachere Möglichkeiten, diese Zahlen zu stehlen.
Akrosman
1

Es spielt keine Rolle, wie wahrscheinlich es ist; es ist möglich. Es könnte bei den ersten beiden Dingen passieren, die Sie hashen (sehr unwahrscheinlich, aber möglich), daher müssen Sie Kollisionen von Anfang an unterstützen.

Karg
quelle
36
Es kann natürlich viele andere schlechte Dinge geben, die mit einer Wahrscheinlichkeit von 1/2 ^ 128 passieren können. Vielleicht möchten Sie diesen nicht herausgreifen, um sich Sorgen zu machen.
Will Dean
2
Das Schlimmste, was hier passieren kann, ist, dass Sie ein Foto bekommen können. Für eine relativ kleine Anzahl würde ich mir keine Sorgen machen. Wenn Ihre Software einen Autopiloten steuert, der ein Flugzeug landet, ist das eine andere Geschichte.
Jim C
9
Du kannst es nicht ernst meinen. Sie müssen 100 Jahre lang jede Sekunde 6 Milliarden Dateien pro Sekunde hashen, um eine gute Kollisionswahrscheinlichkeit zu erzielen. Selbst wenn Sie sehr, sehr unglücklich sind, würde es wahrscheinlich mehr als die gesamte Kapazität von S3 benötigen, die länger als ein menschliches Leben verwendet wird.
Kornel
12
Es ist milliardenfach wahrscheinlicher, dass Ihre Datenbank und ihre Sicherungen alle fehlschlagen. Kollisionen sind keine Sorgen wert.
Artelius
5
Nutzen Sie die Zeit zur Kollisionsverhütung, um einen Bunker zu bauen und Ihren Server zu platzieren! Diese lästigen Meteore können dich treffen (sehr unwahrscheinlich, aber möglich), daher musst du den Meteorschutz vor dem Betteln unterstützen.
polvoazul
1

Eine MD5-Kollision ist äußerst unwahrscheinlich. Wenn Sie haben 9 Billionen MD5 haben, gibt es nur eine Chance in 9 Billionen, dass es zu einer Kollision kommt.

Rick James
quelle
1
Viele der anderen Antworten sprechen von der Wahrscheinlichkeit einer Kollision, wenn ein weiteres Element hinzugefügt wird . Ich denke, meine Antwort ist nützlicher, weil sie davon spricht, dass wahrscheinlich der gesamte Tisch einen Dup hat.
Rick James
1
Dies hat nichts mit MD5 zu tun und ist nicht korrekt. Wenn Sie 9 Billionen Katzen haben, besteht eine Wahrscheinlichkeit von 1 zu 9 Billionen, dass jemand anderes eine identische Katze hat. Das Hauptproblem hierbei ist, dass Sie denselben Hash mit mehr als einem Wert erhalten können.
Joonas Alhonen
@JoonasAlhonen - Ja, das stimmt. Und viele arme Leute benutzen das als Ausrede, um noch einen Lottoschein zu kaufen, den sie sich nicht leisten können.
Rick James
Danke, das ist eigentlich eine sehr nützliche Statistik. Die Wahrscheinlichkeit einer Kollision beim Einsetzen von 9 Billionen Gegenständen. Vielen Dank.
Tom P.