Cryptography Reference
In-Depth Information
Aus der Annahme, dass
p
eine NMAC-kompatible
(
r, D, b, l
)
-Füllfunktion ist, folgt
sofort
|p
(
x
)
|
=
b
für alle
x ∈{
0
,
1
}
l
. Daraus wiederum ergibt sich:
Bemerkung
9.5.2
.
Für
T
in Definition 9.5.2 gilt:
l
.
T
(
x,
(
k
out
,k
in
)) =
f
(
k
out
,p
(
h
k
in
(
x
)))
für alle
x
∈
D
,
k
out
,k
in
∈{
0
,
1
}
Bei der äußeren Anwendung der Hashfunktion wird die Kompressionsfunktion also nicht
iteriert, sondern nur einmal angewendet.
Im Vergleich zum Hash-then-MAC-Schema übernimmt also beim NMAC die Kompres-
sionsfunktion
f
die Aufgabe des Basis-Authentifizierungsschemas. In der Tat wollen wir
f
als MAC auffassen und bezeichnen den durch
f
induzierten MAC mit
l
,T
f
)
,
M
f
=(
{
0
,
1
}
l
.
Da somit der NMAC lediglich eine Instanz des allgemeinen Hash-then-MAC-Schemas
ist, erhalten wir sofort folgenden Satz als Folgerung aus Satz 9.4.1.
b
und
k ∈{
0
,
1
}
für
T
f
(
x, k
)=
f
(
k,x
)
für alle
x ∈{
0
,
1
}
}
≤L
für
l ≤ L<
2
r
. Weiter seien
F
ein Fälscher für NMAC
[
f,p
]
sowie
F
der gemäß Satz 9.4.1
zugehörige Fälscher für
Satz 9.5.1.
Es seien
f
,
p
und
H
wie in Definition 9.5.2 gegeben mit
D
=
{
0
,
1
M
f
und
C
der zugehörige Kollisionsfinder für
H
.Danngilt:
adv
MAC
(
F
,
NMAC
[
f,p
])
≤
adv
MAC
(
F,M
f
)+
adv
weakColl
(
C,H
)
.
M
f
)
sollte also für
jeden geeignet ressourcenbeschränkten Fälscher
F
»klein« sein. Wie sieht es mit dem
Vorteil adv
weakColl
(
C,H
)
aus? Betrachten wir zunächst eine Familie
Nach Annahme ist
M
f
ein sicherer MAC. Der Vorteil adv
MAC
(
F,
C
=
{f
k
}
k∈K
von
(
l,b
)
-Kompressionsfunktionen, so wissen wir, gemäß Folgerung 8.4.1, dass, wenn
C
kol-
H
=
{h
f
k
,p
u
}
(
u,k
)
∈{
0
,
1
}
l
×K
, d. h., für alle (ge-
lisionsresistent ist, dann auch die Familie
H
sollte adv
(
C,
H
)
»klein« sein.
eignet ressourcenbeschränkten) Kollisionsfinder
C
für
H
)
für alle (geeignet ressourcenbeschränkten)
Kollisionsfinder
C
, die lediglich ein Hashorakel als Eingabe bekommen, »klein«. (Um dies
zu folgern, reicht bereits die schwache Kollisionsresistenz von
Insbesondere ist also auch adv
weakColl
(
C,
, da man leicht sieht, dass
sich Folgerung 8.4.1 auf die schwache Kollisionsresistenz überträgt.) Nun sind wir aber
nicht an adv
weakColl
(
C,
C
H
)
, sondern an adv
weakColl
(
C,
H
)
interessiert. Der Unterschied
zwischen
H
und
lediglich eine einzelne Kompressionsfunktion be-
trachten. Folgerung 8.4.1 ist deshalb nicht anwendbar. Dennoch ist es, für geeignete Hash-
funktionen, plausibel anzunehmen, dass adv
weakColl
(
C,
H
ist, dass wir in
H
)
»klein« ist: Immerhin erhält
man nach Satz 8.4.1 aus einer Kollision für ein
h
k
eine Kollision für
f
,mit
h
k
und
f
wie
in Definition 9.5.2. Zudem wird lediglich die schwache Kollisionsresistenz gefordert. (Wie
bereits in Abschnitt 9.4 erwähnt, bietet in manchen Fällen die schwache Kollisionsresis-
tenz jedoch keinen Vorteil gegenüber der (starken) Kollisionsresistenz.) Wir verweisen auf
Abschnitt 9.9 für eine ausführlichere Diskussion zur Annahme, dass adv
weakColl
(
C,
H
)
»klein« ist, insbesondere vor dem Hintergrund der in Abschnitt 8.7 erwähnten Angriffe
auf die Kollisionsresistenz einiger verbreiteter Hashfunktionen.
H
