Paper 2020/188

Out of Oddity -- New Cryptanalytic Techniques against Symmetric Primitives Optimized for Integrity Proof Systems

Tim Beyne, Anne Canteaut, Itai Dinur, Maria Eichlseder, Gregor Leander, Gaëtan Leurent, María Naya-Plasencia, Léo Perrin, Yu Sasaki, Yosuke Todo, and Friedrich Wiemer


The security and performance of many integrity proof systems like SNARKs, STARKs and Bulletproofs highly depend on the underlying hash function. For this reason several new proposals have recently been developed. These primitives obviously require an in-depth security evaluation, especially since their implementation constraints have led to less standard design approaches. This work compares the security levels offered by two recent families of such primitives, namely GMiMC and HadesMiMC. We exhibit low-complexity distinguishers against the GMiMC and HadesMiMC permutations for most parameters proposed in recently launched public challenges for STARK-friendly hash functions. In the more concrete setting of the sponge construction corresponding to the practical use in the ZK-STARK protocol, we present a practical collision attack on a round-reduced version of GMiMC and a preimage attack on some instances of HadesMiMC. To achieve those results, we adapt and generalize several cryptographic techniques to fields of odd characteristic.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2020
Hash functionsintegrity proof systemsGMiMCHadesMiMCIntegral attacks
Contact author(s)
anne canteaut @ inria fr
gaetan leurent @ inria fr
yu sasaki sk @ hco ntt co jp
Maria Naya_Plasencia @ inria fr
maria eichlseder @ iaik tugraz at
Gregor Leander @ rub de
yu sasaki sk @ hco ntt co jp
leo perrin @ inria fr
todo yosuke @ gmail com
friedrich wiemer @ rub de
dinuri @ cs bgu ac il
tim beyne @ student kuleuven be
2020-11-11: last of 3 revisions
2020-02-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tim Beyne and Anne Canteaut and Itai Dinur and Maria Eichlseder and Gregor Leander and Gaëtan Leurent and María Naya-Plasencia and Léo Perrin and Yu Sasaki and Yosuke Todo and Friedrich Wiemer},
      title = {Out of Oddity -- New Cryptanalytic Techniques against Symmetric Primitives Optimized for Integrity Proof Systems},
      howpublished = {Cryptology ePrint Archive, Paper 2020/188},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.