Hugues Thiebeauld
email: hugues.thiebeauld@eshard.com

Georges Gagnerot
email: georges.gagnerot@eshard.com

Antoine Wurcker
email: antoine.wurcker@eshard.com

Christophe Clavier
email: christophe.clavier@unilim.fr

SCATTER : A New Dimension in Side-Channel

Keywords: side-channel, scatter, mutual information, Pearson chisquared

Side-channel techniques have well progressed over the last few years, leading to the creation of a variety of statistical tools for extracting the secrets used in cryptographic algorithms. Such techniques are taking advantage of the side-channel traces collected during the executions of secret computations in the product. Noticeably, the vast majority of side-channel attacks requires the traces have been aligned together beforehand. This prerequisite turns out to be more and more challenging in the practical realisation of attacks as many devices include hardware or software countermeasures to increase this difficulty. This is typically achieved applying random jittering or random executions with fake operations. In this paper, we introduce scatter, a new attack which has the potential to tackle most of the alignment issues. scatter brings a new dimension to improve the efficiency of existing attacks and opens the door to a large set of potential new attack techniques. The effectiveness of scatter has been proven on both simulated traces and real word secure products. As a result, scatter is a new side-channel technique particularly powerful when the trace alignment represents an issue, or even when considering low-cost attacks, as the requirements in terms of equipment and expertise are significantly reduced.

Introduction

Over the past few years, Side-Channel Attacks have been proven to be effective in attacking a wide range of hardware devices [START_REF] Daniel Genkin | Stealing keys from pcs using a radio: Cheap electromagnetic attacks on windowed exponentiation[END_REF][START_REF] Daniel Genkin | Get your hands off my laptop: Physical side-channel key-extraction attacks on pcs[END_REF][START_REF] Daniel Genkin | RSA key extraction via lowbandwidth acoustic cryptanalysis[END_REF]. Recently their application to compromise obfuscated ciphers including whitebox cryptographic libraries has been proven. Therefore, software based products can be subject to these attacks [START_REF] Bos | Differential computation analysis: Hiding your white-box designs is not enough[END_REF]. When successful, the impact of side-channel attacks is severe as it leads to the disclosure of the secret cryptographic key. In case of partial recovery, several techniques [START_REF] Poussier | Simple key enumeration (and rank estimation) using histograms: An integrated approach[END_REF] can be used to achieve the whole key recovery. As a result, a flaw can be exploited and leads to losses. On the other hand, the perception of the product security can be dramatically undermined. In order to avoid any exposure on the field, right protections must be implemented and validated by practical testing.

There are a number of side-channel attack techniques to take into consideration. Beginning with the original Simple Power Analysis (SPA) [START_REF] Paul | Timing attacks on implementations of diffie-hellman, RSA, DSS, and other systems[END_REF] and Differential Power Analysis (DPA) [START_REF] Paul | Differential power analysis[END_REF], several other techniques have been developed over the past few years. The most famous distinguishers are CPA [START_REF] Brier | Correlation power analysis with a leakage model[END_REF], standing for Correlation Power Analysis and exploiting Pearson coefficient, the MIA [START_REF] Gierlichs | Mutual information analysis[END_REF], standing for Mutual Information Analysis and exploiting the Shannon entropy and the LRA for Linear Regression Analysis [START_REF] Doget | Univariate side channel attacks and leakage modeling[END_REF][START_REF] Schindler | A stochastic model for differential side channel cryptanalysis[END_REF]. These attacks can be run on a device without any preliminary knowledge about their implementation. Some other attacks (such as the Templates Attacks also named Profiled Attacks) [START_REF] Chari | Template attacks[END_REF] make use of a profiling stage used to target other similar devices through a matching phase. Finally, another testing methodology with the T-Tests have been introduced [START_REF] Jun | Is your design leaking keys? Efficient testing for side-channel leakage[END_REF][START_REF] Standaert | How (nnot) to Use WWelch's T-test in Side-Channel Security Evaluations[END_REF][START_REF] Gierlichs | Templates vs. stochastic methods[END_REF][START_REF] Goodwill | A Testing Methodology for Side Channel Resistance Validation[END_REF] to characterise potential leakages in an efficient manner.

In the same period several countermeasures have been regularly published and improved in order to defeat these attack techniques. Most common ones consist in misalign different executions with hardware and software techniques [START_REF] Coron | A new DPA countermeasure based on permutation tables[END_REF][START_REF] Tunstall | Efficient use of random delays in embedded software[END_REF][START_REF] Coron | An efficient method for random delay generation in embedded software[END_REF] and/or to de-correlate the information from the traces using random values for masking the data manipulated. In the masking case, more complex but realistic, attacks named Higher-Order Side-Channel Analysis introduced by Messerges [START_REF] Messerges | Using second-order power analysis to attack DPA resistant software[END_REF], studied [START_REF] Prouff | Statistical analysis of second order differential power analysis[END_REF] and later improved [START_REF] Belgarric | Timefrequency analysis for second-order attacks[END_REF][START_REF] Lomné | How to estimate the success rate of higher-order side-channel attacks[END_REF][START_REF] Moradi | Correlation-enhanced power analysis collision attack[END_REF][START_REF] Oswald | Practical second-order DPA attacks for masked smart card implementations of block ciphers[END_REF][START_REF] Tunstall | Masking tables -an underestimated security risk[END_REF] is still applicable when some mask values are identical at some points of interest for the attack in the traces. Generally speaking, traces alignement remains a main technical issue when performing first and higher order side-channel attacks in practice.

We present in this paper a new side-channel analysis technique named scatter which has the potential to tackle most of the alignement issues including random jittering and random order execution. We consider scatter opens doors to improvements in side-channel analyses including higher order sidechannel attacks and requires the development of innovative countermeasures to strengthen the security of existing products. This new technique has been proven efficient and is presented with practical experiments. This paper is organised as follows. Section 2 gives necessary background on side-channel analysis. We present in Section 3 the principles of our scatter method. Section 4 presents a first validation of scatter efficiency based on simulations when practical results on physical measurements from a real hardware device are given in Section 5. Section 6 shows a comparison with some other window-based techniques, such as Fast Fourier Transform (FFT) or average. Section 7 introduces how the technique can be extended to higher order attacks. We discuss the impact of this new technique on secure products and state-of-the art countermeasures in Section 8, and conclude in Section 9.

Side-Channel Analysis Practical Issues

Quite remarkably, except for simple side-channel attacks using one single trace, all attack techniques mostly rely on the assumption that the measurement or data traces have been aligned as much as possible before applying a statistical analysis tool. In other words, it requires the estimated variable to be located at the same (X-axis) index along a certain number of traces -being the minimum number of aligned traces required to exploit the leakage with the statistical test. Without this prerequisite condition, none of the attack listed previously leads to a success. And this condition becomes more and more an issue when the cryptographic algorithm is executed on recent secure devices and on complex devices such as a SoC (System on Chip) in a mobile platform, which includes more complex mechanisms such as multi-threading.

When conducted practically, the alignment step may be time consuming and difficult. This requires a specific expertise and may increase dramatically the number of traces required to expose the key when not properly done. Moreover, the alignment represents a significant part of the effort for performing an attack. Conscious of this, some interesting, but limited, work has been developed to investigate ways to automate the alignment. We can quote the elastic alignment [START_REF] Jasper | Improving differential power analysis by elastic alignment[END_REF] exploiting fast Dynamic Time Warping. Some other techniques explored the use of wavelets [START_REF] Debande | Wavelet transform based pre-processing for side channel analysis[END_REF][START_REF] Liu | Wavelet-based noise reduction in power analysis attack[END_REF][START_REF] Muijrers | RAM: rapid alignment method[END_REF]. All these techniques represent good tools, but they remain hard to apply in a generic way and sometimes they turn out to be inefficient.

On the other hand, some other studies investigated the opportunity to work in the frequency domain via Fourier transformations. Interesting results were obtained on second order attacks in [START_REF] Belgarric | Timefrequency analysis for second-order attacks[END_REF]. Indeed, Fourier transformations represent a valuable tool for tackling a misalignment as it integrates a piece of trace in time domain into its equivalent in frequency domain. All values gathered within the window, even non-aligned, are spread over their corresponding set of frequencies. Practically, this technique shows interesting results, but it remains inefficient in a lot of practical cases. The downside of this technique is mostly related to the nature of Fourier transformations. Indeed, the information is spread over the corresponding sets of frequency and can face a lack of alignment in case of variable clocks. A second issue concerns the relationship between the window size and the information sampling in the frequency domain. Last but not least, the notion of frequency is not all the time applicable, such as for studies of whitebox cryptography implementations, where the side-channel traces are made of data traced from their execution in a emulated environment [START_REF] Bos | Differential computation analysis: Hiding your white-box designs is not enough[END_REF].

Since the alignment is a strict condition for most side-channel attacks, a large set of protections aim at making this task as difficult as possible. Excluding the inherent protocol based countermeasures (padding, session-keys) we can categorise the side-channel countermeasures in the two following categories:

