Kollisionsangriff

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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^{160} mögliche Hashwerte. Dieser Algorithmus muss bei SHA-1 den Test also durchschnittlich 2^{160} 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·1031 Jahre.

Geburtstagsangriff[Bearbeiten]

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·280 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·107 Jahre.

Praktische Angriffe[Bearbeiten]

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.[1]

Siehe auch[Bearbeiten]

Einzelnachweise[Bearbeiten]

  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[Bearbeiten]

  •  Claudia Eckert: IT-Sicherheit: Konzepte – Verfahren – Protokolle. Oldenbourg, ISBN 978-3-486-58270-3, S. 349.

Weblinks[Bearbeiten]