Paper 2024/347
The Algebraic Freelunch: Efficient Gröbner Basis Attacks Against Arithmetization-Oriented Primitives
Abstract
In this paper, we present a new type of algebraic attack that applies to many recent arithmetization-oriented families of permutations, such as those used in Griffin, Anemoi, ArionHash, and XHash8, whose security relies on the hardness of the constrained-input constrained-output (CICO) problem. We introduce the FreeLunch approach: the monomial ordering is chosen so that the natural polynomial system encoding the CICO problem already is a Gröbner basis. In addition, we present a new dedicated resolution algorithm for FreeLunch systems of complexity lower than applicable state-of-the-art FGLM algorithms. We show that the FreeLunch approach challenges the security of fullround instances of Anemoi, Arion and Griffin. We confirm these theoretical results with experimental results on those three permutations. In particular, using the FreeLunch attack combined with a new technique to bypass 3 rounds of Griffin, we recover a CICO solution for 7 out of 10 rounds of Griffin in less than four hours on one core of AMD EPYC 7352 (2.3GHz).
Note: Updated version matching the CRYPTO paper.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- A minor revision of an IACR publication in CRYPTO 2024
- Keywords
- Algebraic attacksGröbner basisFreeLunchSymmetric cryptanalysisGriffinArionAnemoi
- Contact author(s)
-
augustin bariant @ inria fr
aurelien boeuf @ inria fr
axel lemoine @ inria fr
irati @ simula no
morten oygarden @ simula no
leo perrin @ inria fr
haavardr @ simula no - History
- 2024-05-30: revised
- 2024-02-27: received
- See all versions
- Short URL
- https://ia.cr/2024/347
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/347,
author = {Augustin Bariant and Aurélien Boeuf and Axel Lemoine and Irati Manterola Ayala and Morten Øygarden and Léo Perrin and Håvard Raddum},
title = {The Algebraic Freelunch: Efficient Gröbner Basis Attacks Against Arithmetization-Oriented Primitives},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/347},
year = {2024},
url = {https://eprint.iacr.org/2024/347}
}
