Montag, 5. Dezember 2011


Topthema

Donnerstag, 26. April 2007 | Topthema

About Security #102: Hashfunktionen — Einführung

(Link zum Artikel: http://www.entwickler.de/php/kolumnen/035480)
  • Teilen
  • kommentieren
  • empfehlen
  • Bookmark and Share

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.

N E U ! Security aktuell
T�glich aktuelle Security-Infos!

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.

About Security: Die komplette Serie

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.

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 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:

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 z.B. MD4 und MD5, die in der n�chsten Folge vorgestellt werden.

Wenn Sie Fragen oder Themenvorschl�ge haben, k�nnen Sie diese gerne an die angegebene E-Mail-Adresse senden oder im Security-Forum einbringen!

Carsten Eilers

About Security � �bersicht zum aktuellen Thema "Kryptographie � Hashfunktionen"

Kommentare

Gravatar karl 14.08.2009
um 14:37 Uhr
was ist die l�sung dieses hashcodes : 1c28cafdde8131bb1a8df506f61ae6a4 ? #zitieren

Folgende Links könnten Sie auch interessieren