International Association for Cryptologic Research

International Association
for Cryptologic Research


Improving Key-Recovery in Linear Attacks: Application to 28-round PRESENT

Antonio Flórez Gutiérrez , Inria, France
María Naya-Plasencia , Inria, France
DOI: 10.1007/978-3-030-45721-1_9 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: Linear cryptanalysis is one of the most important tools in use for the security evaluation of symmetric primitives. Many improvements and refinements have been published since its introduction, and many applications on different ciphers have been found. Among these upgrades, Collard et al. proposed in 2007 an acceleration of the key-recovery part of Algorithm 2 for last-round attacks based on the FFT. In this paper we present a generalized, matrix-based version of the previous algorithm which easily allows to take into consideration an arbitrary number of key-recovery rounds. We also provide efficient variants that exploit the key-schedule relations and that can be combined with multiple linear attacks. Using our algorithms we provide some new cryptanalysis on PRESENT, including, to the best of our knowledge, the first attack on 28 rounds.
Video from EUROCRYPT 2020
  title={Improving Key-Recovery in Linear Attacks: Application to 28-round PRESENT},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  keywords={Linear cryptanalysis;FFT;Walsh Transform;Algorithm 2;key-recovery algorithm;PRESENT},
  author={Antonio Flórez Gutiérrez and María Naya-Plasencia},