Generalized Boomerang Connectivity Table and Improved Cryptanalysis of GIFT

Abstract

Boomerang connectivity table (BCT), an essential tool in boomerang attack, gives a unified description of the probability in the middle round of a boomerang distinguisher. However, it suffers the drawback that the asymmetric relationship between the upper and lower differentials in the middle round is ignored. To make up for this deficiency, we propose the generalized boomerang connectivity table (GBCT), which characterizes all combinations of upper and lower differentials to provide a more precise probability in the middle round. We first study the cryptographic properties of GBCT and introduce its variants applied in multiple rounds and Feistel structure. Then, we provide an automatic search algorithm to increase the probability of the boomerang distinguisher by adding thorough considerations that more trails can be included, which is applicable to all S-box based ciphers. Finally, we increase the probabilities of the 20-round GIFT-64 distinguisher from $2^{-58.557}$ to $2^{-57.43}$ and the 19-round GIFT-128 distinguisher from $2^{-109.626}$ to $2^{-108.349}$, both of which are the highest so far. Applying the key recovery attack proposed by Dong et al. at Eurocrypt 2022 on the new distinguisher, we achieve the lowest complexities of the attack on GIFT-64 and the best rectangle attack on GIFT-128.

1 Introduction

Differential cryptanalysis, proposed by Biham and Shamir [4] in 1990, is one of the most effective and widely used methods to attack many cryptographic primitives. However, it is often hard to find differential characteristics with high probabilities as the rounds of a cipher increase. In 1999, Wagner [21] proposed boomerang attack to replace one bad long differential trail with two good short differential trails. This attack makes it possible to conquer more rounds, and indicates that the security of a cipher cannot be guaranteed only by the non-existence of differentials with high probability.

In a boomerang attack, the target cipher E is decomposed into two parts as $E= E_1 \circ E_0$, where $E_0$ has a differential trail $\alpha \rightarrow \beta$ and $E_1$ has a differential trail $\gamma \rightarrow \delta$. Compositing the two sub-ciphers in a swerving way admits a boomerang distinguisher as long as $\beta \ne \gamma$, see Fig. 1. Under the independence assumption of $E_0$ and $E_1$, the probability of this distinguisher should be $p^2q^2$. However, it requires an adaptive chosen-plaintext/ciphertext scenario, which is not applicable to most key recovery settings. Then, the rectangle attack [3], a chosen-plaintext attack, is proposed to not only overcome this issue but also increase the probability of the distinguisher. It actually covers all possible differential trails $\alpha \rightarrow \beta _i$ for $E_0$ and $\gamma _j \rightarrow \delta$ for $E_1$ in the framework of a boomerang attack, thus increases the probability of the distinguisher to $2^{-n}\hat{p}^2\hat{q}^2$, where $\hat{p}=\sqrt{\sum _i\Pr ^2(\alpha \rightarrow \beta _i)}$ and $\hat{q}=\sqrt{\sum _j\Pr ^2(\gamma _j\rightarrow \delta )}$. To perform a rectangle attack, one needs to sieve right quarters (x, y, z, w) with $x\oplus y=z\oplus w=\alpha$ according to this probability.

Fig. 1.

The boomerang attack

Fig. 2.

The sandwich attack

It was noticed later that the independence assumption was invalid. To reveal this phenomenon, Biryukov and Khovratovich [5] proposed the boomerang switch to connect two differentials with a strong dependency. The observations were depicted in the framework of sandwich attack [13], which decomposes the cipher as $E=E_1\circ E_m\circ E_0$, where the middle part $E_m$ is the connection of the upper trail $\alpha \rightarrow \beta$ and the lower trail $\gamma \rightarrow \delta$, see Fig. 2. Then, $E_m$ can be regarded as a small boomerang distinguisher with probability r, where

$$\begin{aligned} r = \Pr [E_m^{-1}(E_m(x)\oplus \gamma )\oplus E_m^{-1}(E(x\oplus \beta )\oplus \gamma )=\beta ]. \end{aligned}$$

Thus, the probability of the whole boomerang distinguisher is $\hat{p}^2\hat{q}^2r$. Besides, Murphy [18] has pointed out that there may be incompatibility when connecting two independently chosen differential trails, which will result in an invalid boomerang distinguisher. Since the dependency between these two differential trails has a great impact on the probability of a boomerang distinguisher, at Eurocrypt 2018, Cid et al. [10] captured the above observations in a unified table called boomerang connectivity table (BCT) when $E_m$ is a single S-box layer. A new switch method named generalized switch was also depicted by the BCT.

As automatic tools has been widely used in searching for cryptographic distinguishers, it is natural to consider integrating BCTs with automatic tools to search for good distinguishers. There are mainly three automatic search tools in cryptanalysis, namely MILP (mixed integer linear programming), SAT/SMT (satisfiabality module theory) and Matsui’s algorithm. Liu and Sasaki [17] gave the first generic model of BCT to search for related-key boomerang distinguishers with SMT. Later, Ji et al. [16] proposed an automatic search algorithm by improving Matsui’s algorithm to search for the clustering of related-key differential trails utilized in the related-key boomerang distinguisher for GIFT-64 and GIFT-128, obtaining the best result up to now.

GIFT [2] is a lightweight block cipher with SPN structure. Because of its excellent performance in both hardware and software implementations, GIFT has been chosen as primitives in the design of many ciphers, such as GIFT-COFB [1], HYENA [8], LOCTUS-AEAD and LOCUS-AEAD [7], all of which are submitted to NIST’s Lightweight Cryptography Project, with GIFT-COFB being selected as one of the ten finalists. Studying the security of GIFT is therefore crucial and imperative.

