A Novel Differential Fault Analysis on the Key Schedule of SIMON Family

Abstract

As a family of lightweight block ciphers, SIMON has attracted lots of research attention since its publication in 2013. Recent works show that SIMON is vulnerable to differential fault analysis (DFA) and existing DFAs on SIMON assume the location of induced faults are on the cipher states. In this paper, a novel DFA on SIMON is proposed where the key schedule is selected as the location of induced faults. Firstly, we assume a random one-bit fault is induced in the fourth round key K^T−4 to the last. Then, by utilizing the key schedule propagation properties of SIMON, we determine the exact position of induced fault and demonstrate that the proposed DFA can retrieve 4 bits of the last round key K^T−1 on average using one-bit fault. Till now this is the largest number of bits that can be cracked as compared to DFAs based on random bit fault model. Furthermore, by reusing the induced fault, we prove that 2 bits of the penultimate round key K^T−2 could be retrieved. To the best of our knowledge, the proposed attack is the first one which extracts a key from SIMON based upon DFA on the key schedule. Finally, correctness and validity of our proposed attack is verified through detailed simulation and analysis.

1. Introduction

In 2013, a family of lightweight block ciphers called SIMON was presented by the National Security Agency (NSA), based upon the Feistel structure. Compared with other ciphers, SIMON can provide a better performance for both hardware and software. The block size of SIMON is denoted as 2n (the n represents the word size) with n = 16, 24, 32, 48, or 64. For each block size, it supports 3 key sizes. Thus, SIMON can be implemented on a wide range of devices [1]. Since the publication of SIMON, many cryptanalysis papers about it have been presented, such as integral attack [2,3], differential attack [4,5,6], and linear attack [6,7]. In addition, other attacks, such as differential fault analysis (DFA), have also been proposed to retrieve the secret keys from SIMON [8].

As one of the typical fault attacks (FA) [9], DFA was first proposed by Biham and Shamir in 1997 to obtain the secret key from DES cryptosystem [10]. The idea of DFA is to make use of some erroneous calculations caused by inducing some unexpected faults to retrieve the secret keys of a cipher algorithm. DFA has been greatly developed and poses a serious threat to the security of many cipher algorithms, including block cipher algorithms [8,11,12,13].

In FDTC 2014, Tupsamudre et al. proposed DFA on SIMON family for the first time [8]. In this attack, the authors induced the faults into L^T−2 (the left half input of the penultimate round) and proposed two fault models: random bit fault model and random byte fault model. Through theoretical analysis and experiments, they proved that it could retrieve 2 bits and one byte of the last round key K^T−1 by using one random bit-flip and one-byte fault, respectively. Later, Takahashi et al. proposed a random n-bit fault model against the SIMON family where the n represents the word size. They successfully retrieved the entire key of SIMON family through both, that is, theoretical computations and experimental simulations. For the data complexity (the data complexity refers to the number of the fault injections), they also presented a detail analysis [14].

After that, Vasquez et al. proposed an improved DFA on SIMON family [15]. Similarly to [8], they also assumed a random bit fault model. However, the location of induced fault is in L^T−3. Because more depth of induced fault lead to more efficient diffusion of the induced fault, this scheme can retrieve 3.5 bits of K^T−1 on average by inducing one-bit fault. Furthermore, by reusing the induced one-bit fault, 2 bits of the penultimate round key K^T−2 on average could be retrieved. As a result, they could break the entire key of SIMON96/96 and SIMON128/128 using only one round faults.

In a following work, another improved DFA on SIMON family was presented by Chen et al. in FDTC 2016 [16]. The authors injected faults into L^T−m−1 based on a random byte fault model, where the m represents the key words of SIMON family. They presented a detail analysis about the data complexity in theory and shown that the entire key of SIMON could be recovered. For retrieving the entire secret key of SIMON, they successfully break 6 instances of SIMON by using only one round faults.

This paper proposes a novel DFA on SIMON family. Different from existing DFAs on SIMON family where faults are induced into the cipher state, we induce faults into the key schedule for the first time. Based on a random bit fault model, we prove that 4 bits of K^T−1 and 2 bits of K^T−2 could be retrieved on average when inducing only one-bit fault into the fourth round key K^T−4 to the last. Compared to [8], which also uses random bit fault model, we can recover the entire key of SIMON family through half number of the fault locations. Compared to the previous works, our contributions in this paper are mainly as following:

• Selection of the key schedule as the location of induced fault. Different from these existing DFAs on SIMON family ([8,14,15,16]) where all select the cipher state as the location of induced fault, our DFA on SIMON is the first one which selects the key schedule as the location of induced fault. Thus, we have provided a new train of thought and method for using DFA to crack keys of the SIMON family.
• Compared with existing attacks based on the random bit fault model, our attack is more efficient. For the random bit fault model, paper [15] is the only one which could retrieve two round keys by using one induced round location. In other words, paper [15] can retrieve on average 3.5 bits of K^T−1 and 2 bits of K^T−2 by using one-bit fault induced into the (T−3)th round. Up to now, this is the most efficient method. However, selection of the key schedule especially K^T−4 as the location of induced fault, our attack can retrieve 4 bits of K^T−1 and 2 bits of K^T−2 on average using one-bit fault.

The rest of this paper is arranged as follows. Section 2 presents some necessary notation and a brief introduction for SIMON. Then Section 3 proposes and discusses our DFA on SIMON key schedule. In this section, we present the assumption of the proposed attack, then discuss how to determine the position of the induced fault and retrieve K^T−1 as well as K^T−2. Extended analysis includes the detailed data complexity assessment and scheme to crack the entire secret key of the SIMON family. Simulation results and comparisons are carried out in Section 4. Finally, concluding remarks are given in Section 5.

2. Preliminaries

2.1. Notation

• T: the round number of SIMON
• m: the key word size in SIMON
• n: the word size in SIMON
• P: plaintext
• C, C *: ciphertext and faulty ciphertext
• Lⁱ, Rⁱ: the left and right half input of the ith round, i ∈ {0, …, T−1}, the output of the cipher is denoted by (L^T, R^T)
• L_jⁱ, R_jⁱ: the jth bit of Lⁱ, Rⁱ
• Lⁱ *, Rⁱ *: the left and right half faulty input of the ith round, i ∈ {0, …, T−1}
• Kⁱ: round -key used in ith round, i ∈ {0, …, T−1}
• Kⁱ *: faulty Kⁱ when there is a fault in Kⁱ
• x <<< a: left circular shift of x by a bits
• y >>> b: right circular shift of y by b bits
• &: bitwise AND
• ⊕: bitwise xor
• a%b: a remainder b

2.2. Description for SIMON Family

As a lightweight block cipher, SIMON applies a Feistel structure with a n-bit word and a m-bit word key, which is denoted as SIMON 2n/mn. In the SIMON family, n should be 16, 24, 32, 48, or 64, and m = 2, 3, or 4. The parameters of the SIMON family with different (n, m) combinations are described in

Table 1. Parameters of the SIMON family.

Cipher SIMON2n/mn	Block Size 2n	Key Size mn	Word Size n	Key Words m	Const Seq	Rounds T
SIMON 32/64	32	64	16	4	z0	32
SIMON 48/72	48	72	24	3	z0	36
SIMON 48/96		96		4	z1	36
SIMON 64/96	64	96	32	3	z2	42
SIMON 64/128		128		4	z3	44
SIMON 96/96	96	96	48	2	z2	52
SIMON 96/144		144		3	z3	54
SIMON 128/128	128	128	64	2	z2	68
SIMON 128/192		192		3	z3	69
SIMON 128/256		256		4	z4	72

.

2.2.1. Key Schedule Function

The SIMON key schedule generates a sequence of T key from an input key, where T is the round number. For SIMON 2 n/mn, the T key words (K⁰, …, K^T−1) depend on the value of m and it can be generated using the formulas (1), where c is a constant value and c = 2ⁿ − 4 = 0xff…fc. The z_j represents 5 constant sequences denoted as z₀, z₁, z₂, z₃ and z₄, respectively. More detailed descriptions about the key schedule function and z_j can be obtained in [1].

$$\begin{array}{cc}\hfill m=2: K^i=& {c\oplus (z_j)}_{i-m}\oplus K^{i-2}\oplus \hfill \\ & (K^{i-1}>>>3)\oplus (K^{i-1}>>>4)\hfill \\ \hfill m=3: K^i=& {c\oplus (z_j)}_{i-m}\oplus K^{i-3}\oplus \hfill \\ & (K^{i-1}>>>3)\oplus (K^{i-1}>>>4)\hfill \\ \hfill m=4: K^i=& {c\oplus (z_j)}_{i-m}\oplus K^{i-4}\oplus K^{i-3}\oplus \hfill \\ & (K^{i-3}>>>1)\oplus (K^{i-1}>>>3)\hfill \\ & \oplus (K^{i-1}>>>4)\hfill \end{array}$$

(1)

2.2.2. Round Function

The SIMON round function R_k(Lⁱ, Rⁱ): GF(2)ⁿ × GF(2)ⁿ → GF(2)ⁿ × GF(2)ⁿ is defined as:

$$R_k(L^i,R^i)=(L^{i+1},R^{i+1}) =(R^i\oplus F(L^i)\oplus K^i,L^i)$$

where

$$F(L^i)=(L^i<<<1)\&(L^i<<<8)\oplus (L^i<<<2)$$

(2)

for i ∈ {0, …, T−1}. From (2), it can be known that the jth bit of Lⁱ affects 3 distinct bits of F(Lⁱ):

$$\begin{array}{l}F{(L^i)}_{(j+1)\%n}=(L_j^i\&L_{(j-7)\%n}^i)\oplus L_{(j-1)\%n}^i\\ F{(L^i)}_{(j+2)\%n}=(L_{(j+1)\%n}^i\&L_{(j-6)\%n}^i)\oplus L_j^i\\ F{(L^i)}_{(j+8)\%n}=(L_{(j+7)\%n}^i\&L_j^i)\oplus L_{(j+6)\%n}^i\end{array}$$

(3)

3. The Proposed Attack on SIMON Key Schedule

3.1. Assumption of the Proposed Attack

Different from these existing DFAs on SIMON, we assume the adversary induces a random one-bit fault into the key schedule, and the exact position of the induced fault is in K^T−4. (L^T *, R^T *) is denoted as the faulty output when inducing fault. K^T−4 is randomly corrupted by a random one-bit fault, the fault propagation process is as shown in Figure 1.

In Figure 1, the red thick line in K^T−4 represents the induced j%n bit of K^T−4. Both the red thick line in L^T−3 and R^T−2 represent the corrupted bits. The two yellow thick lines in K^T−3 represent the bit (j−3)%n and (j−4)%n of K^T−3 respectively, which are all corrupted by the j%n bit of K^T−4. And the thick lines show the cipher states and round keys which are necessary to retrieve K^T−1 and K^T−2. The gray in cipher states and round keys represent the faulty intermediate states and faulty round keys, respectively.

3.2. DFA on The (T−4) Round Key

In FDTC 2014, Tupsamudre et al. proposed the following formula to retrieve K^T−1:

$$K^{T-1}=L^{T-2}\oplus F(R^T)\oplus L^T$$

(4)

Thus, in order to make use of the induced random bit faults in K^T−4 to retrieve K^T−1, we need to establish the relationship between induced faults and L^T−2. We suppose the position of induced fault is the jth bit of K^T−4. From Figure 1, it can be deduced that:

$$\begin{array}{ll}{L}^{T*}& =F(L^{T-1*})\oplus K^{T-1*}\oplus R^{T-1*}\\ & =F(R^{T*})\oplus K^{T-1*}\oplus L^{T-2*}\\ & =F(R^{T*})\oplus K^{T-1*}\oplus K^{T-3*}\oplus F(L^{T-3*})\oplus R^{T-3}\end{array}$$

(5)

Therefore, we can derive the following equation from the xor of L^T and L^T *:

$$\begin{array}{ll}{L}^T\oplus L^{T*}=& F(R^T)\oplus F(R^{T*})\oplus K^{T-1}\oplus K^{T-1*}\\ & \oplus K^{T-3}\oplus K^{T-3*}\oplus F(L^{T-3})\oplus F(L^{T-3*})\end{array}$$

(6)

If we move F(R^T)⊕F(R *) in the Equation (6) to the left side, the Equation (6) can be rewritten as:

$$\begin{array}{ll}{L}^T\oplus L^{T*}\oplus & F(R^T)\oplus F(R^{T*})\\ & =K^{T-1}\oplus K^{T-1*}\oplus K^{T-3}\oplus K^{T-3*}\\ & \oplus F(L^{T-3})\oplus F(L^{T-3*})\end{array}$$

(7)

3.2.1. Determining the Position of Induced Fault

In this part, we will show how to determine the position of the induced fault based on Equation (7). From Figure 1, the induced bit fault in K^T−4 that will corrupt the same position bit in L^T−3 can be known, in other words, the jth bit of L^T−3 is flipped. According to the Formula (3), we can identify that 3 distinct bits of F(L^T−3) may be affected: (j + 1)%n, (j + 2)%n and (j + 8)%n. To further illustrate the affected bits, the function F(.) defined in Equation (2) needs further analysis. Assuming the jth bit of Lⁱ is induced, according to the Formula (3), it can be deduced that:

$$\begin{array}{l}F{(L^{i*})}_{(j+1)\%n}=((L_j^i\oplus 1)\&L_{(j-7)\%n}^i)\oplus L_{(j-1)\%n}^i\\ F{(L^{i*})}_{(j+2)\%n}=(L_{(j+1)\%n}^i\&L_{(j-6)\%n}^i)\oplus L_j^i\oplus 1\\ F{(L^{i*})}_{(j+8)\%n}=(L_{(j+7)\%n}^i\&(L_j^i\oplus 1))\oplus L_{(j+6)\%n}^i\end{array}$$

(8)

From the Equation (8), we can know that once the jth bit of Lⁱ is flipped, the (j + 2)%n bit of F(Lⁱ) is also flipped. Due to the jth bit of L^T−3 is flipped, it can be identified that the two bits (j + 1)%n and (j + 8)%n of F(L^T−3) may be affected, and the bit (j + 2)%n of F(L^T−3) must be affected.

According to the Formula (1) and the principle of the SIMON key schedule, we can obtain the following equation no matter the value of m (that is m = 2, 3, or 4):

$$\begin{array}{ll}{K}^{T-3}\oplus K^{T-3*}& =(K^{T-4}>>>3)\oplus (K^{T-4*}>>>3)\\ & \oplus (K^{T-4}>>>4)\oplus (K^{T-4*}>>>4)\end{array}$$

