Cryptography Reference
In-Depth Information
Algorithmus 8.1 Reduktion von Kollisionen für Hashfunktionen auf Kollisionen für
Kompressionsfunktionen
MD-Reduce(
f,p,u,x,x
)
Vorbedingung:
(
x, x
)
ist Kollision für
h
f,p
u
1.
Fülle Nachrichten auf.
y
=
p
(
x
)
;
y
=
p
(
x
)
2.
Zerlege
y
und
y
in Blöcke.
y
=
y
0
···y
n−
1
mit
=
b
für
i<n
;
y
=
y
0
···y
n
−
1
mit
|y
i
|
=
b
für
i<n
|y
i
|
3.
Bestimme Hashwerte und lege Zwischenergebnisse ab.
v
−
1
=
u
;
v
−
1
=
u
für
i
=0
bis
n−
1
v
i
=
f
(
v
i−
1
,y
i
)
für
i
=0
bis
n
−
1
v
i
=
f
(
v
i−
1
,y
i
)
4.
Unterscheide nach Länge der Nachrichten.
falls
|x
|
,so
(
z,z
)=(
v
n−
2
y
n−
1
,v
n
−
2
y
n
−
1
)
sonst
Durchsuche Zwischenwerte nach Kollision.
i
=
n −
|x|
=
1
wiederhole bis
v
i−
1
y
i
=
v
i−
1
y
i
oder
i
=0
1
(
z,z
)=(
v
i−
1
y
i
,v
i−
1
y
i
)
5.
Ausabe.
gib
(
z,z
)
zurück
Nachbedingung:
(
z,z
)
ist eine Kollision von
f
.
i
=
i −
3.
Wende darauf Alogrithmus 8.1 an.
(
z,z
)=MD-Reduce(
f
k
,p,u,x
0
,x
1
)
4.
Ausgabe.
gib
(
z,z
)
zurück
Wegen Satz 8.4.1 wissen wir, dass wenn
A
H
eine Kollison für
h
f
k
,p
gefunden hat, dann
u
liefert
MD-Reduce
eine Kollision für
f
k
. Daraus folgt sofort:
Folgerung 8.4.1.
Es seien
H
,
C
,
A
H
und
A
C
wie oben gegeben. Dann gilt:
adv
(
A
H
,
H
)
≤
adv
(
A
C
,
C
)
.
Die Laufzeit von
E
A
C
unterscheidet sich dabei kaum von der Laufzeit von
E
A
H
;in
E
A
C
wird lediglich
MD-Reduce
zusätzlich ausgeführt.
kollisionsresistent,
d. h., ist der Vorteil von
A
C
klein, so auch der Vorteil von
A
H
, wobei beide Angreifer etwa
die gleiche Laufzeit besitzen. Es ist eine leichte Übung, dies im Sinne von Definition 8.2.3
zu fassen (siehe Aufgabe 8.6.5).
Die Kollisionsresistenz von
C
überträgt sich also auf
H
,dennist
C
