Message-Digest Algorithm 5

Message-Digest Algorithm 5 (MD5) ist eine verbreitete kryptographische Hashfunktion, die aus einer beliebigen Nachricht einen 128-Bit-Hashwert berechnet. Sie wurde 1991 von Ronald L. Rivest am Massachusetts Institute of Technology als Nachfolger von MD4 entwickelt. Der englische Begriff „Message Digest“ steht für einen kurzen Zahlenwert fester Länge, der deterministisch aus der gegebenen Nachricht berechnet wird.

Inzwischen ist bekannt, dass MD5 keine Kollisionsresistenz bietet und somit unsicher ist. Auch die Preimage-Resistenz ist theoretisch gebrochen, allerdings ist ein Preimage-Angriff gegen MD5 nicht praktikabel.

MD5-Hashwert

Die 128 Bit langen MD5-Hashwerte werden üblicherweise als 32-stellige Hexadezimalzahl notiert. Beispiel für eine 59 Byte lange ASCII-Eingabe mit zugehörigem MD5-Hashwert:

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

Es ist praktisch unmöglich, eine weitere Nachricht, die genau diesen Hashwert ergibt, zu bestimmen. Eine beliebige Änderung des Textes (im Folgenden wird nur ein Buchstabe verändert) erzeugt aufgrund des Lawineneffekts einen komplett anderen Hashwert:

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. In Python ist MD5 in der Programmbibliothek (hashlib) enthalten.

Auf vielen anderen Unix-Derivaten ist Python installiert oder man kann sich mit dem meist installierten Programm OpenSSL behelfen. Python kann auch online aufgerufen werden. Microsoft-Windows-Betriebssysteme ab den Versionen Windows 8.1 bzw. Windows Server 2012 R2 verfügen standardmäßig über das PowerShell Cmdlet Get-Filehash.

Prüfsumme einer Datei

Nach erfolgreichem Download einer oder mehrerer Dateien kann der Anbieter der Daten in einer weiteren Datei den dazugehörigen MD5-Hashwert zur Verfügung stellen. Über ein Prüfprogramm kann 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 Übertragungsfehler auf, was dem Anwendungszweck einer Prüfsumme entspricht. Dies bietet keine Sicherheit hinsichtlich einer gezielten Datenmanipulation durch einen Angreifer (Man-in-the-Middle-Angriff), da der Angreifer neben den übertragenen Daten auch den angebotenen MD5-Hashwert manipulieren kann. Bei Verwendung eines Spiegelservers für den Download stellt beispielsweise der Betreiber des Spiegelservers einen möglichen Angreifer dar. Um eine Manipulation durch diesen auszuschließen, muss entweder der MD5-Hashwert aus einer vertrauenswürdigen Quelle über einen sicheren Kanal bezogen werden, oder die Authentizität der Datei muss durch ein anderes Verfahren sichergestellt werden. Dazu eignet sich eine digitale Signatur oder ein Message Authentication Code, der eine Hashfunktion mit einem schlüsselbasierten, kryptographischen Mechanismus kombiniert.

Zufallsgenerator

Wie jede kryptographische Hashfunktion kann MD5 als deterministischer Generator von Pseudo-Zufallszahlen genutzt werden. Dadurch lässt sich zum Beispiel eine Stromverschlüsselung realisieren.

Datenbanken

MD5 kann als Hashfunktion für Datenbankindizes verwendet werden. In gängigen SQL-Datenbankmanagementsysteme wie MySQL oder PostgreSQL ist MD5 als Funktion eingebaut. In dem folgenden Beispiel wird zu jeder gespeicherten URL zusätzlich deren MD5-Hashwert gespeichert. Über den Hashwert lässt sich eine Abfrage realisieren, die effizienter als eine textbasierte Suche ist.

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

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 von 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 in Bits kodiert, angehängt. Die Nachrichtenlänge ist jetzt durch 512 teilbar.

Der Hauptbestandteil von MD5 ist eine Einweg-Kompressionsfunktion, die nacheinander die 512-Bit-Eingabeblöcke verarbeitet. Die Kompressionsfunktion arbeitet mit einem 128-Bit-Puffer, der in vier 32-Bit-Wörter A, B, C und D unterteilt ist. Diese werden beim ersten Nachrichtenblock mit festgelegten Konstanten initialisiert. Die Behandlung eines Nachrichtenblocks geschieht in vier einander ähnlichen Stufen, die „Runden“ genannt werden. Jede Runde besteht aus 16 Operationen, basierend auf einer nichtlinearen Funktion $F$, modularer Addition und Linksrotation. Es gibt vier mögliche Varianten der Funktion $F$, in jeder Runde wird davon eine andere verwendet (hier genannt $F$, $G$, $H$ und $I$):

$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 bitweise XOR, AND, OR und NOT-Operationen.

