# New Linear Cryptanalysis of Chinese Commercial Block Cipher Standard SM4

Authors: Yu Liu; Huicong Liang; Wei Wang; Meiqin Wang
Journal: Security and Communication Networks
 (2017)

---

## Abstract

SM4 is a Chinese commercial block cipher standard used for wireless communication in China. In this paper, we use the partial linear approximation table of S-box to search for three rounds of iterative linear approximations of SM4, based on which the linear approximation for 20-round SM4 has been constructed. However, the best previous identified linear approximation only covers 19 rounds. At the same time, a linear approximation for 19-round SM4 is obtained, which is better than the known results. Furthermore, we show the key recovery attack on 24-round SM4 which is the best attack according to the number of rounds.


---

## Body

## 1. Introduction

SMS4 [1], issued in 2006 by Chinese government, serves the WAPI (WLAN Authentication and Privacy Infrastructure) as the underling block cipher for the security of wireless LANs. In 2012, SMS4 was announced as the Chinese commercial block cipher standard, renamed SM4 [2].SM4 receives more attention from the cryptographic community and a lot of cryptanalytic results for SM4 have been produced. In [3], the rectangle and boomerang attacks on 18-round SM4 and the linear and differential attacks on 22-round SM4 have been presented. Using multiple linear attack, Etrog and Robshaw gave an attack on 23-round SM4 in [4]. Besides these, the differential attack and the multiple linear attack on 22-round SM4 have been introduced in [5, 6]. Till now, the best differential attack for 23-round SM4 is given in [7]. Cho and Nyberg proposed a multidimensional linear attack on 23-round SM4 in [8]. The best linear attack on 23-round SM4 is provided by Liu and Chen in [9]. Bai and Wu proposed a new lookup-table-based white-box implementation for SM4 which could protect the large linear encodings from being cancelled out in [10]. Moreover, related-key differential attack on SM4 has been given in [11] and the lower bound of the number of linear active S-boxes for SMS4-like ciphers has been analyzed in [12].Linear cryptanalysis [13] is one of the most important techniques in the analysis of symmetric-key cryptographic primitives. The linear cryptanalysis focuses on the linear approximation between plaintext, ciphertext, and key. If a cipher behaves differently from a random permutation for linear cryptanalysis, this can be used to build a distinguisher or even a key recovery attack through adding some rounds. The subkeys of appended rounds are guessed and the ciphertexts are decrypted and/or plaintexts are encrypted using these subkeys to calculate intermediate state at the ends of distinguisher. If the subkeys are correctly guessed, then the distinguisher should hold. Otherwise, it will fail. Linear cryptanalysis has been used to analyze many ciphers such as [14–17].Our Contributions. In terms of the number of rounds that all the previous attacks for SM4 can work, the best key recovery attacks on SM4 are linear cryptanalysis and differential cryptanalysis, and both of them are based on 19-round distinguishers. Whether we can get a better distinguisher is our first motivation to improve the attacks on SM4. Therefore, we focus on searching the linear approximation for SM4 to improve the attacks on SM4. The contributions of this paper are summarized as follows.The best previous linear attacks work on the 19-round linear approximations. We design a new search algorithm for the iterative linear approximations for small rounds of SM4 by gradually expanding the partial linear approximation table of S-box. Firstly, it is proved that there is no one-round or two-round iterative linear approximation for SM4, and then some properties are obtained for the iterative linear approximations of 3-round SM4. Based on these properties, we utilize our searching algorithm to get an 19-round linear approximation with bias2-58 and a 20-round linear approximation with bias 2-61. The results about our identified linear approximations with the previous ones are depicted in Table 1. It can be seen that our linear approximations are the best ones so far.Table 1
Summary of linear approximations of SM4.
Rounds
Bias
Reference
19
2
-
62.27
[9]
19
2
-
58
Section3
20
2
-
61
Section3The best previous attacks can work on 23-round SM4. Utilizing our identified 20-round linear approximation of SM4, we give a key recovery attack on 24-round SM4, which is the best attack according to the number of rounds for SM4. Moreover, the new 19-round linear approximation is used to attack 23-round SM4. As a result, the best previous linear attack on 23-round SM4 is improved. A summary of our attacks and the previous attacks on SM4 is listed in Table2.Table 2
Summary of attacks on SM4.
Rounds
Attack type
Data
Time
Memory
Source
13
Integral
2
16
2
114
—
[6]
16
Impossible differential
2
107.9
2
87.7
2
107.9
[18]
18
Rectangle
2
124
2
112.8
2
128
[3]
18
Boomerang
2
120
2
116.8
2
123
[3]
22
Multiple linear
2
112
2
119.8
2
118.8
[19]
23
Differential
2
118
2
126.7
—
[7]
23
Multidimensional linear
2
122.6
2
122.7
2
120.6
[9]
23
Linear
2
126.5
2
122
2
116
[9]
23
Linear
2
120.3
2
121.7
2
85
Section4
24
Linear
2
126.6
2
126.6
2
85
Section4The paper is organized as follows. Section2 briefly describes the notations used in this paper and introduces the SM4 block cipher. Section 3 shows how to search the better linear approximations for SM4. In Section 4, we use the 19-round and 20-round linear approximations to attack 23-round and 24-round SM4, respectively. Section 5 concludes this paper.


## 2. Preliminaries

### 2.1. Notations

In this subsection, we will present the notations used in this paper as follows:(i)
⊕: a bitwise XOR operation(ii)
∥: concatenation of two words(iii)
⋘: left cyclic shift operation(iv)
∘: multiplication of two vectors, matrix and vector, or two matrices(v)
·: bitwise inner product(vi)
&&: logical AND operation(vii)
X[i]: the ith bit of X(viii)
X[i-j]: a bit string starting from the ith bit to the jth bit of X.


### 2.2. Brief Description of SM4

SM4 is a Chinese national standard block cipher used in WAPI for WLAN. It has 128-bit block size and the key size is also 128 bits. The design of SM4 is based on the unbalanced generalized Feistel structure and the number of rounds is 32. We denote the plaintext as(P0,P1,P2,P3)=(X00,X01,X02,X03)∈(F232)4, and the encryption procedure is described as follows:(1)Xr+13=Xr0⊕TXr1⊕Xr2⊕Xr3⊕kr=Xr0⊕L∘SXr1⊕Xr2⊕Xr3⊕kr,forr=0,…,31,where kr is the rth round’s subkey (0≤r≤31). The ciphertext (C0,C1,C2,C3)=(X323,X322,X321,X320). The decryption procedure is the same as the encryption procedure with the reverse order of subkeys.One round of SM4 is shown in Figure1. It can be known from Figure 1 that T is composed of the nonlinear layer S and the linear transformation L. Layer S has four 8×8 S-boxes used in parallel. The specification of the S-box could be referred to [1]. Let X∈F232 and Y∈F232 be the 32-bit input and output words of the linear transformation L. Then (2)Y=LX=X⊕X⋘2⊕X⋘10⊕X⋘18⊕X⋘24.Figure 1
The round function of SM4.The key schedule of SM4 is similar to the encryption procedure but the only difference between them is that the linear transformation in the key schedule is(3)L′X=X⊕X⋘13⊕X⋘23.The 128-bit master key (MK0,MK1,MK2,MK3) is first masked with the constants FK0,FK1,FK2,FK3 and then input to the key schedule function. (4)K0,K1,K2,K3=MK0⊕FK0,MK1⊕FK1,MK2⊕FK2,MK3⊕FK3,where FK0=0xa3b1bac6, FK1=0x56aa3350, FK3=0x677d9197, and FK3=0xb27022dc. And then kr is computed as follows: (5)kr=Kr+4=Kr⊕L′∘SKr+1⊕Kr+2⊕Kr+3⊕CKr,where CKr,r=0,1,…,31, is the constant.


## 2.1. Notations

In this subsection, we will present the notations used in this paper as follows:(i)
⊕: a bitwise XOR operation(ii)
∥: concatenation of two words(iii)
⋘: left cyclic shift operation(iv)
∘: multiplication of two vectors, matrix and vector, or two matrices(v)
·: bitwise inner product(vi)
&&: logical AND operation(vii)
X[i]: the ith bit of X(viii)
X[i-j]: a bit string starting from the ith bit to the jth bit of X.


## 2.2. Brief Description of SM4

SM4 is a Chinese national standard block cipher used in WAPI for WLAN. It has 128-bit block size and the key size is also 128 bits. The design of SM4 is based on the unbalanced generalized Feistel structure and the number of rounds is 32. We denote the plaintext as(P0,P1,P2,P3)=(X00,X01,X02,X03)∈(F232)4, and the encryption procedure is described as follows:(1)Xr+13=Xr0⊕TXr1⊕Xr2⊕Xr3⊕kr=Xr0⊕L∘SXr1⊕Xr2⊕Xr3⊕kr,forr=0,…,31,where kr is the rth round’s subkey (0≤r≤31). The ciphertext (C0,C1,C2,C3)=(X323,X322,X321,X320). The decryption procedure is the same as the encryption procedure with the reverse order of subkeys.One round of SM4 is shown in Figure1. It can be known from Figure 1 that T is composed of the nonlinear layer S and the linear transformation L. Layer S has four 8×8 S-boxes used in parallel. The specification of the S-box could be referred to [1]. Let X∈F232 and Y∈F232 be the 32-bit input and output words of the linear transformation L. Then (2)Y=LX=X⊕X⋘2⊕X⋘10⊕X⋘18⊕X⋘24.Figure 1
The round function of SM4.The key schedule of SM4 is similar to the encryption procedure but the only difference between them is that the linear transformation in the key schedule is(3)L′X=X⊕X⋘13⊕X⋘23.The 128-bit master key (MK0,MK1,MK2,MK3) is first masked with the constants FK0,FK1,FK2,FK3 and then input to the key schedule function. (4)K0,K1,K2,K3=MK0⊕FK0,MK1⊕FK1,MK2⊕FK2,MK3⊕FK3,where FK0=0xa3b1bac6, FK1=0x56aa3350, FK3=0x677d9197, and FK3=0xb27022dc. And then kr is computed as follows: (5)kr=Kr+4=Kr⊕L′∘SKr+1⊕Kr+2⊕Kr+3⊕CKr,where CKr,r=0,1,…,31, is the constant.


## 3. Search for the Linear Approximations of SM4

In terms of the number of rounds, all previous attacks for SM4 can work. One of the best key recovery attacks on SM4 is linear and differential cryptanalysis, and both of them are based on 19-round distinguishers. Whether we can get a better distinguisher is our first motivation to improve the attacks on SM4. Therefore, the key point is to search for the linear approximation of SM4. As far as we know, some methods to search for linear approximations of SM4 have been considered in [3, 4, 9, 19].The search method in [3] is to construct linear approximations for reduced-round SM4 by identifying a one-round linear approximation with the same input and output masks for the T function. In this way, the number of active T functions can be minimized. As a result, an 18-round linear approximation with bias 2-57.28 for SM4 has been found.In [4], Etrog and Robshaw derived a 5-round iterative linear approximation where only the last two rounds are active, and then they concatenated three five-round iterative linear approximations to construct an 18-round linear approximation with bias 2-56.2.In [19], Liu et al. used the branch-and-bound algorithm in [20] to obtain a series of 5-round iterative linear approximations, which are utilized to construct an 18-round linear approximation with bias 2-56.14.In order to get a better linear approximation for SM4, Liu and Chen gave a more dedicated search algorithm in [9]. They firstly used an MILP-based method to search the mode for the linear approximation with the minimum number of active S-boxes for reduced-round SM4; then based on the identified mode they found the 19-round linear approximation with bias 2-62.27.It is obvious that even if the number of active S-boxes for a linear approximation is minimized, the absolute of its bias might not be maximum. From this point, we focus on searching for better linear approximations with a few more active S-boxes.At CT-RSA 2014, Biryukov and Velichkov extended the branch-and-bound algorithm to search for the differential characteristics of ARX ciphers where the partial differential distribution table for modular addition is used in order to improve the search efficiency [21]. Inspired from this idea, we will use the partial linear approximation table to search for linear approximations of SM4.At first, some properties for basic operations such as the XOR operation, the three-forked branching operation, and the linear map will be introduced.Lemma 1 (XOR operation [22]).
Letf(x0,x1)=x0⊕x1; the input mask vector and output mask are Γ=(Γ0,Γ1) and Λ, respectively. Then Pr⁡(Λ·f(x0,x1)=Γ0·x0⊕Γ1·x1)≠1/2 if and only if Γ0=Γ1=Λ.Lemma 2 (three-forked branching operation [22]).
Letf(x)=(x,x); the input mask and output linear mask vector are Γ and Λ=(Λ0,Λ1), respectively. Then Pr⁡(Γ·x=Λ·f(x))≠1/2 if and only if Γ=Λ0⊕Λ1.Lemma 3 (linear map [23]).
Letf(x)=M∘x with the input mask vector Γ=(Γ0,Γ1,…,Γn-1) and output mask vector Λ=(Λ0,Λ1,…,Λn-1); then Pr⁡(Γ·x=Λ·f(x))≠1/2 if and only if   Γ=MT∘Λ, where MT is the transposed matrix of M and M is an n×n invertible binary matrix.Biases in the linear approximation table for S-box of SM4 take the valuesl/28(2≤l≤16). If we put all the linear approximation table into the search program, the program will be too slow to get a better linear approximation. Thus, the partial linear approximation table is used in the search algorithm. The basic idea is that linear approximations of S-box with higher bias are utilized first. If no better linear approximation is output, then we can expand the partial linear approximation table by appending more linear approximations of S-box with less bias successively till a better linear approximation is output.In order to get a better linear approximation, one common method is to find iterative linear approximations for short rounds first based on which long rounds of linear approximations could be produced directly. Thus, we will focus on searching for iterative linear approximations of SM4.Now three properties for iterative linear approximations of SM4 are shown as follows.Property 4.
There is no one-round iterative linear approximation with active S-boxes on SM4.Proof.
From Figure2, if there is an iterative linear approximation for the first round, we have(6)Γr0=Γr+10,Γr1=Γr+11,Γr2=Γr+12,Γr3=Γr0.Using the property of three-forked branch, we have(7)Γr1=Γr+10⊕Γr,Γr2=Γr+11⊕Γr,Γr3=Γr+12⊕Γr.From (6) and (7), we get (8)Γr+11=Γr0⊕Γr,Γr0⊕Γr⊕Γr=Γr+12,Γr3=Γr0⊕Γr⊕Γr⊕Γr=Γr0⊕Γr=Γr0,which implies Γr=0 and all the S-boxes in this round are passive. Thus, there is no one-round iterative linear approximation for SM4.Figure 2
Linear approximation of 3-round SM4.Property 5.
The iterative linear approximation for two rounds of SM4 does not exist.Proof.
If there is an iterative linear approximation for the first two rounds in Figure2, then we have(9)Γr0=Γr+20,Γr1=Γr+21,Γr2=Γr+22,Γr3=Γr+10.With the property of three-forked branch, we have(10)Γr1=Γr+10⊕Γr,Γr2=Γr+20⊕Γr⊕Γr+1,Γr3=Γr+21⊕Γr⊕Γr+1,Γr+22=Γr0⊕Γr+1.According to (9) and (10), we derive (11)Γr2=Γr0⊕Γr⊕Γr+1,Γr3=Γr1⊕Γr⊕Γr+1,Γr2=Γr0⊕Γr+1.Thus, (12)Γr0⊕Γr+1=Γr0⊕Γr⊕Γr+1⟹Γr=0,which means that Γr0=Γr+20=0. Substitute the terms Γr in the above formulas and we have (13)Γr1=Γr+10=Γr+21,Γr2=Γr+1,Γr3=Γr+21⊕Γr+1=Γr+10⊕Γr+1=Γr+10,so Γr+1=0, which means that all S-boxes in the first two rounds are passive. Therefore, 2-round iterative linear approximation for SM4 does not exist.Property 6.
For the iterative linear approximation of 3-round SM4, the minimum number of active S-boxes is 3. Meanwhile, each round has one active S-box and the active S-boxes are located in the same positions of three rounds.Proof.
If there is an iterative linear approximation for three rounds in Figure2, then we have(14)Γr1⊕Γr⊕Γr+2=Γr2,Γr3=Γr2⊕Γr⊕Γr+1,Γr3⊕Γr⊕Γr+1⊕Γr+2=Γr0,Γr0⊕Γr+1⊕Γr+2=Γr1.So(15)Γr+1=Γr⊕Γr+2,Γr0=Γr3.We focus on the linear approximation with less active S-boxes. From (15), it is impossible for a three-round iterative linear approximation to have only one active S-box. If there are two active S-boxes, then Γr=0 or Γr+1=0 or Γr+2=0. Hence, all S-boxes in the three-round linear approximation are passive. Take Γr=0 as an example.
IfΓr=0, then Λr=0, which implies Γr0=0. Then (16)Γr3=Γr+30=Γr+33=Γr0=0,∵Γr+20=Γr+33∴Γr+20=0.Thus, Λr+2=0; we have Γr+2=0. (17)0=Γr3⊕Γr=Γr+12=Γr+1⊕Γr+21=Γr+1⊕Γr+2⊕Γr+30=Γr+1.
In the casesΓr+1=0 and Γr+2=0, we can also obtain that there is no active S-box in the three-round linear approximation by the similar way of the case Γr=0. Therefore, the iterative linear approximation for three-round SM4 has at least three active S-boxes. From (15), it is clear that each round has one active S-box and these active S-boxes are located in the same positions of three rounds.From Property6, we will try to search for the iterative linear approximation of 3-round SM4 where each round has only one active S-box. The search algorithm is listed in Algorithm 1. In Algorithm 1, the following notations are used. Γr=Γr,0∥Γr,1∥Γr,2∥Γr,3 and Λr=Λr,0∥Λr,1∥Λr,2∥Λr,3 are input and output masks of S-layer in the rth round. Γr,j and Λr,j are input and output mask of the jth S-box of the rth round. Tl is a partial linear approximation table of S-box which consists of linear approximations with bias no less than l/28(2≤l≤16).Algorithm 1:Search algorithm for iterative linear approximation of 3-round SM4.
(
1
)  for  l←16 to 2  do
(
2
)  for  j←0 to 3  do
(
3
)    for all Λ0,j≠0,Λ1,j≠0,Λ2,j≠0,Λ0,j′=Λ1,j′=Λ2,j′=0,(0≤j′≠j≤3)  do
(
4
)      Γ0,j′=Γ1,j′=Γ2,j′=0,(0≤j′≠j≤3)
(
5
)      find all m0 input masks indexed by Λ0,j from Tl, and store in Rj[m0]
(
6
)      for  k0←0 to m0-1  do
(
7
)        Γ0,j←Rj[k0]
(
8
)       find all m1 input masks indexed by Λ1,j from Tl, and store in Rj[m1]
(
9
)       for  k1←0 to m1-1  do
(
10
)         Γ1,j←Rj[k1]
(
11
)         find all m2 input masks indexed by Λ2,j from Tl, and store in Rj[m2]
(
12
)         for  k2←0 to m2-1  do
(
13
)           Γ2,j←Rj[k2]
(
14
)           for  i←0 to 2  do
(
15
)             Γi0=LT∘(Λi,0∥Λi,1∥Λi,2∥Λi,3)=LT∘(Λi)
(
16
)           end for
(
17
)           for  i←0 to 2  do
(
18
)             Γi=Γi,0∥Γi,1∥Γi,2∥Γi,3
(
19
)           end for
(
20
)           Γ30=Γ00
(
21
)           Γ31=Γ00⊕Γ1⊕Γ2
(
22
)           Γ32=Γ10⊕Γ2
(
23
)           Γ03=Γ00⊕Γ0⊕Γ1⊕Γ2
(
24
)           Γ01=Γ10⊕Γ0
(
25
)           Γ02=Γ20⊕Γ0⊕Γ1
(
26
)           if  Γ03=Γ20&&Γ01=Γ31&&Γ02=Γ32  then
(
27
)             return  Γ00,Γ10,Γ20,Γ30,Γ0,Γ1,Γ2
(
28
)             // 3-round iterative linear approximation
(
29
)           else
(
30
)             continue.
(
31
)           end if
(
32
)        end for
(
33
)       end for
(
34
)     end for
(
35
)   end for
(
36
)  end for
(
37
)   l=l-2
(
38
) end forAfter proceeding the search algorithm, we identify 12240 3-round iterative linear approximations with bias2-10. With any 3-round iterative linear approximation, we can construct linear approximations for 19-round and 20-round SM4 with bias 2-58 and 2-61, respectively. Compared with the best previous 19-round linear approximation in [9], the bias has been improved from 2-62.27 to 2-58. In Tables 3 and 4, we give linear approximations for 19-round and 20-round SM4, respectively, where all masks are denoted as hexadecimal values and “∗” is undecided.Table 3
Linear approximation for 19-round SM4.
Round
i
Γ
i
0
Λ
i
Γ
i
Bias
Γ
i
1
Γ
i
2
Γ
i
3
1
0
028
A
0828
002
A
0000
00950000
2
-
4
021
F
0828
028
B
0828
028
A
0828
2
1
028
A
0828
002
A
0000
00940000
2
-
4
021
E
0828
021
F
0828
028
A
0828
3
2
028
A
0828
002
A
0000
00010000
2
-
4
028
B
0828
021
E
0828
028
A
0828
4
3
028
A
0828
002
A
0000
00950000
2
-
4
021
F
0828
028
B
0828
028
A
0828
5
4
028
A
0828
002
A
0000
00940000
2
-
4
021
E
0828
021
F
0828
028
A
0828
6
5
028
A
0828
002
A
0000
00010000
2
-
4
028
B
0828
021
E
0828
028
A
0828
7
6
028
A
0828
002
A
0000
00950000
2
-
4
021
F
0828
028
B
0828
028
A
0828
8
7
028
A
0828
002
A
0000
00940000
2
-
4
021
E
0828
021
F
0828
028
A
0828
9
8
028
A
0828
002
A
0000
00010000
2
-
4
028
B
0828
021
E
0828
028
A
0828
10
9
028
A
0828
002
A
0000
00950000
2
-
4
021
F
0828
028
B
0828
028
A
0828
11
10
028
A
0828
002
A
0000
00940000
2
-
4
021
E
0828
021
F
0828
028
A
0828
12
11
028
A
0828
002
A
0000
00010000
2
-
4
028
B
0828
021
E
0828
028
A
0828
13
12
028
A
0828
002
A
0000
00950000
2
-
4
021
F
0828
028
B
0828
028
A
0828
14
13
028
A
0828
002
A
0000
00940000
2
-
4
021
E
0828
021
F
0828
028
A
0828
15
14
028
A
0828
002
A
0000
00010000
2
-
4
028
B
0828
021
E
0828
028
A
0828
16
15
028
A
0828
002
A
0000
00950000
2
-
4
021
F
0828
028
B
0828
028
A
0828
17
16
028
A
0828
002
A
0000
00940000
2
-
4
021
E
0828
021
F
0828
028
A
0828
18
17
028
A
0828
002
A
0000
00010000
2
-
4
028
B
0828
021
E
0828
028
A
0828
19
18
028
A
0828
002
A
0000
00950000
2
-
4
021
F
0828
028
B
0828
028
A
0828
20
19
028
A
0828
002
A
0000
∗
∗
021
E
0828
021
F
0828
028
A
0828Table 4
Linear approximation for 20-round SM4.
Round
i
Γ
i
0
Λ
i
Γ
i
Bias
Γ
i
1
Γ
i
2
Γ
i
3
1
0
8808
A
228
00008200
00006000
2
-
4
8808
C
228
88080828
8808
A
228
2
1
8808
A
228
00008200
0000
C
A
00
2
-
4
88086828
8808
C
228
8808
A
228
3
2
8808
A
228
00008200
0000
A
A
00
2
-
4
88080828
88086828
8808
A
228
4
3
8808
A
228
00008200
00006000
2
-
4
8808
C
228
88080828
8808
A
228
5
4
8808
A
228
00008200
0000
C
A
00
2
-
4
88086828
8808
C
228
8808
A
228
6
5
8808
A
228
00008200
0000
A
A
00
2
-
4
88080828
88086828
8808
A
228
7
6
8808
A
228
00008200
00006000
2
-
4
8808
C
228
88080828
8808
A
228
8
7
8808
A
228
00008200
0000
C
A
00
2
-
4
88086828
8808
C
228
8808
A
228
9
8
8808
A
228
00008200
0000
A
A
00
2
-
4
88080828
88086828
8808
A
228
10
9
8808
A
228
00008200
00006000
2
-
4
8808
C
228
88080828
8808
A
228
11
10
8808
A
228
00008200
0000
C
A
00
2
-
4
88086828
8808
C
228
8808
A
228
12
11
8808
A
228
00008200
0000
A
A
00
2
-
4
88080828
88086828
8808
A
228
13
12
8808
A
228
00008200
00006000
2
-
4
8808
C
228
88080828
8808
A
228
14
13
8808
A
228
00008200
0000
C
A
00
2
-
4
88086828
8808
C
228
8808
A
228
15
14
8808
A
228
00008200
0000
A
A
00
2
-
4
88080828
88086828
8808
A
228
16
15
8808
A
228
00008200
00006000
2
-
4
8808
C
228
88080828
8808
A
228
17
16
8808
A
228
00008200
0000
C
A
00
2
-
4
88086828
8808
C
228
8808
A
228
18
17
8808
A
228
00008200
0000
A
A
00
2
-
4
88080828
88086828
8808
A
228
19
18
8808
A
228
00008200
00006000
2
-
4
8808
C
228
88080828
8808
A
228
20
19
8808
A
228
00008200
0000
C
A
00
2
-
4
88086828
8808
C
228
8808
A
228
21
20
8808
A
228
00008200
∗
∗
88080828
88086828
8808
A
228


