Message-Digest Algorithm 5

Grundidee und Bedeutung

Message-Digest Algorithm 5 (MD5) ist eine kryptographische Hashfunktion. Sie berechnet aus einer Nachricht beliebiger Länge deterministisch einen Hashwert fester Länge von 128 Bit. Ein solcher „Message Digest“ ist ein kurzer Zahlenwert, der die Nachricht repräsentiert. MD5 wurde 1991 von Ronald L. Rivest am Massachusetts Institute of Technology als Nachfolger von MD4 entwickelt.

Heute gilt MD5 als unsicher, weil es keine Kollisionsresistenz bietet. Das bedeutet, dass sich mit geringem Aufwand zwei unterschiedliche Nachrichten M und M′ erzeugen lassen, für die gilt: MD5(M) = MD5(M′). Auch die Preimage-Resistenz ist theoretisch gebrochen; ein entsprechender Angriff ist gegen MD5 jedoch nicht praktikabel. In Internetstandards und technischen Richtlinien, unter anderem von IETF und BSI, wird von der Verwendung von MD5 abgeraten.

Hashwerte und typische Eigenschaften

Ein 128 Bit langer MD5-Hashwert wird üblicherweise als 32-stellige Hexadezimalzahl dargestellt. Für die 59 Byte lange ASCII-Eingabe ergibt sich:

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

Bereits die Änderung eines einzigen Buchstabens führt wegen des Lawineneffekts zu einem vollständig anderen Hashwert:

md5("Frank jagt im komplett verwahrlosten Taxi quer durch Bayern") = 7e716d0e702df0505fc72e2b89467910

Der Hash der leeren Zeichenfolge lautet:

md5("") = d41d8cd98f00b204e9800998ecf8427e

Für einen vorgegebenen Hashwert ist es praktisch unmöglich, eine weitere Nachricht mit genau diesem Hashwert zu bestimmen. Diese Eigenschaft beschreibt die praktische Preimage-Resistenz, ist bei MD5 aber nur eingeschränkt gültig, weil ein theoretischer Angriff bekannt ist.

Aufbau und Berechnung

MD5 basiert auf der Merkle-Damgård-Konstruktion. Damit wird eine Nachricht variabler Länge in eine Ausgabe fester Länge von 128 Bit umgewandelt. Zunächst wird an die ursprüngliche Nachricht ein Bit mit dem Wert 1 angehängt. Danach folgen Nullen, bis die Nachrichtenlänge in Bits 448 modulo 512 beträgt. Anschließend wird eine 64-Bit-Zahl angehängt, die die ursprüngliche Nachrichtenlänge in Bits als Little-Endian-Integer kodiert. Die endgültige Länge ist dadurch durch 512 teilbar.

Eine Einweg-Kompressionsfunktion verarbeitet die Nachricht in aufeinanderfolgenden 512-Bit-Blöcken. Sie arbeitet mit einem 128-Bit-Puffer, der in die vier 32-Bit-Wörter A, B, C und D aufgeteilt ist. Beim ersten Nachrichtenblock werden diese mit festen Konstanten initialisiert. Jeder Block wird in vier Runden mit jeweils 16 Operationen verarbeitet, also insgesamt 64 Operationen.

Jede Operation verwendet eine nichtlineare Funktion, modulare Addition und eine bitweise Linksrotation. Die Addition erfolgt modulo 2³². Für die vier Runden werden die Funktionen F, G, H und I verwendet:

• F(X,Y,Z) = (X ∧ Y) ∨ (¬X ∧ Z)
• G(X,Y,Z) = (X ∧ Z) ∨ (Y ∧ ¬Z)
• H(X,Y,Z) = X ⊕ Y ⊕ Z
• I(X,Y,Z) = Y ⊕ (X ∨ ¬Z)

Dabei stehen ⊕, ∧, ∨ und ¬ für bitweises XOR, AND, OR und NOT. Das Ergebnis der Verarbeitung eines Blocks wird zur Verarbeitung des nächsten Blocks weiterverwendet. Nach dem letzten Block werden A, B, C und D zusammengefügt; daraus entsteht der 128 Bit lange MD5-Hashwert.

Pseudocode und technische Konstanten

