General Differential Fault Attack on PRESENT and GIFT Cipher With Nibble

Lightweight block cipher PRESENT is an algorithm with SPN structure. Due to its excellent hardware performance and simple round function design, it can be well applied to Internet of things terminals with limited computing resources. As an improved cipher of PRESENT, GIFT is similar in structure to PRESENT and has been widely concerned by academia and industry. This article studies the P permutation law of PRESENT and GIFT, and presents a general differential fault attack(DFA) method with their differential characteristics. For PRESENT, this article chooses to inject a nibble fault before the 30^th and 31^st rounds of S-box operation. A total of 32 nibble fault ciphertexts are needed to recover the original key. The computational complexity and data complexity are 2^10.94 and 2⁸, respectively. For GIFT, this article chooses to inject a nibble fault before the 25^th, 26^th, 27^th and 28^th rounds of S-box operation. A total of 64 nibble fault ciphertexts are needed to recover the original key. The computational complexity and data complexity are 2^11.91 and 2⁹, respectively. Compared with other public cryptoanalysis results of PRESENT and GIFT, this general attack method has great advantages. In this article, the DFA of GIFT is experimentally verified and the effectiveness is proved. These experiments have been done on a personal computer and run in a very reasonable time(around 500ms).

SECTION I. Introduction

DFA [1] is a new cryptanalysis method proposed by E. Beniham and A. Hamir based on a combination of mathematical and physical methods in 1997. This method has been applied to many block ciphers, like FOX [2], SMS4 [3], AES [4], LED [5], SIMON [6] etc. Meanwhile, with the development of the Internet of things(IoT), a large number of various lightweight block ciphers have emerged, and have proved its efficiency in resource-constrained environments such as RFID tags and wireless sensor networks(WSN). Many scholars have also conducted DFA on LEA [7], PRINCE [8], TWINE [9] and other ciphers.

PRESENT [10] is a lightweight cryptography algorithm put forward by A. Bogdanov et al. at the CHES 2007 conference in 2007. PRESENT uses SPN structure, which has 80-bit or 128-bit key with 64 bits block length. Since then, the security of PRESENT have been analyzed by many scholars. Wang [11] published a differential attack on PRESENT in 2008 with both computational and data complexity of 2⁶⁴. Subsequently, in CT-RSA 2009, Collard and Standaert [12] published an Saturation cryptanalysis of PRESENT, with a computational complexity of 2²⁰ and a data complexity of 2³⁶. In FSE 2012, Wang et al. [13] proposed the Structure attack method. Reference [14] illustrates the Biclique cryptanalysis results of PRESENT by Zheng Gong et al., and the computational complexity and data complexity are 2^78.9 and 2⁶⁴, respectively [15] illustrates the impossible differential attack on PRESENT by Tezcan. C, with the computational complexity and data complexity of 2^62.62 and 2^63.86, respectively. Reference [16] illustrates that Ya Tian et al. analyzed PRESENT by using the methods of multi-differential-input, single-differential-output and single-differential-input, multi-differential-output. Reference [17] illustrates that Liu et al. adopted the linear cryptanalysis method in 2016, and the computational complexity and data complexity were 2³⁶ and 2³², respectively. In 2017, Liu et al. [17] published the multi-differential cryptanalysis for PRESENT, with the computational complexity and data complexity of 2^57.6 and 2⁶¹, respectively. In 2019, Chen et al. [19] carried out a single-byte DFA on PRESENT, with a computational complexity of 2³¹. In addition, [20] discussed the hardware performance of PRESENT, and Petr Moucha et al. proposed a dummy rounds schemes as a DPA countermeasure in PRESENT [21].

In order to avoid the design defects of PRESENT mentioned above, on the occasion of the 10^th anniversary of PRESENT, Banik et al. [22] proposed a new lightweight block cipher named GIFT in CHES 2017. GIFT has a key length of 128 bits and is divided into 64 bits or 128 bits according to the block length with the number of encryption rounds of 28 and 40 respectively. GIFT, an improved cipher of PRESENT, has a similar structure of PRESENT and can save a lot of computational resources and improve computing speed. In this article, the author analyzed the resistance effect of GIFT under such attack methods as differential cryptanalysis, linear cryptanalysis, invariant subspace attack and algebraic attack. In addition, GIFT also improves the P permutation layer diffusivity of PRESENT to avoid the DFA in [19]. Currently, there are few cryptanalyses of GIFT in the public literature, mainly including Biclique cryptanalysis [23], [24], differential cryptanalysis [25], [26], side-channel fault attack [27], [28] and so on. In addition, Jati et al. [29] analyzed the threshold implementation of GIFT, and Dalmasso et al. [30] analyzed the hardware implementation in FPGA.

A. Our Contribution

We proposed a general DFA method for PRESENT and GIFT by analyzing the displacement law of P permutation layer and S-box differential property. Firstly, the differential properties of the two ciphers were analyzed, and the number of differential function solutions was counted by the differential distribution table of the S-boxes. Secondly, we found that when bits are shifted in the P permutation layer, four bits of each nibble will spread into four different nibbles based on the knowledge of PRESENT and GIFT. Then, we found the appropriate fault injection location according to the obtained diffusion law, and then recovered the key by combining the differential property. Furthermore, we calculated the computational complexity and data complexity of this attack method. For PRESENT, the computational and data complexity are 2^10.94 and 2⁸, respectively. For Gift, computational and data complexity are 2^11.91 and 2⁹, respectively. These results are superior to the existing public literature. Finally, we experimented this attack method on GIFT for 30 times, and it took an average of 87 nibbles faults to recover all the original keys with 500ms attack time.

This attack method mainly studies the PRESENT with a key of 80 bits (PRESENT means PRESENT-80 unless otherwise specified below) and the GIFT with a block length of 64 bits (GIFT means GIFT-64 unless otherwise specified below). It also proposes the optimized DFA. In this article, the remaining organization structure is as follows: Section II makes a brief introduction to the PRSENT and GIFT, and Section III analyzes their S-box differential and P displacement law. Section IV is the DFA principle and steps of PRESENT and GIFT, and Section V part analyses the computational complexity and data complexity of the attack method on these two ciphers. Section VI is the experimental results of DFA on GIFT. At last, Section VII will be a conclusion.

SECTION II. PRESENT and GIFT

A. Symbols and Terminology

In order to better illustrate the encryption and attack process of the two ciphers, the common symbols used in the analysis of the two are defined as follows:

• $B_{i}$ : 64-bit input of the $i^{\mathrm {th}}$ round;

• $x_{j}^{i}$ : 4-bit input value of S-box in position $j$ of the $i^{\mathrm {th}}$ round;

• $\Delta x_{j}^{i}$ : 4-bit input differential value of S-box in position $j$ of the $i^{\mathrm {th}}$ round;

• $\Delta X_{i}$ : 64-bit input differential value of S-box of the $i^{\mathrm {th}}$ round;

• $\Delta y_{j}^{i}$ : 4-bit output differential value of S-box in position $j$ of the $i^{\mathrm {th}}$ round;

• $\Delta Y_{i}$ : 64-bit output differential value of the S-box of the $i^{\mathrm {th}}$ round;

• $K_{i}$ : 64-bit round key involved round function calculation of the $i^{\mathrm {th}}$ round;

• $R_{k_{j}}^{i}$ : 4-bit round key in position $j$ of the $i^{\mathrm {th}}$ round;

• $C_{i}$ : 64-bit correct ciphertext of the $i^{\mathrm {th}}$ round;

• $C_{i}^{\ast }$ : 64-bit incorrect ciphertext of the $i^{\mathrm {th}}$ round;

• $\Delta C_{i}^{\ast }$ : 64-bit differential value between the correct ciphertext and the incorrect ciphertext;

• $c_{j,i}$ : 4-bit correct ciphertext in position $j$ of the $i^{\mathrm {th}}$ round;

• $c_{j,i}^{\ast }$ : 4-bit incorrect ciphertext in position $j$ of the $i^{\mathrm {th}}$ round;

• $\Delta c_{j,i}^{\ast }$ : 4-bit differential value between the 4-bit correct ciphertext and the 4-bit incorrect ciphertext in position $j$ of the $i^{\mathrm {th}}$ round;

• $S(\cdot)$ : S-box operator;

• $S^{-1}(\cdot)$ : S-box inverse operator;

• $P(\cdot)$ : operator of P permutation layer;

• $P^{-1}(\cdot)$ : inverse operator of P permutation layer;

• $a\leftarrow b$ : value of b is assigned to a;

• $a\vert \vert b$ : the cascade of data a and data b;

• $a\oplus b$ : data a and data b are xor by bit;

• $\ll <$ : cyclic shift to the left;

• $\gg >$ : cyclic shift to the right;

• $RC^{i}$ : counter number of the $i^{\mathrm {th}}$ round;

B. Encryption Processes of PRESENT and GIFT

PRESENT and GIFT are both block ciphers based on SPN structure, where PRESENT iterates 31 rounds in the whole encryption process while GIFT only iterates 28 rounds. Take the flow chart of PRESENT encryption as an example, as shown in Fig. 1.

FIGURE 1.

Flow chart of PRESENT encryption.

1) PRESENT Encryption Process

For PRESENT, the encryption process can be divided into three parts: the round key or layer, the nonlinear S-box substitution layer and the linear P permutation layer.

1. Round key xor layer: the input of the $i^{\mathrm {th}}$ round $B_{i} =b_{63}^{i} b_{62}^{i} \cdots b_{2}^{i} b_{1}^{i} b_{0}^{i}$ and the 64-bit round key $K_{i} =k_{63}^{i} k_{62}^{i} \cdots k_{2}^{i} k_{1}^{i} k_{0}^{i}$ of the $i^{\mathrm {th}}$ round carries out xor operation, and the output is $B_{i}^{\prime }$ .

   $$\begin{equation*} B_{i}^{\prime } =B_{i} \oplus K_{i},\quad (0\le i\le 31)\tag{1}\end{equation*}$$

2. Nonlinear S-box substitution layer: divide the above 64-bit output $B_{i}^{\prime }$ into 16 4-bit nibbles represented by $W_{15} W_{14} \cdots W_{0}$ , where $W_{j} =b_{4j+3} \vert \vert b_{4j+2} \vert \vert b_{4j+1} \vert \vert b_{4j},(0\le j\le 15)$ . PRESENT requires 16 identical 4-bit S-boxes with 4-bit inputs and 4-bit outputs. And $W_{j}$ were substituted with the 16 S-boxes respectively, to obtain $S(W_{j})$ . The calculation results of S-box can be obtained from Table 1:

3. Linear P permutation layer: after obtaining the S-box substitution value, each bit is linearly rearranged according to the P permutation table to obtain $P(\cdot)$ . The permutation result of the P permutation layer can be obtained the Table 2 below.

TABLE 1 S-Box Substitution of PRESENT

TABLE 2 P Permutation Layer of PRESENT

2) GIFT Encryption Process

For GIFT, the encryption process can also be divided into three layers: the nonlinear S-box substitution layer, the linear P permutation layer, the key and constant xor layer. The S-box substitution layer and P permutation layer of GIFT are similar to the PRESENT transformation rule. Except for the transformation value, the S-box substitution table and P layer replacement table of GIFT are given, as shown in Table 3 and Table 4 respectively:

TABLE 3 S-Box Substitution of GIFT

TABLE 4 P Permutation Layer of GIFT

For the key and constant xor layer of GIFT, it contains two parts which are round key and round constant. Round key xor means that 32 bits are selected from the 128-bit key set as the round key for xor operation, and the extracted key is divided into two parts, which are expressed as:

$$\begin{equation*} K_{i} =U_{i} \vert \vert V_{i} =u_{15}^{i} \cdots u_{0}^{i} \vert \vert v_{15}^{i} \cdots v_{0}^{i}\tag{2}\end{equation*}$$

Perform xor operation between $U_{i}$ and $V_{i}$ on the output of P permutation layer respectively, namely:

$$\begin{equation*} b_{4j+1}^{i} \!\leftarrow \! b_{4j+1}^{i} \!\oplus \! u_{r}^{i},\quad b_{4j}^{i} \!\leftarrow \! b_{4j}^{i} \!\oplus \! v_{r}^{i},~0\!\le \! r\!\le \! 15\tag{3}\end{equation*}$$

The cyclic constant xor operation refers to the xor bit 63, bit 23, bit 19, bit 15, bit 11, bit 7 and bit 3 from the P permutation layer between a bit value “1” and a length of 6 bits round constant $L_{i} =l_{5}^{i} l_{4}^{i} l_{3}^{i} l_{2}^{i} l_{1}^{i} l_{0}^{i}$ , namely:

$$\begin{align*} b_{63}^{i}\leftarrow&b_{63}^{i} \oplus 1,\quad b_{23}^{i} \leftarrow b_{23}^{i} \oplus l_{5}^{i} \\ b_{19}^{i}\leftarrow&b_{19}^{i} \oplus l{}_{4}^{i},\quad b_{15}^{i} \leftarrow b_{15}^{i} \oplus l{}_{3}^{i} \\ b_{11}^{i}\leftarrow&b_{11}^{i} \oplus l{}_{2}^{i},\quad b_{7}^{i} \leftarrow b_{7}^{i} \oplus l{}_{1}^{i} \\ b_{3}^{i}\leftarrow&b_{3}^{i} \oplus l{}_{0}^{i}\tag{4}\end{align*}$$

C. Round Key Update Scheme

1) Round Key Update Scheme of PRESENT

The key expansion method of PRESENT includes cyclic shift and S-box substitution. Firstly, the initial key $K_{0} =k_{79}^{0} k_{78}^{0} \cdots k_{2}^{0} k_{1}^{0} k_{0}^{0}$ is saved in the shift register. The round key of the $i^{\mathrm {th}}$ round is to take the left 64bit in the current register:

