Paper 2018/541

Generic Attacks against Beyond-Birthday-Bound MACs

Gaëtan Leurent, Mridul Nandi, and Ferdinand Sibleyras


In this work, we study the security of several recent MAC constructions with provable security beyond the birthday bound. We consider block-cipher based constructions with a double-block internal state, such as SUM-ECBC, PMAC+, 3kf9, GCM-SIV2, and some variants (LightMAC+, 1kPMAC+). All these MACs have a security proof up to $2^{2n/3}$ queries, but there are no known attacks with less than $2^{n}$ queries. We describe a new cryptanalysis technique for double-block MACs based on finding quadruples of messages with four pairwise collisions in halves of the state. We show how to detect such quadruples in SUM-ECBC, PMAC+, 3kf9, GCM-SIV2 and their variants with $\mathcal{O}(2^{3n/4})$ queries, and how to build a forgery attack with the same query complexity. The time complexity of these attacks is above $2^n$, but it shows that the schemes do not reach full security in the information theoretic model. Surprisingly, our attack on LightMAC+ also invalidates a recent security proof by Naito. Moreover, we give a variant of the attack against SUM-ECBC and GCM-SIV2 with time and data complexity $\tilde{\mathcal{O}}(2^{6n/7})$. As far as we know, this is the first attack with complexity below $2^n$ against a deterministic beyond-birthday-bound secure MAC. As a side result, we also give a birthday attack against 1kf9, a single-key variant of 3kf9 that was withdrawn due to issues with the proof.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in CRYPTO 2018
Modes of operationCryptanalysisMessage Authentication CodesBeyond-Birthday-Bound security
Contact author(s)
gaetan leurent @ inria fr
2018-06-04: received
Short URL
Creative Commons Attribution


      author = {Gaëtan Leurent and Mridul Nandi and Ferdinand Sibleyras},
      title = {Generic Attacks against Beyond-Birthday-Bound MACs},
      howpublished = {Cryptology ePrint Archive, Paper 2018/541},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.