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.

1 Introduction

The impossible differential (ID) attack, independently introduced by Biham et al. [5] and Knudsen [25], is one of the most important attacks on block ciphers. For example, the ID attack is the first attack breaking 7 rounds of AES-128 [28]. The ID attack exploits an impossible differential in a block cipher, which usually originates from slow diffusion, to retrieve the master key. The zero-correlation (ZC) attack, first introduced by Bogdanov and Rijmen [8], is the dual method of the ID attack in the context of linear analysis, which exploits an unbiased linear approximation to retrieve the master key.

The integral attack is another important attack on block ciphers which was first introduced as a theoretical generalization of differential analysis by Lai [26] and as a practical attack by Daemen et al. [13]. The core idea of integral attacks is finding a set of inputs such that the sum of the resulting outputs is key-independent in some positions. At ASIACRYPT 2012, Bogdanov et al. established a link between the (multidimensional) ZC approximation and integral distinguishers [7]. Sun et al. at CRYPTO 2015 [41] developed further the links among the ID, ZC, and integral attacks. Thanks to this link, we can use search techniques for ZC distinguishers to find integral distinguishers. Ankele et al. studied the influence of the tweakey schedule in ZC analysis of tweakable block ciphers at ToSC 2019 [1] and showed that taking the tweakey schedule into account can result in a longer ZC distinguisher.

The search for ID, ZC, and integral attacks on a block cipher contains two main phases: finding a distinguisher and mounting a key recovery based on the discovered distinguisher. One of the main techniques to find ID and ZC distinguishers is the miss-in-the-middle technique [5, 7]. The idea is to find two differences (linear masks) that propagate halfway through the cipher forward and backward with certainty but contradict each other in the middle. However, applying this technique requires tracing the propagation of differences (resp. linear masks) at the word- or bit-level of block ciphers, which is a time-consuming and potentially error-prone process using a manual approach. When it comes to the key recovery, we should extend the distinguisher at both sides and trace the propagation of more cryptographic properties taking many critical parameters into account. In general, finding an optimum complete ID, ZC, or integral attack usually implies a combinatorial optimization problem which is very hard to solve using a manual approach, especially when the block size is large and there are many possible solutions. Therefore, developing automatic tools is important to evaluate the security of block ciphers against these attacks, mainly, in designing and analyzing lightweight cryptographic primitives, where a higher precision in security analysis lets us minimize security margins.

One approach to solving the optimization problems stemming from cryptanalytic attacks is developing dedicated algorithms. For instance, in CRYPTO 2016, Derbez and Fouque proposed a dedicated algorithm [14] to find $\mathcal{D}\mathcal{S}$-MITM and ID attacks. However, developing and implementing efficient algorithms is difficult and implies a hard programming task. In addition, other researchers may want to adapt these algorithms to other problems with some common features and some differences. This may, again, be very difficult and time-consuming.

Another approach is converting the cryptanalytic problem into a constraint satisfaction problem (CSP) or a constraint optimization problem (COP) and then solving it with off-the-shelf constraint programming (CP) solvers. Recently, many CP-based approaches have been introduced to solve challenging symmetric cryptanalysis problems, which outperform the previous manual or dedicated methods in terms of accuracy and efficiency [20, 30, 37, 39, 46]. For example, at EUROCRYPT 2017, Sasaki and Todo proposed a new automatic tool based on mixed integer linear programming (MILP) solvers to find ID distinguishers [37]. Cui et al. proposed a similar approach to find ID and ZC distinguishers [12]. Sun et al. recently proposed a new CP-based method to search for ID and ZC distinguishers at ToSC 2020 [42].

Although the automatic methods to search for ID, ZC, and integral attacks had significant advances over the past years, they still have some basic limitations:

• The CP models for finding ID/ZC distinguishers proposed in [12, 37, 43] rely on the unsatisfiability of the models where the input/output difference/mask is fixed. This is also the case in all existing CP models to search for integral distinguishers based on division property [15, 44] or monomial prediction [19, 23]. However, finding an optimal key recovery attack is an optimization problem, which is based on satisfiability. Hence, the previous CP models for finding the ID, ZC, and integral distinguishers can not be extended to a unified optimization model for finding a complete attack. The previous CP models for finding ID, ZC, and integral distinguishers also require checking each input/output property individually. As a result, it is computationally hard to find all possible distinguishers when the block size is large enough.

• The CP model proposed in [42] employs the miss-in-the-middle technique to find ID/ZC distinguishers. This approach does not fix the input/output differences/masks. However, the compatibility between the two parts of the distinguisher is checked outside of the CP model by iterating over a loop where the activeness pattern of a state cell at the meeting point should be fixed in each iteration.

• All previous CP models regarding ID, ZC, and integral attacks only focus on finding the longest distinguishers. However, many other important factors affect the final complexity of these attacks, which we can not take into account by only modeling the distinguisher part. For example, the position and the number of active cells in the input/output of the distinguisher, the number of filters in verifying the desired properties at the input/output of distinguishers, and the number of involved key bits in the key recovery are only a few critical parameters that affect the final complexity of the attack but can be considered only by modeling the key recovery part. We show that the best attack does not necessarily require the longest distinguisher. Hence, it is important to unify the key recovery and distinguishing phases for finding better ID, ZC, and integral attacks.

• The tool introduced by Derbez and Fouque [14] is the only tool to find full ID attacks. However, this tool is based on a dedicated algorithm implemented in C/C++ and is not as generic as the CP-based methods. In addition, this tool can not take all critical parameters of ID attacks into account to minimize the final complexity. As other limitations, this tool can not find related-(twea)key ID attacks and is not applicable for ZC and integral attacks.

• None of the previous automatic tools takes the relationship between ZC and integral attacks into account to find ZC distinguishers suitable for integral key recovery. Particularly, there is no automatic tool to take the meet-in-the-middle technique into account for ZC-based integral attacks.

Table 1. Summary of our cryptanalytic results. ID/ZC/Int = impossible differential, zero-correlation, integral. STK/RTK = single/related-tweakey. SK = single-key with given keysize, CP/KP = chosen/known plaintext, CT = chosen tweak. $\dagger$: attack has minor issues.

Our Contributions. We propose a new generic, CP-based, and easy-to-use automatic method to find full ID, ZC, and integral attacks, addressing the above limitations. Unlike all previous CP models for these distinguishers, which are based on unsatisfiability, our CP model relies on satisfiability for finding distinguishers. This way, each solution of our CP models corresponds to an ID, ZC, or integral distinguisher. This key feature enables us to extend our distinguisher models to a unified model for finding an optimal key-recovery attack. Furthermore, our unified CP model takes advantage of key-bridging and meet-in-the-middle techniques. To show the usefulness of our method, we apply it to SKINNY[3], CRAFT [4], SKINNYe-v2 [31], and SKINNYee [32] and significantly improve the ZC, ID, and integral attacks on these ciphers. Table 1 summarizes our results.

• We improve the integral attacks on SKINNY-n-2n and SKINNY-n-3n by 2 and 3 rounds, respectively. To the best of our knowledge, our integral attacks are the best single-key attacks on these variants of SKINNY.

• We improve the ZC attacks on SKINNY-n-n (SKINNY-n-2n) by 2 (resp. 1) rounds. We also propose the first 21-round ZC attack on SKINNY-n-3n. Our ZC attacks are the best attacks on SKINNY in a known-plaintext setting.

• On CRAFT, we provide a 21-round (20-round) single-tweakey ID (resp. ZC) attack that is 2 (resp. 1) rounds longer than the best previous single-tweakey attack proposed on this cipher at ASIACRYPT 2022 [40].

• We improve all previous single-tweakey ID attacks on all variants of SKINNY. We reduce the time complexity of the ID attack on SKINNY-128-256 by a factor of $2^{22.57}$. Our ID attacks are the best single-tweakey attacks on SKINNY-128-128, and all variants of SKINNY-64. We also improved the related-tweakey ID attack on SKINNY-n-3n.

• We provide the first third-party analysis of SKINNYee by proposing 26-round integral and 27-round ID attacks.

• We propose several practical integral distinguishers for reduced round of Deoxys-BC, SKINNY, CRAFT, and SKINNYe-v2/ee (see Table 3).

• Our tool identified several flaws in previous cryptanalytic results on SKINNY (see Table 2). Our tool is efficient and can find all reported results in a few seconds when running on a regular laptop. Its source code is publicly available at the following link: https://github.com/hadipourh/zero

Outline. We recall the background on ID and ZC attacks and review the link between ZC and integral attacks in Sect. 2. In Sect. 3, we show how to convert the problem of searching for ID and ZC distinguishers to a CSP problem. In Sect. 4, we show how to extend our distinguisher models to create a unified model for finding optimum ID attacks. We discuss the extension of our models for ZC and integral attacks in Sect. 5, and finally conclude in Sect. 6. For detailed attack procedures of all analyzed ciphers, we refer to the full version of our paper [21].

Table 2. Attacks with a serious flaw (invalid attacks).

2 Background

Here, we recall the basics of ID and ZC attacks and briefly review the link between the ZC and integral attacks. We also introduce the notations we use in the rest of this paper. We refer to the full version of our paper for the specification of SKINNY and SKINNYe [21, C], CRAFT [21, K.1], and SKINNYee [21, I.1].

2.1 Impossible Differential Attack

The impossible differential attack was independently introduced by Biham et al. [5] and Knudsen [25]. The core idea of an impossible differential attack is exploiting an impossible differential in a cipher to retrieve the key by discarding all key candidates leading to such an impossible differential. The first requirement of the ID attack is an ID distinguisher, i.e., an input difference that can never propagate to a particular output difference. Then, we extend the ID distinguisher by some rounds backward and forward. A candidate for the key that partially encrypts/decrypts a given pair to the impossible differential is certainly not valid. The goal is to discard as many wrong keys as possible. Lastly, we uniquely retrieve the key by exhaustively searching the remaining candidates.

Fig. 1.

Main parameters of the ID attack using an $r_{\textsc {d}}$-round impossible differential distinguisher $\varDelta _{\textsc {u}}\not \rightarrow \varDelta _{\textsc {l}}$. The distinguisher is extended with truncated differential propagation to sets $\varDelta _{\textsc {u}}\rightarrow \varDelta _{\textsc {b}}$ over $r_{\textsc {b}}$ rounds backwards and $\varDelta _{\textsc {l}}\rightarrow \varDelta _{\textsc {f}}$ over $r_{\textsc {f}}$ rounds forward. The inverse differentials $\varDelta _{\textsc {b}}\rightarrow \varDelta _{\textsc {u}}$ and $\varDelta _{\textsc {f}}\rightarrow \varDelta _{\textsc {l}}$ involve $k_{\textsc {b}}, k_{\textsc {f}}$ key bits and have weight $c_{\textsc {b}}, c_{\textsc {f}}$, respectively.

We recall the complexity analysis of the ID attack based on [10, 11]. Let E be a block cipher with n-bit block size and k-bit key. As illustrated in Fig. 1, assume that there is an impossible differential $\varDelta _{\textsc {u}}\nrightarrow \varDelta _{\textsc {l}}$ for $r_{\textsc {d}}$ rounds of E denoted by $E_{\textsc {d}}$. Suppose that $\varDelta _{\textsc {u}}$ ($\varDelta _{\textsc {l}}$) propagates backward (resp. forward) with probability 1 through $E_{\textsc {b}}^{-1}$ (resp. $E_{\textsc {f}}$) to $\varDelta _{\textsc {b}}$ ($\varDelta _{\textsc {f}}$), and $|\varDelta _{\textsc {b}}|$ ($|\varDelta _{\textsc {f}}|$) denotes the dimension of vector space $\varDelta _{\textsc {b}}$ (resp. $\varDelta _{\textsc {f}}$). Let $c_{\textsc {b}}$ ($c_{\textsc {f}}$) be the number of bit-conditions that should be satisfied for $\varDelta _{\textsc {b}}\rightarrow \varDelta _{\textsc {u}}$ (resp. $\varDelta _{\textsc {l}}\leftarrow \varDelta _{\textsc {f}}$), i.e., $\Pr \left( \varDelta _{\textsc {b}}\rightarrow \varDelta _{\textsc {u}}\right) = 2^{-c_{\textsc {b}}}$ (resp. $\Pr \left( \varDelta _{\textsc {l}}\leftarrow \varDelta _{\textsc {f}}\right) = 2^{-c_{\textsc {f}}}$). Moreover, assume that $k_{\textsc {b}}$ ($k_{\textsc {f}}$) denotes the key information, typically subkey bits, involved in $E_{\textsc {b}}$ (resp. $E_{\textsc {f}}$). With these assumptions we can divide the ID attacks into three steps:

• Step 1: Pair Generation. Given access to the encryption oracle (and possibly the decryption oracle), we generate N pairs $(x, y) \in \{0, 1\}^{2n}$ such that $x \oplus y \in \varDelta _{\textsc {b}}$ and $E(x) \oplus E(y) \in \varDelta _{\textsc {f}}$ and store them. This is a limited birthday problem, and according to [11] the complexity of this step is:

  $$\begin{aligned} T_{0} = \max \left\{ \min _{\varDelta \in \{\varDelta _{\textsc {b}}, \varDelta _{\textsc {f}}\}} \left\{ \sqrt{N 2^{n + 1 - |\varDelta |}} \right\} , N 2^{n + 1 - |\varDelta _{\textsc {b}}| - |\varDelta _{\textsc {f}}|} \right\} \end{aligned}$$

  (1)

• Step 2: Guess-and-Filter. The goal of this step is to discard all subkeys in $k_{\textsc {b}}\cup k_{\textsc {f}}$ which are invalidated by at least one of the generated pairs. Rather than guessing all subkeys $k_{\textsc {b}}\cup k_{\textsc {f}}$ at once and testing them with all pairs, we can optimize this step by using the early abort technique [29]: We divide $k_{\textsc {b}}\cup k_{\textsc {f}}$ into smaller subsets, typically the round keys, and guess them step by step. At each step, we reduce the remaining pairs by checking if they satisfy the conditions of the truncated differential trail through $E_{\textsc {b}}$ and $E_{\textsc {f}}$. The minimum number of partial encryptions/decryptions in this step is [10]:

  $$\begin{aligned} T_1 + T_2 = N + 2^{|k_{\textsc {b}}\cup k_{\textsc {f}}|} \frac{N}{2^{c_{\textsc {b}}+ c_{\textsc {f}}}} \end{aligned}$$

  (2)

• Step 3: Exhaustive Search. The probability that a wrong key survives through the guess-and-filter step is $P = \left( 1 - 2^{-(c_{\textsc {b}}+ c_{\textsc {f}})}\right) ^{N}$. Therefore, the number of candidates after performing the guess-and-filter is $P\cdot 2^{|k_{\textsc {b}}\cup k_{\textsc {f}}|}$ on average. On the other hand, the guess-and-filter step does not involve $k - |k_{\textsc {b}}\cup k_{\textsc {f}}|$ bits of key information. As a result, to uniquely determine the key, we should exhaustively search a space of size $T_3 = 2^{k - |k_{\textsc {b}}\cup k_{\textsc {f}}|} \cdot P \cdot 2^{|k_{\textsc {b}}\cup k_{\textsc {f}}|} = 2^{k}\cdot P$.

Then, the total time complexity of the ID attack is:

$$\begin{aligned} T_{tot} = \left( T_{0} + \left( T_{1} + T_{2}\right) C_{E'} + T_{3}\right) C_{E}, \end{aligned}$$

(3)

where $C_{E}$ denotes the cost of one full encryption, and $C_{E'}$ represents the ratio of the cost for one partial encryption to the full encryption.

To keep the data complexity less than the full codebook, we require $T_{0} < 2^{n}$. In addition, to retrieve at least one bit of key information in the guess-and-filter step, $P < \frac{1}{2}$ should hold. Note that Eq. 2 is the average time complexity of the guess-and-filter step; for each ID attack, we must evaluate its complexity accurately to ensure we meet this bound in practice. To see the complexity analysis of the ID attack in the related-(twea)key setting, refer to [21, A].

2.2 Multidimensional Zero-Correlation Attack

Zero-correlation attacks, firstly introduced by Bogdanov and Rijmen [8], are the dual of the ID attack in the context of linear analysis and exploit a linear approximation with zero correlation. The major limitation of the basic ZC attack is its enormous data complexity, equal to the full codebook. To reduce the data complexity of the ZC attack, Bogdanov and Wang proposed the multiple ZC attack at FSE 2012 [9], which utilizes multiple ZC linear approximations. However, the multiple ZC attack relies on the assumption that all involved ZC approximations are independent, which limits its applications. To overcome this assumption of, Bogdanov et al. introduced the multidimensional ZC attack at ASIACRYPT 2012 [7]. We briefly recall the basics of multidimensional ZC attack.

Let $E_{\textsc {d}}$ represent the reduced-round block cipher E with a block size of n bits. Assume that the correlation of m independent linear approximations $\left\langle u_{i}, x \right\rangle + \left\langle w_{i}, E_{\textsc {d}}(x) \right\rangle$ and all their nonzero linear combinations are zero, where $u_{i}, w_{i}, x\in \mathbb {F}_{2}^{n}$, for $i = 0, \dots , m - 1$. We denote by $l = 2^{m}$ the number of ZC linear approximations. In addition, assume we are given N input/output pairs $(x, y = E_{\textsc {d}}(x))$. Then, we can construct a function from $\mathbb {F}_{2}^{n}$ to $\mathbb {F}_{2}^{m}$ which maps x to $z(x) = (z_{0}, \dots , z_{m - 1})$, where $z_{i} := \langle u_{i}, x \rangle + \langle w_{i}, E_{\textsc {d}}(x)\rangle$ for all i. The idea of the multidimensional ZC distinguisher is that the output of this function follows the multivariate hypergeometric distribution, whereas the m-tuples of bits drawn at random from a uniform distribution on $\mathbb {F}_{2}^{m}$ follow a multinomial distribution [7]. For sufficiently large N, we distinguish $E_{\textsc {d}}$ from a random permutation as follows.

We initialize $2^{m}$ counters V[z] to zero, $z\in \mathbb {F}_{2}^{m}$. Then, for each of the N pairs (x, y), we compute $z_{i} = \left\langle u_{i}, x \right\rangle + \left\langle w_{i}, y\right\rangle$ for all $i= 0, \dots , 2^{m} - 1$, and increment V[z] where $z = (z_{0}, \dots , z_{m - 1})$. Finally, we compute the following statistic:

$$\begin{aligned} T = \frac{{N \cdot {2^m}}}{{1 - {2^{ - m}}}}\sum \limits _{z = 0}^{{2^m} - 1} {{{\left( \frac{{V[z]}}{N} - \frac{1}{{{2^m}}}\right) }^2}}. \end{aligned}$$

(4)

For the pairs (x, y) derived from $E_{\textsc {d}}$, i.e., $y = E_{\textsc {d}}(x)$, the statistic T follows a $\chi ^{2}$-distribution with mean ${\mu _0} = (l - 1)\frac{{{2^n} - N}}{{{2^n} - 1}}$ and variance $\sigma _0^2 = 2(l - 1){(\frac{{{2^n} - N}}{{{2^n} - 1}})^2}$. However, it follows a ${\chi ^2}$-distribution with mean ${\mu _1} = (l - 1)$ and variance $\sigma _1^2 = 2(l - 1)$ for a random permutation [7]. By defining a decision threshold $\tau = {\mu _0} + {\sigma _0}{Z_{1 - \alpha }} = {\mu _1} - {\sigma _1}{Z_{1 - \beta }}$, the output of test is ‘cipher’, i.e., the pairs are derived from $E_{\textsc {d}}$, if $T \le \tau$. Otherwise, the output of the test is ‘random’.

This test may wrongfully classify $E_{\textsc {d}}$ as a random permutation (type-I error) or may wrongfully accept a random permutation as $E_{\textsc {d}}$ (type-II error). Let the probability of the type-I and type-II errors be $\alpha$ and $\beta$. Then, the number of required pairs N to successfully distinguish $E_{\textsc {d}}$ from a random permutation is [7]:

$$\begin{aligned} N = \frac{{{2^n}({Z_{1 - \alpha }} + {Z_{1 - \beta }})}}{{\sqrt{l/2} - {Z_{1 - \beta }}}}, \end{aligned}$$

(5)

where $Z_{1 - \alpha }$, and $Z_{1 - \beta }$ are respective quantiles of the standard normal distribution. Thus, the data complexity of the multidimensional ZC attack depends on the number of ZC approximations, $l = 2^{m}$, and the error probabilities $\alpha$ and $\beta$.

To mount a key recovery based on a multidimensional ZC distinguisher for $E_{\textsc {d}}$, we extend $E_{\textsc {d}}$ by a few rounds at both ends, $E = E_{\textsc {f}}\circ E_{\textsc {d}}\circ E_{\textsc {b}}$. Given N plaintext/ciphertext pairs $(p, c = E(p))$, we can recover the key in two steps:

• Step 1: Guess-and-filter. We guess the value of involved key bits in $E_{\textsc {b}}$ ($E_{\textsc {f}}$) and partially encrypt (decrypt) the plaintexts (ciphertexts) to derive N pairs (x, y) for the input $x = E_{\textsc {b}}(p)$ and output $y = E_{\textsc {f}}^{-1}(c)$ of $E_{\textsc {d}}$. Assuming that wrong keys yield pairs (x, y) randomly chosen from $\mathbb {F}_{2}^{2n}$, we use the statistic T to discard all keys for which $T \le \tau$.

• Step 2: Exhaustive Search. Finally, we exhaustively search the remaining key candidates to find the correct key.

The time complexity of the guess-and-filter step depends on the number of pairs N and the size of involved key bits in $E_{\textsc {b}}$ and $E_{\textsc {f}}$. Given that typically a subset of internal variables is involved in the partial encryptions/decryptions, we can take advantage of the partial sum technique [16] to reduce the time complexity of the guess-and-filter step. Moreover, by adjusting the value of $\alpha$ and $\beta$, we can make a trade-off between the time and data complexities as $\alpha$ and $\beta$ affect the data, and $\beta$ influences the time complexity of the exhaustive search.

2.3 Relation Between the Zero-Correlation and Integral Attacks

Bogdanov et al. [7] showed that an integral distinguisher¹ always implies a ZC distinguisher, but its converse is true only if the input and output linear masks of the ZC distinguisher are independent. Later, Sun et al. [41] proposed the following theorem that the conditions for deriving an integral distinguisher from a ZC linear hull in [7] can be removed.

Theorem 1

(Sun et al. [41]). Let $F:\mathbb {F}_{2}^{n}\rightarrow \mathbb {F}_{2}^{n}$ be a vectorial Boolean function. Assume A is a subspace of $\mathbb {F}_{2}^{n}$ and $\beta \in \mathbb {F}_{2}^{n}\setminus \{0\}$ such that $(\alpha , \beta )$ is a ZC approximation for any $\alpha \in A$. Then, for any $\lambda \in \mathbb {F}_{2}^{n}$, $\left\langle \beta , F(x + \lambda )\right\rangle$ is balanced over the set

$$\begin{aligned} A^{\bot } = \{x \in \mathbb {F}_{2}^{n}~|~ \forall ~ \alpha \in A:\left\langle \alpha , x \right\rangle = 0\}. \end{aligned}$$

According to Theorem 1, the data complexity of the resulting integral distinguisher is $2^{n - m}$, where n is the block size and m is the dimension of the linear space spanned by the input linear masks in the corresponding ZC linear hull.

At ToSC 2019, Ankele et al. [1] considered the effect of the tweakey on ZC distinguishers of tweakable block ciphers (TBCs). They showed that taking the tweakey schedule into account can lead to a longer ZC distinguisher and thus a longer integral distinguisher. They proposed Theorem 2, which provides an algorithm to find ZC linear hulls for TBCs following the super-position tweakey (STK) construction of the tweakey framework [24] (see Fig. 2).

Theorem 2

(Ankele et al. [1]). Let $E_{K}(T, P): \mathbb {F}_{2}^{t\times n}\rightarrow \mathbb {F}_{2}^{n}$ be a TBC following the STK construction. Assume that the tweakey schedule of $E_{K}$ has z parallel paths and applies a permutation h on the tweakey cells in each path. Let $(\varGamma _{0}, \varGamma _{r})$ be a pair of linear masks for r rounds of $E_{K}$, and $\varGamma _{1}, \dots , \varGamma _{r - 1}$ represents a possible sequence for the intermediate linear masks. If there is a cell position i such that any possible sequence $\varGamma _{0}[i], \varGamma _{1}[h^{-1}(i)], \varGamma _{2}[h^{-2}(i)], \dots \varGamma _{r}[h^{-r}(i)]$ has at most z linearly active cells, then $(\varGamma _{0}, \varGamma _{r})$ yields a ZC linear hull for r rounds of E.

Fig. 2.

The STK construction of the tweakey framework.

Ankele et al. used Theorem 2 to manually find ZC linear hulls for several twekable block ciphers including SKINNY, QARMA [2], and MANTIS[3]. Later, Hadipour et al. [22] proposed a bitwise automatic method based on SAT to search for ZC linear hulls of tweakable block ciphers. This automatic method was then reused by Niu et al. [34] to revisit the ZC linear hulls of SKINNY-64-$\{$128,192$\}$.

2.4 Constraint Satisfaction and Constraint Optimization Problems

A constraint satisfaction problem (CSP) is a mathematical problem including a set of constraints over a set of variables that should be satisfied. More formally, a CSP is a triple $(\mathcal {X}, \mathcal {D}, \mathcal {C})$, where $\mathcal {X} = \{X_{0}, X_{1}, \dots , X_{n - 1}\}$ is a set of variables; $\mathcal {D} = \{\mathcal {D}_{0}, \mathcal {D}_{1}, \dots , \mathcal {D}_{n - 1}\}$ is the set of domains such that $X_{i} \in \mathcal {D}_{i}$, $0 \le i \le n - 1$; and $\mathcal {C} = \{\mathcal {C}_{0}, \mathcal {C}_{1}, \dots , \mathcal {C}_{n - 1}\}$ is a set of constraints. Each constraint $\mathcal {C}_{j}\in \mathcal {C}$ is a tuple $(\mathcal {S}_{j}, \mathcal {R}_{j})$, where $\mathcal {S}_{j} = \{X_{i_{0}}, \dots , X_{i_{k - 1}}\}\subseteq \mathcal {X}$ and $\mathcal {R}_{j}$ is a relation on the corresponding domains, i.e., $\mathcal {R}_{j} \subseteq \mathcal {D}_{i_{0}} \times \dots \times \mathcal {D}_{i_{k - 1}}$.

Any value assignment of the variables satisfying all constraints of a CSP problem is a feasible solution. The constraint optimization problem extends the CSP problem by including an objective function to be minimized (or maximized). Searching for the solution of a CSP or COP problem is referred to as constraint programming (CP), and the solvers performing the search are called CP solvers.

In this paper, we use MiniZinc [33] to model and solve the CSP and COP problems over integer and real numbers. MiniZinc allows modeling the CSP and COP problems in a high-level and solver-independent way. It compiles the model into FlatZinc, a standard language supported by a wide range of CP solvers. For CSP/COP problems over integer numbers, we use Or-Tools [35], and for CSP/COP problems over real numbers, we employ Gurobi [17] as the solver.

2.5 Encoding Deterministic Truncated Trails

Here, we recall the method proposed in [42] to encode deterministic truncated differential trails. Thanks to the duality relation between differential and linear analysis, one can adjust this method for deterministic truncated linear trails; thus, we omit the details for the linear trails. We define two types of variables to encode the deterministic truncated differential trails. Assume that $\varDelta X = (\varDelta X[0], \dots , \varDelta X[m- 1])$ represents the difference of the internal state X in an n-bit block cipher E, where $n = m\cdot c$, and $\varDelta X[i] \in \mathbb {F}_{2}^{c}$ for all $i = 0, \dots , m- 1$. We use an integer variable $\texttt {AX} [i]$ to encode the activeness pattern of $\varDelta X[i]$ and another integer variable $\texttt {DX} [i]$ to encode the actual $c$-bit difference value of $\varDelta X[i]$:

$$\begin{aligned} \texttt {AX} [i] = {\left\{ \begin{array}{ll} 0 &{} \varDelta X[i] = 0 \\ 1 &{} \varDelta X[i] ~ \text {is nonzero and fixed} \\ 2 &{} \varDelta X[i] ~ \text {can be any nonzero value} \\ 3 &{} \varDelta X[i] ~ \text {can take any value} \end{array}\right. } \qquad \texttt {DX} [i] \in {\left\{ \begin{array}{ll} \{0\} &{} \texttt {AX} [i] = 0 \\ \{1, \dots , 2^{c}\!-\!1\} &{} \texttt {AX} [i] = 1 \\ \{-1\} &{} \texttt {AX} [i] = 2 \\ \{-2\} &{} \texttt {AX} [i] = 3 \end{array}\right. } \end{aligned}$$

Then, we link $\texttt {AX} [i]$ and $\texttt {DX} [i]$ for all $i = 0, \dots , m- 1$ as follows:

$$\begin{aligned} {{\texttt {\textit{Link}}}} (\texttt {AX} [i], \texttt {DX} [i]){:}{=}{\left\{ \begin{array}{ll} {{\texttt {\textit{if}}}} ~ \texttt {AX} [i] = 0 ~ {{\texttt {\textit{then}}}} ~ \texttt {DX} [i] = 0\\ {{\texttt {\textit{elseif}}}} ~ \texttt {AX} [i] = 1 ~ {{\texttt {\textit{then}}}} ~ \texttt {DX} [i] > 0\\ {{\texttt {\textit{elseif}}}} ~ \texttt {AX} [i] = 2 ~ {{\texttt {\textit{then}}}} ~ \texttt {DX} [i] = -1\\ {{\texttt {\textit{else}}}} ~ \texttt {DX} [i] = -2 ~ {{\texttt {\textit{endif}}}} \end{array}\right. } \end{aligned}$$

MiniZinc supports conditional expression ‘if-then-else-endif’, so we do not need to convert to integer inequalities. Next, we briefly explain the propagation rules of deterministic truncated differential trails.

Proposition 1 (Branching)

For $F:\mathbb {F}_{2}^{c}\rightarrow \mathbb {F}_{2}^{2c}$, $F(X) = (Y, Z)$ where $Z = Y = X$, the valid transitions for deterministic truncated differential trails satisfy

$$\begin{aligned} {{\texttt {\textit{Branch}}}} (\texttt {AX}, \texttt {DX}, \texttt {AY}, \texttt {DY}, \texttt {AZ}, \texttt {DZ}):= \left( \texttt {AZ} = \texttt {AX} ~ \wedge ~ \texttt {DZ} = \texttt {DX} ~ \wedge ~ \texttt {AY} = \texttt {AX} ~ \wedge ~ \texttt {DY} = \texttt {DX}\right) \end{aligned}$$

Proposition 2 (XOR)

For $F:\mathbb {F}_{2}^{2c} \rightarrow \mathbb {F}_{2}^{c}$, $F(X, Y) = Z$ where $Z = X \oplus Y$, the valid transitions for deterministic truncated differential trails satisfy

$$\begin{aligned} {{\texttt {\textit{XOR}}}} (\texttt {AX}, \texttt {DX}, \texttt {AY}, \texttt {DY}, \texttt {AZ}, \texttt {DZ})\!{:}{=}\! {\left\{ \begin{array}{ll} {{\texttt {\textit{if}}}} ~ \texttt {AX} + \texttt {AY} > 2 ~ {{\texttt {\textit{then}}}} ~ \texttt {AZ} = 3 \wedge \texttt {DZ} = -2\\ {{\texttt {\textit{elseif}}}} ~ \texttt {AX} + \texttt {AY} = 1 ~ {{\texttt {\textit{then}}}} ~ \texttt {AZ} = 1 \wedge \texttt {DZ} = \texttt {DX} + \texttt {DY} \\ {{\texttt {\textit{elseif}}}} ~ \texttt {AX} = \texttt {AY} = 0 ~ {{\texttt {\textit{then}}}} ~ \texttt {AZ} = 0 \wedge \texttt {DZ} = 0\\ {{\texttt {\textit{elseif}}}} ~ \texttt {DX} + \texttt {DY} < 0 ~ {{\texttt {\textit{then}}}} ~ \texttt {AZ} = 2 \wedge \texttt {DZ} = -1\\ {{\texttt {\textit{elseif}}}} ~ \texttt {DX} = \texttt {DY} ~ {{\texttt {\textit{then}}}} ~ \texttt {AZ} = 0 \wedge \texttt {DZ} = 0\\ {{\texttt {\textit{else}}}} ~ \texttt {AZ} = 1 \wedge \texttt {DZ} = \texttt {DX} \oplus \texttt {DY} ~ {{\texttt {\textit{endif}}}} \end{array}\right. } \end{aligned}$$

Proposition 3 (S-box)

Assume that $S:\mathbb {F}_{2}^{c} \rightarrow \mathbb {F}_{2}^{c}$ is a $c$-bit S-box and $Y = S(X)$. The valid transitions for deterministic truncated differential trails satisfy

$$\begin{aligned} {{\texttt {\textit{S-box}}}} (\texttt {AX}, \texttt {AY})\!{:}{=}\!\left( \texttt {AY} \ne 1 ~ \wedge ~ \texttt {AX} + \texttt {AY} \in \{0, 3, 4, 6\} ~ \wedge ~ \texttt {AY} \ge \texttt {AX} ~ \wedge ~ \texttt {AY} - \texttt {AX} \le 1\right) \end{aligned}$$

For encoding the MDS matrices, see [21, B]. To encode non-MDS matrices, such as the matrix employed in SKINNY, as described in [21, D], we can use the rules of XOR and branching to encode the propagation.

3 Modeling the Distinguishers

Although the key recovery of ZC and ID attacks are different, the construction of ZC and ID distinguishers relies on the same approach, which is the miss-in-the-middle technique [5, 6]. The idea is to find two differences (linear masks) that propagate halfway through the cipher forward and backward with certainty but contradict each other in the middle. The incompatibility between these propagations results in an impossible differential (resp. unbiased linear hull).

Suppose we are looking for an ID or ZC distinguisher for $E_{\textsc {d}}$, which represents $r_{\textsc {d}}$ rounds of a block cipher E. Moreover, we assume that the block size of E is n bits, where $n = m\cdot c$ with $c$ being the cell size and $m$ being the number of cells. We convert the miss-in-the-middle technique to a CSP problem to automatically find ID and ZC distinguishers. We first divide $E_{\textsc {d}}$ into two parts, as illustrated in Fig. 3: An upper part $E_{\textsc {u}}$ covering $r_{\textsc {u}}$ rounds and a lower part $E_{\textsc {l}}$ of $r_{\textsc {l}}$ rounds. Hereafter, we refer to the trails discovered for $E_{\textsc {u}}$ ($E_{\textsc {l}}$) as the upper (lower) trail. We denote the internal state of $E_{\textsc {u}}$ ($E_{\textsc {l}}$) after r rounds by $XU_{r}$ ($XL_{r}$). The state $XU_{r_{\textsc {u}}}$ (or $XL_{0}$) at the intersection of $E_{\textsc {u}}$ and $E_{\textsc {l}}$ is called the meeting point.

Let $\texttt {AXU} _{r}$ and $\texttt {AXL} _{r}$ denote the activeness pattern of the state variables $XU_{r}$ and $XL_{r}$, as shown in Fig. 3. Let $\texttt {DXU} _{r}$ and $\texttt {DXL} _{r}$ denote the actual difference values in round r of $E_{\textsc {u}}$ and $E_{\textsc {l}}$. We encode the deterministic truncated differential trail propagation through $E_{\textsc {u}}$ and $E_{\textsc {l}}$ in opposite directions as two independent CSP problems using the rules described in Sect. 2.5. We exclude trivial solutions by adding the constraints $\sum _{i=0}^{m- 1}\texttt {AXU} _{0}[i] \ne 0$ and $\sum _{i=0}^{m- 1}\texttt {AXL} _{r_{\textsc {l}}} \ne 0$. Let ${{\texttt {\textit{CSP}}}} _{\textsc {u}}(\texttt {AXU} _{0}, \texttt {DXU} _{0}, \dots , \texttt {AXU} _{r_{\textsc {u}}}, \texttt {DXU} _{r_{\textsc {u}}})$ be the model for propagation of deterministic truncated trails over $E_{\textsc {u}}$ and ${{\texttt {\textit{CSP}}}} _{\textsc {l}}(\texttt {AXL} _{0}, \texttt {DXL} _{0}, \dots , \texttt {AXL} _{r_{\textsc {l}}}, \texttt {DXL} _{r_{\textsc {l}}})$ for $E_{\textsc {l}}^{-1}$.

Fig. 3.

Modeling the miss-in-the-middle technique as a CSP problem

The last internal state in $E_{\textsc {u}}$ and the first internal state of $E_{\textsc {l}}$ overlap at the meeting point as they correspond to the same internals state. We define some additional constraints to ensure the incompatibility between the deterministic differential trails of $E_{\textsc {u}}$ and $E_{\textsc {l}}$ at the position of the meeting point:

$$\begin{aligned} \begin{aligned}&{{\texttt {\textit{CSP}}}} _{M}(\texttt {AXU} _{r_{\textsc {l}}}, \texttt {DXU} _{r_{\textsc {l}}}, \texttt {AXL} _{0}, \texttt {DXL} _{0})\!{:}{=}\!\\&\bigvee _{i = 0}^{m- 1}\left( \begin{aligned}&(\texttt {AXU} _{r_{\textsc {u}}}[i] + \texttt {AXL} _{0}[i] > 0) ~ \wedge \\&(\texttt {AXU} _{r_{\textsc {u}}}[i] + \texttt {AXL} _{0}[i] < 3) ~ \wedge \\&~\texttt {AXU} _{r_{\textsc {u}}}[i] \ne \texttt {AXL} _{0}[i] \end{aligned} \right) \vee \bigvee _{i = 0}^{m- 1} \left( \begin{aligned}&\texttt {AXU} _{r_{\textsc {u}}}[i] = 1 ~ \wedge \\&\texttt {AXL} _{0}[i] ~ = 1 ~ \wedge \\&\texttt {DXU} _{r_{\textsc {u}}}[i] \ne \texttt {DXL} _{0}[i] \end{aligned} \right) = {{\texttt {\textit{True}}}} \end{aligned} \end{aligned}$$

(6)

The constraints included in ${{\texttt {\textit{CSP}}}} _{M}$ guarantee the incompatibility between the upper and lower deterministic trails in at least one cell at the meeting point. Lastly, we define ${{\texttt {\textit{CSP}}}} _{\textsc {d}}\!{:}{=}\!{{\texttt {\textit{CSP}}}} _{\textsc {u}}\wedge {{\texttt {\textit{CSP}}}} _{\textsc {l}}\wedge {{\texttt {\textit{CSP}}}} _{M}$, which is the union of all three CSPs. As a result, any feasible solution of ${{\texttt {\textit{CSP}}}} _{\textsc {d}}$ corresponds to an impossible differential. We can follow the same approach to find ZC distinguishers.

Although we encode the deterministic truncated trails in the same way as [42], our method to search for distinguishers has some important differences. Sun et al. [42] solves ${{\texttt {\textit{CSP}}}} _{\textsc {u}}$ and ${{\texttt {\textit{CSP}}}} _{\textsc {l}}$ separately through a loop where the activeness pattern of a cell at the meeting point is fixed in each iteration. The main advantage of our model is that any solutions of ${{\texttt {\textit{CSP}}}} _{\textsc {d}}$ corresponds to an ID (or ZC) distinguisher. In addition, we do not constrain the value of our model at the input/output or at meeting point. These key feature enables us to extend our model for the key recovery and build a unified COP for finding the nearly optimum ID and ZC attacks in the next sections.

We showed how to encode and detect the contradiction in the meeting point. However, the contradiction may occur in other positions, such as in the tweakey schedule (see Theorem 2), leading to longer distinguishers. Next, we show how to generalize this approach to detect the contradiction in the tweakey schedule while searching for ZC-integral distinguishers according to Theorem 2.

Consider a block cipher E that follows the STK construction with z parallel independent paths in the tweakey schedule. Assume that E applies the permutation h to shuffle the position of cells in each path of tweakey schedule. Let $\textit{STK}_{r}[i]$ be the ith cell of subtweakey after r rounds. For all $i = 0, \dots , m- 1$, we define the integer variable $\texttt {ASTK} _{r}[i]\in \{0, 1, 2, 3\}$, to indicate the activeness pattern of $\textit{STK}_{r}[i]$. Then we define the following constraints to ensure that there is a contradiction in the tweakey schedule and the condition of Theorem 2 holds:

$$\begin{aligned} \begin{aligned}&{{\texttt {\textit{CSP}}}} _{\textit{TK}}(\texttt {ASTK} _{0}, \dots , \texttt {ASTK} _{r_{\textsc {d}}- 1})\!{:}{=}\!\\&\bigvee _{i = 0}^{m- 1}\left( \left( \begin{aligned}&\sum _{r = 0}^{r_{\textsc {d}}- 1}{{\texttt {\textit{bool2int}}}} \left( \texttt {ASTK} _{r}[h^{-r}(i)] \ne 0\right) \le z\\&~ \wedge ~ \bigvee _{r = 0}^{r_{\textsc {d}}- 1}\left( \texttt {ASTK} _{r}[h^{-r}(i)] = 1\right) \end{aligned} \right) \vee \left( \bigwedge _{r = 0}^{r_{\textsc {d}}- 1} \texttt {ASTK} _{r}[h^{-r}(i)] = 0\right) \right) \end{aligned} \end{aligned}$$

(7)

Equation 7 guarantees that at least one path of the tweakey schedule has at most z active cells, or it is totally inactive. Finally, we create the CSP problem ${{\texttt {\textit{CSP}}}} _{\textsc {d}}\!{:}{=}\! {{\texttt {\textit{CSP}}}} _{\textsc {u}}\wedge {{\texttt {\textit{CSP}}}} _{\textsc {l}}\wedge {{\texttt {\textit{CSP}}}} _{\textit{TK}}$ to find ZC distinguishers of tweakable block ciphers taking the tweakey schedule into account. According to Eq. 7, if the sequence of linear masks in the involved tweakey lane has z non-zero values, i.e., $\{1, 2\}$, then at least one of the taken non-zero values should be 1. We also practically verified on reduced-round examples that this condition is indeed necessary to obtain valid ZC-integral distinguishers. This essential condition is ignored in [48]; unfortunately, their claimed distinguishers (and hence their attacks) are invalid. We contacted the authors of [48], and they confirmed our claim.

In our model for distinguisher, we assume that the round keys are independent. Thus, our method regards even those differential or linear propagations over multiple rounds that cannot occur due to the global dependency between the round keys as possible propagations. We also consider the S-box as a black box and do not exploit its internal structure. As a result, regardless of the (twea)key schedule and the choice of S-box, the ID/ZC/Integral distinguishers discovered by our method are always valid.

Before extending our models for key recovery, we first show some of the interesting features of our new model for distinguishers. We can optimize the desired property by adding an objective function to our CSP models for finding distinguishers. According to Theorem 1, maximizing the number of active cells at the input of the ZC linear hull is equivalent to minimizing the data complexity of the corresponding integral distinguisher. Therefore, we maximize the integer addition of the activeness pattern at the input of the ZC-Integral distinguisher. Thanks to this feature, we discovered many practical integral distinguishers for reduced-round Deoxys-BC, SKINNY, SKINNYe-v2, SKINNYee, and CRAFT. Table 3 briefly describes the specification of our integral distinguishers for five ciphers. We note that finding integral distinguishers with minimum data complexity is a challenging task using division property [15, 44] or monomial prediction [19, 23], especially when the block cipher employs large S-boxes. However, our tool can find integral distinguishers with low data complexity by only one iteration that takes a few seconds on a regular laptop. For a more detailed comparison between our method and monomial prediction or division property, see [21, M].

Table 3. Summary of integral distinguishers for some ciphers, cell size $c \in \{4, 8\}$.

4 Modeling the Key Recovery for Impossible Differentials

In this section, we present a generic framework which receives four integer numbers ($r_{\textsc {b}}$, $r_{\textsc {u}}$, $r_{\textsc {l}}$, $r_{\textsc {f}}$) specifying the lengths of each part in Fig. 1, and outputs an optimized full ID attack for $r = r_{\textsc {b}}+ r_{\textsc {u}}+ r_{\textsc {l}}+ r_{\textsc {f}}$ rounds of the targeted block cipher. To this end, we extend the CSP model for ID distinguishers in Sect. 3 to make a unified COP model for finding an optimized full ID attack taking all critical parameters affecting the final complexity into account.

Before discussing our framework, we first reformulate the complexity analysis of the ID attack to make it compatible with our COP model. Suppose that the block size is n bits and the key size is k bits. Let N be the number of pairs generated in the pair generation phase, and P represents the probability that a wrong key survives the guess-and-filter step. According to Sect. 2.1, $P = (1 - 2^{-(c_{\textsc {b}}+ c_{\textsc {f}})})^{N}$. Let g be the number of key bits we can retrieve through the guess-and-filter step, i.e., $P = 2^{-g}$. Since $P < \frac{1}{2}$, we have $1 < g \le |k_{\textsc {b}}\cup k_{\textsc {f}}|$. Assuming that $(1 - 2^{-(c_{\textsc {b}}+ c_{\textsc {f}})})^{N} \approx e^{-N\cdot 2^{-(c_{\textsc {b}}+ c_{\textsc {f}})}}$, we have $N = 2^{c_{\textsc {b}}+ c_{\textsc {f}}+ \log _{2}(g) - 0.53}$. Moreover, suppose that ${{\texttt {\textit{LG}}}} (g) = \log _{2}(g) - 0.53$. Therefore, we can reformulate the complexity analysis of the ID attack as follows:

$$\begin{aligned} \begin{aligned}&T_{0} = \max \left\{ \begin{aligned}&\min _{\varDelta \in \{\varDelta _{\textsc {b}}, \varDelta _{\textsc {f}}\}} \{2^{\frac{c_{\textsc {b}}+ c_{\textsc {f}}+ n + 1 - |\varDelta | + {{\texttt {\textit{LG}}}} (g)}{2}}\},\\&2^{c_{\textsc {b}}+ c_{\textsc {f}}+ n + 1 - |\varDelta _{\textsc {b}}| - |\varDelta _{\textsc {f}}| + {{\texttt {\textit{LG}}}} (g)} \end{aligned} \right\} , ~ T_{0}< 2^{n},\\&T_{1} = 2^{c_{\textsc {b}}+ c_{\textsc {f}}+ {{\texttt {\textit{LG}}}} (g)}, ~ T_{2} = 2^{|k_{\textsc {b}}\cup k_{\textsc {f}}| + {{\texttt {\textit{LG}}}} (g)},~ T_{3} = 2^{k - g},\\&T_\text {tot} = \left( T_{0} + \left( T_{1} + T_{2}\right) C_{E'} + T_{3}\right) C_{E}, ~ T_\text {tot}< 2^{k},\\&M_\text {tot} = \min \big \{2^{c_{\textsc {b}}+ c_{\textsc {f}}+ {{\texttt {\textit{LG}}}} (g)}, 2^{|k_{\textsc {b}}\cup k_{\textsc {f}}|} \big \}, ~ M_\text {tot} < 2^{k}. \end{aligned} \end{aligned}$$

(8)

When searching for an optimal full ID attack, we aim to minimize the total time complexity while keeping the memory and data complexities under the threshold values. As can be seen in Eq. 8, $c_{\textsc {b}}, c_{\textsc {f}}, |\varDelta _{\textsc {b}}|, |\varDelta _{\textsc {f}}|$, and $|k_{\textsc {b}}\cup k_{\textsc {f}}|$, are the critical parameters which directly affect the final complexity of the ID attack. To determine $(c_{\textsc {b}}, |\varDelta _{\textsc {b}}|)$, we need to model the propagation of truncated differential trails through $E_{\textsc {b}}$, taking the probability of all differential cancellations into account. To determine $k_{\textsc {b}}$, we need to detect the state cells whose difference or data values are needed through the partial encryption over $E_{\textsc {b}}$. The same applies for partial decryption over $E_{\textsc {f}}^{-1}$ to determine $c_{\textsc {f}}$, $|\varDelta _{\textsc {f}}|$, $k_{\textsc {f}}$. Moreover, to determine the actual size of $k_{\textsc {b}}\cup k_{\textsc {f}}$, we should take the (twea)key schedule and key-bridging technique into account.

4.1 Overview of the COP Model

Our model includes several components:

• Model the distinguisher as in Sect. 3. Unlike the previous methods, our model imposes no constraints on the input/output of the distinguisher.

• Model the difference propagation in outer parts for truncated trails $\varDelta _{\textsc {b}}\xleftarrow {E_{\textsc {b}}^{-1}} \varDelta _{\textsc {u}}$ and $\varDelta _{\textsc {l}}\xrightarrow {E_{\textsc {f}}} \varDelta _{\textsc {f}}$ with probability one. Unlike our model for the distinguisher part, where we use integer variables with domain $\{0, \dots , 3\}$, here, we only use binary variables to encode active/inactive cells. We also model the number of filters $c_{\textsc {b}}$ and $c_{\textsc {f}}$ using new binary variables and constraints to encode the probability of $\varDelta _{\textsc {b}}\xrightarrow {E_{\textsc {b}}} \varDelta _{\textsc {u}}$ and $\varDelta _{\textsc {l}}\xleftarrow {E_{\textsc {f}}^{-1}} \varDelta _{\textsc {f}}$.

• Model the guess-and-determine in outer parts. In this component, we model the determination relationships over $E_{\textsc {b}}$ and $E_{\textsc {f}}$ to detect the state cells whose difference or data values must be known for verifying the differences $\varDelta _{\textsc {u}}$, and $\varDelta _{\textsc {l}}$. Moreover, we model the relation between round (twea)keys and the internal state to detect the (twea)key cells whose values should be guessed during the determination of data values over $E_{\textsc {b}}$, and $E_{\textsc {f}}$.

• Model the key bridging. In this component, we model the (twea)key schedule to determine the number of involved sub-(twea)keys in the key recovery. For this, we can use the general CP-based model for key-bridging proposed by Hadipour and Eichlseder in [18], or cipher-dedicated models.

• Model the complexity formulas. In this component, we model the complexity formulas in Eq. 8 with the following constraints:

  $$\begin{aligned} \begin{aligned}&{{\texttt {\textit{D}}}} [0] \!{:}{=}\! {{\texttt {\textit{min}}}} _{\varDelta \in \{\varDelta _{\textsc {b}}, \varDelta _{\textsc {f}}\}}\{\tfrac{1}{2} (c_{\textsc {b}}+ c_{\textsc {f}}+ n + 1 - |\varDelta | + {{\texttt {\textit{LG}}}} (g))\},\\&{{\texttt {\textit{D}}}} [1] \!{:}{=}\! c_{\textsc {b}}+ c_{\textsc {f}}+ n + 1 - |\varDelta _{\textsc {b}}| - |\varDelta _{\textsc {f}}| + {{\texttt {\textit{LG}}}} (g),\\&{{\texttt {\textit{T}}}} [0] \!{:}{=}\! {{\texttt {\textit{max}}}} \left\{ {{\texttt {\textit{D}}}} [0], {{\texttt {\textit{D}}}} [1] \right\} , ~ {{\texttt {\textit{T}}}} [0]< n,\\&{{\texttt {\textit{T}}}} [1] \!{:}{=}\! c_{\textsc {b}}+ c_{\textsc {f}}+ {{\texttt {\textit{LG}}}} (g), ~ {{\texttt {\textit{T}}}} [2] \!{:}{=}\! |k_{\textsc {b}}\cup k_{\textsc {f}}| + {{\texttt {\textit{LG}}}} (g), ~ {{\texttt {\textit{T}}}} [3] \!{:}{=}\! k - g,\\&{{\texttt {\textit{T}}}} \!{:}{=}\! {{\texttt {\textit{max}}}} \{{{\texttt {\textit{T}}}} [0], {{\texttt {\textit{T}}}} [1], {{\texttt {\textit{T}}}} [2], {{\texttt {\textit{T}}}} [3]\}, ~ {{\texttt {\textit{T}}}} < k.\\ \end{aligned} \end{aligned}$$

  (9)

  Lastly, we set the objective function to $\texttt {Minimize} ~ {{\texttt {\textit{T}}}}$.

All variables in our model are binary or integer variables with a limited domain except for ${{\texttt {\textit{D}}}}$ and ${{\texttt {\textit{T}}}} [i]$ for $i\in \{0, 1, 2, 3\}$ in Eq. 9, which are real numbers. MiniZinc and many MILP solvers such as Gurobi support ${{\texttt {\textit{max}}}}$, and ${{\texttt {\textit{min}}}}$ operators. We also precompute the values of ${{\texttt {\textit{LG}}}} (g)$ with 3 floating point precision for all $g \in \{2, \dots , k\}$, and use the ${{\texttt {\textit{table}}}}$ feature of MiniZinc to model ${{\texttt {\textit{LG}}}} (g)$. As a result, our COP model considers all the critical parameters of the ID attacks. We recall that the only inputs of our tool are four integer numbers to specify the lengths of $E_{\textsc {b}}, E_{\textsc {u}}, E_{\textsc {l}}$, and $E_{\textsc {f}}$. So, one can try different lengths for these four parts to find a nearly optimal attack. We can also modify the objective function of our model to minimize the data or memory complexities where time or any other parameter is constrained. One can extend this single-tweakey model for the related-tweakey setting, as we will show next.

4.2 Detailed Model for SKINNY

Next, we show in more detail how to perform each step. To this end, we build the COP model for finding full related-tweakey ID attacks on SKINNY as an example. We choose the largest variant of SKINNY, i.e., SKINNY-n-3n with cell size $c\in \{4, 8\}$ to explain our model (see [21, C] for the cipher specification). In what follows, given four integer numbers $r_{\textsc {b}}, r_{\textsc {u}}, r_{\textsc {l}}, r_{\textsc {f}}$, we model the full ID attack on $r = r_{\textsc {b}}+ r_{\textsc {u}}+ r_{\textsc {l}}+ r_{\textsc {f}}$ rounds of SKINNY, where $r_{\textsc {d}}= r_{\textsc {u}}+ r_{\textsc {l}}$ is the length of the distinguisher and $r_{\textsc {b}}$, and $r_{\textsc {f}}$ are the lengths of extended parts in backward and forward directions, respectively.

Model the Distinguisher. We first model the difference propagation through the tweakey schedule of SKINNY. For the tweakey schedule of SKINNY, we can either use the word-wise model proposed in [3] or a bit-wise model (see Algorithm 1). Here, we explain the bit-wise model. The tweakey path of TK1 only shuffles the position of tweakey cells in each round. Thus, for tweakey path TK1, we only define the integer variable $\texttt {DTK} {1}[i]$ to encode the $c$-bit difference in the ith cell of TK1. For tweakey path TKm, where $m \in \{2, 3\}$, we define the integer variables $\texttt {DTK} {m}_{r}[i]$ to encode the $c$-bit difference value in the ith cell of $TK{m}_{r}$, where $0 \le i \le 15$. We also define the integer variables $\texttt {ASTK} _{r}[i]$ and $\texttt {DSTK} _{r}[i]$ to encode the activeness pattern as well as the $c$-bit difference value in the ith cell of $STK_{r}$. Our CSP model for the tweakey schedule of SKINNY is a bit-wise model. We use the table feature of MiniZinc to encode the LFSRs. To this end, we first precompute the LFSR as a lookup table and then constrain the variables at the input/output of LFSR to satisfy the precomputed lookup table. This approach is applicable for encoding any function that can be represented as an integer lookup table, such as DDT/LAT of S-boxes. We tested word-wise and bit-wise models and found the word-wise model more efficient.

In the data path of SKINNY, SubCells, AddRoundTweakey, and MixColumns can change the activeness pattern of the state while propagating the deterministic differences. Thus, for the internal state before and after these basic operations, we define two types of variables to encode the activeness pattern and difference value in each state cell. Next, as described in Algorithm 2 and [21, algorithm 6], we build ${{\texttt {\textit{CSP}}}} _{\textsc {u}}$ and ${{\texttt {\textit{CSP}}}} _{\textsc {l}}$. We also build the ${{\texttt {\textit{CSP}}}} _{M}$ according to Eq. 6. The combined CSP model is ${{\texttt {\textit{CSP}}}} _{\textsc {d}}{:}{=}{{\texttt {\textit{CSP}}}} _{\textsc {u}}\wedge {{\texttt {\textit{CSP}}}} _{\textsc {l}}\wedge {{\texttt {\textit{CSP}}}} _{M} \wedge {{\texttt {\textit{CSP}}}} _{DTK}$. Hence, any feasible solution of ${{\texttt {\textit{CSP}}}} _{\textsc {d}}$ corresponds to a related-tweakey ID distinguisher for SKINNY-n-3n. By setting $\texttt {DTK} {3}_{0}$ in Algorithm 1 to zero, we can find related-tweakey ID distinguishers for SKINNY-n-2n. We can also set $\texttt {DTK} {1}, \texttt {DTK} {2}_{0}, \texttt {DTK} {3}_{0}$ in Algorithm 1 to zero to find single-tweakey ID distinguishers of SKINNY.

The first operation in the round function of SKINNY is SubCells. However, we can consider the first SubCells layer as a part of $E_{\textsc {b}}$ and start the distinguisher after it. This way, our model takes advantage of the differential cancellation over the AddRoundTweakey and MixColumns layers to derive longer distinguishers. It happens if the input differences in the internal state (or tweakey paths) are fixed and can cancel out each other through AddRoundTweakey or MixColumns. In this case, we skip the constraints in line 14 of Algorithm 2 for the first round, $r = 0$.

Model the Difference Propagation in Outer Parts. To model the deterministic difference propagations $\varDelta _{\textsc {b}}\xleftarrow {E_{\textsc {b}}^{-1}} \varDelta _{\textsc {u}}$, and $\varDelta _{\textsc {l}}\xrightarrow {E_{\textsc {f}}} \varDelta _{\textsc {f}}$, we define a binary variable for each state cell to indicate whether its difference value is zero. Since the SubCells layer does not change the status of state cells in terms of having zero/nonzero differences, we ignore it in this model.

To model the probability of difference propagations $\varDelta _{\textsc {b}}\!\xrightarrow {E_{\textsc {b}}}\!\varDelta _{\textsc {u}}$, and $\varDelta _{\textsc {l}}\!\xleftarrow {E_{\textsc {f}}^{-1}}\!\varDelta _{\textsc {f}}$, note that there are two types of probabilistic transitions. The first type is differential cancellation through an XOR operation. The second type is any differential transition $(\texttt {truncated} \xrightarrow {S} \texttt {fixed})$ for S-boxes; this is only considered at the distinguisher’s boundary, at the first S-box layer of $E_{\textsc {f}}$ or the last of $E_{\textsc {b}}$.

Let $Z = X \oplus Y$, where $X, Y, Z \in \mathbb {F}_{2}^{c}$. Let $\texttt {AX}, \texttt {AY}, \texttt {AZ} \in \{0, 1\}$ indicate whether the difference of X, Y, Z are zero. We define the new constraint ${{\texttt {\textit{XOR}}}} _{1}$ to model the difference propagation with probability one through XOR:

$$\begin{aligned} {{\texttt {\textit{XOR}}}} _{1}(\texttt {AX}, \texttt {AY}, \texttt {AZ}) {:}{=}(\texttt {AZ} \ge \texttt {AX}) \wedge (\texttt {AZ} \ge \texttt {AY}) \wedge (\texttt {AZ} \le \texttt {AX} + \texttt {AY}) \end{aligned}$$

(10)

We define a binary variable $\texttt {CB} _{r}[i]$ ($\texttt {CF} _{r}[i]$) for each XOR operation in the rth round of $E_{\textsc {b}}$ (resp. $E_{\textsc {f}}$) to indicate whether there is a difference cancellation over the corresponding XOR, where $0 \le i \le 19$. We also define the following constraint to encode the differential cancellation for each XOR operation:

$$\begin{aligned} {{\texttt {\textit{XOR}}}} _{p}(\texttt {AX}, \texttt {AY}, \texttt {AZ}, \texttt {CB}) {:}{=}{{\texttt {\textit{if}}}} ~ (\texttt {AX} + \texttt {AY} = 2 \wedge \texttt {AZ} = 0) ~ {{\texttt {\textit{then}}}} ~ \texttt {CB} = 1 ~ {{\texttt {\textit{else}}}} ~ \texttt {CB} = 0 \end{aligned}$$

(11)

Algorithm 3 and [21, algorithm 7] describe our model for difference propagation over $E_{\textsc {b}}$ and $E_{\textsc {f}}$. We combine ${{\texttt {\textit{CSP}}}} _{\textsc {b}}^{dp}$ and ${{\texttt {\textit{CSP}}}} _{\textsc {f}}^{dp}$ into ${{\texttt {\textit{CSP}}}} _{\textsc {DP}}{:}{=}{{\texttt {\textit{CSP}}}} _{\textsc {b}}^{dp} \wedge {{\texttt {\textit{CSP}}}} _{\textsc {f}}^{dp}$ to model the difference propagation through the outer parts.

Model the Guess-and-Determine in Outer Parts. We now detect the state cells whose difference or value is needed for the filters in $\varDelta _{\textsc {b}}\rightarrow \varDelta _{\textsc {u}}$ and $\varDelta _{\textsc {l}}\leftarrow \varDelta _{\textsc {f}}$.

We first discuss detecting the state cells whose difference values are needed. The difference value in a state cell is needed if the corresponding state cell contributes to a filter, i.e., a differential cancellation. We know that AddRoundTweakey and MixColumns are the only places where a differential cancellation may occur. We thus define the binary variables $\texttt {KDXB} _{r}[i]$ and $\texttt {KDZB} _{r}[i]$ to indicate whether the difference value of $X_{r}[i]$ and $Z_{r}[i]$ over $E_{b}$ should be known. We recall that the difference cancellation through each XOR over $E_{b}$ is already encoded by $\texttt {CB} _{r}[i]$. If $\texttt {CB} _{r}[i] = 1$, then the difference value in the state cells contributing to this differential cancellation is needed. For instance, if $\texttt {CB} _{r}[i] = 1$, then $\texttt {KDZB} _{r}[P[i + 4]] = 1$ and $\texttt {KDZB} _{r}[P[i + 4]] = 1$, where $0 \le i \le 3$ and $0 \le r \le r_{u} - 1$. Besides detecting the new state cells whose difference values are needed in each round, we encode the propagation of this property from the previous rounds, as in lines 14–17 of Algorithm 4. We also define new constraint (line 11) to link the beginning of $E_{\textsc {u}}$ to the end of $E_{\textsc {b}}$. For $E_{\textsc {f}}$, we also define new binary variables $\texttt {KDXF} _{r}[i]$ and $\texttt {KDZF} _{r}[i]$ to indicate whether the difference values of $X_{r}[i]$ and $Z_{r}[i]$ are needed. Then, we follow a similar approach to model the determination of difference values.

When modeling the determination of data values, SubCells comes into effect. We explain modeling the determination of data values over S-boxes in $E_{\textsc {b}}$; a similar model can be used for $E_{\textsc {f}}$. Suppose that $Y_{r}[i] = S(X_{r}[i])$, and the value of $\varDelta X_{r}$ is known. If we want to determine the value of $\varDelta Y_{r}[i]$, e.g., to check a filter, we need to know the value of $X_{r}[i]$. Accordingly, we need the value of $X_{r}[i]$ if either we want to determine $Y_{r}[i]$, or we want to determine $\varDelta Y_{r}[i]$. On the other hand, if neither data nor difference values after the S-box is needed, we do not need to know the data value before the S-box. Therefore, we define binary variables $\texttt {KXB} _{r}[i]$ and $\texttt {KYB} _{r}[i]$ to indicate whether the values of $X_{r}[i]$ and $Y_{r}[i]$ are needed. Then, we model the determination flow over the S-boxes as follows:

$$\begin{aligned} {{\texttt {\textit{S-box}}}} _{gd}(\texttt {KXB} _{r}[i], \texttt {KYB} _{r}[i], \texttt {KDXB} _{r}[i])\!{:}{=}\! {\left\{ \begin{array}{ll} (\texttt {KYB} _{r}[i] \ge \texttt {KXB} _{r}[i])\wedge (\texttt {KYB} _{r}[i] \ge \texttt {KDXB} _{r}[i])\wedge \\ (\texttt {KYB} _{r}[i] \le \texttt {KXB} _{r}[i] + \texttt {KDXB} _{r}[i]) \end{array}\right. } \end{aligned}$$

We also model MixColumns according to [21, Equation 16] when encoding the determination of data values over $E_{\textsc {b}}$ and $E_{\textsc {f}}$.

We now explain how to detect the subtweakey cells that are involved in the determination of data values. Let $\texttt {IKB} _{r}[i]$ be a binary variable that indicates whether the ith cell of subtweakey in the rth round of $E_{\textsc {b}}$ is involved, where $0 \le r \le r_{\textsc {b}}- 1$ and $0 \le i \le 15$. One can see that $\texttt {IKB} _{r}[i] = 1$ if and only if $i \le 7$ and $\texttt {KYB} _{r}[i] = 1$. Otherwise $\texttt {IKB} _{r}[i] = 0$. We define binary variables $\texttt {IKF} _{r}[i]$ to encode the involved subtweakey in $E_{\textsc {f}}$ similarly. Algorithm 4 and [21, algorithm 8] describe our CSP models for the guess-and-determine through $E_{\textsc {b}}$ and $E_{\textsc {f}}$. We refer to ${{\texttt {\textit{CSP}}}} _{\textsc {GD}}{:}{=}{{\texttt {\textit{CSP}}}} _{\textsc {b}}^{gd} \wedge {{\texttt {\textit{CSP}}}} _{\textsc {f}}^{gd}$ as our CSP model for the guess-and-determine through the outer parts.

Model the Key Bridging. Although the subtweakeys involved in $E_{\textsc {b}}$ and $E_{\textsc {f}}$ are separated by $r_{\textsc {d}}$ rounds, they may have some relations due to the tweakey schedule. Guessing the values of some involved key cells may determine the value of others. Key-bridging uses the relations between subwteakeys to reduce the number of actual guessed key variables. We can integrate the generic CSP model for key-bridging over arbitrary tweakey schedules introduced in [18] into our model. However, the tweakey schedule of SKINNY is linear, and we provide a more straightforward method to model the key-bridging of SKINNY. We explain our model for SKINNY-n-3n; it can easily be adapted for the smaller variants.

For the ith cell of subtweakey after r rounds, we have $\textit{STK}_{r}[i] = TK1[h^{r}(i)] \oplus LFSR_{2}^{r}(TK1[h^{r}(i)]) \oplus LFSR_{3}^{r}(TK3[h^{r}(i)])$. Accordingly, knowing $\textit{STK}_{r}[h^{-r}(i)]$ in 3 rounds yields 3 independent equations in variables $\textit{TK}{1}[i], \textit{TK}{2}[i], \textit{TK}{3}[i]$, which uniquely determine the master tweakey cells $\textit{TK}{1}[i], \textit{TK}{2}[i]$, and $\textit{TK}{3}[i]$. Hence, we do not need to guess $\textit{STK}_{r}[h^{-r}(i)]$ for more than 3 different rs. To take this fact into account, we first define new integer variables $\texttt {IK} \in \{0, \dots , r_{\textsc {b}}+ r_{\textsc {f}}- 1\}, \texttt {KE} \in \{0, 1, 2, 3\}$, and $\texttt {KS} \in \{0, \dots , 48\}$. Then, assuming that $r_{\text {off}}= r_{\textsc {b}}+ r_{\textsc {u}}+ r_{\textsc {l}}$ and $z = 3$, we use the following constraints to model the key-bridging:

$$\begin{aligned} {{\texttt {\textit{CSP}}}} _{\textsc {KB}}\!{:}{=}\! {\left\{ \begin{array}{ll}\begin{aligned} \!&{}\texttt {IK} [i] = \sum _{r = 0}^{r_{\textsc {b}}- 1} \texttt {IKB} _{r}[h^{-r}(i)] + \sum _{r = 0}^{r_{\textsc {f}}- 1} \texttt {IKF} _{r}[h^{-(r_{\text {off}}+ r)}(i)] ~ \text {for} ~ 0 \le i \le 15,\\ \!&{}{{\texttt {\textit{if}}}} ~ \texttt {IK} [i] \ge z ~ {{\texttt {\textit{then}}}} ~ \texttt {KE} [i] = z ~ {{\texttt {\textit{else}}}} ~ \texttt {KE} [i] = \texttt {IK} [i] ~ \text {for} ~ 0 \le i \le 15,\\ \!&{}\texttt {KS} = \sum _{i = 0}^{15} \texttt {KE} [i] \end{aligned}\end{array}\right. } \end{aligned}$$

(12)

Model the Complexity Formulas. We now show how to combine all CSP models and model the complexity formulas. The variable $\texttt {KS}$ in Eq. 12 determines the number of involved key cells, corresponding to $|k_{\textsc {b}}\cup k_{\textsc {f}}| = \texttt {c} \cdot \texttt {KS}$ involved key bits for cell size $\texttt {c}$. We can model the other critical parameters of the ID attack as shown in Algorithm 5. We combine all CSP problems into a unified model and define an objective function to minimize the time complexity of the ID attack.

Results. We applied our method to find full ID attacks on all variants of SKINNY in both single and related-tweakey settings. Our model includes integer and real variables, so we used Gurobi to solve the resulting COP problems. Table 1 shows our results. Our ID attacks’ time, date, and memory complexity are much smaller than the best previous ID attacks. Notably, the time complexity of our 19-round single-tweakey ID attack on SKINNY-128-256 ([21, Figure 8], details in [21, F.2]) is smaller by a factor of $2^{22.57}$ compared to the best previous one [47]. As another example, we improved the time complexity of the related-tweakey ID attack on SKINNY-128-384 by a factor of $2^{15.39}$ [21, Figure 10], with smaller data and memory complexity than the best previous one [27]. Our tool can discover the longest ID distinguishers for SKINNY so far in both single and related-tweakey settings. However, we noticed that the best ID attacks do not necessarily rely on the longest distinguishers. For instance, our single-tweakey ID attacks on SKINNY use 11-round distinguishers, whereas our tool also finds 12-round distinguishers.

Fig. 4.

ID attack on 19 rounds of SKINNY [n-2n], $|k_{\textsc {b}}\cup k_{\textsc {f}}| = 26 \cdot c$, $c_{\textsc {b}}= 6\cdot c$, $c_{\textsc {f}}= 15\cdot c$, $\varDelta _{\textsc {b}}= 7\cdot c$, $\varDelta _{\textsc {f}}= 16\cdot c$

We also applied our tool to CRAFT and SKINNYee. On CRAFT, we found a 21-round ID attack which is 2 rounds longer than the best previous single-tweakey attack presented at ASIACRYPT 2022 [40]. For SKINNYee, we found a 27-round related-tweakey ID attack. Our tool can produce all the reported results on a laptop in a few seconds. Besides improving the security evaluation against ID attacks, our tool can significantly reduce human effort and error.

We also used our tool to check the validity of the previous results. To do so, we fix the activeness pattern in our model to that at the input/output of the claimed distinguisher. Moreover, we constrain the time, memory, and data complexities to the claimed bounds. An infeasible model indicates potential issues with the claimed attack. We manually check the attack to find the possible issue in this case. If the model is feasible, we match the claimed critical parameters with the output of our tool. In case of any mismatch, we manually check the corresponding parameter in the claimed attack to ensure it is calculated correctly.

We followed this approach to check the validity of the ID attacks on SKINNY proposed in [45]. For example, our tool returns ‘unsatisfiable’ when we limit it to find a 22-round ID attack on SKINNY-n-3n with the claimed parameters in [45]. To figure out the issue, we relax the time/memory/data complexity bounds and only fix the activeness pattern according to the claimed distinguisher. This way, our tool returns different attack parameters compared to the claimed ones. According to [45, Sec. 6], $c_{\textsc {b}}+ c_{\textsc {f}}$ is supposed to be $18c$ for 22-round ID attack on SKINNY-n-3n with cell size $c$. However, our tool returns $c_{\textsc {b}}=6c$ and $c_{\textsc {f}}=15c$, and thus $c_{\textsc {b}}+ c_{\textsc {f}}= 21 c$. Accordingly, the actual probability that a wrong tweakey is discarded with one pair is about $2^{-21c}$. So, the 22-round ID attack on SKINNY-n-3n in [45] requires more data and thus time by a factor of $2^{3c}$. The time complexity of the 22-round ID attack on SKINNY-64-192 (SKINNY-128-384) in [45] is $2^{183.97}$ (resp. $2^{373.48}$). As a result, the corrected attack requires more time than the exhaustive search. We also checked the 20-round ID attacks on SKINNY-n-2n in [45]. We noticed that a similar issue makes the corrected attack require more data than the full codebook or more time than the exhaustive search. We contacted the authors of [45], and they confirmed our claim.

5 Modeling the Key Recovery of ZC and Integral Attacks

Similar to our approach for ID attacks, we can extend our models for the ZC and integral distinguishers to make a unified model for finding full ZC and ZC-based integral attacks. One of the critical parameters in the key recovery of ZC and integral attacks is the number of involved key cells in the outer parts. Another effective parameter is the number of involved state cells through the outer parts. Thus, we should consider these parameters when modeling the key recovery of the ZC and integral attacks. Moreover, the meet-in-the-middle and partial-sum techniques are essential to reduce the time complexity of integral attacks. Therefore, taking these techniques into account, we provide a generic CP model for key recovery of ZC and ZC-based integral attacks as follows:

• Model the distinguisher as described in Sect. 3.

• Model the guess-and-determine part by modeling the value paths in the outer part and detecting the state/key cells whose values are needed in key recovery.

• Model the key bridging for the key recovery.

• Model the meet-in-the-middle technique for the key recovery of integral attacks.

• Set the objective function to minimize the final time complexity, keeping the data and memory complexities under the thresholds.

We only describe modeling the meet-in-the-middle technique. Other modules can be constructed similarly to our models for ID attacks. Given that there is no restriction for the output of ZC-integral distinguishers in our model, some ZC-integral distinguishers might have more than one balanced output cell. With more than one balanced cell, we might be able to use the meet-in-the-middle (MitM) technique [38] to reduce the time complexity. For example, we can use MitM if the ZC-integral distinguisher of SKINNY has two active output cells in one column, indicating that the sum of these cells is balanced. Then, we can recover the integral sums of these two cells for any keyguess separately and merge compatible key guesses that yield the same sum, i.e., that sum to zero overall.

To consider the MitM technique, we model the path values for each output cell of the distinguisher separately in an independent CP submodel. We also define a new integer variable to capture the number of involved key cells in each path. For example, our CP model for integral attacks on SKINNY splits into 16 submodels for the appended rounds after the distinguisher. Each submodel aims at encoding the involved cells in retrieving a certain output cell of the distinguisher. We note that these submodels, together with our CP model for distinguisher, are all combined into one large unified CP model. This way, we can encode and then minimize the complexity of the most critical path, which requires the maximum number of guessed keys in the guess-and-filter step. Similarly to our CP model for ID attacks, our model for ZC and integral attack receives only four integer numbers as input and returns the full ZC or ZC-based integral attack.

We solve our CP models for integral attacks in two steps with two different objective functions:

• We first solve a CP model to minimize the number of involved key cells.

• Next, we limit the number of involved key cells to the output of the previous step and solve the CP model with the objective of maximizing the number of active cells at the input of ZC-integral distinguisher.

As a result, besides reducing the time complexity, we can reduce the data complexity of the resulting integral attacks. To compute the exact final complexity, we introduce an additional helper tool, AutoPSy, which automates the partial-sum technique [16], and apply it as a post-processing step to the CP output. AutoPSy optimizes the column order in each round of partial-sum key recovery.

We applied our unified framework for finding full ZC and integral attacks to CRAFT, SKINNYe-v2, SKINNYee, and all variants of SKINNY and obtained a series of substantially improved results. Table 1 briefly describes our results. More details on our ZC and integral attacks can be found in [21, G, H, I.3]. As can be seen in [21, Figures 14, 15, 19], the inputs of the corresponding ZC distinguishers have 4 active cells, and the outputs have 2 active cells. The previous tools which fix the input/output linear masks to vectors with at most one active cell can not find such a distinguisher.

Our CP models for ZC and integral attacks include only integer variables. Thus, we can take advantage of all integer programming (IP) solvers. We used Or-Tools in this application, and running on a regular laptop, our tool can find all the reported results in a few seconds.

When reproducing the best previous results on SKINNY with our automatic tool, we again noticed some issues in previous works. The previous ZC-integral attacks on SKINNY proposed by Ankele et al. at ToSC 2019 [1] have some minor issues where the propagation in the key recovery part is incorrect. For example, in the 20-round TK2 attack in [1, Figure 20] between $X_{18}, Y_{18}$, the last row is not shifted; in the 23-round TK3 attack in [1, Figure 22], the mixing between $Y_{20}, Z_{20}$ is not correct. In both cases, this impacts the correctness of all following rounds. However, the attacks can be fixed to obtain similar complexities as claimed.

The comparison with those attacks highlights three advantages of our automated approach: (1) Our approach is much less prone to such small hard-to-spot errors; (2) Our approach can find distinguishers with many active input cells (rather than just one as classical approaches), which is particularly helpful in ZC-integral attacks where a higher input weight implies a lower data complexity; (3) Our approach optimizes the key recovery together with the distinguisher, which together with (2) allows us to attach more key-recovery rounds (7 vs. 5 for TK2 in [1], 9 vs. 7 for TK3 in [1]).

6 Conclusion and Future Works

In this paper, we presented a unified CP model to find full ID, ZC, and ZC-based integral attacks for the first time. Our frameworks are generic and can be applied to word-oriented block ciphers. To show the effectiveness and usefulness of our approach, we applied it to CRAFT, SKINNYe-v2, SKINNYee, and all members of the SKINNY family of block ciphers. In all cases, we obtained a series of substantially improved results compared to the best previous ID, ZC, and integral attacks on these ciphers. Our tool can help the cryptanalysts and the designers of block ciphers to evaluate the security of block ciphers against three important attacks, i.e., ID, ZC, and ZC-based integral attacks, more accurately and efficiently. While we focused on the application to SPN block ciphers, it is also applicable to Feistel ciphers. Applying our approach to other block ciphers such as AES or Feistel ciphers is an interesting direction for future work.

Our improved results show the advantage of our method. However, it also has some limitations. Our CP model for the distinguisher part detects the contradictions in the level of words and does not exploit the internal structure of S-boxes (i.e., DDT/LAT) to consider bit-level contradictions. Thus, one interesting future work is to provide a unified model considering bit-level contradictions. We note that our CP framework for ID, ZC, and integral attacks is modular. The key-recovery part of our CP model can be combined with other CP-based methods for finding distinguishers. For example, regardless of the distinguisher part, one can feed our CP model for the key-recovery part by a set of input/output activeness patterns for the distinguisher part to find the activeness pattern yielding the best key-recovery attack. Next, one can use a more fine-grained CP model that detects bit-level contradictions to check if the selected activeness pattern yields an ID or ZC distinguisher. We recall that in CP models, we can specify a set of input/output activeness patterns by a set of constraints, and we do not have to enumerate all possible input/output activeness patterns. Currently, our tool automatically applies the partial-sum technique as a post-processing step in integral attacks for a refined complexity analysis. Thus, another interesting future work is integrating the partial-sum technique into our CP model for integral attacks. This way, one may be able to improve the integral attacks further.