Grundlagen

Hashfunktion

Eine Hashfunktion (auch Streuwertfunktion) ist eine Abbildung, die eine große Eingabemenge (die Schlüssel) auf eine kleinere Zielmenge (die Hashwerte) abbildet.
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.

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.
Eine gute Hashfunktion zeichnet sich dadurch aus, dass sie für die Eingaben, für die sie entworfen wurde, möglichst wenige Kollisionen erzeugt.

Hashfunktionen haben verschiedene Anwendungsfelder. Dabei lassen sich drei große Gebiete unterteilen:

Datenbanken
- In der Datenspeicherung kann ein Hashwert verwendet werden, um die Speicherstelle der angefragten Daten zu berechnen (z. B. Hashtabelle).
Prüfsummen
- Bei Prüfsummen verwendet man Hashwerte, um Übertragungsfehler zu erkennen.
Kryptologie
- In der Kryptologie werden spezielle kryptologische Hashfunktionen verwendet, bei denen zusätzlich gefordert wird, dass es praktisch unmöglich ist, Kollisionen absichtlich zu finden.

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.

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:

{\begin{aligned}H\left(0\right)&=IV\\H\left(i\right)&=f\left(M\left(i\right),H\left(i-1\right)\right),\qquad i=1,2,\dotsc ,t\\h\left(M\right)&=H(t)\end{aligned}}