×

Generic attacks against beyond-birthday-bound MACs. (English) Zbl 1444.94084

Shacham, Hovav (ed.) et al., Advances in cryptology – CRYPTO 2018. 38th annual international cryptology conference, Santa Barbara, CA, USA, August 19–23, 2018. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 10991, 306-336 (2018).
Summary: 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 Y. Naito [CT-RSA 2018, Lect. Notes Comput. Sci. 10808, 300–318 (2018; Zbl 1507.94051)].{ }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.
For the entire collection see [Zbl 1394.94003].

MSC:

94A60 Cryptography

Citations:

Zbl 1507.94051
PDFBibTeX XMLCite
Full Text: DOI HAL