[Resource Topic] 2018/809: Algebraic Cryptanalysis of Frit

Welcome to the resource topic for 2018/809

Algebraic Cryptanalysis of Frit

Authors: Christoph Dobraunig, Maria Eichlseder, Florian Mendel, Markus Schofnegger


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).

ePrint: https://eprint.iacr.org/2018/809

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .