Skip to content

Verfahren der Kryptographie, Teil 14: Hashfunktionen - Einführung

Normale Hashfunktionen kennen Sie ja vielleicht schon, zum Beispiel in Form der in Datenbanken genutzten Hash-Tabellen.

Vereinfacht ausgedrückt berechnet eine Hashfunktion
H(M)
aus einer beliebig langen Eingabe
M
(zum Beispiel einem Text) einen möglichst eindeutigen Hashwert
h fester Länge
(zum Beispiel 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.

Hashfunktionen allgemein

Aber fangen wir erst mal mit normalen Hashfunktionen an.

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.

Das ergibt die

2. Anforderung an eine Hashfunktion:

Ähnliche Eingaben führen zu verschiedenen Ausgaben.

Hashfunktionen in der Kryptographie

In der Kryptographie kommt hinzu, dass es nicht effizient möglich sein darf, zu einem gegebenen Hashwert eine passende Nachricht zu berechnen. Dies ist die

3. Anforderung an eine kryptographische Hashfunktion:

Zu gegebenen h ist es schwer, ein M mit H(M) = h zu berechnen.

Die entsprechenden Funktionen werden als Einweg-Hashfunktionen bezeichnet.

Die englische Originalbezeichnung "one-way" wurde in diesem Fall 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.

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

Das ergibt die

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:

Damit haben wir die

5. Anforderung an eine kollisionsfreie 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 (bekanntlich das "R" der Erfinder und Namensgeber des RSA-Algorithmus) für 8-Bit-Rechner entwickelt. Der von Ronald L. Rivest geschriebene Sourcecode ist im 1989 veröffentlichten RFC 1115 ("Privacy Enhancement for Internet Electronic Mail: Part III -- Algorithms, Modes, and Identifiers") enthalten, 1992 wurde MD2 in RFC 1319 offiziell beschrieben.

Da bereits seit längerem mögliche Angriffe bekannt sind sollte MD2 nicht mehr verwendet werden. Die IETF hat die Funktion im März 2011 in den "Historic Status" versetzt.

Als Beispiel ist sie aber immer noch gut geeignet.

MD2 berechnet aus einer beliebig langen Eingabe einen 128 Bit langen Hashwert. Der Vorteil von MD2 ist ihre einfache Implementierung.

Der Algorithmus von MD2

S ist eine Permutation der Zahlen 0 bis 255 auf Grundlage der Dezimalstellen von π.
S[i] ist das i-te Element von S.

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 zum Beispiel 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 mit 0 initialisieren */
    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:

MD2("Dies ist mein total sinnloser Testtext") = 68c38c08652c2ef73cfb25388184ed24

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

MD2("Dies ist kein total sinnloser Testtext") = 5d1e3c35e2da15073166789cc8acbf26

Aktuellere Hashfunktionen sind zum Beispiel MD5 und SHA-0, die in der nächsten Folge kurz vorgestellt werden. Außerdem geht es darin um Angriffe auf Hashfunktionen.

Carsten Eilers

Trackbacks

Dipl.-Inform. Carsten Eilers am : Verfahren der Kryptographie, Teil 15: MD4, MD5, SHA und SHA-1 - alle unsicher!

Vorschau anzeigen
Neuere Hashfunktionen als der bereits vorgestellte Algorithmus MD2 sind MD4 und MD5 sowie SHA und SHA-1. Wobei "Neuer" erst mal sehr relativ ist und außerdem nicht gleichzeitig auch "Sicher" bedeutet. MD4 und MD5 MD4 wurde von Ronal

Dipl.-Inform. Carsten Eilers am : Kryptographie - Ein Überblick

Vorschau anzeigen
Die Kryptographie ist ein ein sehr umfangreiches Themengebiet, und obwohl ich mich jetzt seit 30 Artikeln damit befasst habe sind längst nicht alle Themen vorgestellt worden. Aber zumindest die wichtigsten habe ich beschrieben, und damit soll e

Dipl.-Inform. Carsten Eilers am : Die IoT Top 10, #2: Unsichere Authentifizierung/Autorisierung, Teil 6

Vorschau anzeigen
Weiter geht es mit der Beschreibung der gefährlichsten Schwachstellen in den Geräten des IoT gemäß den Top IoT Vulnerabilities von OWASP. Zur Zeit sind wir beim Punkt 2: "Insufficient Authentication/Authorization". Die ve

Dipl.-Inform. Carsten Eilers am : Drucksache: Windows Developer 1.18 - Sicherheit von Kryptoverfahren

Vorschau anzeigen
Im Windows Developer 1.18 ist ein Überblick über den aktuellen Stand der Sicherheit in der Kryptographie erschienen: Welche Kryptoverfahren und Schlüssellängen sollte man verwenden, welche sollte man meiden? Im Windows De

entwickler.de am : PingBack

Die Anzeige des Inhaltes dieses Trackbacks ist leider nicht möglich.