Comparison of CBC MAC Variants and Comments
on NIST’s Consultation Paper
Tetsu Iwata
Department of Computer and Information Sciences,
Ibaraki University
4–12–1 Nakanarusawa, Hitachi, Ibaraki 316-8511, Japan
iwata@cis.ibaraki.ac.jp
May 5, 2003

1SummaryIn this note, we present a comparison of the following CBC MAC variants:• RMAC by Jaulmes, Joux and Valette [9, 10, 5, 6],• EMAC from ISO 9797-1 [1, 13],
• XCBC by Black and Rogaway [3, 4],• TMAC by Kurosawa and Iwata [12], and• OMAC by Iwata and Kurosawa [7].
We consider two RMACs. One is RMAC deﬁned in NIST’s draft [5], which we write RMAC1, withparameter set IV or V, where AES is used as the underlying block cipher, and uses a nonce R. The otherone is RMAC mode 2 stated in NIST’s consultation paper [6], which we write RMAC2, where AES128
is used to compute the CBC MAC tag, AES256 is used to encrypt it, and uses a nonce R. We write
RMAC to mean both RMAC1 and RMAC2 1 .

2Security Comparison

In this section, we show a security comparison.
• Let F [E] denote a MAC F with E as the underlying block cipher, where F is RMAC, EMAC,XCBC, TMAC, or OMAC, and E is TDES112, TDES168, AES128, AES192, or AES256. We write
TDES to mean both TDES112 and TDES168, and we write AES to mean AES128, AES192 andAES256. RMAC[TDES] is considered just for completeness.
• Advmac
F [E] (t, q, L) is the maximum forgery probability, where the maximum is over all adversaries
who run in time at most t, make at most q queries, and the total length of all queries are at mostL blocks.
 • Advprp
E (t , q ) is the the maximum distinguishing probability between the block cipher E and arandomly chosen permutation, where the maximum is over all adversaries who run in time at mostt , and make at most q  queries.

1 We do not consider RMAC with randomly chosen R in the original submission [9, 10], since a nonce is allowed in [5, 6].

1• Advprp−rka(t , q  ) is the the maximum distinguishing probability between the block cipher E andΦk ⊕ ,Ea family of randomly chosen permutations (ideal block cipher) in the related key attack scenario,
where the maximum is over all adversaries who run in time at most t  , and make at most q queries.
• m denotes the length of the tag. If there is no output truncation, then m = 64 for TDES andm = 128 for AES.

2.1

Security Bounds with TDES

• Advmac
RMAC[TDES] (t, q, L) ≤3L2
1
prp−rka  + m + Advprp
TDES (t , q ) + AdvΦk ⊕ ,TDES (t , q ),64
22where t = t + O(L), q  = L, t = t + O(L), and q  = q [11, p .2].

• Advmac
EMAC[TDES] (t, q, L) ≤3L21prp  + m + Advprp
TDES (t , q ) + AdvTDES (t , q ),2642
where t = t + O(L), q  = L, t = t + O(L) and q  = q [13, Theorem 1].

• Advmac
XCBC[TDES] (t, q, L) ≤3L21
 + m + Advprp
TDES (t , q ),2642
where t = t + O(L) and q  = L [8, Theorem 3.1].

• Advmac
TMAC[TDES] (t, q, L) ≤3L21 + m + Advprp
TDES (t , q ),64
22
where t = t + O(L) and q  = L [8, Theorem 3.1].

• Advmac
OMAC[TDES] (t, q, L) ≤4L21
 + m + Advprp
TDES (t , q ),2642
where t = t + O(L) and q  = L + 1 [8, Theorem 3.1].

2.2

Security Bounds with AES• Advmac
RMAC[AES] (t, q, L) ≤3L2
1prp−rka  + m + Advprp
AES (t , q ) + AdvΦk ⊕ ,AES (t , q ),2128
2
where t = t + O(L), q  = L, t = t + O(L), and q  = q [11, p .2].

• Advmac
EMAC[AES] (t, q, L) ≤3L21prp  + m + Advprp
AES (t , q ) + AdvAES (t , q ),2128
2
where t = t + O(L), q  = L, t = t + O(L) and q  = q [13, Theorem 1].

• Advmac
XCBC[AES] (t, q, L) ≤3L21
 + m + Advprp
AES (t , q ),2128
2
where t = t + O(L) and q  = L [8, Theorem 3.1].

• Advmac
TMAC[AES] (t, q, L) ≤3L21 + m + Advprp
AES (t , q ),21282where t = t + O(L) and q  = L [8, Theorem 3.1].

• Advmac
OMAC[AES] (t, q, L) ≤4L21
 + m + Advprp
AES (t , q ),128
22
where t = t + O(L) and q  = L + 1 [8, Theorem 3.1].

2.3

Comments• For RMAC[TDES], we added 0.5L2 /264 + 0.5q 2 /264 ≤ L2 /264 to the bound 2L2 /264 stated in [11],since we consider a random permutation rather than a random function. Also, we added 1/2 m since
we consider a forgery probability rather than a distinguishing probability. The same comment goesfor EMAC[TDES], RMAC[AES], and EMAC[AES].
• Bounds for XCBC, TMAC and OMAC are formally proved in [8].

2

2.4Discussions

In NIST’s consultation paper [6, p. 2, Sec. Security, Proof bounds with AES], it is stated that the security
bound of RMAC[AES] is (517L + t)/2 128 . However:• The bound requires randomly chosen R. Thus, this bound has nothing to do with RMAC withnonce R.
• The corresponding proof [9, Sec. 4.1] is incorrect as was suggested by Rogaway [14, p. 3, Sec. 2.2].
Thus, it is not appropriate to use the bound (517L + t)/2 128 for a comparison, and we believe that thesecurity bound of RMAC[AES] should be understood as the bound stated in [11], which is apparently
worse than that of EMAC as discussed below.
In RMAC submitter’s comment [11] and NIST’s consultation paper [6], it is stated that RMAC withnonce R is as secure as EMAC. However, it seems to be false.
Rogaway’s comment [14] already illustrates this. In [14, p. 3, Sec. 2.2], it is shown that assuming theunderlying block cipher to be a pseudorandom permutation is not suﬃcient for proving the security ofRMAC. This fact does not change even if the RMAC submitters provide the reduction based securitybound.
It may be interpreted as follows: Suppose that the underlying block cipher is a pseudorandom per mutation (that is, Advprp
E (t , q ) is suﬃciently small). Then EMAC is a secure MAC, while RMAC may
prp−rka  not (since AdvΦk ⊕ ,E (t , q ) may be large). Therefore, the security bound of EMAC is better than thatof RMAC.
Here is another example: Suppose that we have found a related key attack against AES. That is,(t , q  ) is no more negligible. Then the security bound of RMAC becomes meaningless, while
Advprp−rka
Φk ⊕ ,AES
this fact has nothing to do with the security bounds of EMAC.
Although a related key attack against AES may not be found, this clearly illustrates the security gap
between EMAC and RMAC, and, at least, we may conclude that the security bound of EMAC is better
than that of RMAC with nonce R.
NIST’s consultation paper states that the security bound of EMAC is better than that of XCBC.
However, in [8], we have proved that XCBC (and TMAC and OMAC) are as secure as EMAC 2 . In fact,for both TDES and AES, we see that there is no signiﬁcant diﬀerence among the security of EMAC,XCBC, TMAC and OMAC. These four MACs are equally secure.

3Eﬃciency Comparison

In this section, we show an eﬃciency comparison.
In what follows:• “K len.” denotes the key length.
• “#K sche.” denotes the number of block cipher key schedulings. It is desirable to minimize this,since TDES and AES have non-trivial key scheduling cost. For RMAC, it requires one block cipher
key scheduling each time generating a tag.
• “#M ” denotes the number messages which the sender has MACed.
• “#E invo.” denotes the number of block cipher invocations to generate a tag for a message M ,assuming |M | > 0.
• “#E pre.” denotes the number of block cipher invocations during the pre-processing time. Theseblock cipher invocations can be done without the message.
• “+kst” means that the key separation technique is used. OMAC does not need the key separation
technique since its key length is optimal in its own form.
• For RMAC2, we assume that AES128 is used to compute the CBC MAC tag, and AES256 is used
to encrypt it.
2 We believe that the results in [8] are mostly trivial for those who are working in this area.

3

3.1

Eﬃciency Comparison without Key Separation Technique
Table 1. Eﬃciency Comparison with TDES112.
Name
RMAC1[TDES112]
EMAC[TDES112]
XCBC[TDES112]
TMAC[TDES112]
OMAC[TDES112]

K len.
224
224
240
176
112

#K sche.
1 + #M
211
1#E invo.
1 + (|M | + 1)/64
1 + (|M | + 1)/64
|M |/64
|M |/64
|M |/64

#E pre.
0000
1

Table 2. Eﬃciency Comparison with TDES168.
Name
RMAC1[TDES168]
EMAC[TDES168]
XCBC[TDES168]
TMAC[TDES168]
OMAC[TDES168]

K len.
336
336
296
232
168

#K sche.
1 + #M
21
1
1#E invo.
1 + (|M | + 1)/64
1 + (|M | + 1)/64
|M |/64
|M |/64
|M |/64#E pre.
00001

Table 3. Eﬃciency Comparison with AES128.
Name
RMAC1[AES128]
RMAC2[AES128]
EMAC[AES128]
XCBC[AES128]
TMAC[AES128]
OMAC[AES128]

K len.
256384
256
384
256
128

#K sche.
1 + #M
1 + #M2
11
1#E invo.
1 + (|M | + 1)/128
1 + |M |/128
1 + (|M | + 1)/128
|M |/128
|M |/128
|M |/128

#E pre.
000001

Table 4. Eﬃciency Comparison with AES192.
Name
RMAC1[AES192]
EMAC[AES192]
XCBC[AES192]
TMAC[AES192]
OMAC[AES192]K len.
384384448
320
192#K sche.
1 + #M2
11
1#E invo.
1 + (|M | + 1)/128
1 + (|M | + 1)/128
|M |/128
|M |/128
|M |/128

#E pre.
0000
1

Table 5. Eﬃciency Comparison with AES256.
Name
RMAC1[AES256]
EMAC[AES256]
XCBC[AES256]
TMAC[AES256]
OMAC[AES256]

K len.
512
512
512
384
256

#K sche.
1 + #M
2
111

4#E invo.
1 + (|M | + 1)/128
1 + (|M | + 1)/128
|M |/128
|M |/128
|M |/128

#E pre.
00001

3.2

Eﬃciency Comparison with Key Separation Technique
Table 6. Eﬃciency Comparison with TDES112 and Key Separation Technique.
Name
RMAC1[TDES112] + kst
EMAC[TDES112] + kst
XCBC[TDES112] + kst
TMAC[TDES112] + kst
OMAC[TDES112]

K len.
112
112
112
112
112

#K sche.
2 + #M322
1#E invo.
1 + (|M | + 1)/64
1 + (|M | + 1)/64
|M |/64
|M |/64
|M |/64

#E pre.
44431

Table 7. Eﬃciency Comparison with TDES168 and Key Separation Technique.
Name
RMAC1[TDES168] + kst
EMAC[TDES168] + kst
XCBC[TDES168] + kst
TMAC[TDES168] + kst
OMAC[TDES168]

K len.
168168168168168#K sche.
2 + #M322
1#E invo.
1 + (|M | + 1)/64
1 + (|M | + 1)/64
|M |/64
|M |/64
|M |/64

#E pre.
665
41

Table 8. Eﬃciency Comparison with AES128 and Key Separation Technique.
Name
RMAC1[AES128] + kst
RMAC2[AES128] + kst
EMAC[AES128] + kst
XCBC[AES128] + kst
TMAC[AES128] + kst
OMAC[AES128]

K len.
128128128128128128#K sche.
2 + #M
2 + #M322
1#E invo.
1 + (|M | + 1)/128
1 + |M |/128
1 + (|M | + 1)/128
|M |/128
|M |/128
|M |/128

#E pre.
222
3
2
1

Table 9. Eﬃciency Comparison with AES192 and Key Separation Technique.
Name
RMAC1[AES192] + kst
EMAC[AES192] + kst
XCBC[AES192] + kst
TMAC[AES192] + kst
OMAC[AES192]

K len.
192
192
192
192
192

#K sche.
2 + #M322
1#E invo.
1 + (|M | + 1)/128
1 + (|M | + 1)/128
|M |/128
|M |/128
|M |/128

#E pre.
3343
1Table 10. Eﬃciency Comparison with AES256 and Key Separation Technique.
Name
RMAC1[AES256] + kst
EMAC[AES256] + kst
XCBC[AES256] + kst
TMAC[AES256] + kst
OMAC[AES256]

3.3

K len.
256
256
256
256
256

#K sche.
2 + #M322
1#E invo.
1 + (|M | + 1)/128
1 + (|M | + 1)/128
|M |/128
|M |/128
|M |/128

#E pre.
4443
1Discussions

None of RMAC, EMAC, XCBC, TMAC and OMAC is optimal in all eﬃciency measures: “K len.,”“#K sche.,” “#E invo.,” and “#E pre.” There is a tradeoﬀ among the above four measures.
Key length: In Tables 1–5, we see that OMAC gives the best performance. We note that OMAC is
as secure as EMAC, XCBC, and TMAC despite of its optimal key length.
In Tables 6–10, the key lengths of RMAC, EMAC, XCBC and TMAC can be reduced to the optimallength. But the cost appears in the number of key schedulings and the number of block cipher invocations
during the pre-processing time.

5Number of key schedulings: RMAC requires one block cipher key scheduling each time generatinga tag. This might be signiﬁcant since TDES and AES have non-trivial key scheduling cost.
In Tables 1–5, XCBC, TMAC and OMAC give the best performance, while EMAC requires two blockcipher key schedulings.
In Tables 6–10, it is obvious that OMAC gives the best performance.
Number of block cipher invocations: In Tables 1–10, RMAC and EMAC requires one or two extra
block cipher invocations compared to XCBC, TMAC and OMAC.
This overhead is signiﬁcant for short messages, which is very common in practice.
Number of block cipher invocations during the pre-processing time: In Tables 1–5, only
OMAC requires one block cipher invocation. But this is not very signiﬁcant since:• it can be done in an idle time, and• it is performed infrequently compared to MAC generation. Thus one or two block cipher invocations
to generate a tag in RMAC and EMAC is much more signiﬁcant since it is performed on eachmessage.
In OMAC, the gain for this cost is its optimal key length, which completely eliminates the need forthe key separation technique. We believe this is a very reasonable and desirable tradeoﬀ since:• key separation technique is a very error-prone process in practice, and• key separation technique is used in many environment, but if it is used, then other MACs have asigniﬁcant key setup cost compared to OMAC.
In fact, we see that the performance of OMAC is far better than RMAC, EMAC, XCBC and TMAC inTables 6–10. Especially, 6 TDES invocations during the pre-processing time in EMAC[TDES168] is alarge cost.
We believe that OMAC gives the best performance and tradeoﬀ in eﬃciency.

4Conclusion

In the last line of [6], it is stated that “For applications that desire additional security assurance, RMAC
can be retained as an option in parameter sets IV or V, possibly with the “mode 2” construction.”
We believe this is not appropriate one to move forward, since:• RMAC2 is not the best choice from a security view point as already pointed out in [14, 2, 15], as
well as in this note, and• it is not the best choice from an eﬃciency view point.
We also claim the following problems:• RMAC2 uses two block ciphers: AES128 and AES256 (according to Table 1 of [6]), which increases
the implementation cost, and• it makes a restriction on the choice of the underlying block cipher (AES128 can not be used in thelast encryption).
We think such a restriction signiﬁcantly limits the wide spread use of the mode. RMAC1 has alreadythis problem, since TDES is not allowed, we think the limitation in RMAC2 is even worse.
In contrast, there is no such limitations in EMAC, XCBC, TMAC and OMAC.

6Recommendation: For security, EMAC, XCBC, TMAC and OMAC are better than RMAC. On theother hand, there is no signiﬁcant diﬀerence among EMAC, XCBC, TMAC and OMAC. These four MACs
are equally secure. For eﬃciency, OMAC gives the best performance. Therefore, our recommendation
would be OMAC (especially OMAC1, which simpliﬁes implementations). If it is not possible for somereason, then we recommend either XCBC or TMAC. They are more eﬃcient than EMAC and as secureas EMAC. Again, if it is not possible for some reason, then we recommend to set r = 0 in both parameter
sets IV and V (thus, choose EMAC). It is not as eﬃcient as OMAC, TMAC and XCBC, but it is moresecure than RMAC.

References[1] A. Berendschot, B. den Boer, J. P. Boly, A. Bosselaers, J. Brandt, D. Chaum, I. Damgård, M. Dichtl,W. Fumy, M. van der Ham, C. J. A. Jansen, P. Landrock, B. Preneel, G. Roelofsen, P. de Rooij, andJ. Vandewalle. Final Report of RACE Integrity Primitives. LNCS 1007, Springer-Verlag, 1995.
[2] J. Black. Comments on Draft SP 800-38B, Available at
http://csrc.nist.gov/encryption/modes/.
[3] J. Black and P. Rogaway. CBC MACs for arbitrary-length messages: The three key constructions.
Advances in Cryptology — CRYPTO 2000, LNCS 1880, pp. 197–215, Springer-Verlag, 2000.
[4] J. Black and P. Rogaway. Comments to NIST concerning AES modes of operations: A suggestion for handling arbitrary-length messages with the CBC MAC. NIST submission. Available at
http://www.cs.ucdavis.edu/~rogaway/.
[5] M. Dworkin. Recommendation for block cipher modes of operation: the RMAC authentication mode.
NIST special publication 800-38B, Available at http://csrc.nist.gov/encryption/modes/.
[6]

Consultation paper on the selection of a block cipher based MAC algorithm.
http://csrc.nist.gov/encryption/modes/.

Available at[7] T. Iwata and K. Kurosawa. OMAC: One-Key CBC MAC. Pre-proceedings of Fast Software Encryption, FSE 2003, pp. 137–161, 2003. To appear in LNCS, Springer-Verlag.
[8] T. Iwata and K. Kurosawa. Stronger security bounds for OMAC, TMAC and XCBC. Manuscript.
Available at Cryptology ePrint Archive, Report 2003/082, http://eprint.iacr.org/.
[9] É. Jaulmes, A. Joux, and F. Valette. On the security of randomized CBC-MAC beyond the birthdayparadox limit: A new construction. Fast Software Encryption, FSE 2002, LNCS 2365, pp. 237–251, Springer-Verlag, 2002. Full version is available at Cryptology ePrint Archive, Report 2001/074,
http://eprint.iacr.org/.
[10] É. Jaulmes, A. Joux, and F. Valette. RMAC a randomized MAC beyond the birthday paradoxlimit. NIST submission. Available at http://csrc.nist.gov/encryption/modes/.
[11] É. Jaulmes, A. Joux, and F. Valette. A remark on the security of RMAC in the related-key security
model. Available at http://csrc.nist.gov/encryption/modes/.
[12] K. Kurosawa and T. Iwata. TMAC: Two-Key CBC MAC. Topics in Cryptology — CT-RSA 2003,
LNCS 2612, pp. 33–49, Springer-Verlag, 2003.
[13] E. Petrank and C. Rackoﬀ. CBC MAC for real-time data sources. J.Cryptology, vol. 13, no. 3, pp.
315–338, Springer-Verlag, 2000.
[14] P. Rogaway. Comments on NIST’s RMAC Proposal. Comments on Draft SP 800-38B, Available at
http://csrc.nist.gov/encryption/modes/.
[15] D. Wagner. Comments on RMAC. Comments on Draft SP 800-38B, Available at
http://csrc.nist.gov/encryption/modes/.

7