3. Message Digest

MD4 ist eine von Ron Rivest entworfene Einweg-Hashfunktion, die einen 128 bit langen Hashwert produziert. MD steht für Message Digest (etwa: Zusammenfassung einer Nachricht).

3.1 Entwurfsziele

• Der Berechnungsaufwand, zwei Nachrichten mit gleichem Hashwert zu finden, geht gegen unendlich. Es gibt keinen effizienteren Angriff als Brute-Force. Die Sicherheit von MD4 beruht auf keinerlei Annahmen, etwa der Schwierigkeit der Faktorisierung.
• MD4 eignet sich für schnelle Software-Implementierungen. Der Algorithmus benutzt nur einfache Bitmanipulationen mit 32-bit-Operanden, d. h. er ist so einfach wie möglich und benutzt keine großen Datenstrukturen oder ein kompliziertes Programm.
• MD4 ist für Mikroprozessorarchitekturen (speziell Intel-Mikroprozessoren) optimiert. Größere und schnellere Computer führen die nötigen Umsetzungen durch.

Diese Entwurfsziele und das Prinzip des Message Digest, das in MD4 verwendet wird, sind Basis einiger anderer Einweg-Hashfunktionen: MD2, MD3, MD5, RIPEMD, HAVAL, SHA. Deren Modifikation im Vergleich zu MD4 sind auch eine Folge der ständig wachsenden Rechenleistung, obwohl sämtliche kryptanalytischen Angriffe nicht auf den ganzen Algorithmus erweitert werden konnten.

3.2 MD2

MD2 ist eine von Ron Rivest entwickelte Einweg-Hashfunktion mit 128 bit langem Hashwert, die zusammen mit MD5 in den Privacy-Enhanced-Mail-(PEM)-Protokollen verwendet wird. Der Klartext wird auf ein Vielfaches von 16 Byte erweitert und anschließend wird eine 16 Byte lange Prüfsumme angehängt. 16 Byte mit Nullen, 16 Byte der Nachricht und deren XOR-Verknüpfung bilden den ersten Block, der noch komprimiert wird. Weitere 16-Byteweise Verknüpfungen und Kompressionen mit der Nachricht bilden die Ausgabe. Die Sicherheit von MD2 hängt von einer zufälligen Bytepermutation ab. Bisher wurden noch keine Schwächen entdeckt, allerdings ist MD2 langsamer als die meisten anderen Algorithmen.

3.3 MD3

MD3 wird hier nur zwecks Vollständigkeit genannt. Wegen mehrerer Mängel brachte Ron Rivest diese Funktion nie über die Experimentierphase hinaus.

3.4 MD5

MD5, ebenfalls von Ron Rivest entwickelt, ist die am weitesten verbreitete Einweg-Hashfunktion. Diese ist zwar komplexer als MD4, arbeitet aber nach einem ähnlichen Prinzip und erzeugt ebenfalls einen Hashwert der Länge 128 bit. MD5 wird auch in Pretty Good Privacy (PGP) angewandt, einem Programm zur E-Mail-Kommunikation.

Beschreibung des Algorithmus

Nach einigen Vorbereitungsschritten verarbeitet MD5 den Eingabetext in Blöcken von 512 bit, aufgeteilt in Teilblöcke der Länge 32 bit. Durch Anhängen einer 64-bit-Darstellung der Länge der Nachricht, eines einzelnen Bits mit dem Wert Eins und sonst Nullen wird die Nachricht auf ein Vielfaches von 512 Bit aufgefüllt. Dadurch wird sichergestellt, daß verschiedene Nachrichten nach dem Auffüllen nicht identisch sind.

Die Hauptschleife des Algorithmus besteht aus vier Runden, die vier 32-bit-Verkettungsvariablen (A, B, C, D) mit nichtlinearen Funktionen und bitweise Rotation verändert, und eine der Variablen durch das Ergebnis ersetzt.

Hauptschleife von MD5

Eine Runde von MD5 (M_j ... j-ten Teilblock, t_i ... Konstanten)

Nach jeder Runde werden initialisierte Variablen (a, b, c, d) zu den Verkettungsvariablen (A, B, C, D) addiert, die am Ende die Ausgabe des Algorithmus bilden. Der 128 bit lange Hashwert ist eine Konkatenierung der vier 32 bit langen Verkettungsvariablen.

Sicherheit des Algorithmus

Bei jeder Operation wird eine unterschiedliche nichtlineare Funktion verwendet, deren einzelne Ergebnisbits unabhängig und gleichmäßig verteilt sind. Im Vergleich zu MD4 wurde der Hauptschleife eine vierte Runde hinzugefügt und jeder Schritt enthält eine eindeutige Konstante. Da jeder Schritt vom Ergebnis des vorherigen abhängt, entsteht ein schnellerer Lawineneffekt.

Kryptanalyse des Algorithmus

Eine differentielle Kryptanalyse ist unwirksam, allerdings können Kollisionen durch Angriffe auf den Kompressionsalgorithmus von MD5 produziert werden. Damit ist zwar eine wichtige Eigenschaft nicht mehr gegeben, aber MD5 ist trotzdem der weitverbreiteste Hash-Algorithmus.