Cryptology ePrint Archive: Report 2018/809

Algebraic Cryptanalysis of Frit

Christoph Dobraunig and Maria Eichlseder and Florian Mendel and Markus Schofnegger

Abstract: Frit is a cryptographic 384-bit permutation recently proposed by Simon et al. and follows a novel design approach for built-in countermeasures against fault attacks. We analyze the cryptanalytic security of Frit in different use-cases and propose attacks on the full-round primitive. We show that the inverse Frit$^{-1}$ of Frit is significantly weaker than Frit from an algebraic perspective, despite the better diffusion of the inverse of the used mixing functions: Its round function has an effective algebraic degree of only about 1.325. We show how to craft structured input spaces to linearize up to 4 (or, conditionally, 5) rounds and thus further reduce the degree. As a result, we propose very low-dimensional start-in-the-middle zero-sum partitioning distinguishers for unkeyed Frit, as well as integral distinguishers for round-reduced Frit and full-round Frit$^{-1}$. We also consider keyed Frit variants using Even-Mansour or arbitrary round keys. By using optimized interpolation attacks and symbolically evaluating up to 5 rounds of Frit$^{-1}$, we obtain key-recovery attacks with a complexity of either $2^{59}$ chosen plaintexts and $2^{67}$ time, or $2^{18}$ chosen ciphertexts and time (about 10 seconds in practice).

Category / Keywords: secret-key cryptography / cryptanalysis, Frit, higher-order differentials, interpolation attack

Date: received 1 Sep 2018, last revised 3 Sep 2018

Contact author: maria eichlseder at iaik tugraz at

Available format(s): PDF | BibTeX Citation

Version: 20180906:192224 (All versions of this report)

Short URL: ia.cr/2018/809


[ Cryptology ePrint archive ]