Quelltext der Seite 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 [[Message-Digest Algorithm 4|MD4]] entwickelt. Der englische Begriff „Message Digest“ steht für einen kurzen Zahlenwert fester Länge, der [[Determinismus (Algorithmus)|deterministisch]] aus der gegebenen Nachricht berechnet wird.

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

== MD5-Hashwert ==
Die 128&nbsp;Bit langen MD5-Hashwerte werden üblicherweise als 32-stellige [[Hexadezimal]]zahl notiert. Beispiel für eine 59 Byte lange [[American Standard Code for Information Interchange|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 [[Lawineneffekt (Kryptographie)|Lawineneffekts]] einen komplett anderen Hashwert:

 md5("Fran'''k''' 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 [[GNU Core Utilities|coreutils]] standardmäßig installiert.

Auf [[Berkeley Software Distribution|BSD]]-abgeleiteten Betriebssystemen wie [[macOS]] gibt es das Kommando md5. In [[Python (Programmiersprache)|Python]] ist MD5 in der [[Programmbibliothek|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|Microsoft-Windows]]-Betriebssysteme ab den Versionen [[Microsoft Windows 8#Windows 8.1|Windows 8.1]] bzw. [[Microsoft Windows Server 2012#Windows Server 2012 R2|Windows Server 2012 R2]] verfügen standardmäßig über das [[PowerShell]] Cmdlet Get-Filehash.<ref>[https://docs.microsoft.com/en-us/powershell/module/microsoft.powershell.utility/get-filehash?view=powershell-4.0 ''Beschreibung des Powershell Cmdlet Get-Filehash''.]</ref>

=== 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 (Informationssicherheit)|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 [[Spiegelserver]]s 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 [[Kryptographisch sicherer Zufallszahlengenerator|Pseudo-Zufallszahlen]] genutzt werden. Dadurch lässt sich zum Beispiel eine [[Stromverschlüsselung]] realisieren.

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

<syntaxhighlight lang="sql">
CREATE TABLE `urls` (
  `url` VARCHAR(4096) DEFAULT NULL,
  `url_md5` CHAR(32) GENERATED ALWAYS AS (MD5(`url`)) STORED,
  UNIQUE KEY `index_url` (`url_md5`)
);
</syntaxhighlight>

== Algorithmus ==
[[Datei:MD5 algorithm.svg|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. ''M<sub>i</sub>'' bezeichnet einen 32-Bit-Block des Eingabestroms und ''K<sub>i</sub>'' eine für jede Operation unterschiedliche 32-Bit-Konstante; [[Datei:lll.png|left shift]]<sub>''s''</sub> bezeichnet die bitweise Linksrotation um ''s'' Stellen, wobei ''s'' für jede Operation variiert. [[Datei:Boxplus.png|Addition]] bezeichnet die Addition modulo 2<sup>32</sup>.]]

MD5 basiert auf der [[Merkles Meta-Verfahren|Merkle-Damgård-Konstruktion]], um aus einer Nachricht variabler Länge eine Ausgabe fester Länge von 128&nbsp;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 [[Initialisierungsvektor|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 <math>F</math>, modularer Addition und [[Bitweiser Operator#Zyklische Verschiebung ohne Übertragsbit|Linksrotation]]. Es gibt vier mögliche Varianten der Funktion <math>F</math>, in jeder Runde wird davon eine andere verwendet (hier genannt <math>F</math>, <math>G</math>, <math>H</math> und <math>I</math>):

:<math>F(X,Y,Z) = (X\wedge{Y}) \vee (\neg{X} \wedge{Z})</math>
:<math>G(X,Y,Z) = (X\wedge{Z}) \vee (Y \wedge \neg{Z})</math>
:<math>H(X,Y,Z) = X \oplus Y \oplus Z</math>
:<math>I(X,Y,Z) = Y \oplus (X \vee \neg{Z})</math>

<math>\oplus, \wedge, \vee, \neg</math> stehen jeweils für [[Bitweiser Operator|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 ==
<nowiki>RFC&nbsp;1321</nowiki><ref name="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 an diesen Zeilen in der Datei ''global.h'':
<syntaxhighlight lang="c">
/* UINT4 defines a four byte word */
typedef unsigned long int UINT4;
</syntaxhighlight>
Der Typ ''unsigned long int'' ist nicht notwendigerweise 4&nbsp;Byte lang. Der Fehler kann behoben werden, indem man diese Zeilen ersetzt durch:
<syntaxhighlight lang="c">
#include <inttypes.h>
...
/* UINT4 defines a four byte word */
typedef uint32_t UINT4;
</syntaxhighlight>

Eine andere, lauffähige Implementierung von [[L Peter Deutsch]] findet man auf Sourceforge.net. Diese Implementation ist aus der Spezifikation des <nowiki>RFC&nbsp;1321</nowiki><ref name="RFC1321" /> abgeleitet und nicht aus der vorher erwähnten [[Referenzimplementierung]] in <nowiki>RFC&nbsp;1321</nowiki>. Darum sind bei Verwendung dieser Implementierung keinerlei Verweise auf ''RSA Data Security, Inc.'' notwendig.

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

 <span style="color:green;">// ''Beachte: Alle Variablen sind vorzeichenlose (unsigned) 32-Bit-Werte und''
 // ''verhalten sich bei Berechnungen [[Kongruenz (Zahlentheorie)|kongruent (≡)]] modulo 2^32''</span>

 <span style="color:green;"> ''// Definition der linksrotation Funktion, c ist der übergebene Wert von s[i] - siehe Hauptschleife''</span>
 '''linksrotation'''(x, c)
     '''return''' (x << c)binär '''or''' (x >> (32-c));

 <span style="color:green;">// ''s definiert die Anzahl der Bits, die pro Runde rotiert werden:''</span>
 '''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}

 <span style="color:green;">// ''Verwende den binären Vorkommateil vom 2^32-fachen Betrag des Sinus''
 // ''von Integerwerten als Konstanten:''</span>
 '''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 }

 <span style="color:green;">// ''Initialisiere die Variablen: (laut <nowiki>RFC&nbsp;1321</nowiki>)''</span>
 '''var''' ''uint'' a0 := 0x67452301
 '''var''' ''uint'' b0 := 0xEFCDAB89
 '''var''' ''uint'' c0 := 0x98BADCFE
 '''var''' ''uint'' d0 := 0x10325476

 <span style="color:green;">// ''Vorbereitung der Nachricht 'message':''</span>
 '''var''' ''uint'' message_laenge := bit_length(message)
 '''erweitere''' message '''um''' bit "1"
 '''erweitere''' message '''um''' bits "0" '''bis''' Länge von message in bits [[Kongruenz (Zahlentheorie)|≡]] 448 (mod 512)
 '''erweitere''' message '''um''' message_laenge als ''64-Bit [[Little endian|little-endian]] Integer''

 <span style="color:green;">// ''Verarbeite die Nachricht in aufeinander folgenden 512-Bit-Blöcken:''</span>
 '''für alle''' ''512-Bit'' Block '''von''' message
 (
     unterteile Block in 16 32-bit [[Little endian|little-endian]] Worte M[i], 0 ≤ i ≤ 15

     <span style="color:green;">// ''Initialisiere den Hash-Wert für diesen Block:''</span>
     '''var''' ''uint'' A := a0
     '''var''' ''uint'' B := b0
     '''var''' ''uint'' C := c0
     '''var''' ''uint'' D := d0

     <span style="color:green;">// ''Hauptschleife:''</span>
     <span style="color:green;">// '''not''' Operator entspricht dem [[Einerkomplement]]</span>
     '''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
     )

     <span style="color:green;">// ''Addiere den Hash-Wert des Blocks zur Summe der vorherigen Hashes:''</span>
     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 <span style="color:green;">// ''Darstellung als [[Little endian|little-endian]]''</span>

Anstatt der Originalformulierung aus dem <nowiki>RFC&nbsp;1321</nowiki> 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 [[Message-Digest Algorithm 4|MD4]] zu bieten, da [[Kryptoanalyse]]n dieser Zeit ergaben, dass MD4 wahrscheinlich nicht [[Kollisionsresistenz|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 <math>M</math> und <math>M'</math> erzeugen, die denselben Hashwert <math>\operatorname{MD5}(M) = \operatorname{MD5}(M')</math> erzeugen. Nicht alle kryptographischen Anwendungen erfordern Kollisionsresistenz. Beispielsweise setzt die [[Schnorr-Signatur]], anders als die Signatur auf Basis von [[RSA-Kryptosystem|RSA]] oder [[Digital Signature Algorithm]], keine kollisionsresistente Hashfunktion voraus.

In Internetstandards und technischen Richtlinien, beispielsweise von der [[Internet Engineering Task Force|IETF]]<ref name="RFC6151">{{RFC-Internet |RFC=6151 |Titel=Updated Security Considerations for the MD5 Message-Digest and the HMAC-MD5 Algorithms |Datum=2011-03 |Autor=Sean Turner, Lily Chen}}</ref> oder dem [[Bundesamt für Sicherheit in der Informationstechnik|BSI]],<ref>{{Internetquelle |url=https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/TechnischeRichtlinien/TR02102/BSI-TR-02102.pdf?__blob=publicationFile&v=8 |titel=Kryptographische Verfahren: Empfehlungen und Schlüssellängen |titelerg=BSI TR-02102-1 |hrsg=Bundesamt für Sicherheit in der Informationstechnik |datum=2023-01-09 |format=PDF |abruf=2023-02-04}}</ref> wird heute von der Verwendung von MD5 abgeraten.

=== Preimage-Angriffe ===
Seit 2009 ist ein theoretischer [[Preimage-Angriff]] auf MD5 bekannt, der jedoch mit <math>2^{123,4}</math> MD5-Hashoperationen einen Rechenaufwand jenseits der Praktikabilität erfordert.<ref>{{Literatur |Autor=Yu Sasaki, Kazumaro Aoki |Hrsg=Antoine Joux |Titel=Finding Preimages in Full MD5 Faster Than Exhaustive Search |Sammelwerk=Advances in Cryptology – EUROCRYPT 2009 |Datum= |DOI=10.1007/978-3-642-01001-9_8}}</ref> Bei einem Preimage-Angriff sucht man zu einem vorgegebenen Hashwert <math>\operatorname{MD5}(M)</math> die Nachricht <math>M</math> oder eine andere Nachricht <math>M'</math>, so dass man <math>\operatorname{MD5}(M) = \operatorname{MD5}(M')</math> erhält. Da man beim Preimage-Angriff <math>M</math> 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-Kryptosystem|RSA]] und MD5 erzeugten [[Digitale Signatur|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.<ref>{{Literatur |Autor=Bert de Boer, Antoon Bosselaers |Hrsg=Tor Helleseth |Titel=Collisions for the compression function of MD5 |Sammelwerk=Proceedings of EUROCRYPT ’93 |Verlag=Springer-Verlag |Ort=New York |Datum=1994 |ISBN=3-540-57600-2 |DOI=10.1007/3-540-48285-7_26}}</ref>

1996 fand [[Hans Dobbertin (Kryptologe)|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.<ref>{{Internetquelle |autor=Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu |url=http://eprint.iacr.org/2004/199.pdf |titel=Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD |format=PDF; 57&nbsp;kB |abruf=2023-02-04}}</ref> Der Anfang der Nachrichten kann beliebig gewählt werden, ist aber bei beiden Nachrichten identisch (''Common-Prefix-Kollision''): <math>M_0, M_1, ..., M_{i-1}</math>. Dahinter folgen zwei präparierte Paare von Nachrichtenblöcken <math>M_i, M_{i+1}</math> und <math>M'_i, M'_{i+1}</math>, 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: <math>M_{i+2}, ..., M_{i+n}</math>.<ref>[http://www.mscs.dal.ca/~selinger/md5collision/ Erläuterung zum Kollisionsproblem bei Manipulation von md5-Hashwerten]</ref> Der Rechenaufwand zur Erzeugung des ersten Angriffsblocks dauerte auf einem [[IBM Power|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|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 [[Digitales Zertifikat|CA-Zertifikat]] zu erzeugen, das von gängigen Webbrowsern als vertrauenswürdige [[Zertifizierungsstelle (Digitale Zertifikate)|Zertifizierungsstelle]] anerkannt wurde. Mit diesem waren sie prinzipiell in der Lage, für jede beliebige URL ein [[Transport Layer Security|SSL]]-Zertifikat zu fälschen und damit die Sicherheitsmechanismen von [[Hypertext Transfer Protocol Secure|HTTPS]] auszuhebeln. Die Arbeit wurde erstmals auf dem 25. [[Chaos Communication Congress]] vorgestellt<ref name="talk25c3sslHarmful">{{Internetquelle |autor=25c3 Talk: David Molnar, Marc Stevens, Arjen Lenstra, Benne de Weger, Alexander Sotirov, Jacob Appelbaum, Dag Arne Osvik |url=https://media.ccc.de/v/25c3-3023-en-making_the_theoretical_possible |titel=MD5 considered harmful today |datum=2008-12-30 |abruf=2025-07-19}}</ref> und einige Monate später in einem wissenschaftlichen Artikel veröffentlicht.<ref name="sslHarmful">{{Internetquelle |autor=Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger |url=http://www.win.tue.nl/hashclash/rogue-ca/ |titel=MD5 considered harmful today |datum=2008-12-30 |abruf=2008-12-30}}</ref> Zur Kollisionsberechnung benutzten sie einen Cluster von 200 [[PlayStation 3|Sony PlayStation 3]].

Die 2012 entdeckte Windows-Malware [[Flame (Computerwurm)|Flame]] verwendete ein gefälschtes [[Code Signing|Code-Signing-Zertifikat]], das auf einer neuen und bis dahin unbekannten Variante einer Chosen-Prefix-Kollision für MD5 basierte.<ref>{{Internetquelle |autor=Marc Stevens |url=http://www.cwi.nl/news/2012/cwi-cryptanalist-discovers-new-cryptographic-attack-variant-in-flame-spy-malware |titel=Technical Background Of The Flame Collision Attack |hrsg=CWI |datum=2012-06-07 |sprache=en |abruf=2012-06-08}} {{" |Sprache=en |Text=the results have shown that not our published chosen-prefix collision attack was used, but an entirely new and unknown variant}}</ref>

=== 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 [[General Purpose Computation on Graphics Processing Unit|GPGPU]] besonders effizient, da sich der MD5-Algorithmus auf [[Grafikprozessor]]en 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 (Kryptologie)|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 [[Rainbow Table|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) [http://citeseer.ist.psu.edu/dobbertin96cryptanalysis.html 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 ==
* {{RFC-Internet |RFC=1321 |Titel=The MD5 Message-Digest Algorithm |Datum=1992-04 |Autor=R. Rivest}}
* [http://www.mathstat.dal.ca/~selinger/md5collision/ MD5 Collision Demo.] mathstat.dal.ca/~selinger – Zwei unterschiedliche Programme mit gleichem MD5-Hash und einer Bibliothek zur Generierung weiterer solcher Programme (englisch)
* [http://cryptography.hyperlink.cz/MD5_collisions.html papers und Demos zu MD5-Kollisionen.] cryptography.hyperlink.cz (englisch)
* Jürgen Schmidt: [https://www.heise.de/security/artikel/Konsequenzen-der-erfolgreichen-Angriffe-auf-MD5-270106.html ''Hash mich, die zweite''.]
* [http://de.toolpage.org/tool/md5 Online-Generator zum Erzeugen von MD5-Hashe.] de.toolpage.org

== Einzelnachweise ==
<references>
<ref name="RFC1321">
{{RFC-Internet |RFC=1321 |Titel=The MD5 Message-Digest Algorithm |Datum=1992-04 |Autor=R. Rivest}}
</ref>
</references>

[[Kategorie:Kryptographische Hashfunktion]]