Welcome to the resource topic for 2022/1147
Title:
Finding the Impossible: Automated Search for Full Impossible Differential, Zero-Correlation, and Integral Attacks (Preliminary Version)
Authors: Hosein Hadipour, Sadegh Sadeghi, Maria Eichlseder
Abstract:Impossible differential (ID) and zero-correlation (ZC) 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 distinguishers. However, previous CP-based methods are focused on finding only the ID or ZC distinguishers, and often only in a limited search space. Notably, none of them 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 and ZC 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 apply it to the ISO standard block cipher SKINNY and improve all of the
existing ID, ZC, and integral attacks on it. 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-2n and SKINNY-n-n by 1 and 2 rounds, respectively.
Applying our tool to discover ID attacks, we improve the ID attacks on all variants of SKINNY in the single-tweakey setting. Particularly, we improve the time complexity of the best previous single key ID attack on SKINNY-128-256 by a factor of 2^{22.57}, while keeping the data and memory complexities much smaller. We also improve the ID attack on SKINNY-n-3n in the related-tweakey setting. Our method is generic and applicable to other word-oriented block ciphers.
ePrint: https://eprint.iacr.org/2022/1147
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .