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

##### 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.

Available format(s)
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Impossible differential attacks Zero-correlation attacks Integral attacks SKINNY CRAFT SKINNYee Deoxys-BC
Contact author(s)
hossein hadipour @ iaik tugraz at
s sadeghi khu @ gmail com
maria eichlseder @ iaik tugraz at
History
2022-12-20: last of 2 revisions
See all versions
Short URL
https://ia.cr/2022/1147

CC BY

BibTeX

@misc{cryptoeprint:2022/1147,
title = {Finding the Impossible: Automated Search for Full Impossible Differential, Zero-Correlation, and Integral Attacks},
howpublished = {Cryptology ePrint Archive, Paper 2022/1147},
year = {2022},
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.