Welcome to the resource topic for 2018/541
Title:
Generic Attacks against Beyond-Birthday-Bound MACs
Authors: Gaëtan Leurent, Mridul Nandi, Ferdinand Sibleyras
Abstract: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.
ePrint: https://eprint.iacr.org/2018/541
Talk: https://www.youtube.com/watch?v=kda7nDqHI9I
Slides: https://crypto.iacr.org/2018/slides/Generic%20Attacks%20against%20Beyond-Birthday-Bound%20MACs.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .