Paper 2022/1234

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 $$, where $$, $$, and $$, denote the block size of the underlying block cipher, the number of queries, and the maximum permissible query length (in terms of $$-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 $$. 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 $$. In practical terms, this means that for a $$-bit block cipher, and message lengths up to $$ Gigabyte, OMAC can process up to $$ messages before rekeying (same as the birthday bound). In comparison, the previous bound only allows $$ 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 $$) for all the CBC-MAC variants, except for the original CBC-MAC.