## 4. Key Recovery Attacks for SM4

### 4.1. Linear Attack on 24-Round SM4

We append two rounds to the bottom and the top of the 20-round linear approximation in Table4, respectively. Then a linear attack on 24-round SM4 is presented. The partial sum technique [24] is used in the partial encryption and decryption procedures. See Figure 3.Figure 3
Key recovery attack on 24-round SM4.According to the linear approximation in Figure3, we denote Γ20=Γ23=Γ220=Γ223=0x8808A228, Γ21=0x8808C228, Γ22=Γ221=0x88080828, Γ222=0x88086828, Λ1=Λ22=0x00008200, and Λ1,2=Λ22,2=0x82. From the linear approximation, we have (18)Γ20·X20⊕Γ21·X21⊕Γ22·X22⊕Γ23·X23⊕Γ220·X220⊕Γ221·X221⊕Γ222·X222⊕Γ223·X223=κ.Consider the partial encryption and decryption; the left side of the above equation can be written as follows:(19)Γ20·P2⊕Γ21·P3⊕Γ22·P0⊕XX0⊕Γ20·P1⊕XX1⊕Γ20·C2⊕XX22⊕Γ22·C3⊕XX23⊕Γ222·C0⊕Γ20·C1=Γ20·P2⊕Γ21·P3⊕Γ22·P0⊕Γ20·P1⊕Γ20·C2⊕Γ22·C3⊕Γ222·C0⊕Γ20·C1⊕Γ22·XX0⊕Γ20·XX1⊕Γ20·XX22⊕Γ22·XX23,where XXr is the state after transformation T and XSr is the state after layer S in the rth round.Since(20)Γ20·XX22=Λ22·XS22=Λ22,2·XS2216–23=Λ1,2·SX221⊕X222⊕X223⊕k2216–23=Λ1,2·SC3⊕C0⊕C116–23⊕XX2316–23⊕k2216–23,Γ20·XX1=Λ1·XS1=Λ1,2·XS116–23=Λ1,2·SX11⊕X12⊕X13⊕k116–23=Λ1,2·SP0⊕P2⊕P316–23⊕XX016–23⊕k116–23,then, (19) can be transformed into (21)Γ20·P2⊕Γ21·P3⊕Γ22·P0⊕Γ20·P1⊕Γ20·C2⊕Γ22·C3⊕Γ222·C0⊕Γ20·C1⊕Γ22·TP1⊕P2⊕P3⊕k0⊕Λ1,2·SP0⊕P2⊕P316–23⊕XX016–23⊕k116–23⊕Λ1,2·SC3⊕C0⊕C116–23⊕XX2316–23⊕k2216–23⊕Γ22·TC0⊕C1⊕C2⊕k23.LetO=Γ20·P2⊕Γ21·P3⊕Γ22·P0⊕Γ20·P1⊕Γ20·C2⊕Γ22·C3⊕Γ222·C0⊕Γ20·C1. The attack process is given as follows:(1)
CollectN plaintext/ciphertext pairs.(2)
Initialize281 counters V0[0],…,V0[281–1] to zero.(3)
For every plaintext/ciphertext pair, calculatew=O∥(P0⊕P2⊕P3)[16–23]∥(C3⊕C0⊕C1)[16–23]∥C0⊕C1⊕C2∥P1⊕P2⊕P3. Then increase the counter V0[w] by one.(4)
Guess the32-bit k23. Allocate 249 counters V1[0],…,V1[249–1] to zero.(5)
For every0≤w≤281–1, calculate O⇐O⊕Γ22·T(C0⊕C1⊕C2⊕k23), XX23 and x=O∥(P0⊕P2⊕P3)[16–23]∥(C3⊕C0⊕C1)[16–23]⊕XX23[16–23]∥P1⊕P2⊕P3. V1x+=V0[w].(6)
Guess the 8-bitk22[16–23]. Allocate 241 counters V2[0],…,V2[241–1] to zero.(7)
For every0≤x≤249–1, calculate O⇐O⊕Λ1,2·SC3⊕C0⊕C116–23⊕XX2316–23⊕k2216–23 and y=O∥(P0⊕P2⊕P3)[16–23]∥P1⊕P2⊕P3. V2[y]+=V1[x].(8)
Guess the32-bit k0. Allocate 29 counters V3[0],…,V3[29–1] to zero.(9)
For every0≤y≤241–1, calculate O⇐O⊕Γ22·T(P1⊕P2⊕P3⊕k0), XX0 and z=O∥(P0⊕P2⊕P3)[16–23]⊕XX0[16–23]. V3[z]+=V2[y].(10)
Guess the8-bit k1[16–23]. Initialize 280 counters Vkey[0],…,Vkey[280–1] to zero.(11)
For every0≤z≤29–1, calculate O⇐O⊕Λ1,2·S((P0⊕P2⊕P3)[16–23]⊕XX0[16–23]⊕k1[16–23]). If O=0, increase the counter Vkey[k0∥k1[16–23]∥k22[16–23]∥k23] by V3[z]; otherwise, decrease it by V3[z].(12)
We set the advantagea to be 47 which implies that the top 233 absolute values in Vkey are kept. For each kept subkey value, we guess the remaining 88 bits of k1[0–15,24–31]∥k2∥k3 (the master key can be gotten from the key schedule) and test the key by trail encryptions.The time complexity of Step(3) is about 2126.6 operations which is equivalent to 2126.6/24=2122.0 24-round encryptions. Both Steps (5) and (9) need 2113 one-round decryptions or encryptions. Steps (7) and (11) take 289 one-round decryptions or encryptions. The complexity of Step (12) is 2121 24-round encryptions. So the total time complexity is about 2122.6 encryptions.The memory complexity of Step(2) is about 281×8=284 bytes and the counter Vkey requires 280×16=284 bytes, so the total memory complexity is about 284+284=285 bytes.If we set the data complexityN=2126.6, the success rate PS=Φ(2N|ϵ|-1+N/2nΦ-1(1-2-a-1))=76.1% by [25]. The time complexity is 2126.6 24-round encryptions.


### 4.2. Linear Attack on 23-Round SM4

Two rounds are added to the bottom and the top of the 19-round linear approximation in Table3, respectively. The key recovery attack on 23-round SM4 is similar to the attack procedure of 24-round SM4, so we omit details of the process.If we set the data complexityN=2120.3 and the advantage a to be 47, the time complexity is 2120.3+2121=2121.7 23-round encryptions, and the memory complexity is 285 bytes. The success rate PS=85.9% is computed with the method in [25].


## 4.1. Linear Attack on 24-Round SM4

We append two rounds to the bottom and the top of the 20-round linear approximation in Table4, respectively. Then a linear attack on 24-round SM4 is presented. The partial sum technique [24] is used in the partial encryption and decryption procedures. See Figure 3.Figure 3
Key recovery attack on 24-round SM4.According to the linear approximation in Figure3, we denote Γ20=Γ23=Γ220=Γ223=0x8808A228, Γ21=0x8808C228, Γ22=Γ221=0x88080828, Γ222=0x88086828, Λ1=Λ22=0x00008200, and Λ1,2=Λ22,2=0x82. From the linear approximation, we have (18)Γ20·X20⊕Γ21·X21⊕Γ22·X22⊕Γ23·X23⊕Γ220·X220⊕Γ221·X221⊕Γ222·X222⊕Γ223·X223=κ.Consider the partial encryption and decryption; the left side of the above equation can be written as follows:(19)Γ20·P2⊕Γ21·P3⊕Γ22·P0⊕XX0⊕Γ20·P1⊕XX1⊕Γ20·C2⊕XX22⊕Γ22·C3⊕XX23⊕Γ222·C0⊕Γ20·C1=Γ20·P2⊕Γ21·P3⊕Γ22·P0⊕Γ20·P1⊕Γ20·C2⊕Γ22·C3⊕Γ222·C0⊕Γ20·C1⊕Γ22·XX0⊕Γ20·XX1⊕Γ20·XX22⊕Γ22·XX23,where XXr is the state after transformation T and XSr is the state after layer S in the rth round.Since(20)Γ20·XX22=Λ22·XS22=Λ22,2·XS2216–23=Λ1,2·SX221⊕X222⊕X223⊕k2216–23=Λ1,2·SC3⊕C0⊕C116–23⊕XX2316–23⊕k2216–23,Γ20·XX1=Λ1·XS1=Λ1,2·XS116–23=Λ1,2·SX11⊕X12⊕X13⊕k116–23=Λ1,2·SP0⊕P2⊕P316–23⊕XX016–23⊕k116–23,then, (19) can be transformed into (21)Γ20·P2⊕Γ21·P3⊕Γ22·P0⊕Γ20·P1⊕Γ20·C2⊕Γ22·C3⊕Γ222·C0⊕Γ20·C1⊕Γ22·TP1⊕P2⊕P3⊕k0⊕Λ1,2·SP0⊕P2⊕P316–23⊕XX016–23⊕k116–23⊕Λ1,2·SC3⊕C0⊕C116–23⊕XX2316–23⊕k2216–23⊕Γ22·TC0⊕C1⊕C2⊕k23.LetO=Γ20·P2⊕Γ21·P3⊕Γ22·P0⊕Γ20·P1⊕Γ20·C2⊕Γ22·C3⊕Γ222·C0⊕Γ20·C1. The attack process is given as follows:(1)
CollectN plaintext/ciphertext pairs.(2)
Initialize281 counters V0[0],…,V0[281–1] to zero.(3)
For every plaintext/ciphertext pair, calculatew=O∥(P0⊕P2⊕P3)[16–23]∥(C3⊕C0⊕C1)[16–23]∥C0⊕C1⊕C2∥P1⊕P2⊕P3. Then increase the counter V0[w] by one.(4)
Guess the32-bit k23. Allocate 249 counters V1[0],…,V1[249–1] to zero.(5)
For every0≤w≤281–1, calculate O⇐O⊕Γ22·T(C0⊕C1⊕C2⊕k23), XX23 and x=O∥(P0⊕P2⊕P3)[16–23]∥(C3⊕C0⊕C1)[16–23]⊕XX23[16–23]∥P1⊕P2⊕P3. V1x+=V0[w].(6)
Guess the 8-bitk22[16–23]. Allocate 241 counters V2[0],…,V2[241–1] to zero.(7)
For every0≤x≤249–1, calculate O⇐O⊕Λ1,2·SC3⊕C0⊕C116–23⊕XX2316–23⊕k2216–23 and y=O∥(P0⊕P2⊕P3)[16–23]∥P1⊕P2⊕P3. V2[y]+=V1[x].(8)
Guess the32-bit k0. Allocate 29 counters V3[0],…,V3[29–1] to zero.(9)
For every0≤y≤241–1, calculate O⇐O⊕Γ22·T(P1⊕P2⊕P3⊕k0), XX0 and z=O∥(P0⊕P2⊕P3)[16–23]⊕XX0[16–23]. V3[z]+=V2[y].(10)
Guess the8-bit k1[16–23]. Initialize 280 counters Vkey[0],…,Vkey[280–1] to zero.(11)
For every0≤z≤29–1, calculate O⇐O⊕Λ1,2·S((P0⊕P2⊕P3)[16–23]⊕XX0[16–23]⊕k1[16–23]). If O=0, increase the counter Vkey[k0∥k1[16–23]∥k22[16–23]∥k23] by V3[z]; otherwise, decrease it by V3[z].(12)
We set the advantagea to be 47 which implies that the top 233 absolute values in Vkey are kept. For each kept subkey value, we guess the remaining 88 bits of k1[0–15,24–31]∥k2∥k3 (the master key can be gotten from the key schedule) and test the key by trail encryptions.The time complexity of Step(3) is about 2126.6 operations which is equivalent to 2126.6/24=2122.0 24-round encryptions. Both Steps (5) and (9) need 2113 one-round decryptions or encryptions. Steps (7) and (11) take 289 one-round decryptions or encryptions. The complexity of Step (12) is 2121 24-round encryptions. So the total time complexity is about 2122.6 encryptions.The memory complexity of Step(2) is about 281×8=284 bytes and the counter Vkey requires 280×16=284 bytes, so the total memory complexity is about 284+284=285 bytes.If we set the data complexityN=2126.6, the success rate PS=Φ(2N|ϵ|-1+N/2nΦ-1(1-2-a-1))=76.1% by [25]. The time complexity is 2126.6 24-round encryptions.


## 4.2. Linear Attack on 23-Round SM4

Two rounds are added to the bottom and the top of the 19-round linear approximation in Table3, respectively. The key recovery attack on 23-round SM4 is similar to the attack procedure of 24-round SM4, so we omit details of the process.If we set the data complexityN=2120.3 and the advantage a to be 47, the time complexity is 2120.3+2121=2121.7 23-round encryptions, and the memory complexity is 285 bytes. The success rate PS=85.9% is computed with the method in [25].


## 5. Conclusions

In this paper, it is firstly shown that there is no one-round or two-round iterative linear approximation for SM4 and the property for the 3-round iterative linear approximation. On the basis of the property, we search for the iterative linear approximation of 3-round SM4 by the partial linear approximation table. Next the 20-round linear approximation is constructed by 3-round iterative linear approximations. The best previous distinguishers only cover 19 rounds. Then the key recovery attack on 24-round SM4 is provided, which is the best known attack on SM4 so far. Moreover, we also get a better 19-round linear approximation, used to improve the linear attack on 23-round SM4. As for future work, we hope to use the similar technique to search for a better differential characteristic for SM4.



---

*Source: 1461520-2017-09-06.xml*