Hashfunktion

Eine Hashfunktion, die Namen auf Ganzzahlen abbildet. Für die Namen „John Smith“ und „Sandra Dee“ gibt es eine Kollision.

Eine Hashfunktion (auch Streuwertfunktion) ist eine Abbildung, die eine große Eingabemenge (die Schlüssel) auf eine kleinere Zielmenge (die Hashwerte) abbildet – sie ist daher nicht bijektiv. Dabei kann die Eingabemenge auch Elemente mit unterschiedlichen Längen enthalten, die Elemente der Zielmenge haben dagegen meist eine feste Länge.

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“ (siehe auch Zerhacker in der Funktechnik). Speziell in der Informatik verwendet man auch den Begriff Hash-Algorithmus (englisch hash algorithm), da Hashfunktionen oftmals in Form eines Algorithmus statt einer mathematischen Funktion spezifiziert werden.

Die Hash- oder Streuwerte sind meist skalare Werte aus einer begrenzten Teilmenge der natürlichen Zahlen. Eine „gute“ Hashfunktion liefert dabei für die (erwarteten) 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 zwei verschiedenen 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.

In der Datenspeicherung kann ein Hashwert verwendet werden, um die Speicherstelle der angefragten Daten zu berechnen (z. B. Hashtabelle).

Bei Prüfsummen verwendet man Hashwerte, um Übertragungsfehler zu erkennen.

In der Kryptologie werden Hashfunktionen verwendet, um den Inhalt übertragener Daten zu verifizieren. Hier wird daher zusätzlich gefordert, dass Kollisionen sehr schwer zu finden sind, damit modifizierte Daten nicht zufällig den gleichen Hashwert besitzen wie das Original.

Für bekannte und beschränkte Eingabemengen können auch perfekte (i. S. v. kollisionsfreie) Hashfunktionen gefunden werden.

Anschauliche Erklärung

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

Je nach Anwendung hat man unterschiedliche Anforderungen an die Funktion. Gruppiert man beispielsweise eine Adresskartei nach dem ersten Buchstaben des Nachnamens, spart man sich offensichtlich bei der Suche viel Zeit – man muss nur einen von 26 Teilen durchsuchen. Diese „Hashfunktion“ ist für den Menschen sehr praktisch (da sie sehr einfach zu „berechnen“ ist), jedoch würde ein Computerprogramm andere Verfahren verwenden, um ein Adressbuch zu organisieren. Für das Programm ist es nämlich wichtig, möglichst wenige Kollisionen zu haben; es gibt aber offenbar viele Namen, die mit demselben Anfangsbuchstaben beginnen, und sie kommen ungleichmäßig oft vor. Legt man also beispielsweise Personalakten nach diesem Prinzip ab, so hat man oftmals viele Akten im Ordner mit dem Buchstaben „S“, während der Ordner „Q“ leer bleibt.

Die einstellige Quersumme ist eine einfache Hashfunktion. Sie ordnet einer beliebigen Zahl eine einstellige Zahl zu, so wird beispielsweise $25$ auf $2+5=7$ abgebildet. Als Prüfsumme ist diese Quersumme aber nicht gut geeignet, da die Vertauschung von Ziffern – ein typischer Fall beim Abtippen von langen Zahlen – nicht erkannt wird. So hat auch die Zahl $52$ dieselbe Quersumme $5+2=7$. Prüfsummen wie bei der ISBN eines Buches oder die CRC-32-Prüfsumme einer Datei (z. B. beim Prüfen eines Downloads auf Übertragungsfehler) eignen sich besser, derartige Fehler zu erkennen.

Bei der Identifikation von Inhalten mit so genannten kryptographischen Hashfunktionen ist es nicht nur wichtig, dass sich der Hashwert bei einer kleinen Modifikation sofort komplett ä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.

Definition einer Hashfunktion

Eine Abbildung $h\colon K \rightarrow S$ heißt Hashfunktion, wenn $|K|\geq\ |S|$ gilt. Insbesondere liefert $h$ eine Hashtabelle der Größe $|S|$. Die Menge $K$ repräsentiert die Daten, die gehasht werden sollen, und wird auch die Menge der Schlüssel genannt; die Menge $S$ ist die Menge der möglichen Hashwerte. Typischerweise wird die Menge der Hashwerte als Anfangsstück der natürlichen Zahlen gewählt: $S \subseteq \left\{ 0, \dotsc, 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|}{\left| S \right|}$ liefert uns den Belegungsfaktor.

Der Fall $k \not= k' \land h(k) = h(k')$ wird als Kollision bezeichnet. Eine injektive Hashfunktion heißt perfekt, u. a. weil sie keine Kollisionen erzeugt.

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 der Nachricht (Eingabewert).
• Chaos – Ä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 lesen müssen.
• ordnungs­erhaltend – Falls die Hashfunktion einen sortierten Zugriff in einer Hashtabelle erlauben soll.

