Paper 2022/668
Key-Reduced Variants of 3kf9 with Beyond-Birthday-Bound Security
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
-
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},
note = {\url{https://eprint.iacr.org/2022/668}},
url = {https://eprint.iacr.org/2022/668}
}
