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 Frit^(-1) 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 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 5 seconds in practice).

Publication
Selected Areas in Cryptography – SAC 2019 - 26th International Conference