Cryptology ePrint Archive: Report 2020/182

An Algebraic Attack on Ciphers with Low-Degree Round Functions: Application to Full MiMC

Maria Eichlseder and Lorenzo Grassi and Reinhard Lüftenegger and Morten Ĝygarden and Christian Rechberger and Markus Schofnegger and Qingju Wang

Abstract: Algebraically simple PRFs, ciphers, or cryptographic hash functions are becoming increasingly popular, for example due to their attractive properties for MPC and new proof systems (SNARKs, STARKs, among many others).

In this paper, we focus on the algebraically simple construction MiMC, which became an attractive cryptanalytic target due to its simplicity, but also due to its use as a baseline in a competition for more recent algorithms exploring this design space.

For the first time, we are able to describe key-recovery attacks on all full-round versions of MiMC over GF(2^n), requiring half the codebook. In the chosen-ciphertext scenario, recovering the key from this data for the n-bit full version of MiMC takes the equivalent of less than 2^(n - log_2(n) + 1) calls to MiMC and negligible amounts of memory.

The attack procedure is a generalization of higher-order differential cryptanalysis, and it is based on two main ingredients. First, we present a higher-order distinguisher which exploits the fact that the algebraic degree of MiMC grows significantly slower than originally believed. Secondly, we describe an approach to turn this distinguisher into a key-recovery attack without guessing the full subkey. Finally, we show that approximately ceil(log_3(2 * R)) more rounds (where R = ceil(n * log_3(2)) is the current number of round of MiMC-n/n) can be necessary and sufficient to restore the security against the key-recovery attack presented here.

The attack has been practically verified on toy versions of MiMC. Note that our attack does not affect the security of MiMC over prime fields.

Category / Keywords: secret-key cryptography / Algebraic attack, MiMC, Higher-order differential

Date: received 14 Feb 2020, last revised 22 May 2020

Contact author: markus schofnegger at iaik tugraz at

Available format(s): PDF | BibTeX Citation

Version: 20200522:212518 (All versions of this report)

Short URL: ia.cr/2020/182


[ Cryptology ePrint archive ]