Kollisions-Wahrscheinlichkeit (Geburtstagsparadoxon)
Näherung für die Anzahl Hashwerte, bei der die Kollisionswahrscheinlichkeit 50 % erreicht: n ≈ √(π/2 · 2^Hashlänge). Daraus folgt die effektive Sicherheit eines b-Bit-Hashes von rund b/2 Bit gegen Kollisionen.
Kollisions-Wahrscheinlichkeit (Geburtstagsparadoxon) berechnen
Näherung für die Anzahl Hashwerte, bei der die Kollisionswahrscheinlichkeit 50 % erreicht: n ≈ √(π/2 · 2^Hashlänge). Daraus folgt die effektive Sicherheit eines b-Bit-Hashes von rund b/2 Bit gegen Kollisionen.
- n — Hashwerte für 50 %
- Hashlänge — Hashlänge
Worum geht es?
Das Geburtstagsparadoxon liefert eine überraschende Aussage: Bei einer Hashfunktion mit b Bit Ausgabe genügen nur etwa √(π/2 · 2^b) zufällige Eingaben, um mit 50 % Wahrscheinlichkeit zwei gleiche Hashwerte zu finden.
Die exakte Wahrscheinlichkeit für mindestens eine Kollision bei n Werten beträgt 1 − e^(−n²/(2·2^b)). Daraus folgt die effektive Kollisionssicherheit eines b-Bit-Hashes von nur b/2 Bit.
Die Formel
n = √(π/2 · 2^Hashlänge)
Umstellung:
Hashlänge = log₂(n² · 2 / π)Die Variablen
| Symbol | Bedeutung | Einheit | Erklärung |
|---|---|---|---|
| Hashlänge | Hashlänge | Bit | Ausgabelänge des Hashes in Bit. |
| n | Hashwerte für 50 % | — | Anzahl Hashes für 50 % Kollision. |
Minimal-Beispiel
Wie viele Hashes für 50 % Kollision bei einer 64-Bit-Ausgabe?
n = √(π/2 · 2^64)
≈ √(2,89 · 10¹⁹)
≈ 5,38 · 10⁹Praxis-Beispiele
Beispiel 1 — MD5 (128 Bit)
n = √(π/2 · 2^128)
≈ 2,17 · 10¹⁹Beispiel 2 — SHA-256
n = √(π/2 · 2^256)
≈ 4,01 · 10³⁸Beispiel 3 — Benötigte Hashlänge für 2^80 Kollisionssicherheit
n = 2^80
Hashlänge = log₂((2^80)² · 2 / π)
≈ 160 − log₂(π/2)
≈ 159,3 Bit