Cryptology ePrint Archive: Report 2020/188

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

Tim Beyne and Anne Canteaut and Itai Dinur and Maria Eichlseder and Gregor Leander and Gatan Leurent and Mara Naya-Plasencia and Lo Perrin and Yu Sasaki and Yosuke Todo and Friedrich Wiemer

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.

Category / Keywords: secret-key cryptography / Hash functions, integrity proof systems, GMiMC, HadesMiMC, Integral attacks

Original Publication (with major differences): IACR-CRYPTO-2020

Date: received 15 Feb 2020, last revised 22 Jun 2020

Contact author: anne canteaut at 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

Available format(s): PDF | BibTeX Citation

Version: 20200622:154904 (All versions of this report)

Short URL: ia.cr/2020/188


[ Cryptology ePrint archive ]