Paper 2023/1659

Partial Sums Meet FFT: Improved Attack on 6-Round AES

Orr Dunkelman, Computer Science Department, University of Haifa, Haifa, Israel
Shibam Ghosh, Computer Science Department, University of Haifa, Haifa, Israel
Nathan Keller, Department of Mathematics, Bar Ilan University, Ramat Gan, Israel
Gaetan Leurent, Inria, Paris, France
Avichai Marmor, Department of Mathematics, Bar Ilan University, Ramat Gan, Israel
Victor Mollimard, Computer Science Department, University of Haifa, Haifa, Israel
Abstract

The partial sums cryptanalytic technique was introduced in 2000 by Ferguson et al., who used it to break 6-round AES with time complexity of $2^{52}$ S-box computations -- a record that has not been beaten ever since. In 2014, Todo and Aoki showed that for 6-round AES, partial sums can be replaced by a technique based on the Fast Fourier Transform (FFT), leading to an attack with a comparable complexity. In this paper we show that the partial sums technique can be combined with an FFT-based technique, to get the best of the two worlds. Using our combined technique, we obtain an attack on 6-round AES with complexity of about $2^{46.4}$ additions. We fully implemented the attack experimentally, along with the partial sums attack and the Todo-Aoki attack, and confirmed that our attack improves the best known attack on 6-round AES by a factor of more than 32. We expect that our technique can be used to significantly enhance numerous attacks that exploit the partial sums technique. To demonstrate this, we use our technique to improve the best known attack on 7-round Kuznyechik by a factor of more than 80, and to reduce the complexity of the best known attack on the full MISTY1 from $2^{69.5}$ to $2^{67}$.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
AESpartial-sums attackFFT
Contact author(s)
orrd @ cs haifa ac il
sghosh03 @ campus haifa ac il
Nathan Keller @ biu ac il
gaetan leurent @ inria fr
avichai @ elmar co il
victor mollimard @ gmail com
History
2023-10-26: approved
2023-10-26: received
See all versions
Short URL
https://ia.cr/2023/1659
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1659,
      author = {Orr Dunkelman and Shibam Ghosh and Nathan Keller and Gaetan Leurent and Avichai Marmor and Victor Mollimard},
      title = {Partial Sums Meet {FFT}: Improved Attack on 6-Round {AES}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1659},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1659}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.