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.
Trackbacks
Dipl.-Inform. Carsten Eilers am : Verfahren der Kryptographie, Teil 15: MD4, MD5, SHA und SHA-1 - alle unsicher!
Vorschau anzeigen
Dipl.-Inform. Carsten Eilers am : Kryptographie - Ein Überblick
Vorschau anzeigen
Dipl.-Inform. Carsten Eilers am : Die IoT Top 10, #2: Unsichere Authentifizierung/Autorisierung, Teil 6
Vorschau anzeigen
Dipl.-Inform. Carsten Eilers am : Drucksache: PHP Magazin 1.18 - Welche Kryptoverfahren sollte man verwenden bzw. meiden?
Vorschau anzeigen
Dipl.-Inform. Carsten Eilers am : Drucksache: Windows Developer 1.18 - Sicherheit von Kryptoverfahren
Vorschau anzeigen
entwickler.de am : PingBack
Die Anzeige des Inhaltes dieses Trackbacks ist leider nicht möglich.