Hashfunktion

Beispiel einer Hashfunktion (hier SHA-1), links drei unterschiedliche Eingabewerte, rechts die entsprechenden Hashcodes

Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge.

Die Hashwerte beziehungsweise Streuwerte sind meist skalare Werte aus einer Teilmenge der natürlichen Zahlen. Eine „gute“ Hashfunktion liefert dabei für die (erwarteten) Daten Werte, so dass zwei unterschiedliche Eingaben auch zu unterschiedlichen Ausgabewerten führen (ansonsten spricht man von einer Kollision). Ein Hashwert wird deshalb auch als Fingerprint bezeichnet, da er eine nahezu eindeutige Kennzeichnung einer größeren Datenmenge darstellt, so wie ein Fingerabdruck einen Menschen nahezu eindeutig identifiziert. In der Kryptologie werden Hashcodes beispielsweise verwendet, um den Inhalt eines Dokumentes zu identifizieren, ohne dass man den kompletten Inhalt übermitteln oder vergleichen muss. In der Datenspeicherung dient der Hashcode um schnell die Speicherstelle der angefragten Daten zu finden, ohne dazu lange suchen zu müssen. Bei Prüfsummen verwendet man Hashwerte um Übertragungsfehler zu erkennen.

Hashfunktionen unterscheiden sich in der Definitionsmenge ihrer Eingaben, der Zielmenge der möglichen Ausgaben und im Einfluss von Mustern und Ähnlichkeiten verschiedener Eingaben auf die Ausgabe (und damit auf auftretende Kollisionen). Hashfunktionen werden vor allem in Hashtabellen, der Kryptologie und der Datenverarbeitung verwendet.

Hash-Algorithmen sind darauf optimiert, Kollisionen zu vermeiden. Eine Kollision tritt dann auf, wenn zwei verschiedenen Datenstrukturen derselbe Hashwert zugeordnet wird. Da der Hashwert in der Praxis meist kürzer als die originale Datenstruktur ist, 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, wenige Kollisionen erzeugt. In Sonderfällen kann auch eine perfekte (kollisionsfreie) Hashfunktion ermittelt werden.

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 typischerweise 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 (engl. hash algorithm), da Hashfunktionen oftmals in Form eines Algorithmus spezifiziert werden. Der Begriff Streuspeicherverfahren wird in der Datenspeicherung verwendet für Verfahren, die eine Hashfunktion zur Organisation der Daten einsetzen.

Anschauliche Erklärung

Hashfunktionen werden typischerweise angewendet um:

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

Je nach Anwendung hat man unterschiedliche Anforderungen an die Funktion. Beispielsweise ist die einstellige Quersumme 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 erkennt. So hat auch die Zahl $52$ die selbe 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.

Gruppiert man 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. Jedoch kommen die Anfangsbuchstaben unterschiedlich häufig vor. So findet man wenige Namen die mit „Q“ beginnen, aber so viele die mit „S“ beginnen, dass man oftmals „Sch“ als separaten Teil anlegt. Diese „Hashfunkion“ ist für den Menschen sehr praktisch (da sie sehr einfach zu „berechnen“ ist), jedoch würde ein Computer andere Verfahren verwenden, um ein Adressbuch zu organisieren. Für den Computer ist sie nämlich sehr ungünstig: normalerweise versucht man möglichst wenige Kollisionen zu haben, es gibt aber offenbar viele Namen, die mit dem selben Anfangsbuchstaben beginnen, und sie kommen ungleichmäßig oft vor. Legt man also Beispielsweise Personalakten nach diesem Prinzip ab, so hat man oftmals viele Ordner mit dem Buchstaben „S“, während der Ordner „Q“ leer bleibt.

Bei der Identifikation von Inhalten mit sogenannten 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 dem selben 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 nun 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.

Beispiel des Logins in eine passwortgeschütze Internetseite: Richtet ein Nutzer einen neuen Account bei einer mit Passwort geschützten Internetseite an, berechnet der Computer mit Hilfe eines Algorithmus einen Hash dieses Passwortes und speichert ihn zusammen mit dem Benutzernamen. Der Algorithmus sollte dabei so gestaltet sein, dass es keine effiziente Möglichkeit gibt, aus dem Hash auf das gespeicherte Passwort zurückzuschließen (bzw. eine Zeichenkette zu finden, die denselben Hash liefert, genannt Kollision). Gibt der Benutzer später sein Passwort ein, um sich einzuloggen, wird der Hash des eingegebenen Passwortes berechnet und mit dem gespeicherten Hash verglichen. Stimmen die Hashes nicht überein, ist das Passwort mit Sicherheit falsch gewesen. Stimmen sie überein, war es mit sehr hoher Wahrscheinlichkeit richtig. Weder ein Hacker, der sich Zugang zu dem Rechner verschafft hat, auf dem die Hashes liegen, noch der Betreiber der Seite, der vollen Zugang zu allen Daten hat, kann diese Information für sich nutzen; denn um sich in den Account eines Benutzers einzuloggen, müsste er eine Zeichenkette ermitteln, die den gleichen Hash erzeugt, wie das von dem Benutzer gewählte Passwort. Dies gelingt im Idealfall nur durch Ausprobieren. Besteht das Passwort etwa aus 10 Zeichen (Alphanumerisch, Case-Sensitiv), dann gibt es bereits 840 Trilliarden Möglichkeiten. Ein Computer, der zu 10.000 Passwörtern pro Sekunde den Hash berechnen kann, würde ca. 3 Millionen Jahre brauchen, alle möglichen Kombinationen durchzutesten. Anders verhält es sich, wenn das Passwort ein bekanntes Wort, z.B. aus dem Duden oder einem anderen Wörterbuch, ist. Im Duden stehen nur etwa 120.000 Wörter, die ein Computer problemlos durchtesten kann (selbst wenn Wortkombinationen verwendet werden).

Der Vergleich mit einem Fingerabdruck ist durchaus zutreffend. Stimmt der an einem Tatort gefundene Fingerabdruck mit demjenigen eines Verdächtigen nicht überein, so stammt der Fingerabdruck mit Sicherheit von einer anderen Person. Im Falle der Übereinstimmung ist es sehr wahrscheinlich, dass der Fingerabdruck zu dem Finger der getesteten Person gehört. Aus der Kenntnis des Fingerabdrucks allein kann allerdings nicht ohne Weiteres die zugehörige Person ermittelt werden, da dazu die Fingerabdrücke einer ganzen Reihe von Personen untersucht und mit dem vorhandenen Fingerabdruck abgeglichen werden muss, was zu viel Aufwand ist. Die Ermittler müssen erst geeignete Kandidaten finden, um den Fingerabdruck nutzen zu können. Um den Hash eines Passwortes verwendbar zu machen, müssen ebenfalls zunächst geeignete Kandidaten ermittelt werden, um die Menge der zu testenden Zeichenketten drastisch zu reduzieren.

Anwendungen

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

1. Datenbanken
2. Kryptologie
3. Prüfsummen

Hashfunktionen in Datenbanken

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

Kryptologie

In der Kryptologie werden kryptologische Hashfunktionen zum Signieren verwendet. Die bekanntesten Verfahren hierzu sind MD5 und SHA-1. Verfahren wie HMAC stellen die Authentizität und Integrität einer Nachricht sicher.

Hashwerte sind auch Bestandteil von verschiedenen Verschlüsselungsverfahren, wie beispielsweise dem Temporal Key Integrity Protocol (TKIP).

Prüfsummen

Prüfsummen werden verwendet um Änderungen an Daten zu erkennen, die entweder durch technische Störeinflüsse oder absichtliche Manipulation auftreten können.

Eine Manipulation ist feststellbar, wenn die berechnete Prüfsumme der geänderten Daten sich von der Prüfsumme der Originaldaten unterscheidet. Die Eignung verschiedener Hashfunktionen zur Prüfsummenberechnung hängt von der Kollisionswahrscheinlichkeit der berechneten Prüfsummen ab. Eine Kollisionsfreiheit ist nur möglich, wenn der Prüfsummenwertebereich größer gleich dem Wertebereich der Eingabedaten ist.

Wenn die Prüfsumme vor gezielten Manipulationen der Daten schützen soll, wird eine kryptographische Hashfunktion verwendet, welche unumkehrbar ist.

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 getauschten 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.

Definition einer Hashfunktion

