Cryptography Reference
In-Depth Information
<
2
r
x
p
b
∈{
0
,
1
}
b
+
l
u
f
f
f
h
f,p
u
(
x
)
l
Abbildung 8.1: Merkle-Damgård-Prinzip
.
Nach Definition 8.4.3, Bedingung 2, gilt damit auch
n
=
n
.
Angenommen,
(
v
i−
1
y
i
,v
i−
1
y
i
)
wird ausgegeben für ein
i
|x|
=
|x
|
2. Fall,
∈{
0
,...,n
−
1
}
und es gilt
v
i−
1
y
i
=
v
i−
1
y
i
. Es gilt
f
(
v
i−
1
,y
i
)=
v
i
und
f
(
v
i−
1
,y
i
)=
v
i
.
WirbetrachtenzweiFälle:i)Für
i
=
n
1
gilt
v
i
=
f
(
v
i−
1
,y
i
)=
h
(
x
)=
h
(
x
)=
f
(
v
i−
1
,y
i
)=
v
i
, also insbesondere
v
i
=
v
i
.ii)Für
i<n
−
1
gilt
v
i
=
v
i
nach Definition
des Algorithmus. Damit ist
(
v
i−
1
y
i
,v
i−
1
y
i
)
in beiden Fällen eine Kollision für
f
.
Es bleibt zu zeigen, dass immer ein
i
−
=
v
i−
1
y
i
:
∈{
0
,...,n
−
1
}
existiert mit
v
i−
1
y
i
Ansonsten ist
v
i−
1
y
i
=
v
i−
1
y
i
für alle
i ∈{
0
,...,n−
1
}
. Insbesondere gilt also
p
(
x
)=
y
n−
1
=
p
(
x
)
. Mit Definition 8.4.3, Bedingung 1, folgt daraus, da
ss
x
=
x
gilt, ein Widerspruch zur Voraussetzung.
y
n−
1
=
y
0
···
y
0
···
Mit Hilfe von Satz 8.4.1 können wir sofort Aussagen über die Kollisionsresistenz von
Familien iterierter MD-Hashfunktionen im Sinne von Definition 8.2.2 machen, falls man
statt einer
(
l,b
)
-Kompressionsfunktion eine Familie
C
=
{f
k
}
k∈K
solcher Funktionen
betrachtet und diese als Familie von Hashfunktionen mit Definitionsbereich
l
+
b
{
0
,
1
}
und Hashbreite
l
interpretiert. Es sei dazu
p
eine MD-kompatible Füllfunktion,
=
{h
f
k
,
u
}
(
u,k
)
∈{
0
,
1
}
l
×K
die zugehörige Familie iterierter MD-Hashfunktionen und
A
H
ein
Angreifer auf
H
h
f
k
,
u
}
k∈K
für einen fest
gewählten Initialisierungsvektor
u
betrachten. Die folgenden Aussagen gelten analog.)
Aus
A
H
gewinnen wir einen Angreifer
A
C
auf
H
. (Alternativ kann man auch die Familie
H
=
{
C
wie folgt:
A
C
(
k
:
K
)
1.
Wähle
u
zufällig.
u
=
flip
(
l
)
.
2.
Simuliere
A
H
(
u, k
)
.
(
x
0
,x
1
)=
A
H
(
u, k
)
