Cryptography Reference
In-Depth Information
3.2
Hash-Funktionen auf Basis von Block-Chiffren
Eine Hashfunktion auf der Basis von Block-Chiffren wurde in Kap. 2.2.4.2 (Einweg-
Hashfunktion auf Basis von DES) bereits vorgestellt. In Abb. 3-1 ist der Fall dargestellt, dass
ein beliebiger Block-Algorithmus BA benutzt wird.
Dazu wird eine Nachricht m in Blöcke aufgeteilt, m = {m
1
, m
2
, ... m
t
}. Die Blocklänge ent-
spricht der Blocklänge des Block-Algorithmus BA, also 64 Bit bei DES und Triple-DES oder
128 Bit bei AES. Der letzte Block m
t
muss gegebenenfalls durch „Padding“ auf die Blocklänge
von BA aufgefüllt werden. Jeder Nachrichtenblock m
i
durchläuft den Block-Algorithmus BA.
Der Ausgang eines Blocks wird mit einem Eingang des nächsten Blocks verkettet, ähnlich wie
bei CBC (Cipher Block Chaining, Kap. 2.7).
m
1
m
2
m
t
IV
BA
BA
BA
h
t -1
h= h(m)
t
Abb. 3-1: Einweg-Hashfunktion auf der Basis eines Block-Algorithmus BA.
Die Länge des Hashwertes h(m) ist gleich der Blocklänge von BA. Bei Verwendung von AES
würde die Blocklänge für Angriffe auf schwache Kollisionsresistenz ausreichen. Durch Paral-
lelschaltung von BA-Blöcken kann die Länge des Hashwertes verdoppelt werden, was aber
keine praktische Bedeutung erlangt hat.
Die stellenweise Addition mod 2 am Ausgang der BA-Blöcke ist für die Eigenschaft als Ein-
wegfunktion wesentlich. Die entsprechende Gleichung (3.2-1) für die letzte Stufe t kann we-
gen der Nichtlinearität nicht nach m
t
aufgelöst werden.
h (m)
m
(m)
(3.2-1)
t
t
t
Ein Angreifer könnte (t1) Nachrichtenblöcke m*
1
...m*
(t1)
frei wählen. Damit ist der Schlüs-
seleingang der Stufe t festgelegt und bekannt. Der letzte Nachrichtenblock m*
t
kann benutzt
werden, um den vorgegebenen Hashwert h(m) = h
t
zu erfüllen. Dazu müsste der Angreifer
jedoch von dem Hashwert h(m) = h
t
auf den letzten Nachrichtenblock m*
t
zurückrechnen, um
zu einem gegebenen h(m) eine Nachricht m* mit dem gleichen Hashwert zu konstruieren.
Dafür ist nur die Möglichkeit eines Brute-Force-Angriffs bekannt.
Es sind weitere Schemata vorgeschlagen worden, um Einweg-Hashfunktionen auf Basis von
Block-Algorithmen zu konstruieren. In Abb. 3-2 sind drei Versionen mit nur einer von jeweils
t Stufen dargestellt. Es bedeuten darin m
i
der Nachrichtenblock der Stufe i, h
i-1
der Hash-
Eingang und h
i
der Hash-Ausgang der Stufe i. Der Hash-Eingang h
0
für die Stufe 1 ist ein