Quantum Attacks Against Type-1 Generalized Feistel Ciphers and Applications to CAST-256

Abstract

Generalized Feistel Schemes (GFSs) are important components of symmetric ciphers, which have been extensively studied in the classical setting. However, detailed security evaluations of GFS in the quantum setting still remain to be explored.

In this paper, we give improved polynomial-time quantum distinguishers on Type-1 GFS in quantum chosen-plaintext attack (qCPA) setting and quantum chosen-ciphertext attack (qCCA) setting. In qCPA setting, we give a new quantum polynomial-time distinguisher on $(3d-3)$-round Type-1 GFS with branches $d\ge 3$, which gains $(d-2)$ more rounds than the previous distinguishers. This leads us to obtain a better key-recovery attack with reduced time complexities by a factor of $2^{\frac{(d-2)n}{2}}$, where n is the bit length of the branch. We also show a quantum distinguishing attack against $(d^2-d+1)$-round version in qCCA setting, and this gives a key-recovery attack with much lower time complexity.

In addition, based on a 14-round quantum distinguisher, we give quantum key-recovery attacks on round-reduced CAST-256 block cipher. For the 256-bit key version, we could attack up to 20-round CAST-256 in time $2^{111}$, which is faster than the quantum brute-force attack by a factor of $2^{17}$. For the 128-bit key version, we could attack 17 rounds in time $2^{55.5}$, while the best previous classical or quantum attacks are no more than 16 rounds.

1 Introduction

Feistel block ciphers are featured by the efficient Feistel network, whose encryption and decryption processes are based on similar operations. This design has been extensively studied [8, 15, 20, 27] and adopted in many standard block ciphers, including DES, Triple-DES, Camellia [3], and GOST [12]. Feistel network was also generalized to form Generalized Feistel Networks (GFNs) or Generalized Feistel Schemes (GFSs). GFSs adopt more than two branches and different operations between the branches. At CRYPTO 1989, Zheng et al. [46] summarized several types of GFSs, called Type-1, Type-2, and Type-3 GFSs. In addition, some other GFSs were invented by Anderson and Biham [2], Lucks [32] and Schneier and Kelsey [38]. Many important primitives employ GFSs, such as block ciphers CAST-256 [1] (Type-1), CLEFIA [39] (Type-2), Simpira [14] (Type-2), as well as hash functions MD5 and SHA-1 (Type-1). GFSs inherit the advantages of Feistel network. Besides, it allows a small round function to construct a cipher with a larger block size, which is beneficial to lightweight implementations.

Classically, Luby and Rackoff [31] proved that the 3-round Feistel scheme is a secure pseudo-random permutation. At CRYPTO 1989, Zheng et al. [46] showed that the $(2d-1)$-round Type-1 GFS is secure against chosen-plaintext attacks. Moriai and Vaudenay pointed out that $(d^2-d)$-round Type-1 GFS is not secure against chosen-ciphertext attacks [33]. See also the analysis by Hoang and Rogaway [17]. Generic attacks on these constructions are also widely studied, such as birthday attack [23], meet-in-the-middle attack [16], differential attacks [34, 41], and Patarin et al.’s attacks [35, 36, 42].

It was a common belief that quantum attacks on symmetric primitives are of minor concern, as they mainly consist of employing Grover’s algorithm [13] to generically speed up search (sub-)problems. However, Kuwakado and Morii [28] found the first polynomial-time quantum distinguisher on 3-round Feistel block ciphers by using Simon’s algorithm [40]. This result proves that there is a case that quantum attacks can exponentially improve classical attacks. Later, various quantum attacks against symmetric primitives were invented, such as key-recovery attacks against Even-Mansour constructions [29], forgery or key-recovery attacks against block cipher based MACs [5, 24], key-recovery attacks against the FX construction [30], and so on.

At FOCS 2012, Zhandry et al. [45] classified the quantum cryptanalysis into two models, i.e., the standard security (Q1 model) and quantum security (Q2 model). In Q1 model, adversaries could only collect data classically and process them with local quantum computers. In contrast to this, in Q2 model, the adversaries could query the oracle with quantum superpositions of inputs, and obtain the corresponding superposition of outputs. Adversaries from Q2 model are more powerful, while Q2 model is not realistic for the foreseeable future. However, Q2 model is still theoretically interesting. Moreover, as stated by Ito et al. [22], “the threat of this attack model becomes significant if an adversary has access to its white-box implementation. Because arbitrary classical circuit can be converted into quantum one, the adversary can construct a quantum circuit from the classical source code given by the white-box implementation”. In this paper, we assume that the adversaries are in the Q2 model.

There have already been papers investigating Feistel schemes or GFSs against Q2 adversaries. Besides Kuwakado and Morii [28]’s work, Ito et al. [22] extended the quantum distinguisher to 4-round Feistel scheme under quantum chosen-ciphertext attack setting. Based on the Grover-meets-Simon algorithm by Leander and May [30], Hosoyamada et al. [19] and Dong et al. [11] introduced some quantum key-recovery attacks on Feistel schemes. Dong et al. [10] gave some quantum distinguishers and key-recovery attacks on some GFSs. Dong et al. [9] and Bonnetain et al. [6] studied 2K-/4K-Feistel schemes against quantum slide attacks. Notably, Hosoyamada and Iwata [18] proved a quantum security bound of the 4-Round Luby-Rackoff construction recently.

Our Contributions. We continue the work of Dong, Li, and Wang [10] to evaluate the security of Type-1 GFSs against quantum attacks. We focus on Type-1 GFSs, as the structure is employed in the above mentioned practical designs¹. We give some improved attacks on Type-1 GFSs in Q2 model with both quantum chosen-plaintext attack (qCPA) setting and quantum chosen-ciphertext attack (qCCA) setting. Then, some applications to CAST-256 block ciphers are given. We have three contributions:

• First, in qCPA setting, we give new quantum polynomial-time distinguishers on $(3d-3)$-round Type-1 GFS with branches $d\ge 3$, which gain $(d-2)$ more rounds than the previous distinguishers. The improvement is obtained by shifting the position of $\alpha _b$, which is a constant used to define a period, so that the period is preserved for longer rounds. It turns out that the observation is simple, but effective to improve the number of rounds that we can attack. Based on Leander and May’s algorithm [30], we could get better key-recovery attacks, whose time complexities gain a factor of $2^{\frac{(d-2)n}{2}}$, where n is the bit length of the branch.

• Second, assuming that we are in the qCCA setting, we show a distinguishing attack against the $(d^2-d + 1)$-round version. The number of rounds is significantly larger than the above, and this follows the intuition in the classical setting where the diffusion of Type-1 GFS in the decryption direction is slow, which is pointed out in [33]. The distinguishers in both qCPA and qCCA settings and the key-recovery attacks are summarized in Tables 1 and 2.

• Third, we also evaluate CAST-256 block cipher against quantum attacks. We find 14-round polynomial-time quantum distinguishers in qCPA setting. Note that the best previous one is 7 rounds [10]. Based on this, we could derive quantum key-recovery attack on 20-round CAST-256. Compared to this, the best previous quantum key-recovery attack is on 16 rounds. The results are summarized in Table 3. We also compare our quantum attacks with classical attacks in Table 4. When the key size of CAST-256 is 128, our result also reaches 17 rounds, which gains one more round than before.

Table 1. Rounds of quantum distinguishers on Type-1 GFS

Table 2. Key-recovery attacks on Type-1 GFS ($d\ge 3$) in quantum settings

Table 3. Quantum attacks on CAST-256†

Table 4. Comparison between classical and quantum attacks on CAST-256

2 Preliminaries

2.1 Notation

For a positive integer n, let $\{0,1\}^n$ be the set of all strings of n bits. Let $\mathrm {Perm}(n)$ be the set of all permutations on $\{0,1\}^n$, and let $\mathrm {Func}(n)$ be the set of all functions from $\{0,1\}^n$ to $\{0,1\}^n$. For vectors a and b of the same dimension, we denote their inner product by $a\cdot b$. In this paper, e denotes Napier’s number.

2.2 Type-1 Generalized Feistel Schemes

In this section, we describe Type-1 generalized Feistel schemes (GFSs) [46]. In Type-1 GFS, we divide the dn-bit state into d branches, where $d\ge 3$ and each branch constitutes an n-bit sub-block. Let $\varPhi _r$ denote the encryption algorithm of the r-round Type-1 GFS, and $\varPhi ^{-1}_r$ denote its decryption algorithm. Let $R_1,R_2,\dots ,R_r\in \mathrm {Func}(n)$ be the keyed round functions of $\varPhi _r$. We assume that the function $R_i$ takes a $k$-bit key $k_i$ as input (thus the total key length of $\varPhi _r$ is $rk$ bits). $\varPhi _r$ takes a plaintext $(x_0^0,x_1^0,\dots ,x_{d-1}^0)\in (\{0,1\}^n)^d$ as input, and outputs a ciphertext $(x_0^r,x_1^r,\dots ,x_{d-1}^r)\in (\{0,1\}^n)^d$, where the i-th round is defined as

$$\begin{aligned} (x_0^i,x_1^i,\ldots ,x_{d-1}^i)=(R_i(x_0^{i-1})\oplus x_1^{i-1},x_2^{i-1},x_3^{i-1},\dots ,x_{d-1}^{i-1},x_0^{i-1})\,. \end{aligned}$$

The decryption is naturally defined by reversing the direction of the shift of the branches. Figure 1 shows the i-th round of Type-1 GFS.

Fig. 1.

The i-th round of Type-1 GFS

2.3 Simon’s Algorithm

Here we review Simon’s algorithm [40] that is the basis of our distinguishers. Simon’s algorithm solves the following problem efficiently.

Problem 1

Given a function $f:\{0,1\}^n\rightarrow \{0,1\}^n$ that has a non-zero period $s\in \{0,1\}^n$ such that