Im Pseudocode sind alle Variablen vorzeichenlose 32-Bit-Werte und Berechnungen kongruent modulo 2³². Die Linksrotation wird definiert als:

linksrotation(x,c) = (x << c) binär or (x >> (32-c))

Die Rotationswerte s sind für die vier Runden festgelegt:

• s[0..15] = {7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22}
• s[16..31] = {5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20}
• s[32..47] = {4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23}
• s[48..63] = {6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21}

Die 64 Konstanten K[i] werden aus dem Vorkommateil des Betrags von sin(i + 1), multipliziert mit 2³², gebildet: K[i] = floor(abs(sin(i + 1)) × 2³²). Im Hauptteil werden je nach i unterschiedliche Funktionen und Nachrichtenwortpositionen g verwendet:

• 0 ≤ i ≤ 15: F = (B and C) or ((not B) and D), g = i
• 16 ≤ i ≤ 31: F = (B and D) or (C and (not D)), g = (5×i + 1) mod 16
• 32 ≤ i ≤ 47: F = B xor C xor D, g = (3×i + 5) mod 16
• 48 ≤ i ≤ 63: F = C xor (B or (not D)), g = (7×i) mod 16

Die Anfangswerte lauten a0 = 0x67452301, b0 = 0xEFCDAB89, c0 = 0x98BADCFE und d0 = 0x10325476. Für jeden Block werden zunächst A, B, C und D aus diesen Werten übernommen. Danach werden sie 64-mal aktualisiert: D wird zu C, C zu B, und B wird um eine Linksrotation des Ausdrucks A + F + K[i] + M[g] ergänzt; A übernimmt den vorherigen Wert von D. Nach dem Block werden A, B, C und D zu den bisherigen Hashwerten addiert. Der endgültige Digest ist die Little-Endian-Darstellung von a0, b0, c0 und d0.

Zur Effizienzsteigerung können in den ersten beiden Runden auch die äquivalenten Ausdrücke F = D xor (B and (C xor D)) sowie F = C xor (D and (B xor C)) verwendet werden.

Verwendung und Implementierungen

MD5 ist auf vielen Systemen und in vielen Programmiersprachen verfügbar. Unter den meisten Linux-Distributionen gehört md5sum zu den standardmäßig installierten coreutils. Auf BSD-abgeleiteten Betriebssystemen wie macOS gibt es das Kommando md5. Python stellt MD5 über die Bibliothek hashlib bereit. Auf vielen anderen Unix-Derivaten kann Python oder das meist installierte Programm OpenSSL verwendet werden. Windows ab Version 8.1 sowie Windows Server 2012 R2 enthalten standardmäßig das PowerShell-Cmdlet Get-FileHash.

Bei einer heruntergeladenen Datei kann ein Anbieter den zugehörigen MD5-Hashwert in einer weiteren Datei veröffentlichen. Ein Prüfprogramm berechnet den Hash der heruntergeladenen Datei; stimmen beide Werte überein, ist die Integrität hinsichtlich unbeabsichtigter Übertragungsfehler bestätigt. Gegen gezielte Manipulation schützt dieses Verfahren nicht: Bei einem Man-in-the-Middle-Angriff kann ein Angreifer sowohl die Datei als auch den angebotenen Hashwert verändern. Der Hashwert muss deshalb aus einer vertrauenswürdigen Quelle über einen sicheren Kanal bezogen werden, oder die Authentizität wird durch eine digitale Signatur beziehungsweise einen Message Authentication Code sichergestellt.

MD5 kann außerdem als deterministischer Generator von Pseudo-Zufallszahlen eingesetzt werden, etwa zur Realisierung einer Stromverschlüsselung. In Datenbanken kann es als Hashfunktion für Indizes dienen. MySQL und PostgreSQL besitzen MD5 als eingebaute Funktion. Ein Beispiel speichert neben einer URL deren 32-stelligen MD5-Wert und legt darauf einen eindeutigen Index an:

CREATE TABLE urls ( url VARCHAR(4096) DEFAULT NULL, url_md5 CHAR(32) GENERATED ALWAYS AS (MD5(url)) STORED, UNIQUE KEY index_url (url_md5) );

Sicherheitsprobleme und Angriffe

Die Sicherheitsprobleme von MD5 betreffen vor allem Kollisionen und die Verwendung beim Passwortschutz. Schon 1994 veröffentlichten Bert de Boer und Antoon Bosselaers Pseudokollisionen der Kompressionsfunktion. 1996 fand Hans Dobbertin eine echte Kollision für zwei unterschiedliche, speziell präparierte Nachrichten, allerdings in einer Variante mit anderen Initialisierungskonstanten. Praktische Angriffe waren damit zunächst noch nicht möglich.

Im August 2004 erzeugte eine chinesische Forschergruppe um Xiaoyun Wang systematisch Kollisionen. Bei einer Common-Prefix-Kollision darf der gemeinsame Nachrichtenanfang M₀, M₁, …, Mᵢ₋₁ frei gewählt werden. Danach folgen zwei präparierte, unterschiedliche Nachrichtenblockpaare Mᵢ, Mᵢ₊₁ und M′ᵢ, M′ᵢ₊₁. Wegen der Merkle-Damgård-Konstruktion kann anschließend an beide Nachrichten derselbe Suffix angehängt werden, ohne die gleiche Hashausgabe zu verlieren. Der Angriff erforderte zwei einzufügende 512-Bit-Blöcke, insgesamt 128 Bytes. Die Berechnung des ersten Angriffsblocks dauerte auf einem IBM-p690-Hochleistungsrechner etwa eine Stunde, die des zweiten bis zu fünf Minuten. Heute kann ein PC eine MD5-Kollision innerhalb von Sekunden berechnen.

Bei einer Chosen-Prefix-Kollision unterscheiden sich auch die Nachrichtenanfänge; sie ist daher aufwendiger. 2008 erzeugten Marc Stevens, Alexander Sotirov und weitere Beteiligte ein gefälschtes CA-Zertifikat, das gängige Webbrowser als vertrauenswürdige Zertifizierungsstelle anerkannten. Damit konnten prinzipiell SSL-Zertifikate für beliebige URLs gefälscht und HTTPS-Sicherheitsmechanismen umgangen werden. Für die Berechnung wurde ein Cluster aus 200 Sony PlayStation 3 verwendet. Die 2012 entdeckte Windows-Malware Flame nutzte ein gefälschtes Code-Signing-Zertifikat, das auf einer neuen Variante einer Chosen-Prefix-Kollision beruhte.

Seit 2009 ist außerdem ein theoretischer Preimage-Angriff bekannt. Er erfordert 2^123,4 MD5-Hashoperationen und ist damit praktisch nicht durchführbar. Ein Preimage-Angriff sucht zu einem vorgegebenen Hashwert MD5(M) die Nachricht M oder eine andere Nachricht M′ mit demselben Hashwert. Weil M dabei nicht frei gewählt werden kann, ist der Angriff schwieriger als ein Kollisionsangriff. Für gefälschte Dokumente zu einer bestehenden RSA-und-MD5-Signatur wäre ein Preimage-Angriff erforderlich; durch einen Kollisionsangriff können jedoch zwei Dokumente mit gleichem Hash erstellt werden, von denen zunächst das legitime signiert und anschließend durch das gefälschte ersetzt wird.

Zum Speichern von Passwörtern ist MD5 ebenfalls ungeeignet. Angreifer können bekannte Passwort-Hashwerte durch Brute-Force- oder Wörterbuchangriffe mit berechneten Kandidaten vergleichen. MD5 lässt sich auf Grafikprozessoren besonders effizient und parallel berechnen. Deshalb sind langsame, spezialisierte Verfahren wie bcrypt oder PBKDF2 besser geeignet.

Ein Salt ist eine zufällige Zeichenkette, die bei der Hashberechnung an das Passwort angefügt und zusammen mit dem Hashwert unverschlüsselt gespeichert wird. Ein einmaliges Salt pro Passwort verhindert, dass ein Angreifer dieselbe Berechnung gleichzeitig gegen viele Passwort-Hashes verwendet. Regenbogentabellen speichern vorberechnete Zeichenketten mit ihren Hashwerten und stellen einen Time-Memory-Tradeoff zwischen Rechenaufwand und Speicherbedarf dar. Ein individuelles Salt würde für jeden Salt eine eigene Tabelle erfordern und damit die Wiederverwendbarkeit der Tabellen weitgehend beseitigen.