2a. Kryptographische Basistechniken

Hash-Funktionen (kryptographische Prüfsummen, Message Digest)


Anforderungen

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

h: S* ---> Sl

mit der Eigenschaft:

Effizienz:
Die Funktion muss schnell zu berechnen sein.

l heißt Länge der Hash-Funktion h.

[Für S nimmt man meistens das Alphabet der Bits 0 und 1 -- natürlich ist die Definition auch über anderen Alphabeten sinnvoll.]

Es gibt auch nicht-kryptographische Hash-Funktionen. Hier interessieren aber die

kryptographischen Anforderungen -

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 (egal mit welchem).

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 × 2l » 2(l-0.5)
Versuche nötig.

Die Resistenz gegen vollständige Suche nach einem Urbild erfordert also eine Hash-Länge von mindestens 90 Bit (siehe Sicherheitsgrenze für vollständige Suche).

Möglicher Angriff:

Zeile 1 _
.
.
.
Zeile i _
.
.
.
Zeile n _
Durch Anfügen von Leerzeichen (durch _ symbolisiert) an einige Zeilen lassen sich aus einem n-zeiligen Text 2n verschiedene Hash-Werte herstellen (verschieden bis auf zufällige Kollisionen).

Falls die Hash-Länge l zu klein ist, kann man aus einem vorliegenden Text-Dokument unauffällig eines mit vorgegebenem Hash-Wert herstellen. (l Zeilen »bearbeiten«, Aufwand 2l.)


Kollisionsfreiheit

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

» 1.2 × 2l/2 » 20.3+l/2
Versuche nötig (Geburtstagsphänomen).

Die Sicherheitsgrenze für Kollisionsfreiheit ist also knapp 2× die nötige Hash-Länge für vollständige Suche ( = Schlüssellänge für symmetrische Verschlüsselung).

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

Möglicher Kollisionsangriff:

Zeile 1 _
.
.
.
Zeile i _
.
.
.
Zeile n _
Durch Anfügen von Leerzeichen an einige Zeilen lassen sich aus einem n-zeiligen Text je 2n verschiedene Hash-Werte herstellen. Zeile 1 _
.
.
.
Zeile i _
.
.
.
Zeile n _

Falls also die Hash-Länge l zu klein ist, kann man aus zwei vorliegenden verschiedenen Text-Dokumenten unauffällig Versionen mit gleichem Hash-Wert herstellen. (Je l/2 Zeilen »bearbeiten«, Aufwand 2×2l/2.)


Anwendungen I

Das kann man realisieren durch einen

MAC (= Message Authentication Code)

Achtung! Ohne Verschlüsselung von h(m) ist ein Angriff durch den Mann in der Mitte möglich:

Nachricht zu m’ und Hashwert zu h(m’) ändern. Der Empfänger hat keine Möglichkeit, die Manipulation zu entdecken.

Bemerkung: Wird die Nachricht sowieso verschlüsselt, ist der MAC überflüssig.

Anwendungen II


Beispiele

Cipher Block Chaining (CBC):
Verwendet wird eine beliebige Block-Verschlüsselungsfunktion f (z. B. DES) Der letzte Block des Cipher Block Chainings ergibt den Hashwert.
MD2, MD4, MD5:
RIPEMD-128, -160:
Von Preneel, Bosselaers und Dobbertin im RIPE-Projekt 1992 ff. entwickelt, 128 bzw. 160 Bit.
SHA-1:
NIST, 160 Bit.
Kollisionen von Wang/Yin/Yu 2005 gefunden.
SHA-2:
NIST 2002 mit 256, 384 oder 512 Bit.
Siehe auch die Seite Secure Hashing des NIST.


Vorlesung Datenschutz und Datensicherheit
Autoren: Klaus Pommerening, Marita Sergl, 31. März 1999; letzte Änderung: 11. Juni 2007.
E-Mail an
Pommerening »AT« imbei.uni-mainz.de.