Cryptography Reference
In-Depth Information
=
i
f
(
f
(
u, v
)
, p
(
x
))
=
h
f,p
f
(
u,v
)
(
x
)
=
h
f
(
u,v
)
(
x
)
.
<
2
r
−b
. Dann gilt:
m
und
x
Es sei nun
k
∈{
0
,
1
}
∈{
0
,
1
}
T
(
x, k
)=
h
(
k
o
·h
(
k
i
·x
))
=
h
(
k
o
·
h
f
(
u,k
i
)
(
x
))
=
h
f
(
u,k
o
)
(
h
f
(
u,k
i
)
(
x
))
.
Falls
f
(
u, k
i
)
und
f
(
u, k
o
)
gleichverteilte und unabhängig voneinander gewählte Bit-
vektoren der Länge
l
wären, so könnten wir aus Lemma 9.6.1 und Satz 9.5.1 leicht folgern,
dass HMAC ein sicheres Authentifizierungsschema ist. Klar ist aber, dass diese Annahme
für
f
(
u, k
i
)
und
f
(
u, k
o
)
nicht gilt: Beide Bitvektoren hängen in deterministischer Weise
von
k
ab und liefern nicht notwendigerweise eine Gleichverteilung auf
l
.
Folgende Annahme ist aber plausibel: Kein (e
zienter) Unterscheider kann zwischen
der durch
(
f
(
u, k
i
)
,f
(
u, k
o
))
induzierten Verteilung auf
{
0
,
1
}
l
l
und der Gleich-
{
0
,
1
}
×{
0
,
1
}
l
unterscheiden. Wir nehmen also an, dass die durch
f
(
u, k
i
)
und
f
(
u, k
o
)
abgeleiteten Schlüssel pseudozufällig sind. Mit dieser Annahme sowie der
Annahme, dass der NMAC sicher ist, folgt, wie wir nun zeigen werden, auch die Sicher-
heit des HMAC. Es sei betont, dass die skizzierte Annahme eine zusätzliche Anforderung
an die verwendete Kompressionsfunktion
f
darstellt. Um die Annahme zu präzisieren,
betrachten wir zunächst die folgende Wahrscheinlichkeitsverteilung.
l
verteilung auf
{
0
,
1
}
×{
0
,
1
}
Definition 9.6.3 (HMAC-Wahrscheinlichkeitsverteilung). Mit den Bezeichnungen aus
Definition 9.6.2 sei
P
f
die durch die Zufallsvariable
k
r
←{
0
,
1
}
m
induzierte Zufallsvariable
ipad
b/
8
)
,f
(
u,
(
k·
0
b−m
)
⊕
opad
b/
8
))
. Wir fassen wie üblich
P
f
auch als
(
f
(
u,
(
k·
0
b−m
)
⊕
l
l
auf.
Wahrscheinlichkeitsverteilung über
{
0
,
1
}
×{
0
,
1
}
Die Annahme ist nun, dass es keinen »guten« und geeignet ressourcenbeschränkten Un-
terscheider für
(
U
[
{
0
,
1
}
l
×{
0
,
1
}
l
]
,P
f
)
gibt, wobei
U
[
{
0
,
1
}
l
×{
0
,
1
}
l
]
die Gleichverteilung
l
bezeichne. Es sei daran erinnert, dass Unterscheider und deren Vorteil
für Paare von Wahrscheinlichkeitsverteilungen in Abschnitt 6.5.2 definiert wurden.
Um die Sicherheit des HMAC auf diese Annahme und die Annahme, dass der NMAC
sicher ist, abzustützen, nehmen wir nun an, dass ein Fälscher
F
für HMAC
[
f,p,u,m
]
gegeben ist. Mit Hilfe von
F
konstruieren wir einen Unterscheider
U
für
(
U
[
{
0
,
1
}
l
auf
{
0
,
1
}
×{
0
,
1
}
l
×
l
]
,P
f
)
wie folgt:
{
0
,
1
}
U
((
w
i
,w
o
)):
}
Simuliere das Experiment
{
0
,
1
NMAC
[
f,p
]
F
E
:
NMAC[
f,p
]
F
E
mit folgender Änderung:
Statt den Schlüssel
(
k
in
,k
out
)
zufällig aus
l
zu wählen, ver-
wende
(
w
i
,w
o
)
als Schlüssel für das zu simulierende Etikettierorakel
T
,
welches ein Etikettieralgorithmus gemäß NMAC
[
f, p
]
ist.
{
0
,
1
}
l
×{
0
,
1
}
