Cryptography Reference
In-Depth Information
≤
adv
MAC
(
F,
M
)+
adv
weakColl
(
C,
H
)
,
wobei sich die letzte Ungleichung direkt aus den Lemmas 9.4.1 und 9.4.2 ergibt.
Satz 9.4.1 besagt in überlicher Weise, dass das Hash-then-MAC-Schema sicher ist,
falls dies für die Komponenten - das Basis-Authentifizierungschema und die Familie von
Hashfunktionen - der Fall ist. Da sich die Laufzeiten sowie die Anzahl und Länge der
Orakelanfragen der verschiedenen Experimente kaum voneinander unterscheiden, hält
sich der Verlust an Sicherheit des Hash-then-MAC-Schemas im Vergleich zur Sicherheit
der Komponenten in Grenzen: Das Hash-then-MAC-Schema ist etwa unter den gleichen
Annahmen sicher, unter denen auch die Komponenten sicher sind. Eine genaue Analyse
soll in Aufgabe 9.8.9 durchgeführt werden.
9.5
Der NMAC
Wir betrachten nun eine Instanziierung des allgemeinen Hash-then-MAC-Schemas aus
dem vorherigen Abschnitt durch iterierte Hashfunktionen, der auf Mihir Bellare, Ran
Canetti und Hugo Krawczyk zurückgeht. Das resultierende Schema wird NMAC genannt.
Dabei werden iterierte Hashfunktionen bzw. die zugehörigen Kompressionsfunktionen
sowohl als Hashfunktionen aufgefasst als auch als MACs.
Für die bei iterierten Hashfunktionen eingesetzen Füllfunktionen wird, wie in Ab-
schnitt 8.4 erläutert, MD-Kompatibilität verlangt. Wir benötigen allerdings noch eine
weitere Eigenschaft, die wir in folgender Definition formulieren.
Definition 9.5.1 (NMAC-kompatible Füllfunktion). Eine MD-kompatible
(
r, D, b
)
-Füll-
funktion
p
heißt
NMAC-kompatible
(
r, D, b, l
)
-Füllfunktion
, falls
l
{
0
,
1
}
⊆
D
und
|
p
(
x
)
|
=
l
gilt.
b
für alle
x ∈{
0
,
1
}
Man sieht leicht:
Bemerkung
9.5.1
.
Es seien
l,r,b ≥
0
mit
0
<r<b
sowie
l
+1
≤ b−r
und
l<
2
r
.Weiter
sei
D
eine Menge mit
<
2
r
. Dann ist die Merkle-Damgård-Füllfunktion
p
b,
MD
mit Definitionsbereich
D
(siehe Definition 8.4.4) eine NMAC-kompatible
(
r, D, b, l
)
-
Füllfunktion.
l
{
0
,
1
}
⊆
D
⊆{
0
,
1
}
Wir können nun das NMAC-Schema definieren.
Definition 9.5.2 (NMAC). Es sei
f
eine
(
l,b
)
-Kompressionsfunktion,
p
eine NMAC-
kompatible
(
r, D, b, l
)
-Füllfunktion und
h
k
}
k∈{
0
,
1
}
l
mit
h
k
=
h
f,
k
die zugehörige
Familie iterierter Hashfunktionen (vgl. Definition 8.4.5). Der zugehörige
NMAC
,dermit
NMAC
[
f,p
]
bezeichnet wird, ist das Tupel
H
=
{
l
l
,T
)
,
NMAC
[
f,p
]=(
{
0
,
1
}
×{
0
,
1
}
mit
l
.
T
(
x,
(
k
out
,k
in
)) =
h
k
out
(
h
k
in
(
x
))
für alle
x
∈
D
,
k
out
,k
in
∈{
0
,
1
}
