Cryptography Reference
In-Depth Information
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
=1
.
weak
A
adv
weakColl
(
A,
H
Die Begriffe
(
t, ε
)
-Kollisionsresistenz und
(
t, ε
)
-Kollisionsinresistenz für schwache Kolli-
sionsresistenz können analog zu Definition 8.2.3 definiert werden. Neben den Parametern
t
und
ε
macht es nun allerdings Sinn, ähnlich wie in Definition 9.2.3, zusätzlich die Pa-
rameter
n
und
q
für die Anzahl der an das Hashorakel gesendeten Bits bzw. die Anzahl
der Orakelanfragen zu betrachten. Wir erhalten also die Begriffe
schwache
(
n, q, t, ε
)
-
Kollisionsresistenz
sowie
schwache
(
n, q, t, ε
)
-Kollisionsinresistenz
.
Der Reduktionsbeweis.
Wir reduzieren nun die Sicherheit des Hash-then-MAC-Sche-
mas
M
=
HashMAC
[
H ,p,M
]
auf diejenige von
M
und
H
. Wir nehmen also an, dass
wir einen (guten) Fälscher
F
für
M
gegeben haben und benutzen diesen Fälscher,
um einen (guten) Fälscher
F
für
M
und einen (guten) Kollisionsfinder
C
für
H
zu
konstruieren. Letztendlich wird unser Ziel sein, den Vorteil von
F
durch denjenigen von
F
(adv
MAC
(
F,
M
)
)und
C
(adv
weakColl
(
C,
H
)
) zu beschränken. Im Folgenden verwenden
wir die Notation aus Definition 9.4.1.
Der Fälscher
F
erhält im Experiment
E
F
per Definition ein Etikettierorakel
E
als
Argument, wobei
E
von der Form
T
(
·,k
m
)
ist;
E
stammt also vom MAC
M
.DieIdee
E
M
ist nun, dass
F
das Experiment
F
simuliert, wobei die Schlüsselwahl nur teilweise
simuliert wird: Den Schlüssel
k
h
für die Hashfunktion erzeugt
F
selbst. Den Schlüssel
k
m
für den MAC erzeugt
F
nicht selbst; als MAC verwendet
F
stattdessen sein Orakel
E
.
Die Hoffnung ist, dass
F
in diesem simulierten Experiment ein gültiges NE-Paar für
M
ausgibt. Daraus wird
F
versuchen, ein gültiges NE-Paar für
M
zu konstruieren. Genauer
ist
F
wie folgt definiert:
r
l
):
r
l
F
(
E
:
{
0
,
1
}
→{
0
,
1
}
{
0
,
1
}
×{
0
,
1
}
1.
Wähle Hashfunktion
k
h
=
flip
(
K
H
)
2.
Simuliere
F
.
F
mit folgenden Änderungen:
a. Eine Anfrage
x
von
F
an das Etikettierorakel wird wie folgt beantwortet:
v
=
h
k
h
(
x
)
x
=
p
(
v
)
Gib
E
(
x
)
zurück an den simulierten Algorithmus
F
b. Wenn
F
das NE-Paar
(
x, t
)
ausgibt, ersetze die Ausgabe wie folgt:
v
=
h
k
h
(
x
)
x
=
p
(
v
)
gib
(
x
,t
)
zurück
E
M
F
E
F
Man sieht leicht, dass die Experimente
und
fast identisch sind. Insbesondere
E
M
F
kann in offensichtlicher Weise zu jedem Lauf
α
von
ein entsprechender Lauf
α
von
