Wie genau ist `md5sum`?

27

Bei der Verwendung md5sumder Integrität einer Datei , um zu überprüfen, wie genau ist der Prozess?

Bedeutet ein verifiziertes MD5, dass JEDES Bit genau gleich ist, oder gibt es einen Schwellenwert, der unterbrochen werden muss, bevor die binäre Änderung im MD5 widergespiegelt wird?

Jede Dokumentation darüber, wie ein MD5 generiert wird, wäre auch dankbar.

Konner Rasmussen
quelle
@choroba Wenn ich das alles richtig lese, steigt die Wahrscheinlichkeit einer unentdeckten Veränderung mit der Größe der zu überprüfenden Datei. Es ist jedoch immer noch eine Wahrscheinlichkeit und 100% Sicherheit kann nur mit einer 16-Byte-Datei gehabt werden. Hab ich recht?
Konner Rasmussen
@Konner Ich habe deine Frage gelesen, die sich mit Dateiübertragung befasst. Zu diesem Zweck ist es sicher. Die Wahrscheinlichkeit, dass bei einer Übertragung etwas beschädigt wird, ist gering, und es ist wahrscheinlicher, dass Sie bei der Übertragung einen Teil der kopierten Datei verlieren, vorausgesetzt, ich habe Ihre vorherige Situation verstanden . MD5 ist bemüht, beide Dateien zu vergleichen, mit dem Vorteil, dass Sie nicht auf beide Dateien gleichzeitig zugreifen müssen.
Doktoro Reichard
15
"Bedeutet ein verifiziertes MD5, dass JEDES Bit genau gleich ist?" Beachten Sie, dass dies dank des Pigeonhole-Prinzips nicht möglich ist. en.wikipedia.org/wiki/Pigeonhole_principle
Plutor
3
Ich glaube nicht, dass Sie eine Garantie für 16-Byte-Dateien erhalten.
Mooing Duck

Antworten:

65

MD5 wird zu diesem Zweck gegen einen intelligenten Gegner gebrochen. Es ist möglich, böswillig zwei verschiedene Datenblöcke zu erstellen, die denselben MD5-Hash erzeugen.

Es ist jedoch durchaus geeignet (obwohl es mit ziemlicher Sicherheit bessere Möglichkeiten gibt), MD5 zum Schutz vor versehentlicher Datenkorruption während des Transports oder der Speicherung zu verwenden. Während es denkbar ist, dass ein solches Ereignis dazu führen könnte, dass der MD5-Hash gleich ist, ist die Wahrscheinlichkeit so gering, dass es fast unvorstellbar ist, dass es sich um eine bedenkenswerte Wahrscheinlichkeit handelt. Ausfälle durch Hintergrundstrahlung, Tunneleffekte, statische Aufladung und Dutzende anderer Quellen wären um Größenordnungen wahrscheinlicher.

Selbst wenn Sie Billiarden Dateneinheiten hätten, ist die Wahrscheinlichkeit, dass ein nicht übereinstimmender MD5 einen MD5-Hash erzeugt, der zu einer dieser Billiarden Einheiten gehört, viel geringer als eine Billiarde.

David Schwartz
quelle
Theoretisch ist es zwar möglich, zwei Dateien mit demselben Hash zu generieren, praktisch ist dies jedoch nicht möglich. Vor allem, wenn die Ersatzdatei auch Sinn machen soll. Wenn es sich bei der Originaldatei beispielsweise um englischen Text handelte, gibt es möglicherweise keine andere Übereinstimmung, die auch englisch ist. Wenn es sich um eine Excel-Tabelle handelt, ist keine der anderen Dateien mit demselben Hash eine gültige Tabelle.
Barmar
1
@Barmar: win.tue.nl/hashclash/Nostradamus Diese Jungs haben eine Reihe von PDF-Dateien mit demselben MD5-Hash erstellt, um zu beweisen, dass dies praktisch machbar ist.
Philfr
26

MD5 ist ein Hash. Grundsätzlich wird der gesamte Inhalt einer Datei in eine kleine Zeichenfolge mit einer Länge von 16 Byte (IIRC) abgebildet.

Es wird offensichtlich mehrere Dateien geben, die die gleiche MD5-Summe haben. Daher ist eine übereinstimmende MD5-Summe keine Garantie für eine genaue Übereinstimmung zwischen Dateien.

Es gibt keine Schwelle als solche, da die Art und Weise, wie Hashes funktionieren. So kann eine MD5-Summe sogar eine einzelne Bitänderung erfassen. Viele einzelne Bitänderungen zusammen können jedoch dazu führen, dass der MD5-Hash identisch ist. Es ist daher durchaus sinnvoll, MD5 zu verwenden, um die Dateiintegrität gegen zufällige Beschädigung zu überprüfen. Wenn jedoch eine böswillige Absicht vorliegt, kann eine Datei geändert werden, während sichergestellt wird, dass der MD5-Hash identisch ist.

