Yanyan Zhou , Senpeng Wang, Bin Hu
Received: 2024-05-09; Revised: 2025-02-27; Accepted: 2025-06-05; Online: 2025-07-11
SIMON is a family of lightweight block ciphers designed by the U.S. National Security Agency (NSA) in 2013. Differential-linear cryptanalysis is an important cryptanalysis method in cryptography, which has received widespread attention since its introduction by Langford and Hellman in 1994. In this paper, we investigate differential-linear cryptanalysis on SIMON. First, we explore the search method for differential-linear distinguishers from an algebraic perspective. By combining the algebraic transitional forms (ATF) technique proposed at CRYPTO 2021 and the automatic search method based on SAT, we obtain differential-linear distinguishers for all versions of SIMON. Second, we introduce dynamic key guessing techniques into differential-linear cryptanalysis, and propose a new framework for key recovery attacks. Finally, we app- ly this new framework to SIMON. As a result, for 20-round SIMON32/64, the data and time complexities are $2^{17.45}$ and $2^{60.63}$, respectively. For the 21-r- ound SIMON48/72, the data and time complexities are $2^{34.95}$ and $2^{67.71}$, respectively. For the 22-round SIMON48/96, 26-round SIMON64/96, 27-round SIMON64/128, 32-round SIMON96/144, 38-round SIMON128/192, and 38-round SIMON128/256, the data complexities are $2^{34.95}$, $2^{43.96}$, $2^{43.96}$, $2^{74.95}$, $2^{106.96}$, and $2^{106.96}$, respectively. The corresponding time complexities are $2^{82.18}$, $2^{88.40}$, $2^{106.89}$, $2^{143.64}$, $2^{178.40}$, and $2^{181.22}$, respectively. To the best of our knowledge, this is the first time that a key-recovery attack has been conducted on all versions of SIMON in differential-linear cryptanalysis. Furthermore, our attack rounds are currently the longest among existing differential-linear c- ryptanalysis results for SIMON.