Channel Security

Normale Hashfunktionen sind den meisten Lesern wahrscheinlich schon bekannt, z.B. in Form der in Datenbanken genutzten Hashtabellen. Vereinfacht ausgedrückt berechnet eine Hashfunktion H(M) aus einer beliebig langen Eingabe M, z.B. einem Text, einen möglichst eindeutigen Hashwert h fester Länge, z.B. eine Zahlen-Buchstaben-Kombination: h = H(M). In der Kryptographie kommt hinzu, dass es nicht effizient möglich sein darf, zu einem gegebenen Hashwert eine passende Eingabe zu berechnen. Der Hashwert wird auch als Fingerprint (Fingerabdruck) der Eingabe bezeichnet.

1. Anforderung an eine Hashfunktion:
Aus einer großen Eingabe wird effizient eine kleine Ausgabe berechnet:
Zu gegebenen M ist es leicht, h = H(M) zu berechnen.

Allgemein wird von Hashfunktionen gefordert, dass sich die Ergebnisse für verschiedene Eingaben mit ausreichend großer Wahrscheinlichkeit unterscheiden: Die Ergebnisse sollen möglichst gleichmäßig auf den definierten Wertebereich verteilt sein. Insbesondere sollen sich die Ausgabewerte für ähnliche Eingabewerte deutlich unterscheiden.

2. Anforderung an eine Hashfunktion:
Ähnliche Eingaben führen zu verschiedenen Ausgaben.

In der Kryptographie kommt hinzu, dass es nicht effizient möglich sein darf, zu einem gegebenen Hashwert eine passende Nachricht zu berechnen. Die entsprechenden Funktionen werden als Einweg-Hashfunktionen bezeichnet. Die englische Originalbezeichnung 'one-way' wurde da leider zu wortgetreu übersetzt, besser wäre 'Einbahn' wie bei der Einbahnstraße gewesen: Die Funktion kann nur in eine Richtung berechnet werden, sie wird ja nicht nach einmaligen Gebrauch unbrauchbar.

3. Anforderung an eine Einweg-Hashfunktion:
Zu gegebenen h ist es schwer, ein M mit H(M) = h zu berechnen.

Außerdem darf es nicht effizient möglich sein, zu einer gegebenen Eingabe eine weitere Eingabe mit gleichem Hashwert zu finden.

4. Anforderung an eine Einweg-Hashfunktion:
Zu gegebenen M ist es schwer, ein anderes M' mit H(M) = H(M') zu berechnen.

Zwei Eingabewerte mit gleichem Hashwert werden als Kollision bezeichnet. Da die Ausgabemenge kleiner als die Eingabemenge ist, muss es zwangsläufig zu Kollisionen kommen. Eine Hashfunktion wird daher als kollisionsfrei (manchmal auch passender als kollisionsresistent) bezeichnet, wenn sich Kollisionen praktisch nicht berechnen lassen:

5. Anforderung an eine kollisionsfrei Einweg-Hashfunktion:
Es ist schwer, zwei beliebige M und M' (M ≠ M') mit H(M) = H(M') zu finden.

Eine gute Übersicht über die Grundlagen von Hashfunktionen gibt die Doktorarbeit 'Analysis and Design of Cryptographic Hash Functions' (PDF) von Bart Preneel.

Eine einfache Einweg-Hashfunktion: MD2
MD2 wurde 1988 von Ronald L. Rivest für 8-Bit-Rechner entwickelt und ist in RFC 1319 standardisiert. Sie berechnet aus einer beliebig langen Eingabe einen 128 Bit langen Hashwert. Ihr Vorteil ist ihre einfache Implementierung. Da es bereits mögliche Angriffe gibt, sollte sie jedoch nicht mehr verwendet werden. Als Beispiel ist sie aber immer noch gut geeignet.

1. Fülle die Nachricht M mit i Bytes mit dem Wert i auf, sodass ihre Länge ein Vielfaches von 16 ist. Die Länge von M sei N.
   Ist die Nachricht z.B. 5 Byte lang, werden 11 Byte mit dem numerischen Wert 11 angehängt.
2. Berechne eine 16 Byte lange Prüfsumme und hänge sie an die Nachricht an:

    /* Prüfsumme löschen */
    FOR i=0 TO 15 DO
    C[i] := 0
    ENDFOR
    
    L := 0
    
    /* Verarbeiten der 16-Byte-Blöcke */
    FOR i=0 TO N/16 - 1 DO 
    /* Prüfsumme für Block i berechnen: */
    FOR j=0 TO 15 DO
    c := M[i*16 + j]
    C[j] := S[c XOR L]
    L := C[j]
    ENDFOR
    ENDFOR
    

   Die 16 Byte der Prüfsumme werden an die Nachricht M angehängt, die Länge von M ist nun N' = N+16.
3. Initialisiere einen 48 Byte langen Block X mit 0.
4. Komprimiere die Nachricht.

    /* Verarbeiten der 16-Byte-Blöcke */
    FOR i=0 TO N'/16 - 1 DO 
    /* Kopiere Block i nach X*/
    FOR j=0 TO 15 DO
    X[16+j] := M[i*16 + j]
    X[32+j] := (X[16+j] XOR X[j])
    ENDFOR
    
    t := 0
    
    /* Es folgen 18 Runden */
    FOR j=0 TO 17 DO
    FOR k=0 TO 47 DO
    t := (X[k] XOR S[t])
    X[k] := t
    ENDFOR
    t := (t+j) MOD 256
    ENDFOR
    ENDFOR
    

5. Der Hashwert (auch als Message Digest bezeichnet) besteht aus den ersten 16 Byte von X: X[0], .., X[15].
   Die Ausgabe erfolgt meist als 32-stellige Hexadezimalzahl.

Ein Beispiel:

Schon eine minimale Änderung am Text erzeugt einen vollständig anderen Fingerprint:

Aktuellere Hashfunktionen sind z.B. MD4 und MD5, die in der nächsten Folge vorgestellt werden.

Carsten Eilers

About Security – Übersicht zum aktuellen Thema "Kryptographie – Hashfunktionen"

• About Security #102: Hashfunktionen – Einführung
• About Security #103: Hashfunktionen – MD4 und Verwandte
• About Security #104: Hashfunktionen – Sicherheit