Das Ergebnis aus dem 128-Bit-Puffer wird zur Verarbeitung des nächsten Nachrichtenblocks weiterverwendet. Die Kompressionsfunktion wird nacheinander angewandt bis alle 512-Bit-Nachrichtenblöcke verarbeitet wurden. Die Ausgabe des Algorithmus ist ein 128 Bit langer MD5-Hashwert.

Referenzimplementierung

RFC 1321 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 an diesen Zeilen in der Datei global.h:

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

Der Typ unsigned long int ist nicht notwendigerweise 4 Byte lang. Der Fehler kann behoben werden, indem man diese Zeilen ersetzt durch:

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

Eine andere, lauffähige Implementierung von L Peter Deutsch findet man auf Sourceforge.net. Diese Implementation ist aus der Spezifikation des RFC 1321 abgeleitet und nicht aus der vorher erwähnten Referenzimplementierung in RFC 1321. 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: (laut 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))

Sicherheit

MD5 wurde mit dem Ziel entwickelt, eine höhere Sicherheit als sein Vorgänger MD4 zu bieten, da Kryptoanalysen dieser Zeit ergaben, dass MD4 wahrscheinlich nicht kollisionsresistent ist. MD5 erlangte weite Verbreitung und wurde ursprünglich als kryptographisch sicher angesehen. Heute ist bekannt, dass MD5 keine Kollisionsresistenz bietet. Mit geringem Aufwand lassen sich zwei unterschiedliche Nachrichten $M$ und $M'$ erzeugen, die denselben Hashwert $\operatorname {MD5} (M)=\operatorname {MD5} (M')$ erzeugen. Nicht alle kryptographischen Anwendungen erfordern Kollisionsresistenz. Beispielsweise setzt die Schnorr-Signatur, anders als die Signatur auf Basis von RSA oder Digital Signature Algorithm, keine kollisionsresistente Hashfunktion voraus.

In Internetstandards und technischen Richtlinien, beispielsweise von der IETF oder dem BSI, wird heute von der Verwendung von MD5 abgeraten.

Preimage-Angriffe

Seit 2009 ist ein theoretischer Preimage-Angriff auf MD5 bekannt, der jedoch mit $2^{123,4}$ MD5-Hashoperationen einen Rechenaufwand jenseits der Praktikabilität erfordert. Bei einem Preimage-Angriff sucht man zu einem vorgegebenen Hashwert $\operatorname {MD5} (M)$ die Nachricht $M$ oder eine andere Nachricht $M'$, so dass man $\operatorname {MD5} (M)=\operatorname {MD5} (M')$ erhält. Da man beim Preimage-Angriff $M$ nicht frei wählen kann, ist dieser Angriff viel schwieriger.

Ein Preimage-Angriff wäre beispielsweise erforderlich, um nachträglich ein gefälschtes Dokument zu erstellen, das zu einer bestehenden, mit RSA und MD5 erzeugten Signatur passt. Es ist jedoch durch einen Kollisionsangriff 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.

Kollisionsangriffe

Bereits 1994 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 beliebig vorzugeben. Somit waren praktische Angriffe auf MD5 zwar nicht möglich, aber die ersten Schwächen des Algorithmus wurden deutlich.

Im August 2004 gelang es einer chinesischen Forschergruppe um Xiaoyun Wang Kollisionen in MD5 systematisch zu erzeugen. Der Anfang der Nachrichten kann beliebig gewählt werden, ist aber bei beiden Nachrichten identisch (Common-Prefix-Kollision): $M_{0},M_{1},...,M_{i-1}$. Dahinter folgen zwei präparierte Paare von Nachrichtenblöcken $M_{i},M_{i+1}$ und $M'_{i},M'_{i+1}$, die sich unterscheiden, aber dennoch denselben Hashwert ergeben. Aufgrund der Merkle-Damgård-Konstruktion kann optional an beide Nachrichten ein identischer Suffix angehängt werden, wobei beide Nachrichten weiterhin einen identischen Hashwert ergeben: $M_{i+2},...,M_{i+n}$. Der Rechenaufwand zur Erzeugung des ersten Angriffsblocks dauerte auf einem IBM p690 Hochleistungsrechner etwa eine Stunde, die des zweiten Angriffsblocks bis zu fünf Minuten. Der Angriff setzt voraus, dass zwei 512-Bit-Nachrichtenblöcke (insgesamt 128 Bytes) in die Nachricht eingefügt werden, die abhängig vom Nachrichtenpräfix präpariert werden. Da die Angriffsblöcke nicht frei gewählt werden können, schränkt dies je nach Anwendungsszenario die Praktikabilität des Angriffs ein.

