Hash-Funktion

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Eine Hash-Funktion bzw. Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe aus einer im Allgemeinen kleineren Zielmenge erzeugt. Diese Hash-Werte bzw. Streuwerte sind meist skalare Werte aus einer Teilmenge der natürlichen Zahlen. Ein Hash-Wert wird auch als Fingerprint bezeichnet. Denn wie ein Fingerabdruck einen Menschen nahezu eindeutig identifiziert, ist ein Hash-Wert eine nahezu eindeutige Kennzeichnung einer übergeordneten Menge.

Hash-Funktionen 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. Hash-Funktionen werden in Hashtabellen, der Kryptologie und der Datenverarbeitung verwendet. Eine gute Hash-Funktion zeichnet sich dadurch aus, dass sie für die Eingaben, für die sie entworfen wurde, wenig Kollisionen erzeugt. Dadurch können die meisten Eingaben anhand ihres Hash-Wertes unterschieden werden.

Hash-Algorithmen sind darauf optimiert, so genannte Kollisionen zu vermeiden. Eine Kollision tritt dann auf, wenn zwei verschiedenen Datenstrukturen derselbe Schlüssel zugeordnet wird. Da der Hash-Wert in der Praxis meist kürzer als die originale Datenstruktur ist, sind solche Kollisionen prinzipiell unvermeidlich, deshalb muss es Verfahren zur Kollisionserkennung geben.

Der Name „Hash-Funktion“ stammt vom englischen Wort „to hash“, das sich als „zerhacken“ übersetzen lässt. Der deutsche Name lautet Streuwertfunktion. Speziell in der Informatik verwendet man auch die Bezeichnung Hash-Algorithmus, da die Berechnung von Funktionen mittels Algorithmen durchgeführt wird.

Inhaltsverzeichnis

1 Anschauliche Erklärung
2 Anwendungen
3 Definition einer Hash-Funktion
4 Kriterien für eine gute Hash-Funktion
- 4.1 Zusätzliche Forderungen für kryptographisch sichere Hash-Funktionen
5 Bekannte Hash-Funktionen
6 Allgemeine Hash-Algorithmen
7 Hash-Algorithmen in der Kryptographie
8 Attacken
9 Weblinks

[Bearbeiten] Anschauliche Erklärung

Bei einer Hash-Funktion geht es meistens darum, zu einer Eingabe beliebiger Länge (zum Beispiel ein Text) eine kurze, möglichst eindeutige Identifikation fester Länge (den Hash-Wert des Textes) zu finden.

Das ist etwa dann sinnvoll, wenn man zwei große, ähnliche Dateien vergleichen will: Anstatt die 25 Seiten eines Textes durchzusehen, ob auch wirklich jeder Buchstabe gleich ist, ist anhand der kurzen Hash-Werte der beiden Dokumente sofort zu sehen, ob diese (höchstwahrscheinlich) gleich oder (mit Sicherheit) verschieden sind.

Praktische Anwendung ist z.B. das Herunterladen einer Datei, zu der der Autor den Hash-Wert angegeben hat: Um zu prüfen, ob es Übertragungsfehler gegeben hat, braucht die Datei nicht etwa ein zweites Mal komplett heruntergeladen werden, sondern es muss nur der Hash-Wert gebildet und mit der Angabe des Autors verglichen werden.

Ein Beispiel für eine einfache Hash-Funktion für Zahlen wäre, von der Zahl (Eingabe) die letzte Ziffer als Hash-Wert zu benutzen. Somit würde 97 den Wert 7 ergeben, 153 würde zu 3, selbst eine große Zahl wie 238.674.991 würde verkleinert zu 1. Der Wertebereich der unendlich großen Quellmenge würde also auf den Wertebereich von 0-9 abgebildet.

Weil bei einer Hash-Funktion der Wertebereich meist kleiner als der der Quellmenge ist, können mehrere verschiedene Eingaben die gleiche Ausgabe erzeugen. Das leuchtet bei unserem Beispiel unmittelbar ein: 11 und 21 liefern beide 1. Das ist die Schwachstelle von Hash-Funktionen und wird als Kollision bezeichnet. Durch die Wahl einer geeigneten Funktion kann die Wahrscheinlichkeit solcher Kollisionen deutlich vermindert werden und man gewinnt für die praktische Anwendung eine hinreichende Sicherheit. Jedoch ist die Wahrscheinlichkeit für Kollisionen sehr groß, wenn schon einige Daten gespeichert wurden, vgl. auch Geburtstagsparadoxon. Man muss sich für den Fall einer Kollision somit auch immer eine Strategie der Kollisionsauflösung überlegen.

