Cryptology ePrint Archive: Report 2019/419

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

Martin R. Albrecht and Carlos Cid and Lorenzo Grassi and Dmitry Khovratovich and Reinhard Lüftenegger and 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.

Category / Keywords: secret-key cryptography / Gröbner Basis, MARVELlous, Jarvis, Friday, MiMC, STARKs, Algebraic Cryptanalysis, Arithmetic Circuits

Original Publication (in the same form): IACR-ASIACRYPT-2019

Date: received 23 Apr 2019, last revised 11 Sep 2019

Contact author: Martin Albrecht at 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

Available format(s): PDF | BibTeX Citation

Version: 20190911:114812 (All versions of this report)

Short URL: ia.cr/2019/419


[ Cryptology ePrint archive ]