Paper 2022/1147

Finding the Impossible: Automated Search for Full Impossible-Differential, Zero-Correlation, and Integral Attacks

Hosein Hadipour, Graz University of Technology
Sadegh Sadeghi, Institute for Advanced Studies in Basic Sciences, Zanjan, Iran
Maria Eichlseder, Graz University of Technology
Abstract

Impossible differential (ID), zero-correlation (ZC), and integral attacks are a family of important attacks on block ciphers. For example, the impossible differential attack was the first cryptanalytic attack on 7 rounds of AES. Evaluating the security of block ciphers against these attacks is very important but also challenging: Finding these attacks usually implies a combinatorial optimization problem involving many parameters and constraints that is very hard to solve using manual approaches. Automated solvers, such as Constraint Programming (CP) solvers, can help the cryptanalyst to find suitable attacks. However, previous CP-based methods focus on finding only the ID, ZC, and integral distinguishers, often only in a limited search space. Notably, none can be extended to a unified optimization problem for finding full attacks, including efficient key-recovery steps. In this paper, we present a new CP-based method to search for ID, ZC, and integral distinguishers and extend it to a unified constraint optimization problem for finding full ID, ZC, and integral attacks. To show the effectiveness and usefulness of our method, we applied it to several block ciphers, including SKINNY, CRAFT, SKINNYe-v2, and SKINNYee. For the ISO standard block cipher SKINNY, we significantly improve all existing ID, ZC, and integral attacks. In particular, we improve the integral attacks on SKINNY-$n$-$3n$ and SKINNY-$n$-$2n$ by 3 and 2 rounds, respectively, obtaining the best cryptanalytic results on these variants in the single-key setting. We improve the ZC attack on SKINNY-$n$-$n$ (SKINNY-$n$-$2n$) by 2 (resp. 1) rounds. We also improve the ID attacks on all variants of SKINNY. Particularly, we improve the time complexity of the best previous single-tweakey (related-tweakey) ID attack on SKINNY-$128$-$256$ (resp. SKINNY-$128$-$384$) by a factor of $2^{22.57}$ (resp. $2^{15.39}$). On CRAFT, we propose a 21-round (20-round) ID (resp. ZC) attack, which improves the best previous single-tweakey attack by 2 (resp. 1) rounds. Using our new model, we also provide several practical integral distinguishers for reduced-round SKINNY, CRAFT, and Deoxys-BC. Our method is generic and applicable to other strongly aligned block ciphers.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
DOI
10.1007/978-3-031-30634-1_5
Keywords
Impossible-differential attacksZero-correlation attacksIntegral attacksSKINNYSKINNYe-v2SKINNYeeCRAFTDeoxys-BCCP
Contact author(s)
hossein hadipour @ iaik tugraz at
s sadeghi khu @ gmail com
maria eichlseder @ iaik tugraz at
History
2024-02-29: last of 7 revisions
2022-09-04: received
See all versions
Short URL
https://ia.cr/2022/1147
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1147,
      author = {Hosein Hadipour and Sadegh Sadeghi and Maria Eichlseder},
      title = {Finding the Impossible: Automated Search for Full Impossible-Differential, Zero-Correlation, and Integral Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1147},
      year = {2022},
      doi = {10.1007/978-3-031-30634-1_5},
      note = {\url{https://eprint.iacr.org/2022/1147}},
      url = {https://eprint.iacr.org/2022/1147}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.