$$\begin{equation*} K_{i} =k_{63}^{i} k_{62}^{i} \cdots k_{2}^{i} k_{1}^{i} k_{0}^{i} =k_{79}^{i} k_{78}^{i} \cdots k_{21}^{i} k_{20}^{i} k_{19}^{i}\tag{5}\end{equation*}$$

The specific steps are as follows:

1. First, loop the key to the left 61 bits in the register:

   $$\begin{equation*} K\ll < 61\tag{6}\end{equation*}$$

2. Then, the left 4-bit value was used for S-box substitution operation:

   $$\begin{equation*} K[{79-76}]\leftarrow S(K[{79-76}])\tag{7}\end{equation*}$$

3. Finally, operate the bitwise xor on $k_{19} k_{18} k_{17} k_{16} k_{15}$ in the round key and the counter number:

   $$\begin{equation*} K[{19-15}]\leftarrow K[{19-15}]\oplus RC^{i}\tag{8}\end{equation*}$$

2) Round Key Update Scheme of GIFT

a: Round Key

The round key extraction rule of GIFT is extracted first and then updated. The updating method is as follows:

$$\begin{equation*} t_{7} \vert \vert t_{6} \vert \vert \cdots \vert \vert t_{1} \vert \vert t_{0} \leftarrow t_{1} \gg >2\vert \vert t_{0} \gg >12\vert \vert \cdots \vert \vert t_{3} \vert \vert t_{2}\tag{9}\end{equation*}$$ where $t$ is a 16-bit word.

b: Round Constant

The initial value of the 6-bit round constant is 0, which needs to be updated through a 6-bit shift register. The update function is as follows:

$$\begin{equation*} (l_{5},l_{4},l_{3},l_{2},l_{1},l_{0})\leftarrow (l_{4},l_{3},l_{2},l_{1},l_{0},l_{5} \oplus l_{4} \oplus l_{1})\tag{10}\end{equation*}$$

Round constants of different rounds are in the Table 5.

TABLE 5 Round Constants of GIFT

SECTION III. Structral Properties of PRESENT and GIFT

A. Structral Properties of PRESENT

1) S-Box Differential Property

If there are $\Delta \alpha =\Gamma _{2}^{4}$ , $\Delta \beta =\Gamma _{2}^{4}$ , $m=\Gamma _{2}^{4}$ . $\Delta \alpha$ is the differential input of S-box, and $\Delta \beta$ is the differential output of S-box, which satisfy: $S(m\oplus \Delta \alpha)\oplus S(m)=\Delta \beta$ . Through calculation, the S-box differential property of PRESNET is obtained as shown in Table 6. Num($\Delta \alpha, \Delta \beta$ ) is the number of $m$ that satisfy the equation $S(m\oplus \Delta \alpha)\oplus S(m)=\Delta \beta$ .

TABLE 6 S-Box Differential Distribution Property of PRESENT

When $Num(\Delta \alpha,\Delta \beta)=0$ is satisfied, $S(m\oplus \Delta \alpha)\oplus S(m)=\Delta \beta$ has no solution. As can be seen from Table 6, of having no solution is 62.1%. Similarly, the probability of the equation having two solutions is 28.2%, the probability of the equation having four solutions is 9.3%, and the probability of the equation having 16 solutions is 0.4%. If we only consider the case where the equation has solutions, namely $Num(\Delta \alpha,\Delta \beta)\ne 0$ , we can get that 74.2% of the probability equation has two solutions, 24.1% of the probability equation has four solutions, and 1.1% of the probability equation has 16 solutions. Therefore, the average number of solutions can be calculated to be 2.648(= 1.484 + 0.998 + 0.276).

2) P Permutation Layer Property

Every four consecutive nibbles are divided into a group(from left to right are Group1, Group 2, Group 3 and Group 4), then each nibble will spread to four different nibbles after P permutation layer. In addition, 4 nibbles from the same group will be diffused to the same four nibbles, and nibbles diffused by different groups will not cross and repeat, so the position of nibble fault can be determined by positions of the diffusion. The specific diffusion locations for each group of nibbles are shown in Table 7:

TABLE 7 P Layer Law of PRESENT

According to the characteristics of four nibbles diffusion positions in each group, the import position of the fault can be determined. Therefore, this article proposes a method of nibble DFA on PRESENT in Chapter IV.

B. Sructual Properties of GIFT

1) S-Box Differential Property

In the same way that PRESENT differential properties were analyzed, GIFT’s S-box differential distribution law can be obtained, as shown in Table 8.

TABLE 8 S-Box Differential Distribution Property of GIFT

