Security Evaluation of Block Ciphers AES, Camellia,
CLEFIA and SC2000 using Two New Techniques:
Biclique Attacks and Zero-Correlation Linear Attacks
Final Report
Version 1.0, November 2012
Andrey Bogdanov

Abstract. CRYPTREC is planning to update the current e-Government Recommended Ciphers List published in 2003 by March 2013. The candidate algorithms
for 128-bit block ciphers are AES, Camellia, CIPHERUNICORN-A, Hierocrypt-3,
SC2000, and CLEFIA. For this purpose, CRYPTREC aims to have the securityof these algorithms reevaluated using some novel techniques of cryptanalysis.
The document deals with two new techniques of symmetric-key cryptanalysis:
biclique-based MITM cryptanalysis and zero-correlation linear cryptanalysis thathave recently turned out to be capable of attacking stronger ciphers than previously believed. We concentrate on block ciphers AES, Camellia, CLEFIA and
SC2000 here. More specifically, we evaluate AES, Camellia, CLEFIA and SC2000
with respect to biclique-based MITM cryptanalysis as well as Camellia and CLEFIA with respect to zero-correlation linear cryptanalysis.
We conclude that all for all full ciphers in question AES, Camellia, CLEFIAand SC2000 applying exhaustive MITM attacks can reduce the complexity of key
recovery with respect to brute force. Zero-correlation linear cryptanalysis turns
out applicable to round-reduced variants of Camellia and CLEFIA.
Keywords: AES, Camellia, CLEFIA, SC2000, biclique cryptanalysis, zero-correlation
linear cryptanalysis
Acknowledgements. This work was supported in part by the Cryptography
Research and Evaluation Committees (CRYPTREC). I would like to thank Meiqin
Wang for her kind permission to include some of the results on zero correlationfrom our unpublished joint work into this report.

1
1.1

Short Specifications of Ciphers
AES-128

For the sake of clarity, we will be trying to reuse as much notation as possible
from [13] – the work introducing biclique cryptanalysis for block ciphers andapplying it to AES. This also applies to the notations regarding the descriptionof AES-128.
AES-128 is a block cipher with 128-bit internal state and 128-bit key K. Theinternal state is represented by a 4×4 byte matrix, and the key is represented by a
4 × 4 matrix. The plaintext is xored with the key, and then undergoes a sequenceof 10 rounds. Each round consists of four transformations: nonlinear bytewise
SubBytes, the byte permutation ShiftRows, linear transformation MixColumns,
and the addition with a subkey AddRoundKey. MixColumns is omitted in thelast round.
SubBytes is a nonlinear transformation operating on 8-bit S-boxes. The operation ShiftRows rotates bytes in row r by r positions to the left. The MixColumns
is a linear transformation with branch number 5, i.e. in the column equation(y0 , y1 , y2 , y3 ) = M C(x0 , x1 , x2 , x3 ) only 5 and more variables can be non-zero.
We address two internal states in each round as follows: #1 is the state before
SubBytes in round 1, #2 is the state after MixColumns in round 1, #3 is thestate before SubBytes in round 2, . . ., #19 is the state before SubBytes in round
10, #20 is the state after ShiftRows in round 10.
The key K is expanded to a sequence of keys K 0 , K 1 , K 2 , . . . , K 10 , which
form a 4 × 60 byte array. Then the 128-bit subkeys $0, $1, $2, . . . , $14 come outof the sliding window with a 4-column step. The keys in the expanded key areformed as follows. First, K 0 = K. Then, column 0 of K r is the column 0 of K r−1
xored with the nonlinear function (SK) of the last column of K r−1 . Subsequently,
column i of K r is the xor of column i − 1 of K r and of column i of K r−1 .
1.2

Camellia

Camellia [1] is a block cipher designed by researchers from Mitsubishi and NTT.
It is part of the ISO/IEC encryption mechanisms as well as NESSIE and CRYPTREC portfolios. The block size of Camellia is 128 bits. The key size of Camellia
is either 128, 192, or 256 bits. Thus, the interfaces are compatible to those of
AES.
Camellia is a balanced Feistel network of 24 rounds organized as 3 blocks of 6
rounds for Camellia-128 and 4 blocks of 6 rounds for Camellia-192 and Camellia256. The 6-round blocks are separated by the applications of F L and F L−12

K2

whiteningfull roundfull round

K9

...

K 10

last roundK1

full roundK0

whitening:
0

Kfull round:m0 m4 m8 m12

u0

u4

u8 u12n0

n4

n8 n12

u1

u5

u9 u13n1

n5

n9 n13m2 m6 m10 m14

u2

u6 u10 u14n2

n6 n10 n14n10 n14 n2 n6

m3 m7 m11 m15

u3

u7 u11 u15

n3

n7 n11 n15

n15 n3 n7 n11

m0 m4 m8 m12

u0

u4

u8 u12u0

u4 u8 u12

m1 m5 m9 m13

u1

u5

u9 u13u5

u9 u13 u1m2 m6 m10 m14

u2

u6 u10 u14

u10 u14 u2

m3 m7 m11 m15

u3

u7 u11 u15

u15 u3

m1 m5 m9 m13

SB

MC

SR

last round:

SB

SR

Kr

u6

u7 u11

SB : ui = S(mi )M C : (n4j , n4j+1 , n4j+2 , n4j+3 )T = M · (u4j , u4j+1 , u4j+2 , u4j+3 )TK r−1,0

K r−1,1

K r−1,2

K r−1,3

S

S

S

RCr

K r,0

K r,1

K r,2

K r,3

Fig. 1. AES-128
3

S

n0

n4

n8 n12n5

n9 n13 n1Krfunctions on the left-hand and right-hand halves of the Feistel state, correspondingly. Before the first 6-round block and after the last 6-round block whitening
keys are added. The F-function maps 64 bits to 64 bits. The input is divided into
8 bytes. Each byte is first added with the corresponding byte of the expanded key
and then is passed through an 8-bit S-box. This is followed by a simple diffusion
layer which can be described as a multiplication by a binary matrix over the fieldof 256 elements. The F L/F L−1 functions linear in the data input (consisting ofshifts and XORs) but are nonlinear in the key input, it being introduced per
bitwise AND and OR. See Figure 2.
1.3

CLEFIA

CLEFIA [69] is a 128-bit block cipher with its key length being 128,192 and 256
bits, which is compatible to AES. It employs a generalized Feistel structure withfour data lines, and the width of each data line is 32 bits. Additionally, there are
key whitening parts at the beginning and the end of the cipher. The numbersof rounds of CLEFIA are 18, 22 and 26 for 128-bit, 192-bit and 256-bit keys,
respectively.
The F -function inside the GFN structure bears similarities to the buidling
blocks of AES: an addition of 4 key bytes (RKi ) to the input is followed 4 8bit S-boxes and a matrix-vector multiplication using a 4x4 MDS matrix (branchnumber 5) over bytes. Before the first round and after the last round, prewhitening
and postwhitening is applied. See Figure 3 for an illustration.
1.4

SC2000SC2000 [68] is a block cipher designed by Fujitsu. It was considered by the
NESSIE project, which did not result in a selection though. SC2000 is part of
the CRYPTREC portfolio. The key size of SC2000 is 128, 192, or 256 bits andthe block size of SC2000 is 128 bits. Thus, its interfaces are compatible to thoseof AES.
The round transform can be outlined in the following way. In a round, addition with subkey (I function) is followed by a layer of 4-bit S-boxes (B function)and by another addition with subkey (I function again). Then a round of balanced Feistel-type transform (R function) is applied with an unkeyed F-function
consisting of a layer of 5-bit and 6-bit S-boxes followed by a linear transform (superposition of a M and L), the swap of state halves (cross connection ×) and by
the Feistel-type transform of R function again. The number of rounds is either
6.5 (for SC2000-128) or 7.5 (for SC2000-192 and SC2000-256). Where the last
half round consists of functions I, B and I only, omitting the R function.

4

k w1

K

S

P

k w2

K

S

P

K

S

6 rounds

P

K

S

P

K

S

P

K

S

P

FL

F L−1

6 rounds

FL

F L−1

kL

6 rounds

FL

!

FL
<<<1

F L−1

!

kR

!

kR

6 rounds

F L−1

k w3

k w4

kL

!

Fig. 2. Camellia-192/256

5

<<<1

RK0

RK1

W K0

F0

F1

RK2

RK3

F0

F1

RK4

RK5

F0

F1

W K1

...
RK2r−6

RK2r−5F0F1RK2r−4RK2r−3F0F1RK2r−2RK2r−1

F0

F1
W K3

W K2

Fig. 3. CLEFIA

6

I function(key addition)

B function(4-bit S-box layer)

I function(key addition)

M

s6
s5
s5
s5
s5
s6

M

s6
s5
s5
s5
s5
s6

L

R function

R function

Fig. 4. SC2000

2

Basic Techniques

Block ciphers are essential to cryptography, both theoretically and practically.
Most bulk encryption and data authentication performed in the field relies on an
efficient block cipher, which is employed after the key has been negotiated in asecurity protocol. The introduction of cryptanalytic techniques that are based on
new principles is a rather rare event in the area of block ciphers. Recently, two newtechniques have been proposed for block ciphers: bicliques and zero correlation.
We start with a brief introduction in the context of these techniques.
2.1

Bicliques

Today, the most frequently used block cipher is AES (Advanced Encryption Standard) [29] — the current U.S. encryption standard selected by NIST in an open
competition. AES is the only publicly known cipher that is NSA-approved for protecting secret and top secret government information in the U.S. Recently, thetheoretical security of AES has been challenged by biclique cryptanalysis [13].
Biclique key recovery is based on the meet-in-the-middle approach at its core but
borrows an important twist – initial structures – from the domain of hash function
cryptanalysis. Namely, biclique cryptanalysis uses the fact that, for some cipherssuch as AES, the adversary can efficiently prepare structures of internal states

7that cover many keys. The work [13] scrutinizes the notion of initial structures
for block ciphers and formalizes it to bicliques (complete bipartite graphs) which
are especially efficient to construct. As a result, the authors of [13] propose key
recovery on all three variants of the full AES with computational complexities
below brute force, though rather high data complexities. It works in the standard
single secret key model. Biclique cryptanalysis has been successfully applied to
AES resulting in key recovery faster than brute force. For AES-128, the best
attack so far has computational complexity 2126.16 and data complexity 288 .
Biclique key recovery may be considered as an advance in the field of symmetrickey cryptography but it has been prepared by a considerable number of works inthe area of meet-in-the-middle (MITM) attacks on block ciphers [15,22,23,34,39]
and hash function cryptanalysis [2, 3, 38] including the introduction of initialstructures [65] and bicliques for preimage search in hash functions [45]. Since theintroduction of bicliques, an entire line of research emerged aiming to apply thetechnique to various block ciphers [26, 40, 44, 59, 75].
Here we provide a brief overview of the existing biclique techniques as applied
to AES.
Biclique-based preimage finding for hash was proposed in [45] by scrutinizing the concept of initial structures introduced in [65]. Biclique cryptanalysis for
ciphers was proposed by [13] in two different paradigms: independent-bicliqueand long-biclique approaches. It is the independent-biclique technique that has
resulted in key recovery for full AES. For the purposes of this report, we will
be focusing on independent bicliques. Correspondingly, for simplicity of presentation, the description of biclique techniques in the sequel is explicitly tailored toindependent-bicliques for AES-128. For a general introduction into bicliques, werefer to [13].
In the key recovery procedure of independent-biclique cryptanalysis for AES128, the entire space of 2128 keys is divided into non-overlapping groups of keys.
In each group of keys, every key is tested using MITM techniques faster thanwith one AES computation. This accounts for the computational advantage ofthe technique over brute force.
Balanced bicliques. Each group of keys has the structure of a biclique – acomplete bipartite graph. A biclique consists of two sets Sx and Sy of intermediate
cipher states (two disjoint sets of vertices of the biclique) and a set of keys K whichmaps each element in one set of states to each element in the other one (edges ofthe biclique).
In the standard independent-biclique cryptanalysis, the biclique is definedsuch that each set of states has |Sx | = |Sy | = 2d elements and the set of keys

8

contains |K| = 22d keys, which actually corresponds to a balanced biclique – abiclique whose vertex sets have equal cardinalities. The structure of the (balanced)
biclique is shown in Figure 8. To fix the notation, we denote Sx = {xj }, Sy = {yi },and K = {K[i, j]} with i, j ∈ {0, 2d − 1}. d is called the biclique dimension.
x0x1x2d −1...

K[2d − 1, 2d − 1]

K[0, 0]

...
y0

y1

y2d −1

Fig. 5. Balanced biclique of dimension d

Bicliques via independent differentials. So far the most efficient way ofbuilding bicliques for AES is from independent related-key differentials. Consider
two families of related-key differentials over the rounds covered by biclique (fromvalues xj to yi ): 2d − 1 distinct ∆-differentials(0, ∆Ki ) 7−→ ∆iwith input state difference 0, input key difference ∆K
i and output state differenced∆i as well as 2 − 1 distinct ∇-differentials(∇j , ∇Kj ) 7−→ 0with input state difference ∇j , input key difference ∇Kj and output state difference 0. Now we assume that the ∆- and ∇-differentials do not share any active
nonlinear components (S-boxes in the case for AES). Then, it has been shownin [13] that if input x0 , output y0 and key K[0, 0] conforms to both ∆- and∇-differentials, then the values
xj = x0 ⊕ ∇ j ,y i = y 0 ⊕ ∆i ,K
K[i, j] = K[0, 0] ⊕ ∇Kj ⊕ ∆i9

Kform a balanced biclique of dimension d, with ∆0 = ∇0 = ∆K
0 = ∇0 = 0. The
computation over the biclique rounds from input x0 to output y0 with key K[0, 0]
is called the base computation. K[0, 0] is called the base key.
For AES-128, the work [13] provides an 8-dimensional biclique over 2.5 lastrounds. That is, the vertex set Sy of the biclique coincides with the set of ciphertexts in the given key group. This biclique is illustrated in Figure 6.

base
computation∆-differentials∇-differentials

Step 2. Add ∆i to the key
x0

xj , #15

x0
SB
SR
MC

SB
SR
MC

SB
SR
MC

∆K
i

∇K
j

#16

SB
SR
MC

key schedule

key schedule

key schedule

$8

SB
SR
MC

#17
SB
SR
MC
#18

SB
SR

key schedule

key schedule

key schedule

$9

SB
SR

#19
SB
SR
#20

$10
yi

y0

y0

Step 1. Start with y0 = 0
Step 3. Add ∇j to the key

Fig. 6. Biclique over 3 last rounds of AES-128 from independent differentials [13]Key recovery. For AES-128, the entire space of 2128 keys is divided into 2112
non-overlapping groups (bicliques) of 22d = 216 keys each. In each biclique, thebase key is fixed.
Now a meet-in-the-middle key recovery with partial matching (in one intermediate state byte) and splice-and-cut technique (going over the decryption oracle
from the generated ciphertexts to the corresponding plaintexts) is applied. For

10each combination of xj and yi (corresponding to K[i, j]), it is tested if there is amatch.
For each biclique, the computational complexity consists of the complexity
Cprecomp of preparing ∆- and ∇-propagations (including preparing the biclique),the complexity Crecomp of recomputing states for each key K[i, j], and the complexity Cf alsepos of checking the key candidates surviving the partial matching:
Cf ull = 2128−2d (Cprecomp + Crecomp + Cf alsepos ).
The computational complexity is dominated by Crecomp . The data complexity isdetermined by the number of state differences ∆j in all key groups, since theciphertext of the base computation remains the same in all key groups.
As regards Crecomp , most computational advantage over brute force originatesfrom the fact that the adversary saves the computation of the 3 (strictly speaking,
only 2.5 rounds, since MixColumns is omitted in the final round) last rounds of
AES-128. In fact, using about 28 partial evaluations of the cipher and some minor storage for ∆- and ∇-trails, one covers 216 combinations of xj and yi (keys).
Another part of computational advantage comes from the partial matching procedure that allows one to save almost 1.5 more rounds of computations. Finally,
the intermediate states xj do not diffuse too fast under K[i, j] in the backward
direction. Also the plaintexts obtained from ciphertext yi using the decryption
oracle with the right key E −1 (yi ), do not diffuse immediately under K[i, j]. This
allows the adversary to save more than one round of computations on top of that.
Combining all this yields a computational complexity of 2126.16 and a data
complexity of 288 chosen ciphertexts. Since the adversary cannot reject the right
key, the success probability is 1.
2.2

Zero Correlation

For the security evaluation of block ciphers, numerous techniques have been proposed over the last decades. However, although various attacks, in particulardifferential cryptanalysis and linear cryptanalysis and their variants, have been
extensively studied, new interesting results are still being discovered. Among others, the fact that zero-correlation linear cryptanalysis [18, 19] has been proposed
only very recently – while impossible differential cryptanalysis [7, 20] (its counterpart in the domain of differential cryptanalysis) has been known for about 15
years now – speaks for itself.
Zero-correlation cryptanalysis [18] is a novel promising attack technique forblock ciphers. The distinguishing property used in zero-correlation cryptanalysis
is the existence of zero-correlation linear approximations over (a part of) the11cipher. Those are linear approximations that hold true with a probability p ofexactly 1/2, that is, strictly unbiased approximations having a correlation c =2p − 1 equal to 0. This gives the adversary the possibility to gain informationfrom perfectly uncorrelated events.
We use the state-of-the-art techniques [?, 19] of zero correlation to decrease
the data complexity, in our cryptanalysis of Camellia, CLEFIA, that allow one totake advantage of a maximum number of zero-correlation linear approximations
available without relying unnecessary assumptions.
Linear approximations with correlation zero Zero correlation linear cryptanalysis has been introduced in [16]. Below we briefly review its basic ideas andmethods.
Consider an n-bit block cipher fK with key K. Let P denote a plaintext which
is mapped to ciphertext C under key K, C = fK (P ). If ΓP and ΓC are nonzero
plaintext and ciphertext linear masks of n bit each, we denote by ΓP → ΓC thelinear approximation
ΓPT P ⊕ ΓCT C = 0.
Here, ΓAT A denotes the multiplication of the transposed bit vector ΓA (linear mask
for A) by a column bit vector A over F2 . The linear approximation ΓP → ΓC has
probability(1)pΓP ,ΓC = Prn {ΓPT P ⊕ ΓCT C = 0}.
P ∈F2

The valuecΓP ,ΓC = 2pΓP ,ΓC − 1(2)

is called the correlation (or bias) of linear approximation ΓP → ΓC . Note thatpΓP ,ΓC = 1/2 is equivalent to zero correlation cΓP ,ΓC = 0:pΓP ,ΓC = Prn {ΓPT P ⊕ ΓCT C = 0} = 1/2.
P ∈F2

(3)

