Algebraic Cryptanalysis of Variants 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 of Frit is significantly weaker than Frit from an algebraic perspective, despite the better diffusion of the inverse of the 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 reduced-round Frit and full-round 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 we obtain key-recovery attacks with a complexity of either chosen plaintexts and time, or chosen ciphertexts and time (about 5 seconds in practice).