Einleitung
Eine Hash-Funktion ist eine Funktion, die eine Zeichenfolge beliebiger Länge auf eine Zeichenfolge mit fester Länge abbildet. Die Funktion ist nicht injektiv.
Ursprünglich stammen Hash-Funktionen aus der Datenverwaltung.
Kryptologische Hash-Funktionen haben weitere Eigenschaften. Eine kryptologische Hash-Funktion sollte zumindest eine Einwegfunktion sein.
Hash-Funktionen dienen der Integritätsprüfung von Dateien oder Nachrichten. Darüber hinaus werden sie u.a. eingesetzt zum Verschlüsseln von Passwortdateien, bei digitalen Unterschriften, als Zufallszahlengeneratoren oder zur Konstruktion von Blockchiffren.
Hash-Funktionen werden klassifiziert in schlüssellose und schlüsselabhängige Hash-Funktionen. Die letzteren werden auch Message Authentication Codes (MACs) genannt. Schlüssellose Hash-Funktionen (kurz Hash-Funktionen) werden ferner unterteilt in One-Way Hash Functions (OWHFs) und Collision Resistant Hash Functions (CRHFs).
Eine OHWF erfüllt folgende Bedingungen:
1. Einwegfunktion: zu einem gegebenen Ausgabewert h(x)=y ist es praktisch unmöglich einen Eingabewert x zu finden (preimage resistance).
2. schwache Kollisionsresistenz: es ist praktisch unmöglich für einen gegebenen Wert x ein davon verschiedenes x’ zu finden, der denselben Hash-Wert h(x)=h(x')=y ergibt (2nd-preimage resistance).
Für eine CRHF gilt zusätzlich:
3. starke Kollisionsresistenz: es ist praktisch unmöglich zwei verschiedene Eingabewerte x und x’ zu finden, die denselben Hash-Wert ergeben (collision resistance).
Außerdem kann man eine Beinahe-Kollisionsresistenz fordern (near-collision resistance). Hierbei sollte es schwierig sein, zu zwei verschiedenen Eingabewerten x und x’ Hash-Werte h(x) und h(x’) zu finden, die sich nur in wenigen Bits unterscheiden.
Konstruktion
Die meisten Hash-Funktionen sind iterierte Kompressionsfunktionen. Die eingegebene Nachricht M wird in Blöcke fester Länge geteilt und mit zusätzlichen Bits aufgefüllt, so dass die Eingabelänge ein ganzzahliges Vielfaches der Blocklänge beträgt. Die Kompressionsfunktion hat als Input einen Nachrichtenblock und den Output der vorherigen Nachrichtenblöcke. Der Hash-Wert der gesamten Nachricht ist der Hash-Wert des letzten Blocks:
H(0)=IV
H(i)=f(M(i),H(i-1), i=1,2,….,t
h(M)=H(t)
IV bezeichnet initial value, einen Startwert.
Iterierte Hash-Funktionen basieren entweder auf Blockchiffren oder auf algebraischen Strukturen oder sind speziell entwickelte Hash-Algorithmen.
Spezielle Hash-Algorithmen
Zu diesen gehören z.B. die MD4-Familie einschließlich SHA und RIPEMD.
Hash-Funktionen, die auf einer Block-Chiffrierung basieren
Dabei unterscheidet man Hash-Funktionen, deren Hash-Wert dieselbe Länge hat wie die Blocklänge und jene, deren Hash-Wert die doppelte Blocklänge hat.
- I) Hash-Länge gleich Blocklänge
Drei verbreitete Konstruktionen sind die
Matyas-Meyer-Oseas-Variante
Davies-Meyer-Variante
Miyaguchi-Preneel-Variante
wobei E die Verschlüsselung mit einem Blockchiffresystem ist, M(i) die Nachrichtenblöcke und H(i) die Hash-Werte.
- II) Hash-Länge mit doppelter Blocklänge
Dazu zählen MDC-2 und MDC-4. Sie bestehen im wesentlichen aus der zwei- bzw. vierfachen Anwendung der Matyas-Meyer-Oseas-Konstruktion.
C. Hash-Funktionen, die auf algebraischen Strukturen basieren
MASH (Modular Arithmetic Secure Hash) verwendet einen RSA-ähnlichen Modulus n=pq, mit p und q Primzahlen. Die Kompressionsfunktion ist im Kern:
A: Konstante,
: excl. oder,
: incl oder
Angriffe
Angriffe gegen Hash-Funktionen können allgemeiner Art sein, und nur von der Bit-Länge des Hash-Werts abhängen und den Hash-Algorithmus als Black-Box behandeln. Sie können sich andererseits gegen die Kompressionsfunktion richten. Bei Hash-Funktionen, die auf einem Block-Chiffre basieren, kann ein Angriff gegen die zugrundeliegende Block-Chiffrierung erfolgen. Überdies sind Angriffe auf die Implementierung des Hash-Algorithmus möglich.
Black-Box Angriffe
- I) Raten (2nd Preimage)
Der Angreifer wählt zufällig eine Nachricht und vergleicht deren Hash-Wert mit dem einer gegebenen Nachricht. Die Erfolgsrate bei diesem Vorgehen liegt bei (2)^n für einen n-Bit langen Hash-Wert.
- II) Geburtstagsangriff (Kollision)
Der Angreifer erzeugt v1 Variationen einer echten Nachricht und v2 Variationen einer gefälschten Nachricht. Er ermittelt die Hash-Werte h(v1) und h(v2) und sucht nach einer Kollision. Eine Kollision ist nach 2^(n/2) Versuchen zu erwarten.
Angriffe auf die Kompressionsfunktion
- I) Meet-in-the-Middle
Der Angreifer erzeugt v1 Variationen der ersten Hälfte einer gefälschten Nachricht und v2 Variationen der zweiten Hälfte. Er berechnet die Hash-Werte vorwärts beim Startwert IV beginnend und rückwärts vom Hash-Resultat aus und versucht eine Kollision am Angriffspunkt zu finden. D.h. er muß die Kompressionsfunktion effizient invertieren können: gegeben H(i+1) ein Paar (H(i), M(i+1)) finden, so dass gilt f(H(i), M(i+1))=H(i+1).
- II) Correcting Block Attack
Der Angreifer ersetzt alle Blöcke einer Nachricht bis auf einen - etwa den ersten. Anschließend legt er diese Variable so fest, dass sie im Laufe der Verkettung den gewünschten Gesamt-Hash-Wert liefert.
- III) Fixed Point Attack
Der Angreifer sucht nach einem H(i-1) und M(i), so dass f(M(i), H(i-1))=H(i-1). In diesem Fall kann er an diesem Punkt Nachrichtenblöcke einfügen, ohne den Hash-Wert zu ändern.
- IV) Differentielle Kryptanalyse
Hierbei werden Eingabedifferenzen und die korrespondierenden Ausgabedifferenzen untersucht. Eine Differenz von Null entspricht dann einer Kollision.
Angriffe auf die Blockchiffrierung
Schwachstellen eines Blockchiffrierverfahrens, die solange das Verfahren zur Verschlüsselung verwendet wird, eigentlich irrelevant sind, können bedeutende Auswirkungen haben, wenn es zur Konstruktion eines Hash-Verfahrens herangezogen wird. Diese wären z.B. schwache Schlüssel oder eine Komplementäreigenschaft.
Quellen
A.J.Menezes, P.C.van Oorschot, S.A.Vanstone. Handbook of Applied Cryptography. CRC Press, 1996, S.321-384.
B.Preneel. "Cryptographic Primitives for Information Authentication - State of the Art"", State of the Art in Applied Cryptography, LNCS 1528, Springer-Verlag, 1998, S.49-104.
D.R.Stinson. Cryptography - Theory and Practice. Chapman&Hall/CRC, 2002, S.117-154.