Hashfunktion

Copyright © Unspash / Jeswin Thomas

Was ist die Hashfunktion?

Eine Hashfunktion (deutsch: Streuwertfunktion) ist eine mathematische Funktion, die Dateneinheiten beliebiger Größe auf Dateneinheiten fester kleinerer Größe abbildet. Die von einer Hashfunktion berechneten Werte werden Hashwerte, Hashcodes, Digests oder einfach Hashes genannt. Ein Hash-Algorithmus berechnet die Hashfunktion.

Ein Beispiel für eine intuitiv im Alltag gebräuchliche Hashfunktionen ist der erste Buchstabe des Nachnamens für die Einsortierung von namensbezogenen Daten. Bei der Suche muss dann nur in einem von 26 Bereichen des Adressbuchs nachgesehen werden.

Ein weiteres einfaches Beispiel ist die Quersumme. Sie ordnet einer größeren (längeren) Zahl eine kleinere (kürzere) zu. Typische in Software genutzten Hash-Algorithmen sind allerdings weitaus komplexer.

Eigenschaften

Eine Hashfunktion sollte folgende Eigenschaften haben:

Kollisionen

Die Hashwerte sind meist natürliche Zahlen. Eine “gute” Hashfunktion liefert für zwei unterschiedliche Eingaben auch zwei unterschiedliche Ausgabewerte. Ein Hashwert wird daher auch als Fingerprint bezeichnet, da er eine nahezu eindeutige Identifizierung einer größeren Datenmenge erlaubt.

Wenn aus unterschiedlichen Eingabedaten derselbe Hashwert berechnet wird, tritt eine sogenannte Kollision auf. Solche Kollisionen können auftreten, weil die Menge der möglichen Hashwerte typischerweise kleiner ist als die Menge der möglichen Eingabedaten. Daher gibt es Verfahren zur Erkennung von Kollisionen. Eine gute Hashfunktion erzeugt möglichst wenige Kollisionen. Für beschränkte Eingabemengen können auch perfekte (kollisionsfreie) Hashfunktionen gefunden werden.

Anwendungen

Anwendungsfelder für Hashfunktionen lassen sich in drei Gebiete einteilen:

Datenbanken

Datenbanksysteme verwenden Hashfunktionen, um Daten in großen Beständen zu suchen. Hashtabellen bilden dabei den Datenbankindex. Ein Index gibt die Stelle in der Hashtabelle an, an der der entsprechende Datensatz gespeichert ist.

Ein Hashwert wird verwendet, um ausgehend von einem Schlüssel (Stichwort) die Speicherstelle angefragter Daten zu berechnen. Wenn verschiedene Schlüssel (Stichwörter) demselben Index einer Hashtabelle zugeordnet werden, ist diesem Slot der Hashtabelle mehr als ein Datensatz zugeordnet, und es herrscht eine Kollision.

Die Hashfunktion gibt dann nur Hinweise auf die Position des Datensatzes. In einer halbvoll besetzten Tabelle wird die weitere Suche durch das Verfahren jedoch in der Regel auf nur einen oder zwei Einträge eingeschränkt, die in dem gefundenen Slot stehen.

Prüfsummen

Prüfsummen sind ein einfaches Mittel, um Veränderungen an übertragenen Daten zu erkennen. Statt die empfangene Datei Zeichen für Zeichen mit der originalen Datei zu vergleichen, muss nur der (viel kleinere) Hashwert der empfangenen Datei berechnet und mit der übertragenen Prüfsumme der Originaldatei verglichen werden.

Mit mehreren erzeugten Prüfsummen kann die Wahrscheinlichkeit einer Kollision zudem stark verringert werden. Soll die Prüfsumme vor Manipulationen der Daten schützen, wird eine kryptografische Hashfunktion verwendet.

Kryptografie

In der Kryptografie kommen Hashfunktionen zur Signierung von Daten zum Einsatz, um ihre Integrität sicherzustellen. Es handelt sich um spezielle Hashfunktionen, bei denen es praktisch unmöglich ist, Kollisionen gezielt zu finden.

Mit einer kryptografischen Hashfunktion kann leicht überprüft werden, ob Eingabedaten authentisch sind, ohne etwas über ihren Inhalt zu verraten. Auch ein abgehörter Hashwert, der eine geheime Datenmenge eindeutig identifiziert, kann nicht dazu genutzt werden, die Daten zu rekonstruieren.

Kryptografische Hashfunktionen sind entweder schlüssellos oder schlüsselabhängig. Eine schlüssellose hat nur einen Eingabewert, eine schlüsselabhängige benötigt als zweiten Eingabewert einen geheimen Schlüssel.

In Webanwendungen werden Hashfunktionen zum Erzeugen von Session-IDs verwendet. Session-IDs werden von Webanwendungen als Identifikationsmerkmal benutzt, um zusammengehörige Anfragen und Eingaben eines Nutzers zu erkennen und ihm (einer “Sitzung”) zuzuordnen. Dabei wird ein Hashwert unter Einbezug von wechselnden Zustandswerten (wie Uhrzeit und IP-Adresse) berechnet.