Paper 2001/074

On the Security of Randomized CBC-MAC Beyond the Birthday Paradox Limit - A New Construction

Eliane Jaulmes, Antoine Joux, and Frederic Valette

Abstract

In this paper, we study the security of randomized CBC-MACs and propose a new construction that resists birthday paradox attacks and provably reaches full security. The size of the MAC tags in this construction is optimal, i.e., exactly twice the size of the block cipher. Up to a constant, the security of the proposed randomized CBC-MAC using an n-bit block cipher is the same as the security of the usual encrypted CBC-MAC using a 2n-bit block cipher. Moreover, this construction adds a negligible computational overhead compared to the cost of a plain, non-randomized CBC-MAC. We give a full standard proof of our construction using one pass of a block cipher with 2n-bit keys but there also is a proof for n-bit keys block ciphers in the ideal cipher model.

Note: This revision includes explanations on MAC truncation. The proof has also been slightly modified, changing the use of the random oracle model for the ideal cipher model.

Metadata
Available format(s)
PS
Category
Cryptographic protocols
Publication info
Published elsewhere. FSE 2002
Keywords
authentication codesblock ciphers
Contact author(s)
eliane jaulmes @ wanadoo fr
History
2002-11-28: last of 2 revisions
2001-08-31: received
See all versions
Short URL
https://ia.cr/2001/074
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2001/074,
      author = {Eliane Jaulmes and Antoine Joux and Frederic Valette},
      title = {On the Security of Randomized CBC-MAC Beyond the Birthday Paradox Limit - A New Construction},
      howpublished = {Cryptology ePrint Archive, Paper 2001/074},
      year = {2001},
      note = {\url{https://eprint.iacr.org/2001/074}},
      url = {https://eprint.iacr.org/2001/074}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.