Paper 2018/809

Algebraic Cryptanalysis of Frit

Christoph Dobraunig, Maria Eichlseder, 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).

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
cryptanalysisFrithigher-order differentialsinterpolation attack
Contact author(s)
maria eichlseder @ iaik tugraz at
History
2018-09-06: received
Short URL
https://ia.cr/2018/809
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/809,
      author = {Christoph Dobraunig and Maria Eichlseder and Florian Mendel and Markus Schofnegger},
      title = {Algebraic Cryptanalysis of Frit},
      howpublished = {Cryptology ePrint Archive, Paper 2018/809},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/809}},
      url = {https://eprint.iacr.org/2018/809}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.