Cryptography Reference
In-Depth Information
Struktur der Hashfunktionen es schwer macht, eine Kollision zu bestimmen. Und das ist
genau das, was wir unter Kollisionsresistenz verstehen wollen. Wir erhalten also folgende
Definitionen.
Definition 8.2.1 (Angreifer auf eine Familie von Hashfunktionen). Es sei
H
=
{
h
k
}
k∈K
eine Familie von Hashfunktionen mit Hashbreite
l
.EinAngreifer
A
für
, auch Kolli-
sionsfinder genannt, ist ein zufallsgesteuerter Algorithmus
A
(
k
:
K
):
{
0
,
1
}
∗
×{
0
,
1
}
∗
,
dessen Laufzeit durch eine Konstante nach oben beschränkt ist.
H
Kollisionsresistenz wird nun über ein Experiment und den Vorteil des Angreifers
bzgl. dieses Experimentes definiert.
Definition 8.2.2 (Experiment und Vorteil). Es sei
A
ein Angreifer für die Familie
=
{h
k
}
k∈K
von Hashfunktionen mit Hashbreite
l
. Das zugehörige
Experiment
,daswirmit
E
A
H
,
E
A
oder einfach
E
bezeichnen, ist der Algorithmus, der gegeben ist durch:
E:
{
0
,
1
}
1.
Indexwahl
k
=
flip
(
K
)
2.
Kollisionsberechung
(
x
0
,x
1
)=
A
(
k
)
3.
Auswertung
falls
(
x
0
,x
1
)
eine Kollision für
h
k
ist, gib
1
, sonst
0
zurück
Der
Vorteil
von
A
bezüglich
H
ist definiert durch:
)=Prob
E
A
=1
.
adv
Coll
(
A,
H
Statt adv
Coll
(
A,
H
)
schreiben wir auch einfach adv
(
A,
H
)
.
Wie üblich kann man nun die Kollisionsresistenz einer Familie von Hashfunktionen
quantifizieren.
Definition 8.2.3 (
t
-beschränkt,
(
t, ε
)
-kollisionsresistent). Es sei
t
eine natürliche Zahl
und
A
ein Angreifer für eine Familie
H
von Hashfunktionen. Der Angreifer
A
ist
t
-
E
A
beschränkt bzgl.
H
,
wenn die Laufzeit des zugehörgen Experimentes
durch
t
be-
schränkt ist.
Es sei
insec
(
t,H
)=sup
{
adv
(
A,H
)
| A
ist
t
-beschränkter Angreifer für
H } .
Es sei weiterhin
ε
heißt
(
t, ε
)
-kollisionsinresistent,
wenn insec
(
t,H
)
≥ ε
gilt. Sie heißt
(
t, ε
)
-kollisionsresistent,
wenn insec
(
t,H
)
≤ ε
gilt.
Neben der Zweites-Urbild-Resistenz und der Kollisionsresistenz, die wir gerade präzi-
se definiert haben, gibt es noch eine dritte Sicherheitsanforderung, die
Urbild-Resistenz
(
preimage resistance
).Dabeiverlangtman,dasses»schwer«möglichseinsoll,zueinem
gegebenen Hashwert
v
einen Bitvektor
x
zu finden, für den
h
(
x
)=
v
gilt.
≥
0
eine reelle Zahl. Die Familie
H
