Hashes
Grundlagen
Eine Hashfunktion (auch Streuwertfunktion) ist eine Abbildung, die eine große Eingabemenge (die Schlüssel) auf eine kleinere Zielmenge (die Hashwerte) abbildet. Der Name „Hashfunktion“ stammt vom englischen Verb to hash, das sich als „zerhacken“ übersetzen lässt. Der deutsche Name lautet Streuwertfunktion. Beide Namen deuten darauf hin, dass diese Funktionen normalerweise darauf angelegt sind, die Daten zu „verstreuen“ und zu „zerhacken“. Speziell in der Informatik verwendet man auch den Begriff Hash-Algorithmus, da Hashfunktionen oftmals in Form eines Algorithmus statt einer mathematischen Funktion spezifiziert werden. Eine „gute“ Hashfunktion liefert dabei für die (erwarteten) Eingabedaten Werte so, dass zwei unterschiedliche Eingaben auch zu unterschiedlichen Ausgabewerten führen. Ein Hashwert wird deshalb auch als englisch Fingerprint bezeichnet, da er eine nahezu eindeutige Kennzeichnung einer größeren Datenmenge darstellt, so wie ein Fingerabdruck einen Menschen nahezu eindeutig identifiziert.
Eine sog. Kollision tritt dann auf, wenn unterschiedlichen Eingabedaten derselbe Hashwert zugeordnet wird. Da die Menge der möglichen Hashwerte meist kleiner ist als die der möglichen Eingaben, sind solche Kollisionen dann prinzipiell unvermeidlich, weshalb es Verfahren zur Kollisionserkennung geben muss. Eine gute Hashfunktion zeichnet sich dadurch aus, dass sie für die Eingaben, für die sie entworfen wurde, möglichst wenige Kollisionen erzeugt.
In der Datenspeicherung kann ein Hashwert verwendet werden, um die Speicherstelle der angefragten Daten zu berechnen (z. B. Hashtabelle). Bei Prüfsummen verwendet man Hashwerte, um Übertragungsfehler zu erkennen. In der Kryptologie werden spezielle kryptologische Hashfunktionen verwendet, bei denen zusätzlich gefordert wird, dass es praktisch unmöglich ist, Kollisionen absichtlich zu finden.
Anwendungen
Hashfunktionen haben verschiedene Anwendungsfelder. Dabei lassen sich drei große Gebiete unterteilen:
- Datenbanken
- Prüfsummen
- Kryptologie
Kryptologische Hashfunktionen
Eine kryptologische Hashfunktion oder kryptographische Hashfunktion ist eine spezielle Form der Hashfunktion, welche kollisionsresistent sein sollte und nach Definition immer eine Einwegfunktion ist. Kryptologische Hashfunktionen werden in schlüssellose und schlüsselabhängige eingeteilt. Schlüssellose Hashfunktionen werden ferner unterteilt in Einweg-Hashfunktionen (englisch: One-Way Hash Function oder OWHF) und kollisionsresistente Hashfunktionen (englisch: Collision Resistant Hash Functions, CRHFs). Schlüsselabhängige Hashfunktionen werden auch Message Authentication Codes (MAC) genannt. Zu diesen zählen Konstrukte wie HMAC, CBC-MAC oder UMAC.
Merkle-Damgård-Verfahren
In der Merkle-Damgård-Konstruktion wird eine Kompressionsfunktion iteriert. Eine Kompressionsfunktion nimmt als Eingabe zwei Bitfolgen der Längen n und m und gibt eine Bitfolge der Länge n aus. Zusätzlich ist sie eine Einwegfunktion, es sollte also schwer sein, zu einer gegebenen Ausgabe passende Eingabewerte zu finden. Oft wird eine Blockchiffre als Kompressionsfunktion benutzt, die Eingaben werden dann als Nachricht und Schlüssel benutzt.
Bei der Merkle-Damgård-Konstruktion wird die eingegebene Nachricht M zuerst in Blöcke fester Länge geteilt und mit zusätzlichen Bits aufgefüllt, so dass die Eingabelänge ein ganzzahliges Vielfaches der Blocklänge beträgt. Die Kompressionsfunktion hat als Input einen Nachrichtenblock und den Output der vorherigen Nachrichtenblöcke. Der Hashwert der gesamten Nachricht ist der Hashwert des letzten Blocks:
- H(0) = IV
- H(i) = f(M(i),H(i-1)), i=1,2,...,t
- h(M) = H(t)
- IV bezeichnet einen Startwert (initial value).