Keywords

1 Introduction

GIFT is a lightweight Substitution-Permutation-Network block cipher proposed by Banik et al. at CHES’17 [7]. GIFT has two versions named GIFT-64 and GIFT-128, whose block sizes are 64 and 128 bits respectively and round numbers are 28 and 40 respectively. The key length of GIFT-64 and GIFT-128 are both 128 bits. As the inheritor of PRESENT [16], GIFT achieves improvements over PRESENT in both security and efficiency. GIFT is the underlying block cipher of the lightweight authenticated encryption schemes GIFT-COFB [1], HYENA [2], SUNDAE-GIFT [3], LOTUS-AEAD and LOCUS-AEAD [4], which are all the round 2 candidates of the NIST lightweight crypto standardization process [5].

Differential cryptanalysis [13] is one of the most fundamental methods for cryptanalysis of block ciphers. The most important step of differential cryptanalysis is to find differential trails with high probabilities. Boomerang attack [31] and rectangle attack [11, 23] are extensions of differential cryptanalysis. Related-key boomerang attack [12, 24] is a combination of boomerang attack and related-key differential cryptanalysis [10].

In recent years, the resistance of GIFT against (related-key) differential cryptanalysis have been extensively studied. In single-key scenario, Zhou et al. [35] succeed in searching the optimal differential trails of GIFT-64 for up to 14 rounds. Ji et al. [22] found the optimal differential trails of GIFT-128 for up to 19 rounds. Li et al. [25] obtained a 20-round differential trail of GIFT-128 and presented a 26-round attack on GIFT-128. In related-key scenario, the designers [7] gave lower bounds of the probabilities of the optimal related-key differential trails of GIFT-64/GIFT-128 for up to 12/9 rounds. Liu and Sasaki [27] searched related-key differential trails of GIFT-64 for up to 21 rounds. They succeed in attacking 21-round GIFT-128 with a 19-round related-key boomerang distinguisher and 23-round GIFT-64 with a 20-round related-key boomerang distinguisher. In [18], Chen et al. constructed a 20-round related-key boomerang distinguisher of GIFT-64 with probability \( Pr = 2^{-50} \). Based on this 20-round distinguisher, a 23-round related-key rectangle attack was proposed in [18] and a 24-round related-key rectangle attack was proposed by Zhao et al. in [34]. According to the analysis in [32], the probability of the 20-round distinguisher should be corrected to \( Pr = 2^{-68} \). The 23-round and 24-round attack are invalid since \( Pr < 2^{-64} \) [11]. The detailed proof process is demonstrated in Appendix C.

Matsui’s algorithm [28] is a branch-and-bound depth-first automatic search algorithm proposed by Matsui to search optimal single-key differential and linear trails of DES. Some improvements of Matsui’s algorithm have been presented and applied to DESL, FEAL, NOEKEON and SPONGENT [6, 8, 22, 29]. In [22], Ji et al. applied three methods to speed up the search process of Matsui’s algorithm. The improved Matsui’s algorithm given in [22] is easy to implement and performs well in searching the optimal single-key differential trails of GIFT.

In this paper, we focus on the following two issues. Firstly, the lower bounds of the probabilities of the optimal related-key differential trails of GIFT found in [7, 27] are loose. We hope to find related-key differential trails of GIFT with higher probabilities. We apply Matsui’s algorithm to search related-key differential trails of GIFT. Secondly, both the probability of the single-key differential distinguisher and the related-key boomerang distinguisher can be improved by considering the clustering of the differential trails. The definitions of the clustering of an R-round single-key differential trail and the clustering of the related-key differential trails utilized in an R-round related-key boomerang distinguisher are presented in Definition 4 and Definition 5. We study how to find the clustering of the single-key differential trails and the related-key differential trails utilized in the related-key boomerang distinguisher.

Our Contributions

  1. 1

    We apply Matsui’s algorithm to search related-key differential trails of GIFT. We search related-key differential trails of GIFT according to the following three steps:

    • Firstly, apply the speeding-up methods in [22] to speed up the search process.

    • Secondly, add three constraints to limit the search space.

    • Finally, search the optimal related-key differential trails on the limited search space.

    The adjusted Matsui’s algorithm devoted to searching related-key differential trails of GIFT is shown in Algorithm 1.

    • We succeed in finding related-key differential trails of GIFT-64/128 for up to 15/14 rounds. The results are summarized in Table 1.

    • As we can see from Table 1, compared with the known results in [7, 18, 27], the related-key differential trails of GIFT we find are the best results so far. For GIFT-128, we find related-key differential trails for up to 14 round, while the previous results up to 9 rounds. For both GIFT-64 and GIFT-128, our results provide tighter lower bounds for the probabilities of the optimal related-key trails.

    In [27], the authors presented a 9-round related-key differential trail l of GIFT-128 with weight 29.830. Through our verification, we find that l cannot be reproduced. It is because that the round key difference of l cannot be generated from the master key difference.

  2. 2

    We propose an automatic search algorithm to search the clustering of the related-key differential trails utilized in the related-key boomerang distinguisher. The new algorithm is presented as Algorithm 2. The target cipher E of the related-key boomerang distinguisher is decomposed as \( E_{1}\circ E_{m}\circ E_{0} \).

    • For GIFT-64, we increase the probability of a 20-round related-key boomerang distinguisher from \( 2^{-67.660} \) to \( 2^{-58.557} \). The clustering of the 10-round related-key differential trail utilized in \( E_{0} \) consists of 5728 trails. The clustering of the 9-round related-key differential trail utilized in \( E_{1} \) consists of 312 trails.

      The 25-round and 24-round related-key rectangle attacks are achieved taking advantage of the 20-round distinguisher. This is the longest attack on GIFT-64 so far, while the previous longest attack is the 23-round related-key boomerang attack proposed in [27].

    • For GIFT-128, we increase the probability of a 19-round related-key boomerang distinguisher from \( 2^{-120.00} \) to \( 2^{-109.626} \). The clustering of the 9-round related-key differential trail utilized in \( E_{0} \) contains 3952 trails. The clustering of the 9-round related-key differential trail utilized in \( E_{1} \) contains 2944 trails. Applying the 19-round distinguisher, we propose a 23-round related-key rectangle attack and a 22-round related-key boomerang attack. This is the longest related-key attack on GIFT-128, while the previous longest related-key attack is the 21-round related-key boomerang attack proposed in [27].

  3. 3

    We apply Matsui’s algorithm to search the clustering of the single-key differential trails.

    • We increase the probability of a 20-round single-key differential distinguisher of GIFT-128 from \( 2^{-121.415} \) to \( 2^{-120.245} \). The clustering of the 20-round single-key differential trail is composed by four trails. We improve the time complexity of the 26-round differential attack on GIFT-128 constructed in [25] from \( 2^{124.415} \) to \( 2^{123.245} \).

The cryptanalytic results are summarized in Table 2.

Table 1. The \( \text{ weight}^\mathrm{{a}} \) of the R-round related-key differential trails of GIFT
Full size table
Table 2. Summary of the cryptanalytic results on GIFT
Full size table

Organization. The paper is organized as follows. In Sect. 2, we give a brief description of GIFT, the speeding-up methods on Matsui’s algorithm and the related-key boomerang and rectangle attack. The definitions and notations adopted throughout the paper are also presented in Sect. 2. In Sect. 3, we introduce how to apply Matsui’s algorithm in related-key scenario. Section 4 declares how to search the clustering of the single-key/related-key differential trails. Section 5 and Sect. 6 provide the details of the 25/24-round attacks on GIFT-64 and the 26/23-round attacks on GIFT-128 respectively. The details of the 22-round attack on GIFT-128 are presented in Appendix B. Sect. 7 is the conclusion and future work.

2 Preliminaries

2.1 Description of GIFT

Let n be the block size of GIFT. The master key is \( iniK := k_{7}||k_{6}||\cdots ||k_{0} \), in which \( |iniK|= 128 \), \( |k_{i}| = 16 \). Each round of GIFT consists of three steps: SubCells, PermBits, and AddRoundKey.

Table 3. The specifications of the S-box GS in GIFT
Full size table
  1. 1

    SubCells. The S-box GS is applied to every nibble of the cipher state. The specifications of GS is given in Table 3.

  2. 2

    PermBits. Update the cipher state by a linear bit permutation \( P(\cdot ) \) as \( b_{P(i)} \leftarrow b_{i} \), \( \forall i \in \{0, \cdots , n-1\} \).

  3. 3

    AddRoundKey. An n/2-bit round key RK is extracted from the key state. It is further partitioned into two s-bit words \( RK := U||V = u_{s-1}\cdots u_{0}||v_{s-1}\cdots v_{0} \), \( s=n/4 \). For GIFT-64, RK is XORed to the state as \( b_{4i+1} \leftarrow b_{4i+1} \oplus u_{i}, \, b_{4i} \leftarrow b_{4i} \oplus v_{i}, \, \forall i \in \{0, \cdots , 15\}. \) For GIFT-128, RK is XORed to the state as \( b_{4i+2} \leftarrow b_{4i+2} \oplus u_{i}, \, b_{4i+1} \leftarrow b_{4i+1} \oplus v_{i}, \, \forall i \in \{0, \cdots , 31\}. \) For both versions, a single bit “1” and a 6-bit constant C are XORed into the internal state at positions \( n - 1 \), 23, 19, 15, 11, 7 and 3 respectively.

Key Schedule. For GIFT-64, \( RK = U||V = k_{1}||k_{0} \). For GIFT-128, \( RK = U||V = k_{5}||k_{4}||k_{1}||k_{0} \). For both versions, the key state is updated as

$$\begin{aligned}\begin{gathered} k_{7}||k_{6}||\cdots ||k_{1}||k_{0} \leftarrow k_{1} \ggg 2||k_{0} \ggg 12||\cdots ||k_{3}||k_{2}, \end{gathered}\end{aligned}$$

where \( \ggg i \) is an i-bit right rotation within a 16-bit word.

We refer readers to [7] for more details of GIFT.

2.2 Definitions and Notations

Definition 1

([20]). The weight of a difference propagation \( (a', b') \) is the negative of the binary logarithm of the difference propagation probability over the transformation h, i.e.,

$$\begin{aligned} w_{r}(a', b') = -log_{2}^{Pr^{h}(a', b')}. \end{aligned}$$
(1)

\( a' \) is the input difference and \( b' \) is the output difference.

Definition 2

([19]). Let \( \varphi \) be an invertible function from \( \mathbb {F}_{2}^{m} \) to \( \mathbb {F}_{2}^{m} \), and \( \varDelta _{0} , \nabla _{0} \in \mathbb {F}_{2}^{m} \). The boomerang connectivity table (BCT) of \( \varphi \) is defined by a \( 2^{m} \times 2^{m} \) table, in which the entry for (\( \varDelta _{0} , \nabla _{0} \)) is computed by:

$$\begin{aligned} \text{ BCT }(\varDelta _{0} , \nabla _{0}) = \sharp \{x \in \{0,1\}^{n}|\varphi ^{-1}(\varphi (x)\oplus \nabla _{0}) \oplus \varphi ^{-1}(\varphi (x\oplus \varDelta _{0})\oplus \nabla _{0})= \varDelta _{0}\}. \end{aligned}$$
(2)

Definition 3

([32]). Let \( \varphi \) be an invertible function from \( \mathbb {F}_{2}^{m} \) to \( \mathbb {F}_{2}^{m} \), and \( \varDelta _{0} , \varDelta _{1}, \nabla _{0}, \nabla _{1} \in \mathbb {F}_{2}^{m} \). The boomerang difference table (BDT) of \( \varphi \) is a three-dimensional table, in which the entry for (\( \varDelta _{0} , \varDelta _{1}, \nabla _{0} \)) is computed by:

$$\begin{aligned} { \begin{aligned} \text{ BDT }(\varDelta _{0} , \varDelta _{1}, \nabla _{0}) = \sharp \{x \in \{0,1\}^{n}|\varphi ^{-1}(\varphi (x)\oplus \nabla _{0}) \oplus \varphi ^{-1}(\varphi (x\oplus \varDelta _{0})\oplus \nabla _{0})= \varDelta _{0}, \\ \varphi (x)\oplus \varphi (x \oplus \varDelta _{0})= \varDelta _{1} \}. \\ \end{aligned}} \end{aligned}$$
(3)

The iBDT, as a variant of BDT, is evaluated by:

$$\begin{aligned} { \begin{aligned} \text{ iBDT }(\nabla _{0}, \nabla _{1}, \varDelta _{0}) = \sharp \{x \in \{0,1\}^{n}|\varphi (\varphi ^{-1}(x)\oplus \varDelta _{0}) \oplus \varphi (\varphi ^{-1}(x\oplus \nabla _{0})\oplus \varDelta _{0})= \nabla _{0}, \\ \varphi ^{-1}(x)\oplus \varphi ^{-1}(x \oplus \nabla _{0})= \nabla _{1}\}. \\ \end{aligned}} \end{aligned}$$
(4)

The notations used in this paper are defined as follows:

figure a

2.3 Three Methods to Speed up Matsui’s Algorithm

Matsui’s algorithm [28] works by induction on the number of rounds and derives the R-round optimal weight \( B_{R} \) from the knowledge of all i-round optimal weight \( B_{i} \ (1\le i < R) \). The program requires an initial value for \( B_{R} \), which is represented as \( Bc_{R} \). It works correctly for any \( Bc_{R} \) as long as \( Bc_{R} \ge B_{R} \). In [22], Ji et al. applied three methods to improve the efficiency of Matsui’s algorithm. The three speeding-up methods are named (1) Reconstructing DDT and LAT According to Weight, (2) Executing Linear Layer Operations in Minimal Cost and (3) Merging Two 4-bit S-boxes into One 8-bit S-box.

Speeding-up method-1 contributes to pruning unsatisfiable candidates quickly. The authors reconstructed the DDT to sort the input and output differences according to their weights. Speeding-up method-2 and method-3 contribute to reducing the cost of executing linear layer operations. The authors merged 2ns 4-bit S-boxes into ns 8-bit new S-boxes. The new linear table is constructed according to the output differences of each S-box. The SSE instructions are applied to reduce the cost of linear layer operations.

The improved Matsui’s algorithm for GIFT is demonstrated as Algorithm 3 in Appendix A. We refer readers to [22] for more details of the speeding-up methods.

Fig. 1.
figure 1

The boomerang distinguisher

Full size image
Fig. 2.
figure 2

The sandwich distinguisher

Full size image

2.4 Related-key Boomerang Attack and Rectangle Attack

Basic Related-key Boomerang Attack and Rectangle Attack. Related-key boomerang attack is an adaptive chosen-plaintext/ciphertext attack. As is shown in Fig. 1, the adversary can split the target cipher E into two sub-ciphers \( E_{0} \) and \( E_{1} \), i.e., \( E = E_{1} \circ E_{0}\). Assume that there are a differential trail \( \alpha \rightarrow \beta \) under the key difference \( \varDelta K \) over \( E_{0} \) with probability p and a differential trail \( \gamma \rightarrow \delta \) under the key difference \( \nabla K \) over \( E_{1} \) with probability q. Once \( K_{1} \) is known, the other three keys are determined: \( K_{2} = K_{1} \oplus \varDelta K \), \( K_{3} = K_{1} \oplus \nabla K \), \( K_{4} = K_{2} \oplus \nabla K \). Given \( P_{1}\oplus P_{2} = \alpha \) and \( K_{1}\oplus K_{2} = \varDelta K \), the probability that we obtain two plaintexts satisfying \( P_{3}\oplus P_{4} = \alpha \) through the boomerang distinguisher is:

$$\begin{aligned} p^{2}q^{2} = Pr[E^{-1}(E(x,K_{1})\oplus \delta , K_{3} )\oplus E^{-1}(E(x \oplus \alpha , K_{2} )\oplus \delta , K_{4}) = \alpha ] \end{aligned}$$
(5)

If \( (P_{1}, P_{2}, P_{3}, P_{4} )\) can pass the boomerang distinguisher, then it is called a right quartet.

Fig. 3.
figure 3

A 1-round \( E_{m} \)

Full size image
Fig. 4.
figure 4

A 2-round \( E_{m} \)

Full size image

For a random permutation, given \( P_{1}\oplus P_{2} = \alpha \) and \( K_{1}\oplus K_{2} = \varDelta K \), the probability that two random plaintexts satisfying \( P_{3}\oplus P_{4} = \alpha \) is \( 2^{-n} \). Therefore, only if \( pq > 2^{-n/2} \) can we count more right quartets than random noise through the related-key boomerang distinguisher.

Related-key rectangle attack is a chosen-plaintext attack, which is a further development of the related-key boomerang attack. In Fig. 1, given \( P_{1}\oplus P_{2} = \alpha \) and \( P_{3}\oplus P_{4} = \alpha \) under \( K_{1}, K_{2}, K_{3}, K_{4} \), the probability that the corresponding ciphertexts \( C_{1}, C_{2}, C_{3}, C_{4} \) meets \( C_{1}\oplus C_{3} = \delta \) and \( C_{2}\oplus C_{4} = \delta \) (or \( C_{1}\oplus C_{4} = \delta \) and \( C_{2}\oplus C_{3} = \delta \)) is \( 2^{-n}p^{2}q^{2} \). If \( (P_{1}, P_{2}, P_{3}, P_{4} )\) can pass the rectangle distinguisher under \( (K_{1}, K_{2}, K_{3}, K_{4}) \), then it is called a right quartet. For a random permutation, we get a right quartet with probability \( 2^{-2n} \) in the rectangle attack. Thus, only if \( pq > 2^{-n/2} \) can we count more right quartets than random noise.

Boomerang Switch. The interaction between the two differential trails over \( E_{0} \) and \( E_{1} \) is utilized to improve the boomerang and rectangle attack [14, 15], which is called the boomerang switch [15]. The idea of the boomerang switch is to minimize the overall complexity of the distinguisher by optimizing the transition between \( E_{0} \) and \( E_{1} \). In [21], a new framework named sandwich attack was proposed. As is shown in Fig. 2, the sandwich attack decomposes the target cipher E as \( E_{1}\circ E_{m} \circ E_{0} \). The propagation of the boomerang switch is captured by the propagation of \( E_{m} \).

For the fixed \( \beta \) and \( \gamma \), the probability that a quartet can pass \( E_{m} \) is denoted as:

$$\begin{aligned} r : = Pr[E_{m}^{-1}(E_{m}(x,K_{1})\oplus \gamma , K_{3}) \oplus E_{m}^{-1}(E_{m}(x \oplus \beta , K_{2} ) \oplus \gamma , K_{4}) = \beta ] \end{aligned}$$
(6)

Thus, the probability that we obtain a right quartet through the sandwich distinguisher (i.e., the boomerang distinguisher with boomerang switch) is \( p^{2}q^{2}r \).

The value of r can be evaluated by the boomerang connectivity table [19] or the boomerang difference table [32] at the S-box level. Let \( \beta [2\text{ ns}]||\cdots ||\beta [1] := \beta \) and \( \gamma [2\text{ ns}]||\cdots ||\gamma [1] := \gamma \). Let S and L be the non-linear and linear layer operations of E, \( \beta '=S(\beta ) \), \( \beta ''=L(\beta ') \), \( \gamma ' = S^{-1}(\gamma ) \) and \( \gamma '' = L^{-1}(\gamma ') \). For a 1-round \( E_{m} \), the propagation of \( \beta \) and \( \gamma \) is illustrated in Fig. 3. Then we have

$$\begin{aligned} r=2^{-n}\varSigma _{1\le i \le 2\text{ ns }}\text{ BCT }(\beta [i],\gamma [i]). \end{aligned}$$

For a 2-round \( E_{m} \), the propagation of \( \beta \) and \( \gamma \) is illustrated in Fig. 4. Then we have

$$\begin{aligned} r=2^{-2n}\varSigma _{1\le i \le 2\text{ ns }}(\text{ BDT }(\beta [i],\beta '[i],\gamma ''[i]) \times \text{ iBDT }(\gamma [i],\gamma '[i],\beta ''[i])). \end{aligned}$$

For a related-key boomerang distinguisher, if there are multiple trails \( \alpha {\mathop {\rightarrow }\limits ^{E_{0}}}\beta _{i} \) and \( \gamma _{j}{\mathop {\rightarrow }\limits ^{E_{1}}}\delta \) (\( \beta _{i} \ne \gamma _{j} \)) under fixed \( \alpha \), \( \varDelta K \), \( \delta \) and \( \nabla K \), the probability of obtaining a right quartet can be increased to:

$$\begin{aligned} \hat{p}^{2}\hat{q}^{2} : = \varSigma _{i,j}p_{i}^{2} q_{j}^{2} r_{ij}, \end{aligned}$$
(7)

in which \( p_{i}=Pr(\alpha {\mathop {\rightarrow }\limits ^{E_{0} }}\beta _{i}) \), \( q_{j}=Pr(\gamma _{j}{\mathop {\rightarrow }\limits ^{ E_{1}}}\delta ) \) and \( r_{ij} = Pr(\beta _{i} {\mathop {\rightarrow }\limits ^{ E_{m}}} \gamma _{j}) \).

A new key-recovery model for the related-key boomerang and rectangle attack against block ciphers with linear key schedules was constructed by Zhao et al. in [33, 34]. This new model is a modification of Liu et al.’s model [26]. In this paper, we utilize the model proposed by Zhao et al. to perform the key-recovery attack against GIFT.

3 Searching Related-key Differential Trails

3.1 Applying Matsui’s Algorithm in Related-key Scenario

Our objective is to find related-key differential trails with high probabilities. We apply Matsui’s algorithm to search related-key differential trails of GIFT. Firstly, we apply the speeding-up methods introduced in Sect. 2.3 to improve the search process. Secondly, we add three constraints to limit the search space. Finally, we search the optimal related-key differential trails on the limited search space. The adjusted Matsui’s algorithm aiming at searching optimal related-key differential trails of GIFT on limited search space is demonstrated in Algorithm 1.

figure b

Let R be the round number of E. Let \( \varDelta iniK := \varDelta k_{7} || \cdots || \varDelta k_{0} \) be the master key difference and \( \varDelta K_{i} \) be the round key difference in round i. We utilize the following three constraints to limit the search space:

  1. 1

    Restricting the input difference of round \( \boldsymbol{fr} \) to zero and traverse \( \boldsymbol{fr }\) from \( \boldsymbol{ 1} \) to \( \boldsymbol{ R} \).

    It has been declared in [29] that the number of candidates in the first two rounds of Matsui’s algorithm is the dominant factor of the search complexity. In Algorithm 3, the number of candidates \( \varDelta Y_{1} \) in Procedure Round-1 depends on the value of \( Bc_{R} - B_{R-1} \). Algorithm 1 starts from Procedure Round-fr with only one candidate \( \varDelta Y_{fr} = 0\). Since \( \varDelta Y_{fr} = 0\), we can determine the input difference of round \( i+1 \) which is \( \varDelta K_{i} \) and the output difference of round \( i-1 \) which is \( \varDelta K_{i-1} \).

    Therefore, the complexity of Matsui’s algorithm in related-key scenario is improved benefitting from constraint-1.

  2. 2

    Restricting the number of the active bits in the master key difference.

    The key schedule of GIFT is a linear transformation. The value of \( \varDelta K_{i} \) are determined by \( \varDelta iniK \). The input difference of \( S(\cdot ) \) in round i is \( \varDelta X_{i} = P(\varDelta Y_{i-1})\oplus \varDelta K_{i-1} \). The related-key differential trails with small weight will not contain too many active S-boxes in \( S(\cdot ) \). Thus, there should not be too many active bits in \( \varDelta K_{i} \) (\( 1\le i \le R \)). The details of constraint-2 are as follows.

    • Restricting the number of the active bits in \( \varDelta iniK \) to no more than four when \( R < 11 \).

    • Restricting the number of the active bits in \( \varDelta iniK \) to no more than three when \( R\ge 11 \).

    • Restricting the four active bit positions to belong to four different \( \varDelta k_{j} \) (\( 0\le j \le 7 \)) if the number of the active bits is four.

    The total number of the candidate \( \varDelta iniK \) is \( C_{128}^{1} + C_{128}^{2} + C_{128}^{3} + C_{7}^{4} \cdot (C_{16}^{1})^{4} = 4\,937\,152\).

  3. 3

    Restricting the number of the active S-boxes in round \( \boldsymbol{ i} \) (\( \boldsymbol{ 1\le i \le R }\)) to no more than five when \( \boldsymbol{ R\ge 11 }\).

3.2 Results on Related-Key Differential Trails of GIFT

Applying Algorithm 1, we find related-key differential trails of GIFT-64/128 for up to 15/14 rounds. The results are summarized in Table 1. Table 10 in Appendix D presents a 15-round related-key differential trail of GIFT-64 and a 14-round related-key differential trail of GIFT-128 found by Algorithm 1.

Compared to the previous results in [7, 18, 27], the optimal related-key differential trails found by Algorithm 1 on the limited search space are the best results known so far. We find related-key differential trails of GIFT-128 for up to 14 rounds, while the previous results up to 9 rounds. We provide tighter lower bounds for the probabilities of the optimal related-key trails of both GIFT-64 and GIFT-128. It indicates that the three constraints we choose perform well in limiting the search space while preserving the related-key differential trails with high probabilities.

4 Increasing the Probability of the Distinguisher Utilizing Clustering Effect

Both the probability of the single-key differential distinguisher and the related-key boomerang distinguisher can be increased by searching the clustering of the differential trails. Next, we give the definitions of the clustering of an \( \boldsymbol{ R }\)-round single-key differential trail and the clustering of the related-key differential trails utilized in an \( \boldsymbol{ R} \)-round boomerang distinguisher and explain how to search the clustering.

4.1 Single-key Scenario

Definition 4

The clustering of an R-round single-key differential trail is defined as:

$$\begin{aligned} \begin{aligned} \mathcal {C}(R, \eta _{in} , \eta _{out} , Bc_{R}) : = \{\text{ all } R\text{-round } \text{ single-key } \text{ differential } \text{ trails } l^{i} \ | \ \\ W(l^{i})\le Bc_{R}, \varDelta X_{1} = \eta _{in}, P(\varDelta Y_{R}) = \eta _{out}\}. \\ \end{aligned} \end{aligned}$$
(8)

In fact, for an R-round single-key differential trail \( \mathcal {L} \) with fixed input difference \( \eta _{in} \) and output difference \( \eta _{out} \), the clustering of \( \mathcal {L} \) is composed by all the differential trails whose input difference is \( \eta _{in} \) and output difference is \( \eta _{out} \), i.e., \( \mathcal {C}(R, \eta _{in} , \eta _{out}, \infty ) \). It will take immeasurable time to determine all the trails in \( \mathcal {C}(R, \eta _{in} , \eta _{out}, \infty ) \). Therefore, we only search all the trails with weight no more than \( Bc_{R} \). The choice of \( Bc_{R} \) is heuristic.

We call Algorithm 3 to search \( \mathcal {C}(R, \eta _{in} , \eta _{out} , Bc_{R}) \). The greater the value of \( Bc_{R} \), the more trails can we find, while the longer the search time is required.

4.2 Related-key Scenario

figure c

Definition 5

The clustering of the related-key differential trails utilized in an R -round related-key boomerang distinguisher is defined as:

$$\begin{aligned} { \begin{aligned} \mathcal {C}(R_{0},R_{1},R_{m}, \alpha , \varDelta iniK_{0}, Bc_{R_{0}}, \delta , \varDelta iniK_{1}, Bc_{R_{1}}) : = \{\text{ all } \text{ combinations } \text{ of } (l_{0}^{i},l_{1}^{j}) \ | \ \\ l_{0}^{i} \in \mathcal {C}_{I}(R_{0}, \alpha , \varDelta iniK_{0}, Bc_{R_{0}}), l_{1}^{j} \in \mathcal {C}_{O}(R_{1}, \delta , \varDelta iniK_{1},Bc_{R_{1}} )\}, \\ \end{aligned}} \end{aligned}$$
(9)

in which

$$\begin{aligned} \begin{aligned} \mathcal {C}_{I}(R_{0}, \alpha , \varDelta iniK_{0}, Bc_{R_{0}}) : = \{\text{ all } R_{0}\text{-round } \text{ related-key } \text{ differential } \text{ trails } l_{0}^{i} \ | \ \\ W(l_{0}^{i})\le Bc_{R_{0}}, \varDelta X_{1} = \alpha ,\text{ MKD }= \varDelta iniK_{0}\}, \\ \end{aligned} \end{aligned}$$
(10)
$$\begin{aligned} \begin{aligned} \mathcal {C}_{O}(R_{1}, \delta , \varDelta iniK_{1}, Bc_{R_{1}}) : = \{\text{ all } R_{1}\text{-round } \text{ related-key } \text{ differential } \text{ trails } l_{1}^{j} \ | \ \\ W(l_{1}^{j})\le Bc_{R_{1}}, K(\varDelta Z_{R_{1}}) = \delta , \text{ MKD }=\varDelta iniK_{1}\}, \\ \end{aligned} \end{aligned}$$
(11)

and \( R=R_{0}+R_{m}+R_{1} \).

In fact, the clustering of an \( R_{0} \)-round related-key differential trail \( \mathcal {L} \) with fixed input difference \( \alpha \) and master key difference \( \varDelta iniK_{0} \) contains all the related-key differential trails with arbitrary weight, i.e., \( \mathcal {C}_{I}(R_{0}, \alpha , \varDelta iniK_{0}, \infty ) \). It will take immeasurable time to determine all the trails in \( \mathcal {C}_{I}(R_{0}, \alpha , \varDelta iniK_{0}, \infty ) \). Therefore, we only search all the trails with weight no more than \( Bc_{R_{0}} \). The choice of \( Bc_{R_{0}} \) is heuristic. The modification above also applies to \( \mathcal {C}_{O}(R_{1}, \delta , \varDelta iniK_{1}, \infty ) \).

To construct an R-round related-key boomerang distinguisher \( \mathcal {D} \) for the target cipher \( E = E_{1}\circ E_{m}\circ E_{0} \), we firstly determine the round number \( R_{0}/R_{m}/R_{1} \) for \( E_{0}/E_{m}/E_{1} \) satisfying \( R = R_{0} + R_{m} + R_{1} \). The general way to determine the probability of the distinguisher \( \mathcal {D} \) is:

  1. 1

    Choose an \( R_{0} \)-round trail \( l_{0} \) for \( E_{0} \); Get the input difference \( \alpha \), the output difference \( \beta \) and the master key difference \( \varDelta iniK_{0} \).

  2. 2

    Choose an \( R_{1} \)-round trail \( l_{1} \) for \( E_{1} \); Get the input difference \( \gamma \), the output difference \( \delta \) and the master key difference \( \varDelta iniK_{1} \).

  3. 3

    Apply the BCT to calculate \( Pr(\beta \rightarrow \gamma ) \) if \( R_{m} =1 \); Apply the BDT and the iBDT to calculate \( Pr(\beta \rightarrow \gamma ) \) if \( R_{m} =2 \).

For a distinguisher \( \mathcal {D} \) with fixed \( \alpha \) and \( \delta \), there could be mulitiple values of \( \beta \) and \( \gamma \). To increase the probability of \( \mathcal {D} \), we hope to find as more combinations of \( (\beta , \gamma ) \) as we can. We propose Algorithm 2 to search \( \mathcal {C}(\mathcal {D}) \), i.e.,

$$\begin{aligned} \mathcal {C}(R_{0},R_{1},R_{m}, \alpha , \varDelta iniK_{0}, Bc_{R_{0}}, \delta , \varDelta iniK_{1}, Bc_{R_{1}}) \end{aligned}$$

and calculate the probability of \( \mathcal {D} \) by traversing all combinations of \( (l_{0}^{i}, l_{1}^{j}) \) in \( \mathcal {C}(\mathcal {D}) \). The greater the value of \( Bc_{R_{0}} \) and \( Bc_{R_{1}} \), the more trails can we find.

Explanations on Algorithm 2

  1. 1

    Different choices of \( \alpha \) (or \( \delta \)) will lead to different amounts and values of \( \beta \) (or \(\gamma \)).

    Therefore, in Phase 1 of Algorithm 2, we first determine all the choices of \( \alpha \) and \( \delta \).

  2. 2

    For GIFT, we find the fact that for fixed \( S(\alpha ) \) of \( E_{0} \) and fixed \( S^{-1}\circ P^{-1}\circ K^{-1}(\delta ) \) of \( E_{1} \), the choices of \( \alpha \) and \( \delta \) will not influence the value of \( \hat{p}^{2}\hat{q}^{2} \).

    Therefore, in the search process of GIFT, we only care about the value of \( S(\alpha ) \) (i.e., \( \varDelta Y_{1} \) of \( E_{0} \)) and the value of \( S^{-1}\circ P^{-1}\circ K^{-1}(\delta ) \) (i.e., \( \varDelta X_{R_{1}} \) of \( E_{1} \)).

  3. 3

    For fixed \( l_{0}^{i} \) and \( l_{1}^{j} \) (\( 1\le i \le a \), \( 1\le j \le b \)), we get \( \mathcal {C}_{I}(R_{0}, \alpha _{i}, \varDelta iniK_{0}^{i}, B_{R_{0}}+bw) \) and \( \mathcal {C}_{O}(R_{1}, \delta _{j}, \varDelta iniK_{1}^{j}, B_{R_{1}}+bw) \) through Phase 2. In Phase 3, we traverse all combinations of \( (l_{0}^{i_{u}}, l_{1}^{j_{v}}) \), in which

    $$\begin{aligned} l_{0}^{i_{u}}\in \mathcal {C}_{I}(R_{0}, \alpha _{i}, \varDelta iniK_{0}^{i}, B_{R_{0}}+bw), \ l_{1}^{j_{v}} \in \mathcal {C}_{O}(R_{1}, \delta _{j}, \varDelta iniK_{1}^{j}, B_{R_{1}}+bw), \end{aligned}$$

    to calculate

    $$\begin{aligned} \hat{p_{i}}^{2}\hat{q_{j}}^{2} \leftarrow \sum _{u,v} 2^{-2B_{R_{0}}^{i_{u}}} \cdot 2^{-2B_{R_{1}}^{j_{v}}} \cdot \text{ Middle }(\beta ^{i_{u}},\gamma ^{j_{v}}, R_{m}). \end{aligned}$$

    For each \( l_{0}^{i_{u}}\) and \( l_{1}^{j_{v}} \), the value of \( \beta ^{i_{u}} \) and \( \gamma ^{j_{v}} \) are determined. The incompatibility between \( \beta ^{i_{u}} \) and \( \gamma ^{j_{v}} \) can be captured by the BCT or the BDT.

  4. 4

    The value of \( \boldsymbol{ \alpha } \) and \( \boldsymbol{ \delta } \) should be carefully determined to keep the value of \( \boldsymbol{ r_{b} }\), \( \boldsymbol{ m_{b}} \), \( \boldsymbol{ r_{f}} \) and \( \boldsymbol{ m_{f}} \) appropriate. The probability of the distinguisher is the main factor affecting the complexity of the key-recovery attack. Nevertheless the value of \( r_{b} \), \( m_{b} \), \( r_{f} \) and \( m_{f} \) can also affect the complexity, which is influenced by the value of \( \alpha \) and \( \delta \).

    Therefore, once we get the value of \(max_{i,j}\{\hat{p_{i}}^{2}\hat{q_{j}}^{2}\}\), \( \alpha _{i} \) and \( \delta _{j} \) from Algorithm 2, we should carefully adjust the value of \( \alpha _{i} \) and \( \delta _{j} \) to reduce the complexity of the attack.

5 Attacks on GIFT-64

5.1 Related-key Rectangle Attack on 25-Round GIFT-64

Determining the Related-key Rectangle Distinguisher. We utilize a 20-round related-key rectangle distinguisher to attack the 25-round GIFT-64. Choose \( R_{0} = 10 \) for \( E_{0} \), \( R_{1} = 9 \) for \( E_{1} \), \( R_{m} = 1 \) for \( E_{m} \). Set \( bw = 4 \). Apply Algorithm 2 to search the probability of the 20-round distinguisher.

In Phase 1 of Algorithm 2, we find sixteen 10-round trails with weight 20.415 for \( E_{0} \), marked as \( l_{0}^{1}, \cdots , l_{0}^{16}\). We find eight 9-round trails with weight 13.415 for \( E_{1} \), marked as \( l_{1}^{1}, \cdots , l_{1}^{8}\). The details of \( l_{0}^{1}, \cdots , l_{0}^{16}\) and \( l_{1}^{1}, \cdots , l_{1}^{8}\) are listed in Table 13 and Table 14 in Appendix D.

In Phase 3, we determine the maximum value of \( \hat{p_{i}}^{2}\hat{q_{j}}^{2} \), which is \( \hat{p_{5}}^{2}\hat{q_{8}}^{2} = 2 ^{-58.557}\). We choose the value of \( \alpha \) and \( \delta \) according to \( S(\alpha _{5}) = 0x 00 00 00 00 00 00 10 00\) and \( S^{-1}\circ P^{-1}\circ K^{-1}(\delta _{8}) = 0x 00 00 20 00 00 00 00 00 \). Finally, we obtain a 20-round related-key rectangle distinguisher with probability \( \boldsymbol{ 2^{-n} \hat{p}^{2}\hat{q}^{2} = 2^{-64}\cdot 2 ^{-58.557} }\). The specifications of the 20-round related-key rectangle distinguisher of GIFT-64 are shown in Table 4. There are 5728 trails in \( \mathcal {C}_{I}(R_{0}, \alpha , \varDelta iniK_{0}, Bc_{R_{0}}) \) and 312 trails in \( \mathcal {C}_{O}(R_{1}, \delta , \varDelta iniK_{1}, Bc_{R_{1}}) \).

Table 4. The specifications of 20-round related-key rectangle distinguisher of GIFT-64
Full size table

We construct the 25-round key-recovery model for GIFT-64, which is shown in Table 5, by appending two rounds at the end of the 20-round distinguisher and appending three rounds at the beginning of the distinguisher.

Table 5. The 25-round key-recovery model of the related-key rectangle attack for GIFT-64
Full size table

Data Collection. Since there is no whitening key XORed to the plaintext, we collect data in \( \varDelta Z_{1} \). There are 44 unknown bits in \( \varDelta Z_{1} \) marked as “?", affecting 12 S-boxes in round 1 and three S-boxes in round 2. Thus, \( \boldsymbol{ r_{b} = 44 }\) and the number of key bits needed to be guessed in \( E_{b} \) is \( \boldsymbol{ m_{b} = 2\times (12+3) = 30}\). Similarly, we have \( \boldsymbol{ r_{f} = 48 }\) and \( \boldsymbol{ m_{f} = 2\times (12+4) = 32} \) in \( E_{f} \). We utilize the key-recovery model proposed by Zhao et al. in [33] to perform the rectangle key-recovery attack.

  1. 1

    Construct \( y = \sqrt{s} \cdot 2^{n/2-r_{b}} / \hat{p}\hat{q}\) structures of \( 2^{r_{b}} \) plaintexts each. s is the expected number of right quartets. Each structure takes all the possible values of the \( r_{b} \) active bits while the other \( n - r_{b} \) bits are fixed to some constant.

  2. 2

    For each structure, query the \( 2^{r_{b}} \) plaintexts by the encryption oracle under \( K_{1}, K_{2}, K_{3} \) and \( K_{4} \) where \( K_{1} \) is the secret key, \( K_{2} = K_{1} \oplus \varDelta K \), \( K_{3} = K_{1} \oplus \nabla K \) and \( K_{4} = K_{1} \oplus \varDelta K \oplus \nabla K \). Obtain four plaintext-ciphertext sets denoted by \( L_{1}, L_{2}, L_{3} \) and \( L_{4} \). Insert \( L_{2} \) and \( L_{4} \) into hash tables \( H_{1} \) and \( H_{2} \) indexed by the \( r_{b} \) bits of the plaintexts.

  3. 3

    Guess the \( m_{b} \) bits subkey involved in \( E_{b} \), then:

    1. (a)

      Initialize a list of \( 2^{m_{f}} \) counters, each of which corresponds to a \( m_{f} \) bits subkey guess.

    2. (b)

      For each structure, partially encrypt plaintext \( P_{1} \in L_{1} \) to the position of \( \alpha \) by the guessed subkeys, and partially decrypt it to the plaintext \( P_{2} \) after XORing the known difference \( \alpha \). Then we look up \( H_{1} \) to find the plaintext-ciphertext indexed by the \( r_{b} \) bits. Do the same operations with \( P_{3} \) and \( P_{4} \). We get two sets:

      $$\begin{aligned}\begin{gathered} S_{1} = \{( P_{1} , C_{1}, P_{2}, C_{2}) : (P_{1} , C_{1}) \in L_{1}, (P_{2}, C_{2}) \in L_{2}, E_{b_{K_{1}}}(P_{1}) \oplus E_{b_{K_{2}}}(P_{2}) = \alpha \}, \\ S_{2} = \{( P_{3} , C_{3}, P_{4}, C_{4}) : (P_{3} , C_{3}) \in L_{3}, (P_{4}, C_{4}) \in L_{4}, E_{b_{K_{3}}}(P_{3}) \oplus E_{b_{K_{4}}}(P_{4}) = \alpha \}. \end{gathered}\end{aligned}$$
    3. (c)

      The size of \( S_{1} \) and \( S_{2} \) are both \( M = y \cdot 2^{r_{b}} \). Insert \( S_{1} \) into a hash table \( H_{3} \) indexed by the \( n - r_{f} \) bits of \( C_{1} \) and the \( n - r_{f} \) bits of \( C_{2} \) in which the output difference of \( E_{f} \) are all “0”. For each element of \( S_{2} \), we find the corresponding \( ( P_{1} , C_{1}, P_{2}, C_{2}) \) satisfying \( C_{1} \oplus C_{3} = 0 \) and \( C_{2} \oplus C_{4} = 0 \) in the \( n - r_{f} \) bits. In total, we obtain \( M^{2} \cdot 2^{-2(n-r_{f} )} \) quartets.

    4. (d)

      We use all the quartets obtained in step (c) to recover the subkeys involved in \( E_{f} \). This step is a guess and filter procedure. We denote the time complexity in this step as \( \varepsilon \).

    5. (e)

      Select the top \( 2^{m_{f} - h} \) hits in the counter to be the candidates which delivers a h bits or higher advantage.

    6. (f)

      Exhaustively search the remaining \( k - m_{b} - m_{f} \) unknown key bits in the master key.

Key Recovery. Choose the expected number of right quartets s to be 2, then we have \( y = 2^{17.78} \) and \( M = y \cdot 2^{r_{b}} = 2^{61.78} \). Make use of all the \( M^{2} \cdot 2^{-2(n-r_{f} )} = 2^{91.56} \) quartets obtained in step 3(c) to recover the subkeys involved in \( E_{f} \).

The following are the details of the guess and filter procedure in step 3(d), which are similar to the process used in [34]. \( \varDelta X_{i}[u,\cdots ,v] \) represents the \( u^{th} \) bit, \( \cdots \), the \( v^{th} \) bit of \( \varDelta X_{i} \).

  1. d.1

    \( \varDelta Y_{25}[63,62,61,60] \) can be computed by the cipertext pair \( (C_{1}, C_{3}) \) and \( \varDelta X_{25}[63,62,61,60] \) is known. We guess the \( 2^{2} \) possible values of the involved key bits in this S-box and partially decrypt the cipertexts \( (C_{1}, C_{3}) \) and \( (C_{2}, C_{4}) \). Then check whether \( \varDelta X_{25}[63,62,60] \) is 0 or not. If yes, we keep the guessed key and the quartet, otherwise discard it. There are about \( 2^{91.56} \cdot 2^{2} \cdot 2^{-6} = 2^{87.56}\) remaining quartets associated with the guessed 2-bit keys, i.e. for each of the \( 2^{2} \) candidate values of the 2-bit involved keys, there are \( 2^{85.56} \) quartets remain.

  2. d.2

    Carry out a similar process to all the active S-boxes in round 25. There are about \( 2^{87.56} \cdot 2^{(2-4)\times 4} \cdot 2^{(2-6)\times 6} \cdot 2^{(2-8)} = 2^{87.56-38} = 2^{49.56}\) remaining quartets associated with the guessed keys.

  3. d.3

    Partially decrypt all the remaining quartets with the obtained key bits in steps 1 and 2. \( \varDelta Y_{24}[59,58,57,56] \) can be calculated from the end of the distinguisher. Guess the \( 2^{2} \) possible values of the key bits involved in this S-box. For each guess, only \( 2^{49.56} \cdot 2^{2-8} = 2^{43.56}\) quartets remain. Carry out a similar process to all the active S-boxes in round 24, there are about \( 2^{43.56} \cdot 2^{(2-8)\times 3} = 2^{25.56} \) quartets remain.

  4. d.4

    Utilize the remaining quartets to count the \( m_{f} = 32 \) key bits. The two right quartets will all vote for the right key. The \( 2^{25.56} \) random quartets will vote for a random key with probability \( 2^{25.56-m_{f}} = 2^{-6.44}\).

  5. d.5

    Choose \( h = 22 \). Select the top \( 2^{ m_{f} - h} \) hits in the counter to be the candidates. Exhaustively search the remaining \( 128 - m_{b} - m_{f} \) unknown key bits in the master key.

