Geburtstagsangriff
 | Geburtstagsangriff
 | statistisches Phänomen
 | wenigstens zwei Personen |
| mit fünfzigprozentiger
Wahrscheinlichkeit |
| am gleichen Tag Geburtstag |
|
|
Geburtstagsparadoxon
beweisen
| alle Personen mit gleicher Wahrscheinlichkeit für jeden
Tag des Jahres (zu 365 Tagen) Geburtstag haben |
| Geburtstage
unabhängig sind (also keine Zwillinge usw.). |
| 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 p1=1
keine zwei Personen mit dem gleichen Geburtstag. |
| Eine Gruppe mit zwei Personen enthält mit Wahrscheinlichkeit p2=p1*(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 p3=p2*(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 pN=(365/365)*(364/365)*...*(366-N/365)
keine zwei Personen mit dem gleichen Geburtstag. |
|
Für N=22 ist p22=0,52430469,
danach ist p23=0,49270277,
also 1-p23=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
|
Wahrscheinlichkeit, keine von N Personen an bestimmtem
Tag Geburtstag
| qN=(364/365)N. |
|
| N=252 gilt:
| 1-q252=1-(364/365)252=0,4991, |
|
1-q253=1-(364/365)253=0,5005. |
|
| von mindestens 253 Personen mit 50 %
Wahrscheinlichkeit mindestens eine an einem bestimmten Tag Geburtstag |
|
|
zu gegebenem Hashwert anderen Text mit gleichem
Hashwert finden
|
Aufwand proportional zur Länge des
Hashwerts |
|
|
nur zwei gleiche Hashwerte finden
|
Aufwand in der Regel nur ca. Quadratwurzel aus der Anzahl. |
|
|
Geburtstagsangriff arbeitet jetzt folgendermaßen:
|
Ziel: gefälschtes Dokument signieren |
|
zwei Dokumente D und F
erzeugen,
|
eines einen harmlosen, |
|
anders einen entsprechend
veränderten Text |
|
|
Beide Dokumente durch unwesentliche
Änderungen variiert
|
Leerzeichen, |
|
Backspaces, |
|
Tabs |
|
usw. |
|
|
Hashwerte verglichen |
|
zwei Dokumente mit gleichen Fingerabdrücken gefunden
|
das eine Dokument vorlegen, Hashwert signieren lassen |
|
später
das andere vorlegen, auf Erfüllung pochen |
|
|
|
Geschäftspartner kann gleichermaßen
|
erstes
Dokument vorlegen |
|
argumentieren, wesentlich schwieriger, zu
gegebenem Hashwert passendes Dokument zu finden als zwei Dokumente mit
gleichem Hashwert vorzulegen |
|
vermutlich würde ein Gericht ihm auch eher
glauben |
|
Dennoch
|
Schwachpunkt des Hashverfahrens
durch diesen Angriff |
|
auf jeden Fall bei Ermittlung eines Hashwerts darauf achten,
|
Anzahl der Stellen des Hashwerts
mindestens doppelt so groß ist wie eigentlich aus
rechentechnischen Gründen notwendig |
|
Text vor Hashen von redundanten Zeichen befreien, |
|
nur ASCII-Texte zu
verwenden, |
|
keine Leerzeichen als die notwendigen, |
|
keine Backspaces, |
|
Tabs |
|
usw. |
|
wird in Standards auch entsprechend
gefordert |
|
Text zunächst von beiden Parteien
redigieren lasse |
|
|
|
|
