Birthday Attack
Der Geburtstagsangriff nutzt das Geburtstagsparadoxon: Nach etwa 2^(n/2) Hash-Berechnungen besteht eine 50-%-Chance, eine Kollision in einem n-Bit-Hash zu finden — das legt die erforderliche Ausgabelänge fest.
Zweck
Legt die Untergrenze der Hash-Ausgabelänge fest, damit die Kollisionssuche unpraktikabel bleibt.
Mechanismus
Geburtstagsparadoxon: Unter 23 Personen beträgt die Wahrscheinlichkeit 50 %, dass zwei am selben Tag Geburtstag haben. Bei einem Hash mit n-Bit-Ausgabe ergeben etwa 1.177×√(2^n) = 1.177×2^(n/2) zufällige Eingaben eine 50-%-Kollisionswahrscheinlichkeit. Ein 128-Bit-Hash ist daher schon mit nur 2^64 Versuchen unsicher.
Anwendungsfälle
- Wahl der Hash-Ausgabelänge
- Sicherheitsniveau digitaler Signaturen
- Bewertung der Zertifikatslebensdauer
- Kryptographie-Vermittlung
Beispiele
- Eingabe
128-bit hashOutputCollision found in 2^64 trialsInsecure
Häufige Fehler
- Assuming an n-bit hash needs 2^n trials to collide
- Collisions take only 2^(n/2); use outputs of at least 256 bits
Verwandte Begriffe
Collision Resistance
Kollisionsresistenz ist die Eigenschaft einer Hashfunktion, wonach es unpraktikabel ist, zwei verschiedene Eingaben mit gleichem Hashwert zu finden. Der Geburtstagsangriff bestimmt die erforderliche Ausgabelänge. GLOSSAR
SHA-256
SHA-256 ist das 256-Bit-Ausgabemitglied der SHA-2-Familie, weit verbreitet in TLS, Blockchains und Kryptoanwendungen, ohne bekannte praktische Angriffe. GLOSSAR
MD5
MD5 ist eine 128-Bit-kryptografische Hashfunktion von Ronald Rivest; durch Kollisionsangriffe als unsicher erwiesen, wird sie heute nur für nicht sicherheitsrelevante Zwecke wie Prüfsummen verwendet. GLOSSAR