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.

Algorithmus

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 ${\displaystyle F}$, modularer Addition und Linksrotation. Es gibt vier mögliche Varianten der Funktion ${\displaystyle F}$, in jeder Runde wird davon eine andere verwendet (hier genannt ${\displaystyle F}$, ${\displaystyle G}$, ${\displaystyle H}$ und ${\displaystyle I}$):

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

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

${\displaystyle H(X,Y,Z)=X\oplus Y\oplus Z}$

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

${\displaystyle \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 ${\displaystyle M}$ und ${\displaystyle M'}$ erzeugen, die denselben Hashwert ${\displaystyle \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.

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

Einzelnachweise

1. ↑ Beschreibung des Powershell Cmdlet Get-Filehash.
2. 1 2 R. Rivest: RFC 1321 – The MD5 Message-Digest Algorithm. April 1992 (englisch).
3. ↑ Sean Turner, Lily Chen: RFC 6151 – Updated Security Considerations for the MD5 Message-Digest and the HMAC-MD5 Algorithms. März 2011 (englisch).
4. ↑ Kryptographische Verfahren: Empfehlungen und Schlüssellängen. (PDF) BSI TR-02102-1. Bundesamt für Sicherheit in der Informationstechnik, 9. Januar 2023, abgerufen am 4. Februar 2023. 
5. ↑ Yu Sasaki, Kazumaro Aoki: Finding Preimages in Full MD5 Faster Than Exhaustive Search. In: Antoine Joux (Hrsg.): Advances in Cryptology – EUROCRYPT 2009. doi:10.1007/978-3-642-01001-9_8. 
6. ↑ Bert de Boer, Antoon Bosselaers: Collisions for the compression function of MD5. In: Tor Helleseth (Hrsg.): Proceedings of EUROCRYPT ’93. Springer-Verlag, New York 1994, ISBN 3-540-57600-2, doi:10.1007/3-540-48285-7_26. 
7. ↑ Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD. (PDF; 57 kB) Abgerufen am 4. Februar 2023. 
8. ↑ Erläuterung zum Kollisionsproblem bei Manipulation von md5-Hashwerten
9. ↑ Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger: MD5 considered harmful today. 30. Dezember 2008, abgerufen am 30. Dezember 2008. 
10. ↑ Marc Stevens: Technical Background Of The Flame Collision Attack. CWI, 7. Juni 2012, abgerufen am 8. Juni 2012 (englisch).  “the results have shown that not our published chosen-prefix collision attack was used, but an entirely new and unknown variant”