International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Tim Beyne , KU Leuven
Anne Canteaut , Inria
Itai Dinur , Ben-Gurion University
Maria Eichlseder , TU Graz and Ruhr-Universität Bochum
Gregor Leander , Ruhr-Universität Bochum
Gaëtan Leurent , Inria
Léo Perrin , Inria
María Naya Plasencia , Inria
Yu Sasaki , NTT Security Labs
Yosuke Todo , NTT Secure Platform Laboratories and Ruhr-Universität Bochum
Friedrich Wiemer , Ruhr-Universität Bochum and Cryptosolutions
DOI: 10.1007/978-3-030-56877-1_11 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2020
Abstract: 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.
Video from CRYPTO 2020
  title={Out of Oddity -- New Cryptanalytic Techniques against Symmetric Primitives Optimized for Integrity Proof Systems},
  author={Tim Beyne and Anne Canteaut and Itai Dinur and Maria Eichlseder and Gregor Leander and Gaëtan Leurent and Léo Perrin and María Naya Plasencia and Yu Sasaki and Yosuke Todo and Friedrich Wiemer},