Paper 2022/668

Key-Reduced Variants of 3kf9 with Beyond-Birthday-Bound Security

Yaobin Shen, Shanghai Jiao Tong University, UCLouvain
Ferdinand Sibleyras, NTT Social Informatics Laboratories
Abstract

3kf9 is a three-key CBC-type MAC that enhances the standardized integrity algorithm f9 (3GPP-MAC). It has beyond-birthday-bound security and is expected to be a possible candidate in constrained environments when instantiated with lightweight blockciphers. Two variants 2kf9 and 1kf9 were proposed to reduce key size for efficiency, but recently, Leurent et al. (CRYPTO'18) and Shen et al. (CRYPTO'21) pointed out critical flaws on these two variants and invalidated their security proofs with birthday-bound attacks. In this work, we revisit previous constructions of key-reduced variants of 3kf9 and analyze what went wrong in security analyzes. Interestingly, we find that a single doubling at the end can not only fix 2kf9 to go beyond the birthday bound, but also help 1kf9 to go beyond the birthday bound. We then propose two new key-reduced variants of 3kf9, called n2kf9 and n1kf9. By leveraging previous attempts, we prove that n2kf9 is secure up to 2^{2n/3} queries, and prove that n1kf9 is secure up to 2^{2n/3} queries when the message space is prefix-free. We also provide beyond-birthday analysis of n2kf9 in the multi-user setting. Note that compared to EMAC and CBC-MAC, the additional cost to provide a higher security guarantee is expected to be minimal for n2kf9 and n1kf9. It only requires one additional blockcipher call and one doubling.

Note: This is the full version of our proceeding paper.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2022
Keywords
Message authentication code CBC-MAC 3kf9 Beyond-birthday-bound security
Contact author(s)
yaobins180 @ gmail com
sibleyras ferdinand ez @ hco ntt co jp
History
2022-09-13: revised
2022-05-29: received
See all versions
Short URL
https://ia.cr/2022/668
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/668,
      author = {Yaobin Shen and Ferdinand Sibleyras},
      title = {Key-Reduced Variants of 3kf9 with Beyond-Birthday-Bound Security},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/668},
      year = {2022},
      url = {https://eprint.iacr.org/2022/668}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.