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.Beschreibung des 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 mini|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. Mi bezeichnet einen 32-Bit-Block des Eingabestroms und Ki eine für jede Operation unterschiedliche 32-Bit-Konstante; left shifts bezeichnet die bitweise Linksrotation um s Stellen, wobei s für jede Operation variiert. Addition bezeichnet die Addition modulo 232.
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 , modularer Addition und Linksrotation. Es gibt vier mögliche Varianten der Funktion , in jeder Runde wird davon eine andere verwendet (hier genannt , , und ):
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 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 und erzeugen, die denselben Hashwert 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