Kollisionsangriff

Ein Kollisionsangriff ist ein Angriff auf eine kryptologische Hashfunktion mit dem Ziel, zwei verschiedene Dokumente zu finden, die auf einen identischen Hashwert abgebildet werden. Im Gegensatz zu Preimage-Angriffen sind dabei beide Dokumente (und damit auch der Hashwert) frei wählbar. Werden solche Kollisionen gefunden, bedeutet dies unter anderem, dass die Hashfunktion für kryptografische Anwendungen (Datenverschlüsselung, digitale Signaturverfahren) nicht geeignet ist. Bei Hashfunktionen, die nicht entwickelt wurden, um kryptologischen Anforderungen zu genügen, sind solche Kollisionen oft leicht zu finden. Ein Beispiel hierfür ist die CRC-32-Prüfsumme: Die Wörter "buckeroo" und "plumless" führen beide zum Prüfwert 4ddb0c25.

Ein generischer Angriff auf schlüssellose Hashfunktionen ist der Geburtstagsangriff, der das namensgebende Geburtstagsparadoxon nutzt, um eine hohe Erfolgswahrscheinlichkeit zu erzielen. Dieser Angriff ist auf jede Hashfunktion möglich und reduziert die Anzahl der Versuche deutlich (auf die Quadratwurzel der möglichen Hashwerte). Da dieser Angriff immer möglich ist, bildet er einen Vergleichswert, an dem andere Angriffe gemessen werden: Ein erfolgreicher Angriff auf eine Hashfunktion muss effizienter sein als der Geburtstagsangriff. Dazu muss er Schwächen der Hashfunktion ausnutzen.

Naiver Ansatz

Einer der naheliegendsten Ansätze besteht darin, ein Dokument $x$ zu wählen, für dieses den Hashwert $y=H(x)$ zu berechnen und dann ein zweites Dokument $x'$ zu suchen, das ebenfalls den Hashwert $y$ hat. Dieser Ansatz entspricht einem Preimage-Angriff.

 NaiveCollision(H)
     wähle zufälliges Dokument x
     y := H(x)
    REPEAT
        wähle zufälliges Dokument x' != x
    UNTIL H(x') = y
    RETURN (x, x')

Hierbei ergibt sich eine durchschnittliche Laufzeit von $m$, wobei $m$ die Anzahl der möglichen Hashwerte ist.

Beispiel: SHA-1 hat immer eine binäre 160-Bit-Ausgabe, also 2¹⁶⁰ mögliche Hashwerte. Dieser Algorithmus muss bei SHA-1 den Test also durchschnittlich 2¹⁵⁹ Wiederholungen ausführen, bis er eine Kollision findet. Für einen Rechner, der 1 Milliarde Versuche pro Sekunde schafft, beträgt die Laufzeit 4,6 · 10³¹ Jahre.

Geburtstagsangriff

Eine viel höhere Erfolgswahrscheinlichkeit erreicht man mit dem Geburtstagsangriff. Hier wählen wir zufällig $q$ Dokumente $x_{1}$ bis $x_{q}$, berechnen jeweils $y_{1}=H(x_{1})$ bis $y_{q}=H(x_{q})$ und testen dann, ob unter den $y_{i}$ zwei gleich sind.

 BirthdayCollision(H)
     wähle zufällige Dokumente x_1 ... x_q
    FOR i = 1 TO q
        berechne y_i := H(x_i)
     finde i, j mit i != j und y_i = y_j
    RETURN (x_i, x_j)

Hierbei ergibt sich analog zum Geburtstagsparadoxon bei $m$ möglichen Hashwerten die Erfolgswahrscheinlichkeit

$p=1-\left({\frac {m}{m}}\cdot {\frac {m-1}{m}}\cdot {\frac {m-2}{m}}\cdots {\frac {m-q+1}{m}}\right)$

Nach Umformung und Abschätzung ergibt sich, dass man etwa $q=1{,}18\cdot {\sqrt {m}}$ Dokumente durchmustern muss, um eine Erfolgswahrscheinlichkeit von p = ½ zu erhalten.

Für das Beispiel SHA-1 bedeutet das, dass 1,18 · 2⁸⁰ Versuche benötigt werden, um mit einer Wahrscheinlichkeit von ½ eine Kollision zu finden. Für einen Rechner, der 1 Milliarde Versuche pro Sekunde schafft, beträgt die Laufzeit hier nur noch 4,5 · 10⁷ Jahre.

Praktische Angriffe

Die meisten standardisierten Hashfunktionen beruhen auf der Merkle-Damgård-Konstruktion. Aufgrund ihrer Struktur ist es leicht, wenn einmal eine Kollision gefunden wurde, weitere Kollisionen, also Nachrichtenpaare mit gleichem Hashwert zu erzeugen. Für den MD5-Algorithmus sind sogar Kollisionen bekannt, bei denen der Anfang der Nachricht frei wählbar ist. Somit kann ein Angreifer zwei Dokumente mit unterschiedlichem Inhalt aber gleichem Hashwert erstellen. Beispielsweise kann er zwei Zertifikate erstellen, die den gleichen Hashwert besitzen. Eines davon ist ein unverdächtiges Zertifikat, das zweite Zertifikat berechtigt ihn zum Ausstellen weiterer Zertifikate, was eigentlich nur eine Zertifizierungsstelle darf. Er lässt nun das erste von einer Zertifizierungsstelle unterschreiben. Bei einer digitalen Signatur wird aber in der Regel nicht die ganze Nachricht, sondern nur deren Hashwert unterschrieben. Damit besitzt der Angreifer auch eine Unterschrift für das zweite und kann nun gültige Zertifikate für beliebige Schlüssel erstellen.

Siehe auch

• Kollisionssicherheit

Weblinks

• heise.de – Konsequenzen der erfolgreichen Angriffe auf SHA-1
• Beispielimplementation von MD5-Kollisionen zweier unterschiedlicher Programme