Geburtstags- und Kollisionsangriffe

In einer Gruppe von 23 Personen liegt die Wahrscheinlichkeit, dass zwei am selben Tag Geburtstag haben, über 50 %. Bei 70 Personen liegt sie über 99,9 %. Mathematisch gilt: In einer Menge der Größe N übersteigt die Kollisionswahrscheinlichkeit nach ungefähr √N Stichproben 50 %. Dies ist die Geburtstagsgrenze.

Für eine n-Bit-Hashfunktion kann eine Kollision (H(m1) = H(m2), m1 ≠ m2) mit ungefähr 2^{n/2} zufälligen Versuchen gefunden werden. Für SHA-256 (256 Bit) erfordert eine Kollision ungefähr 2^{128} Rechenaufwand — praktisch undurchführbar. Für MD5 (128 Bit) sind es ungefähr 2^{64} — gerade noch machbar.

Allgemeines Finden von Kollisionen: 2^{n/2} zufällige Nachrichten erzeugen, die Hashes berechnen, nach dem Hashwert sortieren und Duplikate finden. Speicherbedarf O(2^{n/2}). Der Rho-Algorithmus (Floys Verfahren zur Zykluserkennung) reduziert den Speicherbedarf bei gleichen Zeitkosten auf O(1). Die parallele Kollisionssuche nach van Oorschot und Wiener reduziert den Zeitaufwand durch den Einsatz von Hardware.

Praktische MD5-Kollisionen wurden von Wang et al. (2004) mithilfe differentieller Kryptanalyse gefunden — nicht durch den Geburtstagsangriff. Zwei verschiedene 1024-Bit-Nachrichten konnten innerhalb von Sekunden denselben MD5-Hash erzeugen. Hertzbleed-/Chosen-Prefix-Kollisionen ermöglichen Zertifikatskollisionen. MD5 ist für Kollisionsresistenz vollständig gebrochen.

Leistungsfähiger ist folgende Variante: Für zwei beliebige Präfixe P1 und P2 werden Suffixe S1 und S2 gefunden, sodass H(P1||S1) = H(P2||S2). Stevens et al. (2017) fanden Chosen-Prefix-MD5-Kollisionen. Damit wurde ein bösartiges CA-Zertifikat mit einer gültigen MD5-Signatur erstellt. Dadurch wurde MD5 aus der Zertifikatsverwendung entfernt.

Googles SHAttered (2017) war die erste praktische SHA-1-Kollision. Zwei verschiedene PDF-Dateien hatten denselben SHA-1-Hash. Dafür waren 2^{63.1} SHA-1-Kompressionen erforderlich — entsprechend 6.500 CPU-Jahren und 110 GPU-Jahren. Die Kosten betrugen ungefähr 110.000 US-Dollar. Browser stuften SHA-1-Zertifikate 2017 als veraltet ein.

Für Merkle-Damgård-Hashfunktionen (MD5, SHA-1, SHA-2) gilt: Wenn Sie H(m) kennen, können Sie H(m||padding||m') berechnen, ohne m zu kennen. Dadurch werden MAC-Konstruktionen wie H(secret||message) unsicher. Abhilfe schaffen HMAC (mit innerem und äußerem Padding) oder SHA-3 (Sponge-Konstruktion, immun gegen Längenerweiterungsangriffe).

Kollisionsresistenz: Finden Sie zwei beliebige verschiedene Nachrichten mit demselben Hash (Aufwand 2^{n/2}). Zweitpräbildresistenz: Gegeben m, finden Sie m' ≠ m mit demselben Hash (Aufwand 2^n). Präbildresistenz: Finden Sie zu einem gegebenen Hash eine beliebige Nachricht (Aufwand 2^n). Die Kollisionsresistenz ist immer die schwächste dieser Eigenschaften.

Wenn ein MAC eine kollisionsanfällige Hashfunktion verwendet, kann ein Angreifer, der Kollisionen in H finden kann, möglicherweise MACs fälschen. HMAC-MD5 gilt trotz der MD5-Kollisionen als sicher, weil die HMAC-Konstruktion Präbildangriffe und nicht nur Kollisionen erfordert. Für neue Systeme sollten Sie dennoch von HMAC-MD5 wegmigrieren.

Joux (2004): Bei Merkle-Damgård-Hashfunktionen erfordert das Finden von 2^k-fachen Kollisionen (2^k Nachrichten mit demselben Hash) nur das k-Fache des Aufwands für eine einzelne Kollision, nicht das k-Fache mehr. Dadurch verstärken sich Schwachstellen verketteter Hashfunktionen (H1(m)||H2(m) ist nicht so sicher, wie Sie vielleicht denken).

Verwenden Sie SHA-256 oder SHA-3 für kollisionsresistentes Hashing. Vermeiden Sie MD5 und SHA-1 für jeden Sicherheitszweck. Für MACs: HMAC-SHA-256 oder HMAC-SHA-3. Für Passwort-Hashing: Argon2 (nicht direkt SHA-2). Verwenden Sie immer SHA-3, wenn Resistenz gegen Längenerweiterungsangriffe erforderlich ist.

Wie viele Hash-Berechnungen sind ungefähr erforderlich, um eine Kollision in einer n-Bit-Hashfunktion zu finden?

Der Geburtstagsangriff findet Hash-Kollisionen mit einem Aufwand von 2^{n/2}. Für MD5 existieren praktisch nutzbare Kollisionen mit gewähltem Präfix; SHA-1 wurde 2017 gebrochen. Längenerweiterungsangriffe brechen naive MACs der Form H(key||msg). Verwenden Sie SHA-256 oder SHA-3 sowie HMAC zur Nachrichtenauthentifizierung. Als Nächstes: Meet-in-the-Middle-Angriffe.