Block cipher ARIA was first proposed by some South Korean experts in 2003, and later, it was established as a Korean Standard block cipher algorithm by Korean Agency for Technology and Standards. In this paper, we focus on the security evaluation of ARIA block cipher against the recent zerocorrelation linear cryptanalysis. In addition, Partialsum technique and FFT (Fast Fourier Transform) technique are used to speed up the cryptanalysis, respectively.
We first introduce some 4round linear approximations of ARIA with zerocorrelation, and then present some keyrecovery attacks on 6/7round ARIA128/256 with the Partialsum technique and FFT technique. The keyrecovery attack with Partialsum technique on 6round ARIA128 needs 2
^{123.6}
known plaintexts (KPs), 2
^{121}
encryptions and 2
^{90.3}
bytes memory, and the attack with FFT technique requires 2
^{124.1}
KPs, 2
^{121.5}
encryptions and 2
^{90.3}
bytes memory. Moreover, applying Partialsum technique, we can attack 7round ARIA256 with 2
^{124.6}
KPs, 2
^{203.5}
encryptions and 2
^{152}
bytes memory and 7round ARIA256 employing FFT technique, requires 2
^{124.7}
KPs, 2
^{209.5}
encryptions and 2
^{152}
bytes memory . Our results are the first zerocorrelation linear cryptanalysis results on ARIA.
1. Introduction
A
RIA
[1]
is a block cipher designed by a group of Korean experts in 2003. In 2004, ARIA was established as a Korean Standard block cipher algorithm by the Ministry of Commerce, Industry and Energy. ARIA is a generalpurpose involutional SPN(substitution permutation network) block cipher algorithm, optimized for both lightweight environments and hardware implementation. ARIA supports 128bit block length with the key sizes of 128/192/256 bits, and the most interesting characteristic is its involution based on the special usage of neighbouring confusion layer and involutional diffusion layer.
The security of ARIA has been internally evaluated by the designers
[1]
with differential cryptanalysis, linear cryptanalysis, truncated differential cryptanalysis, impossible differential cryptanalysis, higher order differential cryptanalysis, square attack and interpolation attack. Biryukov et al.
[2]
performed an evaluation of ARIA with truncated differential cryptanalysis and dedicated linear cryptanalysis. For the first time, Wu et al.
[3]
found a nontrivial 4round impossible differential and they gave an attack on 6round ARIA requiring about 2
^{121}
chosen plaintexts and 2
^{112}
encryptions. Based on some properties of the binary matrix used in the diffusion layer, Li et al.
[4]
found some new 4round impossible differentials of ARIA, and they gave an efficient attack on 6round ARIA. Later, Fleischmann et al.
[5]
proposed the boomerang attack on 6round ARIA and integral attacks
[6]
were introduced in the analysis of 7round ARIA. Tang et al.
[7]
proposed the meetinthemiddle attack on 7round ARIA. Du et al.
[8]
proposed the impossible differentials on 7round ARIA256 and recently, Xie et al.
[9]
gave some improvements. Attack results on ARIA are summarized in
Table 1
.
Comparison of Attacks on ARIA
KP(CP) refer to the number of known(chosen) plaintexts, Enc refers to the number of encryptions.
In this paper, we apply the recent zerocorrelation linear attacks to the block cipher ARIA. Zerocorrelation linear cryptanalysis, proposed by Bogdanov and Rijmen
[1]
, is a novel promising attack technique for block ciphers. It uses the linear approximation with correlation zero generally existing in block ciphers to distinguish the differences between a random permutation and a block cipher. The initial distinguishers
[10]
had some limitations in terms of data complexity, which needs at least half of the codebook. In FSE 2012, Bogdanov and Wang
[11]
proposed a more dataefficient distinguisher by making use of multiple linear approximations with correlation zero. The date complexity is reduced, however, the distinguishers rely on the assumption that all linear approximations with correlation zero are independent. To remove the unnecessary independency assumptions on the distinguishing side, multidimensional distinguishers
[12]
had been constructed for the zerocorrelation property at AsiaCrypt 2012. Recently, the multidimensional zerocorrelation linear cryptanalysis has been using in the attack of block ciphers CAST256
[12]
, Camellia
[13]
, CLEFIA
[13]
, HIGHT
[14]
, LBlock
[15]
and E2
[16]
, successfully.
Some improving techniques for zerocorrelation linear cryptanalysis have been proposed, such as Partialsum technique and FFT technique. Partialsum technique was proposed by Ferguson et al.
[17]
to conduct the integral attacks on 6round AES. The basic idea of Partialsum technique is to partially compute the sum by guessing each key one after another instead of guessing all the keys one time. Since zerocorrelation linear cryptanalysis use enormous plaintextciphertext pairs, thus, Partialsum technique can also be used to reduce the computation complexity in the attack process. FFT technique of computational complexity reduction was first proposed by Collard et al.
[18]
in the linear attack on the AES candidate Serpent in 2007. It also relies on eliminating the redundant computations from the partial encryption/decryption in attack process. At SAC 2013, Bogdanov et al.
[13]
applied FFT technique to the zerocorrelation linear cryptanalysis of Camellia.
In this paper, 4round zerocorrelation linear approximations of ARIA are discussed in detail. Furthermore, we investigate the security of 6/7round ARIA128/256 with both Partialsum and FFT techniques. Our contributions can be summarized as follows:
1. We reveal some 4round zerocorrelation linear approximations of ARIA. If we treat the input/output masks as the input/output differentials, they are 4round impossible differentials of ARIA owing that the diffusion layer of the round function is a diagonal matrix.
2. Based on those new linear approximations with zerocorrelation, keyrecovery attacks on 6/7round ARIA128/256 are proposed. In addition, we use Partialsum technique and FFT technique to speed up the attacks. They are the first zerocorrelation linear attacks on reducedround ARIA.
The paper is organized as follows. Section 2 gives a brief description of block cipher ARIA and outlines the ideas of zerocorrelation linear cryptanalysis. Some new zerocorrelation linear approximations are shown in Section 3. Section 4 and Section 5 illustrate our attacks on 6/7round ARIA128/256 with Partialsum and FFT technique, respectively. We conclude this paper in Section 6.
2. Preliminaries
 2.1 Description of ARIA
ARIA is an SPN style block cipher and the number of the round is 12/14/16 corresponding to key of 128/192/256 bits. The round function consists of 3 basic operations: the substitution layer, the diffusion layer and the round key addition, which can be described as follows:
Round Key Addition(KA)
: This is done by XORing the 128bit round key, which is derived from the cipher key by means of the key schedule.
Substitution Layer(SL)
: Applying the 8×8 Sboxes 16 times in parallel on each byte. There are two types of substitution layers to be used so as to make the cipher involution, see
Fig. 1
. For convenience, we denote by
S_{r ,k}
,
the
k
th Sbox of
r
th round and its inverse Sbox.
Substitution Layer of ARIA
Diffusion Layer(DL)
: A linear map
is given by
Note that the diffusion layer of the last round is replaced by a round key addition. We shall assume that the 6/7round ARIA also has the last diffusion layer replaced by a round key addition in the attack of 6/7round ARIA. In addition, our attacks do not utilize the round key relations, so we omit the details of ARIA's key schedule.
 2.2 Basic ideas of zerocorrelation linear cryptanalysis
In this section, we briefly recall the basic concepts of zerocorrelation linear cryptanalysis, which is based on linear approximations determined by an input mask
α
and an output mask
β
. The linear approximation
α
→
β
of a vectorial function
f
with the correlation can be denoted as

C(β·f(x),α·x) = 2Prx(β·f(x)⊕α·x=0)1,
where we denote the scalar product of binary vectors by
In zerocorrelation linear cryptanalysis, distinguishers uses linear approximations with zero correlation for all keys ,while the classical linear cryptanalysis utilizes linear approx imations with correlation far from zero. Zerocorrelation linear cryptanalysis with multiple linear approximations was introduced in
[11]
.
Let the number of available zerocorrelation linear approximations for an nbit block cipher be denoted by
l
. Let the number of required known plaintexts be
N
. For each of the
l
given linear approximation, the adversary computes the number
T_{i}
of times that linear approximation
i
is fulled on
N
plaintexts and ciphertexts,
i
∈{1,...,
l
} . Each
T_{i}
suggests an empirical correlation value
ĉ_{i}
= 2
T_{i}
/
N
1. Under a statistical independency assumption,
follows a X
^{2}
distribution with mean
μ
_{0}
=
l
/
N
and variance
= 2
l
/
N
^{2}
for the right key guess, while for the wrong key guess, it follows a X
^{2}
distribution with mean
μ
_{1}
=
l
/
N
+
l
/ 2
^{n}
and standard deviation
If we denote the probability of false positives and the probability of false negatives to distinguish between a wrong key and a right key as
β
_{0}
and
β
_{1}
, respectively. We consider the decision threshold
the number of known plaintexts
N
should be approximately:
where
and
are the respective quantiles of the standard normal distribution.
Recently, Bogdanov et al.
[12]
proposed a multidimensional zerocorrelation linear distinguisher using
l
zerocorrelation linear approximations to remove the statistical independency assumption, which requires
known plaintexts, where
n
is the block size of a cipher. We treat the zerocorrelation linear approximations available as a linear space spanned by
m
base zerocorrelation linear approximations such that all
l
=2
^{m}
nonzero linear combinations of them have zero correlation. For each of the 2
^{m}
data values
z
∈
, the attacker initializes a counter
V
[
z
],
z
=0,1,...,2
^{m}
1 to value zero. Then, for each dis tinct plaintext, the attacker computes the corresponding data value in
by evaluating the
m
basis linear approximations and increments the counter
V
[
z
] of this data value by one. Then the attacker computes the statistic
T
:
The statistic
T
follows a X
^{2}
distribution with mean
μ
_{0}
=(
l
1)(2
^{n}

N
) / (2
^{n}
1) and variance
= 2(
l
1)(2
^{n}

N
)
^{2}
/ (2
^{n}
1)
^{2}
for the right key guess, while for the wrong key guess, it follows a X
^{2}
 distribution with mean
μ
_{1}
=
l
1 and variance
= 2(
l
1).
If we denote the probability of false positives and the probability of false negatives to distinguish between a wrong key and a right key as
β
_{0}
and
β
_{1}
, respectively. We consider the decision threshold
then the number of known plaintexts
N
should be about
3. Some zerocorrelation linear approximations for 4round ARIA
In this section, we show some zerocorrelation linear approximations for 4round ARIA, following the properties on the propagation of linear masks over basic block cipher operations proposed in
[10]
. We consider 4round linear approximations with zerocorrelation, which is built in a missinthemiddle manner. Some 2round linear approximations with nonzero bias is concatenated to some 2round linear approximations with nonzero bias in the inverse direction, where the intermediate masks states contradict with each other.
We assert that the 4round linear approximations
have zerocorrelation, where
b
and
h
denote any nonzero value.
Consider that the input masks (0,0,0,0,
b
,0,0,0;0,0,0,0,0,0,0,0) for
R
_{2}
will result that the output mask for
R
_{3}
is (
e
_{0}
,
e
_{1}
,...,
e
_{14}
,
e
_{15}
) in the forward direction, where
e_{i}
, 0≤
i
≤15 denotes any byte value. The three bytes
e
_{3}
,
e
_{4}
,
e
_{10}
satisfy that
e
_{3}
⊕
e
_{4}
⊕
e
_{10}
=
d
_{5}
, and we know that
b
≠0 means that
d
_{5}
≠0, then
e
_{3}
⊕
e
_{4}
⊕
e
_{10}
≠0. In the backward direction, we can get that the input mask of
R
_{4}
is (
g
_{0}
,
g
_{1}
,...,
g
_{14}
,
g
_{15}
) from the output (0,0,
h
,0,0,
h
,0,0;0,0 0,
h
,
h
,0,0,0) for
R
_{5}
, where
g_{i}
, 0≤
i
≤15 also denotes any byte value. We can deduce that
g
_{3}
=
g
_{4}
=
g
_{10}
=0, which leads that
g
_{3}
⊕
g
_{4}
⊕
g
_{10}
≠0 and it contradicts with
e
_{3}
⊕
e
_{4}
⊕
e
_{10}
≠0. Then, the linear hull is a zerocorrelation linear hull, see
Fig. 2
. We also have the following 4round linear approximations with zerocorrelation,
Zerocorrelation linear approximations of 4round ARIA
In addition, it is easy to see that the linear map
P
of diffusion layer can be treated as a diagonal matrix. If we treat the input /output masks as the input/output differentials, they are also 4round impossible differentials.
4. Keyrecovery attacks on 6round ARIA with PartialSum and FFT
In this section, based on the first 4round zerocorrelation linear approximates, we present some keyrecovery attacks on 6round ARIA128 with zerocorrelation linear cryptanalysis. In the attack, the Partialsum and FFT techniques are used to speed up, respectively.
 4.1 Keyrecovery attacks on 6round ARIA with Partialsum technique
To attack 6round ARIA, the 4round linear approximates with zerocorrelation start from round 2 and end at round 5. One round is added before and one round is appended after the linear approximates, refer to
Fig. 3
. The partial encryption and decryption using the partial sum technique are proceeded as follows.
Keyrecovery Attacks on 6Round ARIA
1. Allocate 40bit counters
V
_{1}
[
x
_{1}
] for 2
^{88}
possible values of
x
_{1}
=
m
_{1}
[0,2,5,8,11,14,15] 
m
_{7}
[2,5,11,12] and initialize them to zero. For the corresponding ciphertexts after 6 round encryption, extract the value of
x
_{1}
and increment the corresponding counter
V
_{1}
[
x
_{1}
] . The time complexity of this step is
N
memory accesses to process the chosen plaintextciphertext pairs. We assume that processing each pair is equivalent to one round encryption, then the time complexity of this step is about
N
x1/ 6 6round encryptions.
2. Allocate a counter
V
_{2}
[
x
_{2}
] for 2
^{88}
possible values of
and initialize them to zero. Guess
k
_{7}
[2] and partially decrypt
x
_{1}
to get the value of
x
_{2}
, that is, compute
then update the corresponding counter by
V
_{2}
[
x
_{2}
]+
V
_{1}
[
x
_{1}
]. The computation is about 2
^{88}
x2
^{8}
x1/16x1/ 6 6round encryptions.
The following steps in the partial encryption and decryption phase are similar to Step 2, we use
Table 2
to show the details of each partial encryption and decryption step. In
Table 2
, the second column stands for the counters should be allocated in this step. The subkey bytes that have to be guessed in each step are shown in the third column. the fourth column denotes the time complexity of corresponding step measured in 1/16x1/ 6 6round encryption. The intermediate state values are shown in the last column.
Partial Encryption and Decryption of the Attack on 6Round ARIA128
Partial Encryption and Decryption of the Attack on 6Round ARIA128
13. Allocate a counter vector
V
[
z
] of size 2
^{16}
where each element is 120bit length for 16bit
z
(
z
is the concatenation of evaluations of 16 basis zerocorrelation masks). For 2
^{16}
values of
x
_{12}
, evaluate all basis zerocorrelation masks on
V
_{12}
and put the evaluations to the vector
z
, then add the corresponding
V
[
z
]:
V
[
z
]+ =
V
_{12}
[
x
_{12}
] . According Equation(2), compute
if
T
˂
τ
, then the guessed key is a possible key candidate.
In the attack, we set the typeI error probability
β
_{0}
=2
^{2.7}
and the typeII error probability
β
_{1}
=2
^{90}
. We have
≈ 1,
≈ 11,
n
=128 ,
l
=2
^{16}
. According to Equation (3), the date complex
N
should be about 2
^{123.6}
and the decision threshold
τ
≈ 2
^{15.9}
.
The complexity of Step 3 to Step 12 is no more than 2
^{108.6}
6round ARIA encryptions and the complexity of Step 1 is about 2
^{121}
6round ARIA encryptions which is also the dominant part of our attack. In total, the data complexity is about 2
^{123.6}
known plaintexts, the time complexity is about 2
^{121}
6round ARIA encryptions and the memory requirement are about 2
^{90.3}
bytes for counters.
 4.2 Keyrecovery attacks on 6round ARIA with FFT technique
Using the FFT technique, we can attack 6round AIRA128 starting from the first round by placing the 4round zerocorrelation linear approximations in rounds 2 to 5. One round is added before and one round is appended after the linear approximates, also see
Fig. 3
.
In our attack, we guess the subkeys and evaluate the linear approximation
(0,0,0,0,
b
,0,0,0; 0,0,0,0,0,0,0,0)·
m
_{2}
⊕(0,0,h,0,0,h,0,0; 0,0,0,h,h,0,0,0)·
m
_{6}
=0 that is ,
Let
k
_{6}
=
k
_{6}
[2]⊕
k
_{6}
[5]⊕
k
_{6}
[11]⊕
k
_{6}
[13] and
v
=
u
⊕
b
·
k
_{6}
, then we have
Our attack is equivalent to evaluating the correlation of the linear approximation
v
= 0 . The correlation of the linear approximation
v
= 0 can be evaluated as the matrix vector product where the matrix is:
see
[13]
and
[18]
for detail. Then the attack is performed as follows:
1. Allocate the vector of counters
V_{k}
of the experimental correlation for every subkey candidate
k
=
k
_{1}
[0,2,5,8,11,14,15] 
k
_{7}
[2,5,11,12] .
2. For each of
N PC
pairs, extract the 88bit value
i
=
m
_{1}
[0,2,5,8,11,14,15] 
m
_{7}
[2,5, 11,12]
and increment the counters
x_{i}
according to the value of
i
.
3. For each of the 2
^{16}
linear approximations,
(i). Perform the key counting phase and compute the first column of
M
using (4) and (5). As
M
is a 88level circulant matrix, this information is sufficient to denote matrix
M
completely ,which requires 2
^{88}
operations.
(ii). Evaluate the vector
ε
=
M
·
x
, which requires about 3x88x2
^{88}
operations.
(iii). Let
W
=
W
+ (
ε
/
N
)
^{2}
, If
W
˂
τ
, then the corresponding
k
is a possible subkey candidate and all master keys are tested exhaustively.
After Step 3, we obtain 2
^{88}
counters
V_{k}
, which are the sum of squares of correlations for 2
^{16}
linear approximations under each
k
. The correct subkey is then selected from the candidates with
V_{k}
less than the threshold
τ
. If we set
β
_{0}
=2
^{2.7}
and
β
_{0}
=2
^{90}
, we get
≈ 1 and
≈ 11. Since the block size
n
=128 and we have
l
= 2
^{16}
linear approximations, according to Equation (1), the number of known plaintextciphertext pairs
N
should be about 2
^{124.1}
and the threshold
τ
≈ 2
^{108.4}
. In Step 3, only the right guess is expected to survive for the 88bit target subkeys. The complexities for Step 2, Step 3, are 2
^{121.5}
memory accesses, 2
^{16}
x4x88x2
^{88}
=2
^{112.5}
operators, respectively. If we assume that one time of memory access, one time of operators, one 6round Camellia encryption are equivalent, then the total time complexity is about 2
^{121.5}
encryptions. The memory requirements are about 2
^{90.3}
bytes.
5. Keyrecovery attacks on 7round ARIA with PartialSum and FFT
In this section, we describe some zerocorrelation linear cryptanalysis of 7round ARIA. The attack is based on the first 4round zerocorrelation linear approximates with additional one round in the begin and two rounds at the end, see
Fig. 4
. PartialSum and FFT are also used in the attack process, respectively.
Keyrecovery Attacks on 7Round ARIA
 5.1 Keyrecovery attacks on 7round ARIA with Partialsum technique
Similarly to the attacks to 6round ARIA, the partial encryption and decryption using the partial sum technique are proceeded as follows.
1. Allocate 8bit counters
V
_{1}
[
x
_{1}
] for 2
^{152}
possible values of
x
_{1}
=
m
_{1}
[0,2,5,8,11,14,15] 
m
_{8}
[1,2,3,4,6,7,9,10,11,12,14,15] and initialize them to zero. For the corresponding ciphertexts after 7 round encryption, extract the value of
x
_{1}
and increment the corresponding counter
V
_{1}
[
x
_{1}
] . The time complexity of this step is
N
memory accesses to process the chosen plaintextciphertext pairs. We assume that processing each
PC
pair is equivalent to one round encryption, then the time complexity of this step is about
N
x1/ 7 7round encryptions.
2. Allocate a counter
V
_{2}
[
x
_{2}
] for 2
^{120}
possible values of
x
_{2}
=
m
_{1}
[2,5,8,11,14,15] 
m
_{8}
[11,12,14,15]
and set them to zero. Guess
k
_{1}
[0] and
k
_{8}
[1,2,3,4,6,7,9,10] , and partially decrypt
x
_{1}
to get the value of
x
_{2}
, that is, compute
then update the corresponding counter by
V
_{2}
[
x
_{2}
]+=
V
_{1}
[
x
_{1}
]. The computation in this step is no more than
N
x2
^{72}
x1/16x1/7 7round encryptions.
3. Allocate a counter
V
_{3}
[
x
_{3}
] for 2
^{112}
possible values of
x
_{3}
=
m
_{1}
[2,5,8,11,14,15] 
m
_{8}
[12,14,15] 
and initialize them to zero. Guess
k
_{8}
[11] and partially decrypt
x
_{2}
to get the value of
x
_{3}
, that is, compute
then update the corresponding counter by
V
_{3}
[
x
_{3}
]+=
V
_{2}
[
x
_{2}
]. The computation in this step is no more than 2
^{120}
x2
^{80}
x1/16x1/7 7round encryptions.
4. Allocate a counter
V
_{4}
[
x
_{4}
] for the 2
^{104}
possible values of
x
_{4}
=
m
_{1}
[2,5,8,11,14,15] 
m
_{8}
[14,15] 
and initialize them to zero. Guess
k
_{8}
[12] and partially decrypt
x
_{3}
to get the value of
x
_{4}
, that is, compute
then update the corresponding counter by
V
_{4}
[
x
_{4}
]+=
V
_{3}
[
x
_{3}
]. The computation in this step is no more than 2
^{112}
x2
^{88}
x1/16x1/7 7round encryptions.
5. Allocate a counter
V
_{5}
[
x
_{5}
] for the 2
^{96}
possible values of
x
_{5}
=
m
_{1}
[2,5,8,11,14,15] 
m
_{8}
[15] 
and initialize them to zero. Guess
k
_{8}
[14] and partially decrypt
x
_{4}
to get the value of
x
_{5}
, that is, compute
then update the corresponding counter by
V
_{5}
[
x
_{5}
]+=
V
_{4}
[
x
_{4}
]. The computation in this step is no more than 2
^{104}
x2
^{96}
x1/16x1/7 7round encryptions.
6. Allocate a counter
V
_{6}
[
x
_{6}
] for the 2
^{88}
possible values of
x
_{6}
=
m
_{1}
[2,5,8,11,14,15] 
and initialize them to zero. Guess
k
_{8}
[15]and partially decrypt
x
_{5}
to get the value of
x
_{6}
, that is, compute
then update the corresponding counter by
V
_{6}
[
x
_{6}
]+=
V
_{5}
[
x
_{5}
]. The computation in this step is no more than 2
^{96}
x2
^{104}
x1/16x1/7 7round encryptions.
Similarly, we use
Table 3
to show the details of each partial encryption and decryption step, where we let
k
_{7,2}
=⊕
_{i}
_{=1,4,6,10,11,12,15}
k
_{7}
[
i
],
k
_{7,5}
=⊕
_{i}
_{=1,3,4,9,10,14,15}
k
_{7}
[
i
],
k
_{7,11}
=⊕
_{i}
_{=2,3,4,7,9,12,14}
k
_{7}
[
i
] and
k
_{7,12}
=⊕
_{i}
_{=1,2,6,7,9,11,12}
k
_{7}
[
i
]. After Step 16, we have reached the boundaries of the zerocorrelation linear approximations over 7round ARIA. We then proceed the following steps to recover the right key.
Partial Encryption and Decryption of the Attack on 7Round ARIA256
Partial Encryption and Decryption of the Attack on 7Round ARIA256
17. Allocate a counter vector
V
[
z
] of size 2
^{16}
where each element is 120bit length for 16bit
z
(
z
is the concatenation of evaluations of 16 basis zerocorrelation masks). For 2
^{16}
values of
x
_{16}
, evaluate all basis zerocorrelation masks on
V
_{16}
and put the evaluations to the vector
z
, then add the corresponding
V
[
z
] :
V
[
z
]+=
V
_{16}
[
x
_{16}
] . According the Equation (2), compute
if
T
˂
τ
, then the guessed keys are a possible key candidates.
In this attack, we set the typeI error probability
β
_{0}
= 2
^{2.7}
and the typeII error probability
β
_{1}
= 2
^{186}
. We have
≈ 1,
≈ 15.7,
n
=128,
l
= 2
^{16}
. According to Equation (3), the date complex
N
is about 2
^{124.6}
and the decision threshold
τ
≈ 2
^{15.9}
. There are 184 bit key values guessed during the encryption phase, and only the right key candidates can survive in the wrong key filtration. The complexity of Step 3 to Step 16 is no more than 2
^{203.5}
7round ARIA encryptions and In total, the data complexity is about 2
^{124.6}
known plaintexts, the time complexity is about 2
^{203.5}
7round ARIA encryptions and the memory requirements are about 2
^{152}
bytes for counters.
 5.2 Keyrecovery attacks on 7round ARIA with FFT technique
