Einweg-Hashfunktionen

Hashfunktionen dienen allgemein dazu Daten variabler Länge (z.B. Zeichenketten)
auf Werte fester Länge (bsp. ganzzahlige Feldindexe) abzubilden.

Für die Kryptologie sind primär Einweg-Hashfunktionen relevant,
also jene, die sich zwar leicht berechnen, aber nur sehr schwer invertieren
lassen.

Ein durch eine solche Funktion bestimmter Hashwert wird auch als Message
Digest (MD) bzw. Fingerabdruck (fingerprint) bezeichnet.

Eine Einweg-Hashfunktion H zeichnet sich durch folgende Eigenschaften
aus:

• Der Hashwert H(x) einer Bitfolge x läßt
  sich relativ einfach, d.h. mit wenig Rechenaufwand bestimmen.
  
  Das Argument der Hashfunktion, also die Bitfolge x, wird auch
  als preimage bezeichnet.

• Es ist rechnerisch nicht möglich, zu einem vorgegebenen Hashwert
  z eine Nachricht x zu generieren, so daß H(x) = z
  gilt. Anders ausgedrückt, es darf keinen (wesentlich) effektiveren
  Weg zur Ermittlung von x geben, als alle in Frage kommenden
  Bitfolgen durchzuprobieren, bis man eine findet, die den Hashwert
  z besitzt.
  
  Diese Eigenschaft wird auch als preimage resistance bezeichnet.

• Es ist rechnerisch ebenfalls nicht möglich, zu einer vorgegebenen
  Nachricht eine zweite zu finden, die denselben Hashwert wie die erste
  hat.
  
  Hierfür findet man in der Literatur den Begriff second preimage
  resistance bzw. 2nd-preimage resistance.

Für bestimmte Zwecke wird zusätzlich die Kollisionsresistenz (collision resistance)
gefordert, die besagt, daß es rechnerisch unmöglich ist, eine
Kollision, d.h. zwei beliebige unterschiedliche Nachrichten zu finden,
die denselben Hashwert haben, obwohl natürlich klar ist, daß
es viele davon gibt, sobald deutlich mehr Nachrichten als Hashwerte existieren.

Verschiedene Verfahren :

• MD2
  
  verarbeitet Nachrichten die aus beliebig vielen 8-Bit-Bytes bestehen.
  
  Erzeugt 128 Bit lange Hashwerte.
  
• MD4
  
  verarbeitet Nachrichten die aus beliebig vielen Bits bestehen.
  
  Erzeugt 128 Bit lange Hashwerte.
  
  3 Runden
  
• MD5 Message Digest Algorithm (R. Rivest)
  
  verarbeitet Nachrichten die aus beliebig vielen Bits bestehen.
  
  Erzeugt 128 Bit lange Hashwerte.
  
  Ist optimiert für 32-Bit Maschinen
  
  4 Runden
• RIPEMD-160
  
  Erzeugt 160 Bit lange Hashwerte
  
  Relativ neu >> 1996
  
  Komplett offenes Design
  
• SHA-1 (Secure Hash Algorithm) entworfen von NIST/NSA
  
  Verarbeitet Nachrichten die weniger als 2⁶⁴ Bit lang sind.
  
  Erzeugt 160 Bit lange Hashwerte.
  
  MD4 Familie
  
• Tiger
  
  Erzeugt 192/160/128 Bit lange Hashwerte
  
  Relativ neu >> 1995
  
  Frei zu nutzen, keine MD4 Familie
  

Anwendungsgebiete :

• Sichere Verdichtung (Kompression) von speziell langen Nachrichten
  die signiert werden sollen.
• Authentifizierung, Passwortschutz. Es werden nur noch die Hashwerte
  der Passworte lokal gespeichert.
• Integritätssicherung von Dateien (Fingerabdrücke) Bsp. Tripwire
• Vergleich ob Dokumente gleich sind (Hashwertvergleich am Telefon)
  
• Erstellung kryptografischer Prüfsummen (HMAC)
• Pseudzufallsgeneratoren
• Einmal-Passwortsystem (es wird nur der Hashwert verglichen)

Ein interessantes Beispiel ist HMAC.

Hier werden Hashfunktionen anstatt Verschlüsselungsverfahren benützt
um MAC's zu berechnen.

Gründe

• Software-Realisierungen von Einweg-Hashfunktionen sind wesentlich
  schneller als entsprechende Implementierungen von Verschlüsselungsalgorithmen,
• letztere sind z.T. patentiert (z.B. IDEA, RSA) und
• unterliegen im Gegensatz zu Hashfunktionen oft staatlichen Restriktionen
  (z.B. einem Exportverbot).