Eine weitere Schwachstelle der o. a. Beispielfunktion ist, dass nur die Änderung der letzten Stelle eine Änderung des Hash-Wertes ergibt, ein Zahlendreher oder eine fehlende Ziffer weiter vorn würde stets unentdeckt bleiben.

[Bearbeiten] Anwendungen

Hashfunktionen haben verschiedene Anwendungsfelder. Dabei lassen sich drei grosse Gebiete unterteilen:

Datenbanken
Kryptologie
Prüfsummen

[Bearbeiten] 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.

[Bearbeiten] Kryptologie

In der Kryptologie werden Hashfunktionen zum Signieren von Dokumenten oder zum Erzeugen von Einweg-Verschlüsselungen verwendet.

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

[Bearbeiten] 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.

Absichtliche Manipulationen sind jedoch nur begrenzt feststellbar. Mindestanforderung an die Hashfunktion sind hierbei die Kollisionsfreiheit und die Unumkehrbarkeit.

[Bearbeiten] Beispiele

Hash-Werte haben unter anderem bei P2P-Anwendungen aus verschiedenen Gründen eine wichtige Aufgabe. Die Hash-Werte 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 Hash-Funktionen bei denen für kleinere Teile einer Datei der Hash-Wert berechnet wird und dann aus diesen Werten ein Gesamtwert (z.B. Tiger-Tree Hash bei Gnutella G2, Shareaza, Direct Connect).

Das Auffinden von Dateien aufgrund des Hash-Wertes 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 Hash-Funktionen zum Erzeugen von Session-IDs genutzt, indem unter Verwendung von wechselnden Zustandswerten (wie Zeit, IP-Adresse) ein Hash-Wert berechnet wird.

[Bearbeiten] Definition einer Hash-Funktion

Eine Abbildung $h: K \rightarrow S$ heißt Hash-Funktion, 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|}{m}$ liefert uns den Belegungsfaktor.

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

[Bearbeiten] Kriterien für eine gute Hash-Funktion

Datenreduktion

Der Speicherbedarf des Hash-Wertes soll deutlich kleiner sein als der der Nachricht.

Chaotisch

Ähnliche Quellelemente sollen zu völlig verschiedenen Hash-Werten führen. Im Idealfall verändert das Umkippen eines Bits in der Eingabe durchschnittlich die Hälfte aller Bits im resultierenden Hash-Wert.

Surjektiv

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.

[Bearbeiten] Zusätzliche Forderungen für kryptographisch sichere Hash-Funktionen

Kollisionsfreiheit

Es darf nicht effizient möglich sein, zwei Quellelemente mit demselben Hash-Wert zu finden. Andererseits sind Kollisionen bei der Adressberechnung in Datenbanken nicht zu vermeiden, so dass eine entsprechende Behandlungs-Strategie verfügbar sein muss.

Unumkehrbarkeit

Zu der Funktion gibt es keine effizient berechenbare inverse Funktion, mit der es möglich wäre, für ein gegebenes Zielelement ein passendes Quellelement zu finden.

[Bearbeiten] Bekannte Hash-Funktionen

[Bearbeiten] Allgemeine Hash-Algorithmen

[Bearbeiten] Hash-Algorithmen in der Kryptographie

[Bearbeiten] Attacken

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 Hash-Wert abbilden lassen. Bei einem Preimage-Angriff muss hingegen zu einer vorgegebenen Eingabe eine andere Eingabe mit gleichem Hash-Wert gefunden werden.

[Bearbeiten] Weblinks

Hash-Algorithmen

HAVAL | MD2 | MD4 | MD5 | N-Hash | SHA | Snefru | Tiger | RIPEMD-160 | Whirlpool | CRC32 |

Von „http://de.wikipedia.org../../../h/a/s/Hash-Funktion_0a7e.html“

Kategorie: Hash