# Multiple Impossible Differentials Cryptanalysis on 7-Round ARIA-192

Authors: Zi-Long Jiang; Chen-Hui Jin
Journal: Security and Communication Networks
 (2018)

---

## Abstract

This paper studies the security of 7-round ARIA-192 against multiple impossible differentials cryptanalysis. We propose six special 4-round impossible differentials which have the same input difference and different output difference with the maximum number of nonzero common bytes. Based on these differentials, we construct six attack trails including the maximum number of common subkey bytes. Under such circumstances, we utilize an efficient sieving process to improve the efficiency of eliminating common subkeys; therefore, both data and time complexities are reduced. Furthermore, we also present an efficient algorithm to recover the master key via guess-and-determine technique. Taking advantage of the above advances, we have obtained the best result so far for impossible differential cryptanalysis of ARIA-192, with time, data, and memory complexities being2189.8 7-round ARIA encryptions, 2116.6 chosen plaintexts, and 2139.3 bytes, respectively.


---

## Body

## 1. Introduction

Impossible differential attack [1] is a significant method in cryptanalysis for block ciphers. Researchers will first build one or more differentials whose probabilities are zero. Then based on these differentials, they will construct attack trails and obtain the correct subkeys by rejecting all the wrong subkeys. The second phase is called the subkey sieving phase. Actually, the subkey sieving phase is highly technical: in 2008, Lu et al. [2] introduced the early abort technique. They guessed a small quantity of subkeys and selected the useful pairs which can produce the expected difference so as to reduce time complexity. At ASIACRYPT 2014, Boura et al. [3] presented the state-test technique to reduce time complexity by decreasing the quantity of subkey bits during an attack. Li et al. [4] presented the new early abort technique which does not need to check all the remaining pairs, therefore reducing time complexity. As a powerful form of cryptanalysis, impossible differential attack is extensively used to analyze many block ciphers, such as ARIA [5] and AES [6].In 2008, multiple impossible differentials cryptanalysis was proposed by Tsunoo et al. [7], and Lu et al. also presented the idea that multiple variants of the attack trail can be applied using the same data set [8]. After that, Boura et al. [3] and Li et al. [4, 9] also used multiple impossible differentials to attack CLEFIA, Camellia, FOX, and so on and got good results. They aimed at recovering more subkey bits and increasing the probability of the remaining pairs, thus reducing data complexity. For example, Li et al. [9] presented multiple impossible differentials attacks on FOX with better results than other cryptanalysis of FOX known so far. They constructed four impossible differentials to recover four parts of subkeys. Note that these four differentials play the same role, and the order of differentials to be used does not affect the result.ARIA, a 128-bit substitution-permutation network block cipher, was proposed as Korean standard block cipher algorithm in 2004. After analyzing its security against liner, differential, impossible differential, and square attacks, the designers declared that ARIA has a better resistance against the above cryptanalysis than AES. Wu et al. [10] constructed a 4-round impossible differential and presented a 6-round attack on ARIA. The cryptanalytic result was further enhanced by Li et al. [11] and Shenhua and Chunyan [12], respectively. Then Du and Chen [13] proposed a 7-round impossible differential attack on ARIA-256. Xie and Chen [14] presented a 7-round impossible differential attack on ARIA-192 (however, we find a flaw in the steps of its cryptanalysis). Despite all these contributions, the previous studies neither recover the actual master key of ARIA nor have a research on the security against multiple impossible differentials cryptanalysis.At EUROCRYPT 2016, Sun et al. proved that if the details of theS-boxes are not considered, the length of the impossible differential of ARIA could not be improved [15], so we would like to improve the sieving process to obtain better results. Different from preceding studies, our multiple impossible differentials cryptanalysis is expected to reduce the retention rate of wrong subkeys in subkey sieving phase, thus reducing data complexity and time complexity. We also optimize the order of attack trails (i.e., the attack trails with the maximum number of common bytes are priority). If we conclude that a current common subkey is wrong, it is unnecessary for this common subkey to be sieved by other attack trails; therefore, the efficiency of eliminating common subkeys can be improved. Based on this efficient sieving process, we propose the first multiple impossible differentials attack on 7-round ARIA-192, which improves impossible differential attack in two dimensions (i.e., data and time complexities). Table 1 is the comparison of cryptanalytic results on ARIA.Table 1
The comparison of cryptanalytic attacks on ARIA.
Attack type Rounds Time Data Memory Reference Impossible differential 5 2 71.6 2 71.3 2 72 [12] Impossible differential 6 2 112 2 121 2 121 [10] Impossible differential 6 2 104 2 120.5 2 121 [12] Impossible differential 7 2 238 2 125 - [13] Impossible differentialmk 7 2 189.8 2 116.6 2 139.3 This paper Integral attack 7 2 225.8 2 100.6 - [16] Boomerang attack 7 2 236 2 128 2 184 [17] Meet-in-the-middle 7 2 161.3 2 96 2 185 [18] Meet-in-the-middlemk 7 2 136.1 2 115 2 130 [19] Meet-in-the-middle 8 2 251.6 2 56 2 252 [18] Meet-in-the-middlemk 8 2 245.9 2 113 2 138 [19] mk: recover the actual master key; -: not given in the related paper.The remainder of the paper is organized as follows. Section2 briefly describes the ARIA cipher and provides the notations adopted in this paper. Section 3 constructs the 4-round multiple impossible differentials. Section 4 presents our impossible differential attacks on 7-round ARIA-192 combined with various techniques. Section 5 concludes this paper.


## 2. Preliminaries

### 2.1. Description of ARIA

The block cipher ARIA is a 128-bitSPN model and the numbers of the round are 12/14/16 corresponding to the keys of 128/192/256 bits, respectively. The plaintext, the ciphertext, and the internal state of ARIA are treated as a 4×4 matrix, as shown in Figure 1.Figure 1
Sixteen cells with every byte numbered.Three operations are applied in every round as follows.(1) Round Key Addition (AK). This operation includes an XOR with the round subkeys which are derived from the master key.(2) Substitution Layer (SL). This operation, based on four types of 8-bit S-boxes S1, S2, S1-1, and S2-1, has two types of substitution layers SL1 and SL2. SL1 is for the odd rounds, and SL2 is for the even rounds. The specific layers are as follows. (1)SL1=S1S2S1-1S2-1S1S2S1-1S2-1S1S2S1-1S2-1S1S2S1-1S2-1SL2=S1-1S2-1S1S2S1-1S2-1S1S2S1-1S2-1S1S2S1-1S2-1S1S2.(3) Diffusion Layer (DL). A linear map DL:F2816→F2816 is given by (x0,x1,…,x15)→(y0,y1,…,y15), where (2)y0=x3⊕x4⊕x6⊕x8⊕x9⊕x13⊕x14y1=x2⊕x5⊕x7⊕x8⊕x9⊕x12⊕x15y2=x1⊕x4⊕x6⊕x10⊕x11⊕x12⊕x15y3=x0⊕x5⊕x7⊕x10⊕x11⊕x13⊕x14y4=x0⊕x2⊕x5⊕x8⊕x11⊕x14⊕x15y5=x1⊕x3⊕x4⊕x9⊕x10⊕x14⊕x15y6=x0⊕x2⊕x7⊕x9⊕x10⊕x12⊕x13y7=x1⊕x3⊕x6⊕x8⊕x11⊕x12⊕x13y8=x0⊕x1⊕x4⊕x7⊕x10⊕x13⊕x15y9=x0⊕x1⊕x5⊕x6⊕x11⊕x12⊕x14y10=x2⊕x3⊕x5⊕x6⊕x8⊕x13⊕x15y11=x2⊕x3⊕x4⊕x7⊕x9⊕x12⊕x14y12=x1⊕x2⊕x6⊕x7⊕x9⊕x11⊕x12y13=x0⊕x3⊕x6⊕x7⊕x8⊕x10⊕x13y14=x0⊕x3⊕x4⊕x5⊕x9⊕x11⊕x14y15=x1⊕x2⊕x4⊕x5⊕x8⊕x10⊕x15.Note that Diffusion Layer is an involution and therefore DL-1=DL. In the last round, the DL is substituted by AK to generate ciphertexts.The key schedule algorithm can be divided into two parts, that is, Initialization and Round Key Generation. This section focuses on the description of ARIA-192. For more details, please refer to [5].(1) Initialization. The master key is 192 bits in size which is loaded to 256 bits (KL,KR), and the remaining 64-bit space on KR is filled with zero.Then, four 128-bit values of(W0,W1,W2,W3) are generated from (KL,KR) as follows:(3)W0=KL(4)W1=FoW0,CK1⊕KR(5)W2=FeW1,CK2⊕W0(6)W3=FoW2,CK3⊕W1,where Fe is the even round function and Fo is the odd round function. Three 128-bit values of (CK1,CK2,CK3) are constants.(2) Round Key Generation. Eight round subkeys ki are generated as follows (0≤i≤7):(7)k0=W0⊕W1>>>19(8)k1=W1⊕W2>>>19(9)k2=W2⊕W3>>>19(10)k3=W0>>>19⊕W3(11)k4=W0⊕W1>>>31(12)k5=W1⊕W2>>>31(13)k6=W2⊕W3>>>31(14)k7=W0>>>31⊕W3.


### 2.2. Notations

Some notations are given as follows:P: plaintextC: ciphertextΔx: the difference of xki,(p,…,r): pth,…,rth byte in the i-th round subkeyΔa→i-roundΔb: Δa cannot be Δb after i-roundxi,(p,...,r)AK/SL/DL: the intermediate values of pth,…,rth bytes in the i-th round after the AK/SL/DLIn this paper, we denote the whitening key ask0.


## 2.1. Description of ARIA

The block cipher ARIA is a 128-bitSPN model and the numbers of the round are 12/14/16 corresponding to the keys of 128/192/256 bits, respectively. The plaintext, the ciphertext, and the internal state of ARIA are treated as a 4×4 matrix, as shown in Figure 1.Figure 1
Sixteen cells with every byte numbered.Three operations are applied in every round as follows.(1) Round Key Addition (AK). This operation includes an XOR with the round subkeys which are derived from the master key.(2) Substitution Layer (SL). This operation, based on four types of 8-bit S-boxes S1, S2, S1-1, and S2-1, has two types of substitution layers SL1 and SL2. SL1 is for the odd rounds, and SL2 is for the even rounds. The specific layers are as follows. (1)SL1=S1S2S1-1S2-1S1S2S1-1S2-1S1S2S1-1S2-1S1S2S1-1S2-1SL2=S1-1S2-1S1S2S1-1S2-1S1S2S1-1S2-1S1S2S1-1S2-1S1S2.(3) Diffusion Layer (DL). A linear map DL:F2816→F2816 is given by (x0,x1,…,x15)→(y0,y1,…,y15), where (2)y0=x3⊕x4⊕x6⊕x8⊕x9⊕x13⊕x14y1=x2⊕x5⊕x7⊕x8⊕x9⊕x12⊕x15y2=x1⊕x4⊕x6⊕x10⊕x11⊕x12⊕x15y3=x0⊕x5⊕x7⊕x10⊕x11⊕x13⊕x14y4=x0⊕x2⊕x5⊕x8⊕x11⊕x14⊕x15y5=x1⊕x3⊕x4⊕x9⊕x10⊕x14⊕x15y6=x0⊕x2⊕x7⊕x9⊕x10⊕x12⊕x13y7=x1⊕x3⊕x6⊕x8⊕x11⊕x12⊕x13y8=x0⊕x1⊕x4⊕x7⊕x10⊕x13⊕x15y9=x0⊕x1⊕x5⊕x6⊕x11⊕x12⊕x14y10=x2⊕x3⊕x5⊕x6⊕x8⊕x13⊕x15y11=x2⊕x3⊕x4⊕x7⊕x9⊕x12⊕x14y12=x1⊕x2⊕x6⊕x7⊕x9⊕x11⊕x12y13=x0⊕x3⊕x6⊕x7⊕x8⊕x10⊕x13y14=x0⊕x3⊕x4⊕x5⊕x9⊕x11⊕x14y15=x1⊕x2⊕x4⊕x5⊕x8⊕x10⊕x15.Note that Diffusion Layer is an involution and therefore DL-1=DL. In the last round, the DL is substituted by AK to generate ciphertexts.The key schedule algorithm can be divided into two parts, that is, Initialization and Round Key Generation. This section focuses on the description of ARIA-192. For more details, please refer to [5].(1) Initialization. The master key is 192 bits in size which is loaded to 256 bits (KL,KR), and the remaining 64-bit space on KR is filled with zero.Then, four 128-bit values of(W0,W1,W2,W3) are generated from (KL,KR) as follows:(3)W0=KL(4)W1=FoW0,CK1⊕KR(5)W2=FeW1,CK2⊕W0(6)W3=FoW2,CK3⊕W1,where Fe is the even round function and Fo is the odd round function. Three 128-bit values of (CK1,CK2,CK3) are constants.(2) Round Key Generation. Eight round subkeys ki are generated as follows (0≤i≤7):(7)k0=W0⊕W1>>>19(8)k1=W1⊕W2>>>19(9)k2=W2⊕W3>>>19(10)k3=W0>>>19⊕W3(11)k4=W0⊕W1>>>31(12)k5=W1⊕W2>>>31(13)k6=W2⊕W3>>>31(14)k7=W0>>>31⊕W3.


## 2.2. Notations

Some notations are given as follows:P: plaintextC: ciphertextΔx: the difference of xki,(p,…,r): pth,…,rth byte in the i-th round subkeyΔa→i-roundΔb: Δa cannot be Δb after i-roundxi,(p,...,r)AK/SL/DL: the intermediate values of pth,…,rth bytes in the i-th round after the AK/SL/DLIn this paper, we denote the whitening key ask0.


## 3. Four-Round Impossible Differentials of ARIA

We find six 4-round impossible differentials of ARIA with the same input difference. As shown in Figure2, two bytes of the input difference are nonzero, and the others are zero. Four bytes of the output difference are nonzero and equal, and the others are zero. The other five differentials have the same input difference and different output difference with the maximum number of nonzero common bytes. The positions of nonzero difference are shown in Table 2.Table 2
Six 4-round impossible differential distinguishers of ARIA.
Number The positions of nonzero input difference The positions of nonzero output difference ( 1 ) ( 7,13 ) ( 0,4 , 13,15 ) ( 2 ) ( 0,1 , 4,13 ) ( 3 ) ( 0,1 , 13,15 ) ( 4 ) ( 0,1 , 4,7 ) ( 5 ) ( 0,4 , 7,15 ) ( 6 ) ( 0,1 , 7,15 )Figure 2
One of 4-round impossible differentials of ARIA.Taking the first differential as an example, we describe its property as follows.Property 1.
There is a 4-round impossible differential of ARIA:(15)0,0,0,0,0,0,0,e7,0,0,0,0,0,e13,0,0⟶4-roundm,0,0,0,m,0,0,0,0,0,0,0,0,m,0,m,where (e7,e13)≠(0,0) and m is nonzero difference.Proof.
First, we analyze the first two rounds of the differential. Two nonzero difference bytesf7, f13 can be obtained from the input difference through the AK and SL operations. Then calculate Δx3DL=(g0,g1,0,g3,0,0,g6,g7,g8,0,g10,g11,g12,g13,0,0), where gi are nonzero difference bytes. Δx3DL is preserved after the AK and SL operations, and then Δx4SL=(h0,h1,0,h3,0,0,h6,h7,h8,0,h10,h11,h12,h13,0,0) is obtained. After DL operation, we can obtain i0=i10=h3⊕h6⊕h8⊕h13 and i0⊕i10=0.Second, we analyze the last two rounds of the differential. We can obtainΔx6I=(0,l1,0,0,0,0,0, l7,0,l9,0,l11,0,0,0,0) from the output difference after the operations DL-1, SL-1, and AK-1. The DL-1 of R5 makes s0=l9≠0, s10=0. Then after the operations SL-1, AK-1, we obtain j0≠0, j10=0 and therefore j0⊕j10≠0, which contradicts i0⊕i10=0.Figure2 underlines this contradiction, and the other five impossible differentials can also be proven in a similar way.


## 4. A Multiple Impossible Differentials Attack on 7-Round ARIA-192

As shown in Figure3, two rounds at the top and one round at the bottom are added to the 4-round differentials. We first propose the multiple impossible differentials attack on 7-round ARIA-192 combined with a series of techniques.Figure 3
One of 7-round impossible differential attack trails.


### 4.1. Properties of Diffusion Layer

In this section, we first analyze the flaw in [14] and then describe the two linear properties used in this paper.In attacking 6-byte subkeyk1,(0,1,7,10,11,12), 6-byte values of x1,(0,1,7,10,11,12)DL are needed. From the definition of the Diffusion Layer, we know that the 6-byte values are functions of 14-byte x1,(1,2,3,4,5,6,7,8,9,11,12,13,14,15)SL. However, the attack scenario in [14] did not attack 2-byte whitening keys k0,(5,15) and cannot obtain 2-byte values of x1,(1,10)DL, so the input difference of the differential cannot be obtained and the attack does not work. Section  4 of [14] presented another attack scenario attacking 14-byte x1,(1,2,3,4,5,6,7,8,9,11,12,13,14,15)SL, but the time complexity exceeded 2192 7-round ARIA encryptions. To sum up, the attack scenario of ARIA-192 in [14] does not work. This paper corrects this flaw. Moreover, we present the multiple impossible differentials attack on 7-round ARIA-192.We provide Properties2 and 3 of Diffusion Layer. By using Property 2, if the input difference before DL in the first round satisfies eight difference equations of Property 2, we conclude that 10-byte difference Δx1,(2,3,4,5,6,8,9,13,14,15)DL are zero. Similarly, by using Property 3, if the 6-byte difference satisfies d0=d1=d7=d10=d11=d12=d≠0 and the others are zero, we conclude that 2-byte difference e7=e13=e≠0 and the others are zero. We describe these two properties as follows.Property 2.
Let(b0,b1,…,b15) and (c0,c1,…,c15) denote the input difference and output difference of the Diffusion Layer in the first round. Then c2=c3=c4=c5=c6=c8=c9=c13=c14=c15=0 if and only if the following eight equations are satisfied simultaneously. (16)b1=b11(17)b4=b14(18)b5=b15(19)b1⊕b4⊕b5⊕b7⊕b13=0(20)b4⊕b5⊕b6⊕b12=0(21)b1⊕b2⊕b4⊕b8=0(22)b2⊕b7⊕b9⊕b12⊕b13=0(23)b1⊕b3⊕b5⊕b9=0.Property 3.
Let(d0,d1,…,d15) and (e0,e1,…,e15) denote the input difference and output difference of the Diffusion Layer in the second round. Six-byte difference satisfies d0=d1=d7=d10=d11=d12=d≠0 and the others are zero; we can reach that 2-byte difference satisfies e7=e13=e≠0 and the others are zero.See Appendix for the proof of these two properties.


### 4.2. An Efficient Sieving Process

In this section, we introduce an efficient sieving process. For simplicity, we abbreviate the notation in Table3.Table 3
Six 4-round impossible differential distinguishers of ARIA.
Number The positions of nonzero output difference Whitening key and 1-st round subkeys 7-th round subkeys ( 1 ) A 1 = { 0,4 , 13,15 } k 0 ′ = k 0 , ( 1,2 , 3,4 , 5,6 , 7,8 , 9,11,12,13,14,15 )  k1′=k1,(0,1,7,10,11,12) k 7 ( 1 ) = k 7 , ( 0,4 , 13,15 ) ( 2 ) A 2 = { 0,1 , 4,13 } k 7 ( 2 ) = k 7 , ( 0,1 , 4,13 ) ( 3 ) A 3 = { 0,1 , 13,15 } k 7 ( 3 ) = k 7 , ( 0,1 , 13,15 ) ( 4 ) A 4 = { 0,1 , 4,7 } k 7 ( 4 ) = k 7 , ( 0,1 , 4,7 ) ( 5 ) A 5 = { 0,4 , 7,15 } k 7 ( 5 ) = k 7 , ( 0,4 , 7,15 ) ( 6 ) A 6 = { 0,1 , 7,15 } k 7 ( 6 ) = k 7 , ( 0,1 , 7,15 ) k 0 ′, k1′ are 14-byte whitening keys and 6-byte subkeys in the first round during an attack, respectively; k7(i) are 4-byte subkeys which need to be guessed in the 7-th round when using the i-th distinguisher.The idea of the efficient sieving process is summarized as below. We would like to construct some special attack trails with the maximum number of common bytes. Then the common subkeys can be repeatedly sieved by multiple attack trails. If we conclude that the current common subkey is wrong, it is unnecessary for this common subkey to be sieved by other attack trails, therefore reducing the retention rate in sieving subkeys and improving the result.First, we find some impossible differentials which have the same input difference and different output difference with the maximum number of nonzero common bytes. In this paper, only 2-byte extra nonzero output differences are needed, and then five extra differentials can be constructed.Second, we optimize the order of attack trails to be used (i.e., the attack trails with the maximum number of common bytes are priority). In this paper, although each attack trail discards possible values of 24 subkey bytes, the first two attack trails have 23 common subkey bytes, and only 26 subkey bytes need to be sieved in our attack scenario, which concludes six attack trails. Then these common subkeys can be sieved multiple times and the wrong subkeys will be rejected as soon as possible, therefore reducing the complexity.In Section4.3, we use the efficient sieving process to reduce data complexity and time complexity from steps (12) to (16) in online phase. In Section 4.6, we analyze the complexity when attackers only use one of these attack trails with the same techniques. The comparison of the two complexities indicates that this efficient sieving process is practical.


### 4.3. The Procedure of 7-Round Attack on ARIA-192

In this section, the procedure will be divided into two phases.Precomputation Phase. Let S denote one of four types of 8-bit S-boxes and Δin and Δout denote the input and output difference of S-boxes. When Δin and Δout are nonzero bytes, the equation S(x)⊕S(x⊕Δin)=Δout has one solution on average.According to four types ofS-boxes S1, S2, S1-1, and S2-1, we construct four tables Λi(i=1,2,3,4), respectively. Then store the calculated x in Λi(i=1,2,3,4) indexed by 216 possible values of (Δin,Δout).Online Phase. The online phase can be summarized in the following steps. Through the quick sort method [20], steps (1) and (2) select useful plaintext pairs whose ciphertext pairs meet the requirements of the structure. By using Properties 2 and 3, steps (3)–(11) select the plaintext pairs which can obtain the input difference of the distinguisher. According to six special impossible differential attack trails, steps (12)–(16) reject wrong subkeys through the efficient sieving process. Taking advantage of master key recovery algorithm, step (17) rejects wrong subkeys and recovers the master key of ARIA-192.The specific steps are as follows:(1)
Select2112 plaintexts which are fixed in 2 bytes (0,10), and take all the values in other 14 bytes. These 2112 plaintexts are called a structure. We take 2n structures and obtain 2n+112×(2n+112-1)/2≈2n+223 plaintext pairs.(2)
By the quick sort method [20], we can choose the pairs whose ciphertext pairs have zero difference in all but the 4 bytes at Ai(i=1,…,6). Then 2n+223×2-96=2n+127 pairs remain in 2n structures. Store the remaining plaintext pairs at 14 bytes (1,2,3,4,5,6,7,8,9,11,12,13,14,15) and the corresponding ciphertext pairs at 4 bytes Ai(i=1,…,6) in table Ωi, which are indexed by the serial number of plaintext pairs (hereafter referred to as SN).(3)
Guessk0,(1,11) and partially encrypt plaintext pairs in Ω1, and then select plaintext pairs whose difference b(1,11) satisfies (16). We store 2n+127×2-8=2n+119 remaining (b(1,11),x1,(1,11)SL) and its SN in table T(1) indexed by k0,(1,11).(4)
For currentk0,(1,11), guess k0,(4,14) and partially encrypt plaintext pairs in T(1), and then select plaintext pairs whose difference b(4,14) satisfies the equation (17). We store 2n+119×2-8=2n+111 remaining (b(4,14),x1,(4,14)SL) and its SN in table T(2) indexed by k0,(4,14).(5)
For currentk0,(1,4,11,14), guess k0,(5,15) and partially encrypt plaintext pairs in T(2), and then select plaintext pairs whose difference b(5,15) satisfies the equation (18). We store 2n+111×2-8=2n+103 remaining (b(5,15),x1,(5,15)SL) and its SN in table T(3) indexed by k0,(5,15).(6)
For currentk0,(1,4,5,11,14,15), guess k0,(7,13) and partially encrypt plaintext pairs in T(3), and then select plaintext pairs whose difference b(7,13) satisfies (19). We store 2n+103×2-8=2n+95 remaining (b(7,13),x1,(7,13)SL) and its SN in table T(4) indexed by k0,(7,13).(7)
For currentk0,(1,4,5,7,11,13,14,15), guess k0,(6,12) and partially encrypt plaintext pairs in T(4), and then select plaintext pairs whose difference b(6,12) satisfies (20). We store 2n+95×2-8=2n+87 remaining (b(6,12),x1,(6,12)SL) and its SN in table T(5) indexed by k0,(6,12).(8)
For currentk0,(1,4,5,6,7,11,12,13,14,15), guess k0,(2,8) and partially encrypt plaintext pairs in T(5), and then select plaintext pairs whose difference b(2,8) satisfies (21). We store 2n+87×2-8=2n+79 remaining (b(2,8),x1,(2,8)SL) and its SN in table T(6) indexed by k0,(2,8).(9)
For currentk0,(1,2,4,5,6,7,8,11,12,13,14,15), we have known b(2),b(7),b(12),b(13), and then b(9) can be obtained from (22). The value of x1,(9)AK can be obtained by accessing the row in table Λ2. Compute P9⊕x1,(9)AK, and k0,(9) can be obtained. Store 2n+79×2-8=2n+71 remaining (b9,x1,(9)SL) and its SN in table T(7) indexed by k0,(9).(10)
For currentk0,(1,2,4,5,6,7,8,9,11,12,13,14,15), we have known b(1),b(5),b(9), and then b(3) can be obtained from (23). The value of x1,(3)AK can be obtained by accessing the row in table Λ4. Compute P3⊕x1,(3)AK, and k0,(3) can be obtained. Store 2n+71×2-8=2n+63 remaining (b3,x1,(3)SL) and its SN in table T(8) indexed by k0,(3).(11)
For currentk0′, (x2,(0,1,7,10,11,12)I,Δx2,(0,1,7,10,11,12)I) can be obtained by computing DL(x1,(1,2,3,4,5,6,7,8,9,11,12,13,14,15)SL). We choose the pairs whose 6-byte difference Δx2,(0,1,7,10,11,12)I is all nonzero. Guess Δx2,(0)SL and then obtain 6-byte difference Δx2,(0,1,7,10,11,12)SL. For each of these 6-byte differences, 6-byte values of x2,(0,1,7,10,11,12)AK can be obtained by accessing the row in corresponding table Λi. Compute x2,(0,1,7,10,11,12)I⊕x2,(0,1,7,10,11,12)AK and obtain k1′. We store 2n+63×28÷248=2n+23 SN in table T(9) indexed by 248 possible values of k1′.(12)
For current(k0′,k1′), guess 1-byte nonzero difference Δx7,(0)I and then obtain 4-byte difference Δx7,(0,4,13,15)I. From the cipher pairs, we can obtain Δx7,(0,4,13,15)SL. For each of these 4-byte differences, 4-byte values of x7,(0,4,13,15)SL can be obtained by accessing the row in corresponding table Λi. Compute x7,(0,4,13,15)SL⊕C2,(0,4,13,15) and obtain k7(1). We store candidate subkeys k7(1) in table C(1) indexed by k7,(0,4,13). For each k7,(0,4,13), if all k7,(15) are discarded, we conclude that the current (k0′,k1′,k7,(0,4,13)) cannot be right, so it is discarded.(13)
For current(k0′,k1′) and the remaining subkeys k7,(0,4,13) in table C(1), we use the second attack trail to sieve wrong subkeys and perform the following substeps.
(13.1)
For each plaintext pairs inΩ2, use the current (k0′,k1′) to select useful pairs whose differences are zero in all but 2 bytes at (7,13) after 2 rounds of ARIA encryptions (i.e., the input difference of distinguishers). Compute SL(Pi⊕k0,i) to satisfy (16)–(23) step by step. Then compute SL(x2,(0,1,7,10,11,12)AK) and choose the pairs which satisfy Property 3. The quantity of the remaining pairs is 2n+127×2-64×2-40=2n+23.(13.2)
The procedure of sieving wrong subkeys is similar to step(12). For each k7,(0,4,13), if all k7,(1) are wrong, the current (k0′,k1′,k7,(0,4,13)) cannot be right and is thus discarded. Otherwise, access the list with index k7,(0,4,13) in table C(1). If k7,(0,4,13) is also a candidate subkey in C(1), we store candidate subkeys k7,(0,1,4,13,15) in table C(2).(14)
For current(k0′,k1′) and the remaining subkeys k7,(0,1,4,13,15) in table C(2), we use the third attack trail to sieve wrong subkeys.
(14.1)
The procedure of choosing the expected pairs ofΩ3 is similar to step (13.1).(14.2)
For eachk7(3) in table C(2), if a k7(3) decrypts a ciphertext pairs to the impossible differential, then this corresponding subkey (k0′,k1′,k7,(0,1,4,13,15)) is wrong and is thus discarded. If all the remaining subkeys in table C(2) are wrong, the current subkey (k0′,k1′) is wrong, and then return to step (12) and check the next (k0′,k1′). Otherwise, store the remaining subkeys k7,(0,1,4,13,15) in table C(3).(15)
For current(k0′,k1′) and the remaining subkeys k7,(0,1,4,13,15) in table C(3), we use the fourth attack trail to sieve wrong subkeys.
(15.1)
The procedure of choosing expect pairs ofΩ4 is similar to step (13.1).(15.2)
For eachk7,(0,1,4) in table C(3), we need to guess one-byte subkey k7,(7). The procedure of sieving subkeys is similar to step (14.2). If all subkeys in C(3) are wrong, then return to step (12) and check the next (k0′,k1′), or store the remaining subkeys k7,(0,1,4,7,13,15) in table C(4).(16)
For currentk0′,k1′ and the remaining subkeys k7,(0,1,4,7,13,15) in table C(4), we use the fifth and the sixth attack trails (i=5,6) to sieve wrong subkeys.
(16.1)
The procedure of choosing the expected pairs ofΩi is similar to step (13.1).(16.2)
For eachk7,(0,1,4,7,13,15) in table C(4), the procedure of sieving wrong subkeys is similar to step (14.2). If all subkeys in C(4) are wrong, return to step (12) and check the next (k0′,k1′), or store the remaining subkeys k7,(0,1,4,7,13,15) in table C(5).(17)
Taking advantage of master key recovery algorithm, if the candidate subkey(k0′,k1′,k7,(0,1,4,7,13,15)) passes the check of the algorithm, we conclude that this subkey is right and recover the master key, or return to step (12) and check the next (k0′,k1′).


### 4.4. Complexity Analysis

The complexity in Precomputation Phase can be neglected compared with the complexity in online phase. The complexities of steps(2)–(10) are shown in Table 4.Table 4
The complexity of online phase.
Step Time complexity (7-round ARIA encryptions) Memory complexity (bytes) ( 2 ) 6 × 2 n × 2 112 log 2 ⁡ 2 112 × 1 16 × 1 7 = 2 n + 114.6 6 × 2 n + 127 × 2 × ( 4 + 14 ) ≈ 2 n + 134.7 ( 3 ) 2 × 2 n + 127 × 2 16 × 2 16 × 1 7 = 2 n + 138.2 2 n + 119 × 4 + n + 127 8 ( 4 ) 2 × 2 16 × 2 n + 119 × 2 16 × 2 16 × 1 7 = 2 n + 146.2 2 n + 111 × 4 + n + 127 8 ( 5 ) 2 × 2 32 × 2 n + 111 × 2 16 × 2 16 × 1 7 = 2 n + 154.2 2 n + 103 × 4 + n + 127 8 ( 6 ) 2 × 2 48 × 2 n + 103 × 2 16 × 2 16 × 1 7 = 2 n + 162.2 2 n + 95 × 4 + n + 127 8 ( 7 ) 2 × 2 64 × 2 n + 95 × 2 16 × 2 16 × 1 7 = 2 n + 170.2 2 n + 87 × 4 + n + 127 8 ( 8 ) 2 × 2 80 × 2 n + 87 × 2 16 × 2 16 × 1 7 = 2 n + 178.2 2 n + 79 × 4 + n + 127 8 ( 9 ) 2 96 × 2 n + 79 × 1 16 × 1 7 = 2 n + 168.2 2 n + 71 × 2 + n + 127 8 ( 10 ) 2 104 × 2 n + 71 × 1 16 × 1 7 = 2 n + 168.2 2 n + 63 × 2 + n + 127 8In step(11), the time complexity is 2112×2n+63×28×(1/16)×(1/7)=2n+176.2 7-round ARIA encryptions, and the memory demands 2n+23×(n+127)/8 bytes.Step(12) needs 2160×2n+23×28×(1/16)×(1/7)=2n+184.2 7-round ARIA encryptions.The time complexity of step(13) has the same value as step (12).Each wrong subkey is rejected by2n+23 pairs with a probability of P1=(1-2-24)2n+23. Step (14) just needs to cheek 240×(P1)2 subkeys in table C(2). Taking advantage of new early abort [9], the probability that a wrong subkey can pass 224d tests of pairs while rejecting 224(d+1) tests of pairs is pd=(1-2-24)224d-(1-2-24)224(d+1), and the mathematical expectation is E(d)=∑d=1∞dpd≈∑d=1∞d(e-d-e-(d+1))≈2-0.8. Thus, the time complexity of step (14) is 2160×240×(P1)2×224-0.8×(1/16)×(1/7)=2216.4×(P1)2 7-round ARIA encryptions.Step(15) just needs to check the remaining subkeys of C(3), so the time complexity is 2160×248×(P1)3×223.2×(1/16)×(1/7)=2224.4×(P1)3 7-round ARIA encryptions.Step(16) just needs to check the remaining subkeys of C(4), so the time complexity is 2160×248×(P1)4×223.2×(1/16)×(1/7)=2224.4×(P1)4 and 2224.4×(P1)5 7-round ARIA encryptions, respectively.The complexity of step(17) is detailed in Section 4.5


