Paper 2022/723

Optimizing Rectangle Attacks: A Unified and Generic Framework for Key Recovery

Ling Song, College of Information Science and Technology, Jinan University, Guangzhou, China
Nana Zhang, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Qianqian Yang, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Danping Shi, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Jiahao Zhao, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Lei Hu, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Jian Weng, College of Information Science and Technology, Jinan University, Guangzhou, China
Abstract

The rectangle attack has shown to be a very powerful form of cryptanalysis against block ciphers. Given a rectangle distinguisher, one expects to mount key recovery attacks as efficiently as possible. In the literature, there have been four algorithms for rectangle key recovery attacks. However, their performance vary from case to case. Besides, numerous are the applications where the attacks lack optimality. In this paper, we investigate the rectangle key recovery in depth and propose a unified and generic key recovery algorithm, which supports any possible attacking parameters. Notably, it not only covers the four previous rectangle key recovery algorithms, but also unveils five types of new attacks which were missed previously. Along with the new key recovery algorithm, we propose a framework for automatically finding the best attacking parameters, with which the time complexity of the rectangle attack will be minimized using the new algorithm. To demonstrate the efficiency of the new key recovery algorithm, we apply it to Serpent, CRAFT, SKINNY and Deoxys-BC-256 based on existing distinguishers and obtain a series of improved rectangle attacks.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
Boomerang attack Rectangle attack Key recovery algorithm Serpent CRAFT SKINNY Deoxys-BC
Contact author(s)
songling qs @ gmail com
zhangnana @ iie ac cn
yangqianqian @ iie ac cn
shidanping @ iie ac cn
zhaojiahao @ iie ac cn
hulei @ iie ac cn
cryptjweng @ gmail com
History
2022-09-20: revised
2022-06-06: received
See all versions
Short URL
https://ia.cr/2022/723
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/723,
      author = {Ling Song and Nana Zhang and Qianqian Yang and Danping Shi and Jiahao Zhao and Lei Hu and Jian Weng},
      title = {Optimizing Rectangle Attacks: A Unified and Generic Framework for Key Recovery},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/723},
      year = {2022},
      url = {https://eprint.iacr.org/2022/723}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.