Eine Hash-Kollision entsteht, wenn zwei verschiedene Eingaben denselben Hashwert erzeugen. Bei jeder Hashfunktion mit fester Ausgabelänge sind Kollisionen unvermeidbar: Es gibt unendlich viele Eingaben, aber nur endlich viele Digest-Werte (Schubfachprinzip). Entscheidend ist, ob Kollisionen praktisch auffindbar sind.
Das Geburtstagsparadoxon
Eine Kollision findet man deutlich schneller als gedacht: Nach dem Geburtstagsparadoxon genügen etwa 2^(n/2) Versuche, um bei einem n-Bit-Hash zwei Eingaben mit gleichem Digest zu finden. Ein 128-Bit-Hash wie MD5 hat damit eine Geburtstagsschranke von 2^64 — für gut ausgestattete Angreifer machbar. Bei 160 Bit (SHA-1) wären es 2^80, bei SHA-256 bereits 2^128. Die Suche nach einer Preimage (vorgegebener Hashwert, beliebige Eingabe) ist mit 2^n deutlich teurer — deshalb bleibt die Umkehrung von Hashes auf Raten oder Rainbow Tables beschränkt.
Warum Kollisionen gefährlich sind
Digitale Signaturen signieren nicht die Datei, sondern ihren Hash. Kann ein Angreifer zwei Dateien mit gleichem Hash erzeugen, von denen eine harmlos und eine schädlich ist, unterschreibt das Opfer die harmlose — und der Angreifer tauscht sie anschließend aus. Genau das machten Chosen-Prefix-Angriffe auf MD5 möglich: 2008 entstand daraus ein gefälschtes CA-Zertifikat.
Beispiele realer Kollisionen
- MD5: 2004 praktische Kollisionen mit etwa 2^39 Berechnungen (Wang/Yu).
- SHA-1: 2017 „SHAttered“ mit etwa 2^63 Berechnungen.
- CRC32 und andere Prüfsummen sind trivial kollidierbar — sie sind keine kryptographischen Hashes.
Kollisionen in der Praxis
Nicht jede Kollision ist ein Sicherheitsproblem: Hash-Tabellen in Datenstrukturen nutzen schnelle, nicht-kryptographische Hashes. Dort führen viele Kollisionen nur zu langsameren Zugriffen — ein Angreifer kann das für Denial-of-Service ausnutzen, wenn er Eingaben mit kollidierenden Hashes gezielt erzeugt. Für sicherheitsrelevante Zwecke immer kryptographische Hashfunktionen mit ausreichend langem Digest verwenden (SHA-256, SHA-3).
Verwandte Grundlagen: Hashfunktion, MD5, SHA-1, SHA-256.