Message-Digest Algorithm 5

Message-Digest Algorithm 5 (MD5) ist eine weit verbreitete kryptographische Hashfunktion, die aus einer beliebigen Nachricht einen 128-Bit-Hashwert erzeugt. Dies erlaubt beispielsweise die leichte Überprüfung eines Downloads auf Korrektheit. Sie ist ein Vertreter aus einer Reihe von kryptographischen Hashfunktionen, die 1991 von Ronald L. Rivest am Massachusetts Institute of Technology entwickelt wurde, als Analysen ergaben, dass sein Vorgänger MD4 wahrscheinlich unsicher ist. MD5 gilt inzwischen ebenfalls als nicht mehr sicher, da es mit überschaubarem Aufwand möglich ist, unterschiedliche Nachrichten zu erzeugen, die den gleichen MD5-Hashwert aufweisen, findet jedoch im nichtkryptographischen Bereich seinen Verwendungszweck aufgrund niedrigerer Rechenanforderungen.

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 des Textes erzeugt einen komplett anderen Hash. Beispielsweise ergibt sich mit Frank statt Franz (nur ein Buchstabe verändert):

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

Der Hash einer Zeichenfolge der Länge null ist:

md5("") = d41d8cd98f00b204e9800998ecf8427e

Verwendung und Verfügbarkeit

Unter den meisten Linux-Distributionen wird das Programm md5sum als Bestandteil der coreutils standardmäßig installiert.

Auf BSD-abgeleiteten Betriebssystemen wie macOS gibt es das Kommando md5.

Auf vielen anderen Unix-Derivaten kann man sich mit dem meist installierten Programm OpenSSL behelfen.

Microsoft-Windows-Betriebssysteme ab den Versionen Windows 8.1 bzw. Windows Server 2012 R2 verfügen standardmäßig über das PowerShell Cmdlet Get-Filehash.

Überprüfung des MD5-Hashwerts

Nach erfolgreichem Download einer Datei oder eines Ordners mit Dateien wird häufig in einer weiteren Datei der dazugehörige MD5-Hashwert zur Verfügung gestellt. Über ein Prüfprogramm kann dann wiederum der Hashwert aus der heruntergeladenen Datei berechnet werden, der dann mit dem zur Verfügung gestellten Hashwert verglichen wird. Sind beide Hashwerte identisch, ist die Integrität der heruntergeladenen Datei bestätigt. Demnach traten beim Download der Datei keine Fehler auf. Dies bietet keine Sicherheit hinsichtlich einer gezielten Datenmanipulation durch einen Angreifer (Man-in-the-Middle-Angriff), da der Angreifer auch die Übertragung des MD5-Hashwertes manipulieren kann.

Etwas anders stellt sich die Situation bei der Verwendung eines Spiegelservers für das Herunterladen von Dateien dar. Hier ist der Betreiber des Spiegelservers ein möglicher Angreifer. Um eine Manipulation durch diesen auszuschließen, muss der dazugehörige MD5-Hashwert jedoch nicht vom Spiegelserver, sondern von der Originalquelle geladen werden.

Algorithmus

Eine MD5-Operation. MD5 besteht aus 64 Operationen dieses Typs, gruppiert in 4 Durchläufen mit jeweils 16 Operationen. F ist eine nichtlineare Funktion, die im jeweiligen Durchlauf eingesetzt wird. M_i bezeichnet einen 32-Bit-Block des Eingabestroms und K_i eine für jede Operation unterschiedliche 32-Bit-Konstante; _s bezeichnet die bitweise Linksrotation um s Stellen, wobei s für jede Operation variiert. bezeichnet die Addition modulo 2³².

MD5 basiert auf der Merkle-Damgård-Konstruktion, um aus einer Nachricht variabler Länge eine Ausgabe fester Länge (128 Bit) zu erzeugen. Zuerst wird eine Eins an die Ausgangsnachricht angehängt. Danach wird die Ausgangsnachricht mit Nullen so aufgefüllt, dass ihre Länge 64 Bits davon entfernt ist, durch 512 teilbar zu sein. Nun wird eine 64-Bit-Zahl, die die Länge der Ausgangsnachricht codiert, angehängt. Die Nachrichtenlänge ist jetzt durch 512 teilbar.

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 Komprimierungsfunktion 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 besteht aus 16 Operationen, basierend auf einer nichtlinearen Funktion „F“, modularer Addition und Linksrotation. 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 usw., bis zum letzten 512-Bit-Block. Als Ergebnis wird wiederum ein 128-Bit-Wert geliefert – die MD5-Summe.

