CISPA
Browse
cispa_all_3853.pdf (897.85 kB)

Towards Tight Security Bounds for OMAC, XCBC and TMAC

Download (897.85 kB)
conference contribution
posted on 2023-11-29, 18:25 authored by Soumya Chattopadhyay, Ashwin Jha, Mridul Nandi
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 264 messages before rekeying (same as the birthday bound). In comparison, the previous bound only allows 248 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.

History

Preferred Citation

Soumya Chattopadhyay, Ashwin Jha and Mridul Nandi. Towards Tight Security Bounds for OMAC, XCBC and TMAC. In: International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)

Legacy Posted Date

2022-10-15

Open Access Type

  • Green

BibTeX

@inproceedings{cispa_all_3853, title = "Towards Tight Security Bounds for OMAC, XCBC and TMAC", author = "Chattopadhyay, Soumya and Jha, Ashwin and Nandi, Mridul", booktitle="{International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC