Cryptography Reference
In-Depth Information
Die Zahl
r
wird
Längenparameter
genannt. In Kapitel 9 werden wir auch Füllfunktionen
betrachten, deren Definitionsbereich eine Teilmenge
D
von
<
2
r
ist. Wir sprechen
dann von einer MD-kompatiblen
(
r, D, b
)
-Füllfunktionen, wobei die Bedingungen 1. bis
3. entsprechend auf
D
eingeschränkt werden.
{
0
,
1
}
Eine einfache, in der Praxis verwendete MD-kompatible Füllfunktion wird in der fol-
genden Definition festgelegt. In dieser steht
(
x
)
l
2
für die Binärdarstellung von
|
x
|
mit
vorangestellten Nullen, so dass eine Gesamtlänge von
l
Bits erreicht wird.
Definition 8.4.4 (Merkle-Damgård-Füllfunktion). Es seien
r
und
b
mit
0
<r≤ b
gege-
ben. Die
Merkle-Damgård-Füllfunktion
p
b,
MD
:
<
2
r
b
+
mit den Parametern
{
0
,
1
}
→{
0
,
1
}
b
und
r
ist gegeben durch
p
b,
MD
(
x
)=
x
0
s
(
x
)
r
2
·
1
·
·
,
wobei
s ≥
0
minimal so gewählt wird, dass
b − r
=(
|x|
+1+
s
)
mod
b
gilt.
Man sieht sofort:
Bemerkung
8.4.1
.
Merkle-Damgård-Füllfunktionen sind MD-kompatibel.
Wir können nun das Merkle-Damgård-Prinzip beschreiben (siehe auch Abbildung 8.1).
Definition 8.4.5 (Merkle-Damgård-Prinzip). Es sei
f
eine
(
l,b
)
-Kompressionsfunktion,
p
:
{
0
,
1
}
<
2
r
l
ein
In-
itialisierungsvektor
. Die nach dem Merkle-Damgård-Prinzip definierte
iterierte MD-Hash-
funktion
h
f,
u
:
{
0
,
1
}
b
+
eine MD-kompatible
(
r, b
)
-Füllfunktion und
u ∈{
0
,
1
}
→{
0
,
1
}
<
2
r
l
ist definiert durch
→{
0
,
1
}
h
f,
u
(
x
)=
i
f
(
u, p
(
x
))
.
Für eine MD-kompatible
(
r, D, b
)
-Füllfunktion sind die betrachteten Funktionen auf den
Definitionsbereich
D
beschränkt.
Iterierte MD-Hashfunktionen haben nun die gewünschte Eigenschaft: Ist die zugrunde
liegende Kompressionsfunktion kollisionsresistent, so auch die nach dem Merkle-Damgård-
Prinzip konstruierte Hashfunktion. Genauer kann man aus einer Kollision für die Hash-
funktion leicht eine Kollision für die Kompressionsfunktion konstruieren, wie wir nun
beweisen werden. Dazu betrachten wir Algorithmus 8.1, der genau das Gewünschte leistet:
Satz 8.4.1.
Es sei
h
=
h
f,
u
eine iterierte MD-Hashfunktion. Dann bestimmt Algorith-
mus 8.1 zu gegebener Kollision
(
x, x
)
von
h
eine Kollision
(
z,z
)
von
f
. Dabei ist die
Laufzeit des Algorithmus linear in der Laufzeit zur Berechnung von
h
(
x
)
und
h
(
x
)
.
Beweis.
Die Aussage zur Laufzeit von Algorithmus 8.1 verifiziert man leicht. Was die
Kollisionen angeht, führen wir eine Fallunterscheidung durch.
1. Fall,
.
Dann gibt das Verfahren
(
v
n−
2
y
n−
1
,v
n
−
2
y
n
−
1
)
zurück. Wir wis-
sen, dass
f
(
v
n−
2
,y
n−
1
)=
h
(
x
)=
h
(
x
)=
f
(
v
n
−
2
,y
n
−
1
)
gilt. Aus Definition 8.4.3,
Bedingung 3, folgt, dass
y
n−
1
=
y
n
−
1
|x|
=
|x
|
und damit
v
n−
2
y
n−
1
=
v
n
−
2
y
n
−
1
gilt. Also ist
(
v
n−
2
y
n−
1
,v
n
−
2
y
n
−
1
)
eine Kollision für
f
.