Our Contributions. The main contributions of this paper are summarized below.

• 1. We propose a generalized boomerang connectivity table (GBCT).

  The GBCT, which can be viewed as a generalized version of BCT, receives four distinct differences as input to determine the number of quartets that meet these four differences. Additionally, we study the cryptographic properties of GBCT and give some variants of GBCT applied in multiple rounds and Feistel structure.

• 2. We provide a new search algorithm for boomerang distinguishers with considerations that more trails can be included, and increase the probability of distinguishers for GIFT.

  By adding three additional factors to the algorithm in [16], a better automatic search algorithm for boomerang distinguishers is obtained. Firstly, we relax the condition of input/output differences from optimal to suboptimal to get a better clustering effect. Secondly, we modify their method of searching for differential trails to search for differentials within a probability range. Lastly, we incorporate GBCT to ensure the compatibility of $E_0$ and $E_1$. Using the new algorithm, we improved the probabilities of distinguishers for GIFT-64 and GIFT-128, which increase from $2^{-58.557}$ to $2^{-57.43}$ and from $2^{-109.626}$ to $2^{-108.349}$ respectively.

• 3. We decrease the complexity of the attack on GIFT-64/GIFT-128 under the key recovery framework proposed by Dong et al.

  We apply the key recovery attack proposed by Dong et al. on the distinguishers and achieve a lower complexity than previous attacks. The data and time complexity drop from $2^{63.78}$ to $2^{62.72}$ and from $2^{122.78}$ to $2^{121.75}$ when attacking the 26-round GIFT-64. When attacking 23-round GIFT-128, the data and time complexity decrease from $2^{121.31}$ to $2^{120.175}$ and from $2^{126.89}$ to $2^{124.25}$ respectively. The current cryptanalytic results on GIFT are summarized in Table 1.

Table 1. Summary of the cryptanalytic results on GIFT

Outline. The rest of the paper is organized as follows. In Sect. 2, we give a brief overview of some previous work. In Sect. 3, we introduce the generalized boomerang connectivity table and study properties and variants of it. In Sect. 4, we outline the strategies for searching for a rectangle distinguisher, and give a new search algorithm. In Sect. 5, we provide the complexity analysis of the 26/23-round attacks on GIFT-64/GIFT-128. Section 6 concludes the paper.

2 Background and Previous Work

In this section, we give some preliminaries. First, we introduce some tables used to connect two sub-ciphers, such as BCT, BDT, EBCT (Figs. 3 and 4). Secondly, we give a brief introduction of some concepts necessary to search for a rectangle distinguisher, including the automatic search tool and the clustering effect. Finally, we recall the latest advances in key recovery attacks given in [12].

Fig. 3.

Structure of BCT

Fig. 4.

Structures of BDT and EBCT

2.1 BCT, BDT, EBCT

BCT is the first unified tool for evaluating dependencies between $E_0$ and $E_1$, but only applicable when $E_m$ is a single S-box layer. For $\beta ,~\gamma \in \mathbb {F}_2^n$, define

$$\begin{aligned} BCT(\beta ,\gamma )=\#\{x\in \mathbb {F}_2^n\mid S^{-1}(S(x)\oplus \gamma )\oplus S^{-1}(S(x\oplus \beta )\oplus \gamma )=\beta \}.\nonumber \end{aligned}$$

Song et al. [19] noticed that dependencies could affect more rounds. Meanwhile, some practical experiments [9, 17] showed that a higher probability could be achieved when $E_m$ contained two rounds. It is reasonable to believe that the more rounds $E_m$ contains, the more accurate the probability will be. Then, how to employ BCT in more rounds received much attention in the following research. Wang et al. [22] proposed a systematic analysis of the boomerang switching effect in multiple rounds and gave the boomerang difference table (BDT), renamed as UBCT in [11]. And its variant called BDT’ is also denoted by $D_{BCT}$ in [19] and renamed as LBCT in [11]. Its entry for $(\beta ,\beta ',\gamma )\in (\mathbb {F}_2^n)^3$ is computed by

After that, Delaune et al. [11] provided a new table to connect two differentials in more than two rounds, called extended boomerang connectivity table (EBCT), where for $(\beta ,\beta ',\gamma ,\gamma ')\in (\mathbb {F}_2^n)^4$,

$$\begin{aligned} EBCT(\beta ,\beta ',\gamma ',\gamma )=\#\left\{ x\in \mathbb {F}_2^n\biggm | \begin{aligned}&S(x)\oplus S(x\oplus \beta )=\beta ',~S(x)\oplus S(x\oplus \gamma ')=\gamma ,\nonumber \\&S^{-1}(S(x)\oplus \gamma )\oplus S^{-1}(S(x\oplus \beta )\oplus \gamma )=\beta \nonumber \end{aligned} \right\} . \end{aligned}$$

Besides, Hadipour et al. [14] introduced a new tool to model the dependency in more rounds called double boomerang connectivity table (DBCT) and used it for automatic searching for boomerang distinguishers.

2.2 Automatic Tools Modeling BCT

Because of its efficiency and simplicity, automatic tools have become crucial techniques for cryptanalysis in recent years. The effect of many commonly used attacks can be improved with the help of automatic tools, not only in searching for distinguishers but also in key recovery attacks. In this paper, we propose an algorithm to search for boomerang distinguishers with the automatic tool SMT. Here we give a brief introduction to it.

SMT is refereed to the problem of determining whether a mathematical formula is satisfiable. In cryptanalysis, one can use languages (e.g., SMTLIB2, CVC or BTOR) to model the property of components of a cipher, such as propagation of a differential and its probability, as an SMT problem, and obtain a desired solution (e.g., a differential trail with high probability) by SMT solvers. For example, in [17] the authors modelled the DDT and BCT with boolean constraints of an S-box. Following is an example of the description of BCT.

Example 1

Given boomerang propagations $(2\rightarrow 5)$ and $(2\rightarrow 6)$ of a $4\times 4$ S-box with $BCT(2,5) = BCT(2,6)=4$, we can model them with the logic expression $(x = 2)\wedge ((y = 5)\vee (y = 6))$. It is true when $x=2$ and $y=5$ or 6. Meanwhile, the probability is depicted by $w_4=((x = 2)\wedge (y = 5)\vee (x = 2)\wedge (y = 6))$, which means $w_4=1$ when the expression in the RHS is true, and the probability is obviously $4\cdot w_4/16$.

2.3 Clustering Effect in Boomerang Distinguishers

When utilizing a boomerang distinguisher, two essential factors are the input and output differences and the probability of the boomerang trail. Except for the input and output differences, the specific value of the differentials in the middle rounds is no longer important. We use $\hat{r}$ to denote the probability of getting a right quartet that follows an exact boomerang trail. The actual probability r is composed of the probabilities $\hat{r}$ corresponding to all possible intermediate differences and hence r is always greater than or equal to any single $\hat{r}$. Ji et al. gave a definition of the clustering of the related-key differential trails utilized in an R-round related-key boomerang distinguisher and proposed an automatic search algorithm for boomerang distinguishers, which exploits the concept of clustering effect to make the probability improved [16].

2.4 Key-Recovery Algorithms for Rectangle Attacks

Much research has been done on the key recovery algorithm for the rectangle attacks. The first rectangle attack [3] was proposed by Biham et al. in 2001, and was applied to Serpent in the single-key setting. Later, numerous research have been done to reduce the complexity of the attacks. For ciphers with linear key schedules, Dong et al. recently built a new key recovery attack model, with which the ratio of right quartets greatly soared. They found the right quartets must satisfy some nonlinear relations, which could be exploited to filter the wrong ones, so as to increase the proportion of the right quartets and decrease the attack complexity. The key recovery attack on GIFT-64 with their algorithm is the best so far. Afterwards, Dong et al. [12] made some modifications on their algorithm to give a unified and generic key recovery algorithm, which achieved the optimal complexity by selecting different parameters. In order to better illustrate the advantage of the new distinguisher, we use the same attack in [12] to launch on GIFT. Symbols used in the complexity analysis in Sect. 5 of our attack are the same to theirs as well.

Fig. 5.

Structure of GBCT

3 Generalized Boomerang Connectivity Table

In this section, we give a generalized boomerang connectivity table (GBCT), which looses the limitation of the symmetric connections to be arbitrary. After that, some cryptographic properties of GBCT are exhibited. In addition, we present some variants of GBCT for multiple rounds and Feistel structure. Finally, the benefits of GBCT are illustrated by some applications.

3.1 Introduction to GBCT

The idea for generalizing the BCT is natural, that is, instead of considering symmetric differences in two directions of the connection part of two sub-ciphers, we take all possible values in four directions in to consideration, see Fig. 5. When loosing the limitation of the symmetric input and output differences to be arbitrary, all possible connections of two sub-ciphers $E_0$ and $E_1$ are covered. Thus, a more precise probability of a boomerang distinguisher can be obtained with GBCT. This idea was mentioned in the [14] with no formal description given.

Definition 1

Let S be a permutation over $\mathbb {F}_2^n$ and $\beta _1,\beta _2,\gamma _1,\gamma _2\in \mathbb {F}_2^n$. The generalized boomerang connectivity table of S is a four-dimensional table, in which the entry for $(\beta _1,\beta _2;\gamma _1,\gamma _2)$ is computed by

It is easy to see that GBCT can also be represented as

$$\begin{aligned} GBCT(\beta _1,\beta _2;\gamma _1,\gamma _2)=\#\left\{ (x,y)\in \mathbb {F}^n_2\times \mathbb {F}^n_2 \biggm | \begin{aligned}&S(x)\oplus S(y)=\gamma _1,\\&S(x\oplus \beta _1)\oplus S(y\oplus \beta _2)=\gamma _2 \end{aligned} \right\} . \end{aligned}$$

The probability for an S-box with a given quarter of differences $(\beta _1,\beta _2;\gamma _1,\gamma _2)$ is $p=\frac{1}{2^n}\times GBCT(\beta _1,\beta _2;\gamma _1,\gamma _2)$. The time complexity for generating the GBCT for an n-bit S-box is $O(2^{4n})$.

In the following, we explain why GBCT can gain more solutions than BCT with the S-box of GIFT as an example.

Example 2

Given an input difference $\beta =8$, and two output differences $\gamma _1=8$, $\gamma _2=c$, the value of GBCT, DDT, and BCT are $GBCT(8,8;8,c)=16,$ $DDT(8,8)=DDT(8,c)=0,~ BCT(8,8)=BCT(8,c)=0$, respectively.

By looking up the DDT, we can find $\{\gamma '_1:DDT(\gamma '_1,8)=2\}=\{\gamma '_2:DDT(\gamma '_2,c)=2\}=\{1,3,5,7,9,b,c,e\}$, and the solution for each input difference is shown in the following table.

$\gamma '_1$	1	3	5	7	9	b	c	e
$(x_1,x'_1)$	(2, 3)	(d, e)	(9, c)	(0, 7)	(1, 8)	(4, f)	(6, a)	(5, b)
$\gamma '_2$	1	3	5	7	9	b	c	e
$(x_2,x'_2)$	(a, b)	(5, 6)	(1, 4)	(8, f)	(9, 0)	(c, 7)	(2, e)	(3, d)

It is clear that $(x_1,x'_1)\oplus (x_2,x'_2)=(8,8)$ always holds when $\gamma '_1=\gamma '_2$. That means if $(x_1,x'_1)$ and $(x_2,x'_2)$ are the solutions of two faces of a boomerang structure, we can use a difference $\beta _1=\beta _2=8$ to connect the differential trails on both sides to get a boomerang trail. Due to the symmetry of solutions, we can obtain 16 solutions in total.

Example 3

Given two input differences $\beta _1=1,~\beta _2=7$ and an output difference $\gamma =5$, the value of GBCT, DDT, and BCT are $GBCT(1,7;5,5)=10,~ DDT(1,5)=DDT(7,5)=2,~ BCT(1,5)=BCT(7,5)=2$, respectively. By looking up the DDT, we can find $\{\gamma ':DDT(\gamma ',5)=2 ~\text {or}~ 4\}=\{1,2,3,4,5,7\}$. Solutions of $DDT(\gamma ',5)>0$ are given below.

$\gamma '$	1	2	3	4	5	7
$(x,x')$	(c, d)	(0, 2)	(8, b)	(1, 5)	(a, f)	(9, e)
		(4,6)		(3,7)

Let $\beta _1=1$ and $\beta _2=7$, we can get $(x\oplus \beta _1,x'\oplus \beta _2)$ as follows.

$(x,x')$	(c, d) (d, c)	(0, 2) (2, 0)	(4, 6) (6, 4)	(8, b) (b, 8)	(1, 5) (5, 1)	(3, 7) (7, 3)	(a, f) (f, a)	(9, e) (e, 9)
$(x\oplus \beta _1,x'\oplus \beta _2)$	(d, a) (c, b)							(8, 9) (f, e)

When x and $x'$ are shifted by $\beta _1=1$ and $\beta _2=7$ respectively, there are 10 solutions whose output differences are 5. A boomerang trail can be obtained by connecting the differential trails on both sides of a boomerang structure with differences $\beta _1=1$ and $\beta _2=7$.

It can be concluded from the above examples that for a boomerang structure, $(x_1,x'_1)$ and $(x_2,x'_2)$ are solutions to differential trails $\gamma '_1\rightarrow \gamma _1$ and $\gamma '_2\rightarrow \gamma _2$ respectively on both sides of the structure, then $GBCT(\beta _1,\beta _2;\gamma _1,\gamma _2)>0$ as long as there exists two differences $\beta _1$ and $\beta _2$ such that $(x_2\oplus \beta _1,x'_2\oplus \beta _2)=(x_1,x'_1)$.

3.2 Properties of GBCT

In the following we give some basic properties of GBCT and its links with other tables, most of which can be deduced directly from the definition, so some proofs are omitted here.

Proposition 1

(Symmetry of GBCT)

$$\begin{aligned}&GBCT(\beta _1,\beta _2;\gamma _1,\gamma _2)\\ {}&=GBCT(\beta _2,\beta _1;\gamma _1,\gamma _2)=GBCT(\beta _1,\beta _2;\gamma _2,\gamma _1)=GBCT(\beta _2,\beta _1;\gamma _2,\gamma _1). \end{aligned}$$

Proposition 2

(Telations with DDT and BCT)

$$\begin{aligned}&GBCT(\beta ,\beta ;\gamma ,\gamma )=BCT(\beta ;\gamma ),~~GBCT(\beta _2,\beta _1;0,\gamma _2)=DDT(\beta _1\oplus \beta _2;\gamma _2),\\ {}&GBCT(0,\beta _2;\gamma _1,\gamma _2)=DDT(\beta _2;\gamma _1\oplus \gamma _2). \end{aligned}$$

Proposition 3

(Summation formula I)

$$\begin{aligned}&\sum _{\beta _1}GBCT(\beta _1,\beta _2;\gamma _1,\gamma _2)=\sum _{\beta _2}GBCT(\beta _1,\beta _2;\gamma _1,\gamma _2)=2^n,\\&\sum _{\gamma _1}GBCT(\beta _1,\beta _2;\gamma _1,\gamma _2)=\sum _{\gamma _2}GBCT(\beta _1,\beta _2;\gamma _1,\gamma _2)=2^n. \end{aligned}$$

Proposition 4

(Summation formula II)

$$\sum _{\beta _1,\beta _2}GBCT(\beta _1,\beta _2;\gamma _1,\gamma _2)=\sum _{\gamma _1,\gamma _2}GBCT(\beta _1,\beta _2;\gamma _1,\gamma _2)=2^{2n}.$$

Proposition 5

$$GBCT_{S^{-1}}(\gamma _1,\gamma _2;\beta _1,\beta _2)=GBCT_S(\beta _1,\beta _2;\gamma _1,\gamma _2).$$

Proposition 6

$$\begin{aligned}&GBCT(\beta _1,\beta _2;\gamma _1,\gamma _2)\\&=CDDT(\beta _1,\gamma _2;\beta _2,\gamma _1) +\sum _{\alpha \ne 0,\beta _2}\#\left( \bigcup _{\alpha ,\gamma _1}\cap \left( \bigcup _{\alpha \oplus \gamma _1\oplus \gamma _2,\gamma _2}\oplus \beta _1\right) \right) , \end{aligned}$$

where $\bigcup _{a,b}:=\{x\in \mathbb {F}^n_2|S(x)\oplus S(x\oplus a)=b\}$ and the cross-DDT of S is

Proposition 7

$$\begin{aligned}&GBCT(\beta _1,\beta _2;\gamma _1,\gamma _2)\\&=\frac{1}{2^{4n}}\cdot \sum _{a,b,c,d}(-1)^{a\cdot \gamma _1\oplus b\cdot \gamma _2\oplus c\cdot \beta _1\oplus d\cdot \beta _2}\cdot W_F(c,a)\cdot W_F(c,b)\cdot W_F(d,a)\cdot W_F(d,b). \end{aligned}$$

where $W_F(u,v):=\sum _{x}(-1)^{ux\oplus vF(x)}$.

Proof

We have

$$\begin{aligned}&GBCT(\beta _1,\beta _2;\gamma _1,\gamma _2)\\&=\#\{(x,y)\in \mathbb {F}^n_2\times \mathbb {F}^n_2|F(x)\oplus F(y)=\gamma _1,~F(x\oplus \beta _1)\oplus F(y\oplus \beta _2)=\gamma _2\}\\&=\frac{1}{2^{2n}}\sum _{x,y}\sum _{a,b}(-1)^{a(F(x)\oplus F(y)\oplus \gamma _1)}(-1)^{b(F(x\oplus \beta _1)\oplus F(y\oplus \beta _2)\oplus \gamma _2)}\\&=\frac{1}{2^{2n}}\sum _{a,b}(-1)^{a\gamma _1\oplus b\gamma _2}\sum _{x,y} (-1)^{a\cdot F(x)\oplus b\cdot F(x\oplus \beta _1)}(-1)^{a\cdot F(y)\oplus b\cdot F(y\oplus \beta _2)}\\&=\frac{1}{2^{2n}}\sum _{a,b}(-1)^{a\gamma _1\oplus b\gamma _2}C_{\beta _1}(a,b)C_{\beta _2}(a,b), \end{aligned}$$

where

$$\begin{aligned} C_\beta (a,b)&=\sum _x(-1)^{a\cdot F(x)\oplus b\cdot F(x\oplus \beta )}\\&=\frac{1}{2^n}\sum _w(-1)^{w(x\oplus y)}\sum _{x,y}(-1)^{a\cdot F(x)\oplus F(y\oplus \beta )}\\&=\frac{1}{2^n}\sum _w(-1)^{w\cdot z}\sum _{x,z}(-1)^{a\cdot F(x)\oplus b\cdot F(x\oplus z\oplus \beta )}\\&=\frac{1}{2^n}\sum _{w,x,z}(-1)^{[a\cdot F(x)\oplus w\cdot x]\oplus [b\cdot F(x\oplus z\oplus \beta )\oplus w(x\oplus z\oplus \beta )]\oplus w\cdot \beta }\\&=\frac{1}{2^n}\sum _w(-1)^{w\cdot \beta }W_F(w,a)\cdot W_F(w,b). \end{aligned}$$

Proposition 8

Let F, G be two permutations of $\mathbb {F}_2^n$ with $G=F\circ L$ for an invertible affine transformation L of $\mathbb {F}_2^n$. Then we have

$$g_G(a_1,a_2;b_1,b_2)=g_F(L_1(a_1),L_1(a_2), L^{-1}_2(b_1), L^{-1}_2(b_2)).$$

for all $a,b \in \mathbb {F}^n_2$, where $g_F(a_1,a_2;b_1,b_2)=GBCT(a_1,a_2;b_1,b_2)$ for F.

3.3 Variants of GBCT

GBCT in Multi-rounds. Just as how Wang et al. extend BCT to be used in two-round $E_m$, GBCT can also be converted with the same idea to be applied in two rounds. We introduce the generalized boomerang differential table (GBDT) (Fig. 6).

Fig. 6.

Structures of GBDT (left) and GBET (right)

Definition 2

Let S be a permutation over $\mathbb {F}_2^n$ and $\beta _1,\beta _2,\gamma _1,\gamma _2,\beta '_1,\beta '_2 \in \mathbb {F}_2^n$. The generalized boomerang differential table (GBDT) of S is a 6-dimensional table, in which the entry for $(\beta _1,\beta _2;\gamma _1,\gamma _2;\beta '_1,\beta '_2)$ is computed by

GBDT and BDT shares some properties, most of which can be easily obtained from the definition, so it is not proved here. Refer interested readers to [22] for more details.

Next, we use the same notations as in [22] to show how to calculate the probability with GBDT. The probability of a two-round $E_m$ is the product of the two probabilities $r=p_1p_2$, where

$$\begin{aligned}&p_1=\prod _{(\varDelta _1,\varDelta _2;\nabla ''_1,\nabla ''_2;{\varDelta '_1},{\varDelta '_2})\in L_1}GBDT(\varDelta _1,\varDelta _2;\nabla ''_1,\nabla ''_2;{\varDelta '_1},{\varDelta '_2})/2^n,\\&p_2=\prod _{(\nabla _1,\nabla _2;\varDelta ''_1,\varDelta ''_2;{\nabla '_1},{\nabla '_2})\in L_2}GBDT(\nabla _1,\nabla _2;\varDelta ''_1,\varDelta ''_2;{\nabla '_1},{\nabla '_2})/2^n. \end{aligned}$$

When $E_m$ covers more rounds, we can borrow the idea of EBCT [11] to give the definition of GBET.

Definition 3

Let S be a permutation over $\mathbb {F}_2^n$ and $\beta _1,\beta _2,\gamma _1,\gamma _2,\beta '_1,\beta '_2,\gamma '_1,\gamma '_2 \in \mathbb {F}_2^n$. The generalized boomerang extended table (GBET) of S is a 8-dimensional table, in which the entry for $(\beta _1,\beta _2;\gamma _1,\gamma _2;\beta '_1,\beta '_2;\gamma '_1,\gamma '_2)$ is computed by

When $E_m$ covers more rounds, the probability is $r=\prod _{i}p_i$, where

$$\begin{aligned}&p_i=\prod _{(\varDelta _1,\varDelta _2;\nabla _1,\nabla _2;{\nabla '_1},{\nabla '_2};{\varDelta '_1},{\varDelta '_2})\in L_i}GBDT(\varDelta _1,\varDelta _2;\nabla _1,\nabla _2;{\nabla '_1},{\nabla '_2};{\varDelta '_1},{\varDelta '_2})/2^n, \end{aligned}$$

and $L_i$ has the same meaning as the previous one.

Fig. 7.

The GBCT in a Feistel structure

Put GBCT into a Feistel Structure. The FBCT was proposed as a counterpart of BCT for Feistel structures and its properties have also been studied in [6, 15]. Similar to BCT, GBCT is also applicable into Feistel structures. Here we take a generic Feistel structure as example, as shown in Fig. 7. Denote the output after one round of $X^i=L^i||R^i,i=1,...,4$ as $Y^i=G^i||L^i,i=1,...,4$. Assume that $X^1\oplus X^2=\beta _1=\beta _1^L||\beta _1^R$, $Y^1\oplus Y^3=\gamma _1=\gamma _1^L||\gamma _1^R$ and $Y^2\oplus Y^4=\gamma _2=\gamma _2^L||\gamma _2^R$. Now, we check whether $X^3\oplus X^4=\beta _2=\beta ^L_2||\beta ^R_2$:

$$\begin{aligned} \beta ^L_2&= L^3\oplus L^4= L^1\oplus \gamma _1^R\oplus L^2\oplus \gamma _2^R=\beta _1^L \oplus \gamma _1^R\oplus \gamma _2^R,\\ \beta ^R_2&=R^3\oplus R^4=F(L^3)\oplus G^3\oplus F(L^4)\oplus G^4\\&= R^1\oplus R^2\oplus \gamma _1^L\oplus \gamma _2^L\oplus F(L^1)\oplus F(L^1\oplus \gamma _1^R)\oplus F(L^2)\oplus F(L^2\oplus \gamma _2^R)\\&=\beta _1^R \oplus \gamma _1^L\oplus \gamma _2^L\oplus F(L^1)\oplus F(L^1\oplus \gamma _1^R)\oplus F(L^1\oplus \beta _1^L)\oplus F(L^1\oplus \beta _1^L\oplus \gamma _2^R). \end{aligned}$$

If $X^3\oplus X^4=\beta _2$, then $\beta _2$ should satisfy $\beta _2^L=\beta _1^L\oplus \gamma _1^R\oplus \gamma _2^R$ and $\beta _2^R=\beta _1^R \oplus \gamma _1^L\oplus \gamma _2^L\oplus F(L^1)\oplus F(L^1\oplus \gamma _1^R)\oplus F(L^1\oplus \beta _1^L)\oplus F(L^1\oplus \beta _1^L\oplus \gamma _2^R)$.

We degenerate the F function to the S-box layer. For each S-box, the input difference deduced from $\beta _i^L,i=1,2$ and $\gamma _i^R,i=1,2$ are denoted as $\varDelta ^L_i,i=1,2$ and $\varDelta ^R_i,i=1,2$. The output differences are denoted as $\nabla _i,i=1,2$ which are deduced from $\beta _i^R\oplus \gamma _i^L$. Then, the definition of FGBCT for each S-box is given below:

Definition 4

Let $S: \mathbb {F}_2^n\rightarrow \mathbb {F}_2^m$, $\varDelta ^L_1,\varDelta ^R_1,\varDelta ^L_2,\varDelta ^R_2,\nabla _1,\nabla _2\in \mathbb {F}_2^n$. The FGBCT of S is given by a 6-dimensional table, in which the entry for the $(\varDelta ^L_1,\varDelta ^R_1;\varDelta ^L_2,$ $\varDelta ^R_2;\nabla _1,\nabla _2)$ position is given by

Then, the probability of a boomerang for a Feistel structure with an S-box is given by $2^{-n}\cdot FGBCT(\varDelta ^L_1,\varDelta ^R_1;\varDelta ^L_2,\varDelta ^R_2;\nabla _1,\nabla _2)$.

Similarly, we give the definition of FGBDT and FGBET used in multi-round $E_m$. Symbols in the definitions are shown in the Fig. 8.

Definition 5

Let $S: \mathbb {F}_2^n\rightarrow \mathbb {F}_2^m$, and the differences $\varDelta ^L_1,\varDelta ^R_1,\varDelta ^L_2,\varDelta ^R_2,\nabla _1,\nabla _2,$ ${{\varDelta '_1}}^L,{{\varDelta '_2}}^L\in \mathbb {F}_2^n$. The FGBDT of S is given by a 8-dimensional table, in which the entry for the $(\varDelta ^L_1,\varDelta ^R_1;\varDelta ^L_2,\varDelta ^R_2;\nabla _1,\nabla _2;{{\varDelta '_1}}^L,{{\varDelta '_2}}^L)$ position is given by

Fig. 8.

Structures of FGBDT and FGBET

Definition 6

Let $S: \mathbb {F}_2^n\rightarrow \mathbb {F}_2^m$, and the differences $\varDelta ^L_1,\varDelta ^R_1,\varDelta ^L_2,$ $\varDelta ^R_2,\nabla _1,\nabla _2,$ ${\varDelta '_1}^L,{\varDelta '_2}^L,{\varDelta '_1}^R,{\varDelta '_2}^R\in \mathbb {F}_2^n$. The FGBET of S is given by a 10-dimensional table, in which the entry for the $(\varDelta ^L_1,\varDelta ^R_1;\varDelta ^L_2,\varDelta ^R_2;\nabla _1,\nabla _2;{\varDelta '_1}^L,{\varDelta '_2}^L;{\varDelta '_1}^R,{\varDelta '_2}^R)$ position is given by

3.4 The Advantages of GBCT

The probability of a boomerang distinguisher with BCT in one-round $E_m$ is calculated in [16] as

$$\begin{aligned} \hat{p}^2\hat{q}^2= \frac{1}{2^n}\sum _{i,j}p^2_i\cdot q^2_j\cdot BCT(\beta _i,\gamma _j). \end{aligned}$$

For each boomerang trail $\alpha \rightarrow \beta _i\rightarrow \gamma _j\rightarrow \delta$, if the value of $BCT(\beta _i,\gamma _j)$ is 0, even if the value of $p^2_i\cdot q^2_j$ is high enough, the trail is still in vain. Yet, BCT is limited to connecting $\beta$ and $\gamma$ that are symmetric in two faces of $E_m$, leaving out a large number of asymmetric combinations, which can be completed by GBCT.

In order to illustrate that GBCT can completely describe all combinations of $\beta$ and $\gamma$, we list the distribution of GBCTs of some 4-bit S-boxes used in cryptographic primitives in Table 2, where the blue font represents the corresponding value of BCT. It turns out that GBCT can provide some probabilities that BCT cannot. The following example illustrates a boomerang trail that is incompatible when connecting $E_0$ and $E_1$ via BCT but effective with GBCT.

Table 2. GBCTs of 4-bit S-boxes from Sage’s Cryptography package; see https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/sboxes.html

Fig. 9.

20-round boomerang trail with GBCT

Example 4

A 20-round boomerang trail of GIFT-64 with GBCT is shown in Fig. 9. The trail is obtained by connecting two 10-round related-key differential trails in $E_0$ and two 9-round related-key differential trails in $E_1$ with GBCT. And two key differences are

$$\begin{aligned} \varDelta iniK&= 0x 0004 0000 0000 0800 0000 0000 0000 0010,\\ \nabla iniK&= 0x 2000 0000 0000 0000 0800 0000 0200 0800 \end{aligned}$$

The probability of this distinguisher is $p^2 q^2 r = 2^{-21\cdot 2}\cdot 2^{-15\cdot 2}\cdot 2^{-1}=2^{-73}$ when connected with GBCT, but 0 when connected with BCT.

4 New Search Algorithm for a Boomerang Distinguisher

The instance in Example 4 illustrates the effectiveness of using GBCT as the connection in a boomerang trail. Then, we consider to construct a generic model of the GBCT with automatic the search tool SMT, and search for boomerang distinguishers.

4.1 Strategies in the Search Algorithm

In [16], Ji et al. proposed an automatic search algorithm to boost the probability of a related-key boomerang distinguisher by taking the cluster effect into account, which has the best performance in searching for boomerang distinguishers. Making some improvements on the base of the algorithm, we obtain a new search algorithm performing better. With the new algorithm, we get boomerang distinguishers with higher probabilities for GIFT-64 and GIFT-128. The details of the distinguishers will be given in the next subsection.

Table 3. Symbols in Algorithm 1

Here gives the strategy to search for a rectangle distinguisher. Firstly, we find that when searching for the 10-round differential trails the optimal probability is $2^{-19.83}$, rather than $2^{-20.415}$ searched in [16]. The details of the optimal differentials are listed in Table 6 in Appendix A. Taking the probability range $bw=4$, and choosing the optimal $\alpha$, we discover that it has only 263 output differences $\beta _i$ and a total of 308 trails can be obtained, which is smaller than the quantity of that with the suboptimal $\alpha$, who has 2944 distinct $\beta _i$ and a total of 5728 trails. Thus, to get a better cluster effect, we should select $\alpha$ and $\delta$ with more $\beta$ and $\gamma$ in the first phase. In addition, replacing the probability of each differential trail with the probability of differential is a better way to approximate the real probability. Thirdly, the completeness of the connections in $E_m$ should be ensured to form more valid boomerang trails. Finally, an improved boomerang distinguisher search Algorithm 1 is proposed in light of the aforementioned factors. And the search algorithm in single-key setting can be obtained likewise. Symbols used in Algorithm 1 is explained in Table 3.

4.2 The Improved Distinguisher with GBCT for GIFT

Here, we give the details of the new distinguisher of GIFT-64 and GIFT-128.

Choosing $R_0=10$ for $E_0$, $R_1=9$ for $E_1$, $R_m=1$ for $E_m$ and $bw=\bar{bw}=4$ to search for a 20-round GIFT-64 distinguisher. The experimental result indicates that the probability of the new distinguisher is optimal with the $\alpha$ and $\delta$ used in [16]. But, in Phase 2, we get 376 differentials trails with 376 distinct $\gamma _j$ more than 312 differentials trails searched in [16]. In phase 3, we found a total of 5520 boomerang trails that were left out as BCT could not connect. Finally, the probability of the 20-round distinguisher found in [16] is increased to $2^{-57.43}$.

For GIFT-128, we chose $R_0$= 9 for $E_0$, $R_1$ =9 for $E_1$, $R_m$ = 1 for $E_m$ and $bw=\bar{bw} = 4$. In phase 1, we got 10184 distinct $\beta$. All the $\beta$ and $\gamma$ can form $(10184\times 2944)^2$ possible boomerang trails, which leads to an excessive calculating complexity. So we select the top 200 $\beta$ and 450 $\gamma$ with high probability to connect by GBCT($\beta ^i,\beta ^j;\gamma ^s,\gamma ^t$), and the remaining are still connected by BCT($\beta , \gamma$). Finally, 2782 trails ignored under BCT connection are obtained, and the probabilities of these trails are accumulated to obtain the probability of the distinguisher of $2^{-108.349}$.

All the parameters of the 20/19-round related-key rectangle distinguisher for GIFT-64/128 are shown in Table 4 and Table 5.

Table 4. The specifications of the 20-round related-key rectangle distinguisher for GIFT-64

Table 5. The specifications of the 19-round related-key rectangle distinguisher for GIFT-128

5 Rectangle Attacks on GIFT-64 and GIFT-128 with Reduced Complexities

Since the new distinguishers for GIFT-64 and GIFT-128 improve only the probability while using the same input-output differences as in [16], Dong’s key recovery algorithm can be directly applied with it. Here, we only give the complexity analysis of the attack and will not dwell on the details of the key recovery process. Interested readers are referred to [12, 16].

5.1 Complexity Analysis of Key-Recovery Attack on GIFT-64

The target key bits are 68 with 30 bits in $E_b$ and 38 bits in $E_f$. We first guess $m_b+m'_f=60$ bits subkey to construct quartet candidates. Then eliminate the wrong quartets in a guess and filter procedure to determine the remaining 8 bits. Finally, guess the remaining $128-h$ bit keys to check the full key.

- Data complexity: we need to prepare $4\cdot D=4\cdot y\cdot 2^{r_b}=\sqrt{s}\cdot 2^{n/2+2}/{\hat{p}\hat{q}}=\sqrt{s}\cdot 2^{62.715}$ data.

- Memory complexity: we need $4\cdot D+2^{68-x}=\sqrt{s}\cdot 2^{62.715}+2^{68-x}$ memory to store the data and key counters.

- Time complexity: Firstly, we need $T_1=\sqrt{s}\cdot 2^{m_b+m'_f+n/2+1}/{\hat{p}\hat{q}}=\sqrt{s}\cdot 2^{121.715}$ to generate quartet candidates. Then, the time complexity of filtering wrong quartets is $T_2=(s\cdot 2^{m_b+m'_f-n+2r_f-2h_f}/{{\hat{p}}^2{\hat{q}}^2})\cdot \varepsilon =s\cdot 2^{83.43}\cdot \varepsilon$. Finally, we need $T_3=2^{128-h}$ for an exhaustive search.

To balance the above complexity, we choose $x = 8$, $h = 20$ and $s = 1$ in order to achieve a success probability of $69.45\%$. At last, we have a time complexity of $2^{121.715}$ for 26-round encryptions, a data complexity of $2^{62.715}$ and a memory complexity of $2^{62.715}$.

5.2 Complexity Analysis of Key-Recovery Attack on GIFT-128

The target key bits is 39 with 6 bits in $E_b$ and 33 bits in $E_f$. We repeat the same process as the attack on GIFT-64 for GIFT-128 with $m_b+m'_f=6+0=6$.

- Data complexity: we need to prepare $4\cdot D=\sqrt{s}\cdot 2^{120.175}$ data.

- Memory complexity: we need $4\cdot D+2^{68-x}=\sqrt{s}\cdot 2^{120.175}+2^{39}$ memory to store the data and key counters.

- Time complexity: Firstly, we need $T_1=\sqrt{s}\cdot 2^{m_b+m'_f+n/2+1}/{\hat{p}\hat{q}}=\sqrt{s}\cdot 2^{125.175}$ to generate quartet candidates. Then, the time complexity of filtering wrong quartets is $T_2=(s\cdot 2^{m_b+m'_f-n+2r_f-2h_f}/{{\hat{p}}^2{\hat{q}}^2})\cdot \varepsilon =s\cdot 2^{90.5}\cdot \varepsilon$. Finally, we need $T_3=2^{128-h}$ for an exhaustive search.

To balance the above complexity, We choose $h = 20$ and $s = 1$ in order to achieve a good success probability of $84.00\%$. At last, we have a time complexity of $2^{125.175}$ 23-round encryptions, a data complexity of $2^{120.175}$ and a memory complexity of $2^{120.175}$.

6 Conclusion and Future Discussion

In this paper, we propose the GBCT to complement the leaky part that can not be evaluated by BCT, so as to obtain a more accurate distinguisher probability. Then, an automatic search algorithm applicable to all S-box-based block ciphers is provided to obtain a rectangle distinguisher with higher probability. Utilizing the algorithm, we achieve the optimal probability of distinguishers for 20/19-round GIFT-64/128, and therefore the lowest data and time complexities of the related-key rectangle attacks on GIFT-64/128 up to now.

There are still some unfinished work to be investigated in the future. More variables introduced by GBCT are very constrained for the MILP model when $E_m>1$. In addition, the search algorithm is only applicable to ciphers with S-boxes as the nonlinear layers. In the future, we will extend the research to fully assess the probability in $E_m$, not only when $E_m>1$, but also for ciphers with nonlinear components like modular additions or bit-wise AND operations.

A 10-Round Optimal (Related-Key) Differentials for GIFT-64

Table 6. Input and Output differences of 10-round related-key differential trails with weight 19.8 of GIFT-64