Hash-Funktion

Einführung

Der Name „Hashfunktion“ stammt vom englischen Verb to hash, das sich als „zerhacken“ übersetzen lässt. Der deutsche Name lautet Streuwertfunktion. Beide Namen deuten darauf hin, dass diese Funktionen normalerweise darauf angelegt sind, die Daten zu „verstreuen“ und zu „zerhacken“.

Eine Hashfunktion (auch Streuwertfunktion) ist eine Abbildung, die eine große Eingabemenge auf eine kleinere Zielmenge (die Hashwerte) abbildet. Die Eingabemenge kann Elemente unterschiedlicher Längen enthalten, die Elemente der Zielmenge haben dagegen meist eine feste Länge (Quelle: Wikipedia).

Eine Hashfunktion liefert dabei für die Eingabedaten Werte so, dass zwei unterschiedliche Eingaben auch zu unterschiedlichen Ausgabewerten führen. Ein Hashwert wird deshalb auch als englisch Fingerprint bezeichnet, da er eine nahezu eindeutige Kennzeichnung einer größeren Datenmenge darstellt, so wie ein Fingerabdruck einen Menschen nahezu eindeutig identifiziert. Eine sog. Kollision tritt dann auf, wenn unterschiedlichen Eingabedaten derselbe Hashwert zugeordnet wird. Da die Menge der möglichen Hashwerte meist kleiner ist als die der möglichen Eingaben, sind solche Kollisionen dann prinzipiell unvermeidlich, weshalb es Verfahren zur Kollisionserkennung geben muss. Eine gute Hashfunktion zeichnet sich dadurch aus, dass sie für die Eingaben, für die sie entworfen wurde, möglichst wenige Kollisionen erzeugt.

Bei der Identifikation von Inhalten mit sogenannten kryptologischen Hashfunktionen ist es nicht nur wichtig, dass sich der Hashwert bei jeder kleinen Modifikation scheinbar zufällig (d. h. nicht etwa mit nur wenigen Bits) ändert (hierfür würde eine normale Prüfsumme reichen) und dass es nicht einfach ist, einen zweiten Inhalt mit demselben Hashwert zu erzeugen (um einen Komplettaustausch des Inhaltes zu vermeiden). Ebenso wichtig ist es, dass der Inhalt nicht aus dem Hashwert rekonstruiert werden kann. Hat man zwei Dokumente ausgetauscht und möchte beispielsweise am Telefon die erfolgreiche Übertragung überprüfen, so reicht es, am Telefon die Korrektheit des Hashwertes zu überprüfen. Wird das Gespräch abgehört, so wird dabei nichts über den Inhalt der Nachricht verraten, selbst falls Teile des Inhalts bereits bekannt sein sollten.

Anwendungsfälle

Hashfunktionen werden typischerweise angewendet, um:

einem komplexen Objekt einen Speicherort zuzuweisen. Beispiel: „Max Mustermann“ wird im Ordner „m“ abgelegt – dem ersten Buchstaben des Nachnamens.
eine (kurze) Prüfsumme zu dem Objekt zu berechnen. Beispiel: Prüfsumme einer ISBN, Zyklische Redundanzprüfung zur Erkennung von Übertragungsfehlern von Dateien
einen Inhalt nahezu eindeutig (aber immer noch „kurz“) zu identifizieren, ohne etwas über den Inhalt zu verraten. Beispiel: Anwendungen in der Kryptographie.

Kriterien für eine gute Hashfunktion

Geringe Wahrscheinlichkeit von Kollisionen der Hashwerte für den Eingabewertebereich, also möglichst eine Gleichverteilung der Hashwerte auf die erwarteten Eingabewerte.
Der Speicherbedarf des Hashwertes soll deutlich kleiner sein als jener des Schlüssels (Eingabewert).
Chaos oder Lawineneffekt – Ähnliche Quellelemente (Eingabewerte) sollen zu völlig verschiedenen Hashwerten führen. Im Idealfall verändert das Umkippen eines Bits in der Eingabe durchschnittlich die Hälfte aller Bits im resultierenden Hashwert.
Surjektivität – Kein Ergebniswert (Hashwert) soll unmöglich sein, jedes Ergebnis (jeder Hashwert 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 (Eingabewerte) möglichst nur einmal zu lesen brauchen.
ordnungserhaltend – Falls die Hashfunktion einen sortierten Zugriff in einer Hashtabelle erlauben soll.

Je nach Anwendung spielen diese Kriterien eine unterschiedliche Rolle. So sind Chaos und Ordnungserhaltung offenbar im Widerspruch zueinander. In der Kryptographie ist letztere tabu, für bestimmte Datenbankanwendungen ist dies dafür genau erwünscht.

Page updated

Google Sites

Report abuse