In fact, for a randomly drawn permutation of sufficiently large bit size n, zerois the most frequent single value of correlation for a nontrivial linear approximation. Correlation goes to small values for increasing n, the probability to get
exactly zero decreases as a function of n though. More precisely, the probabilityof the linear approximation ΓP → ΓC with ΓP , ΓC 6= 0 to have zero correlation
can be approximated by
1 4−n√ 2 2 .
(4)2π

12Two examples Given a randomly chosen permutation, however, it is hard totell a priori which of its nontrivial linear approximations in particular has zero correlation. At the same time, it is often possible to identify groups of zerocorrelation linear approximations for a block cipher fK once it has compact description with a distinct structure. Moreover, in many interesting cases, theselinear approximations will have zero correlation for any key K. Here are two
examples:– AES: The data transform of AES has a set of zero correlation linear approximations over 4 rounds (3 full rounds appended by 1 incomplete rounds with
MixColumns omitted). If Γ and Γ ′ are 4-byte column linear masks with exactly one nonzero byte, then each of the linear approximations (Γ, 0, 0, 0) →(Γ ′ , 0, 0, 0) over 4 AES rounds has zero correlation.
– CLEFIA-type GFNs: CLEFIA-type generalized Feistel networks (also known
as type-II GFNs with 4 lines) have zero correlation linear approximations
over 9 rounds, if the underlying F-functions of the Feistel construction are
invertible. For a 6= 0, the linear approximations (a, 0, 0, 0) → (0, 0, 0, a) and(0, 0, a, 0) → (0, a, 0, 0) over 9 rounds have zero correlation.
plaintext P

partial encryption
E

check for zero correlation

rounds covered byzero correlation
linear approximation

D

partial decryption

ciphertext C

Fig. 7. High-level view of key recovery in zero correlation linear cryptanalysis

13Key recovery with zero correlation linear approximations Based on linear approximations of correlation zero, a technique similar to Matsui’s Algorithm 2 can be used for key recovery. Let the adversary have N known plaintextciphertexts and ℓ zero correlation linear approximations {ΓE → ΓD } for a partof the cipher, with ℓ = |{ΓE → ΓD }|. The linear approximations {ΓE → ΓD } areplaced in the middle of the attacked cipher. Let E and D be the partial intermediate states of the data transform at the boundaries of the linear approximations.
Then the key can be recovered using the following approach (see also Figure 7):
1. Guess the bits of the key needed to compute E and D. For each guess:(a) Partially encrypt the plaintexts and partially decrypt the ciphertexts up
to the boundaries of the zero correlation linear approximation ΓE → ΓD .

(b) Estimate the correlations {ĉΓE ,ΓD } of all linear approximations in {ΓE →ΓD } for the key guess using the partially encrypted and decrypted values E and D by counting how many times ΓET E ⊕ ΓDT D is zero over N
input/output pairs, see (1) and (2).

(c) Perform a test on the estimated correlations {ĉΓE ,ΓD } for {ΓE → ΓD } totell of the estimated values of {ĉΓE ,ΓD } are compatible with the hypothesisthat all of the actual values of {cΓE ,ΓD } are zero.
2. Test the surviving key candidates against a necessary number of plaintextciphertext pairs according to the unicity distance for the attacked cipher.
Step 1(c) of the technique above relies on an efficient test distinguishing between the hypothesis that {cΓE ,ΓD } are all zero and the alternative hypothesis.
The work [16] requires the exact evaluation of the correlation value (defined by
the probability of a linear approximation) and the data complexity is restricted
to N = 2n in [16]. Thus, a small number ℓ of linear approximations is usually enough in [16] and ĉΓE ,ΓD = cΓE ,ΓD , though the data complexity of the fullcodebook is too restrictive.
For most ciphers (including the examples of Subsection 2.2), however, a large
number ℓ of zero correlation linear approximations is available. This freedom
is not used in [16]. At the same time, it has been shown in the experimental
work [27] that any value of correlation can be used for key recovery in a linear attack with reduced data complexity, once enough linear approximations areavailable. Despite its convincing experimental evidence, [27] gives no theoretical
data complexity estimations and does not provide any ways of constructing linear
approximations with certain properties.

14

3
3.1

New Techniques
Stars

For the purposes of this analysis, we propose to use stars (unbalanced bicliques
which are trees with one node and many leaves) for low data complexity key
recovery. Those are unbalanced bicliques which are trees with one node and many
leaves – for the analysis of block ciphers. We further apply this concept to discovera star-based independent-biclique key recovery for the full AES-128 which requires
only one or two known plaintext-ciphertext pairs and works with computational
complexity 2126.7 .
3.2

The concept of stars

We start with the observation that the biclique does not have to be balanced –i.e. contain 2d states in each of its two vertex sets – to cover 22d keys. Indeed,
there is a biclique with just one state in one vertex set and 22d states in the otherone: Sx = {x}, Sy = {yi,j }, i, j ∈ {0, 2d − 1}, where each yi,j is obtained byencrypting x with key K[i, j], covering 22d keys. This biclique is called a star of
dimension d.
x

K[2d − 1, 2d − 1]

K[0, 0]

...
y0,0

y0,1

y2d −1,2d −1

Fig. 8. Star: maximally unbalanced biclique of dimension d for the minimum data
complexity
Now, if we place the star at the beginning of the cipher, and let x be theplaintext (or ciphertext) the data complexity of the MITM part of the key recovery will be exactly 1. Note that x can be any value and, thus, we deal witha known-plaintext key recovery here. The overall data complexity will be solely
defined by the unicity distance of the cipher and, therefore, minimal theoreticallyattainable.

15

3.3

Stars from independent differentials

Similarly to balanced bicliques, stars can be constructed efficiently from independent sets of differentials. Unlike balanced bicliques, however, the necessary formof differentials is different. Suppose we have a set of 2d − 1 distinct related-key∆-differentials from x to yi,j :(0, ∆Ki ) 7−→ ∆iand a set of 2d − 1 distinct related-key ∇-differentials from over the same part ofthe cipher:(0, ∇Kj ) 7−→ ∇j .
We assume that the ∆-differentials and ∇-differentials do not share any active
nonlinear components. If input x, output y0,0 and key K[0, 0] conform to both∆- and ∇-differentials, then the values
xyi,j = y0,0 ⊕ ∆i ⊕ ∇j , andK
K[i, j] = K[0, 0] ⊕ ∆Ki ⊕ ∇jKform a star of dimension d, with ∆0 = ∇0 = ∆K
0 = ∇0 = 0.

4
4.1

Improved Biclique Cryptanalysis of AES
Introduction

Today, the most frequently used block cipher is AES (Advanced Encryption Standard) [29] — the current U.S. encryption standard selected by NIST in an open
competition. AES is the only publicly known cipher that is NSA-approved forprotecting secret and top secret government information in the U.S.
The original work [13] introducing biclique key recovery leaves several questions unanswered though, which are crucial to judging about the real-world security of AES and implications of the biclique cryptanalysis in general:– Is there much potential in minimizing the data complexity of the biclique attacks? In fact, it is low data complexity attacks that are most relevant inpractice, especially in the context of efficient implementation of the attacks –the point clearly made in [12]. Actually, the data complexity of the original
biclique attacks makes any practical implementation of them highly unreasonable since the standard brute force is very likely to be both cheaper andfaster in reality (mainly due to the high requirements in terms of storage ororacle access).

16

– Though the new technique has been coined after bicliques, the initial structures are explicitly limited to balanced bicliques only, i.e. complete bipartite
graphs the two set of vertices of which have exactly the same cardinality. So
the question remains: Can one take any advantage of using other types ofbicliques as initial structures?
– Finally, no comprehensive investigation of attack optimality in terms of computational complexity, data complexity or both has been performed. So it isstill not clear if there are faster biclique attacks, even in the same class of theattacks as proposed in [13].
In this report, we aim to bridge these gaps and answer all three questions in
the positive for the case of AES-128:– As regards more general initial structures, we drop the balancedness requirement for bicliques. We propose to use stars, which are the most unbalanced
bicliques, having only one vertex in one of the two disjoint sets of biclique vertices (see Section 3.1). This allows us to come up with a star-based biclique
key recovery technique for block ciphers that inherently has the minimal theoretically attainable data complexity – the one due to the unicity distance.
– In terms of the attack space exploration for biclique cryptanalysis, we limit ourselves to the most promising class of attacks as applied to AES-128:
Namely, we enumerate all truncated independent balanced bicliques and stars
whose key modification trails have a single active byte in some state of the
expanded key. For the sake of conciseness, we will refer to this class of attacks as based on tight truncated independent bicliques and stars (see Subsection 4.2). Clearly, this exploration does not cover many advanced and inherently harder-to-analyze attack vectors such as long-bicliques (bicliques ofa lower dimension whose key modification differentials share active S-boxes)
or narrow bicliques [44]. That is why, one cannot claim any formal bounds onthe complexity of biclique attack complexity in general.
Nonetheless, it is the tight truncated independent-biclique approach to key
recovery that has resulted in the fastest attack on the full AES-128 so far,though requiring a part of the state to be recomputed for each key. However,
we believe that this investigation does provide important new insight into
the limits of the current techniques of biclique cryptanalysis when applied to
AES-128.
– Using stars as initial structures, we propose the first key recovery on AES-128
with the minimal theoretically possible data complexity and faster than brute
force. It requires 1 or 2 known plaintexts and has computational complexity 2126.7 (Subsection 4.3). Note that this computational complexity is only
slightly higher than that of the original attack (of computational complexity172126.16 and data complexity 288 ). Moreover, both the time and data complexities of this new attack are actually lower than those of the attack in [12](requiring 2128.9 time and 24 chosen plaintexts).
– Next, we exhaustively enumerate all attacks based on tight truncated independent bicliques and stars for AES-128 which have a data complexity lower
than the full codebook. It turns out that among them the ones of computational complexity 2126.16 are fastest. Interestingly, this exactly corresponds
to the original key recovery on AES-128 [13]. We further investigate the data
complexity of these attacks for the biclique dimension d = 8 and show that theminimum data complexity is 264 (cf. 288 in the original attack). This implies
that the original attack did not have the optimal data complexity.
– To investigate the limits of this class of biclique cryptanalysis, we abandon
all restrictions on the data complexity and search for the fastest attack on
AES-128 in this class. We find that the one with computational complexity
2125.6 is fastest (though requiring the full code book). It is interesting that
this attack is based on independent-bicliques of length of 3 full AES rounds.
This is the longest independent-biclique constructed so far for AES-128.
With respect to AES-128, the cryptanalytic results of the report are summarized in Table 1.
Table 1. Secret key recovery with bicliques for full AES-128 (10 rounds)
data
88

computations memory success prob biclique length (rounds)

property shownreference

2.5

-

[13]

2

-

[12]

126.162

82

1288 CP

2126.89

28

1Unic. dist: 1 or 2 KP

126.7

2

8

2

1

1

fastest with minimum data Subsection 4.3

264 CC

2126.16

28

1

2.5

fastest with < 2128 data

Subsection 4.4

2128

2125.628

1

3

fastestSubsection 4.4

2

CC

4.2

A search tool for biclique attacks on AES-128

In this section, we describe how we enumerate all biclique key recoveries in alarge promising class of biclique attacks.
Enumerating bicliques. Clearly, going over all possible initial structures, even
without enumerating possibilities for the actual key recovery, would be infeasible
for the AES. So we have to confine the search space of attacks by imposing

18

some limitations. In here, we describe the search space along with the respective
justifications:– First, we consider bicliques (complete bipartite graphs) as initial structures.
We stress that we include both balanced bicliques and stars in our search,
unlike the attacks of [13] and [12] that consider only balanced bicliques.
– Second, we restrict the search to independent-bicliques only. Those are exactly the bicliques that can be constructed from independent related-key differentials, that is, related-key differentials that do not share active non-linear
components. The principle of independent-biclique construction is describedin Subsection 2.1.
This constraint excludes such bicliques as long-bicliques [13] and narrowbicliques [44], which are especially challenging to enumerate. However, though
not optimal in the number of rounds covered, it is the independent-bicliquesthat attain the highest advantages over brute force for full AES-128 so far.
– Third, for AES-128, we confine the search to independent related-key differentials that have a key state in their trails with exactly one active byte. Notethat this byte does not have to be the byte where the key difference is injected and the key difference still can be injected in multiple bytes. Actually, thebest biclique key recoveries on AES-128 proposed so far are based on suchbicliques.
– Finally, to keep the search space from exploding, we have to consider the
trails of the bilciques in a truncated manner: We do not differentiate between
the active values of the key modification trails in our bicliques (values ofdifferences in the related-key differentials). In particular, this means that, once
activated, a difference in a byte of a trail cannot be cancelled out. This is asignificant but necessary limitation since we believe it is infeasible to run theexhaustive search otherwise, for excessively high computational complexities.
We implement these restrictions in a C program and are able to successfully
enumerate all tight truncated independent balanced bicliques and stars of AES128 within a very limited time on a standard PC.
Searching for key recoveries. Having enumerated all the bilciques as describedabove exhaustively, we apply MITM techniques to each of the obtained initialstructures to evaluate their time and data complexities. This is done as follows.
First of all, we set the optimization goal as minimizing the time complexity
for a given data complexity restriction. That is, in each search for a key recovery,
we fix an upper bound on the data complexity. Then we perform the exhaustive
search over all possibilities for matching. In terms of key enumeration, we impose

19the restriction that the forward and backward key modifications should have atleast one state of linear intersection. This stipulates the full key space coverageand success probability of 1. The MITM techniques used include partial matching(the matching is performed on a byte of the state to save computations) and the
cut-and-splice technique (so that trails can go over the encryption/decryption
oracles to win degrees of freedom).
To evaluate the time complexity of a key recovery efficiently on-the-fly, thetool uses the computational model proposed in [13]: All linear operations (AddRoundKey, ShiftRows, and MixColumns) are ignored and one counts only the
number of S-box computations that have to be performed. One full AES-128 computation is, thus, equivalent to 200 S-box computations – a metric that proved
to be meaningful in practice [12]. The evaluated time complexity is output in thenumbers of S-box computations that have to be performed per key tested. Again,
this is the parameter that has lead to the fastest attacks so far since it makes the
key group larger and minimizes the impact of biclique construction on the total
complexity.
Depending on the data complexity restriction, the tool can find the optimal
attack (the attack with lowest evaluated time complexity under the data complexity restriction) within a very limited lime on our PC.
As a second optimization goal, we have minimizing the data complexity for agiven time complexity. This second optimization is applied once a key recovery
has been found in the previous step. At this point, we already know that there areno faster key recoveries in our search space. So we check if the data complexity of
the fastest attack identified can be reduced. This task typically requires much lesscomputations and can usually be completed within an hour on our computational
platform.
Applications to find attacks with minimal data and time complexities.
We applied the tool to search for three data complexity restrictions:– Minimum data complexity: In fact, the minimum data complexity attack of
Subsection 4.3 was discovered using this tool by setting the upper bounds ofthe key recovery to its theoretical minimum of the unicity distance. So we
can claim that this is the fastest biclique key recovery with the minimal data
complexity of exactly the unicity distance in the class of biclique and key
recoveries covered by our tool. To recall its details, this key recovery requires
2126.7 time and 1 or 2 KPs of data. Note that the tool suggests that going fora star as the initial structure is optimal in this case.
– Data complexity strictly lower than the full codebook: This restriction is astandard line that is informally drawn between interesting attacks – that20

require less that the full codebook of texts - and less interesting attacks – thatcan only work with the full codebook. The tool demonstrates that the fastest
biclique key recoveries in the covered class with these restrictions require
2126.16 time. Optimizing for data complexity among all attacks with this timecomplexity yields that the lowest data complexity is 264 CCs. This attack issummarized in Subsection 4.4. This attack is based on a balanced biclique ofthe exactly same lenth as the AES-128 biclique of [13]. However, the form of
the biclique in [13] was not optimal in terms of data complexity.
– No data complexity constraint: The tool finds that the fastest biclique key
recovery in the entire class of biclique attacks covered is the one requiring
2125.6 time and the full codebook of data. This attack provides an important
insight into the limits of the independent-biclique approach as developed sofar. This attack is outlined in Subsection 4.4 and relies on balanced bicliques.
4.3

Minimum data complexity key recovery for AES-128

Stars of dimension 8 over 1 round of AES-128 In AES-128, it is possible
to construct a star of dimension 8 over the first round. ∆-trail activates byte 0 of
key $0. ∇-trail activates byte 1 of key $0, see Figure 9(a). Difference propagationin those differentials over one round is non-overlapping till the end of round 1.
In state #4, there is a linear overlap between those and, already in round 2, one
has to recompute 2 S-boxes for each key. See Figure 9(a).
Rather surprisingly, even if the length of the star is just one round, the formof its trails is such that this short biclique still allows the adversary to obtain areasonable computational advantage over brute force.
Key enumeration. We define the 2112 groups of keys with respect to $0, i.e.
the first subkey which equals the master key. The base keys are all keys of the
form
0
0

,
where bytes 0 and 1 are fixed to zero. The other 14 bytes are fixed anew for eachkey group. The keys in each group are enumerated with respect to the base key
by applying difference:ij,which yields 216 keys in a group.

21

Step 3. Add ∇K
j to the key
Step 2. Add ∆K
i to the key
Step 1. Start with fixed x

∆K
i

x

∇K
j

x

P

SB
SR
MC

#1, x

key schedule

key schedule

key schedule

$0

SB
SR
MC

SB
SR
MC
#2

$1
yi

star &

#13

#12

MC
SR
SB

#14

AK

#15

MC
SR
SB

∇-differentials

AK

#16

MC
SR
SB

#17

AK

#18

MC
SR
SB

#19

AK

SR
SB

#20

∆-differentials(a) Star over the first roundenc oracle

CT

AK

base
computation

#3

#11

matching byte

recomputed

$10

$9

#10

AK

#9

SB
SR
MC

#8

AK

#7

SB
SR
MC

#6

AK

#5

SB
SR
MC

#4

AK

star

#3

SB
SR
MC

(b) Recomputation backwards#11matching byte

recomputed(c) Recomputation forwards

Fig. 9. Fastest biclique attack on AES-128 with minimum data: time 2126.7 anddata 1 or 2 KPs

Matching and recomputations. In the forward direction of matching, startingin round 2, a part of the state has to be recomputed for each key. In round 2,
only 2 S-boxes have to be recomputed. Starting in round 3 and forwards, thepropagation affects the whole state. See Figure 9(c).
In the backward direction of matching, one starts with the ciphertext obtainedusing the encryption oracle under the right key for plaintext x. The ∆- and ∇propagations in the key schedule are such that only 5 bytes of the $10 depend on
both ∆ and ∇. This means that only 5 S-boxes have to be recomputed in round2210. Starting in round 9 and backwards, the propagation affects the full state. See
Figure 9(b).
We match on byte 12 in state #11 of round 5, in which only one S-boxes
need recomputation. In round 4 and round 6, only 4 S-boxes, respectively, arerecomputed. The S-boxes in the four remaining rounds need to be recomputed
completely (another 64 S-boxes). No S-box recomputations are needed in the keyschedule.
Complexities. The matching yields a recomputation of 80 out of 200 S-boxes.
Thus, Crecomp ≈ 214.678 in one key group. About 28 keys will be suggested ineach key group and need to be tested on more bytes of matching. This requires
at most 4 S-boxes to be recomputed in both rounds 4 and 6 as well as 1 S-box inround 5, i.e. at most Cf alsepos ≈ 23.526 . The complexity of precomputations andstar generation is upper-bounded by Cprecomput ≈ 28.5 full AES computations.
Thus, Cf ull ≈ 2126.698 .
The data complexity exactly corresponds to the unicity distance of AES128 – the minimal data complexity theoretically attainable. 1 known plaintextciphertext pair can sometimes be enough (with success probability of 1/e ≈0.3679). 2 known plaintext-ciphertext pairs yield a success probability of practically 1.
4.4

Fastest key recoveries for AES-128

Fastest biclique key recovery with less than the full codebook of data.
This attack is based on a balanced biclique of dimension 8 of the last 2.5 roundsof AES-128. It is depicted in Figure 10(a). The forward and backwards trails inthe biclique have an intersection in byte 0 of $8. However, this intersection isin a linear operation (xor) of the key schedule and does not affect the bicliqueproperty. Note that the forward and backward trails in original attack did nothave any intersection at all over the biclique. This is the additional degree of
freedom used in our key recovery. See Figure 10(a).
The key is enumerated in $9 which is the only key state linear in the key
modification both in forward and backward trails. The bytes of key enumeration
with i and j are non-intersecting. i is placed in bytes 0,4,8, and 12. j is put in
bytes 5 and 9. The base key in each group is chosen such that the key coverage
is complete and there are no intersections between the key groups: The bytes
not affected by key modification run over all possibilities. In the bytes affectedby i-modification, byte 0 is always set to zero and bytes 4,8, and 12 run over all
possibilities. Similarly, in the bytes of j-modification, byte 5 is always 0 and byte
9 accepts all possible values. Thus, the key group size is 216 .

23

base
computation∆i -differentials∇j -differentials

Step 2. Add ∆i to the key
x0

#15

x0
SB
SR
MC

SB
SR
MC

SB
SR
MC

∇K
j

∆K
i

#16

SB
SR
MC

#17

key schedule

key schedule

key schedule

$8

SB
SR
MC

SB
SR
MC
#18

SB
SR

#19

key schedule

key schedule

key schedule

$9

SB
SR

SB
SR
#20

$10
yi

y0

y0

Step 1. Start with y0 = 0
Step 3. Add ∇j to the key

#6

MC
SR
SB

#7

AK

#8

MC
SR
SB

#9

AK

#10

MC
SR
SB

#11

AK

#12

MC
SR
SB

#13

AK

MC
SR
SB

#14

biclique#15AK(a) Biclique over last 2.5 rounds#5

matching byte∆Kjrecomputed
$7

$6

#4

AK

#3

SB
SR
MC

#2

AK

SB
SR
MC

#1

decryption
oracle &bicliquePTAK(b) Recomputation backwards#5matching byte

∇Kirecomputed$0(c) Recomputation forwards

Fig. 10. Fastest biclique attack on AES-128 with less than full codebook: time2126.16 and data 264

24

The key recovery is MITM with partial matching in byte 12 of data state #5of round 3, where only one S-box needs recomputation. In round 2 and round4, only 4 S-boxes, respectively, are recomputed. In round 7, only 8 S-boxes arerecomputed. In round 1, 5 S-boxes are recomputed as the plaintext is influenced
by 5 active bytes of the backward key modification through the key schedule. The
S-boxes of rounds 5 and 6 have to be recomputed completely. See Figures 10(b)and 10(c). Rounds 8-10 are covered by the biclique.
All in all, also counting the necessary recomputations in the key schedule
we arrive at 55 S-boxes that have to be recomputed for each key, resulting in
Crecomp ≈ 214.137 . As in the previous attacks, Cf alsepos ≈ 23.526 and Cprecomp ≈28.5 . This yields Cf ull ≈ 2126.16 . The data complexity as defined by the form of thebiclique is 264 chosen ciphertexts. As in all our attacks, the success probability is
1.

Fastest biclique key recovery. When we drop the constraint of data complexity being below the full codebook, we can construct a balanced biclique ofdimension over 3 full AES-128 rounds and with the minimal recomputation ofjust one S-box in the fourth round right after the biclique. The biclique is placedin rounds 2-4 which implies the data complexity of 2128 for the backward trail.
See 11(a).
In the forward recomputation, one byte in round 5 is affected. See Figure 11(b). In the backward direction, four bytes in round 1 are recomputed.
See Figure 11(c). The remainder of the rounds is the matching on one byte inround 8. This involves recomputation of 2 full rounds (amounting to 32 S-boxes),
invocation of the encryption oracle, and recomputation of 9 S-boxes in rounds
7,8 and 9.
Thus, we have to recompute 37 S-boxes altogether for each key, resultingin Crecomp ≈ 213.56 . For all attacks of this type (matching on one byte), we
have Cf alsepos ≈ 23.526 . The precomputations are approximately the same with
Cprecomp ≈ 28.5 . This yields Cf ull ≈ 2125.6 . The data complexity in this attackis the full codebook. The success probability is again 1 since key coverage iscomplete.
This key recovery can be converted into a preimage search for the compression function constituted by AES-128 in Davies-Meyer mode. Here the attack
works offline and does not have to make any online queries. This preimage attack requires 2125.6 AES-128 operations and finds a preimage with probability
about 0.632. The generic preimage search would require 2128 time to succeed
with probability 0.632.

25

base
computation∆i -differentials∇j -differentials

Step 2. Add ∆i to the key

∇K
j

∆K
i

$1
key schedule

SB
SR
MC

key schedule

SB
SR
MC

#3
SB
SR
MC

SB
SR
MC

key schedule

key schedule
key schedule

SB
SR
MC

x0
SB
SR
MC

key schedule

key schedule
key schedule

SB
SR
MC

key schedule

x0
SB
SR
MC

SB
SR
MC

#4

$2
#5

#6

$3
#7

#8

$4
yi

y0

#9

Step 1. Start with y0 = 0
Step 3. Add ∇j to the key

#16

MC
SR
SB

#17

AK

#18

MC
SR
SB

#19

AK

#20

SR
SB

AK

CT

encryption
oracle

#1

AK

#2

MC
SR
SB

biclique(a) Biclique over 3 rounds in the middle#15

recomputed

#14

AK

#13

SB
SR
MC

#12

AK

#11

SB
SR
MC

AK

#10

biclique

#9

SB
SR
MC

(b) Recomputation backwards#15

matching byte

∇Kirecomputed$5(c) Recomputation forwards

Fig. 11. Fastest biclique attack on AES-128: time 2125.6 and full codebook

26

matching byte

5

5.1

Biclique Cryptanalysis of Camellia

Summary

For the purpose of this analysis, we confine ourselves to the case of independent
bicliques with at most a single-byte key modification. This is the type of biclique
cryptanalysis that proved most successful for AES. Because of the SPN structureused in the round function of Camellia, we can presume that this will be also
a good choice for Camellia. Moreover, since the purpose of this document is anindication of a security level for these ciphers, we take the approach of letting
the data complexity of such biclique attacks be unlimited. This might result inbiclique attacks that require full code book, though not necessarily. However,their computational complexity can be seen as a lower bound of what can beattained for Camellia with these techniques. In this preliminary document, weonly report results for the full Camellia since those are most interesting.
The properties of the key schedule are highly important to make a bicliqueattack work. In Camellia, one can observe that the key schedule is designed tomake it robust to related-key differential attacks. This is done by maintaining
different types of intermediate keys: KL and KA for Camellia-128 as well as KL ,KR , KA and KB for Camellia-192 and Camellia-256, where KA and KB depend
in a complex way on KL or KL and KR , respectively. Moreover, the key schedule
is such that no three adjacent rounds use subkeys from either KL and KR or
KA and KB . This complicates the biclique construction and makes its effective
length shorter. It is also the reason to enumerate the keys with respect to a basekey of KL |KR in each key group.
Applying this approach to Camellia, we report key recovery results as follows.
For the full Camellia-128, we can recover the key with a complexity of 2127.6 , data complexity 2128 , negligible memory complexity and success probability 1. We
have found a key recovery for the full Camellia-192 with computational complexity 2191.7 , data complexity 2128 , negligible memory complexity and successprobability 1. For the full Camellia-256, we report a key recovery with a computational complexity of 2255.7 , data complexity 2128 , negligible memory complexity
and success probability 1. Note that if we just apply exhaustive MITM key recovery without constructing a biclique structure, it is possible to convert these
attacks to lower data complexity attacks at the expense of an increase in thecomputational complexity. We choose not to do so since the time complexities of
the key recoveries are quite high even with bicliques.

27

Table 2. Summary of our biclique key recoveries for full Camellia
cipherroundsattack type data time memory
Camellia-128 18 (of 18) biclique MITM 2128 2127.6 small
Camellia-192 24 (of 24) biclique MITM 2128 2191.7 small
Camellia-256 24 (of 24) biclique MITM 2128 2255.7 small

5.2

Base line: complexity of brute force

We understand brute force key recovery for a cipher with a k-bit key as thecomplete computation of the cipher encryption on each of the 2k keys. The firstand most time-consuming filtering stage can be performed using one plaintextciphertext pair then, followed by subsequent and much less frequent tests if needed. So before discussing advantages of any other key recovery procedure, one
needs to establish a base line for the respective computation of relative advantage– namely, quantify the complexity of the brute force key recovery with successprobability 1.
For Camellia, just in line with the computational model introduced in thebiclique attacks for AES, the unit will be the application of an 8-bit S-box. Thisis arguably the most consuming component in terms of implementations — both
software (table lookups or bitslice) or hardware (ASIC or FPGA).
Table 3. Computational base line for Camellia (brute force)data transform key schedule total
total(rounds)(rounds) (rounds) (S-boxes)
Camellia-128
18R
4R
22R
176
24R
6R
30R
240
Camellia-192
Camellia-256
24R
6R
30R
240
cipherAs indicated in Table 3, one Camellia-128 computation requires in total 176
S-box applications, since each round transform includes 8 S-box applications andthere is an equivalent of 22 rounds in the full Camellia-128. Similar applies toCamellia-192 and Camellia-256 yielding a total of 240 S-box applications.
5.3

Independent bicliques over 2 rounds

We describe here how to construct an independent biclique of dimension 8 over2 rounds of a 6-round block in Camellia. For this, one needs to specify rounds

28such that round 3 and 4 of the 6-round block use key KL or KR . In all Camellia
versions, there are such pairs of numbers even using KL only. So without unnecessary loss of generality, we construct bicliques in the rounds as specified inTable 4.
Table 4. 2-round bicliques and key modification for Camellia
ciphertype key modification
subkeyround number
forwardone byte(KL <<< 15)L(64)3
Camellia-128
backward
one byte(KL <<< 15)R(64)4forwardone byte(KL <<< 45)L(64)9Camellia-192
backward
one byte(KL <<< 45)R(64)10forwardone byte(KL <<< 45)L(64)9Camellia-256
backward
one byte(KL <<< 45)R(64)10

The key modification in both forward and backward directions is in 8 bits
which corresponds to an independent biclique of dimension 8. The actual bicliqueconstruction is outlined in Figure 12.
In the backward direction, one byte key modification in round 4 of the 6-roundblock in the backward direction activates 5 bytes at the output of the F -function
due to the specific choice of the byte position according to the specification of P .
This, in turn, activates 5 bytes at the input of the F -function in round 3 of the
6-round block, which can activate 8 bytes at the output of this function.
In the forward direction, a similar key modification is applied. In round 3 of
the 6-round block, a single byte of the round subkey is activated which gives 5
active bytes at the output of the F -function in that round. In the next round,
this yields 5 active S-boxes and an 8-byte active output pattern.
We show now how this construction forms an independent 2-round bicliqueof dimension 8. First, we require that the input difference at the input of round-3
F -function in the backward propagation does not include the byte of key modification in the forward direction. And vice versa, we require that the input differenceat the input of round-4 F -function in the forward propagation does not cover
the byte of key modification of the backward propagation. Obviously, this canbe easily attained by inspecting the P -layer. Now we observe that though wehave a lot of difference intersections in the backward and forward directions overthe 2 rounds, they never intersect in the non-linear components (S-boxes). Thissuffices for the construction of an independent biclique. Then, we see that we can29forward modiﬁcation

F

F

F

F

bicliquebackward modiﬁcation

5

8

1

F
5
F

1

5
F

8

5
F

F

F

F

F

Fig. 12. Independent biclique construction over 2 rounds of Camellia: Numbers
indicate the number of active bytes in the F -function right after the subkey
addition and right after the P -layer. Numbers in grey circles indicate spots ofkey difference injections
inject up to an 8-bit difference in each direction. This defines the dimension of
the biclique to be 8.
5.4

Partial matching over 3 rounds

Having construction a biclique, we can apply recomputation with precomputation
over the biclique area to save operations. Moreover, we can have more savings
due to partial matching which is illustrated in Figure 13.
We match in round 4 of a 6-round block in one byte of a 8-byte half state.
This requires the recomputation of only 5 bytes in rounds 3 and 5 but full recomputations of rounds 1,2, and 6 (8 S-boxes each).
5.5

Recomputation over the remaining rounds and in the keyschedule

All S-boxes in the remaining rounds of the data transform need to be recomputedfor every key. In the key schedule though, some more savings are possible. A glanceat the key schedule of Camellia (see Figure 16) suggests that no full recomputationis necessary given the type of key modification we have employed.

30

matching

8

8
F

5

8
F

5
F
0

1
0
1

F
5
F
5

1
8

F

Fig. 13. Partial matching over 3 rounds for Camellia: Numbers indicate the number of bytes to be recomputed in the corresponding lines. The number in grey
circle indicates the byte of matching
In Camellia-128, we need to compute KA from every modification of KL . Thisrequires at most 4 rounds. However, since our key modification is in two distinct
bytes of KL which are in two distinct 64-bit halves of the user-supplied key, only
one S-box needs to be recomputed in the first round. 5 bytes are actived at theoutput of this F -function and at the input of the F -function in the second round.
Thus, we need to compute only 6 S-boxes instead of 16 in the first two rounds.
In Camellia-192 and Camellia-256, both KA and KB need to be computedfrom KL and KR . We have no modification in KR and only single-byte modification in two distinct 64-bit halves of KL again. So again we have a saving of 10
S-box computations in the key schedule recomputation.
5.6

Complexity

In total, we have saved 14 S-box computations due to the construction of thebiclique, 16 S-box computations due to the partial matching and another 10 Sbox computations due to the optimized recomputation in the key schedule. This
results in 40 S-boxes saved per key tested.
Memory complexity in the biclique construction and recomputations within
the key group is negligible because of the limited biclique dimension. The compu176
tational complexity for Camellia-128 is defined by the advantage factor of 176−40

31and amounts to about 2127.6 . For Camellia-192 and Camellia-256, the advantage
240
which brings the computational complexity to 2191.7 and 2256.7 ,factor is 240−40
respectively. Note that we do not take into account the complexity of bicliqueconstruction since the dimension of the biclique is large enough to make it negligible.
The data complexity of this key recovery is 2128 , that is, the full codebook.
Due to the specification of the key schedule – both the computation of the subkeys
and the order of their usage in rounds – it is challenging to have both a non-trivial
biclique (accounting for more computation savings) and a lower data complexity.
For instance, in Camellia-128, if key modification is in KL , then KA will lookrandom for each key modification which will lead to the propagation of the key
modification to the full state at the plaintext or ciphertext, depending on where
the biclique is exactly put. Similar applies to Camellia-192 and Camellia-256.

6
6.1

Zero Correlation Cryptanalysis of Camellia
Summary

In the course of the key recovery in zero correlation linear cryptanalysis, thecorrelation of a linear approximation over a part of the cipher needs to be evaluated for many key guesses. While the length of the underlying zero correlation
approximation mainly determines the number of rounds that can be attacked, itis the partial encryption and decryption of plaintexts and ciphertexts up to theboundaries of the linear approximation that dominates the computational complexity of the attack. We use the discrete Fast Fourier transform to reduce thecomputational complexity at this end. For data complexity reduction, the novel
multidimensional zero-correlation distinguisher is applied. Though some cryptanalysts prefer to skip FL/FL−1 functions for simplicity, we analyze Camellia-192
and Camellia-256 with FL/FL−1 functions, ensuring that we actually cryptanalyze Camellia transform and not a related variant.
For a generic construction like Camellia (balanced Feistel network), there are
numerous of zero-correlation linear approximations over only 5 rounds. However,for Camellia, we are able to identify a bunch of 7-round zero-correlation linear approximations due to the properties of the FL/FL−1 functions and the F-functionsof the round transformation.
For 11-round Camellia-192, we report a key recovery requiring 2125.1 data,
2157.79 operations equivalent to 11 rounds of Camellia-192 as well as 2101 blocks
of memory. For 12-round Camellia-256, we have identified a key recovery using
2125.9 data, 2234.31 operations equivalent to 12 rounds of Camellia-192 as well as2165 blocks of memory. The 7-round zero-correlation linear approximations are of32the form (0bb0bb0b|00000000) → (00000000|h00h0hhh) where b and h are nonzero
bytes.
Table 5. Summary of our zero correlation attacks on round-reduced Camellia
with F L/F L−1 functions
cipherroundsattack type data time memory
Camellia-192 11 of 24 zero correlation 2125.1 2157.79 2101
Camellia-256 12 of 24 zero correlation 2125.9 2234.31 2165

6.2

7-round zero-correlation linear approximations for Camellia
with F L/F L−1 functions

In this section, we will present some zero-correlation linear hulls for 7-round
Camellia with F L/F L−1 function. Firstly, we will introduce some properties for
F L/F L−1 .
Property 1: If the input mask of F L function is IM = (0|0|0|0|0|i|0|0), theoutput mask of F L function OM = (0|?|?|0|0|?|?|0), where ”?” is an unknown
value.
Proof. If we denote the input mask for IM = IML |IMR and OM = OML |OMR ,from the definition of F L, we have
OML = IML ⊕ ((IMR ≫ 1) ∩ kL ), OMR = (OML ∪ kR ) ⊕ IMR .
As
IML = 0,OML = ((IMR ≫ 1) ∩ kL ) = ((0|i|0|0) ≫ 1) ∩ kL = (0|?|?|0)and
OMR = ((0, ?, ?, 0) ∪ kR ) ⊕ (0|i|0|0) = (0|?|?|0).
⊔⊓Similarly, we can get the following relation between IM and OM for F L function,
IM = (0|0|0|0|0|0|0|i) ⇒ OM = (?|0|0|?|?|0|0|?).

33

Property 2: If the output mask of F L−1 function is OM = (i|0|0|0|0|0|0|0), theinput mask of F L−1 function IM = (i||0|0|?||0|0). If OM = (0|0|0|0|i|0|0|0),
it holds thatIM = (?|?|0|0|?|?|0|0).
Proof. From the definition of F L−1 , we have
IML = OML ⊕ (OMR (≫ 1) ∩ kL ), IMR = (IML ∪ kR ) ⊕ OMR .
As
OM = (0|i|0|0|0|0|0|0),
one has thatOMR = 0and
OML = (0|i|0|0).
Then we have IML = OML = (0|i|0|0) and IMR = (0|?|0|0), where ”?” is theunknown value.
As OM = (0|0|0|0|i|0|0|0), we have that OML = 0 and OMR = (i|0|0|0).
Then we have
IML = (OMR ≫ 1) = (?|?|0|0)and
IMR = ((?|?|0|0) ∪ kR ) ⊕ (0|i|0|0) = (?|?|0|0),
where ”?” is the unknown value.

⊔⊓

In the similar way, we can get the following relations between IM and OM for
F L−1 ,
OM = (0|i||0|0|0|0|0) ⇒ IM = (0|i||0|0|?|?|0),
OM = (0|0|i|0|0|0|0|0) ⇒ IM = (0|0|0|i|0|0|0|?),
OM = (0|0|0|i|0|0|0|0) ⇒ IM = (0|0|0|i|0|0|0|?),
OM = (0|0|0|0|0|i|0|0) ⇒ IM = (0|?|?|0|0|?|?|0),
OM = (0|0|0|0|0|0|i|0) ⇒ IM = (0|0|?|?|0|0|?|?),
OM = (0|0|0|0|0|0|0|i) ⇒ IM = (?|0|0|?|?|0|0|?).
With the above properties, we can get some zero-correlation linear hulls for
7-round Camellia.

34

Type 1: For 7-round Camellia consisting of(F |F |F |F |F L/F L−1 |F |F |F ),if the input mask of the first round is(0|b|b|0|b|b|0|b, 0|0|0|0|0|0|0|0)
and the output mask of the last round is(0|0|0|0|0|0|0|0, h|0|0|h|0|h|h|h),the correlation of the linear hull for the 7-round Camellia is zero, where b, h ∈F82 , b 6= 0, h 6= 0.
Proof. From Fig. 14(a), the input mask
(0|b|b|0|b|b|0|b, 0|0|0|0|0|0|0|0)
produces the input mask
(0|0|0|0|0|a|0|0)
for F L function, and the output mask
(0|0|0|0|0|0|0|0, h|0|0|h|0|h|h|h)results in the output mask
(f1 |f2 |f3 |f4 |f5 |f6 |f7 |f8 ⊕ i)
for F L function, wherea, b, h, i, ck (k ∈ {2, 3, 5, 7, 8}), gl (l ∈ {1, 4, 5, 6, 7})
and fj (1 ≤ j ≤ 8) are non-zero value. From Property 1, if the input mask for F L
function
IM = (0|0|0|0|0|a|0|0),
the output mask
OM = (0|?|?|0|0|?|?|0).
Then f1 = 0, f4 = 0, f5 = 0 and f8 ⊕ i = 0. According to the relations between
fj and gl , the following equations should hold,f4 = 0 ⇒ g1 ⊕ h ⊕ g5 ⊕ g6 ⊕ h ⊕ g7 ⊕ h = g1 ⊕ g5 ⊕ g6 ⊕ g7 ⊕ h = 0,35

(0|b|b|0|b|b|0|b)(0|0|0|0|0|0|0|0)

KS

P

Ͱ

KS

P

Ͱ (0|b|b|0|b|b|0|b)(0|b|b|0|b|b|0|b)(0|0|0|0|0|b|0|0)(0|0|0|0|0|a|0|0)
KS

P(0|a|a|0|a|0|a|a)(0|0|0|0|0|a|0|0)(0|bͰF2|bͰF3|0|bͰF5|b|F7|bͰF8)(f1|f2|f3|f4|f5|f6|f7|f8ͰL)

KS

P

KS

P

Ͱ(0|b|b|0|b|b|0|b)KS

P(0|a|a|0|a|0|a|a)KSP(f1|f2|f3|f4|f5|f6Ͱa|f7|f8)
FL -1

FL
P

Ͱ

(g1|0|0|g4|g5|g6|g7|0)(0|0|0|0|0|0|0|i)

KS(i|0|0|i|i|i|i|0)

KS

P

P

Ͱ

P

Ͱ (h|0|0|h|0|h|h|h)(0|0|0|0|0|0|0|h)(0|0|0|0|0|0|0|i)(0|0|0|0|0|0|0|0)

KS(h|0|0|h|0|h|h|h)(0|0|0|0|0|0|0|0)Ͱ (0|0|0|0|0|0|0|i)(i|0|0|i|i|i|i|0)

KS(0|0|0|0|0|0|0|h)KSP(g1|0|0|g4|g5|g6|g7|0)

Ͱ (h|0|0|h|0|h|h|h)(0|0|0|0|0|0|0|i)P（b)Fig. 14. Zero-correlation linear approximations for 7-round Camellia

36

Ͱ

(0|0|0|0|0|0|0|0)(h|0|0|h|0|h|h|h)(0|0|0|0|0|0|0|0)（a)(0|bͰF2|bͰF3|0|bͰF5|b|F7|bͰF8)

Ͱ

(f1|f2|f3|f4|f5|f6|f7|f8)(0|bͰF2|bͰF3|0|bͰF5|b|F7|bͰF8)J5|hͰg6|hͰg7|h)KS

Ͱ (0|0|0|0|0|a|0|0)(0|c2|c3|0|c5|0|c7|c8)Ͱ (hͰJ1|0|0|hͰJ4|(f1|f2|f3|f4|f5|f6|f7|f8)

Ͱ

(0|0|0|0|0|b|0|0)

FL -1

FL

P

(0|0|0|0|0|a|0|0)Ͱ (0|0|0|0|0|a|0|0)(0|c2|c3|0|c5|0|c7|c8)(0|0|0|0|0|0|0|0)KSf5 = 0 ⇒ g1 ⊕ h ⊕ g5 ⊕ g7 ⊕ h ⊕ h = g1 ⊕ g5 ⊕ g7 ⊕ h = 0.

From the above two equations, we can deduce g6 = 0, which contradicts that
g6 6= 0. As a result, the linear hull is a zero-correlation linear hull.
There is another zero-correlation linear hull for 7-round Camellia which is asfollows7r(b|0|0|b|0|b|b|b, 0|0|0|0|0|0|0|0) → (0|0|0|0|0|0|0|0, 0|h|h|0|h|h|0|h).
The input mask(b|0|0|b|0|b|b|b, 0|0|0|0|0|0|0|0)
and the output mask
(0|0|0|0|0|0|0|0, 0|h|h|0|h|h|0|h)will result that the input mask is IM = (0|0|0|0|0|0|0|a) and the output mask is(f1 |f2 |f3 |f4 |f5 |f6 ⊕ i|f7 |f8 )for F L function. From Property 1, the input mask for F L function
IM = (0|0|0|0|0|0|0|a),and the output mask is OM = (?|0|0|?|?|0|0|?). Then f2 = 0, f3 = 0, f6 ⊕ i = 0
and f7 = 0. According to the relations between fj and gl , the following equations
should hold,f2 = 0 ⇒ g3 ⊕ h ⊕ g5 ⊕ h ⊕ g7 ⊕ g8 ⊕ h = g3 ⊕ g5 ⊕ g7 ⊕ g8 ⊕ h = 0,
f7 = 0 ⇒ g3 ⊕ h ⊕ g5 ⊕ h ⊕ h ⊕ g7 = g3 ⊕ g5 ⊕ g7 ⊕ h = 0.

It is easy to deduce that g8 = 0, which contradicts that g8 6= 0. As a result, thelinear hull is also a zero-correlation linear hull.
⊔⊓
Type 2: For 7-round Camellia consisting of(F |F |F |F L/F L−1 |F |F |F |F ),if the input mask of the first round is(0|b|b|0|b|b|0|b, 0|0|0|0|0|0|0|0)
and the output mask of the last round is(0|0|0|0|0|0|0|0, h|0|0|h|0|h|h|h),the correlation of the linear hull for the 7-round Camellia is zero, where b, h ∈F82 , b 6= 0, h 6= 0, see Fig. 14(b).

37Proof. From Fig. 14(b), the input mask
(0|b|b|0|b|b|0|b, 0|0|0|0|0|0|0|0)
produces the input mask
(f1 |f2 |f3 |f4 |f5 |f6 ⊕ a|f7 |f8 )for F L−1 function, and the output mask
(0|0|0|0|0|0|0|0, h|0|0|h|0|h|h|h)produces the output mask
(0|0|0|0|0|0|0|i)
for F L−1 function, where a, b, h, i, ck (k ∈ {2, 3, 5, 7, 8}), gl (l ∈ {1, 4, 5, 6, 7}) andfj (1 ≤ j ≤ 8) are non-zero value. From Property 2, the output mask for F L−1

function OM = (0|0|0|0|0|0|0|i), the input mask IM = (?|0|0|?|?|0|0|?). Then
f2 = 0, f3 = 0, f6 ⊕ a = 0 and f7 = 0. According to the relations between fj andgl , the following equations should hold,f2 = 0 ⇒ c3 ⊕ b ⊕ c5 ⊕ b ⊕ c7 ⊕ c8 ⊕ b = c3 ⊕ c5 ⊕ c7 ⊕ c8 ⊕ b = 0,
f7 = 0 ⇒ c3 ⊕ b ⊕ c5 ⊕ b ⊕ c7 ⊕ b = c3 ⊕ c5 ⊕ c7 ⊕ b = 0.

So we can derive that c8 = 0, which contradicts that c8 6= 0. As a result, thelinear hull is also a zero-correlation linear hull.
⊔⊓
There are some similar zero-correlation linear hulls for 7-round Camellia as
follows:7r(b|0|0|b|0|b|b|b, 0|0|0|0|0|0|0|0) → (0|0|0|0|0|0|0|0, 0|h|h|0|h|h|0|h),7r(b|b|0|0|b|0|b|b, 0|0|0|0|0|0|0|0) → (0|0|0|0|0|0|0|0, 0|0|h|h|h|h|h|0),7r(0|0|b|b|b|b|b|0, 0|0|0|0|0|0|0|0) → (0|0|0|0|0|0|0|0, h|h|0|0|h|0|h|h),7r(0|b|b|b|0|b|b|b, 0|0|0|0|0|0|0|0) → (0|0|0|0|0|0|0|0, 0|h|h|h|0|h|h|h),7r(b|0|b|b|b|0|b|b, 0|0|0|0|0|0|0|0) → (0|0|0|0|0|0|0|0, h|0|h|h|h|0|h|h),7r(b|b|0|b|b|b|0|b, 0|0|0|0|0|0|0|0) → (0|0|0|0|0|0|0|0, h|h|0|h|h|h|0|h),7r(b|b|b|0|b|b|b|0, 0|0|0|0|0|0|0|0) → (0|0|0|0|0|0|0|0, h|h|h|0|h|h|h|0).
To save on space, we will not provide the proof for these zero-correlation linear
approximations here.

38

PL
kw1

PR

Ͱ

k1

kw2

KS

(*,*,*,*,*,*,*,*)PͰͰ (0,*,*,0,*,0,*,*)

PL
kw1

k2
KS

(0,*,*,0,*,0,*,*)PͰ (0,0,0,0,0,*,0,0)PR

Ͱ(0,*,*,0,*,0,*,*)

KS(0,0,0,0,0,*,0,0)

k2
KS

k3
KS

P

Ͱ (0,b,b,0,b,b,0,b)(0,0,0,0,0,b,0,0)(0,0,0,0,0,0,0,0)(0,b,b,0,b,b,0,b)(0,0,0,0,0,0,0,0)P(0,0,0,0,0,0,0,0)(h|0|0|h|0|h|h|h)Ͱkw3

Ͱ(0,0,0,0,0,0,0,*)

Ͱ

Ͱ

CL

CR

k10
KS

P

(h|0|0|h|0|h|h|h)Ͱ(0,0,0,0,0,0,0,h)(*,0,0,*,*,*,*,0)P

Ͱ (0,b,b,0,b,b,0,b)

7-round zero correlation
linear hull

k12
KS

P

(0,0,0,0,0,b,0,0)(0,0,0,0,0,0,0,0)(0,0,0,0,0,0,0,h)(*,0,0,*,*,*,*,0)PͰͰ (0,0,0,0,0,*,0,0)(0,b,b,0,b,b,0,b)

7-round zero correlation
linear hull

k11
KS

kw2

(0,*,*,0,*,0,*,*)(0,*,*,0,*,0,*,*)(0,0,0,0,0,*,0,0)

k1

kw3
kw4

k11
KS

P

Ͱ(0,0,0,0,0,0,0,*)

Ͱ

Ͱ

CL

CR
(b)

(a)

Fig. 15. Zero correlation linear attacks on 12-rounds Camellia-256 and 11-rounds
Camellia-192

39

kw4

6.3

Attack on 12-round Camellia-256

We use the 7-round zero-correlation linear approximations to attack 12-round
Camellia-256, see Fig. 15(a). In Fig. 15(a), we also try to determine the mask
value before or after the 7-round zero-correlation linear hull, where ∗ denotes thatthe mask value for the corresponding byte position cannot be determined.
In the following, we will use some notations. X i1 ,i2 ,... denotes the i1 -th, i2 th,. . . byte of X and X can be the plaintext word, ciphertext word or subkey
word, S j denotes the output of the j-th S-Box, Fj denotes the output of theround function for the j-th round and Fjl denotes the l-th output byte of theround function for the j-th round. If we denote K0 = kw1 ⊕ k1 , K1 = kw2 ⊕ k2 ,K2 = kw1 ⊕ k3 , K3 = kw3 ⊕ k11 , and K4 = kw4 ⊕ k12 , we can get the following
linear approximation:
8 ⊕ αT · P 2,3,5,8 ⊕ β T · C 1,4,6,7 ⊕ bT · S 6 (P 6 ⊕ K 6 )bT · PR6 ⊕ hT · CR
0LRR⊕bT · S 6 {PL6 ⊕ K26 ⊕ F26 [PR2,3,5,7,8 ⊕ K12,3,5,7,8 ⊕ F1 (PL1,...,8 ⊕ K01,...,8 )}(5)

8 ⊕ F 8 (C 1,4,5,6,7 ⊕ K 1,4,5,6,7 )] = 0.
⊕hT · S 8 [CL8 ⊕ K11
5
4
R

where αT = (b, b, b, b), β T = (h, h, h, h), b ∈ F28 , b 6= 0, h ∈ F28 , h 6= 0.
In order to express Equation (5) as a circulant matrix, we will fix some parameters to obtain the following circulant matrix:
5 |C 1,4,6,7 ∧ (h̄|h̄|h̄|h̄), K 1,2,3,4,5,7,8 |K 5 |K 1,4,6,7 ∧ (h̄|h̄|h̄|h̄) =M (PL1,2,3,4,5,7,8 |CR4
0
4
R
1,4,6,7
αT · PR2,3,5,8 ⊕ β T · CR
⊕ bT · S 6 (PL6 ⊕ K06 )(6)⊕bT · S 6 {PL6 ⊕ K26 ⊕ F26 [PR2,3,5,7,8 ⊕ K12,3,5,7,8 ⊕ F1 (PL1,...,8 ⊕ K01,...,8 )]}8 ⊕ F 8 (C 1,4,5,6,7 ⊕ K 1,4,5,6,7 )].
⊕hT · S 8 [CL8 ⊕ K11
5
4R

In Equation (6), PL6 has also been involved outside the round function F1 , so wemust fix the value of PL6 . Moreover, in order to use more zero-correlation linear
hulls, more values of h will be taken. At the same time, in order to control thetime complexity, we will take all values for h with the Hamming weight one or
1,4,6,7
1,4,6,7, so∧ (h|h|h|h) have been involved in β T · CR
two. It means that CR
1,4,6,7∧ (h|h|h|h) and express the remaining bits
we must fix the value of bits CR
1,4,6,7∧ (h̄|h̄|h̄|h̄) in circulant matrix. Here h̄ = h ⊕ f fx .
CR
We proceed with the attack as follows:40

– Set the global counter Cκ as zero for each of 2160 possible values ofκ = (K01,2,3,4,5,6,7,8 |K12,3,5,7,8 |K26 |K38 |K41,4,5,6,7 ).
– For
 h ∈
 S and b ∈ F28 , b 6= 0, S = {x : 1 ≤ W (x) ≤ 2, x ∈ F28 }, |S| =88+2
1 = 36, where W (x) is the Hamming weight of x:• Data counting phase:
1. For N plaintext-ciphertext pairs, extract 56 + 4W (h) bits value
1,4,6,7i = (PR2,3,5,7,8 |PL6 |CR∧ (h|h|h|h)|CL8 )and the corresponding 64 + 4(8 − W (h)) bits value
1,4,6,75∧ (h̄|h̄|h̄|h̄)).
|CRj = (PL1,2,3,4,5,7,8 |CR

2. Increment the counter j of the vector xi according to the parity of
8.
bT · PR6 ⊕ hT · CR

• Key counting phase: For each possible 64 + 4W (h) bits value k of
(K06 |K26 |K12,3,5,7,8 |K38 |K41,4,6,7 ∧ (h|h|h|h)) :1. For each possible 56 + 4W (h) bits value
1,4,6,7(PR2,3,5,7,8 |PL6 |CR∧ (h|h|h|h)|CL8 ) :compute
1,4,6,7
Z = αT · PR2,3,5,8 ⊕ β T · CR
∧ (h|h|h|h) ⊕ b · S 6 (PL6 ⊕ K06 ).

(a) Select the corresponding vector of counters xi(b) Compute the first column Mi of the matrix
5 |C 1,4,6,7 ∧ (h̄|h̄|h̄|h̄),
Mi (PL1,2,3,4,5,7,8 |CRR
1,2,3,4,5,7,8
K0|K45 |K41,4,6,7 ∧ (h̄|h̄|h̄|h̄)) =
T

6

8

8

2,3,5,7,8

66(−1)Z⊕b ·S {PL ⊕K2 ⊕F2 [PRT

8

8

1,4,5,6,7(−1)h ·S [CL ⊕K3 ⊕F5 (CR41⊕K12,3,5,7,8 ⊕F1 (PL1,...8 ⊕K01,...8 )]} ×⊕K41,4,5,6,7 )] .

As Mi is (64 + 4(8 − W (h)))-level circulant, this information is
sufficient to define M completely (requires 264+4(8−W (h)) operations
which are equivalent to
264+4(8−W (h)) · (1 + 85 + 81 + 58 + 18 )/12 = 264+4(8−W (h)) · 2.5/12 =
264+4(8−W (h))−2.26 = 293.74−4W (h)12-round encryptions.
(c) The evaluation of the linear approximation for the subset of texts
with the corresponding
1,4,6,7(PR2,3,5,7,8 |PL6 |CR∧ (h|h|h|h)|CL8 )value is given by the matrix vector product ǫi = M · xi which
requires3 · 2(64+4(8−W (h))) · (64 + 4(8 − W (h))))operations1 . This approaches to

3 · 2(64+4(8−W (h))) · (64 + 4(8 − W (h))))times of one-round Camellia encryption.
b|h2. The global vector of bias ǫk for the particular choice of (b|h) and(K06 |K26 |K12,3,5,7,8 |K38 |K41,4,6,7 ∧ (h|h|h|h))
X
b|h
ǫi .
is the sum of ǫi : ǫk =ib|h3. Let Cκ = Cκ + (ǫk /N )2 .
We obtain 2160 counters for Cκ corresponding to the evaluation of the biasof the linear approximation for the 160-bit subkey guess. The correct subkey isthen selected among the candidates with Cκ less than the threshold√√l
213.16213.202l
2 · 213.16· z1−β0 +=·2+=.
t = σ0 · z1−β0 + µ0 =
N
N
N
N
N
From the section on data complexity reduction, the number of known plaintextciphertext pairs should satisfy the following condition:r
2n+0.52NN ≥ √ (z1−β1 1 + n + z1−β0 ).
2l1From [28], the k-level matrix vector product can be computed with 3 times of 2k -point Fast
Fourier Transform.

42If we set β0 = 0.023 and β1 = 2−98 , we get z1−β0 = 2 and z1−β1 = 11.37.
n = 128, l = 255 · 36 = 213.16 . As N = 2125.9 , the above condition can be satisfied.
The memory requirements in the data counting phase and the key counting
phase are 2152 nibbles and 292 nibbles, respectively. The memory requirements
for the global counters Cκ are 2160 256-bit words. Therefore, the whole memory
complexity is about 2165 bytes.
The time complexity for the data counting phase is 213.16 · 2126.3 = 2139.46
memory accesses. In step (b) of the key counting phase, the time complexity is
28 · 272 · 264 · 293.74−4·2 + 8 · 268 · 260 · 293.74−4 = 2226.58
12-round Camellia encryptions. In step (c) of the key counting phase, the timecomplexity is
8 · (268 · 260 · 3 · 92 · 292 ) + 28 · (272 · 264 · 3 · 88 · 288 )) = 2236.89
times of one-round encryptions which is equivalent to 2233.30 times of 12-roundencryptions.
Due to β1 = 2−98 and the total number of recovered bits is 160, the numberof the remaining subkey values is 2−98 · 2160 = 262 .
Then we use another 7-round zero-correlation linear hull with
α = (b, 0, 0, b, 0, b, b, b)
and
β = (0, h, h, 0, h, h, 0, h)
to proceed the above key recovery attack, and we can recover K11,4,6 , K28 , K36 andK42,3,8 , the time complexity and the memory complexity are equal to that in thefirst attack. Due to β1 = 2−98 and the total number of recovered bits is 160,
the number of the remaining subkey values is 2−98 · 2160 = 262 . Therefore, thetotal number of the remaining subkey values is about 262 · 262 = 2124 . The right
key from the first attack and the second attack should has the same value forthe 96 shared subkey bits, so the remaining number of subkey values should be2124 · 2−96 = 228 .
According to the key schedule for Camellia-256, its 256-bit master key is
K = KL kKR , where KL and KR are 128 bits. With KL and KR , the key schedulealgorithm first calculates KA and KB , which is described in Fig.16. F is the round
function of Camellia and Ci (1 ≤ i ≤ 6) are constants used as the subkeys. Thenthe round subkey kwi (i = 1, . . . , 4), kr (r = 1, . . . , 24) and klj (j = 1, . . . , 6) are
derived from rotating KL , KR , KA or KB .

43

KLͰKR
C1
F

C2
F

KR

KL
C5

C3
F

C6

C4

F

F

F

KA

KB

Fig. 16. The Calculation of KA and KB

K0 = (KL ≪ 0)L ⊕ (KB ≪ 0)L ,(7)

K1 = (KL ≪ 0)R ⊕ (KB ≪ 0)R ,(8)

K2 = (KL ≪ 0)L ⊕ (KR ≪ 15)L ,(9)

K3 = (KA ≪ 45)L ⊕ (KB ≪ 111)L ,(10)

K4 = (KA ≪ 45)R ⊕ (KB ≪ 111)R .

(11)

Now we have recovered 64-bit K0 , 64-bit K1 , 64-bit K4 , 16-bit K26,8 and 16-bit
K36,8 , we can recover the master key with the following procedure:
For each of 228 remaining subkey values and for each of 2128 values of KB :1. Compute KL from Equation (7) and Equation (8).
0∼44,109∼127
2. Compute (KA ≪ 45)R from Equation (11), and it means that KA
has been deduced.

44

85∼92,101∼108
55∼62,71∼78
3. Compute KAfrom Equation (10) and KR
from Equation(9).
4. Decrypt from KB to KA with Fig. 16, and we can derive 96-bit KR .
45∼54,63∼70,79∼84,93∼100, deduce
5. For each possible remaining 32-bit value for KR
the master key K = KL kKR .
6. Using two pairs of plaintext-ciphertext to verify the master key K.
45∼54,63∼70,79∼84,93∼100
can always pass the verificaThe right guess for KB and KR
tion for step 6, but the wrong guess will pass the verification with the probability
2−96 . So we can recover the master key with high probability. The time complexity to recover the master key is much less than that to recover 160-bit subkey inthe previous, so it can be negligible.
In all, the data complexity is about 2125.9 known plaintexts, the time complexity is about 2234.31 12-round Camellia-256 encryptions and the memory requirements are 2165 bytes.

6.4

Attack on 11-round Camellia-192

We use the 7-round zero-correlation linear approximations to attack 11-round
Camellia-192, see Fig. 15(b). If we denote K0 = kw1 ⊕ k1 , K1 = kw2 ⊕ k2 , K2 =kw3 ⊕ k10 , and K3 = kw4 ⊕ k11 , the following linear approximation can be derived:
8 ⊕ αT · P 2,3,5,8 ⊕b · PL6 ⊕ h · CRL
1,4,6,7
β T · CR
⊕ bT · S 6 [PR6 ⊕ K16 ⊕ F16 (PL2,3,5,7,8 ⊕ K02,3,5,7,8 )]⊕(12)

1,4,5,6,7
hT · S 8 [CL8 ⊕ K28 ⊕ F48 (CR⊕ K31,4,5,6,7 )] = 0,

where αT = (b, b, b, b), β T = (h, h, h, h), b ∈ F28 , b 6= 0, h ∈ F28 , h 6= 0.
In order to express Equation (12) as a circulant matrix, some parameters need
to be fixed to obtain the following circulant matrix:
5 |C 1,4,6,7 ∧ (h̄|h̄|h̄|h̄),
M (PL7 |PL2,3,5,8 ∧ (b̄|b̄|b̄|b̄)|CRR

K07 |K02,3,5,8 ∧ (b̄|b̄|b̄|b̄)|K35 |K31,4,6,7 ∧ (h̄|h̄|h̄|h̄)) =1,4,6,7
αT · PL2,3,5,8 ⊕ β T · CR
⊕ bT · S 6 [PR6 ⊕ K16 ⊕ F16 (PL2,3,5,7,8 ⊕ K02,3,5,7,8 )]
1,4,5,6,7⊕ K31,4,5,6,7 )].
⊕hT · S 8 [CL8 ⊕ K28 ⊕ F48 (CRThe attack can be described in the following way:

45

(13)

– Set the global counter Cκ as zero for each of 296 values ofκ = (K02,3,5,7,8 |K16 |K28 |K31,4,5,6,7 ).
– For h ∈ S and b ∈ S with
S = {x : 1 ≤ W (x) ≤ 4, x ∈ F28 }and       
8
8
8
8
|S| =
+
+
+
= 162.
4
3
2
1• Data counting phase:
1. For N plaintext-ciphertext pairs, extract 16 + 4W (b) + 4W (h) bits
value
1,4,6,7i = (PL2,3,5,8 ∧ (b|b|b|b)|PR6 |CR∧ (h|h|h|h)|CL8 )and the corresponding 16 + 4(8 − W (b)) + 4(8 − W (h)) bits value
1,4,6,75|CR
j = (PL7 |PL2,3,5,8 ∧ (b̄|b̄|b̄|b̄)|CR∧ (h̄|h̄|h̄|h̄)).

2. Increment the counter j of the vector xi according to the parity of
8b · PL6 ⊕ h · CR.

• Key counting phase: For each possible 16 + 4W (b) + 4W (h) bits value kof(K16 |K02,3,5,8 ∧ (b|b|b|b)|K28 |K31,4,6,7 ∧ (h|h|h|h)) :1. For each possible 16 + 4W (b) + 4W (h) bits value
1,4,6,7(PL2,3,5,8 ∧ (b|b|b|b)|PR6 |CR∧ (h|h|h|h)|CL8 ) :(a) Select the corresponding vector of counters xi(b) Compute the first column Mi of the matrix
5 |C 1,4,6,7 ∧ (h̄|h̄|h̄|h̄),
Mi (PL7 |PL2,3,5,8 ∧ (b̄|b̄|b̄|b̄)|CRR

K07 |K02,3,5,8 ∧ (b̄|b̄|b̄|b̄)|K38 |K31,4,6,7 ∧ (h̄|h̄|h̄|h̄))T

2,3,5,88

8= (−1)α ·PL
T

1,4,6,7
6 ⊕K 6 ⊕F 6 (P 2,3,5,7,8 ⊕K 2,3,5,7,8 )]⊕β T ·CR⊕bT ·S 6 [PR
1
1
0
L
×

8

8

1,4,5,6,7(−1)h ·S [CL ⊕K2 ⊕F4 (CR46⊕K31,4,5,6,7 )] .

As Mi is (16 + 4(8 − W (b)) + 4(8 − W (h)))-level circulant, thisinformation is sufficient to define M completely. This requires
216+4(8−W (b))+4(8−W (h))
operations which are equivalent to216+4(8−W (b))+4(8−W (h)) · ( 58 + 18 + 85 + 18 )/11 =216+4(8−W (b))+4(8−W (h)) · 1.5/11 = 277.13−4W (b)−4W (h)11-round encryptions.
(c) The evaluation of the linear approximation for the subset of texts
with the corresponding
1,4,6,7(PL2,3,5,8 ∧ (b|b|b|b)|PR6 |CR∧ (h|h|h|h)|CL8 )value is given by the matrix vector product ǫi = M ·xi . This requires
9 · 2(16+4(8−W (b))+4(8−W (h))) · (16 + 4(8 − W (b)) + 4(8 − W (h)))
clock cycles.
b|h2. The global vector of bias ǫk for the particular choice of (b|h) and(K16 |K02,3,5,8 ∧ (b|b|b|b)|K28 |K31,4,6,7 ∧ (h|h|h|h))b|his the sum of ǫi : ǫk

=

X

ǫi .

i
b|h
3. Let Cκ = Cκ + (ǫk /N )2 .

We obtain 296 counters for Cκ corresponding to the evaluation of the bias ofthe linear approximation for the 96-bit subkey guess. The correct subkey is thenselected among the candidates with Cκ less than the threshold√√l
214.68214.692l
2 · 214.68· Z1−β0 +=·2+=.
t = σ0 · Z1−β0 + µ0 =
N
N
N
N
N
From Theorem 1 in Section of Data Complexity Reduction, the number ofknown plaintext-ciphertext pairs should satisfy the following condition:r
2n+0.52NN ≥ √ (z1−β1 1 + n + z1−β0 ).
2l47

If we set β0 = 0.023 and β1 = 2−106 , we get z1−β0 = 2 and z1−β1 = 11.85.
n = 128, l = 214.68 . As N = 2125.1 , the above condition can be satisfied.
The memory requirements in the data counting phase and the key counting
phase are 296 32-bit words and 272 nibbles, respectively. The memory requirements for the global counters Cκ are 296 256-bit words. Therefore, the wholememory complexity is about 2101 bytes.
The time complexity for the data counting phase is 214.68 · 2125.1 = 2139.78
memory accesses. In step (b) of the key counting phase, the time complexity isabout   88·
· 277.13+16+16+4·4+4·4 = 2153.39
4
4
11-round Camellia encryptions.
In step (c) of the key counting phase, the time complexity is about  
8
8··216+4·4+4·4+16+4·4+4·4+16+32+32−4·4−4·4 ·9·(16+32+32−4·4−4·4)) = 2165.01
4
4clock cycles, which is equivalent to 2165.01 ·24/(326·11) = 2157.79 11-round Camellia encryptions. Therefore, the whole time complexity is about 2157.79 11-round
Camellia encryptions.
Due to β1 = 2−106 , the total number of recovered bits is 96, the number ofthe remaining wrong subkey values is 2−106 · 296 = 2−10 .
Then we use other 7-round zero-correlation linear hulls to recover other subkey
bits as follows:
7r

1. Use (b|0|0|b|0|b|b|b, 0|0|0|0|0|0|0|0) → (0|0|0|0|0|0|0|0, 0|h|h|0|h|h|0|h), to recover K01,4,6 , K18 , K26 and K32,3,8 .
7r

2. Use (b|b|0|0|b|0|b|b, 0|0|0|0|0|0|0|0) → (0|0|0|0|0|0|0|0, 0|0|h|h|h|h|h|0) to recover K15 and K27 .
7r

3. Use (0|0|b|b|b|b|b|0, 0|0|0|0|0|0|0|0) → (0|0|0|0|0|0|0|0, h|h|0|0|h|0|h|h) to recover K17 and K25 .
7r

4. Use (0|b|b|b|0|b|b|b, 0|0|0|0|0|0|0|0) → (0|0|0|0|0|0|0|0, 0|h|h|h|0|h|h|h) to recover K11 and K21 .
7r

5. Use (b|0|b|b|b|0|b|b, 0|0|0|0|0|0|0|0) → (0|0|0|0|0|0|0|0, h|0|h|h|h|0|h|h) to recover K12 and K22 .
7r

6. Use (b|b|0|b|b|b|0|b, 0|0|0|0|0|0|0|0) → (0|0|0|0|0|0|0|0, h|h|0|h|h|h|0|h) to recover K13 and K23 .
7r

7. Use (b|b|b|0|b|b|b|0, 0|0|0|0|0|0|0|0) → (0|0|0|0|0|0|0|0, h|h|h|0|h|h|h|0) to recover K14 and K24 .

48

The time complexity with the later zero-correlation linear hull is much less thanthat with the first zero-correlation linear hull attack because many subkey bits
have been recovered in the first attack, so we can ignore it. Now, we have recovered
K0 , K1 , K2 and K3 .
The key schedule for Camellia-192 is similar as that for Camellia-256. The
only difference is that the 192-bit master key K = KL |KR and KRR = KRL .
According to the key schedule, we can write the following equations:
K0 = (KL ≪ 0)L ⊕ (KB ≪ 0)L ,(14)

K1 = (KL ≪ 0)R ⊕ (KB ≪ 0)R ,(15)

K2 = (KL ≪ 45)R ⊕ (KB ≪ 111)L .

(16)

K3 = (KA ≪ 45)L ⊕ (KB ≪ 111)R ,(17)

We will implement the following procedure to recover the 192-bit master key.
For each of the 2128 values of KB :1. Compute KL from Equation (14) and Equation (15).
2. Verify if KL and KB satisfy Equation (16), if so, go to next step.
45∼108 from Equation (17).
3. Compute (KA ≪ 45)L = KA
19
109∼127 to get K
4. For all 2 possible values of KA
AR :(a) Decrypt from KB to KAR with Fig. 16, and derive KRR to obtain themaster key K = KL kKRR .
(b) Using one pair of plaintext-ciphertext to verify the master key K.
109∼127 can always pass the verification for step 4,
The right guess for KB and KA
but the wrong guess will pass the verification with the probability 219+64−128 =2−45 . So we can recover the master key with high probability. The time complexity
to recover the master key is much less than that to recover 96-bit subkey in theprevious, so it can be negligible.
In all, the data complexity is 2125.1 known plaintexts, the time complexity is
about 2157.79 11-round Camellia-192 encryptions, and the memory requirements
are about 2101 bytes.

49

7
7.1

Biclique Cryptanalysis of CLEFIA
Summary

Again, we concentrate ourselves on the independent biclique approach with at
most a single-byte key modification, since this proved to be the way to go with
AES so far. Since CLEFIA has MDS matrices and the local SPN structure similar
to that of AES, it is reasonable to assume that such biclique attacks will do agood job also for CLEFIA. As in the case of Camellia, we adopt the approachof unlimited data complexity meaning a lower bound on the computational complexity of independent bicliques. It turns out though that the full codebook isnever needed for CLEFIA.
The key schedule of CLEFIA is complex compared to that of AES. Like in
Camellia, it again relies on an intermediate key L which is computed from theuser-supplied key K in a highly nonlinear manner. Now the subkeys in every
round (except for the whitening keys that depend on K only) depend on L.
The subkeys in rounds 3 and 4 in each 4-round block additionally depend on K.
This limits the length of bicliques compared to AES. We have found an efficient
key enumeration only for CLEFIA-128 and CLEFIA-256. Here we enumerate
the keys in each group with respect to L, since there are adjacent rounds where
the computation only depends on L. For CLEFIA-192, not every value of L
corresponds to a valid key K. The results reported below for CLEFIA-192 arebased on partial matching computational advantage only, that is, MITM without
the biclique initial structure. Here we enumerate keys with respect to K.
Our biclique results for CLEFIA are as follows. For the full CLEFIA-128, wereport a key recovery with computational complexity 2127.7 CLEFIA-128 operations, data complexity 264 , negligible memory complexity and success probability
1. For the full CLEFIA-192, there is a MITM key recovery with computational
complexity of 2191.5 CLEFIA-192 executions, negligible memory and data complexities as well as success probability 1. For the full CLEFIA-256, a key recovery
requires 2255.5 CLEFIA-256 executions, data complexity 264 , negligible memory
complexity and success probability 1. The low data complexity MITM-only attack on CLEFIA-128 and CLEFIA-256 is also possible which would lead to anincrease in the computational complexity and is hence not reported.
7.2

Cost of brute force key recovery: establishing base line

To establish the base line for the subsequent comparisons, we derive the complexity of the brute force key recovery that involves one full computation of thecipher for every key.

50

Table 6. Summary of our biclique key recoveries for full CLEFIA
cipherroundsattack type
data time memory
CLEFIA-128 18 (of 18) biclique MITM 264 CP 2127.7 small
CLEFIA-192 22 (of 22)
MITM
2KP 2191.5 small
CLEFIA-256 26 (of 26) biclique MITM 264 CP 2255.5 small

For CLEFIA, according to the standard computational model of biclique
cryptanalysis, the unit will be again (as for AES and Camellia) the application of an 8-bit S-box. Similarly to AES, this is arguably the most consuming
component in terms of implementations. As for AES and as opposed to Camellia,
4x4-byte MDS diffusion matrices are employed in CLEFIA. However, firstly, it
almost always goes with S-box computations (no separate account needed) and,secondly, the contribution of the matrix-vector multiplication is rather limited
compared to 4 8-bit S-boxes in most implementations.
Table 7. Cost of brute force for CLEFIA
data transform key schedule
total
total
(F -functions) (F -functions) (F -functions) (S-boxes)
CLEFIA-128
18R=36F
12R=24F
60F
240
22R=44F
10R=40F
84F
336
CLEFIA-192
CLEFIA-256
26R=52F
10R=40F
92F
368
cipherAs shown in Table 7, one CLEFIA-128 computation needs 240 S-box applications, since each F -function includes 4 S-box applications and there are equivalently 60 F -functions rounds in the full CLEFIA-128. Similar derivation holds for
CLEFIA-192 and CLEFIA-256 resulting in 336 and 368 S-boxes, respectively, in
total. The difference for CLEFIA-192 and CLEFIA-256 is though that instead of
12 rounds of a 4-line type-II GFN for CLEFIA-128, 10 rounds of a 8-line type-II
GFN are used, involving 4 F -functions per round instead of 2 F -functions.
7.3

Constructing bicliques over 2 rounds for CLEFIA-128 and
CLEFIA-256

Unlike for Camellia, we will construct an independent biclique using two forward
computations. In CLEFIA-128 and CLEFIA-256, we enumerate keys in a keygroup with respect to L. We place the key modification in the subkeys in round51

1. Subkeys RK0 and RK1 are just the first 64 bits of L added with a constantstring of bits. We construct bicliques as specified in Table 8.
The length of bicliques is limited by the key schedule. In a block of 4 rounds,
only rounds 1 and 2 depend on L only. Rounds 3 and 4 of a 4-round block, dependon both L and K. Given the complex relation between L and K, this modifies
the computation in rounds 3 and 4 completely even if only a slight change has
been made to L.
Table 8. 2-round bicliques and key modification for CLEFIA
ciphertype key modification subkey round number
forward 1
one byte
RK0
1
CLEFIA-128
forward 2
one byte
RK1
1
CLEFIA-192
one byte
W K0
whitening
forward 1
one byte
RK0
1
CLEFIA-256
forward 2
one byte
RK1
1

forward modiﬁcation 2

forward modiﬁcation 1

RK0
1

RK1
4

biclique

F0
RK2
4

0

RK0
0

0

F1

F0

RK3

RK2

4

F0

RK1
0

1

4

F1
RK3
4

F1

F0

4

F1

Fig. 17. Building a biclique over 2 rounds of CLEFIA-192 and CLEFIA-256:
Numbers indicate the number of active bytes in the F -function right after thesubkey addition and right after the diffusion layer. Numbers in grey circles indicate the spots of key difference injections

The key is modified only in the forward direction: one forward modification
is in the left-hand F -function and the other one is the right-hand F -function.

52

Since we modify a byte, the dimension of the biclique is 8. The actual bicliqueconstruction is outlined in Figure 17.
In the left-hand modification, the injection byte in RK0 activates the entire
output of F0 in round 1 which in turn activates the input and output of F0 inround 2. In the right-hand modification, the injection byte in RK1 activates theentire output of F1 in round 1 and, thus, the input to and output of F1 in round2.
It is easy to see that this is an independent 2-round biclique of dimension 8:
The forward key modifications are such that the propagations in both of them
are entirely independent for two rounds.
7.4

Key enumeration for CLEFIA-192

In CLEFIA-192, the keys are enumerated with respect to K. We can be more
precise and say that we modify one byte in KL which corresponds to a byte modification in one of the two prewhitening keys W K0 or W K1 . The exact positionof this modification is rather not important since the operation of the first round
depends on L that in turn depends on K in a complex way. This will make thecomputation starting from the first round as for a completely fresh key.
Note that we cannot efficiently construct a nontrivial independent biclique for
CLEFIA-192. This is due to the fact that we want to enumerate the keys withrespect to L since there are rounds in CLEFIA data path that just depend on L.
However, not every value of L to corresponds to a valid value of K (user-suppliedkey) in CLEFIA-192. This is because of the redundancy that is introduced to K
before it is passed to the 10-round 8-line type-II GFN for the derivation of L:
The last 64 bits of the input depend on other 64 bits in K.
7.5

Partial matching over 5 rounds

The construction of the CLEFIA data transform is such that is allows for a partial
matching over 5 rounds. These matching rounds can be placed in the middleof the cipher. An illustration is provided in Figure 18. As opposed to bicliqueconstruction, partial matching can be performed for all CLEFIA versions.
We match the middle of the 5 rounds in one byte of a 4-byte quarter state. It
suffices to recompute 16 S-boxes instead of 40 that would be needed for matchingon the full state, resulting in a saving of 24 S-boxes. Note that no recomputationis needed in round 3 of the 5-round block. Only 4 S-boxes need to be recomputedin the other 4 rounds.

53

0

4

0

F0

0

F1

0

F1

1

0

F0

0

0

F0

0

0

F1

1

1

4

1

4

F0

0

4

0

F1

0

4

F0

4

F1

Fig. 18. Partial matching over 5 rounds of CLEFIA: Numbers indicate the number of bytes to be recomputed in the corresponding lines. The number in grey
circle indicates the byte of matching
7.6

Recomputing the key scheduleThough the key recovery does not specify any further savings in the data transform of CLEFIA and all S-boxes in the remaining rounds have to be recomputedfor every key, some more savings are possible in the key schedule.
In CLEFIA-128, the key schedule consists of 12 rounds of the data transform
applies to K with constants as round keys to obtain L. Since we enumerate keys
with respect to L, we need to apply decryption for every modification of L. Since
we modify in two distinct 32-bit subkeys, this will have effect on two lines of input
to the inverse 4-line GFN. The first 3 of 12 rounds do not have to be recomputed
entirely. One S-box is recomputed in round 1, 4 S-boxes in round 2 and 5 S-boxes
in round 3 of the inverse GFN. This results in a saving of 10 S-boxes.

54

In CLEFIA-192, keys are enumerated with respect to K. A single byte ismodified there. So we have to check how many computations are actually neededin the forward 8-line 10-round type-II GFN if only a byte of its input gets modified. In round 1, no S-boxes need recomputation. Only 1 S-box is recomputed inround 2, followed by 4 S-boxes in round 3 and 5 in round 4. Similarly, we can seethat even in round 8 only 13 out of 16 S-boxes need recomputation. In rounds 9
and 10, all 16 S-boxes are recomputed. In total, this yields 84 S-boxes instead of
160 which gives a saving of 76 S-boxes. Similarly, for CLEFIA-256, we obtain asaving of 60 S-boxes.
7.7

Complexity

In total, we have saved 16 S-box computations due to the construction of thebiclique for CLEFIA-128 and CLEFIA-256 and 0 S-boxes for CLEFIA-192, 24
S-box computations due to the partial matching, as well as another 10, 76 and
60 S-box computations due to the optimized recomputation in the key schedule,
in CLEFIA-128, CLEFIA-192, and CLEFIA-256, respectively. This results incoincidentally round numbers of 50, 100 and 100 S-boxes saved per key tested,correspondingly.
Thus, the computational complexity for CLEFIA-128 is
240 − 24 − 16 − 10 128
2 ≈ 2127.7 .
240
For CLEFIA-256, we have time complexity of
368 − 24 − 16 − 60 256
2 ≈ 2255.5 .
368
For CLEFIA-192, we need336 − 24 − 76 256
2 ≈ 2191.5
336
computations without the biclique saving. Note that we do not take into accountthe complexity of biclique construction since the dimension of the biclique is large
enough to make it negligible. Memory complexity in the biclique construction andrecomputations within the key group is negligible because of the limited bicliquedimension.
The data complexity for CLEFIA-192 is just the unicity distance which is 2
known- plaintexts here, due to the absence of any initial structure. For CLEFIA128 and CLEFIA-256, we start with a constant value for all keys after prewhitening and before round 1 where the forward modifications are applied. So in the55

backward recomputation, the only parts of the plaintext affected by the modifications are the 64 bits whitened by the prewhitening which depends on K. So
the data complexity is 264 chosen plaintexts.

88.1

Zero Correlation Linear Cryptanalysis of CLEFIA
Summary

For many ciphers, especially for those with XOR addition of the round subkeys,
the partial encryption and decryption in the basic zero correlation cryptanalysis
is performed many times for the same value. The technique is to precomputeall required intermediate values for all key bits involved into partial encryption/decryption and to store them instead of recomputing again once needed.
This technique can be seen as equivalent to the discrete Fast Fourier Transformand significantly reduces the computational complexity of the zero correlation
linear cryptanalysis at the expense of introducing some memory complexity.
The data transform of CLEFIA (type-II generalized Feistel network with 4lines) exhibits a set of about 232 9-round zero-correlation linear approximations of
the form (0, 0, 0, a) → (a, 0, 0, 0). So we have a budget of about 232 approximations
for the data complexity reduction with the multidimensional zero-correlation distinguisher. We can attain either a data complexity reduction of factor about 216
or trade it off for time complexity reduction and/or more attacked rounds whencombined with the discrete FFT.
Our zero correlation results for CLEFIA are the following. For the purposeof evaluation, we only report the attacks on the highest numbers of rounds wehave found, even if they require the full codebook. As a matter of fact, we canattack less rounds with much lower complexities. First, as regards CLEFIA-192,
we can attack 13 rounds of it using 2125.8 data and 2159.56 operations equivalent
to 13 rounds of CLEFIA-192, and 2104 blocks of memory. Second, we can attack
14 rounds of CLEFIA-256 with 2128 texts, 2222 time, and 2136 blocks of memory.
Table 9. Summary of our zero correlation attacks on round-reduced CLEFIA
cipherrounds attack type data time memory
CLEFIA-192 13 zero correlation 2125.8 2159.56 2104
CLEFIA-256 14 zero correlation 2128 2222
2136

56

8.2

9-round zero-correlation linear approximations for CLEFIA anddistiguisher

In this section, we will give some zero-correlation linear hulls for 9-rounds CLEFIA. We find (a, 0, 0, 0) → (0, 0, 0, a), with input select pattern (a, 0, 0, 0) andoutput select pattern (0, 0, 0, a),a s described in the figure. We can use the linear
hulls to attack more rounds block cipher.
0

0

a

a

c

a

a
a

0 bb

a 0a

0 dd

0

b

a

0 00

a 0a

0

c

a

input
0 0
0

0
0

0

0

a

0

0

0

a 0a

0 00

0 00

0

a

a
a

0

0

0

0

a 0a

0

0

0

0

0

0

output
0
0

b

0 00

0 cc

a
a

d
d

a 0a
0
0
zero-correlationa, b, c, d = nonzero linear selection patterns

0Fig. 19. 9-round zero-correlation linear approximation for CLEFIA-type ciphers(type-II generalized Feistel network) with balanced F-functions
The original zero-correlation linear analysis used only a few linear approximations and had a high data complexity close to 2128 for CLEFIA. That is to say,we should use all the plaintext-ciphertext pairs. If we want to reduce the data
complexity we should use more linear hulls.
We will be using the following technique to reduce the data complexity of ourattacks:– Distinguishing between two normal distributions
Consider two normal distributions, which can be seen as randomly drawn
permutation and real block cipher respectively: N (µ0 , σ0 ) with mean µ0 andstandard deviation σ0 , and N (µ1 , σ1 ) with mean µ1 and standard deviation
σ1 . Without loss of generality, assume that µ0 < µ1 . A sample s is drawn
from either N (µ0 , σ0 ) or N (µ1 , σ1 ). It has to be decided if this sample is fromN (µ0 , σ0 ) or from N (µ1 , σ1 ). The text is performed by comparing the value s
to some threshold value t. If s ≤ t, the test returns ”s ∈ N (µ0 , σ0 )”, otherwise,
if s > t, the test returns ”s ∈ N (µ1 , σ1 )”. There will be error probabilities of
two types:57

β0 = P r”s ∈ N (µ1 , σ1 )”|s ∈ N (µ0 , σ0 )β0 = P r”s ∈ N (µ1 , σ1 )”|s ∈ N (µ0 , σ0 )Here conditions are given on µ0 , µ1 , σ0 , σ1 such that the error probabilities are
not higher than β0 and β1 .
For the test to have error probabilities of at most β0 and β1 , the parametersof the normal distributions N (µ0 , σ0 ) and N (µ1 , σ1 ) with µ0 < µ1 have tobe such thatz1−β1 + z1−β0≤ 1.
µ1 − µ0– Known plaintext distinguisher for many zero-correlation linear hulls.
Let the adversary be given N known plaintext-ciphertext pairs and ℓ zerocorrelation linear hulls for an n-bit block cipher with a fixed secret key. The
adversary aims to distinguish between this cipher and a randomly drawn
permutation.
The procedure is as follows. For each of the ℓ given linear hulls, the adversary
computes the number Ti of times the linear hull is fulfilled on N plaintexts,i ∈ 1 · · · ℓ. Each Ti suggests an empirical correlation value Ci = 2 TNi − 1. Thenthe adversary evaluates the statistic:Pℓ2
i=1 (Ci ) =

Pℓ

Ti
2
i=1 (2 N − 1)

(18)

It is expected that for the cipher with ℓ known zero-correlation linear hulls,
the value of statistic (1) will be lower than for random ℓ linear approximationsof a random drawn permutation. In a key-recovery setting, the right key will
result in statistic (1) being among the lowest values for all candidate keys ifℓ is high enough.
In the sequel, we treat this more formally.
– Data complexity for the distinguisher
For ℓ zero-correlation linear hulls,eachof the values Ci in (1) will be approxi√
mately distributed as N (0, 1/ N ). For a random permutation and a random
linear approximation, the value of Ci will be approximately distributed as
N (bi , √1N ), where bi is the exact value of the correlation which is itself distributed as N (0, 2−n/2 ).
Now we will derive the distribution of statistic (1) in these two cases.
1. Cipher: zero-correlation linear hulls In case we deal with ℓ zero-correlation
linear hulls:
ℓ
X
i=1

Ci2 ∼

ℓ
X
i=1

ℓ
X
√
N 2 (0, 1) = 1/N χ2ℓ
N (0, 1/ N ) = 1/N
2

i=1

58

with ℓ degree of freedom which has mean
Where χ2ℓ is the χ2 -distribution√
to theℓ and standard deviation 2ℓ. For sufficiently large ℓ, χ2ℓ converges√
2normal distribution. That is, χℓ approximately follows N (ℓ, 2ℓ).and:Pℓ2
2
i=1 Ci ∼ 1/N χℓ ≈ 1/N N (ℓ,√√2ℓ) = N ( Nℓ , N2ℓ )(19)Consider ℓ nontrivial zero-correlation linear hulls for a block cipher witha fixed key. If N is the number of plaintext-ciphertext pairs, Ti is thenumber of times such a linear hull is fulfilled for i = 1 · · · ℓ, and ℓ ishigh enough, then the following approximate distribution holds:
√
ℓ
X
Ti
ℓ
2ℓ
2
(2 − 1) ∼ N ( ,
)
N
N N
i=1

2. Random permutation: random linear approximations In case we deal witha randomly drawn permutation, the ℓ given linear hulls will correspond toa set of random linear approximations. Thus, as mentioned above:
ℓ
X
i=1

Ci2 ∼

ℓ
X
i=1

√
N 2 (bi , 1/ N ), where bi ∼ N (0, 2−n/2 )Consider ℓ random nontrivial linear approximations for a randomly drawn
permutation. If N is the number of plaintext-ciphertext pairs, Ti is thenumber of times such a linear hull is fulfilled for i = 1 · · · ℓ, and ℓ ishigh enough, then the following approximate distribution holds:
r
ℓ
X
ℓ
ℓ 1
N
Ti
2
2(ℓ + 2ℓ n ))(2 − 1) ∼ N ( + n ,
N
N
2 N
2
i=1

3. Combining what has been said, one obtains the condition:q√z1−β0 N1 2(ℓ + 2ℓ 2NN ) + z1−β1 N1 2ℓ≤1( Nℓ + 2ℓn ) − Nℓ
For an n-bit block cipher, let ℓ nontrivial zero-correlation linear hulls be
given. Then, to distinguish it from a randomly drawn permutation withprobability β1 of false positives and probability β0 of false negatives,a number N of known plaintext-ciphertext pairs is sufficient if thefollowing condition is fulfilled:r2N
2n+0.5√ (z1−β0 1 + n + z1−β1 ) ≤ 1
2
N ℓ

59

The success probability of an attack is defined by the probability β0 of false
negatives. The probability β1 of false positives determines the number ofsurviving key candidates and, thus, the complexity of the key recovery.
Making β0 ≈ 0.023 and β1 ≈ 2−50.5 . Thus the following statement holds:
For probability β0 ≈ 0.023 of false negatives, probability β1 ≈ 2−50.5 offalse positives, and N ≤ 2n−1 , the condition on the data complexityis:2n+3.94N≥ √ .
ℓ
8.3

Attack on 13-round CLEFIA-192

We take advantage of a large number of 9-round zero-correlation linear approximations of (a, 0, 0, 0) → (0, 0, 0, a) kind to attack 13-round CLEFIA-192, theapproximation covers round 3 to 11, and has 32 active bits in the first and lastround. Now we find out 392 ∗ 32 different linear hull of this type and we also
make sure all α have the following property: when they go through the inverse of
the M1 they have only one active byte, but when they go through the inverse of
the M0 they have 4 active bytes. This kinds of α can be made sure that have thelowest time complexity.
Let us denote by E = (E0 , E1 , E2 , E3 ) the value of the encryption stateat the beginning of the third round, and by D = (D0 , D1 , D2 , D3 ) the valueof encryption state at the end of the 11 round. All the possible 9-round zerocorrelation linear approximation used can be written as: aT · E0 ⊕ aT · D3 . In
order to evaluate the bias of this linear approximations, we have to perform apartial encryption of two first rounds and a partial decryption of the two lastrounds.
According to the structure of CLEFIA, we can get the following relations:aT · E 0 =aT · P2 ⊕ aT · F0 (RK2 ⊕ WK0 ⊕ P1 ⊕ F0 (RK0 ⊕ P0 ))(20)

aT · D3 =aT · C2 ⊕ aT · F1 (RK2r−3 ⊕ WK2 ⊕ C1 ⊕ F0 (RK2r−2 ⊕ C0 ))(21)

For compactness, we will be using the following notation:
K0 = RK0
K1 = RK2 ⊕ WK0

60

P0

K0=RK0

F0

P1

P3

P2



F1



F1



K1=RK2Ͱ WK0F0K2=RK2r-3ͰWK2
F0



F1





F1



K3=RK2r-2
F0
C0

C1

C2

C3

Fig. 20. Zero correlation linear attack on 13-round CLEFIA-192

61

K2 = RK2r−3 ⊕ WK2
K3 = RK2r−2
the linear approximation can be written as:aT · (P2 ⊕ C2 ) ⊕ aT · F0 (K1 ⊕ P1 ⊕ F0 (K0 ⊕ P0 ))⊕aT · F1 (K2 ⊕ C1 ⊕ F0 (K3 ⊕ C0 ))(22)

We want to use FFT methods to reduce the time complexity, which the linear
approximation is required to be expressed as a circulant matrix. We can observethat neither aT · F0 (K1 ⊕ P1 ⊕ F0 (K0 ⊕ P0 ) nor aT · F1 (K2 ⊕ C1 ⊕ F0 (K3 ⊕ C0 ))can be expressed as a circulant matrix because K1 and K2 need to be guessed andmoreover, P1 and C1 need to be traversed. However, by guessing of fixing theseparameters, it is possible to decompose the expression in smaller parts which
involve the following circulant matrix:
M (P0 |C0 , K0 |K3 ) =(23)
aT · F0 (K1 ⊕ P1 ⊕ F0 (K0 ⊕ P0 )) ⊕ aT · F1 (K2 ⊕ C1 ⊕ F0 (K3 ⊕ C0 )).
The attack works as follows:– Data counting phase:
1. For each of the 240 value i of (P1 , C1 ), define vector xi of 240 counters.
2. For each of the plaintext-ciphertexts (P, C), extract the 40 bits valuei = (P1 , C1 ) and the 64-bit value j = (P0 , C0 )3. Increment or decrement the counter j of the vector xi according to theparity of aT · (P2 ⊕ C2 ).
– Key counting phase: For each possible 40-bit value k of (K1 |K2 ):1. For each possible 40-bit value of (P1 , C1 ):(a) Select the corresponding vector of counters xi(b) Compute the first column Mi of the matrix
Mi (P0 |C0 , K0 |K3 ) =TT(−1)a ·F0 (K1 ⊕P1 ⊕F0 (K0 ⊕P0 ))⊕a ·F1 (K2 ⊕C1 ⊕F0 (K3 ⊕C0 )) .
As Mi is 64-level circulant, this information is sufficient to define M
completely (requires 264 operations).
(c) The evaluation of the linear approximation for the subset of texts withthe corresponding (P1 |C1 ) value is given by the matrix vector productǫi = M · xi (requires 64 · 264 operations).
2. The global X
vector of bias ǫk for the particular choice of (K1 |K2 ) is the sumof ǫi : ǫk =
ǫi .
i

62

At the end of the key counting phase, we obtain 240 vectors ǫk of size 264
corresponding to the evaluation of the linear approximation of the bias of thelinear approximation for the 104-bit key guess (K0 , K1 , K2 , K3 ). The correct key
is then selected among the candidates with a corresponding counter equal to 0.
We want to reduce the data complexity down to 2125.8 from 2128 , we choose 213.61
different α to evaluate the correlation. The data counting phase has a memory
complexity of 2104 counters since we must store 240 vectors of 264 counters. Itstime complexity is the number of plaintext-ciphertext pairs N = 2125.8 . The key
counting phase is dominated by the matrix vector product, which is performed forevery guess of K1 |K2 and every choice of P1 |C1 . The time complexity of this phaseis thus 213.61 · 240 · 240 · 64 · 264 · 9 = 2166.78 clock cycles. CLEFIA-192 encryption
need 15.8 cycles for a byte, then 15.8 · 16 cycles for 16 bytes. We also know that
CLEFIA-192 is 22 rounds, then 13 rounds CLEFIA here need 252.8/22 · 13 = 149
cycles. Then the time complexity is: 2166.78 /149 = 2159.56 .
The output linear pattern to evaluate becomes:′

bT · D = bT · (M−1
1 (C2 ) ⊕ S1 (K2 ⊕ C1 ⊕ F0(K3 ⊕ C0 )))





K0

X0

bĄЬDĄ
S1
0

K1

X1

y0

y1

S0

K2

X2

M1
0

K3

X3

y2

S1
0
S0

Fig. 21. Selection pattern before M1

63

y3

(24)

8.4

Attack on 14-round CLEFIA-256

We also use the 9-round zero-correlation linear approximation to attack 14round CLEFIA-256. This approximation covers round 4 to 12, and has 32 active bits in the first and last round. Let us denote by E = (E0 , E1 , E2 , E3 ),the value of the encryption state at the beginning of the fourth round, and by
D = (D0 , D1 , D2 , D3 ) the value of the encryption state at the end of 12 round.
In order to evaluate the bias of this approximations, we perform a partial encryption of three first rounds and a partial decryption of the two last rounds, then the
9-round zero-correlation linear approximation can by written as: aT · E0 ⊕ aT · D3 .
The relations can be derived:aT · E0 =aT · (P3 ⊕ F1 (k1 ⊕ P2 ) ⊕ F0 (k3 ⊕ P2 ⊕ F0 (k2 ⊕ P1 ⊕ F0 (k0 ⊕ P0 ))))

(25)

aT · D3 = aT · (C2 ⊕ F1 (k4 ⊕ C1 ⊕ F0 (k5 ⊕ C0 )))(26)

aT · E0 ⊕aT · D3 =aT · (P3 ⊕ C2 )⊕aT · (F1 (k1 ⊕ P2 ) ⊕ F0 (k3 ⊕ (P2 ) ⊕ F0 (k2 ⊕ F0 (k0 ⊕ P0 ))))⊕
aT · F1 (k4 ⊕ C1 ⊕ F0 (k5 ⊕ C0 ))(27)

We have:

Guess the key bits (k1 , k2 , k3 , k4 ), and fixing the parameters (P1 , P2 , C1 ), it ispossible to decompose the expression in smaller parts which involve the following
circulant matrix:
M (P0 |C0 , k0 |k5 ) =aT · (F1 · (k1 ⊕ P2 ) ⊕ F0 (k3 ⊕ P2 ⊕ F0 (k2 ⊕ P1 ⊕ F0 (k0 ⊕ P0 ))))⊕
aT · F1 (k4 ⊕ C1 ⊕ F0 (k5 ⊕ C0 )).

(28)

The attack proceeds as follows:– Data counting phase:
1. For each of the 272 values i of (P1 , P2 , C1 ), define vector xi of 272 counters.
2. For each of the plaintext-ciphertext (P, C), extract the 72 bits valuesi = (P1 , P2 , C1 ) and the 64 bits value j = (P0 , C0 ).
3. Increment or decrement the counter j of the vector xi according to theparity of aT · (P3 ⊕ C2 ).

64

P0

K0=RK0

F0

P1

P2



K1

P3

F1



F1



F0



K2=RK2Ͱ WK0
F0

K3



K3=RK4Ͱ WK1
F0



K4
F0



F1





F1



K5

F0
C0

C2

C1

C3

Fig. 22. Zero correlation linear attack on 14-round CLEFIA-256

65

– Key counting phase: for each possible 80-bit value k of (k1 , k2 , k3 , k4 ):1. For each possible 72-bit value i of (P1 , P2 , C1 ):(a) Select the corresponding vector of counters xi(b) Compute the first column Mi of the matrix
Mi (P0 |C0 , k0 |k5 ) =TT(−1)a ·(F1 ·(k1 ⊕P2 )⊕F0 (k3 ⊕P2 ⊕F0 (k2 ⊕P1 ⊕F0 (k0 ⊕P0 ))))⊕a ·F1 (k4 ⊕C1 ⊕F0 (k5 ⊕C0 )) .
As Mi is 64-circulant, this information is sufficient to define M completely (requires 264 operations).
(c) The evaluation of the linear approximation for the subset of texts withthe corresponding (P1 , P2 , C1 ) value is given by the matrix vector
product ǫi = M · xi (requires 64 · 264 clock cycles.)2. The global vector ofX
bias ǫk for the particular choice of (k1 , k2 , k3 , k4 ) is
the sum of ǫi : ǫk =ǫi .
i

At the end of the key counting phase, we obtain 280 vectors ǫk of size of 264
corresponding to the evaluation of the bias of the linear approximation for the
144-bit subkey guess. The correct subkey is then selected among the candidates
with a corresponding counter equal to 0. The data counting phase has a memory
complexity of 2136 counters since we must store 272 vectors of 264 counters, its
time complexity is the number of plaintext-ciphertext pairs N = 2128 . The key
counting phase is dominated by the matrix vector product. which is performed
for every guess of (k1 , k2 , k3 , k4 ) and every choice of (P1 , P2 , C1 ), the timecomplexity of this phase is thus 280 · 272 · 64 · 264 = 2222 operations.

99.1

Biclique and MITM Cryptanalysis of SC2000
Summary

The computational advantage over brute force that can be gained with independent biclique key recovery usually originates from two major sources. First, if abiclique of a significant length can be built, the recomputation cost of the statesat the boundaries of the biclique for each key covered by the biclique is relatively
small. Second, if the structure of the cipher in question allows one to performpartial matching over a considerable number of rounds (which mainly depends
on how fast the diffusion in the data transformation is), one obtains an additional
advantage in computational complexity.

66

The key enumeration in biclique key recovery is usually done in some suitableround subkey or several round subkeys (for forward and backward key modification). The attacker’s hope is then that some local change in the subkey(s) will
only cause local modifications in the internal state (block of data being operatedwith) for a significant number of rounds in both forward and backward directions. Another important issue to make the key recovery successful is to ensure
the near-to-full coverage of the user-supplied keys with the biclique construction.
Even for ciphers with a slow local diffusion in the data transform, constructing
bicliques of significant length can be made complex by complex and/or noninvertible key schedules. This is due to the complication with the enumeration of
the keys with respect to the base key in a biclique. The complication can be bothdue to the shortage in master key coverage that would destroy any computational
advantage one can get though constructing a biclique and due to the complex
dependencies of the block data to be operated with on the forward/backward
modification of the subkey. The structure of the SC2000 key schedule is suchthat it does not allow one to efficiently construct independent bicliques.
However, even if one deals with a complex and non-invertible key schedule thatwould prohibit the advantage through the biclique construction, it is still possible
to gain computational advantage from the partial matching in an exhaustive
meet-in-the-middle key recovery. Actually, this is the case for SC2000. The results
reported below are due to this type of analysis.
Our cryptanalytic results as regards SC2000 are as follows. For the full SC2000128, we report a MITM key recovery with computational complexity equivalent
to 2126.5 SC2000-128 operations including key schedule as well as negligible data
and memory complexities. For the full SC2000-192, we have found a MITM key
recovery with computational complexity equivalent to 2190.6 SC2000-192 operations incl. key schedule as well as negligible data and memory complexities. For
the full SC2000-256, we provide a MITM key recovery with computational complexity equivalent to 2254.5 SC2000-256 operations incl. key schedule as well as
negligible data and memory complexities. Note that the factors of advantage are
relatively high even given the fact that we were unable to construct bicliques efficiently so far. The relatively high gain is not least due to the heavy key schedule
whose cost can be leveraged in a MITM key recovery.
Table 10. Summary of our biclique key recoveries for full SC2000
cipherrounds attack type datatime memory
SC2000-128 6.5 (of 6.5) MITM 1 or 2KP 2126.5 small
SC2000-192 7.5 (of 7.5) MITM
2KP 2190.6 small
SC2000-256 7.5 (of 7.5) MITM 2 or 3KP 2254.5 small

67

9.2

Complexity of brute force key recovery

To quantify the complexity of the brute force key recovery with success probability
1, we again look at the non-linear operation of the cipher. For SC2000, there are 3
different types of S-boxes: 4-bit, 5-bit and 6-bit. For the sake of simplicity, we willconsider the complexity of these S-boxes equal in our analysis. Strictly speaking,this is not true though and the 6-bit S-box is about 4 times more costly to
implement than the 4-bit S-box. However, since there are a lot of S-boxes we will
be counting in the complexity estimations of each type, making this distinction
would not have much effect on the complexity estimations here.
Thus, according to the computational model introduced in the biclique attacks
for AES, the unit will be the application of one S-box. The other operations of thedata transform are linear and comparatively less costly. Also for the operation in
the key schedule, the S-boxes account for a major part of computations.
Table 11. Computational base line for SC2000 (brute force)one B #B one R #R key scheduletotal(S-boxes)(S-boxes)(S-boxes)
SC2000-128
32
7
12
12
576
368+576=944
SC2000-192
32
8
12
14
576
424+576=1000
SC2000-256
32
8
12
14
576
424+576=1000
cipherAs indicated in Table 11, one SC2000-128 computation requires in total 944
S-box applications, since each round transform includes 7 B functions and 12 R
functions and the key schedule requires another 576 iterative applications of the
S-boxes. Similar applies to SC2000-192 and SC2000-256 yielding a total of 1000
S-box applications.
9.3

Key enumeration

The key schedule of SC2000 is non-invertible which complicates the constructionof bicliques. The non-invertibility of the key schedule follows from the fact thatthe values a, b, c and d in the key schedule are obtained by xoring values derived
from two adjacent master key words uk[i] and uk[i + 1]. Furthermore, the actual
32-bit subkey ek can depend on much more than 2 master key words uk due tothe extended-key generation function that is also not invertible in ek.
We do not construct a biclique but still have to enumerate the keys efficiently.
We divide the key space into groups and modify at most 5 bits at a time. The

68

modification is placed in uk[0] which is the first 32 bits of the user-supplied key inall SC2000 versions. Modifying in uk[0] means that we need to compute the keyschedule only forwards so that its non-invertibility does not matter. In the key
recovery, we start with a base key, modify it and compute forward and backward
looking for a match.
Table 12. Key modification for SC2000
key modification subkey
cipher
SC2000-128
5 bitsuk[0]SC2000-192
5 bitsuk[0]SC2000-256
5 bitsuk[0]9.4Partial matching over 3 rounds

SC2000 does allow for an efficient partial matching over many rounds due tothe low-diffusion structure of its data transform though. If the sequence of consecutive functions consisting of I, B, I and double R with appropriate masks
and connections is one round, then it is possible to perform a partial matchingover 3 rounds of SC2000 (out of 6.5 rounds for SC2000-128 and 7.5 rounds for
SC2000-192/256). This allows for savings which is illustrated in Figure 23.
We match in the B function of round 1 in the 3-round block on 8 bits - tworightmost 4-bit S-boxes in B. While a regular recomputation would require 56
S-box computations, the partial matching requires a recomputation of only 30 Sboxes in round 1, 14 S-boxes in round 2, and 42 5-boxes in round 3 of the 3-roundblock. Thus, the total saving through the matching is 82 S-box computations.
9.5

Recomputation in the key schedule

While S-boxes in the remaining rounds of the data transform need to be recomputed for every key, there is still some room for savings in the key schedule. In
fact, the brute force computation of the key schedule is far from efficient.
To compute the values of a[i], b[i], c[i] and d[i], we need 4 iterations of a loop
each of which straightforwardly involves 16 layers (S) of 6 S-boxes each (2 6-bit
S-boxes and 4 5-bit S-boxes).
For SC2000-128, out of all those S-boxes, one needs to recompute one S-box
in S(uk[0]) and one S-box in S(uk[4]) as well as the agregations (full layers of 6
S-boxes each) before the final linear diffusion to deliver a[i] and c[i]. This amounts
to 14 S-box recomputations in the first iteration and 12 S-boxes in each of thefollowing 3 iterations. The saving is 576-50=526 S-boxes.
For SC2000-192, it is one S-box in S(uk[0]) and one in S(uk[6]) that require
recomputation along with the corresponding two full layers for aggregation, giving

69

I
B
I

18

R

12

R

0

I
B
I

2

R

0

R

12

I
B
I

18

R

12

R

12

Fig. 23. Partial matching over 3 rounds for SC2000: Numbers indicate the number of S-boxes to be recomputed in the corresponding functions (B or R). The
number in grey circle indicates the point of matching
again 14 S-box recomputations in the first iteration and 12 S-boxes in teach of
the subsequent ones, saving again 576-50=526 S-boxes
For SC2000-256, it is only one S-box in S(uk[0]) and the corresponding 6
S-boxes of aggregation, yielding just 7 S-boxes, that need recomputation in thefirst iteration. Each subsequent iteration involves 6 S-boxes. The saving amounts
to 576-25=551 S-boxes.
We notice that the significant savings in the key schedule are mostly due to thebiclique-type computational model assumed and the inefficiency of the reference
point. However, we are not aware of a better model here and stick to the standard
one.
9.6

Complexity

The savings are as follows. We have a saving of 82 S-box computations due tothe partial matching and over 500 S-box computations due to the recomputation

70

with precomputations in the key schedule. Due to heavy and non-invertible keyschedule, it is difficult to efficiently construct non-trivial biclique to attain further
savings.
The computational complexities are:944−82−526 128
2 ≈ 2126.5 for SC2000-128944
1000−82−526 192
2 ≈ 2190.6 for SC2000-192, and
1000
1000−82−551 256
2 ≈ 2254.5 for SC2000-256.
1000

We omit the false positive testing complexity and the precomputation complexities as we have enough matching bits and the key group is large enough and thosewould not have a major impact.
Memory complexity is negligible and is mainly due to the precomputations
while recomputing. The data complexity of this key recovery is just the unicity
distance since we did not employ any initial structure. The data complexity for
SC2000-128 is, thus, 1 or 2 known plaintext-ciphertext pairs, for SC2000-192 it
is 2 known plaintexts and for SC2000-256 one requires 2 or 3 known plaintexts.

10

Executive Conclusions

With respect to the novel biclique cryptanalysis and MITM attacks, all ciphersinvestigated (AES, Camellia, CLEFIA, SC2000) exhibit some properties thatallow one to recover the key slightly faster than brute force. Based on our results
so far, one can say that the effect of biclique cryptanalysis on Camellia, CLEFIAand SC2000 is lower than that on AES. Moreover, for AES-128 we have founda property akin to that of the complementation property for DES in terms of
its effect on the key recovery: Using just the minimum number of plaintexts(1 or 2 KP), the key recovery complexity drops from 2128 to 2126.7 AES-128
computations. More specifically, we exhaustively analyze the most promising classof biclique cryptanalysis as applied to AES-128: Namely, under some reasonable
restrictions, we enumerate all its independent bicliques and stars. In this classof bicliques for AES-128, in a computer-assisted search, we find optimal attacks
towards lowest computational and data complexities:– Among attacks with the minimal data complexity of the unicity distance (i.e.
1 known plaintext is enough with probability 1/e and 2 known plaintexts are
sufficient for success probability 1), the one of computational complexity 2126.7
is fastest. Note that its time complexity is only marginally higher than thatof the original attack, while it requires only 1 or 2 known plaintexts insteadof 288 chosen ciphertexts. This attack has stars instead of balanced bicliques
at its core.

71

– Among attacks with data complexity less than the full codebook, the onesof computational complexity 2126.16 are fastest. Among those, the one withdata complexity 264 requires the smallest amount of data. Thus, the original
attack did not have the optimal data complexity.
– Among all attacks covered, the one of computational complexity 2125.6 isfastest, though requiring the full codebook. This can be considered as anindication of the limitations of the independent-biclique attack approach as
applied to AES-128.
Thus, this report explores the limits of the most promising class of bicliques so
far in terms of minimizing time and data complexities.
With respect to zero-correlation linear cryptanalysis, we discovered someproperties over a reduced number of rounds for Camellia and CLEFIA exploitablefor key recovery. Based on our results, one can say that Camellia and CLEFIA
look robust enough to zero correlation cryptanalysis. Whereas we could attack
only less than the half of rounds for Camellia, we were successful for a higher portion of rounds in CLEFIA. Thus, Camellia looks somewhat more secure againstzero-correlation cryptanalysis than CLEFIA does.

References
1. Kazumaro Aoki, Tetsuya Ichikawa, Masayuki Kanda, Mitsuru Matsui, Shiho Moriai, Junko
Nakajima, Toshio Tokita: Camellia: A 128-Bit Block Cipher Suitable for Multiple Platforms- Design and Analysis. Selected Areas in Cryptography 2000:39-56
2. Kazumaro Aoki and Yu Sasaki. Preimage attacks on one-block MD4, 63-step MD5 andmore. In Selected Areas in Cryptography’08, volume 5381 of Lecture Notes in Computer
Science, pages 103–119. Springer, 2008.
3. Kazumaro Aoki and Yu Sasaki. Meet-in-the-middle preimage attacks against reduced SHA0 and SHA-1. In CRYPTO’09, volume 5677 of Lecture Notes in Computer Science, pages
70–89. Springer, 2009.
4. Dongxia Bai, Leibo Li: New Impossible Differential Attacks on Camellia. ISPEC 2012:80-96
5. Behran Bahrak and Mohammad Reza Aref. A novel impossible differential cryptanalysis of
AES. In Proceedings of the Western European Workshop on Research in Cryptology 2007
(WEWoRC’07), pages 152–156, 2007.
6. Behran Bahrak and Mohammad Reza Aref. Impossible differential attack on seven-round
AES-128. IET Inf. Secur., 2(2):28–32, June 2008.
7. Eli Biham, Alex Biryukov, Adi Shamir. Cryptanalysis of Skipjack reduced to 31 rounds
using impossible differentials. Advances in Cryptology: EUROCRYPT’99, LNCS, vol. 1592,
pp. 12–23, Springer-Verlag, 1999.
8. Alex Biryukov, Ivica Nikolic: Automatic Search for Related-Key Differential Characteristics in Byte-Oriented Block Ciphers: Application to AES, Camellia, Khazad and Others.
EUROCRYPT 2010:322-344
9. Alex Biryukov, Orr Dunkelman, Nathan Keller, Dmitry Khovratovich, and Adi Shamir.
Key recovery attacks of practical complexity on AES-256 variants with up to 10 rounds.
In EUROCRYPT’10, volume 6110 of Lecture Notes in Computer Science, pages 299–319.
Springer, 2010.

72

10. Alex Biryukov and Dmitry Khovratovich. Related-Key Cryptanalysis of the Full AES-192
and AES-256. In ASIACRYPT’09, volume 5912 of Lecture Notes in Computer Science,
pages 1–18. Springer, 2009.
11. Alex Biryukov, Dmitry Khovratovich, and Ivica Nikolić. Distinguisher and related-key
attack on the full AES-256. In CRYPTO’09, volume 5677 of Lecture Notes in Computer
Science, pages 231–249. Springer, 2009.
12. Andrey Bogdanov, Elif Bilge Kavun, Christof Paar, Christian Rechberger, and Tolga Yalcin. Better than brute-forceoptimized hardware architecture for efficient biclique attacks on
AES-128, SHARCS’12 – Special-Purpose Hardware for Attacking Cryptographic Systems,
March 2012, Washington D.C., USA, 2012.
13. Andrey Bogdanov, Dmitry Khovratovich and Christian Rechberger. Biclique Cryptanalysisof the Full AES. ASIACRYPT 2011, LNCS 7073, pp. 344–371, Springer-Verlag, 2011.
14. Andrey Bogdanov, Gregor Leander, Kaisa Nyberg, Meiqin Wang. Integral and Multidimensional Linear Distinguishers with Correlation Zero. Asiacrypt’12, Lecture Notes in Computer
Science, Springer-Verlag, 2012.
15. Andrey Bogdanov and Christian Rechberger. A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN. In SAC’10, volume 6544 of Lecture
Notes in Computer Science, pages 229–240. Springer, 2010.
16. Andrey Bogdanov and Vincent Rijmen. Linear Hulls with Correlation Zero and Linear
Cryptanalysis of Block Ciphers. Accepted to Designs, Codes and Cryptography, in press,
Springer-Verlag, 2012.
17. Andrey Bogdanov, Vincent Rijmen. Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block Ciphers. Preprint available as Cryptology ePrint Archive: Report 2011/123,
http://eprint.iacr.org/2011/123.
18. Andrey Bogdanov, Meiqin Wang. Zero Correlation Linear Cryptanalysis with Reduced Data
Complexity. FSE’12, LNCS, Anne Canteaut (ed.), Springer-Verlag, 2012.
19. Andrey Bogdanov and Meiqin Wang. Zero Correlation Linear Cryptanalysis of Some Block
Ciphers, unpublished manuscript, 2012.
20. J. Borst, L. R. Knudsen, and V. Rijmen. Two Attacks on Reduced IDEA. In EUROCRYPT’97, LNCS, vol. 1233, pp. 1–13, Springer-Verlag, 1997.
21. Charles Bouillaguet, Patrick Derbez, Orr Dunkelman, Pierre-Alain Fouque, Nathan Keller,
Vincent Rijmen: Low-Data Complexity Attacks on AES. IEEE Transactions on Information
Theory (TIT) 58(11):7002-7017 (2012)
22. Charles Bouillaguet, Patrick Derbez, and Pierre-Alain Fouque. Automatic Search of Attacks
on Round-Reduced AES and Applications. In CRYPTO’11, volume 2442 of Lecture Notes
in Computer Science, pages 169–187. Springer, 2011.
23. David Chaum and Jan-Hendrik Evertse. Crytanalysis of DES with a Reduced Number ofRounds: Sequences of Linear Factors in Block Ciphers. In CRYPTO’85, volume 218 ofLecture Notes in Computer Science, pages 192–211, 1986.
24. Jiazhe Chen, Leibo Li: Low Data Complexity Attack on Reduced Camellia-256. ACISP
2012:101-114
25. Jiazhe Chen, Keting Jia, Hongbo Yu, Xiaoyun Wang: New Impossible Differential Attacks
of Reduced-Round Camellia-192 and Camellia-256. ACISP 2011:16-33
26. Shao-Zhen Chen, TIan-Min Xu. Biclique Attack of the Full ARIA-256. IACR Eprint Archive
Report 2012/11, 2012.
27. B. Collard and F.-X. Standaert: Experimenting Linear Cryptanalysis. In P. Junod, A. Canteaut (eds.) Advanced Linear Cryptanalysis of Block and Stream Ciphers, vol, 7 of Cryptology
and Information Security Series. IOS Press, 2011.

7328. B. Collard, F. Standaert, J. Quisquater. Improving the time complexity of matsuis linear
cryptanalysis. In: Nam, K.-H., Rhee, G. (eds.) ICISC 2007. LNCS, vol. 4817, pp. 7788.
Springer, Heidelberg (2007).
29. Joan Daemen and Vincent Rijmen. The Design of Rijndael. Springer-Verlag, 2002.
30. Hüseyin Demirci and Ali Aydin Selçuk. A meet-in-the-middle attack on 8-round AES. In
FSE’08, volume 5086 of Lecture Notes in Computer Science, pages 116–126. Springer, 2008.
31. Hüseyin Demirci, Ihsan Taskin, Mustafa Çoban, and Adnan Baysal. Improved Meet-in-theMiddle Attacks on AES. In INDOCRYPT’09, volume 5922 of Lecture Notes in Computer
Science, pages 144–156. Springer, 2009.
32. Orr Dunkelman and Nathan Keller. The effects of the omission of last round’s MixColumns
on AES. Inf. Process. Lett., 110(8-9):304–308, 2010.
33. Orr Dunkelman, Nathan Keller, and Adi Shamir. Improved Single-Key Attacks on 8-RoundAES-192 and AES-256. In ASIACRYPT’10, volume 6477 of Lecture Notes in Computer
Science, pages 158–176. Springer, 2010.
34. Orr Dunkelman and Nathan Keller. The effects of the omission of last round’s MixColumns
on AES. Inf. Process. Lett., 110(8-9):304–308, 2010.
35. Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Michael Stay, David Wagner,and Doug Whiting. Improved cryptanalysis of Rijndael. In FSE’00, volume 1978 of Lecture
Notes in Computer Science, pages 213–230. Springer, 2000.
36. Henri Gilbert and Marine Minier. A Collision Attack on 7 Rounds of Rijndael. In AES
Candidate Conference, pages 230–241, 2000.
37. Henri Gilbert and Thomas Peyrin. Super-Sbox cryptanalysis: Improved attacks for AESlike permutations. In FSE’10, volume 6147 of Lecture Notes in Computer Science, pages
365–383. Springer, 2010.
38. Jian Guo, San Ling, Christian Rechberger, and Huaxiong Wang. Advanced Meet-in-theMiddle Preimage Attacks: First Results on Full Tiger, and Improved Results on MD4 andSHA-2. In ASIACRYPT’10, volume 6477 of Lecture Notes in Computer Science, pages
56–75. Springer, 2010.
39. Takanori Isobe. A single-key attack on the full GOST block cipher. In FSE’11, volume 6733
of Lecture Notes in Computer Science, pages 290–305. Springer, 2011.
40. Takanori Isobe and Kyoji Shibutani. Security Analysis of the Lightweight Block Ciphers
XTEA, LED and Piccolo. ACISP 2012, LNCS, Springer-Verlag, 2012.
41. Guan Jie, Zhang Zhongya: Improved Collision Attack on Reduced Round Camellia. CANS
2006:182-190
42. Deukjo Hong, Bonwook Koo, Dong-Chan Kim: Preimage and Second-Preimage Attacks on
PGV Hashing Modes of Round-Reduced ARIA, Camellia, and Serpent. IEICE Transactions(IEICET) 95-A(1):372-380 (2012)
43. Liam Keliher: Toward Provable Security Against Differential and Linear Cryptanalysis for
Camellia and Related Ciphers. I. J. Network Security (IJNSEC) 5(2):167-175 (2007)
44. Dmitry Khovratovich, Gaetan Leurent, and Christian Rechberger. Narrow Bicliques: Cryptanalysis of Full IDEA. EUROCRYPT’12, LNCS, Springer-Verlag, 2012.
45. Dmitry Khovratovich, Christian Rechberger, and Alexandra Savelieva.
Bicliquesfor preimages: attacks on Skein-512 and the SHA-2 family.
Available at
http://eprint.iacr.org/2011/286.pdf, 2011.
46. Duo Lei, Chao Li, Keqin Feng: Square Like Attack on Camellia. ICICS 2007:269-283
47. Duo Lei, Chao Li, Keqin Feng: New Observation on Camellia. Selected Areas in Cryptography 2005:51-64
48. Leibo Li, Jiazhe Chen, Keting Jia: New Impossible Differential Cryptanalysis of ReducedRound Camellia. CANS 2011:26-39

7449. Yanjun Li, Wenling Wu, Lei Zhang: Improved Integral Attacks on Reduced-Round CLEFIABlock Cipher. WISA 2011:28-39
50. Ya Liu, Leibo Li, Dawu Gu, Xiaoyun Wang, Zhiqiang Liu, Jiazhe Chen, Wei Li: New
Observations on Impossible Differential Cryptanalysis of Reduced-Round Camellia. FSE
2012:90-109
51. Ya Liu, Dawu Gu, Zhiqiang Liu, Wei Li: Improved results on impossible differential
cryptanalysis of reduced-round Camellia-192/256. Journal of Systems and Software (JSS)
85(11):2451-2458 (2012)
52. Ji-Qiang Lu: Differential Attack on Five Rounds of the SC2000 Block Cipher. J. Comput.
Sci. Technol. (JCST) 26(4):722-731 (2011)
53. Jiqiang Lu: Differential Attack on Five Rounds of the SC2000 Block Cipher. Inscrypt
2009:50-59
54. Jiqiang Lu: The (related-key) impossible boomerang attack and its application to the AES
block cipher. Des. Codes Cryptography (DCC) 60(2):123-143 (2011)
55. Jiqiang Lu, Orr Dunkelman, Nathan Keller, and Jongsung Kim. New impossible differential
attacks on AES. In INDOCRYPT’08, volume 5365 of Lecture Notes in Computer Science,
pages 279–293. Springer, 2008.
56. Jiqiang Lu, Jongsung Kim, Nathan Keller, Orr Dunkelman: Improving the Efficiency of
Impossible Differential Cryptanalysis of Reduced Camellia and MISTY1. CT-RSA 2008:370386
57. Jiqiang Lu, Yongzhuang Wei, Enes Pasalic, Pierre-Alain Fouque: Meet-in-the-Middle Attack
on Reduced Versions of the Camellia Block Cipher. IWSEC 2012:197-215
58. Stefan Lucks. Attacking seven rounds of Rijndael under 192-bit and 256-bit keys. In AES
Candidate Conference, pages 215–229, 2000.
59. Hamid Mala. Bilcique Cryptanalysis of the Block Cipher Square. IACR Eprint Archive
Report 2011/500, 2011.
60. Hamid Mala, Mohammad Dakhilalian, Mohsen Shakiba: Impossible Differential Attacks on
13-Round CLEFIA-128. J. Comput. Sci. Technol. (JCST) 26(4):744-750 (2011)61. Hamid Mala, Mohammad Dakhilalian, Vincent Rijmen, and Mahmoud Modarres-Hashemi.
Improved Impossible Differential Cryptanalysis of 7-Round AES-128. In INDOCRYPT’10,
volume 6498 of Lecture Notes in Computer Science, pages 282–291. Springer, 2010.
62. Hamid Mala, Mohsen Shakiba, Mohammad Dakhilalian, Ghadamali Bagherikaram: New
Results on Impossible Differential Cryptanalysis of Reduced-Round Camellia-128. Selected
Areas in Cryptography 2009:281-294
63. Raphael Chung-Wei Phan. Impossible differential cryptanalysis of 7-round advanced encryption standard (AES). Inf. Process. Lett., 91(1):33–38, 2004.
64. Havard Raddum, Lars R. Knudsen: A Differential Attack on Reduced-Round SC2000. Selected Areas in Cryptography 2001:190-198
65. Yu Sasaki and Kazumaro Aoki. Finding Preimages in Full MD5 Faster Than Exhaustive
Search. In EUROCRYPT’09, volume 5479 of Lecture Notes in Computer Science, pages
134–152. Springer, 2009.
66. Yu Sasaki. Meet-in-the-Middle Preimage Attacks on AES Hashing Modes and an Application to Whirlpool. In FSE’11 Preproceedings, 2011.
67. Yu Sasaki, Sareh Emami, Deukjo Hong, Ashish Kumar: Improved Known-Key Distinguishers on Feistel-SP Ciphers and Application to Camellia. ACISP 2012:87-100
68. Takeshi Shimoyama, Hitoshi Yanami, Kazuhiro Yokoyama, Masahiko Takenaka, Kouichi
Itoh, Jun Yajima, Naoya Torii, Hidema Tanaka: The Block Cipher SC2000. FSE 2001:312327
69. Taizo Shirai, Kyoji Shibutani, Toru Akishita, Shiho Moriai, Tetsu Iwata: The 128-Bit Blockcipher CLEFIA (Extended Abstract). FSE 2007:181-195

75

70. Xuehai Tang, Bing Sun, Ruilin Li, Chao Li: Impossible differential cryptanalysis of 13-round
CLEFIA-128. Journal of Systems and Software (JSS) 84(7):1191-1196 (2011)
71. Michael Tunstall: Improved ”Partial Sums”-based Square Attack on AES. SECRYPT
2012:25-34
72. Cihangir Tezcan: The Improbable Differential Attack: Cryptanalysis of Reduced Round
CLEFIA. INDOCRYPT 2010:197-209
73. Yukiyasu Tsunoo, Etsuko Tsujihara, Maki Shigeri, Teruo Saito, Tomoyasu Suzaki, Hiroyasu
Kubo: Impossible Differential Cryptanalysis of CLEFIA. FSE 2008:398-411
74. Qingju Wang, Andrey Bogdanov: The provable constructive effect of diffusion switchingmechanism in CLEFIA-type block ciphers. Inf. Process. Lett. (IPL) 112(11):427-432 (2012)
75. Yanfeng Wang, Wenling Wo, Xiaoli Yu. Biclique Cryptanalysis of Reduced-Round Piccolo
Block Cipher. IPSEC 2012, LNCS, vol. 7232, pp.337-352, Springer-Verlag, 2012.
76. Yongzhuang Wei, Jiqiang Lu, Yupu Hu: Meet-in-the-Middle Attack on 8 Rounds of the AES
Block Cipher under 192 Key Bits. ISPEC 2011:222-232
77. Wenling Wu, Lei Zhang, Wentao Zhang: Improved Impossible Differential Cryptanalysis of
Reduced-Round Camellia. Selected Areas in Cryptography 2008:442-456
78. Wenling Wu, Wentao Zhang, Dengguo Feng: Impossible Differential Cryptanalysis of
Reduced-Round ARIA and Camellia. J. Comput. Sci. Technol. (JCST) 22(3):449-456 (2007)
79. Hitoshi Yanami, Takeshi Shimoyama, Orr Dunkelman: Differential and Linear Cryptanalysis
of a Reduced-Round SC2000. FSE 2002:34-48
80. Wenying Zhang, Jing Han: Impossible Differential Analysis of Reduced Round CLEFIA.
Inscrypt 2008:181-191
81. Wentao Zhang, Wenling Wu, and Dengguo Feng. New results on impossible differential
cryptanalysis of reduced AES. In ICISC’07, volume 4817 of Lecture Notes in Computer
Science, pages 239–250. Springer, 2007.

76