Cryptology ePrint Archive: Report 2018/541

Generic Attacks against Beyond-Birthday-Bound MACs

GaŽtan Leurent and Mridul Nandi and 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.

Category / Keywords: secret-key cryptography / Modes of operation, Cryptanalysis, Message Authentication Codes, Beyond-Birthday-Bound security

Original Publication (in the same form): IACR-CRYPTO-2018

Date: received 1 Jun 2018

Contact author: gaetan leurent at inria fr

Available format(s): PDF | BibTeX Citation

Version: 20180604:215314 (All versions of this report)

Short URL: ia.cr/2018/541


[ Cryptology ePrint archive ]