Practical Algebraic Attacks against some Arithmetization-oriented Hash Functions

Augustin Bariant (1) , Clémence Bouvier (2) , Gaëtan Leurent (1) , Léo Perrin (1)

1 COSMIQ - Cryptologie symétrique, cryptologie fondée sur les codes et information quantique
2 SU - Sorbonne Université

Several challenges have been announced on arithmetization-oriented hash functions, with bounties funded by the Ethereum Foundation. In this note, we report on our work to solve several of these challenges, on Feistel-MiMC, Rescue Prime and Poseidon. Our results are obtained by writing the challenges as systems of polynomial equations over the large field, and solving them with off-the-shelf tools (SageMath, NTL, Magma).

Mots clés: Arithmetization-oriented hash functions; Poseidon; Feistel-MiMC; Rescue Prime; algebraic cryptanalysis

Domaines: Cryptographie et sécurité [cs.CR]; Mathématique discrète [cs.DM]

Augustin Bariant, Clémence Bouvier, Gaëtan Leurent, Léo Perrin. Practical Algebraic Attacks against some Arithmetization-oriented Hash Functions. [Research Report] Inria. 2022. ⟨hal-03518757⟩