Message Digest Algorithm 5

Stichpunkte

Allgemein
	MD5 (Message Digest Algorithm 5) ist eine weitverbreitete kryptografische Hashfunktion
	die einen 128-Bit-Hashwert erzeugt
	MD5 wurde 1991 von Ronald L
	Rivest entwickelt
	werden möglicherweise auf sicherere Alternativen umsteigen. Inhaltsverzeichnis showTocToggle("Anzeigen"
	Im August 2004 wurden ernsthafte Sicherheitsmängel in MD5 entdeckt
	und viele Systeme
	die MD5 verwenden
	"Verbergen") 1 Geschichte 2 MD5-Hashes 3 Algorithmus 4 Sicherheitsüberlegungen 4.1 Die Brute-Force-Methode 4.2 Die Analyse-Methode 5 Literatur 6 Weblinks [Bearbeiten]
Geschichte
	die von Professor Ronald L
	MD5 ist ein Vertreter aus einer Reihe von Hashfunktionen
	Rivest am MIT entwickelt wurden
	dass MD5s Vorgänger — MD4 — wahrscheinlich unsicher war
	wurde MD5 1991 als sicherer Ersatz entwickelt
	Als Analysen ergaben
	Tatsächlich wurden später von Hans Dobbertin Schwächen in MD4 gefunden
	1996 meldete Dobbertin eine Kollision in der Kompressionsfunktion von MD5
	dennoch empfahlen Kryptographen bereits damals
	Dies war zwar kein Angriff auf die vollständige MD5-Funktion
	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
	bleibt abzuwarten. [Bearbeiten]
	Wie sich diese Entdeckung auf die Verwendung von MD5 auswirkt
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
	ob die Datei verändert oder beschädigt wurde
	So kann festgestellt werden
	Auf Unix-artigen sowie Windows-Betriebssystemen gibt es dazu das Programm md5sum. [Bearbeiten]
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
	an das Ende der Nachricht gehängt
	Das Auffüllen geschieht folgendermaßen: Zunächst wird ein einzelnes Bit
	1
	um die Nachricht auf eine Länge von 64 Bits weniger als dem nächsten Vielfachen von 512 zu bringen
	Es folgen so viele Nullen wie nötig sind
	die die ursprüngliche Länge der Nachricht repräsentiert
	Die übrigen Bits werden mit einer 64-Bit-Integerzahl aufgefüllt
	C und D unterteilt ist
	B
	der in vier 32-Bit-Wörter A
	Der Hauptalgorithmus von MD5 arbeitet mit einem 128-Bit-Puffer
	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
	von Kryptografen "Runden" genannt
	Die Behandlung eines Nachrichtenblocks geschieht in vier einander ähnlichen Stufen
	modularer Addition und Linksrotation basierenden Operationen zusammengesetzt
	Jede Runde ist aus 16 auf einer nichtlinearen Funktion "F"
	Y
	neg<math> stehen jeweils für XOR
	OR und NOT-Operationen
	Z) = X oplus Y oplus Z<math> <math>I(X
	Y
	Z) = (Xwedge{Y}) vee (neg{X} wedge{Z})<math> <math>G(X
	Z) = (Xwedge{Z}) vee (Y wedge neg{Z})<math> <math>H(X
	wedge
	Y
	AND
	vee
	Z) = Y oplus (X vee neg{Z})<math> <math>oplus
	in jeder Runde wird davon eine andere verwendet: <math>F(X
	Y
	Es gibt vier mögliche "F"-Funktionen
	Auf das Ergebnis wird dieselbe Funktion mit dem zweiten Nachrichtenblock als Parameter aufgerufen
	und so weiter bis zum letzten 512-Bit-Block
	die MD5-Summe. [Bearbeiten]
	Als Ergebnis wird wiederum ein 128-Bit-Wert geliefert
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
	wurde auch von Professor Hans Dobbertin (damals BSI
	um echte Kollisionen zu finden
	heute Universität Bochum) geleistet
	der bereits den erfolgreichen Angriff auf MD4 entwickelt hatte
	Grundlegende Arbeit
	und die dabei verwendeten Techniken auf MD5 übertrug
	eine in den Parametern modifizierte Version von MD5 zu brechen. [Bearbeiten]
	Zwischenzeitlich war es ihm gelungen
Die Brute-Force-Methode
	Paul C. van Oorschot und Michael J
	die mit Hilfe eines damals 10 Millionen US-Dollar teuren fiktiven Rechners durchgeführt werden sollte
	Wiener legten 1994 das Konzept einer Brute-Force-Attacke auf MD5 vor
	der speziell auf diese Aufgabe ausgelegt war
	Damit sollte es theoretisch möglich sein
	innerhalb von 24 Tagen eine Kollision in MD5 zu finden
	das eine solche Kollision mit 0 Dollar Kosten finden wollte
	indem man das Konzept des verteilten Rechnens ausnutzt
	Im März 2004 startete das Projekt MD5CRK
	die sicherheitsrelevante Prozesse noch immer über MD5 absichern
	erhoffte man sich durch MD5CRK im Erfolgsfall auch psychologische Effekte auf Unternehmen
	Obwohl eine Kollision ohne jede Kontrolle über die Ausgangsdaten zunächst wertlos erscheint
	dass die Kompressionsfunktion anfällig für Kollisionen ist
	Neben der obigen Attacke konnte Hans Dobbertin zeigen
	Diese Lücke konnte zunächst noch nicht ausgenutzt werden. [Bearbeiten]
Die Analyse-Methode
	Im August 2004 fand ein chinesisches Wissenschaftlerteam die erste Kollision in der vollständigen MD5-Funktion [1] (http://eprint.iacr.org/2004/199.pdf)
	davon ausgehend ließen sich weitere Kollisionen innerhalb von maximal fünf Minuten finden
	Auf einem IBM P690-Cluster benötigte ihr erster Angriff eine Stunde
	Der Angriff der chinesischen Forscher basierte auf Analysen
	Kurz nach der Veröffentlichung der Arbeit der Chinesen wurde MD5CRK eingestellt
	man kennt ein M (Text) und sucht ein M' (Kollision)
	Kollisionen finden heißt
	so dass hash(M) = hash(M')
	Wenn man nur den Hashwert hat
	eine Kollision für den Hash zu finden
	ist es weiterhin schwierig
	diese Kollisionen sind eher eine Gefahr für Digitale Signaturen. [Bearbeiten]
	Deswegen besteht keine akute Gefahr für Passwörter die als MD5-Hash gespeichert wurden
Literatur
	Cryptanalysis of MD5 compress
	(auf Englisch) Hans Dobbertin
	Announcement on Internet
	May 1996 [2] (http://citeseer.ist.psu.edu/dobbertin96cryptanalysis.html). Hans Dobbertin
	The Status of MD5 After a Recent Attack
	in CryptoBytes 2(2)
	1996 [3] (http://www.rsasecurity.com/rsalabs/node.asp?id=2149). [Bearbeiten]
Weblinks
	The MD5 Message-Digest Algorithm; R
	RFC 1321
	Rivest
	MD5- und SHA-1-Werten zu eingegebenen Strings [5] (http://www.01-scripts.de/passgen.php) - Online-Berechnung von MD5- und SHA-1-Werten zu eingegebenen Strings (ohne JavaScript) [6] (http://eprint.iacr.org/2004/199.pdf) - Veröffentlichung des chinesischen Teams über die erste Kollision [7] (http://passcracking.com/) - ein MD5 Online Cracking Dienst Jacksum (http://www.jonelo.de/java/jacksum/index.html) Plattformunabhängiges Open Source Programm zum Berechnen und Verifizieren von u. a
	April 1992 [4] (http://pajhome.org.uk/crypt/md5/) - Online-Berechnung von MD4-
	MD5 Fingerprints Prüfsummen Assistent (http://www.iss-datasecurity.de/pa/) Windows-Programm zum Berechnen und Verifizieren von u. a
	MD5 Fingerprints md5 Kurzübersicht und Prüfsummen (http://www.dseitz.de/md5) Kurze Einführung und Beispiel zum md5 Verfahren Siehe auch: Hash-Funktion und die dort genannten Verfahren und Kryptographie en:MD5 fi:MD5 fr:MD5 ja:MD5 pl:MD5

Dieser Artikel basiert auf dem Artikel Message Digest Algorithm 5 aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.