Quelltext der Seite 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-Angriff]]en 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 Signatur|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 <code>4ddb0c25</code>.

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 nächstliegenden Ansätze besteht darin, ein Dokument <math>x</math> zu wählen, für dieses den Hashwert <math>y = H(x)</math> zu berechnen und dann ein zweites Dokument <math>x'</math> zu suchen, das ebenfalls den Hashwert <math>y</math> 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 <math>m</math>, wobei <math>m</math> die Anzahl der möglichen Hashwerte ist.

Beispiel: [[SHA-1]] hat immer eine binäre 160-Bit-Ausgabe, also 2<sup>160</sup> mögliche Hashwerte. Dieser Algorithmus muss bei SHA-1 den Test also durchschnittlich 2<sup>159</sup> 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&#8239;·&#8239;10<sup>31</sup> Jahre.

== Geburtstagsangriff ==
Eine viel höhere Erfolgswahrscheinlichkeit erreicht man mit dem Geburtstagsangriff. Hier wählen wir zufällig <math>q</math> Dokumente <math>x_1</math> bis <math>x_q</math>, berechnen jeweils <math>y_1 = H(x_1)</math> bis <math>y_q = H(x_q)</math> und testen dann, ob unter den <math>y_i</math> 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 <math>m</math> möglichen Hashwerten die Erfolgswahrscheinlichkeit

:<math>p = 1 - \left(\frac{m}{m} \cdot \frac{m-1}{m} \cdot \frac{m-2}{m} \cdots \frac{m-q+1}{m} \right)</math>

Nach Umformung und Abschätzung ergibt sich, dass man etwa <math>q = 1{,}18\cdot\sqrt{m}</math> Dokumente durchmustern muss, um eine Erfolgswahrscheinlichkeit von ''p''&nbsp;=&nbsp;½ zu erhalten.

Für das Beispiel SHA-1 bedeutet das, dass 1,18&#8239;·&#8239;2<sup>80</sup> 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&#8239;·&#8239;10<sup>7</sup> 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 (Digitale Zertifikate)|Zertifizierungsstelle]] unterschreiben. Bei einer [[Digitale Signatur|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.<ref>Alexander Sotirov et al.: [https://www.win.tue.nl/hashclash/rogue-ca/ ''MD5 considered harmful today'']. 30. Dezember 2008.</ref>

== Siehe auch ==
* [[Kollisionsresistenz]]

== Literatur ==
* {{Literatur| Autor = Claudia Eckert| Titel = IT-Sicherheit: Konzepte – Verfahren – Protokolle| Verlag= Oldenbourg| ISBN  = 978-3-486-58270-3| Seiten= 349}}

== Weblinks ==
* [https://www.heise.de/security/artikel/Konsequenzen-der-erfolgreichen-Angriffe-auf-SHA-1-270648.html heise.de – Konsequenzen der erfolgreichen Angriffe auf SHA-1]
* [https://www.mscs.dal.ca/~selinger/md5collision/ Beispielimplementation von MD5-Kollisionen zweier unterschiedlicher Programme]

== Einzelnachweise ==
<references />

[[Kategorie:Kryptanalytisches Verfahren]]