Complexity. The data complexity is \( 4M = 4y \cdot 2^{r_{b}} = 2^{63.78}\) chosen plaintexts. We need 4M encryptions in step 2. \( 2^{m_{b}}\cdot 3M = 2^{93.36}\) looking-up-table operations are needed in step 3(b) and 3(c). We need \( 2^{m_{b}}\cdot M^{2} \cdot 2^{-2(n-r_{f} )} \cdot 4\cdot 2^{2}/25 = 2^{120.92}\) encryptions and \( 2^{k-h} = 2^{106}\) encryptions to recover the master key. So the time complexity is bounded by \( 2^{120.92} \). The memory complexity is bounded by the size of sets \( H_{1}, H_{2}, H_{3}, S_{1}\) and \( S_{2} \), which is \( 5M = 2^{64.10}\).

Success Probability. According to the success probability calculation method of differential attacks proposed in [30], for both boomerang and rectangle attack, the success probability is

$$\begin{aligned} P_{r} = \varPhi (\dfrac{\sqrt{s S_{N}}- \varPhi ^{-1} (1- 2^{-h})}{\sqrt{S_{N}+1}}), \end{aligned}$$
(12)

in which \( S_{N} = \hat{p}^{2}\hat{q}^{2}/ 2^{-n}\) is the signal-to-noise ratio.

The success probability of the 25-round attack on GIFT-64 is \( 74.00\% \).

5.2 Related-key Rectangle Attack on 24-Round GIFT-64

Determining the Related-key Rectangle Distinguisher. We choose the same 20-round related-key rectangle distinguisher as in Sect. 5.1. We append two rounds at the end of the distinguisher and two rounds at the beginning of the distinguisher. The details of the 24-round key-recovery model are shown in Table 5. The input difference of the 24-round model equals to

Data Collection and Key Recovery. To prepare the plaintexts, we collect data in \( \varDelta Z_{2} \) of Table 5. There are ten unknown bits in \( \varDelta Z_{2} \) marked as “?", affecting three S-boxes in round 2. Thus, \( \boldsymbol{ r_{b} = 10 }\) and the number of key bits needed to be guessed in \( E_{b} \) is \( \boldsymbol{ m_{b} = 2\times 3 = 6}\). Similarly, \( \boldsymbol{ r_{f} = 48 }\) and \( \boldsymbol{ m_{f} = 2\times (12+4) = 32} \) in \( E_{f} \). The following data collection and key recovery process are similar to the process of the 25-round attack in Sect. 5.1.

Construct \( y = \sqrt{s} \cdot 2^{n/2-r_{b}} / \hat{p}\hat{q}\) structures of \( 2^{r_{b}} \) plaintexts each. For each structure, query the \( 2^{r_{b}} \) plaintexts by the encryption oracle under \( K_{1}, K_{2}, K_{3} \) and \( K_{4} \). There are about \( M^{2} \cdot 2^{-2(n-r_{f} )} \) quartets left after executing step 3(c). Choosing \( s = 2 \), we have \( y = 2^{51.78} \), \( M = y \cdot 2^{r_{b}} = 2^{61.78} \) and \( M^{2} \cdot 2^{-2(n-r_{f} )} = 2^{91.56}\). After the key guessing and filtering process, there are about \( M^{2} \cdot 2^{-2(n-r_{f} )} \cdot 2^{-66} = 2^{25.56}\) remaining quartets. Choose \( h = 22 \) and select the top \( 2^{ m_{f} - h} \) hits in the counter to be the candidates. Exhaustively search the remaining \( 128 - m_{b} - m_{f} \) unknown key bits in the master key.

Complexity and Success Probability. The data complexity is \( 4M = 2^{63.78}\) chosen plaintexts. We need \( 2^{m_{b}}\cdot 3M = 2^{69.36}\) looking-up-table operations in step 3(b) and 3(c). We need \( 2^{m_{b}} \cdot M^{2} \cdot 2^{-2(n-r_{f} )} \cdot 4\cdot 2^{2}/24 = 2^{96.98}\) encryptions and \( 2^{k-h} = 2^{106}\) encryptions to recover the master key. So the time complexity is bounded by \( 2^{106} \). The memory complexity is bounded by \( 5M = 2^{64.10} \). The success probability is \( 74.00\% \) according to Eq. 12.

6 Attacks on GIFT-128

6.1 Single-Key Differential Attack on 26-Round GIFT-128

In [25], Li et al. found a 20-round differential trail \( l^{0} \) of GIFT-128 with probability \( p = 2^{-121.415} \). The propagation of \( l^{0} \) is shown in Table 12 of Appendix D. The 26-round differential attack was obtained by extending four rounds backward and two rounds forward. The data complexity is \( 2^{3}/p = 2^{124.415}\). The time complexity is bounded by the data complexity. The memory complexity is the cost of the key filter counter, which is \( 2^{109} \).

Next, we search the clustering of \( l^{0} \). According to Definition 4, we choose \( Bc_{20} = 124 \),

$$\begin{aligned} \begin{aligned} \eta _{in}=\varDelta X_{1}&= 0x 0000 0000 0000 0000 0000 0000 0000 00\text{ a }0, \\ \eta _{out}=P(\varDelta Y_{20})&= 0x 0000 0000 4001 0000 2000 0000 1004 0000. \end{aligned} \end{aligned}$$
(13)

Then call Algorithm 3 to search \( \mathcal {C}(20, \varDelta X_{1}, P(\varDelta Y_{20}) , Bc_{20}) \). We find four trails: \( l^{0} \) with weight 121.415, \( l^{2} \) and \( l^{3} \) with weight 122.415 and \( l^{4} \) with weight 123.415. The probability of the 20-round single-key distinguisher that satisfies Eq. 13 is increased to \(\hat{p} = 2^{-120.245} \). The details of \( l^{i} (0 \le i < 4) \) are demonstrated in Table 12.

Hence, the data complexity of the 26-round differential attack on GIFT-128 is reduced to \( 2^{3}/\hat{p} = 2^{123.245} \). The time complexity is reduced to \( 2^{123.245} \) as well. The cost of the key filter counter does not change.

6.2 Related-Key Rectangle Attack on 23-Round GIFT-128

Determining the Related-Key Rectangle Distinguisher. We utilize a 19-round related-key rectangle distinguisher to attack the 23-round GIFT-128. Set \( R_{0} = 9 \) for \( E_{0} \), \( R_{1} = 9 \) for \( E_{1} \), \( R_{m} = 1 \) for \( E_{m} \) and \( bw = 3 \). Apply Algorithm 2 to search the probability of the 19-round distinguisher.

In Phase 1 of Algorithm 2, we find two 9-round trails with weight 30.000 for \( E_{0} \), marked as \( l_{0}^{1}, l_{0}^{2}\). We find two 9-round trails with weight 30.000 for \( E_{1} \), marked as \( l_{1}^{1}, l_{1}^{2}\). The details of \( l_{0}^{1}, l_{0}^{2}\) and \( l_{1}^{1}, l_{1}^{2}\) are listed in Table 15 and Table 16 of Appendix D.

In Phase 3 of Algorithm 2, we determine \( \hat{p_{1}}^{2}\hat{q_{1}}^{2} = 2 ^{-110.987}\), \( \hat{p_{2}}^{2}\hat{q_{1}}^{2} = 2 ^{-112.908}\), \( \hat{p_{1}}^{2}\hat{q_{2}}^{2} = 2 ^{-107.626}\) and \( \hat{p_{2}}^{2}\hat{q_{2}}^{2} = 2 ^{-109.913}\). We select \( l_{0}^{1} \) and \( l_{1}^{2} \) to make up the 19-round distinguisher. Since

$$\begin{aligned} S^{-1}\circ P^{-1}\circ K^{-1}(\delta _{2}) = 0x00 00 00 00 00 00 00 00 00 50 00 00 00 20 00 00, \end{aligned}$$

if we choose \( P^{-1}\circ K^{-1}(\delta _{2}) = 0x\)000000000000000000f0000000\( *\)00000 (\( *\)= 5 or 6), then \( r_{f} = 80\) and the complexity of the key filtering procedure will be too large. As a compromise, we choose \( P^{-1}\circ K^{-1}(\delta _{2}) = 0x00 00 00 00 00 00 00 00 0\) 020000000600000 which leads to \( \boldsymbol{ \hat{p}^{2}\hat{q}^{2} = 2 ^{-107.626+2} = 2 ^{-109.626}}\). In Table 11 of Appendix D, we show two examples of \( l_{0}^{1} \) and \( l_{1}^{2} \).

Finally, we obtain a 19-round related-key rectangle distinguisher with probability \( \boldsymbol{ 2^{-n} \hat{p}^{2}\hat{q}^{2} = 2^{-128}\cdot 2 ^{-109.626} }\). The specifications of the 19-round distinguisher are shown in Table 6. There are 3952 trails in \( \mathcal {C}_{I}(R_{0}, \alpha , \varDelta iniK_{0}, Bc_{R_{0}}) \) and 2944 trails in \( \mathcal {C}_{O}(R_{1}, \delta , \varDelta iniK_{1}, Bc_{R_{1}}) \).

Table 6. The specifications of the 19-round related-key rectangle distinguisher of GIFT-128
Full size table
Table 7. The 23-round key-recovery model of the related-key rectangle attack for GIFT-128
Full size table

We construct the 23-round key-recovery model for GIFT-128, which is shown in Table 7, by appending two rounds at the end of the 19-round distinguisher and two rounds at the beginning of the distinguisher.

Data Collection and Key Recovery. To prepare the plaintexts, we collect data in \( \varDelta Z_{1} \) of Table 7. There are nine unknown bits in \( \varDelta Z_{1} \) marked as “?", affecting three S-boxes in round 1. Thus, \( \boldsymbol{ r_{b} = 9 }\) and the number of key bits needed to be guessed in \( E_{b} \) is \( \boldsymbol{ m_{b} = 2\times 3 = 6}\). We have \( \boldsymbol{ r_{f} = 52} \) and \( \boldsymbol{ m_{f} = 2\times (13+4) = 34 }\) in \( E_{f} \). The following data collection and key recovery process are similar to the process of the 25-round attack in Sect. 5.1.

Construct \( y = \sqrt{s} \cdot 2^{n/2-r_{b}} / \hat{p}\hat{q}\) structures of \( 2^{r_{b}} \) plaintexts each. For each structure, query the \( 2^{r_{b}} \) plaintexts by the encryption oracle under \( K_{1}, K_{2}, K_{3} \) and \( K_{4} \). There are about \( M^{2} \cdot 2^{-2(n-r_{f} )} \) quartets left after executing step 3(c). Choosing \( s = 2 \), we have \( y = 2^{110.31} \), \( M = y \cdot 2^{r_{b}} = 2^{119.31} \) and \( M^{2} \cdot 2^{-2(n-r_{f} )} = 2^{86.62}\). After the key guessing and filtering process, there are about \( M^{2} \cdot 2^{-2(n-r_{f} )} \cdot 2^{-(48+24)} = 2^{14.62}\) remaining quartets. The two right quartets will all vote for the right key. The \( 2^{14.62} \) random quartets will vote for a random key with probability \( 2^{14.62-m_{f}} = 2^{-19.38}\). Choose \( h = 22 \) and select the top \( 2^{ m_{f} - h} \) hits in the counter to be the candidates. Exhaustively search the remaining \( 128 - m_{b} - m_{f} \) unknown key bits in the master key.

Complexity and Success Probability. The data complexity is \( 4M = 2^{121.31}\) chosen plaintexts. We need \( 2^{m_{b}}\cdot 3M = 2^{126.89}\) looking-up-table operations in step 3(b) and 3(c). We need \( 2^{m_{b}} \cdot M^{2} \cdot 2^{-2(n-r_{f} )} \cdot 4\cdot 2^{2}/23 = 2^{92.10}\) encryptions and \( 2^{k-h} = 2^{106}\) encryptions to recover the master key. So the time complexity is bounded by \( 2^{126.89} \). The memory complexity is bounded by \( 5M = 2^{121.63} \). The success probability is \( 92.01\% \) according to Eq. 12.

The related-key boomerang attack on 22-round GIFT-128 is demonstrated in Appendix B.

7 Conclusion and Future Work

In this paper, we carry out a further research on the resistance of GIFT against single-key and related-key differential cryptanalysis. We succeed in finding related-key differential trails of GIFT-64/128 for up to 15/14 rounds. We find the longest related-key differential trails for GIFT-128 and provide tighter lower bounds for the probabilities of the optimal related-key trails for both GIFT-64 and GIFT-128.

We find a 20-round related-key boomerang distinguisher of GIFT-64 with probability \( 2^{-58.557} \) and construct a 25-round related-key rectangle attack, which is the longest attack on GIFT-64. We obtain a 19-round related-key boomerang distinguisher of GIFT-128 with probability \( 2^{-109.626} \) and propose a 23-round related-key rectangle attack, which is the longest related-key attack on GIFT-128. The probability of the 20-round single-key differential distinguisher of GIFT-128 is also increased from \( 2^{-121.415} \) to \( 2^{-120.245} \). We improve the time complexity of the 26-round differential attack on GIFT-128 from \( 2^{124.415} \) to \( 2^{123.245} \).

Among the 32 candidates of the NIST lightweight crypto standardization process, there are four candidates which are based on GIFT: GIFT-COFB, HYENA, SUNDAE-GIFT, LOTUS-AEAD and LOCUS-AEAD. In the next work, we will study the security of these four lightweight authenticated encryption schemes against single-key/related-key differential cryptanalysis. Besides, We will try to apply Algorithm 1 and Algorithm 2 to other SPN ciphers with linear key schedule, for example, SKINNY [9].