(2022) Towards Tight Security Bounds for OMAC, XCBC and TMAC.
|
Text
main.pdf Download (919kB) | Preview |
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 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.
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Divisions: | Antoine Joux (AJ) Benoît-Michel Cogliati (BC) |
| Conference: | ASIACRYPT International Conference on the Theory and Application of Cryptology and Information Security |
| Depositing User: | Ashwin Jha |
| Date Deposited: | 15 Oct 2022 12:14 |
| Last Modified: | 15 Oct 2022 12:14 |
| Primary Research Area: | NRA1: Trustworthy Information Processing |
| URI: | https://publications.cispa.saarland/id/eprint/3853 |
Actions
Actions (login required)
 |
View Item |