Geburtstagsangriff
Kollisionen tauchen nach der Wurzel aus der Anzahl der Möglichkeiten auf, nicht nach der Anzahl selbst — deshalb ist ein 256-Bit-Hash nur 128 Bit wert.
Der Name stammt vom Geburtstagsparadoxon: In einem Raum mit 23 Personen liegt die Wahrscheinlichkeit, dass zwei am selben Tag Geburtstag haben, bei über 50 Prozent — obwohl das Jahr 365 Tage hat. Dieselbe Mathematik gilt für Hashwerte. Für einen n-Bit-Hash reichen bereits rund 2^(n/2) Versuche, bis zwei beliebige Eingaben kollidieren.
Deshalb entspricht die Kollisionsresistenz immer der halben Hash-Länge: SHA-256 bietet 128 Bit Sicherheit gegen Kollisionen, nicht 256. Der Unterschied zum Finden einer Kollision mit einem bestimmten Wert ist entscheidend — dafür braucht es weiterhin 2^n. Der Angriff gab SHA-1 2017 den Rest, als Google und CWI mit rund 2^63 Operationen zwei PDF-Dateien mit identischem Hash erzeugten.