In our attack, one round is added before and two rounds are appended after the linear approximates with zerocorrelation from rounds 2 to 5, see
Fig. 4
. We evaluate the linear approximations

(0,0,0,0,b,0,0,0; 0,0,0,0,0,0,0,0) ·m2⊕(0,0,h,0,0,h,0,0; 0,0,0,h,h,0,0,0) ·m6=0,
that is ,
Let
K
_{7,2}
=⊕
_{i=0,2,5,8,11,14,15}
K
_{7}
[
i
],
K
_{7,5}
=⊕
_{i}
_{=1,4,6,10,11,12,15}
K
_{7}
[
i
],
K
_{7,11}
=⊕
_{i}
_{=1,3,4,9,10,14,15}
K
_{7}
[
i
],
K
_{7,12}
=⊕
_{i}
_{=2,3,4,7,9,12,14}
K
_{7}
[
i
],
K
_{6}
=
k
_{6}
[2]⊕
k
_{6}
[5]⊕
k
_{6}
[11]⊕
k
_{6}
[12], and
v
=
u
⊕
b
·
K
_{6}
, then we have
Our attack is equivalent to evaluating the correlation of the linear approximation v = 0, which can be evaluated as the matrix vector product where the matrix is:
Then the attack is performed as follows:
1. Allocate the vector of counters
V_{k}
of the experimental correlation for every subkey candidate.
k
=
k
_{1}
[0,2,5,8,11,14,15] 
k
_{8}
[1,2,3,4,6,7,9,10,11,12,14,15] 
k
_{7,2}

k
_{7,5}

k
_{7,11}

