Article
Geburtstagsparadoxon: Die Mathematik hinter Hash-Kollisionen
Intuition täuscht
In einem Raum mit nur 23 Menschen besteht bereits eine 50%ige Wahrscheinlichkeit, dass zwei von ihnen am selben Tag Geburtstag haben. Das erscheint kontraintuitiv, lässt sich aber mit Schulmathematik beweisen.
Der mathematische Ansatz
Die Wahrscheinlichkeit für mindestens ein übereinstimmendes Geburtstagspaar berechnet sich über die inverse Wahrscheinlichkeit, dass niemand am selben Tag Geburtstag hat:
P(mindestens eine Übereinstimmung) = 1 - P(keine Übereinstimmungen)
Bei n Personen: P(keine Übereinstimmungen) = 365!/365^n(365-n)!
Für n=23 ergibt sich etwa 50%.
Von Mises und die “Occupancy Probability”
1939 erklärte der österreichische Mathematiker Richard von Mises einen häufigen Fehler. Versicherungsmathematiker hatten berechnet, wie wahrscheinlich drei von 60 Kollegen am selben Tag Geburtstag haben und kamen auf ~0.06%. Von Mises zeigte: Die Fragestellung war falsch.
Statt nach einem spezifischen Tag zu fragen, sollte man fragen: “Wie oft erwarten wir diesen Ereignistyp allgemein?” Bei 60 Menschen beträgt die Wahrscheinlichkeit etwa 22% für irgendeine Dreifach-Übereinstimmung.
Verbindung zur IT-Sicherheit
Das Birthday Problem ist fundamental für Hash-Tabellen und Kryptographie:
- Hash-Tabellen: Tage werden zu Tabellenfeldern, Menschen zu Hashes. Die Kollisionsberechnungen bleiben identisch.
- Birthday Attack: Ein spezieller Brute-Force-Angriff nutzt diese Mathematik, um Kollisionen zu erzeugen. Statt auf einen spezifischen Hash-Wert zu warten, genügt irgendeine Kollision. SHA-256 mit 2^256 Ausgaben würde etwa 2^128 Versuche zum Knacken benötigen.
Der Erwartungswert E(x_s) erlaubt die approximative Darstellung der Kollisionen, die in einer Hash-Tabelle auftreten werden, abhängig von den gewählten Werten.