A Note on the Security of CHES 2014 Symmetric Infective Countermeasure

Abstract

Over the years, fault injection has become one of the most dangerous threats for embedded devices such as smartcards. It is thus mandatory for any embedded system to implement efficient protections against this hazard. Among the various countermeasures suggested so far, the idea of infective computation seems fascinating, probably due to its aggressive strategy. Originally conceived to protect asymmetric cryptosystems, infective computation has been recently adapted to symmetric systems. This paper investigates the security of a new symmetric infective countermeasure suggested at CHES 2014. By noticing that the number of executed rounds is not protected, we develop four different attacks that exploit the infection algorithm to disturb the round counter and related variables. Our attacks allow one to efficiently recover the secret key of the underlying cryptosystem by using any of the three most popular fault models used in literature.

1 Introduction

Over the last 20 years, the security of embedded devices has been challenged by several specific attacks. In particular, Boneh et al. showed in 1996 that a simple disturbance during the execution of an embedded algorithm may totally break its security [5]. They illustrated this new method by explaining how to break an CRT-RSA implementation by inducing only one error during the algorithm execution. By using so-called fault attacks, many signature schemes and symmetric cryptosystems have been broken only a few months after the original Boneh et al. publication [1, 4]. A whole new research field thus appeared aiming at discovering new fault-based attacks and providing efficient countermeasures [11, 13, 15]. While researchers improved and discovered new fault attacks on each and every cryptosystem, the countermeasures were difficult to find and costly to implement. Among the ideas that emerged, the two most popular methods are the signature verification for asymmetric systems and the duplication method for symmetric ones. The first one simply consists in performing a signature verification on the result. If a fault occurred then the signature is not consistent and the verification fails. The second method requires to execute the algorithm twice and to compare both results. If an attacker disturbs one of the two executions then the comparison detects the attack and no output is returned. A third approach called infective was suggested in 2001 by Yen et al. [19]. Their method consists in modifying and amplifying the injected error in such a way that the attacker cannot retrieve any information from the corresponding faulty output. Firstly applied to asymmetric cryptosystems [19] this method is tricky to conceive and all infective countermeasures for asymmetric algorithms published so far have been broken, see [3, 8, 17, 18] for instance. The infective method has been adapted only recently to the symmetric case. The first example of symmetric infection was proposed by Lomné et al. in 2012 to protect AES [12]. The authors suggest to execute the AES twice and to compute the infection by multiplicatively masking the differential of the two AES outputs. A second symmetric infection was suggested by Gierlichs et al. in [10] by using a random sequence of cipher and redundant rounds together with dummy rounds. If the outputs of the redundant and cipher rounds are different then the temporary result is infected. Unfortunately both methods have been broken by Battistello and Giraud in [2].

At CHES 2014, Tupsamudre et al. improved in [16] the attack of Battistello and Giraud and they also suggested an improved version of the infective countermeasure of Gierlichs et al. While this new proposal is secure against the attacks found in [2, 16], one wonders if they are sufficient to make a symmetric implementation effectively secure, especially in the absence of a proof of security. Such a study has been done by Patranabis et al. in [14] where they provide an information theoretical analysis of the countermeasure suggested in [16]. They found weaknesses and proposed ways to reduce the efficiency of such threats.

In this paper, we extend the analysis of [14] by studying the security of the proposition of Tupsamudre et al. We firstly refine the attack presented in [14] and we analyze precisely its efficiency. We also suggest three other different attack paths that allow the attacker to modify the number of executed rounds by disturbing the infective algorithm variables. In order to mount our attacks we exploit three common fault models used in literature, from skip faults to random error faults. This paper not only shows that a straightforward implementation of the CHES 2014 infective countermeasure is insecure but also shows that implementers should pay particular attention to any aspect of a security countermeasure when implementing it.