Kurz nach der Veröffentlichung von Wang wurde das Volunteer-Computing-Projekt MD5CRK eingestellt, das versuchte, eine Kollision per Brute-Force-Methode zu finden. Die Angriffsmethode 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-Kollision). 2008 gelang es einer Gruppe um Marc Stevens und Alexander Sotirov einen solchen Kollisionsangriff durchzuführen, um ein gefälschtes CA-Zertifikat zu erzeugen, das von gängigen Webbrowsern als vertrauenswürdige Zertifizierungsstelle anerkannt wurde. 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 auszuhebeln. Die Arbeit wurde erstmals 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 verwendete ein gefälschtes Code-Signing-Zertifikat, das auf einer neuen und bis dahin unbekannten Variante einer Chosen-Prefix-Kollision für MD5 basierte.

Password-Hashing

Ein Einsatzzweck von MD5 und anderen kryptographischen Hashfunktionen ist die Schlüsselableitung aus einem geheimen Passwort. Wenn die Hashwerte dem Angreifer bekannt sind, können sie per Brute-Force-Methode oder Wörterbuchangriff zum Klartext zurückgerechnet werden. Der Angriff besteht darin, zu möglichst vielen Passwortkandidaten den dazugehörigen Hashwert zu berechnen und ihn auf Gleichheit mit dem gesuchten Passwort-Hashwert zu vergleichen. Dabei handelt es sich um einen naiven Preimage-Angriff, dessen Erfolg davon abhängt, ob das Passwort erraten werden kann und wie viele Hashwerte der Angreifer in einer gegebenen Zeit berechnen kann.

Die Brute-Force-Methode ist bei MD5 durch den Einsatz von GPGPU besonders effizient, da sich der MD5-Algorithmus auf Grafikprozessoren gut parallelisieren und effizient berechnen lässt. Aus diesem Grund eignen sich spezialisierte Hashfunktionen wie zum Beispiel bcrypt oder PBKDF2 besser zum sicheren Speichern von Passwort-Hashwerten.

Eine Maßnahme zur Erhöhung der Effizienz eines Brute-Force-Angriffs ist es, mehrere Passwort-Hashwerte gleichzeitig anzugreifen. Hierbei muss die Hashwert-Berechnung nur einmal erfolgen, kann aber gegen eine Liste von Hashwerten erfolgen. Diese Effizienzsteigerung kann durch die Verwendung eines Salt abgewehrt werden. Ein Salt ist eine zufällige Zeichenkette, die bei der Hashwert-Berechnung an das Passwort angefügt wird und die mit dem Passwort-Hashwert unverschlüsselt gespeichert wird. Idealerweise verwendet jedes Passwort ein einmaliges Salt, da der Angreifer dann keinen Mehrfachvergleich gegen eine Liste von Passwort-Hashes durchführen kann, sondern für jede Vergleichsoperation die Hashfunktion mit dem jeweils einmaligen Salt neu berechnen muss.

Eine andere Angriffsmethode stellen Regenbogentabellen dar. In diesen Tabellen sind Zeichenketten mit den zugehörigen Hashwerten gespeichert. Es handelt sich dabei um einen Kompromiss des Angreifers zwischen dem Rechenaufwand und Speicherbedarf (Time-Memory Tradeoff). Gegenüber einem Brute-Force-Angriff spart die Verwendung von Regenbogentabellen teilweise Rechenaufwand, benötigt jedoch viel Speicherplatz zum Durchsuchen der vorberechneten und gespeicherten Tabellen. Für die Erstellung der Regenbogentabellen ist ein hoher Rechenaufwand erforderlich, jedoch nur einmalig, wenn die Tabellen für mehrere Angriffe wiederverwendet werden. Auch hier kann durch die Verwendung eines Salt die Angriffsmethode abgewehrt werden. Der Angreifer müsste für jeden zufälligen Salt eine eigene Regenbogentabelle vorberechnen, wodurch die Wiederverwendbarkeit und damit das Einsparpotential der Regenbogentabelle nicht mehr gegeben ist.

Literatur

• Hans Dobbertin: Cryptanalysis of MD5 compress. Announcement on Internet, Mai 1996 (englisch) citeseer.ist.psu.edu
• Hans Dobbertin: The Status of MD5 After a Recent Attack. In: CryptoBytes, 1996, 2(2) (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

• R. Rivest: RFC 1321 – The MD5 Message-Digest Algorithm. April 1992 (englisch).
• MD5 Collision Demo. mathstat.dal.ca/~selinger – Zwei unterschiedliche Programme mit gleichem MD5-Hash und einer Bibliothek zur Generierung weiterer solcher Programme (englisch)
• papers und Demos zu MD5-Kollisionen. cryptography.hyperlink.cz (englisch)
• Jürgen Schmidt: Hash mich, die zweite.
• Online-Generator zum Erzeugen von MD5-Hashe. de.toolpage.org