Cryptography Reference
In-Depth Information
Man beachte, dass F in der Tat auch als Fälscher für NMAC [ f, p ] aufgefasst werden
kann. Falls ( w i ,w o ) gemäß U [ { 0 , 1 }
l
×{ 0 , 1 }
l ] gewählt wird, so ist nach Konstruktion
NMAC[ f,p ]
F
von U klar, dass U genau das Experiment
E
simuliert, genauer gesagt: das
( U [ { 0 , 1 } l ×{ 0 , 1 } l ] ,P f )
U
NMAC[ f,p F überein,
wobei sich b , gemäß Definition des verkürzten Experimentes zu U , auf die Wahl der
Wahrscheinlichkeitsverteilung bezieht. Wird dagegen ( w i ,w o ) gemäß P f gewählt, so sieht
man wegen Lemma 9.6.1 leicht, dass U genau das Experiment
Experiment
S
b =0
stimmt mit dem Experiment
E
HMAC[ f,p,u,m ]
F
E
simuliert,
( U [ { 0 , 1 } l ×{ 0 , 1 } l ] ,P f )
U
HMAC[ f,p,u,m ]
F
d. h., die Experimente
S
b =1
und
E
stimmen überein.
Damit folgt sofort:
Prob
=1 =Prob
b =0 =1
( U [ { 0 , 1 } l ×{ 0 , 1 } l ] ,P f )
U
NMAC[ f,p ]
F
E
S
,
Prob
=1 =Prob
=1 .
( U [ { 0 , 1 } l ×{ 0 , 1 } l ] ,P f )
U
HMAC[ f,p,u,m ]
F
E
S
b =1
Daraus ergibt sich der folgende Satz, der, in üblicher Weise, die Sicherheit des HMACs
auf die Ununterscheidbarkeit von U [
l
l ] und P f sowie die Sicherheit des
{
0 , 1
}
×{
0 , 1
}
NMACs reduziert.
Satz 9.6.1. Es sei HMAC [ f,p,u,m ] ein HMAC gemäß Definition 9.6.2. Weiter sei F
ein Fälscher für HMAC [ f,p,u,m ] und U der obige Unterscheider. Dann gilt:
adv MAC ( F, HMAC [ f,p,u,m ]) = adv MAC ( F, NMAC [ f, p ]) +
adv ( U, ( U [
l
l ] ,P f )) .
{
0 , 1
}
×{
0 , 1
}
( U [ { 0 , 1 } l ×{ 0 , 1 } l ] ,P f )
U
Beweis. Wir kürzen S
mit
S U ab und schreiben
S U
1
statt
S U
b =1
;
l
l ] schreiben wir kurz U [ l ] . Mit den bisher gemachten
analog für b =0 .Für U [
{
0 , 1
}
×{
0 , 1
}
Beobachtungen gilt:
adv MAC ( F, HMAC [ f,p,u,m ]) = Prob
=1
HMAC[ f,p,u,m ]
F
E
=Prob
{ S U
1
=1
}
=Prob
{ S U
1
=1
}−
Prob
{ S U
0
=1
+
Prob { S U
}
0
=1
}
= adv ( U, ( U [ l ] ,P f )) + Prob
=1
NMAC[ f,p ]
F
E
= adv ( U, ( U [ l ] ,P f )) + adv MAC ( F, NMAC [ f, p ]) .
Da, wie man leicht sieht, sich die Laufzeiten der betrachteten Experimente, nämlich
( U [ { 0 , 1 } l ×{ 0 , 1 } l ] ,P f )
U
HMAC[ f,p,u,m ]
F
NMAC[ f,p ]
F
E
, sowie die Anzahl und die Länge der
Anfragen kaum unterscheiden, ist die angegebene Reduktion sehr gut, d. h., die Sicherheit
des HMAC ist etwa unter den gleichen Bedingungen gewährleistet wie die Sicherheit des
NMAC und die Ununterscheidbarkeit von U [
,
E
und
E
l ] und P f .
Angesichts der Definition des HMAC liegt der Gedanke nahe, statt des komplexe-
ren Etikettieralgorithmus T ( x, k )= h f ( u,k o ) ( h f ( u,k i ) ( x )) ,einfach T ( x, k )= h ( k
l
{
0 , 1
}
×{
0 , 1
}
·
x ) zu
Search WWH ::




Custom Search