Generic Key Recovery Attack on Feistel Scheme
Takanori Isobe and Kyoji ShibutaniSony Corporation
1-7-1 Konan, Minato-ku, Tokyo 108-0075, Japan{Takanori.Isobe,Kyoji.Shibutani}@jp.sony.com

Abstract. We propose new generic key recovery attacks on Feistel-type
block ciphers. The proposed attack is based on the all subkeys recovery
approach presented in SAC 2012, which determines all subkeys insteadof the master key. This enables us to construct a key recovery attack
without taking into account a key scheduling function. With our advanced techniques, we apply several key recovery attacks to Feistel-type
block ciphers. For instance, we show 8-, 9- and 11-round key recovery
attacks on n-bit Feistel ciphers with 2n-bit key employing random keyed
F-functions, random F-functions, and SP-type F-functions, respectively.
Moreover, thanks to the meet-in-the-middle approach, our attack leads
to low-data complexity. To demonstrate the usefulness of our approach,
we show a key recovery attack on the 8-round reduced CAST-128, whichis the best attack with respect to the number of attacked rounds. Since
our approach derives the lower bounds on the numbers of rounds to be
secure under the single secret key setting, it can be considered that we
unveil the limitation of designing an efficient block cipher by a Feistel
scheme such as a low-latency cipher.
Keywords: block cipher, key scheduling function, all-subkeys-recovery
attack, meet-in-the-middle attack, key recovery attack, low-data complexity attack

1

Introduction

A block cipher is considered as an essential technology on modern cryptography,
since it is one of the most widely used primitives. Moreover, studies on designinga secure and efficient block cipher are useful also for designing other symmetricprimitives such as hash functions and stream ciphers. Since DES was developedin 1977 [19], a lot of progress has taken place in this area. Recently, with the large
deployment of network devices requiring security, block ciphers satisfying new
demands such as lightweight and low-latency have received a lot of attention. In
fact, several block ciphers designed for a lightweight hardware implementation
have been proposed such as PRESENT [9], KATAN/KTANTAN [16], LED [20]and Piccolo [34]. The concept of a low-latency encryption, which is used for an
application requiring an instant response, was discussed in [24]. Since a lowlatency encryption requires a quick response, the number of rounds must be
reduced as much as possible compared to a general-purpose block cipher such

as AES. In 2012, PRINCE was proposed as an instantiation of a low-latency
cipher [12]. Note that PRINCE is not only a low-latency cipher, but also alightweight block cipher even after supporting both encryption and decryption.
Those features are considered to be important in practical use of the cipher,since its lightweightness directly leads to low power and energy consumption
and supporting decryption function without much cost leading to this cipher
being used more widely.
In general, an SPN cipher requires an inverse function when supporting decryption, and thus an SPN cipher with a decryption function needs additional
gate areas. In spite of the fact that PRINCE is an SPN cipher, it is efficiently
implemented even when implementing a decryption function due to its novel
property called α-reflection. However, as pointed out by the designers, it has
been known that α-reflection reduces the security of the cipher [12, 23, 35] andthus the cipher having α-reflection does not have optimal security. Meanwhile,it has been known that a Feistel cipher, another traditional structure of blockcipher, is suitable for a lightweight block cipher especially when supporting both
encryption and decryption, since it does not require an inverse function. Thus,a Feistel cipher is considered as a possible candidate of a low-latency cipher, if
it has sufficiently small number of rounds. However, it has been still unknown
how many rounds are sufficient for a Feistel cipher to be secure. Note that, forlow-latency encryption, since the key scheduling function can be precomputed,
it can be a heavy function. Thus, its performance with respect to low-latency is
considered to mainly depend on the data processing part, namely its number ofrounds. Hence, our question is “how many rounds can be reduced without lossof security requirements for Feistel schemes”.
In this paper, we tackle the security evaluations of several Feistel schemes,
assuming that the key scheduling function is an ideal function. We deal withkey recovery attacks under the single secret key setting by extending the all
subkeys recovery approach [22]. Since our approach derives the lower bounds
on the numbers of rounds to be secure against a key recovery attack even if theunderlying key scheduling function is an ideal function, our results show the limitation of designing a low-latency encryption by a Feistel scheme. We introduce
several advanced techniques including function reduction and key linearization.
Using those advanced techniques and with the help of the meet-in-the-middle
approach [10, 21], we show several key recovery attacks on various Feistel ciphers.
Table 1 summarizes the number of attacked rounds for Feistel schemes by both
distinguishers and key recovery attacks under the single secret key and knownkey settings. Compared to the previous results, some of our attacks are the first
generic key recovery attacks and also the best for several Feistel schemes withrespect to the number of attacked rounds, even if the attacker is allowed to use
the known secret key. Moreover, our attack does not restrict the underlying Ffunction to a permutation, which is a limitation of some of the previous attacks.
Furthermore, one of the advantages of our approach is its low data requirement
thanks to the meet-in-the-middle approach, in contrast to the classical statistical
attacks such as an impossible differential attack [6]. As an example for the prac2

Table 1. Numbers of Attacked Rounds by Generic Attacks on Feistel Schemes
Single Secret Key Setting
Feistel-1
Feistel-2 Feistel-3
5 [30]
5 [30]
5 [30]
Distinguisher5∗ [25]5∗ [25]5∗ [25]5∗ [11]
5∗ [11]
5∗ [11]
Key Recovery Attack (k = 2n)7 [22] 8 (Ours) 9 (Ours) 11 (Ours)
Key Recovery Attack (k = 3n/2) 5 [22] 6 (Ours) 7 (Ours) 9 (Ours)
Key Recovery Attack (k = n)
3 [22] 4 (Ours) 5 (Ours) 7 (Ours)
Known Key Setting
Distinguisher
not given
7 [26]
11* [33]* : Each F function is restricted to a permutation
Attack Typetical impact of our work, we show the best attack on the reduced CAST-128 [1]even when its key scheduling function is ideal. Also, we show extremely low-dataattacks on the reduced Camellia [5] with less than 60 data sets.
This paper is organized as follows: Section 2 gives notations and definitions
used throughout this paper, and gives a brief review of the all subkeys recovery
approach. We review the related work and show its improvement in Section 3.
Our key recovery attacks on two types of Feistel ciphers and those applications
to CAST-128 and Camellia are described in Sections 4 and 5. Section 6 discusses
the usefulness of our attack. Finally, we conclude in Section 7.

2

Preliminary

In this section, we give notations used throughout this paper, then define ourtarget Feistel ciphers. Finally, we briefly review the all subkeys recovery approachpresented in [22].
2.1

Notation

The following notation will be used throughout this paper:n: block size.
k: the size of the master key.
Li , Ri : left or right half of the i-th round input.
Ki: the i-th round subkey (n/2 bits).
ℓ: the size of an S-box.
m: the number of S-boxes in an S-box layer.
Xi: the i-th round state.
Xi,j: the j-th S-box word (ℓ-bit data) of Xi .
XiL , XiR : left or right half bits of Xi .
a|b or (a|b) : Concatenation.
2.2

Feistel Cipher

In this paper, we focus on balanced Feistel networks as illustrated in Fig. 1.
An n-bit plaintext P is divided into two sub-blocks as P = (L1 , R1 ), where3Kk

key scheduling function
K1

Ka−2

n/2

Ka−1

Ka+1

Ka

Ka+2

Kr
Lr+1

R1
n

P

F

...

F

F

F

F

F

...

F

C
Rr+1

L1

r rounds

Fig. 1. Balanced Feistel Network (Feistel-1)

Li , Ri ∈ {0, 1}n/2 . Then the (i + 1)-th round input state is calculated as follows:(Li+1 , Ri+1 ) ← (Ri ⊕ FiKi (Li ), Li ),where FiKi : {0, 1}n/2 → {0, 1}n/2 is a keyed function in the i-th round using thei-th round (n/2)-bit subkey Ki . An n-bit ciphertext C for the r-round encryptionfunction is derived as C = (Rr+1 , Lr+1 ). Note that the last round of the Feistel
cipher does not have a swap operation. Hereafter, the size of each subkey usedin one round is assumed to be half of the block size (i.e., Ki ∈ {0, 1}n/2 ).
In this work, we deal with three types of Feistel block ciphers illustrated inFig. 2. Feistel-1 denotes the Feistel cipher with random keyed F-functions. Eachsubkey is assumed to be randomly independent. Thus each keyed F-function is
also independent from each other. In concrete ciphers, each subkey is usually
XORed before an F-function. Feistel-2 reflects such ciphers. In other words, theoutput of the F-function Yi = FiKi (Xi ) is represented as Yi = Fi (Xi ⊕ Ki ),where Fi is a fixed function in the i-th round (not limited to a permutation).
Similarly, Feistel-3 is the Feistel-2 cipher whose Fi is limited to an SP-type Ffunction, where each F-function consists of a bijective S-box layer (S-layer) anda linear diffusion layer (P-layer), and an n/2-bit subkey is XORed before the
S-box layer. Each S-box layer consists of m ℓ-bit S-boxes (i.e., m · ℓ = n/2), andeach P-layer consists of an m × m linear matrix represented as Mi . Note that
Feistel-1 includes Feistel-2 and Feistel-3, also Feistel-3 is a subset of Feistel-2.
The size of the master key is denoted as Feistel-[k]. For example, Feistel-2[n] is
the Feistel cipher with fixed F-functions XORed by a subkey before the function
whose master key size is the same as the block size (e.g., a 128-bit block cipher
taking a 128-bit key).
2.3

All Subkeys Recovery Approach [22]The all subkeys recovery (ASR) attack was proposed by Isobe and Shibutani at
SAC 2012 [22]. The ASR attack is considered as an extension of the meet-in-themiddle (MITM) attack, which mainly exploits a low key-dependency in the keyscheduling function. The basic concept of the ASR attack is guessing all subkeys
instead of the master key so that the attack can be constructed independently
4

...

Ki

Ki
Fi

s
s
...

Fi

...

...

Ki

Mi

...

...

...

s

Feistel-1

Feistel-2

Feistel-3

Fig. 2. Target Feistel Ciphersfrom the structure of the key scheduling function, by regarding all subkeys as
independent variables. Thus the attack can also be applied to a block cipher
having a complex key scheduling function.
Let us briefly review the procedure of the ASR attack. In the ASR attack,an attacker first determines a t-bit matching state X, where X ∈ {0, 1}t . In theforward direction, the matching state derived from a plaintext P and a set of
subkeys K(1) by a function F(1) is represented as X = F(1) (P, K(1) ). Similarly,
the state computed from a ciphertext C and another set of subkeys K(2) by−1
a function F(2) in the backward direction is denoted as X = F(2)(C, K(2) ).
K(3) denotes a set of the remaining subkeys not required for computing X, i.e.,|K(1) | + |K(2) | + |K(3) | = r · n/2. The attacker guesses K(1) and K(2) in parallel,−1(C, K(2) ) holds. Note that thethen checks if the equation F(1) (P, K(1) ) = F(2)equation holds when the guessed subkey bits are correct. After this process,it is expected that there will be 2r·n/2−t key candidates. Finally, the attacker
exhaustively searches the correct key from the surviving key candidates. The
required computations of the attack in total Ccomp using N plaintext/ciphertext
pairs is estimated as
Ccomp = max(2|K(1) | , 2|K(2) | ) × N + 2r·n/2−N ·t .

(1)

The number of required plaintext/ciphertext pairs is max(N, ⌈(r·n/2−N ·t)/n⌉).
The required memory is about min(2|K(1) | , 2|K(2) | ) × N blocks, which is the costof the table used for the matching. Clearly, the ASR attack works faster than thebrute force attack when Eq.(1) is less than 2k , which is the required computations
for the brute force attack.

3

Generic Key Recovery Attack on Feistel-1

In this section, we first review key recovery attacks on balanced Feistel networks
presented in [22] and generalize it to Feistel-1[n], -1[ 32 n] and -1[2n]. After that,
we show that the basic attack can be improved by using splice and cut [3] andkey linearization techniques. By the improved attack, the numbers of attacked
rounds for the Feistel-1 are increased by one round.
For a Feistel-1 cipher, an (n/2)-bit matching state X is computed from aplaintext P and a set of subkeys K(1) ∈ {K (1) , K (2) , ..., K (a−1) } as shown in
5

R1
K1 F1

R1
K2 F2

K 3 F3

L1

n/4
′
K1R

CON

′
K1L

K2 F2

K 3 F3

n/4
n/2

Fig. 3. Splice and Cut Technique for Feistel-1

Fig. 1 (i.e., X = F(1) (P, K(1) )). Similarly, the matching state is obtained froma ciphertext C and another set of subkeys K(2) ∈ {K (a+1) , K (a+2) , ..., K (r) } as
−1
(C, K(2) ). Also, X is computed independently from an (n/2)-bit subkey
X = F(2)K (a) , i.e., K(3) ∈ {K (a) }.
3.1

Basic Attack on Feistel-1 [22]For Feistel-1[2n] (e.g., a 128-bit block cipher accepting a 256-bit key), 7 roundsof the cipher can be attacked in a straightforward manner, since F(1) and F(2)are composed of 3 rounds of the cipher and thus the sizes of K(1) and K(2) areboth 3 · n/2 bits. In this attack, the total time complexity Ccomp using four
plaintext/ciphertext pairs is estimated as
Ccomp = max(23n/2 , 23n/2 ) × 4 + 27·n/2−4·n/2 ≈ 23n/2+2(= 23k/4+2 )The required memory is about 4×23n/2 blocks. Since Ccomp is less than 22n (= 2k )when (4 < n), the attack works faster than the exhaustive key search.
Similarly to this, for Feistel-1[ 32 n] and Feistel-1[n] (e.g., a 128-bit block cipher
accepting a 192-bit key or a 128-bit key), key recovery attacks of at least 5 and 3
rounds of the cipher are constructed, respectively. For Feistel-1[ 32 n], F(1) and F(2)consist of 2 rounds of the cipher, and thus the sizes of K(1) and K(2) are both nbits. Therefore, the required time complexity using 3 plaintext/ciphertext pairs
is estimated as Ccomp = max(2n , 2n ) × 3 + 25n/2−3n/2 ≈ 2n+2 , and the required
memory is about 2n+2 blocks. For Feistel-1[n], a similar attack on 3 rounds
requiring 2n/2+1 (≈ 2n/2 × 2 + 2n/2 ) computations and (2 × 2n/2 ) blocks memory
is mounted by using 1 round of F(1) and F(2) . Roughly speaking, when Eq.(1) isless than 2k , the ASR attack works faster than the brute force attack. Therefore,
the necessary condition for the basic ASR attack is that each size of all subkeys
in F(1) and F(2) is less than the size of the master key.
3.2

Improved Attack on Feistel-1

We demonstrate that the basic attack on Feistel-1 presented in [22] is improvedby controlling the value of plaintexts. It allows us to attack one more round on
Feistel-1, e.g., an 8-round attack on Feistel-1[2n].
Suppose that an input L1 (= R2 ) is fixed to an arbitrary (n/2)-bit constantCON, then L2 is expressed as L2 = R1 ⊕ K1′ , where K1′ = F1 (K1 ⊕ CON ).
6

Since K1′ depends only on K1 , it is regarded that a new (n/2)-bit subkey K1′
is linearly inserted in the first round without an F-function, which is called key
linearization.
′
As shown in Fig. 3, since K1′ can be divided into two (n/4)-bit words K1L′′
and K1R , the splice and cut technique in [4] enables us to separately use K1L′
and K1R in F(1) and F(2) , respectively. Note that, in the splice and cut technique, the MITM attack starts from multiple values of start states for parallel
guesses of K(1) and K(2) , while the basic MITM attack starts from multiple
plaintext/ciphertext pairs.
For Feistel-1[2n], an 8-round generic key recovery attack is mounted thanks
to the splice and cut technique, while each cost (namely time, memory and data)
for the attack is increased by O(2n/4 ) compared to the basic attack. The size ofeach key set K(1) and K(2) is increased by (n/4) bits due to the splice and cut,and thus the size of each set K(1) and K(2) is 7n/4(= 3 · n/2 + n/4) bits long. In
this attack, the total time complexity Ccomp using five start states is estimatedasCcomp = max(27n/4 , 27n/4 ) × 5 + 28·n/2−5·n/2 ≈ 27n/4+3(= 27k/8+3 ).

The required memory is about 5× 27n/4 blocks. Since (n/4) bits of plaintexts arevaried depending on K(2) and the start states, the required data is 2n/4 chosen
plaintexts when the other 3n/4 bits of the start state are fixed.
For Feistel-1[ 32 n] and Feistel-1[n], by using the splice and cut technique,key recovery attacks of at least 6 and 4 rounds of the cipher are constructed,
respectively. For Feistel-1[ 32 n], the sizes of K(1) and K(2) are 5n/4 bits each.
Therefore, the required time complexity with four start states is estimated as
Ccomp = max(25n/4 , 25n/4 ) × 4 + 26n/2−4n/2 ≈ 25n/4+2 , and the required memory is about 25n/4+2 blocks. For Feistel-1[n], a similar attack requiring 23n/4+2(≈ 23n/4 × 3 + 2n/2 ) computations and (3 × 23n/4 ) blocks memory is mounted.
These attacks also require 2n/4 chosen plaintexts. Those results are summarizedin Table 2.

4

Key Recovery Attack on Feistel-2

This section shows generic key recovery attacks on Feistel-2 ciphers. In contrast to Feistel-1 ciphers, key injections of Feistel-2 ciphers are restricted to
XOR operations. This allows an attacker to equivalently transform subkeys,
then more rounds can be attacked. To begin with, we introduce an advanced
technique called function reduction, which enables us to reduce the number of
involved subkey bits by exploiting degrees of freedom of a plaintext/ciphertext
pair. Combining it with a (multi-)collision technique, 5, 7 and 9 rounds attacks
on Feistel-2[n], -2[ 32 n] and -2[2n] are demonstrated, respectively. The overview
of the function reduction is depicted in Fig. 4. The required complexities for
those attacks are summarized in Table 2, and the overview of the attacks areillustrated in Fig. 5. Note that the key additions of Feistel-2 are limited to XOR
operations, however, similar idea may be applied to other key additions such as
7

L1

K1

L2

K2

L3

K3

L4

K4

L5

K5

R1

CON

F
R2 L2

F
R3 L3

F
R4 L4

F
R5 L5

F

K2

K3

K4

K5

′
K1

F

F

(a)

R2 L′
2

′
K2

R3 L3

K3

R4 L′
4

R5 L5

F

R1

CON

F

R6 L6

L6

R1

′
K4

F
F
F
′
K1

R6

(b)

R2 L′
2

′
K2

′ L
R3
3

K3

R4 L′
4

′
K4

′ L
R5
5

K5

L6

(c)

R1

CON

′
K1

R2

F
F
F
F

′
R3

′ = F (K ⊕ CON )K1
1
1′ = K ⊕ K′
K2
2
1

R 4 K ′ = K4 ⊕ K ′
4
1

′
′
R5
L′i = Li ⊕ K1
′ = R ⊕ K′
Ri
i
1
R6

(d)

Fig. 4. Function Reduction Techniquemodular additions. Moreover, as an application of our approach on Feistel-2, weshow a key recovery attack on the reduced CAST-128 [1, 2]. The structure of
CAST-128 is similar to Feistel-2, however, the size of each round key of CAST128 is larger than that of Feistel-2 and the key additions are not only XOR
operations but also modular additions and subtractions. Since the larger round
key generally requires more computations to guess, it seems to be hard to directly mount an attack on CAST-128. We use the improved function reduction
technique to make an attack feasible, then show a key recovery attack on the
8-round reduced CAST-128, which is the best attack known in literature.
4.1

Function Reduction Technique

Suppose that the half outputs of the r-round Feistel-2 cipher Lr+1 and Rr+1
are represented by functions FL,r and FR,r as Lr+1 = FL,r (KL , L1 |R1 ) andRr+1 = FR,r (KR , L1 |R1 ), where KL and KR denote sets of subkeys used in FL,rand FR,r , respectively. In general, after sufficient number of round operations,
all subkeys are required to compute Lr+1 , i.e., |KL | = n/2 · r, while Rr+1 isderived independently from the last subkey Kr , i.e., |KR | = n/2 · (r − 1). For the
Feistel-2 cipher, fixing half bits of inputs, one more round of subkey data can be
reduced as follows:
Theorem 1 (Function Reduction). For the Feistel-2 cipher, if L1 is fixed,
KL and KR used in FL,r and FR,r contain at most (n/2 · r) and (n/2 · (r − 2))subkey bits when r is odd, and contain at most (n/2 · (r − 1)) and (n/2 · (r − 1))subkey bits when r is even, respectively.
Proof. By using the key linearization, L2 is considered to be linearly affected by
the subkey K1′ as follows. Assuming that L1 is an arbitrary (n/2)-bit constantCON, L2 and R2 are expressed as L2 = R1 ⊕ K1′ and R2 = CON , where
K1′ = F (K1 ⊕ CON )1 . Since K1′ depends only on K1 , it can be regarded as a1

For simplicity, we assume that all F-functions are identical. However, our attack
works even if each F-function is distinct from each other.

8

R1

R2

′
K1

F
′
K2

R4

L6

R5

F

′ = F (K ⊕ CON )K1
1
1′ = K ⊕ K′
K2
2
1′
K5 = F (K5 ⊕ CON2 )′ = K ⊕ K′
K4
4
5

F
′
K4

K3

L2

CON1

′
K5

R3

L4

L3

CON2

L5

(a) 5-round Attack on Feistel-2[n]

R1

R2

F
′
K2
CON1

R4

R3

L2

F

′′
K7

R5

F

K3

′
K4

L3

L4

R6

F

R7

L8

L7

CON2

F
′
K6

K5

L6

L5

′ = F (K ⊕ CON )K1
1
1′ = K ⊕ K′
K2
2
1
′ = K ⊕ K′
K4
4
1
′ = K ⊕ K′
K6
6
7
′ = F (K ⊕ CON )K7
72′′ = K ′ ⊕ K ′K7
17(b) 7-round Attack on Feistel-2[ 32 n]

R1

R2

F
′
K2
CON1 L2

R4

R3

F

′
K9

R5

F

K3

′
K4

L3

L4

′
K1
K5
L5

R6

F

R7

F

R8

F

R9 L
10

F

′
K6

K7

′
K8

L6

L7

L8

L9

′ = F (K ⊕ CON )K1
1
1′ = K ⊕ K′
K2
2
1
′
′
K4 = K4 ⊕ K1
′ = K ⊕ K′
K6
6
9
′ = K ⊕ K′
K8
8
9′
K9 = F (K9 ⊕ CON2 )CON2(c) 9-round Attack on Feistel-2[2n]Fig. 5. Key Recovery Attacks on Feistel-2 Ciphers

new subkey instead of K1 (see Fig. 4-(b)). By using an equivalent transform,
K1′ is moved to the end of the cipher as shown in Figs. 4-(c) and (d). After thetransform, each subkey introduced in even round is XORed with K1′ , and thus
it can be redefined as Kp′ = Kp ⊕ K1′ (p is even). When r is even, K1′ is linearlyaffecting to Rr+1 in the last as shown in Fig. 4-(c). Therefore, both Lr+1 andRr+1 contain at most (n/2·(r −1)) bits of subkeys. When r is odd, K1′ is linearlyaffecting to Lr+1 in the last as shown in Fig. 4-(d). Consequently, Rr+1 contains
at most (n/2 · (r − 2)) bits of subkeys, while the amount of subkey bits requiredfor computing Lr+1 is not reduced (i.e., |KL | = n/2 · r).
⊓⊔

The function reduction technique, which consists of equivalent transforms ofround keys and the key linearization, is related to the complementation properties of Feistel networks in which the round keys of even (or odd) rounds arecomplemented by some fixed values. It essentially exploits the property of Feistel network that an input of a keyed F-function in the i-th round (Li ) linearlyaffects an input of a keyed F-function in the (i + 2)-th round (Li+2 ). In otherwords, the relation of Li and Li+2 is expressed as Li+2 = Li ⊕ Xi+1 , where Xi+1
is an output of an F-function of (Li+1 ). We exploit it in the line of a MITM attack to reduce the subkey data for the computation of the intermediate values,
while the previous attacks are used for differential attacks [15, 8] and speeding
up keysearches using equivalent keys [7, 18].
9

4.2

Key Recovery Attack on 5-round Feistel-2[n]In order to apply the function reduction to both the forward and backward
computations, we prepare plaintext/ciphertext pairs in the form of L1 = CON1
and R6 = CON2 , where CON1 and CON2 denote arbitrary (n/2)-bit constants.
Let R4 be an (n/2)-bit matching state. From Theorem 1, in the forward
computation, R4 can be computed by an (n/2)-bit subkey K2′ (= K2 ⊕ K1′ ),where K1′ = F (K1 ⊕ CON1 ). In the backward computation, since R4 can be
regarded as an output of the even round (r = 2), R4 can also be computed by an(n/2)-bit subkey K4′ (= K4 ⊕ K5′ ), where K5′ = F (K5 ⊕ CON2 ), i.e., K(1) ∈ K2′
and K(2) ∈ K4′ . Since |K(1) | = |K(2) | = n/2 and the size of the matching stateis also n/2, two plaintext/ciphertext pairs are sufficient to determine K(1) andK(2) . In order to obtain such two pairs that have the form of L1 = CON1
and R6 = CON2 , we use 2n/4 chosen plaintexts by randomly changing R1 as
P = (CON1 |R1 ). After this process, we have 2n/4 corresponding ciphertexts,
and thus there will exist (n/2) bits colliding R6 with high probability due to thebirthday paradox.
The time complexity of determining K2′ and K4′ by the MITM approach isestimated as Ccomp = max(2n/2 , 2n/2 ) × 2 = 2n/2+1 . In order to determine all
subkeys, we use the following equation: F (R4 ⊕ K3 ) = R1 ⊕ K1′ ⊕ L6 ⊕ K5 =R1 ⊕ L6 ⊕ K1′′ , where K1′′ = K1′ ⊕ K5 . Since R4 can be computed from K2′ or
K4′ , we can recursively mount the MITM approach to determine K3 and K1′′
with complexity of 2n/2+1 (= max(2n/2 , 2n/2 ) × 2). After exhaustively guessing
K1 with a time complexity of 2n/2 , all subkeys Ki (1 ≤ i ≤ 5) are determinedfrom the previously obtained subkeys K2′ , K4′ and K1′′ . Therefore, the whole timecomplexity is estimated as 2n/2+2 (≈ 2n/2+1 + 2n/2+1 + 2n/2 ). Due to k = n, thetime complexity 2n/2+2 = 2k/2+2 is less than 2k which is required computations
for the brute force attack. The required data is 2n/4 chosen plaintext, and therequired memory is about 2n/2+1 words. If the function reduction technique isused only in the forward computation, a 4-round attack is constructed with lessdata (see Fig. 5-(a) and Table 2).

4.3

Key Recovery Attack on 9-round Feistel-2[2n]A key recovery attack on a 9-round Feistel-2[2n] is constructed in a similar
way to the 5-round attack on Feistel-2[n]. In this attack, we can add 2 morerounds in each direction, and a 6-multicollision is required to obtain desired
plaintext/ciphertext pairs unlike the attack on Feistel-2[n]. It has been known
that an n-bit t-multicollision is found in t! · 2n·(t−1)/t random data with highprobability [36]. Thus, the six plaintext/ciphertext pairs whose form are P =(CON1 |R1 ) and C = (CON2 |L10 ) could be found from 6!1/6 · (2n/2 )5/6 ≈ 3 ·(2n/2 )5/6 chosen plaintexts. More precisely, after querying 3 · (2n/2 )5/6 chosen
plaintexts with distinct R1 , there will exist a 6-collision of R10 in corresponding
ciphertexts with high probability (see Fig. 5-(c) and Table 2).
10Table 2. Details of Our Attacks
Target key size Round

Time

MemoryData

Reference

n
3
n
2
2n

4
6
8

23n/4+2
25n/4+2
27n/4+3

23n/4+2
25n/4+2
27n/4+3

2n/4
2n/4
2n/4

Sect. 3
Sect. 3
Sect. 3

4
5
6
7
8
9

2n/2+22n/2+225n/4+4
25n/4+4
23n/2+3
23n/2+3

2n/2+12n/2+12n+4
2n+4
3n/2+32
23n/2+3

2
2n/4
9
9!1/9 · (2n/2 )8/9
6
1/6
6!
· (2n/2 )5/6

Sect. 4.2
Sect. 4.2
Sect. 4.4
Sect. 4.4
Sect. 4.3
Sect. 4.3

Feistel-1nFeistel-2

3
n
2

2n
n
Feistel-3

3
n
2

2n

7
8
9
11

23n/4+ℓ · N1 23n/4+ℓ · N1
N1
Sect. 5.3
2n+ℓ · N22n+ℓ · N2
N2
Sect. 5.5
n+ℓ
n+ℓ
1/N2
n/2 (N2 −1)/N2
2· N2
2· N2 N !
· (2 )
Sect. 5.5
27n/4+ℓ · N3 27n/4+ℓ · N3
N3
Sect. 5.4

N1 = (3n/2 + 2ℓ)/ℓ, N2 = (2n + 2ℓ)/ℓ, N3 = (7n/2 + 2ℓ)/ℓ

4.4

Key Recovery Attack on 7-round Feistel-2[ 32 n]

In this attack, R5 is used as the matching state. From Theorem 1, in the forward
computation, R5 can be computed from 3 · n/2 bits subkeys K2′ , K3 and K1′ ,where K2′ = K2 ⊕ K1′ and K1′ = F (K1 ⊕ CON1 ). In the backward computation,
R5 can be computed from 3 · n/2 bits subkeys K6′ , K5 and K7′ , where K6′ =K6 ⊕ K7′ and K7′ = F (K7 ⊕ CON2 ). Since R5 is expressed as K1′ ⊕ L4 andK7′ ⊕ (F (R6 ⊕ K5 ) ⊕ L6 ), if only (n/4) bits of K1′ ⊕ K7′ are guessed, (n/4)bit matching is feasible. It is regarded that K7′′ (= K1′ ⊕ K7′ ) is included in the
backward computation (see Fig. 5-(b)).
Then, since |K(1) | = n/4, |K(2) | = 5n/4, and the size of the matching stateis n/4, nine plaintext/ciphertext pairs are required to determine K(1) and K(2)due to the relation (n + 5n/4)/(n/4) = 9. Such nine plaintext/ciphertext pairs
whose form are P = (CON1 |R1 ) and C = (CON2 |L8 ) can be found from 9!1/9 ·(2n/2 )8/9 ≈ 4.2 · (2n/2 )8/9 chosen plaintexts. The other complexities required forthis attack and the low data attack on 6-round Feistel-2[ 32 n] are described inTable 2.

4.5

Application to 8-Round Reduced CAST-128

In order to demonstrate the practical impact of our work on Feistel-2, we apply
it to CAST-128 block cipher. Using the improved function reduction techniques,
we show an attack on the 8-round reduced CAST-128 having more than 118 bits
key, which is the best attack with respect to the number of attacked rounds inliterature even when its key scheduling is an ideal function.
11

R2

R1

f
Kr

1 ≪

Km

1

L1

f
Kr

2 ≪

Km
L2

2

′
K8

R4

R3

f
Kr

L3

3

Kr

4 ≪

Km
L4

4

R7

R6

f

3 ≪

Km

R5

f
Kr

5 ≪

′
Km
L5

5

R8

f
Kr

6 ≪

Km
L6

f
Kr

7 ≪

Km

6
L7

7

L9

′
K8
= f ((Km8⊕ CON ) ≪ Kr )
8

′
Km
′
K8

5
= Km

L8

5

′
⊕ K8

CON

Fig. 6. Key Recovery Attack on 8-Round CAST-128

Description of CAST-128. CAST-128 [1, 2] is a 64-bit Feistel block cipher
accepting a variable key size from 40 up to 128 bits (but only in 8-bit increments).
The number of rounds is 16 when the key size is longer than 80 bits. First, thealgorithm divides the 64-bit plaintext into two 32-bit words L0 and R0 , then thei-th round function outputs two 32-bit data Li+1 and Ri+1 as follows:
Li+1 = Ri ⊕ Fi (Li , Kirnd ), Ri+1 = Li ,where Fi denotes the i-th round function and Kirnd is the i-th round key consisting of a 32-bit masking key Kmi and a 5-bit rotation key Kri . The detail of
Fi is expressed as
Fi = f ((Li i Kmi ) ≪ Kri ),where f consists of four 8 to 32-bit S-boxes, ≪ Kri denotes a Kri -bit left rotation, and i denotes addition, XOR or subtraction depending on the round number i, i.e., i denotes addition for i ∈ {1, 4, 7, 10, 13}, XOR for i ∈ {2, 5, 8, 11, 14}
and subtraction for i ∈ {3, 6, 9, 12, 15}. We omit the details of f , since, in our
analysis, it is regarded as the random function that outputs a 32-bit random
value from a 32-bit input.
Key Recovery Attack on 8-round CAST-128. The structure and the parameter of CAST-128 having sufficiently large key are similar to Feistel-2[2n].
However, for CAST-128, a 37(= 32 + 5)-bit subkey is inserted into each Fi , i.e.,
a 32-bit subkey is used in i and the remaining 5-bit subkey is used in a key dependent rotation, while a 32-bit subkey is inserted in each round for Feistel-2[2n]with n = 32. Thus, the 9-round attack on Feistel-2[2n] is not directly applicable
to CAST-128. However, the improved function reduction technique allows us toconstruct an 8-round attack on CAST-128.
Let R5 be an (n/2)-bit matching state. In the backward computation, R9 isfixed as CON , and K8′ = f ((CON ⊕ Km8 ) ≪ Kr8 ) is moved to L5 and an input′= K8′ ⊕Km5 , as shown inof the 7-th round function, by converting Km5 into Km
5
Fig. 6. Then, the input of f in the 7-th round is expressed as (L9 ⊕ K8′ ) + Km7 .
If the lower b bits of L9 , which are controllable by the ciphertext, are fixed
to 0, the lower b bits of this computation are expressed as K8′ + Km7 . Thus,′(K8′ + Km7 ) is regarded as a new b-bit subkey Km= (K8′ + Km7 ), while the7′upper (n/2 − b) bits remain (L9 ⊕ K8 ) + Km7 . In the backward computation of
R5 , |K(2) | = 37 × 2 + (b + (n/2 − b) × 2 + 5) bits of the key are involved.
12

