Hashfunktion

Grundidee und Definition

Eine Hashfunktion oder Streuwertfunktion bildet eine große Menge möglicher Eingaben, die Schlüssel, auf eine kleinere Menge von Hashwerten ab. Die Eingaben können unterschiedlich lang sein, während Hashwerte meist eine feste Länge haben. Da es gewöhnlich mehr mögliche Schlüssel als Hashwerte gibt, ist eine Hashfunktion im Allgemeinen nicht injektiv: Verschiedene Eingaben können denselben Wert erhalten.

Formal heißt eine Abbildung h: K → S Hashfunktion, wenn |K| ≥ |S| gilt. K ist die Schlüsselmenge, S die Menge möglicher Hashwerte. Typisch ist S ⊆ {0, …, m−1}; diese Menge heißt Adressraum. Eine Hashtabelle besitzt dann die Größe |S|.

Praktisch wird meist nur eine Teilmenge K′ ⊆ K verwendet. Die tatsächlich belegten Hashwerte sind S′ := {h(k) | k ∈ K′}. Der Belegungsfaktor lautet β = |S′| / |S|. Eine Kollision liegt vor, wenn k ≠ k′ und h(k) = h(k′) gilt. Kollisionen sind nach dem Schubfachprinzip grundsätzlich unvermeidlich, wenn die Hashwertmenge kleiner ist als die Eingabemenge. Eine injektive, also kollisionsfreie Hashfunktion heißt perfekt; für bekannte und beschränkte Eingabemengen können solche Funktionen gefunden werden.

Anforderungen an gute Hashfunktionen

Eine gute Hashfunktion soll für den vorgesehenen Eingabebereich möglichst wenige Kollisionen erzeugen. Dazu sollen die Hashwerte möglichst gleichverteilt sein. Außerdem soll die Funktion surjektiv sein: Kein Hashwert im festgelegten Wertebereich soll unerreichbar bleiben.

Wichtig ist auch die Effizienz. Die Berechnung soll schnell sein, wenig Speicher benötigen, einen deutlich kleineren Hashwert als den Schlüssel erzeugen und die Eingabedaten möglichst nur einmal lesen müssen. Soll eine Datenbank einen sortierten Zugriff über die Hashtabelle erlauben, ist zusätzlich Ordnungserhaltung wichtig.

Kryptographische Hashfunktionen benötigen weitere Eigenschaften: Beim Lawineneffekt oder Chaos führt schon eine kleine Änderung der Eingabe zu stark veränderten Hashwerten; idealerweise ändert das Umkippen eines Eingabebits durchschnittlich die Hälfte aller Bits des Hashwerts. Konfusion bedeutet, dass der Hashwert keine Rückschlüsse auf die Eingabe zulässt. Unumkehrbarkeit bedeutet, dass es kein praktisches Verfahren geben soll, aus einem Hashwert die Eingabe zu bestimmen.

Anwendungen in Speicherung und Datenbanken

Hashwerte können komplexen Objekten Speicheradressen zuordnen, etwa für Hashtabellen. Sie dienen außerdem als kurze Kennzeichnung größerer Datenmengen und werden deshalb auch Fingerprint genannt: Der Wert soll einen Inhalt nahezu eindeutig und mit wenig Speicherplatz identifizieren. In der Kryptographie soll er dabei möglichst nichts über den Inhalt verraten.

Bei einer Kartei wäre der erste Buchstabe eines Nachnamens eine einfache Hashfunktion. Sie verringert den Suchbereich auf einen von 26 Teilen, verteilt Namen aber ungleichmäßig: Beispielsweise können viele Akten im Ordner S liegen, während Q leer bleibt. Für Computerprogramme sind daher Verfahren wichtig, die Kollisionen besser vermeiden.

Datenbankmanagementsysteme verwenden Hashfunktionen in Hashtabellen für Datenbankindizes. Außerdem können Datensätze fragmentiert werden: Die Hashfunktion wird auf den Primärschlüssel angewandt, und ihr Ergebnis verweist auf den Speicherort. Auch Kompressionsalgorithmen wie LZW verwenden Hashfunktionen für vergleichsweise kleine Datenmengen.

In einer Blockchain wie Bitcoin oder Ethereum verknüpfen kryptographische Hashfunktionen Transaktionen und Blöcke. Jeder Block enthält den Hash des vorherigen Blocks. Schon eine minimale Änderung würde den Hash verändern und die Verknüpfung ungültig machen; nachträgliche Manipulationen gespeicherter Daten fallen dadurch auf.

Prüfsummen und kryptographische Nutzung

Prüfsummen erhöhen die Plausibilität, Veränderungen übertragener Daten zu erkennen. Stimmt die aus empfangenen Daten berechnete Prüfsumme nicht mit der übertragenen Prüfsumme der Originaldaten überein, ist sicher ein Fehler festgestellt. Die Verfälschung kann dann allerdings auch nur die Prüfsumme betreffen. Unerkannt bleibt nur eine Datenverfälschung, die dieselbe Prüfsumme erzeugt; mehrere passend erzeugte Prüfsummen können die Kollisionswahrscheinlichkeit stark senken.

Die einstellige Quersumme ist ein einfaches Beispiel: 25 wird auf 2 + 5 = 7 abgebildet. Als Prüfsumme ist sie ungeeignet, um Ziffernvertauschungen zuverlässig zu erkennen, weil auch 52 die Quersumme 5 + 2 = 7 besitzt. ISBN-Prüfsummen und CRC-32 eignen sich besser zur Erkennung solcher Übertragungsfehler.

Bei gezielten Manipulationen braucht man kryptographische Hashfunktionen, weil Kollisionen nur mit sehr hohem Rechenaufwand gefunden werden können. Sie sind kollisionsresistente Einwegfunktionen und sichern etwa die Datenintegrität, digitale Signaturen und Schlüsselableitung. Bei der Schlüsselableitung entsteht aus einem Passwort ein Hashwert zur sicheren, unumkehrbaren Passwortspeicherung oder als Schlüssel für ein Verschlüsselungsverfahren. Für Session-IDs in Internet-Anwendungen können wechselnde Zustandswerte wie Zeit und IP-Adresse in einen Hashwert einfließen.

Entwurf und Rechenmethoden

Beim Entwurf helfen Informationen über die erwartete Verteilung der Schlüssel. Idealerweise hängt der Hashwert von jedem Bit des Schlüssels ab. Schlüssel, die sich nur in einem Bit oder einer Bitfolge unterscheiden, sollen verschiedene Werte erhalten; das gilt auch für Permutationen wie 256 und 625. Einen bloßen Teil des Schlüssels zu übernehmen, ist deshalb ungeeignet.

Beim Hashing durch Division gilt h(key) = key mod tablesize. Die Methode benötigt nur eine Division und ist schnell. Die Tabellengröße sollte jedoch keine Potenz einer Zahl sein: Bei tablesize = rᵖ hängt der Hashwert stets von den letzten Bits des Schlüssels ab. Gute Ergebnisse liefert oft eine Primzahl, die nicht zu nahe an einer Zweierpotenz liegt.

Beim Hashing durch Multiplikation wird ein Schlüssel mit einer reellen Konstanten c mit 0 < c < 1 multipliziert. Verwendet werden die Nachkommastellen von key · c: h(key) = floor(tablesize · (key · c mod 1)). Die Tabellengröße ist hier weniger kritisch und ist typischerweise eine Zweierpotenz, um die Implementierung zu beschleunigen. Die Methode funktioniert mit jeder reellen Zahl c, aber einige Werte sind besser geeignet als andere.

Weitere Arten und Beispiele

Zu weiteren allgemeinen Hashverfahren gehören Brent-Hashing, Doppel-Hashing, Mittquadratmethode, Zerlegungsmethode und Ziffernanalyse. Gitterbasierte Hashfunktionen sind Ajtai, Micciancio, Peikert-Rosen, die Schnelle Fourier-Transformation (FFT-Hashfunktion) und LASH.

Als Prüfsummen werden unter anderem Fletcher’s Checksum, Adler-32, CRC (Zyklische Redundanzprüfung), Parität und Quersumme genannt. Bekannte kryptographische Hashfunktionen sind MD2, MD4, MD5, Secure Hash Algorithm (SHA), RIPEMD-160, Tiger, HAVAL und Whirlpool. Passwort-Hashfunktionen sind LM-Hash, PBKDF2, Bcrypt, Scrypt und Argon2.

Hashwerte werden in P2P-Anwendungen zum Suchen, Identifizieren und Prüfen übertragener Dateifragmente genutzt. Große Dateien lassen sich so in kleinen Segmenten austauschen. Gestufte Hashfunktionen berechnen zunächst Hashwerte kleinerer Dateiteile und daraus einen Gesamtwert; in G2 und Direct Connect werden beispielsweise Tiger-Tree-Hash-Funktionen verwendet.