Hashfunktion einfach erklärt: Hashwerte verstehen

Eine Hashfunktion ist eine Abbildung. Sie nimmt eine große Menge möglicher Eingaben, die Schlüssel, und ordnet jeder Eingabe einen Wert aus einer kleineren Zielmenge zu. Diese Werte heißen Hashwerte. Die Eingaben können unterschiedlich lang sein. Die Hashwerte haben dagegen meist eine feste Länge.

Weil die Zielmenge kleiner ist, ist eine Hashfunktion im Allgemeinen nicht injektiv. Das heißt: Zwei verschiedene Eingaben können zum selben Hashwert führen. Das nennt man eine Kollision. Da die Menge der möglichen Hashwerte meist kleiner ist als die der möglichen Eingaben, sind Kollisionen dann prinzipiell unvermeidlich.

Eine gute Hashfunktion erzeugt für die Eingaben, für die sie entworfen wurde, möglichst wenige Kollisionen. Für bekannte und beschränkte Eingabemengen können auch perfekte, also kollisionsfreie, Hashfunktionen gefunden werden.

Ein Hashwert wird auch Fingerprint genannt (englisch für Fingerabdruck). Er stellt eine nahezu eindeutige Kennzeichnung einer größeren Datenmenge dar, so wie ein Fingerabdruck einen Menschen nahezu eindeutig identifiziert.

Eine Hashtabelle ist eine Indexstruktur, mit der man Datenelemente in einer großen Datenmenge sucht. Die Hashfunktion berechnet die Position eines Objekts in der Tabelle. Dadurch erübrigt sich das Durchsuchen vieler Datenobjekte. In der Praxis wird die Tabelle als Array implementiert.

Bei der Divisionsmethode wird ein Schlüssel einem Hashwert zugeordnet, indem man den Rest des Schlüssels bei Division durch die Größe der Hashtabelle berechnet. Die Formel lautet: h(key) = key mod tablesize. Dabei ist key der Schlüssel, tablesize die Größe der Hashtabelle und mod (Modulo) steht für den Rest der Division. Der Hashwert bestimmt das Fach der Tabelle, in dem das Datenobjekt liegt. Dieses Fach heißt Bucket (englisch für Behälter).

So gehst du vor: Teile key durch tablesize, nur mit ganzen Zahlen. Der Rest ist der Hashwert. Weil nur eine einzige Divisionsoperation nötig ist, ist dieses Verfahren ziemlich schnell.

Landen zwei Schlüssel im selben Fach, ist das eine Kollision. Dann muss die Tabelle mehrere Werte im selben Bucket aufnehmen. Kollidierte Daten werden nach einer Ausweichstrategie in alternativen Feldern oder in einer Liste gespeichert. Bei der Suche vergleicht man dann den Suchschlüssel mit den Objekten im Bucket.

Je nach Anwendung hat man unterschiedliche Anforderungen an eine Hashfunktion. Für eine Hashtabelle sind wenige Kollisionen wichtig, die Hashwerte sollen möglichst gleichmäßig verteilt sein. Außerdem muss die Funktion schnell berechenbar sein. Mit steigendem Füllgrad der Tabelle, also je voller sie wird, wächst die Wahrscheinlichkeit einer Kollision. Schlimmstenfalls entartet die Tabelle: Wenige Hashwerte sind sehr vielen Objekten zugewiesen, andere bleiben unbenutzt.

Bei der Divisionsmethode kommt es auch auf die Größe der Tabelle an. Sie sollte keine Potenz einer Zahl sein. Eine Primzahl, die nicht zu nah bei einer Zweierpotenz liegt, ist oft eine gute Wahl.

Prüfsummen erkennen Übertragungsfehler. Wie gut eine Hashfunktion dafür taugt, hängt von ihrer Kollisionswahrscheinlichkeit ab. Die Quersumme ist als Prüfsumme nicht gut geeignet, weil vertauschte Ziffern nicht auffallen: 25 und 52 haben dieselbe Quersumme. Soll die Prüfsumme vor gezielten Manipulationen schützen, nimmt man eine kryptographische Hashfunktion, also eine für die Kryptologie entworfene. Bei ihr kann nur mit sehr hohem Rechenaufwand eine Kollision gefunden werden.

Kryptographische Hashfunktionen sind kollisionsresistente Einwegfunktionen. Kollisionsresistent heißt: Es ist praktisch unmöglich, Kollisionen absichtlich zu finden. Einwegfunktion heißt: Aus dem Hashwert lässt sich der Eingabewert praktisch nicht bestimmen. Diese Eigenschaften sind notwendig, um zum Beispiel die Integrität von Daten sicherzustellen, also zu prüfen, ob sie verändert wurden. Dafür wendet man die Funktion auf die Datei an und vergleicht mit einem bekannten Hashwert. Weicht er ab, wurde die Datei verändert. Ein Angreifer könnte aber Datei und Hashwert zugleich verändern. Dagegen kann ein schlüsselbasiertes Verfahren helfen, zum Beispiel eine digitale Signatur oder ein Message Authentication Code (ein Prüfwert, der mit einem geheimen Schlüssel berechnet wird).

Auch Passwörter werden mit solchen Hashfunktionen gespeichert: Das System vergleicht den Hashwert des eingegebenen Passworts mit dem gespeicherten Hashwert. Stimmen beide überein, ist das Passwort mit sehr hoher Wahrscheinlichkeit richtig. Außerdem sollen bei kryptologischen Hashfunktionen ähnliche Eingaben zu völlig verschiedenen Hashwerten führen.

Verschlüsselung ist die Umwandlung von Informationen, dem Klartext, in einen Geheimtext. Sie geschieht mit kryptografischen Verfahren und einem geheimzuhaltenden Schlüssel, der nur den befugten Personen bekannt sein darf. Mit Kenntnis des Schlüssels kann der Geheimtext wieder in den Klartext zurückgewandelt werden. Das heißt Entschlüsselung.

Eine kryptographische Hashfunktion hat keinen solchen Rückweg. Sie erzeugt aus der Eingabe einen Hashwert fester Länge und ist eine Einwegfunktion. Der Inhalt soll nicht aus dem Hashwert rekonstruiert werden können. Der Hashwert soll einen Inhalt nahezu eindeutig kennzeichnen, ohne etwas über den Inhalt zu verraten. Diese Unumkehrbarkeit wird speziell von kryptologischen Hashfunktionen gefordert.

Bei Passwörtern heißt das: Das System speichert nur den Hashwert. Ein Angreifer mit Lesezugriff auf die Datenbank erlangt so nicht das Passwort. Im Idealfall kann er es aus dem Hashwert nicht oder nur mit erheblichem Aufwand rekonstruieren.

In einer Wikibooks-Anleitung zu PHP heißt es, man könne die Passwörter nicht einfach entschlüsseln, und dort wird von einer „Hashverschlüsselung“ gesprochen. Das Wort ist missverständlich: Eine Einwegfunktion hat anders als die Verschlüsselung keinen Rückweg zum Klartext. Der Angreifer müsste alle möglichen Passwörter hashen und mit dem gespeicherten Wert vergleichen.