Paper 2018/809

Algebraic Cryptanalysis of Frit

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