The rest of the paper is organized as follows. In Sect. 2 we recall the countermeasure suggested in [16]. Section 3 presents four different attacks on this countermeasure. In particular, we show that it is possible to recover the secret key by using any of the three most popular fault models used in the literature. Section 4 finally concludes this paper.

2 Description of CHES 2014 Infective Countermeasure

The infective countermeasure suggested at CHES 2014 by Tupsamudre et al. [16] is based on the work presented at LatinCrypt 2012 by Gierlichs et al. [10]. For the sake of simplicity we recall in Algorithm 1 the CHES 2014 countermeasure suggested in [16] applied to AES-128. For more information about AES, the reader can refer to [9].

Algorithm 1 uses three states denoted $R_0, R_1$ and $R_2$ for the cipher, the redundant and the dummy rounds respectively. The execution order of these rounds is given by a random bit string rstr generated at the beginning of the algorithm. Each “0” on the string encodes a dummy round, while a “1” encodes a redundant or cipher round. Each time a “1” occurs, an index i is incremented and a redundant round (resp. a cipher round) is executed if i is odd (resp. even). Algorithm 1 thus executes a loop over the rstr string bits and executes a cipher, redundant or dummy round accordingly. One may note that Algorithm 1 computes the redundant round before the cipher round all along the algorithm and dummy rounds can happen randomly at any time.

Dummy rounds are executed over a dummy state $R_2$ which is initialized to a random 128-bit value $\beta$ and by using the round key $k^0$ which is computed such that:

$$\begin{aligned} \mathtt {RoundFunction}(\beta , k^0) = \beta . \end{aligned}$$

(1)

The number of dummy rounds is parameterized by a security level t chosen by the developer. More precisely, this parameter represents the whole number of cipher, redundant and dummy rounds performed during Algorithm 1 execution. For instance in the case of AES-128, $t-22$ dummy rounds will be performed.

Regarding the infective part, a first infection is activated after each cipher round if its state $R_0$ is different from the redundant state $R_1$ (Steps 9 and 11). Moreover another infection occurs if $R_2 \ne \beta$ after the execution of a dummy round (Steps 10 and 11). These infections consist in replacing the cipher state $R_0$ with the random value $R_2$, leaving no chance to the attacker to obtain information on the secret key once the infection is applied. To do so, a Boolean function $\mathtt {BLFN}$ is used which maps non-zero 128-bit values to 1 and outputs 0 for a null input.

Compared to the original LatinCrypt 2012 proposal, the CHES 2014 infective countermeasure differs by the way of dealing with the sequence of cipher, redundant and dummy rounds which is now done by using a random string rstr and by the way the infection is performed which is now fully random.

Despite the security analysis of Algorithm 1 presented in [16], we show in the next section that it may be insecure if implemented as such. Furthermore we show that an attacker can recover the full secret key for each of the three most popular fault models used in literature.

3 Attacks

In this section we firstly present the principle of our attacks which are based on the fact that the variables dealing with the number of rounds to perform are not protected. We then exploit this remark to suggest four different attacks that use different fault models such as the instruction skip, the stuck-at and the random error fault model.

3.1 Principle of Our Attacks

Due to the improvements of Algorithm 1 compared with the original LatinCrypt 2012 countermeasure, it is impossible for the attacker to obtain any information on the secret key once the infection has occurred. In order to thwart this countermeasure, we thus investigate the possibility to disturb the number of executed rounds since the corresponding variable is not protected in integrity. Indeed, if the attacker succeeds in disturbing the number of rounds she may be able to retrieve the secret key from the corresponding faulty ciphertext [6, 7]. In the remainder of this section, we show how such an attack works if the last round of an AES-128 has been skipped.

If the attacker knows a correct and a faulty ciphertext obtained by skipping the last AES round then it is equivalent to know the input $S^{10}$ and the output $S^{11}$ of the last round. Due to the lack of MixColumns transformation during the last AES round, the last round key $k^{11}$ can be recovered byte per byte by XORing the corresponding bytes of $S^{10}$ and $S^{11}$:

