Einfuhrung

2.1 Einführung

Kryptografische Hash-Funktionen bilden das Rückgrat von Kryptoverfahren und -algorithmen [MvV92]. Wie die aus der Informatik bekannten Hash-Funktionen auch, bilden sie eine große Eingangsmenge ${x}$ eindeutig (deterministisch) auf eine viel kleinere Ausgangsmenge $y= H (x)$ ab. Sie haben jedoch folgende ergänzende Eigenschaften, welche deren algorithmische Komplexität mit dem jeweiligen Stand der Technik in Verbindung bringen:

Es ist praktisch unmöglich zwei Eingangswerte $′ x⁄= x$ zu finden (wahlfrei), die denselben Hashwert $y$ besitzen (Kollisionsfreiheit).
Der Algorithmus ist eine Einweg-Funktion, d. h. für einen gegebenen Hash-Wert $y$ kann man praktisch keinen zugehörigen Wert $x= H −1(y)$ berechnen (1. Urbild-Festigkeit).¹⁴
Es ist praktisch unmöglich zu einem vorgegebenen Eingangswert $x$ einen weiteren Wert $′ x ⁄= x$ zu finden, der denselben Hash-Wert $y$ erzeugt (2. Urbild-Festigkeit).

Insbesondere ältere Hash-Funktionen, wie z. B. der MD5 können dies heute nicht mehr gewährleisten, aber auch der SHA-1 gilt seit 2005 als „geknackt”. Alternativen wie SHA-256 oder SHA-512 (auch kurz SHA-2 genannt) stehen zwar zur Verfügung, werden aber noch nicht überall konsequent genutzt.¹⁵

Wirkprinzip Die Berechnung des Hash-Wertes $y$ erfolgt üblicherweise durch Zerlegung des Eingangs-Vektors $x$ in $k$ Blöcke fester Breite, die dann iterativ mit Hilfe einer nichtlinearen Kompressionsfunktion $C$ verarbeitet werden. Abbildung 2.1 zeigt die unter dem Namen Merkle/Damgård-Konstruktion bekannte Struktur [Mer90, Dam90].¹⁶ Für jeden Zwischenwert gilt ausgehend von $y0 = IV$ die Gleichung $yi = C(yi−1,xi)$ und so für das Ergebnis: $y= H (x) = yk$ .

Abbildung 2.1:

Merkle/Damgård-Konstruktion