Similarly, when $Num(\Delta \alpha,\Delta \beta)=0$ is satisfied, $S(m\oplus \Delta \alpha)\oplus S(m)=\Delta \beta$ has no solution. As can be seen from Table 8, of having no solution is 61.3%. And then, the probability of the equation having two solutions is 30.5%, the probability of the equation having four solutions is 3.1%, the probability of the equation having four solutions is 0.8%, and the probability of the equation having 16 solutions is 0.4%. If we only consider the case where the equation has solutions, namely $Num(\Delta \alpha,\Delta \beta)\ne 0$ , we can get that 78.8% of the probability equation has two solutions, 18.2% of the probability equation has four solutions, 2.0% of the probability equation has four solutions, and 1.0% of the probability equation has 16 solutions. Therefore, the average number of solutions can be calculated to be 2.584(= 1.576 + 0.728 + 0.120 + 0.160).

2) Permutation Layer Property

According to Table 4, the displacement law of P permutation layer of GIFT is analyzed. The specific diffusion locations for each group of nibbles are shown in Table 9:

TABLE 9 P Layer Law of GIFT

According to the characteristics of four nibbles diffusion positions in each group, the import position of the fault can be determined. Therefore, this article proposes a method of nibble DFA on GIFT in Chapter IV.

SECTION IV. Nibble Differential Fauaul Attacks on PRESENT and GIFT

A. Attack Basic Assumption

In order to make a better analysis, two basic assumptions are put forward before introducing concept of attack:

1. The fault can be imported into nibble of any round with the unknown fault value and position, then the correct ciphertext $C_{i}$ and error ciphertext $C_{i}^{\ast }$ can be obtained.

2. For same plaintext and round key, random nibble faults can be induced at same times and locations of iterations, then the corresponding error ciphertext $C_{i}^{\ast }$ can be acquired.

B. DFA on PRESENT

1) Attack Model and Principle of PRESENT

Because PRESENT’s S-box is a nonlinear substitution of 4-bit input and output, this article chooses to import a nibble fault to construct attack model. Depending on the attack hypothesis and the actual situation, we usually only get the last round of ciphertext. Therefore, we first chose to import random failure in the 31^th round before the S-box operation.

After randomly choosing a set of plaintext and key and get the correct ciphertext by encryption. The fault is imported in the any nibble group of the 31^th round, and some features of ciphertext are obtained by combining the characteristics of DFA. Furthermore, through the reverse process of the encryption, the partial round key is deduced. By repeating the process several times with the same ciphertext, the partial key will be recovered in a unique value. And then, attack the other three groups of nibbles of the 31^th round in the same way until the 64-bit round key is recovered. We can reverse the ciphertext of the 30^th round according to the key of 31^th round, and then use the same attack method to recover the key of the 30^th round. According to the PRESENT key update scheme, the complete 80-bit original key can be derived by two consecutive round keys.

2) Specific Steps of Attack

1. Generate plaintext $B$ and a round key $K$ randomly, and the correct ciphertext $C_{31}$ is obtained after 31 rounds of encryption by PRESENT.

2. Use the original plaintext $B$ and key $K$ for encryption. In the 31^th round of encryption, a random nibble fault is induced in the S-box of PRESENT. The wrong ciphertext $C_{31}^{\ast }$ is obtained and the differential operation with the correct ciphertext in the 31^st round is performed to obtain the differential error ciphertext:

   $$\begin{equation*} \Delta C_{31}^{\ast } =C_{31} \oplus C_{31}^{\ast }\tag{11}\end{equation*}$$

   Import a fault in the first nibble on the left side $x^{15}_{31}$ of Group 1 as an example, and output the differential result in the form of ($\Delta c_{15,31}^{\ast }$ , 0, 0, 0, $\Delta c_{11,31}^{\ast }$ , 0, 0, 0, $\Delta c_{7,31}^{\ast }$ , 0, 0, 0, $\Delta c_{3,31}^{\ast }$ , 0, 0, 0).

3. Through the correct ciphertext and the wrong ciphertext, find the fault S-box, and differential output:

   $$\begin{equation*} \Delta Y_{31} =P^{-1}(\Delta C_{31}^{\ast })\tag{12}\end{equation*}$$

4. Because it is a fault attack on the input of the first S-box, $\Delta Y_{31}$ has only one non-zero nibble $\Delta y_{31}^{15}$ . List the S-box differential equation:

   $$\begin{equation*} \Delta y_{31}^{15} =S(x_{31}^{15})\oplus S(x_{31}^{15} \oplus \Delta x_{31}^{15})\tag{13}\end{equation*}$$

   $\Delta x_{31}^{15}$ has 2⁴ = 16 possible values, and then 16 values are exhausted and solve the values of $x_{31}^{15}$ , which satisfy (13). Furthermore, store the calculated $x_{31}^{15}$ in a set M₁.

5. According to the analysis of the S-box property of PRESENT(Table 6), there may be more than one matching result, so attack steps (2)~(4) will be continuously repeated until set M₁ to reserve only one nibble, which is the correct $x_{31}^{15}$ .

6. Repeat (2)~(5), and attack the other three nibbles in Group 1 in the same way to get other 4-bit input differential value of S-box $x_{31}^{11},x_{31}^{7}$ and $x_{31}^{3}$ .

7. Repeat (2)~(6), and attack other nibbles in Group 2, Group 3 and Group 4 in turn to until the 64-bit input differential value of S-box $\Delta X_{31}$ is recovered.

8. Through the following formula, 64-bit round key $K_{31}$ is obtained.

   $$\begin{equation*} K_{31} =P(S(\Delta X_{31}))\oplus C_{31}\tag{14}\end{equation*}$$

9. Similarly, DFA on PRESENT in the 30^th round, and steps (2)~(8) are repeated to recover the key $K_{30}$ .

10. Based on the recovered two successive rounds of key $K_{30}$ and $K_{31}$ , the PRESENT original 80-bit key is rolled out.

C. DFA on GIFT

1) Attack Model and Principle of GIFT

Because GIFT’s S-box is a nonlinear substitution of 4-bit input and output, this article chooses to import a nibble fault to construct attack model. Similar to PRESENT, we first chose to import random failure in the 28^th round before the S-box operation.

In the same way, the failure is imported at the 28^th round of the GIFT encryption process and the 32-bit round key is recovered using the same method as PRESENT. According to the GIFT key update scheme, a complete 128-bit original key can be derived by four consecutive round keys. Therefore, the 128-bit original key of GIFT is derived by using the same steps to obtain their round keys for the 25^th, 26^th and 27^th rounds respectively.

2) Specific Steps of Attack

1. Generate plaintext $B$ and a round key $K$ randomly, and the correct ciphertext $C_{28}$ is obtained after 28 rounds of encryption by GIFT.

2. Use the original plaintext $B$ and key $K$ for encryption. In the 28^th round of encryption, a random nibble fault is induced in the S-box of GIFT. The wrong ciphertext $C_{28}^{\ast }$ is obtained and the differential operation with the correct ciphertext in the 28^th round is performed to obtain the differential error ciphertext:

   $$\begin{equation*} \Delta C_{28}^{\ast } =C_{28} \oplus C_{28}^{\ast }\tag{15}\end{equation*}$$

   Import a fault in the first nibble on the left side $x^{15}_{28}$ of Group 1 as an example, and output the differential result in the form of ($\Delta c_{15,28}^{\ast }$ , 0, 0, 0, $\Delta c_{11,28}^{\ast }$ , 0, 0, 0, $\Delta c_{7,28}^{\ast }$ , 0, 0, 0, $\Delta c_{3,28}^{\ast }$ , 0, 0, 0).

3. Through the correct ciphertext and the wrong ciphertext, find the fault S-box, and differential output:

   $$\begin{equation*} \Delta Y_{28} =P^{-1}(\Delta C_{28}^{\ast })\tag{16}\end{equation*}$$

4. Because it is a fault attack on the input of the first S-box, $\Delta Y_{28}$ has only one non-zero nibble $\Delta y_{28}^{15}$ . List the S-box differential equation:

   $$\begin{equation*} \Delta y_{28}^{15} =S(x_{28}^{15})\oplus S(x_{28}^{15} \oplus \Delta x_{28}^{15})\tag{17}\end{equation*}$$

   $\Delta x_{28}^{15}$ has 2⁴ = 16 possible values, and then 16 values are exhausted and solve the values of $x_{28}^{15}$ , which satisfy (17). Furthermore, store the calculated $x_{28}^{15}$ in a set M₂.

5. According to the analysis of the S-box property of GIFT(Table 8), there may be more than one matching result, so attack steps (2)~(4) will be continuously repeated until set M₂ to reserve only one nibble, which is the correct $x_{28}^{15}$ .

6. Repeat (2)~(5), and attack the other three nibbles in Group 1 in the same way to get other 4-bit input differential value of S-box $x_{28}^{14},x_{28}^{13}$ and $x_{28}^{12}$ .

7. Repeat (2)~(6), and attack other nibbles in Group 2, Group 3 and Group 4 in turn to until the 64-bit input differential value of S-box $\Delta X_{28}$ is recovered.

8. Through the following formula, round key $K_{28}$ is obtained.

   $$\begin{equation*} K_{28} =P(S(\Delta X_{28}))\oplus C_{28}\tag{18}\end{equation*}$$

9. Similarly, DFA on GIFT in the 27^th, 26^th and 25^th rounds, and steps (2)~(8) are repeated to recover the keys $K_{27}$ , $K_{26}$ and $K_{25}$ .

10. Based on the recovered four successive rounds of key $K_{25}$ , $K_{26}$ , $K_{27}$ and $K_{28}$ , the GIFT original 128-bit key is rolled out.

SECTION V. Complexity Analysis

A. Complexity Analysis of PRENSENT

The attack mode established based on the fault propagation property is optimized compared with the traditional exhaustive search method of PRESENT. The complexity of recovering the round key is 2⁶⁴ in the traditional exhaustive search method. In this article, according to the propagation property of the fault, possible values of the non-zero nibble position of the differential output are exhausted, which can effectively reduce the complexity required by the attack.

A nibble fault can recover the 4-bit $\Delta x_{31}^{15}$ , so the minimum number of faults required to recover the 64-bit round key of PRESENT is calculated as follows:

$$\begin{align*} \begin{cases} 0, & d=0 \\ \left \lceil{ {\frac {m}{d}} }\right \rceil \!, & 1\le d\le m \\ \end{cases}\tag{19}\end{align*}$$

In (4), m is the number of round-key bits; d represents the number of round key bits corresponding to a fault. If $d={\textit {0}}$ , the attack does not recover any bits of the round key. For the PRESENT and the attack method in this article, the condition is $m={\textit {64}}$ and $d={\textit {4}}$ . Therefore, a 64-bit round key need minimum 16 nibble faults to recover itself. According to the key update scheme of PRESENT, 32 nibble faults need to be imported to restore the original 80-bit key. Then, the data complexity required for the attack is the sum of the fault ciphertext and the plaintext at the corresponding fault location. The complexity is calculated as $32\times 4\times 2=2^{8}$ .

In addition to data complexity, computational complexity is often used to measure the computational time and resources consumed by attack methods, which is also an important metric. For computational complexity, the process would be divided into three steps.

The first step is to guess the 4-bit non-zero nibble of the input differential of S-box, so the complexity is 2⁴.

Second, we need to compute $x_{31}^{15}$ based on the exhausted values of $\Delta x_{31}^{15}$ . According to the S-box differential property of PRESENT, the expected number of candidate values is 2.648 in (13), therefore, the complexity is $2.648\times 2^{4}\approx 2^{5.41}$ .

Third, the 4-bit candidate of $\Delta x_{31}^{15}$ in set M₀ needs to be further screened. So, the computational complexity is 2.648.

Therefore, the sum of computational complexity to recover 4-bit $x_{31}^{15}$ is $2^{4}+2^{5.41}+2.648\approx 2^{5.94}$ , and the complexity required to find 64-bit $\Delta X_{31}$ is $2^{5.94}\times 16=2^{9.94}$ , which equals the complexity to recover 64-bit round key. According to the key update scheme of PRESENT, the complete 80-bit original key can be obtained after two consecutive rounds of the round key, so the complexity of recovering the full original key is $2^{9.94}\times 2=2^{10.94}$ .

B. Complexity Analysis of GIFT

Use the same approach for the complexity analysis of GIFT. According to the characteristic of GIFT keys and constant xor layers, only 2-bit round key participate in xor for a 1-byte, so only 2-bit round key can be recovered from a 1-byte fault. Therefore, for GIFT, there are $m={\textit {32}}$ and $d={\textit {2}}$ , which mean 16 nibble faults need to be imported at least. According to the GIFT key update scheme, 64 nibble faults are imported to restore the original 128-bit key. Then, the data complexity required for the attack is the sum of the fault ciphertext and the plaintext of the corresponding fault location. The complexity is calculated as $64\times 4\times 2=2^{9}$ .

For computational complexity, the process would be divided into three steps.

The first step is to guess the 4-bit non-zero nibble of the input differential of S-box, so the complexity is 2⁴.

Second, we need to compute $x_{28}^{15}$ based on the exhausted values of $\Delta x_{28}^{15}$ . According to the S-box differential property of PRESENT, the expected number of candidate values is 2.584 in (18), therefore, the complexity is $2.584\times 2^{4}\approx 2^{5.37}$ .

Third, the 4-bit candidate of $\Delta x_{28}^{15}$ in set M₁ needs to be further screened. So, the computational complexity is 2.584.

Therefore, the sum of computational complexity to recover 4-bit $x_{28}^{15}$ is $2^{4}+2^{5.37}+2.584\approx 2^{5.91}$ , and the complexity required to find 64-bit $\Delta X_{28}$ is $2^{5.91}\times 16=2^{9.91}$ , which equals the complexity to recover 64-bit round key. According to the key update scheme of GIFT, the complete 128-bit original key can be obtained after two consecutive rounds of the round key, so the complexity of recovering the full original key is $2^{9.91}\times 4=2^{11.91}$ .

SECTION VI. Experiment

The encryption process of GIFT and PRESENT is similar, and the attack method in this article has obvious effect on both. Therefore, only the attack experiment on GIFT is given.

A. Experimental Configuration

The hardware is configured as a PC (the CPU is Intel Core i5-4200M 2.5GHz, the operating system is 64-bit, and the memory is 4GB), and the programming environment is the C++ language in the platform of Microsoft Visual Studio 2019.

B. Experimental Results

Fault injection is implemented by the programming language modify the encryption process of GIFT. Then, the incorrect ciphertext obtained from the injected random fault was processed. At last, the number of incorrect ciphertext needed for the round key and the running time of the program are recorded. We carried out 30-times experiments, and the results are shown in Table 10.

TABLE 10 Experimental Result of Differential Fault Analysis on GIFT

As can be seen from the above table, this attack method requires an average of 87 nibble faults to recover all keys of GIFT, which is higher than the theoretical result of 64 nibble faults mentioned above. Meanwhile, the attack can be completed in about 500ms. In order to show the fluctuation of the results of these 30-times experiments, we drew the line chart as shown in Fig. 2. As can be seen from the figure, the fluctuation of the results decreases with the increase of the number of experiment.

FIGURE 2.

Experimental results of DFA on GIFT.

C. Results Discussion

The number of faults required by the experimental results is larger than that of the theoretical analysis, which we believe is mainly due to the following two reasons:

1. The round key of is closely related to the solution of the differential equation (18), and according to the differential property of GIFT, the solution of the differential equation is not unique. Therefore, sometimes one round of encryption needs to be attacked multiple times to obtain a unique round of keys.

2. Because the sample space of this article is limited, so the result is different from the theoretical value. In this article, fault propagation paths effectively used by the sample space are slightly less than the theoretical value. Namely, the impact of each fault on the input of S-box is slightly less than the theoretical value. Therefore, the actual incorrect ciphertext required would be marginally more than the theoretical value. On average, it only takes 87 faults to recover all the key information in one second.

SECTION VII. Conclusion

In this article, a general DFA is proposed for PRESENT and its improved algorithm GIFT. The effectiveness of this method is also verified on GIFT. By analyzing the permutation law of P permutation layer and combining the differential characteristics, the following conclusions are obtained:

1. According to PRESENT’s P permutation layer, nibble fault is imported into the 30^th and 31^th rounds respectively. In theory, 32 nibble faults are needed to fully recover the original 80-bit key, with a computational complexity of 2^10.94 and a data complexity of 2⁸. The following table lists this method and the existing attack methods for PRESENT.

   It can be seen from Table 10 that the PRESENT is attacked by this method, which has great advantages in both computational complexity and data complexity.

2. According to GIFT’s P permutation layer, nibble fault is imported into the 25^th, 26^th, 27^th and 28^th rounds respectively. In theory, 64 nibble fault are needed to fully recover the original 128-bit key, with a computational complexity of 2^11.91 and a data complexity of 2⁹. The following table lists this method and the existing attack methods for GIFT.

   It can be seen from Table 11 that the GIFT is attacked by this method, which has great advantages in both computational complexity and data complexity.

3. GIFT is improved compared with PRESENT, which can resist differential analysis, linear analysis and algebraic analysis [24], but the nibble differential fault attack proposed in this article has obvious effect. In addition, this method is simple, clear, and has a certain universality, which can be applied to other lightweight cipher that P permutation layer has a certain propagation law. Although different ciphers have different permutation layers, by studying the propagation law, it is possible to recover the original key by this method.

TABLE 11 The Cryptanalysis Results of PRESENT-80 in Public Literature

TABLE 12 The Cryptanalysis Results of GIFT-64 in Public Literature

Our proposed a general DFA approach for PRESENT and GIFT performs well in both data complexity and computational complexity. However, the hardware implementation may be limited because it is difficult to induce a nibble fault in the real situation. Therefore, in the future work, we will implement this attack method on FPGA or other hardware, and study the performance of this method in the real environment. In addition, we will continue to explore more DFA approaches to other lightweight block ciphers. Finally, we will discuss the security of various cryptographic application scenarios, such as privacy protection [31], [32] and identity authentication [33].

ACKNOWLEDGMENT

Haoxiang Luo would like to thank the Glasgow College, UESTC, for their support of this research.