-Signals desynchronisation: it aims at avoiding as much as possible an efficient alignment between the same point of interest of the execution among the different traces (executions). This can be achieved with hardware security features: noise generators, dummy cycles, clock jittering or power filtering. It can also be done using software security measures: dummy operations, inserting fake or variable instructions amongst the real one, execute the operations in random order but constant time [START_REF] Coron | A new DPA countermeasure based on permutation tables[END_REF][START_REF] Coron | An efficient method for random delay generation in embedded software[END_REF][START_REF] Tunstall | Efficient use of random delays in embedded software[END_REF]. Doing so, it makes the alignment task difficult or even impossible when the same operation is hidden in the middle of fake but similar operations.

-Signals de-correlation: the principle is to make the leakage independent from the sensitive data and to prevent attackers from predicting intermediate value manipulated during the known algorithm execution. Masking and randomisation techniques are in this category. It consists of the application to the sensitive data of a randomly chosen value, named the mask [START_REF] Paul | Timing attacks on implementations of diffie-hellman, RSA, DSS, and other systems[END_REF][START_REF] Akkar | An implementation of DES and aes, secure against some attacks[END_REF][START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF][START_REF] Coron | On boolean and arithmetic masking against differential power analysis[END_REF][START_REF] Fumaroli | Affine masking against higher-order side channel analysis[END_REF][START_REF] Rivain | Provably secure higher-order masking of AES[END_REF]. We will define those methods under the term masking in the following.

As a result, there remains a significant technical challenge of extracting a secret key when the information is present in the traces but the alignment is not obvious. Scatter addresses this technical problem, by removing or at least reducing the need of alignment.

Notations. In this paper the following notations are being used:

-C i = E(P i , K) where E(., .) is an encryption function with plaintext P i and a secret key K, -P denote the set of the n plaintext values {P 0 , . . . , P n }, -S denote the set of n side-channel traces {S 0 , . . . , S n } collected from the measurements of E(P i , K) on the targeted device, -U denote the set containing all the possible ordinates values of points of S, -#S = #P = n: the number of elements (traces) of the sets S and #P, -S i,j the j th point of i th trace S i of the set S, -T i denote the set of #T i Points of Interest in the trace S i , so the points related to the side-channel leakage, -O i denote the set of #O i Points of No-Interest in the trace S i , so the points not related to the side-channel leakage, -S i = T i ∪ O i , -G = {g 0 , . . . , g b-1 } is the set of b = 2 possible guesses for a targeted secret key -bit value k of whole key K, ⇒ e.g. G = {0, . . . , 255} for an 8-bit guess and secret key k. g or g i is one guess value and g * = k is the good -bit guess f (P i , g) is the intermediate calculation targeted for the statistical analysis, for instance the output of the SubBytes in the first round of the AES, w(.) is the function used to model the way the information leaks, for instance w(x) is the Hamming weight of point value x in case of a Hamming weight based leakage, -H is the set of possible values h = w(x) for x = f (P i , g), for instance H = {0, . . . , 8} for h = w(x) in the case where x are byte values. -I (w)(Pi,g) is the set of corresponding modelized intermediate values w o f (P i , g) for the guess g and trace S i (and plaintext P i ).

scatter Principle

scatter lies on the exploitation of side-channel leakages using an innovative representation of the measurements points and the way to process them. More particularly it integrates all measurements within a window of interest and convert the data into their distribution depicting the number of times each value occurred. The distribution method is given in Algorithm 1. It is processed for each trace by choosing a relevant window of interest to target the leakage. Figure 1 shows the window selection in traces and the corresponding conversion into their respective distributions. We will denote hereafter distribution of a trace the outcome of the distribution process for a trace.

Algorithm 1: Distribute Trace Data Doing so, a new dimension is created. Indeed the useful information counts the same wherever it stands in the window. Furthermore it lies together with adjacent measurements, that are mostly independent from the estimated variable. In the following, we use the defined notation T i for the leakage related measurement part and not related part in a trace S , #T i the corresponding number of leaking points, #O i the corresponding number of not leaking points. The corresponding distribution for the i th realisation can be expressed as:

Input: trace Si Output: DT D(Si) = DS i 1 begin 2 DS i ← {0, . . . , 0}; 3 for j ∈ [0, . . . , #Si -1] do 4 DS i [Si,j]+ = 1;
DT D(S i ) = DT D(T i ) + DT D(O i ) (1)
For the next step of the attack, the distribution of each trace needs to be sorted against the estimated value over all key guesses. The estimated value is denoted h. In this paper, h will be chosen as the hamming weight of the targeted variable. This choice is not restrictive; other models could be applied, such as the value itself or any subset. Moreover, it is important to mention that scatter is built in such a way that it does not assume anything about the linearity of the model. In other words, scatter works indifferently on either linear or non linear leakages.

Sorting the traces requires the creation of so called accumulators. An accumulator Acc (g)(h) is a three dimension vector defined for each guess g and for each value h ∈ H. This Acc (g)(h) is collecting trace distributions added on top of each others for each guess g and value h on all traces of S for the #U possible points values. To discriminate the useful information, the sorting has to be to done for each key guess g and the proper h value given by the estimated current value w o f (P i , g). Denoting #G the number of key guesses and #H the number of potential values h, the attack requires therefore the allocation of #G × #H accumulators. Taking the example of an 8-bit variable f (P i , g) estimated from an 8-bit key chunk (ie. byte) value k, scatter requires then the allocation of 256 × 9 accumulators, as #G = 256 and #H = 9.

In the course of the attack, each trace, once distributed, is processed #G times by accumulating it into the corresponding Acc (g)(h) by implementing Algorithm 2.

Algorithm 2: Accumulate Trace Data According to Guesses

Input: trace set S,intermediate values

I (w)(P i ,g) Output: accumulator set Acc (g)(h) 1 begin 2 Acc (g)(h) ← T able[null, 1, #G][null, 1, #H][null, 1, #U ]; 3 for i ∈ [0, . . . , #S -1] do 4 DS i ← DT D(Si); 5 for g ∈ G do 6 h = w o f (Pi, g); 7 Acc (g)(h) + = DS i ; 8 end 9 end 10 end
Once the accumulation step is performed, the corresponding values shall be normalised with the total number of point within the accumulator. Denoting X the random variable related to the measurement, and Y the random variable related to the estimation, the new expression leads to the probability density function pdf (x) = P (X = x/Y ).

It is important to note that scatter is not tied with a leakage model. It targets successfully hamming weight related leakage, for both linear or non linear model. Other models, such as the value itself or any subset can be considered assuming to adapt accordingly the accumulators and the way the distributions are sorted into them. For the sake of clarity, the hamming weight model is chosen in this paper. The corresponding accumulation algorithm depicted as Algorithm 3: Normalize Accumulator

Input: accumulator Acc (g)(h) Output: normalized accumulator pdf (g,h) 1 begin 2 sum ← 0; 3 pdf (g,h) ← 0, . . . , 0; 4 for u ∈ U do 5 sum+ = Acc (g)(h) [u]; 6 end 7 for u ∈ U do 8 pdf (g,h) [u] = Acc (g)(h) [u]/sum; 9 end 10 end
Algorithm 2 can be processed as follows returning 256 × 9 accumulators:

Having done this, it is worth exploring the expected behaviour in the resulted distributions pdf (g,h) . Interestingly, different profiles should pop up depending on the correctness of the key guess. On one hand, the non informative points within O spreads themselves in a similar way regardless the key guess. More particularly, they are converging towards an asymptotical distribution related to the nature of the signal. On the other hand, each point belonging to T follows a Gaussian distribution for the wrong key guess, as they have not been sorted against their real value. This is not the case for the correct key guess, where the set of #T points sticks to the same area with a measurement data matching with the estimation. A simple graphical representation is depicted on Figure 2. Getting this behaviour, it becomes possible to discriminate pdf (k,h) related to the correct key from all other pdf (g,h) for a given estimation h. To achieve this, different distinguishers may be used. For instance authors in [START_REF] Linge | Using the joint distributions of a cryptographic function in side channel analysis[END_REF] suggested several ones to compare different distributions . In the context of this paper, two distinguishers will be explored using classical statistical tools in the information technology area. The first one makes use of Pearson's chi-squared (χ 2 ) statistical test. This test is a good fit as it expresses how much a distribution differs from a general distribution. The general formula is given as follows:

χ 2 = u∈U (B[u] -E[u]) 2 E[u] B[u]
being the observed frequency of u and E[u] the expected frequency of u. The application to scatter is pretty much straightforward, as it is providing a way to explore how much a accumulator N ormAcc (g)(h) differs from the expected frequency that can be expressed as the average distribution:

χ 2 (g)(h) = u∈U (pdf (g,h) [u] - 1 #G • g ∈G pdf (g ,h) [u]) 2 1 #G • g ∈G pdf (g ,h) [u]
Following this, the factors can be combined over the different values h in order to provide a simple discriminant related to g:

scatter χ 2 (g) = h∈H χ 2 (g)(h)
A second distinguisher exploits the mutual information as introduced in [START_REF] Gierlichs | Mutual information analysis[END_REF]. The difference of entropy remains an appropriate factor, in spite of the presence of O. In the same way as the work described in this area, the difference of entropy is given by the formula:

MI = X P (X) • log(P (X)) - Y P (Y ) • X P (X/Y ) • log(P (X/Y ))
Which can be written in a different way expressing better the difference of behaviour we are looking for:

MI = Y P (Y ) • ( X P (X) • log(P (X)) - X P (X/Y ) • log(P (X/Y ))
Mutual Information can be simply applied to scatter as any individual value in pdf (g,h) represents the probability P (X/Y ). The rest can be translated as follows: P (Y ) = P (Y = h) and P (X) = N orm( h Acc (g,h) ) for any arbitrary g as this value yields the same regardless g. The resulting expression becomes:

scatter MI (g) = h∈H P (Y = h) • ( u∈U P (X)[u] • log(P (X)[u]) - u∈U pdf (g,h) [u] • log(pdf (g,h) [u]))
In the following, both distinguishers are systematically kept as practical results have shown different levels of success for one or the other.

Attack Simulation

Practical validations of scatter effectiveness were first validated on simulated traces. This study was done to analyse scatter's resilience to an additive gaussian noise on one hand and to the level of misalignment on the other hand. Along the testing, the question of a fair comparison with existing techniques was raised. Indeed, the integration in time confers a new dimension not relevant for classical techniques. This explains why the focus has been made in extending the window of interest together with the addition of a random shift in time of the traces. By extending the size of the window of interest, this highlights how much scatter remains efficient in spite of the addition of a larger number of unrelated points (O). Since scatter is not influenced by the location of the leakage point within the window of interest, the traces were shifted in time in such a way that the leakage point always remains within the window with the same level of probability about its location. Doing so, it provides a way to analyse the technique robustness facing poorly-aligned traces, or when different patterns have to be integrated to tackle shuffled implementations. Different distinguishers or techniques have been created in the side-channel area, such as DPA, CPA, MIA, LRA. As they all assume an alignment prior to running the attack, only the CPA is used in this paper for the sake of comparison.

scatter concerns all algorithms subject to side-channel analyses. For the sake of consistency, all practical work described in this article focuses on the AES algorithm. This choice was made without removing the general impact of the new technique. Furthermore, simulation traces were generated to represent the Hamming weight of all intermediate values during an AES 128 encryption.

The simulations for widow size is f were generated following the process:

1. Generate a secret key, the value is kept for checking the validity of the results but is not exploited for the attack, 2. Generate a 16-byte long random plaintext, 3. Compute and save the output of one SBOX from SubBytes operation during the first round of AES 128 computation, 4. Generate and save f -1 random bytes, 5. Convert all values into their Hamming weight, 6. Apply a chosen Gaussian noise level to simulate non-perfect measurements, 7. Apply countermeasures such as shuffling, 8. Go back to step 2 until enough simulation traces are generated.

The Gaussian noise was added using the following formula:

T j = α × (HW (data) + noise(σ)) + β (2)
O j = α × (HW (random data) + noise(σ)) + β (3)
All points share the same α and β parameters and σ is the standard deviation of the Gaussian noise applied with a mean set to 0. The simulations results have been averaged over different campaigns in order to smooth down potential statistical inconsistencies. Within the window of interest, a random shift in time between 0 and f -1 is applied so that the leakage point falls randomly with the same probability. As a result, the maximum number of traces with the leakage point properly aligned converges to 1/f . On following figures, the X-axis represents, in logarithmic scale, the size f of the window of interest for scatter methods results (bottom scale of the trace) and 1/f the portions of related points at each instant of the studied area for CPA results (top scale of the trace). The Y-axis represents the number of traces necessary to extract the key value. The Y-axis is in normal scale, except in Figure 4 where the logarithmic scale is used. The score is defined when the correct key value remains above all guesses for the given key byte. One can notice that the lowest this number is, the most successful the attack. the effectiveness of the techniques with different levels of Gaussian noise (respectively σ = 0 and σ = 3). All computations were made using both scatter χ 2 and scatter MI distinguishers. Results are depicted together with CPA computations, where the highest outcome was taken into account within the window. For both scatter techniques, all points in the window were integrated. Remarkably, scatter's outcomes remain solid with a growing window size, even though it implies the integration of an increasing number of non informative points (O). In this configuration, scatter MI configuration stays slightly better than scatter χ 2 , but stays comparable. Unsurprisingly, CPA results decrease significantly (the number of traces needed grows faster) when the shift in time grows. Indeed, a poor alignment quickly undermines the effectiveness of the attack.

Depending on the level of noise σ, the number of traces necessary to retrieve the key changes. However, the general outcome remains similar with scatter techniques showing valuable results even with large windows.

For small windows, and consequently a fairly good alignment, the CPA technique give better results. More generally speaking, this indicates that classical techniques remain relevant when the traces are well aligned. However, the results confirm that scatter represents a real value when the condition of alignment cannot be satisfactorily fulfilled, due to a poor quality of traces or shuffling countermeasures. 3a showing results as linear Finally, Figure 4 shows the same results as Figure 3a but with logarithmic scale on Y-axis. In that representation the results follow linear representation, illustrating scatter methods' resilience to window size f and shift in time. In this model, the behaviour is highly predictable.

In Time Integration: Accumulate Information

The previous simulations took into account one single leakage point. With the integration in time, scatter has the ability to combine different leakage points in time and consequently cumulate nicely the information available. As a result the technique gives stronger results. The benefit of accumulating different points of leakage is achieved, even though their measurement levels are not identical.

To illustrate this benefit, corresponding simulation traces were generated using the same methodology as previously. For this purpose, the traces were forged using two set of points of equal cardinality: f /2, the sets having point parameters equal to (α 1 , β 1 ) and (α 2 , β 2 ) respectively. Compared to the previous analysis, the window of interest contains two leakage points and no longer one. Figure 5 captures the corresponding results computed with a noise σ = 0. In dashed, the outcome of the attacks using one single leakage point is depicted and, in plain, two leakage points are present within the window of interest.

The outcome of this analysis shows a positive impact of having two leakage points instead of one. Using either scatter χ 2 or scatter MI distinguishers, the gain is significant and reaches in this case a factor of at least 2. In other words, the key could be extracted with at least twice less traces in the same conditions. This result could be obviously magnified in the event of more leakages. Appendix A shows other observations for different combination of α and/or β. They all lead to the same conclusion of a significant gain when dealing with more leakage points.

In Time Integration: Face the Shuffling Countermeasure

Shuffling countermeasure has been shown as an efficient way to protect algorithms. This is typically implemented by randomising the execution order of independent operations. As an example this works well when executing SBOX operations during the SubBytes of an AES. In the same vein, any sensitive operation can be concealed, by hiding it randomly in the middle of fake but similar operations. Doing this makes the identification of the correct operation difficult, or even impossible, and prevents the alignment between different execution traces.

By either integrating the whole area in the trace, or by picking up the small pieces for each individual operation, scatter has the potential to defeat such protection. Indeed, fake values are likely independent from the targeted value, and consequently do not interfere negatively during the discrimination of the right key guess. Equivalent to random noise, it can be considered that the results depicted in Figure 3 remain valid to highlight scatter performances in case of shuffling.

Practical Results

Further testing were performed on a hardware device. This was an unprotected AES 128 implementation running on an 8-bit AVR micro-controller. Physical measurements were performed using a low-end near-field electromagnetic probe and a low cost acquisition hardware. The global cost of the equipment used for this campaign turns around $1 000. The setup was chosen to represent a real case scenario with poor quality of traces.

The choice was made to acquire traces with an external trigger and no jitter. AES-128 encryptions were performed with a fixed key and random plain texts. In a post processing, the aim was to downgrade the initial alignment with a random shift in time as it was done on the simulation traces previously. As it can be observed on Figure 6, the quality of the traces is very poor. Without any signal processing, we did not find any way to align these traces since no pattern was found exploitable. With a random shift in time, the model looked realistic to represent an attack scenario with jittering and no good way to perform the alignment. Figure 6 shows the processing of one round of AES 128 encryption. The operations are not visible but it gives an idea of the number of points involved.

In a similar way as the previous testing, scatter's performance is analysed with the integration of a growing number of points. A random shift in time is applied to spread the leakage uniformly within the window of interest. Once done, both scatter and CPA were applied yielding to the results depicted in Figure 7. Xaxis is in a logarithmic scale and Y-axis shows the number of traces necessary to get the good key guess staying on top of all other guesses. These result confirm the observations made during the simulation campaign. All techniques expose the secret key. The results stay relatively in the same range for a low level of misalignment. A significant gap appears quickly showing a strong resilience of scatter techniques to the window size. The good results can be explained by multiple points of leakages present in the window of interest. In this case, both scatter χ 2 or scatter MI show good results, with slightly better outcomes for the scatter MI distinguisher.

For having a clear view of the integration in time, Figure 8 illustrates scatter techniques evolution together with the time representation of the AES encryption. Looking at this figure, it becomes clear that scatter techniques remains very efficient when integrating the whole SubBytes operation, including the 16 SBOXes. This means that any random order execution countermeasure would have no effect, and the attack results remain the same. Furthermore, the technique is still valid albeit less efficient when integrating the whole round operation. This gives a lot of latitude for exploring the leakage area with raw window sizes.

As a result, this practical session led to several valuable observations. First of all, scatter showed a great benefit when handling raw traces, where alignment is not obvious. This can be exploited to characterise the leakages in an exploration mode or even to break the implementation when a good alignment could not be performed. Besides, it proved that scatter has the potential to defeat several countermeasures, such as any random executions. Fig. 8: Practical result of a growing window integration reachin sequencially the size of a suboperation(SBOX), algorithm step (SubBytes), a round and more

A comparison with window-based techniques

The comparison between scatter and preprocessing technique (such as average or FFT) is not easy. Indeed the results can vary significantly from one device to the other, or remain highly dependent on the model when dealing with simulation traces.

The main purpose of the following test was to define a realistic simulation model and highlight how much the different techniques perform in that case.

To serve this purpose a model with two sets of parameters was defined. One stating the jitter and the related window size. And a second describing the leakage model, including the value representation and the noise.

Different levels of jitter were chosen, more particularly 3, 10, 30 or 50 points. The maximum jitter value is denoted J and a dedicated set of test was performed for the given value J. With J defined, sets of traces were generated with 2 * J points per traces. The right value is located at the same index J for all traces. A random jitter was simulated by taking J points from an index randomly chosen between [0, J]. Doing so, the model integrates a jitter J and the information is always present once within the window of size J.

Regarding the trace profile, the intention was to remain generic and therefore to cover most of practical cases. The hamming weight of values was applied with couples (α, β), with (α, β) defined random in time but remaining the same from a trace to the other:

T i,j = α j × HW(x i,j ) + β j + Random(σ)
with:

-T i,j , the point j within the trace i -HW(x) function returning the Hamming weight of the value x -N (0, σ 2 ) representing a noise factor The Gaussian noise has been chosen at σ = 1 representing a fair amount of noise without being excessive.

Taking into account that a trace is not only made of leakage points, even unrelated to the targeted variable, α was chosen equal to 0 for 70% of the points, and α randomly chosen between [START_REF]Cryptographic Hardware and Embedded Systems -CHES 2014 -16th International Workshop[END_REF][START_REF] Brier | Correlation power analysis with a leakage model[END_REF] for the 30% remaining points.

β was chosen randomly between [50,200] for all points. α and β range of values were defined with the aim to represent an information fitting an 8-bit oscilloscope with values staying within the range [0, 255]. The realization of the noise N (0, σ 2 ) being a real value, data in the traces were truncated to stay within the range [0, 255].

x i,j are 8-bit values chosen randomly within [0, 255]. The point of interest is located at the index j = J.

For this study, our choice was to compare scatter with respectively a CPA average and the CPA FFT. For a proper comparison, it was important to keep the same window of points for all techniques. The window remains fix in this set of results. Applying a moving average would not help the comparison, as the same could be applied to all techniques.

For the CPA average, all points within the window were summed together and the CPA subsequently applied. On the other hand, a Fourier transformation was performed and the CPA applied to the resulting real value. The first point of the FFT was excluded as the frequency 0 is equivalent to the averaged window and therefore would give the same result as the CPA average.

The results shown below are the outcome of 200 runs with the same parameters. These runs aim at smoothing down the statistical discrepancy. The selected jitter levels J have been applied. When the maximum jitter level was increased, it resulted to get a larger window and therefore required more traces to get a strong success rate for all techniques. Doing so, the corresponding impact of the window size could be observed.

All results are captured on the following figures: For all jitter levels, it can be observed that scatter success rate turns out to be higher than the other techniques after a reasonable amount of traces has been processed.

As a result, this case shows that scatter technique represents a value when jitter and desynchronisation could not be fully removed.

An Introduction to Higher Order Extension

As previously said, one of the most efficient countermeasure to protect products from (first-order) side-channel attacks uses random values for masking the operations (i.e. data manipulated) [START_REF] Rivain | Provably secure higher-order masking of AES[END_REF][START_REF] Fumaroli | Affine masking against higher-order side channel analysis[END_REF][START_REF] Coron | Higher-order side channel security and mask refreshing[END_REF]. When properly implemented, masking countermeasures are effective and first order leakage is no longer available. As a result, scatter in the simple form does no longer work and needs to be extended into higher order attacks. In a same way, classical attacks had to be adapted to extract the information when facing masking countermeasures. This led to the creation of dedicated techniques whose principle is to select and combine two (resp. n) pieces of the same trace: one targeting the value related to the secret, and the second targeting the mask value, we then perform a second-order (resp. n th -order) side-channel analysis [START_REF] Belgarric | Timefrequency analysis for second-order attacks[END_REF][START_REF] Lomné | How to estimate the success rate of higher-order side-channel attacks[END_REF][START_REF] Messerges | Using second-order power analysis to attack DPA resistant software[END_REF][START_REF] Moradi | Correlation-enhanced power analysis collision attack[END_REF][START_REF] Oswald | Practical second-order DPA attacks for masked smart card implementations of block ciphers[END_REF][START_REF] Prouff | Statistical analysis of second order differential power analysis[END_REF][START_REF] Tunstall | Masking tables -an underestimated security risk[END_REF]. In these conditions, the secret can be extracted requiring a significant number of traces compared to the first order technique.

Except the techniques using Fourier transformations, second-order attacks practicality is significantly challenged by the alignment issue. Indeed, the alignment turns out to have a square complexity as it concernes both pieces of traces. As a result, the number of traces necessary to succeed a second order attack is even higher as the perfect alignment is most of the time impossible to achieve. This is no longer the case with scatter at a higher order. Adding another dimension will create a scatter second order that will defeat all CPA leakage model and alignment restriction to achieve cutting-edge second order attack. This will be subject to further work.

Impact on Current State-of-the-Art

With the introduction of a new attack technique, it is important to consider the impact for secure implementations. First of all, the first order scatter technique only works for algorithm with first order vulnerabilities. However it is possible to extend the attack, this be subject to further work. The main impact concerns the hiding countermeasures that scatter may seriously threaten. Indeed, gathering the useful information within a window of interest may defeat the effort of desynchronisation, and more particularly when the shift in time remains limited, such as a clock jitter or some dummy instructions. Potentially the cost incurred by such hardware countermeasures may be questioned if scatter technique turns out to be efficient on the device. Furthermore, practical testing on secure devices showed that scatter remains effective with large windows. This very much depends on the signal to noise ratio and the number of points of interest caught within the window. In that cases, some other well-known countermeasures may be defeated. This is the case of shuffling protections, hiding the right operation randomly within a significant number of fake operations.

The success of the attack will vary from one device to another, but no clear restriction seems to appear and scatter technique represents a clear threat for hiding type of protections. Taking into account this new paradigm, the choice of building a strong algorithmic protection looks like the right way for securing a software-or hardware-based cryptographic implementation. and practical cases, the testing results have shown a high effectiveness, particularly when the set of traces has not been or could not be aligned prior to the attack. Unlike a large number of existing attacks, the scatter technique is still able to extract the secret key, even when the traces are non-aligned. As a result, the technical difficulties related to practical side-channel realisations are significantly lowered. This provides new opportunities of attack when alignment is not possible properly due to the nature of the traces. On the other hand, it makes the attacks cheaper in terms of equipment cost and expertise level. As a result, it is very likely that scatter will make practical realisations of side-channels more affordable.

The technique is generic and consequently concerns all algorithms, both symmetrical and asymmetrical. Furthermore, it opens up new exploitation opportunities, particularly when combining different pieces of information available during a sensitive algorithm execution. Extensions to higher order attacks are powerful and were briefly introduced in this article. Representing a new step in side-channels and bringing a complement to existing techniques, scatter questions the relevance of many countermeasures, more particularly those aiming at making the alignment difficult or impossible.

A Low Influence of α and β Variations onto scatter Method

Figure 13 represent a comparison between Figure 3a results (repelled in dashed lines) where only one leakage point with parameter (α,β) value was used, and the results obtained with two leakage points with variations onto α, β, both or neither respectively on 13a, 13b, 13c, 13d. Those results show that the modification of parameters have a reduced impact onto attack effectiveness.

The improvement brought by a second leakage point with same parameters (Figure 13d) is lowered but stay strong when parameters are modified.

2 Fig. 1 :

 21 Fig. 1: Illustration of transformation from temporal traces portions to untemporal distributions.

Fig. 2 :

 2 Fig. 2: Pdf functions for the right and a wrong key guess

3 Fig. 3 :

 33 Fig. 3: Simulation of the impact of window size parameter f onto CPA and scatters methods under σ = 0 and σ = 3 noises

  Figures 3a and 3b illustrate the effectiveness of the techniques with different levels of Gaussian noise (respectively σ = 0 and σ = 3). All computations were made using both scatter χ 2 and scatter MI distinguishers. Results are depicted together with CPA computations, where the highest outcome was taken into account within the window. For both scatter techniques, all points in the window were integrated. Remarkably, scatter's outcomes remain solid with a growing window size, even though it implies the integration of an increasing number of

Fig. 4 :

 4 Fig.4: Y-axis log scale applied onto Figure3ashowing results as linear

Fig. 5 :

 5 Fig. 5: Comparison results when integrating one point of leakage (dashed) vs two points of leakage (plains)

Fig. 6 :

 6 Fig. 6: Near field EM traces from a HW AES 128 execution showing that even synchronized traces do not share identifyable patterns

Fig. 7 :

 7 Fig. 7: Practical result similar to simulation results

Fig. 9 : 10 Fig. 11 :

 91011 Fig. 9: comparison with jitter = 3 Fig. 10: comparison with jitter = 10

Fig. 13 :

 13 Fig. 13: Comparision one point leakage (dashed) vs two point leakages (plains), with variations of α and β coefficients.

This article introduces scatter, a new side-channel technique taking benefit of the integration in time of several data or measurements. On both simulated


Christophe Clavier
email: christophe.clavier@unilim.fr

Julien Francq
email: julien.francq@airbus.com

Antoine Wurcker
email: antoine.wurcker@xlim.fr

Study of a Parity Check Based Fault-Detection Countermeasure for the AES Key Schedule

Keywords: side-channel analysis, fault attacks, parity check countermeasure, AES key schedule

come   L'archive ouverte pluridisciplinaire

Introduction

Beside Side Channel Analysis (SCA) originally revealed by Kocher in 1996 [START_REF] Paul | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF] and later improved in different ways [START_REF] Paul | Differential Power Analysis[END_REF][START_REF] Brier | Correlation Power Analysis with a Leakage Model[END_REF][START_REF] Gierlichs | Mutual Information Analysis[END_REF], Differential Fault Analysis (DFA) introduced in 1997 [START_REF] Biham | Differential Fault Analysis of Secret Key Cryptosystems[END_REF][START_REF] Boneh | On the Importance of Checking Cryptographic Protocols for Faults (Extended Abstract)[END_REF] is another powerful means to jeopardize implementations of embedded cryptography. In DFA an attacker provokes faults during the execution of a cryptographic algorithm in order to extract information about the secret by analyzing the differential effect on the outputs.

The Advanced Encryption Standard (AES) is the current symmetric encryption standard since it has been adopted by the NIST 3 in 2001 [START_REF]Advanced Encryption Standard (AES). Federal Information Processing Standard #197[END_REF]. First DFA applied on AES [START_REF] Dusart | Differential Fault Analysis on AES[END_REF][START_REF] Giraud | DFA on AES[END_REF][START_REF] Piret | A Differential Fault Attack Technique against SPN Structures, with Application to the AES and KHAZAD[END_REF] essentially consisted in modifying the value of a state byte near the end of the encryption path (typically in the 8 th round of AES-128). In another type of DFA on AES the attacker injects a fault during the key schedule while the expanded key is computed on-the-fly.

Fault attacks on the AES key schedule were first introduced by Giraud [START_REF] Giraud | DFA on AES[END_REF] where random byte faults are injected on K 9 , K 8 and M 8 (the state after the 8 th round). If the locations are correctly chosen, 31 faulty ciphertexts are required and 2 16 candidates are remaining at the end of the process (a brute-force is then feasible to deduce the key). Later Chen et al. [START_REF] Chen | Differential Fault Analysis on AES Key Schedule and Some Countermeasures[END_REF] also use random byte fault injections at chosen locations but only on K 9 and K 8 . Here, 22 faulty ciphertexts are needed to retrieve the key, where 2 24 candidates are remaining. In [START_REF] Peacham | DFA against AES Key Expansion[END_REF] Peacham et al. need to inject random word faults on chosen locations on only K 9 . Only 12 faulty ciphertexts are required, and at the end of the fault process, there is only one candidate left (the key is then retrieved without uncertainty). In [START_REF] Takahashi | DFA Mechanism on the AES Key Schedule[END_REF] Takahashi et al. propose a powerful DFA where only two faults on a random word (column) of K 8 are required and where a brute-force can be used to retrieve the correct key among 2 40 candidates. This number can be decreased if the attacker can induce four faults instead of two, and then, the number of candidates can be decreased up to 2 16 . A more powerful DFA on the key schedule has been presented by Kim et al. [START_REF] Hee | New Differential Fault Analysis on AES Key Schedule: Two Faults Are Enough[END_REF]. Like in [START_REF] Takahashi | DFA Mechanism on the AES Key Schedule[END_REF] only two faults are required but on three bytes of K 9 and with a computation complexity of only 2 32 . Moreover, four faults lead to the key without uncertainty. Finally, the ultimate goal of a DFA on AES key schedule requiring only a single faulty ciphertext has been reached by Ali et al. [START_REF] Ali | A Differential Fault Analysis on AES Key Schedule Using Single Fault[END_REF]. They exploit a fault that must be injected in the first column of K 8 and only 2 8 key candidates remain to be exhausted.

Very few attacks in literature are considering higher versions of AES key schedule: AES-192 and AES-256. In [START_REF] Floissac | From AES-128 to AES-192 and AES-256, How to Adapt Differential Fault Analysis Attacks on Key Expansion[END_REF] Floissac et al. manage to adapt [START_REF] Hee | New Differential Fault Analysis on AES Key Schedule: Two Faults Are Enough[END_REF] to these two sizes with 16 faulty ciphertexts. This attack has been improved to around 4 faulty ciphertexts by Kim in [START_REF] Hee | Improved Differential Fault Analysis on AES Key Schedule[END_REF].

In [START_REF] Chen | Differential Fault Analysis on AES Key Schedule and Some Countermeasures[END_REF] Chen et al. propose a DFA on AES key schedule that improves the original attack of Giraud [START_REF] Giraud | DFA on AES[END_REF]. Interestingly, they also provide a parity check based countermeasure supposed to protect implementations from their own attack. The Chen et al.'s paper is cited more than hundred times including at least [START_REF] Takahashi | DFA Mechanism on the AES Key Schedule[END_REF][START_REF] Behnam Ghavami | An EDA Tool for Implementation of Low Power and Secure Crypto-Chips[END_REF] where authors recommends this countermeasure as protection against fault injections. As far as the authors know, this countermeasure has not been investigated for the 192 and 256 bits versions of the AES. Furthermore, no security proof has been provided by the authors. This implies that this flawed countermeasure may have been actually implemented. The motivations of this paper are threefold: extend -and evaluate this extension -Chen et al.'s countermeasure to the AES-192 and 256, assess the real security of the initial method of Chen et al. and correct its flaws by providing right parity formulae.

Chen et al.'s countermeasure and the notations used in this paper are introduced in Sect. 2. We then provide a study of the countermeasure security in Sect. 3. Finally we propose corrections, optimizations and an evaluation of the cost for this countermeasure in Sect. 4 and conclude the paper in the last section.

Notations and Background

Notations

Throughout this paper we use the following notations that apply for all 128-, 192-and 256-bit versions of the AES:

-K r the r th 128-bit round key with r = 0, . . . , 10|12|14 -K r,i the i th byte of K r with i = 0, . . . , 15 w i the i th 4-byte column of the expanded key with i = 0, . . . , 43|51|59 w i,j the j th byte of w i with j = 0, . . . , 3 -RW the operation RotWord -SW the operation SubWord -RC the operation Rcon We also denote by N i and N i the 4-byte non-linear vectors defined as:

AES-128 N i = Rcon(SubWord(RotWord(w 4 * i-1 ))) with i = 1, . . . , 10 AES-192 N i = Rcon(SubWord(RotWord(w 6 * i-1 ))) with i = 1, . . . , 8 AES-256 N i = Rcon(SubWord(RotWord(w 8 * i-1 ))) with i = 1, . . . , 7 N i = SubWord(w 8 * i+3 ) with i = 1, . . . , 6

AES Key Schedule

We now give a brief description of AES key schedule for all key sizes. We refer the reader to the NIST standard [START_REF]Advanced Encryption Standard (AES). Federal Information Processing Standard #197[END_REF] for more detailed information. The 128-bit key schedule uses a 128-bit ciphering key as a 4 × 4 byte matrix and successively derives new 4-byte columns by combining the previous column and the column at the same place in previous matrix as can be seen in Fig. 1. For the first column of each matrix a prior transformation is applied on the previous column which is constituted by RotWord (RW) that vertically rotates the column, SubWord (SW) that replaces every byte by its image through the AES S-Box and Rcon (RC) that XOR-es the column with a round-dependent constant. The other columns combination is simply a XOR operation. Eleven 128-bit round keys K 0 to K 10 are generated. The 192-bit key schedule uses a 192-bit ciphering key as a 4 × 6 byte matrix and generates thirteen 128-bit round keys K 0 to K 12 by a similar process as for the 128bit version as can be seen in Fig. 2. Each column is obtained by XOR-ing the previous column with the column at the same position in previous matrix. Here also, there is a prior transformation that applies when computing the first column of each matrix. All 4 × 6 matrices contain one 128-bit round key and a half. One can remark that the two last columns of the last matrix do not need to be computed. The 256-bit key schedule uses a 256-bit ciphering key as a 4 × 8 byte matrix and also generates fifteen 128-bit round keys K 0 to K 14 by a similar process than for other AES versions as can be seen in Fig. 3. One can note a difference though, which is an extra non-linear transformation that applies when computing each fifth column of a matrix by application of a SubWord step on the previous column before XOR-ing it. All 4 × 8 matrix contain two 128-bit round keys. One can remark that the four last columns of the last matrix do not need to be computed.

W0 W1 W2 W3 K 0 W4 W5 W6 W7 K 1 W8 W9 W10 W11 K 2 RC SW RW ⊕ ⊕ ⊕ ⊕ RC SW RW ⊕ ⊕ ⊕ ⊕ W40 W41 W42 W43 K 10 RC SW RW ⊕ ⊕ ⊕ ⊕
W0 W1 W2 W3 W4 W5 K 0 K 1 W6 W7 W8 W9 W10 W11 K 2 K 1 RC SW RW ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ W48 W49 W50 W51 K 12 RC SW RW ⊕ ⊕ ⊕ ⊕
W0 W1 W2 W3 W4 W5 W6 W7 K 0 K 1 W8 W9 W10 W11 W12 W13 W14 W15 K 2 K 3 RC SW RW ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ SW W56 W57 W58 W59 K 14 RC SW RW ⊕ ⊕ ⊕ ⊕
Fig. 3. The AES-256 key schedule.

Chen and Yen's Countermeasure

As DFA on AES also concerns the key schedule, countermeasures are required for this process. In order to protect from such attacks, countermeasure like duplication (computing the key schedule twice and compare the results) or parity checking can be implemented. Chen et al.'s countermeasure is a parity check based countermeasure which detects byte fault injections, and consists in:

(i) separating the linear part and the non-linear part of the key schedule, (ii) storing -or preferably accumulating -the values of the non-linear 4-byte vectors during round keys derivation, (iii) checking that the last round key verifies particular relations involving the first round key and the non-linear vectors. The separation of the linear and non-linear parts is illustrated on Fig. 4 that describes the countermeasure applied on 128-bit AES key schedule. The non-linear process induced by the SubWord and the Rcon steps generates ten 4-byte vectors N 1 to N 10 that are stored for future usage. During the computation of K i the vector N i is obtained by successively applying RotWord, SubWord and Rcon operations on the last column of previous key:

W0 W1 W2 W3 K 0 W4 W5 W6 W7 K 1 W8 W9 W10 W11 K 2 RC SW RW N1 ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ RC SW RW N2 ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ W36 W37 W38 W39 K 9 W40 W41 W42 W43 K 10 RC SW RW N9 ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ RC SW RW N10 ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕
N i = RC(SW (RW (w 4 * i-1 )))
The linear part consists in cumulatively XOR-ing columns of the previous matrix. Finally the new key columns are obtained by XOR-ing columns of the linear part with the column N i of the non-linear part. Here are the equations for K i columns:

w 4 * i+0 = N i ⊕ w 4 * (i-1)
w 4 * i+1 = N i ⊕ w 4 * (i-1) ⊕w 4 * (i-1)+1 w 4 * i+2 = N i ⊕    w 4 * (i-1) ⊕w 4 * (i-1)+1 ⊕w 4 * (i-1)+2 w 4 * i+3 = N i ⊕        w 4 * (i-1) ⊕w 4 * (i-1)+1 ⊕w 4 * (i-1)+2 ⊕w 4 * (i-1)+3
Chen et al. base their countermeasure on the fact that storing the N i values allows to check parity relations between the first and the last key. They propose the following equations to check columns and rows parity.

for every row i = 0, . . . , 3 the following equation holds:

K 10,i ⊕ K 10,4+i ⊕ K 10,8+i ⊕ K 10,12+i = K 0,8+i ⊕ K 0,12+i ⊕ N 3,i ⊕ N 7,i (1)
for the last column of the last key the following equation holds:

3 i=0 K 10,12+i = 3 i=0 (K 0,4+i ⊕ K 0,12+i ⊕ N 2,i ⊕ N 6,i ⊕ N 10,i ) (2)
A method is given in order to get other columns equations and authors claim that row checks are able to detect any fault induced into K 8 to K 10 .

3 Study of the Countermeasure

Deriving Equations

Chen et al. obtain their equations by computing from the first to the last key. They do not give equations for AES-192 nor AES-256. We detail hereafter a generalization allowing to derive equations from the last key to the first one so that it can be adapted for all AES key sizes. All the processes are illustrated on Fig. 5, 7 and 9. Equations for AES-128 First of all we have to point out some relations inherited from AES-128 key schedule construction for all rounds r = 1, . . . , 10:

w 4 * r = w 4 * (r-1) ⊕ N r (3)
w 4 * r+1 = w 4 * (r-1)+1 ⊕ w 4 * r (4)
w 4 * r+2 = w 4 * (r-1)+2 ⊕ w 4 * r+1 (5)
w 4 * r+3 = w 4 * (r-1)+3 ⊕ w 4 * r+2 (6)
Equation ( 3) shows the relation that exists between the first column of a key, the first column of the previous key and a non-linear vector. Equations ( 4) to [START_REF] Chen | Differential Fault Analysis on AES Key Schedule and Some Countermeasures[END_REF] show the relation that exists between others columns of a key, the corresponding column of the previous key and the previous column.

For the first column of the last key w 40 we combine together all round equations of type [START_REF] Boneh | On the Importance of Checking Cryptographic Protocols for Faults (Extended Abstract)[END_REF]. After simplification it remains:

w 40 = w 0 ⊕ 10 i=1 N i (7)
For the second column of the last key w 41 we combine together all round equations of type (4). After simplification it still remains ten first columns residues that we combine pairwise -by using equations of type (3) -to obtain five non-linear vectors:

w 41 = w 1 ⊕ 5 i=1 N i * 2 (8)
A similar process is applied for the two last columns w 42 and w 43 of the last key. After simplification and combination using Equations ( 3) to (6) as depicted on Fig. 5 we obtain relations between only the first key, the last key and non-linear vectors:

w 42 = w 2 ⊕ w 0 ⊕ 2 i=0 (N 1+4 * i ⊕ N 2+4 * i ) (9)
w 43 = w 3 ⊕ w 1 ⊕ N 2 ⊕ N 6 ⊕ N 10 (10)
Note that Chen et al. have already found Equations ( 7) to [START_REF] Behnam Ghavami | An EDA Tool for Implementation of Low Power and Secure Crypto-Chips[END_REF]. The method described here aims at simplifying the derivation of these equations and presents the advantage to be straightforwardly applicable for other key sizes.

Equations for AES-192

The AES-192 key schedule is very similar to the AES-128 one.

The main difference is that it involves 6-column matrices to generate 13 round keys in only 8 steps producing non-linear vectors N 1 to N 8 . The countermeasure is illustrated on Fig. 6. The method to derive equations for AES-128 can still be applied to relate last key columns to first key ones. Equations ( 3) to ( 6) become: Step by step description and resulting equations are given in Fig. 7.

W0 W1 W2 W3 W4 W5 K 0 K 1 W6 W7 W8 W9 W10 W11 K 2 K 1 RC SW RW N1 ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ W42 W43 W44 W45 W46 W47 K 11 RC SW RW N7 ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ W48 W49 W50 W51 K 12 RC SW RW N8 ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕
w 6 * i = w 6 * (i-1) ⊕ N i (11)
w 6 * i+1 = w 6 * (i-1)+1 ⊕ w 6 * i ( 12
)
w 6 * i+2 = w 6 * (i-1)+2 ⊕ w 6 * i+1 (13)
w 6 * i+3 = w 6 * (i-1)+3 ⊕ w 6 * i+2 (14)

Equations for AES-256

The AES-256 key schedule is different from the two other versions. There are 7 steps in key schedule that generate 15 round keys using two different non-linear transformations at each step. The computation of each 8-column matrix involves two types of non-linear vectors: N 1 to N 7 for the first half of each matrix, and N 1 to N 6 for the second half (except for the last key). The countermeasure is illustrated on Fig. 8. Here also we can apply the same method as for other key sizes to derive equations that relate last key columns to first key ones: One can remark that these equations are independent from {N i } i=1..6 non-linear vectors because the last round key is made of only the first 4 columns of the last matrix.

W0 W1 W2 W3 W4 W5 W6 W7 K 0 K 1 W8 W9 W10 W11 W12 W13 W14 W15 K 2 K 3 RC SW RW N1 SW N 1 ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ W56 W57 W58 W59
w 8 * i = w 8 * (i-1) ⊕ N i ( 15
)
w 8 * i+1 = w 8 * (i-1)+1 ⊕ w 8 * i (16)
w 8 * i+2 = w 8 * (i-1)+2 ⊕ w 8 * i+1 (17)
w 8 * i+3 = w 8 * (i-1)+3 ⊕ w 8 * i+2 (18)
Step by step description and resulting equations are given in Fig. 9.

Countermeasure Behavior Facing Faults

We point out that every term of previously obtained equations are 4-byte columns. We can thus decompose them into four equations that put in relation bytes from the last key, bytes from the first key and bytes from non-linear vectors. For every key size, we thus have 16 so-called atomic equations, one per last key byte.

Chen et al. propose to check parity of rows by using equations obtained by XOR-ing the four atomic equations from a same row (cf. Equation ( 1)). They claim that "The row parity check can detect the fault induced on the eighth to tenth round keys.". We will show that it is partially false. Indeed this rows parity check protects from the attack described in their paper where byte faults must occur in the last column of K 9 and the two last columns of K 8 . But it does not detect every fault injection. They also evoke that a column parity check can be done by using some equations obtained by XOR-ing four atomic equations from a same column (cf. Equation ( 2)).

In order to evaluate Chen et al. countermeasure we performed simulations that provoke byte fault injections at every location of the expanded key and test if the differentials that propagate to the last key are detected or not by the different equations. For the sake of completeness, we also simulated fault injections into the countermeasure registers, namely the linear and the non-linear parts.

Remark that a fault induced into the ciphering key K 0 is never detected. This is because it is equivalent to encrypt with another key and thus with a fully valid expanded key. In the following sections we only consider byte faults occurring on round keys from K 1 onward.

Analysis of AES-128 Countermeasure

Fault Propagation Due to a lack of diffusion the fault propagation in AES key schedule is tightly related to the location of the fault, as described by Clavier et al. in [START_REF] Clavier | Simple Power Analysis on AES Key Expansion Revisited[END_REF]. Thus when the location of the fault is known the positions of bytes hit by fault propagation are also known. Furthermore we can predict separately the fault propagation pattern on the linear part and that on the non-linear part, whose superposition gives the propagation pattern on the expanded key.

The countermeasure principle lies in accumulating non-linear vectors during process, in order to verify that combined with last key K 10 they fit with first key K 0 and then try to detect a differential inserted by fault.

Note that this method can only detect a small part of a differential propagation. Indeed, the progressive accumulation of non-linear vectors during the key calculation process makes that some differentials propagate simultaneously on both expanded key and non-linear vectors. As a result, only the propagation of the original differential on the linear part can be detected by checking parity equations. This is illustrated on the example given on Fig. 10. An original differential δ 1 is induced by a fault occurring on K 4,4 4 . This differential propagates on the linear part according to a pattern specific to the fault location. Only this propagation will be noticeable by the countermeasure whose parity check equations do not involve the linear steps. This is due to the fact that other propagated differentials through non-linear steps simplify as they appear twice in the equations, both in the last key and in non-linear vectors. A differential δ 2 is created when δ 1 passes from the last column of K 5 through the nonlinear process to create N 6 so we can not relate it to δ 1 without knowing key bytes values. New differentials are created each time a differential passes into a non-linear step, while the linear steps propagate differentials that remain unchanged. At the end the last key contains many differentials, but columns C 0 to C 3 (see Figure 10), that are the non-linear vectors combinations used in countermeasure equations, also contain almost the same differential pattern. When combining the last key and the non-linear accumulators C i the only differentials that remain are the two occurrences of δ 1 propagated through the linear part.

We can make some remarks about the propagation of the original differential through linear steps. As one can see, the following properties are verified by δ 1 on Fig. 10: 1. As the linear process only consists in XOR-ing columns together, the original differential always stays on the same row -e.g. δ 1 never leaves the first row. 2. For each matrix computation, the linear step always consists in accumulating columns from the first one to the last one of the matrix. As a consequence, the original differential never appears earlier in a matrix than in the previous ones -e.g. δ 1 injected into a second column of a matrix will never appear in any first column. 3. For a similar reason than for the previous property, the original differential that has been injected in some column of a matrix will always appear in the same column of subsequent matrices, and the appearance pattern is cyclic for the next columns. As an example, δ 1 injected into a second column will always be present in the second column of each subsequent matrix and have a cyclic appearance of period 4 keys, restarting in K 8 the same sequence.

Rows Parity Check Our simulations show that 64 out of the 160 key bytes positions5 of K 1 to K 10 produce differential propagations that are not detected by the rows parity check method proposed by Chen et al. We previously remarked that only the original differential can possibly propagate up to the parity check equation without cancellation. We also noticed that this propagation always stays on the same row. As a consequence, the countermeasure which consists in checking whether the XOR of all four bytes of a same row is null or not does not detect faults on positions that produce an even number of occurrences of the original differential in a same row of the last key. This is illustrated on Fig. 10 where δ 1 occurs twice on the same row in the detectable square on the right. Only the positions that produce an odd number of occurrences are safe.

Columns Parity Check Contrarily to the rows parity check, our simulations show that the columns parity check detects any single byte fault that occurs on a byte of any K 1 to K 10 . This observation matches with the theory since any single byte fault creates detectable differentials that are on the same row, and there is at least one occurrence of the original differential on every matrix following the one at which the fault occurred (c.f. the third remark above). As only the injection row may contain active differentials that are detectable, checking the parity by XOR-ing all bytes of a column always detects the fault at least in the column of injection.

The last part of this analysis, that was not evaluated by Chen et al., is about injections of faults into countermeasure registers We observed that faults injected into the linear part are always detected while some are not for the non-linear part. Both phenomenons can be explained by the construction of this countermeasure that checks a differential between the key obtained and the non-linear part. On the first hand, a differential into the linear part propagates into the keys and not directly into the non-linear part, so that it is always detected. On the other hand a fault injected into non-linear part may propagate, under certain circumstances, by the same way into keys and non-linear part leading to a nondetection at the end of the process. More precisely, this non-detection effect is produced when the fault is injected in a non linear vector before it is used into the key calculation. By this way, both non-linear vector and round key are infected leading to the same infection on both sides of parity equations (see Figure 11). If the non-linear vector has been used without error at least one time, the fault is detected because only a part of the round key is infected, leading to a different infection on the respective parts of parity equations (see Figure 12). As this undesirable effect is dependant to the fact that the error must infect all columns of the round key under injection, it can be simply avoided by re-computing each N i vector during K i calculation after that at least one column was already calculated. For example the Table 1 details the difference between the computation of K 1 with (right) and without (left) recalculation of N 1 vector after two column calculations. We could have chosen to recalculate N 1 before w 5 or w 7 instead of w 6 .

L = w0 L = w0 w4 = N1 ⊕ L w4 = N1 ⊕ L L = L ⊕ w1 L = L ⊕ w1 w5 = N1 ⊕ L w5 = N1 ⊕ L L = L ⊕ w2 L = L ⊕ w2 N1= T (w3) w6 = N1 ⊕ L w6 = N1 ⊕ L L = L ⊕ w3 L = L ⊕ w3 w7 = N1 ⊕ L w7 = N1 ⊕ L T (X) = RC(SW (RW (X)))

Analysis of AES-192 and AES-256 Countermeasure

The study realized on AES-128 in Sect. 3.3 is still valid concerning the role of non-linear and linear parts for AES-192 and AES-256.

Interestingly our simulations for these key sizes show that there are faults that are not detected by the columns parity check. Precisely, for AES-192 (resp. AES-256) any fault occurring on one of the 2 (resp. 4) last columns of a matrix is not detected. This is explained by the second remark above which states that differentials on the linear part never propagate in previous matrix columns. They can only propagate to the right, never to the left. Since the proposed countermeasure checks parity only on the first 4 columns of the last matrix which do contain the last round key (c.f. Fig. 6 and8), faults occurring on one of the 2 (resp. 4) last columns of a matrix are not detected.

4 Corrections, Optimizations, Cost Evaluation and General Discussions The problem of columns parity check non-detection detailed in Sect. 3.4 can be corrected by checking the whole last matrix values instead of only the last key. As the last columns of last matrix are not calculated we propose instead to perform extra parity checks on the 2 (resp. 4) last columns of the penultimate matrix.

Here are given the 2 extra equations for AES-192. They have been obtained by using the same method than in Sect. 3.1:

w 46 = w 3 ⊕ w 4 ⊕ 7 i=4 N i w 47 = w 4 ⊕ w 5 ⊕ N 5 ⊕ N 7
Here are the 4 extra equations for AES-256. Note that in those equations N i are involved instead of N i :

w 52 = w 4 ⊕ 6 i=1 N i w 54 = w 4 ⊕ w 6 ⊕ N 1 ⊕ N 2 ⊕ N 5 ⊕ N 6 w 53 = w 5 ⊕ 3 i=1 N 2 * i w 55 = w 5 ⊕ w 7 ⊕ N 2 ⊕ N 6
Those equations were integrated into our simulator which validated the detection for any byte fault injected into K 1 to K 12 (resp. K 14 ).

Optimization for the Byte Fault Model

We showed that the columns parity check detects every single byte fault6 propagation, even on AES-192 and AES-256 if the proposed correction (extra parity equations) is applied. As an optimization we recommend to use only columns parity check and not rows parity check in order to do only 4 (resp. 6 or 8) tests instead of 8 (resp. 10 or 12) ones. In that configuration defender can also reduce the countermeasure cost by accumulating in memory the 8-bit XOR of the 4 bytes of the non-linear vectors instead of the 32-bit vector itself, dividing by 4 the memory requirement.

Adaptation to the Multi-Byte Fault Model

While the columns parity check is able to detect every single byte fault injection, it may not detect a multi-byte fault. It is notably the case if the XOR of differentials in the injection column is equal to 0. Although such fault effect can be difficult to produce, it is still possible to protect from it by using atomic parity check equations instead of columns parity check. We remind that the atomic equations are obtained by the decomposition of 4-byte columns equations into four 1-byte equations. i.e. four atomic equations are combined to create one column parity check equation. Checking atomic equations requires 16 (resp. 24 or 32) checks but avoids non-detection in cases of differential compensations.

Cost Evaluation

We have implemented three AES-128 countermeasures in 8-bit software in order to compare their respective extra costs with respect to a non protected implementation. The results are summarized in Table 2 which also provides the extra costs between the countermeasures.

First we implement the classic doubling countermeasure that executes the whole7 key schedule twice and checks the equality of the two obtained keys. We then implement two corrected versions of Chen et al.'s countermeasure, the one with atomic equations checking and the one -that we call compressed -that refers to the reduced memory version detailed in Section 4.2. We compiled with the tool avr-gcc for an 8-bit AVR microcontroller (ATmega328) without optimization option. The size evaluation is realized using avr-size and the time evaluation is done using oscilloscope measurement of executions.

The results show that those three versions are more or less close in term of extra costs. Depending on the device used and the implementation choices Chen et al.'s countermeasure -strengthened by our corrections -may be a good candidate as countermeasure.

Remark on Chen and Yen Proposition

Chen et al. are wrong saying that the rows parity check covers every positions of K 8 , K 9 and K 10 , but they are right when they claim that it can protect from their attack. Indeed, their attack requires to inject faults only in the last column of K 9 and the two last ones of K 8 , which are positions covered by the rows parity check. If the defender is satisfied by the rows parity check coverage -which we consider risky -, then Chen et al.'s proposition reduces the computational cost of the countermeasure because Equation (1) involves only 2 non-linear vectors (for AES-128) to accumulate in memory instead of 24 ones for Equation ( 7) to [START_REF] Behnam Ghavami | An EDA Tool for Implementation of Low Power and Secure Crypto-Chips[END_REF] of the columns parity check.

Sensitivity to Double Faults

While we do not provide any proof, we have the intuition that the parity checking countermeasure may provide more resistance then the doubling countermeasure against double fault injections attacks. The idea behind this intuition is that the doubling countermeasure seems particularly vulnerable when the attacker can produce the same fault effect twice8 .

On the contrary, it does not appear obvious why the parity check based countermeasure would be more vulnerable to such same-repeated-faults than to any other type of double fault. We let the study of the comparative vulnerability of both countermeasures as an open problem.

Conclusion

In this paper we deeply study the AES key schedule fault detection countermeasure proposed by Chen et al. that has been cited as countermeasure but never evaluated, implying a risk that may have been implemented with flaws. We provide a generalization of their approach and give a constructive method to obtain parity equations for all columns and for every key sizes, where the original paper only recommends rows parity check (which is flawed) and only for AES-128. We analyze the underlying reasons why and when the countermeasure works or do not work. In particular, we have evaluated the original proposal and showed that it is not as good as expected by the authors as it is far from covering every byte fault positions. We point out detection holes of the straightforward application of the countermeasure to AES-192 and AES-256, and provide extra parity equations to fix this problem. We also suggest optimizations that reduce the memory and computational costs of the countermeasure, and propose an adaptation to a more general fault model.

Fig. 1 .

 1 Fig. 1. The AES-128 key schedule.

Fig. 2 .

 2 Fig. 2. The AES-192 key schedule.

Fig. 4 .

 4 Fig. 4. Illustration of countermeasure on AES-128 key schedule.

w40 = w36⊕N 10 w36 = w32⊕N 9 w32 = w28⊕N 8 w28 = w24⊕N 7 w24 = w20⊕N 6 w20 = w16⊕N 5 w16 = w12⊕N 4 w12w22 = w18⊕w 21 w18 = w14⊕w 17 w14 = w10⊕w 13 w10 2 i=0(w19 = w15⊕w 18 w15 = w11⊕w 14 w11=

 1098765421171321814 w8 = w0 ⊕ N1 ⊕ N2 w42 = w2 ⊕ w0 ⊕ N1+4 * i ⊕ N2+4 * i) w43 = w39⊕w 42 w39 = w35⊕w 38 w35 = w31⊕w 34 w31 = w27⊕w 30 w27 = w23⊕w 26 w23 = w19⊕w 22 w1 ⊕ N2 w43 = w3 ⊕ w1 ⊕ N2 ⊕ N6 ⊕ N10

Fig. 5 .

 5 Fig. 5. Method to obtain equations between last key and first key for AES-128.

Fig. 6 .

 6 Fig. 6. Illustration of countermeasure on AES-192 key schedule.

w48 = w42⊕N 8 w42 = w36⊕N 7 w36 = w30⊕N 6 w30 = w24⊕N 5 w24 = w18⊕N 4 w18 = w12⊕N 3 w12 8 i=1w21 = w15⊕w 20 w15

 876543820 = w6 ⊕N2 w6 = w0 ⊕N1 w48 = w0 ⊕ Ni w49 = w43⊕w 48 w43 = w37⊕w 42 w37 = w31⊕w 36 w31 = w25⊕w 30 w25 = w19⊕w 24 w19 = w13⊕w 18 w13 = w7 ⊕w12 w7 = w1 ⊕w6 w50 = w2 ⊕ N3 ⊕ N4 ⊕ N7 ⊕ N8 w51 = w45⊕w 50 w45 = w39⊕w 44 w39 = w33⊕w 38 w33 = w27⊕w 32 w27 = w21⊕w 26

Fig. 7 .

 7 Fig. 7. Method to obtain equations between last key and first key for AES-192.

Fig. 8 .

 8 Fig. 8. Illustration of countermeasure on AES-256 key schedule.

w56 = w48⊕N 7 w48 = w40⊕N 6 w40 = w32⊕N 5 w32 = w24⊕N 4 w24 = w16⊕N 3 w16Fig. 9 .

 765439 Fig. 9. Method to obtain equations between last key and first key for AES-256.

2 i=0(Fig. 10 .

 210 Fig.10. Differential propagation from injection in K4,4 illustrating that Equations (7) to[START_REF] Behnam Ghavami | An EDA Tool for Implementation of Low Power and Secure Crypto-Chips[END_REF] can detect only original differential δ1 propagated by the linear part.

Fig. 11 .

 11 Fig.11. Injection of differential δ1 into non-linear vector N9 before it was used into K9 calculation leading to an undetectability of the fault by the parity checks.

Fig. 12 .

 12 Fig. 12. Injection of differential δ1 into non-linear vector N9 after two proper K9 columns calculation leading to a detectability of the fault by the parity checks.

4. 1

 1 Correction for AES-192 and AES-256

Table 1 .

 1 Successive operations of calculation of K1 vectors with (right) and without (left) recalculation of N1

	Ni re-computation
	No	Yes
	N1= T (w3) N1= T (w3)

Table 2 .

 2 Results of software extra costs of three secured implementations with respect to two reference implementations

		Countermeasures (CM)
			Chen et al.
		Doubling	Compressed
	Reference	Yes	No
	Without size +86% +71% +96%
	CM	time +111% +155% +179%
	Doubling	size time +0% +0%	-8% +21% +32% +5%

We voluntarily choose a fault injection in middle rounds of the key schedule, even if it may not be exploitable by an attacker, in order to explicit more clearly the propagation and compensation phenomenons.

More details about the patterns of non-detection are provided in Appendix. A.

Except possibly faults on K0. Notice however that in the case were the fault occurs while reading K from NVM to RAM the parity equations still detect the fault if the checksum computation involves bytes from original K (in NVM) instead of bytes of read K0 (in RAM).

We choose to implement a doubling of the whole key schedule in order to be able to detect the same area of injection than the corrected countermeasure of Chen et al.

This is true for the encryption-encryption version, but may not but true for the encryption-decryption version.

Acknowledgments

Simulations presented in this paper have been partly performed on the CALI computing cluster of university of Limoges, funded by the Limousin region, XLIM, IPAM and GEIST institutes, as well as the university of Limoges. This work is part of ICT COST ACTION IC1204 TRUDEVICE (Trustworthy Manufacturing and Utilization of Secure Devices).

A Remarkable Patterns in Propagation

We describe how patterns can be inferred from the propagation of an original differential through AES-128 key schedule. Fig. 13 shows an example of propagation of four differentials, one per column (the differential propagation pattern does not depend on the row).

Remark that the fault propagation patterns have a period that depends on the injection column. First and second columns show a period of 4 round keys while the third column shows a period of 2 keys, and the fourth column a period of 1 key.

We have surrounded in red the row segments that contain an even number of differentials. They are not detected by the rows parity check if the last key lies at these positions. In order to derive the 16 columns (i.e. 64 bytes) that are concerned by non-detection of faults, we write, for each injection column, equations that relate the round r of the fault injection, the offset of the non-detection segment, and the period: