KaoruKurosawaand Tetsu Iwata
Department ofComputer andInformationS ien es,
IbarakiUniversity
4{12{1Nakanarusawa,Hita hi, Ibaraki316-8511,Japan
fkurosawa, iwatag is.ibaraki.a .jp
Abstra t. Inthis pap er,weprop ose TMAC,Two-KeyCBC Message
Authenti ationCo de.TMACisare nementofXCBC(whi hisavariant
ofCBC MAC) shown by Bla k andRogaway. Weuse only (k+n)-bit
key forTMAC while XCBCuses (k+2n)-bit key,where k is the key
lengthoftheunderlying blo k ipherandnisitsblo klength.The ost
forredu ing the size of se ret keys is almost negligibl e; only one shift
andone onditional XOR.Similarly to XCBC,ouralgorithm orre tly
andeÆ iently handlesmessagesofarbitrarybitlength.
1 Introdu tion Let E : f0;1g k f0;1g n !f0;1g n
b e ablo k ipher:it uses a k -bitkey K 2
f0;1g k
to en rypt an n-bit blo k X 2 f0;1g n
into an n-bit iphertext Y =
E
K (X).
1.1 CBC MAC
TheCBCMAC[8,10℄isthesimplestandmostwell-knownalgorithmtomakea
MACfromablo k ipher.LetM =M
1 jjM
2
jjjjM
m
b eamessagestringsu h
that jM 1 j=jM 2 j==jM m j =n.Then CBC E K (M), theCBC MACof M
underkeyK,is de nedasC
m ,where C i =E K (M i C i 1 ) fori=1;:::;mandC 0 =0 n .
Bellare,Kilian,andRogawayprovedthese urityoftheCBCMACfor xed
message length mn [3℄.It is well known, however, that the CBC MAC is not
se ure ifthemessagelengthvaries.
1.2 EMAC
To deal with variable message length in blo ks m, En rypted MAC (EMAC)
wasdevelop ed.EMACen ryptsCBC
E
K
1
(M)usinganewblo k ipherkeyK
2 . Thatis, EMAC E K 1 ;E K 2 (M)=E K 2 (CBC E K 1 (M)) :
these urity [12℄.
Aproblemisthat themessagelengthislimitedto ap ositivemultipleof n,
thatis,thedomainislimitedto(f0;1g n
) +
.Thesimplestapproa htodealwith
messageswhoselengths arenotamultipleofnistoapp endtheminimal10 i
to
M asapaddingso that thelengthisamultipleof n.Note thatthepaddingis
app ended evenifthesize ofthemessageisalreadyamultipleofn.
In this way, EMAC an deal with ompletely variable message length. In
otherwords,thedomainisf0;1g
.We allthisEMAC
.
1.3 RMAC
Jaulmes,Joux,andValetteprop osedRMAC[11℄whi hisanextensionofEMAC.
RMACen rypts CBC E K 1 (M)withK 2
R,whereRis ann-bit randomstring
anditisapartofthetag.Thatis,
RMAC E K 1 ;E K 2 (M)=(E K 2 R (CBC E K 1 (M));R) :
They showed that the se urity of RMAC is b eyond the birthday paradox
limit.However,thetaglengthisnbitslongerthantheotherCBCMACvariants.
1.4 XCBC
EMAC
andRMACrequire 1+d(jMj+1)=ne blo k ipher invo ations.Bla k
and Rogaway prop osed XCBC [5℄ whi h requires only djMj=ne blo k ipher
invo ations.
XCBC takes three keys: one blo k ipher key K
1
, and two n-bit keys K
2
and K
3
. XCBC makes two ases to deal with arbitrarylength messages:M 2
(f0;1g) + andM 62(f0;1g) + .IfM 2(f0;1g) +
thenXCBC omputesexa tlythe
sameastheCBCMAC,ex ept XORingann-bitkeyK
2
b eforeen ryptingthe
last blo k. If M 62 (f0;1g) +
then minimal10 i
padding(i 0) is app ended to
M so thatthelengthisamultipleofn,andXCBC omputesexa tly thesame
as theCBCMAC,ex ept XORinganothern-bit keyK
3
b eforeen rypting the
lastblo k.
1.5 OurContribution
Thekey lengthofXCBCis(k+2n)bitsintotal.Toredu ethekey length,the
authors suggested the followingsolution [6℄for n k 2n. A se ret key is a
singlekey KofE. Thenfor somedistin t onstantsC
1a ,C 1b ,C 2 ,andC 3 ,let K 1 =the rstkbitsofE K (C 1a )jjE K (C 1b ); K 2 =E K (C 2 ); K 3 =E K (C 3 ):
3or4additionalblo k ipherinvo ations.
2. Itneedstwokey s hedulingsfortwoblo k ipherkeys K andK
1 .
These problemsmayb esigni antifonefrequently hangesthese ret key.
Inthis pap er, we prop ose TMAC, Two-Key CBC Message Authenti ation
Co de.TMACisare nementofXCBCshownbyBla kandRogaway.Weuseonly
(k+ n)-bitkeyforTMACwhileXCBCuses(k+ 2n)-bitkey.The ostforredu ing
the size of se ret keys is almostnegligible; only one shift and one onditional
XOR.Similarlyto XCBC, thedomainis f0;1g
and itrequires djMj=ne blo k
ipherinvo ations.
We showa omparisonofCBC MAC anditsvariantsinTable1,where M
is themessageand E isablo k ipher. Thethird olumngives the numb erof
invo ations of E, assuming jMj > 0.The fourth olumn gives the numb er of
di erentkeysusedforE.
Table1.ComparisonofCBCMACandItsVariants.
Name Domain #EInvo ations #EKeysKeyLength
CBCMAC[8,10,3℄ (f0;1g n ) m jMj=n 1 k EMAC [4,12℄ f0;1g 1+d(jMj+1)=ne 2 2k RMAC[11℄ f0;1g 1+d(jMj+1)=ne 2 2k XCBC[5,6℄ f0;1g djMj=ne 1 k+2n
TMAC(Ourprop osal) f0;1g
djMj=ne 1 k+n
1.6 OtherRelatedWorks
Re ently, some resear hers prop osed parallelizable MAC algorithms. Bellare,
Guerin, and Rogawayprop osed XOR MAC [2℄.Gligor,and Dones u prop osed
XECB-MAC[9℄.Bla kand Rogawayprop osedPMAC[7℄.
However, these MAC algorithmshave overhead as follows. XOR MAC
re-quiresmu hmoreinvo ationsofEthantheotherMACalgorithms.XECB-MAC
requiresmo dulo2 n
arithmeti andthreemoreinvo ationsofEthanXCBCand
TMAC.PMACneedsto generate asequen e ofmasks.
Therefore,TMACandXCBCareb etterthanthesealgorithmsinnon-parallelizable
environment.
2 Mathemati al Preliminaries
2.1 Notation
IfA isa nite set then#Adenotes thenumb erofelementsinA. For aset A,
x R
A meansthatxisrandomly hosen fromA.If 2f0;1g
isastring then
j jdenotesitslengthinbits.If ; 2f0;1g
areequal-lengthstringsthen
Forann-bitstring =a n 1 a 1 a 0 2f0;1g ,let <<1=a n 2 a n 3 a 1 a 0 0 : Similarly,let >>1=0a n 1 a n 2 a 2 a 1 :
2.2 TheFieldwith2 n
Points
Weinter hangeably thinkofap ointainGF(2 n
)inanyofthefollowingways:
1. asanabstra tp ointina eld;
2. asann-bitstringa n 1 a 1 a 0 2f0;1g n ;
3. asaformalp olynomiala(u)=a
n 1 u n 1 ++a 1 u+a 0
withbinary o
eÆ- ients.
Toaddtwop ointsinGF(2 n
),taketheirbitwiseXOR.Wedenotethisop
er-ationbyab.
Tomultiplytwop oints, x someirredu iblep olynomialf(u) havingbinary
o eÆ ientsanddegreen.Tob e on rete, ho osethelexi ographi ally rstp
oly-nomialamongtheirredu ible degreenp olynomialshavingaminimumnumb er
of o eÆ ients.We listsomeindi atedp olynomials.
8 < : f(u)=u 64 +u 4 +u 3 +u+1 forn=64, f(u)=u 128 +u 7 +u 2 +u+1 forn=128,and f(u)=u 256 +u 10 +u 5 +u 2 +1 forn=256.
Tomultiplytwop ointsa2GF(2 n
)and b2GF(2 n
),regard aand bas p
olyno-mialsa(u)=a n 1 u n 1 ++a 1 u+a 0 and b(u)=b n 1 u n 1 ++b 1 u+b 0 ,
formtheirpro du t (u)whereoneaddsandmultiplies o eÆ ientsinGF(2),and
taketheremainderwhendividing (u)byf(u).
Note that it is parti ularly easy to multiply a p oint a 2 f0;1g n
by u. We
showametho dforn=128,wheref(u)=u 128
+u 7
+u 2
+u+1.Thenmultiplying
a=a 127 a 1 a 0
by uyieldsapro du t a
n 1 u n +a n 2 u n 1 ++a 1 u 2 +a 0 u. Thus, ifa n 1 =0, thenau=a<<1. If a n 1
=1,then we mustadd u 128 to a<<1.Sin eu 128 +u 7 +u 2 +u+1=0wehaveu 128 =u 7 +u 2 +u+1,soadding u 128 meansto xorby0 120 10000111.Insummary,when n=128, au= a<<1 ifa 127 =0, (a<<1)0 120 10000111 otherwise, (1)
where au=a(u)umo df(u).
Also,note that it is easyto devide ap ointa2f0;1g n
byu, meaningthat
onemultipliesabythemultipli ativeinverseofuinthe eld:au 1
.Weshowa
metho dforn=128.Thenmultiplyinga=a
127 a 1 a 0 byu 1
yieldsapro du t
a n 1 u n 2 +a n 2 u n 3 ++a 2 u+a 1 +a 0 u 1 .Thus,ifa 0 =0,thenau 1 =a>>1. Ifa 0
=1,thenwe mustaddu 1 toa>>1.Sin eu 128 +u 7 +u 2 +u+1=0we
have u =u +u+1+u ,so addingu =u +u +u+1meansto xor by10 120 1000011.Insummary,whernn=128, au 1 = a>>1 ifa 0 =0, (a>>1)10 120 1000011 otherwise. (2) 3 Spe i ation 3.1 Basi Sp e i ation
TouseTMAC,one mustsp e ifyablo k ipherE.
The blo k ipher E is afun tion E : K
E f0;1g n ! f0;1g n , where ea h E(K ;)=E K ()is ap ermutationonf0;1g n ,K E
istheset ofp ossiblekeys and
n istheblo klength.The p opular blo k ipherto usewithTMACis likelyto
b eAES,but anyotherblo k ipheris ne.
TMACisafun tiontaking twokeys K
1 2K E ,K 2 2f0;1g n andamessage M 2 f0;1g
, and returning a string in f0;1g n
. The key spa e Kof TMAC is
K=K
E
f0;1g n
.Thefun tionisde nedinFig.1andillustratedinFig.2.
AlgorithmTMACE K 1 ;K 2 (M) ifM 2(f0;1g n ) + thenK K2uandP M elseK K 2 andP Mjj10 i ,wherei n 1 jMjmo dn LetP=P1jjP2jjjjPm,wherejP1j=jP2j==jPmj=n C 0 0 n for i 1to m 1do C i E K1 (P i C i 1 ) returnT =E K 1 (P m C m 1 K)
Fig.1.De nitionofTMAC.
M1 ? E -K 1 -M2 ? f ? E -K 1 -M3 ? f ? E -K 1 ? T K 2 u M1 ? E -K 1 -M2 ? f ? E -K 1 -M3 10 i | {z } ? f ? E -K 1 ? T K 2
Fig.2.Illustration ofTMAC.
Inthe third line of Fig. 1and inthe last blo kof left hand side inFig.2,
K
2
uisamultipli ationinGF(2 n
).It anb e omputedwithonlyoneshiftand
We have twooptions onthe omputationof K
2
u.The rstoptionis to keep
b oth K
2 andK
2
uinthememory.Ituses amemoryof2nbits.
The se ond option uses amemoryof only n bits. We rst keep K
2 in the memory.WhenK 2 u isneeded, we omputeK 2 ufromK 2 . We thenrepla e K 2 withK 2
u inthememory.Next whenK
2 is needed,we ompute K 2 from K 2 uandrepla e K 2 uwithK 2
inthememory.Rep eatthis pro ess.
Notethat itis easyto omputeK
2
fromK
2
u sin e multipli ationbyu 1
anb e omputedwithonlyoneshiftandone onditionalXORasshownin(2).
3.3 ComparisonwithXCBC XCBC is obtained byrepla ing K 2 x with K 3 in Fig.2, where K 3 2 f0;1g n
isarandomstring. Inanother wayaround,TMACisobtainedfromXCBC by
repla ingK
3
withK
2
x.Thesizeofkeysisredu edfrom(k+2n)bitsto(k+n)
bitsinthisway.
4 Se urity of TMAC
4.1 Se urityDe nitions
AnadversaryAisanalgorithmwithanora le(orora les).Theora le omputes
somefun tion.Without lossofgenerality,adversaries areassumed toneverask
aqueryoutside thedomainoftheora le, andtonever rep eataquery.
Ablo k ipherisafun tionE:K
E f0;1g n !f0;1g n whereK E isa nite
set andea h E
K
()=E(K ;)isap ermutationonf0;1g n
.LetPerm(n)denote
theset ofallp ermutationsonf0;1g n
.Wesaythat P isarandomp ermutation
ifP israndomly hosen fromPerm(n).
NotethatfE
K
()jK2K
E
gshouldlo oklikePerm(n).Foranadversary A,
wede ne Adv prp E (A) def = Pr (K R K E :A E K () =1) Pr (P R Perm(n):A P() =1) :
TheadversaryA annotdistinguishfE
K
()jK2K
E
gfromPerm(n)ifAdv prp
E (A)
isnegligible.
Similarly,aMACfun tionfamilyfromf0;1g tof0;1g n isamapF:K F f0;1g !f0;1g n where K F
is aset with an asso iated distribution.We write
F
K
()forF(K ;).We saythat A FK()
forges ifAoutputs(x;F
K
(x))where A
neverqueriedxto itsora le F
K ().Thenwe de ne Adv ma F (A) def = Pr (K R K F :A F K () forges) :
LetRand(;n)denotethesetofallfun tionsfromf0;1g
tof0;1g n
.Thissetis
asso iates to ea h string x2f0;1g arandomstring R(x)2 f0;1g . Then we de ne Adv viprf F (A) def = Pr(K R K F :A F K () =1) Pr (R R Rand(;n):A R() =1) : Alsowewrite Adv prp E (t;q ) def = max A fAdv prp E (A)g;
wherethemaximumisoveralladversarieswhorunintimeatmosttandmake
atmostqqueries. Further we write
Adv ma F (t;q ;) def = max A fAdv ma F
(A)g andAdv viprf F (t;q ;) def = max A n Adv viprf F (A) o ;
where themaximumisoveralladversaries whorunintimeat mostt,makeat
mostqqueries,ea h ofwhi hisatmost-bits.
4.2 TheoremStatements
Wegivethefollowinginformation-theoreti b oundonthese urityofTMAC.A
pro ofofthislemmaisgiveninthenextse tion.
Weidealizeablo k ipherbyarandomp ermutationdrawnfromPerm(n).
Lemma 4.1. LetAbeanadversarywhi hasksatmostqqueries,ea hofwhi h
isatmost nm-bits.Assume m2 n =4.Then Pr (P 1 R Perm(n);K 2 R f0;1g n :A TMAC P 1 ;K 2 () =1) Pr(R R Rand(;n):A R() =1) (3m 2 +1)q 2 2 n :
Fromthe ab ove theorem,it is standard topass tothe omplexity-theoreti
result.(Forexample,see[3,Se tion 3.2℄.)Thenwehavethefollowing orollary.
Corollary 4.1. Let E :K E f0;1g n !f0;1g n
be the underlying blo k ipher
usedin TMAC.Then
Adv viprf TMAC (t;q ;nm) (3m 2 +1)q 2 2 n +Adv prp E (t 0 ;q 0 ) ; wheret 0 =t+O (mq ) andq 0 =mq .
These urity ofMACisalsoderived intheusualway.(For example,see[3,
Prop osition2.7℄.)Thenwe havethefollowingtheorem.
Theorem4.1. Let E : K E f0;1g n !f0;1g n
be the underlying blo k ipher
usedin TMAC.Then
Adv ma TMAC (t;q ;nm) (3m 2 +1)q 2 +1 2 n +Adv prp E (t 0 ;q 0 ) ; wheret 0 =t+O (mq ) andq 0 =mq .
E K 1 ;E K 2 ;E K 3 ifM 2(f0;1g n ) + thenK K 2 ,andP M elseK K3,andP Mjj10 i ,wherei n 1 jMjmo dn LetP =P 1 jjP 2 jjjjP m ,wherejP 1 j=jP 2 j==jP m j=n C0 0 n for i 1to m 1do Ci EK 1 (PiCi 1) returnEK(PmCm 1) Fig.3.De nition ofFCBC. M 1 ? E -K1 -M 2 ? f ? E -K1 -M 3 ? f ? E -K2 ? T M 1 ? E -K1 -M 2 ? f ? E -K1 -M 3 10 i | {z } ? f ? E -K3 ? T Fig.4.IllustrationofFCBC. 4.3 Pro of ofLemma 4.1
Forarandomp ermutationP andarandomn-bitstring K,let
Q 1 (x) def = P(Kx); Q 2 (x) def = P((Ku)x): We rstshowthatP();Q 1 ();Q 2
()areindistinguishablefromthreeindep endent
randomp ermutationsP 1 ();P 2 ();P 3 ().
Lemma 4.2. LetAbe anadversarywhi hasksatmostq queries.Then
Pr (P R Perm(n);K R f0;1g n :A P();P(K);P((Ku)) =1) Pr (P 1 ;P 2 ;P 3 R Perm(n):A P1();P2();P3() =1) q 2 2 n :
Apro ofisgivenintheapp endix.
Next we re all FCBC whi h app eared in the analysis of XCBC [5℄.FCBC
is a fun tion taking three keys K
1 ;K 2 ;K 3 2K E and a messageM 2 f0;1g ,
and returning astring in f0;1g n
, where E is theunderlying blo k ipher. The
fun tionisde nedinFig.3andillustratedinFig.4.Bla kandRogawayshowed
thefollowingresult forFCBC[5℄.
Prop osition4.1 (Bla k and Rogaway [5℄). Let A be an adversary whi h
asks at most q queries, ea h of whi h is at most nm-bits. Assume m 2 n
Pr (P 1 ;P 2 ;P 3 R Perm(n):A FCBCP 1 ;P 2 ;P 3 () =1) Pr (R R Rand(;n):A R() =1) (2m 2 +1)q 2 2 n :
We nallygiveapro ofofLemma4.1.
Proof (of Lemma4.1).Bythetriangleinequality,
Pr (P 1 R Perm(n);K 2 R f0;1g n :A TMAC P 1 ;K 2 () =1) Pr(R R Rand(;n):A R() =1) (3) isatmost Pr(P 1 ;P 2 ;P 3 R Perm(n):A FCBC P 1 ;P 2 ;P 3 () =1) Pr (R R Rand(;n):A R() =1) (4) + Pr(P 1 R Perm(n);K 2 R f0;1g n :A TMAC P 1 ;K 2 () =1) Pr(P 1 ;P 2 ;P 3 R Perm(n):A FCBC P 1 ;P 2 ;P 3 () =1) : (5)
Prop osition4.1[5℄givesusanupp er b oundon(4).Wenextb ound(5).(5)isat
most Pr (P R Perm(n);K R f0;1g n :A P();P(K);P((Ku)) =1) Pr(P 1 ;P 2 ;P 3 R Perm(n):A P 1 ();P 2 ();P 3 () =1) (6)
sin e any adversary whi h do es well in the setting (5) ould b e onverted to
onewhi hdo es wellinthesetting(6),wherewe assumethat Ain(6)makesat
mostmqtotalqueriestoherora les.ByapplyingLemma4.2,(5)isb oundedby
m 2 q 2 =2 n .Therefore (3)isatmost (2m 2 +1)q 2 2 n + m 2 q 2 2 n = (3m 2 +1)q 2 2 n : u t 5 Dis ussion
5.1 Summaryof Prop erties
Se urityFun tion Message Authenti ation Co de. More generally,
TMAC is a variable input length (f0;1g
)
pseudo-random fun tion (VIPRF) with xed output length
(f0;1g n
).
ErrorPropagation Notappli able.
Syn hronization Notappli able.
Parallelizabil i ty Sequential.
KeyingMaterial Two keys. One blo k ipher key andone n-bitkey,
wherenistheblo k lengthoftheblo k ipher.
Ctr/IV/Non eRequirements None.No ounter/IV/non eisused.
MemoryRequirements Very mo dest. Memory requirements for the CBC
MACplusnbitforkey.
Pre-pro essingCapability Limited. Key-setup of the underlying blo k ipher
and K2 u an b e pre- omputed. Additional
pre- omputation isnotp ossible.
Message-LengthRequirementsArbitrarily length.Anybitstring M 2f0;1g
an
b e omputed,in ludin g theempty string. Thelength
ofthestringneednotb eknowninadvan e.
CiphertextExpansion Notappli able.
5.2 Advantages
ShortKey. TMACrequiresonly(k+n)-bitkeyswhileXCBCuses(k+2n)-bit
keys.
ProvableSe urity. WeprovedthatTMACisavariableinputlength(f0;1g
)
pseudorandomfun tion(VIPRF) with xedoutput length(f0;1g n
)by
as-sumingthattheunderlyingblo k ipherisapseudorandomp ermutation.
EÆ ien y. TMACuses maxf1;djMj=negblo k ipher alls.Theoverhead b
e-yondblo k ipher alls isalmostnegligible.
ArbitrarilyMessageLength. Anybit stringM 2f0;1g
anb e omputed,
in ludingtheemptystring. Thelengthof thestring neednot b e knownin
advan e.
No Re-Keying. Whereas some omp eting s hemes (e.g., in [1,4,11℄) would
requireinvokingEwithtwoorthreedi erentkeys,TMACrequiresonlyone
key asXCBC. Therefore anykey-setup ostsare minimized.This enhan es
eÆ ien yinb oth softwareandhardware.
No de ryption. AsforanyCBCMACvariant,TMACdo esnotusede ryption
oftheblo k ipher.
Ba kwardsCompatibility. TMAC with K
2 = 0
n
is ba kwards ompatible
withtheCBCMAC.
Simpli ity. Be ause TMACissimple,itiseasilyimplementedinb othsoftware
We notethe followinglimitations.They apply to anyCBC MAC variantsand
therefore noneofthemissp e i toTMAC.
SequentialBlo kCipher Calls. TheCBC MACand itsvariants,in luding
TMAC,arenotparallelizable.
LimitedPre-pro essingCapability. Key-setup of the underlying blo k
i-pher and K
2
u an b e pre- omputed. Additional pre- omputation is not
p ossiblewithoutknowingthemessage.
5.4 Design Rationale
TMACisgeneralized toTMACfamilyas follows.Let C
1 and C 2 inf0;1g n b e
twodistin t onstants. Let H : K
H f0;1g n ! f0;1g n b e a(universal) hash
fun tionasfollows,whereK
H
isthesetofp ossiblekeysofH.
Foranyy2f0;1g n ,#fK2K H jH K (C 1 )=y g= #K H 2 n , (7) Foranyy2f0;1g n ,#fK2K H jH K (C 2 )=y g= #KH 2 n ,and (8) Foranyy2f0;1g n ,#fK2K H jH K (C 1 )H K (C 2 )=y g= #KH 2 n . (9) By usingC 1 ;C 2
andH,TMACfamilyissp e i edinFig.5andFig.6.
AlgorithmTMAC E K 1 ;H K 2 ;C 1 ;C 2 (M) ifM 2(f0;1g n ) + thenK H K 2 (C 1 )andP M elseK HK 2 (C2)andP Mjj10 i ,wherei n 1 jMjmo dn LetP=P1jjP2jjjjPm,wherejP1j=jP2j==jPmj=n C0 0 n for i 1to m 1do C i E K 1 (P i C i 1 ) returnEK 1 (PmCm 1 K)
Fig.5.De nitionofTMACfamily.
M 1 ? E -K1 -M 2 ? f ? E -K1 -M 3 ? f ? E -K1 ? T H K 2 (C 1 ) M 1 ? E -K1 -M 2 ? f ? E -K1 -M 3 10 i | {z } ? f ? E -K1 ? T H K 2 (C 2 )
Fig.6.Illustration ofTMACfamily.
We an then prove the se urity of TMAC family similarlyto Lemma 4.1,
Corollary 4.1 and Theorem 4.1. The se urity b ounds are exa tly the sameas
Our hoi eforTMAC orresp onds toK H =f0;1g ,H K (x)=Kx,C 1 =u, and C 2 = 1, or equivalentlyH K (C 1 ) = Ku and H K (C 2 ) = K, where K 2 f0;1g n
. It is easyto see that our hoi e meets the onditions (7),(8),and (9).
Below,we listreasons ofthis hoi e.
{ Weadoptedmultipli ationsinGF(2 n
)sin eitissimple,easytounderstand,
andeasyto implementforappropriate onstants.
{ Weadopted1anduas onstants,sin emultipli ationsby1anduareb oth
easyto implementeÆ ientlyas we haveseen in(1).
{ ThereasonwhyweletH
K (C 1 )=KuandH K (C 2 )=K(notH K (C 1 )=K and H K (C 2
) = Ku) is that, most of the ase we have M 62 (f0;1g n ) + , ratherthanM 2(f0;1g n ) +
,ifthemessageisarandomstring.Thereforewe
have hosen omputationallyeasierwayfor the ase M 62(f0;1g n
) +
.
6 Test Ve tors
Testve torswillb eprovidedinaseparatepap er.
7 Performan eEstimation
SimilarlytoXCBC,TMACuses djMj=neblo k ipherinvo ationsforany
non-empty message M. (The empty string is an ex eption; it requires one blo k
ipherinvo ation.)Overheadb eyond blo k ipher allsisalmostnegligible.
Thesize ofse retkeys isnbitssmallerthan XCBC.The ostforthis short
keyistouseK
2
u.Itis omputedwithonlyoneshiftandone onditionalXOR.
8 Intelle tualProperty Statement
Theauthorsofthispap erhavenopatentrelatedtoTMAC.Asfaraswe know,
TMACis overed bynopatents.
Referen es
1. ANSI X9.19. Ameri annational standard |Finan ial institution retailmessage
authenti ation. ASCX9Se retariat|Ameri anBankersAsso iation, 1986.
2. M.Bellare, R.Guerin,andP.Rogaway. XOR MACs: Newmetho ds formessage
authenti ation using nite pseudorandom fun tions. Advan esin Cryptology |
CRYPTO'95,LNCS963, pp.15{28,Springer-Verlag,1995.
3. M.Bellare, J.Kilian, andP.Rogaway. These urityofthe ipher blo k haining
message authenti ation o de. JCSS, vol. 61, no.3, 2000.Earlier version in
Ad-van esinCryptology|CRYPTO'94,LNCS839, pp.341{358,Springer-Verlag,
1994.
4. A. Berends hot, B. den Bo er, J. P. Boly, A. Bosselaers, J. Brandt, D. Chaum,
I.Damgard,M.Di htl,W.Fumy,M.vanderHam,C.J.A.Jansen,P.Landro k,
B.Preneel,G.Ro elofsen,P.deRo oij, andJ.Vandewalle. FinalRep ortofRACE
key onstru tions. Advan esin Cryptology|CRYPTO 2000,LNCS1880, pp.
197{215,Springer-Verlag,2000.
6. J.Bla kandP.Rogaway.CommentstoNIST on erningAESmo desofop erations:
Asuggestionforhandling arbitrary-length messageswiththeCBCMAC. Se ond
ModesofOperationWorkshop. Available at
http://www. s.u davis.edu/~rogaway/.
7. J. Bla k and P. Rogaway. A blo k- ipher mo de of op eration for parallelizab le
message authenti ation. Advan es in Cryptology| EUROCRYPT 2002,LNCS
2332, pp.384{397,Springer-Verlag,2002.
8. FIPS 113. Computer dataauthenti ation. FederalInformation Pro essing
Stan-dardsPubli atio n 113, U.S.Department ofCommer e/National Bureauof
Stan-dards,NationalTe hni al InformationServi e,Spring eld, Virginia,1994.
9. V.Gligor,andP.Dones u.Fasten ryptionandauthenti ation: XCBCen ryption
andXECBauthenti ation mo des.FastSoftwareEn ryption,FSE2001,toappear
inLNCS, pp.97{111,2001.Fullversionisavailable at
http:// sr .nist.gov/en ryption/modes/proposedmodes/.
10. ISO/IEC9797-1. Informationte hnology |se urity te hniques |dataintegrity
me hanism using a ryptographi he k fun tion employing a blo k ipher
algo-rithm. International OrganizationforStandards,Geneva,Switzerland,1999.
Se -ondedition.
11.
E. Jaulmes,A. Joux,and F.Valette. On these urity of randomized CBC-MAC
b eyondthebirthdayparadoxlimit:Anew onstru tion.FastSoftwareEn ryption,
FSE 2002, to appear in LNCS, pp. 231{245, 2002. Full version is available at
http://eprint.ia r.org/2001/074/.
12. E. Petrankand C.Ra ko . CBCMACforreal-time datasour es. J.Cryptology,
vol.13,no.3,pp.315{338,Springer-Verlag,2000.
A Proof of Lemma 4.2
Let fA (1)
;:::;A (q )
g b e a set of n-bit strings, that is, A (i) 2 f0;1g n for 1 8i q .We say fA (1) ;:::;A (q )
g are distin t as shorthand for A (i)
6=A (j)
for
18i<8jq .
BeforeprovingLemma4.2,we needthefollowinglemma.
Lemma A.1. Letq ;q
1 ;q
2 ;q
3
bepositiveintegerssu h thatq=q
1 +q 2 +q 3 .Let x (1) 1 ;:::;x (q 1 ) 1 ;x (1) 2 ;:::;x (q 2 ) 2 ;x (1) 3 ;:::;x (q 3 ) 3
be xedn-bitstringssu h thatfx (1) 1 ;:::;x (q1) 1 garedistin t,fx (1) 2 ;:::;x (q2) 2 gare distin t,and fx (1) 3 ;:::;x (q3) 3
gare distin t.Similarly,Let
y (1) 1 ;:::;y (q1) 1 ;y (1) 2 ;:::;y (q2) 2 ;y (1) 3 ;:::;y (q3) 3
be xed n-bit stringssu h that fy (1) 1 ;:::;y (q1) 1 ;y (1) 2 ;:::;y (q2) 2 ;y (1) 3 ;:::;y (q3) 3 gare
distin t. Let P 2Perm(n) and K 2f0;1g n
.Then the number of (P ;K) whi h
satis es 8 > < > : P(x (i) 1 )=y (i) 1 for18iq 1 , P(Kx (i) 2 )=y (i) 2 for18iq 2 ,and P((Ku)x (i) 3 )=y (i) 3 for18iq 3 (10)
isatleast(2 (q 1 +q 2 +q 3 ))!(2 (q 1 q 2 +q 1 q 3 +q 2 q 3 )). Wenotethat (2 n (q 1 +q 2 +q 3 ))!(2 n (q 1 q 2 +q 1 q 3 +q 2 q 3 ))(2 n q )! 2 n q 2 2 sin e q 1 q 2 +q 1 q 3 +q 2 q 3 = q 2 q 2 1 q 2 2 q 2 3 2 .
Proof (of LemmaA.1).We rst ountthenumb erofK.
Numberof K. First,forany xediandj su h that 1iq
1
and1j q
2 ,
wehaveexa tly oneK su hthatx (i)
1
=Kx (j)
2
. Sin ethereareq
1 q 2 hoi eof (i;j),we have #fKjx (i) 1 =Kx (j) 2 for19iq 1 and19j q 2 gq 1 q 2 : (11)
Next,for any xed i and j su h that 1i q
1
and 1j q
3
, we have
exa tlyoneKsu hthatx (i)
1
=(Ku)x (j)
3
.Sin ethereareq
1 q 3 hoi eof(i;j), wehave #fKjx (i) 1 =(Ku)x (j) 3 for19iq 1 and19jq 3 gq 1 q 3 : (12)
Next,for any xed i and j su h that 1i q
2
and 1j q
3
, we have
exa tlyoneK su h thatKx (i)
2
=(Ku)x (j)
3
.Sin ethereareq
1 q 3 hoi eof (i;j),we have #fKjKx (i) 2 =(Ku)x (j) 3 for19iq 2 and19j q 3 gq 2 q 3 : (13)
Then from(11), (12) and (13),we have at least 2 n (q 1 q 2 +q 1 q 3 +q 2 q 3 ) hoi e ofK2f0;1g n
whi hsatis esthefollowingthree onditions:
8 > < > : x (i) 1 6=Kx (j) 2 for18iq 1 and18j q 2 , x (i) 1 6=(Ku)x (j) 3 for18iq 1 and18j q 3 ,and Kx (i) 2 6=(Ku)x (j) 3 for18iq 2 and18j q 3 .
Wenow xanyKwhi hsatis esthesethree onditions.
Numberof P. NowKis xedinsu h awaythat
fx (1) 1 ;:::;x (q1) 1 ;Kx (1) 2 ;:::;Kx (q2) 2 ;(Ku)x (1) 3 ;:::;(Ku)x (q3) 3 g
(whi hareinputsto P)aredistin t.Also,the orresp ondingoutputs
fy (1) 1 ;:::;y (q 1 ) 1 ;y (1) 2 ;:::;y (q 2 ) 2 ;y (1) 3 ;:::;y (q 3 ) 3 g
aredistin t.Inotherwords,forP,theab oveq
1 +q
2 +q
3
input-outputpairsare
determined. Theremaining2 n (q 1 +q 2 +q 3
)input-outputpairsare
undeter-mined.Thereforewehave(2 n (q 1 +q 2 +q 3
))!p ossible hoi eofP foranysu h
{ atleast2 n (q 1 q 2 +q 1 q 3 +q 2 q 3 ) hoi eofK,and { (2 n (q 1 +q 2 +q 3
))! hoi eofP whenK is xed.
This on ludesthepro ofof thelemma. ut
Wenowprove Lemma4.2.
Proof (of Lemma 4.2).LetO
1 ;O 2 ;O 3 b e eitherP(), P(K),P((Ku)) orP 1 (),P 2 (),P 3
().TheadversaryAhasora le a essto O
1 ,O 2 andO 3 .
Therearethreetyp esofqueriesA anmake:either(1;x)whi hdenotesthe
query \what is O
1
(x)?," (2;x) whi h denotes the query \what is O
2
(x)?," or
(3;x)whi hdenotesthequery\whatisO
3
(x)?."Forthei-th queryAmakesto
O
j
,de nethequery-answerpair(x (i) j ;y (i) j )2f0;1g n f0;1g n
,whereA'squery
was(j;x (i)
j
)andtheansweritgotwas y (i)
j .
Withoutloss ofgenerality,we assumethatA makesq
1 queries to O 1 (x),q 2 queries toO 2 (x), andq 3 queries toO 3 (x), whereq 1 +q 2 +q 3 =q .Further,we
assumethat Aisdeterministi (otherwise we onsiderarbitrarily xedrandom
tap e). De neviewv ofAas v=h(x (1) 1 ;y (1) 1 );:::;(x (q1) 1 ;y (q1) 1 ); (x (1) 2 ;y (1) 2 );:::;(x (q 2 ) 2 ;y (q 2 ) 2 ); (x (1) 3 ;y (1) 3 );:::;(x (q3) 3 ;y (q3) 3 )i :
Wesaythatvisapossibleview ifthefollowingthree onditionsaresatis ed:
8 > < > : fy (1) 1 ;:::;y (q 1 ) 1 garedistin t, fy (1) 2 ;:::;y (q2) 2
garedistin t, and
fy (1) 3 ;:::;y (q 3 ) 3 garedistin t.
Wenotethatsin e Anever rep eats aquery,we have
8 > < > : fx (1) 1 ;:::;x (q 1 ) 1 garedistin t, fx (1) 2 ;:::;x (q 2 ) 2
garedistin t,and
fx (1) 3 ;:::;x (q 3 ) 3 garedistin t.
We also note that sin e A is deterministi , the i-th query A makes is fully
determinedbythe rsti 1query-answerpairs.Thenthenumb erofallp ossible
viewN all isN all = (2 n )! (2 n q 1 )! (2 n )! (2 n q 2 )! (2 n )! (2 n q 3 )!
. Similarly,the nal output ofA
(0 or 1) dep ends onlyon v .Hen e denote by C
A
(v ) the nal output of Aas a
fun tionofv .
Let v
one
b e a set of all p ossible view v su h that A outputs 1. That is,
v one def = fv j C A (v ) = 1g. We let N one def = #v one . Also, let v good b e a set of
all p ossible view v su h that fy (1) 1 ;:::;y (q1) 1 ;y (1) 2 ;:::;y (q2) 2 ;y (1) 3 ;:::;y (q3) 3 g are distin t. We let N good def = #v good , then N good = (2 n )! (2 n (q 1 +q 2 +q 3 ))! . Therefore we have #fvjv 2(v one \v good )gN one (N all N good ) : (14)
rand p rand def = Pr(P 1 ;P 2 ;P 3 R Perm(n):A P1();P2();P3() =1) : Wehave p rand = #f(P 1 ;P 2 ;P 3 )jA P 1 ();P 2 ();P 3 () =1g f(2 n )!g 3 : Forea h v2v one ,thenumb erof (P 1 ;P 2 ;P 3 )su h that 8 > < > : P 1 (x (i) 1 )=y (i) 1 for18iq 1 , P 2 (x (i) 2 )=y (i) 2 for18iq 2 ,and P 3 (x (i) 3 )=y (i) 3 for18iq 3 (15) isexa tly (2 n q 1 )!(2 n q 2 )!(2 n q 3 )!. Therefore,wehave p rand = X v 2vone #f(P 1 ;P 2 ;P 3 )j(P 1 ;P 2 ;P 3 )satisfying(15)g f(2 n )!g 3 =N one (2 n q 1 )!(2 n q 2 )!(2 n q 3 )! f(2 n )!g 3 = N one N all : Evaluation of p real . Wenext evaluate p real def = Pr(P R Perm(n);K R f0;1g n :A P();P(K);P((Ku)) =1) : Wehave p real = #f(P ;K)jA P();P(K);P((Ku)) =1g (2 n )!2 n :
ThenfromLemmaA.1,wehave
p real X v 2(vone\v good ) #f(P ;K)j(P ;K)satisfying(10)g (2 n )!2 n X v 2(vone\v good ) (2 n q )! (2 n )! 1 q 2 22 n : From(14)we have p real (N one N all +N good ) (2 n q )! (2 n )! 1 q 2 22 n = N one N all 1+ N good N all N all (2 n q )! (2 n )! 1 q 2 22 n : (16)
N good N all 1 q (q 1) 22 n and N all (2 n q )! (2 n )! 1 :
The rstinequalityfollowssin e
N good N all = Q 1iq 1 1 i 2 n Q 1iq 1 1 1 i 2 n Q 1iq 2 1 1 i 2 n Q 1iq 3 1 1 i 2 n Y 1iq 1 1 i 2 n 1 1+2++(q 1) 2 n :
Thenfrom(16)wehave
p real p rand q (q 1) 22 n 1 q 2 22 n p rand q 2 2 n : (17)
Applyingthesameargumentto1 p
real and 1 p rand yieldsthat 1 p real 1 p rand q 2 2 n : (18)
Finally,(17)and(18)givejp
real p rand j q 2 2 n . ut
