Hashfunktion

Eine Hash-Funktion bzw. Streuwertfunktion ist eine mathematische Funktion, die zu einer Eingabe aus weitgehend beliebigen Daten, praktisch unbegrenzter Menge, die von einem Computer verarbeitet werden können, einen eindeutigen Funktionswert definiert. Der Funktionswert oder Hashwert ist letztlich als eine natürliche Zahl n interpretierbar, die typischer Weise als 20 Bytewert (n kleiner 2¹⁶⁰ = 1.461.501.637.330.902.918.203.684.832.716.283.019.655.932.542.976) gespeichert werden kann.

Ein Hashwert wird auch als Fingerprint bezeichnet. Denn wie ein Fingerabdruck einen Menschen nahezu eindeutig identifiziert, ist ein Hashwert eine nahezu eindeutige Kennzeichnung beliebiger elektronischer Daten wie Texte, Bilder oder Software.

Hash-Funktionen werden innerhalb der Datenverarbeitung in Hashtabellen und der Kryptologie verwendet. Hash-Funktionen mit mindestens 20 Byte Länge sind in der Regel kollisionsfrei, d.h. es ist praktisch unmöglich unterschiedliche Daten zu finden, die den gleichen Hashwert ergeben.

Die Berechung erfolgt in der Regel indem die Daten zunächst in Blöcke zerlegt werden, die nacheinander verarbeitet werden. Daher erklärt sich der Name „Hash-Funktion“ vom englischen Wort „to hash“, das sich als „zerhacken“ übersetzen lässt. Der deutsche Name Streuwertfunktion beschreibt genauer den Zweck einer Hashfunktion. Aus beliebigen Daten werden scheinbar zufällig gestreute Werte berechnet. Zuweilen wird der Begriff Hash-Algorithmus gebraucht.

Vergleich mit Prüfsummen

Eine Hash-Funktion nichts anderes als eine Prüfsumme, die zu einer Eingabe beliebiger Länge (zum Beispiel ein Text) einen kurzen, möglichst eindeutigen Prüfwert berechnet.

In der Regel wird der Begriff Prüfsumme verwendet, falls nur eine Prüfziffer oder ein relativ kurzer Prüfwert berechnet wird. Letzlich besteht jedoch kein prinzipieller Unterschied. Die Prüfsumme sollte von der gesamten Eingabe abhängen. Die letzte Ziffer einer Zahl wäre eine sehr ungünstige Wahl für ein Prüfsummenverfahren.

Wird nur eine Ziffer als Prüfwert benutzt, besteht eine 10 Prozent Wahrscheinlichkeit für zufällig Übereinstimmungen bei unterschiedlichen Daten (Kollisionen). Bei längeren Hashwerten ist eine zufällig Übereinstimmung praktisch ausgeschlossen. Wegen des Geburtstagsparadoxons ist die dopplete Länge von etwa 20 Byte statt nur 10 Byte erforderlich, um kollisionsfreie Hashfunktion zu erhalten.

Anwendungen

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

Prüfsummen erzeugen ebenfalls eine Abbildung auf eine reduzierte Datenmenge – stellen somit auch eine Hash-Funktion dar –, hier mit dem Ziel, die Datenintegrität bei Störeinflüssen oder absichtlichen Manipulationen sicherzustellen. Absichtliche Manipulationen sind jedoch nur begrenzt feststellbar, solange die Hash-Funktion gewissen Ansprüchen genügt (siehe Kollisionsfreiheit und Unumkehrbarkeit).

Bei der Programmierung von Internet-Anwendungen werden Hash-Funktionen zum Erzeugen von Session-IDs genutzt, indem unter Verwendung von wechselnden Zustandswerten (wie Zeit, IP-Adresse) ein Hashwert berechnet wird.

Formale Definition einer Hash-Funktion

Eine Abbildung $h:K\rightarrow S$ heißt Hash-Funktion, wenn $|K|\geq \ |S|$ gilt. Insbesondere liefert $h$ eine Hashtabelle der Größe $|S|$ . $S$ heißt auch die Menge der Schlüssel. Die Menge $K$ repräsentiert die Daten die gehasht werden sollen. Typischerweise wird die Menge der Schlüssel als Anfangsstück der natürlichen Zahlen gewählt: $S\subseteq \left\{0,\ldots ,m-1\right\}$ Diese Menge heißt dann auch Adressraum.

Typischerweise wird in der Praxis immer nur eine kleine Teilmenge $K'{}\subseteq {}K$ mit $h$ abgebildet. Die Menge $S':=\{h(k)|k\in K'\}$ sind dann die tatsächlich genutzten Schlüssel.

Das Verhältnis $\beta ={\frac {\left|S'\right|}{m}}$ liefert uns den Belegungsfaktor.

Der Fall $k\not =k'\land h(k)=h(k')$ wird als Kollision bezeichnet. Eine injektive Hash-Funktion heißt perfekt, u.a. weil sie keine Kollisionen erzeugt.

Kriterien für eine gute Hash-Funktion

Datenreduktion

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

Chaotisch

Ä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.

Surjektiv

Kein Ergebniswert soll unmöglich sein, jedes Ergebnis (im definierten Wertebereich) soll tatsächlich vorkommen können.

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.

Bekannte Hash-Funktionen

Allgemeine Hash-Algorithmen

Hash-Algorithmen in der Kryptographie

Attacken

Man unterscheidet Kollisionsangriffe und die wesentlich aufwändigeren Preimage-Angriffe. Bei einem Kollisionsangriff geht es darum, zwei beliebige Eingaben zu finden, die sich auf den gleichen Hash-Wert abbilden lassen. Bei einem Preimage-Angriff muss hingegen zu einer vorgegebenen Eingabe eine andere Eingabe mit gleichem Hash-Wert gefunden werden.

Weblinks

Vorlage:Navigationsleiste Hash-Algorithmen