CryptoDB
The Algebraic Freelunch: Efficient Gröbner Basis Attacks Against Arithmetization-Oriented Primitives
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | CRYPTO 2024 |
| 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 full-round 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). |
BibTeX
@inproceedings{crypto-2024-34190,
title={The Algebraic Freelunch: Efficient Gröbner Basis Attacks Against Arithmetization-Oriented Primitives},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-68385-5_5},
author={Augustin Bariant and Aurélien Bœuf and Axel Lemoine and Irati Manterola Ayala and Morten Øygarden and Léo Perrin and Håvard Raddum},
year=2024
}