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

Ling Song; Nana Zhang; Qianqian Yang; Danping Shi; Jiahao Zhao; Lei Hu; Jian Weng

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: 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},
      note = {\url{https://eprint.iacr.org/2022/723}},
      url = {https://eprint.iacr.org/2022/723}
}