International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Probabilistic Extensions: A One-Step Framework for Finding Rectangle Attacks and Beyond

Authors:
Qianqian Yang , Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering
Ling Song , College of Cyber Security, Jinan University
Yincen Chen , College of Cyber Security, Jinan University
Lei Hu , State Key Laboratory of Information Security, Institute of Information Engineering
Jian Weng , College of Cyber Security, Jinan University
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2024
Abstract: In differential-like attacks, the process typically involves extending a distinguisher forward and backward with probability 1 for some rounds and recovering the key involved in the extended part. Particularly in rectangle attacks, a holistic key recovery strategy can be employed to yield the most efficient attacks tailored to a given distinguisher. In this paper, we treat the distinguisher and the extended part as an integrated entity and give a one-step framework for finding rectangle attacks with the purpose of reducing the overall complexity or attacking more rounds. In this framework, we propose to allow probabilistic differential propagations in the extended part and incorporate the holistic recovery strategy. Additionally, we introduce the ``split-and-bunch technique'' to further reduce the time complexity. Beyond rectangle attacks, we extend these foundational concepts to encompass differential attacks as well. To demonstrate the efficiency of our framework, we apply it to Deoxys-BC-384, SKINNY, ForkSkinny, and CRAFT, achieving a series of refined and improved rectangle attacks and differential attacks. Notably, we obtain the first 15-round attack on Deoxys-BC-384, narrowing its security margin to only one round. Furthermore, our differential attack on CRAFT extends to 23 rounds, covering two more rounds than the previous best attacks.
BibTeX
@inproceedings{eurocrypt-2024-33923,
  title={Probabilistic Extensions: A One-Step Framework for Finding Rectangle Attacks and Beyond},
  publisher={Springer-Verlag},
  author={Qianqian Yang and Ling Song and Yincen Chen and Lei Hu and Jian Weng},
  year=2024
}