New differential fault analysis on PRESENT

Boneh et al. introduced the fault attack in September 1996[1]. Later, in October 1996, Biham and Shamir published an attack on secret key cryptosystems called differential fault analysis (DFA) which combined the ideas of fault attack and differential attack[2]. Given a plaintext, the DFA attack derived information about the secret key by examining the differences between a related cipher text resulting from a correct encryption and a cipher text of the same plaintext resulting from a faulty encryption. Normally, a faulty cipher text is taken by giving external impact on a device with voltage variation, glitch, laser, etc. A fault may be induced with these external impacts; however, we know neither the location nor the value of the fault. This attack is commonly used to analyze the security of cryptosystems. DFA have been employed to attack several block ciphers where DES[3, 4], AES[5–11], PRINTCIPHER[12], Camellia[13], CALEFIA[14, 15], RC4[16], SMS4[17], and ARIA[18] are examples. In general, there are two techniques to apply a DFA attack on a block cipher. The first one assumes that the intermediate states were corrupted by the fault injection and tries to recover the key, while the second form assumes that the key schedule algorithm was corrupted by the fault injection and tries to recover the key.

PRESENT is an ultra-lightweight block cipher proposed at CHES 2007 by Bogdanov et al. This block cipher is an SP network-based cipher and consists of 31 rounds. The block length is 64 bits, and two key lengths of 80 and 128 bits are supported[19], denoted by PRESENT-80 and PRESENT-128, respectively. Several basic attacks such as differential cryptanalysis, linear cryptanalysis, and their variants have been applied on PRESENT already[20–23]. In this paper, we concentrate on the security of PRESENT-80 against DFA attack.

1.1 Previous works

A DFA on PRESENT-80 key schedule has been proposed by Wang et al.[24]. They assumed that the key schedule was corrupted by the fault injection and tried to recover the key. They have reduced the master key search space of PRESENT-80 to 2²⁹ with 64 pairs of correct and faulty cipher texts on average. In addition, Zhao et al.[25] proposed a fault propagation pattern-based DFA on PRESENT-80/128. They reduce the master key search space of PRESENT-80/128 to 2^14.7 and 2^21.1, respectively, with 8 and 16 pairs of correct and faulty cipher texts on average.

1.2 Paper contributions

In this paper, we present two differential fault analyses on PRESENT-80. For the first attack, we assume that the fault occurs on only one bit of the intermediate states. In the second attack, we induce a fault on a single nibble of the intermediate states and we employ our first attack to retrieve the master key. Our attack can recover the master key, given 18 faulty cipher texts on average.

The notations used in the paper are presented in Section 3. PRESENT is briefly described in Section 3.2. In Section 4, we describe our basic attack. We present another DFA attack based on the basic attack in Section 5. Finally, we conclude the paper in Section 6.

3.1 Notations

Throughout the paper, we use the following notations:

•  P : denotes the plaintext.

•  K : denotes the master key.

•  S ⁱ: denotes the correct state before i th round’s S-box layer and$S_j^i$ denotes the j th bit of S ⁱ.

•  S ^i∗: denotes the faulty state before i th round’s S-box layer.

•  S ⁱ N ^j: denotes the j th nibble of state before i th round’s S-box layer and$S^i{N}_n^j$ denotes its n th bit of the nibble.

•  B ⁱ: denotes the state after i th round’s S-box layer and B ⁱ N ^j denotes the j th nibble of B ⁱ.

•  B ^i∗: denotes the faulty state after i th round’s S-box layer and B ^i∗ N ^j denotes the j th nibble of B ^i∗.

•  K ⁱ: denotes i th subround key and$K_j^i$ denotes the j th bit of K ⁱ.

•  C : denotes the correct cipher text.

•  D : denotes the faulty cipher text.

3.2 Description of PRESENT

The PRESENT block cipher, depicted in Figure1, is an ultra-lightweight substitution-permutation network and consists of 31 rounds. The block length is 64 bits. The cipher supports 80 and 128-bit secret keys. Each round of PRESENT consists of three stages: key addition, non-linear substitution layer, and bit-wise permutation layer.

PRESENT encryption algorithm.

Full size image

3.2.1 Key addition

As the first step of i th round, for 1 ≤ i ≤ 32, the current state is combined using bit-wise XOR with the i th round subkey.

where K ³² is used for postwhitening.

3.2.2 Substitution layer (S-box)

The output of the key addition stage goes through the S-box layer (Table1) which is the non-linear operation of the round. The S-box used in PRESENT is a single 4-bit to 4-bit S-box which is applied 16 times in parallel. The action of the S-box is shown by the following table.

3.2.3 Permutation layer P

Finally, the output of the S-box layer is rearranged to the permutation layer (Table2). Following this operation, bit i of the current state is moved to the bit position P(i).

The key schedule algorithm supports two key lengths of 80 and 128 bits. However, we do not explain the key schedule algorithm here because it is not directly relevant to our attack. For more information about the key schedule, the interested reader can refer to[19].

In this section, we introduce a basic DFA attack against PRESENT-80 which is based on the injection of a fault on only one bit of intermediate states at the beginning of the last round’s S-box layer. The given attack requires a single-bit fault in the last round of the cipher which may sound difficult in practice. However, the recent results[26] show the feasibility of this type of DFA attacks.

The main idea of the given attack is to obtain S ³¹ by searching in the differences distribution table of the S-box (see Appendix 1), then we can obtain K ³². Injection of a single-bit fault on the j th nibble of S ³¹, S ³¹ N ^j, can be on$S^{31}{N}_0^j$,$S^{31}{N}_1^j$,$S^{31}{N}_2^j$, or$S^{31}{N}_3^j$. We denote the difference between the j th nibble of the correct state S ³¹ N ^j and the j th nibble of the faulty state S ^31∗ N ^j by a, i.e., a = S ³¹ N ^j ⊕ S ^31∗ N ^j. Hence, there are four possible fault differences for this nibble, a ∈ {1,2,4,8}. In Figure2, an example of the fault required for the basic attack is given where the first bit of the first nibble of S ³¹ is corrupted.

An example of an injection of a single bit fault on S ³¹ .

Full size image

Through the attack, we assume that the master key and the input plaintext remain fixed. Moreover, for each faulty cipher text, exactly one bit of S ³¹ is randomly modified. To recover the last round key, following this attack, the adversary processes each nibble of intermediate state independently. To implement this attack, the adversary should obtain each nibble of S ³¹, S ³¹ N ^j for 1 ≤ j ≤ 16. Obtaining each nibble would be possible if we are given, on average, three distinct faulty cipher texts, assuming that the faults are injected on different bits of the nibble. To find out the nibble of S ³¹ which is involved in the faults, the adversary may reverse the difference output of P layer (P layer⁻¹(C ⊕ D)) following the approaches presented in Algorithms 1 and 2 to obtain one nibble of S ³¹. Algorithm 1 arranges the faulty cipher texts and correct the cipher text in 16 groups of difference outputs of last round’s S-box layer, i.e., ΔB ³¹ N ^j for 1 ≤ j ≤ 16. In each specific group, the bits of faults occurred on the bits of the same nibble and the related nibble of S ³¹, S ³¹ N ^j, can be obtained following Algorithm 2. On the other hand, Algorithm 1 determines for each faulty cipher text, which the nibble has been corrupted. Hence, at the end of Algorithm 1, we expect to receive three difference outputs of last round’s S-box layer for each nibble. It is possible to repeat Algorithm 2 and retrieve whole nibbles of S ³¹. Given S ³¹ and the correct cipher text C, K ³² can be extracted as follows:

Hence, following the given attack, it is possible to retrieve K ³² given on average 48 faulty cipher texts and related correct cipher text for the fixed value of input message P (Additional details of the basic attack are given in Appendix 2).

