Rechnernetze

Geburtstagsangriff

Der Geburtstagsangriff beruht auf dem statistischen Phänomen, dass bereits in einer sehr kleinen Gruppe wenigstens zwei Personen mit fünfzigprozentiger Wahrscheinlichkeit am gleichen Tag Geburtstag haben.

Um das Geburtstagsparadoxon zu beweisen, geht man davon aus, dass alle Personen mit gleicher Wahrscheinlichkeit für jeden Tag des Jahres (zu 365 Tagen) Geburtstag haben, und dass diese Geburtstage unabhängig sind (also keine Zwillinge usw.). Die Wahrscheinlichkeit, dass eine Person nicht an einem von k Tagen Geburtstag hat, ist somit (365-k)/365.

	Eine Gruppe mit einer Person enthält mit Wahrscheinlichkeit p₁=1 keine zwei Personen mit dem gleichen Geburtstag.
	Eine Gruppe mit zwei Personen enthält mit Wahrscheinlichkeit p₂=p₁*(364/365)=364/365 keine zwei Personen mit dem gleichen Geburtstag, da die zweite Person an allen außer einem Tag Geburtstag haben kann.
	Eine Gruppe mit drei Personen enthält mit Wahrscheinlichkeit p₃=p₂*(363/365) keine zwei Personen mit dem gleichen Geburtstag, da die dritte Person an allen außer zwei Tagen Geburtstag haben kann.
	Eine Gruppe mit N Personen enthält mit Wahrscheinlichkeit p_N=(365/365)(364/365)...*(366-N/365) keine zwei Personen mit dem gleichen Geburtstag.

Für N=22 ist p₂₂=0,52430469, danach ist p₂₃=0,49270277, also 1-p₂₃=0,50729723. Daher beträgt bei einer Gruppe von 23 Personen die Wahrscheinlichkeit, dass mindestens zwei Personen am gleichen Tag Geburtstag haben, über 50 %.

Mit den obigen Bedingungen ergibt sich die Wahrscheinlichkeit, dass keine von N Personen an einem bestimmten Tag Geburtstag hat, offenbar zu q_N=(364/365)^N. Für N=252 gilt: 1-q²⁵²=1-(364/365)²⁵²=0,4991, 1-q²⁵³=1-(364/365)²⁵³=0,5005. Also müssen mindestens 253 Personen anwesend sein, damit mit 50 % Wahrscheinlichkeit mindestens eine an einem bestimmten Tag Geburtstag hat.

Soll zu einem gegebenen Hashwert ein anderer Text mit gleichem Hashwert gefunden werden, so ist der Aufwand proportional zur Länge des Hashwerts. Sollen jedoch nur zwei gleiche Hashwerte gefunden werden, so ist der Aufwand in der Regel nur ca. die Quadratwurzel aus der ersten Anzahl.

Der Geburtstagsangriff arbeitet jetzt folgendermaßen: Um ein gefälschtes Dokument zu signieren, lassen sich zwei Dokumente D und F erzeugen, von denen eines einen harmlosen, das andere einen entsprechend veränderten Text enthält. Beide Dokumente werden durch unwesentliche Änderungen (Leerzeichen, Backspaces, Tabs usw.) variiert, und deren Hashwerte verglichen. Sobald zwei Dokumente mit gleichen Fingerabdrücken gefunden werden, kann man das eine Dokument vorlegen, den Hashwert signieren lassen und später das andere vorlegen und auf dessen Erfüllung pochen.

Natürlich kann der Geschäftspartner gleichermaßen das erste Dokument vorlegen und argumentieren, dass es wesentlich schwieriger ist, zu einem gegebenen Hashwert ein passendes Dokument zu finden als zwei Dokumente mit gleichem Hashwert vorzulegen, und vermutlich würde ein Gericht ihm auch eher glauben. Dennoch stellt dieser Angriff einen Schwachpunkt des Hashverfahrens dar. Man sollte auf jeden Fall bei der Ermittlung eines Hashwerts darauf achten, dass die Anzahl der Stellen mindestens doppelt so groß ist wie eigentlich aus rechentechnischen Gründen notwendig. Außerdem ist es sinnvoll, den Text vor dem Hashen von redundanten Zeichen zu befreien, insbesondere nur ASCII-Texte zu verwenden, keine Leerzeichen als die notwendigen, keine Backspaces, Tabs usw. zu benutzen. Dieses wird in den Standards auch entsprechend gefordert. Darüber hinaus sollte der Text zunächst von beiden Parteien redigiert werden können, ehe er gehasht wird.