### 4.5. The Procedure of Recovering the Master Key for ARIA-192

In 2015, Akshima et al. [19] presented the master key recovery attacks on ARIA for the first time. Through the guess-and-determine technique, we present an efficient algorithm to recover the master key. Taking step (1) of the master key recovery algorithm as an example, if we guess 2128 values of W0 as proposed in [19], the time complexity is equal to 2128×(1/7)=2125.2 7-round ARIA encryptions. Based on guess-and-determine technique, the time complexity can be reduced to 276.5 7-round ARIA encryptions in this paper. For better understanding, we first describe the idea of master key recovery algorithm, and then the specific steps are specified.(1)
Attack2128 possible values for W0:
(a)
By[W0,k0,(1,2,3,4,5,6,7,8,9,11,12,13,14,15)] and (7), we can obtain 112 bits W1 whose 61 bits belong to the first eight bytes and other 51 bits belong to the last eight bytes.(b)
From the key schedule algorithm, we obtainKR(8,9,10,11,12,13,14,15)=0. According to (4), W1,(8,9,10,11,12,13,14,15) can be obtained by calculating F0(W0,CK1).(c)
Take advantage of the common 51 bits ofW1 to reject some wrong guesses of W0. We obtain 2128×2-51=277 remaining W0 and 125 bits of W1. Note that now we cannot obtain 61-th, 62-th, and 63-th bit of W1 and denote 125 bits of W1 as W1′.(2)
Attack the 61-th, 62-th, and 63-th bits ofW1:
(a)
By (8) and [W1′,k1,(0,1,7,10,11,12)], we obtain 48 bits of W2.(b)
By (5) and [W0,W1], we obtain W2.(c)
Take advantage of the common 48 bits ofW2 to obtain 280×2-48=232 remaining [W0,W1,W2].(3)
For each[W0,W1,W2],
(a)
by (6) and [W1,W2], we obtain W3;(b)
by (14) and [W0,k7,(0,1,4,7,13,15)], obtain 48 bits of W3,(c)
taking advantage of the common 48 bits ofW3, we can reject some wrong guesses. We obtain the remaining [W0,W1,W2, W3] and thus can recover the first seven subkeys [k0,…,k7] by calculating (7)–(14). Randomly select 210 plaintexts. If these corresponding ciphertexts can be obtained after 7-round ARIA encryptions, we judge that this subkey is right and recover the master key, or reject this candidate subkey and check the next.The details of step(1) are as follows.(1.1)
Guess 7-byteW0,(0,1,5,6,11,12,14), and W1,(9) can be obtained by calculating (4) and (7). So the retention rate is 2-8 and the quantity of W0,(0,1,5,6,11,12,14) is 248.(1.2)
Guess 2-byteW01=W0,(2⊕3⊕8⊕15), W0,(13), and W1,(10) can be obtained by calculating (4) and (7). So the retention rate is 2-8 and the quantity of [W0,(0,1,5,6,11,12,13,14),W01] is 256.(1.3)
Guess 1-byteW02=W0,(2⊕3⊕4⊕7⊕9), and W1,(11) can be obtained by calculating (4) and (7). So the retention rate is 2-8 and the quantity of [W0,(0,1,5,6,11,12,13,14),W01,W02] is 256.(1.4)
Guess 2-byteW03=W0,(4⊕8⊕10⊕15), W0,(2), and W1,(15) can be obtained by calculating (4) and (7). So the retention rate is 2-8 and the quantity of [W0,(0,1,2,5,6,11,12,13,14),W01,W02,W03] is 264.(1.5)
Guess 2-byteW04=W0,(7⊕9), W0,(15), and W1,(12) can be obtained by calculating (4) and (7). So the retention rate is 2-8 and the quantity of [W0,(0,1,2,5,6,10,11,12,13,14,15),W01,W02,W03,W04] is 272 (note that W0,(10)=W01⊕W02⊕W03⊕W04).(1.6)
Guess 1-byteW05=W0,(4⊕7), and 5-bit of W1,(8) can be obtained by calculating (4) and (7). So the retention rate is 2-5 and the quantity of [W0,(0,1,2,5,6,10,11,12,13,14,15),W01,W02,W03,W04, W05] is 275.(1.7)
Guess 1-byteW0,(3).By[W0,(0,1,2,3,5,6,10,11,12,13,14,15),W01,W02,W03, W04,W05], we can obtain 283W0. Six-bit W1,(13,14) can be obtained by calculating (4) and (7). So the retention rate is 2-6 and the quantity of W0 is 277.To sum up, the time complexity of steps(1.1)–(1.7) is 256,264,264,272,272,280,280, and 283, respectively. So the time complexity of step (1) is (283+2×280)×(1/16)×(1/7)≈276.5 7-round ARIA encryptions.The details of step(2) are as follows.(2.1)
We first sieve the277 remaining W0. According to [W1,(0,10,11,12),k1,(0,10,11,12)] and (8), we can obtain W2,(9,14). Then W2,(9,14) can be obtained by calculating (5). So the retention rate is 2-16 and the quantity of [W0,W1′] is 261.(2.2)
Guess 61-th, 62-th, and 63-th bits ofW1 and we can obtain W1. Then other 32-bit common W2 can be obtained, so the retention rate is 2-32 and the quantity of [W0,W1,W2] is 261+3×2-32=232.To sum up, the time complexity of step(2) is (277+264)×(1/16)×(1/7)≈270.2 7-round ARIA encryptions.The time complexity of step(3) is 232 1-round ARIA encryptions. Consequently, for a subkey (k0′,k1′,k7,(0,1,4,7,13,15)), our algorithm needs 276.5 7-round ARIA encryptions to recover the master key.


### 4.6. The Summary of Complexity

By the analysis in Sections4.4 and 4.5, we take n=4.6 and obtain P1=2-17.5.In step(16) of Section 4.4, the number of the remaining subkeys is ξ=2208×(2-17.5)6=2103, and this step demands ξ×276.5=2179.5 7-round ARIA encryptions.Consequently, our cryptanalysis demands2n+112=2116.6 chosen plaintexts. The memory complexity is dominated by step (2), which is 2n+134.7=2139.3 bytes. The time complexity is dominated by steps (12) and (13), which is 2×2n+184.2=2189.8 7-round ARIA encryptions.By attacking as many common subkey bytes as possible when using different attack trails, the efficient sieving process can improve the efficiency of sieving wrong subkey, so it helps to reduce the retention rate of wrong subkeys to2-17.5×6=2-105. Furthermore, based on one of these attack trails, we analyze the complexity with the same attack scenario, which need to take n=7.1, and the time, data, and memory complexities are 2191.3, 2119.1, and 2189.8, respectively. The comparison of the two complexities is shown in Table 5.Table 5
The comparison of two complexities of ARIA-192.
Attack type Time Data Memory Impossible differential attack with one attack trail 2 191.3 2 119.1 2 139.3 Impossible differential attack in Section4.3 2 189.8 2 116.6 2 139.3It is known from the comparison that the efficient sieving process can increase the efficiency of sieving subkeys, so the results are improved to an extent.


## 4.1. Properties of Diffusion Layer

In this section, we first analyze the flaw in [14] and then describe the two linear properties used in this paper.In attacking 6-byte subkeyk1,(0,1,7,10,11,12), 6-byte values of x1,(0,1,7,10,11,12)DL are needed. From the definition of the Diffusion Layer, we know that the 6-byte values are functions of 14-byte x1,(1,2,3,4,5,6,7,8,9,11,12,13,14,15)SL. However, the attack scenario in [14] did not attack 2-byte whitening keys k0,(5,15) and cannot obtain 2-byte values of x1,(1,10)DL, so the input difference of the differential cannot be obtained and the attack does not work. Section  4 of [14] presented another attack scenario attacking 14-byte x1,(1,2,3,4,5,6,7,8,9,11,12,13,14,15)SL, but the time complexity exceeded 2192 7-round ARIA encryptions. To sum up, the attack scenario of ARIA-192 in [14] does not work. This paper corrects this flaw. Moreover, we present the multiple impossible differentials attack on 7-round ARIA-192.We provide Properties2 and 3 of Diffusion Layer. By using Property 2, if the input difference before DL in the first round satisfies eight difference equations of Property 2, we conclude that 10-byte difference Δx1,(2,3,4,5,6,8,9,13,14,15)DL are zero. Similarly, by using Property 3, if the 6-byte difference satisfies d0=d1=d7=d10=d11=d12=d≠0 and the others are zero, we conclude that 2-byte difference e7=e13=e≠0 and the others are zero. We describe these two properties as follows.Property 2.
Let(b0,b1,…,b15) and (c0,c1,…,c15) denote the input difference and output difference of the Diffusion Layer in the first round. Then c2=c3=c4=c5=c6=c8=c9=c13=c14=c15=0 if and only if the following eight equations are satisfied simultaneously. (16)b1=b11(17)b4=b14(18)b5=b15(19)b1⊕b4⊕b5⊕b7⊕b13=0(20)b4⊕b5⊕b6⊕b12=0(21)b1⊕b2⊕b4⊕b8=0(22)b2⊕b7⊕b9⊕b12⊕b13=0(23)b1⊕b3⊕b5⊕b9=0.Property 3.
Let(d0,d1,…,d15) and (e0,e1,…,e15) denote the input difference and output difference of the Diffusion Layer in the second round. Six-byte difference satisfies d0=d1=d7=d10=d11=d12=d≠0 and the others are zero; we can reach that 2-byte difference satisfies e7=e13=e≠0 and the others are zero.See Appendix for the proof of these two properties.


## 4.2. An Efficient Sieving Process

In this section, we introduce an efficient sieving process. For simplicity, we abbreviate the notation in Table3.Table 3
Six 4-round impossible differential distinguishers of ARIA.
Number The positions of nonzero output difference Whitening key and 1-st round subkeys 7-th round subkeys ( 1 ) A 1 = { 0,4 , 13,15 } k 0 ′ = k 0 , ( 1,2 , 3,4 , 5,6 , 7,8 , 9,11,12,13,14,15 )  k1′=k1,(0,1,7,10,11,12) k 7 ( 1 ) = k 7 , ( 0,4 , 13,15 ) ( 2 ) A 2 = { 0,1 , 4,13 } k 7 ( 2 ) = k 7 , ( 0,1 , 4,13 ) ( 3 ) A 3 = { 0,1 , 13,15 } k 7 ( 3 ) = k 7 , ( 0,1 , 13,15 ) ( 4 ) A 4 = { 0,1 , 4,7 } k 7 ( 4 ) = k 7 , ( 0,1 , 4,7 ) ( 5 ) A 5 = { 0,4 , 7,15 } k 7 ( 5 ) = k 7 , ( 0,4 , 7,15 ) ( 6 ) A 6 = { 0,1 , 7,15 } k 7 ( 6 ) = k 7 , ( 0,1 , 7,15 ) k 0 ′, k1′ are 14-byte whitening keys and 6-byte subkeys in the first round during an attack, respectively; k7(i) are 4-byte subkeys which need to be guessed in the 7-th round when using the i-th distinguisher.The idea of the efficient sieving process is summarized as below. We would like to construct some special attack trails with the maximum number of common bytes. Then the common subkeys can be repeatedly sieved by multiple attack trails. If we conclude that the current common subkey is wrong, it is unnecessary for this common subkey to be sieved by other attack trails, therefore reducing the retention rate in sieving subkeys and improving the result.First, we find some impossible differentials which have the same input difference and different output difference with the maximum number of nonzero common bytes. In this paper, only 2-byte extra nonzero output differences are needed, and then five extra differentials can be constructed.Second, we optimize the order of attack trails to be used (i.e., the attack trails with the maximum number of common bytes are priority). In this paper, although each attack trail discards possible values of 24 subkey bytes, the first two attack trails have 23 common subkey bytes, and only 26 subkey bytes need to be sieved in our attack scenario, which concludes six attack trails. Then these common subkeys can be sieved multiple times and the wrong subkeys will be rejected as soon as possible, therefore reducing the complexity.In Section4.3, we use the efficient sieving process to reduce data complexity and time complexity from steps (12) to (16) in online phase. In Section 4.6, we analyze the complexity when attackers only use one of these attack trails with the same techniques. The comparison of the two complexities indicates that this efficient sieving process is practical.


## 4.3. The Procedure of 7-Round Attack on ARIA-192