Je nach Anwendung spielen diese Kriterien eine unterschiedliche Rolle. So ist Chaos und Ordnungserhaltung offenbar widersprüchlich. In der Kryptographie ist letztere tabu, für bestimmte Datenbank­anwendungen ist dies dafür genau erwünscht.

Anwendungen

Hashfunktionen haben verschiedene Anwendungsfelder. Dabei lassen sich drei große Gebiete unterteilen:

1. Datenbanken
2. Prüfsummen
3. Kryptologie

Hashfunktionen in Datenbanken

Datenbank­managementsysteme verwenden Hashfunktionen, um Daten in großen Datenbeständen mittels Hashtabellen zu suchen. In diesem Fall spricht man von einem Datenbankindex.

Prüfsummen

→ Hauptartikel: Prüfsumme

Prüfsummen sind ein einfaches Mittel um Veränderungen an übertragenen Daten zu erkennen.

Ein Fehler ist feststellbar, wenn die berechnete Prüfsumme der empfangenen Daten sich von der übertragenen Prüfsumme, also der der Originaldaten, unterscheidet. Die Eignung verschiedener Hashfunktionen zur Prüfsummenberechnung hängt von deren Kollisionswahrscheinlichkeit ab.

Wenn die Prüfsumme vor gezielten Manipulationen der Daten schützen soll, wird eine kryptographische Hashfunktion verwendet, da hier nur mit sehr hohem Rechenaufwand eine Kollision gefunden werden kann.

Beispiele

Hashwerte haben unter anderem bei P2P-Anwendungen aus verschiedenen Gründen eine wichtige Aufgabe. Die Hashwerte werden hier sowohl zum Suchen und Identifizieren von Dateien, als auch zum Erkennen und Prüfen von übertragenen Dateifragmenten verwendet. So lassen sich große Dateien zuverlässig in kleinen Segmenten austauschen.

Zur Anwendung in P2P-Netzen kommen vor allem gestufte Hashfunktionen, bei denen für kleinere Teile einer Datei der Hashwert und dann aus diesen Werten ein Gesamtwert berechnet wird. Bei den Netzwerken Gnutella G2, Shareaza und Direct Connect sind dies zum Beispiel Tiger-Tree-Hash-Funktionen.

Das Auffinden von Dateien aufgrund des Hashwertes ihres Inhaltes ist zumindest in den USA als Softwarepatent geschützt. Der Inhaber verfolgt Programme und Firmen, die auf Basis dieses Systems die Suche von Dateien ermöglichen, einschließlich Firmen, die im Auftrag von RIAA oder MPAA Anbieter von unlizenzierten Inhalten ermitteln wollen.

Bei der Programmierung von Internet-Anwendungen werden Hashfunktionen zum Erzeugen von Session-IDs genutzt, indem unter Verwendung von wechselnden Zustandswerten (wie Zeit, IP-Adresse) ein Hashwert berechnet wird.

Kryptologie

→ Hauptartikel: Kryptologische Hashfunktion

Es gibt eine Gruppe von sog. kryptologischen Hashfunktionen, die spezielle Eigenschaften besitzen. Sie werden verwendet, um Nachrichten zu signieren bzw. die Integrität von Daten sicherzustellen.

Hash-Algorithmen

Bekannte

• Brent-Hashing
• Divisions-Rest-Methode
• Doppel-Hashing
• FNV
• Kuckucks-Hashing
• Multiplikative Methode
• Mittquadratmethode
• Zerlegungsmethode
• Ziffernanalyse

Gitterbasierte

• Ajtai
• Micciancio
• Peikert-Rosen
• Schnelle Fourier-Transformation (FFT Hashfunktion)
• LASH

Prüfsummen

• Fletcher-32
• Adler-32
• CRC (Zyklische Redundanzprüfung)
• Parität
• Quersumme

Kryptologische Hashfunktionen

• MD2, MD4, MD5
• Secure Hash Algorithm (SHA)
• RIPEMD-160
• Tiger
• HAVAL
• Whirlpool
• LM-Hash
• NTLM

Literatur

•  Donald E. Knuth: The Art of Computer Programming Volume 3. 2. Auflage. Addison Wesley, 1998, ISBN 0-201-89685-0, S. 513 ff.
•  Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. 2. Auflage. Oldenbourg Wissenschaftsverlag, München 2007, ISBN 978-3-486-58262-8, S. 221 ff.

Weblinks

• CRC Press – Handbook of Applied Cryptography (Kapitel 9) (PDF; 471 kB)
• Konstruktion von Hashfunktionen (PDF; 841 kB)