If we can induce a fault on one bit of several nibbles of S ³¹ for each fault experiment, we can reduce the required number of faulty cipher texts to obtain S ³¹ and K ³². In this case, we can still use Algorithms 1 and 2 for obtaining S ³¹ and K ³². Obviously, the injection of a single bit fault for a nibble of S ³¹ generates a faulty nibble at the output of last round’s S-box layer, and single bit faults injection on several nibbles of S ³¹ generates several faulty nibbles at the output of last round’s S-box layer.

Algorithm 1 Determining the faulty output of last round’s S-box layer

Algorithm 2 Obtain one nibble of S ³¹

In Figure3, the flowchart of this attack is depicted.

The flowchart of DFA on present.

Full size image

Given K ³², a similar attack can be used to retrieve S ³⁰ and K ³¹ and finally recover the master key. However, the number of required faulty cipher texts would be increased (96 faulty cipher texts on average), but in the next section, we show an approach to obtain the master key given 18 faulty cipher texts on average.

Remarks 1

It must be noted that sometimes faulty cipher texts will be repeated (if we inject a fault on the same bit of S ³¹ ), and we exclude this faulty cipher text. We collect three unique faulty cipher texts on average for obtaining each nibble of S ³¹.

In the previous section, we described a basic attack that, on each experiment, induces a fault on a single bit of intermediate state of the last round. In this section, to retrieve the whole master key, we extend the previous attack such that the adversary can inject a fault on one nibble rather than a bit.

In the design criteria of PRESENT, it has been stated that:

1. 1.

   The four input bits to an S-box come from four distinct S-boxes of the same group.

2. 2.

    The input bits to a group of 4 S-boxes come from 16 different S-boxes.

3. 3.

    The four output bits from a particular S-box enter four distinct S-boxes, each of which belongs to a distinct group of S-boxes in the subsequent round.

4. 4.

    The output bits of S-boxes in distinct groups go to distinct S-boxes.

Following the above criteria, we state that:

•  Inducing a fault on only one nibble of intermediate states at the beginning of the i th round’s S-box layer, S ⁱ, leads to fault occurrence on one bit of some S-boxes of the next round, where on average, the inputs of two S-boxes would be corrupted at the beginning of S ⁱ⁺¹.

•  Inducing a fault on only one nibble of intermediate states at the beginning of the i th round’s S-box layer, S ⁱ, leads to fault occurrences on one bit of some S-boxes of the next round, S ⁱ⁺¹, where on average the inputs of two S-boxes would be corrupted at the beginning of S ⁱ⁺¹. These differences are propagated to extra S-boxes in (i + 2)th round. However, following the designing criteria, for any corrupted input of S-boxes at (i + 1)th and (i + 2)th round, we have difference on one bit. Therefore, the injection of a fault on a nibble of intermediate states at the beginning of the 29th round’s S-box layer, on average, provides the adversary with faults on single bits of four nibbles of S ³¹.

Now, following the above argument, we assume that a fault on only one nibble of intermediate states at the beginning of the 29th round’s S-box layer has occurred. We can use this approach to reduce the number of required faulty cipher texts in the basic attack (same as when we can induce the single bit faults on several nibbles of S ³¹ in the basic attack). An example of fault injection at the beginning of the 29th round’s S-box layer and its propagation toward 31st round has been depicted in Figure4. In this picture, for the sake of simplicity, we have assumed that the first nibble of S ²⁹ is corrupted. It can be seen that eight nibbles of S ³¹ have been corrupted, and also, only one bit of inputs of each faulty S-boxes at 31st round is corrupted. Therefore, we can apply the basic attack on the received data. However, in the new fault model, we receive on average four faulty nibbles at the output 31st round in each fault injection (four nibbles of the output of the last round’s S-box layer were corrupted). Hence, the required number of faulty cipher texts to obtain the S ³¹ is reduced to 12.

The example of our fault model.

Full size image

Whenever we obtained S ³¹ and K ³², we can also retrieve K ³¹. To retrieve K ³¹, from the first phase of attack which retrieves K ³², we have 24 nibbles of the faulty output of the 30th round’s S-box layer (B ^30∗ N ^j) on average, and we require extra 24 nibbles of the faulty output of the 30th round’s S-box layer to obtain S ³⁰ and K ³¹. We can obtain those faulty states by inducing six extra faults on nibbles of intermediate state at the beginning of the 28th round’s S-box layer on average.

Therefore, we can obtain K ³² given 12 faulty cipher texts on average, where we have injected faults on the nibbles of S ²⁹. To retrieve K ³¹, we require also to induce faults on the nibbles of intermediate state at the beginning of the 28th round’s S-box layer. Following the basic attack (with some change in notation and extent formula, see Appendix 1), to retrieve K ³¹, we require additional six faulty cipher texts on average. Given the round keys K ³¹ and K ³², it is possible to determine the master key uniquely. Hence, in total, it is possible to recover the master key of PRESENT-80 given 18 faulty cipher texts on average (An toy example of attacks are given in Appendix 3).

To compare our approach with[25], it must be noted that they have injected fault on the 29th round and tried to find the difference input of S-box 31st round where they have got some candidates for S-box inputs of 31st round and then recovered K ³² and K ³¹. On the other hand, the given attack in this paper does not require to find the difference input of S-box 31st round, and it recovers the S-box input of 31st round by searching in the differences distribution table of S-box and then obtains K ³².

Any secure cryptosystems should be protected against DFA attacks. So, any implementation of PRESENT also requires to protect the last round of encryption against the basic DFA attack and protect the 29th and 30th rounds of encryption against the second DFA attack. Therefore, an implementation of PRESENT requires to protect the three last rounds against our DFA attacks.

Remarks 2

Sometimes, we may receive useless faulty nibbles of cipher texts through the experiments which increase the attack complexity, i.e., number of required faulty cipher texts. Based on the random nature of the faults, and also the faults propagation property, it is possible to receive same errors on the same nibbles of the 31st round in different experiments. It should be noted that the errors that we induce in different experiments could be in different nibbles or even in the same nibble. These errors are propagated through the remaining rounds. However, if we receive several errors in a same bit of a nibble at the beginning of the 31st round, then only one of them is useful and the rest do not include new information. For example, following Figure 4 which is drawn for a fault on the first nibble of the internal state of 29th round, if we induce another fault on the same nibble in the next experiment and assume that the output difference of the related S-box at round 29 is 3, it has overlapped with the previous fault and it does not provide us with new information. It must be noted that we collect the unique nibble of faulty cipher texts and unique nibbles of faulty cipher texts on average to obtain one nibble of S ³¹.

In this paper, we introduced two new DFAs on PRESENT-80. Our attacks are based on the injection of the faults on the intermediate state of the cipher and can retrieve the last round key and the master key efficiently. The basic attack which requires to induce a fault on a single bit of nibbles at the input of the last round requires 48 faulty cipher texts on average, and the extended attack which retrieves the master key induces a fault on a nibble of the intermediate states and requires 18 faulty cipher texts on average.

The difference distribution table of the S-box and the categorization algorithm for the faulty cipher texts

The difference distribution table of the S-box is shown in Table3. The categorization algorithm for the faulty cipher texts is shown in Algorithm 3.

Algorithm 3 Categorize the faulty cipher texts and cipher text in 16 groups based on the difference output of the 30th round’s S-box layer

Algorithm 4 Obtain one nibble of S ³⁰ , given that K ³¹ = P - Layer( S -Layer( S ³⁰ )) ⊕ S ³¹

Additional details of the basic attack

For each faulty cipher text, we have got a difference output of the last round’s S-box layer, and we can determine possible inputs of the last round’s S-box layer by searching in the differences distribution table of the S-box. In Table4, all possible inputs of the last round’s S-box layer for each difference output of the last round’s S-box layer are shown (remember that difference input can be a ∈ {1,2,4,8}).

In Table4, it can be seen that given a faulty cipher text, eight candidates for S-box input with probability$\frac{5}{11}$ have been determined or four candidates for S-box input with probability$\frac{6}{11}$ have been determined.

In Table5, all S-box difference outputs for each S-box input, with one bit difference in S-box input, are depicted.

Given in Table5, we see that the sets of S-box difference outputs for each specific input are different. Hence, we can obtain the exact value of the S-box input with four faulty cipher texts. In the following, we explain the states that two and three faulty cipher texts are given.

•  When two faulty cipher texts are given, these states can occur:

  • Two faulty cipher texts determine eight candidates for S-box input. In this state, when we apply Algorithm 2, we obtain two, three, four, or five candidates for S-box input.

  • The first faulty cipher text determined eight candidates for S-box input, and the second faulty cipher text determined four candidates for S-box input. If we denote by A the sets of the candidates obtained with the first faulty cipher text except the correct value of S-box input and by B the sets of the candidates obtained with the second faulty cipher text except the correct value of S-box input, we can identify the correct value with probability:

    $$\begin{array}{ll}P& =P(A\cap B=\varnothing )=P(\left|A\cap B\right|=0)\\ =\frac{\left(\genfrac{}{}{0.0pt}{}{16}{7}\right)\times \left(\genfrac{}{}{0.0pt}{}{16-7}{3}\right)}{\left(\genfrac{}{}{0.0pt}{}{16}{7}\right)\times \left(\genfrac{}{}{0.0pt}{}{16}{3}\right)}\simeq 15\%\end{array}$$

  • The first faulty cipher text determined four candidates for S-box input, and the second faulty cipher text determined four candidates for S-box input.

    In this state, we can identify the correct value with probability:

    $$\begin{array}{ll}P& =P(A\cap B=\varnothing )=P(\left|A\cap B\right|=0)\\ =\frac{\left(\genfrac{}{}{0.0pt}{}{16}{3}\right)\times \left(\genfrac{}{}{0.0pt}{}{16-3}{3}\right)}{{\left(\genfrac{}{}{0.0pt}{}{16}{3}\right)}^2}\simeq 51\%\end{array}$$

• When three faulty cipher texts are given, these states can occur:

• All faulty cipher texts determined eight candidates for S-box input.

  If we denote by C the sets of the candidates obtained with the third faulty cipher text except the correct value of S-box input, we can identify the correct value with probability:

  $$\begin{array}{ll}P& =P(A\cap B\cap C=\varnothing )=P(\left|A\cap B\cap C\right|=0)\\ =\sum _{k=1}^{4}P(\left|A\cap B\right|=k,\left|A\cap B\cap C\right|=0)\\ =\sum _{k=1}^{4}P(\left|A\cap B\right|=k)\times P(\left|A\cap B\cap C\right|=0/\left|A\cap B\right|=k)\\ =\frac{\left(\genfrac{}{}{0.0pt}{}{16}{7}\right)\times \left(\genfrac{}{}{0.0pt}{}{7}{k}\right)\times \left(\genfrac{}{}{0.0pt}{}{16-7}{7-k}\right)}{{\left(\genfrac{}{}{0.0pt}{}{16}{7}\right)}^2}\times \frac{\left(\genfrac{}{}{0.0pt}{}{16}{k}\right)\times \left(\genfrac{}{}{0.0pt}{}{16-k}{7}\right)}{\left(\genfrac{}{}{0.0pt}{}{16}{k}\right)\times \left(\genfrac{}{}{0.0pt}{}{16}{7}\right)}\simeq 18\%\end{array}$$

  The first and second faulty cipher texts determine eight candidates for S-box input, and the third faulty cipher text determine four candidates for S-box input.

  In this state, we can identify the correct value with probability:

  $$\begin{array}{ll}P& =P(A\cap B\cap C=\varnothing )=P(\left|A\cap B\cap C\right|=0)\\ =\sum _{k=1}^{4}P(\left|A\cap B\right|=k,\left|A\cap B\cap C\right|=0)\\ =\sum _{k=1}^{4}P(\left|A\cap B\right|=k)\times P(\left|A\cap B\cap C\right|=0/\left|A\cap B\right|=k)\\ =\frac{\left(\genfrac{}{}{0.0pt}{}{16}{7}\right)\times \left(\genfrac{}{}{0.0pt}{}{7}{k}\right)\times \left(\genfrac{}{}{0.0pt}{}{16-7}{7-k}\right)}{{\left(\genfrac{}{}{0.0pt}{}{16}{7}\right)}^2}\times \frac{\left(\genfrac{}{}{0.0pt}{}{16}{k}\right)\times \left(\genfrac{}{}{0.0pt}{}{16-k}{3}\right)}{\left(\genfrac{}{}{0.0pt}{}{16}{k}\right)\times \left(\genfrac{}{}{0.0pt}{}{16}{3}\right)}\simeq 50\%\end{array}$$

• The first faulty cipher texts determine eight candidates for S-box input, and the second and third faulty cipher texts determine four candidates for S-box input.

  In this state, we can identify the correct value with probability:

  $$\begin{array}{ll}P& =P(A\cap B\cap C=\varnothing )=P(\left|A\cap B\cap C\right|=0)\\ =\sum _{k=1}^{4}P(\left|A\cap B\right|=k,\left|A\cap B\cap C\right|=0)\\ =\sum _{k=1}^{4}P(\left|A\cap B\right|=k)\times P(\left|A\cap B\cap C\right|=0/\left|A\cap B\right|=k)\\ =\frac{\left(\genfrac{}{}{0.0pt}{}{16}{7}\right)\times \left(\genfrac{}{}{0.0pt}{}{7}{k}\right)\times \left(\genfrac{}{}{0.0pt}{}{16-7}{3-k}\right)}{\left(\genfrac{}{}{0.0pt}{}{16}{7}\right)\times \left(\genfrac{}{}{0.0pt}{}{16}{3}\right)}\times \frac{\left(\genfrac{}{}{0.0pt}{}{16}{k}\right)\times \left(\genfrac{}{}{0.0pt}{}{16-k}{3}\right)}{\left(\genfrac{}{}{0.0pt}{}{16}{k}\right)\times \left(\genfrac{}{}{0.0pt}{}{16}{3}\right)}\simeq 62\%\end{array}$$

A toy example of attacks

Assume that a message M is encrypted by PRESENT-80, the basic attack works as follows. For the sake of simplicity, we assume that the first nibble of S ³¹, S ³¹ N ⁰, is A in hexadecimal ((1010)₂ in binary). So, if we inject a single-bit fault on S ³¹ N ⁰, we obtain a faulty cipher text D. If we do this fault injection to other bits of S ³¹ N ⁰, we have four faulty cipher texts that is shown in the following table (Table6, note that throughout the attack, we do not know the fault location, and we put this value in this table only for the reader):

So we show each step of Algorithm 2 in the following table (Table7):

After we obtain S ³¹ N ⁰, we obtain 4 bits of K ³².

For verifying the second attack, we present an example that the message, key, and some details are shown in Table8. We injected 16 faults on S ³¹ in random and have got 16 faulty cipher texts. In Table9, the value and location of faults were given (this table was given just for the reader); then, in Table10, the results of Algorithms 1 and 2 were given.

In Table10, two candidates existed for nibbles 4, 6, and 11 of S ³¹, so for obtaining the exact value of these nibbles, we have to inject at least three faults on S ²⁹. In total, we obtain 13 nibbles of K ³², 9 nibbles of K ³¹, and two candidates for some nibbles of K ³² and K ³¹ with 16 faulty cipher texts (in this example). For recovering whole of K ³¹, we have to inject some faults as mentioned in Section 5.