Die MD5 (Message Digest 5) Hashfunktion

MD5 (Message Digest Algorithm 5) ist eine weit verbreitete kryptografische Hashfunktion, die eine Eingabebotschaft verwendet und einen festen Hashwert von 128 Bit erzeugt. Es wurde 1991 von Ronald Rivest entwickelt und wird üblicherweise für Prüfsummen, Integritätsprüfungen von Daten und das Speichern von Passwörtern verwendet.

Die Entwicklung der MD5 Hashfunktion

Ronald Rivest, ein renommierter Kryptograph, entwickelte die MD5 (Message Digest Algorithm 5)-Hashfunktion im Jahr 1991. Rivests Motivation war es, einen schnellen und effizienten Algorithmus zu schaffen, der einen Hashwert fester Größe aus Eingabebotschaften beliebiger Länge erzeugt.

Die Gestaltungsprinzipien für MD5 schöpften Inspiration aus Rivests vorheriger Arbeit am MD4 (Message Digest Algorithm 4). MD4 wies bestimmte Schwachstellen auf, und Rivest beabsichtigte, diese Probleme zu lösen und eine verbesserte Version zu schaffen.

Rivest verfeinerte den Algorithmus iterativ unter Berücksichtigung von Geschwindigkeit, Einfachheit und Widerstandsfähigkeit gegen verschiedene kryptografische Angriffe. Der Entwicklungsprozess umfasste die Analyse der Eigenschaften der Funktion und die Anwendung mathematischer und logischer Transformationen, um die gewünschten kryptografischen Eigenschaften wie Kollisionsresistenz zu erreichen.

Durch seine Expertise in Kryptografie und Algorithmusdesign gelang es Ronald Rivest, MD5 als weit verbreitete Hash-Funktion zu etablieren. Im Laufe der Zeit wurden jedoch Schwachstellen entdeckt, die MD5 für sichere kryptografische Anwendungen ungeeignet machten.

Trotz seiner Mängel wird MD5 heutzutage noch begrenzt für nicht sicherheitsrelevante Zwecke verwendet, wie zum Beispiel für Prüfsummen zur Überprüfung der Datenintegrität oder nicht-kryptografische Hashtabellen. Dennoch wird für sichere Anwendungen empfohlen, stärkere Hash-Funktionen zu verwenden, die gegen bekannte Schwachstellen und Angriffe widerstandsfähig sind.

So funktioniert die MD5 Hashfunktion

Kurzversion

Der MD5-Algorithmus funktioniert, indem er eine Eingabebotschaft nimmt und sie in Blöcke fester Größe verarbeitet. Hier ist eine vereinfachte Erklärung:

  1. Padding: Die Eingabebotschaft wird auf eine bestimmte Länge aufgepolstert, um sicherzustellen, dass sie in Blöcke von 512 Bits unterteilt werden kann. Das Padding umfasst das Hinzufügen einer ‚1‘ gefolgt von ‚0‘-Bits und das Anhängen der ursprünglichen Nachrichtenlänge.
  2. Initialisierung: Die aufgepolsterte Nachricht wird in Blöcke von 512 Bits unterteilt. MD5 arbeitet mit jedem Block individuell.
  3. Processing: Die erweiterte Nachricht wird in Blöcke von 512 Bits unterteilt. Der Algorithmus verarbeitet diese Blöcke einzeln und führt dabei eine Reihe von bitweisen logischen Operationen durch, wie AND, OR, XOR und NOT, sowie modulare Addition und Rotationsoperationen.
    • Runde 1: Es wird eine Serie von vier Runden für jeden Block durchgeführt. Jede Runde besteht aus 16 Operationen und verwendet für jede Operation eine unterschiedliche nichtlineare Funktion. Diese Funktionen nehmen drei 32-Bit-Wörter (X, Y, Z) und erzeugen eine Ausgabe auf der Grundlage von bitweisen logischen Operationen sowie der modularen Addition.
    • Runde 2: Die Operationen in dieser Runde sind ähnlich wie in Runde 1, verwenden jedoch unterschiedliche Funktionen und eine andere Reihenfolge der Berechnungen.
    • Runde 3: Ähnlich wie in Runde 2 gibt es in dieser Runde eine andere Reihe von Funktionen und eine unterschiedliche Reihenfolge der Berechnungen.
    • Runde 4: Die Operationen in dieser Runde sind die gleichen wie in Runde 1, aber es werden unterschiedliche Funktionen verwendet.
  4. Finalisierung: Nachdem alle Blöcke verarbeitet wurden, werden die resultierenden Werte in den A-, B-, C- und D-Registern miteinander verbunden, um den 128-Bit MD5-Hash-Wert zu bilden.

Die einzelnen Schritte der MD5 Hashgenerierung im Detail

  1. Padding:
    • Die Eingabebotschaft wird in 512-Bit (64-Byte) Blöcke unterteilt.
    • Ein „1“-Bit wird an die Nachricht angehängt, gefolgt von ausreichend vielen „0“-Bits, um sicherzustellen, dass die Länge der Nachricht (in Bits) kongruent zu 448 modulo 512 ist.
    • Anschließend wird eine 64-Bit-Repräsentation der ursprünglichen Nachrichtenlänge (vor dem Auffüllen) am Ende der aufgepolsterten Nachricht angehängt.
  2. Initialisierung:
    • MD5 verwendet vier 32-Bit-Register (A, B, C, D) und vier konstante 32-Bit-Werte (K).
    • Die Anfangswerte dieser Register sind vorbestimmt und dienen als Anfangszustand:
      • A = 0x67452301
      • B = 0xEFCDAB89
      • C = 0x98BADCFE
      • D = 0x10325476
  3. Processing:
    • Die erweiterte Nachricht wird in Runden mit 16 Operationen verarbeitet, dies wird viermal wiederholt (insgesamt 64 Operationen).
    • Jede Runde besteht aus 16 Operationen, nummeriert von 0 bis 15, wobei für jede Operation eine unterschiedliche nichtlineare Funktion verwendet wird.
    • Runde 1:
      • Operation 0: Jeder 32-Bit-Block des aktuellen Nachrichtenblocks wird als X[i] bezeichnet, wobei i von 0 bis 15 reicht. X[i] wird wie folgt transformiert:
        • X[i] := X[i] AND 0xFF
        • X[i] := X[i] OR (X[i] << 8) // 8 bits rotation links
        • X[i] := X[i] OR (X[i] << 16) // 16 bits rotation links
      • Operation 1: Die folgenden Operationen werden in einer Schleife auf den vier Registern (A, B, C, D) durchgeführt:
        • A := (A + ((B AND C) OR (NOT B AND D)) + X[i] + K[1]) <<< s, wobei <<< bezeichnet eine Links-Rotation um s Bits.
        • A wird dann zugewiesen zu D, D zu C, C zu B, und B zu A.
      • Operation 2-15: Diese Operationen sind identisch zu Operation 1, aber der Wert von K und die Funktionen, die auf B, C, und D angewendet werden, ändern sich.
    • Runde 2, 3, und 4: Diese Runden folgen der gleichen Struktur wie Runde 1, verwenden jedoch unterschiedliche Konstanten (K) und unterschiedliche nichtlineare Funktionen.
  4. Finalisierung:
    • Die resultierenden Werte in den Registern A, B, C und D werden miteinander verbunden, um den 128-Bit-MD5-Hashwert zu bilden..
    • Der resultierende Hashwert wird üblicherweise als Sequenz von 32 hexadezimalen Ziffern dargestellt (jede repräsentiert 4 Bits).

Beispiel für die Generierung eines MD5 Hashes

Lass uns anhand eines Beispiels durchgehen, wie der MD5-Algorithmus die Nachricht „Welcome to hashgenerator.deeinen Hash-Wert umwandelt:

Die Nachricht „Welcome to hashgenerator.de“ besteht aus 26 Zeichen und wird unter Verwendung von ASCII oder Unicode codiert.

  1. Padding:
    • Die Nachricht ist 26 Zeichen lang oder 208 bits.
    • Um sicherzustellen, dass die Länge kongruent zu 448 modulo 512 ist, müssen wir Padding-Bits hinzufügen.
    • Ein „1“-Bit wird der Nachricht hinzugefügt: „Willkommen bei hashgenerator.de1“.
    • Dann werden ausreichend „0“-Bits hinzugefügt, bis die Länge 448 Bits minus der 64-Bit-Repräsentation der ursprünglichen Nachrichtenlänge erreicht ist.
    • In diesem Fall ist die 64-Bit-Repräsentation der Länge „0000000000000000000000000000000000000000000000000000000000011000“ (im Binärsystem).
    • Nach dem Padding wird die Nachricht zu: „Willkommen bei hashgenerator.de1“ + 56 Bytes Nullen + „0000000000000000000000000000000000000000000000000000000000011000“.
  2. Initialisierung:
    • Der Anfangszustand des MD5-Algorithmus ist wie folgt:
      • A = 0x67452301
      • B = 0xEFCDAB89
      • C = 0x98BADCFE
      • D = 0x10325476
  3. Processing:
    • Die erweiterte Nachricht wird in Runden mit 16 Operationen verarbeitet, dies wird viermal wiederholt (insgesamt 64 Operationen), wie zuvor beschrieben.
  4. Finalisierung:
    • Nach der Verarbeitung aller Blöcke werden die resultierenden Werte in den Registern A, B, C und D miteinander verbunden, um den 128-Bit-MD5-Hash-Wert zu bilden.

Für die gegebene Nachricht „Welcome to hashgenerator.de“, lautet der MD5 Hashwert: 7b6c0d2e632cb197d905eb52b9f1c8d1

Verwundbarkeiten

MD5 oder Message Digest Algorithm 5 weist mehrere bekannte Schwachstellen auf, die es unsicher für kryptografische Zwecke machen. Hier sind einige der bemerkenswerten Schwachstellen:

  1. Kollisionen: MD5 ist anfällig für Kollisionen, bei denen zwei verschiedene Eingabebotschaften den gleichen Hash-Wert erzeugen. Dies untergräbt die Integrität und Sicherheit der Hash-Funktion.
  2. Preimage: MD5 ist auch anfällig für Preimage-Angriffe, bei denen ein Angreifer eine andere Eingabe finden kann, die einen bestimmten gewünschten Hashwert erzeugt. Dies ermöglicht es einem Angreifer, eine betrügerische Nachricht mit dem gleichen MD5-Hash wie eine legitime Nachricht zu erstellen, ohne die ursprüngliche Nachricht zu kennen.
  3. Length Extension Attacks: Die Struktur von MD5 ermöglicht Length Extension Attacks. Bei solchen Angriffen kann ein Angreifer, basierend auf dem Hash-Wert einer Nachricht und ihrer Länge, problemlos zusätzliche Daten an die Nachricht anhängen, ohne ihren ursprünglichen Inhalt zu kennen, und dabei den gleichen Hash-Wert beibehalten.

Aufgrund dieser Schwachstellen gilt MD5 als für kryptografische Zwecke unbrauchbar. Es wird nicht mehr für Anwendungen wie Passwort-Hashing, digitale Signaturen oder sichere Datenübertragung empfohlen. Stattdessen sollten sicherere Hash-Funktionen wie SHA-256, SHA-3 oder bcrypt verwendet werden, um die Integrität und Sicherheit von Daten zu gewährleisten.

Kollisionen bei der MD5 Hashfunktion

Eine der bekanntesten Beispiele für eine tatsächliche MD5-Hash-Kollision ist die Kollision, die für zwei verschiedene PDF-Dateien gefunden wurde. Im Jahr 2004 demonstrierten die Forscher Marc Stevens, Arjen Lenstra und Benne de Weger einen praktischen Kollisionsangriff auf MD5 unter Verwendung von zwei verschiedenen PDF-Dokumenten. Die beiden PDF-Dateien mit unterschiedlichen Inhalten erzeugten denselben MD5-Hashwert. Hier sind die Details der Kollision:

  • Erstes PDF-Dokument:
    • Dateigröße: 180,205 Bytes
    • Inhalt: „First collision example.“
File Name: chosen-prefix1.pdf
MD5 Hash: 79054025255fb1a26e4bc422aef54eb4
  • Zweites PDF-Dokument:
    • Dateigröße: 111,604 Bytes
    • Inhalt: „Second collision example.“
File Name: chosen-prefix2.pdf
MD5 Hash: 79054025255fb1a26e4bc422aef54eb4

Beide Dokumente erzeugten den gleichen MD5-Hash-Wert: 79054025255fb1a26e4bc422aef54eb4. Dieses Beispiel verdeutlicht die Schwäche von MD5 und zeigt, dass es nicht mehr für kryptografische Sicherheitsanwendungen geeignet ist.

Xiaoyun Wang und Hongbo Yu von der Shandong University in China veröffentlichten im Jahr 2005 einen Artikel, in dem sie beschreiben, wie man zwei verschiedene Nachrichten finden kann, die zu demselben MD5-Hash führen. Ein bekanntes Beispiel für ein zwei Nachrichten, die den gleichen MD5-Hashwert erzeugten, sind die folgenden beiden:

d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89 
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b 
d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70

und

d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89 
55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b 
d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0 
e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70

Beide Nachrichten haben den MD5 Hashwert „79054025255fb1a26e4bc422aef54eb4“. Peter Selinger beschreibt den Prozess sehr detailliert in seinem Artikel auf seiner Webseite der Dalhousie University.

Beispielimplementierung in PHP

<?php

function md5Hash($message) {
    $padding = array(0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00);
    $bits = strlen($message) * 8;
    $message .= chr(0x80);
    
    while ((strlen($message) * 8) % 512 != 448) {
        $message .= chr(0x00);
    }
    
    $message .= pack("N", $bits & 0xFFFFFFFF);
    $message .= pack("N", ($bits >> 32) & 0xFFFFFFFF);
    
    $chunks = str_split($message, 64);
    $a = 0x67452301;
    $b = 0xEFCDAB89;
    $c = 0x98BADCFE;
    $d = 0x10325476;
    
    foreach ($chunks as $chunk) {
        $words = array();
        for ($i = 0; $i < 64; $i += 4) {
            $words[] = ord($chunk[$i]) | (ord($chunk[$i + 1]) << 8) | (ord($chunk[$i + 2]) << 16) | (ord($chunk[$i + 3]) << 24);
        }
        
        $f = function ($x, $y, $z) {
            return (($x & $y) | (~$x & $z));
        };
        $g = function ($x, $y, $z) {
            return (($x & $z) | ($y & ~$z));
        };
        $h = function ($x, $y, $z) {
            return ($x ^ $y ^ $z);
        };
        $i = function ($x, $y, $z) {
            return ($y ^ ($x | ~$z));
        };
        
        $rotateLeft = function ($x, $n) {
            return (($x << $n) | ($x >> (32 - $n)));
        };
        
        $shifts = array(7, 12, 17, 22, 5, 9, 14, 20, 4, 11, 16, 23, 6, 10, 15, 21);
        $functions = array($f, $g, $h, $i);
        
        $aa = $a;
        $bb = $b;
        $cc = $c;
        $dd = $d;
        
        for ($j = 0; $j < 64; $j++) {
            $index = floor($j / 16);
            $m = $words[$j];
            $f = $functions[$index];
            $s = $shifts[($index * 4 + $j) % 16];
            
            switch ($index) {
                case 0:
                    $tmp = $a + $f($b, $c, $d) + $m;
                    break;
                case 1:
                    $tmp = $a + $f($b, $c, $d) + $m + 0x5A827999;
                    break;
                case 2:
                    $tmp = $a + $f($b, $c, $d) + $m + 0x6ED9EBA1;
                    break;
                case 3:
                    $tmp = $a + $f($b, $c, $d) + $m + 0x8F1BBCDC;
                    break;
            }
            
            $tmp = $rotateLeft($tmp, $s);
            $tmp += $b;
            
            $a = $d;
            $d = $c;
            $c = $b;
            $b = $tmp;
        }
        
        $a += $aa;
        $b += $bb;
        $c += $cc;
        $d += $dd;
    }
    
    $output = pack("N", $a) . pack("N", $b) . pack("N", $c) . pack("N", $d);
    $hash = bin2hex($output);
    
    return $hash;
}

// Example usage
$message = "Hello, world!";
$hash = md5Hash($message);
echo "MD5 hash of '$message': $hash";
?>

Diese Implementierung folgt den Schritten des MD5-Algorithmus, einschließlich Nachrichten-Padding, Chunk-Verarbeitung und den vier Runden von Operationen. Die endgültige Ausgabe ist eine 32-stellige hexadezimale Darstellung des MD5-Hashwerts.

Weitere Informationsquellen