You are looking at a specific version 20200218:090204 of this paper. See the latest version.

Paper 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 an ongoing competition for more recent designs 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. Recovering the key from this data for the n-bit 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, a zero-sum distinguisher which exploits the fact that the algebraic degree of MiMC grows much slower than originally believed. Second, an approach to turn the zero-sum distinguisher into a key-recovery attack without needing to guess the full subkey. 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Algebraic AttackMiMCHigher-Order Differential
Contact author(s)
markus schofnegger @ iaik tugraz at
History
2020-12-16: last of 3 revisions
2020-02-18: received
See all versions
Short URL
https://ia.cr/2020/182
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.