Message-Digest Algorithm 5

MD5 (Message Digest Algorithm 5) ist eine weitverbreitete kryptographische Hash-Funktion, die einen 128-Bit-Hashwert erzeugt. MD5 wurde 1991 von Ronald L. Rivest entwickelt.

Geschichte

MD5 ist ein Vertreter aus einer Reihe von Hashfunktionen, die von Professor Ronald L. Rivest am MIT entwickelt wurden. Als Analysen ergaben, dass der Vorgänger MD4 wahrscheinlich unsicher ist, wurde MD5 1991 als sicherer Ersatz entwickelt. Tatsächlich wurden später von Hans Dobbertin Schwächen in MD4 gefunden.

1996 meldete Dobbertin eine Kollision in der Kompressionsfunktion von MD5. Dies war zwar kein Angriff auf die vollständige MD5-Funktion, dennoch empfahlen Kryptographen bereits damals, wenn möglich auf sicherere Algorithmen wie SHA-1 oder RIPEMD-160 umzusteigen. Im August 2004 fanden chinesische Forscher Kollisionen für die vollständige MD5-Funktion. Wie sich diese Entdeckung auf die Verwendung von MD5 auswirkt, bleibt abzuwarten.

Diese Attacken wirken sich allerdings nur auf Kollisionsangriffe aus, Preimage Angriffe können auch mit diesen Methoden nicht in sinnvoller Zeit durchgeführt werden. So kann ein bestehendes, mit MD5 erzeugtes Zertifikat nach wie vor nicht gefälscht werden.

MD5-Hashes

Die 128 Bit langen MD5-Hashes (englisch auch "message digests") werden normalerweise als 32-stellige Hexadezimalzahl notiert. Folgendes Beispiel zeigt eine 59 Byte lange ASCII-Eingabe und den zugehörigen MD5-Hash:

md5("Franz jagt im komplett verwahrlosten Taxi quer durch Bayern") = a3cca2b2aa1e3b5b3b5aad99a8529074

Eine kleine Änderung der Nachricht erzeugt (mit sehr großer Wahrscheinlichkeit) einen komplett anderen Hash. Mit dem ersten Zeichen als Kleinbuchstaben ergibt sich:

md5("franz jagt im komplett verwahrlosten Taxi quer durch Bayern") = 4679e94e07f9a61f42b3d7f50cae0aef

Der Hash eines Strings der Länge Null ist:

md5("") = d41d8cd98f00b204e9800998ecf8427e

MD5-Summen werden unter anderem von PGP verwendet und zur Integritätsprüfung von Dateien benutzt. Dabei wird die momentane MD5-Summe der Datei mit einer bekannten früheren Summe verglichen. So kann festgestellt werden, ob die Datei verändert oder beschädigt wurde. Auf Unix-artigen sowie Windows-Betriebssystemen gibt es dazu das Programm md5sum.

Algorithmus

MD5 erzeugt aus einer Nachricht variabler Länge eine Ausgabe fester Länge (128 Bit). Die Eingabenachricht wird in 512-Bit-Blöcke aufgeteilt. Die Nachricht wird dann aufgefüllt so dass ihre Länge durch 512 teilbar ist. Das Auffüllen geschieht folgendermaßen: Zunächst wird ein einzelnes Bit, 1, an das Ende der Nachricht gehängt. Es folgen so viele Nullen wie nötig sind, um die Nachricht auf eine Länge von 64 Bits weniger als dem nächsten Vielfachen von 512 zu bringen. Die übrigen Bits werden mit einer 64-Bit-Integerzahl aufgefüllt, die die ursprüngliche Länge der Nachricht repräsentiert.

Der Hauptalgorithmus von MD5 arbeitet mit einem 128-Bit-Puffer, der in vier 32-Bit-Wörter A, B, C und D unterteilt ist. Diese werden mit bestimmten Konstanten initialisiert. Auf diesen Puffer wird nun die Verschlüsselungsfunktion (häufig auch Komprimierungsfunktion genannt) mit dem ersten 512-Bit-Block als Schlüsselparameter aufgerufen. Die Behandlung eines Nachrichtenblocks geschieht in vier einander ähnlichen Stufen, von Kryptografen "Runden" genannt. Jede Runde ist aus 16 auf einer nichtlinearen Funktion "F", modularer Addition und Linksrotation basierenden Operationen zusammengesetzt. Es gibt vier mögliche "F"-Funktionen, in jeder Runde wird davon eine andere verwendet:

$F(X,Y,Z)=(X\wedge {Y})\vee (\neg {X}\wedge {Z})$

$G(X,Y,Z)=(X\wedge {Z})\vee (Y\wedge \neg {Z})$

