Hashfunktion

Eine Hash-Funktion (von en. "to hash": zerhacken, dt. Bezeichnung: Streuwertfunktion) ist eine nicht umkehrbare Funktion (ein Algorithmus), die eine umfangreiche Quellmenge (i.d.R. Texte) auf eine wesentlich kleinere Zielmenge (Hash-Werte, i.d.R. natürliche Zahlen und Buchstaben) abbildet.

Anschaulich und unmathematisch wird das im ersten Abschnitt erklärt.

Der Hashwert kann zum Auffinden von Daten in einer Datenbank oder zum digitalen Signieren eines Dokumentes verwendet werden. Hash-Funktionen können auch zur Einweg-Verschlüsselung verwendet werden. (Siehe auch: Kryptologie)

Prüfsummen erzeugen ebenfalls eine Abbildung auf eine reduzierte Datenmenge, hier mit dem Ziel, die Datenintegrität bei Störeinflüssen sicherzustellen.

Anschauliche Erklärung

Bei einer Hash-Funktion geht es allgemein darum, eine lange Eingabe (zum Beispiel einen Text) in eine kurze Ausgabe (den Hash-Wert des Textes) zu verwandeln.

Das ist etwa dann sinnvoll, wenn man zwei große ähnliche Dateien vergleichen will: Anstatt die 25 Seiten eines Textes durchzusehen, ob auch wirklich jeder Buchstabe gleich ist, schauen wir auf die kurzen Hash-Werte der beiden Dokumente und sehen sofort, ob diese beiden gleich oder verschieden sind.

Das kann man praktisch anwenden, wenn wir eine Datei aus dem Internet herunterladen und der Autor den Hash-Wert angegeben hat: Um zu prüfen, ob es Übertragungsfehler gegeben hat, müssen wir die Datei nicht etwa ein zweites Mal komplett herunterladen, sondern nur den Hash-Wert bilden und diesen mit der Angabe des Autors vergleichen.

Ein Beispiel für eine einfache Hash-Funktion mit Zahlen wäre, von einer Zahl nur die letzte Ziffer zu nehmen. Alle Eingaben würden so auf nur eine Ziffer verkürzt: 97 würde zu 7, 153 würde zu 3, selbst eine große Zahl wie 238.674.991 würde verkleinert zu 1.

Weil bei einer Hash-Funktion die Ausgabe meist kleiner als die Eingabe ist, können mehrere verschiedene Eingaben die gleiche Ausgabe erzeugen. Das leuchtet bei unserem Beispiel unmittelbar ein: 11 und 21 liefern beide 1. Das ist die Schwachstelle von Hash-Funktionen und wird als Kollision bezeichnet. Durch die Wahl einer geeigneten Funktion kann die Wahrscheinlichkeit solcher Kollisionen deutlich vermindert werden und man gewinnt für die praktische Anwendung eine hinreichende Sicherheit.

Definition einer Hash-Funktion

Seien

k:    Schlüsselwert (key)
h(k): Hashfunktion
w:    Menge aller möglichen Schlüssel
s:    Menge der zu speichernden Schlüssel
β:    Belegungsfaktor
m:    Größe der Hash-Tabelle

so ist:

$\left\{0,\cdots ,m-1\right\}$

die Menge der Hash-Adressen (Adressraum),

$h:k\rightarrow \left\{0,\cdots ,m-1\right\}$

die Hash-Funktion und

$\beta ={\frac {\left|s\right|}{m}}$

der Belegungsfaktor.

Der Fall $k\not =k'\rightarrow h(k)=h(k')$ wird als Kollision bezeichnet. Eine injektive Hashfunktion heißt perfekt.

Kriterien für eine gute Hash-Funktion

Datenreduktion

Der Speicherbedarf des Hash-Wertes soll deutlich kleiner sein als der der Nachricht.

Zufälligkeit

Ähnliche Quellelemente sollen zu völlig verschiedenen Hash-Werten führen. Im Idealfall verändert das Umkippen eines Bits in der Eingabe durchschnittlich die Hälfte aller Bits im resultierenden Hash-Wert.

Eindeutigkeit

Die Funktion muss deterministisch von der Quellmenge auf die Zielmenge abbilden. Wiederholtes Berechnen des Hash-Wertes desselben Quellelements muss also dasselbe Ergebnis liefern.

Effizienz

Die Funktion muss schnell berechenbar sein, ohne großen Speicherverbrauch auskommen und sollte die Quelldaten möglichst nur einmal lesen müssen.

Zusätzliche Forderungen für kryptographisch sichere Hash-Funktionen:

Kollisionsfreiheit