$$\begin{aligned} k^{11}_i = S^{11}_i \oplus \texttt {SBox}(S^{10}_{\text {SR}^{-1}(i)}),\forall i\in \{1, \ldots , 16\}, \end{aligned}$$

(2)

where SR corresponds to the byte index permutation induced by the transformation ShiftRows. In such a case, the attacker can recover the full AES-128 key from only one pair of correct and faulty ciphertexts.

One may note that this attack works similarly if the attacker knows the input and the output of the first round. For further details on the first round attack the reader can refer to [6].

In the following, we describe different ways of disturbing Algorithm 1 by using several fault models such that it does not perform the AES with the correct number of rounds whereas no infection is performed. In our description we make use of AES-128 as a reference, however our attacks can apply straightforwardly to other key sizes.

3.2 Attack 1 by Using Instruction Skip Fault Model

The first attack that we present is an extension of the one presented in [14] which exploits the instruction skip fault model. The attack essentially works because whenever the variable i is odd and $\lambda =1$ then a redundant round is executed and this kind of round does not involve any infection. In the following we assume that the attacker can skip an instruction of its choice by means of a fault injection.

Description. If the attacker skips Step 12 of Algorithm 1 after the last redundant round then the increment of i is not performed. Therefore i stays odd so the last cipher round is replaced by another redundant round. As no infection is involved for redundant rounds, the algorithm returns the output of the penultimate round. The attacker can thus take advantage of such an output to recover the secret key as explained in Sect. 3.1.

Efficiency. As explained in Appendix A, the probability of skipping the last cipher round and thus to recover the AES key after disturbing r different AES executions by skipping Step 12 during the q-th loop is given by:

$$\begin{aligned} \mathcal {P}_r = 1-\left( 1-\frac{\left( {\begin{array}{c}q-1\\ 20\end{array}}\right) \left( {\begin{array}{c}t-q\\ 1\end{array}}\right) }{\left( {\begin{array}{c}t\\ 22\end{array}}\right) }\right) ^r. \end{aligned}$$

(3)

where t is the total number of rounds performed during Algorithm 1, i.e. the number of while loops.

Some numerical values of (3) are given in Table 1 for t equal to 30, 40 and 50, $q=t-3,\cdots , t-1$ and $r=1, \cdots , 4$. One can notice that if the fault is injected when q equals t then the attack does not work because all the rounds have already been executed.

Table 1. Probability of obtaining at least one useful faulty ciphertext by skipping Step 12 during the q-th loop of Algorithm 1.

By analyzing Table 1, one can deduce the best strategy for the attacker. For example if $t=30$ then the attacker should target the 29-th loop in order to obtain the best chances of retrieving the key with the minimal number of fault injections.

Experiments. The attack described in this section has been simulated for $t=30$ and for each q between 25 and 29. The experiment has been repeated $3\,000$ times for each configuration. The results of our tests are depicted in Fig. 1.

Fig. 1.

Experimental probability of obtaining a useful faulty ciphertext by skipping Step 12 during the q-th loop of Algorithm 1 for $t=30$.

By comparing Fig. 1 and the row $t=30$ of Table 1, one can notice that the experiments perfectly match with the theoretical results.

3.3 Attack 2 by Using Stuck-At 0 Fault Model

In this section we use the stuck-at 0 fault model where we assume that the attacker can set to zero a variable of her choice. As for the attack presented in Sect. 3.2, the goal of the attacker is to skip the execution of the last cipher round.

Description. To avoid the execution of the last cipher round by using a stuck-at 0 fault model without activating an infection, the attacker can set to zero the variable $\lambda$ right after Step 5 during the loop involving the last “1” of rstr, i.e. during the loop dealing with the last cipher round. The computation of the last cipher round is thus skipped since $\lambda =0$ implies a dummy round. The attacker thus retrieves an exploitable faulty ciphertext that can be used to retrieve the secret key as described in Sect. 3.1. As no consistency check is performed on $\lambda$, rstr nor on the number of cipher rounds executed, Algorithm 1 does not detect the fault.

Efficiency. We detail in Appendix B the reasoning to compute the probability of obtaining at least one useful faulty ciphertext after disturbing r different AES executions by setting $\lambda$ to 0 after Step 5 of the q-th loop. Such a probability is given by:

$$\begin{aligned} \mathcal {P}_r = 1-\left( 1-\frac{ \left( {\begin{array}{c}q - 1\\ 21\end{array}}\right) }{\left( {\begin{array}{c}t\\ 22\end{array}}\right) }\right) ^r. \end{aligned}$$

(4)

Some numerical values of (4) are given in Table 2 for t equal to 30, 40 and 50, $q=t-2,\cdots , t$ and $r=1, \cdots , 4$.

Table 2. Probability of obtaining at least one useful faulty ciphertext by sticking $\lambda$ at 0 during the q-th loop of Algorithm 1

By comparing Table 2 with Table 1, one may note that the attack presented in this section is more efficient than the one presented in Sect. 3.2, especially when the attacker targets the last loop execution.

Experiments. We simulated the attack for $t=30$ and for q from 27 to 30. For each value of q we performed $3\,000$ tests with random rstr. The results of such experiments are depicted in Fig. 2.

Fig. 2.

Experimental probability of obtaining a useful faulty ciphertext by sticking $\lambda$ at 0 during the q-th loop of Algorithm 1 for $t=30$.

3.4 Attack 3 by Using Random Error Fault Model

We show in this section how the attacker can use the random error fault model to obtain a useful faulty ciphertext. In this fault model, we assume that the attacker can change the value of a chosen internal variable into a random value.

Description. Due to its central role in the infection and scheduling, string rstr is very sensitive. However, the authors of [16] do not suggest any mean of ensuring its integrity. We thus investigated this path and we noticed that an attacker can disturb the generation of rstr at Step 3 of Algorithm 1 such that it does not contain 22 “1” anymore. If the fault disturbs the string rstr such that it contains only 21 (resp. 20) “1” then Algorithm 1 does not execute the last cipher round (resp. the last redundant and cipher rounds). In both cases no infection is performed allowing the attacker to exploit the corresponding faulty ciphertext to recover the secret key as explained in Sect. 3.1.

Efficiency. The probability to obtain at least one useful faulty ciphertext after disturbing r different AES executions by randomly modifying the least significant byte of rstr during Step 3 is given by:

$$\begin{aligned} \mathcal {P}_r = 1-\left( 1-\left( \sum _{i = 1}^{8} \frac{\left( {\begin{array}{c}t-8\\ 22-i\end{array}}\right) \left( {\begin{array}{c}8\\ i\end{array}}\right) }{\left( {\begin{array}{c}t\\ 22\end{array}}\right) } \sum _{j=1}^{i}\frac{\left( {\begin{array}{c}i\\ j\end{array}}\right) \left( {\begin{array}{c}8 - i\\ j-1\end{array}}\right) }{255} + \sum _{i = 2}^{8} \frac{\left( {\begin{array}{c}t-8\\ 22-i\end{array}}\right) \left( {\begin{array}{c}8\\ i\end{array}}\right) }{\left( {\begin{array}{c}t\\ 22\end{array}}\right) } \sum _{j=2}^{i}\frac{\left( {\begin{array}{c}i\\ j\end{array}}\right) \left( {\begin{array}{c}8 - i\\ j-2\end{array}}\right) }{255} \right) \right) ^r. \end{aligned}$$

(5)

For more details about the computation of this probability, the reader can refer to Appendix C.

Table 3 gives the probability to obtain a useful faulty ciphertext for t equal to 30, 40 and 50.

