Geburtstagsangriff/Geburtstagsparadoxon

Als Geburtstagsparadoxon wird ein Phänomen aus der Kombinatorik bezeichnet, bei dem die statistischen Wahrscheinlichkeiten für zwei ähnliche Ereignisse überraschend stark voneinander abweichen.

Folgende zwei Szenarien werden dabei miteinander verglichen:

  1. Wie viele Gäste muss ein Gastgeber zu seiner Geburtstagsfeier einladen, so dass mit einer Wahrscheinlichkeit von mindestens 50% wenigstens ein Gast am selben Tag Geburtstag hat wie der Gastgeber?


  2. Wie viele Personen müssen auf der Geburtstagsfeier anwesend sein, so dass mit einer Wahrscheinlichkeit von mindestens 50% zwei beliebige Anwesende am gleichen Tag Geburtstag haben?

Antwort: Es müssen mindestens 253 Personen auf der Feier anwesend sein, damit der Gastgeber mit einer 50%-Wahrscheinlichkeit nicht das einzige Geburtstagskind auf seiner Feier ist.

Dagegen liegt schon bei 23 anwesenden Gästen die Wahrscheinlichkeit bei über 50%, dass zwei Gäste am gleichen Tag Geburtstag haben (welcher Tag das ist, ist egal).

Aufgrund der großen Diskrepanz zwischen 253 Gästen im einen und 23 Gästen im anderen Szenario spricht man von einem Paradoxon.

Details zur Herleitung der Formeln finden Sie z.B. in Jan Blumenstein: Methoden und Werkzeuge für Angriffe auf die digitale Signatur, 2003.

Übertragen auf die Suche nach Hashwert-Kollisionen bedeutet das:

Wenn man an beiden Dokumenten Änderungen vornehmen kann statt ein Dokument fix zu halten, braucht man von drastisch weniger veränderten Dokumenten die Hashwerte zu berechnen, um 2 Dokumente mit demselben Hashwert zu finden.

Lässt man am Vergleichsdokument keine Änderung zu, hat man bei einer 128-Bit-Hashfunktion mit 50% Wahrscheinlichkeit nach etwa 2127 Rechenschritten ein verändertes zweites Dokument mit gleichem Hashwert gefunden (2127 ~ 1,7 * 1038).

Der Geburtstagsangriff ermöglicht es, 128-Bit-Hashfunktionen nach etwa 264 Rechenschritten zu brechen: Dabei werden Veränderungen an beiden Dokumenten vorgenommen – es ist wie im 2. Beispiel oben egal, welcher Hashwert (Geburtstag) herauskommt, wichtig ist, dass sie gleich sind (264 ~ 1,8 * 1019).

Da 264 ein Aufwand ist, der mit einer großen Anzahl von heute üblichen parallel geschalteten Rechnern bewältigt werden kann, gelten 128-Bit-Hashfunktionen im Kontext starke Kryptographie als nicht mehr sicher.

Weitere Online-Hilfe hierzu: