Next Article in Journal
AnScalable Matrix Computing Unit Architecture for FPGA, and SCUMO User Design Interface
Previous Article in Journal
Novel Dead-Time Compensation Strategy for Wide Current Range in a Three-Phase Inverter
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

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

1
College of Electronic and Information Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China
2
Institute of Computer Application, Taizhou University, Linhai 317000, China
*
Author to whom correspondence should be addressed.
Electronics 2019, 8(1), 93; https://doi.org/10.3390/electronics8010093
Submission received: 11 December 2018 / Revised: 3 January 2019 / Accepted: 10 January 2019 / Published: 15 January 2019
(This article belongs to the Section Circuit and Signal Processing)

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 KT−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 KT−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 KT−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 LT2 (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 KT1 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 LT−3. Because more depth of induced fault lead to more efficient diffusion of the induced fault, this scheme can retrieve 3.5 bits of KT1 on average by inducing one-bit fault. Furthermore, by reusing the induced one-bit fault, 2 bits of the penultimate round key KT2 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 LTm−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 KT1 and 2 bits of KT2 could be retrieved on average when inducing only one-bit fault into the fourth round key KT4 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 KT−1 and 2 bits of KT−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 KT−4 as the location of induced fault, our attack can retrieve 4 bits of KT1 and 2 bits of KT2 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 KT−1 as well as KT−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
  • Li, Ri: the left and right half input of the ith round, i ∈ {0, …, T−1}, the output of the cipher is denoted by (LT, RT)
  • Lji, Rji: the jth bit of Li, Ri
  • Li *, Ri *: the left and right half faulty input of the ith round, i ∈ {0, …, T−1}
  • Ki: round -key used in ith round, i ∈ {0, …, T−1}
  • Ki *: faulty Ki when there is a fault in Ki
  • 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.

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 (K0, …, KT−1) depend on the value of m and it can be generated using the formulas (1), where c is a constant value and c = 2n − 4 = 0xff…fc. The zj represents 5 constant sequences denoted as z0, z1, z2, z3 and z4, respectively. More detailed descriptions about the key schedule function and zj can be obtained in [1].
m = 2 :   K i = c ( z j ) i m K i 2 ( K i 1 > > > 3 ) ( K i 1 > > > 4 ) m = 3 :   K i = c ( z j ) i m K i 3 ( K i 1 > > > 3 ) ( K i 1 > > > 4 ) m = 4 :   K i = c ( z j ) i m K i 4 K i 3 ( K i 3 > > > 1 ) ( K i 1 > > > 3 ) ( K i 1 > > > 4 )

2.2.2. Round Function

The SIMON round function Rk(Li, Ri): GF(2)n × GF(2)n → GF(2)n × GF(2)n is defined as:
R k ( L i , R i ) = ( L i + 1 , R i + 1 )   = ( R i F ( L i ) K i , L i )
where
F ( L i ) = ( L i < < < 1 ) & ( L i < < < 8 ) ( L i < < < 2 )
for i ∈ {0, …, T−1}. From (2), it can be known that the jth bit of Li affects 3 distinct bits of F(Li):
F ( L i ) ( j + 1 ) % n = ( L j i & L ( j 7 ) % n i ) L ( j 1 ) % n i F ( L i ) ( j + 2 ) % n = ( L ( j + 1 ) % n i & L ( j 6 ) % n i ) L j i F ( L i ) ( j + 8 ) % n = ( L ( j + 7 ) % n i & L j i ) L ( j + 6 ) % n i

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 KT−4. (LT *, RT *) is denoted as the faulty output when inducing fault. KT−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 KT−4 represents the induced j%n bit of KT−4. Both the red thick line in LT−3 and RT−2 represent the corrupted bits. The two yellow thick lines in KT−3 represent the bit (j−3)%n and (j−4)%n of KT−3 respectively, which are all corrupted by the j%n bit of KT−4. And the thick lines show the cipher states and round keys which are necessary to retrieve KT−1 and KT−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 KT−1:
K T 1 = L T 2 F ( R T ) L T
Thus, in order to make use of the induced random bit faults in KT−4 to retrieve KT−1, we need to establish the relationship between induced faults and LT−2. We suppose the position of induced fault is the jth bit of KT−4. From Figure 1, it can be deduced that:
L T * = F ( L T 1 * ) K T 1 * R T 1 * = F ( R T * ) K T 1 * L T 2 * = F ( R T * ) K T 1 * K T 3 * F ( L T 3 * ) R T 3
Therefore, we can derive the following equation from the xor of LT and LT *:
L T L T * = F ( R T ) F ( R T * ) K T 1 K T 1 * K T 3 K T 3 * F ( L T 3 ) F ( L T 3 * )
If we move F(RT)⊕F(R *) in the Equation (6) to the left side, the Equation (6) can be rewritten as:
L T L T * F ( R T ) F ( R T * ) = K T 1 K T 1 * K T 3 K T 3 * F ( L T 3 ) F ( L T 3 * )

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 KT−4 that will corrupt the same position bit in LT−3 can be known, in other words, the jth bit of LT−3 is flipped. According to the Formula (3), we can identify that 3 distinct bits of F(LT−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 Li is induced, according to the Formula (3), it can be deduced that:
F ( L i * ) ( j + 1 ) % n = ( ( L j i 1 ) & L ( j 7 ) % n i ) L ( j 1 ) % n i F ( L i * ) ( j + 2 ) % n = ( L ( j + 1 ) % n i & L ( j 6 ) % n i ) L j i 1 F ( L i * ) ( j + 8 ) % n = ( L ( j + 7 ) % n i & ( L j i 1 ) ) L ( j + 6 ) % n i
From the Equation (8), we can know that once the jth bit of Li is flipped, the (j + 2)%n bit of F(Li) is also flipped. Due to the jth bit of LT−3 is flipped, it can be identified that the two bits (j + 1)%n and (j + 8)%n of F(LT−3) may be affected, and the bit (j + 2)%n of F(LT−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):
K T 3 K T 3 * = ( K T 4 > > > 3 ) ( K T 4 * > > > 3 ) ( K T 4 > > > 4 ) ( K T 4 * > > > 4 )
Equation (9) shows that one fault bit of KT−4 will affect 2 distinct bits of KT−3. In other words, the jth bit of KT−4 affects the bits (j − 3)%n and (j − 4)%n of KT−3.
( K T 3 K T 3 * ) ( j 3 ) % n = K T 4 ( K T 4 1 ) = 1 ( K T 3 K T 3 * ) ( j 4 ) % n = K T 4 ( K T 4 1 ) = 1
Further, the bit (j − 3)%n of KT−3 will affect the bits (j − 6)%n and (j − 7)% of KT−2, the bit (j − 4)%n of KT−3 will affect the bits (j − 7)%n and (j − 8)% of KT−2. As a result, the bits (j − 3)%n and (j − 4)%n of KT−3 will affect the bits (j − 6)%n and (j − 8)% of KT−2. Through similar analysis, we can deduce the affected bits in KT−1. The jth bit of KT−4 affects the bits of KT−3, KT−2 and KT−1 are given in Table 2: 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 (LTLT*F(RT)⊕F(RT*)). For convenience, we write (LTLT*F(RT)⊕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:
LFR j % n = K T 1 K T 1 1 = 1 LFR ( j 3 ) % n = K T 3 K T 3 1 = 1 LFR ( j 4 ) % n = K T 3 K T 3 1 = 1 LFR ( j 1 ) % n = K T 1 K T 1 1 = 1 LFR ( j 9 ) % n = K T 1 K T 1 1 = 1 LFR ( j 10 ) % n = K T 1 K T 1 1 = 1 LFR ( j 11 ) % n = K T 1 K T 1 1 = 1 LFR ( j 12 ) % n = K T 1 K T 1 1 = 1 LFR ( j + 2 ) % n = L j T 3 L j T 3 1 = 1 ,
as well as the following equations:
LFR ( j + 1 ) % n = ( L j T 3 & L ( j 7 ) % n T 3 ) ( ( L j T 3 1 ) & L ( j 7 ) % n T 3 ) LFR ( j + 8 ) % n = ( L ( j + 7 ) % n T 3 & L j T 3 ) ( L ( j + 7 ) % n T 3 & ( L j T 3 1 ) )
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.
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 KT−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 ←LTLT*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%nn-8 + i
8.          else
9.              j%ni - 8
10.          end
11.    end
12.  end

3.2.2. Retrieving LT−2 and KT−1

According to the formula (4), it is known that if someone wants to retrieve KT−1, she/he must obtain LT, RT and LT−2 first. Because (LT, RT) is the output of SIMON which could be obtained directly, so she/he only needs to obtain LT−2. From Figure 1, it can be deduced that:
R T * = F ( L T 2 * ) K T 2 * L T 3 *
Therefore, the following equation could be derived from the xor of RT and RT *:
R T R T * = F ( L T 2 ) F ( L T 2 * ) K T 2 K T 2 * L T 3 L T 3 *
From the discussion in Section 3.2.1, it is known that when the jth bit of KT−4 is flipped, the jth bit of LT−3 will also be flipped, so the bit (j + 2)%n of F(LT−3) is flipped. Because LT−2* can be written as:
L T 2 * = F ( L T 3 ) K T 3 * R T 3 ,
and the (j − 3)%n and (j − 4)%n of KT−3 are flipped (this conclusion can be obtained from Table 2), so there must be 3 bits which are flipped in LT−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:
( R T R T * ) ( j + 4 ) % n = ( L ( j + 3 ) % n T 2   &   L ( j 4 ) % n T 2 ) ( L ( j + 3 ) % n T 2   &   ( L ( j 4 ) % n T 2 1 ) ) 1 ( R T R T * ) ( j + 5 ) % n = ( L ( j + 4 ) % n T 2   &   L ( j 3 ) % n T 2 ) ( L ( j + 4 ) % n T 2 &   ( L ( j 3 ) % n T 2 1 ) ) ( R T R T * ) ( j 2 ) % n = ( L ( j 3 ) % n T 2 &   L ( j 10 ) % n T 2 ) ( ( L ( j 3 ) % n T 2 1 )   &   L ( j 10 ) % n T 2 ) 1 ( R T R T * ) ( j 3 ) % n = ( L ( j 4 ) % n T 2   &   L ( j 11 ) % n T 2 ) ( ( L ( j 4 ) % n T 2 1 )   &   L ( j 11 ) % n T 2 )
Through the Equation (16), we have made truth tables to illustrate the relationships between the bits in LT−2 and the bits in (RTRT*).
From Table 4, it can be seen that if ( R T 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, Table 6 and Table 7, it can be seen that if ( R T R T * ) ( j + 5 ) % n = 0 , then L ( j + 4 ) % n T 2 = 0 , otherwise it is 1; If ( R T R T * ) ( j 2 ) % n = 0 , then L ( j 10 ) % n T 2 = 1 , otherwise it is 0; If ( R T 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:
L ( j + 3 ) % n T 2 = ( R T R T * ) ( j + 4 ) % n 1 L ( j + 4 ) % n T 2 = ( R T R T * ) ( j + 5 ) % n L ( j 10 ) % n T 2 = ( R T R T * ) ( j 2 ) % n 1 L ( j 11 ) % n T 2 = ( R T R T * ) ( j 3 ) % n
Therefore, there are 4 bits (j + 3)%n, (j + 4)%n, (j − 10)%n and (j − 11)%n of KT−1 that could be recovered according to the Equations (17) and (4):
K ( j + 3 ) % n T 1 = L ( j + 3 ) % n T 2 F ( R T ) ( j + 3 ) % n L ( j + 3 ) % n T K ( j + 4 ) % n T 1 = L ( j + 4 ) % n T 2 F ( R T ) ( j + 4 ) % n L ( j + 4 ) % n T K ( j 10 ) % n T 1 = L ( j 10 ) % n T 2 F ( R T ) ( j 10 ) % n L ( j 10 ) % n T K ( j 11 ) % n T 1 = L ( j 11 ) % n T 2 F ( R T ) ( j 11 ) % n L ( j 11 ) % n T

3.2.3. Retrieving KT−2

After retrieving KT−1, we can reuse LT−2 with similar operations to those described in Section 3.2.2 to retrieve KT−2.
Now we obtain LT−2, because RT−1 = LT−2 and LT−1 = RT, in other words the output of the T−2 round of SIMON: (LT−1, RT−1) is obtained. As shown in Figure 1, because K T 2 = F ( R T 1 ) L T 1 L T 3 , if LT−3 is known, then KT−2 could be recovered. Based on the Equation (12), there are 2 bits (j − 7)%n and (j + 7)%n of LT−3 could be deduced, therefore two bits of KT−2 can be recovered when inducing one-bit fault in KT−4.

3.3. Extended Analysis

According to the Equation (18), we can obtain 4 bits of KT−1 which could be retrieved in theory by inducing one-bit fault in KT−4. Furthermore, 2 bits of KT−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 KT−1. Although paper [15] can also recover 2 bits of KT−2, but it can only recover 3.5 bits of KT−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:
m = 2 :   K k = c ( z j ) k m + 2 K k + 2   ( K k + 1 > > > 3 ) ( K k + 1 > > > 4 )
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, KT−1 and KT−2 can be retrieved by inducing faults in KT−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:
m = 3 :   K k = c ( z j ) i 3 + m K k + 3 ( K k + 2 > > > 3 ) ( K k + 2 > > > 4 ) m = 4 :   K k = c ( z j ) i 4 + m K k + 4 K k + 1 ( K k + 1 > > > 1 ) ( K k + 3 > > > 3 ) ( K k + 3 > > > 4 )
From the Equation (20), for m = 3, we know that if we can obtain KT−2 and KT−3, then the entire key of SIMON could be recovered. Therefore, we need to induce faults in two round keys: KT−4 and KT−6. The first inducing faults in KT−4 are used to retrieve both KT−1 and KT−2, the second inducing faults in KT−6 are used to only retrieve KT−3. For m = 4, we also need to induce faults in two round keys: KT−4 and KT−6. However, it is different from the case when m = 3, in this case, we need to induce faults in KT−6 to retrieve two round keys: KT−3 and KT−4. The key retrieving for SIMON family and specific fault locations are shown in Table 8, Table 9 and Table 10.

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 (LT, RT). Then we induced random one-bit faults in KT−4 to obtain the faulty ciphertexts (LT *, RT *). Finally, we used the proposed attack to retrieve KT−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 KT−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 KT−6 to retrieve only KT−3 instead of retrieving both KT−3 and KT−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(LT−3). We show how to retrieve 4 bits of KT−1 and 2 bits of KT−2 on average based on only one-bit fault induced in KT−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 LT−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.

Author Contributions

Conceive and structure of the concept of this paper, J.Z.; Resources, F.Z. and N.W.; Supervision, N.W.; Writing-original draft, J.Z.; Writing-review and editing, M.R.Y. and J.L.

Funding

This work was supported by National Natural Science Foundation of China (Nos. 61774086, 61376025), Natural Science Foundation of Jiangsu Province (No. BK20160806), Funding of Jiangsu Innovation Program for Graduate Education (No. KYLX16_0373), Research project of education department of Zhejiang province (No. Y201840245).

Acknowledgments

The authors would like to thank Xiaoqiang Zhang and Qiangjia Bi for their beneficial suggestions and comments.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Beaulieu, R.; Shors, D.; Smith, J.; Treatman-Clark, S.; Weeks, B.; Wingers, L. The SIMON and SPECK Families of Lightweight Block Ciphers. Cryptology ePrint Archive. Report 2013/404. 2013. Available online: http://eprint.iacr.org/ (accessed on 11 December 2018).
  2. Wang, Q.; Liu, Z.; Varıcı, K.; Sasaki, Y.; Rijmen, V.; Todo, Y. Cryptanalysis of Reduced Round SIMON32 and SIMON48. In Progress in Cryptology–INDOCRYPT 2014; ser. LNCS; Meier, W., Mukhopadhyay, D., Eds.; Springer International Publishing: New York, NY, USA, 2014; Volume 8885, pp. 143–160. [Google Scholar]
  3. Zhang, H.; Wu, W.; Wang, Y. Integral Attack Against Bit-Oriented Block Ciphers. In Information Security and Cryptology-ICISC 2015; ser. LNCS; Kwon, S., Yun, A., Eds.; Springer International Publishing: New York, NY, USA, 2015; Volume 9558, pp. 102–118. [Google Scholar]
  4. Abed, F.; List, E.; Lucks, S.; Wenzel, J. Differential Cryptanalysis of Round-Reduced SIMON and SPECK. In Fast Software Encryption; ser. LNCS; Cid, C., Rechberger, C., Eds.; Springer: Berlin/Heidelberg, Germany, 2014; Volume 8540, pp. 525–545. [Google Scholar]
  5. Wang, S. Related-key differential analysis of round-reduced Simeck. In Proceedings of the International Conference on IoT in Social, Mobile, Analytics and Cloud-I-SMAC, Palladam, India, 10–11 February 2017; pp. 834–838. [Google Scholar]
  6. Abed, F.; List, E.; Lucks, S.; Wenzel, J. Differential and Linear Cryptanalysis of Reduced-Round SIMON. Cryptology ePrint Archive. Report 2013/526. 2013. Available online: http://eprint.iacr.org/ (accessed on 11 December 2018).
  7. Alizadeh, J.; Bagheri, N.; Gauravaram, P.; Kumar, A.; Sanadhya, S.K. Linear Cryptanalysis of Round Reduced SIMON. Cryptology ePrint Archive. Report 2013/663. 2013. Available online: http://eprint.iacr.org/ (accessed on 11 December 2018).
  8. Tupsamudre, H.; Bisht, S.; Mukhopadhyay, D. Differential Fault Analysis on the families of SIMON and SPECK ciphers. In Proceedings of the International Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC 2014), Busan, Korea, 23 September 2014; IEEE Computer Society: Washington, DC, USA, 2014; pp. 40–48. [Google Scholar]
  9. Karaklajić, D.; Schmidt, J.M.; Verbauwhede, I. Hardware designer’s guide to fault attacks. IEEE Trans. Very Large Scale Integr. Syst. 2013, 21, 2295–2306. [Google Scholar] [CrossRef]
  10. Biham, E.; Shamir, A. Differential Fault Analysis of Secret Key Cryptosystems. In Advances in Cryptology-CRYPTO’97; ser. LNCS; Kaliski, B.S., Jr., Ed.; Springer International Publishing: New York, NY, USA, 1997; Volume 1294, pp. 513–525. [Google Scholar]
  11. Chong, H.K. Improved Differential Fault Analysis on AES Key Schedule. IEEE Trans. Inf. Forensics Secur. 2012, 7, 41–50. [Google Scholar]
  12. Huo, Y.; Zhang, F.; Feng, X.; Wang, L. Improved Differential Fault Attack on the Block Cipher SPECK. In Proceedings of the International Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC 2015), Saint Malo, France, 13 September 2015; IEEE Computer Society: Washington, DC, USA, 2015; pp. 28–34. [Google Scholar]
  13. Hemme, L. A Differential Fault Attack against Early Rounds of (triple-) DES. In International Workshop on Cryptographic Hardware and Embedded Systems-(CHES 2004); ser. LNCS; Joye, M., Quisquater, J.-J., Eds.; Springer International Publishing: New York, NY, USA, 2004; Volume 3156, pp. 254–267. [Google Scholar]
  14. Takahashi, J.; Fukunaga, T. Fault Analysis on SIMON Family of Lightweight Block Ciphers. In Information Security and Cryptology-ICISC 2014; ser. LNCS; Lee, J., Kim, J., Eds.; Springer International Publishing: New York, NY, USA, 2014; Volume 8949, pp. 175–189. [Google Scholar]
  15. Vasquez, J.D.C.G.; Borges, F.; Portugal, R.; Lara, P. An Efficient One-Bit Model for Differential Fault Analysis on Simon Family. In Proceedings of the International Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC 2015), Saint Malo, France, 13 September 2015; IEEE Computer Society: Washington, DC, USA, 2015; pp. 61–70. [Google Scholar]
  16. Chen, H.; Feng, J.; Rijmen, V.; Liu, Y.; Fan, L.; Li, W. Improved Fault Analysis on SIMON Block Cipher Family. In Proceedings of the International Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC 2016), Santa Barbara, CA, USA, 16 August 2016; IEEE Computer Society: Washington, DC, USA, 2016; pp. 16–24. [Google Scholar]
Figure 1. Fault propagation when the jth bit KT−4 is randomly corrupted.
Figure 1. Fault propagation when the jth bit KT−4 is randomly corrupted.
Electronics 08 00093 g001
Table 1. Parameters of the SIMON family.
Table 1. Parameters of the SIMON family.
Cipher SIMON2n/mnBlock Size 2nKey Size mnWord Size nKey Words mConst SeqRounds T
SIMON 32/643264164z032
SIMON 48/724872243z036
SIMON 48/96964z136
SIMON 64/966496323z242
SIMON 64/1281284z344
SIMON 96/969696482z252
SIMON 96/1441443z354
SIMON 128/128128128642z268
SIMON 128/1921923z369
SIMON 128/2562564z472
Table 2. The jth bit of KT−4 affects the bits of KT−3, KT−2 and KT−1.
Table 2. The jth bit of KT−4 affects the bits of KT−3, KT−2 and KT−1.
The Position of Induced FaultKey Words: mAffected Bits
jth bit of KT−44KT−3: j − 3, j − 4
KT−2: j − 6, j − 8
KT−1: j, j − 1, j − 9, j − 10, j − 11, j − 12
3KT−3: j − 3, j − 4
KT−2: j − 6, j − 8
KT−1: j, j − 9, j − 10, j − 11, j − 12
2KT−3: j − 3, j − 4
KT−2: j, j − 6, j − 8
KT−1: j − 9, j − 10, j − 11, j − 12
Table 3. The jth bit of KT−4 affects the bits of LFR.
Table 3. The jth bit of KT−4 affects the bits of LFR.
The Position of Induced FaultKey Words: mThe Value of Bits in LFR(LFR = LTLT *F(RT)⊕F(RT*)
jth bit of KT−441: j, j − 1, j − 3, j − 4, j − 9, j − 10, j − 11, j − 12, j + 2
may be 1: j + 1, j + 8
31: j, j − 3, j − 4, j − 9, j − 10, j − 11, j − 12, j + 2
may be 1: j + 1, j + 8
21: j − 3, j − 4, j − 9, j − 10, j − 11, j − 12, j + 2
may be 1: j + 1, j + 8
Table 4. The relationship between the bit L ( j + 3 ) % n T 2 and ( R T R T * ) ( j + 4 ) % n .
Table 4. The relationship between the bit L ( j + 3 ) % n T 2 and ( R T R T * ) ( j + 4 ) % n .
L ( j + 3 ) % n T 2 L ( j 4 ) % n T 2 L ( j 4 ) % n T 2 1 ( R T R T * ) ( j + 4 ) % n
0011
0101
1010
1100
Table 5. The relationship between the bit L ( j + 4 ) % n T 2 and ( R T R T * ) ( j + 5 ) % n .
Table 5. The relationship between the bit L ( j + 4 ) % n T 2 and ( R T R T * ) ( j + 5 ) % n .
L ( j + 4 ) % n T 2 L ( j 3 ) % n T 2 L ( j 3 ) % n T 2 1 ( R T R T * ) ( j + 5 ) % n
0010
0100
1011
1101
Table 6. The relationship between the bit L ( j 10 ) % n T 2 and ( R T R T * ) ( j 2 ) % n .
Table 6. The relationship between the bit L ( j 10 ) % n T 2 and ( R T R T * ) ( j 2 ) % n .
L ( j 10 ) % n T 2 L ( j 3 ) % n T 2 L ( j 3 ) % n T 2 1 ( R T R T * ) ( j 2 ) % n
0011
0101
1010
1100
Table 7. The relationship between the bit L ( j 11 ) % n T 2 and ( R T R T * ) ( j 3 ) % n .
Table 7. The relationship between the bit L ( j 11 ) % n T 2 and ( R T R T * ) ( j 3 ) % n .
L ( j 11 ) % n T 2 L ( j 4 ) % n T 2 L ( j 4 ) % n T 2 1 ( R T R T * ) ( j 3 ) % n
0010
0100
1011
1101
Table 8. Experiment results for the average number of the fault inductions to retrieve KT−1/LT−2.
Table 8. Experiment results for the average number of the fault inductions to retrieve KT−1/LT−2.
Word Size: nAvg. No. of the Fault Inductions At least No. of the Fault Inductions in Theory:
Random Byte Fault ModelRandom Bit Fault ModelRandom Byte Fault ModelRandom Bit Fault Model
[8][8][15]This paper[8]: n/8[8]: n/2[15]: n/3.5This Paper: n/4
1662515.2611.12284.574
2494329.7019.823126.866
32136244.1929.254169.148
482110477.0249.6762413.7112
6430150110.8171.6183218.2916
Table 9. Comparison of the experimental results of the fault inductions.
Table 9. Comparison of the experimental results of the fault inductions.
SIMON 2n/mnAvg. No. of the Fault Inductions
Random Byte Fault ModelRandom n-Bit Fault ModelRandom Bit Fault Model
[8][16][14][8][15]This Paper
SIMON32/6424 12.20101.7250.8550.32
SIMON48/7227 9.91130.7887.1962.78
SIMON48/9636 13.22174.3787.1985.86
SIMON64/963931.5710.45189.44126.2991.57
SIMON64/12852 13.93252.58126.29124.72
SIMON96/964235.087.46210.24105.12104.00
SIMON96/1446350.8411.19315.36210.24153.64
SIMON128/1286050.557.82299.68149.84148.51
SIMON128/1929072.8811.73449.52299.68220.15
SIMON128/256120104.8215.64599.36299.68297.02
Table 10. Comparison of the fault locations of differential fault analysis (DFA) on SIMON family.
Table 10. Comparison of the fault locations of differential fault analysis (DFA) on SIMON family.
SIMON2 n/mnFault Locations of DFA on SIMON Family
Random Byte Fault ModelRandom n-Bit Fault ModelRandom Bit Fault Model
[8][16][14][8][15]This Paper
SIMON32/64L27, L28, L29, L30L27L27, L28, L29, L30L27, L28, L29, L30L27, L29K26, K28
SIMON48/72L32, L33, L34L32L32, L33, L34L32, L33, L34L32, L33K30, K32
SIMON48/96L31, L32, L33, L34L31L31, L32, L33, L34L31, L32, L33, L34L31, L33K30, K32
SIMON64/96L38, L39, L40L38L38, L39, L40L38, L39, L40L38, L39K36, K38
SIMON64/128L39, L40, L41, L42L39L39, L40, L41, L42L39, L40, L41, L42L39, L41K38, K40
SIMON96/96L49, L50L49L49, L50L49, L50L49K48
SIMON96/144L50, L51, L52L50L50, L51, L52L50, L51, L52L50, L51K48, K50
SIMON128/128L65, L66L65L65, L66L65, L66L65K64
SIMON128/192L65, L66, L67L65L65, L66, L67L65, L66, L67L65, L66K63, K65
SIMON128/256L67, L68, L69, L70L67L67, L68, L69, L70L67, L68, L69, L70L67, L69K66, K68

Share and Cite

MDPI and ACS Style

Zhang, J.; Wu, N.; Zhou, F.; Yahya, M.R.; Li, J. A Novel Differential Fault Analysis on the Key Schedule of SIMON Family. Electronics 2019, 8, 93. https://doi.org/10.3390/electronics8010093

AMA Style

Zhang J, Wu N, Zhou F, Yahya MR, Li J. A Novel Differential Fault Analysis on the Key Schedule of SIMON Family. Electronics. 2019; 8(1):93. https://doi.org/10.3390/electronics8010093

Chicago/Turabian Style

Zhang, Jinbao, Ning Wu, Fang Zhou, Muhammad Rehan Yahya, and Jianhua Li. 2019. "A Novel Differential Fault Analysis on the Key Schedule of SIMON Family" Electronics 8, no. 1: 93. https://doi.org/10.3390/electronics8010093

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop