Improved differential fault analysis of Grain-128AEAD

Bit-flipping fault attack

A bit-flipping fault attack is a side-channel attack that complements the target register bit by injecting a fault. Salam et al. ^[4] applied a bit-flipping fault attack on Grain-128AEAD. This aspect of their work investigated the existence of unique quadratic terms in the keystream outputs. Consider the output function $$ z_{0} $$, expressed as:

where the monomial $$ s_{13} s_{20} $$ is a unique quadratic term in the fault-free pre-output $$ z_0 $$. This enables the recovery of $$ s_{13} $$ by complementing the content of $$ s_{20} $$, and vice versa. Applying this approach to the different keystream polynomials of Grain-128AEAD, this work managed to recover 128 LFSR bits and 95 NFSR bits with a data complexity of $$ 2^{7.88} $$.

Probabilistic random fault attack

A probabilistic random fault attack is applied when the attacker cannot conclusively determine whether the value of the faulty register has been complimented, i.e., the effect of the fault is random. In the research by Salam et al. ^[4], several distinct cases are considered when a register $$ s_i $$ is injected by a fault for which the impact of the fault is unknown. Consider the fault target register appears as a linear term in the fault-free keystream $$ z_{i} $$. By XOR-ing the fault-free keystream $$ z_i $$ and the faulty keystream $$ z'_i $$, the output differential $$ \delta_i $$ can be calculated by

By observing the output differential $$ \delta_i = 1 $$, the impact of the fault is conclusive; i.e., certain that the target register contents are complemented. However, the fault impact cannot be confirmed when $$ \delta_i = 0 $$. This finding suggests that if the fault is injected into the same target register several times, the impact of the injected fault can be concluded with a high probability. The probability of conclusively determining the impact of the fault is higher when more faults are injected into the target register. This work ^[4] indicates that the probability approaches 99.99% when injecting more than six faults. The data complexity of the applied probabilistic random fault model is $$ 2^{11.60} $$.

Deterministic random fault attack

The deterministic random fault attack ^[4] is carried out on attack models with three different levels of control precision. A simple example is used to illustrate the idea. Notice that $$ s_{93} $$ in Equation (12) is a unique linear term. Let $$ z'_0 $$ represent the faulty keystream resulting from a fault $$ e $$ at time $$ t=0 $$, as given in

Then, the value of the fault $$ e $$, which can be determined by XOR-ing Equations (12) and (14), is calculated by

The unique linear term in the equation is targeted by the fault model and can be determined by calculating the first-order derivative of the keystream equations with respect to the LFSR register $$ s_i $$ or the NFSR register $$ b_i $$, with $$ 0 \leq i \leq 127 $$, as given in

With this approach, a list of the output indices can be generated and used to compute the value of the random fault for Grain-128AEAD. Accordingly, once the fault is determined to complement the target register, the corresponding equations with the unique quadratic terms (bit-flipping) are used to recover specific state bit(s).

As previously stated, three varying degrees of precision control are considered in these attacks: precise, moderate, and no control. From the results of precise control, it was concluded that an average of two faults is needed to complement a specific target register. The average number of required faults for this approach is 200, with a data complexity of $$ 2^{8.88} $$. In the moderate control, the fault was injected in a 1-byte array, assuming that the injected fault could affect any registers within that byte array. Applying this approach to all the 128-bit LFSR and 128-bit NFSR, the entire internal state of LFSR and 24 NFSR register bits can be identified with a data complexity of $$ 2^{11.69} $$. For the no-control approach, the fault is injected at a random location within the LFSR and at any time. In their study, the no-control model was shown to be infeasible in recovering the LFSR and required further investigation.

Determining required single output index to confirm the effect of random fault

To further reduce the data complexity, this study obtains single or multiple output keystream bits that may be used to conclusively determine the impact on the fault for any target register. The first step is eliminating the duplicated output indices in two bytes because observing output indices with duplicated values can only conclude an ambiguous result. In Figure 2, all the output indices that output a differential of 1 for each register in $$ S_{byte0} $$ and $$ S_{byte1} $$ are listed. The duplicated output indices are in matching colors, and the unique output indices are not colored. Suppose that a fault is injected into a random register in $$ S_{byte0} $$ and $$ S_{byte1} $$, and it can be observed from Figure 2 that when $$ \delta_{34}=1 $$, the fault may be injected at $$ s_0 $$ or $$ s_7 $$. After removing the duplicated values, every output index of $$ s_1 $$, $$ s_3 $$, $$ s_5 $$, $$ s_7 $$, $$ s_9 $$, $$ s_{10} $$, $$ s_{11} $$, $$ s_{13} $$ and $$ s_{15} $$ is removed, leaving no keystream indices to identify the impact of the fault. After the same approach is performed on all eight LFSR two-byte arrays, it was observed that in every array, a similar situation occurs where some output indices of a target register are duplicated and eliminated. The next step is to determine whether it is possible to recover the fault location using a single output differential, $$ \delta_j $$. To do this, we experimented on each LFSR two-byte array, as given in Algorithm 1. For each register in each two-byte array, the output polynomials are tested for 100 random initial key-Ⅳ pairs. The output differentials between the faulty and fault-free keystreams for each keystream round ($$ 0\le j \le 199 $$) are then calculated, and the number of times when $$ \delta_j = 1 $$ in 100 tests is recorded.

Figure 2. Output indices to determine the target registers in $$ S_{byte0} \& S_{byte1} $$ (duplicated values are presented in matching colors).

Algorithm 1: Determining the number of times when $$ \delta_j=1 $$ for each target register
Require: Target register $$ R_t $$ in two consecutive bytes and the corresponding output indices $$ z_j $$ of the two bytes
For$$ R_t $$do

As an example, Figure 3 shows the result obtained from Algorithm 1 using registers in $$ S_{byte0} \& S_{byte1} $$, i.e., the number of times for each register in the two-byte array where $$ \delta_j=1 $$ in 100 random experiments. For better observation of the data representation, the cells with values equal to 100 are highlighted in green, while cells with values between 0 and 100 are highlighted in red. This experiment shows that we cannot determine the fault target by observing a single output differential, as the signature is not always unique in the given byte array. For instance, when $$ \delta_{50}=1 $$, the fault could be applied at $$ s_2 $$, $$ s_9 $$, and $$ s_{12} $$. This is because, in 100 tests, a fault injected at $$ s_{12} $$ leads to $$ \delta_{50}=1 $$ for 100 times, while 42 times at $$ s_2 $$ and 53 times at $$ s_9 $$ for $$ \delta_{50}=1 $$. The result of this experiment clearly indicates that it is infeasible to conclusively determine the target location in LFSR two-byte arrays using a single-bit keystream differential.

Figure 3. Number of times $$ \delta_j = 1 $$ for registers in $$ S_{byte0} \& S_{byte1} $$ in 100 tests (values of the number of times = 100 are colored in green and $$ 0 < values < 100 $$ are colored in red).

Then, attempting to gain a clearer conclusion, the experiment is extended by not removing the duplicated values in Figure 2 and using Algorithm 1. The results obtained are shown in Figure 4. We observe that although the output differential injected with a fault may be applied to only two registers, it is still impossible to indicate the fault location conclusively. For example, when $$ \delta_{58}=1 $$, the fault could be applied at $$ s_4 $$ and $$ s_{10} $$. This is because, in 100 tests, a fault injected at $$ s_{4} $$ leads to $$ \delta_{58}=1 $$ for 100 times, while 50 times at $$ s_{10} $$. Hence, the fault location in LFSR two-byte arrays cannot be determined by observing a single output index only.

Figure 4. Number of times $$ \delta_j = 1 $$ for registers in $$ S_{byte0}\&S_{byte1} $$ in 100 tests with duplicated output differentials (values of the number of times = 100 are colored in green, and $$ 0 < values < 100 $$ are colored in red).

Determining required pairs of keystream indices to confirm the effect of random fault

Another experiment was conducted to determine the unique pairs of output keystream bits that can conclusively establish if the injected fault affects a target register. For this, in each register of the two-byte array, all the possible pairs of keystream indices were generated first. For example, pairs of differentials can be formed from the output indices array of register $$ s_1 $$ as $$ (\delta_{64}, \delta_{76}) $$, $$ (\delta_{64}, \delta_{82}) $$, $$ (\delta_{76}, \delta_{82}) $$.

