International Association
for Cryptologic Research

Integral, zero-correlation (ZC), and impossible-differential (ID) attacks are three of the most important attacks on block ciphers. However, manually finding these attacks can be a daunting task, which is why automated methods are becoming increasingly important. Most of the automatic tools regarding integral, ZC and ID attacks have been focused only on finding distinguishers rather than complete attacks. At EUROCRYPT 2023, Hadipour et al. proposed a generic and efficient constraint programming (CP) model based on satisfiability for finding ID, ZC, and integral distinguishers. This new model can be extended to a unified CP model for finding full key recovery attacks. However, their method has some limitations, including the fact that the location of contradiction should be determined in advance, and the model is a cell-wise model unsuitable for weakly aligned ciphers, e.g., Ascon and PRESENT. In addition, they left developing a CP model for the partial-sum technique in key recovery as a future work.

In this paper, we improve the method by Hadipour et al. in several ways. First, we remove the limitation of determining the contradiction location in advance. Second, we show how to extend the distinguisher model to a bit-wise model, considering the internal structure of S-boxes and keeping the model based on satisfiability. Third, we introduce a CP model for the partial-sum technique for the first time. To show the usefulness and versatility of our approach, we applied it to different designs, from strongly aligned designs such as ForkSKINNY and QARMAv2 to weakly aligned designs such as Ascon and PRESENT, obtaining significantly improved results. To mention a few of our results, we improve the integral distinguisher of QARMAv2-128 (resp. QARMAv2-64) by 7 (resp. 5) rounds, and the integral distinguisher of ForkSKINNY by 1 round, only thanks to our cell-wise distinguisher modelings. By using our new bit-wise modeling, our tool can find a group of $2^{155}$ 5-round ID and ZC distinguishers for Ascon in only one run, taking a few minutes on a regular laptop. Thanks to the new CP model for the partial-sum technique, we could improve the integral attacks on all variants of SKINNY. Particularly, we improved the best attack on SKINNY-$n$-$n$ in the single-key setting by 1 round. We also improved the ID attacks on ForkSKINNY and analyzed this cipher in the limited reduced-round setting for the first time. Our methods are generic and applicable to other block ciphers.