Eine Abbildung $h:K\rightarrow S$ heißt Hashfunktion, wenn $|K|\geq \ |S|$ gilt. Insbesondere liefert $h$ eine Hashtabelle der Größe $|S|$. $S$ heißt auch die Menge der Schlüssel. Die Menge $K$ repräsentiert die Daten, die gehasht werden sollen. Typischerweise wird die Menge der Schlüssel als Anfangsstück der natürlichen Zahlen gewählt: $S\subseteq \left\{0,\ldots ,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 bzw. möglichst Gleichverteilung der Hashwerte
• Datenreduktion – Der Speicherbedarf des Hashwertes soll deutlich kleiner sein als jener der Nachricht.
• Chaos – Ähnliche Quellelemente 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 soll unmöglich sein, jedes Ergebnis (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 möglichst nur einmal lesen müssen.
• ordnungsserhaltend - 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 Datenbankanwendungen ist dies dafür genau erwünscht.

Zusätzliche Forderungen für kryptographisch sichere Hashfunktionen

In der Kryptographie werden Hashfunktionen bzw. Familien von Hashfunktionen danach beurteilt, welchen Formen von Angriffen sie widerstehen können, d.h. welche Angriffe komplexitätstheoretisch schwierig sind.

• Der Urbild-Angriff auf eine Hashfunktion h besteht darin, zu gegebenem Hash y eine Zeichenkette x mit $h(x)=y$ zu finden. Funktionen, welche diesem Angriff widerstehen, heißen Einwegfunktionen. Urbildresistenz gilt als schwächste Sicherheitseigenschaft von Hashfunktionen.

• Der Zweites-Urbild-Angriff auf eine Hashfunktion h besteht darin, zu gegebener Zeichenkette $x_{1}$ eine weitere Zeichenkette $x_{2}\neq x_{1}$ zu ermitteln, welche denselben Hash besitzt ($h(x_{2})=h(x_{1})$).

• Beide Angriffstypen lassen sich auch für Familien $(h_{a})_{a}$ von Hashfunktionen definieren: in diesem Fall besteht der Urbild-Angriff darin, zu gegebenem a und gegebenem y ein x mit $h_{a}(x)=y$ zu konstruieren, und der Zweites-Urbild-Angriff darin, zu gegebenen $a,x_{1}$ eine weitere Zeichenkette $x_{2}\neq x_{1}$ zu ermitteln, welche unter $h_{a}$ denselben Hash besitzt ($h_{a}(x_{2})=h_{a}(x_{1})$). Der Angriff auf eine ganze Hashfamilie ist u.U. schwieriger als auf eine einzelne Hashfunktion, da für alle h_a ein gemeinsamer Algorithmus gefunden werden muss. Deshalb impliziert zwar (Zweites-)Urbild-Resistenz für jedes einzelne $h_{a}$ (Zweites-)Urbild-Resistenz für die gesamte Familie, aber nicht umgekehrt.

• Der Geburtstagsangriff auf eine Familie $(h_{a})_{a}$ von Hashfunktionen besteht darin, zu gegebenem a zwei verschiedene Zeichenketten $x_{1}\neq x_{2}$ mit $h_{a}(x_{2})=h_{a}(x_{1})$ zu konstruieren. Familien, welche diesem Angriff widerstehen, heißen kollisionsresistent. Kollisionsresistente Familien sind stets auch urbild- und zweites-Urbild-resistent. Üblicherweise verwendet man deshalb in der Kryptographie kollisionsresistente Familien von Hashfunktionen.

Hash-Algorithmen

Bekannte

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

Allgemeine

• Adler-32
• FNV
• Hashtabelle
• Merkles Meta-Verfahren
• Modulo-Funktion
• Parität
• Prüfsumme
• Prüfziffer
• Quersumme
• Salted Hash
• Zyklische Redundanzprüfung

Gitterbasierte

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

Algorithmen in der Kryptographie

• MD2, MD4, MD5
• SHA
• RIPEMD-160
• Tiger
• HAVAL
• Whirlpool
• LM-Hash
• NTLM

Angriffe

Man unterscheidet Kollisionsangriffe und die wesentlich aufwändigeren Preimage-Angriffe. Bei einem Kollisionsangriff geht es darum, zwei beliebige Eingaben zu finden, die sich auf den gleichen Hashwert abbilden lassen. Bei einem Preimage-Angriff muss hingegen zu einer vorgegebenen Eingabe eine andere Eingabe mit gleichem Hashwert gefunden werden.

Siehe auch

• Vergleich von Programmen für Prüfsummen und Hashfunktionen

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-Datei; 471 kB)
• Konstruktion von Hashfunktionen (PDF-Datei; 841 kB)