Paper 2019/419

Algebraic Cryptanalysis of STARK-Friendly Designs: Application to MARVELlous and MiMC

Martin R. Albrecht, Carlos Cid, Lorenzo Grassi, Dmitry Khovratovich, Reinhard Lüftenegger, Christian Rechberger, and Markus Schofnegger

Abstract

The block cipher Jarvis and the hash function Friday, both members of the MARVELlous family of cryptographic primitives, are among the first proposed solutions to the problem of designing symmetric-key algorithms suitable for transparent, post-quantum secure zero-knowledge proof systems such as ZK-STARKs. In this paper we describe an algebraic cryptanalysis of Jarvis and Friday and show that the proposed number of rounds is not sufficient to provide adequate security. In Jarvis, the round function is obtained by combining a finite field inversion, a full-degree affine permutation polynomial and a key addition. Yet we show that even though the high degree of the affine polynomial may prevent some algebraic attacks (as claimed by the designers), the particular algebraic properties of the round function make both Jarvis and Friday vulnerable to Gröbner basis attacks. We also consider MiMC, a block cipher similar in structure to Jarvis. However, this cipher proves to be resistant against our proposed attack strategy. Still, our successful cryptanalysis of Jarvis and Friday does illustrate that block cipher designs for “algebraic platforms” such as STARKs, FHE or MPC may be particularly vulnerable to algebraic attacks.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2019
Keywords
Gröbner BasisMARVELlousJarvisFridayMiMCSTARKsAlgebraic CryptanalysisArithmetic Circuits
Contact author(s)
Martin Albrecht @ rhul ac uk
Carlos Cid @ rhul ac uk
lorenzo grassi @ iaik tugraz at
khovratovich @ gmail com
reinhard lueftenegger @ iaik tugraz at
christian rechberger @ iaik tugraz at
markus schofnegger @ iaik tugraz at
History
2019-09-11: last of 3 revisions
2019-04-24: received
See all versions
Short URL
https://ia.cr/2019/419
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/419,
      author = {Martin R.  Albrecht and Carlos Cid and Lorenzo Grassi and Dmitry Khovratovich and Reinhard Lüftenegger and Christian Rechberger and Markus Schofnegger},
      title = {Algebraic Cryptanalysis of STARK-Friendly Designs: Application to MARVELlous and MiMC},
      howpublished = {Cryptology ePrint Archive, Paper 2019/419},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/419}},
      url = {https://eprint.iacr.org/2019/419}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.