Mi

X

X

s

s

Ri+1

...

Li

...

X

−1
(Ri )
i

...

...

s
s

Mi

...

Li

M
s
s

...

Ki+1

X

Ki

Ri
s
s
...

Mi

s
Li+1

Ki

Ri

...

s
s

...

Ki

...

Li

Mi+1

matchings−1(Li+3 )
i+2

X

Ri+3

...

Mi+2

s
Li+3

M
s
s
...

Ri+3

s

Ki+2

Li+3
s
s

...

Mi+2

Ki+2

...

Ri+2

...

s
s

...

Ki+2

...

Li+2

Mi+2

s

Ri+3

Fig. 7. Matching without Matrix

Evaluation. Since |K(1) | = 111, |K(2) | = 114 (b = 29) and the size of thematching state is 32 bits, eight plaintext/ciphertext pairs are required to determine K(1) and K(2) due to the relation (111 + 114)/32 < 8(= 232−29 ). The′
required time complexity to determine subkeys K1rnd , K2rnd , K3rnd , K6rnd , Km,
5′′Kr5 , the lower 29 bits of Km7 , the upper 3 bits of K8 , and Km7 is estimatedas Ccomp = max(2111 , 2114 ) × 10 ≈ 2118 . The remaining Kr4 and K8′ are exhaustively searched with the time complexity of 264 . Then, all subkeys are ob′′′and= K8′ ⊕ Km
= K8′ + Km7 , Kmtained by using the relations of Km
557′K8 = f ((CON ⊕ Km8 ) ≪ Kr8 ). The required data is eight chosen ciphertexts,
and the required memory is 2111 words. Therefore, when the key size is morethan 118 bits long, our attack works faster than the brute force attack.

5

Key Recovery Attack on Feistel-3

This section presents generic key recovery attacks on Feistel-3 ciphers. Feistel-3
ciphers are the Feistel-2 ciphers whose F-functions are restricted to be SP-type Ffunctions, which consist of an S-box layer followed by a linear matrix operation.
This allows an attacker to exploit a linearity of a matrix computation, and thus
the number of attacked rounds can be increased. To begin with, we review two
techniques which exploit a linearity of a matrix computation. We refer those
two techniques as matching without matrix and matrix separation to make our
explanation simple. However, those techniques have already been introduced,
for example, in [29, 32]. Combining them with a (multi-)collision technique andfunction reduction, 7, 9 and 11 rounds attacks on Feistel-3[n], -3[ 32 n] and -3[2n]are demonstrated, respectively. Furthermore, as an application of our approachon Feistel-3, we show several key recovery attacks on the reduced Camellia [5].
Since Camellia is a Feistel cipher with SP-type F-functions, our attack on Feistel3 can be directly applied to it even if its key scheduling function is ideal. Besides,
the number of attacked rounds by our attack is further increased by one roundfor Camellia due to its non-MDS matrix. Consequently, we present generic key
recovery attacks requiring extremely low data on the 8-, 10-, 12-round reduced
Camellia without F L/F L−1 functions and key whitenings.
13

Li,1 Li,2 Li,3 Li,4
Li,1 Li,2 Li,3 Li,4
Ki,2
Ki,3
Ki,4
ℓ

ℓ

ℓ

Ki,2

Ri
Ki,1

Ki,1

Ki,3

s

s
s

Mi

0

s
s

Ri
s

Mi

ℓ

ℓ

ℓ

0

ℓ

0

s

ℓ
Ki,4

0

Mi

s

Fig. 8. Matrix Separation

5.1

Matching without Matrix [32]Let us consider three consecutive rounds of the Feistel-3 cipher whose input andoutput are represented as (Li |Ri ) and (Li+3 |Ri+3 ) as shown in Fig. 7. Assumingthat an attacker knows those input and output variables, the following equation
holds:Fi (Li ⊕ Ki ) ⊕ Ri = Fi+2 (Ri+3 ⊕ Ki+2 ) ⊕ Li+3 .
(2)In order to check if the equation holds, we need to guess 2 · n/2 bits subkeys
Ki and Ki+2 , while Ki+1 is not needed to be guessed. However, if F-functions
are SP-type F-functions (i.e., Fi = Mi ◦ Si , where Mi and Si denote an m × m
matrix and an S-box layer consisting of m ℓ-bit S-boxes, respectively), the sizeof guessing subkey bits can be reduced by exploiting the linearity of the matrix
operation. Since Mi is a linear function, Eq.(2) is redescribed as:
Mi (Si (Li ⊕ Ki )) ⊕ Ri = Mi+2 (Si+2 (Ri+3 ⊕ Ki+2 )) ⊕ Li+3 ,−1(Li+3 )).
Mi (Si (Li ⊕ Ki ) ⊕ Mi−1 (Ri )) = Mi+2 (Si+2 (Ri+3 ⊕ Ki+2 ) ⊕ Mi+2

When Mi = Mi+2 , we have−1
Si (Li ⊕ Ki ) ⊕ Mi−1 (Ri ) = Si+2 (Ri+3 ⊕ Ki+2 ) ⊕ Mi+2
(Li+3 ).

(3)

Unlike Eq.(2), we can separately check if Eq.(3) holds by the size of the Sbox ℓ. Therefore, this technique enables us to reduce the number of subkey
bits to be guessed for the 3-round matching from 22·n/2 to 22ℓ . When Mi 6=
Mi+2 , the matching technique called matching through matrix presented in [31]is utilized. In this case, more than m · ℓ bits subkeys are required to be guessed.
For simplicity, from now on, we assume that Mi = Mi+2 .
In the function reduction, the modified subkey K1′ affects L2t and R2t−1(t = 1, 2, ...). Also, in the matching without matrix, we utilize the relation of
Li+1 as the matching state. This implies that if (i + 1) is even (i.e., (i + 1) = 2t),
Li+1 is affected by K1′ and it cannot be used as the matching state. Therefore,
if the matching without matrix is used with the function reduction, the starting
round of the matching i must be even (i.e., (i + 1) must be odd).
5.2

Matrix Separation [29]In general, for the function reduction technique, all inputs of an F-function
are needed to be fixed. However, in the Feistel-3 ciphers, the (partial) function
14

reduction is constructed by fixing only a part of inputs due to the linearity of thematrix. This technique referred as matrix separation in this paper gives moredegrees of freedom to the inputs.
Since Mi is a linear operation, each operation can be divided by ℓ bits.
For instance, we show the case of m = 4 as an example (see Fig. 8). Supposethat Ki = (Ki,1 |Ki,2 |Ki,3 |Ki,4 ), Ki,j ∈ {0, 1}ℓ and Li = (Li,1 |Li,2 |Li,3 |Li,4 ),Li,j ∈ {0, 1}ℓ . If three input words Li,1 , Li,2 and Li,3 are fixed, only 3/4×n/2 bitsof Ki are linearly inserted into the (i + 1)-round by regarding T = M (S ′ ((Li,1 ⊕Ki,1 )|(Li,2 ⊕Ki,2 )|(Li,3 ⊕Ki,3 ))|0ℓ ) as new subkey bits, where S ′ consists of three
S-boxes and 0ℓ denotes ℓ bits of 0. Note that T is an (n/2)-bit data, however,
it is determined by (3/4 · n/2) bits subkeys Ki,1 , Ki,2 and Ki,3 . Since Li,4 is
not fixed, M (03/4·n/2 |s(Li,4 ⊕ Ki,4 )) is non-linearly inserted into the (i + 1)-thround.
5.3

Key Recovery Attack on 7-round Feistel-3[n]For the 7-round Feistel-3[n], it seems that the function reduction is applied toboth directions and the matching without matrix is used in the rounds 3 to 5.
However, this approach does not work due to the restriction of the combination of the matching without matrix and the function reduction. To overcome
this problem, we utilize the partial function reduction in conjunction with thematching without matrix.
At first, L1 is fixed as CON1 , and K1′ = F (K1 ⊕ CON1 ) is moved to R5
by converting K2 and K4 into K2 ⊕ K1′ and K4 ⊕ K1′ , respectively. In addition,
R1L , which is the left half of R1 (n/4 bits), is also fixed as an n/4-bit constant
CONL . Using the matrix separation technique, the partial function reduction′
technique is applicable to the left half of K2′ represented as K2L. Specifically, let
′
′
n/4
′′
′′
an n/2-bit variable K2 be K2 = M (S (K2L ⊕ CONL )|0 ), where S ′ consistingof m/2 S-boxes and 0n/4 denotes n/4 bits of 0. Since K2′′ is linearly inserted inround 2 by the matrix separation, it is possible to move to L7 (see Fig. 9-(a)).
The matching without matrix technique is applied to the three consecutive
rounds from rounds 4 to 6. In the forward and backward computations, (L4 |R4 )′′and (L7 |R7 ) are computable from (K2R
, K3′ ) and (K2L
, K7′ ), respectively. Then,′
if ℓ bits of K4 and K6 are guessed, an ℓ-bit matching is feasible, i.e., K(1) ∈
′
′
′
′
and
{K2R
, K3′ , K4,a} and K(2) ∈ {K2L
, K7′ , K6,a }, where (1 ≤ a ≤ m), and K4,a′
K6,a denote arbitrary ℓ bits data of K4 and K6 , respectively.
Since |K(1) | = |K(2) | = 3/2 · n/2 + ℓ and the matching size is ℓ bits, N1 =(3n/2 + 2ℓ)/ℓ plaintext/ciphertext pairs are required to determine K(1) andK(2) . The complexity of determining K(1) and K(2) is estimated as Ccomp =max(23n/4+ℓ , 23n/4+ℓ ) × N1 . After that, we are able to determine the other bits
for finding all subkey bits by using a simple MITM attack on the remaining K4′
and K6 , and K1′ and K5 , respectively.
Therefore, the whole time complexity is estimated as 23n/4+ℓ × N1 . Due tok = n, the required complexity 23k/4+ℓ · N1 is less than 2k . The required data is
N1 = (3n/2 + 2ℓ)/ℓ chosen plaintexts, and the memory is 23n/4+ℓ · N1 words.
15

matching without matrix

CONL |R1R

M

M

′
K2R
L2

CON1

R4

R3

R2

R5
′
K1
M

M

′
K3

′
K4

L3

L4

R7

R6
M

′′
K2
L7

L6

L5

′ = K ⊕ K ′ = K ′ |K ′
K2
2
1
2L
2R
′ = K ⊕ K′
K4
4
1

M

K6

K5

′ = F (K ⊕ CON )
K1
1
1

L8

′′ = M (S ′ (K ′n/4
K2
2L ⊕ CONL )|0

K7′ = K ⊕ K ′′
K3
3
2

R8

′ = K ⊕ K ′′K5
52(a) 7-round Attack on Feistel-3[n]
R1

R2
M

CON1

R4

R3
M

R5
′
′
K1
M K9

M

′
K2

K3

′
K4

L2

L3

L4

R7

R6

K5
L5

M

′ = F (K ⊕ CON )K1
1
1
R9 L10R8
M′ = K ⊕ K′
K4
4
1

M

′
K6

K7

′
K8

L6

L7

L8

′ = K ⊕ K′
K2
2
1

′ = K ⊕ K′
K6
6
9
′ = K ⊕ K′
K8
6
9′
L9 CON2 K9 = F (K9 ⊕ CON2 )(b) 9-round Attack on Feistel-3[ 23 n]′ = F (K ⊕ CON )K1
1
1′ = K ⊕ K ′ = K ′ |K ′
K2
2
1
2L
2R
′′ = M (S ′ (K ′n/4 )K2
2L ⊕ CONL )|0

CONL |R1R
R3

R2
M
′
K2R
CON1

L2

R4
M

R5
M

R7

R6
M

M

′
K3

′
K4

′
K5

′
K6

L3

L4

L5

L6

R8

′
K1
M
K7
L7

R10

R9
M

M

R11 L12

M

M

K8′′ K9 K10
K2

K11

L8

L9

L11 R12

L10′ = K ⊕ K′
K4
4
1
′ = K ⊕ K′
K6
6
1
′ = K ⊕ K ′′K3
32
′ = K ⊕ K ′′K5
52
′ = K ⊕ K ′′K7
72(c) 11-round Attack on Feistel-3[2n]Fig. 9. Key Recovery Attacks on Feistel-3 Ciphers

5.4

Key Recovery Attack on 11-round Feistel-3[2n]Similarly to the attack on the 7-round Feistel-3[n], chosen plaintexts in the formof P = (L1 |R1L |R1R ) = (CON |CONL |R1R ) are used. Then two more rounds canbe added to both forward and backward directions due to increasing the masterkey size. Thus, an 11-round attack is constructed. For the detailed parameters,
see Table 2 and Fig. 9.
5.5

Key Recovery Attack on 9-round Feistel-3[ 32 n]

As shown in Fig. 9-(b), for the 9-round Feistel-3[ 32 n], the function reduction isapplied to both directions combined with the matching without matrix to therounds 4 to 6, since the middle of the matching is odd indexed round. Thus, a
key recovery attack is constructed in a straightforward way, unlike the attacks
on Feistel-3[n] and -3[2n].
In this attack, since |K(1) | = |K(2) | = 2n/2 + ℓ and the matching size is ℓbits from Fig. 9-(b), N2 = (2n + 2ℓ)/ℓ plaintext/ciphertext pairs are required todetermine K(1) and K(2) . Such pairs in the form of L1 = CON1 and R10 = CON2
are found from N2 !1/N2 · (2n/2 )N2 −1/N2 chosen plaintext/ciphertext pairs. Note
that, if the number of required chosen plaintext/ciphertext pairs, which depends
on the parameter n and ℓ, is more than n/2, the partial function reduction
16

technique can be applied to L1 and R10 . Otherwise, another attack approachis required for this variant. Moreover, if the function reduction is used only inthe forward direction, an 8-round attack with extremely low data complexity isderived (see Table 2).
5.6

Application to Reduced Camellia

In order to demonstrate the usefulness and versatility of our approach on Feistel3, we apply our attack to the reduced version of Camellia block cipher [5], which
is Camellia without F L/F L−1 functions and key whitenings. Camellia is a Feistel block cipher whose F-function is the SP-type F-function consisting of eight
8-bit S-boxes followed by an 8 × 8 matrix operation. Thus, our attacks on the
Feistel-3 cipher presented in the previous section are directly applicable to the
7/9/11-round reduced Camellia-128/192/256. Note that since our attack does
not depend on the key scheduling function, the attack works on any key scheduling function even ideal. Furthermore, by exploiting the low diffusion propertyon the matrix used in Camellia, we develop the advanced five round matching
technique. Then we present low-data complexity attacks requiring less than 60
plaintext/ciphertext pairs on the 8/10/12-round reduced Camellia-128/192/256
without F L/F L−1 and key whitenings.
Five Round Matching for Non-MDS Matrix. Let us consider five consecutive rounds of the Camellia whose input and output are represented as (Li |Ri )and (Li+5 |Ri+5 ), respectively. By using the three-round matching without matrix technique in the middle, the following equation holds.
S(Li+1 ⊕ Ki+1 ) ⊕ M −1 (Li ) = S(Ri+4 ⊕ Ki+3 ) ⊕ M −1 (Ri+5 ).
Since the S-box layer consists of eight 8-bit S-boxes, by guessing two bytes ofsubkeys with the same byte position Ki+1,j and Ki+3,j , the 8-bit matching ispossible if the same indexed 8 bits data Li+1,j and Ri+4,j are also known. Since
Li+1 = M (S(Li ⊕Ki ))⊕Ri and Ri+4 = M (S(Li+5 ⊕Ki+4 ))⊕Ri+5 , all bits of Ki
and Ki+4 are required to be guessed to obtain any byte of Li+1 and Ri+4 if theunderlying matrix M is optimal (i.e., MDS matrix). However, for Camellia, the
8 bits data Li+1,j and Ri+4,j are derived by guessing corresponding 40(= 8 × 5)
bits of Ki and Ki+4 when (5 ≤ j ≤ 8), since Camellia utilizes non-MDS matrix(See [5] for the details of the matrix used in Camellia). For example, Li+1,5
and Ri+4,5 are derived from Ki,p (p ∈ {1, 2, 6, 7, 8}) and Ki+4,q (q ∈ {1, 2, 6, 7, 8},
respectively. Therefore, the number of key bits to be guessed for the 5-roundmatching in each direction is reduced from 128 bits (= 64 × 2) to 48 bits (= 8+ 40).
Key Recovery Attack on 8-Round Reduced Camellia-128. Let us consider the 8-round reduced Camellia-128. In order to use the function reduction
technique in the forward process, we collect chosen plaintexts in the form of
L1 = CON1 .
17

5-round matching for non-MDS matrix
R1

R2
M
′
K2

CON1

R4

R3

L2

M

R5
M

K3

′
K4

L3

L4

R7

R6

′
K1

M

K5
L5

M

M

′ = F (K ⊕ CON )
K1
1
1

L9

R8

′ = K ⊕ K′
K2
2
1
′ = K ⊕ K′
K4
4
1

M

K6

K7

K8

L6

L7

L8

′ = K ⊕ K′
K6
6
1′′ = M (S ′ (K ′8
K22,1−7 ⊕ CONL )|0 )R9′ = K ⊕ K ′′K3
32(a) 8-round Attack on Camellia-128′ = K ⊕ K ′′K5
52
′ = K ⊕ K ′′K7
72
′ = K ⊕ K ′′
K9
9
2

CON2

R2
M
′
K2,8

CON1

R4

R3

L2

M

R5
M

R7

R6
M

M

′
K3

′
K4

′
K5

′
K6

L3

L4

L5

L6

M

′
K7
L7

R10

R9

R8

′
K1

M

M

K8

′
K9

L8

L9

′′
K2

L11
M
K10

L10

R11

(b) 10-round Attack on Camellia-192
R1

R2
M
′
K2

CON1

L2

R4

R3
M

R5
M

R7

R6
M

M

K3

′
K4

K5

′
K6

L3

L4

L5

L6

′
K1

R8
M

K7
L7

R10

R9
M

M

R11

R12

M

M

M

K8

K9

K10

K11

K12

L8

L9

L10

L11

L12

L13

R13

(c) 12-round Attack on Camellia-256

Fig. 10. Key Recovery Attacks on Reduced Camellia-128/192/256

The five round matching for non-MDS matrix technique is used from rounds
3 to 7. In the forward and backward computations, (L3 |R3 ) and (L8 |R8 ) arecomputable by using K2′ (= K2 ⊕ K1′ ) and K8 , respectively. Then, for the 8-bit′
matching, 8 bits subkey K4,aand the corresponding 40 bits of subkey K3 in theforward computation are required to be guessed, where K4′ = K4 ⊕K1′ . Similarly,
we need to guess 8 bits subkey K6,a and the corresponding 40 bits of subkey K7′
in the backward computation. In other words, K(1) ∈ {K2′ , K4,a
, 40 bits of K3 }and K(2) ∈ {K8 , K6,a , 40 bits of K7 }, where 5 ≤ a ≤ 8.
Since |K(1) | = |K(2) | = 112 and the matching size is 8 bits, 28(= (112 +112)/8) plaintext/ciphertexts are sufficient to determine K(1) and K(2) . The complexity of determining K(1) and K(2) is estimated as Ccomp = max(2112 , 2112 ) ×
28 ≈ 2117 . After that, we are able to determine the other bits for finding all
subkeys by using the simple MITM attack on the remaining 24 bits of K3 andK7 , and 56 bits of K4′ and K6 in the forward and backward computations, respectively. Therefore, the whole complexity is estimated as 2117 (≈ 2117 + 280 ).
The required memory is 2117 words, and the required data is only 28 chosen
plaintext/ciphertext pairs (see Fig. 10-(a)).
18

Table 3. Comparisons of Key Recovery Attacks on Reduced Camellia-128/192/256
without F L/F L−1 Functions and Key Whitenings
Target# Attacked Rounds

Camellia-128
Camellia-192
Camellia-256

Attack TypeTime

MemoryData Reference

not given 2116.3 [28]Meet-in-the-Middle
22117
28 Sect. 5.6
182.2
Impossible Differential 2
not given 2117
[27]
Meet-in-the-Middle
2190
2174
44 Sect. 5.6

12
8
14
10

Impossible Differential 2

16
12

Impossible Differential

116.6
117

Meet-in-the-Middle

2249 not given 2123
[27]
2246
2246
60 Sect. 5.6

Key Recovery Attack on 12-Round Reduced Camellia-256. Similarly
to the attack on the reduced Camellia-128, for the reduced Camellia-256, thefive round matching for non-MDS matrix technique is used. Since two morerounds can be appended to each direction, a 12-round attack is constructed (seeFig. 10-(c) and Table 3).
Key Recovery Attack on 10-Round Reduced Camellia-192. In this attack, in order to utilize the function reduction technique in conjunction withthe matrix separation technique, we collect chosen plaintexts in the form of
L1 = CON1 and R1,1−7 = CONL , where R1,1−7 denotes the left 56 bits of R1
and CONL is a 56-bit constant. Then K1′ = F (CON1 ⊕ K1 ) is moved to R7 byredefining Kp′ = Kp ⊕ K1′ (p = 2, 4, 6). In addition, the left 56 bits of K2′ defined′as K2,1−7is also moved to R10 by using the partial function reduction technique.
′
Namely, we assume that K2′′ = M (S ′ (K2,1−7⊕ CONL )|08 ) is linearly inserted′
in round 2 and the remaining 8-bit subkey K2,8 is non-linearly inserted in round2, where S ′ consists of seven 8-bit S-boxes.
The five round matching for non-MDS matrix technique is used from rounds′, K3′ (= K3 ⊕5 to 9. Here, (L5 |R5 ) and (L10 , R10 ) are computed from (K2,8′′)) and (K2,1−7, K9 ), respectively. For the 8-bit matchK2′′ ), K4′ (= K4 ⊕ K1L′
ing, K6,8
and the corresponding 40 bits of K5′ (= K5 ⊕ K2′′ ) are required to be
guessed in the forward computation, where K6′ = K6 ⊕ K1′ . Similarly, in the
backward computation, K8,8 and the corresponding 40 bits of K9′ (= K9 ⊕ K2′′ )′′are required to be guessed. Namely, K(1) ∈ {K2,8, K3′ , K4′ , K6,8
, 40 bits of K5′ }′and K(2) ∈ {K2,1−7, K9 , K8,8 , 40 bits of K9′ }. In this attack, the whole complexity to determine all subkey bits is estimated as 2190 (≈ 2190 + 280 ). The required
memory is 2174 (≈ 2168 × 44) words, and the required data is only 44 chosen
plaintext/ciphertext pairs (see Fig. 10-(b) and Table 3).

6

Discussion

In order to compare the numbers of attacked rounds by our attacks with theprevious results, we consider key recovery attacks from a 5-round impossible
differential distinguisher or a 5-round zero-correlation linear distinguisher on19the Feistel ciphers employing bijective F-functions [6, 11]. Note that those distinguishers depend only on the structure of the cipher unlike the other distinguishers such as a differential and a linear distinguisher. When k = n, guessing
n/2 bits subkey involved in the 6-th round, it is possible to construct a 6-roundkey recovery attack from the 5-round distinguishers. Similarly, for k = 3n/2
and k = 2n, a 7 and an 8-round key recovery attacks are constructed by additionally guessing n/2 and n bits subkeys, respectively. Compared to thoseresults, our attacks are the best attacks with respect to the number of attacked
rounds for Feistel-2[2n], -3[n], -3[ 32 n] and -3[2n] as described in Table 1. Also, for
Feistel-1[2n] and Feistel-2[ 32 n], the same numbers of rounds are attacked by ourapproach. Especially, the attack on the 11-round Feistel-3[2n] greatly exceeds
the number of attacked rounds given by the distinguisher based attacks. More
importantly, Feistel-3[2n] structure is well used in concrete block ciphers suchas a 128-bit block cipher taking a 256-bit key, e.g., Camellia-256.
In addition, thanks to the MITM approach, most of our attacks require an
extremely small data complexity, in contrast to the classical statistical attacks
such as the impossible differential and zero correlation linear attacks that generally require huge amount of data. This implies that our attacks may work even
if the number of queries to the encryption oracle is restricted. In fact, the similar
approach, which is the low-data complexity attacks on AES, has already beenstudied in [13, 14]. Thus, our work is also regarded as the first evaluation resultson the low-data complexity attacks on the Feistel schemes.

7

Conclusion

This paper has shown the improved generic key recovery attacks on Feistel
schemes independent of the key scheduling function. The proposed approachis based on the all subkeys recovery attack. With several advanced techniquessuch as function reduction and key linearization, which basically reduce the number of involved subkey bits, we presented several new key recovery attacks on
the Feistel schemes.
To demonstrate the usefulness and the versatility of our approach, we showed
several attacks on the concrete block ciphers including CAST-128 and Camellia.
Among them, we would like to stress that the presented attack on the 8-round
reduced CAST-128 having more than 118 bits key is the best attack with respect
to the number of attacked rounds. Since our approach is generic, it is expected
to be applied to other Feistel-type block ciphers. We believe that our results areuseful not only for a deeper understanding the security of the Feistel schemes,
but also for designing an efficient block cipher such as a low-latency cipher.
Moreover, we expect that our attacks could be improved by combining with therecent attack called sieve-in-the-middle attack [17].

References
1. C. Adams, “The CAST-128 encryption algorithm.” RFC-2144, May 1997.

20

2. C. Adams, “Constructing symmetric ciphers using the CAST design procedure.”
Des. Codes Cryptography, vol. 12, no. 3, pp. 283–316, 1997.
3. K. Aoki and Y. Sasaki, “Preimage attacks on one-block MD4, 63-step MD5 andmore.” in SAC (R. Avanzi, L. Keliher, and F. Sica, eds.), vol. 5381 of LNCS ,pp. 103–119, Springer, 2008.
4. K. Aoki, J. Guo, K. Matusiewicz, Y. Sasaki, and L. Wang, “Preimages for stepreduced SHA-2.” in ASIACRYPT (M. Matsui, ed.), vol. 5912 of LNCS , pp. 578–
597, Springer, 2009.
5. K. Aoki, T. Ichikawa, M. Kanda, M. Matsui, S. Moriai, J. Nakajima, and T. Tokita,“Camellia: A 128-bit block cipher suitable for multiple platforms - design andanalysis.” in Selected Areas in Cryptography (D. R. Stinson and S. E. Tavares,eds.), vol. 2012 of LNCS , pp. 39–56, Springer, 2000.
6. E. Biham, A. Biryukov, and A. Shamir, “Cryptanalysis of Skipjack reduced to 31
rounds using impossible differentials.” in EUROCRYPT (J. Stern, ed.), vol. 1592
of LNCS , pp. 12–23, Springer, 1999.
7. E. Biham and A. Shamir, “Differential cryptanalysis of Snefru, Khafre, REDOC-II,
LOKI and Lucifer.” in CRYPTO (J. Feigenbaum, ed.), vol. 576 of LNCS , pp. 156–
171, Springer, 1991.
8. A. Biryukov and I. Nikolić, “Complementing Feistel ciphers.” in Pre-proceeding of
FSE’13 , LNCS, Springer-Verlag, 2013.
9. A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. B. Robshaw, Y. Seurin, and C. Vikkelsoe, “PRESENT: An ultra-lightweight block cipher.”in CHES (P. Paillier and I. Verbauwhede, eds.), vol. 4727 of LNCS , pp. 450–466,
Springer, 2007.
10. A. Bogdanov and C. Rechberger, “A 3-subset meet-in-the-middle attack: Cryptanalysis of the lightweight block cipher KTANTAN.” in Selected Areas in Cryptography (A. Biryukov, G. Gong, and D. R. Stinson, eds.), vol. 6544 of LNCS ,pp. 229–240, Springer, 2010.
11. A. Bogdanov and V. Rijmen, “Linear hulls with correlation zero and linear cryptanalysis of block ciphers.” IACR Cryptology ePrint Archive, vol. 2011, p. 123,2011.
12. J. Borghoff, A. Canteaut, T. Güneysu, E. B. Kavun, M. Knezevic, L. R. Knudsen,
G. Leander, V. Nikov, C. Paar, C. Rechberger, P. Rombouts, S. S. Thomsen,
and T. Yalçin, “PRINCE - a low-latency block cipher for pervasive computing
applications - extended abstract.” in ASIACRYPT (X. Wang and K. Sako, eds.),
vol. 7658 of LNCS , pp. 208–225, Springer, 2012.
13. C. Bouillaguet, P. Derbez, O. Dunkelman, N. Keller, V. Rijmen, and P.-A. Fouque,“Low data complexity attacks on AES.” IEEE Transactions on Information Theory, vol. 58, no. 11, pp. 7002–7017, 2012.
14. C. Bouillaguet, P. Derbez, and P.-A. Fouque, “Automatic search of attacks onround-reduced AES and applications.” in CRYPTO (P. Rogaway, ed.), vol. 6841
of LNCS , pp. 169–187, Springer, 2011.
15. C. Bouillaguet, O. Dunkelman, G. Leurent, and P.-A. Fouque, “Another look atcomplementation properties.” in FSE (S. Hong and T. Iwata, eds.), vol. 6147 of
LNCS , pp. 347–364, Springer, 2010.
16. C. D. Cannière, O. Dunkelman, and M. Knežević, “KATAN and KTANTAN - afamily of small and efficient hardware-oriented block ciphers.” in CHES (C. Clavier
and K. Gaj, eds.), vol. 5747 of LNCS , pp. 272–288, Springer, 2009.
17. A. Canteaut, M. Naya-Plasencia, and B. Vayssière, “Sieve-in-the-middle: Improved
MITM attacks.” in CRYPTO (1) (R. Canetti and J. A. Garay, eds.), vol. 8042 of
LNCS , pp. 222–240, Springer, 2013.

21

18. I. Dinur, O. Dunkelman, and A. Shamir, “Improved attacks on full GOST.” in
FSE (A. Canteaut, ed.), vol. 7549 of LNCS , pp. 9–28, Springer, 2012.
19. FIPS, “Data Encryption Standard.” Federal Information Processing Standards
Publication 46.
20. J. Guo, T. Peyrin, A. Poschmann, and M. J. B. Robshaw, “The LED block cipher.” in CHES (B. Preneel and T. Takagi, eds.), vol. 6917 of LNCS , pp. 326–341,
Springer, 2011.
21. T. Isobe, “A single-key attack on the full GOST block cipher.” J. Cryptology,
vol. 26, no. 1, pp. 172–189, 2013.
22. T. Isobe and K. Shibutani, “All subkeys recovery attack on block ciphers: Extending meet-in-the-middle approach.” in Selected Areas in Cryptography (L. R.
Knudsen and H. Wu, eds.), vol. 7707 of LNCS , pp. 202–221, Springer, 2012.
23. J. Jean, I. Nikolić, T. Peyrin, L. Wang, and S. Wu, “Security analysis of PRINCE.”
in Pre-proceeding of FSE’13 , LNCS, Springer-Verlag, 2013.
24. M. Knezevic, V. Nikov, and P. Rombouts, “Low-latency encryption - is “lightweight= light + wait”?.” in CHES (E. Prouff and P. Schaumont, eds.), vol. 7428 of LNCS ,pp. 426–446, Springer, 2012.
25. L. R. Knudsen, “DEAL - a 128-bit block cipher.” Technical Report 151, Universityof Bergen, Department of Informatics, Norway, Feb. 1998.
26. L. R. Knudsen and V. Rijmen, “Known-key distinguishers for some block ciphers.”
in ASIACRYPT (K. Kurosawa, ed.), vol. 4833 of LNCS , pp. 315–324, Springer,
2007.
27. J. Lu, Y. Wei, J. Kim, and P.-A. Fouque, “Cryptanalysis of reduced versions of
the Camellia block cipher.” in Pre-Proceedings of SAC’11 , 2011.
28. H. Mala, M. Shakiba, M. Dakhilalian, and G. Bagherikaram, “New results on
impossible differential cryptanalysis of reduced-round Camellia-128.” in Selected
Areas in Cryptography (M. J. Jacobson Jr., V. Rijmen, and R. Safavi-Naini, eds.),
vol. 5867 of LNCS , pp. 281–294, Springer, 2009.
29. C. Ohtahara, K. Okada, Y. Sasaki, and T. Shimoyama, “Preimage attacks on fullARIRANG: Analysis of DM-mode with middle feed-forward.” in WISA (S. Jungand M. Yung, eds.), vol. 7115 of LNCS , pp. 40–54, Springer, 2011.
30. J. Patarin, “Security of random Feistel schemes with 5 or more rounds.” in
CRYPTO (M. K. Franklin, ed.), vol. 3152 of LNCS , pp. 106–122, Springer, 2004.
31. Y. Sasaki, “Meet-in-the-middle preimage attacks on AES hashing modes and an
application to Whirlpool.” in FSE (A. Joux, ed.), vol. 6733 of LNCS , pp. 378–396,
Springer, 2011.
32. Y. Sasaki, “Preimage attacks on Feistel-SP functions: Impact of omitting the last
network twist.” in ACNS (M. J. Jacobson Jr., M. E. Locasto, P. Mohassel, and
R. Safavi-Naini, eds.), vol. 7954 of LNCS , pp. 170–185, Springer, 2013.
33. Y. Sasaki and K. Yasuda, “Known-key distinguishers on 11-round Feistel and collision attacks on its hashing modes.” in FSE (A. Joux, ed.), vol. 6733 of LNCS ,pp. 397–415, Springer, 2011.
34. K. Shibutani, T. Isobe, H. Hiwatari, A. Mitsuda, T. Akishita, and T. Shirai, “Piccolo: An ultra-lightweight blockcipher.” in CHES (B. Preneel and T. Takagi, eds.),
vol. 6917 of LNCS , pp. 342–357, Springer, 2011.
35. H. Soleimany, C. Blondeau, X. Yu, W. Wu, K. Nyberg, H. Zhang, L. Zhang, andY. Wang, “Reflection cryptanalysis of PRINCE-like ciphers.” in Pre-proceeding of
FSE’13 , LNCS, Springer-Verlag, 2013.
36. K. Suzuki, D. Tonien, K. Kurosawa, and K. Toyota, “Birthday paradox for multicollisions.” in ICISC (M. S. Rhee and B. Lee, eds.), vol. 4296 of LNCS , pp. 29–40,
Springer, 2006.

22