In this section, the procedure will be divided into two phases.Precomputation Phase. Let S denote one of four types of 8-bit S-boxes and Δin and Δout denote the input and output difference of S-boxes. When Δin and Δout are nonzero bytes, the equation S(x)⊕S(x⊕Δin)=Δout has one solution on average.According to four types ofS-boxes S1, S2, S1-1, and S2-1, we construct four tables Λi(i=1,2,3,4), respectively. Then store the calculated x in Λi(i=1,2,3,4) indexed by 216 possible values of (Δin,Δout).Online Phase. The online phase can be summarized in the following steps. Through the quick sort method [20], steps (1) and (2) select useful plaintext pairs whose ciphertext pairs meet the requirements of the structure. By using Properties 2 and 3, steps (3)–(11) select the plaintext pairs which can obtain the input difference of the distinguisher. According to six special impossible differential attack trails, steps (12)–(16) reject wrong subkeys through the efficient sieving process. Taking advantage of master key recovery algorithm, step (17) rejects wrong subkeys and recovers the master key of ARIA-192.The specific steps are as follows:(1)
Select2112 plaintexts which are fixed in 2 bytes (0,10), and take all the values in other 14 bytes. These 2112 plaintexts are called a structure. We take 2n structures and obtain 2n+112×(2n+112-1)/2≈2n+223 plaintext pairs.(2)
By the quick sort method [20], we can choose the pairs whose ciphertext pairs have zero difference in all but the 4 bytes at Ai(i=1,…,6). Then 2n+223×2-96=2n+127 pairs remain in 2n structures. Store the remaining plaintext pairs at 14 bytes (1,2,3,4,5,6,7,8,9,11,12,13,14,15) and the corresponding ciphertext pairs at 4 bytes Ai(i=1,…,6) in table Ωi, which are indexed by the serial number of plaintext pairs (hereafter referred to as SN).(3)
Guessk0,(1,11) and partially encrypt plaintext pairs in Ω1, and then select plaintext pairs whose difference b(1,11) satisfies (16). We store 2n+127×2-8=2n+119 remaining (b(1,11),x1,(1,11)SL) and its SN in table T(1) indexed by k0,(1,11).(4)
For currentk0,(1,11), guess k0,(4,14) and partially encrypt plaintext pairs in T(1), and then select plaintext pairs whose difference b(4,14) satisfies the equation (17). We store 2n+119×2-8=2n+111 remaining (b(4,14),x1,(4,14)SL) and its SN in table T(2) indexed by k0,(4,14).(5)
For currentk0,(1,4,11,14), guess k0,(5,15) and partially encrypt plaintext pairs in T(2), and then select plaintext pairs whose difference b(5,15) satisfies the equation (18). We store 2n+111×2-8=2n+103 remaining (b(5,15),x1,(5,15)SL) and its SN in table T(3) indexed by k0,(5,15).(6)
For currentk0,(1,4,5,11,14,15), guess k0,(7,13) and partially encrypt plaintext pairs in T(3), and then select plaintext pairs whose difference b(7,13) satisfies (19). We store 2n+103×2-8=2n+95 remaining (b(7,13),x1,(7,13)SL) and its SN in table T(4) indexed by k0,(7,13).(7)
For currentk0,(1,4,5,7,11,13,14,15), guess k0,(6,12) and partially encrypt plaintext pairs in T(4), and then select plaintext pairs whose difference b(6,12) satisfies (20). We store 2n+95×2-8=2n+87 remaining (b(6,12),x1,(6,12)SL) and its SN in table T(5) indexed by k0,(6,12).(8)
For currentk0,(1,4,5,6,7,11,12,13,14,15), guess k0,(2,8) and partially encrypt plaintext pairs in T(5), and then select plaintext pairs whose difference b(2,8) satisfies (21). We store 2n+87×2-8=2n+79 remaining (b(2,8),x1,(2,8)SL) and its SN in table T(6) indexed by k0,(2,8).(9)
For currentk0,(1,2,4,5,6,7,8,11,12,13,14,15), we have known b(2),b(7),b(12),b(13), and then b(9) can be obtained from (22). The value of x1,(9)AK can be obtained by accessing the row in table Λ2. Compute P9⊕x1,(9)AK, and k0,(9) can be obtained. Store 2n+79×2-8=2n+71 remaining (b9,x1,(9)SL) and its SN in table T(7) indexed by k0,(9).(10)
For currentk0,(1,2,4,5,6,7,8,9,11,12,13,14,15), we have known b(1),b(5),b(9), and then b(3) can be obtained from (23). The value of x1,(3)AK can be obtained by accessing the row in table Λ4. Compute P3⊕x1,(3)AK, and k0,(3) can be obtained. Store 2n+71×2-8=2n+63 remaining (b3,x1,(3)SL) and its SN in table T(8) indexed by k0,(3).(11)
For currentk0′, (x2,(0,1,7,10,11,12)I,Δx2,(0,1,7,10,11,12)I) can be obtained by computing DL(x1,(1,2,3,4,5,6,7,8,9,11,12,13,14,15)SL). We choose the pairs whose 6-byte difference Δx2,(0,1,7,10,11,12)I is all nonzero. Guess Δx2,(0)SL and then obtain 6-byte difference Δx2,(0,1,7,10,11,12)SL. For each of these 6-byte differences, 6-byte values of x2,(0,1,7,10,11,12)AK can be obtained by accessing the row in corresponding table Λi. Compute x2,(0,1,7,10,11,12)I⊕x2,(0,1,7,10,11,12)AK and obtain k1′. We store 2n+63×28÷248=2n+23 SN in table T(9) indexed by 248 possible values of k1′.(12)
For current(k0′,k1′), guess 1-byte nonzero difference Δx7,(0)I and then obtain 4-byte difference Δx7,(0,4,13,15)I. From the cipher pairs, we can obtain Δx7,(0,4,13,15)SL. For each of these 4-byte differences, 4-byte values of x7,(0,4,13,15)SL can be obtained by accessing the row in corresponding table Λi. Compute x7,(0,4,13,15)SL⊕C2,(0,4,13,15) and obtain k7(1). We store candidate subkeys k7(1) in table C(1) indexed by k7,(0,4,13). For each k7,(0,4,13), if all k7,(15) are discarded, we conclude that the current (k0′,k1′,k7,(0,4,13)) cannot be right, so it is discarded.(13)
For current(k0′,k1′) and the remaining subkeys k7,(0,4,13) in table C(1), we use the second attack trail to sieve wrong subkeys and perform the following substeps.
(13.1)
For each plaintext pairs inΩ2, use the current (k0′,k1′) to select useful pairs whose differences are zero in all but 2 bytes at (7,13) after 2 rounds of ARIA encryptions (i.e., the input difference of distinguishers). Compute SL(Pi⊕k0,i) to satisfy (16)–(23) step by step. Then compute SL(x2,(0,1,7,10,11,12)AK) and choose the pairs which satisfy Property 3. The quantity of the remaining pairs is 2n+127×2-64×2-40=2n+23.(13.2)
The procedure of sieving wrong subkeys is similar to step(12). For each k7,(0,4,13), if all k7,(1) are wrong, the current (k0′,k1′,k7,(0,4,13)) cannot be right and is thus discarded. Otherwise, access the list with index k7,(0,4,13) in table C(1). If k7,(0,4,13) is also a candidate subkey in C(1), we store candidate subkeys k7,(0,1,4,13,15) in table C(2).(14)
For current(k0′,k1′) and the remaining subkeys k7,(0,1,4,13,15) in table C(2), we use the third attack trail to sieve wrong subkeys.
(14.1)
The procedure of choosing the expected pairs ofΩ3 is similar to step (13.1).(14.2)
For eachk7(3) in table C(2), if a k7(3) decrypts a ciphertext pairs to the impossible differential, then this corresponding subkey (k0′,k1′,k7,(0,1,4,13,15)) is wrong and is thus discarded. If all the remaining subkeys in table C(2) are wrong, the current subkey (k0′,k1′) is wrong, and then return to step (12) and check the next (k0′,k1′). Otherwise, store the remaining subkeys k7,(0,1,4,13,15) in table C(3).(15)
For current(k0′,k1′) and the remaining subkeys k7,(0,1,4,13,15) in table C(3), we use the fourth attack trail to sieve wrong subkeys.
(15.1)
The procedure of choosing expect pairs ofΩ4 is similar to step (13.1).(15.2)
For eachk7,(0,1,4) in table C(3), we need to guess one-byte subkey k7,(7). The procedure of sieving subkeys is similar to step (14.2). If all subkeys in C(3) are wrong, then return to step (12) and check the next (k0′,k1′), or store the remaining subkeys k7,(0,1,4,7,13,15) in table C(4).(16)
For currentk0′,k1′ and the remaining subkeys k7,(0,1,4,7,13,15) in table C(4), we use the fifth and the sixth attack trails (i=5,6) to sieve wrong subkeys.
(16.1)
The procedure of choosing the expected pairs ofΩi is similar to step (13.1).(16.2)
For eachk7,(0,1,4,7,13,15) in table C(4), the procedure of sieving wrong subkeys is similar to step (14.2). If all subkeys in C(4) are wrong, return to step (12) and check the next (k0′,k1′), or store the remaining subkeys k7,(0,1,4,7,13,15) in table C(5).(17)
Taking advantage of master key recovery algorithm, if the candidate subkey(k0′,k1′,k7,(0,1,4,7,13,15)) passes the check of the algorithm, we conclude that this subkey is right and recover the master key, or return to step (12) and check the next (k0′,k1′).


## 4.4. Complexity Analysis

The complexity in Precomputation Phase can be neglected compared with the complexity in online phase. The complexities of steps(2)–(10) are shown in Table 4.Table 4
The complexity of online phase.
Step Time complexity (7-round ARIA encryptions) Memory complexity (bytes) ( 2 ) 6 × 2 n × 2 112 log 2 ⁡ 2 112 × 1 16 × 1 7 = 2 n + 114.6 6 × 2 n + 127 × 2 × ( 4 + 14 ) ≈ 2 n + 134.7 ( 3 ) 2 × 2 n + 127 × 2 16 × 2 16 × 1 7 = 2 n + 138.2 2 n + 119 × 4 + n + 127 8 ( 4 ) 2 × 2 16 × 2 n + 119 × 2 16 × 2 16 × 1 7 = 2 n + 146.2 2 n + 111 × 4 + n + 127 8 ( 5 ) 2 × 2 32 × 2 n + 111 × 2 16 × 2 16 × 1 7 = 2 n + 154.2 2 n + 103 × 4 + n + 127 8 ( 6 ) 2 × 2 48 × 2 n + 103 × 2 16 × 2 16 × 1 7 = 2 n + 162.2 2 n + 95 × 4 + n + 127 8 ( 7 ) 2 × 2 64 × 2 n + 95 × 2 16 × 2 16 × 1 7 = 2 n + 170.2 2 n + 87 × 4 + n + 127 8 ( 8 ) 2 × 2 80 × 2 n + 87 × 2 16 × 2 16 × 1 7 = 2 n + 178.2 2 n + 79 × 4 + n + 127 8 ( 9 ) 2 96 × 2 n + 79 × 1 16 × 1 7 = 2 n + 168.2 2 n + 71 × 2 + n + 127 8 ( 10 ) 2 104 × 2 n + 71 × 1 16 × 1 7 = 2 n + 168.2 2 n + 63 × 2 + n + 127 8In step(11), the time complexity is 2112×2n+63×28×(1/16)×(1/7)=2n+176.2 7-round ARIA encryptions, and the memory demands 2n+23×(n+127)/8 bytes.Step(12) needs 2160×2n+23×28×(1/16)×(1/7)=2n+184.2 7-round ARIA encryptions.The time complexity of step(13) has the same value as step (12).Each wrong subkey is rejected by2n+23 pairs with a probability of P1=(1-2-24)2n+23. Step (14) just needs to cheek 240×(P1)2 subkeys in table C(2). Taking advantage of new early abort [9], the probability that a wrong subkey can pass 224d tests of pairs while rejecting 224(d+1) tests of pairs is pd=(1-2-24)224d-(1-2-24)224(d+1), and the mathematical expectation is E(d)=∑d=1∞dpd≈∑d=1∞d(e-d-e-(d+1))≈2-0.8. Thus, the time complexity of step (14) is 2160×240×(P1)2×224-0.8×(1/16)×(1/7)=2216.4×(P1)2 7-round ARIA encryptions.Step(15) just needs to check the remaining subkeys of C(3), so the time complexity is 2160×248×(P1)3×223.2×(1/16)×(1/7)=2224.4×(P1)3 7-round ARIA encryptions.Step(16) just needs to check the remaining subkeys of C(4), so the time complexity is 2160×248×(P1)4×223.2×(1/16)×(1/7)=2224.4×(P1)4 and 2224.4×(P1)5 7-round ARIA encryptions, respectively.The complexity of step(17) is detailed in Section 4.5


## 4.5. The Procedure of Recovering the Master Key for ARIA-192

In 2015, Akshima et al. [19] presented the master key recovery attacks on ARIA for the first time. Through the guess-and-determine technique, we present an efficient algorithm to recover the master key. Taking step (1) of the master key recovery algorithm as an example, if we guess 2128 values of W0 as proposed in [19], the time complexity is equal to 2128×(1/7)=2125.2 7-round ARIA encryptions. Based on guess-and-determine technique, the time complexity can be reduced to 276.5 7-round ARIA encryptions in this paper. For better understanding, we first describe the idea of master key recovery algorithm, and then the specific steps are specified.(1)
Attack2128 possible values for W0:
(a)
By[W0,k0,(1,2,3,4,5,6,7,8,9,11,12,13,14,15)] and (7), we can obtain 112 bits W1 whose 61 bits belong to the first eight bytes and other 51 bits belong to the last eight bytes.(b)
From the key schedule algorithm, we obtainKR(8,9,10,11,12,13,14,15)=0. According to (4), W1,(8,9,10,11,12,13,14,15) can be obtained by calculating F0(W0,CK1).(c)
Take advantage of the common 51 bits ofW1 to reject some wrong guesses of W0. We obtain 2128×2-51=277 remaining W0 and 125 bits of W1. Note that now we cannot obtain 61-th, 62-th, and 63-th bit of W1 and denote 125 bits of W1 as W1′.(2)
Attack the 61-th, 62-th, and 63-th bits ofW1:
(a)
By (8) and [W1′,k1,(0,1,7,10,11,12)], we obtain 48 bits of W2.(b)
By (5) and [W0,W1], we obtain W2.(c)
Take advantage of the common 48 bits ofW2 to obtain 280×2-48=232 remaining [W0,W1,W2].(3)
For each[W0,W1,W2],
(a)
by (6) and [W1,W2], we obtain W3;(b)
by (14) and [W0,k7,(0,1,4,7,13,15)], obtain 48 bits of W3,(c)
taking advantage of the common 48 bits ofW3, we can reject some wrong guesses. We obtain the remaining [W0,W1,W2, W3] and thus can recover the first seven subkeys [k0,…,k7] by calculating (7)–(14). Randomly select 210 plaintexts. If these corresponding ciphertexts can be obtained after 7-round ARIA encryptions, we judge that this subkey is right and recover the master key, or reject this candidate subkey and check the next.The details of step(1) are as follows.(1.1)
Guess 7-byteW0,(0,1,5,6,11,12,14), and W1,(9) can be obtained by calculating (4) and (7). So the retention rate is 2-8 and the quantity of W0,(0,1,5,6,11,12,14) is 248.(1.2)
Guess 2-byteW01=W0,(2⊕3⊕8⊕15), W0,(13), and W1,(10) can be obtained by calculating (4) and (7). So the retention rate is 2-8 and the quantity of [W0,(0,1,5,6,11,12,13,14),W01] is 256.(1.3)
Guess 1-byteW02=W0,(2⊕3⊕4⊕7⊕9), and W1,(11) can be obtained by calculating (4) and (7). So the retention rate is 2-8 and the quantity of [W0,(0,1,5,6,11,12,13,14),W01,W02] is 256.(1.4)
Guess 2-byteW03=W0,(4⊕8⊕10⊕15), W0,(2), and W1,(15) can be obtained by calculating (4) and (7). So the retention rate is 2-8 and the quantity of [W0,(0,1,2,5,6,11,12,13,14),W01,W02,W03] is 264.(1.5)
Guess 2-byteW04=W0,(7⊕9), W0,(15), and W1,(12) can be obtained by calculating (4) and (7). So the retention rate is 2-8 and the quantity of [W0,(0,1,2,5,6,10,11,12,13,14,15),W01,W02,W03,W04] is 272 (note that W0,(10)=W01⊕W02⊕W03⊕W04).(1.6)
Guess 1-byteW05=W0,(4⊕7), and 5-bit of W1,(8) can be obtained by calculating (4) and (7). So the retention rate is 2-5 and the quantity of [W0,(0,1,2,5,6,10,11,12,13,14,15),W01,W02,W03,W04, W05] is 275.(1.7)
Guess 1-byteW0,(3).By[W0,(0,1,2,3,5,6,10,11,12,13,14,15),W01,W02,W03, W04,W05], we can obtain 283W0. Six-bit W1,(13,14) can be obtained by calculating (4) and (7). So the retention rate is 2-6 and the quantity of W0 is 277.To sum up, the time complexity of steps(1.1)–(1.7) is 256,264,264,272,272,280,280, and 283, respectively. So the time complexity of step (1) is (283+2×280)×(1/16)×(1/7)≈276.5 7-round ARIA encryptions.The details of step(2) are as follows.(2.1)
We first sieve the277 remaining W0. According to [W1,(0,10,11,12),k1,(0,10,11,12)] and (8), we can obtain W2,(9,14). Then W2,(9,14) can be obtained by calculating (5). So the retention rate is 2-16 and the quantity of [W0,W1′] is 261.(2.2)
Guess 61-th, 62-th, and 63-th bits ofW1 and we can obtain W1. Then other 32-bit common W2 can be obtained, so the retention rate is 2-32 and the quantity of [W0,W1,W2] is 261+3×2-32=232.To sum up, the time complexity of step(2) is (277+264)×(1/16)×(1/7)≈270.2 7-round ARIA encryptions.The time complexity of step(3) is 232 1-round ARIA encryptions. Consequently, for a subkey (k0′,k1′,k7,(0,1,4,7,13,15)), our algorithm needs 276.5 7-round ARIA encryptions to recover the master key.


## 4.6. The Summary of Complexity

By the analysis in Sections4.4 and 4.5, we take n=4.6 and obtain P1=2-17.5.In step(16) of Section 4.4, the number of the remaining subkeys is ξ=2208×(2-17.5)6=2103, and this step demands ξ×276.5=2179.5 7-round ARIA encryptions.Consequently, our cryptanalysis demands2n+112=2116.6 chosen plaintexts. The memory complexity is dominated by step (2), which is 2n+134.7=2139.3 bytes. The time complexity is dominated by steps (12) and (13), which is 2×2n+184.2=2189.8 7-round ARIA encryptions.By attacking as many common subkey bytes as possible when using different attack trails, the efficient sieving process can improve the efficiency of sieving wrong subkey, so it helps to reduce the retention rate of wrong subkeys to2-17.5×6=2-105. Furthermore, based on one of these attack trails, we analyze the complexity with the same attack scenario, which need to take n=7.1, and the time, data, and memory complexities are 2191.3, 2119.1, and 2189.8, respectively. The comparison of the two complexities is shown in Table 5.Table 5
The comparison of two complexities of ARIA-192.
Attack type Time Data Memory Impossible differential attack with one attack trail 2 191.3 2 119.1 2 139.3 Impossible differential attack in Section4.3 2 189.8 2 116.6 2 139.3It is known from the comparison that the efficient sieving process can increase the efficiency of sieving subkeys, so the results are improved to an extent.


## 5. Conclusion

In this paper, we utilize an efficient sieving process, which can be applied to multiple impossible differentials attack. The efficient sieving process can reduce the retention rate of wrong subkeys; thus, both data complexity and time complexity can be reduced. Taking advantage of a series of techniques, we present multiple impossible differentials cryptanalysis on 7-round ARIA-192 and recover the master key, with the best result so far for impossible differential cryptanalysis of ARIA-192.



---

*Source: 7453572-2018-03-14.xml*