Was ist eine Birthday Attack und was ist das Birthday Paradoxon?
Die Birthday Attack ist ein Angriff auf eine kryptographische Hashfunktion (z.B. SHA-1) und basiert auf dem Birthday Paradoxon.
Nötiges Vorwissen zur Hash-Funktion
Eine Hash-Funktion erzeugt aus einem großen Datensatz einen kurzen Hash-Wert, dieser dient als eine Art Fingerabdruck. Ein Beispiel ist die Hash-Funktion SHA-1, die für sicherheitsrelevante Anwendungen wie Signaturen Standard war.
Die Anwendung des Hash-Werts: Wenn ein gespeicherter Hash-Wert mit dem einer Kopie übereinstimmt, wird von gleichen bzw. unveränderten Daten ausgegangen.
Wie sicher ist eine kryptografischen Hash-Funktion?
Die Beurteilung der Güte einer kryptografischen Hash-Funktion basiert auf der Widerstandsfähigkeit gegen zwei Angriffs-Typen:
1. Preimage-Angriff: Ist eine Hash-Wert vorgegeben, wie schwer ist es dann eine Nachricht zu erzeugen, die zum selben Hash-Wert führt?
2. Birthday Attack (Kollionsangriff): Wie schwer ist es, zwei unterschiedliche Nachrichten mit gleicher Prüfsumme zu finden?
Aufwand für einen Angriff mit Brute-Force-Attacke
Die beiden Angriffsformen lassen sich mit einer Brute-Force-Attacke durchführen. Beispiel SHA-1: SHA-1 bildet Hash-Werte mit 160 Bit, es gibt insgesamt 2^160 Datensätze, viele ergeben denselben Hash-Wert.
Ist ein Wert vorgegeben (Preimage-Angriff) und man probiert 2^160 Nachrichten, gibt es mit sehr hoher Wahrscheinlichkeit einen Treffer. Die Suche würde mit gängiger Hardware allerdings mehr als 100 Millionen Jahre dauern.
Ist man jedoch nur an zwei Nachrichten mit gleichem Hash-Wert (egal welchem) interessiert, will also eine Kollision finden, sind für die gleiche Trefferwahrscheinlichkeit nur 2^80 Versuche nötig. Ein Preimage-Angriff benötigt also im Vergleich zum Kollisionsangriff 2^80 mal so viele Hash-Operationen.
Das Geburtstagsparadoxon
Den Unterschied zwischen den Angriffsformen veranschaulicht das Geburtstagsparadoxon: Bereits bei einer Gruppengröße von 23 Personen liegt die Wahrscheinlichkeit bei etwas über 50 Prozent, dass zwei beliebige Gruppenmitglieder am selben Tag (unabhängig vom Jahr) Geburtstag haben. Wird für einen vorgegeben Geburtstag eine weitere Person gesucht, sind für die gleiche Trefferwahrscheinlichkeit 253 Personen nötig. Da diese Wahrscheinlichkeit falsch eingeschätzt wird, ist von einem Paradoxon die Rede. Bei einer Gruppe aus 50 Personen liegt die Wahrscheinlichkeit bereits bei über 97 Prozent.
Die Birthday Attack
Bei der Birthday Attack wird ein Kollisionsangriff auf eine kryptografische Hashfunktion gestartet. Das Ziel: Zwei Dokumente finden, die auf den gleichen Hashwert abgebildet werden. Werden zwei solche Dokumente mit realistischem Aufwand gefunden, lässt sich die Hashfunktion nicht für die Kryptografie nutzen. Beim Kollisionsangriff ist daher die Frage: Wie schwierig ist es, zwei unterschiedliche Nachrichten mit gleicher Prüfsumme zu finden? Anfang 2017 haben Forscher von der Universität von Amsterdam und Google die Hashfunktion SHA-1 gebrochen. Sie haben zwei unterschiedliche PDF-Dateien mit demselben SHA-1 Hash erzeugt. Dafür wurde eine Rechenkapazität von 6.500 CPU-Jahren und 100 GPU-Jahre bereitgestellt. Als Alternative zu SHA-1 stehen unter anderem SHA-2 und SHA-3 bereit.