Table 3. Probability of obtaining at least one useful faulty ciphertext by disturbing Step 3 of Algorithm 1.

Experiments. Figure 3 shows the results obtained by simulating the attack described above. The simulations have been performed by generating a random string rstr and disturbing it with an 8-bit random error. The test has been performed $3\,000$ times for each t equal to 30, 40 and 50.

Fig. 3.

Experimental probability of obtaining a useful faulty ciphertext by disturbing Step 3 of Algorithm 1.

3.5 Attack 4 by Using Random Error Fault Model

This section describes a second attack that can be mounted by using the random error fault model.

Description. The idea of the attack is to disturb the increment of index q at Step 13 of Algorithm 1 during the execution of the first cipher round. We noticed that if the disturbance produces an error e such that $q \oplus e > t$ then the evaluation at Step 4 is false and the algorithm returns. If the algorithm computes only one cipher round then the attacker can use such an output to retrieve the first round key, cf. [6]. It is important to notice that in order to retrieve a useful output, the attacker needs to disturb the execution during the first cipher round and not after a redundant or dummy round.

Efficiency. As detailed in Appendix D, the probability to obtain at least one useful faulty ciphertext after disturbing r different AES executions by injecting a random error during Step 13 of the q-th loop is given by:

$$\begin{aligned} \mathcal {P}_r = 1-\left( 1-\frac{2^8- t}{2^8} \sum _{i=2}^{3}\frac{\left( {\begin{array}{c}q\\ i\end{array}}\right) \left( {\begin{array}{c}t-q\\ 22 -i\end{array}}\right) }{\left( {\begin{array}{c}t\\ 22\end{array}}\right) }\right) ^r. \end{aligned}$$

(6)

We give in Table 4 the probability that the attacker retrieves a useful faulty ciphertext for t equal to 30, 40 and 50 and for q from 2 to 4.

Table 4. Probability of obtaining a useful faulty ciphertext by injecting a random error fault on Step 13 of Algorithm 1.

The attacker can use Table 4 to choose the best strategy for her attack. For example for $t=30$, one obtains the best chances to retrieve a useful faulty ciphertext by attacking the third loop. Furthermore when comparing the efficiency of our four attacks, the attack presented in this section is the most efficient one.

Experiments. We mounted several simulations where we disturbed the Step 13 of the q-th loop with a random byte error e. We mounted the experiments for $t=30$ and for q from 2 to 6. For each different q we repeated the experiment $3\,000$ times. The results of such experiments are shown in Fig. 4.

Fig. 4.

Experimental probability of obtaining a useful faulty ciphertext by a injecting random error fault on Step 13 of Algorithm 1 for $t=30$.

The simulations shows that this attack has a remarkable success rate. For example for $t = 30$, an attacker that reiterates the fault injection only twice during the third loop has a probability of retrieving a useful faulty ciphertext greater than $90\,\%$.

4 Conclusion

In this article we showed that the infective countermeasure of CHES 2014 is not as secure as expected. While the countermeasure gives no information to the attacker once the infection is applied, we discovered that it does not protect the number of cipher rounds effectively executed. Despite the fact that attacks on the round counter are well known, our work describes attack paths that are difficult to spot and involve disturbances on the infective variables intentionally added to thwart fault attacks. The aim of this paper is thus to warn the reader of possible security weaknesses that may reside in straightforward implementations of the countermeasure.

We applied the three most popular fault models and found four different attack paths that allow an attacker to recover the secret key of the underlying cryptosystem. For each attack we studied the success probability and performed simulations that validated our theoretical results.

An obvious countermeasure consists in ensuring the integrity of i, q, $\lambda$ and rstr for instance. In their work Patranabis et al. [14] suggest a possible countermeasure based on this remark to thwart the instruction skip fault model. However, their analysis does not take into account other fault models that are exploited in this work. We thus suggest that a possible idea for future improvements may be to fill this gap.

