Das Birthday Paradox
Wie viele Personen müssen sich in einem Raum befinden, damit die Wahrscheinlichkeit größer als 50 Prozent ist, dass mindestens zwei von ihnen am selben Tag Geburtstag haben?
Vielleicht 100?
Oder 183, weil das ungefähr der Hälfte von 365 Tagen entspricht?
Tatsächlich reichen bereits:
23 Personen.
Unter der vereinfachenden Annahme von 365 gleich wahrscheinlichen Geburtstagen liegt die Wahrscheinlichkeit für mindestens einen gemeinsamen Geburtstag bei rund 50,7 Prozent.
Dabei handelt es sich um ein vereinfachtes Wahrscheinlichkeitsmodell: Der 29. Februar wird ignoriert, und alle 365 Tage gelten als gleich wahrscheinlich.
Dieses überraschende Ergebnis wird als Birthday Paradox oder Geburtstagsparadoxon bezeichnet.
Für kryptografische Hashfunktionen ist dieser Effekt besonders interessant, weil er erklärt, warum die Kollisionssicherheit eines idealen Hashes deutlich kleiner ist als seine Ausgabelänge vermuten lässt.
Warum sind 23 Personen schon genug?
Der entscheidende Denkfehler besteht häufig darin, folgende zwei Fragen miteinander zu verwechseln:
Wie wahrscheinlich ist es, dass jemand meinen Geburtstag hat?
und:
Wie wahrscheinlich ist es, dass irgendwelche zwei Personen denselben Geburtstag haben?
Das sind unterschiedliche Probleme.
Bei 23 Personen gibt es nicht nur 23 Möglichkeiten für einen Treffer.
Jede Person kann mit jeder anderen Person verglichen werden.
Die Anzahl möglicher Paare beträgt:
n × (n - 1) / 2
Bei 23 Personen sind das:
23 × 22 / 2
=
253 Paare
Es gibt also bereits 253 mögliche Paare, bei denen ein gemeinsamer Geburtstag auftreten könnte.
Die Gegenwahrscheinlichkeit ist einfacher
Die Wahrscheinlichkeit für mindestens einen gemeinsamen Geburtstag lässt sich besonders einfach über die Gegenwahrscheinlichkeit berechnen.
Zunächst fragen wir:
Wie wahrscheinlich ist es, dass alle Personen unterschiedliche Geburtstage haben?
Für die erste Person spielt der Geburtstag keine Rolle:
365 / 365
Für die zweite Person bleiben 364 Tage:
364 / 365
Für die dritte:
363 / 365
und so weiter.
Für n Personen ergibt sich:
P(keine Übereinstimmung)
=
365/365
×
364/365
×
363/365
×
...
×
(365 - n + 1)/365
Damit ist:
P(mindestens eine Übereinstimmung)
=
1 - P(keine Übereinstimmung)
Für 23 Personen ergibt sich ungefähr:
50,7 %
Das wirkt zunächst überraschend – mathematisch ist es aber eine direkte Folge der schnell wachsenden Anzahl möglicher Paare.
Was hat das mit Hashfunktionen zu tun?
Statt Geburtstagen können wir uns Hashwerte vorstellen.
Angenommen, wir hätten eine stark vereinfachte Hashfunktion mit nur 365 möglichen Hashwerten.
Jede Eingabe erzeugt einen dieser Werte.
Wenn wir immer mehr unterschiedliche Eingaben hashen, steigt die Wahrscheinlichkeit, dass irgendwann zwei davon denselben Hashwert besitzen.
Eingabe A → 127
Eingabe B → 291
Eingabe C → 044
...
Eingabe X → 127
Jetzt haben zwei unterschiedliche Eingaben denselben Hashwert:
Hash(A) = Hash(X)
Wir haben eine Hash Collision gefunden.
Was eine Hash Collision genau ist, erkläre ich im Artikel Was ist eine Hash Collision?.
Von 365 Geburtstagen zu 2²⁵⁶ Hashwerten
SHA-256 besitzt natürlich nicht nur 365 mögliche Ausgaben.
Ein SHA-256-Hash besteht aus 256 Bit.
Damit gibt es:
2²⁵⁶
mögliche Hashwerte.
Das ist eine unvorstellbar große Zahl.
Trotzdem müssen für eine generische Kollisionssuche nicht ungefähr 2²⁵⁶ Hashwerte berechnet werden.
Der Birthday-Effekt führt dazu, dass Kollisionen bereits in der Größenordnung von:
√(2²⁵⁶)
=
2¹²⁸
relevant werden.
Allgemein gilt für einen idealen n-Bit-Hash:
Kollisionsaufwand ≈ 2^(n/2)
NIST führt SHA-256 deshalb mit einer Collision-Resistance-Stärke von 128 Bit.
Warum bedeutet 50 Prozent nicht, dass danach sicher eine Collision existiert?
Der Birthday Bound ist eine Wahrscheinlichkeitsaussage.
Er sagt nicht:
Nach einer bestimmten Anzahl von Versuchen muss eine Kollision auftreten.
Stattdessen steigt mit der Anzahl untersuchter Hashwerte die Wahrscheinlichkeit, mindestens ein kollidierendes Paar zu finden.
Das ist ein wichtiger Unterschied.
Auch nach Erreichen der Größenordnung des Birthday Bounds ist eine Kollision nicht garantiert.
Probier es selbst aus
Mit dem folgenden Birthday Collision Simulator kannst du die Größe eines Hashraums auswählen und festlegen, wie viele Hashwerte erzeugt werden.
Der Simulator berechnet daraus exakt, wie wahrscheinlich mindestens eine Hash Collision ist – und zeigt, wie viele Paare dabei miteinander verglichen werden.
Probier zuerst das Geburtstagsbeispiel mit 23 Personen aus und wechsle danach zu einem 16- oder 24-Bit-Hashraum.
Birthday Collision Simulator
Wähle die Größe des Hashraums und die Anzahl erzeugter Hashwerte – die Wahrscheinlichkeit einer Hash Collision wird sofort exakt berechnet.
- Ausgabelänge
- 8 Bit
- Mögliche Hashwerte
- 28 = 256
- Erzeugte Hashwerte
- 20
- Mögliche Paare k(k−1)/2
- 190
- Exakte Wahrscheinlichkeit
- 53,3 %
- Näherung 1 − e^(−k(k−1)/(2N))
- ≈ 52,4 %
- Birthday Bound (Größenordnung)
- 24 ≈ 16
- 50-%-Schwelle √(2·N·ln 2)
- ≈ 18,8 (exakt ab 20)
Die exakte Wahrscheinlichkeit folgt aus P(keine Collision) = N/N × (N−1)/N × … × (N−k+1)/N. Die Näherung ist nur eine Abschätzung. 2n/2 beschreibt die Größenordnung, ab der Collisions wahrscheinlich werden – keine exakte 50-%-Grenze.
Merke: Entscheidend ist nicht die Zahl der Hashwerte, sondern die Zahl der Paare. Sie wächst quadratisch – deshalb reichen schon etwa √N Versuche für eine realistische Chance auf eine Hash Collision.
Du findest dieses Tool auch im Tools-Bereich.
Achte dabei besonders auf den Wert bei ungefähr 2^(n/2) erzeugten Hashwerten: Dort liegt die Wahrscheinlichkeit bereits bei rund 39 Prozent.
Wie ein echtes Experiment mit zufälligen Eingaben aussieht, zeige ich im Artikel Wie funktioniert ein Birthday Attack?. Dort wird so lange gehasht, bis tatsächlich eine Collision auftritt – und wiederholst du das Experiment, tritt die erste Collision nicht immer beim gleichen Versuch auf.
Birthday Paradox und Collision Resistance
Jetzt wird auch verständlicher, warum Hashlänge und Collision Resistance nicht dasselbe sind.
Für einen idealen Hash gilt grob:
| Hashlänge | generische Collision Security |
|---|---|
| 128 Bit | 64 Bit |
| 256 Bit | 128 Bit |
| 384 Bit | 192 Bit |
| 512 Bit | 256 Bit |
Das bedeutet nicht, dass bei SHA-256 „128 Bit fehlen“.
Die 128 Bit sind die erwartete generische Kollisionssicherheit eines idealen 256-Bit-Hashes.
Diesen Zusammenhang erkläre ich ausführlicher im Artikel Was ist Collision Resistance?.
Birthday Paradox und Preimage Resistance
Das Birthday Paradox erklärt außerdem einen wichtigen Unterschied zu Preimage Resistance.
Bei einer Collision darf ich irgendein kollidierendes Paar suchen:
x ≠ y
Hash(x) = Hash(y)
Bei einem Preimage-Angriff ist dagegen bereits ein bestimmter Hashwert vorgegeben:
H
gesucht:
x mit Hash(x) = H
Ich kann also nicht einfach auf irgendeine Übereinstimmung warten.
Deshalb liegt der generische Preimage-Aufwand für einen idealen 256-Bit-Hash in der Größenordnung von:
2²⁵⁶
während der generische Kollisionsaufwand bei ungefähr:
2¹²⁸
liegt.
Mehr dazu erkläre ich im Artikel Was ist Preimage Resistance?.
Das Wichtigste in Kürze
Das Birthday Paradox beschreibt den überraschend schnellen Anstieg der Wahrscheinlichkeit, dass in einer Gruppe zwei Werte übereinstimmen.
Die wichtigsten Punkte:
- Bei 23 Personen liegt die Wahrscheinlichkeit für mindestens einen gemeinsamen Geburtstag im vereinfachten Modell mit 365 gleich wahrscheinlichen Tagen bereits bei rund 50,7 Prozent.
- Entscheidend ist die schnell wachsende Anzahl möglicher Paare.
- Derselbe mathematische Effekt spielt bei Hash Collisions eine wichtige Rolle.
- Bei einem idealen
n-Bit-Hash liegt der generische Kollisionsaufwand in der Größenordnung von2^(n/2). - Für einen idealen 256-Bit-Hash ergibt sich deshalb ungefähr
2¹²⁸. - NIST führt SHA-256 entsprechend mit 128 Bit Collision Resistance.
- Das Birthday Paradox betrifft die Suche nach beliebigen Kollisionen und ist nicht mit einem Preimage-Angriff gleichzusetzen.
Wie geht es weiter?
Das Birthday Paradox erklärt, warum Kollisionen früher auftreten als man intuitiv erwarten könnte.
Im nächsten Artikel geht es darum, wie sich dieses Prinzip gezielt für einen Angriff verwenden lässt:
Wie funktioniert ein Birthday Attack?
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 kryptografischen Hashfunktionen, darunter die Collision-Resistance-Stärke von SHA-256.
-
National Institute of Standards and Technology (NIST), SP 800-57 Part 1 Rev. 5 – Recommendation for Key Management: Part 1 – General Definition und Einordnung kryptografischer Security Strength.