Anforderungen

Umrechnung (Einweg) einer beliebig langen Bit-Kette in eine (kurze) von vorgegebener Länge, also eine Funktion

h: S^* ® Sⁿ

(wobei S das Alphabet der Bits 0 und 1 ist) mit folgenden Eigenschaften:

Effizienz:

Die Funktion muss schnell zu berechnen sein.

Pseudozufälligkeit:

Ähnliche Texte sollen völlig unterschiedliche Hash-Werte ergeben.

Einweg-Eigenschaft:

Es darf nicht effizient möglich sein, zu einem gegebenen Hash-Wert einen passenden Text zu finden.

Kollisionsfreiheit:

Es darf nicht effizient möglich sein, zwei Texte mit gleichem Hash-Wert zu finden.

Zum folgenden siehe den Abschnitt Das Geburtstagsphänomen in der Kryptologie-Vorlesung.

Einweg-Eigenschaft

Um mit Wahrscheinlichkeit ³ ½ einen vorgegebenen Hash-Wert der Länge l zu treffen, sind

» 0.7 × 2^l » 2^(l-0.5)

Resistenz gegen vollständige Suche nach einem Urbild erfordert also eine Hash-Länge von mindestens 90 Bit.

Kollisionsfreiheit

Um mit Wahrscheinlichkeit ³ ½ eine Kollision zwischen zwei Hash-Werten der Länge l zu finden, sind

» 1.2 × 2^l/2 » 2^0.3+l/2

Kollisionsfreiheit erfordert also eine Hash-Länge von mindestens 2×90 = 180 Bit.

Anwendungen

• Vereinfachung der digitalen Signatur (s. später)
• Ablage-Nummern (Suchen ohne Index in Datenbanken)
• Schlüssel: Umwandlung von leicht zu merkenden Passwörtern oder Passphrasen (»Vom Eise befreit sind Strom und Bäche«) in schwer zu merkende Schlüssel technischer Natur (»AF 03 D4 7C 91 3A BB 29«)
• Zufallserzeugung: Extraktion oder Verdichtung der Entropie.

Beispiele

Die Länge der Hash-Werte wird in Bit angegeben. Wegen des »Geburtstagsphänomens« ist die Sicherheitsgrenze knapp 2× der nötigen Schlüssellänge für starke symmetrische Verfahren.

Cipher Block Chaining (CBC):

Verwendet wird eine beliebige Block-Verschlüsselungsfunktion f (z. B. DES) mit beliebigem (öffentlich bekannten) Schlüssel und Initialwert.

MD2, MD4, MD5:

Von Rivest (MIT/RSA) 1990/1991 entwickelte, sehr effiziente Verfahren (128 Bit). Ihre Sicherheit ist seit 1995 ins Wanken geraten.

RIPEMD-128, -160:

Von Preneel, Bosselaers und Dobbertin im RIPE-Projekt 1992 ff. entwickelt, 128 bzw. 160 Bit.

SHA-1:

NIST, 160 Bit.

SHA-2:

NIST, 256, 384 oder 512 Bit.

Umwandlungstricks für kryptographische Basisfunktionen

Folgende Aussagen über die Existenz von kryptographischen Basisfunktionen sind im komplexitätstheoretischen Sinne im wesentlichen äquivalent:

1. Es gibt eine symmetrische Chiffre, die sicher vor Angriffen mit bekanntem Klartext ist.
2. Es gibt eine Einweg-Funktion.
3. Es gibt eine Hash-Funktion.
4. Es gibt einen perfekten Zufallsgenerator.
5. P ungleich NP.

Die Äquivalenz von D und E ist ein Satz von Yao.

Von D nach A kommt man durch die Bitstrom-Verschlüsselung. Umgekehrt erzeugt man aus der symmetrischen Chiffre F eine Zufallsfolge x_i = F(x_i-1, k), wobei der Schlüssel k als interner Parameter des Zufallsgenerators geheimgehalten wird.

Der Weg von A nach B wurde schon hier gezeigt. Von B nach A (MDC = Message Digest Cryptography) kommt man z. B. nach E. Bachus so:

F(m, k) = f(m) XOR f(k).

Von A nach C kommt man, wie oben erwähnt, durch Cipher Block Chaining (CBC) (wobei die Kollisionsfreiheit evtl. nur mit Zusatzbedingungen erfüllbar ist).

Von C nach B braucht man nur die Hash-Funktion auf Zeichenketten der Länge des Hash-Wertes einzuschränken. (Auch hier ist eigentlich eine genauere Betrachtung nötig, wenn man die Bijektivität der Einweg-Funktion haben will.)

Moral

• Wer Kryptographie verbieten will, muss auch Hash-Funktionen und Zufallsgeneratoren verbieten.
• Wer Kryptographie unmöglich machen will, muss P = NP beweisen.