$H(X,Y,Z)=X\oplus Y\oplus Z$

$I(X,Y,Z)=Y\oplus (X\vee \neg {Z})$

$\oplus ,\wedge ,\vee ,\neg$ stehen jeweils für XOR, AND, OR und NOT-Operationen.

Auf das Ergebnis wird dieselbe Funktion mit dem zweiten Nachrichtenblock als Parameter aufgerufen, und so weiter bis zum letzten 512-Bit-Block. Als Ergebnis wird wiederum ein 128-Bit-Wert geliefert, die MD5-Summe.

Sicherheitsüberlegungen

MD5 ist weitverbreitet und wurde ursprünglich als kryptografisch sicher angesehen. Bereits 1994 wurden von Bert den Boer und Antoon Bosselaers Pseudo-Kollisionen in MD5 entdeckt. Grundlegende Arbeit, um echte Kollisionen zu finden, wurde auch von Professor Hans Dobbertin (damals BSI, heute Universität Bochum) geleistet, der bereits den erfolgreichen Angriff auf MD4 entwickelt hatte, und die dabei verwendeten Techniken auf MD5 übertrug. Zwischenzeitlich war es ihm gelungen, eine in den Parametern modifizierte Version von MD5 zu brechen.

Die Brute-Force-Methode

Paul C. van Oorschot und Michael J. Wiener legten 1994 das Konzept einer Brute-Force-Attacke auf MD5 vor, die mit Hilfe eines damals 10 Millionen US-Dollar teuren fiktiven Rechners durchgeführt werden sollte, der speziell auf diese Aufgabe ausgelegt war. Damit sollte es theoretisch möglich sein, innerhalb von 24 Tagen eine Kollision in MD5 zu finden. Im März 2004 startete das Projekt MD5CRK, das eine solche Kollision mit 0 Dollar Kosten finden wollte, indem man das Konzept des verteilten Rechnens ausnutzt. Obwohl eine Kollision ohne jede Kontrolle über die Ausgangsdaten zunächst wertlos erscheint, erhoffte man sich durch MD5CRK im Erfolgsfall auch psychologische Effekte auf Unternehmen, die sicherheitsrelevante Prozesse noch immer über MD5 absichern.

Neben der obigen Attacke konnte Hans Dobbertin zeigen, dass die Kompressionsfunktion anfällig für Kollisionen ist. Diese Lücke konnte zunächst noch nicht ausgenutzt werden.

Die Analyse-Methode

Im August 2004 fand ein chinesisches Wissenschaftlerteam die erste Kollision in der vollständigen MD5-Funktion [1]. Auf einem IBM P690-Cluster benötigte ihr erster Angriff eine Stunde, davon ausgehend ließen sich weitere Kollisionen innerhalb von maximal fünf Minuten finden. Der Angriff der chinesischen Forscher basierte auf Analysen. Kurz nach der Veröffentlichung der Arbeit der Chinesen wurde MD5CRK eingestellt.

Kollisionen finden heißt, man kennt ein M (Text) und sucht ein M' (Kollision), so dass hash(M) = hash(M'). Wenn man nur den Hashwert hat, ist es weiterhin schwierig, eine Kollision für den Hash zu finden.

Deswegen besteht keine akute Gefahr für Passwörter die als MD5-Hash gespeichert wurden, diese Kollisionen sind eher eine Gefahr für Digitale Signaturen.

Modifikation HAVAL

HAVAL ist eine kryptografische Hashfunktion und weitere Modifikation von MD5.

Es können Hashwerte der Länge 128, 160, 192, 224 oder 256 Bit erzeugt werden.

Literatur

(auf Englisch)

• Hans Dobbertin, Cryptanalysis of MD5 compress. Announcement on Internet, May 1996 [2].
• Hans Dobbertin, The Status of MD5 After a Recent Attack, in CryptoBytes 2(2), 1996 [3].

Weblinks

• RFC 1321, The MD5 Message-Digest Algorithm; R. Rivest, April 1992
• http://eprint.iacr.org/2004/199.pdf - Veröffentlichung des chinesischen Teams über die erste Kollision
• http://pajhome.org.uk/crypt/md5/ - Online-Berechnung in Javascript von MD4-, MD5- und SHA-1-Werten zu eingegebenen Strings
• http://www.01-scripts.de/passgen.php - Online-Berechnung von MD5- und SHA-1-Werten zu eingegebenen Strings (ohne JavaScript)
• http://prefect.ch/ - eine MD5 Online Datenbank (knapp 6 Millionen Wörter)
• Jacksum Plattformunabhängiges Open Source Programm zum Berechnen und Verifizieren von u. a. MD5 Fingerprints