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
- »Gewöhnliche Prüfsumme« h (in der Codierungstheorie):
- Nachricht m aus S* wird
übertragen, zusammen mit h(m).
- Tritt ein Übertragungsfehler auf, passt h(m)
nicht mehr zu m.
- D. h., der Fehler wird beim Empfänger entdeckt.
- Fall »Murphy« – Schutz gegen zufällige Fehler.
- »Kryptographische Prüfsumme«:
- Nachricht m aus S* wird
übertragen.
- Hashwert h(m) wird übertragen (auf sicherem Kanal,
z. B. verschlüsselt).
- Ändert ein Angreifer m, passt h(m) nicht
mehr zu m.
- Fall »Satan« – Schutz gegen böswillige Änderungen.
Das kann man realisieren durch einen
MAC (= Message Authentication Code)
- Verschlüsselte (oder schlüsselabhängige) Hash-Funktion,
- schützt die Integrität einer Nachricht.
- Sender und Empfänger benötigen gemeinsamen geheimen Schlüssel.
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
- Vereinfachung der digitalen Signatur
(s. später).
- Schlüssel: Umwandlung von leicht zu merkenden Passwörtern
oder Passphrasen
(z. B. »Vom Eise befreit sind Strom und Bäche«) in schwer zu merkende
Schlüssel technischer Natur
(»AF 03 D4 7C 91 3A BB 29« - dieser Schlüssel ist dann
pseudozufällig).
- »Fingerprint« von Schlüsseln (z. B. bei PGP
oder SSL).
- Zufallserzeugung: Extraktion oder Verdichtung der
Entropie (s. später).
- Klassische nicht-kryptologische Anwendung: Ablage-Kennzeichen
(Suchen ohne Index in Datenbanken).
Beispiele
- Cipher Block Chaining (CBC):
- Verwendet wird eine beliebige Block-Verschlüsselungsfunktion
f (z. B. DES)
- Version 1: mit beliebigem (öffentlich bekannten) Schlüssel und
Initialwert.
- Version 2: der klassische MAC; ebenso, aber mit geheimem
Schlüssel.
Der letzte Block des Cipher Block Chainings ergibt den Hashwert.
- MD2,
MD4,
MD5:
- Von Rivest (MIT/RSA) 1990/1991 entwickelte, sehr effiziente
Verfahren (128 Bit).
- Lange Zeit als Standard-Hashfunktionen im Gebrauch.
- Ihre Sicherheit ist seit 1995
ins Wanken geraten
(systematisch Kollisionen gefunden).
- Siehe auch
hier
[Stevens, Lenstra, de Weger]
- 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.
- Bezeichnung: SHA-256 usw. [Es gibt auch SHA-224.]
- Passend zu AES mit 128, 192 oder 256 Bit.
- Standard-Dokument: FIPS 180-2 »Secure Hash Standard«.
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.