Hashfunktion

Beispiel einer Hashfunktion (hier SHA-1), links drei unterschiedliche Eingabewerte, rechts die entsprechenden Hashcodes- Auf den meisten unixartigen Systemen lassen sich diese Beispiele mit echo -n "Fox" | sha1sum etc. nachvollziehen

Eine Hashfunktion oder Streuwertfunktion ist eine Abbildung, die zu jeder Eingabe aus einer oft sehr großen Quellmenge eine Ausgabe aus einer kleineren Zielmenge erzeugt, den sogenannten Hashcode (oder Hashwert).

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

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) 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 dazu, schnell die Speicherstelle der angefragten Daten zu finden, ohne 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 der Kryptographie ist es zusätzlich wünschenswert, dass es nach praktischen Maßstäben nicht möglich ist, künstlich Kollisionen zu erzeugen (Kollisionssicherheit). In Sonderfällen kann auch eine perfekte (also kollisionsresistente) Hashfunktion ermittelt werden.

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 – dem ersten Buchstaben 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 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.

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 „Hashfunktion“ 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 Akten im Ordner mit dem Buchstaben „S“, während der Ordner „Q“ leer bleibt.

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.

Beispiel des Logins in eine passwortgeschützte 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 oder eine Kollision rückzuschließen (also eine Zeichenkette zu finden, die denselben Hashwert liefert wie das eigentliche Passwort). 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 sensitive), dann gibt es bereits 840 Billiarden Möglichkeiten (1 Billiarde = 10¹⁵). Ein Computer, der zu 10.000 Passwörtern pro Sekunde den Hash berechnen kann, würde fast 3 Millionen Jahre brauchen, um alle möglichen Kombinationen durchzutesten (bei verbreiteten Hash-Funktionen sind inzwischen jedoch oft Millionen von Passwörtern pro Sekunde möglich). Anders verhält es sich, wenn das Passwort ein bekanntes Wort, etwa 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.^[1]

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, also möglichst eine Gleichverteilung der Hashwerte auf die erwarteten Eingabewerte.
• Datenreduktion – 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.
• ordnungserhaltend – 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 und 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₁ eine weitere Zeichenkette $x_2 \neq x_1$ zu ermitteln, welche denselben Hash besitzt (h(x₂) = h(x₁)).
• 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₁ eine weitere Zeichenkette $x_2 \neq x_1$ zu ermitteln, welche unter h_a denselben Hash besitzt (h_a(x₂) = h_a(x₁)). 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₂) = h_a(x₁) 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
• Kuckucks-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
• Schnelle Fourier-Transformation (FFT Hashfunktion^[2])
• LASH^[3]

Algorithmen in der Kryptographie

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

Angriffe

Man unterscheidet Kollisionsangriffe und die wesentlich aufwendigeren 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.

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)

Einzelnachweise

1. ↑ Albrecht Beutelspacher, Heike Neumann, Thomas Schwarzpaul: Kryptografie in Theorie und Praxis: mathematische Grundlagen für Internetsicherheit, Mobilfunk und elektronisches Geld. 2. Auflage. Vieweg + Teubner, 2010, ISBN 978-3-8348-0977-3, S. 175-194.
2. ↑ C.P. Schnorr, Serge Vaudenay: Parallel FFT-hashing. In: Fast Software Encryption, pp 149–156, 1993
3. ↑ K. Bentahar, D. Page, J.H. Silverman, M.-J. O. Saarinen, N.P. Smart: LASH. 2^nd NIST Cryptographic Hash Workshop, 2006