### Towards Tight Security Bounds for OMAC, XCBC and TMAC

##### 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)
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

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.