Itai
quelle
1
So lang ist die Rede davon, dass ein md5 nichts anderes als eine schnelle und schmutzige Methode zur Überprüfung der Dateiintegrität ist und nur verwendet werden sollte, wenn ein nicht erkannter Fehler keine katastrophalen Auswirkungen hätte ... richtig?
Konner Rasmussen
3
Die beste Verwendung ist die Erkennung von Beschädigungen während der Übertragung oder des Kopierens. Nicht wirklich als Sicherheitssache.
Michael Martinez
12
@KonnerRasmussen - es geht nicht um das Ausmaß der Auswirkungen, sondern um die Art der Bedrohung. Wenn Sie befürchten, dass zwei Dokumente versehentlich dasselbe MD5 haben könnten, machen Sie sich keine Sorgen mehr: Die Wahrscheinlichkeit, dass Ihre Computer spontan in Flammen aufgehen, ist erheblich höher. Wenn Sie befürchten, ein intelligenter Angreifer könnte ein Dokument erstellen, das mit dem bereits vorhandenen Dokument übereinstimmt, ist dies ein ernstes Problem, und Sie sollten einen besseren Hash erhalten. Wenn Sie befürchten, ein intelligenter Angreifer könnte zwei Dokumente erstellen, die zueinander passen, machen Sie sich keine "Sorgen": Es wird mit Sicherheit passieren.
Malvolio
5
Zwar ist die Generierung einer MD5-Hash-Kollision theoretisch möglich, doch die Generierung einer nützlichen Kollision (da es sich bei der kollidierenden Datei um denselben Dateityp handelt und deren Inhalt zumindest plausibel authentisch ist) ist viel schwieriger ...
Shadur
6
@Shadur: Das war früher der Fall, aber die laufende Sicherheitsforschung hat neue Wege gefunden, um MD5-Kollisionen zu erzeugen, die dies erleichtern. Insbesondere wenn Ihr Dateiformat Blöcke von "Kommentar" -Daten im freien Format zulässt, ist es möglich, jeden MD5-Hash zuzuordnen, indem Sie einen geeigneten Kommentar einfügen.
MSalters
17

Ein MD5-Hash besteht aus 128 Bit. Ein einzelnes gekipptes Bit in der Quelle kippt (im Durchschnitt) 64 Bits im Hash.

Die Wahrscheinlichkeit, dass zwei Hashes versehentlich kollidieren, ist 1/2 ^ 128, was 1 zu 340 undecillion 282 decillion 366 nonillion 920 octillion 938 septillion 463 sextillion 463 quintillion 374 quadrillion 607 trillion 431 milliarden 768 millionen 211 tausend 456 ist.

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

Quelle: porneL, https://stackoverflow.com/questions/201705/how-many-random-elements-before-md5-produces-collisions

Zsolt Szilagy
quelle
8
Sie sagen also, es gibt noch eine Chance? : p
Holloway
1
Das Problem ist, dass Sie, obwohl Sie 100 Jahre lang 6 Milliarden Dateien pro Sekunde hacken MÜSSEN, sicher sein müssen, dass Sie eine Kollision finden. es könnte durchaus innerhalb der ersten Sekunde passieren.
Deroby
Es ist wahr, es könnte in der ersten Sekunde passieren. Aber wie immer geht es um ausgleichende Gründe. Es könnte militärische Anwendungen geben, bei denen dieses Risiko nicht akzeptabel ist, aber ich würde ohne nachzudenken ein Auto mieten, bei dem die Airbagsensoren md5 verwenden. Denken Sie daran, es besteht die Möglichkeit, dass Sie mehrmals vom Blitz getroffen werden, während Sie auf eine MD5-Kollision warten.
Zsolt Szilagy
Es tut mir leid, aber die Hälfte von 2 ^ 128 ist 2 ^ 127, nicht 2 ^ 64.
Fischi
2
@fischi, lies den Link zum Geburtstagsparadoxon und auch en.wikipedia.org/wiki/Birthday_attack - es geht nicht nur darum, die Gesamtzahl der Hashes zu halbieren. Bei gegebenem Suchraum H beträgt die Anzahl der Hashes, die Sie generieren müssen, bevor Sie eine 50% ige Kollisionswahrscheinlichkeit erhalten, ungefähr sqrt ((pi / 2) * H). Wenn Sie mit 2 ^ 128 rechnen, erhalten Sie eine Zahl von ungefähr 2 ^ 64
Paul Dixon,