Referenzimplementierung

RFC1321 enthält auch unter dem Titel "Appendix A Reference Implementation" eine Implementierung des Algorithmus in C. Diese Implementierung aus dem Jahre 1992 von RSA Data Security, Inc. läuft auf vielen 64-Bit-Systemen fehlerhaft, sie berechnet falsche Hashwerte. Dies liegt daran, dass in der Datei global.h die Zeilen

/* UINT4 defines a four byte word */
typedef unsigned long int UINT4;

nicht notwendigerweise gegeben sind. Der Fehler kann behoben werden, indem man diese Zeilen durch

#include <inttypes.h>
...
/* UINT4 defines a four byte word */
typedef uint32_t UINT4;

ersetzt. Eine andere, lauffähige Implementierung von L Peter Deutsch findet man auf Sourceforge.net. Diese Implementation ist aus der Spezifikation des RFC1321 abgeleitet und nicht aus der vorher erwähnten Referenzimplementation in RFC1321. Darum sind bei Verwendung dieser Implementierung keinerlei Verweise auf RSA Data Security, Inc. notwendig.

Pseudocode

Es folgt der Pseudocode für den MD5-Algorithmus.

// Beachte: Alle Variablen sind vorzeichenlose (unsigned) 32-Bit-Werte und
// verhalten sich bei Berechnungen kongruent (≡) modulo 2^32

 // Definition der linksrotation Funktion, c ist der übergebene Wert von s[i] - siehe Hauptschleife
linksrotation(x, c)
    return (x << c)binär or (x >> (32-c));

// s definiert die Anzahl der Bits, die pro Runde rotiert werden:
var uint[64] s, K
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}

// Verwende den binären Vorkommateil vom 2^32-fachen Betrag des Sinus
// von Integerwerten als Konstanten:
für alle i von 0 bis 63
(
    K[i] := floor(abs(sin(i + 1)) × 2^32)
)

// Alternativ kann man auch folgende Tabelle nutzen:
K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee }
K[ 4.. 7] := { 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 }
K[ 8..11] := { 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be }
K[12..15] := { 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 }
K[16..19] := { 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa }
K[20..23] := { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 }
K[24..27] := { 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed }
K[28..31] := { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a }
K[32..35] := { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c }
K[36..39] := { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 }
K[40..43] := { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 }
K[44..47] := { 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 }
K[48..51] := { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 }
K[52..55] := { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 }
K[56..59] := { 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 }
K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 }

// Initialisiere die Variablen: (lt. RFC 1321)
var uint a0 := 0x67452301
var uint b0 := 0xEFCDAB89
var uint c0 := 0x98BADCFE
var uint d0 := 0x10325476

// Vorbereitung der Nachricht 'message':
var uint message_laenge := bit_length(message)
erweitere message um bit "1"
erweitere message um bits "0" bis Länge von message in bits ≡ 448 (mod 512)
erweitere message um message_laenge als 64-Bit little-endian Integer

// Verarbeite die Nachricht in aufeinander folgenden 512-Bit-Blöcken:
für alle 512-Bit Block von message
(
    unterteile Block in 16 32-bit little-endian Worte M[i], 0 ≤ i ≤ 15

    // Initialisiere den Hash-Wert für diesen Block:
    var uint A := a0
    var uint B := b0
    var uint C := c0
    var uint D := d0

    // Hauptschleife:
    // not Operator entspricht dem Einerkomplement
    für alle i von 0 bis 63
    (
        wenn 0 ≤ i ≤ 15 dann
            F := (B and C) or ((not B) and D)
            g := i
        sonst wenn 16 ≤ i ≤ 31 dann
            F := (B and D) or (C and (not D))
            g := (5×i + 1) mod 16
        sonst wenn 32 ≤ i ≤ 47 dann
            F := B xor C xor D
            g := (3×i + 5) mod 16
        sonst wenn 48 ≤ i ≤ 63 dann
            F := C xor (B or (not D))
            g := (7×i) mod 16
        wenn_ende

        temp := D
        D := C
        C := B
        B := B + linksrotation((A + F + K[i] + M[g]), s[i])
        A := temp
    )

    // Addiere den Hash-Wert des Blocks zur Summe der vorherigen Hashes:
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
)

var uint digest := a0 anfügen b0 anfügen c0 anfügen d0 // Darstellung als little-endian

Anstatt der Originalformulierung aus dem RFC 1321 kann zur Effizienzsteigerung Folgendes verwendet werden:

( 0 ≤ i ≤ 15): F := D xor (B and (C xor D))
(16 ≤ i ≤ 31): F := C xor (D and (B xor C))

Angriffe

Bereits 1993 veröffentlichten Bert de Boer und Antoon Bosselaers einen Algorithmus zum Erzeugen von Pseudokollisionen auf die Kompressionsfunktion von MD5: zwei unterschiedliche Initialisierungskonstanten ergeben für dieselbe Nachricht denselben Hashwert.

1996 fand Hans Dobbertin eine Kollision für zwei unterschiedliche Nachrichten. Es handelt sich dabei um eine echte Kollision, also zwei speziell präparierte Nachrichten, die sich unterscheiden, aber dennoch denselben Hashwert ergeben. Allerdings verwendete Dobbertin eine modifizierte MD5-Variante, in der andere Initialisierungskonstanten (für A, B, C, D) verwendet werden. Auch war es nicht möglich, den Inhalt der kollidierenden Nachrichten vorzugeben. Somit waren praktische Angriffe auf MD5 zwar nicht möglich, aber die Schwächen von MD5 wurden deutlich, so dass Kryptologen zu einem Umstieg auf andere Hashfunktionen rieten.

2004 gelang es einer chinesischen Forschergruppe um Xiaoyun Wang, Kollisionen systematisch zu erzeugen, wenn der Anfang der Nachricht beliebig gewählt werden kann, aber bei beiden Nachrichten identisch ist (common-prefix collision). Zu diesem Anfang der Nachricht können mit vertretbarem Aufwand zwei verschiedene Fortsetzungen der Nachricht errechnet werden, die zum selben Hashwert führen. Diese Kollision bleibt auch erhalten, wenn an beide Nachrichten (jeweils bestehend aus dem gleichen Anfang und der einen bzw. der anderen Fortsetzung) das gleiche Suffix angehängt wird. Dieser Angriff wurde von Wang und anderen Forschergruppen verbessert, sodass ein PC heute innerhalb von Sekunden eine MD5-Kollision berechnen kann.

Der Aufwand zum Finden einer Kollision ist größer, wenn der Anfang der beiden Nachrichten abweicht (chosen-prefix collision). 2008 gelang es einem Team um Marc Stevens und Alexander Sotirov einen solchen Kollisionsangriff durchzuführen, um ein gefälschtes und als vertrauenswürdig anerkanntes CA-Zertifikat zu erstellen. Mit diesem waren sie prinzipiell in der Lage, für jede beliebige URL ein SSL-Zertifikat zu fälschen und damit die Sicherheitsmechanismen von HTTPS im Web auszuhebeln. Die Arbeit wurde erstmals im Dezember 2008 auf dem 25. Chaos Communication Congress vorgestellt und einige Monate später in einem wissenschaftlichen Artikel veröffentlicht. Zur Kollisionsberechnung benutzten sie einen Cluster von 200 Sony PlayStation 3.

Die 2012 entdeckte Windows-Malware Flame verwendet ein gefälschtes Code-Signing-Zertifikat, das auf einer neuen und bislang unbekannten Variante einer Chosen-Prefix-Kollision für MD5 basiert.

Preimage-Angriffe können auch mit den genannten Methoden noch nicht in sinnvoller Zeit durchgeführt werden. Dadurch ist es weiterhin unmöglich, nachträglich ein gefälschtes Dokument zu erstellen, das zu einem bestimmten, mit MD5 erzeugten Zertifikat passt. Es ist jedoch durch Kollisionsangriffe in vielen Fällen möglich, zwei Dokumente zu erstellen, die denselben MD5-Hashwert ergeben, dann das erste, legitime Dokument signieren zu lassen, und anschließend dieses durch das zweite, gefälschte Dokument auszutauschen. Vor diesem Hintergrund ist von einer Weiterverwendung von MD5 abzuraten.

Sicherheit

MD5 ist weit verbreitet und wurde ursprünglich als kryptografisch sicher angesehen. Bereits 1994 entdeckten Bert den Boer und Antoon Bosselaers Pseudokollisionen in MD5. Grundlegende Arbeit, um echte Kollisionen zu finden, leistete auch Hans Dobbertin (damals am BSI), der bereits den erfolgreichen Angriff auf MD4 entwickelt hatte und die dabei verwendeten Techniken auf MD5 übertrug.

Kollisionsresistenz

Im August 2004 fand ein chinesisches Wissenschaftlerteam die erste Kollision in der vollständigen MD5-Funktion. 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. Kurz nach der Veröffentlichung der Arbeit der Chinesen wurde MD5CRK eingestellt, das versuchte, Kollisionen per Brute-Force-Methode zu finden.

