Ein Hash ist ein Typ von Algorithmus, der aus einem langen Datentext (String) beliebiger Länge einen kurzen Wert oder Text fester Länge errechnet. Die Abbildungsfunktion sollte sich effizient errechnen lassen. Umgekehrt darf aus dem errechneten Wert sich aber der ursprüngliche Text nicht reproduzieren lassen.
Einsatzfälle
Eingesetzt werden Hashs auf zwei verschiedene Arten und Weise. In der Kryptographie werden sie als Message Digest und digitale Signatur eingesetzt. Dabei bildet man aus dem Text und einem Schlüssel Hashwerte. Mit diesen lässt sich die Unversehrtheit eines Textes nachweisen, da eine Veränderung am Text einen anderen Hashwert ergibt, der aber nur gebildet werden kann, wenn man den richtigen Schlüssel besitzt. Bekannte kryptographische Hash-Algorithmen sind MD4, MD5, SHA-1 und TIGER. Genutzt wird dies auch, um Passwörter auch für den Administartor unlesbar abzuspeichern. Statt das Passwort im Klartext zu speichern wird nur der Hashwert des Passwortes gespeichert und mit dem Hashwert des Passwortes einer späteren Eingabe verglichen. Damit diese Verfahren weiterhin sicher sind, müssen sie heute mit Salts oder Key Stretching kombiniert und mehrfach angewendet werden.
Der zweite Einsatzfall sind Datenstrukturen, die ebenfalls als Hash oder Hashtabelle bezeichnet werden. Von einem String, der gespeichert werden soll, wird mit einer Hashfunktion ein Wert errechnet, der als Index in einer Tabelle verwendet wird. Unter dem Index wird der String oder die Datenstruktur, die der String repräsentiert, dann abgelegt. Da Hashfunktionen schneller sind als das Suchen in einer Tabelle, kann mit Hashes sehr schnell auf Daten zugegriffen werden. Allerdings haben die Hashfunktionen, die hierfür eingesetzt werden, andere Eigenschaften als in der Kryptographie. Da die Tabelle nur eine begrenzte Länge haben kann, werden potentiell verschiedene Texte auf die gleiche Indexposition abgebildet. Wenn dies wirklich passiert, dann muss der Hash dafür ein Ausweichverfahren besitzen (Werte in zusätzliche Listen auslagern oder auf andere Plätze in der Tabelle verschieben).
Eigenschaften kryptografischer Hash-Funktionen
Die Tauglichkeit kryptografischer Hashfunktionen wird nach drei Kriterien bewertet:
- Kollisionsfestigkeit
- Nichtreproduzierbarkeit des Klartextes aus dem Hashwert
- Puzzle-Eignung
Kollisionsfestigkeit bedeutet, dass es sehr schwer ist zwei Klartexte zu finden, welche den gleichen Hashwert ergeben. Sehr schwer bedeutet nicht unmöglich. Denn es muss ja Kollisionen geben, da die Eingabemenge beliebig groß, die Abbildungsmenge aber endlich ist. In der Praxis bedeutet dies, dass es sehr schwer sein soll, dass ähnlich Eingabewerte (zum Beispiel fast identische Dokumente) den gleichen Hashwert ergeben. Kleine Änderungen am Eingabewert müssen daher große Änderungen in der Abbildung verursachen.
Nichtreproduzierbarkeit bedeutet, dass man nur mit dem Hashwert nicht in der Lage sein soll, den zugehöhrigen Klartext zu ermitteln. Das gilt aber nur, wenn der Klartext selbst nicht gut vorhersagbar ist. Denn natürlich kann man zum Beispiel die Hashwerte von beliebten Passworten vorherberechnen (Rainbow Table) und durch die Suche in der Menge dieser vorberechnen Hashes die Klartextermittlung versuchen abzukürzen. Um das zu verhindern muss man die Eingabemenge also zum Beispiel durch Salting zufälliger gestalten.
Puzzle-Eignung bedeutet, dass es sehr aufwändig (ca. 2^n Versuche für einen n-Bit-langen Hashwert) ist, einen Klartext zu finden, der den gleichen Hashwert ergibt wie der, der zu einem vorgegebenen Klartext ermittelt wurde. Es darf keine Abkürzung oder bessere Lösungsstrategie geben als die Menge der Eingabewerte zufällig durchzuprobieren. Diese Eigenschaft eines kryptografischen Hashes wird zum Beispiel beim Bitcoin-Mining genutzt.
