Welche Kombination gibt für eine ideale Hashfunktion mit 256-Bit-Ausgabe die ungefähre Zahl der Berechnungen bei einem Brute-Force-Angriff in zwei Fällen richtig an: eine Eingabe finden, die einen vorgegebenen Hashwert ergibt (Urbildangriff), und beliebige zwei verschiedene Eingaben finden, die denselben Hashwert ergeben (Kollisionsangriff)?

Antwort: A. Urbildangriff etwa 2^256, Kollisionsangriff etwa 2^128

Eine ideale Hashfunktion mit n-Bit-Ausgabe hat 2^n mögliche Hashwerte, und jede ausprobierte Eingabe trifft einen vorgegebenen Hashwert mit der Wahrscheinlichkeit 1/2^n. Ein Urbildangriff braucht daher etwa 2^n Berechnungen, bei n = 256 also etwa 2^256. Beim Kollisionsangriff dagegen dürfen zwei beliebige Eingaben übereinstimmen; mit k ausprobierten Eingaben gibt es etwa k^2/2 vergleichbare Paare. Nähert sich k^2/2 dem Wert 2^n, also bei k in der Größenordnung von 2^(n/2), wird eine Kollision wahrscheinlich; bei n = 256 sind das etwa 2^128. Das ist derselbe Gedanke wie beim Geburtstagsparadoxon, nach dem in einer Gruppe von 23 Personen die Wahrscheinlichkeit, dass zwei am selben Tag Geburtstag haben, über 50 % liegt; man spricht daher vom Geburtstagsangriff. Folglich wird die Kollisionsresistenz einer Hashfunktion mit der halben Ausgabelänge angesetzt, und für eine Sicherheit von 128 Bit ist eine 256-Bit-Ausgabe erforderlich.