Fachkonzept - Kryptologische Hash-Funktion
Hash-Funktion
Eine Hash-Funktion ist eine Funktion, die Zeichenketten neue Zeichenketten einer fest vorgegebenen Länge zuordnet.
Man nennt Funktionswerte von Hash-Funktionen auch Hash-Werte.
Beispiel: Die Hash-Funktion SHA-256 ordnet jeder Zeichenkette (jedem Text) ein
Bitmuster bestehend aus 256 Bits (hier dargestellt als Hexadezimalzahl) als Hash-Wert zu.
Hash-Funktionen reduzieren in der Regel eine größere Datenmenge (wie einen Text) auf einen kleineren Datensatz mit vorgegebener Größe (wie ein 256-Bit-Muster).
Hash-Funktion als Einwegfunktion
Die in der Kryptologie benutzten Hash-Funktionen sind in der Regel Einwegfunktionen.
Bei einer Einwegfunktion ist es praktisch unmöglich, aus einem möglichen Zielwert einen Ausgangswert so zu bestimmen, dass der Zielwert Funktionswert zum Ausgangswert ist.
In mathematischer Kurzform kann man das so beschreiben: Eine Funktion f ist eine Einwegfunktion, wenn es praktisch unmöglich ist, zu gegebenem y aus der Zielmenge ein x aus der Definitionsmenge von f zu finden, so dass f(x) = y gilt.
Beispiel: Mit unseren Mitteln ist es praktisch unmöglich, z.B. einen Text zum SHA-256-Hash-Wert "07 A4 73 DB 10 9F 05 33 32 F4 68 44 B2 06 40 02 0F 58 BB AF 48 AA CB 1C 96 AE 37 1D 5B 0B 67 46" zu rekonstruieren. Wir können SHA-256 daher als Einwegfunktionen ansehen.
Kollisionsresistenz bei Hash-Funktionen
Zur Erzeugung sicherer digitaler Signaturen benötigt man Hash-Funktionen, die es Angreifern sehr schwer machen, Texte zu vorgegebenen Hash-Werten zu erzeugen. Hierzu fordert man, dass Hash-Funktionen kollisionsresistent sind.
Schwache Kollisionsresistenz: Eine Hash-Funktion ist schwach kollisionsresistent, wenn es praktisch unmöglich ist, zu einem gegebenen Ausgangswert x einen weiteren, davon verschiedenen Ausgangswert x' zu finden, die denselben Hash-Wert y haben.
Hier betrachtet man also die Kollisionsresistenz für ein festes, gegebenes x. Eine Funktion kann also schwach kollisionsresistent sein, obwohl es ein offensichtliches Paar (oder auch mehrere) mit dem gleichen Hash-Wert gibt, das man allerdings ausschließt.
Eine etwas stärkere Anforderung erhält man wir folgt:
Starke Kollisionsresistenz: Eine Hash-Funktion ist stark kollisionsresistent, wenn es praktisch unmöglich ist, zwei beliebige verschiedene Ausgangswerte x und x' zu finden, die denselben Hash-Wert y haben.
Hier sind die Ausgangswerte frei wählbar. Es darf also im Allgemeinen nicht möglich sein, irgendein Paar x und x' mit den gleichen Hash-Werten zu finden.
Beachte: Wenn man eine Hash-Funktion wie SHA-256 benutzt, um beliebigen Texten einen Hash-Wert zuzuordnen, so muss es Kollisionen (d.h. Texte mit gleichem Hash-Wert) geben, da es unendlich viele Texte, aber nur eine endliche Menge von Hash-Werten gibt. Kollisionsresistenz bedeutet: Obwohl es (sogar unendlich) viele Kollisionen gibt, ist es uns praktisch unmöglich, solche Kollisionen zu erzeugen.
Angriffsszenarien
Bei einem Urbildangriff (engl. preimage attack) verfolgt der Angreifer das Ziel, zu einem gegebenen Hashwert einer unbekannten Nachricht (Erster Urbildangriff) oder zu einer gegebenen Nachricht selbst (Zweiter Urbildangriff) eine weitere Nachricht zu konstruieren, die denselben Hashwert besitzt.
Beispiel: Angenommen, ein Angreifer fängt ein signiertes Dokument ab. Er ist dann im Besitz des Dokumenttextes (z.B. "Hiermit bestelle ich 2 Konzertkarten zu je 40 €.") sowie des zugehörigen Hashwerts. Der Angreifer versucht jetzt, aus der Nachricht oder dem Hashwert eine veränderte Nachricht mit demselben Hashwert zu erzeugen. Eine zusätzliche Schwierigkeit besteht darin, dass die neue Nachricht auch noch Sinn machen soll.
Eine andere Form von Angriff betrifft die Erzeugung von Kollisionen:
Bei einem Kollisionsangriff (engl. collision attack) verfolgt der Angreifer das Ziel, zwei verschiedene Dokumente zu konstruieren, die beide denselben Hashwert besitzen.
Beachte, dass es sich hier um unterschiedliche Angriffsszenarien handelt. Das zeigt sich auch in der Praxis. Während Kollisionsangriffe bei SHA-1 möglich sind, sind Urbildangriffe bei SHA-2 derzeit noch nicht möglich.
