Kollisionsangriff

Ein Kollisionsangriff ist ein Angriff auf eine kryptologische Hashfunktion mit dem Ziel, zwei verschiedene Dokumente zu finden, die auf einen identischen Hashwert führen. Im Gegensatz zu Preimage-Angriffen sind dabei beide Dokumente (und damit auch der Hashwert) frei wählbar.

Eine beliebte Strategie für schlüssellose Hashfunktionen ist der Geburtstagsangriff, der das namensgebende Geburtstagsparadoxon nutzt, um eine hohe Erfolgswahrscheinlichkeit zu erzielen. Dadurch kann die Anzahl der Versuche deutlich reduziert werden. Bei diesem Angriff wird immer davon ausgegangen, dass keine Schwächen des Algorithmus bekannt sind, da man andernfalls diese Schwächen nutzen würde, um das Problem zu lösen. Man geht außerdem davon aus, dass die Menge der möglichen Dokumente mindestens doppelt so groß ist wie die Menge der möglichen Hashwerte. Dies nennt man "Kompressions-Eigenschaft".

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 $\tfrac{m}{2}$, 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 $\tfrac{2^{160}}{2} = 2^{159}$ Wiederholungen ausführen, bis er eine Kollision findet. Für einen Rechner, der 1 Milliarde Versuche pro Sekunde schafft, beträgt die Laufzeit 2,3·10³¹ Jahre.

Geburtstagsangriff

Eine viel höhere Erfolgswahrscheinlichkeit erreicht man mit dem Geburtstagsangriff. Hier wählen wir zufällig q Dokumente x₁ bis x_q, berechnen jeweils y₁ = H(x₁) 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 die Erfolgswahrscheinlichkeit

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

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 durchschnittlich 1,18·2⁸⁰ Versuche benötigt werden. Für einen Rechner, der 1 Milliarde Versuche pro Sekunde schafft, beträgt die Laufzeit hier nur noch 4,5·10⁷ Jahre.

Praktische Angriffe

Besonderes Merkmal der bisher bekannten Umsetzungen von Kollisionsangriffen ist, dass beide Dokumente aus derselben Quelle erzeugt werden müssen. 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 Zeritifizierungsstelle darf. Er lässt nun das erste von einer Zertifizierungsstelle unterschreiben. Damit besitzt er auch eine Unterschrift für das zweite und kann nun gültige Zertifikate für beliebige Schlüssel erstellen.^[1]

Siehe auch

• Kollisionssicherheit

Einzelnachweise

1. ↑ Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger: MD5 considered harmful today. (http://www.win.tue.nl/hashclash/rogue-ca/).

Literatur

• Claudia Eckert: IT-Sicherheit: Konzepte – Verfahren – Protokolle. Oldenbourg, ISBN 3486582704, S. 349.

Weblinks

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