k
_{7,12}
2. For each of
N
plaintextciphertext pairs, extract the 8bit value
i
=
m
_{1}
[0,2,5,8,11,8 14,15] 
m
_{8}
[1,2,3,4,6,7,9,10,11,12,14,15], increment the counters
x_{i}
according to the value of
i
.
3. For each of the 2
^{16}
linear approximations,
(i). Perform the key counting phase and compute the first column of
M
using (6) and (7). As
M
is a 184level circulant matrix, this information is sufficient to denote
M
completely, which requires 2
^{184}
operations.
(ii). Evaluate the vector
ε
=
M
·
x
, which requires about 3x184x2
^{184}
operations.
(iii). Let
W
=
W
+ (
ε
/
N
)
^{2}
, If
W
˂
τ
, then the corresponding
k
is a possible subkey candidate and all master keys are tested exhaustively.
After Step 3, we obtain 2
^{184}
counters
V_{k}
which are the sum of squares of correlations for 2
^{16}
linear approximations under each
k
. The correct subkey is then selected from the candidates with
V_{k}
less than the threshold
τ
. If we set
β
_{0}
=2
^{2.7}
and
β
_{1}
=2
^{186}
, we get
≈ 1 and
≈ 15.7. Since the block size
n
=128 and we have
l
= 2
^{16}
linear approximations, according to Equation (1), the number of known plaintextciphertext pairs
N
should be about 2
^{124.7}
and the threshold
τ
≈ 2
^{108.4}
. In Step 3, only the right guess is expected to survive for the 184bit target subkey. The complexities for Step 2, Step 3, are 2
^{121.9}
memory accesses, 2
^{16}
x4x184x2
^{184}
=2
^{209.5}
operators, respectively. If we assume that one time of memory access, one time of operators, one 7round Camellia encryption are equivalent, then the total time complexity is about 2
^{209.5}
encryptions. The memory requirements are about 2
^{152}
bytes.
6. Conclusion
In this paper, we evaluate the security of ARIA block cipher with respect to the technique of zerocorrelation linear cryptanalysis. We deduce some 4round zerocorrelation linear approximations of ARIA, and based on those linear approximations, we give some keyrecovery attacks on 6/7 round ARIA128/256 with Partialsum technique and FFT technique taken into consideration. For the first time, we consider the security of ARIA against zerocorrelation linear cryptanalysis. While two techniques are used in the attack, it also gives us a chance to compare the partialsum technique and the FFT technique.
BIO
Wentan Yi was born in 1989. He is currently pursuing for the Ph.D degree in Zhengzhou Information Science and Technology Institute. His research interest is the analysis of block cipher.
Email: nlwt8988@gmail.com
Shaozhen Chen was born in 1965. Currently, she is a professor in Zhengzhou Information Science and Technology Institute.
Her research interests are cryptography and information security.
Email: chenshaozhen@vip.sina.com
Kuanyang Wei was born in 1989. He is currently pursuing for the B.S degree in Zhengzhou Information Science and Technology Institute. His research interest is the analysis of block cipher.
Email: wky543@sina.com
Daesung K.
,
Jaesung K.
,
Sangwoo P.
“New Block Cipher: ARIA. Information Security and Cryptology,”
ICISC'03, LNCS
2003
Vol.2971
432 
445
Biryukov A.
,
Canniere C.
2004
“Security and Performance Analysis of ARIA,”Version 1.2.
Wu W.
,
Zhang W.
,
Feng D.
2007
“Impossible Differential Cryptanalysis of ReducedRound ARIA and Camellia,”
Journal of Computer Science and Technology
22
449 
456
DOI : 10.1007/s1139000790560
Li S.
,
Song C.
“Improved Impossible Differential Cryptanalysis of ARIA,”
IEEE Computer Society, ISA
2008
192 
132
Fleischmann E.
,
Gorski M.
,
Lucks S.
“Attacking Reduced Rounds of the ARIA Block Cipher,”
Li Y.
,
Wu W.
,
Zhang L.
2010
“Integral Attacks on Reducedround ARIA Block Cipher,”
ISPEC, LNCS
Vol.6047
19 
29
Tang X.
,
Sun B.
,
Li R.
2011
“A Meetinthemiddle Attack on ReducedRound ARIA,”
Journal of Systems and Software
84
1685 
1692
DOI : 10.1016/j.jss.2011.04.053
Du C.
,
Chen J.
“Impossible Differential Cryptanalysis of ARIA Reduced to 7 Rounds,”
CANS, LNCS
2010
Vol.6467
20 
30
Xie Z.
,
Chen S.
2013
“Impossible Differential Cryptanalysis of 7Round ARIA192,”
Journal of Electronics Information Technology
35
2301 
2306
DOI : 10.3724/SP.J.1146.2012.01615
Bogdanov A .
,
Rijmen V.
2014
“Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block Ciphers,”
Designs, Codes and Cryptography
70
369 
383
DOI : 10.1007/s106230129697z
Bogdanov A.
,
Wang M.
“Zero Correlation Linear Cryptanalysis with Reduced Data Complexity,”
FSE 2012, LNCS
2012
Vol. 7549
29 
48
Bogdanov A.
,
Leander G.
,
Nyberg K.
,
Wang M.
“Integral and Multidimensional Linear Distinguishers with Correlation Zero,”
ASIACRYPT 2012, LNCS
2012
Vol. 7658
244 
261
Bogdanov A.
,
Geng H.
,
Wang M.
,
Wen L.
,
Collard B.
“Zerocorrelation Linear Cryptanalysis with FFT and Improved Attacks on ISO Standards Camellia and CLEFIA,”
SAC’13, LNCS
2014
306 
323
Wen L.
,
Wang M.
,
Bogdanov A.
,
Chen H.
2014
“Multidimensional ZeroCorrelation Attacks on Lightweight Block Cipher HIGHT: Improved Cryptanalysis of an ISO Standard,”
Information Processing Letters
114
322 
330
DOI : 10.1016/j.ipl.2014.01.007
Soleimany H.
,
Nyberg K.
2014
“Zerocorrelation Linear Cryptanalysis of Reduced round LBlock,”
Designs, Codes and Cryptography
73
(2)
683 
698
DOI : 10.1007/s106230149976y
Wen L.
,
Wang M.
,
Bogdanov A.
“Multidimensional ZeroCorrelation Linear Cryptanalysis of E2,”
Progress in Cryptology  AFRICACRYPT 2014, LNCS
2014
Vol. 8469
147 
164
Ferguson N.
,
Kelsey J.
“Improved Cryptanalysis of Rijndael,”
FSE. LNCS
2000
Vol.1978
213 
230
Collard B.
,
Standaert F.
,
Quisquater J.
“Improving the Time Complexity of Matsui's Linear Cryptanalysis,”
ICISC 2007, LNCS
2007
Vol. 4817
77 
88