Advanced
Zero-Correlation Linear Cryptanalysis of Reduced Round ARIA with Partial-sum and FFT
Zero-Correlation Linear Cryptanalysis of Reduced Round ARIA with Partial-sum and FFT
KSII Transactions on Internet and Information Systems (TIIS). 2015. Jan, 9(1): 280-295
Copyright © 2015, Korean Society For Internet Information
  • Received : January 16, 2014
  • Accepted : December 13, 2014
  • Published : January 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Wen-Tan Yi
Shao-Zhen Chen
Kuan-Yang Wei

Abstract
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 zero-correlation linear cryptanalysis. In addition, Partial-sum technique and FFT (Fast Fourier Transform) technique are used to speed up the cryptanalysis, respectively. We first introduce some 4-round linear approximations of ARIA with zero-correlation, and then present some key-recovery attacks on 6/7-round ARIA-128/256 with the Partial-sum technique and FFT technique. The key-recovery attack with Partial-sum technique on 6-round ARIA-128 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 Partial-sum technique, we can attack 7-round ARIA-256 with 2 124.6 KPs, 2 203.5 encryptions and 2 152 bytes memory and 7-round ARIA-256 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.
Keywords
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 general-purpose involutional SPN(substitution permutation network) block cipher algorithm, optimized for both lightweight environments and hardware implementation. ARIA supports 128-bit 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 non-trivial 4-round impossible differential and they gave an attack on 6-round 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 4-round impossible differentials of ARIA, and they gave an efficient attack on 6-round ARIA. Later, Fleischmann et al. [5] proposed the boomerang attack on 6-round ARIA and integral attacks [6] were introduced in the analysis of 7-round ARIA. Tang et al. [7] proposed the meet-in-the-middle attack on 7-round ARIA. Du et al. [8] proposed the impossible differentials on 7-round ARIA-256 and recently, Xie et al. [9] gave some improvements. Attack results on ARIA are summarized in Table 1 .
Comparison of Attacks on ARIA
PPT Slide
Lager Image
KP(CP) refer to the number of known(chosen) plaintexts, Enc refers to the number of encryptions.
In this paper, we apply the recent zero-correlation linear attacks to the block cipher ARIA. Zero-correlation 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 data-efficient 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 zero-correlation property at AsiaCrypt 2012. Recently, the multidimensional zero-correlation linear cryptanalysis has been using in the attack of block ciphers CAST-256 [12] , Camellia [13] , CLEFIA [13] , HIGHT [14] , LBlock [15] and E2 [16] , successfully.
Some improving techniques for zero-correlation linear cryptanalysis have been proposed, such as Partial-sum technique and FFT technique. Partial-sum technique was proposed by Ferguson et al. [17] to conduct the integral attacks on 6-round AES. The basic idea of Partial-sum technique is to partially compute the sum by guessing each key one after another instead of guessing all the keys one time. Since zero-correlation linear cryptanalysis use enormous plaintext-ciphertext pairs, thus, Partial-sum 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 zero-correlation linear cryptanalysis of Camellia.
In this paper, 4-round zero-correlation linear approximations of ARIA are discussed in detail. Furthermore, we investigate the security of 6/7-round ARIA-128/256 with both Partial-sum and FFT techniques. Our contributions can be summarized as follows:
1. We reveal some 4-round zero-correlation linear approximations of ARIA. If we treat the input/output masks as the input/output differentials, they are 4-round 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 zero-correlation, key-recovery attacks on 6/7-round ARIA-128/256 are proposed. In addition, we use Partial-sum technique and FFT technique to speed up the attacks. They are the first zero-correlation linear attacks on reduced-round ARIA.
The paper is organized as follows. Section 2 gives a brief description of block cipher ARIA and outlines the ideas of zero-correlation linear cryptanalysis. Some new zero-correlation linear approximations are shown in Section 3. Section 4 and Section 5 illustrate our attacks on 6/7-round ARIA-128/256 with Partial-sum 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 128-bit round key, which is derived from the cipher key by means of the key schedule.
Substitution Layer(SL) : Applying the 8×8 S-boxes 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 Sr ,k ,
PPT Slide
Lager Image
the k -th S-box of r -th round and its inverse S-box.
PPT Slide
Lager Image
Substitution Layer of ARIA
Diffusion Layer(DL) : A linear map
PPT Slide
Lager Image
is given by
PPT Slide
Lager Image
Note that the diffusion layer of the last round is replaced by a round key addition. We shall assume that the 6/7-round ARIA also has the last diffusion layer replaced by a round key addition in the attack of 6/7-round 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 zero-correlation linear cryptanalysis
In this section, we briefly recall the basic concepts of zero-correlation 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
PPT Slide
Lager Image
In zero-correlation 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. Zero-correlation linear cryptanalysis with multiple linear approximations was introduced in [11] .
Let the number of available zero-correlation linear approximations for an n-bit 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 Ti of times that linear approximation i is fulled on N plaintexts and ciphertexts, i ∈{1,..., l } . Each Ti suggests an empirical correlation value ĉi = 2 Ti / N -1. Under a statistical independency assumption,
PPT Slide
Lager Image
follows a X 2 -distribution with mean μ 0 = l / N and variance
PPT Slide
Lager Image
= 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
PPT Slide
Lager Image
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
PPT Slide
Lager Image
the number of known plaintexts N should be approximately:
PPT Slide
Lager Image
where
PPT Slide
Lager Image
and
PPT Slide
Lager Image
are the respective quantiles of the standard normal distribution.
Recently, Bogdanov et al. [12] proposed a multidimensional zero-correlation linear distinguisher using l zero-correlation linear approximations to remove the statistical independency assumption, which requires
PPT Slide
Lager Image
known plaintexts, where n is the block size of a cipher. We treat the zero-correlation linear approximations available as a linear space spanned by m base zero-correlation linear approximations such that all l =2 m non-zero linear combinations of them have zero correlation. For each of the 2 m data values z
PPT Slide
Lager Image
, 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
PPT Slide
Lager Image
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 :
PPT Slide
Lager Image
The statistic T follows a X 2 -distribution with mean μ 0 =( l -1)(2 n - N ) / (2 n -1) and variance
PPT Slide
Lager Image
= 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
PPT Slide
Lager Image
= 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
PPT Slide
Lager Image
then the number of known plaintexts N should be about
PPT Slide
Lager Image
3. Some zero-correlation linear approximations for 4-round ARIA
In this section, we show some zero-correlation linear approximations for 4-round ARIA, following the properties on the propagation of linear masks over basic block cipher operations proposed in [10] . We consider 4-round linear approximations with zero-correlation, which is built in a miss-in-the-middle manner. Some 2-round linear approximations with nonzero bias is concatenated to some 2-round linear approximations with nonzero bias in the inverse direction, where the intermediate masks states contradict with each other.
We assert that the 4-round linear approximations
PPT Slide
Lager Image
have zero-correlation, where b and h denote any non-zero 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 ei , 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 gi , 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 zero-correlation linear hull, see Fig. 2 . We also have the following 4-round linear approximations with zero-correlation,
PPT Slide
Lager Image
PPT Slide
Lager Image
Zero-correlation linear approximations of 4-round 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 4-round impossible differentials.
4. Key-recovery attacks on 6-round ARIA with Partial-Sum and FFT
In this section, based on the first 4-round zero-correlation linear approximates, we present some key-recovery attacks on 6-round ARIA-128 with zero-correlation linear cryptanalysis. In the attack, the Partial-sum and FFT techniques are used to speed up, respectively.
- 4.1 Key-recovery attacks on 6-round ARIA with Partial-sum technique
To attack 6-round ARIA, the 4-round linear approximates with zero-correlation 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.
PPT Slide
Lager Image
Key-recovery Attacks on 6-Round ARIA
1. Allocate 40-bit 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 plaintext-ciphertext 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 6-round encryptions.
2. Allocate a counter V 2 [ x 2 ] for 2 88 possible values of
PPT Slide
Lager Image
and initialize them to zero. Guess k 7 [2] and partially decrypt x 1 to get the value of x 2 , that is, compute
PPT Slide
Lager Image
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 6-round 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 6-round encryption. The intermediate state values are shown in the last column.
Partial Encryption and Decryption of the Attack on 6-Round ARIA-128
PPT Slide
Lager Image
Partial Encryption and Decryption of the Attack on 6-Round ARIA-128
13. Allocate a counter vector V [ z ] of size 2 16 where each element is 120-bit length for 16-bit z ( z is the concatenation of evaluations of 16 basis zero-correlation masks). For 2 16 values of x 12 , evaluate all basis zero-correlation 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
PPT Slide
Lager Image
if T ˂ τ , then the guessed key is a possible key candidate.
In the attack, we set the type-I error probability β 0 =2 -2.7 and the type-II error probability β 1 =2 -90 . We have
PPT Slide
Lager Image
≈ 1,
PPT Slide
Lager Image
≈ 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 6-round ARIA encryptions and the complexity of Step 1 is about 2 121 6-round 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 6-round ARIA encryptions and the memory requirement are about 2 90.3 bytes for counters.
- 4.2 Key-recovery attacks on 6-round ARIA with FFT technique
Using the FFT technique, we can attack 6-round AIRA-128 starting from the first round by placing the 4-round zero-correlation 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 ,
PPT Slide
Lager Image
Let k 6 = k 6 [2]⊕ k 6 [5]⊕ k 6 [11]⊕ k 6 [13] and v = u b · k 6 , then we have
PPT Slide
Lager Image
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:
PPT Slide
Lager Image
see [13] and [18] for detail. Then the attack is performed as follows:
1. Allocate the vector of counters Vk 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 88-bit value i = m 1 [0,2,5,8,11,14,15] | m 7 [2,5, 11,12]
and increment the counters xi 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 88-level 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 Vk , 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 Vk less than the threshold τ . If we set β 0 =2 -2.7 and β 0 =2 -90 , we get
PPT Slide
Lager Image
≈ 1 and
PPT Slide
Lager Image
≈ 11. Since the block size n =128 and we have l = 2 16 linear approximations, according to Equation (1), the number of known plaintext-ciphertext 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 88-bit 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 6-round 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. Key-recovery attacks on 7-round ARIA with Partial-Sum and FFT
In this section, we describe some zero-correlation linear cryptanalysis of 7-round ARIA. The attack is based on the first 4-round zero-correlation linear approximates with additional one round in the begin and two rounds at the end, see Fig. 4 . Partial-Sum and FFT are also used in the attack process, respectively.
PPT Slide
Lager Image
Key-recovery Attacks on 7-Round ARIA
- 5.1 Key-recovery attacks on 7-round ARIA with Partial-sum technique
Similarly to the attacks to 6-round ARIA, the partial encryption and decryption using the partial sum technique are proceeded as follows.
1. Allocate 8-bit 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 plaintext-ciphertext 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 7-round 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]
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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 7-round 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] |
PPT Slide
Lager Image
and initialize them to zero. Guess k 8 [11] and partially decrypt x 2 to get the value of x 3 , that is, compute
PPT Slide
Lager Image
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 7-round 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] |
PPT Slide
Lager Image
and initialize them to zero. Guess k 8 [12] and partially decrypt x 3 to get the value of x 4 , that is, compute
PPT Slide
Lager Image
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 7-round 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] |
PPT Slide
Lager Image
and initialize them to zero. Guess k 8 [14] and partially decrypt x 4 to get the value of x 5 , that is, compute
PPT Slide
Lager Image
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 7-round 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] |
PPT Slide
Lager Image
and initialize them to zero. Guess k 8 [15]and partially decrypt x 5 to get the value of x 6 , that is, compute
PPT Slide
Lager Image
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 7-round 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 zero-correlation linear approximations over 7-round ARIA. We then proceed the following steps to recover the right key.
Partial Encryption and Decryption of the Attack on 7-Round ARIA-256
PPT Slide
Lager Image
Partial Encryption and Decryption of the Attack on 7-Round ARIA-256
17. Allocate a counter vector V [ z ] of size 2 16 where each element is 120-bit length for 16-bit z ( z is the concatenation of evaluations of 16 basis zero-correlation masks). For 2 16 values of x 16 , evaluate all basis zero-correlation 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
PPT Slide
Lager Image
if T ˂ τ , then the guessed keys are a possible key candidates.
In this attack, we set the type-I error probability β 0 = 2 -2.7 and the type-II error probability β 1 = 2 -186 . We have
PPT Slide
Lager Image
≈ 1,
PPT Slide
Lager Image
≈ 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 7-round ARIA encryptions and In total, the data complexity is about 2 124.6 known plaintexts, the time complexity is about 2 203.5 7-round ARIA encryptions and the memory requirements are about 2 152 bytes for counters.
- 5.2 Key-recovery attacks on 7-round ARIA with FFT technique
In our attack, one round is added before and two rounds are appended after the linear approximates with zero-correlation 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 ,
PPT Slide
Lager Image
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
PPT Slide
Lager Image
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:
PPT Slide
Lager Image
Then the attack is performed as follows:
1. Allocate the vector of counters Vk 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 plaintext-ciphertext pairs, extract the 8-bit 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 xi 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 184-level 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 Vk 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 Vk less than the threshold τ . If we set β 0 =2 -2.7 and β 1 =2 -186 , we get
PPT Slide
Lager Image
≈ 1 and
PPT Slide
Lager Image
≈ 15.7. Since the block size n =128 and we have l = 2 16 linear approximations, according to Equation (1), the number of known plaintext-ciphertext 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 184-bit 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 7-round 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 zero-correlation linear cryptanalysis. We deduce some 4-round zero-correlation linear approximations of ARIA, and based on those linear approximations, we give some keyrecovery attacks on 6/7 round ARIA-128/256 with Partial-sum technique and FFT technique taken into consideration. For the first time, we consider the security of ARIA against zero-correlation linear cryptanalysis. While two techniques are used in the attack, it also gives us a chance to compare the partial-sum 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.
E-mail: 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.
E-mail: 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.
E-mail: wky543@sina.com
References
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 Reduced-Round ARIA and Camellia,” Journal of Computer Science and Technology 22 449 - 456    DOI : 10.1007/s11390-007-9056-0
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 Reduced-round ARIA Block Cipher,” ISPEC, LNCS Vol.6047 19 - 29
Tang X. , Sun B. , Li R. 2011 “A Meet-in-the-middle Attack on Reduced-Round 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 7-Round ARIA-192,” 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/s10623-012-9697-z
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. “Zero-correlation 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 Zero-Correlation 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 “Zero-correlation Linear Cryptanalysis of Reduced round LBlock,” Designs, Codes and Cryptography 73 (2) 683 - 698    DOI : 10.1007/s10623-014-9976-y
Wen L. , Wang M. , Bogdanov A. “Multidimensional Zero-Correlation 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