# Improved Integral Attacks on SIMON32 and SIMON48 with Dynamic Key-Guessing Techniques

Authors: Zhihui Chu; Huaifeng Chen; Xiaoyun Wang; Xiaoyang Dong; Lu Li
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Dynamic key-guessing techniques, which exploit the property of AND operation, could improve the differential and linear cryptanalytic results by reducing the number of guessed subkey bits and lead to good cryptanalytic results for SIMON. They have only been applied in differential and linear attacks as far as we know. In this paper, dynamic key-guessing techniques are first introduced in integral cryptanalysis. According to the features of integral cryptanalysis, we extend dynamic key-guessing techniques and get better integral cryptanalysis results than before. As a result, we present integral attacks on 24-round SIMON32, 24-round SIMON48/72, and 25-round SIMON48/96. In terms of the number of attacked rounds, our attack on SIMON32 is better than any previously known attacks, and our attacks on SIMON48 are the same as the best attacks.


---

## Body

## 1. Introduction

The integral attack, proposed by Daemen et al. [1], is an important cryptanalytic technique for symmetric-key primitives. The integral distinguisher is based on the property that when some parts of the input (constant bits) of distinguishers are held constant whereas the other parts (active bits) vary through all possibilities, the sum of all the output values equals zero at some particular locations (balanced bits). In the key recovery, the sum is random if the guessed key is incorrect, while the sum is zero if the guessed key is correct. As a powerful class of cryptanalytic techniques, integral cryptanalysis has been applied to many block ciphers, especially the ones with low-degree round functions.SIMON is a family of ten lightweight block ciphers designed by the US National Security Agency [2]. The SIMON2n/mn family of lightweight block ciphers have classical Feistel structures with 2n-bit block size and mn-bit key, where n is the word size.SIMON has been extensively scrutinized [3–25]. As an ultralightweight primitive, SIMON is a very good target for integral cryptanalysis. In integral cryptanalysis, Wang et al. [21] experimentally found an integral distinguisher for 14 rounds of SIMON32 and mounted a key-recovery attack on 21-round SIMON32. At EUROCRYPT 2015, Todo proposed the division property [17], which is a generalized integral property. This new technique enables the cryptographers to propagate the integral property in a more precise manner. As a result, an 11-round integral distinguisher of SIMON48 was found. Subsequently, using the bit-based division property, Todo and Morii proved the 14-round distinguisher of SIMON32 theoretically in [18]. However, searching integral characteristics by the bit-based division property requires much time and memory complexity. In order to overcome the problem, Xiang et al. [23] proposed a state partition to achieve a trade-off between the accuracy of the integral distinguisher and the time-memory complexity. Accordingly, Todo’s result was improved by one round for SIMON48. Afterwards, MILP method was applied by Xiang et al. [22] to find integral characteristics of some lightweight block ciphers, including a 15-round integral distinguisher for SIMON48. At ACNS 2016, some integral distinguishers of SIMON-like ciphers were constructed by Kondo et al. [10]. However, the block size considered is only 32 bits. Later in [7], with the equivalent-subkey technique, Fu et al. presented integral attacks on 22-round SIMON32, 22-round SIMON48/72, and 23-round SIMON48/96. Good results [6, 13, 20] were achieved in differential and linear cryptanalysis, as well. The cryptanalytic results that attack the most rounds of SIMON were obtained in [6], and these results were achieved by linear hull cryptanalysis. The most efficient differential and linear attacks on SIMON were presented with the help of dynamic key-guessing techniques.With regard to dynamic key-guessing techniques, they were initially proposed to improve the differential attacks on SIMON [20]. The techniques, which exploit the property of AND operation, help reduce the average number of guessed key bits significantly in differential cryptanalysis. Then they were applied to linear hull attacks on SIMON [6]. In both [6, 20], with the techniques above, the adversaries are able to extend previous differential (resp., linear hull) results on SIMON by 2 to 4 more rounds, using existing differential (resp., linear hull) distinguishers. Subsequently, Qiao et al. [13] released a tool, which provides the differential security evaluation of SIMON given differential distinguishers of high probability. Moreover, with newly proposed differentials [9], Qiao et al. improved differential attacks against SIMON, using the techniques. Also in the differential cryptanalysis and linear cryptanalysis of Simeck [26], good results [13, 27] have been obtained by using dynamic key-guessing techniques. Up to now, the dynamic key-guessing techniques have only been combined with linear and differential cryptanalysis methods. There is no attempt to combine the dynamic key-guessing techniques with integral attack so far.Besides the above results under the single-key model, the security of SIMON has also been evaluated under the related-key [11] and known-key [8] models. In the related-key setting, Kondo et al. [11] constructed a 15-round related-key impossible differential distinguisher of SIMON32.Our Contributions. In this paper, we first apply dynamic key-guessing techniques to integral attacks. In our improved integral cryptanalysis, we extend dynamic key-guessing techniques to compute the sum, which is in the form of ∑xf(x,k)·V[x], where f is a nonlinear Boolean function and V[x] are counters for x. The dynamic key-guessing techniques improve the time complexity of the computation significantly. Please see the following example. Suppose f(x,k)=1⊕f1(x1,k1)&f2(x2,k2), where x=x1∥x2, k=k1∥k2, and f1 and f2 are two Boolean functions. We guess k1 at first; then we split x=x1∥x2 into two sets: S1={x∣f1(x1,k1)=0} and S2={x∣f1(x1,k1)=1}. We continue to compute the sum for each set. For set S1, there is no need to guess k2 since f(x,k)=1 when x∈S1. Finally, we sum them up.Using the dynamic key-guessing techniques, we present improved integral attacks on SIMON32 and SIMON48 in the single-key model. We present integral attacks on 24-round SIMON32, 24-round SIMON48/72, and 25-round SIMON48/96. In terms of the number of attacked rounds, our attack on SIMON32 is better than any previously known attacks, and our attacks on SIMON48 are the same as the best attacks. In order to verify the correctness of our approach, we implement the summation procedure of the integral attack on 22-round SIMON32. A summary of our results is given in Table1.Table 1
Summary of some related results for SIMON32 and SIMON48.
Target
Rounds
Data
Time
Memory(bytes)
Successprobability
Attacktype
Source
SIMON32/64
21
2
31
2
63E
2
54
1
Integ.
[21]
21
2
31
2
55.25E
-
51
%
Diff.
[20]
22
2
31
2
63E
2
55.8
1
Integ.
[7]
22
2
32
2
58.76E
-
31.5
%
Diff.
[13]
23
2
31.19
2
57.19TWO+261.84A+256E
-
28
%
Lin. hull
[6]
24
2
32
2
63E
2
33.64
1
Integ.
Section4.3
SIMON48/72
18
-
-
-
1
Integ.
[23]
22
2
47
2
71E
2
42
1
Integ.
[7]
23
2
47
2
63.25E
-
48
%
Diff.
[20]
24
2
47.92
2
69.92ONE+267.89A+256E
-
-
Lin. hull
[6]
24
2
48
2
71E
2
50
1
Integ.
AppendixB.2
SIMON48/96
19
-
-
-
1
Integ.
[23]
23
2
47
2
95E
2
47
1
Integ.
[7]
24
2
47
2
87.25E
-
48
%
Diff.
[20]
24
2
48
2
78.99E
-
47.5
%
Diff.
[13]
25
2
47.92
2
91.92TWO+289.89A+280E
-
-
Lin. hull
[6]
25
2
48
2
95E
2
50
1
Integ.
AppendixB.3
Note. This table summaries our results along with some previous major results of SIMON32 and SIMON48 in the single-key setting; E: encryption; A: addition; TWO: two rounds of encryption or decryption; ONE: one round of encryption or decryption.Outline. This paper is structured as follows. Section 2 briefly describes the specification of SIMON and some integral distinguishers. In Section 3, we discuss the time reduction in integral cryptanalysis of bit-oriented block ciphers. In Section 4, we present improved integral attacks on SIMON32 and SIMON48. In Section 4.1, we give the experimental result. Finally, Section 5 draws conclusions.


## 2. Preliminaries

### 2.1. Notations

n: the word size
x
i: the ith bit of bit string x
x
[
i
-
j
]
(
or
x
i
-
x
j
): the ith to the jth bits of bit string x
x
i
1
,
…
,
i
n: the XOR sum of xi, where i=i1,…,in, i.e., ⨁i∈{i1,…,in}xi
x
∥
y: concatenation of two bit strings x and y
X
r: the input of round r or output of round (r-1)
X
L
r
,
X
R
r: the left and right halves of Xr, that is, Xr=XLr∥XRr
X
L
,
i
r
(
resp
.
X
R
,
i
r
): the ith bit of bit string XLr(resp.XRr)
X
L
,
[
i
-
j
]
r (orXL,ir-XL,jr): the ith to the jth bits of bit string XLr
X
R
,
[
i
-
j
]
r (orXR,ir-XR,jr): the ith to the jth bits of bit string XRr
K
r: the subkey used in rth round
k
\
{
k
i
1
,
…
,
k
i
n
}: a new bit string, of which bits are derived from bit string k, excluding {ki1,…,kin}
⊕: bitwise XOR
&: bitwise AND
x
⋘
t: a left circular shift of bit string x by t bits
V
[
x
]
,
W
[
x
]
,
Y
[
x
]: counters for bit string x
B
k
(
f
): Bk(f)=∑xf(x,k)·V[x], where f is a Boolean function of x and k (actually, Bk(f) are counters for k)
F
(
x
): F(x)=[(x⋘1)&(x⋘8)]⊕(x⋘2)
F
(
x
)
i: the ith bit of bit string F(x)


### 2.2. Description of SIMON2n/mn

SIMON2n/mn is a two-branch balanced Feistel network with 2n-bit block size and mn-bit key, where n is the word size. There are 10 variants for SIMON. The parameters of SIMON32/64, SIMON48/72, and SIMON48/96 are listed in Table 2, since only these three variants are considered in this paper. Let Xi=XLi∥XRi denote the input of round i and Xi+1=XLi+1∥XRi+1 be the output of round i. The subkey used in round i is denoted by Ki. The ith round is as follows (also see Figure 1): (1)XRi+1=XLi,XLi+1=FXLi⊕XRi⊕Ki, where the internal nonlinear function F is defined as (2)FXLi=XLi⋘1&XLi⋘8⊕XLi⋘2. The key schedules are different depending on the key size. Please refer to [2] for more details.Table 2
Parameters of SIMON32 and SIMON48.
Block size(2n)
Key size(mn)
Rounds
32(n=16)
64(m=4)
32
48(n=24)
72(m=3)
36
96(m=4)
36Figure 1
Round function of SIMON.


### 2.3. Integral Distinguishers of SIMON32 and SIMON48

Attackers prepare a set of texts where some bits (constant bits) are fixed to same values and the other bits (active bits) range over all possible values. If some bits (balanced bits) in the encrypted texts sum to zero afterR¯ rounds encryption, the cipher has an R¯-round integral distinguisher.Wang et al. [21] found a 14-round integral distinguisher of SIMON32 experimentally. Later, Todo and Morii [18] proved the correctness of this distinguisher using division property. Also, Fu et al. [7] revealed this distinguisher from the view of degree of the Boolean function. Integral characteristics of SIMON32 and SIMON48 were found in [7, 18, 21, 22]. And we apply them to our attacks. The constant bit, active bit, balanced bit, and unknown bit are labeled as c, a, b, and ?, respectively. The integral characteristics used in this literature are as follows.(i)
SIMON32’s 14-round distinguisher:Input: (caaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaa)Output: (????????????????, ?b??????b??????b)(ii)
SIMON48’s 15-round distinguisher:Input: (caaaaaaaaaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaaaaaaaaaa)Output: (????????????????????????, bbbbbbbbbbbbbbbbbbbbbbbb)


## 2.1. Notations

n: the word size
x
i: the ith bit of bit string x
x
[
i
-
j
]
(
or
x
i
-
x
j
): the ith to the jth bits of bit string x
x
i
1
,
…
,
i
n: the XOR sum of xi, where i=i1,…,in, i.e., ⨁i∈{i1,…,in}xi
x
∥
y: concatenation of two bit strings x and y
X
r: the input of round r or output of round (r-1)
X
L
r
,
X
R
r: the left and right halves of Xr, that is, Xr=XLr∥XRr
X
L
,
i
r
(
resp
.
X
R
,
i
r
): the ith bit of bit string XLr(resp.XRr)
X
L
,
[
i
-
j
]
r (orXL,ir-XL,jr): the ith to the jth bits of bit string XLr
X
R
,
[
i
-
j
]
r (orXR,ir-XR,jr): the ith to the jth bits of bit string XRr
K
r: the subkey used in rth round
k
\
{
k
i
1
,
…
,
k
i
n
}: a new bit string, of which bits are derived from bit string k, excluding {ki1,…,kin}
⊕: bitwise XOR
&: bitwise AND
x
⋘
t: a left circular shift of bit string x by t bits
V
[
x
]
,
W
[
x
]
,
Y
[
x
]: counters for bit string x
B
k
(
f
): Bk(f)=∑xf(x,k)·V[x], where f is a Boolean function of x and k (actually, Bk(f) are counters for k)
F
(
x
): F(x)=[(x⋘1)&(x⋘8)]⊕(x⋘2)
F
(
x
)
i: the ith bit of bit string F(x)


## 2.2. Description of SIMON2n/mn

SIMON2n/mn is a two-branch balanced Feistel network with 2n-bit block size and mn-bit key, where n is the word size. There are 10 variants for SIMON. The parameters of SIMON32/64, SIMON48/72, and SIMON48/96 are listed in Table 2, since only these three variants are considered in this paper. Let Xi=XLi∥XRi denote the input of round i and Xi+1=XLi+1∥XRi+1 be the output of round i. The subkey used in round i is denoted by Ki. The ith round is as follows (also see Figure 1): (1)XRi+1=XLi,XLi+1=FXLi⊕XRi⊕Ki, where the internal nonlinear function F is defined as (2)FXLi=XLi⋘1&XLi⋘8⊕XLi⋘2. The key schedules are different depending on the key size. Please refer to [2] for more details.Table 2
Parameters of SIMON32 and SIMON48.
Block size(2n)
Key size(mn)
Rounds
32(n=16)
64(m=4)
32
48(n=24)
72(m=3)
36
96(m=4)
36Figure 1
Round function of SIMON.


## 2.3. Integral Distinguishers of SIMON32 and SIMON48

Attackers prepare a set of texts where some bits (constant bits) are fixed to same values and the other bits (active bits) range over all possible values. If some bits (balanced bits) in the encrypted texts sum to zero afterR¯ rounds encryption, the cipher has an R¯-round integral distinguisher.Wang et al. [21] found a 14-round integral distinguisher of SIMON32 experimentally. Later, Todo and Morii [18] proved the correctness of this distinguisher using division property. Also, Fu et al. [7] revealed this distinguisher from the view of degree of the Boolean function. Integral characteristics of SIMON32 and SIMON48 were found in [7, 18, 21, 22]. And we apply them to our attacks. The constant bit, active bit, balanced bit, and unknown bit are labeled as c, a, b, and ?, respectively. The integral characteristics used in this literature are as follows.(i)
SIMON32’s 14-round distinguisher:Input: (caaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaa)Output: (????????????????, ?b??????b??????b)(ii)
SIMON48’s 15-round distinguisher:Input: (caaaaaaaaaaaaaaaaaaaaaaa, aaaaaaaaaaaaaaaaaaaaaaaa)Output: (????????????????????????, bbbbbbbbbbbbbbbbbbbbbbbb)


## 3. Time Reduction in Integral Attacks on Bit-Oriented Block Ciphers

Suppose the input of the integral distinguisher is from the set(3)SI=Xi=XLi,XRi∣XL,0i=c,XL,1-15i∈F2n-1,XRi∈F2n.After R¯-round encryption, some bits of the output Xi+R¯ are balanced. For simplicity, let the first bit of the right part, that is, XR,0i+R¯, be balanced. We add α rounds before the distinguisher and append β rounds after it. Let the Boolean expressions of XL,0i and XR,0i+R¯ be functions represented as fEα(xP,kP) and fDβ(xC,kC), where xP, xC, kP, and kC are effective bit strings derived from the plaintext, the ciphertext, and involved subkeys.We briefly outline the idea of our integral attacks onα+R¯+β rounds of ciphers. Given the entire codebook, we guess some subkey bits and carry out the first α rounds’ encryption. Then choose a set of states that form the input space SI. For the corresponding ciphertexts, we guess the related subkey bits and decrypt the last β rounds to check if the target bit XR,0i+R¯ is balanced.In general, the time complexity of the integral attack is roughlyO(2l·N), where l  is the number of guessed subkey bits and N denotes the number of plaintext-ciphertext pairs. But we can optimize it with dynamic key-guessing techniques.


### 3.1. Find Collections of Ciphertexts

LetV[xP,xC] denote the counters into which we store the frequency of (xP,xC). For each guessed kP, we traverse the whole plaintext space and make partial encryptions. If fEα(xP,kP)=c, we store the corresponding ciphertext. Thus, we generate new counters W[kP,xC], which are defined as ∑xP,fEα(xP,kP)=cV[xP,xC].Furthermore, iffEα is linear with some bit of kP, say kP,0, we let fEα(xP,kP)=kP,0⊕fEα′(xP,kP′), where kP=kP,0∥kP′. We now assign c the value kP,0⊕1. Accordingly, W[kP′,xC]=∑xP,fEα′(xP,kP′)=1V[xP,xC], which means that the condition fEα′(xP,kP′)=1 can be transformed to a coefficient. Therefore, it is sufficient to calculate W[kP′,xC]=∑xPfE′(xP,kP′)·V[xP,xC].


### 3.2. Compute∑xf(x,k)·V[x] with Dynamic Key-Guessing Techniques

As described above, the modeling to find the collections of ciphertexts can be converted into the task of computing another counterW[k] which is defined as(4)Wk=∑xfx,k·Vx, where f is a Boolean function of x and k, and V[x] denotes the number of x. Let x be a l1-bit value and k be a l2-bit value. In a naive way, it needs O(2l1+l2) calculations of f to get the counters W[k]. Using dynamic key-guessing techniques, the calculation can be done with improved time complexity. The basic idea is as follows.Letk=kG∥kA∥kB∥kC, where kG, kA, kB, and kC are l2G, l2A, l2B, and l2C bits. After guessing kG, the set of x can be split into two sets SA and SB with NA and NB elements, respectively. For values in SA, f is independent of kB. Similarly, for values in SB, f is independent of kA. Thus, ∑xf(x,k)·V[x]=∑x∈SAf(x,kG∥kA∥kC)·V[x]+∑x∈SBf(x,kG∥kB∥kC)·V[x]. We compute the sum for each set, then we sum them up. Therefore, using dynamic key-guessing techniques, the improved time complexity becomes O(NA·2l2G+l2A+l2C+NB·2l2G+l2B+l2C).Again, we provide a toy example that illustrates the idea behind the improvement. Letx∈F23,k∈F23, and f(x,k)=x0⊕k0⊕((x1⊕k1)&(x2⊕k2)). Firstly, we guess k1. Then,(5)∑xfx,k·Vx=∑x1=k1,x0∈F2,x2∈F2x0⊕k0·Vx+∑x1=k1⊕1,x0∈F2,x2∈F2x0,2⊕k0,2·Vx.Next, we create four counters T0,0, T0,1, T1,0, and T1,1 and assign some values to them: T0,0=V[0∥k1∥0]+V[0∥k1∥1], T0,1=V[1∥k1∥0]+V[1∥k1∥1], T1,0=V[0∥(k1⊕1)∥0]+V[1∥(k1⊕1)∥1], and T1,1=V[0∥(k1⊕1)∥1]+V[1∥(k1⊕1)∥0]. Finally, W[k]=T0,k0⊕1+T1,k0⊕k2⊕1. Thus, the calculation of W[k] essentially requires 2×(2+2+22)=24 additions, while it takes 26 operations in a straightforward method.See AppendixA for more information on the time complexity of the calculation of ∑xf(x,k)·V[x].


### 3.3. Compute the XOR Sum of the Recovered Bit

Assume now that we obtain the new countersW[kP′,xC]. For a fixed kP′, we guess kC and partially decrypt each effective bit string xC to get the value of the target bit, that is, fDβ(xC,kC). Then, check whether the XOR sum of the recovered bit is zero. Note that the XOR sum amounts to the parity of ∑xCfDβ(xC,kC)·W[kP′,xC]. For simplicity, let fDβ(xC,kC) be kC,0⊕fDβ′(xC,kC′), where kC,0 is the first bit of kC, kC=kC,0∥kC′. We can omit kC,0 since it does not affect the XOR sum. Hence, the XOR sum essentially equals the parity of new counters Y[kP′,kC′] which is defined as ∑xCfDβ′(xC,kC′)·W[kP′,xC]. Also, dynamic key-guessing techniques can be applied in the last β rounds to improve the time complexity.


## 3.1. Find Collections of Ciphertexts

LetV[xP,xC] denote the counters into which we store the frequency of (xP,xC). For each guessed kP, we traverse the whole plaintext space and make partial encryptions. If fEα(xP,kP)=c, we store the corresponding ciphertext. Thus, we generate new counters W[kP,xC], which are defined as ∑xP,fEα(xP,kP)=cV[xP,xC].Furthermore, iffEα is linear with some bit of kP, say kP,0, we let fEα(xP,kP)=kP,0⊕fEα′(xP,kP′), where kP=kP,0∥kP′. We now assign c the value kP,0⊕1. Accordingly, W[kP′,xC]=∑xP,fEα′(xP,kP′)=1V[xP,xC], which means that the condition fEα′(xP,kP′)=1 can be transformed to a coefficient. Therefore, it is sufficient to calculate W[kP′,xC]=∑xPfE′(xP,kP′)·V[xP,xC].


## 3.2. Compute∑xf(x,k)·V[x] with Dynamic Key-Guessing Techniques

As described above, the modeling to find the collections of ciphertexts can be converted into the task of computing another counterW[k] which is defined as(4)Wk=∑xfx,k·Vx, where f is a Boolean function of x and k, and V[x] denotes the number of x. Let x be a l1-bit value and k be a l2-bit value. In a naive way, it needs O(2l1+l2) calculations of f to get the counters W[k]. Using dynamic key-guessing techniques, the calculation can be done with improved time complexity. The basic idea is as follows.Letk=kG∥kA∥kB∥kC, where kG, kA, kB, and kC are l2G, l2A, l2B, and l2C bits. After guessing kG, the set of x can be split into two sets SA and SB with NA and NB elements, respectively. For values in SA, f is independent of kB. Similarly, for values in SB, f is independent of kA. Thus, ∑xf(x,k)·V[x]=∑x∈SAf(x,kG∥kA∥kC)·V[x]+∑x∈SBf(x,kG∥kB∥kC)·V[x]. We compute the sum for each set, then we sum them up. Therefore, using dynamic key-guessing techniques, the improved time complexity becomes O(NA·2l2G+l2A+l2C+NB·2l2G+l2B+l2C).Again, we provide a toy example that illustrates the idea behind the improvement. Letx∈F23,k∈F23, and f(x,k)=x0⊕k0⊕((x1⊕k1)&(x2⊕k2)). Firstly, we guess k1. Then,(5)∑xfx,k·Vx=∑x1=k1,x0∈F2,x2∈F2x0⊕k0·Vx+∑x1=k1⊕1,x0∈F2,x2∈F2x0,2⊕k0,2·Vx.Next, we create four counters T0,0, T0,1, T1,0, and T1,1 and assign some values to them: T0,0=V[0∥k1∥0]+V[0∥k1∥1], T0,1=V[1∥k1∥0]+V[1∥k1∥1], T1,0=V[0∥(k1⊕1)∥0]+V[1∥(k1⊕1)∥1], and T1,1=V[0∥(k1⊕1)∥1]+V[1∥(k1⊕1)∥0]. Finally, W[k]=T0,k0⊕1+T1,k0⊕k2⊕1. Thus, the calculation of W[k] essentially requires 2×(2+2+22)=24 additions, while it takes 26 operations in a straightforward method.See AppendixA for more information on the time complexity of the calculation of ∑xf(x,k)·V[x].


## 3.3. Compute the XOR Sum of the Recovered Bit

Assume now that we obtain the new countersW[kP′,xC]. For a fixed kP′, we guess kC and partially decrypt each effective bit string xC to get the value of the target bit, that is, fDβ(xC,kC). Then, check whether the XOR sum of the recovered bit is zero. Note that the XOR sum amounts to the parity of ∑xCfDβ(xC,kC)·W[kP′,xC]. For simplicity, let fDβ(xC,kC) be kC,0⊕fDβ′(xC,kC′), where kC,0 is the first bit of kC, kC=kC,0∥kC′. We can omit kC,0 since it does not affect the XOR sum. Hence, the XOR sum essentially equals the parity of new counters Y[kP′,kC′] which is defined as ∑xCfDβ′(xC,kC′)·W[kP′,xC]. Also, dynamic key-guessing techniques can be applied in the last β rounds to improve the time complexity.


## 4. Integral Attacks on SIMON32 and SIMON48

### 4.1. Integral Attack on 22-Round SIMON32

We start with a key-recovery attack over four rounds of partial encryption and four rounds of partial decryption, exploiting the 14-round integral characteristic. Any of balanced bits can be taken as the target bit. Here, we pickXR,0i+14. In the attack, we compress each plaintext-ciphertext pair into counters. Then we apply the approach given above to the reduced SIMON32.The Boolean expression of the constant bitXL,15i has the same general form as that of the balanced bit XR,0i+14. The general form is shown in (6). The specific information on each bit is listed in Tables 3 and 4. In the tables, Xi-4 and Xi+18, respectively, denote the plaintext and the ciphertext.(6)fx,k=x0⊕k0⊕x1⊕k1&x2⊕k2⊕x3⊕k3&x4⊕k4⊕x5⊕k5⊕x6⊕k6&x7⊕k7&x8⊕k8⊕x9⊕k9&x7⊕k7⊕x10⊕k10⊕x6⊕k6&x7⊕k7⊕x11⊕k11⊕x12⊕k12&x13⊕k13&x14⊕k14⊕x3⊕k3&x13⊕k13&x15⊕k15⊕x7⊕k7&x9⊕k9⊕x14⊕k14⊕x13⊕k13&x3⊕k3&x16⊕k16⊕x3⊕k3&x4⊕k4.Table 3
Each effective bit of the Boolean expression ofXL,15i.
xi
Representation ofxi
k
i
Representation ofki
x0
X
L
,
7
i
-
4
⊕
(
X
L
,
8
i
-
4
&
X
L
,
1
i
-
4
)
⊕
X
R
,
9
i
-
4
⊕
X
L
,
11
i
-
4
⊕
X
L
,
15
i
-
4
k
0
K
9
i
-
4
⊕
K
11
i
-
3
⊕
K
15
i
-
3
⊕
K
13
i
-
2
⊕
K
15
i
-
1
x1
X
L
,
8
i
-
4
⊕
(
X
L
,
9
i
-
4
&
X
L
,
2
i
-
4
)
⊕
X
R
,
10
i
-
4
k
1
K
10
i
-
4
x2
X
L
,
1
i
-
4
⊕
(
X
L
,
2
i
-
4
&
X
L
,
11
i
-
4
)
⊕
X
R
,
3
i
-
4
k
2
K
3
i
-
4
x3
X
L
,
12
i
-
4
⊕
(
X
L
,
13
i
-
4
&
X
L
,
6
i
-
4
)
⊕
X
R
,
14
i
-
4
k
3
K
14
i
-
4
x4
X
L
,
5
i
-
4
⊕
(
X
L
,
6
i
-
4
&
X
L
,
15
i
-
4
)
⊕
X
R
,
7
i
-
4
k
4
K
7
i
-
4
x5
X
L
,
8
i
-
4
⊕
(
X
L
,
9
i
-
4
&
X
L
,
2
i
-
4
)
⊕
X
R
,
10
i
-
4
⊕
X
L
,
12
i
-
4
k
5
K
10
i
-
4
⊕
K
12
i
-
3
x6
X
L
,
9
i
-
4
⊕
(
X
L
,
10
i
-
4
&
X
L
,
3
i
-
4
)
⊕
X
R
,
11
i
-
4
k
6
K
11
i
-
4
x7
X
L
,
2
i
-
4
⊕
(
X
L
,
3
i
-
4
&
X
L
,
12
i
-
4
)
⊕
X
R
,
4
i
-
4
k
7
K
4
i
-
4
x8
X
L
,
1
i
-
4
⊕
(
X
L
,
2
i
-
4
&
X
L
,
11
i
-
4
)
⊕
X
R
,
3
i
-
4
⊕
X
L
,
5
i
-
4
k
8
K
3
i
-
4
⊕
K
5
i
-
3
x9
X
L
,
11
i
-
4
⊕
(
X
L
,
12
i
-
4
&
X
L
,
5
i
-
4
)
⊕
X
R
,
13
i
-
4
k
9
K
13
i
-
4
x10
x
3
⊕
x
5
k
10
k
3
⊕
k
5
⊕
K
14
i
-
2
x11
X
L
,
9
i
-
4
⊕
(
X
L
,
10
i
-
4
&
X
L
,
3
i
-
4
)
⊕
X
R
,
11
i
-
4
⊕
X
L
,
13
i
-
4
k
11
K
11
i
-
4
⊕
K
13
i
-
3
x12
X
L
,
10
i
-
4
⊕
(
X
L
,
11
i
-
4
&
X
L
,
4
i
-
4
)
⊕
X
R
,
12
i
-
4
k
12
K
12
i
-
4
x13
X
L
,
3
i
-
4
⊕
(
X
L
,
4
i
-
4
&
X
L
,
13
i
-
4
)
⊕
X
R
,
5
i
-
4
k
13
K
5
i
-
4
x14
X
L
,
2
i
-
4
⊕
(
X
L
,
3
i
-
4
&
X
L
,
12
i
-
4
)
⊕
X
R
,
4
i
-
4
⊕
X
L
,
6
i
-
4
k
14
K
4
i
-
4
⊕
K
6
i
-
3
x15
x
4
⊕
x
8
k
15
k
4
⊕
k
8
⊕
K
7
i
-
2
x16
X
L
,
11
i
-
4
⊕
(
X
L
,
12
i
-
4
&
X
L
,
5
i
-
4
)
⊕
X
R
,
13
i
-
4
⊕
X
L
,
15
i
-
4
k
16
K
13
i
-
4
⊕
K
15
i
-
3Table 4
Each effective bit of the Boolean expression ofXR,0i+14.
xi
Representation ofxi
ki
Representation ofki
x0
XR,8i+18⊕(XR,9i+18&XR,2i+18)⊕XL,10i+18⊕XR,12i+18⊕XR,0i+18
k0
K10i+17⊕K12i+16⊕K0i+16⊕K14i+15⊕K0i+14
x1
XR,9i+18⊕(XR,10i+18&XR,3i+18)⊕XL,11i+18
k1
K11i+17
x2
XR,2i+18⊕(XR,3i+18&XR,12i+18)⊕XL,4i+18
k2
K4i+17
x3
XR,13i+18⊕(XR,14i+18&XR,7i+18)⊕XL,15i+18
k3
K15i+17
x4
XR,6i+18⊕(XR,7i+18&XR,0i+18)⊕XL,8i+18
k4
K8i+17
x5
XR,9i+18⊕(XR,10i+18&XR,3i+18)⊕XL,11i+18⊕XR,13i+18
k5
K11i+17⊕K13i+16
x6
XR,10i+18⊕(XR,11i+18&XR,4i+18)⊕XL,12i+18
k6
K12i+17
x7
XR,3i+18⊕(XR,4i+18&XR,13i+18)⊕XL,5i+18
k7
K5i+17
x8
XR,2i+18⊕(XR,3i+18&XR,12i+18)⊕XL,4i+18⊕XR,6i+18
k8
K4i+17⊕K6i+16
x9
XR,12i+18⊕(XR,13i+18&XR,6i+18)⊕XL,14i+18
k9
K14i+17
x10
x3⊕x5
k10
k3⊕k5⊕K15i+15
x11
XR,10i+18⊕(XR,11i+18&XR,4i+18)⊕XL,12i+18⊕XR,14i+18
k11
K12i+17⊕K14i+16
x12
XR,11i+18⊕(XR,12i+18&XR,5i+18)⊕XL,13i+18
k12
K13i+17
x13
XR,4i+18⊕(XR,5i+18&XR,14i+18)⊕XL,6i+18
k13
K6i+17
x14
XR,3i+18⊕(XR,4i+18&XR,13i+18)⊕XL,5i+18⊕XR,7i+18
k14
K5i+17⊕K7i+16
x15
x4⊕x8
k15
k4⊕k8⊕K8i+15
x16
XR,12i+18⊕(XR,13i+18&XR,6i+18)⊕XL,14i+18⊕XR,0i+18
k16
K14i+17⊕K0i+16During the computation ofY[kP′,kC′], we first guess kP′; then we guess kC′. Since there is no difference between the first and the second halves of the computation, in the following, we mainly discuss the first half, that is, the computation of (7)WkP′,xC=∑xPfE′xP,kP′·VxP,xC.To describe our procedure in a convenient way, we simplify our modeling. We give a brief description of the modeling. We aim to compute another counter Bk′(f′), which is defined as ∑xf′(x,k′)·V[x], where k=k0∥k′ and f(x,k)=k0⊕f′(x,k′). Our approach is as follows.(
a
) Guess k1,k3,k7 and then split the texts into 8 sets according to the value (x1⊕k1,x3⊕k3,x7⊕k7). Table 5 shows corresponding variants of the Boolean function f′(x,k′). Accordingly, we have(8)f000=x0⊕x5⊕k5&x8⊕k8⊕x10⊕k10⊕x11⊕k11⊕x12⊕k12&x13⊕k13&x14⊕k14&x15⊕k15⊕x14⊕k14&x16⊕k16,⋮f111=x0,2,4⊕k2,4⊕x5,6⊕k5,6&x8,9⊕k8,9⊕x6,10⊕k6,10⊕x11⊕k11⊕x12⊕k12&x13⊕k13&x13,14⊕k13,14&x9,15⊕k9,15⊕x13,14⊕k13,14&x4,16⊕k4,16.Table 5
Variants of the Boolean functionf′(x,k′).
Guess
x
1
⊕
k
1, x3⊕k3, x7⊕k7
f
′
k1,k3,k7
0,0
,
0
f
000
0
,
0
,
1
f
001
0
,
1
,
0
f
010
0
,
1
,
1
f
011
1
,
0
,
0
f
100
1
,
0
,
1
f
101
1
,
1
,
0
f
110
1
,
1
,
1
f
111Then we create new counters for the next step. For example, if(x1⊕k1,x3⊕k3,x7⊕k7)=(1,1,1), f′ is equal to f111. Thus, we compress corresponding counters into new counters V111, where(9)V111x0,2,4,x5,6,x8,9,x6,10,x11,x12,x13,x13,14,x9,15,x4,16 is initialized to(10)∑x1=k1⊕1,x3=k3⊕1,x7=k7⊕1,x2∈F2,x5∈F2,x8∈F2Vx. Due to x10=x3⊕x5, x6,10 is uniquely determined by x5,6. Besides, 3-bit information is independent of the value [x0,2,4,x5,6,x8,9,x6,10,x11,x12,x13,x13,14,x9,15,x4,16]. Consequently, the creation in this example costs 29×7 additions.(
b
) For each set of texts and corresponding Boolean function, we compute Bk′∖{k1,k3,k7}(f′). We take f111 as an example when (x1⊕k1,x3⊕k3,x7⊕k7)=(1,1,1).(
1
) The next guesses, k5,6 and k13,14, are constrained by the simplified Boolean function f111. The corresponding texts are split into four sets. The Boolean functions simplified even further are shown in Table 6.Table 6
Variants of the Boolean functionf111.
Guess
x5,6⊕k5,6,x13,14⊕k13,14
f111
k5,6,k13,14
0,0
f
111
00
0
,
1
f11101
1
,
0
f11110
1
,
1
f11111(i)(x5,6⊕k5,6,x13,14⊕k13,14)=(0,0).The new countersV11100 are created. They are given by(11)V11100x0,2,4,x6,10,x9,15=∑x5,6=k5,6,x13,14=k13,14V111x0,2,4,x5,6,x8,9,x6,10,x11,x12,x13,x13,14,x9,15,x4,16.The creation of new counters takes 22×(25-1) addition operations. Accordingly, we have(12)f11100=x0,2,4⊕k2,4⊕x6,10⊕k6,10&x9,15⊕k9,15. In Appendix A, the time complexity of computing Bk2,4,k6,10,k9,15(f11100) (Case 2 in Appendix A) is estimated. The calculation of Bk2,4,k6,10,k9,15(f11100) requires 24 additions.(ii)(x5,6⊕k5,6,x13,14⊕k13,14)=(0,1).Similarly,(13)V11101x0,2,4,x6,10,11,x12,x13,x4,9,15,16=∑x5,6=k5,6,x13,14=k13,14⊕1V111x0,2,4,x5,6,x8,9,x6,10,x11,x12,x13,x13,14,x9,15,x4,16,f11101=x0,2,4⊕k2,4⊕x6,10,11⊕k6,10,11⊕x12⊕k12&x13⊕k13&x4,9,15,16⊕k4,9,15,16.The creation of new counters takes25×(22-1)=27-25 addition operations. And the calculation of Bk2,4,k6,10,11,k12,k13,k4,9,15,16(f11101) costs 26.75 additions.(iii)(x5,6⊕k5,6,x13,14⊕k13,14)=(1,0).(14)V11110x0,2,4,8,9,x6,10,x9,15=∑x5,6=k5,6⊕1,x13,14=k13,14V111x0,2,4,x5,6,x8,9,x6,10,x11,x12,x13,x13,14,x9,15,x4,16,f11110=x0,2,4,8,9⊕k2,4,8,9⊕x6,10⊕k6,10&x9,15⊕k9,15.The creation of new counters takes22×(25-1)=27-22 addition operations. And the calculation of Bk2,4,8,9,k6,10,k9,15(f11101) costs 24 additions.(iv)(x5,6⊕k5,6,x13,14⊕k13,14)=(1,1).(15)V11111x0,2,4,8,9,x6,10,11,x12,x13,x4,9,15,16=∑x5,6=k5,6⊕1,x13,14=k13,14⊕1V111x0,2,4,x5,6,x8,9,x6,10,x11,x12,x13,x13,14,x9,15,x4,16,f11111=x0,2,4,8,9⊕k2,4,8,9⊕x6,10,11⊕k6,10,11⊕x12⊕k12&x13⊕k13&x4,9,15,16⊕k4,9,15,16.The creation of new counters takes25×(22-1)=27-25 addition operations. And the calculation of Bk2,4,8,9,k6,10,11,k12,k13,k4,9,15,16(f11111) costs 26.75 additions.(
2
) After this, we sum the four temporary variables up; namely,(16)Bk2,4,k5,6,k8,9,k6,10,k11-k14,k9,15,k4,16f111=Bk2,4,k6,10,k9,15f11100+Bk2,4,8,9,k6,10,k9,15f11110+Bk2,4,k6,10,11,k12,k13,k4,9,15,16f11101+Bk2,4,8,9,k6,10,11,k12,k13,k4,9,15,16f11111. Thus, the time complexity of the summation requires no more than 28×3=28.58 additions, for each k5,6,k13,14.In this example, it takes22×((27-22+24+27-25+26.75)×2+28.58)=212.06 additions to compute Bk′∖{k1,k3,k7}(f′).(
c
) For each k1,k3,k7, we sum the eight temporary variables up. The summation yields a time complexity of 213×7 addition operations.Thus, for eachxC, the time complexity of computing W[kP′,xC] is approximately 219.87 additions. The details are given in Table 7. T1 denotes the time complexity of creating new counters according to guessed key bits. T2 denotes the time complexity of computing the sum for each set. T3 denotes the time complexity of summing them up.Table 7
Time complexity of calculatingW[kP′,xC] with a fixed xC.
Guess
x
1
⊕
k
1, x3⊕k3, x7⊕k7
f
′
Time
T1
T2
T
3
k1,k3,k7
0,0
,
0
f
000
2
9
×
7
2
12.06
2
13
×
7
0
,
0
,
1
f
001
2
9
×
7
2
12.06
0
,
1
,
0
f
010
2
9
×
7
2
12.06
0
,
1
,
1
f
011
2
9
×
7
2
12.06
1
,
0
,
0
f
100
2
9
×
7
2
12.06
1
,
0
,
1
f
101
2
9
×
7
2
12.06
1
,
1
,
0
f
110
2
9
×
7
2
12.06
1
,
1
,
1
f
111
2
9
×
7
2
12.06
Total time
(
(
2
9
×
7
+
2
12.06
)
×
8
+
2
13
×
7
)
×
2
3
=
2
19.87Let us review the procedure proc_simon_32_bit_cond used to computeY[kP′,kC′] and the key-recovery attack on 22-round SIMON32. The procedure is as follows.(1)
For each of215xC, we compute W[kP′,xC].(2)
For each of216kP′, we compute Y[kP′,kC′].The time complexity of proc_simon_32_bit_cond procedure is215×219.87+216×219.87=236.45 additions.The attack works as follows.(1)
Compress the whole plaintext-ciphertext pairs into230 counters V[xP,xC].(2)
Call proc_simon_32_bit_cond.(3)
Check the parity ofY[kP′,kC′]. If the parity is odd, discard the 32-bit subkey guess. Otherwise, use the key schedule to recover 32 bits of the master key and then exhaustively search for the remaining 32-bit keys.It is noted that there is one AND operation and three XOR operations in one round of SIMON. In our analysis, we approximate them as four XOR operations. The time complexity of step 1 is232 compressions, which is equivalent to about 232×104/4×16×22=228.24 encryptions. Since we care about the parity of Y[kP′,kC′], all counters can be taken modulo 2. The addition is actually the bitwise XOR operation in the calculation of Y[kP′,kC′]. Thus, the time complexity of step 2 is equivalent to about 236.45×1/4×16×22=226 encryptions. The time complexity of step 3 is 263 encryptions. Hence, the proposed attack on 22-round SIMON32 requires 232 known plaintexts and has a total time complexity equivalent to about 263 encryptions.We have implemented the calculation ofY[kP′,kC′]. The experiment was performed on Intel Core i7-4790 with 8 GBytes of DDR3 memory. The experimental result confirmed the correctness of our technique.


### 4.2. Integral Attack on 23-Round SIMON32

In this section, we extend the 22-round attack by one round. The improved attack is as follows. Guess 13 bits’ subkeykα and partially encrypt plaintexts, where kα=K1i-5-K6i-5∥K8i-5-K13i-5∥K15i-5. Then carry out the 22-round attack.We briefly explain why there is no need to guessK7i-5. Let the first bit of xP (resp., kP) be xP,0 (resp., kP,0). In our attack, we make the redefinitions, xP,0=K7i-5⊕XL,7i-4⊕(XL,8i-4&XL,1i-4)⊕XR,9i-4⊕XL,11i-4⊕XL,15i-4 and kP,0=K7i-5⊕K9i-4⊕K11i-3⊕K15i-3⊕K13i-2⊕K15i-1. It is evident that K7i-5⊕XL,7i-4⊕(XL,8i-4&XL,1i-4)⊕XR,9i-4⊕XL,11i-4⊕XL,15i-4 can be obtained after guessing 13 bits’ subkey kα. Consequently, we still have fE′(xP,kP′)=1.The 23-round attack has a data complexity of232 known plaintexts and a time complexity of about 263 encryptions.


### 4.3. Integral Attack on 24-Round SIMON32

The 22-round attack can be extended by one round in forward and one round in backward direction in a straightforward way. The improved attack proceeds as follows. Guess 26 bits subkeykα∥kβ, where kβ=K0i+18∥K2i+18-K7i+18∥K9i+18-K14i+18. Partially encrypt plaintexts and partially decrypt corresponding ciphertexts. Then carry out the 22-round attack presented above. It should be noted that we do not guess K8i+18. The reason is essentially the same as the case mentioned above.In this attack, the dominant part of the time complexity is still exhaustively searching half of the key space. The total time complexity of our attack is about263 encryptions. The number of the required known plaintexts is 232. The success probability of our attack is 100%.The total memory complexity of our attack is determined by the size of the entire SIMON32 codebook,V[xP,xC] and W[kP′,xC]. This corresponds to a memory requirement of about 233.64 bytes. Note that we can only store F(XRi+19)0⊕XL,0i+19∥(F(XRi+19)⊕XLi+19)2-(F(XRi+19)⊕XLi+19)14∥XR,4i+19-XR,6i+19∥XR,8i+19∥XR,10i+19-XR,15i+19 for each ciphertext. In addition, there is no need to store Y[kP′,kC′]. The elements of it can be computed on-the-fly. As soon as a value of Y[kP′,kC′] is computed, the bit condition is checked. If the condition is satisfied, then exhaustively search for the remaining 6-bit key.


### 4.4. Improved Integral Attacks on SIMON48

We can improve the integral attacks on SIMON48/72 and SIMON48/96, using dynamic key-guessing techniques. Since the attack procedures for them are similar, we present these integral attacks in AppendixB. The results are summarized in Table 1.


## 4.1. Integral Attack on 22-Round SIMON32

We start with a key-recovery attack over four rounds of partial encryption and four rounds of partial decryption, exploiting the 14-round integral characteristic. Any of balanced bits can be taken as the target bit. Here, we pickXR,0i+14. In the attack, we compress each plaintext-ciphertext pair into counters. Then we apply the approach given above to the reduced SIMON32.The Boolean expression of the constant bitXL,15i has the same general form as that of the balanced bit XR,0i+14. The general form is shown in (6). The specific information on each bit is listed in Tables 3 and 4. In the tables, Xi-4 and Xi+18, respectively, denote the plaintext and the ciphertext.(6)fx,k=x0⊕k0⊕x1⊕k1&x2⊕k2⊕x3⊕k3&x4⊕k4⊕x5⊕k5⊕x6⊕k6&x7⊕k7&x8⊕k8⊕x9⊕k9&x7⊕k7⊕x10⊕k10⊕x6⊕k6&x7⊕k7⊕x11⊕k11⊕x12⊕k12&x13⊕k13&x14⊕k14⊕x3⊕k3&x13⊕k13&x15⊕k15⊕x7⊕k7&x9⊕k9⊕x14⊕k14⊕x13⊕k13&x3⊕k3&x16⊕k16⊕x3⊕k3&x4⊕k4.Table 3
Each effective bit of the Boolean expression ofXL,15i.
xi
Representation ofxi
k
i
Representation ofki
x0
X
L
,
7
i
-
4
⊕
(
X
L
,
8
i
-
4
&
X
L
,
1
i
-
4
)
⊕
X
R
,
9
i
-
4
⊕
X
L
,
11
i
-
4
⊕
X
L
,
15
i
-
4
k
0
K
9
i
-
4
⊕
K
11
i
-
3
⊕
K
15
i
-
3
⊕
K
13
i
-
2
⊕
K
15
i
-
1
x1
X
L
,
8
i
-
4
⊕
(
X
L
,
9
i
-
4
&
X
L
,
2
i
-
4
)
⊕
X
R
,
10
i
-
4
k
1
K
10
i
-
4
x2
X
L
,
1
i
-
4
⊕
(
X
L
,
2
i
-
4
&
X
L
,
11
i
-
4
)
⊕
X
R
,
3
i
-
4
k
2
K
3
i
-
4
x3
X
L
,
12
i
-
4
⊕
(
X
L
,
13
i
-
4
&
X
L
,
6
i
-
4
)
⊕
X
R
,
14
i
-
4
k
3
K
14
i
-
4
x4
X
L
,
5
i
-
4
⊕
(
X
L
,
6
i
-
4
&
X
L
,
15
i
-
4
)
⊕
X
R
,
7
i
-
4
k
4
K
7
i
-
4
x5
X
L
,
8
i
-
4
⊕
(
X
L
,
9
i
-
4
&
X
L
,
2
i
-
4
)
⊕
X
R
,
10
i
-
4
⊕
X
L
,
12
i
-
4
k
5
K
10
i
-
4
⊕
K
12
i
-
3
x6
X
L
,
9
i
-
4
⊕
(
X
L
,
10
i
-
4
&
X
L
,
3
i
-
4
)
⊕
X
R
,
11
i
-
4
k
6
K
11
i
-
4
x7
X
L
,
2
i
-
4
⊕
(
X
L
,
3
i
-
4
&
X
L
,
12
i
-
4
)
⊕
X
R
,
4
i
-
4
k
7
K
4
i
-
4
x8
X
L
,
1
i
-
4
⊕
(
X
L
,
2
i
-
4
&
X
L
,
11
i
-
4
)
⊕
X
R
,
3
i
-
4
⊕
X
L
,
5
i
-
4
k
8
K
3
i
-
4
⊕
K
5
i
-
3
x9
X
L
,
11
i
-
4
⊕
(
X
L
,
12
i
-
4
&
X
L
,
5
i
-
4
)
⊕
X
R
,
13
i
-
4
k
9
K
13
i
-
4
x10
x
3
⊕
x
5
k
10
k
3
⊕
k
5
⊕
K
14
i
-
2
x11
X
L
,
9
i
-
4
⊕
(
X
L
,
10
i
-
4
&
X
L
,
3
i
-
4
)
⊕
X
R
,
11
i
-
4
⊕
X
L
,
13
i
-
4
k
11
K
11
i
-
4
⊕
K
13
i
-
3
x12
X
L
,
10
i
-
4
⊕
(
X
L
,
11
i
-
4
&
X
L
,
4
i
-
4
)
⊕
X
R
,
12
i
-
4
k
12
K
12
i
-
4
x13
X
L
,
3
i
-
4
⊕
(
X
L
,
4
i
-
4
&
X
L
,
13
i
-
4
)
⊕
X
R
,
5
i
-
4
k
13
K
5
i
-
4
x14
X
L
,
2
i
-
4
⊕
(
X
L
,
3
i
-
4
&
X
L
,
12
i
-
4
)
⊕
X
R
,
4
i
-
4
⊕
X
L
,
6
i
-
4
k
14
K
4
i
-
4
⊕
K
6
i
-
3
x15
x
4
⊕
x
8
k
15
k
4
⊕
k
8
⊕
K
7
i
-
2
x16
X
L
,
11
i
-
4
⊕
(
X
L
,
12
i
-
4
&
X
L
,
5
i
-
4
)
⊕
X
R
,
13
i
-
4
⊕
X
L
,
15
i
-
4
k
16
K
13
i
-
4
⊕
K
15
i
-
3Table 4
Each effective bit of the Boolean expression ofXR,0i+14.
xi
Representation ofxi
ki
Representation ofki
x0
XR,8i+18⊕(XR,9i+18&XR,2i+18)⊕XL,10i+18⊕XR,12i+18⊕XR,0i+18
k0
K10i+17⊕K12i+16⊕K0i+16⊕K14i+15⊕K0i+14
x1
XR,9i+18⊕(XR,10i+18&XR,3i+18)⊕XL,11i+18
k1
K11i+17
x2
XR,2i+18⊕(XR,3i+18&XR,12i+18)⊕XL,4i+18
k2
K4i+17
x3
XR,13i+18⊕(XR,14i+18&XR,7i+18)⊕XL,15i+18
k3
K15i+17
x4
XR,6i+18⊕(XR,7i+18&XR,0i+18)⊕XL,8i+18
k4
K8i+17
x5
XR,9i+18⊕(XR,10i+18&XR,3i+18)⊕XL,11i+18⊕XR,13i+18
k5
K11i+17⊕K13i+16
x6
XR,10i+18⊕(XR,11i+18&XR,4i+18)⊕XL,12i+18
k6
K12i+17
x7
XR,3i+18⊕(XR,4i+18&XR,13i+18)⊕XL,5i+18
k7
K5i+17
x8
XR,2i+18⊕(XR,3i+18&XR,12i+18)⊕XL,4i+18⊕XR,6i+18
k8
K4i+17⊕K6i+16
x9
XR,12i+18⊕(XR,13i+18&XR,6i+18)⊕XL,14i+18
k9
K14i+17
x10
x3⊕x5
k10
k3⊕k5⊕K15i+15
x11
XR,10i+18⊕(XR,11i+18&XR,4i+18)⊕XL,12i+18⊕XR,14i+18
k11
K12i+17⊕K14i+16
x12
XR,11i+18⊕(XR,12i+18&XR,5i+18)⊕XL,13i+18
k12
K13i+17
x13
XR,4i+18⊕(XR,5i+18&XR,14i+18)⊕XL,6i+18
k13
K6i+17
x14
XR,3i+18⊕(XR,4i+18&XR,13i+18)⊕XL,5i+18⊕XR,7i+18
k14
K5i+17⊕K7i+16
x15
x4⊕x8
k15
k4⊕k8⊕K8i+15
x16
XR,12i+18⊕(XR,13i+18&XR,6i+18)⊕XL,14i+18⊕XR,0i+18
k16
K14i+17⊕K0i+16During the computation ofY[kP′,kC′], we first guess kP′; then we guess kC′. Since there is no difference between the first and the second halves of the computation, in the following, we mainly discuss the first half, that is, the computation of (7)WkP′,xC=∑xPfE′xP,kP′·VxP,xC.To describe our procedure in a convenient way, we simplify our modeling. We give a brief description of the modeling. We aim to compute another counter Bk′(f′), which is defined as ∑xf′(x,k′)·V[x], where k=k0∥k′ and f(x,k)=k0⊕f′(x,k′). Our approach is as follows.(
a
) Guess k1,k3,k7 and then split the texts into 8 sets according to the value (x1⊕k1,x3⊕k3,x7⊕k7). Table 5 shows corresponding variants of the Boolean function f′(x,k′). Accordingly, we have(8)f000=x0⊕x5⊕k5&x8⊕k8⊕x10⊕k10⊕x11⊕k11⊕x12⊕k12&x13⊕k13&x14⊕k14&x15⊕k15⊕x14⊕k14&x16⊕k16,⋮f111=x0,2,4⊕k2,4⊕x5,6⊕k5,6&x8,9⊕k8,9⊕x6,10⊕k6,10⊕x11⊕k11⊕x12⊕k12&x13⊕k13&x13,14⊕k13,14&x9,15⊕k9,15⊕x13,14⊕k13,14&x4,16⊕k4,16.Table 5
Variants of the Boolean functionf′(x,k′).
Guess
x
1
⊕
k
1, x3⊕k3, x7⊕k7
f
′
k1,k3,k7
0,0
,
0
f
000
0
,
0
,
1
f
001
0
,
1
,
0
f
010
0
,
1
,
1
f
011
1
,
0
,
0
f
100
1
,
0
,
1
f
101
1
,
1
,
0
f
110
1
,
1
,
1
f
111Then we create new counters for the next step. For example, if(x1⊕k1,x3⊕k3,x7⊕k7)=(1,1,1), f′ is equal to f111. Thus, we compress corresponding counters into new counters V111, where(9)V111x0,2,4,x5,6,x8,9,x6,10,x11,x12,x13,x13,14,x9,15,x4,16 is initialized to(10)∑x1=k1⊕1,x3=k3⊕1,x7=k7⊕1,x2∈F2,x5∈F2,x8∈F2Vx. Due to x10=x3⊕x5, x6,10 is uniquely determined by x5,6. Besides, 3-bit information is independent of the value [x0,2,4,x5,6,x8,9,x6,10,x11,x12,x13,x13,14,x9,15,x4,16]. Consequently, the creation in this example costs 29×7 additions.(
b
) For each set of texts and corresponding Boolean function, we compute Bk′∖{k1,k3,k7}(f′). We take f111 as an example when (x1⊕k1,x3⊕k3,x7⊕k7)=(1,1,1).(
1
) The next guesses, k5,6 and k13,14, are constrained by the simplified Boolean function f111. The corresponding texts are split into four sets. The Boolean functions simplified even further are shown in Table 6.Table 6
Variants of the Boolean functionf111.
Guess
x5,6⊕k5,6,x13,14⊕k13,14
f111
k5,6,k13,14
0,0
f
111
00
0
,
1
f11101
1
,
0
f11110
1
,
1
f11111(i)(x5,6⊕k5,6,x13,14⊕k13,14)=(0,0).The new countersV11100 are created. They are given by(11)V11100x0,2,4,x6,10,x9,15=∑x5,6=k5,6,x13,14=k13,14V111x0,2,4,x5,6,x8,9,x6,10,x11,x12,x13,x13,14,x9,15,x4,16.The creation of new counters takes 22×(25-1) addition operations. Accordingly, we have(12)f11100=x0,2,4⊕k2,4⊕x6,10⊕k6,10&x9,15⊕k9,15. In Appendix A, the time complexity of computing Bk2,4,k6,10,k9,15(f11100) (Case 2 in Appendix A) is estimated. The calculation of Bk2,4,k6,10,k9,15(f11100) requires 24 additions.(ii)(x5,6⊕k5,6,x13,14⊕k13,14)=(0,1).Similarly,(13)V11101x0,2,4,x6,10,11,x12,x13,x4,9,15,16=∑x5,6=k5,6,x13,14=k13,14⊕1V111x0,2,4,x5,6,x8,9,x6,10,x11,x12,x13,x13,14,x9,15,x4,16,f11101=x0,2,4⊕k2,4⊕x6,10,11⊕k6,10,11⊕x12⊕k12&x13⊕k13&x4,9,15,16⊕k4,9,15,16.The creation of new counters takes25×(22-1)=27-25 addition operations. And the calculation of Bk2,4,k6,10,11,k12,k13,k4,9,15,16(f11101) costs 26.75 additions.(iii)(x5,6⊕k5,6,x13,14⊕k13,14)=(1,0).(14)V11110x0,2,4,8,9,x6,10,x9,15=∑x5,6=k5,6⊕1,x13,14=k13,14V111x0,2,4,x5,6,x8,9,x6,10,x11,x12,x13,x13,14,x9,15,x4,16,f11110=x0,2,4,8,9⊕k2,4,8,9⊕x6,10⊕k6,10&x9,15⊕k9,15.The creation of new counters takes22×(25-1)=27-22 addition operations. And the calculation of Bk2,4,8,9,k6,10,k9,15(f11101) costs 24 additions.(iv)(x5,6⊕k5,6,x13,14⊕k13,14)=(1,1).(15)V11111x0,2,4,8,9,x6,10,11,x12,x13,x4,9,15,16=∑x5,6=k5,6⊕1,x13,14=k13,14⊕1V111x0,2,4,x5,6,x8,9,x6,10,x11,x12,x13,x13,14,x9,15,x4,16,f11111=x0,2,4,8,9⊕k2,4,8,9⊕x6,10,11⊕k6,10,11⊕x12⊕k12&x13⊕k13&x4,9,15,16⊕k4,9,15,16.The creation of new counters takes25×(22-1)=27-25 addition operations. And the calculation of Bk2,4,8,9,k6,10,11,k12,k13,k4,9,15,16(f11111) costs 26.75 additions.(
2
) After this, we sum the four temporary variables up; namely,(16)Bk2,4,k5,6,k8,9,k6,10,k11-k14,k9,15,k4,16f111=Bk2,4,k6,10,k9,15f11100+Bk2,4,8,9,k6,10,k9,15f11110+Bk2,4,k6,10,11,k12,k13,k4,9,15,16f11101+Bk2,4,8,9,k6,10,11,k12,k13,k4,9,15,16f11111. Thus, the time complexity of the summation requires no more than 28×3=28.58 additions, for each k5,6,k13,14.In this example, it takes22×((27-22+24+27-25+26.75)×2+28.58)=212.06 additions to compute Bk′∖{k1,k3,k7}(f′).(
c
) For each k1,k3,k7, we sum the eight temporary variables up. The summation yields a time complexity of 213×7 addition operations.Thus, for eachxC, the time complexity of computing W[kP′,xC] is approximately 219.87 additions. The details are given in Table 7. T1 denotes the time complexity of creating new counters according to guessed key bits. T2 denotes the time complexity of computing the sum for each set. T3 denotes the time complexity of summing them up.Table 7
Time complexity of calculatingW[kP′,xC] with a fixed xC.
Guess
x
1
⊕
k
1, x3⊕k3, x7⊕k7
f
′
Time
T1
T2
T
3
k1,k3,k7
0,0
,
0
f
000
2
9
×
7
2
12.06
2
13
×
7
0
,
0
,
1
f
001
2
9
×
7
2
12.06
0
,
1
,
0
f
010
2
9
×
7
2
12.06
0
,
1
,
1
f
011
2
9
×
7
2
12.06
1
,
0
,
0
f
100
2
9
×
7
2
12.06
1
,
0
,
1
f
101
2
9
×
7
2
12.06
1
,
1
,
0
f
110
2
9
×
7
2
12.06
1
,
1
,
1
f
111
2
9
×
7
2
12.06
Total time
(
(
2
9
×
7
+
2
12.06
)
×
8
+
2
13
×
7
)
×
2
3
=
2
19.87Let us review the procedure proc_simon_32_bit_cond used to computeY[kP′,kC′] and the key-recovery attack on 22-round SIMON32. The procedure is as follows.(1)
For each of215xC, we compute W[kP′,xC].(2)
For each of216kP′, we compute Y[kP′,kC′].The time complexity of proc_simon_32_bit_cond procedure is215×219.87+216×219.87=236.45 additions.The attack works as follows.(1)
Compress the whole plaintext-ciphertext pairs into230 counters V[xP,xC].(2)
Call proc_simon_32_bit_cond.(3)
Check the parity ofY[kP′,kC′]. If the parity is odd, discard the 32-bit subkey guess. Otherwise, use the key schedule to recover 32 bits of the master key and then exhaustively search for the remaining 32-bit keys.It is noted that there is one AND operation and three XOR operations in one round of SIMON. In our analysis, we approximate them as four XOR operations. The time complexity of step 1 is232 compressions, which is equivalent to about 232×104/4×16×22=228.24 encryptions. Since we care about the parity of Y[kP′,kC′], all counters can be taken modulo 2. The addition is actually the bitwise XOR operation in the calculation of Y[kP′,kC′]. Thus, the time complexity of step 2 is equivalent to about 236.45×1/4×16×22=226 encryptions. The time complexity of step 3 is 263 encryptions. Hence, the proposed attack on 22-round SIMON32 requires 232 known plaintexts and has a total time complexity equivalent to about 263 encryptions.We have implemented the calculation ofY[kP′,kC′]. The experiment was performed on Intel Core i7-4790 with 8 GBytes of DDR3 memory. The experimental result confirmed the correctness of our technique.


## 4.2. Integral Attack on 23-Round SIMON32

In this section, we extend the 22-round attack by one round. The improved attack is as follows. Guess 13 bits’ subkeykα and partially encrypt plaintexts, where kα=K1i-5-K6i-5∥K8i-5-K13i-5∥K15i-5. Then carry out the 22-round attack.We briefly explain why there is no need to guessK7i-5. Let the first bit of xP (resp., kP) be xP,0 (resp., kP,0). In our attack, we make the redefinitions, xP,0=K7i-5⊕XL,7i-4⊕(XL,8i-4&XL,1i-4)⊕XR,9i-4⊕XL,11i-4⊕XL,15i-4 and kP,0=K7i-5⊕K9i-4⊕K11i-3⊕K15i-3⊕K13i-2⊕K15i-1. It is evident that K7i-5⊕XL,7i-4⊕(XL,8i-4&XL,1i-4)⊕XR,9i-4⊕XL,11i-4⊕XL,15i-4 can be obtained after guessing 13 bits’ subkey kα. Consequently, we still have fE′(xP,kP′)=1.The 23-round attack has a data complexity of232 known plaintexts and a time complexity of about 263 encryptions.


## 4.3. Integral Attack on 24-Round SIMON32

The 22-round attack can be extended by one round in forward and one round in backward direction in a straightforward way. The improved attack proceeds as follows. Guess 26 bits subkeykα∥kβ, where kβ=K0i+18∥K2i+18-K7i+18∥K9i+18-K14i+18. Partially encrypt plaintexts and partially decrypt corresponding ciphertexts. Then carry out the 22-round attack presented above. It should be noted that we do not guess K8i+18. The reason is essentially the same as the case mentioned above.In this attack, the dominant part of the time complexity is still exhaustively searching half of the key space. The total time complexity of our attack is about263 encryptions. The number of the required known plaintexts is 232. The success probability of our attack is 100%.The total memory complexity of our attack is determined by the size of the entire SIMON32 codebook,V[xP,xC] and W[kP′,xC]. This corresponds to a memory requirement of about 233.64 bytes. Note that we can only store F(XRi+19)0⊕XL,0i+19∥(F(XRi+19)⊕XLi+19)2-(F(XRi+19)⊕XLi+19)14∥XR,4i+19-XR,6i+19∥XR,8i+19∥XR,10i+19-XR,15i+19 for each ciphertext. In addition, there is no need to store Y[kP′,kC′]. The elements of it can be computed on-the-fly. As soon as a value of Y[kP′,kC′] is computed, the bit condition is checked. If the condition is satisfied, then exhaustively search for the remaining 6-bit key.


## 4.4. Improved Integral Attacks on SIMON48

We can improve the integral attacks on SIMON48/72 and SIMON48/96, using dynamic key-guessing techniques. Since the attack procedures for them are similar, we present these integral attacks in AppendixB. The results are summarized in Table 1.


## 5. Conclusion

In this paper, dynamic key-guessing techniques are first introduced in integral cryptanalysis, and we extend dynamic key-guessing techniques to fit our needs. Dynamic key-guessing techniques significantly improve the complexity of calculating∑xf(x,k)·V[x]. Using dynamic key-guessing techniques, we can attack two more rounds than previously known integral attacks on SIMON32 and SIMON48.



---

*Source: 5160237-2018-02-19.xml*