(9)

Equation (9) shows that one fault bit of K^T−4 will affect 2 distinct bits of K^T−3. In other words, the jth bit of K^T−4 affects the bits (j − 3)%n and (j − 4)%n of K^T−3.

$$\begin{array}{l}(K^{T-3}\oplus K^{T-3*}){}_{(j-3)\%n}=K^{T-4}\oplus (K^{T-4}\oplus 1)=1\\ (K^{T-3}\oplus K^{T-3*}){}_{(j-4)\%n}=K^{T-4}\oplus (K^{T-4}\oplus 1)=1\end{array}$$

(10)

Further, the bit (j − 3)%n of K^T−3 will affect the bits (j − 6)%n and (j − 7)% of K^T−2, the bit (j − 4)%n of K^T−3 will affect the bits (j − 7)%n and (j − 8)% of K^T−2. As a result, the bits (j − 3)%n and (j − 4)%n of K^T−3 will affect the bits (j − 6)%n and (j − 8)% of K^T−2. Through similar analysis, we can deduce the affected bits in K^T−1. The jth bit of K^T−4 affects the bits of K^T−3, K^T−2 and K^T−1 are given in

Table 2. The jth bit of K^T−4 affects the bits of K^T−3, K^T−2 and K^T−1.

The Position of Induced Fault	Key Words: m	Affected Bits
jth bit of KT−4	4	KT−3: j − 3, j − 4
		KT−2: j − 6, j − 8
		KT−1: j, j − 1, j − 9, j − 10, j − 11, j − 12
	3	KT−3: j − 3, j − 4
		KT−2: j − 6, j − 8
		KT−1: j, j − 9, j − 10, j − 11, j − 12
	2	KT−3: j − 3, j − 4
		KT−2: j, j − 6, j − 8
		KT−1: j − 9, j − 10, j − 11, j − 12

: For simplicity, (j − x)%n writes as j − x, where x ∈ {0,…,n}.

By combining the Equation (7), Table 2 and the analysis above, it can be identified some bits value in (L^T⊕L^T*⊕F(R^T)⊕F(RT*)). For convenience, we write (L^T⊕L^T*⊕F(R^T)⊕F(RT*)) as “LFR”, thus when key words m = 4 (only take m = 4 for example, when m = 3 or 2, the processes of discussion remain the same), we can get:

$$\begin{array}{l}{\mathrm{LFR}}_{j\%n}=K^{T-1}\oplus K^{T-1}\oplus 1=1\\ {\mathrm{LFR}}_{(j-3)\%n}=K^{T-3}\oplus K^{T-3}\oplus 1=1\\ {\mathrm{LFR}}_{(j-4)\%n}=K^{T-3}\oplus K^{T-3}\oplus 1=1\\ {\mathrm{LFR}}_{(j-1)\%n}=K^{T-1}\oplus K^{T-1}\oplus 1=1\\ {\mathrm{LFR}}_{(j-9)\%n}=K^{T-1}\oplus K^{T-1}\oplus 1=1\\ {\mathrm{LFR}}_{(j-10)\%n}=K^{T-1}\oplus K^{T-1}\oplus 1=1\\ {\mathrm{LFR}}_{(j-11)\%n}=K^{T-1}\oplus K^{T-1}\oplus 1=1\\ {\mathrm{LFR}}_{(j-12)\%n}=K^{T-1}\oplus K^{T-1}\oplus 1=1\\ {\mathrm{LFR}}_{(j+2)\%n}=L_j^{T-3}\oplus L_j^{T-3}\oplus 1=1,\end{array}$$

(11)

as well as the following equations:

$$\begin{array}{ll}{\mathrm{LFR}}_{\left(j+1\right)\%n}=& (L_j^{T-3}\&L_{(j-7)\%n}^{T-3})\\ & \oplus ((L_j^{T-3}\oplus 1)\&L_{(j-7)\%n}^{T-3})\\ {\mathrm{LFR}}_{\left(j+8\right)\%n}=& (L_{\left(j+7\right)\%n}^{T-3}\&L_j^{T-3})\\ & \oplus (L_{\left(j+7\right)\%n}^{T-3}\&(L_j^{T-3}\oplus 1))\end{array}$$

(12)

Through the Equation (11), it can be seen that 4 contiguous bits (j − 9)%n, (j − 10)%n, (j − 11)%n and (j − 12)%n of LFR are all 1. In fact, when m = 3, or 2, there are all 4 consecutive bits (j − 9)%n, (j − 10)%n, (j − 11)%n and (j − 12)%n be 1 in LFR. We present statistics on the value of bits in LFR under different conditions in

Table 3. The jth bit of K^T−4 affects the bits of LFR.

The Position of Induced Fault	Key Words: m	The Value of Bits in LFR(LFR = LT⊕LT *⊕F(RT)⊕F(RT*)
jth bit of KT−4	4	1: j, j − 1, j − 3, j − 4, j − 9, j − 10, j − 11, j − 12, j + 2
		may be 1: j + 1, j + 8
	3	1: j, j − 3, j − 4, j − 9, j − 10, j − 11, j − 12, j + 2
		may be 1: j + 1, j + 8
	2	1: j − 3, j − 4, j − 9, j − 10, j − 11, j − 12, j + 2
		may be 1: j + 1, j + 8

.

As can be seen in Table 3, there exists only one group of 4 contiguous 1 in LFR no matter if m = 4, 3 or 2, and this is a very important property. In fact, the idea for deducing the position j is based on this property.

To determine the position of induced fault, Algorithm 1 has been proposed. Here, the value of constant A depends on the word size n: (A, n) = {(F400, 16), (F40000, 24), …}. F(.) represents the non-linear function defined in Equation (2). The position of j can be determined by Algorithm 1, in other words, we can accurately determine the position of induced fault: jth bit of K^T−4.

Algorithm 1 Deducing the position of induced fault j in KT−4

Input: (LT, RT), (LT *, RT *), the word size n, constant A Output: deducing j.

1.   LFR ←LT⊕LT*⊕F(RT)⊕F(RT*)

2.   for i = 0: n − 1

3.      B ← circshift(A,[0,−i])          % right circular shift for binary

4.      C ← LFR & B

5.      if ( C == A)

6.          if (i <8)

7.              j%n ← n-8 + i

8.          else

9.              j%n ← i - 8

10.          end

11.    end

12.  end

3.2.2. Retrieving L^T−2 and K^T−1

According to the formula (4), it is known that if someone wants to retrieve K^T−1, she/he must obtain L^T, R^T and L^T−2 first. Because (L^T, R^T) is the output of SIMON which could be obtained directly, so she/he only needs to obtain L^T−2. From Figure 1, it can be deduced that:

$$R^{T*}=F(L^{T-2*})\oplus K^{T-2*}\oplus L^{T-3*}$$

(13)

Therefore, the following equation could be derived from the xor of R^T and R^T *:

$$\begin{array}{c}{R}^T\oplus R^{T*}=F(L^{T-2})\oplus F(L^{T-2*})\oplus K^{T-2}\oplus K^{T-2*}\\ \oplus L^{T-3}\oplus L^{T-3*}\end{array}$$

(14)

From the discussion in Section 3.2.1, it is known that when the jth bit of K^T−4 is flipped, the jth bit of L^T−3 will also be flipped, so the bit (j + 2)%n of F(L^T−3) is flipped. Because L^T−2* can be written as:

$$L^{T-2*}=F(L^{T-3})\oplus K^{T-3*}\oplus R^{T-3},$$

(15)

and the (j − 3)%n and (j − 4)%n of K^T−3 are flipped (this conclusion can be obtained from Table 2), so there must be 3 bits which are flipped in L^T−2: (j + 2)%n, (j − 3)%n and (j − 4)%n. Thus, combined the Equation (14) and the results from Table 2, the following equations could be obtained:

$$\begin{array}{ll}{(R^T\oplus R^{T*})}_{(j+4)\%n}& =(L_{(j+3)\%n}^{T-2} \& L_{(j-4)\%n}^{T-2})\\ & \oplus (L_{(j+3)\%n}^{T-2} \& (L_{(j-4)\%n}^{T-2}\oplus 1))\oplus 1\\ {(R^T\oplus R^{T*})}_{(j+5)\%n}& =(L_{(j+4)\%n}^{T-2} \& L_{(j-3)\%n}^{T-2})\\ & \oplus (L_{(j+4)\%n}^{T-2}\& (L_{(j-3)\%n}^{T-2}\oplus 1))\\ {(R^T\oplus R^{T*})}_{(j-2)\%n}& =(L_{(j-3)\%n}^{T-2}\& L_{(j-10)\%n}^{T-2})\\ & \oplus ((L_{(j-3)\%n}^{T-2}\oplus 1) \& L_{(j-10)\%n}^{T-2})\oplus 1\\ {(R^T\oplus R^{T*})}_{(j-3)\%n}& =(L_{(j-4)\%n}^{T-2} \& L_{(j-11)\%n}^{T-2})\\ & \oplus ((L_{(j-4)\%n}^{T-2}\oplus 1) \& L_{(j-11)\%n}^{T-2})\end{array}$$

(16)

Through the Equation (16), we have made truth tables to illustrate the relationships between the bits in L^T−2 and the bits in (R^T⊕R^T*).

From

Table 4. The relationship between the bit $L_{(j+3)\%n}^{T-2}$ and ${(R^T\oplus R^{T*})}_{(j+4)\%n}$.

${\mathit{L}}_{(\mathit{j}+3)\%\mathit{n}}^{\mathit{T}-2}$	${\mathit{L}}_{(\mathit{j}-4)\%\mathit{n}}^{\mathit{T}-2}$	${\mathit{L}}_{(\mathit{j}-4)\%\mathit{n}}^{\mathit{T}-2}\oplus 1$	${({\mathit{R}}^{\mathit{T}}\oplus {\mathit{R}}^{\mathit{T}*})}_{(\mathit{j}+4)\%\mathit{n}}$
0	0	1	1
0	1	0	1
1	0	1	0
1	1	0	0

, it can be seen that if ${(R^T\oplus R^{T*})}_{(j+4)\%n}=0$, then $L_{(j+3)\%n}^{T-2}=1$, otherwise it is 0. This is independent of the value of $L_{(j-4)\%n}^{T-2}$. Besides, from

Table 5. The relationship between the bit $L_{(j+4)\%n}^{T-2}$ and ${(R^T\oplus R^{T*})}_{(j+5)\%n}$.

${\mathit{L}}_{(\mathit{j}+4)\%\mathit{n}}^{\mathit{T}-2}$	${\mathit{L}}_{(\mathit{j}-3)\%\mathit{n}}^{\mathit{T}-2}$	${\mathit{L}}_{(\mathit{j}-3)\%\mathit{n}}^{\mathit{T}-2}\oplus 1$	${({\mathit{R}}^{\mathit{T}}\oplus {\mathit{R}}^{\mathit{T}*})}_{(\mathit{j}+5)\%\mathit{n}}$
0	0	1	0
0	1	0	0
1	0	1	1
1	1	0	1

,

Table 6. The relationship between the bit $L_{(j-10)\%n}^{T-2}$ and ${(R^T\oplus R^{T*})}_{(j-2)\%n}$.

${\mathit{L}}_{(\mathit{j}-10)\%\mathit{n}}^{\mathit{T}-2}$	${\mathit{L}}_{(\mathit{j}-3)\%\mathit{n}}^{\mathit{T}-2}$	${\mathit{L}}_{(\mathit{j}-3)\%\mathit{n}}^{\mathit{T}-2}\oplus 1$	${({\mathit{R}}^{\mathit{T}}\oplus {\mathit{R}}^{\mathit{T}*})}_{(\mathit{j}-2)\%\mathit{n}}$
0	0	1	1
0	1	0	1
1	0	1	0
1	1	0	0

and

Table 7. The relationship between the bit $L_{(j-11)\%n}^{T-2}$ and ${(R^T\oplus R^{T*})}_{(j-3)\%n}$.

${\mathit{L}}_{(\mathit{j}-11)\%\mathit{n}}^{\mathit{T}-2}$	${\mathit{L}}_{(\mathit{j}-4)\%\mathit{n}}^{\mathit{T}-2}$	${\mathit{L}}_{(\mathit{j}-4)\%\mathit{n}}^{\mathit{T}-2}\oplus 1$	${({\mathit{R}}^{\mathit{T}}\oplus {\mathit{R}}^{\mathit{T}*})}_{(\mathit{j}-3)\%\mathit{n}}$
0	0	1	0
0	1	0	0
1	0	1	1
1	1	0	1

, it can be seen that if ${(R^T\oplus R^{T*})}_{(j+5)\%n}=0$, then $L_{(j+4)\%n}^{T-2}=0$, otherwise it is 1; If ${(R^T\oplus R^{T*})}_{(j-2)\%n}=0$, then $L_{(j-10)\%n}^{T-2}=1$, otherwise it is 0; If ${(R^T\oplus R^{T*})}_{(j-3)\%n}=0$, then $L_{(j-11)\%n}^{T-2}=0$, otherwise it is 1. As a result, we can obtain the following equations:

$$\begin{array}{l}{L}_{(j+3)\%n}^{T-2}={(R^T\oplus R^{T*})}_{(j+4)\%n}\oplus 1\\ L_{(j+4)\%n}^{T-2}={(R^T\oplus R^{T*})}_{(j+5)\%n}\\ L_{(j-10)\%n}^{T-2}={(R^T\oplus R^{T*})}_{(j-2)\%n}\oplus 1\\ L_{(j-11)\%n}^{T-2}={(R^T\oplus R^{T*})}_{(j-3)\%n}\end{array}$$

(17)

Therefore, there are 4 bits (j + 3)%n, (j + 4)%n, (j − 10)%n and (j − 11)%n of K^T−1 that could be recovered according to the Equations (17) and (4):

$$\begin{array}{l}{K}_{(j+3)\%n}^{T-1}=L_{(j+3)\%n}^{T-2}\oplus F{(R^T)}_{(j+3)\%n}\oplus L_{(j+3)\%n}^T\\ K_{(j+4)\%n}^{T-1}=L_{(j+4)\%n}^{T-2}\oplus F{(R^T)}_{(j+4)\%n}\oplus L_{(j+4)\%n}^T\\ K_{(j-10)\%n}^{T-1}=L_{(j-10)\%n}^{T-2}\oplus F{(R^T)}_{(j-10)\%n}\oplus L_{(j-10)\%n}^T\\ K_{(j-11)\%n}^{T-1}=L_{(j-11)\%n}^{T-2}\oplus F{(R^T)}_{(j-11)\%n}\oplus L_{(j-11)\%n}^T\end{array}$$

(18)

3.2.3. Retrieving K^T−2

After retrieving K^T−1, we can reuse L^T−2 with similar operations to those described in Section 3.2.2 to retrieve K^T−2.

Now we obtain L^T−2, because R^T−1 = L^T−2 and L^T−1 = R^T, in other words the output of the T−2 round of SIMON: (L^T−1, R^T−1) is obtained. As shown in Figure 1, because $K^{T-2}=F(R^{T-1})\oplus L^{T-1}\oplus L^{T-3}$, if L^T−3 is known, then K^T−2 could be recovered. Based on the Equation (12), there are 2 bits (j − 7)%n and (j + 7)%n of L^T−3 could be deduced, therefore two bits of K^T−2 can be recovered when inducing one-bit fault in K^T−4.

3.3. Extended Analysis

According to the Equation (18), we can obtain 4 bits of K^T−1 which could be retrieved in theory by inducing one-bit fault in K^T−4. Furthermore, 2 bits of K^T−2 could be retrieved on an average by reusing the induced one-bit fault. When considering the random bit fault model, paper [8] can recover only 2 bits of K^T−1. Although paper [15] can also recover 2 bits of K^T−2, but it can only recover 3.5 bits of K^T−1 on average, Thus, our proposed one-bit fault attack for SIMON is more efficient.

As in the similar discussion in [15], when m = 2, the whole keys of SIMON (96/96 and 128/128) might also be retrieved by using only one round key faults. Indeed, for m = 2 and k = i −2, according to the Formula (1), we can obtain:

$$\begin{array}{l}m=2: K^k=c\oplus {(z_j)}_{k-m+2}\oplus K^{k+2} \oplus \\ (K^{k+1}>>>3)\oplus (K^{k+1}>>>4)\end{array}$$

(19)

So, for m = 2, by using only continuous two round keys of SIMON, the entire key of SIMON could be retrieved. As discussed in Section 3.2.2 and Section 3.2.3, K^T−1 and K^T−2 can be retrieved by inducing faults in K^T−4; thus we can retrieve the whole keys of SIMON (96/96 and 128/128) using only one round key faults. Similarly, considering m = 3 and m = 4, the following equations by the Formula (1) could be obtained:

$$\begin{array}{ll}m=3: K^k=& c\oplus {(z_j)}_{i-3+m}\oplus K^{k+3}\oplus \\ & (K^{k+2}>>>3)\oplus (K^{k+2}>>>4)\\ m=4: K^k=& c\oplus {(z_j)}_{i-4+m}\oplus K^{k+4}\oplus K^{k+1}\oplus \\ & (K^{k+1}>>>1)\oplus (K^{k+3}>>>3)\\ & \oplus (K^{k+3}>>>4)\end{array}$$

(20)

From the Equation (20), for m = 3, we know that if we can obtain K^T−2 and K^T−3, then the entire key of SIMON could be recovered. Therefore, we need to induce faults in two round keys: K^T−4 and K^T−6. The first inducing faults in K^T−4 are used to retrieve both K^T−1 and K^T−2, the second inducing faults in K^T−6 are used to only retrieve K^T−3. For m = 4, we also need to induce faults in two round keys: K^T−4 and K^T−6. However, it is different from the case when m = 3, in this case, we need to induce faults in K^T−6 to retrieve two round keys: K^T−3 and K^T−4. The key retrieving for SIMON family and specific fault locations are shown in

Table 8. Experiment results for the average number of the fault inductions to retrieve K^T−1/L^T−2.

Word Size: n	Avg. No. of the Fault Inductions				At least No. of the Fault Inductions in Theory:
	Random Byte Fault Model	Random Bit Fault Model			Random Byte Fault Model	Random Bit Fault Model
	[8]	[8]	[15]	This paper	[8]: n/8	[8]: n/2	[15]: n/3.5	This Paper: n/4
16	6	25	15.26	11.12	2	8	4.57	4
24	9	43	29.70	19.82	3	12	6.86	6
32	13	62	44.19	29.25	4	16	9.14	8
48	21	104	77.02	49.67	6	24	13.71	12
64	30	150	110.81	71.61	8	32	18.29	16

,

Table 9. Comparison of the experimental results of the fault inductions.

SIMON 2n/mn	Avg. No. of the Fault Inductions
	Random Byte Fault Model		Random n-Bit Fault Model	Random Bit Fault Model
	[8]	[16]	[14]	[8]	[15]	This Paper
SIMON32/64	24		12.20	101.72	50.85	50.32
SIMON48/72	27		9.91	130.78	87.19	62.78
SIMON48/96	36		13.22	174.37	87.19	85.86
SIMON64/96	39	31.57	10.45	189.44	126.29	91.57
SIMON64/128	52		13.93	252.58	126.29	124.72
SIMON96/96	42	35.08	7.46	210.24	105.12	104.00
SIMON96/144	63	50.84	11.19	315.36	210.24	153.64
SIMON128/128	60	50.55	7.82	299.68	149.84	148.51
SIMON128/192	90	72.88	11.73	449.52	299.68	220.15
SIMON128/256	120	104.82	15.64	599.36	299.68	297.02

and

Table 10. Comparison of the fault locations of differential fault analysis (DFA) on SIMON family.

SIMON2 n/mn	Fault Locations of DFA on SIMON Family
	Random Byte Fault Model		Random n-Bit Fault Model	Random Bit Fault Model
	[8]	[16]	[14]	[8]	[15]	This Paper
SIMON32/64	L27, L28, L29, L30	L27	L27, L28, L29, L30	L27, L28, L29, L30	L27, L29	K26, K28
SIMON48/72	L32, L33, L34	L32	L32, L33, L34	L32, L33, L34	L32, L33	K30, K32
SIMON48/96	L31, L32, L33, L34	L31	L31, L32, L33, L34	L31, L32, L33, L34	L31, L33	K30, K32
SIMON64/96	L38, L39, L40	L38	L38, L39, L40	L38, L39, L40	L38, L39	K36, K38
SIMON64/128	L39, L40, L41, L42	L39	L39, L40, L41, L42	L39, L40, L41, L42	L39, L41	K38, K40
SIMON96/96	L49, L50	L49	L49, L50	L49, L50	L49	K48
SIMON96/144	L50, L51, L52	L50	L50, L51, L52	L50, L51, L52	L50, L51	K48, K50
SIMON128/128	L65, L66	L65	L65, L66	L65, L66	L65	K64
SIMON128/192	L65, L66, L67	L65	L65, L66, L67	L65, L66, L67	L65, L66	K63, K65
SIMON128/256	L67, L68, L69, L70	L67	L67, L68, L69, L70	L67, L68, L69, L70	L67, L69	K66, K68

.

4. Simulation Results and Comparisons

In this section, we performed simulations to verify the correctness and validity of our proposed attack using C on a personal computer with a HP Intel^® Core i5-7300HQ. We assumed the adversary can induce a random one-bit fault in the round keys of SIMON.

Firstly, we randomly chose a set of plaintext and secret key to obtain the correct ciphertext (L^T, R^T). Then we induced random one-bit faults in K^T−4 to obtain the faulty ciphertexts (L^T *, R^T *). Finally, we used the proposed attack to retrieve K^T−1. For different word size n = 16, 24, 32, 48, and 64, we carried out simulation experiments respectively. The experiment was repeated 100,000 times for every value of n same as in [14,15,16]. Experimental results show that the proposed attack can recover the n-bit K^T−1 successfully. For different n, the average number of the fault inductions are described in Table 8. For retrieving the entire keys of the SIMON family, we make some comparisons with existing DFAs on SIMON family, as described in Table 9 and Table 10.

As shown in Table 8, when considering the random bit fault model, our proposed attack needs the least average number of fault inductions. Compared with the number of fault inductions in theory, the average number of fault inductions is much more, this is because we assume the position of the induced fault is random, so the faults can affect the same position many times. However, if we control precisely the position of induced faults, then the average number of fault inductions is very close to the number in theory.

As shown in Table 9 and Table 10, comparing the fault locations between the proposed attack and existing ones, our proposed attack is the only one which selects the round keys as the fault locations. When considering the random bit model, the proposed attack requires only half number of the fault locations compared with [8], and the numbers are as the same required in [15]. Except the random n-bit model [14] and the random byte model [16], the number of the fault inductions required in the proposed attack is least than required in [8,15]. Especially, when the key words m = 3, the number required in the proposed attack is much less than required in [15], this is because we induce faults in K^T−6 to retrieve only K^T−3 instead of retrieving both K^T−3 and K^T−4, so our proposed attack is more efficient.

5. Conclusions

This paper proposes a novel DFA on SIMON family by exploiting the leaked information by the AND operation used in the F(L^T−3). We show how to retrieve 4 bits of K^T−1 and 2 bits of K^T−2 on average based on only one-bit fault induced in K^T−4. Furthermore, we have proved that the entire key of SIMON96/96 and SIMON128/128 could be retrieved by using only one round faults.

Compared with existing works, the proposed attack in this paper is the first one which selects the SIMON key schedule as the location of induced faults. Considering the random bit fault model, our attack is the most efficient one up to data. When considering the random n-bit model [14] and random byte model [16], our attack requires a higher average number of fault inductions; this is because the different fault models are selected.

In the future, we will try to crack more bits by conferring whether the bit (j + 1)% and (j + 8)% of L^T−2 have been flipped. Further, we aim to explore the attack based upon different models such as the random n-bit model and random byte model so as to further reduce the required average number of fault inductions. Besides, how to apply our ideas on the block cipher SPECK will also be explored.