Kurzbeschreibung: Ein Eingabeblock (512 Bit) wird modifiziert, wobei versucht wird, eine bestimmte Differenz zum Original im Ausgang zu erzeugen. Durch eine aufwändige Analyse des Algorithmus kann die Anzahl der unbekannten Bits so weit verringert werden, dass dies rechnerisch gelingt. Im nächsten 512-Bit-Block wird mit den gleichen Methoden versucht, die Differenz wieder aufzuheben. Die Fälschung benötigt also einen zusammenhängenden Datenblock von 1024 Bit = 128 Byte, was den Einsatz stark einschränkt.

Inzwischen sind die Kollisionsangriffe so weit fortgeschritten, dass eine weitere Nutzung von MD5, insbesondere in solchen Szenarien, in denen der Nutzer nicht die zu signierenden Dateien komplett kontrolliert, abzulehnen ist. Ein 2009 durchgeführter Test des Computermagazins c’t unter Verwendung von GPGPU ermöglicht es einem etwa ein Jahr alten Highend-Spiele-PC mit zwei Nvidia GeForce 9800 GX2 (insgesamt vier Grafikprozessoren), in knapp 35 Minuten eine Kollision zu finden.

Einwegeigenschaft

Eine andere Angriffsmethode stellen Regenbogentabellen dar. In diesen Tabellen sind Zeichenketten mit den zugehörigen MD5-Hashwerten gespeichert. Der Angreifer durchsucht diese Tabellen nach dem vorgegebenen Hashwert und kann dann passende Zeichenketten auslesen. Dieser Angriff kann vor allem eingesetzt werden, um Passwörter zu ermitteln, die als MD5-Hashes gespeichert sind. Die dazu notwendigen Regenbogentabellen sind jedoch sehr groß und es bedarf eines hohen Rechenaufwands, um sie zu erstellen. Deshalb ist dieser Angriff im Allgemeinen nur bei kurzen Passwörtern möglich. Für diesen Fall existieren vorberechnete Regenbogentabellen, bei denen zumindest der Rechenaufwand zum Erstellen der Liste entfällt. Die Verwendung eines Salt, also eines zufälligen nicht vorhersehbaren Wertes, welcher an den Klartext angefügt wird, macht die Effektivität von vorberechneten Regenbogentabellen jedoch zunichte.

Zusammenfassung

Kollisionen zu finden bedeutet, zwei unterschiedliche Texte M und M' mit hash(M) = hash(M') zu finden. Bei einem Preimage-Angriff sucht man zu vorgegebenen M bzw. hash(M) ein M', so dass hash(M) = hash(M'). Da man beim Preimage-Angriff nur M' kontrolliert, nicht auch M, ist dieser viel schwieriger.

Derzeit ist MD5 nur bezüglich der Kollisionsangriffe gebrochen.

Zum sicheren Speichern von Passwörtern sollten aber andere Algorithmen in Betracht gezogen werden, die speziell für diesen Zweck entwickelt wurden, z. B. bcrypt oder PBKDF2.

Da noch kein erster Preimage-Angriff bekannt ist, sind in der Vergangenheit signierte MD5-Hashes aktuell (2013) noch sicher.

Siehe auch

• Kryptologische Hashfunktion

Literatur

• Hans Dobbertin: Cryptanalysis of MD5 compress. Announcement on Internet, Mai 1996 (englisch, online)
• Hans Dobbertin: The Status of MD5 After a Recent Attack. In: CryptoBytes 2(2), 1996 (englisch)
• Philip Hawkes, Michael Paddon, Gregory G. Rose: Musings on the Wang et al. MD5 Collision. Detaillierte Analyse der differentiellen Attacke auf den MD5 (englisch)
• Vlastimil Klima: Finding MD5 Collisions on a Notebook PC using multi-message modifications. Nochmals verbesserte Angriffstechnik (englisch)

Weblinks

• RFC 1321 – The MD5 Message-Digest Algorithm; R. Rivest, April 1992 (englisch)
• MD5 Collision Demo Zwei unterschiedliche Programme mit gleichem MD5-Hash und einer Bibliothek zur Generierung weiterer solcher Programme (englisch)
• papers und Demos zu MD5-Kollisionen (englisch)
• Jürgen Schmidt: Hash mich, die zweite
• Online-Generator zum Erzeugen von MD5-Hashes
• Sourceforge.net: RFC1321-based (RSA-free) MD5 library