Wie funktioniert ein Birthday Attack?
Das Birthday Paradox zeigt, dass Übereinstimmungen in einer großen Menge möglicher Werte überraschend schnell auftreten können.
In der Kryptografie lässt sich genau dieser Effekt auf Hashfunktionen übertragen.
Ein Birthday Attack ist ein generischer Ansatz zur Suche nach Hash Collisions.
Das Ziel lautet:
Finde x und y
mit:
x ≠ y
und
Hash(x) = Hash(y)
Der Angreifer versucht also nicht, einen bestimmten Hashwert zu treffen.
Er sucht irgendein Paar unterschiedlicher Eingaben mit demselben Hash.
Ein stark vereinfachtes Beispiel
Stellen wir uns eine Hashfunktion mit nur 8 Bit Ausgabe vor.
Dann existieren:
2⁸ = 256
mögliche Hashwerte.
Wir erzeugen unterschiedliche Eingaben:
Input 1 → 73
Input 2 → 194
Input 3 → 21
Input 4 → 238
...
und speichern die Ergebnisse.
Irgendwann könnte Folgendes passieren:
Input 12 → 73
Damit haben wir:
Hash(Input 1)
=
Hash(Input 12)
obwohl:
Input 1 ≠ Input 12
Das ist eine Collision.
Warum müssen nicht alle 256 Werte ausprobiert werden?
Weil wir keinen bestimmten Hashwert suchen.
Jeder neue Hashwert wird mit allen bereits gefundenen Hashwerten verglichen.
Mit jeder zusätzlichen Eingabe wächst damit die Anzahl möglicher Paare.
Für einen idealen n-Bit-Hash liegt der generische Kollisionsaufwand deshalb in der Größenordnung von:
2^(n/2)
Bei 8 Bit bedeutet das ungefähr:
2⁴ = 16
Bei SHA-256:
2¹²⁸
Das zugrunde liegende Wahrscheinlichkeitsproblem erkläre ich ausführlich im Artikel Das Birthday Paradox.
Wie sieht ein generischer Birthday Attack aus?
Vereinfacht könnte ein Angriff so aussehen:
1. Erzeuge eine Eingabe.
2. Berechne ihren Hash.
3. Speichere Eingabe und Hash.
4. Erzeuge eine weitere Eingabe.
5. Berechne ihren Hash.
6. Prüfe, ob dieser Hash bereits vorhanden ist.
7. Wiederhole den Vorgang.
Sobald ein bereits gespeicherter Hash erneut auftritt, existieren zwei unterschiedliche Eingaben mit demselben Hashwert.
Konzeptionell:
A → 42
B → 91
C → 17
D → 203
E → 42
Damit gilt:
Hash(A) = Hash(E)
und der Angriff hat eine Collision gefunden.
Warum ist das bei SHA-256 trotzdem nicht praktikabel?
2¹²⁸ ist wesentlich kleiner als 2²⁵⁶.
Aber 2¹²⁸ ist immer noch eine enorme Größenordnung.
NIST ordnet SHA-256 deshalb eine Collision-Resistance-Stärke von 128 Bit zu.
„Nur halb so viele Bits“ bedeutet nicht, dass der Angriff plötzlich praktisch wird.
128 Bit Security stehen für einen Arbeitsaufwand in der Größenordnung von 2¹²⁸ grundlegenden Operationen. NIST definiert Security Strength genau über die Größenordnung des zum Brechen eines kryptografischen Systems erforderlichen Arbeitsaufwands.
Warum SHA-256 trotz 256 Bit Ausgabe genau diese Kollisionssicherheit besitzt, erkläre ich im Artikel Was ist Collision Resistance?.
Birthday Attack ist kein Preimage Attack
Bei einem Birthday Attack sucht ein Angreifer:
irgendein x
und
irgendein y
mit gleichem Hash.
Bei einem Preimage Attack ist dagegen bereits ein Zielhash vorgegeben:
H
und gesucht wird:
x mit Hash(x) = H
Der Angreifer besitzt beim Birthday Attack also wesentlich mehr Freiheit.
Genau daraus entsteht der Unterschied zwischen ungefähr 2^(n/2) für generische Kollisionen und 2^n für generische Preimage-Suche bei einem idealen n-Bit-Hash.
Was Preimage Resistance bedeutet, erkläre ich im Artikel Was ist Preimage Resistance?.
Birthday Attack ist auch kein Second-Preimage Attack
Beim Second-Preimage Attack ist bereits eine konkrete Eingabe vorgegeben:
x
Gesucht wird eine andere:
y
mit:
Hash(x) = Hash(y)
Beim Birthday Attack darf der Angreifer dagegen beide Eingaben auswählen.
Eine Möglichkeit, irgendeine Collision zu finden, bedeutet deshalb nicht automatisch, dass zu einer beliebigen bestehenden Nachricht ein Second Preimage gefunden werden kann.
Mehr dazu erkläre ich im Artikel Was ist Second-Preimage Resistance?.
Probier den Angriff selbst aus
Für SHA-256 wäre ein echtes Experiment mit vollständigen Hashwerten natürlich völlig ungeeignet – wir wollen schließlich nicht 2¹²⁸ Werte erzeugen.
Stattdessen lässt sich der Effekt mit einem künstlich verkleinerten Hashraum demonstrieren.
Das folgende Tool berechnet für zufällige Eingaben den vollständigen SHA-256-Hash, vergleicht aber nur die ersten 8, 12, 16 oder 20 Bit.
Bei 16 Bit gibt es:
65.536
mögliche Werte.
Der Birthday Bound liegt aber nur in der Größenordnung von:
2⁸ = 256
Versuchen.
Starte das Experiment und beobachte, nach wie vielen zufälligen Eingaben die erste Collision gefunden wird:
Birthday Attack auf einen gekürzten Hash
Starte das Experiment: Es werden zufällige Eingaben gehasht, bis zwei davon denselben gekürzten Hashwert liefern.
Für dieses Experiment wird SHA-256 berechnet, aber nur ein kleiner Teil des Hashwerts verglichen. Dadurch wird der Hashraum künstlich verkleinert. Über vollständiges SHA-256 sagt das Experiment nichts aus.
- Effektive Bitlänge
- 16 Bit
- Mögliche gekürzte Hashwerte
- 216 = 65.536
- Birthday Bound (Größenordnung)
- 28 = 256
- Erwartete Versuche √(π·N/2)
- ≈ 321
- Versuche
- 0
- Vergangene Zeit
- –
Merke: Bei 216 möglichen Werten genügen meist Versuche in der Größenordnung von 28. Für vollständiges SHA-256 wären das rund 2128 – praktisch unerreichbar.
Du findest dieses Tool auch im Tools-Bereich.
Wiederholst du das Experiment mehrmals, schwankt die Zahl der Versuche – sie bleibt aber fast immer in der Größenordnung von 2^(n/2) und weit unter der Zahl möglicher Werte.
Wichtig: Das Kürzen des Hashwerts dient hier ausschließlich der Demonstration. Es sagt nichts darüber aus, dass vollständiges SHA-256 praktisch kollidiert werden könnte.
Was schützt gegen Birthday Attacks?
Die wichtigste generische Verteidigung ist eine ausreichend große Hashausgabe in Verbindung mit einer kryptografisch sicheren Hashfunktion.
Wenn n Bit Ausgabe ungefähr n/2 Bit generische Kollisionssicherheit liefern, muss die Ausgabe entsprechend groß gewählt werden.
SHA-256 liefert beispielsweise 128 Bit generische Collision Resistance.
SHA-512 liefert 256 Bit.
Wie diese Sicherheitsstärken einzuordnen sind, erkläre ich im Artikel Wie sicher sind 128, 256 und 512 Bit?.
Das Wichtigste in Kürze
Ein Birthday Attack nutzt den Birthday-Effekt zur generischen Suche nach Hash Collisions.
- Gesucht werden zwei unterschiedliche Eingaben mit demselben Hashwert.
- Kein bestimmter Zielhash ist vorgegeben.
- Bei einem idealen
n-Bit-Hash liegt der generische Aufwand in der Größenordnung von2^(n/2). - Bei SHA-256 entspricht das einer Collision-Resistance-Stärke von 128 Bit.
2¹²⁸ist trotzdem eine praktisch enorme Größenordnung.- Ein Birthday Attack ist kein Preimage Attack.
- Er ist auch kein Second-Preimage Attack.
- Mit gekürzten Hashwerten lässt sich der Effekt sehr gut experimentell demonstrieren.
Wie geht es weiter?
Jetzt kennen wir sowohl die Mathematik hinter dem Birthday Paradox als auch ihre Bedeutung für Kollisionsangriffe.
Damit stellt sich eine naheliegende Frage:
Wie sicher sind 128, 256 und 512 Bit eigentlich?
Quellen und weiterführende Standards
Die folgenden Primär- und Normquellen bilden die Grundlage für die technischen Aussagen dieses Artikels:
-
National Institute of Standards and Technology (NIST), Hash Functions Security Strengths von SHA-2 und SHA-3, darunter die Collision-Resistance-Stärken von SHA-256 und SHA-512.
-
National Institute of Standards and Technology (NIST), CSRC Glossary – Security Strength Definition von Security Strength („Bits of Security“) über den zum Brechen erforderlichen Arbeitsaufwand.