CryptoDB
Generic Attacks Against Beyond-Birthday-Bound MACs
| Authors: | |
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | CRYPTO 2018 |
| 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. |
Video from CRYPTO 2018
BibTeX
@inproceedings{crypto-2018-28843,
title={Generic Attacks Against Beyond-Birthday-Bound MACs},
booktitle={Advances in Cryptology – CRYPTO 2018},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={10991},
pages={306-336},
doi={10.1007/978-3-319-96884-1_11},
author={Gaëtan Leurent and Mridul Nandi and Ferdinand Sibleyras},
year=2018
}