$$\begin{aligned} f(x)=f(x')\Leftrightarrow x'=x\oplus s \end{aligned}$$

for any distinct $x,x'\in \{0,1\}^n$, the goal is to find the period s.

In the classical setting, $O(2^{n/2})$ queries are needed to find s, while Simon’s algorithm finds s with O(n) quantum queries.

In what follows, we recall how Simon’s algorithm works. Assume that we have access to the quantum oracle $U_f$, which is defined as . For an n-qubit state , Hadamard transformation $H^{{}\otimes n}$ is defined as . Simon proposed a circuit ${\mathcal S}_f$ that computes a vector that is orthogonal to s for a periodic function f, which is defined as ${\mathcal S}_f=(H^{{}\otimes n}\otimes I_n) \cdot U_f \cdot (H^{{}\otimes n}\otimes I_n)$ and works as follows.

(1)

If f satisfies $f(x)=f(x')\Leftrightarrow x'=x\oplus s$, then Eq. (1) can be rearranged as

where V is a linear subspace of $\{0,1\}^n$ of dimension $(n-1)$ that partitions $\{0,1\}^n$ into cosets V and $V+s$. The vector y such that $y\cdot s\equiv 1\pmod {2}$ satisfies $(-1)^{x\cdot y}+(-1)^{(x\oplus s)\cdot y}=0$. Therefore, the vector y that we obtain by measuring the first n qubits of satisfies $y\cdot s\equiv 0\pmod {2}$. By repeating this measurement for O(n) times, we obtain $(n-1)$ linearly independent vectors that are all orthogonal to s with a high probability. Then we can recover s by solving the system of linear equations with $O(n^3)$ classical steps.

2.4 Quantum Distinguisher Based on Simon’s Algorithm

Next, we introduce a quantum distinguisher based on Simon’s algorithm. We follow the approach of Kaplan et al. [24] and Santoli and Schaffner [37], and the formalization by Ito et al. [22]. To recover s with Simon’s algorithm, the function f has to satisfy $f(x)=f(x')\Leftrightarrow x'=x\oplus s$. However, for distinguishers, the condition can be relaxed.

In more detail, suppose that we are given an oracle ${\mathcal O}:\{0,1\}^n\rightarrow \{0,1\}^n$, which is either an encryption algorithm $E_K\in \mathrm {Perm}(n)$ or a random permutation $\varPi \in \mathrm {Perm}(n)$, and our goal is to distinguish the two cases. We assume that the quantum oracles $U_{\mathcal O}$ and $U_{{\mathcal O}^{-1}}$ are given. The distinguisher in [22] can be applied to a function $f^{\mathcal O}:\{0,1\}^\ell \rightarrow \{0,1\}^m$, where there exists a non-zero period s when ${\mathcal O}=E_K$, i.e., $f^{\mathcal O}$ such that $f^{E_K}(x)=f^{E_K}(x\oplus s)$ holds for all x. We expect that, with a high probability, $f^\varPi$ does not have any period. The distinguisher works as follows:

• 1. Prepare an empty set ${\mathcal Y}$.

• 2. Measure the first $\ell$ qubits of and add the obtained vector y to ${\mathcal Y}$ for $\eta$ times.

• 3. Calculate the dimension d of the vector space spanned by ${\mathcal Y}$.

• 4. If $d=\ell$, then output ${\mathcal O}=\varPi$, otherwise output ${\mathcal O}=E_K$.

If $f^{\mathcal O}$ has the period s, the obtained vector y is orthogonal to s. Therefore the dimension d of the vector space spanned by ${\mathcal Y}$ is at most $\ell -1$. On the other hand, if $f^{\mathcal O}$ has no period, the dimension can reach $\ell$. Thus we can distinguish the two cases by checking the dimension.

This distinguisher fails only if ${\mathcal O}=\varPi$ and the dimension of the vector space spanned by ${\mathcal Y}$ is less than $\ell$. To analyze the success probability of the distinguisher, define a parameter $\epsilon _f^\pi$ as

$$\begin{aligned} \epsilon _f^{\pi } = \underset{t\in \{0,1\}^{\ell }\backslash \{0^\ell \}}{\max } \mathop {\Pr }\limits _x\left[ f^\pi (x)=f^\pi (x\oplus t)\right] \,, \end{aligned}$$

where $\pi \in \mathrm {Perm}(n)$ is a fixed permutation. This parameter shows how the dimension of y is biased when $\varPi =\pi$. If this parameter is large (i.e., there exists t that is close to a period), then with a high probability, the vector space spanned by ${\mathcal Y}$ is orthogonal to t. Thus, we take a small constant $0\le \delta <1$ arbitrarily, and we say that a permutation $\pi$ is irregular if $\epsilon _f^{\pi }>1-\delta$. In addition, define the set of the irregular permutations $\mathsf{irr}_f^\delta$ as

$$\begin{aligned} \textsf {irr}_{f}^{\delta } = \{\pi \in \text {perm}(n) \mid \epsilon _f^{\pi }> 1-\delta \}\,. \end{aligned}$$

The following theorem was proved in [22].

Theorem 1

([22]). Let $\ell$ and m be positive integers that are O(n). Assume that we have a quantum circuit with $O(poly(\ell ,m))$ qubits which computes $f^{\mathcal O}:\{0,1\}^\ell \rightarrow \{0,1\}^m$ by making O(1) queries to ${\mathcal O}$, and runs in time $T(\ell ,m)$. The distinguisher makes $O(\eta )$ quantum queries, and distinguishes $E_K$ from $\varPi$ with probability at least

$$\begin{aligned} 1-\frac{2^\ell }{e^{\delta \eta /2}}-\mathop {\Pr }\limits _\varPi [\varPi \in \mathsf{irr}_f^\delta ]\,. \end{aligned}$$

This shows that the distinguisher succeeds if $\Pr _\varPi [\varPi \in \mathsf{irr}_f^\delta ]$ is a small value.

2.5 Hosoyamada and Sasaki’s Method to Truncate Outputs of Quantum Oracles

At ISIT 2010, Kuwakado and Morii [28] introduced a quantum distinguishing attack on 3-round Feistel scheme by using Simon’s algorithm. As shown in Fig. 2, let $\alpha _0$ and $\alpha _1$ be arbitrary constants, and define f as:

$$\begin{aligned} f:\{0,1\}\times \{0,1\}^n&\rightarrow \{0,1\}^n\\ (b,x)&\mapsto \alpha _b\oplus x_{1}^{3}\,,\\ \text {where}~~(x_0^3,x_1^3)&=E(\alpha _b,x)\,. \end{aligned}$$

E is the 3-round Feistel scheme and f can be written as $f(b,x)=R_2(R_1(\alpha _b)\oplus x))$. It is easy to see that f is a periodic function that satisfies $f(b,x)=f(b\oplus 1, x\oplus R_1(\alpha _0)\oplus R_1(\alpha _1))$ for any (b, x). Then by using Simon’s algorithm, one obtains the period $s=1\Vert R_1(\alpha _0)\oplus R_1(\alpha _1)$ in polynomial time.

Fig. 2.

3-round Feistel cipher

In the above distinguisher, one has to truncate the 2n-bit output of E to obtain the right half n bits, namely $x_1^3$. However, Kaplan et al. [24] and Hosoyamada et al. [19] pointed out that in quantum setting, it is non-trivial to truncate the entangled 2n qubits to n qubits, since the usual truncation destroys entanglements.

At SCN 2018, Hosoyamada and Sasaki [19] introduced a method to simulate truncation of outputs of quantum oracles without destroying quantum entanglements. Here, we review their method. Let $\mathcal {O}:|x\rangle |y\rangle |z\rangle |w\rangle \mapsto |x\rangle |y\rangle |z\oplus \mathcal {O}_L(x,y)\rangle |w\oplus \mathcal {O}_R(x,y)\rangle$ be the encryption oracle $E_K$, where $\mathcal {O}_L$, $\mathcal {O}_R$ denote the left and right n bits of the complete encryption, respectively. The goal is to simulate the oracle $\mathcal {O}_R:|x\rangle |y\rangle |w\rangle \mapsto |x\rangle |y\rangle |w\oplus \mathcal {O}_R(x,y)\rangle$. Hosoyamada and Sasaki first try to simulate a tweaked $\mathcal {O}_R$, i.e., $\mathcal {O}'_R:|x\rangle |y\rangle |w\rangle |0^{n}\rangle \mapsto |x\rangle |y\rangle |w\oplus \mathcal {O}_R(x,y)\rangle |0^{n}\rangle$ with ancilla qubits. Let $|+\rangle :=H^{\otimes n}|0^{n}\rangle =\frac{1}{\sqrt{2^{n}}}\sum _z|z\rangle$, where $H^{\otimes n}$ is an n-qubit Hadamard gate. Thus,

$$\begin{aligned} \mathcal {O}|x\rangle |y\rangle |+\rangle |w\rangle&= \mathcal {O}(|x\rangle |y\rangle [\frac{1}{\sqrt{2^{n}}}\sum _z|z\rangle ]|w\rangle )\nonumber \\&= |x\rangle |y\rangle [\frac{1}{\sqrt{2^{n}}}\sum _z|z\oplus \mathcal {O}_L(x,y)\rangle ]|w\oplus \mathcal {O}_R(x,y)\rangle \,. \end{aligned}$$

(2)

Let $z'=z\oplus \mathcal {O}_L(x,y)$. Then Eq. (2) becomes

$$\begin{aligned} |x\rangle |y\rangle [\frac{1}{\sqrt{2^{n}}}\sum _z|z'\rangle ]|w\oplus \mathcal {O}_R(x,y)\rangle&= |x\rangle |y\rangle [\frac{1}{\sqrt{2^{n}}}\sum _{z'}|z'\rangle ]|w\oplus \mathcal {O}_R(x,y)\rangle \\&=|x\rangle |y\rangle |+\rangle |w\oplus \mathcal {O}_R(x,y)\rangle \,. \end{aligned}$$

So $\mathcal {O}|x\rangle |y\rangle |+\rangle |w\rangle =|x\rangle |y\rangle |+\rangle |w\oplus \mathcal {O}_R(x,y)\rangle$. Hosoyamada and Sasaki define $\mathcal {O}'_R:=(I\otimes H^{\otimes n})\circ \texttt {Swap}\circ \mathcal {O} \circ \texttt {Swap}\circ (I\otimes H^{\otimes n})$, where $\texttt {Swap}$ is an operator that swaps the last 2n bits: $|x\rangle |y\rangle |z\rangle |w\rangle \mapsto |x\rangle |y\rangle |w\rangle |z\rangle$. So we have

$$\begin{aligned} \mathcal {O}'_R |x\rangle |y\rangle |w\rangle |0^{n}\rangle&= (I\otimes H^{\otimes n})\circ \texttt {Swap}\circ \mathcal {O} \circ \texttt {Swap}\circ (I\otimes H^{\otimes n})|x\rangle |y\rangle |w\rangle |0^{n}\rangle \\&=(I\otimes H^{\otimes n})\circ \texttt {Swap}\circ \mathcal {O}|x\rangle |y\rangle |+\rangle |w\rangle \\&= (I\otimes H^{\otimes n})\circ \texttt {Swap}|x\rangle |y\rangle |+\rangle |w\oplus \mathcal {O}_R(x,y)\rangle \\&=(I\otimes H^{\otimes n})|x\rangle |y\rangle |w\oplus \mathcal {O}_R(x,y)\rangle |+\rangle \\&=|x\rangle |y\rangle |w\oplus \mathcal {O}_R(x,y)\rangle |0^n\rangle \,. \end{aligned}$$

Hence, $\mathcal {O}_R$ could be simulated given the complete encryption oracle $\mathcal {O}$ using ancilla qubits. Intuitively, Hosoyamada and Sasaki first randomize the left part by using the Hadamard transformation, and then force it to become $|0^n\rangle$ by applying the Hadamard transformation again.

2.6 Combining Grover Search and Distinguishers

Leander and May combined Grover search and Simon’s algorithm to show a key recovery attack against the FX construction [30]. Hosoyamada and Sasaki [19], and Dong and Wang [11] showed key recovery attacks against Feistel schemes by using this combining technique.

Grover Search. Grover search provides a quadratic speed up on unsorted-database search [13]. Let N be the number of elements in the database, and assume that there exists only one target element. In the classical setting, we can find the target element in time O(N). However, in the quantum setting, Grover’s algorithm can find it in time $O(\sqrt{N})$.

This algorithm was generalized later as quantum amplitude amplification by Brassard et al. [7] as in the following theorem.

Theorem 2

([7]). Let ${\mathcal A}$ be any quantum algorithm on q qubits that uses no measurement. Let ${\mathcal B}:\{0,1\}^q\rightarrow \{0,1\}$ be a function that classifies outcomes of ${\mathcal A}$ as good or bad. Let $p>0$ be the initial success probability that a measurement of is good. Set $m=\lfloor \pi / 4\theta _p \rfloor$, where $\theta _p$ is defined so that $\sin ^2(\theta _p)=p$ and $0<\theta _p\le \pi /2$. Moreover, define the unitary operator $Q=-{\mathcal A}S_0{\mathcal A}^{-1}S_{\mathcal B}$, where the operator $S_{\mathcal B}$ conditionally changes the sign of the amplitudes of the good states,

while the operate $S_0$ changes the sign of the amplitude if and only if the state is the zero state . Then, after the computation of , a measurement is good with probability at least $\max \{1-p,p\}$.

Fig. 3.

The FX construction

Key Recovery Attack Against the FX Construction. The FX construction by Killian and Rogaway is a way to extend the key length of a block cipher [25, 26]. Let E be an n-bit block cipher that takes an m-bit key $k_0$ as input. The FX construction under two additional n-bit keys $k_1,k_2$ is described as

$$\begin{aligned} \mathrm {Enc}(x)=E_{k_0}(x\oplus k_1)\oplus k_2\,. \end{aligned}$$

Figure 3 shows the FX construction.

Leander and May constructed a function f(k, x) that is defined as

$$\begin{aligned} f(k,x)=\mathrm {Enc}(x)\oplus E_k(x)=E_{k_0}(x\oplus k_1)\oplus k_2\oplus E_k(x)\,. \end{aligned}$$

If $k=k_0$, f(k, x) satisfies $f(k,x)=f(k,x\oplus k_1)$ for all $x\in \{0,1\}^n$. That is, the function $f(k_0,\cdot )$ has a period $k_1$. However, if $k\ne k_0$, with a high probability, the function $f(k,\cdot )$ does not have any period. Then they apply Grover search over $k\in \{0,1\}^m$. They construct the classifier ${\mathcal B}$ that identifies the states as good if $k=k_0$ by using Simon’s algorithm to $f(k,\cdot )$. The time complexity of Grover search is $O(2^{m/2})$ and Simon’s algorithm runs in time O(n) in the classifier ${\mathcal B}$. Thus this attack runs in time $O(2^{m/2})$. For more details, see [30].

3 Previous Attacks

Fig. 4.

$(2d-1)$-round distinguishing attack

Fig. 5.

$(d^2-d+2)$-round key recovery attack for $d=4$

In this section, we review the quantum attacks against Type-1 GFSs by Dong et al. [10]. They showed a $(2d-1)$-round distinguishing attack and a $(d^2-d+2)$-round key recovery attack.

We first review the distinguishing attack. Let $\alpha _0, \alpha _1\in \{0,1\}^n$ be two arbitrary distinct n-bit constants, and $x_1^0, x_2^0, \dots , x_{d-2}^0\in \{0,1\}^n$ be arbitrary n-bit constants. Given the oracle ${\mathcal O}$, they define a function $f^{\mathcal O}$ as

$$\begin{aligned} f^{\mathcal O}:\{0,1\}\times \{0,1\}^{n}&\rightarrow \{0,1\}^{n}\nonumber \\ (b, x)&{} \mapsto \alpha _b \oplus y_1\,,\nonumber \\ \mathrm {where}~(y_0, y_1,\dots , y_{d-1})&{}={\mathcal O}(\alpha _b, x_1^0,x_2^0,\dots , x_{d-2}^0, x)\,. \end{aligned}$$

(3)

Let the intermediate state value after the first i rounds be $(x_0^i, x_1^i,\dots , x_{d-1}^i)$. If ${\mathcal O}$ is $\varPhi _{2d-1}$, then the function $f^{\mathcal O}$ is described as

$$\begin{aligned} f(b,x)&{}=\alpha _b\oplus x_1^{2d-1} \nonumber \\&{}=\alpha _b\oplus x_0^{d} \nonumber \\&{}=\alpha _b\oplus R_d(x_0^{d-1})\oplus \alpha _b \nonumber \\&{}=R_d(R_{d-1}(R_{d-2}(\cdots R_2(R_1(\alpha _b)\oplus x_1^0)\oplus x_2^0 \cdots )\oplus x_{d-2}^0)\oplus x)\,, \end{aligned}$$

(4)

where in the second equality, we use the fact that $x_0^{i}=x_{d-1}^{i+1}=x_{d-2}^{i+2}=\dots = x_1^{i+d-1}$ (See Fig. 4). Let $h(\cdot )=R_{d-1}(R_{d-2}(\cdots R_2(R_1(\cdot )\oplus x_1^0)\oplus x_2^0 \cdots )\oplus x_{d-2}^0)$. We see that $h(\cdot )$ is a function that is independent of the input (b, x), since $x_1^0,x_2^0,\dots , x_{d-2}^0$ are constants. By using $h(\cdot )$, we can describe Eq. (4) as $f^{\mathcal O}=R_d(h(\alpha _b)\oplus x)$, and $f^{\mathcal O}$ satisfies

$$\begin{aligned} f(b,x)&{}=R_d(h(\alpha _b)\oplus x)\\&{}=R_d(h(\alpha _{b\oplus 1})\oplus h(\alpha _0)\oplus h(\alpha _1)\oplus x)\\&{}=f(b\oplus 1,x\oplus h(\alpha _0)\oplus h(\alpha _1))\,. \end{aligned}$$

This implies that the function $f^{\mathcal O}$ has the period $(1,h(\alpha _0)\oplus h(\alpha _1))$.

If ${\mathcal O}$ is $\varPi$, then with a high probability, $f^{\mathcal O}$ does not have any period. Therefore, $\Pr _\varPi [\varPi \in \mathsf{irr}_f^\delta ]$ is a small value and we can distinguish the two cases.

We next review the key recovery attack. We recover the key of the $(d^2-d+2)$-round Type-1 GFS by appending $(d^2-3d+3)$ rounds after the $(2d-1)$-round distinguisher (See Fig. 5). For each $x^i_1$, where $d\ge 3$, we have $x^i_1=R_{i+1}(x^{i+1}_d,k_{i+1})\oplus x^{i+1}_0$. This implies that when we need the value of $x^i_1$, we have to recover $k_{i+1}$. From the property of Feistel cipher, we have $x^i_j=x^{i+1}_{j-1}=\cdots =x^{i+j-1}_1$ for $3\le j \le d$, and $x^i_0=x^{i+d-1}_1$. For d branches, it holds that $x^{2d-1}_1=R_{2d}(x^{2d}_{d-1},k_{2d})\oplus x^{2d}_0$, and thus we need to recover one sub-key $k_{2d}$, and since $x^{2d}_0=x^{3d-1}_1$ and $x^{2d}_{d-1}=x^{3d-2}_1$ hold, we need two sub-keys $k_{3d-1}$ and $k_{3d}$. By parity of this reasoning, the subkey length that we need to recover becomes $[1+2+3+\cdots +(d-2)]k+k=(\frac{d^2}{2}-\frac{3d}{2}+2)k$ bits. Thus, the time complexity of the exhaustive search for $(d^2-d+2)$ rounds by Grover search is $O(2^{(\frac{d^2}{2}-\frac{3d}{2}+2)\cdot \frac{k}{2}})$. The distinguisher runs in time O(n) and the time complexity of this attack is $O(2^{(\frac{d^2}{2}-\frac{3d}{2}+2)\cdot \frac{k}{2}})$.

This attack is better than the direct application of Grover search to the entire $(d^2-d+2)k$-bit subkey. If we recover the subkey of r rounds for $r>d^2-d+2$, the time complexity is $O(2^{(\frac{d^2}{2}-\frac{3d}{2}+2)\cdot \frac{k}{2}+\frac{(r-d^2+d-2)k}{2}})$, since the subkey length that we need to recover becomes $(\frac{d^2}{2}-\frac{3d}{2}+2)k+(r-d^2+d-2)k$ bits in total.

4 $(3d-3)$-Round Distinguishing Attack in qCPA Setting

Fig. 6.

$(3d-3)$-round distinguishing attack

In this section, we present our distinguishing attacks against $(3d-3)$-round Type-1 GFSs. We improve the number of rounds that we can distinguish from $(2d-1)$ rounds to $(3d-3)$ rounds by shifting the position of $\alpha _b$ in the plaintext.

As before, we first fix two arbitrary distinct constants $\alpha _0, \alpha _1\in \{0,1\}^n$ and fix arbitrary constants $x_0^0, x_1^0, \dots ,x_{d-3}^0\in \{0,1\}^n$. Given the oracle ${\mathcal O}$, we define a function $f^{\mathcal O}$ as

$$\begin{aligned} f^{\mathcal O}:\{0,1\}\times \{0,1\}^{n}&\rightarrow \{0,1\}^{n}\\ (b, x)&{} \mapsto \alpha _b \oplus y_1\,,\\ \mathrm {where}~(y_0, y_1,\dots , y_{d-1})&{}={\mathcal O}(x_0^0,x_1^0,\dots , x_{d-3}^0, \alpha _b, x)\,. \end{aligned}$$

Observe that the difference from Eq. (3) is the position of $\alpha _b$.

If ${\mathcal O}$ is $\varPhi _{3d-3}$, let $(x_0^i, x_1^i,\dots , x_{d-1}^i)$ be the intermediate state value after the first i rounds. Now $f^{\mathcal O}$ is described as:

$$\begin{aligned} f^{\mathcal O}(b,x)&{}=\alpha _b\oplus y_1 \nonumber \\&{}=\alpha _b\oplus x_1^{3d-3} \nonumber \\&{}=\alpha _b\oplus x_0^{2d-2}\,, \end{aligned}$$

(5)

since $x_0^{i}=x_{d-1}^{i+1}=x_{d-2}^{i+2}=\dots = x_1^{i+d-1}$ (See Fig. 6).

Our main observation is the following lemma.

Lemma 1

If ${\mathcal O}$ is $\varPhi _{3d-3}$, then for any $b\in \{0,1\}$ and $x\in \{0,1\}^n$, the function $f^{\mathcal O}$ satisfies

$$\begin{aligned} f^{\mathcal O}(b,x)=f^{\mathcal O}(b\oplus 1, x \oplus R_{d-1}(C\oplus \alpha _0)\oplus R_{d-1}(C\oplus \alpha _1))\,, \end{aligned}$$

where $C=R_{d-2}(R_{d-3}(\cdots R_1(x_0^0)\oplus x_1^0 \cdots )\oplus x_{d-3}^0)$. That is, $f^{\mathcal O}$ has the period $s=(1, R_{d-1}(C\oplus \alpha _0)\oplus R_{d-1}(C\oplus \alpha _1))$.

Proof

We first consider the intermediate state value after the first $(d-2)$ rounds in which $\alpha _b$ reaches the leftmost position (See Fig. 6). The value is described as

$$\begin{aligned} (x_0^{d-2}, x_1^{d-2}, \dots , x_{d-1}^{d-2})&{}=\varPhi _{d-2}(x_0^0,x_1^0,\dots , x_{d-3}^0, \alpha _b, x)\\&{}=(R_{d-2}(x_0^{d-3})\oplus \alpha _b, x, x_0^0, x_0^1, \dots , x_0^{d-3})\,. \end{aligned}$$

For $1\le i \le d-3$, $x_0^i$ is described as

$$\begin{aligned} x_0^i=R_{i}(R_{i-1}(\cdots R_1(x_0^0)\oplus x_1^0 \cdots )\oplus x_{i-1}^0)\oplus x_{i}^0\,. \end{aligned}$$

We see that $x_0^i$ is a constant that is independent of the input (b, x), since $x_0^0, x_1^0, \dots , x_{d-3}^0$ are constants. Let $C=R_{d-2}(x_0^{d-3})$, which is independent of (b, x) and hence can be treated as a constant. The output after one more round, which is the output after the first $(d-1)$ rounds, is described as

$$\begin{aligned} (x_0^{d-1}, x_1^{d-1}, \dots , x_{d-1}^{d-1})&{}=(R_{d-1}(C\oplus \alpha _b)\oplus x, x_0^0, x_0^1, \dots , x_0^{d-3},C\oplus \alpha _b)\,. \end{aligned}$$

Now we consider the value of $x_0^{2d-2}$. This is the intermediate state value after the first $(2d-2)$ rounds in which $\alpha _b\oplus C$ reaches the leftmost position again, and is described as

$$\begin{aligned} x_0^{2d-2}&{}=R'(R_{d-1}(C\oplus \alpha _b)\oplus x)\oplus \alpha _b \oplus C\,, \end{aligned}$$

(6)

where $R'(\cdot )=R_{2d-2}(R_{2d-3}(\cdots R_{d+1}(R_{d}(\cdot )\oplus x_0^0)\oplus x_0^1 \cdots )\oplus x_0^{d-3})$ (See Fig. 6). $R'(\cdot )$ is a function that is independent of the input (b, x), since $x_0^0,x_0^1,\dots , x_0^{d-3}$ are constants. From Eqs. (5) and (6), the function $f^{\mathcal O}$ is described as

$$\begin{aligned} f^{\mathcal O}(b,x)&{}=\alpha _b \oplus R'(R_{d-1}(C\oplus \alpha _b)\oplus x)\oplus \alpha _b \oplus C \\&{}=R'(R_{d-1}(C\oplus \alpha _b)\oplus x) \oplus C\,. \end{aligned}$$

The function $f^{\mathcal O}$ has the claimed period since it satisfies

$$\begin{aligned}&{}f^{\mathcal O}(b\oplus 1,x\oplus R_{d-1}(C\oplus \alpha _0)\oplus R_{d-1}(C\oplus \alpha _1))\\&{}=R'(R_{d-1}(C\oplus \alpha _{b\oplus 1})\oplus R_{d-1}(C\oplus \alpha _0)\oplus R_{d-1}(C\oplus \alpha _1) \oplus x)\oplus C\\&{}=R'(R_{d-1}(C\oplus \alpha _b)\oplus x) \oplus C \\&{}=f^{\mathcal O}(b,x)\,, \end{aligned}$$

and hence the lemma follows.    $\square$

Therefore, we can distinguish the $(3d-3)$-round Type-1 GFS by using the function $f^{\mathcal O}$. The success probability of the distinguishing attack with measuring $(4n+4)$ times is at least $1-(2/e)^{n+1}-\Pr [\varPi \in \mathsf{irr}_f^{1/2}]$, where we use $\delta =1/2$ and $\eta =4n+4$. Note that $\Pr [\varPi \in \mathsf{irr}_f^{1/2}]$ is a small value, since with a high probability, the function $f^{\mathcal O}$ does not have any period when ${\mathcal O}$ is $\varPi$, since $\varPi$ is a random permutation.²

5 $(d^2-d+1)$-Round Distinguishing Attack in qCCA Setting

Fig. 7.

$(d^2-d+1)$-round distinguishing attack

If we can use the decryption oracle in the quantum setting, we can construct a distinguishing attack against the $(d^2-d+1)$-round Type-1 GFS. We write the i-th round function in decryption as $R_i$. Note that this is different from the notation in Sect. 4.

We fix two distinct constants $\alpha _0, \alpha _1$ and $(d-2)$ constants $x_1^0, x_2^0, \dots , x_{d-2}^0$, which are all n bits. Given the decryption oracle ${\mathcal O}^{-1}$, we define $f^{{\mathcal O}^{-1}}$ as

$$\begin{aligned} f^{{\mathcal O}^{-1}}:\{0,1\}\times \{0,1\}^{n}&\rightarrow \{0,1\}^{n}\\ (b, x)&{} \mapsto \alpha _b \oplus y_0\,,\\ \mathrm {where}~(y_0, y_1,\dots , y_{d-1})&{}={\mathcal O}^{-1}(x, x_1^0,x_2^0,\dots , x_{d-2}^0, \alpha _b)\,. \end{aligned}$$

Consider the case ${\mathcal O}^{-1}=\varPhi ^{-1}_{d^2-d+1}$, and let the intermediate state value after the first i rounds be $(x_0^i, x_1^i,\dots , x_{d-1}^i)$. $f^{{\mathcal O}^{-1}}$ is described as:

$$\begin{aligned} f^{{\mathcal O}^{-1}}(b,x)&{}=\alpha _b\oplus y_0 \nonumber \\&{}=\alpha _b\oplus x_0^{d^2-d+1} \nonumber \\&{}=\alpha _b\oplus x_1^{d^2-2d+2}\,, \end{aligned}$$

(7)

since $x_1^{i}=x_{2}^{i+1}=x_{3}^{i+2}=\dots = x_0^{i+d-1}$ (See Fig. 7).

The following lemma holds.

Lemma 2

If ${\mathcal O}^{-1}$ is $\varPhi ^{-1}_{d^2-d+1}$, then for any $b\in \{0,1\}$ and $x\in \{0,1\}^n$, the function $f^{{\mathcal O}^{-1}}$ satisfies

$$\begin{aligned} f^{{\mathcal O}^{-1}}(b,x)=f^{{\mathcal O}^{-1}}(b\oplus 1, x \oplus R_{1}(\alpha _0)\oplus R_{1}(\alpha _1))\,. \end{aligned}$$

That is, $f^{{\mathcal O}^{-1}}$ has the period $s=(1, R_{1}(\alpha _0)\oplus R_{1}(\alpha _1))$.

Proof

In the first round, $R_1(\alpha _b)$ is xored into x. In the d-th round, the value $R_1(\alpha _b)\oplus x$ is used as the input of $R_d$, and the output of $R_d$ is xored into $x_1^0$. This implies that $x_1^d$ is

$$\begin{aligned} x_1^d=R_d(R_1(\alpha _b)\oplus x)\oplus x_1^0\,. \end{aligned}$$

(8)

See Fig. 7. The function $R(\cdot )=R_d(\cdot )\oplus x_1^0$ is independent of the input (b, x), since $x_1^0$ is a constant. Therefore, Eq. (8) can be described as

$$\begin{aligned} x_1^d=R(R_1(\alpha _b)\oplus x) \end{aligned}$$

with some function $R\in \mathrm {Func}(n)$. After additional $(d-1)$ rounds, this value is used as the input of $R_{2d-1}$, and the output of $R_{2d-1}$ is xored into the sub-block which was $x_2^0$ at the input. The sub-block which was $x_2^0$ at the input is a constant because it is not xored by the value that includes b nor x (Specifically, it depends only on $x_1^0$). Therefore, for some function $R'\in \mathrm {Func}(n)$, the value of $x_1^{2d-1}$ is described as

$$\begin{aligned} x_1^{2d-1}=R'(R_1(\alpha _b)\oplus x)\,. \end{aligned}$$

After that, for each $(d-1)$ rounds, this value is used as the input to the round function and the output is xored into the sub-block which was $x_i^0$ at the input, for $i=3,4,\ldots ,d-2$. We see that the sub-block itself depends on $x_1^0,\ldots ,x_{i-1}^0$, but it is a constant that is independent of the input (b, x) since a value related to (b, x) is not xored into the sub-block. Therefore, the value of $x_1^{2d-1+(d-1)\times (d-4)}=x_1^{d^2-3d+3}$ is described as

$$\begin{aligned} x_1^{d^2-3d+3}=R''(R_1(\alpha _b)\oplus x) \end{aligned}$$

for some function $R''\in \mathrm {Func}(n)$.

In the $(d^2-2d+2)$-th round, $R_{d^2-2d+2}(R''(R_1(\alpha _b)\oplus x))$ is xored into the sub-block which was $\alpha _b$ at the input. Since only the value that does not include b nor x is xored into the sub-block which was $\alpha _b$, with some function $R'''\in \mathrm {Func}(n)$, the value of $x_1^{d^2-2d+2}$ is described as

$$\begin{aligned} x_1^{d^2-2d+2}=R'''(R_1(\alpha _b)\oplus x)\oplus \alpha _b\,. \end{aligned}$$

(9)

From Eqs. (7) and (9), the function $f^{{\mathcal O}^{-1}}$ can be written as

$$\begin{aligned} f^{{\mathcal O}^{-1}}(b,x)&{}=\alpha _b \oplus R'''(R_1(\alpha _b)\oplus x)\oplus \alpha _b \\&{}=R'''(R_1(\alpha _b)\oplus x)\,. \end{aligned}$$

The function $f^{\mathcal O}$ satisfies

$$\begin{aligned} f^{{\mathcal O}^{-1}}(b\oplus 1,x\oplus R_{1}(\alpha _0)\oplus R_{1}(\alpha _1))&{}=R'''(R_1(\alpha _{b\oplus 1})\oplus x \oplus R_{1}(\alpha _0)\oplus R_{1}(\alpha _1))\\&{}=R'''(R_{1}(\alpha _b)\oplus x)\\&{}=f^{{\mathcal O}^{-1}}(b,x)\,, \end{aligned}$$

and hence we have the lemma.    $\square$

The success probability of the distinguishing attack using the function $f^{{\mathcal O}^{-1}}$ with measuring $(4n+4)$ times is at least $1-(2/e)^{n+1}-\Pr [\varPi \in \mathsf{irr}_f^{1/2}]$, where we use $\delta =1/2$ and $\eta =4n+4$. We see that $\Pr [\varPi \in \mathsf{irr}_f^{1/2}]$ is a small value, and hence the attack succeeds with a high probability.

6 Key Recovery Attacks on Type-1 GFSs

Similarly to the previous key recovery attacks by Dong et al. [10] that combine Grover search and the distinguisher, we can construct key recovery attacks against Type-1 GFSs based on our distinguishers.

With the $(3d-3)$-round distinguisher in qCPA setting, we can recover the key of the $d^2$-round Type-1 generalized Feistel cipher in time $O(2^{(\frac{d^2}{2}-\frac{3d}{2}+2)\cdot \frac{k}{2}})$ by replacing the $(2d-1)$-round distinguisher in Dong et al.’s attack with our $(3d-3)$-round distinguisher. In general, the key recovery attack against the r-round version, where $r\ge d^2$, runs in time $O(2^{(\frac{d^2}{2}-\frac{3d}{2}+2)\cdot \frac{k}{2}+\frac{(r-d^2)k}{2}})$.

With the $(d^2-d+1)$-round distinguisher in qCCA setting, by using the decryption oracle, we can recover the key of the r-round Type-1 GFS for $r> d^2-d+1$ in time $O(2^{\frac{(r-(d^2-d+1))k}{2}})$, because the subkey length that we need to recover is $(r-d^2+d-1)k$ bits.

If $d=3$, the time complexity of these two key recovery attacks is the same because $(\frac{d^2}{2}-\frac{3d}{2}+2)\cdot \frac{k}{2}+\frac{(r-d^2)k}{2} - \frac{(r-(d^2-d+1))k}{2}=\frac{k(d-2)(d-3)}{4}$. If $d>3$, the key recovery attack with the $(d^2-d+1)$-round distinguisher is better than the one with the $(3d-3)$-round distinguisher.

Fig. 8.

14-round distinguishing attack on CAST-256

7 Quantum Attacks on Round-Reduced CAST-256 Block Cipher in qCPA Setting

CAST-256 block cipher [1] is a first-round AES candidate. It has 48 rounds, including 24 rounds Type-1 GFS and 24 rounds inverse Type-1 GFS. The block size is 128 bits, which are divided into four 32-bit branches and the key size can be 128, 192 or 256 bits. Each round function absorbs 37-bit subkey. Our attack is quite general and does not need any other details of the cipher.

In this section, we introduce a new 14-round quantum distinguisher in qCPA on CAST-256 shown in Fig. 8. The distinguisher, started from the 24th round, is composed of 1-round Type-1 GFS and 13-round inverse Type-1 GFS. It is derived based on the result presented in Sect. 5. When $d=4$, $(d^2-d+1) = 13$ round distinguisher is obtained (from round $R_{25}$ to $R_{37}$ of CAST-256). Thanks to the special structure of CAST-256, we could add one more round $R_{24}$ to the 13-round distinguisher for free. Hence, the 14-round distinguisher is derived.

We also fix two distinct constants $\alpha _0, \alpha _1$ and 2 constants $x_2^{23}, x_3^{23}$, which are all n bits. Given the 14-round CAST-256 encryption oracle ${\mathcal O}$, we define $f^{{\mathcal O}}$ as

$$\begin{aligned} f^{{\mathcal O}}:\{0,1\}\times \{0,1\}^{n}&\rightarrow \{0,1\}^{n}\\ (b, x)&{} \mapsto \alpha _b \oplus y_0\,,\\ \mathrm {where}~(y_0, y_1,y_2, y_{3})&{}={\mathcal O}(\alpha _b, x,x_2^{23},x_{3}^{23})\,. \end{aligned}$$

According to Lemma 2, $f^{\mathcal O}$ has the period $s=(1,R_{24}(\alpha _0)\oplus R_{25}(\alpha _0)\oplus R_{24}(\alpha _1)\oplus R_{25}(\alpha _1))$. As is shown in Sect. 6, we could add or append several rounds to attack $r>14$ rounds CAST-256 in time ${\mathcal O}(2^{\frac{37(r-14)}{2}})$, because the subkey length that we need to recover is $37(r-14)$ bits. Thus we could attack 20-round CAST-256 with 256-bit key in time $2^{111}$, which is faster than Grover’s algorithm by a factor of $2^{128-111}=2^{17}$.

8 Conclusions

In this paper, we give some improved polynomial-time quantum distinguishers on Type-1 GFS in qCPA and qCCA settings. First, we give new qCPA quantum distinguishers on $(3d-3)$-round Type-1 GFS with branches $d\ge 3$, which gain $(d-2)$ more rounds than the previous distinguishers. Hence, we could get better key-recovery attacks, whose time complexities gain a factor of $2^{\frac{(d-2)n}{2}}$. We also obtain $(d^2-d+1)$-round qCCA quantum distinguishers on Type-1 GFS, which gain many more rounds than the previous distinguishers. In addition, we also discuss the quantum attack on CAST-256 block cipher.

As an open question, the tight bound of the number of rounds that we can distinguish is not known. There is a possibility that we can distinguish more than $(3d - 3)$ rounds in qCPA setting, and we may distinguish more than $(d^2 - d + 1)$ rounds in qCCA setting. Moreover, we may distinguish more than 14 rounds of CAST-256 when considering its special structure, which applies both Type-1 GFS and its inverse as the round functions. We anticipate the analysis with respect to the provable security approach in [18] can settle the problem, while this is beyond the scope of this paper. We also note that we do not know the impact of combining qCPA and qCCA as applied against 4-round Feistel block ciphers in [22].

Another open question is that, we could apply $(d^2-d+1)$-round qCCA quantum distinguishers to other block ciphers. Note that when the branch number is large, the distinguisher becomes very long.