Hash-Funktion

Eine Hash-Funktion bzw. Streuwertfunktion ist eine Funktion, die zu einer Eingabe aus einer (üblicherweise) großen Quellmenge eine Ausgabe aus einer (im Allgemeinen) kleineren Zielmenge (die Hashwerte, meist eine Teilmenge der natürlichen Zahlen) erzeugt.

Hash-Funktionen unterscheiden sich in der Definitionsmenge ihrer Eingaben, der Zielmenge der möglichen Ausgaben und im Einfluss von Mustern und Ähnlichkeiten verschiedener Eingaben auf die Ausgabe. Hash-Funktionen werden in Hashtabellen, der Kryptologie und der Datenverarbeitung verwendet. Eine gute Hash-Funktion zeichnet sich dadurch aus, dass sie für die Eingaben, für die sie entworfen wurde, wenig Kollisionen erzeugt. Dadurch können die meisten Eingaben an Hand ihres Hashwertes unterschieden werden.

Der Name „Hash-Funktion“ stammt vom englischen Wort „to hash“, das sich als „zerhacken“ übersetzen lässt. Der deutsche Name lautet Streuwertfunktion. Speziell in der Informatik verwendet man auch die Bezeichnung Hash-Algorithmus, da die Berechnung von Funktionen mittels Algorithmen durchgeführt wird.

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.

Sinnvoll ist die Anwendung auch dann, wenn man Daten zusammen mit Schlüsseln speichern möchte und die Wertemenge der Schlüssel viel größer ist als die Menge der Objekte. Sind die Schlüssel z.B. 7-stellige Zahlen, so könnte man theoretisch 10 Millionen Datensätze (10⁷) speichern. Ist dies in der Praxis nicht der Fall, benutzt man eine Hash-Funktion die aus einer 7-stelligen Zahl eine kleinere erzeugt.

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 der Wertebereich meist kleiner als der der Quellmenge 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. Jedoch ist die Wahrscheinlichkeit für Kollisionen sehr groß, wenn schon einige Daten gespeichert wurden, vgl. auch Geburtstagsparadoxon. Man muss sich für den Fall einer Kollision eine Strategie der Kollisionsauflösung überlegen.

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.

Definition einer Hash-Funktion

Eine Abbildung

h: K \rightarrow S

heißt Hash-Funktion, wenn

|K|\geq\ |S|

gilt. Insbesondere liefert

h

eine Hashtabelle, wenn

|S|

eine natürliche Zahl

m

ist, die Größe der Hashtabelle.

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.

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.

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

Kryptologie | Algorithmus | Diskrete Mathematik

Gourt Home::Gourt :: Hash-Funktion