Es darf nicht effizient möglich sein, zwei Quellelemente mit demselben Hash-Wert zu finden. Andererseits sind Kollisionen bei der Adressberechnung in Datenbanken nicht zu vermeiden, so dass eine entsprechende Behandlungs-Strategie verfügbar sein muss.

Unumkehrbarkeit

Zu der Funktion gibt es keine effizient berechenbare inverse Funktion, mit der es möglich wäre, für ein gegebenes Zielelement ein passendes Quellelement zu finden.

Behandlung von Kollisionen

Die einzelnen Zellen einer Hashtabelle lassen sich als Behälter vorstellen. Im allgemeinen ist die Anzahl der möglichen Schlüssel weitaus höher als die verfügbaren Behälter. Es kommt daher schnell zu Kollisionen, d.h. verschiedene Schlüssel werden auf denselben Behälter abgebildet. Das offene Hashing löst dieses Problem ganz prinzipiell, nimmt aber Einbußen bei den Zugriffszeiten in Kauf. Das geschlossene Hashing ist hingegen auf explizite Strategien zur Kollisionsbehandlung angewiesen.

Hashing mit Verkettung

Beim Hashing mit Verkettung ist die Hash-Tabelle so strukturiert, dass jeder Behälter eine dynamische Datenstruktur aufnehmen kann - beispielsweise auf eine Liste oder einen Baum. Jeder Schlüssel wird dann in dieser Datenstruktur eingetragen oder gesucht. So ist es problemlos möglich, mehrere Schlüssel in einem Behälter abzulegen, was allerdings zu mehr oder weniger verlängerten Zugriffszeiten führt. Die Effizienz des Zugriffs wird dabei davon bestimmt, wie schnell Datensätze in die gewählte Datenstruktur eingefügt und darin wiedergefunden werden können.

Offenes Hashing

Beim offenen Hashing (auch Hashing mit offener Adressierung genannt) kann jedem Behälter nur eine feste Anzahl von Schlüsseln zugewiesen werden. Häufig wählt man einfach einen einzigen möglichen Schlüssel pro Behälter. Im Kollisionsfall muss dann nach einem alternativen Behälter gesucht werden. Dabei geht man so vor, dass man für m Behälter eine ganze Folge von m Hash-Funktionen definiert. Führt die Anwendung der ersten Hash-Funktion, nennen wir sie $h_{0}$ , zu einer Kollision, so wendet man $h_{1}$ an. Führt diese ebenfalls zu einer Kollision (d.h. der entsprechende Behälter ist bereits belegt), so wendet man $h_{2}$ an, und so weiter bis $h_{m}-1$ . Das Verfahren arbeitet mit sogenannter offener Adressierung, da durch Kollisionen gleiche Schlüssel unterschiedliche Adressen zugewiesen bekommen können.

Lineares Sondieren

Die einfachste Möglichkeit zur Definition einer solchen Folge besteht darin, so lange den jeweils nächsten Behälter zu prüfen, bis man auf einen freien Behälter trifft. Die Definition der Folge von Hash-Funktionen sieht dann so aus:

$h_{i}(x)=(h(x)+i){\bmod {m}}$

Die Anwendung des Modulo hat mit der begrenzten Zahl von Behältern zu tun: Wurde der letzte Behälter geprüft, so beginnt man wieder beim ersten Behälter. Das Problem dieser Methode ist, dass sich so schnell Ketten oder Cluster bilden und die Zugriffszeiten im Bereich solcher Ketten schnell ansteigen. Das lineare Sondieren ist daher wenig effizient.

Quadratisches Sondieren

Wie beim linearen Sondieren wird nach einem neuen freien Speicher gesucht, allerdings nicht sequenziell, sondern mit stetig quadratisch wachsender Schrittweite und in beide Richtungen. Verursacht h(k) eine Kollision, so werden z. B. h(k) + 1 , h(k) - 1 , h(k) + 4 , h(k) - 4 , h(k) + 9 usw. probiert. Den ständigen Wechsel des Vorzeichens bei dieser Kollisionsstrategie nennt man auch "alternierendes quadratisches Sondieren" oder "quadratisches Sondieren mit Verfeinerung". Wählt man die Anzahl der Behälter geschickt (nämlich m = 4·j+3, m als Primzahl), dann wird sichergestellt, dass alle Behälter irgendwann getroffen werden.

Doppel-Hashing

Beim Doppel-Hashing werden zwei unabhängige Hash-Funktionen h und h' angewandt. Diese heißen unabhängig, wenn die Wahrscheinlichkeit für eine sogenannte Doppelkollision, d.h. $h(x)=h(y)\land h'(x)=h'(y)$ gleich $1/m^{2}$ und damit minimal ist. Die Folge von Hash-Funktionen, die nun mittels h und h' gebildet werden, sieht so aus: