Paper 2022/1234

Towards Tight Security Bounds for OMAC, XCBC and TMAC

Soumya Chattopadhyay, Indian Statistical Institute, Kolkata, India
Ashwin Jha, CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Mridul Nandi, Indian Statistical Institute, Kolkata, India
Abstract

OMAC --- a single-keyed variant of CBC-MAC by Iwata and Kurosawa --- is a widely used and standardized (NIST FIPS 800-38B, ISO/IEC 29167-10:2017) message authentication code (MAC) algorithm. The best security bound for OMAC is due to Nandi who proved that OMAC's pseudorandom function (PRF) advantage is upper bounded by $ O(q^2\ell/2^n) $, where $ n $, $ q $, and $ \ell $, denote the block size of the underlying block cipher, the number of queries, and the maximum permissible query length (in terms of $ n $-bit blocks), respectively. In contrast, there is no attack with matching lower bound. Indeed, the best known attack on OMAC is the folklore birthday attack achieving a lower bound of $ \Omega(q^2/2^n) $. In this work, we close this gap for a large range of message lengths. Specifically, we show that OMAC's PRF security is upper bounded by $ O(q^2/2^n + q\ell^2/2^n)$. In practical terms, this means that for a $ 128 $-bit block cipher, and message lengths up to $ 64 $ Gigabyte, OMAC can process up to $ 2^{64} $ messages before rekeying (same as the birthday bound). In comparison, the previous bound only allows $ 2^{48} $ messages. As a side-effect of our proof technique, we also derive similar tight security bounds for XCBC (by Black and Rogaway) and TMAC (by Kurosawa and Iwata). As a direct consequence of this work, we have established tight security bounds (in a wide range of $\ell$) for all the CBC-MAC variants, except for the original CBC-MAC.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
Keywords
OMAC CMAC XCBC tMAC CBC-MAC PRF tight security
Contact author(s)
s c 2357 @ gmail com
ashwin jha1991 @ gmail com
mridul nandi @ gmail com
History
2022-09-19: approved
2022-09-17: received
See all versions
Short URL
https://ia.cr/2022/1234
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1234,
      author = {Soumya Chattopadhyay and Ashwin Jha and Mridul Nandi},
      title = {Towards Tight Security Bounds for OMAC, XCBC and TMAC},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1234},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1234}},
      url = {https://eprint.iacr.org/2022/1234}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.