With this work we also remark that the lack of formal security proofs in this field is clearly an issue. We hope that new ideas may pave the way to formally prove the security of cryptosystems against fault-based cryptanalysis.

Appendices

A Probability of Success of Attack 1

The success of Attack 1 depends on the chances for the attacker to fault the increment of i in the loop corresponding to the last redundant round execution. Let us denote by $e_1$ the event of faulting the last redundant round during the q-th loop. The probability $\mathcal {P}(e_1)$ is thus the probability of having a bit-string rstr that contains 20 “1” on the first $q -1$ positions, one bit set on the q-th position and a last sub-string with only one bit set on the last $t-q$ positions. The corresponding number of such sub-strings being equal to $\left( {\begin{array}{c}q-1\\ 20\end{array}}\right)$, $\left( {\begin{array}{c}1\\ 1\end{array}}\right)$ and $\left( {\begin{array}{c}t-q\\ 1\end{array}}\right)$ respectively, this leads us to $\left( {\begin{array}{c}q-1\\ 20\end{array}}\right) \left( {\begin{array}{c}t-q\\ 1\end{array}}\right)$ exploitable rstr strings.

By dividing this value by the number of possible rstr strings, we obtain the probability $\mathcal {P}(e_1)$:

$$\begin{aligned} \mathcal {P}(e_1) = \frac{\left( {\begin{array}{c}q-1\\ 20\end{array}}\right) \left( {\begin{array}{c}t-q\\ 1\end{array}}\right) }{\left( {\begin{array}{c}t\\ 22\end{array}}\right) }. \end{aligned}$$

(7)

As described in Appendix E, we then compute by using Eq. (20) the probability to obtain at least one useful faulty ciphertext by repeating the fault injection r times.

B Probability of Success of Attack 2

Let us evaluate the probability that the event $e_2$ of obtaining a useful faulty ciphertext by setting to zero the variable $\lambda$ at Step 5 of Algorithm 1 happens. The probability $\mathcal {P}(e_2)$ corresponds to the probability of obtaining a string rstr that has 21 bits set on the first $q-1$ positions, a “1” on the q-th position and only “0”’s on the last $t-q$ positions. As we have done in Appendix A, we compute this probability as the number of such strings divided by the total number of possible rstr strings. As there is only one possibility that the last $t-(q-1)$ bits of rstr are exactly “$1\,0\cdots 0$”, we thus obtain:

$$\begin{aligned} \mathcal {P}(e_2) = \frac{ \left( {\begin{array}{c}q - 1\\ 21\end{array}}\right) }{\left( {\begin{array}{c}t\\ 22\end{array}}\right) }, \end{aligned}$$

(8)

As described in Appendix E, we then compute by using Eq. (20) the probability to obtain at least one useful faulty ciphertext by repeating the fault injection r times.

C Probability of Success of Attack 3

Let us denote by $e_3$ the event that a random byte error disturbs the string rstr such that it contains only 21 or 20 “1”. To evaluate the probability $\mathcal {P}(e_3)$ that the event $e_3$ occurs, let us assume for the sake of simplicity that the attacker disturbs the least significant byte B of rstr which corresponds to a random byte fault model. By firstly evaluating the case 21, we observe that the probability that a bit-string has exactly 21 bits set on the first $t-8$ positions and the remaining “1” in one of the last 8 positions is:

$$\begin{aligned} \mathcal {P}(HW(B) = 1) = \frac{\left( {\begin{array}{c}t-8\\ 21\end{array}}\right) \left( {\begin{array}{c}8\\ 1\end{array}}\right) }{\left( {\begin{array}{c}t\\ 22\end{array}}\right) }, \end{aligned}$$

(9)

where we denote by HW(B) the Hamming weight of the byte B. Equation (9) corresponds to the probability that the last byte of rstr has an Hamming weight equal to 1. By summing the corresponding probabilities for all the Hamming weights between 1 and 8 we obtain the probability that the last byte of rstr has an Hamming weight greater than zero:

$$\begin{aligned} \mathcal {P}(HW(B) > 0) = \sum _{i = 1}^{8}\frac{\left( {\begin{array}{c}t-8\\ 22 -i\end{array}}\right) \left( {\begin{array}{c}8\\ i\end{array}}\right) }{\left( {\begin{array}{c}t\\ 22\end{array}}\right) }. \end{aligned}$$

(10)

Now, let us compute the probability of injecting a random error on a byte of Hamming weight i such that the byte contains only $i-1$ “1” after the disturbance. We thus count for each possible value of B how many 8-bit values e exist such that $HW(B \oplus e) = HW(B) - 1$. This corresponds to the number of possible errors setting to “0” j bits “1” while setting to “1” $j-1$ bits “0”. Afterwards we divide the result by the number of possible values for the error e:

$$\begin{aligned} \begin{array}{rcl} \mathcal {P}(HW(B \oplus e) &{} = &{}HW(B) - 1 | B)\\ {} &{}=&{} \frac{\sum _{j=1}^{HW(B)}\left( {\begin{array}{c}HW(B)\\ j\end{array}}\right) \left( {\begin{array}{c}8 - HW(B)\\ j-1\end{array}}\right) }{255}. \end{array} \end{aligned}$$

(11)

This corresponds to the probability that $HW(B \oplus e) = HW(B) - 1$ by injecting a random error e on a random 8-bit value B.

By combining the two probabilities above, we obtain the probability that rstr contains 21 “1” after a random error injection on the last byte of rstr:

$$\begin{aligned} \mathcal {P}(HW(B \oplus e) = 21) = \sum _{i = 1}^{8} \frac{\left( {\begin{array}{c}t-8\\ 22-i\end{array}}\right) \left( {\begin{array}{c}8\\ i\end{array}}\right) }{\left( {\begin{array}{c}t\\ 22\end{array}}\right) } \sum _{j=1}^{i}\frac{\left( {\begin{array}{c}i\\ j\end{array}}\right) \left( {\begin{array}{c}8 - i\\ j-1\end{array}}\right) }{255}. \end{aligned}$$

(12)

For the case where rstr contains only 20 “1”, we use the same reasoning and we obtain:

$$\begin{aligned} \mathcal {P}(HW(B \oplus e) = 20) = \sum _{i = 2}^{8} \frac{\left( {\begin{array}{c}t-8\\ 22-i\end{array}}\right) \left( {\begin{array}{c}8\\ i\end{array}}\right) }{\left( {\begin{array}{c}t\\ 22\end{array}}\right) } \sum _{j=2}^{i}\frac{\left( {\begin{array}{c}i\\ j\end{array}}\right) \left( {\begin{array}{c}8 - i\\ j-2\end{array}}\right) }{255}. \end{aligned}$$

(13)

Thus the total probability of disturbing the generation of one byte of rstr such that it contains a total of 21 or 20 “1” is:

$$\begin{aligned} \mathcal {P}( e_3) = \sum _{i = 1}^{8} \frac{\left( {\begin{array}{c}t-8\\ 22-i\end{array}}\right) \left( {\begin{array}{c}8\\ i\end{array}}\right) }{\left( {\begin{array}{c}t\\ 22\end{array}}\right) } \sum _{j=1}^{i}\frac{\left( {\begin{array}{c}i\\ j\end{array}}\right) \left( {\begin{array}{c}8 - i\\ j-1\end{array}}\right) }{255} + \sum _{i = 2}^{8} \frac{\left( {\begin{array}{c}t-8\\ 22-i\end{array}}\right) \left( {\begin{array}{c}8\\ i\end{array}}\right) }{\left( {\begin{array}{c}t\\ 22\end{array}}\right) } \sum _{j=2}^{i}\frac{\left( {\begin{array}{c}i\\ j\end{array}}\right) \left( {\begin{array}{c}8 - i\\ j-2\end{array}}\right) }{255}. \end{aligned}$$

(14)

As described in Appendix E, we then compute by using Eq. (20) the probability to obtain at least one useful faulty ciphertext by repeating the fault injection r times.

D Probability of Success of Attack 4

In the following we denote by $e_4$ the event that the error e is injected after a cipher round and is such that $q \oplus e >t$. In order to evaluate the probability $\mathcal {P}(e_4)$ we need to compute:

• the probability that the error e leads to $q \oplus e > t$,

• the probability that the attacker disturbs the algorithm after a cipher round and not after a redundant or dummy round.

For the first probability, without loss of generality, we assume that q is coded over one byte which should be the case in practice. We thus obtain that the probability of injecting an 8-bit error e such that $q \oplus e > t$ depends only on t and is given by:

$$\begin{aligned} \mathcal {P}(q \oplus e > t) = \frac{2^8- t}{2^8}. \end{aligned}$$

(15)

In order to evaluate the second probability we remark that it is equivalent to the probability that the string rstr contains two or three “1” in the first q positions. We recall that rstr is a string with 22 “1” at most. Thus the number of possible strings rstr with only two “1” in the first q positions is:

$$\begin{aligned} \left( {\begin{array}{c}q\\ 2\end{array}}\right) \left( {\begin{array}{c}t-q\\ 20\end{array}}\right) . \end{aligned}$$

(16)

Summing Eq. (16) to the number of possible strings rstr with only three “1” in the first q positions we obtain the number of favorable cases for the attacker:

$$\begin{aligned} \left( {\begin{array}{c}q\\ 2\end{array}}\right) \left( {\begin{array}{c}t-q\\ 20\end{array}}\right) + \left( {\begin{array}{c}q\\ 3\end{array}}\right) \left( {\begin{array}{c}t-q\\ 22 -3\end{array}}\right) . \end{aligned}$$

(17)

By dividing by the total number of possible rstr strings we thus obtain the probability that the algorithm has executed only one cipher round after q rounds:

$$\begin{aligned} \mathcal {P}(HW(rstr[1, \ldots , q]) \in [2,3]) = \frac{\left( {\begin{array}{c}q\\ 2\end{array}}\right) \left( {\begin{array}{c}t-q\\ 20\end{array}}\right) + \left( {\begin{array}{c}q\\ 3\end{array}}\right) \left( {\begin{array}{c}t-q\\ 19\end{array}}\right) }{\left( {\begin{array}{c}t\\ 22\end{array}}\right) }, \end{aligned}$$

(18)

where $rstr[1, \ldots , q]$ denotes the sub-string of rstr between the first and the q-th position. By combining the two probabilities we obtain:

$$\begin{aligned} \mathcal {P}(e_4) = \frac{2^8- t}{2^8} \sum _{i=2}^{3}\frac{\left( {\begin{array}{c}q\\ i\end{array}}\right) \left( {\begin{array}{c}t-q\\ 22 -i\end{array}}\right) }{\left( {\begin{array}{c}t\\ 22\end{array}}\right) }, \end{aligned}$$

(19)

which corresponds to the probability that the algorithm returns an exploitable faulty ciphertext by injecting a random error after q rounds.

As described in Appendix E, we then compute by using Eq. 20 the probability to obtain at least one useful faulty ciphertext by repeating the fault injection r times.

E Attack Repetition Probability

For each attack, we denote by $\mathcal {P}(e_i)$ the probability that event $e_i$ occurs. By assuming that $\mathcal {P}(e_i)$ is independent for each execution we can compute the probability of getting at least one useful faulty ciphertext by repeating the fault injection r times as:

$$\begin{aligned} \mathcal {P}_r = 1 - (1- \mathcal {P}(e_i))^{r}. \end{aligned}$$

(20)