The pair combination of output indices for each register in $$ S_{byte0} \& S_{byte1} $$ is shown in Figure 5. The duplicated values are highlighted in matching colors. It can be seen that when $$ \delta_{34} = \delta_{70} = 1 $$, the potential faulty registers are $$ s_0 $$ and $$ s_7 $$. To further locate the injected fault, the duplicated pairs should be removed. Then, an experiment is conducted to determine the possibility of identifying the fault location using the differentials of the unique pairs of output keystream indices. This experiment aims to identify the conditions under which the faulty register can be decisively determined. Similar to the previous experiment, 100 tests are run with a random initial state for each register in the two-byte array and the number of times where the output differential $$ \delta_j=1 $$ is recorded. The algorithm applied is similar to Algorithm 1. The difference is that the output is grouped into output indices pairs formed from the array of output indices according to the register.

Figure 5. Pairs of output keystream indices to determine the target registers in $$ S_{byte0}\&S_{byte1} $$ (Duplicated pairs are presented in matching colors).

Figure 6 presents the results obtained from the experiment with differential pairs of output indices for the target register $$ s_0 $$. The experiment shows that if a fault is injected into a random register within $$ S_{byte0} \& S_{byte1} $$ and $$ \delta_{34} = \delta_{38} = \delta_{54} = \delta_{66} = 1 $$ is observed, it can be concluded that the register $$ s_0 $$ is affected by the fault. This is because no other faulty registers in $$ S_{byte0} \cap S_{byte1} $$ produce $$ (\delta_{34} = \delta_{38}) = (1, 1) $$ or $$ (\delta_{34} = \delta_{54}) = (1, 1) $$ or $$ (\delta_{54} = \delta_{66}) = (1, 1) $$.

Figure 6. Number of times where $$ \delta_i=\delta_j=1 $$ for each register in $$ S_{byte0} \& S_{byte1} $$. The unique pairs of output indices listed here are for target register $$ s_0 $$. Pairs with both values equivalent to 100 are highlighted in green, while those greater than 0 and less than 100 are highlighted in red.

Generally, these conclusive pairs of output differentials can be obtained by examining the table columns where no other faulty target results in $$ \delta_{i}=\delta_{j}=1 $$, i.e., by observing table columns with only green-colored cells. Carrying out the experiment for all the sixteen registers in $$ S_{byte0} $$ and $$ S_{byte1} $$ using the output indices, the conclusive pairs for each register are directly obtained except for $$ s_{1} $$, $$ s_{3} $$, $$ s_{5} $$, $$ s_{7} $$, $$ s_{9} $$, $$ s_{11} $$, $$ s_{13} $$ and $$ s_{15} $$. Table 4 shows the conclusive pairs of output differentials for the sixteen registers in $$ S_{byte0} \& S_{byte1} $$.

Table 4 indicates that it is infeasible to obtain conclusive pairs of output differentials for registers $$ s_1 $$, $$ s_3 $$, $$ s_5 $$, $$ s_7 $$, $$ s_9 $$, $$ s_{11} $$, $$ s_{13} $$ and $$ s_{15} $$ with the unique pair of output indices. This is because the unique pairs of these target registers do not produce similar results, as shown in Figure 6, where there is no single column with only green-colored cells. Take $$ s_1 $$ as an example; the result produced using the unique pairs of $$ s_1 $$ in $$ S_{byte0} \& S_{byte1} $$ are displayed in Figure 7. It can be observed that no clear indication of pairs can conclusively determine the location of the faulty register. For instance, when $$ \delta_{64} = \delta_{82} = 1 $$, the faulty register may be $$ s_{0} $$, $$ s_{1} $$, or $$ s_{10} $$. The same situation appears in pair ($$ \delta_{76}, \delta_{82} $$). Since no columns contain only the green-colored cell, there are no conclusive pairs of output indices for the register $$ s_1 $$. The same case happens to register $$ s_1 $$, $$ s_3 $$, $$ s_5 $$, $$ s_7 $$, $$ s_9 $$, $$ s_{11} $$, $$ s_{13} $$ and $$ s_{15} $$.

Figure 7. Number of times where $$ \delta_i=\delta_j=1 $$ for each register in $$ S_{byte0} \& S_{byte1} $$. The unique pairs of output keystream indices listed here are for target register $$ s_1 $$. Pairs with both values equivalent to 100 are highlighted in green, while those greater than 0 and less than 100 are highlighted in red.

Determining required conditions to confirm the effect of random fault

After conducting the above-mentioned set of experiments for all the registers in $$ S_{byte0} \& S_{byte1} $$, it can be observed that a particular register is affected by the fault if several conditions are satisfied. Figure 7 shows that when $$ \delta_{64} = \delta_{82} = 1 $$, there are three possible fault registers, $$ s_0 $$, $$ s_1 $$, or $$ s_{10} $$. However, in Table 4, the conclusive pairs that can determine $$ s_0 $$ or $$ s_{10} $$ being injected with the fault can be found by observing if $$ \delta_{34} = \delta_{38} = \delta_{54} = \delta_{66} = 1 $$ and $$ \delta_{44} = \delta_{48} = \delta_{64} = 1 $$, respectively. Hence, $$ (\delta_{34} \neq 1 $$ or $$ \delta_{38} \neq 1 $$ or $$ \delta_{54} \neq 1 $$ or $$ \delta_{66} \neq 1) $$ and $$ (\delta_{44} \neq 1 $$ or $$ \delta_{48} \neq 1 $$ or $$ \delta_{64} \neq 1) $$ imply that $$ s_0 $$ and $$ s_{10} $$ are not injected with the fault. Furthermore, if $$ \delta_{64} = \delta_{82} = 1 $$, it can be concluded that $$ s_1 $$ is the register injected with the fault. Similarly, the conditions that should be satisfied to determine whether the registers $$ s_3 $$, $$ s_5 $$, $$ s_7 $$, $$ s_9 $$, $$ s_{11} $$, $$ s_{13} $$ and $$ s_{15} $$ are the faulty register can be concluded. The summary of the conditions is provided in Table 5.

After implementing this experiment on all eight two-byte arrays, the conditions required to confirm the target registers are determined for $$ S_{byte0} \& S_{byte1} $$ and $$ S_{byte2} \& S_{byte3} $$, but for the remaining six, some target registers cannot be conclusively determined; one example is $$ S_{byte10} \& S_{byte11} $$, where no target registers can be determined.

Determining required combinations of output indices to confirm the effect of random fault

To further investigate the conditions used to confirm all the registers in the remaining six two-byte arrays, instead of using pairs, a combination of all the unique output indices of the corresponding register is generated and used to further determine the faulty register. The process is similar to Algorithm 1, but the output pairs are replaced with a list of all unique output differentials of the register. As determined by Algorithm 2, arrays are declared to store the result of all the registers in the two-byte array of the 100-round tests. The experiment is carried out on every two consecutive bytes of LFSR.

For example, Figure 8 presents the results of the experiment conducted using all the combinations of output indices for register $$ s_{82} $$ in $$ S_{byte10} \& S_{byte11} $$. The outcomes illustrate that if a random register in $$ S_{byte10} \& S_{byte11} $$ is subjected to a fault, and $$ \delta_{46}=\delta_{82}=\delta_{104}=\delta_{116}=\delta_{136}=\delta_{148}=\delta_{168}=1 $$ is observed, then it can be inferred that $$ s_{82} $$ is affected by the fault. This is due to the absence of any other faulty register that can produce $$ (\delta_{46}, \delta_{82, }\delta_{104}, \delta_{116}, \delta_{136}, \delta_{148}, \delta_{168})=(1, 1, 1, 1, 1, 1, 1) $$ in 100 out of 100 tests. However, we observed that the signatures generated through this experiment are insufficient to precisely determine the fault locations for all the sixteen target registers in $$ S_{byte10} \& S_{byte11} $$. For example, Figure 9 indicates that when $$ \delta_{44}=\delta_{102}=\delta_{114}=\delta_{118}=\delta_{134}=\delta_{146}=\delta_{150}=\delta_{166}=1 $$, the fault might have been injected either at $$ s_{80} $$ or $$ s_{87} $$.

Figure 8. All unique output indices for register $$ s_{82} $$ are combined. The table illustrates the differentials of these combinations for each target register in $$ S_{byte10} \& S_{byte11} $$ (all values equal to 100 are colored in green).

Figure 9. All unique output indices for register $$ s_{80} $$ are combined. The table illustrates the differentials of these combinations for each target register in $$ S_{byte10} \& S_{byte11} $$ Differential combinations with all values equal to 100 are colored in green, and combinations with all values larger than 0 and less than 100 are colored in red.

Figure 10 demonstrates that for the target register $$ s_{81} $$ in $$ S_{byte10} \& S_{byte11} $$, although the combination of output indices equals one for $$ s_{81} $$ and $$ s_{82} $$, it only appears to $$ s_{81} $$ where the combined output indices are equal to one in the same round test. Here, the same round test refers to all the corresponding differentials being simultaneously one for the unique combinations of $$ s_{81} $$ or $$ s_{82} $$. Hence, the target register $$ s_{81} $$ can be determined using the result of the combined output indices.

Figure 10. Number of counts for which all the combinations of unique differentials are one for each register in $$ S_{byte10} \& S_{byte11} $$ in the 100 random tests. The unique combination of output indices listed here is for target register $$ s_{81} $$. Differential combinations with all values equal to 100 are highlighted in green, and combinations with all values larger than 0 and less than 100 are highlighted in red.

Algorithm 2: Determine the number of times when combined unique output indices result in a differential of one for each register in Grain-128AEAD
Require: Register $$ R_t $$ in two consecutive bytes and the corresponding output indices $$ z_j $$ of the two bytes
For$$ R_t $$do

Figure 11 shows the number of times where the differentials $$ \delta_i=\delta_j=1 $$ for each register in $$ S_{byte10} \& S_{byte11} $$. The unique combination of output indices listed here is for target register $$ s_{80} $$. As Figure 11 shows, using only the combined output indices, it is impossible to determine whether $$ s_{80} $$ is the faulty register, as the combined output indices are equal to one for both $$ s_{80} $$ and $$ s_{87} $$. However, applying this approach to all sixteen registers in $$ S_{byte10} \& S_{byte11} $$, we may infer the condition for identifying the target register $$ s_{80} $$ when all the unique output differentials of $$ s_{80} $$ are one while at least one of the unique output differentials of $$ s_{87} $$ is zero. Therefore, the condition for the injected fault to be located at $$ s_{80} $$ is given by $$ (\delta_{40}, \delta_{72}, \delta_{104}, \delta_{114}, \delta_{134}, \delta_{146}, \delta_{162}, \delta_{168})\neq (1, 1, 1, 1, 1, 1, 1, 1) $$, i.e., excluding the condition for $$ s_{87} $$, and $$ (\delta_{44}=\delta_{102}=\delta_{114}=\delta_{118}=\delta_{134}=\delta_{146}=\delta_{150}=\delta_{166}=1) $$, where $$ \delta_i $$ represents the $$ i^{th} $$ output index.

Figure 11. Number of counts for which all the combinations of unique differentials are one for each register in $$ S_{byte10} \& S_{byte11} $$ in the 100 random tests. The unique combination of output indices listed here is for target register $$ s_{80} $$. Differential combinations with all values equal to 100 are highlighted in green, and combinations with all values greater than 0 and less than 100 are highlighted in red.

After conducting the above approach to all the registers in the last six two-byte arrays, the injected faulty target can be located for the majority of the registers. However, there still exists a situation where a few target registers cannot be determined due to insufficient conditions. Then, the probability of successfully determining the remaining faulty register is calculated based on the experiment results of the combined output indices, as given in

where $$ P(s_i) $$ is the probability of determining the faulty register $$ s_i $$, and $$ m $$ and $$ n $$ stand for the number of times the faulty register and other registers equal one for the combined output indices in the same test round. For these experiments, we used the threshold of 100 random tests similar to the threshold value used in previous works. A larger threshold value enables us to estimate the probability more precisely; however, this also slows down the experimental process. To identify the fault target, we have included all the unique output signatures for a given target register. Hence, using the 100 tests to identify the target register is reasonable, given that all the respective output indices resulting in a differential of 1 in the same round test are negligible. In our experiments, if the probability of locating the fault is higher than 95%, then we consider that the fault target can be determined with a high probability. By implementing these approaches to all eight two-byte arrays in the LFSR, we can determine the required conditions to confirm which target registers in LFSR are injected with a fault. The details of the required keystreams to be observed and the conditions to be satisfied are listed in tables in Appendix A.

Summarizing required conditions to confirm the effect of random fault

The method employed in this work reduces the number of output indices that need to be observed to identify the target register in the LFSR. For example, based on earlier observations, the output differentials required to be observed for identifying the fault targets in $$ S_{byte0} \& S_{byte1} $$ are 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 64, 68, 82, 84, 86, 92, 94, and 96. Applying this method to all the eight two-byte arrays, we get the output indices required for the entire LFSR. The total number of required keystream bits for every two-byte array is calculated based on the tables in Appendix A. Table 6 shows the number of keystream bits that need to be observed in each two-byte array to confirm whether the register is affected by the injected fault.