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

Maria Eichlseder, Lorenzo Grassi, Reinhard Lüftenegger, Morten Øygarden, Christian Rechberger, Markus Schofnegger*, Qingju Wang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

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 F2n, requiring half the code book. 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 2n-log2(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 ⌈ log 3(2 · R) ⌉ more rounds (where R= ⌈ n· log 3(2 ) ⌉ is the current number of rounds 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.

Original languageEnglish
Title of host publicationAdvances in Cryptology – ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, 2020, Proceedings
Subtitle of host publication26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part
EditorsShiho Moriai, Huaxiong Wang
Place of PublicationCham
PublisherSpringer
Pages477-506
Number of pages30
Volume1
ISBN (Print)978-3-030-64836-7
DOIs
Publication statusPublished - 1 Jan 2020
EventASIACRYPT 2020 : International Conference on the Theory and Application of Cryptology and Information Security - Virtuell, Korea, Republic of
Duration: 7 Dec 202011 Dec 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12491 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceASIACRYPT 2020
Country/TerritoryKorea, Republic of
CityVirtuell
Period7/12/2011/12/20

Keywords

  • Algebraic attack
  • Higher-order differential
  • MiMC

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'An Algebraic Attack on Ciphers with Low-Degree Round Functions: Application to Full MiMC'. Together they form a unique fingerprint.

Cite this