International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Ling Song , College of Information Science and Technology, Jinan University, Guangzhou, China
Nana Zhang , Institute of Information Engineering, Beijing, China
Qianqian Yang , Institute of Information Engineering, Beijing, China
Danping Shi , Institute of Information Engineering, Beijing, China
Jiahao Zhao , Institute of Information Engineering, Beijing, China
Lei Hu , Institute of Information Engineering, Beijing, China
Jian Weng , College of Information Science and Technology, Jinan University, Guangzhou, China
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2022
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.
Video from ASIACRYPT 2022
BibTeX
@inproceedings{asiacrypt-2022-32450,
  title={Optimizing Rectangle Attacks: A Unified and Generic Framework for Key Recovery},
  publisher={Springer-Verlag},
  author={Ling Song and Nana Zhang and Qianqian Yang and Danping Shi and Jiahao Zhao and Lei Hu and Jian Weng},
  year=2022
}