Paper 2018/809

Algebraic Cryptanalysis of Frit

Christoph Dobraunig
Maria Eichlseder
Florian Mendel
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 Frit1 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. 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, we obtain key-recovery attacks with a complexity of either chosen plaintexts and time, or chosen ciphertexts and time (about 10 seconds in practice).

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. SAC 2019
DOI
10.1007/978-3-030-38471-5_7
Keywords
cryptanalysisFrithigher-order differentialsinterpolation attack
Contact author(s)
maria eichlseder @ iaik tugraz at
History
2024-06-07: revised
2018-09-06: received
See all versions
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},
      doi = {10.1007/978-3-030-38471-5_7},
      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.