Birthday Bound
Die Geburtstagsgrenze ist die durch das Geburtstagsparadoxon festgelegte Untergrenze der Angriffskomplexität: Eine Kollision in einer Menge von N Elementen zu finden erfordert etwa sqrt(N) Stichproben.
Zweck
Setzt die Sicherheitsobergrenze für Hashfunktionen und Blockchiffren-Modi: Ein n-Bit-Hash bietet nur 2^(n/2) Kollisionswiderstand, und CBC/CTR-Modi eines n-Bit-Blocks wiederholen sich nach 2^(n/2) Blöcken.
Mechanismus
Nach dem Geburtstagsparadoxon wiederholt sich zufälliges Ziehen aus einer N-Elemente-Menge mit hoher Wahrscheinlichkeit nach etwa sqrt(N) Zügen. Daher erfordert eine Kollision eines n-Bit-Hash 2^(n/2) Operationen, und SHA-256 bietet 128 Bit Kollisionswiderstand.
Anwendungsfälle
- Bewertung der Sicherheitsstärke von Hashfunktionen
- Blockzahl-Obergrenzen für Blockchiffren-Modi
- Wahl der Signatur-Hashlängen