Emmanuel Prouff

François-Xavier Standaert

Christophe Clavier

Bruno Rouzeyre

Thomas Roche

Unsupervised Side-Channel Analysis Based on Mutual Information and its Neural Estimation

Keywords: ADC, 15 bits Chapter 4. The EVIL Machine, Encode, Visualize and Interpret

Yes, I am a criminal. My crime is that of curiosity. My crime is that of outsmarting you, something that you will never forgive me for. I am a hacker, and this is my manifesto.

Introduction to Cryptography

Everyone remembers that day in primary school when this message written on a small piece of paper, sent by a little boy discovering the wriggling of love, was intercepted by the teacher while passing from hand to hand with the ultimate goal of getting to Ema. A simple shift of each letter three letters further down the alphabet would have saved him from the intense feeling of shame of having the whole class know that he had just declared his love to Ema. Unfortunately, he only discovered cryptography a few years later... The term cryptography, from the greek kryptós (secret) and graphein (writing), refers to the art of encrypting messages. It encompasses all the techniques useful for a secure communication in the presence of an adversary. The basic idea is to transform a private message, the plaintext, into an unintelligible message, the ciphertext, which should appear like nonsense to anyone who intercepts it. The only way to understand this message would be to reverse to process of encryption, which often involves owning a secret. As stated by A. Kerckhoff in his famous principle, the general specifications of the encryption scheme should not be part of this secret. The encryption procedure should rely on a secret key, often shared by the two parties trying to communicate, but everything else about the system should be public knowledge. For example, in Caesar's code described above, the fact that letters may be shifted by a certain amount would be public knowledge and the specific shift of three would be the shared secret. Obviously, under these conditions, the latter scheme does not feel very secure. One could easily try the 26 possible shifts and recover the private message, thereby conducting the most basic cryptanalysis technique...

Cryptanalysis is the branch of cryptology (the science of the secret) studying the resistance of cryptographic schemes. The main goal is to develop attacks in order to assess to what extent a malicious adversary could break a crypto-system's security claims. Cryptography and cryptanalysis are complementary domains that evolve in symbiosis with the aim of converging toward secure algorithms.

The art of cryptography is very ancient but has experienced tremendous growth in the last century, with the advent of computers and the general rise of information technology. It has become increasingly complex and is now considered a proper science, often called Modern Cryptography, taking place at the intersection of many disciplines such as applied mathematics, computer science, electrical engineering, and information security. Modern cryptographic protocols are designed to ensure at least one of the four following information security properties:

1. Confidentiality: The private message should only be retrievable by a set of authorized parties.

2. Integrity: the receiver should be convinced that the message has not been modified during transmission.

3. Authenticity: the receiver should be able to identify the sender of the message.

Non-repudiation:

The sender should not be able to deny sending the message afterward.

Low-level cryptographic routines, often called cryptographic primitives, are the basic blocks used to build cryptographic protocols. A primitive is considered mathematically secured if an adversary, granted with the ability to query as many couples (plaintext, ciphertext) as he wants, can not recover the secret key in a reasonable amount of time.

Two branches of cryptography may be distinguished: the symmetric and asymmetric cryptography. The first one, known as secret key cryptography, is the most ancient one and is predicated on the idea that the two entities involved have shared a common secret prior to the communication. The second, also known as public key 1.2. Side-Channel Analysis 3 cryptography, was first introduced in the 1970s and differs from symmetric cryptography in the fact that the key used for the encryption is not the same as the one used for the decryption. Such schemes are computationally heavier and are often only used to securely share a symmetric key between two parties. Even though some ideas may be extended to asymmetric cryptography, a significant part of this thesis focuses on analyzing the security of symmetric crypto-systems. Most of the examples and experiments are conducted on the Advanced Encryption Standard (AES) which is the most used symmetric cryptographic primitive nowadays.

Side-Channel Analysis

Modern cryptography proposes solutions to secure communications. Until the middle of the nineties, cryptographic algorithms were considered as a black-box in the sense that an adversary can only observe the inputs and outputs of a computation. Therefore, the actual security of the system was equivalent to the mathematical security of its primitives. However, in his seminal paper about Side-Channel Analysis (SCA) [START_REF] Paul | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF], Paul Kocher showed that this black-box model may not always be the appropriate adversary's model. Indeed, cryptographic algorithms are implemented on electronic devices which inevitably manipulate the secret keys. Such manipulations involve physical processes, mostly related to the flow of electrons in semiconductors, and may thus, induces observable variations in the surrounding of the device.

These variations may take different forms: the so called side-channels. Any measurable physical quantity carrying information about the secret can be considered a side channel. The most famous examples are the instantaneous power consumption of a device [START_REF] Kocher | Differential power analysis[END_REF] and its ElectroMagnetic (EM) emanations [START_REF] Quisquater | Electromagnetic analysis: Measures and counter-measures for smart cards[END_REF]. Figure 1.2 shows an example of the EM emanation captured by an EM probe positioned close to a device executing an AES. Such acquired data are often called side-channel traces.

Many other side-channels have been pointed out in the literature such as timing attacks [START_REF] Billy | Remote Timing Attacks Are Still Practical[END_REF], cache monitoring [START_REF] Percival | Cache Missing for Fun and Profit[END_REF] or even network packets length analysis [START_REF] Schaub | Attacking Suggest Boxes in Web Applications Over HTTPS Using Side-Channel Stochastic Algorithms[END_REF].

Secret keys take the form of bit string long enough so that the number of possible combinations would far exceed the brute force capability of any adversary. For example, the AES in its lowest security setting involves 128 bits secret keys leading to 2 128 key possibilities. Enumerating all these possible values would be longer than the age of the universe. The main idea of a side-channel attack is to gather enough information, via the leakage channel, so that the amount of remaining possibilities becomes enumerable in a reasonable time. It often involves a divide and conquer strategy. Indeed, algorithms use key chunks to perform independent computations which may induce leakage on intermediate variables only depending on a sub-part of the key. For example, in the AES the internal variables are naturally processed at the byte level and a typical SCA strategy would be to focus only on one specific key byte and repeat the process 16 times to recover the whole key.

Notations Probabilistic notations

Random variables are represented as upper-case letters such as X. They take their values in the corresponding set X depicted with a calligraphic letter. The carnality of X is denoted |X |. Lower-case letters such as x stand for elements of X . The probability density function associated to the variable X is denoted P X (replaced by P when there is no ambiguity). The notations P X (X = x) and P X (x) are equivalent. If f is a function defined over X , E X [ f (X)] denotes the expected value of the random variable f (X), under the distribution P X so that:

E X [ f (X)] = ∑ x∈X P X (x) • f (x) (1.1)
Such notation is replaced by E[ f (X)] when there is no ambiguity. Similarly, the variance of f (X) is denoted by Var X [ f (X)] (or Var[ f (X)]) , :

Var

X [ f (X)] = ∑ x∈X P X (x) • ( f (x) -E X [ f (X)]) 2 (1.2)
When two random variables X and Y are considered, their joint probability density function is denoted by P X,Y . The conditional probability of X given Y is denoted P(X | Y). The covariance of the two variables is denoted by cov(X, Y):

cov(X, Y) = ∑ x∈X ∑ y∈Y P X,Y (x, y) • (x -E X [X]) • (y -E Y [Y]) (1.3)
1.2. Side-Channel Analysis 5 Eventually, when a set of realization (x i ) 1≤i≤N of X is available, the hat notation represents a statistical estimation of the underlying quantity. For example:

E X [ f (X)] = 1 N N ∑ i=1 f (x i ) (1.4)

SCA framework

In this thesis, the evaluation/attack framework is described considering that an adversary targets the manipulation of a sensitive variable Z ∈ Z = F n 2 , for a given n ∈ N. This variable is supposed to functionally depends on a public variable X ∈ X = F m 2 , for a given m ∈ N, and a secret key chunk k * ∈ K = F m 2 through the relation: Z = g(X, k * ) where g : X × K → Z is a known function depending on the underlying cryptographic algorithm. For simplicity, g(X, k) is denoted g k (X) in the rest of the thesis.

The evaluator/adversary is supposed to be able to acquire a set {(ℓ i , x i ), 1 ≤ i ≤ N} of N side-channel traces labeled with the corresponding public value of X. Depending on the situation, the latter may have control over the X variable (be able to choose it) or not. Traces correspond to realizations of a leakage variable L ∈ L coming from a stochastic process S, Z S -→ L. When the sensitive variable is directly processed in the internal of the device (i.e. no masking countermeasure, see section 1.2.4) the leakage L is supposed to be separable into a deterministic and a noise part:

L = φ(Z) + N (1.5)
where φ is a function from Z to R p , for some p ∈ N, denoted the leakage model in this thesis and where N represents an independent noise distribution (which is often supposed to be normal). Note that in this thesis, the expression Leakage model stands for the deterministic part of the true leakage which may differ from other SCA materials. In addition, we consider the leakage model to be potentially multidimensional: it encompasses the whole side-channel trace which can be composed of thousands of time samples (for example, Figure 1.2 contains p = 50k samples).

Leakage Assessment

A first step that a designer/adversary may conduct to identify a side channel, is to perform a leakage detection. Many techniques have been developed for this purpose and are known as leakage assessment techniques. The main goal is to identify if L contains information about Z. A minimum requirement for a leakage to occurs is that there exist z 1 and z 2 such that φ(z 1 ) ̸ = φ(z 2 ). The more values of Z with a different model, the better the leakage. However, these differences should also be compared to the amount of noise present in the traces. Indeed a low difference between φ(z 1 ) and φ(z 2 ) drowned in the noise would not be very informative.

Chapter 1. Context and motivations

The main problem to characterize differences between values of φ(Z) is that φ is often a highly multidimensional function since it represents the whole trace. In addition, the leakage may only occur in small specific areas of the traces. In other words, even in the case of a leakage, φ(z 1 ) and φ(z 2 ) represent long vectors that are very likely equal on most of their components. That is why a classical solution to leakage assessment is to compute sample-wise statistics S L (s), for 1 ≤ s ≤ p, on the variables L[s] representing the projection of the leakage on one of its components. The aim of such statistics is to quantify a sort of instantaneous signal strength, transforming a non-trivial multi-dimensional problem into a simple monodimensional one. There exists multiple of these statistics such as the Sum of Differences (SoD) [START_REF] Rechberger | Practical Template Attacks[END_REF], the Sum of Squared T-difference (SoST) [START_REF] Gierlichs | Templates vs. Stochastic Methods[END_REF], the Normalized Inter-Class Variance (NICV) [START_REF] Bhasin | NICV: Normalized inter-class variance for detection of side-channel leakage[END_REF]. We give here as an example, one of the most famous of them which is the classical Signal-to-Noise Ratio (SNR). It is defined as:

SNR L (s) = Var Z E[L[s] | Z] E Z Var[L[s] | Z] (1.6)
The intuition behind this formula is that it compares the variance of the signal interclass (representing the useful part of the signal) to the intra-class variance (representing the noise). A peak of SNR corresponds to a leakage area in the traces.

Since the essence of such statistic is to assess if there exists some kind of information between L and Z, it is also possible to use the Mutual Information (MI) which is exactly designed for such purpose as explained in section 1.4:

MI L (s) = I(Z, L[s]) (1.7)
The way to conduct the MI estimation is not discussed here as it is the object of Chapter 2. However, as shown in [START_REF] Prouff | Theoretical and Practical Aspects of Mutual Information Based Side Channel Analysis[END_REF] it can be easily estimated when dealing with univariate variables.

Remark 1. One may argue that such computation cannot be done by an adversary in a blackbox setting because it requires the knowledge of Z and therefore of the correct key chunk k * .

However, in many cases, the g function linking Z and X for a fixed k * is a bijective function.

For example, in the AES case a classical choice of sensitive variable is Z = Sbox[X ⊕ k * ]. This implies that partitioning traces according to Z is the same as partitioning them according to X. In such a cases, Equation 1.6 and Equation 1.7 can be replaced respectively by:

SNR L (s) = Var X E[L[s] | X] E X Var[L[s] | X] (1.8) MI L (s) = I(X, L[s]) (1.9)
1.2. Side-Channel Analysis 7

The two main drawbacks of such univariate statistics are the following:

1. They can not detect higher-order leakages, in other words, they would fail to detect a leakage that comes from the dependency of multiple samples. Such leakage models are widely met when dealing with masked implementations (see section 1.2.4).

2. They can not accumulate several small leakages coming from multiple different sources. They would fail to detect a leakage if all the instantaneous leakages stay under the detection threshold while the aggregation of all these small leakages would still make the trace informative.

Higher-Order Detection

The previously discussed univariate statistics could be extended in order to detect higher-order leakages. If one wants to detect up to a d-order leakage the main idea is to combine all the possible d-tuple of time samples from the trace through a Combining function C : R d → R and to apply the univariate statistic on the output of C.

Formally, for all (s 1 , . . . , s d ) ∈ 1, p d one can compute:

S (C) L (s 1 , . . . , s d ) = S L (C(L[s 1 ], . . . , L[s d ])) (1.10)
The choice of the combining function is not trivial. Some proposals have been made in [START_REF] Prouff | Statistical Analysis of Second Order Differential Power Analysis[END_REF][START_REF] Oswald | Template Attacks on Masking-Resistance Is Futile[END_REF]. A common choice is the centered product combining function1 .

Even without considering the choice of the combining function, this method suffers from a major drawback. Indeed, the number of possible d-tuple increases exponentially with d and becomes quickly critical even for low values of d.

In addition, even though such a strategy solves to some extent the first drawback of the univariate method, it does not bring anything regarding the second drawback related to the problem of aggregating enough small leakages to pass above a detection threshold.

Side-Channel Attacks

Any side-channel attack aiming at recovering a key chunk k * ∈ K can be summarized in the following two-step procedure:

1. Acquire a set of traces L = {(ℓ i , x i ), 1 ≤ i ≤ N} labeled with their corresponding public variable.

8

Chapter 1. Context and motivations 2. Apply a distinguisher function mapping any set of traces L to a scoring vector in R |K| :

D : L →     . . . D L [k] . . .    
(1.11) Such procedure will then be repeated for all key chunks (obviously, the same set of traces can be re-used if they contain leakage related to multiple key chunks).

Then, the adversary will feed all the scoring vectors into a key enumeration algorithm [START_REF] Veyrat-Charvillon | An Optimal Key Enumeration Algorithm and Its Application to Side-Channel Attacks[END_REF][START_REF] Poussier | Simple Key Enumeration (and Rank Estimation) Using Histograms: An Integrated Approach[END_REF] which should test the keys one by one from the most probable to the least probable according to the scoring vector of each key chunk (most of the times, the scores are normalized to be treated as probabilities). The test usually considers a given couple (plaintext, ciphertext) and consists in encrypting the plaintext and comparing it to the ciphertext. The exact design of such enumeration algorithms is out of the scope of this thesis but as a rule of thumb the better the score of each correct key chunk, the faster the algorithm will find the full key. Even if a correct key chunk is ranked first through the distinguisher one should also consider its distinguishability with respect to the other hypothesis because it affects the final enumeration.

Therefore, an exciting part of side-channel attacks lies in the design and choice of such a distinguisher. A first observation from [START_REF] Whitnall | The Myth of Generic DPA. . . and the Magic of Learning[END_REF] is that there does not exist a generic distinguisher that would asymptotically (with respect to the number of acquired traces) work whatever the leakage model φ. This means that the adversary has to use some kind of a priori knowledge on the leakage model of the target to choose a distinguisher. Side-channel attacks are mostly divided into two categories:

the supervised attacks where this a priori comes from a preliminary profiling phase of the target and the unsupervised attacks where this a priori comes from pure physical knowledge about how electronics works and from assumptions on the device being targeted.

Supervised Attacks

Supervised attacks correspond to a strong adversary's model where the latter is supposed to be able to conduct a profiling phase of the target with full control on the device, prior to the attack. Such a profiling phase is a machine learning task whose goal is to learn either a generative or a discriminative model of the leakage from labeled examples. A generative model is an estimation of the conditional probability P(L | Z). A discriminative model is an estimation of the conditional probability P(Z | L). Both are linked through the well-known Bayes' theorem:

P(Z | L) = P(L | Z) • P(Z) P(L) (1.12) 1.2. Side-Channel Analysis
Given a set of attack traces L = {(ℓ i , x i ), 1 ≤ i ≤ N}, a common way to derive a distinguisher from a discriminative model is to define:

D L [k] = N ∏ i=1 P(Z = g(x i , k) | L = ℓ i ) (1.13)
If the model is generative, one can replace If the model, either generative or discriminative, is perfectly learned during the profiling phase, these attacks are known to be optimal from an information theory point of view. Therefore, research in this field mostly resides in practical improvements of machine learning tools (essentially deep learning tools in the last 5 years) in order to improve the estimation of probability distributions in an SCA context. The main drawback of these attacks is their assumption on the adversary's capability. It is often impossible to run the profiling phase on the target device itself. A more realistic assumption is that the adversary may acquire a clone of the device over which she would have full control. However, it is not always easy to find the exact same model and setup than the targeted device and it introduces the template portability problems [START_REF] Elaabid | Portability of templates[END_REF] due to variations in the manufacturing process.

P(Z = g(x i , k) | L = ℓ i ) by P(L = ℓ i | Z = g(x i , k)) • P(Z = g(x i , k)),

Unsupervised Attacks

As opposed to supervised attacks, unsupervised attacks do not require preliminary profiling of the target, constituting a broader threat since they imply weaker assumptions on the adversary model. Since they do not suppose prior specific information on the device, one has to use physical a priori to design a sound distinguisher. Such a priori is usually related to the binary representation of the sensitive variable since processors manipulate bits. There exist multiple distinguishers translating different types of a priori into an actual strategy. They consist in computing, for all key candidate k, a certain statistic from the traces under the assumption that the sensitive variable is Z k = g(X, k). Since statistics are usually well suited for univariate data, they suffer from the same problem as leakage assessment techniques. The classical method is to compute a sample-wise statistic on all the samples of the traces and to retain the maximum (or minimum) as a score.

Chapter 1. Context and motivations Differential Power Analysis. Historically, one of the first proposed a priori is to suppose that a particular bit of the sensitive variable induces differences in the leakage when set to 0 or 1. This gives rise to the so called Differential Power Analysis (DPA) [START_REF] Kocher | Differential power analysis[END_REF]. In such case one can define the following distinguishers:

D (DPA) L [k] = max s 1 |A k | ∑ ℓ∈A k ℓ[s] - 1 |B k | ∑ ℓ∈B k ℓ[s] (1.14)
where ℓ[s] stands for sample s of trace ℓ and A k and B k form a partition of the set of traces L according to the value of the leaking bit of Z k . Such distinguisher exploits the leakage of only one bit of the sensitive variable.

A more generic framework, brought by the stochastic attacks, allows to take into account more generic a priori. In such attacks, the adversary expresses the instantaneous leakage model φ k * [s] as a parametric model whose parameters are regressed from the traces through a regression technique, still under a key assumption. A measure of fitness is then used as distinguisher.

Correlation Power Analysis. The most famous example is probably the Correlation Power Analysis (CPA) [START_REF] Brier | Correlation Power Analysis with a Leakage Model[END_REF] which assumes that there exist some parameters

α, β ∈ R such that: φ k * [s](Z k * ) = α • HW(Z k * ) + β (1.15)
where HW stands for the Hamming weight function counting the number of bits set to 1 in the variable. In such a case, the measure of fitness can directly be computed with the Pearson correlation coefficient:

D (CPA) L [k] = max s cov(L[s], HW(Z k )) Var(L[s]) • Var(HW(Z k )) (1.16)
Linear Regression Analysis. Then, the Linear Regression Analysis [START_REF] Doget | Univariate side channel attacks and leakage modeling[END_REF],

came to relax the assumption that all the bits of the sensitive variable should have the same contribution to the leakage. Instead, they may be weighted by real coefficients (α 0 , . . . , α n ) ∈ R:

φ k * [s](Z k * ) = α 0 + n ∑ i α i • Z k * [i] (1.17) where Z k * [i] represents the i th bit of Z k * .
Such assumption traduces the fact that the instantaneous leakage model can be expressed as a polynomial of degree one.

Thus, for all key hypothesis k, a linear regression can be performed to find such

polynomial p k [s] of degree 1 minimizing the quadratic error E[ L -p k (Z k ) 2 ].
Then, the coefficient of determination (R 2 ) can be used as a distinguisher:

D (LRA) L [k] = max s 1 - E[ L[s] -p k [s](Z k ) 2 ] Var(L[s]) (1.18)
D (MBA) L [k] = max s S M(Z k ) L (s) (1.19)
The most classic example of such model-based attacks is probably the Mutual Information Analysis (MIA) [START_REF] Gierlichs | Mutual Information Analysis[END_REF] which uses the MI as leakage assessment technique:

D (MIA) L [k] = max s I(L[s], M(Z k )) (1.20)
An in-depth analysis about this strategy and the optimal choice of the model is conducted in Chapter 3.

All the distinguishers discussed in this section have their strengths and weaknesses. It is not possible to rank them according to a single objective criteria, for example the number of required traces to rank the correct key at the first position.

As shown in [START_REF] Doget | Univariate side channel attacks and leakage modeling[END_REF] a CPA performs better than a LRA if the true leakage is effectively a Hamming weigh model because it is simpler (with a lower capacity) which induces a higher distinguishability. For the same reason, if the leakage effectively comes from only one bit, the DPA may outperform the other attacks. However, in many practical cases the LRA would perform better because the bit are weighted with very different coefficients, (even sign inversions [START_REF] Cristiani | A Bit-Level Approach to Side Channel Based Disassembling[END_REF]). The main advantage of the MBA is that they offer a way to work with any leakage assessment techniques.

This means that any improvement of such techniques would automatically be translatable into an improvement of the corresponding attack (which is the outline of the two next chapters of this thesis).

Distinguishers discussed in this section all have different strengths, yet they all share the same drawback: the fact of being intrinsically unidimensional. The two inconvenients discussed in subsection 1.2.2 for the leakage assessment technique also apply to these distinguishers. The maximum along time samples could be replaced by some kind of combination of several samples (for example summing the scores over a window) but such a strategy would be impacted by non-informative samples and brings questions about the length of the window. In any case, the incentive of designing an intrinsically multidimensional distinguisher is high and the intuition behind this thesis is that research in this direction might be fruitful, especially with the global rise of deep learning techniques introduced in section 1.3.

Chapter 1. Context and motivations

Side-Channel Countermeasures

In order to counteract side-channel attacks, designers may implement strategies that aim at reducing the dependency between the leakage and the sensitive variables.

These countermeasures are mainly divided into two categories: the hiding and the masking countermeasures which can be combined to increase security.

Hiding

The main principle of hiding countermeasures is to add perceived noise in the adversary's measurements without modifying the internal variables being processed. A common approach to defeat such countermeasures is to apply some kind of preprocessing to the traces before the attack. These include realignment through pattern matching [START_REF] Nagashima | DPA Using Phase-Based Waveform Matching against Random-Delay Countermeasure[END_REF], integration techniques [Man04; MOP10] or transformation of small parts of the traces into probability distribution as in the SCATTER strategy [START_REF] Thiebeauld | SCATTER: A New Dimension in Side-Channel[END_REF]. More recently, deep learning techniques came proposing a sound alternative to such preprocessing techniques (mainly for the supervised attacks) with promising results as discussed in subsection 1.3.2.

Many

Masking

As opposed to hiding, masking countermeasures modify the internal variables of the algorithms using secret sharing techniques [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF]. The idea is to split each sensitive intermediate variable Z, into d shares: (Z i ) 1≤i≤d . The d -1 shares Z 2 , ..., Z d are randomly chosen and the last one, Z 1 is processed such that:

Z 1 = Z * Z 2 * • • • * Z d (1.21)
for a group operation * of Z. The processing of Z is replaced by the processing of all the shares which are only recombined at the end of the computation to give the correct ciphertext. This has the effect of complexifying the stochastic process 1.3. Emergence of Deep Learning in SCA S generating L from Z, rendering it no longer separable into a deterministic and a noise part. Assuming the masks are uniformly distributed, the knowledge of d -1 shares does not tell anything about Z (this is why such masking is said to be of order d -1).

However, partial information on the d shares can be exploited to retrieve information about Z. That is why, to defeat masking, one should use a distinguisher able to combine the leakage of at least d samples of the traces (assuming shares do not leak at the same time). For supervised attacks, this corresponds to modeling multivariate probability densities which does not drastically change the shape of the attack even though it significantly increases the number of required traces. It is a bit trickier for unsupervised attacks. A common strategy is to combine a model-based attack with higher-order leakage assessment techniques discussed in section 1.2.2.

However, such strategies bring questions about the optimal choice of the model (as discussed in Chapter 3) and about the combination function. Stochastic attacks may also be extended to deal with masked implementations [START_REF] Dabosville | A New Second-Order Side Channel Attack Based on Linear Regression[END_REF], although they suffer from limitations pointed out in Chapter 5.

Emergence of Deep Learning in SCA

General Concept of Deep Learning

Machine learning is a branch of computer science that groups all the techniques that aim at granting a computer the ability to learn from data. Deep Learning (DL) is a sub-part of machine learning based on artificial neural networks. Such networks are inspired by the processing of information in biological systems and aim at approximating a function solving an optimization problem. They consist of a succession of processing units called neurons organized in layers as represented in Figure 1.3. Input and output layers are specified by the function that should be approximated.

Hidden layers are not specified which gives rise to many different architectures adapted by designers to the nature of the underlying problem. By analogy with the synapses in the brain, neurons share connections with the adjacent layers' neurons.

The strength of such connections is materialized by weighting coefficients which are updated during the training phase of the network. The objective of the network is encoded in the so called loss function which should be minimized. Such a loss function takes as input the output of the network and may also take some additional data often called the labels. The training consists in applying a form of the gradient descent algorithm in order to minimize the loss function, computed with the available data.

Each parameter is iteratively updated in the opposite direction of the loss function's gradient, which is estimated through the backpropagation algorithm [START_REF] Henry | Gradient theory of optimal flight paths[END_REF].

(θ).

There exist several such loss functions, for example, [START_REF] Masure | A Comprehensive Study of Deep Learning for Side-Channel Analysis[END_REF] showed that the negative log-likelihood is sound in an SCA context:

L(θ) = 1 N N ∑ i=1 -log 2 (F θ (ℓ i )[z i ]) (1.22)
The main advantage of using DL over more classical hand-crafted methods is the flexibility of neural networks. Indeed, it has been shown in the universal approxima- [START_REF] Timon | Non-Profiled Deep Learning-based Side-Channel attacks with Sensitivity Analysis[END_REF] is that it does not discuss the choice of the model. Indeed, it is hard to analytically reason from classification neural network outputs and their analysis is mostly empirical. This is why one of the core ideas of this thesis is to bridge DL techniques to some more tractable concepts from the information theory in order to ease the theoretical reasoning.

Information Theory

The entropy H(X) [START_REF] Shannon | A mathematical theory of communication[END_REF] of a random variable is a fundamental quantity in information theory that indicates how much information one would gain, in average, by learning a particular realization x of X. It is defined as the expectation of the self-information log 2 (1/p X ). In a discrete context:

H(X) = ∑ x∈X P X (x) • log 2 ( 1 P X (x) ) (1.23)
In a side-channel context, X could be replaced by L, the leakage variable. However, one is not interested in the absolute information provided by L but rather in the amount of information revealed about a second variable such as a sensitive variable Z. This is exactly what is measured by the mutual information I(Z, L). It is defined as:

I(Z, L) = H(Z) -H(Z | L) = H(L) -H(L | Z) (1.24)
where H(A | B) stands for the conditional entropy of A knowing B:

H(A | B) = ∑ b∈B P B (b) • H(A | B = b) (1.25)
Chapter 1. Context and motivations

Another useful way to characterize I(Z, L) is to express it as the Kullback-Leibler (KL) divergence between the joint distribution and the product of the marginals:

I(Z, L) = D KL (P Z,L || P Z ⊗ P L ) = ∑ z∈Z ∑ l∈L P(z, l) • log P(z, l) P(z) • P(l) (1.26)

Thesis Motivations and Outline

As shown throughout this introductory chapter, many techniques have been developed to extract and exploit the dependency between a sensitive variable and a leakage variable. This diversity makes it hard for designers and evaluators to draw an objective metric in order to assess leakage. From an information theory point of view, the maximum amount of information one could extract from a side-channel trace is bounded by the mutual information, I(Z, L) between the sensitive variable Z and the trace L. This quantity is, indeed, central in the side-channel domain. The goals of the different actors could be summarized as follows:

• Designers aim at implementing countermeasures to decrease as far as possible I(Z, L), with computational, spatial and efficiency constraints.

• Evaluators aim at estimating I(Z, L) as closely as possible to assess leakages in a worst-case scenario.

• Attackers aim at developing strategies to partially or fully exploit I(Z, L) in order to recover a secret.

The main problem of such a unified paradigm is that I(Z, L) is known to be hard to estimate from drawn samples when the variables live in a high dimensional space, which is generally the case of L. Indeed, computing I(Z, L) usually requires an estimation of the conditional density Pr(Z|L) which is hard because of the wellknown curse of dimensionality. This explains why conventional leakage assessment tools and classical attack strategies typically focus on one (or a few) samples at a time in the trace. As a result, the amount of information effectively detected or used may be significantly lower than I(Z, L).

In a completely unrelated context, Belghazi et al. [START_REF] Ishmael | Mutual Information Neural Estimation[END_REF] lately introduced a Mutual Information Neural Estimator (MINE) which uses the power of deep learning to compute mutual information in high dimension. They have proposed applications in a pure machine learning context but we argue that this tool might be of great interest in the side-channel domain. Indeed, as discussed in subsection 1.3.2, deep learning techniques seem to be promising and well-suited for SCA. Being able to efficiently compute I(Z, L) in an unsupervised way (no profiling of the target needed), no matter the target, the implementation, or the countermeasures used, would be highly relevant for all the different parties.

Thesis Motivations and Outline

The analysis of MINE in a side-channel context is the first contribution of this thesis and is discussed in Chapter 2. We show that it constitutes a new multidimensional leakage assessment tool that outputs an interpretable number representing the upper bound of information one could potentially exploit from the target.

However, knowing how much information is leaking is not the same as knowing Eventually, the analysis of EMA in the context of masked implementations raised questions about higher-order generalizations of stochastic attacks. Some inconsistencies related to the genericity of the state-of-the-art generalizations with respect to the masking scheme are pointed out in Chapter 5. We then propose a new unsupervised strategy, the Joint Moment Regression (JMR), which aims at being generic regarding the masking scheme, while still benefiting from the flexibility of the stochastic attacks. As a final thought, we highlight the fact that EMA and JMR might be combined to form a deep learning-based unsupervised attack agnostic to the underlying masking scheme and requiring only one network training.

To ease the reading of this thesis and make the chapters standalone, there may be small overlaps between their introductory parts as we reintroduce notations that are useful for the understanding of the aforesaid chapters.

Chapter 2

Leakage Assessment through Neural Estimation of the Mutual Information

"Truth is multi-dimensional."

Peter Shepherd

A large variety of side-channel attacks have been developed to extract secrets from electronic devices through their physical leakages. Whatever the utilized strategy, the amount of information one could gain from a side-channel trace is always bounded by the Mutual Information (MI) between the secret and the trace. This makes it, a key quantity for leakage evaluation. Unfortunately, traces are usually of too high dimension for existing statistical estimators to stay sound when computing the MI over full traces. However, recent works from the machine learning community have shown that it is possible to evaluate the MI in high dimensional space thanks to new deep learning techniques. This chapter explores how this new estimator could impact the side channel domain. It presents an analysis whose aim is to derive the best way of using this estimator in practice. Then, it shows how such a tool can be used to assess the leakage of any device.

Introduction

Context

As explained in the introductory chapter, Side-Channel Analysis (SCA) is defined as the set of techniques aiming at gaining information on a secret, owned by a system, through an auxiliary leakage channel often related to its physical implementation.

The secret is usually a cryptographic key but could be as well basic block execution, assembly instructions, or even the value of an arbitrary register. The basic assumption is that the secret and the side-channel data are statistically dependent. Many techniques have been developed to exploit part of this dependency and mount an attack but the incentive to develop a leakage assessment protocol can be found in several works [MSQ08; SM15; Bro+19]. From a purely theoretical point of view, the best metric to assess the quantity of leakage would be the mutual information I(Z, L) between the sensitive variable and the full trace as it measures the dependency between these two variables, by definition. However, such a metric has not really been used in the state-of-the-art. Indeed, it is famously hard to estimate due to the so called curse of dimensionality. Traces being usually of too high dimension, the majority of the leakage assessment techniques work in a univariate way, computing sample-wise statistics from the trace, as pointed out in subsection 1.2.2. Thus, they may underestimate the leakage or even state that there is no leakage when there is.

On the other hand, latest deep learning techniques have proved to be a very interesting tool for SCA since neural networks are able to automatically combine information from many samples of the traces. In addition, Belghazi et al. [START_REF] Ishmael | Mutual Information Neural Estimation[END_REF] lately introduced a Mutual Information Neural Estimator (MINE) which uses deep learning techniques to produce an estimation of mutual information between high dimensional variables. MINE has been developed in a completely unrelated context, but this chapter proposes to analyze its applicability in the side-channel domain.

The goal is to derive the best way to use MINE, in order to develop a new leakage assessment tool able to directly compute I(Z, L).

Chapter Organization

The general method and the mathematical ideas behind MINE are presented in section 2.2. Section 2.3 proposes an in-depth analysis of MINE in a side-channel context supported with synthetic traces, highlights the problem of overfitting and suggests ways of dealing with it. Section 2.4 provides some real case applications. It shows how this estimator constitutes a reliable leakage assessment tool that can be used to compare leakage from different implementations and devices. This section also shows that such an estimator can be used as a guide for an evaluator/attacker to maximize the MI captured from different hardware side-channel setups.

Mutual Information Neural Estimation

21

Mutual Information Neural Estimation

Mutual information is a powerful tool in data science since it measures the dependencies between two variables. In our case, it may be seen as an upper bound on the amount of information an attacker could gain on the secret from the target's leakage. The main problem is that side-channel data are often of too high dimension for classical estimators to stay sound when computing the MI with the full trace. The most common ways to estimate MI are the histogram method and the kernel density estimation both described in [START_REF] Prouff | Theoretical and Practical Aspects of Mutual Information Based Side Channel Analysis[END_REF]. There also exists a non parametric estimation based on k-nearest neighbors [START_REF] Kraskov | Estimating mutual information[END_REF]. This chapter is interested in MINE [START_REF] Ishmael | Mutual Information Neural Estimation[END_REF], a new estimator based on deep learning techniques, which claims to scale well with high dimensions. Technical details about MINE are given hereafter.

A well known property of I(Z, L) is its equivalence with the Kullback-Leibler (KL) divergence between the joint probability p Z,X = Pr(Z, L) and the product of the marginals p Z ⊗ p L = Pr(Z) • Pr(L):

I(Z, L) = D KL (p Z,L || p Z ⊗ p L ) (2.1)
where D KL (p, q) is defined as follow:

D KL (p || q) = E p log p q (2.2)
whenever p is absolutely continuous with respect to q. This property guarantees that when q is equal to 0, p is also equal to 0 and there is no division by 0 in the logarithm.

By definition, p Z,L is absolutely continuous with respect to p Z ⊗ p L .

The key technical ingredient of MINE is to express the KL-divergence with variational representations, especially the Donsker-Varadhan representation that is given hereafter. Let p and q be two densities over a compact set Ω ∈ R d .

Theorem 1. (Donsker-Varadhan, 1983) The KL-divergence admits the following dual representation:

D KL (p || q) = sup T: Ω→R E p [T] -log(E q [e T ]) (2.3)
where the supremum is taken over all functions T such that the two expectations are finite.

A straightforward consequence of this theorem is that for any set F of functions T : Ω → R satisfying the integrability constraint of the theorem we have the following lower bound:

D KL (p || q) ≥ sup T∈F E p [T] -log(E q [e T ]) (2.4)
Thus, using Equation 2.1, one have the following lower bound for I(Z, L):

I(Z, L) ≥ sup T∈F E p Z,L [T] -log(E p Z ⊗p L ) [e T ]) (2.5)
Chapter 2. Leakage Assessment through Neural Estimation of the Mutual Information How to compute I(Z, L). To put it short, the idea is to define F as the set of all functions T θ parametrized by a neural network with parameters θ ∈ Θ and to look for the parameters maximizing the loss function L : Θ → R:

L(θ) = E p Z,L [T θ ] -log(E p Z ⊗p L ) [e T θ ]) (2.6)
This loss function is itself bounded by I(Z, L). The universal approximation theorem for neural networks guarantees that this bound can be made arbitrarily tight for some well-chosen parameters θ. The goal is then to find the best θ, potentially using all the deep learning techniques and, more generally, all the tools for optimization problem-solving. The expectations in Equation 2.6 can be estimated using empirical samples from p Z,L and p Z ⊗ p L and the maximization can be done with the classical gradient ascent. A noticeable difference with a classical deep learning setup is that the trained network is not used for any kind of prediction. Instead, the evaluation of the loss function at the end of the training gives an estimation of I(Z, L).

We give hereafter the formal definition of the estimator as stated in the original paper [START_REF] Ishmael | Mutual Information Neural Estimation[END_REF].

Definition 1. (MINE) Let A = {(z 1 , ℓ 1 ), . . . , (z n , ℓ n )} and B = {( ∼ z 1 , ∼ ℓ 1 ), . . . , ( ∼ z n , ∼
ℓ n )} be two sets of n empirical samples respectively from p Z,L and p Z ⊗ p L . Let F = {T θ } θ∈Θ be the set of functions parametrized by a neural network. MINE is defined as follows:

I(Z, L) n = sup T∈F E A [T] -log(E B [e T ]) (2.7)
where E S [•] stands for the expectation empirically estimated over the set S.

The main theoretical result proved in [START_REF] Ishmael | Mutual Information Neural Estimation[END_REF] is that MINE is strongly consistent.

Theorem 2. (Strong consistency) For all ϵ > 0 there exist a positive integer N such that:

∀n > N, |I(Z, L) -I(Z, L) n | < ϵ, a.e.
(2.8)

In practice, one often only have a set of samples from the joint distribution: A = {(z 1 , ℓ 1 ), . . . (z n , ℓ n )}. Samples from the product of the marginals can be artificially generated by shuffling the variable X using a random permutation σ: B = {(z 1 , ℓ σ(1) ), . . . , (z n , ℓ σ(n) )}. We provide a pseudo-code implementation of MINE, in algorithm 1, that uses minibatch gradient ascent. Note that B is regenerated after each epoch. Thus, this algorithm is not strictly implementing MINE as defined in Equation 2.7 because B is fixed in this definition. Theoretical arguments are provided in subsection 2.3.4 to explain why this regeneration limit overfitting in practice and is therefore mandatory.

Algorithm 1: Mine implementation

Input: A = {(z 1 , ℓ 1 ), . . . (z n , ℓ n )} θ ← Initialize network
for i = 1; i = n b do L(θ) ← E A i [T θ ] -log(E B i [e T θ ]) // Evaluate the loss function G(θ) ← ∇ θ L(θ) //

Analysis of MINE in a Side-Channel Context

MI has found applications in a wide range of disciplines and it is not surprising that it is also of great interest for side-channel analysis. Unlike Pearson correlation coefficient, it detects non-linear dependencies and thus does not require any assumptions on the leakage model. Another key property of the MI is that it is invariant to bijective transformations of the variables. This is of interest for side-channel as Z usually represents the state of an internal variable (ex: Z = k * ⊕ X for an AES) and is therefore unknown but bijectively related to a public variable X. In that case, there exists a bijective function g k * such that Z = g k * (X) and:

I(Z, L) = I(g -1 k * (Z), L) = I(X, L) (2.9)
Thus, one may estimate I(Z, L) with only the knowledge of X and L and therefore quickly get the amount of leakage an attacker could potentially exploit.

In what follows, we consider that we are granted n samples (z 1 , ℓ 1 ), . . . , (z n , ℓ n ) of traces associated to the sensitive variable being processed in the device (or as stated above, to any bijection of this variable). These samples will be either generated on simulation or measured from real case experiments. The goal is to derive the best way to use MINE in a side-channel context in order to compute a reliable estimation of I(Z, L).

Simulated Traces Environment

In order to assess the capabilities of MINE experiments on synthetic traces were first conducted. These traces have been generated using a leakage model which may seem awkward since the whole point of conducting MI analysis is to avoid any assumption on the leakage model. But we argue that as a first step, it brings Trace generation. To generate traces, featuring n l + n r independent samples, a sensitive byte 0 ≤ s ≤ 255 was first drawn uniformly. The leakage was spread over the n l samples drawn from a normal distribution centered in the Hamming Weight (HW) of s and with noise σ ∼ N (HW(z), σ). The n r remaining samples are random points added to the trace to artificially increase the dimension and be closer from a real scenario. Each of the n r samples is drawn from a normal distribution centered in c and with noise σ ∼ N (c, σ), where c is an integer itself drawn uniformly between 0 and 8. A very simple yet informative case is to set n l = 1, n r = 0 and σ = 1. In that case, the true mutual information I(Z, L) is equal to:

I(Z, L) = H(Z) -H(Z|L) = 8 - 255 ∑ z=0 ∞ -∞ Pr(z, l) • log 2 1 Pr(z|l) dl = 8 - 255 ∑ z=0 ∞ -∞ 1 2 8 1 √ 2π e -1 2 (l-HW(z)) 2 • log 2 ∑ 255 z ′ =0 e -1 2 (l-HW(z ′ )) 2 e -1 2 (l-HW(z)) 2 dl ≈ 0.

Input Decompression

Trying to gain intuition about the reasons causing the network to perform poorly in this situation, we hypothesized that the information in the first layer, especially the value of z, could be too condensed in the sense that only one neuron is used to describe it. Intuitively, the information provided by z about the corresponding trace ℓ is not continuous in z. The meaning of this statement is that there is no reason that two close values of z induce two close values of l. For example, in a noise-free

Hamming weight leakage model, the traces corresponding to a sensitive value of 127 and 128 would be very different since HW(127) = 7 and HW(128) = 1. Since neural networks are built using a succession of linear and activation functions which are all continuous, approximating functions with quick and high variations may be harder for them. Indeed, building a neural classifier that extracts the Hamming weight of an integer is not an easy task. However, if the value of this integer is split into multiple neurons holdings its binary representation, the problem becomes trivial as it ends up being a simple sum.

This observation led us to increase the input size to represent the value of z in its binary form, thus using 8 neurons. However, computing I(Z, L) in that case gives an unfair advantage to the arbitrarily chosen Hamming weight model. Indeed, the value of L would be closely related to the sum of the input bits. So we decided to compute I(Z ⊕ k, L) instead of I(Z, L), with a fixed k. As stated above this bijective transformation does not change the MI anyway and removes a possible confusion factor in the analysis. Results with the same parameters as before (n l = 1, n r = 0,

σ = 1)

Learning Random Permutations

In order to test this hypothesis in a more generic case, this section proposes to build a neural network P θ which goal is to learn a random permutation P of {0, . . . , n -1} and to analyze its performance in terms of ID. Permutations have been chosen because they are arbitrary functions with no relation between close inputs. For an integer m < n the network returns a float P θ (m) which has to be as close as possible to P(m). The loss function was defined as error: L(θ) = |P θ (m) -P(m)|. Network architecture was again a simple MLP but with 3 hidden layers of size 100.

To study the effect of ID the input layer was defined to be the representation of m in different bases, with one neuron per digit. presents a scenario where using base 2 is a better choice, when computing the MI with assembly instructions.

Remark 3. Note that the constant function P θ = n 2 would result in an average loss function of n 4 , which explains the knee point around n 4 observable in most of the curves: quickly converging towards this function is an efficient strategy for the network to minimize its loss at the beginning of the learning phase. We verified this statement by looking at the predictions of the network which were all close from n 2 in the early stages of the training.

MINE in Higher Dimension

This section presents results of simulations in higher dimension and compare MINE estimation to that provided by the classical histogram and KNN methods. The histogram estimator has been implemented following the description from [PR09] and Steeg's implementation [START_REF] Ver | Non-parametric Entropy Estimation Toolbox[END_REF] has been utilized for KNN. Network architecture described in subsection 2.3.1 has been used with OHE to encode the S variable. We have kept n l = σ = 1 so the true MI is still around 0.8 bits but n r was no longer set to 0 in order to increase the traces dimension. Figure 2.4 shows the results for n r = 1 and n r = 9. In both case MINE correctly converges toward the true MI. The histogram method tends to overestimate the MI (as explained in [START_REF] Nguyen | Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance[END_REF]) while KNN method underestimates it. With dimension greater than 10 these methods are not reliable anymore. One could argue that any dimension reduction technique applied in the above experiments would allow to compute the MI with classical estimators.

While this is true in this case it may result in a loss of information in a real case scenario where the information could be split into multiple samples of the traces. We have conducted many experiments with different parameters and MINE always returned reliable estimations even in very high dimension (ex: Figure 2.5b with n l = 5 and n r = 1000).

Chapter 2. Leakage Assessment through Neural Estimation of the Mutual

Information (A) Trace dimension = 2 (n l = 1, n r = 1, σ = 1) (B) Trace dimension = 10 (n l = 1, n r = 9, σ = 1)
FIGURE 2.4: Comparison of MINE with classical estimators in higher dimension

Analysis of the Overfitting Problem

Results of simulations are encouraging as they seem accurate with a lot of different parameters but one problem still has to be solved before testing MINE on real traces:

when to stop the training ? Until now, training has been manually stopped when the loss had converged towards the true MI. No such threshold value will be granted in real cases. One could argue that since the loss function is theoretically bounded by the true MI, a good strategy would be to let the training happen during a sufficiently long time and to retain the supremum of the loss function as the MI estimation.

We argue that this strategy is not viable: in practice the bound does not hold as expectations in the loss are not the true expectations but are only estimated through empirical data. Thus, MINE can still produce output above the true MI. In other terms, MINE is no exception to the rule when it comes to the overfitting problem: the network can learn ways to exploit specificities of the data it is using to train, in order to maximize its loss function. We propose hereafter a detailed analysis of this problem and answer to the following question: is it possible to control (for example to bound with a certain probability) the error made by the network ?

Let us return to the definition of MINE estimator:

I(Z, L) n = sup θ∈Θ E A [T θ ] -log(E B [e T θ ]) (2.11)
The problem comes from the fact that the two expectations are estimated over the set of empirical data A and B. The error can not be controlled in the classical way with the central limit theorem because there is a notion of order that is important: the two sets A and B are selected before the network tries to find the supremum over Θ. Thus, the network can exploit specificities of A and B in its research. We show in Theorem 3 that given two sets A and B, the supremum may not even be bounded. Theorem 3. Let X, Y be two random variables over Ω. Let ⃗ x = (x 1 , . . . , x n ) ∈ Ω n and ⃗ y = (y 1 , . . . , y n ) ∈ Ω n be two samples of n realizations of respectively X and Y. Then,

sup T: Ω→R E ⃗ x [T(X)] -log(E ⃗ y [e T(Y) ]) < ∞ ⇔ ∀i, ∃j such that x i = y j
Proof. Let us introduce two new random variables, X ′ and Y ′ defined as follows:

∀ω ∈ Ω, P(X ′ = ω) = 1 n • |{x i = ω}| and P(Y ′ = ω) = 1 n • |{y i = ω}|
The samples ⃗ x and ⃗ y are perfect samples of X ′ and Y ′ (by definition of X ′ and Y ′ ), thus, the estimated expectations are equal to the true expectations computed over this new variables: sup

T: Ω→R E ⃗ x [T(X)] -log(E ⃗ y [e T(Y) ]) = sup T: Ω→R E X ′ [T(X ′ )] -log(E Y ′ [e T(Y ′ ) ])
Now let us assume the right part of the equivalence. This condition means that there is no isolated x i , or in other words: ∀ω,

Pr(Y ′ = ω) = 0 ⇒ Pr(X ′ = ω) = 0.
This guarantees the absolute continuity of p X ′ with respect to p Y ′ and thus, that

D KL (p X ′ || p Y ′ ) exists. Therefore, using Theorem 1: sup T: Ω→R E ⃗ x [T(X)] -log(E ⃗ y [e T(Y) ]) = D KL (p X ′ || p Y ′ ) < ∞
If, on the other hand, this condition is false: ∃i such that ∀j, x i ̸ = y j . For any given function T one can exploit this isolated x i modifying T(x i ) without influencing the second expectation. In particular, if T(x i ) tends towards infinity:

Chapter 2. Leakage Assessment through Neural Estimation of the Mutual Information lim T(x i )→∞ E ⃗ x [T(X)] -log(E ⃗ y [e T(Y) ]) = lim T(x i )→∞ 1 n n ∑ k=1 x k T(x k ) -log( 1 n n ∑ k=1 y k e T(y k ) ) = lim T(x i )→∞ 1 n n ∑ k=1 x k T(x k ) -log( 1 n n ∑ k=1 y k e T(y k ) ) = ∞ So in that case: sup T: Ω→R E ⃗ x [T(X)] -log(E ⃗ y [e T(Y) ]) = ∞
This theorem means that most of the time (and especially for high dimensional variables) the supremum is infinite and MINE is not even well defined. The natural question that comes now is: why does MINE seem to work in practice?

We claim that this is due to the implementation and especially to the randomization of the set B evoked in section 2.2: after each epoch a new permutation σ is drawn to generate samples from p Z ⊗ p L : B = {(z 1 , ℓ σ(1) ), . . . , (z n , ℓ σ(n) )}. Thus, the isolated samples from A are not always the same at each epoch which does not leave time for the network to exploit them. To verify that this was a key element, MINE was run without this randomization process. The loss function diverged towards infinity, as predicted by Theorem 3.

In the long run, the network can still learn statistical specificities of the dataset such as samples from A that has a greater probability of being isolated, and exploit them. This explains why MINE may overfit when it has a long time to train. That is why we suggest to add a validation loss function.

Validation Loss Function

A validation loss function is a common tool when it comes to detect overfitting and

Fill the Holes

Theorem 3 states that there is still a case where the supremum is bounded: when ∀a ∈ A, ∃b ∈ B such that a = b, or in other words, when there is no isolated value in A. An alternative solution to prevent overfitting is thus to force this condition to be true instead of regenerating B after each epoch. Naively filling the holes by adding to B all the isolated values is not a good idea because the resulting set would be biased, not containing stricto sensu samples drawn from p Z ⊗ p L . However, with

A = {(z 1 , ℓ 1 ), . . . (z n , ℓ n )}, A Z = {z 1 , . . . , ℓ n } and A L = {z 1 , . . . , ℓ n } one can define B ′ as the Cartesian product 1 B ′ = A Z × A L which
is by definition a non-biased dataset that covers all the elements of A. The problem is that its size is no longer n but n 2 which drastically impacts the computational time of MINE as the network has to compute T θ (b) for all b ∈ B ′ at each epoch. However, the number of network evaluations can be reduced to c • n where c is the cardinality of the set Z made up of all the possible values taken by the sensitive variable Z. For example, if S is a byte, c = 256. The idea is to evaluate T θ on the c • n elements of the set Z × A L which is sufficient to cover all the couples from B ′ as elements from A Z × A L can all be found in Z × A L . With this implementation MINE is fundamentally bounded by a quantity denoted Maxmi equal to the KL-divergence between the empirical distributions associated to A and B as stated in the proof of Theorem 3. Figure 2.6b shows an example of MINE with this implementation applied to the already considered case (n l = 1, n r = 0, σ = 1). One may observe that the loss function is a lot smoother and is effectively bounded by Maxmi (we tried to let the network train for more than 100k epochs) which is another empirical confirmation of Theorem 3.

However, when the dimension of the variables increases samples tend to be more and more unique. At the limit, they hold the full information about the corresponding sensitive variable z which means that Maxmi will tends towards H(Z). Knowing if the network will always converge towards his supremum or will stabilize to a 1 These sets are actually multisets as they may contains repetitions of a single elements but the Cartesian product can be canonicaly extended to multisets.

Chapter 2. Leakage Assessment through Neural Estimation of the Mutual Information value close to the true MI is an open question. We do think that the randomization proposed in the precedent strategy may help to that aim and that is why we will stick to the validation method for our real-life experiments, which is faster anyway.

Application of MINE in an Evaluation Context

This section provides real case examples where MINE could be useful especially in an evaluation context. Its most straightforward utilization is probably to assess the quantity of information leaking from a device when it computes a cryptographic algorithm. It can be seen as a first security metric, easy to compute whatever the target and the implementation, with low expertise required. However, MINE only returns an upper bound on the amount of leakage potentially usable. In practice, an attacker may not be able to fully exploit this information, depending on her strategy, and that is why classical evaluation methods still have to be performed.

That being said, MINE is also a great comparison tool. Indeed, its output is an interpretable number that allows to objectively rank different devices or implementations in terms of their leakage. It can be used to analyze the effect of a countermeasure or even to compare different hardware setup in order to maximize the MI for future attacks or evaluations.

Leakage Evaluation of an Unprotected AES

As a first real case experiment, our target was an unprotected AES implemented on a cortex M4 device. 20k EM traces centered on the first round of the AES have been acquired through a Langer probe (RF-B 0,3-3) linked to an low noise amplifier and a Tektronix oscilloscope (MSO64, 2.5 GHz) with a sample rate of 1 GS/s. Resulting traces had a length of 50k samples. They have been labeled with the first byte of the corresponding plaintext which was drawn randomly for each computation of the AES.

The main goal of this first experiment was to demonstrate how adding more samples to the analysis, which is the purpose of MINE, increases the amount of information one can recover. To this end, only the n samples with the maximum SNR were kept in the traces, with n in {1, 5, 500}. Network architecture was the same as in the simulated experiments. Results are presented in Figure 2.7. The thick blue plot shows that if one only uses one sample in his analysis (for example with a CPA or histogram-based MIA) he would be able to extract at most 1.15 bits about the secret, per trace. While it is a huge amount of information (it is an unprotected AES) it is possible to extract almost 4 times more using 500 samples. For clarity reasons, only the validation loss has been plotted. Training has been stopped after epoch 500 as these validations (especially the green one) started to decrease. Going further with n ≥ 500 did not produce better results as it seems that the remaining samples were absolutely not informative about the secret.

ADC Comparison

The oscilloscope used in the former experiment offers the possibility to set the ADC precision to either 8 or 15 bits. This is a good opportunity to show MINE comparative interest and its ability to answer questions such as "Is it really worth it to buy the newest scope with the enhanced ADC precision?" in a quantitative and objective way. 10k traces instead of 20k (so that the occupied memory stayed constant) were thus acquired with the 15 bits precision. Results are represented by the thin plots on Figure 2.7. In this case, the answer is that there is a slight improvement (around 10%) working with the 15 bits precision rather than the 8 bits one.

Leakage Evaluation of a Masked AES from the ASCAD Database

One of the main difficulties of side-channel analysis is to extract information even when the target algorithm has been masked. Indeed, masking removes all the firstorder leakage and thus, obliges one to combine samples together to detect a dependency with the secret. This is usually very long as all the couples of samples (or n-tuple) have to be tested.

It is thus a great challenge for MINE to see if it is able to automatically perform this recombination, and detect higher-order leakages. For that purpose, the public dataset ASCAD [START_REF] Benadjila | Study of deep learning techniques for side-channel analysis and introduction to ASCAD database[END_REF] (with no jitter) has been used. It provides a database of 50k EM traces of 700 samples each, of an AES protected with a Boolean masking. A MI estimation, derived from deep learning attack results, has already been done on this dataset [START_REF] Masure | A Comprehensive Study of Deep Learning for Side-Channel Analysis[END_REF]. They reported a MI of 0.065 bit between the traces and the third key byte (the first two were not masked) which provides a reference point.

At first, MINE was not successful: the loss function increased but the validation started to decrease very early which is a direct sign of overfitting. Intuitively, when the underlying problem is more complex, it may be easier for the network to learn properties of the empirical data before the true structure of these data. Then, classical solutions against overfitting have been applied to MINE. These include Batch Normalization (BN) layers, dropout, and regularization techniques. While the last, did not impact performances significantly, the combination of BN and dropout greatly Chapter 2. Leakage Assessment through Neural Estimation of the Mutual Information improved the results. A BN layer has been applied to the inputs in order to normalize them. This is known to make the loss function smoother and thus the optimization easier [START_REF] Santurkar | How Does Batch Normalization Help Optimization[END_REF]. Dropout was activated with p = 0.2 so that each neuron has a probability p of being set to 0 when an output of the network is computed (except when the validation is computed). This is also known to reduce overfitting and make the training more robust [START_REF] Srivastava | Dropout: A Simple Way to Prevent Neural Networks from Overfitting[END_REF].

Results are presented in Figure 2.8: validation loss reached a value of 0.2 bits which is about three times bigger than the MI reported in [START_REF] Masure | A Comprehensive Study of Deep Learning for Side-Channel Analysis[END_REF]. Due to how validation is computed this value cannot be an overestimation of the MI. Our MLP structure may be a little more adapted than the CNN used in [START_REF] Masure | A Comprehensive Study of Deep Learning for Side-Channel Analysis[END_REF] as there is no jitter in that case. We also suggest that the input decompression technique, only usable with MINE, could help the network to learn, especially for complex problems such as when the algorithm is masked. This may explain why MINE was able to extract more information in that case. One can observe that it took 100 epochs for the network to start to learn something. It may seem random but this period of 100 epochs was surprisingly repeatable across experiments.

Instructions Leakage

Another advantage of MINE is that it cannot only compute MI for high dimensional traces but also for secrets with a high number of classes. This is the case if one is interested in recovering information about the raw assembly instructions that are being executed. This branch of SCA is called Side Channel Based Disassembling (SCBD) [GP08; EPW10; Str+15; CLH20] and the main difficulty in this domain is the size of the attacked variable, generally the couple (opcode, operands) which is no longer a simple byte. For example the target device in [EPW10; Str+15; CLH20] is a PIC16F from Microchip which encodes its instruction on 14 bits. Even though some opcodes are not valid, the number of possible couples (opcode, operands) is around 2 12 . It is even worse for more complex processors encoding their instruction on 16 or 32 bits. MINE treats the attacked variable as an input and the number of neurons used to encode it can be adjusted with ID as stated in subsection 2.3.2. Using base 2, one only need 14 neurons to encode an instruction in the PIC example.

In order to test MINE in this context, we have generated a program with 12k randoms instructions for the PIC. Using the same experimental setup described in section 4.2 of [START_REF] Cristiani | A Bit-Level Approach to Side Channel Based Disassembling[END_REF], an EM trace of the whole execution has been acquired (it was averaged on 500 traces as the program is repeatable). This trace has then been separated into 12k sub-traces of 2000 samples each. Each sub-trace was labeled with the executed instruction. As it has been shown in [START_REF] Cristiani | A Bit-Level Approach to Side Channel Based Disassembling[END_REF] that the probe position may be very important, MINE has been applied at 100 different positions (using a (10 × 10) grid) resulting in the MI cartography given in Figure 2.9. The value at each position is the mean of the network's validation computed over the 100 last epochs of the training (all the training lasted 500 epochs and a Gaussian filter has been applied to the figure). Up to 8 bits of information have been found for the best positions which is a high amount if one compares to the full entropy of an instruction which is approximately 12 bits. This shows that MINE stays sound even when the target variable has a high number of classes.

Coil Comparison

Similar to what has been done regarding the selection of the oscilloscope precision, another hardware comparative experiment was conducted. Two probes with two different coil orientations (Langer ICR HH and HV 100-27) have been used. While the "hot" zones are globally the same, one may observe that the coil orientation may have a significant impact on the captured information for some specific positions.

This experiment suggests that MINE could be used to guide the positioning of EM probes during evaluations.

Conclusion

This chapter suggests ways MINE, a new deep learning technique to estimate mutual information, could constitute a new tool for side-channel analysis. The main advantage is its ability to estimate MI between high dimensional variables. Indeed, being able to consider full (or large part of) traces as a variable, allows to assess all potential leakage sources with no a priori on the leakage model neither on the implementation. It seems that MINE can be used as a very simple tool to obtain an objective leakage evaluation from traces. Thus, it may be employed for massive and quick evaluations for designers in their development process as well as for evaluators as a first leakage metric.

These suggestions result from a theoretical and practical analysis of MINE in a side-channel context. MINE's overfitting problem has been deeply investigated as well as the way input representation may have a big impact on performances.

The next natural challenge, which is the object of the next chapter is to investigate Chapter 3

Revisiting Mutual Information Analysis

Multidimensionality, Neural Estimation and Optimality Proofs "Information is not knowledge."

Albert Einstein

The preceding chapter showed how Mutual Information Neural Estimation (MINE) could be applied to side-channel analysis in order to evaluate the amount of leakage of an electronic device. One of the main advantages of MINE over classical estimation techniques is to enable the computation between high dimensional traces and a secret, which is relevant for leakage assessment. However, optimally exploiting this information in an attack context in order to retrieve a secret remains a non-trivial task especially when a profiling phase of the target is not allowed. Within this context, the purpose of this chapter is to address this problem based on a simple idea: there are multiple leakage sources in side-channel traces and optimal attacks should necessarily exploit most/all of them.

Introduction

Context

The Bat+11]) is not complete and rely too much on intuition. As a result, it is difficult to derive the best way to use the new MI estimators, especially in the context of high dimensional variables, where intuition quickly falls short. That is why rebuilding a mathematical framework along with rigorous proofs on how to conduct an optimal multidimensional MIA is one of the contributions of this chapter.

Contributions

1. Clarifying the State Of The Art (SOTA) around the MIA.

We explicitly split MIA into two different versions (this is not explicitly done in the SOTA), to help understanding the need or not of an a priori on the leakage model (subsection 3.2.2). We then highlight inconsistencies with the second version mainly related to the fact that MIA relies on a distinguisher computing a score for each key hypotheses, but the wrong hypotheses scores are not taken into account in the analysis (subsection 3.2.3). This leads us to define a new generic version of MIA which objective is related to a maximization problem that includes the impact of the wrong hypotheses scores (subsection 3.2.4).

Chapter 3. Revisiting Mutual Information Analysis: Multidimensionality, Neural Estimation and Optimality Proofs 2. Providing proofs to analytically solve the mathematical problems emerging from our new version of MIA.

One of the main contributions of this chapter, given by Theorem 4 (subsection 3.2.5), is to solve the optimization problem defined in subsection 3.2.4. Then, Theorem 5 provides an extension of the analysis in the context of masking (section 3.3). Both theorems are designed to take into account the potential multidimensionality of the leakage and therefore are suited to support the use of the new neural MI estimators.

Presenting a new unsupervised multidimensional attack: the Neural Estimated

Mutual Information Analysis (NEMIA).

Mathematical results are then combined with recent breakthroughs regarding neural MI estimation in high dimension. This allows to derive, to the best of our knowledge, the first unsupervised side-channel attack able to benefit from both deep learning techniques (highly multidimensional, no pre-processing of the data...) and the valuable theoretical properties of MI (section 3.4).

Providing Simulations and experiments to support the analysis.

Simulations are provided both to empirically validate the mathematical analysis as well as to gain intuition about their meaning and about which situations are best suited for the use of NEMIA (section 3.5). Eventually, practical experiments on the ASCAD database (both on raw traces and on artificially noised traces) are conducted and show that this new attack seems outperform classical SCA strategies in terms of number of traces needed and noise resiliency (section 3.6).

Mutual Information Analysis

Unsupervised attacks

Suppose an adversary wants to recover the secret key used by the physical implementation of a cryptographic algorithm. He has access to a set of traces (L i ) 1≤i≤n labeled with a public variable X i used for the encryption/decryption. The general idea of an unsupervised side-channel attack is to make a series of hypotheses k i , on a sub-part of the key and to use a distinguisher D(k) allowing to rank the different candidates. Distinguishers use statistical dependencies between traces and an intermediate variable Z k * = g(X, k * ) that depends on a public variable X and the correct key k * through a deterministic function g : X × K → Z related to the underlying algorithm. For simplicity, g(X, k) is denoted g k (X) in the rest of the chapter. Common distinguishers such as Pearson's coefficient or coefficient of determination in a linear regression exploit some a priori on the leakage model. A common intuition about mutual information used as a distinguisher [START_REF] Gierlichs | Mutual Information Analysis[END_REF] is that it has been introduced precisely to reduce the need to have an a priori. It is often found in the literature (e.g. [START_REF] Batina | Mutual Information Analysis: A Comprehensive Study[END_REF]) that it aims at generality, leading to successful attacks without requiring specific knowledge or assumptions on the target. While this is true in some sense, this assertion is mitigated hereafter.

State of the Art

This section presents the state of the art of MIA [Gie+08; PR09; VCS09; Bat+11] and is organized to discuss and clarify the importance of the adversary's leakage model a priori.

MIA uses a distinguisher D which takes the following form 1 :

D(k) = I f (Z k ), L (

MIA Version 1 (Leakage model a priori free)

In its most basic form, MIA uses I(Z k = g k (X), L) as a distinguisher, making hypotheses on k. With φ : Z → R n representing the leakage model of the target, L can be written as L = φ(Z k * ) + N, with N being a random variable independent of Z k for all k, and representing the noise. With these notations, the distinguisher becomes:

D(k) = I Z k , φ(Z k * ) + N (3.2)
Proposition 1. This distinguisher is maximized for the correct key hypothesis k * .

Proof. Using Equation 1.24, for any k ∈ K:

D(k * ) -D(k) = H(L) -H(L | Z k * ) -H(L) -H(L | Z k ) = H φ(Z k * ) + N | Z k -H φ(Z k * ) + N | Z k * (3.3)
Since adding knowledge can only decrease entropy:

D(k * ) -D(k) ≥ H φ(Z k * ) + N | Z k , Z k * -H φ(Z k * ) + N | Z k * (3.4) 1 Due to MI estimator limitations, D(k) is often replaced in practice by max i I( f (Z k ), L[i])
, where L[i] represents the i-th sample of the trace. This does not affect the theory described in this section so we decided to keep it as described in Equation 3.1 for the sake of simplicity. More details are provided in subsection 3.4.1.

MIA Version 2 (Leakage model a priori dependent)

It is still possible to target Z k * = g k * (P) for bijective g k functions. The idea is to apply a non-injective function f to Z k and use I( f (Z k ), L) as distinguisher. The application of f create a partition of Z so f will be called the "partition function" in the rest of this thesis. Since no data transformation can create information (this is the so called data processing inequality [START_REF] Beaudry | An intuitive proof of the data processing inequality[END_REF]), the application of f inevitably decreases the initial information:

∀ f , ∀k, I( f (Z k ), L) ≤ I(Z k , L).
The goal is then to find a function that decreases more I(Z k , L) than I(Z k * , L) and therefore, enhance the discriminating power of the analysis.

For example, assuming that bits leak independently, [START_REF] Gierlichs | Mutual Information Analysis[END_REF] proposes to drop one bit of Z. This is equivalent to redefine the intermediate variable as a restrictive number of bits of g k * (P), and apply MIA version 1 with no partition function. Another idea is to use a guessed version φ of the leakage model φ. Indeed,

I φ(Z k ), φ(Z k * ) + N is clearly maximized for k = k * . Therefore, if φ is not too far from φ, I φ(Z k ), φ(Z k * ) + N may still be maximized for k = k * . It is shown in [VCS09]
that error in the approximation of φ may be less penalizing than for other attacks.

In addition, MIA is more flexible in the sense that it is not limited to exploit linear dependencies and gives an option to mount a successful attack with any leakage model. However, it should be emphasized that, for this version, the adversary must have a good enough a priori on the leakage, otherwise, the attack is unsuccessful. A suitable choice for the partition function necessarily uses assumptions on φ.

While we think this point needed to be clarified, we do not see this as a criticism of MIA. As stated in [START_REF] Whitnall | The Myth of Generic DPA. . . and the Magic of Learning[END_REF], hopes of finding a leakage model free strategy able to target a bijective intermediate variable are vain, even outside the context of MIA. We present hereafter a synthetic proof of the main result of [START_REF] Whitnall | The Myth of Generic DPA. . . and the Magic of Learning[END_REF].

Proposition 2. Let g k be a bijective map for all k. For any strategy S which takes as input a set of traces ⃗ L = φ(g k * (P i )) 1≤i≤n and outputs a ranking of the different key hypotheses, there exists a leakage model φ that would rank k * in the last position such that the attack completely fails.

Proof. First, apply S on traces obtained through any leakage model φ 0 and denote by k the last key returned by S. Now, for all P, define φ0 (g k * (P)) = φ 0 (g k(P)), which completely defines φ0 as g¯k is bijective. Applying S on traces obtained through φ0 would now rank k * in the last position.

This proposition shows that there does not exist any generic distinguisher, that would both:

1) Exploit statistical dependencies between traces and an intermediate variable bijectively related to the plaintext.

2) Work whatever the leakage model of the target.

Since MIA version 2, with a fixed partition function, verifies 1), it necessarily fails for some leakage models or, in other words, has to use an assumption on the leakage model to succeed. Even though it requires an analysis on what partition function should be used, the rest of this chapter is more focused on MIA version 2 since it is more generic in the sense that it can be applied in many more situations.

About the Distinguishability

As stated in [START_REF] Whitnall | A Comprehensive Evaluation of Mutual Information Analysis Using a Fair Evaluation Framework[END_REF], even if D(k) is maximized for k = k * , it is not enough to guarantee a successful attack in practice, when noise comes into play. What is really important is the difference between D(k * ) and the others, or in other words, the distinguishability of the correct hypothesis through the distinguisher D. The idea found in the literature is that for a wrong key hypothesis:

«false predictions will form a partition corresponding to a random sampling of

[L] and therefore simply give scaled images of the global side-channel probability Chapter 3. Revisiting Mutual Information Analysis: Multidimensionality, Neural Estimation and Optimality Proofs density function. Hence, the estimated mutual information will be equal (or close) to zero in this case.» [START_REF] Batina | Mutual Information Analysis: A Comprehensive Study[END_REF].

We do not agree with this fact since the wrong hypotheses scores totally depend on the partition function f and on g k . As explained in the previous section, if the g k 's are bijective, all the scores would be equal if f is also bijective. This fact is well noted in all the papers about MIA but we would like to emphasize that even for non-bijective f the wrong hypotheses score depends on the "degree of bijectiveness" of f . Intuitively, the more compact f is (in the sense of more collisions through f ) the smaller the wrong hypotheses scores would be. But the same is true for the correct score which means that there is a trade-off between how much one wants to decrease I f (Z k ), L for the wrong k and keep I f (Z k * ), L high, to enhance the distinguishability.

Towards an Optimal Partition Function

In the SOTA, the partition function is not seen as a parameter on which a maximization research could be done. Therefore, no research on finding the optimal function f has been conducted. It is generally fixed to one or two constant choices, except in [START_REF] Prouff | Theoretical and Practical Aspects of Mutual Information Based Side Channel Analysis[END_REF] where authors proposed that f could be a generic function. However, it is stated that the adversary:

«does not need a good linear approximation of φ but only a function

[ f ] such that the mutual information I f (Z k * ), φ(Z k * ) is non-negligible » [PR09].
Again, this condition is necessary but not sufficient. Even if bijective functions are excluded one can create the following f 0 function such that:

f 0 (x) =    0, if x ∈ {0, 1} x, else (3.6)
Being almost the identity function, f 0 is such that I f 0 (Z k * ), φ(Z k * ) is high but would have a very low discriminating power. This shows that the wrong hypotheses scores cannot be left out of the analysis. One typically wants to find the f function maximizing the distinguishability of the correct hypothesis. Several criterion has been studied in the literature [START_REF] Whitnall | A Comprehensive Evaluation of Mutual Information Analysis Using a Fair Evaluation Framework[END_REF][START_REF] Reparaz | A Note on the Use of Margins to Compare Distinguishers[END_REF]. In this chapter we chose to use the nearest rival criterion2 . Therefore, let us define the optimal set of functions F opt as:

F opt = arg max f : Z →R n I f (Z k * ), L -max k̸ =k * I f (Z k ), L (3.7)
F opt is a set since the maximum is reached by an infinite amount of functions. Indeed, if f opt ∈ F opt , for any bijection b, b • f opt is also in F opt since bijections do not affect MI. Note that f is not restricted to be one-dimensional. Its domain is set to be R n where n can be any positive integer.

Analytical Resolution

Being consistent with Proposition 2, F opt depends on L and therefore on the leakage model. Since knowledge on φ is required anyway, this section assumes a full knowledge on φ in order to conduct an analytical analysis to find the optimal f function.

Traces are also supposed to be acquired in an ideal set-up, without noise, so that, at least for a significant sub-part of the trace, L = φ(Z k * ). Bounds taking into account imperfect knowledge on φ as well as noise will be given in subsection 3.2.7.

A natural choice for the partition function would be to take f = φ because it maximizes the left term in Equation 3.7: I f (Z k * ), φ(Z k * ) . But it may be possible to find a function that would maximize the global objective without maximizing the left term of Equation 3.7 (we emphasize that f and φ can be multi-dimensional which make the intuition harder to have). Theorem 4 actually proves that it is not possible and that whatever the leakage model, φ ∈ F opt . The main demonstration requires the use of a helper which is introduced in the form of a lemma hereafter.

Lemma 1. Let f : Z → R n be any function. For any leakage model φ: Z → R n there exists

a decomposition of f into f = f 2 • f 1 , with f 1 : Z → N, f 2 : N → R n , satisfying the two following properties: 1) ∃ f 3 : Im f 1 → R n such that f 3 • f 1 = φ 2) ∀z ∈ Z, f 2 | f 1 φ -1 ({φ(z)}) is bijective of reciprocal f -1 2 | f 2 • f 1 φ -1 ({φ(z)})
Proof. The proof is given in Appendix A.

Theorem 4. Let P follow a uniform distribution. Let Z k represent the hypothetical intermediate variables such that Z k = g k (P) with bijective g k 's. Let φ: Z → R n be the leakage model of the target so that L = φ(Z k * ). Then, φ ∈ F opt .

Proof. Let S f = I f (Z k * ), Lmax k̸ =k * I f (Z k ), L represent the distinguishability score for a given function f such that:

F opt = arg max f : Z →R n {S f }
Since all the Z k follow a uniform distribution (P follows a uniform distribution and the g k functions are bijective), the entropy H( f (Z k )) is equal for all k. Then using

I(A, B) = H(A) -H(A | B): S f = -H f (Z k * ) | L + min k̸ =k * H f (Z k ) | L (3.8) Symmetrically, using I(A, B) = H(B) -H(B | A): S f = -H L | f (Z k * ) + min k̸ =k * H L | f (Z k ) (3.9)
Let f : Z → R n be any function. Applying Lemma 1, there exist f 1 and f 2 satisfying the two properties given in Lemma 1, such that f = f 2 • f 1 . The goal is to show that S f ≤ S φ . The proof is divided into two phases: first show that S f ≤ S f 1 using Equation 3.8, then show that S f 1 ≤ S φ using Equation 3.9. Let us start with Equation 3.8:

S f = -H f 2 • f 1 (Z k * ) | L + min k̸ =k * H f 2 • f 1 (Z k ) | L ≤ -H f 2 • f 1 (Z k * ) | L + min k̸ =k * H f 1 (Z k ) | L (3.10)
since applying f 2 in the second term can only decrease entropy (see Lemma 2). The goal is now to remove f 2 in the first term:

-H f 2 • f 1 (Z k * ) | L = ∑ l∈L f2 ∈Im f 2 P(l) • P( f2 | l) • log(P( f2 | l))
(3.11)

P( f2 | l) = P f 2 • f 1 (Z k * ) = f2 | φ(Z k * ) = l = P f 1 (Z k * ) ∈ f -1 2 ( f2 ) | φ(Z k * ) = l (3.12) Knowing that φ(Z k * ) = l implies that Z k * ∈ φ -1 ({l}) and also that f 1 (Z k * ) ∈ f 1 (φ -1 ({l})). Let A l denotes f 1 (φ -1 ({l}))
to avoid heavy notations. Then:

φ(Z k * ) = l =⇒ f 1 (Z k * ) ∈ A l =⇒ f 1 (Z k * ) ∈ f -1 2 ( f 2 (A l )) (3.13)
which means that:

P( f2 | l) = P f 1 (Z k * ) ∈ f -1 2 | f 2 (A l ) ( f2 ) | l if f2 ∈ f 2 (A l ) 0 else (3.14) Lemma 1 states that f 2 | A l is bijective of reciprocal f -1 2 | f 2 (A l ) , so if f2 ∈ f 2 (A l ): P( f2 | l) = P f 1 (Z k * ) = f -1 2 | f 2 (A l ) ( f2 ) | l (3.15)
Let us plug this result back into Equation 3.11:

-H f 2 • f 1 (Z k * ) | L = ∑ l∈L ∑ f2 ∈ f 2 (A l ) P(l) • P f 1 (Z k * ) = f -1 2 | f 2 (A l ) ( f2 ) | l • log P f 1 (Z k * ) = f -1 2 | f 2 (A l ) ( f2 ) | l (3.16)
Applying the following change of variable in the second sum:

f1 = f -1 2 | f 2 (A l ) ( f2 ): -H f 2 • f 1 (Z k * ) | L = ∑ l∈L ∑ f1 ∈A l P(l) • P f 1 (Z k * ) = f1 ) | l • log P f 1 (Z k * ) = f1 ) | l (3.17) Finally, since P f 1 (Z k * ) = f1 ) | l = 0 when f1 ∈ Im f 1 \ A l ,
one can artificially add some terms equal to 0 in the second sum:

-H f 2 • f 1 (Z k * ) | L = ∑ l∈L ∑ f1 ∈Im f 1 P(l) • P( f1 | l) • log P( f1 | l) = -H f 1 (Z k * ) | L (3.18)
Applying this result to Equation 3.10 gives:

S f ≤ -H f 1 (Z k * ) | L + min k̸ =k * H f 1 (Z k ) | L S f ≤ S f 1 (3.19)
which concludes the first step of the demonstration. Now the goal is to show that S f 1 ≤ S φ . Lemma 1 guarantees that there exists f 3 such that f 3 • f 1 = φ. Let us use this in Equation 3.9:

S f 1 = -H L | f 1 (Z k * ) + min k̸ =k * H L | f 1 (Z k ) ≤ -H L | f 1 (Z k * ) + min k̸ =k * H L | f 3 • f 1 φ (Z k ) (3.20)
since applying f 3 to the known variable can only increase the global entropy (see Lemma 3). Now using L = φ(Z k * ):

-H L | f 1 (Z k * ) ≤ 0 -H L | f 1 (Z k * ) ≤ -H φ(Z k * )|φ(Z k * ) = 0 (3.21)
Therefore:

S f 1 ≤ -H L | φ(Z k * ) + min k̸ =k * H L | φ(Z k ) S f 1 ≤ S φ (3.22)
Finally, using both part of the demonstration:

S f ≤ S f 1 ≤ S φ (3.23)
which ensures that φ is better than any other functions and so that φ ∈ F opt .

Remark 4. Demonstration of Theorem 4 would have worked exactly the same if one had first fixed a particular hypothesis k, and tried to maximize

S f ,k = I f (Z k * ), L -I f (Z k ), L .
Therefore, for each k, φ maximizes the distance between the score of k * and k which is an even stronger version of the theorem. One could not be sure that such a function would exist a priori, that is why F opt has not been defined with this criterion. However, this shows a posteriori that Theorem 4 is still valid even if one decides to redefine F opt , for example using the distance with the mean (instead of the maximum) of the wrong hypotheses scores.

Interpretation. This theorem tells that to conduct an optimal MIA, one has to transform the targeted variable Z k by applying the leakage model φ (or any bijection of φ) and use I(φ(Z k ), L) as a distinguisher. Note the multidimensional aspect of this theorem since both φ(Z k ) and L can live in high dimensional space. This is a key point in this chapter that will be discussed in detail in subsection 3.4.1 which bridges this theorem with newest multidimensional MI estimators in order to derive a new attack. Note that this theorem also implies that if the leakage model is itself bijective, MIA is not a valid strategy since the distinguishability score would be bounded by 0.

Selecting Leakage Model a Priori

In a real-life experiment, one might not perfectly know the leakage model φ but only an estimation φ. This is especially true when working in an unsupervised context.

This section provides a procedure to evaluate the correctness of φ, helping to choose from multiple guesses φ1 , . . . , φn . This test relies on the following observation:

Proposition 3. Let L = φ(Z k * ) + N, with N an independent random variable representing the noise. Then: φ ∈ arg max f [I f (Z k * ), L ]
Proof. On one hand:

I f (Z k * ), L = H(L) -H L | f (Z k * ) ≤ H(L) -H φ(Z k * ) + N | f (Z k * ), φ(Z k * ) ≤ H(L) -H(N) (3.24)
and on the other hand:

I φ(Z k * ), L = H(L) -H L | φ(Z k * ) = H(L) -H φ(Z k * ) + N | φ(Z k * ) = H(L) -H(N) (3.25) Then: I φ(Z k * ), L ≥ I f (Z k * ), L (3.26)
which concludes the proof.

The identity function obviously also maximizes: I f (Z k * ), L so combining this with Proposition 3:

I Z k * , L = I φ(Z k * ), L (3.27) or, I Z k * , L = max k [I φ(Z k ), L ] (3

Leakage Model Uncertainty and Noise

Let assume that the adversary has chosen a given estimation φ of φ. Let also assume that the ideal data L = φ(Z k * ), used in Theorem 4, are now noisy so that the acquired data takes the following form: L = φ(Z k * ) + N, with N an independent random variable. This section aims at complementing Theorem 4 by lower bounding the distinguishably score S φ that one would get in practice in such a context:

S φ = I φ(Z k * ), L -max k̸ =k * I φ(Z k ), L (3.29)
Our goal is to compare S φ with the optimal score S φ (from Theorem 4) that one would get with the perfect knowledge of φ and un-noised data such that:

S φ = I φ(Z k * ), L -max k̸ =k * I φ(Z k ), L (3.30)
Proposition 4. S φ is lower-bounded by the following inequality:

S φ ≥ S φ -H(N) -H φ(Z k * ) | φ(Z k * ) -max k̸ =k * H φ(Z k ) | φ(Z k ) (3.31)
Proof. Using the same argument as in Equation 3.9 one has:

S φ = -H φ(Z k * ) + N | φ(Z k * ) + min k̸ =k * H φ(Z k * ) + N | φ(Z k ) (3.32)
Since removing noise on the right term can only decrease entropy:

S φ ≥ -H φ(Z k * ) + N | φ(Z k * ) + min k̸ =k * H φ(Z k * ) | φ(Z k ) (3.33)
Now since H(A + B) ≤ H(A) + H(B) and using the independence of N:

S φ ≥ -H(N) -H φ(Z k * ) | φ(Z k * ) + min k̸ =k * H φ(Z k * ) | φ(Z k ) (3.
S φ ≥ -H(N) -H φ(Z k * ) | φ(Z k * ) + min k̸ =k * H φ(Z k * ) | φ(Z k ) -H φ(Z k ) | φ(Z k ) ≥ -H(N) -H φ(Z k * ) | φ(Z k * ) + min k̸ =k * H φ(Z k * ) | φ(Z k ) -max k̸ =k * H φ(Z k ) | φ(Z k ) (3.35)
Now let S φ appear in the equation:

min k̸ =k * H φ(Z k * ) | φ(Z k ) = min k̸ =k * H φ(Z k * ) | φ(Z k ) - 0 H φ(Z k * ) | φ(Z k * ) = S φ (3.36) So: S φ ≥ S φ -H(N) -H φ(Z k * ) | φ(Z k * ) -max k̸ =k * H φ(Z k ) | φ(Z k ) (3.37)
which concludes the proof.

This proposition describes the impact of the noise and leakage model approximation in a quantitative way. Its qualitative interpretation is fairly intuitive. It clearly shows that one has two strategies to get closer to the optimal score: reducing the noise entropy or improving his guess on φ. When H(N) tends towards 0 and φ gets closer to φ , S φ tends towards the optimal score S φ . It also captures the fact that bijective errors do not impact the outcome of the attack since if there exists a bijection between φ(Z k ) and φ(Z k ), both terms

H φ(Z k * ) | φ(Z k * ) and max k̸ =k * [H φ(Z k ) | φ(Z k )
] would be equal to 0.

MIA Against Masked Implementations

Masking is one of the most widely used countermeasures to protect implementations of block ciphers against side-channel analysis [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF]. The idea is to split each sensitive intermediate value Z, into d shares, following the relation:

Z 1 = Z * Z 2 * • • • * Z d (3.38)
for a group operation * .

MIA, a Natural Choice Against Masking

Although higher-order CPA attacks lead to successful key recoveries, they are not optimal from an information-theoretic point of view. Indeed, by the data processing inequality [START_REF] Beaudry | An intuitive proof of the data processing inequality[END_REF], the application of the combining function leads to an information loss. Opposed to Pearson's correlation, mutual information can deal with dependencies of multidimensional variables. Therefore, no combining function is required which makes MIA a very natural strategy against masked implementations. An extension of MIA in the context of masking has been proposed in [START_REF] Prouff | Theoretical and Practical Aspects of Mutual Information Based Side Channel Analysis[END_REF] and [START_REF] Batina | Mutual Information Analysis: A Comprehensive Study[END_REF].

The idea is very similar to the non-masked case. Concepts of MIA versions 1 and 2 still apply and one can use I( f (Z k ), L) as a distinguisher.

About the Partition Function in the Presence of Masking

Using I( f (Z k ), L) as distinguisher still raises the question of the optimal f function. Theorem 4 cannot be applied straightforwardly since, for masked implementation, the leakage cannot be expressed as a deterministic function φ(Z k * ) modulo some noise. Instead, with Z i representing the shares, one now has:

L = ∑ i φ i (Z i ) (3.39)
for some functions φ i : Z → R n . Note that, as for the unmasked case, a noisefree version of the leakage is first considered to simplify the analysis. Noise will be added in subsection 3.3.3. Most of the time, the φ i supports can be supposed disjoint (i.e. leakages of the shares do not overlap). In that case, the leakage vector could be summarized as:

L = [φ 1 (Z 1 ), . . . , φ d (Z d )] (3.40)
with φ i taking its values in a subspace of R n . Even with this simplification, we could not solve analytically the problem of finding an optimal partition function, or, in other words, a function f ∈ F opt as defined in Equation 3.7. However, we still give some useful insights in the common case of Boolean masking on a device leaking the Hamming weight (or Hamming distance with a known value) of the shares.

For this specific case, [START_REF] Batina | Mutual Information Analysis: A Comprehensive Study[END_REF] HW(Z k * ) is not directly related to any physical leakage. More generally, there is no proof that if all shares leak with the same leakage model φ, taking f = φ is the optimal (or even a good) option. However, in the specific case of a Hamming weight leakage model, [START_REF] Prouff | Statistical Analysis of Second Order Differential Power Analysis[END_REF] has shown that their exists a linear correlation between HW(Z k * ) and the covariance: cov HW(Z k * ⊕ M), HW(M) which is a clue that there exists a non-negligible mutual information between HW(Z k * ) and L. However, we go further in this chapter by showing in Theorem 5 that there is actually no loss of information when applying the Hamming weight function to the Z k * variable. This result can then be used to give a formal justification for using f = HW, as done hereafter.

Let us introduce F Le f t as the left part of Equation 3.7:

F Le f t = arg max f : Z →R n I f (Z k * ), L (3.42)
This set does not consider the wrong hypotheses. Therefore it is not hard to find a function f ∈ F Le f t : the identity or any bijective function works. The problem is that with a bijective map, I f (Z k * ), L = I f (Z k ), L for any k. However, a noninjective function f such that f ∈ F Le f t would naturally decrease I f (Z k ), L and create some distinguishability. Such a function is not a priori likely to exist. But the following theorem shows that, while being highly non-injective, HW ∈ F Le f t .

Theorem 5. Let L represent the leakage of a masked variable Z k * with a mask M. Let both shares follow any bijection b 1 and b 2 of a Hamming weight leakage model so that:

L = b 1 HW(Z k * ⊕ M) , b 2 HW(M) (3.43)
Then, HW ∈ F Le f t or in other words:

I HW(Z k * ), L = I Z k * , L .
The following proof is generalized to higher-order in section A.4, (see subsection 3.5.4 for an empirical validation), but for simplicity, only a first-order masking is considered here.

Proof. Since bijective transformations do not impact mutual information, one can consider without loss of generality that:

L = HW(Z k * ⊕ M),
I f (Z k * ), L = ∑ f ∈ f (Z ) ∑ l∈L P( f , l) • log P( f , l) P( f ) • P(l) (3.45)
One can split the first sum by summing on z instead of f :

I f (Z k * ), L = ∑ z∈Z ∑ l∈L P(z, l) • log P(l | f (z)) P(l) = ∑ z∈Z ∑ l∈L P(z) • P(l | z) • log P(l | f (z)) P(l) (3.46)
Since the identity function is bijective and maximizes this quantity, it would be enough to show that P(l | HW(z)) = P(l | z) for any given z and a given l = [HW(z ⊕ m), HW(m)] for a fixed m. Let us start by the latter term:

P(l | z) = P(HW(m)) • P(HW(z ⊕ m) | z, HW(m)) (3.47)
To compute the right term one can evaluate the cardinal of the set M of all the masks m ′ satisfying the following conditions:

1) HW(m ′ ) = HW(m) 2) HW(z ⊕ m ′ ) = HW(z ⊕ m)
and divide by the number of byte with a Hamming Weight of HW(m) which is ( 8 HW(m) ).

To evaluate this cardinal, we first show an invariance property. For any m ′ ∈ M, let n m ′ denotes the number of bits set to 1 in m ′ such that there is also a bit set to 1 at the same position (0 to 7) in z. Then:

HW(z ⊕ m ′ ) = HW(m ′ ) + HW(z) -2 • n m ′ ⇐⇒ n m ′ = HW(m ′ ) + HW(z) -HW(z ⊕ m ′ ) 2 (3.48)
Now since m ′ satisfies the above two conditions:

n m ′ = HW(m) + HW(z) -HW(z ⊕ m) 2 (3.49)
which does not depend on m ′ anymore. As n m ′ has to be a positive integer, the above equation shows that:

HW(m) + HW(z) -HW(z ⊕ m) / ∈ 2N =⇒ M = ∅ (3.50) Thus, I HW(Z k * ), L = I Z k * , L (3.58)
which ensures that HW ∈ F le f t and concludes the proof.

Interpretation. This theorem shows that when the shares leak in Hamming weight, it is sound to use f = HW in practice because it creates some distinguishability by decreasing the information only for the wrong hypotheses. Since the Hamming distance with a computable value can be rewritten as a Hamming weight, it also works in that case. However, Theorem 5 is not generalizable to any leakage model φ (for example on 3 bits words, φ = 2b 1 + b 2 + b 3 gives a counter-example).

Knowing if there exists a generic strategy against masking (depending on φ but working for any φ) or if one will always be condemned to work on a case-by-case basis is an interesting question and may be handled in future works.

Remark 5. Note that since

I Z k * , L = I HW(Z k * ), L = max k [I HW(Z k ), L ],
the procedure described in subsection 3.2.6 can also be applied on a masked implementation, to test the validity of the Hamming weight leakage model hypothesis. If the Hamming weight is too far from the true model, a practical alternative is to use only specific bits of the unmasked variable as partition function. An example of this is given in section 3.6.

Considering the distinguishability score:

S f = I f (Z k * ), L -max k̸ =k * I f (Z k ), L (3.59)
HW has not been shown to be optimal. However, a partial result can be given introducing the concept of "wider" function.

Definition 2. A function f is said wider than g if there exists another function h such that:

h • f = g.
Corollary 1. Let L be defined as in Equation 3.43. Then, for any function h wider than HW, S HW ≥ S¯h.

Proof. The proof is given in Appendix A.

Even though we do not conjecture so, a function with a better distinguishability than the HW may exist. But a straightforward consequence of Theorem 5, given by Corollary 1, is that HW has a better distinguishability score than any other wider function.

Noise and Multidimensionality

The advantage of MINE is to be able to exploit the information contained in multiple samples at the same time. In a Hamming weight leakage scenario, the Hamming Chapter 3. Revisiting Mutual Information Analysis: Multidimensionality, Neural Estimation and Optimality Proofs weight of a variable is probably not going to leak perfectly on a single sample. Instead, multiple samples may leak a noisy version of it. To ensure that it is sound to use MINE and its multidimensional capabilities to mount an attack in the case of masking, one would need a multidimensional version of Theorem 5. This is exactly the purpose of Corollary 2, in which the noise is directly included.

In the context of masking the actual useful part of the leakage could be expressed as:

L = b 1 HW(Z k * ⊕ M) + N 1 , . . . , b m 1 HW(Z k * ⊕ M) + N m 1 , b ′ 1 HW(M) + N ′ 1 , . . . , b ′ m 2 HW(M) + N ′ m 2 (3.60)
with b i and b ′ j being bijective maps, and N i and N ′ j being discrete noise variables independent of the shares. The following corollary shows that Theorem 5 is still valid in that case.

Corollary 2. Let L be defined as in Equation 3.60. Then, one still has HW ∈ F Le f t as defined in Equation 3.42.

Proof. As for Theorem 5, one can drop, without loss of generality, the bijections in L as they do not affect the MI. Let N be the noise vector [N 1 , . . . , N m 1 , N1 , . . . , Nm 2 ] and L the noise-free version of the leakage so that L = L + N. As for Theorem 5, it is enough to show that P(l | HW(z)) = P(l | z) for any given l and z. Decomposing on all the possible values of the noise one has:

P(l | z) = ∑ n∈N P(n) • P(L = l | z and n) = ∑ n∈N P(n) • P( L = l -n | z) (3.61)
Since L is noise free, it consists of the repetition of the same two variables: HW(Z k * ⊕ M) (m 1 times) and HW(M) (m 2 times). So for the probability P( L = ln | z) to be non-zero, the vector ln should be constant on its first m 1 coordinates, and constant on its m 2 last one. Let N c be the subset of N verifying the precedent property. If n / ∈ N c , then:

P( L = l -n | z) = P( L = l -n | HW(z)) = 0 (3.62) Else, if n ∈ N c , then, with a n = (l -n)[1], b n = (l -n)[m 1 + m 2 ] and L = [HW(Z k * ⊕ M)
, HW(M)]:

P( L = l -n | z) = P( L = [a n , b n ] | z) (3.63)
So Equation 3.61 can be rewritten as: This corollary shows that it is sound to use I(HW(Z k ), L) as distinguisher even when considering a noisy multidimensional leakage vector. Theorem 5 still applies and MINE may benefit from the different leakage sources resulting in an attack (presented in the next section) exploiting a bigger amount of the available information.

P(l | z) = ∑ n∈N c P(n) • P( L = [a n , b n ] | z) (3.64)

Neural Estimated Mutual Information Analysis (NEMIA)

This section aims at formally describing the new attack proposed in this chapter.

Note that throughout this work, a tool able to compute I(Z, L) with high dimensional variables has been assumed to exist. This research has been driven by recent progress regarding neural estimation techniques. However, this work is not absolutely related to MINE. It would stay sound with any MI estimator able to work in high dimension. In particular, any progress in the field, which is likely to happen since it is a very active domain, would instantly impact the attack efficiency.

Multidimensional Paradigm

MINE is by essence a tool that estimates MI in a multidimensional way, enabling to compute the MI between f (Z k ) and full (or at least large part of) traces. This was not possible with classical MI estimators which do not scale with high dimensional variables. Until now, MIA was only performed with the following distinguisher:

D old (k) = max i I( f (Z k ), L[i]) (3.66)
where L[i] represents the i-th sample of the trace. This way, trace dimension is kept low, allowing methods such as the histogram or the kernel density estimation [START_REF] Prouff | Theoretical and Practical Aspects of Mutual Information Based Side Channel Analysis[END_REF] to produce reliable results. However, this comes at the cost of sacrificing some, and maybe a large part, of the available information. MINE allows to directly use:

D new (k) = I( f (Z k ), L) (3.67)
as a distinguisher. This comes with two main advantages:

• Intermediate variables often leak at multiple instants in the trace. MINE allows to exploit all these leakage sources at the same time.

Chapter 3. Revisiting Mutual Information Analysis: Multidimensionality, Neural Estimation and Optimality Proofs

• Other intermediate variables, statistically dependent from the first one, can also leak information. For example, there could be some useful information about an AES key, before and after the application of the first S-box. In this context, MINE could exploit leakage from both intermediate variables at the same time, without any assumption related to the kind of link between these variables.

Theorem 4 states that the optimal distinguisher is I(φ(Z k ), L) with φ being the leakage model. It is important to note that φ(Z k ) itself can be multidimensional. Therefore, an optimal MI attack should exploit this multidimensionality of the leakage model to increase the distinguishability of the correct hypothesis. However, it is frequent that multiple samples leak with the same underlying model: for example, a noisy version of the Hamming weight of Sbox[k * ⊕ P] can leak multiple times in the trace. In such a context, the deterministic parts of the leakage of all these samples are all bijectively related. As adding bijection of the same variables multiple times would not change the MI, one can keep only one version of each different subleakage model. For example, if the target leaks (maybe multiple times) the Hamming weight of the first S-box of an AES and the Hamming distance between the S-box and k ⊕ P, Z k could be defined as k ⊕ P and one could replace φ(Z k ) by the two-dimensional vector:

HW Sbox[Z k ] , HW Sbox[Z k ] ⊕ Z k (3.68)
Remark 6. In practice, one may deliberately drop some intermediates variables for not being enough discriminating for wrong key candidates making them less tolerant regarding errors in the estimation of φ. For example, it is theoretically possible to use leakage on a xor: HW(k ⊕ P) (assuming a Hamming weight a priori) but it is preferable to use intermediate variables where each bit depends on multiple bits of k such as the output of an S-box. Indeed, these variables are more discriminating since single bit errors on k are diffused to the whole variable which prevents from rewarding wrong hypotheses with several correct bits.

Scalability with Masking Order. In the context of masking, another advantage of multidimensionality emerges. In a classical d-order attack one often does not know the exact leakage time of each share, and therefore, has to compute the value of the distinguisher for each possible tuple (i 1 , . . . , i d ) and select the maximum. In the case of MIA the old distinguisher takes the following form:

D old (k) = max i 1 ,...,i d {I( f (Z k ), L[i 1 , . . . , i d ])} (3.69)
For long traces, this can become a huge constraint since the total number of tuples grows exponentially with the masking order. Our version of the MIA which uses I( f (Z k ), L) as distinguisher, does not suffer from this since it does not require any kind of recombination between time samples. Note that it does not mean that 3.5. Simulation Experiments 59 masking is useless: it still decreases exponentially the information contains in sidechannel traces [START_REF] Prouff | Masking against Side-Channel Attacks: A Formal Security Proof[END_REF] and an attack may require exponentially more traces to succeed. However, for a fixed number of traces, the computational effort required to mount a NEMIA does not scale exponentially with the order of the attack.

Attack Description

A step-by-step description of the NEMIA is given hereafter. It takes as input a set of traces and outputs a ranking of the key hypotheses.

1 It appears that, in some cases, it is efficient to keep a restrictive number of bits of the unmasked variable as partition function, for example in a situation where some bits of the shares leak much more information than the others (an example of this is given in section 3.6).

Simulation Experiments

In order to gain confidence in the mathematical results presented in this chapter, as well as to gain intuition about their implications, this section presents experiments on synthetic data. These experiments all use the same architecture of MINE.

It should be seen as a proof of concept with almost no hyper-parameters tuning and without considering recent optimizations nor improvements in the technique (non-exhaustively: [CL20; Lin+19; Cha+19]). A study focused on deep learning optimizations would be interesting but is out of the scope of this thesis.

Chapter 3. Revisiting Mutual Information Analysis: Multidimensionality, Neural Estimation and Optimality Proofs

About the Network's Architecture

The network's input layer consists of a concatenation of both Z and L variables.

We have shown in Chapter 2 that the representation of Z is important and that one should use the One-Hot Encoding (OHE) or a binary encoding of Z (unless otherwise specified we used the OHE in this chapter). The output layer is a single neuron.

Other layers are not specified by the method and should be adapted to the underlying problem (e.g. convolutional layers to counter jitter or traces misalignment).

For our experiments, we used a Convolutional Neural Network (CNN) where a batch normalization layer is added after the first layer and dropout layers are inserted after each hidden layer in order to mitigate overfitting. The activation function is set to the Exponential Linear Unit (ELU) and the batch size to 1000. The precise architecture is depicted in Appendix B. The validation dataset represents 20 percent of the full dataset.

On the Importance of the a Priori

The main message of Theorem 4 is that, to maximize the distinguishability of the correct hypothesis, one should use the leakage model φ to create the hypothesis vectors H k . In a classical side-channel scenario, with no other specific information, one may often guess a Hamming weight leakage of the intermediate variables. This is justified by electronic arguments. However, it has been shown that bits may have different leakage behaviours, such as leakage weighting or even sign inversions [START_REF] Cristiani | A Bit-Level Approach to Side Channel Based Disassembling[END_REF].

To illustrate Theorem 4, 10k synthetic traces leaking a slightly modified version φ 0 of the Hamming weight have been generated. They consist of a single sample leaking the Hamming weight of Z k * = Sbox(k * ⊕ P) but with a flipped sign for bit 0 so that:

φ 0 (z) = -z 0 + 7 ∑ i=1 z i (3.70)
with z i representing the i-th bit of z. Some Gaussian noise has been added to the traces so that L = φ 0 (Z) + N (0, 1). Figure 3.1 shows the results of a NEMIA with k * = 0, both with HW and φ 0 as partition function. As predicted by Theorem 4, the distinguishability score:

S f = I f (Z k * ), L -max k̸ =k * I f (Z k ), L (3.71)
is higher for f = φ 0 than for f = HW. Obviously, an attacker may not know φ 0 and an attack with the Hamming weight still succeeds in that case. However, this shows that, if by any means, an adversary knows the particularity of bit 0 of such a target, he can perform more efficient attacks.

Semi-Supervised Attacks. This opens the idea of semi-supervised attacks. One of the main problems of profiling attacks is the portability [START_REF] Elaabid | Portability of templates[END_REF]. Indeed, during the characterization phase, the adversary learns a perfect representation of the

f = 0 f = HW FIGURE 3.1: I f (Z k ), L in terms of k, with k * = 0
leakage model which may overfit on the particular target which is profiled. It has been shown that portability to other targets is not trivial. Therefore NEMIA could be turned into a semi-supervised attack where the purpose of the characterization phase is only to learn general leakage characteristics, such as the sign or weighting of each bit, and use them as an improved a priori for a NEMIA. Since NEMIA is agnostic towards bijective errors in the leakage model estimation, it has a better chance of being portable on many other targets similar to the one used for profiling.

The Potential of Multidimensionality

One of the main advantages of NEMIA is its potential to exploit at the same time, multiple leakage sources. It is possible that multiple intermediate variables leak information on the key and each particular variable may leak multiple times in the traces. This section aims at showing how NEMIA could exploit all these leakage sources as well as to compare it with other state of the art attacks.

Traces Generation

To this aim, a dataset of 100k synthetic traces have again been generated. These traces represent the leakage of an AES that both leaks A k * = HW(Sbox[k * ⊕ P]) and B k * = HW(Sbox[k * ⊕ P] ⊕ (k * ⊕ P)). One could imagine that the bus leaks the Hamming weight of the S-box data and that the update of the state register leaks the Hamming distance with its precedent value (e.g. [START_REF] Moradi | Information Leakage of Flip-Flops in DPA-Resistant Logic Styles[END_REF]).

One of the strength of using deep learning in an unsupervised attack is the absence of need for preprocessing techniques. To highlight this fact we also added 90 % of uninformative samples as well as some misalignment in the traces following the shifting deformation procedure introduced in [CDP17] which simulates a random delay effect of maximal amplitude T by shifting each trace by a random number uniformally drawn between 0 and T. The procedure for the trace generation is depicted in algorithm 2. pothesis, and uses a metric (we used the accuracy as suggested in [START_REF] Timon | Non-Profiled Deep Learning-based Side-Channel attacks with Sensitivity Analysis[END_REF]) as a distinguisher. Note that a partition function also has to be applied to the intermediate variables but its optimal choice has not been discussed in [START_REF] Timon | Non-Profiled Deep Learning-based Side-Channel attacks with Sensitivity Analysis[END_REF].

We use the Hamming weight function in this experiment. 7. The same deep learning attack but in a non-limited setup regarding the number of traces during profiling. In practice we have trained the network using another dataset of 100k traces generated with algorithm 2. This attack is denoted DL-supervised ∞ . In this case, the application of the partition function is only beneficial and does not induce information loss since the true leakage model is known.

To the best of our knowledge, classical MI-based attacks always performed worse than CPA in the literature, when considering the Hamming weight model, which is again confirmed by our results. This experiment shows that in a low-information scenario (noisy traces with jitter), NEMIA may be worth considering among the other unsupervised attacks.

Empirical Validation of Theorem 5

Theorem 5 may seem very counterintuitive since it basically states that: when shares of a Boolean masking leak in a Hamming weight model, one has: does not alter information. The HW function is even doing a little better which can be explained with practical machine learning considerations. Indeed, the information being constant, it is easier for the network to learn with a 9-classes variable than with a 256 classes variable (note that in this experiment, id(Z k * ) has been encoded in binary rather than in OHE, because it produced slightly better results). Also, since overfitting was not really a problem in this experiment, the dropout parameter has been set to p = 0.1.

I HW(Z k * ), L = I Z k * , L (
Figure 3.3b shows the result of the same experiment performed on a secondorder masking, with three shares and 10 leakage samples for each. Noise has been a bit decreased (σ = 0.5 instead of 1) to keep comparable level of information. This result confirms that Theorem 5 is generalizable to higher-order masking, as shown in section A.4, and that MINE is able to extract information even with a second-order masking.

A practical Case: Attack on ASCAD

This section provides a real case experiment on the public dataset of ASCAD [START_REF] Benadjila | Study of deep learning techniques for side-channel analysis and introduction to ASCAD database[END_REF].

We In a real attack scenario, an adversary mounting a NEMIA could obviously try to use every single bit of the unmasked variable as partition function. But in order to gain some intuition, and since the masks values are given in the database, we first performed a linear regression on both shares, assuming bits leak independently so that the actual leakage of share s is: This indicates that the LSB may be a good partition function since it is highly noninjective and still keep a decent amount of information for the correct hypothesis. We also tried with other bits but the information, while being non-zero, was significantly lower. Even though attacks with the Hamming weight were successful, we decided to use the LSB as partition function for the rest of our analysis. The attacks presented in this section uses the whole 700 samples as input. We compared the following attacks:

∑ 7 i=0 α i s i + β.
1. A classical second-order CPA [START_REF] Prouff | Statistical Analysis of Second Order Differential Power Analysis[END_REF] with a Hamming weight model. The architechture of the network is depicted in Appendix B.

Results.

In order to evaluate the potential of NEMIA to exploit leakage even in very low information context, the dataset has been artificially degraded adding Gaussian noise N (0, σ 2 ) to each sample. All the attacks have been performed with σ going from 0 to 20, using the whole 50k traces. For each level of noise, the attacks have been repeated 10 times (with different random sampling of the noise) in order to compute the average rank of the correct hypothesis. Results are presented in

Conclusion and Perspectives

This chapter first proposes a clarification of the state of the art around the MIA.

It provides rigorous proofs

Introduction

Context

Side-Channel Analysis (SCA) is mainly divided into two categories: supervised and unsupervised SCA and their utilization depends on the considered threat model. In the first one, the adversary is supposed to be able to conduct a profiling step of the target, most likely on a clone device, in which she learns the leakage model of the intermediate variables and then adopts a maximum likelihood approach to recover the secret key. This includes strategies such as Gaussian template attacks [START_REF] Chari | Template attacks[END_REF] or deep learning profiled attacks [START_REF] Masure | A Comprehensive Study of Deep Learning for Side-Channel Analysis[END_REF]. If the model is perfectly learned during the characterization phase, these attacks are known to be optimal from an information theory point of view.

However, being able to conduct a sound profiling step is not always possible and refers to a strong threat model for the adversary. Indeed, the latter one may not be able to obtain a clone with full control on the device and even in cases where she could, template portability issues [START_REF] Elaabid | Portability of templates[END_REF] may still stand in the way. In this case, the adversary can "replace" the profiling of the target by its a priori on the leakage model to mount what is called unsupervised SCA. Such an a priori usually comes from physical assumptions and is central to unsupervised SCA. Indeed, as shown in [START_REF] Whitnall | The Myth of Generic DPA. . . and the Magic of Learning[END_REF], there does not exist a generic unsupervised strategy that would work without requiring such an a priori. However, a priori is a very vague term that only captures the fact that the adversary has to have some knowledge about the leakage model for the attack to work. This knowledge can take many different forms.

In a first type of unsupervised SCA, known under the stochastic attacks, the a priori takes the form of a parametric model. For example, the well-known Linear Regression Analysis (LRA) [START_REF] Doget | Univariate side channel attacks and leakage modeling[END_REF] falls into this category. The advantage of such attacks is their ability to work with weak a priori such as the only assumption that the bits of the sensitive variable leak independently. This makes them robust and applicable in a wide range of cases. • The time complexity of the attack which requires as many network trainings as there are key hypotheses (which means 256 trainings when attacking a key byte). If the adversary wants to test multiple a priori, this issue is then amplified which leads to complex or even unpractical attacks for highly noisy target requiring a lot of traces and therefore long trainings.

Contributions

This chapter presents a new unsupervised strategy, denoted the EVIL Machine Attack (EMA), which allows to use a flexible a priori (as in the stochastic attack) while still being able to exploit the power of deep learning. We show that it only requires one network training whatever the number of key hypotheses. Therefore, EMA overcomes the two main issues of unsupervised deep learning attacks.

The architecture of the EVIL machine is presented in section 4.2. It is a Generative Adversarial Network (GAN) like structure whose goal is to derive the leakage model of the target under a key assumption. The actual attack and how the number of network training is reduced to only one is described in section 4.3. Results on synthetic and real traces are also presented in this section. Eventually, section 4.4 gives an introduction to a higher-order version of the attack, when dealing with masked implementation.

Learning a Leakage Model Representation

As shown in chapter 3, one of the main difficulties of the model-based SCA is to have a sound representation of the leakage model to use it as a partition function.

The original idea of this work is to transfer the task of finding such a representation to a neural network without having to use any a priori. This representation is conditioned by a key assumption otherwise it would provide an a priori free strategy contradicting [START_REF] Whitnall | The Myth of Generic DPA. . . and the Magic of Learning[END_REF]. So to ease the reading of the chapter, the correct key is first assumed to be known in this section. However, section 4.3 shows how such a tool can be turned into an actual unsupervised attack.

Notations and SCA framework

We recall here the SCA notations used in this chapter. In order to gain information on the secret key the adversary targets the manipulation of a sensitive variable Z ∈ Z = F n 2 , for a given n ∈ N. This variable is supposed to functionally depends on a public variable X ∈ X = F m 2 , for a given m ∈ N, and a secret key k * ∈ K = F m depending on the underlying cryptographic algorithm. If an hypothesis k is made on the secret key, one can define Z k = g(X, k) such that Z = Z k * . For a fixed k we denote by g k the g(•, k) function. All the g k are supposed to be bijective in this chapter of reciprocal g -1 k (for example, in the classical first round AES case one would have

g k (X) = SBOX[X ⊕ k] of reciprocal g -1 k (Z) = SBOX -1 [Z ⊕ k].
Eventually, traces L leaking information about Z through a leakage model φ can be expressed as L = φ(Z) + E where E represent an independent noise variable.

Building the Network's Architecture

Classical Mutual Information (MI) attacks rank the key hypotheses with the following distinguisher:

D(k) = I f (Z k ), L (4.1)
where I(X, Y) stands for the MI between X and Y and f is the partition function transforming the guessed intermediate variable. The starting point of the reasoning behind the EVIL machine is the Theorem 4 (the main theoretical result of the Chapter 3) which states that the leakage model φ belong to the set of optimal partition functions as recalled hereafter:

Theorem 1. (Leakage model optimality)

φ ∈ F opt = arg max f : Z →R p I f (Z k * ), L -max k̸ =k * I f (Z k ), L (4.2)
Note that traces can be multidimensional. Therefore the output domain of φ is R p where p can be any positive integer.

Our goal is to derive from this theorem a neural network architecture able to produce an encoding function E : Z → R of the leakage model φ. The main challenge is to define the network's objective function. Optimally, E should carry the same information as φ and therefore be a bijection of φ encoding it into one dimension 1 .

Combined with Equation 4.2, this property could be derived as an objective for E.

Indeed, since bijective transformations do not affect the MI:

E ∈ B(φ) =⇒ E ∈ F opt (4.3)
where B(φ) stands for the set of all bijections of φ. The reciprocal of Equation 4.3 is not formally proven even though we conjecture so. Thus, we make the hypothesis here that a function belonging to F opt would give a valuable representation of the leakage model and try to find such a function thanks to deep learning tools. A naive 1 One could design an encoding function encoding the leakage model in more than one dimension. However, preliminary analyses did not show any real value of increasing the output dimension.

In addition, since one-dimensional data are easier to interpret and better suited for the attack phase presented in section 4.3, we only focus on functions with a one-dimensional output in this work. The first problem is the presence of the max function which is not differentiable.

This problem can be solved using Remark 4 which states that the theorem is still

valid if one fixes k ∈ K \ k * . So ∀ k ∈ K \ k * : φ ∈ F opt = arg max f : Z →R p I f (Z k * ), L -I f (Z¯k), L (4.4)
The second problem is the computation of the MI terms which are known to be hard, especially for high-dimensional traces. However, we showed in Chapter 2 that these MI terms could be estimated using deep learning tool and more precisely a Mutual Information Neural Estimator (MINE) [START_REF] Ishmael | Mutual Information Neural Estimation[END_REF]. Therefore such a tools could be incorporated into the EVIL machine architecture in order to compute the objective function of the encoder E. In this chapter it is enough to see MINE as a black-box deep learning method that defines a network, taking as input the traces and label variable, with an objective function converging toward the MI between these two variables. Further details on the theory and implementation in an SCA context can be found in Chapter 2.

Architecture. The architecture of the EVIL Machine is depicted in Figure 4.1. It is composed of three neural networks interacting with each other:

• An encoder E which takes as input a label (for instance, the value of Z k * or Z¯k)

and outputs a value in R (its final layer is a single neuron).

• MINE A which objective function produces an estimation Î (E(Z k * ), L) of I(E(Z k * ), L).

• MINE B which objective function produces an estimation Î (E(Z¯k), L) of I(E(Z¯k), L), where k is fixed to any value in K \ k * .

The encoder E is applied on both Z k * and Z¯k where k can be fixed to any value except k * . Then E(Z k * ) and E(Z¯k) are both concatenated with the traces (each trace is con- catenated with its associated encoded label) and provided to the MINE networks

Simulation Experiments

We have implemented the generic architecture described in the previous section us-

Hamming Weight Leakage Model

For the first experiment, we have generated the most basic side-channel traces composed of one sample leaking a noised version of the Hamming weight of Z k * = SBOX[P ⊕ k * ], with P and k * respectively representing a plaintext and a key byte. The leakage traces can then be expressed as:

L = HW(Z k * ) + N (0, 1) (4.5)
with N (0, 1) representing the standard normal distribution. The evolution of the output of E is depicted in

Linear Leakage Model

To assess the EVIL machine capabilities on a more generic leakage model, we repeated the previous experiment emulating a linear leakage with respect to the bits of the sensitive variable. In this case, the leakage traces can then be expressed as:

L = φ 0 (Z k * ) + N (0, 1) (4.6)
with φ 0 = ∑ 8 1 α i b i where b i represents the projection on the i th bit and α i a random coefficient uniformly drawn from [-1, 1]. Results are depicted in Figure 4.3. Each point is colored according to the value of φ 0 (z). The encoder is again converging towards a meaningful representation of the leakage model. Indeed, the figure looks like a uniform rainbow which highlights the fact that the relation between E(Z k * ) and φ 0 (Z k * ) is quasi-linear.

Multidimensional Leakage Model

One of the main advantages of the EVIL machine is its ability to take large parts of the trace as input and to compress int one neuron multiple leakage sources. To highlight this multidimensional capability we design a simple example where the leakage is split on two samples. Each sample leaks respectively the Hamming weight of Z + k * and Z - k * which represent the four most and least significant bits of Z k * . The leakage traces can then be expressed as:

L = [HW(Z + k * ) + N (0, 1), HW(Z - k * ) + N (0, 1)] (4.7)
Results are presented in Figure 4.4. The two plots are the same but colored differently. Figure 4.4a is colored according to HW(Z + k * ) while Figure 4.4b is colored according to HW(Z - k * ). It appears that the encoder uses the macro structure (the five big branches) to encode the information on Z + k * and the micro structure (the position in the branch) to encode the information on Z - k * . Therefore, the encoder successfully learned a compressed version of a multidimensional leakage model. In this case it could almost be expressed as linear combination of both leakage sources:

E(z) ≈ αHW(Z + k * ) + βHW(Z - k * ), for some α, β ∈ R.

Non-Linear Leakage Model

Finally, to show that the EVIL machine is not limited to linear leakage models, we present an experiment with a non-linear model φ NL . We used a linear leakage model φ 0 on the 7 MSBs of Z k * where the sign of the leakage is determined by the value of the LSB: φ NL = (-1) b 8 * φ 0 with φ 0 = ∑ 7 1 α i b i , where α i are random coefficient uniformly drawn from [0, 1]. The leakage traces can then be expressed as:

L = φ NL (Z k * ) + N (0, 1) (4.8)
Results are depicted in Figure 4.5. Each point is colored according to the value of φ 0 (z). In this case, it appears that the encoder learned a representation of the leakage model φ NL composed of two symmetric branches, each one encoding the linear part of the model φ 0 but in the opposite direction due to the sign inversion related to the value of the LSB of Z k * . This confirms that the EVIL machine can still learn sound representations of the leakage even if the latter is non-linear.

This section has shown that the EVIL machine could learn a sound representation of the leakage model. Such a tool can be useful in itself, for example, for designers to gain intuition on the leakage of their devices. It does require the knowledge of the key to work, however, it is possible to use key guesses as explained in the next section which aims at turning this tool into an unsupervised attack.

The EVIL Machine Attack

The EVIL machine presented in the previous section produces a representation of the leakage model assuming that the correct key is known. However, making hypotheses on the key allows to convert this tool into a key recovery strategy, denoted the EVIL Machine Attack (EMA). For any k ∈ K one can run an iteration of the EVIL machine producing a representation E k of the leakage model φ k representing the leakage model under the assumption that the correct key is k. All of these models φ k mathematically exist. They are functions representing a hypothetical leakage model that would be the real one if the processed variable was the wrongly guessed Z k = g(X, k) instead of Z k * . Thus, they satisfy the following property:

φ k (Z k ) = φ k * (Z k * ) (4.9)
They are therefore, very likely, complicated functions (with a high algebraic degree) due to cryptographic properties of the g k functions2 linking Z k and Z k * together by the relation:

Z k = g k (g -1 k * (Z k * )).
The main idea of EMA is then to choose among all the possible representations of the leakage model E k , the simplest one, implementing a form of Occam's razor principle. This choosing step involves physical knowledge on what a leakage model should look like and this is where the adversary's a priori knowledge comes into play.

To illustrate the point, we repeated the Hamming weight leakage model experiment of section 4.2 but with a wrong key guess k 0 . The evolution of E k 0 and E k * , the one obtained with the correct key guess, are plotted in Figure 4.6 in order to compare them. One can visually note the difference: E k * is related to the Hamming weight function while E¯k seems unstructured and close to a random output. Such property can be used to define a distinguisher between key guesses as explained in subsection 4.3.2.

One Training to Rule them All

Obtaining all the E k can be done by running |K| times the EVIL machine with different key assumptions. However, this may be very long, especially for low-information scenarios requiring a lot of traces which are precisely the use cases considered in this work. This section shows that the adversary can in fact make a first guess k 0 , which may be wrong, compute E k 0 , and mathematically derive E k for any k ∈ K from E k 0 . This method allows running only once the EVIL machine to rule all cases.

As explained in the previous section E k 0 gives a representation of φ k 0 , the leakage model if the correct key was k 0 . For any k ∈ K Equation 4.9 gives:

φ k (Z k ) = φ k * (Z k * ) (4.10)
which is also true for k 0 :

φ k 0 (Z k 0 ) = φ k * (Z k * ) (4.11)
So one can deduce from Equations 4.10 and 4.11 that:

φ k (Z k ) = φ k 0 (Z k 0 ) φ k g k 0 (g -1 k (Z k )) = φ k 0 g k 0 (g -1 k (Z k 0 )) φ k (Z k 0 ) = φ k 0 g k 0 (g -1 k (Z k 0 )) (4.12)
which completely define φ k from φ k 0 . Since E k stands for a representation of φ k , one has by analogy:

E k (Z k 0 ) = E k 0 g k 0 (g -1 k (Z k 0 )) (4.13)
And since Z k 0 and Z live in the same set Z, one can simplify the previous equation:

E k (Z) = E k 0 g k 0 (g -1 k (Z)) (4.14)
So one can quickly and easily deduce any E k including E k * from the only knowledge of E k 0 with k 0 arbitrary chosen by the adversary. This reduces by a factor |K| (when targeting a key byte, |K| = 256) the time complexity of the attack.

Example. In the AES case with g k (P) = SBOX[P ⊕ k] where P represents a plaintext byte, one can deduce E k from E k 0 with the following formula:

E k (Z) = E k 0 SBOX SBOX -1 [Z ⊕ k] ⊕ k 0 (4.15)

About the Distinguisher

In a real attack scenario, one does not know the true leakage model so it is impossible to use the visualization technique used in the previous section (where each sample is colored according to the true leakage model) to discriminate between the key candidates. Therefore, one would need a distinguisher D scoring each leakage model representation E k to rank the key hypotheses. The intuition behind EMA is that D should give a score reflecting the plausibility of the leakage representation E k according to physical a priori on the leakage model and on which properties the latter should follow.

Assumption on the Degree of E k *

We herein give a proposal of distinguisher for the common a priori stating that the leakage model φ k * should be a function from Z = F 2 n → R p such that the p coordinate functions have a low algebraic degree (bonded by a degree d). This is the multivariate version of assumption 3 (Leakage Interpolation Degree) followed in [START_REF] Doget | Univariate side channel attacks and leakage modeling[END_REF] for the setup of the well-known LRA. For example, a degree d = 1 traduces the fact that, for each time sample, all the bits of the processed variable leak independently. We propose to extend the assumption on the degree of φ k * (precisely of its coordinate functions) to the degree of its representation E k * , produced by the EVIL machine.

Distinguisher

If this assumption is true, then one can perform a polynomial regression of order d to find the polynomial p k of degree d minimizing the quadratic error ||E k (Z k )p k (Z k )|| 2 for all k. As explained in [START_REF] Doget | Univariate side channel attacks and leakage modeling[END_REF], such a regression can be seen as a linear regression by choosing an appropriate basis and is easily solvable using the least square method. A measure of fitness such as the coefficient of determination R 2 is then used as a score for each key:

D(k) = 1 - ||E k (Z k ) -p k (Z k )|| 2 var E k (Z k ) (4.16)
Since the assumption on the degree of E k is true only for k = k * , the correct key should have the highest score leading to a successful attack.

Intuition Behind the Assumption

The justification of the assumption on the degree of E k * is empirical. Indeed two functions in bijection do not necessarily have the same algebraic degree. However, we observed in the experiments of section 4.2 that the encoder naturally converges towards a "smooth" representation of the leakage model. Our intuition is that since neural networks are composed of a succession of continuous functions it is easier for it to map two values z 1 and z 2 that have a close leakage model (φ k * (z 1 ) close to

φ k * (z 2 )), to close encoding values E k * (z 1
) and E k * (z 2 ). Such continuous representation has more chance of preserving the degree. In addition, in Figure 4.4, it seems that when dealing with multidimensional leakages, the encoder produces a linear combination of the representation of univariate leakages. Such additive behavior would also preserve the degree since by hypothesis all the coordinate functions are of degree less or equal than d.

Experiments Supporting the Assumption

One may argue that the intuitions shared in the previous paragraph come from simple experiments and may not scale with high dimensional traces containing much more leaking samples as well as uninformative samples. Therefore we designed two experiments to assess the assumption in these harder cases. We have generated 10000 synthetic traces of dimension 1000 for both experiments. They contains 100 informative samples randomly distributed in the traces leaking information about Z = Sbox[P ⊕ k * ] where P represents a plaintext byte uniformly drawn from 0, 255 . In the first experiments, a linear leakage model is assigned to each sample, thus, the leakage L of each sample can be expressed as: where bit i (Z) stands for the i th bit of Z. The α i are random coefficient uniformly drawn from [-1, 1]. These coefficients are redrawn for each leaking sample. The second experiment emulates quadratic leakages (with no linear coefficients) such that for each sample:

L = α 0 + 8 ∑ i=1 α i • bit i (Z) + N (0, 1) (4.17
L = α 0 + 8 ∑ i=1 8 ∑ j=i+1 α i,j • bit i (Z) • bit j (Z) + N (0, 1) (4.18)
In both experiments, the 900 non-informative samples follow a normal distribution N (0, 1). We ran the EVIL machine assuming k 0 ̸ = k * and derived all the E k as explained in subsection 4.3.1. Figure 4.7 reports the evolution of D(k) for each k computed with linear and quadratic regression respectively for the first and second experiments. In both cases, the coefficient of determination converges toward 1 for the correct key. This means that after some epochs, E k * can be perfectly regressed by a linear/quadratic model. These two results support the assumption on the degree of E k * regarding the maximum degree of the coordinate function of the leakage model φ k * . In addition, this is not at all the case of E k for k ̸ = k * leading to a high distinguishability between the correct and the wrong keys.

Attack Description

The steps required to perform the EMA are summarized hereafter.

1. Choose any k 0 and run the EVIL machine for n e epochs with k 0 as a key assumption. This gives a representation E

k 0 for each epoch e.

Derive E (e)

k for all e and k using the formula:

E (e) k (Z k 0 ) = E (e) k 0 g k 0 (g -1 k (Z k 0 )) (4.19)
Chapter 4. The EVIL Machine: Encode, Visualize and Interpret the Leakage 3. Compute for all e and k the distinguishing score:

D (e) (k) = 1 - ||E (e) k (Z k ) -p k (Z k )|| 2 var E (e) k (Z k ) (4.20)
4. Derive a single score for each key:

D(k) = max n s ≤e≤n e D (e) (k) (4.21)
5. Rank the keys according to their distinguishing score.

The n s and n e parameters are hyper-parameters set by the adversary. The purpose of n s is to not take into account potential early fluctuation where the networks might be not stable yet. This turned out to be useful for very noisy situations (for our experiments, we used n s = 50 and n e = 100).

Experimental Results

EMA uses the classical LRA distinguisher on the encoder's output whose purpose is to encapsulate all the informative components of the traces. The classical LRA computes the regression directly on the traces in a univariate way (selecting the maximum score along all samples as a distinguisher). This section provides sim- The latter offers the capability to potentially exploit multiple leakage sources at the same time while reducing the need of preprocessing techniques thanks to the power of DL techniques. For example, convolutional layers may handle desynchronized traces [START_REF] Cagli | Convolutional Neural Networks with Data Augmentation Against Jitter-Based Countermeasures[END_REF]. To confirm that these advantages translate into objective improvements in terms of noise resilience or number of traces required, we present hereafter two experiments.

Experiments on Synthetic traces

For the first experiment, we generated multidimensional synthetic traces subject to desynchronization. These traces contains 20 informative samples, leaking information about Z = Sbox[P ⊕ k * ] trough linear leakage models, with randomly chosen coefficients, to which we added Gaussian noise with a standard σ. Traces contains also 80 uninformative samples and are artificially desynchronized. Each trace is shifted by a random number sh uniformly drawn from 0, 50 . The precise generation procedure is depicted in algorithm 3. We ran the classical LRA and the EMA following the procedure explained in subsection 4. for 1 ≤ i ≤ 10k do for 1 ≤ j ≤ 20 // Add leakage one every 5 samples do

L[i, 5 * j] ← L[i, 5 * j] + ∑ 8 l=1 R[j, l] • bit l (Z[i]) end end for 1 ≤ i ≤ 10k do
sh ← Draw a random integer uniformly from 0, 50

L[i] ← Roll(L[i]
, sh) // Apply the jitter (Roll is a function shifting the array by sh, in a looping way) end return L, P correct key computed over 100 independent experiments realized with a given value of σ. It appears that the EMA is way more resilient to the noise added to the traces resulting in successful attacks where the LRA fails. We highlight the fact that with such leakage models, (linear model with random coefficient from [-1, 1]) it would be hard to run an effective model-based attack since it would require an explicit model assumption.

Experiments on Real Traces

In order to validate our methodology on a real case scenario, we have acquired one million AES traces from a cortex A7-based System-on-Chip (SoC) running a Linux OS. The AES implementation comes from the OpenSSL library [START_REF]OpenSSL: The Open Source toolkit for SSL/TLS[END_REF]. We chose to run the analysis on a very noisy SoC subject to desynchronization, thus, offering

Introduction to Higher-Order Generalization

One of the most widely used countermeasures to prevent instantaneous leakages and mitigate first-order SCA is to mask the sensitive data using secret sharing techniques [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF]. The idea is to split each sensitive intermediate value z, into d shares: (z i ) 1≤i≤d . The d -1 shares z 2 , ..., z d are randomly chosen and the last one, z 1 is processed such that:

z 1 = z * z 2 * • • • * z d (4.22)
for a group operation * of Z. This led to the emergence of the so called higher-order attacks which combine multiple samples from the same traces leaking information from each share to deduce information on Z. The EVIL machine is, by nature, multidimensional and may therefore be extended to masked implementations. Indeed, we have shown in Chapter 2 that MINE can automatically recombine samples to find information in masked cases. It would therefore be possible to run straightforwardly the EVIL machine on masked implementations. However, the main theoretical problem is that in masked case the leakage model cannot be expressed as a deterministic function L = φ(Z) with some noise. Thus, there is no equivalent of Equation 4.2 for masked cases. A natural question is then to ask towards what kind of representation the encoder typically converge.

Encoder's Output and Joint Moments

When dealing with masked implementations, the leakage variable is not separable into a deterministic and a noise part anymore. Instead, traces correspond to realizations of a leakage variable L coming from a stochastic process S, Z S -→ L which encapsulates the random choice of the masks and the leakage model of each share.

L follows a multivariate probability distribution which, as any distribution, is completely determined by the list of all its joint moments. First-order SCA exploit information in the first-order moment: the leakage model being the mean per class:

φ(z) = E[L | Z = z] (4.23)
For a masked implementation the discriminating information, if it exists, is necessarily hidden in higher-order joint moments since lower-order leakages are prevented by masking. Therefore, the idea of higher-order attacks [PRB09; [START_REF] Dabosville | A New Second-Order Side Channel Attack Based on Linear Regression[END_REF][START_REF] Cristiani | Fit The Joint Moments -How to Attack any Masking Schemes[END_REF] is to exploit the lowest-order4 centered joint moment containing information, thus replacing Equation 4.23 by the joint moment per class. For a d-order masked implementation and (L 1 , . . . , L d ) representing one leakage sample for each share, such a joint moment can be expressed as:

jm L (z) = E d ∏ i=1 (L i -µ L i | Z = z) (4.24)
where µ L i stands for the expectation of L i . For example, the classical second-order CPA [START_REF] Prouff | Statistical Analysis of Second Order Differential Power Analysis[END_REF] combines samples with the centered product function which happens to be the covariance, a.k.a. the second order joint moment.

Hypothesis on the Encoder's Output

By analogy with the unmasked case where the encoder of the EVIL machine converged towards a representation of φ (Equation 4.23) our hypothesis is that, for masked implementations, the encoders will converge towards a representation of jm L (Equation 4.24). Our intuition is that jm L (Z) is a sound way to encode Z to keep information between jm L (Z) and L while limiting the information I jm L (Z¯k), L computed with a wrong key candidate k.

Experiment Supporting the Hypothesis

To validate this hypothesis, we present experiments on masked synthetic traces for three different second-order masking schemes: Boolean, arithmetic and multiplicative. The group operations are respectively the xor ⊕, the addition over Z/nZ +[n] and the multiplication over the Galois field ⊗. The multiplication by m being reversible for m ̸ = 0 the multiplicative mask has to be chosen in F * 2 n . In addition, the multiplicative scheme is biased since Z = 0 implies Z ⊗ m = 0 which induces a first-order leakage. For each masking scheme, we have generated 50k traces containing two samples representing the leakage of each share, Z 1 and Z 2 , through a linear model. The leakage L can be expressed as:

L = 8 ∑ i=1 α i bit i (Z 1 ) + N (0, 1), 8 ∑ i=1 β i bit i (Z 2 ) + N (0, 1) (4.25)
where the α i and β i coefficients are uniformly drawn from [-1, 1]. We have run the EVIL machine as explained in section 4.2 and present the result in Figure 4.9. For the Boolean and arithmetic schemes, each point is colored according to the theoretical covariance per class: cov(L | Z = z) which is computable knowing the α i and β i . It appears that the encoder is converging towards a smooth representation of covariance per class (the second-order joint moment), thus, supporting the hypothesis. For the multiplicative scheme, it seems that the encoder learned to distinguish the class Z = 0 from the others, confirming that it is focusing on lower-order leakages, if it exists, in priority.

About the Distinguisher

Stochastic attacks (with flexible a priori) have been extended to masked implemen-

A Practical Case on ASCAD

As a proof of concept of the higher-order version of the EMA, this section presents an attack on the public ASCAD dataset In order to identify which features of the traces has been exploited by the EVIL machine (with the correct key assumption) we plotted the evolution of the encoder's output in Figure 4.10b and colored each point of according to the value of the LSB.

Indeed, we showed in Chapter 3 that the higher-order leakage of ASCAD traces is mostly related to the value of the LSB of Z. It appears that after 200 epochs (when the attack begins to work) the encoder actually learned to split the two classes related to the LSB illustrating the interpretability of the encoder's output.

To give an order of magnitude, running the full attack (with the 500 epochs) took approximately 5 minutes on a workstation embedding a Tesla V100. Eventually, the last part of the chapter is dedicated to an introduction of higherorder generalizations of the strategy, replacing the leakage model estimation with the joint moment estimation. It raises the question of how to conduct an optimal attack considering that the adversary is granted an estimation of the joint moments per class of the leakage. The following chapter precisely tackle this question offering a new unsupervised strategy working as a stand alone attack but which combines nicely with EMA to serve as a distinguisher in the higher-order case.

Conclusion

Chapter 5

Fit the Joint Moments

How to Attack any Masking Scheme "No one can wear a mask for very long"

Seneca the Younger

One of the main countermeasure against SCA is to use secret sharing technique to mask the sensitive variables. Supervised attack can straightforwardly be extended to masked implementations even if the profiling phase may require more traces. However, defeating masking is less trivial when it comes to unsupervised attacks. While classical strategies such as CPA or LRA have been extended to masked implementations, we show in this chapter that these extensions only hold for Boolean and arithmetic schemes. Therefore, we propose a new unsupervised strategy, the Joint Moments Regression (JMR), able to defeat any masking schemes (multiplicative, affine, polynomial, inner product...), which are gaining popularity in real implementations. The starting point of JMR is an estimation of the joint moment per class.

In this chapter this estimation is assumed to be computed in a classical way combining samples from traces. However as shown in the previous chapter the EVIL machine could be used to replace this joint moment estimation and benefits from all the deep learning's advantage.

The main idea behind JMR is to directly regress the leakage model of the shares by fitting a system based on higher-order joint moments conditions. We show that this idea can be seen as part of a more general framework known as the Generalized Method of Moments (GMM). This offers mathematical foundations on which we rely to derive optimizations of JMR. Simulations results confirm the interest of JMR over state-of-the-art attacks, even in the case of Boolean and arithmetic masking. Eventually, we apply this strategy to real traces and provide, to the best of our knowledge, the first unsupervised attack on the protected AES implementation proposed by the ANSSI for SCA research, which embeds an affine masking and shuffling counter-measures.

Introduction

Context

To prevent instantaneous leakage of the sensitive variables, a classical strategy is to protect implementations using masking techniques. It consists in splitting the internal state of the processing into multiple random shares following secret sharing ideas [START_REF] Blakley | Safeguarding cryptographic keys[END_REF]. SCA against masked implementations is still possible through the so called higher-order attacks which combine multiple leakage samples corresponding to each share. However, these attacks are harder to conduct since the impact of the noise is amplified exponentially with the masking order [START_REF] Prouff | Masking against Side-Channel Attacks: A Formal Security Proof[END_REF]. Among unsupervised attacks, the multivariate CPA described in [START_REF] Prouff | Statistical Analysis of Second Order Differential Power Analysis[END_REF] has often proved to be an efficient strategy in practice. However, it relies on a Hamming weight leakage assumption (of the shares) that may not be correct especially when it comes to local EM measurements. Indeed, each bit of the intermediate variable can have very different leakage behavior and even sign inversions of their coefficients as shown in [START_REF] Cristiani | A Bit-Level Approach to Side Channel Based Disassembling[END_REF].

To deal with such situations [START_REF] Dabosville | A New Second-Order Side Channel Attack Based on Linear Regression[END_REF] proposed a generalization of the LRA whose main strength is to offer flexibility on the a priori without constraining each bit to have the same impact on the leakage. This method exploits information hidden in the covariance, i.e., the second order joint moment of the distribution since the first order moments (the means) are leakage-free thanks to masking. However, we argue that this method is not generic enough because it is based on the assumption that the covariance per class could be expressed as a low algebraic function, assumption that only holds for Boolean and low order arithmetic masking as shown in this chapter. Indeed, the proposed attack fails even in theory (on synthetic traces with zero noise) when dealing with other masking schemes such as the multiplicative or affine ones. These masking schemes along with the polynomial and inner product masking are getting more and more studied recently and begin to be used in modern implementations. This trend may continue in the future since these schemes seem to offer better resistance against side-channel attacks [START_REF] Balasch | Theory and Practice of a Leakage Resilient Masking Scheme[END_REF]. Mutual information-based attacks have also been extended to masked implementations but have not either proven to be valid strategies for any kind of masking and their applicability is mainly related to the open questions, raised in Chapter 3, about the choice of the partitioning function. This leads us to the following observation:

To the best of our knowledge, no generic unsupervised strategy able to defeat any kind of masking outside of the Hamming weight leakage assumption emerges from the state-of-theart.

We propose such a strategy in this chapter: the Joint Moment Regression (JMR).

The latter is built on the idea that the discriminating information, if it exists, is necessarily hidden in higher-order joint moments since lower-order leakages are prevented by masking (at least when not considering glitches from the physical implementation [START_REF] Mangard | Side-Channel Leakage of Masked CMOS Gates[END_REF]). Intuitively, joint moments encapsulate information about the corresponding distribution. The idea is to make a leakage assumption on each share (for example a linear leakage) and try to directly regress the leakage model of each share, using joint moments conditions, instead of trying to regress the joint moment itself as it is done in [START_REF] Dabosville | A New Second-Order Side Channel Attack Based on Linear Regression[END_REF]. This comes at the cost of the loss of linearity since the joint moment conditions involve a multiplication between the leakage parameters of the different shares which gives rise to a non-linear system of equations.

However, we show that numerical optimization algorithms can be used to find an estimation of the solution that best fits the conditions. A measure of fitness is used as a distinguisher between key candidates. The joint moment conditions depend on the underlying masking scheme which allows to embed knowledge of the latter into the system and, therefore, makes the attack generic.

Contributions

• The first contribution of the chapter is to present the state-of-the-art on the stochastic higher-order attacks, especially focusing on the method proposed in [START_REF] Dabosville | A New Second-Order Side Channel Attack Based on Linear Regression[END_REF] to understand its strengths and limitations. This analysis can be found in section 5.2.

• As a second contribution, we introduce a new attack strategy: the Joint Moment Regression (JMR) in section 5.3. It is built to circumvent the issues found in the state-of-the-art and proposes a method which is agnostic to the underlying masking scheme.

• We then draw a parallel between the core of JMR and a more general framework: the Generalized Method of Moment (GMM) [START_REF] Peter Hansen | Large Sample Properties of Generalized Method of Moments Estimators[END_REF] which is a wellstudied paradigm in statistics and economics. This allows to improve our attack in the case of biased masking schemes such as the multiplicative and affine ones. This analysis can be found in section 5.4.

• Finally, section 5.5.2 presents applications of JMR to real traces and provides at the same time, to the best of our knowledge, the first unsupervised attack on the secured AES implementation of the ANSSI, protected by an affine masking scheme. Attacks that do and do not exploit the lower-order leakage are both presented.

Related Work and Limitations

General Attack Framework

We recall the notation and attack framework used in this chapter. We consider that an adversary targets the manipulation of a sensitive variable Z ∈ Z = F n 2 , for a given n ∈ N. This variable is supposed to functionally depends on a public variable X ∈ X = F m 2 , for a given m ∈ N, and a secret key k * ∈ K = F m 2 through the relation: Z = f (X, k * ) where f : X × K → Z is a known function depending on the underlying cryptographic algorithm. The adversary is supposed to own a set {(ℓ i , x i ), 1 ≤ i ≤ N} of N side channel traces labeled with the corresponding public value of X. Traces correspond to realizations of a leakage variable L ∈ L coming from a stochastic process S, Z S -→ L (often separable into a deterministic and a noise part). The leakage variable L is supposed to contain information about Z. The general idea of an unsupervised side-channel attack is to make a series of hypotheses k i on the key, and to use the dependency between Z and L to build a distinguisher D : K → R to rank the different key candidates. One of these distinguishers, the LRA, is described in the next section.

Linear Regression Analysis

The following procedure recalls the steps required to perform an LRA such as suggested in [START_REF] Lomné | Behind the Scene of Side Channel Attacks[END_REF]. Traces are assumed to feature one sample. In a real-life scenario, the same procedure would be repeated for each sample and the final distinguisher keeps the best value along all samples according to a chosen policy (often being the minimum/maximum value of the distinguisher). 4. Making hypotheses. For k ∈ K compute the hypotheses matrix:

H k = b i • f (x, k) x∈X , 1≤i≤r
5. Linear regression. For k ∈ K find the parameter vector θ k = (θ k,1 , . . . , θ k,r ) T minimizing the euclidean norm of the error vector:

θ k = argmin θ ||H k • θ -L|| 2
5.2. Related Work and Limitations 93 6. Ranking. Rank the keys according to their distinguisher value (from low to high) 1 :

D(k) = ||H k • θ k -L|| 2
Since step 5 corresponds to a linear regression it has a closed-form solution:

θ k = (H k T • H k ) -1 • H k T • L
However, to highlight similarities with JMR later in the chapter, we decided to keep the generic formulation of the optimization problem.

The choice of the basis is important since it should be large enough for the leakage to be representable as a linear combination with the b i • f functions when k = k * but small enough so that it is not the case for wrong hypotheses. The adversary uses his a priori on the leakage model, often related to physical assumptions, to choose the basis.

A common example is to assume that each bit of the sensitive variable contributes to the leakage independently from the others. If this assumption holds there exists α = (α 0 , . . . , α n ) such that ℓ i = α 0 + ∑ α j • bit j (z i ) + ϵ with bit j denoting the projection on the j th bit and ϵ being sampled from a noise distribution. In such a case, the basis would be {1, bit 1 , . . . , bit n } and θ k * should be close to α.

Another example is to assume that the leakage is depending on the Hamming Weight (HW) of the sensitive variable so that ℓ i = α 1 HW(z i ) + α 0 + ϵ. The basis is then reduced to {1, HW} and the attack corresponds to the classical CPA.

Masking

To prevent instantaneous leakages and mitigate the first-order attacks presented above, one of the most widely used countermeasures is masking [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF]. The idea is to split each sensitive intermediate value Z, into d shares: (Z i ) 1≤i≤d . The d -1 shares Z 2 , ..., Z d are randomly chosen and the last one, Z 1 is processed such that:

Z 1 = Z * Z 2 * • • • * Z d (5.1)
for a group operation * of Z. This has the effect of complexifying the stochastic process S generating L from Z, rendering it no longer separable into a deterministic and a noise part. Assuming the masks are uniformly distributed, the knowledge of d -1 shares does not tell anything about Z (this is why such masking is said to be of order d -1). Therefore, any sound SCA strategy has to combine leakage samples from the d shares to perform an attack (which corresponds to at least d samples if the leakages are disjoint). Such attacks are called d th order attacks. One of them, the second-order LRA is presented in the next section.

1 Sometimes the coefficient of determination R 2 is used instead but the ranking is strictly equivalent except that one ranks from high to low values of the distinguisher. The uniform assumption is sometimes not strictly realized in practice depending on the masking scheme being used. Four of the most common masking schemes that will be studied in this chapter are listed in Table 5.1. The ⊕ and ⊗ respectively stand for the addition and the multiplication operation in F n 2 . Since the multiplication by 0 is not invertible the "multiplicative shares" have to be chosen in F n 2 \ {0}. As Z itself can take the value 0, the multiplicative and affine schemes are then slightly biased, and therefore, do not guarantee in theory, SCA resilience to all the (d -1) th and lower order attacks. Such attacks will be discussed in section 5.4.

Group operation Masked Variable

(Z 1 ) Uniform Reference Boolean ⊕ Z ⊕ Z 2 ⊕ • • • ⊕ Z d Yes [Cha+99] Arithmetic + mod 2 n Z + Z 2 + • • • + Z d [2 n ] Yes [CG00] Multiplicative ⊗ Z ⊗ Z 2 ⊗ • • • ⊗ Z d No [GPQ11] Affine ⊕, ⊗ Z ⊗ Z 2 ⊕ Z 3 No [Fum+11]

Second-Order LRA

This section describes the generalization of the LRA introduced in [DDP13] which aims at defeating a first-order masked implementation (d = 2). Traces are considered to be composed of 2 samples: L = (L 1 , L 2 ) where L 1 and L 2 represent respectively the leakage of the first and second share. In a real-life scenario, the attack would be repeated with all the combinations of two samples from the raw traces.

To perform a second-order LRA the adversary is supposed to own a set of N traces {(ℓ i 1 , ℓ i 2 ), 1 ≤ i ≤ N}. The idea is to replace the estimated mean per class by the estimated covariance per class in the classical LRA which naturally combines information from the two samples. Indeed the covariance Y = cov(L 1 , L 2 ) involves the product of the centered variable L 1µ 1 and L 2µ 2 , with (µ 1 , µ 2 ) = E[L], which has been shown to be a good combining function for second-order SCA [START_REF] Prouff | Statistical Analysis of Second Order Differential Power Analysis[END_REF].

The steps to perform a second-order LRA are depicted hereafter.

Partitioning. Partition the traces into |X | classes

: L x = {(ℓ i 1 , ℓ i 2 ), x i = x}. 2. Estimating covariances. Compute the estimated covariance for each class Ȳ = ( ȳx ) x∈X with ȳx = 1 |L x | ∑ ℓ∈L x (ℓ 1 -μ1 )(ℓ 2 -μ2 )
where ( μ1 , μ2 ) stands for the estimated mean of L.

3. Basis choice. Choose a basis of functions (b i ) 1≤i≤r such that b i : Z → R.

4. Making hypotheses. For k ∈ K compute the hypotheses matrix:

H k = b i • f (x, k) x∈X , 1≤i≤r
5. Linear regression. For k ∈ K find the parameter vector θ k = (θ k,1 , . . . , θ k,r ) T minimizing the euclidean norm of the error vector:

θ k = argmin θ ||H k • θ -Ȳ|| 2
6. Ranking. Rank the keys according to their distinguisher value (from low to high):

D(k) = ||H k • θ k -Ȳ|| 2
The attack may seem very similar to a first-order LRA except that it is performed on the covariance instead of the mean (the change happens in step 2). However, the choice of the basis is much more delicate. The link between the adversary a priori and a basis leading to a successful attack is not trivial anymore. Indeed, the hypotheses matrix is constructed using the unmasked variable Z (k) = f (X, k) while the leakage a priori concerns the shares. The choice of the basis proposed in [START_REF] Dabosville | A New Second-Order Side Channel Attack Based on Linear Regression[END_REF] is based on an assumption that is recalled hereafter.

Let us define the set of functions (φ k ) k∈K : Z = F n 2 → R such that:

φ k (z) = cov(L 1 , L 2 | Z (k) = z) (5.2)
Since all the Boolean functions in F n 2 can be represented by a multivariate polynomial in R[z 1 , . . . , z n ]/(z 2 1z 1 , . . . , z 2 nz n ) (i.e. the degree of every z i in every monomial is at most 1) [START_REF] Carlet | Boolean Functions for Cryptography and Error Correcting Codes[END_REF], there exists, for any k, a unique set of coefficients (α k,u ) u∈F n 2 such that:

φ k (z) = ∑ u=(u 1 ,...,u n )∈F n 2 α k,u • z u (5.3)
where each term z u denotes the monomial (function) z → z u 1 1 z u 2 2 . . . z u n n with z u i i ∈ F 2 . Let deg(φ k ) stands for the degree of the polynomial representing φ k . The assumption on which the attack from [START_REF] Dabosville | A New Second-Order Side Channel Attack Based on Linear Regression[END_REF] relies is the following:

Assumption 1. ∀k ̸ = k * , deg(φ k * ) < deg(φ k ).
The intuition behind this assumption is that since

φ k = φ k * • f k • f -1 k * (where f k = f (•, k)), φ k is expected to have a high degree (close to n) if k ̸ = k * ,
due to cryptographic properties of f which often embeds highly non-linear S-boxes to prevent algebraic attacks. Note that this reasoning only holds if φ k * itself has a low degree which is implicitly assumed in [START_REF] Dabosville | A New Second-Order Side Channel Attack Based on Linear Regression[END_REF]. This point will be discussed later.

If Assumption 1 holds, the basis:

(b i ) i = {z u , u ∈ F n 2 , HW(u) ≤ deg(φ k * )
} is a valid basis for the second-order LRA. Indeed, it spans all the functions of degree less or equal deg(φ k * ). Therefore there exists a decomposition of φ k * in this basis while it is not the case for other φ k , by hypothesis, which guarantees the success of the attack (provided that the number of traces allows for a fair approximation of the covariances per class).

Limitations

The first observation is that even if Assumption 1 holds, the attack may fail in practice if deg(φ k * ) is not low enough. Indeed, the cardinal of the basis, and therefore the number of parameters to estimate, increases quickly with deg(φ k * ) offering a big capacity to the statistical model to fit the data whatever the considered value of k. If the noise is not negligible, this often means that the wrong hypotheses can reach similar scores to the correct one which reduces the distinguishability and therefore the effectiveness of the attack. For example, with n = 8 and deg(φ k * ) ∈ {1, 2, 3} the cardinal of the basis is respectively equal to 9, 37 and 93. In practice authors of [START_REF] Dabosville | A New Second-Order Side Channel Attack Based on Linear Regression[END_REF] run their attack with the following basis: (b i ) i = {z u , u ∈ F n 2 , HW(u) ≤ d max } where d max ∈ {1, 2, 3}. Choosing d max = 3 never led to the best attack even in cases where deg(φ k * ) was strictly greater than 2 (due to the high model capacity and lack of distinguishability).

Then, one may ask if Assumption 1 holds at all. Since φ k * (z) = cov(L 1 , L 2 |Z (k * ) = z) it is obviously related to the nature of the leakage L 1 and L 2 . These variables can be assumed to be separable into a deterministic and a noise part with respect to the shares:

L i = l i (Z i ) + ϵ i (5.4)
with l i : Z → R representing the leakage of share i and ϵ i being an independent random noise variable. By bilinearity of the covariance and independence of ϵ i :

φ k * (z) = cov l 1 (Z 1 ), l 2 (Z 2 ) | Z (k * ) = z = cov l 1 (z * Z 2 ), l 2 (Z 2 ) (5.5) since Z 1 = Z (k * ) * Z 2 .
Both l 1 and l 2 can be assumed of low degree (through a physical a priori on the leakage). For example, it is realistic to assume that both shares follow a linear leakage. But we argue that this is not enough to guarantee Assumption 1 and that it is still depending on the underlying masking scheme, especially on the nature of the * operation.

Then, a natural question arises: why does the attack presented in [START_REF] Dabosville | A New Second-Order Side Channel Attack Based on Linear Regression[END_REF] work?

We argue that it is related to the studied masking schemes in their paper. Indeed, the latter one focuses on the Boolean and arithmetic masking schemes which are both exceptions as far as Assumption 1 is concerned. This claim is justified by the two following propositions.

(z) = cov l 1 (z ⊕ Z 2 ), l 2 (Z 2 ) . Then, deg(φ Bool ) ≤ 1 (5.6)
Proof can be found in Appendix D.

One important property of JM (and of simple moments) is that, for distributions defined on a compact set of R n , the distribution is fully defined by the list (maybe infinite) of all its JM. This is also true for the centered JM provided that the first order JM are also given.

The effect of a d-order masking is that no information related to the sensitive variable can be found in the d -1 and lower JM. That is why the second-order LRA performed a regression on the second-order centered JM with u = (1, 1) which happens to be the covariance. Indeed it is the lowest order JM bringing information on the sensitive variable. Information could also be found in higher-order JM but they are harder to estimate. Indeed, more terms are involved in the product and the noise in each one of them is amplified through the multiplication. One typically wants to take the JM with the lowest standard error (the standard deviation of its estimator).

This also explains why centered JM are preferred: as shown in [START_REF] Prouff | Statistical Analysis of Second Order Differential Power Analysis[END_REF], they have a lower standard error than their uncentered counterpart.

Attack Description

Let an adversary own a set of N traces {ℓ i , 1 ≤ i ≤ N} of a d order masked implementation. Traces are considered to be composed of d samples: ℓ i = {(ℓ i 1 , . . . , ℓ i d ). In a real-life scenario, the attack would be repeated on combinations of d samples from the raw traces depending on the attacker a priori on the points of interest. To defeat this implementation a naive solution would be to extend the attack proposed in [START_REF] Dabosville | A New Second-Order Side Channel Attack Based on Linear Regression[END_REF] using centered JM instead of covariance but as stated in section 5.2.5: there is no obvious link between the physical a priori, which happens to be on the shares, and the basis that has to be chosen and applied to the unmasked sensitive variable.

That is why we propose a new strategy where the adversary chooses d basis, one for each share (in practice they will often be the same basis), and directly regresses the leakage of each share using information from the estimated d order centered JM.

The steps of what we call the Joint Moment Regression (JMR) are depicted hereafter.

JMR

L x = {(ℓ i 1 , . . . , ℓ i d ), x i = x}.
2. Estimating JM. Compute the estimated centered d order joint moments matrix J M. Each row represents the estimation for one class:

J M =           1 |L 0 | ∑ ℓ∈L 0 d ∏ j=1 (ℓ j -μj ) . . . 1 |L 2 m -1 | ∑ ℓ∈L 2 m -1 d ∏ j=1 (ℓ j -μj )          
where ( μ1 , . . . , μd ) stands for the estimated mean of L.

3. Basis choice. For j ∈ [1, d], choose a basis of functions (b (j)

i ) 1≤i≤r such that b (j) i : Z → R. Intuitively, if l j corresponds to the leakage of share j, the adversary wants to choose a basis such that l j (z j ) = ∑ r i=1 θ j,i • b (j)

i (z j ) + ϵ j for some coefficient θ j ∈ R r , with ϵ j representing an independent random noise variable.

4. Making hypotheses. Let lj (z j ) stand for the leakage prediction of share j according to the chosen basis:

lj (z j ) = r ∑ i=1 θ j,i • b (j) i (z j ) (5.12)
For k ∈ K, define the theoretical JM vector J M k (θ) with respect to θ ∈ R d×r , that traduces the leakage assumption of step 3 into |X | = 2 m JM per class expressions:

J M k (θ) =           a 0 ∑ (z 1 ,...,z d )∈A 0 d ∏ j=1 lj (z j ) -µ θ j . . . a 2 m -1 ∑ (z 1 ,...,z d )∈A 2 m -1 d ∏ j=1 lj (z j ) -µ θ j           with A x = {(z 1 , . . . , z d )|Z = f (x, k)} and a x = 1 |A x | .
Here, µ θ j stands for the theoretical mean of the leakage of share j under the assumption of θ j :

µ θ j = E Z j r ∑ i=1 θ j,i • b (1) i (Z j )
5. Non-linear regression. For k ∈ K, find through numerical optimization techniques (see subsection 5.3.3), the parameter vector θ (k) ∈ R d × R r minimizing the euclidean norm of the error vector:

θ (k) = argmin θ ||J M k (θ) -J M|| 2
6. Ranking. Rank the keys according to their distinguisher value (from low to high):

D(k) = ||J M k (θ (k) ) -J M|| 2

Attack Soundness

The general attack structure of JMR is very similar to the LRA and second-order LRA. The main difference with the latter one is that the assumption is done on the is itself based on the Gauss-Newton algorithm and the method of gradient descent.

The attack time or complexity is mostly constant regarding the number of traces because the latter does not affect the number of parameters nor equations in the system. The only part that scales with the number of traces is the estimation of the JM per class which is just a product and a sum and that can be handled with numpy [Har+20] array manipulations.

Since the least-squares problems related to the different key hypotheses are independent, the implementation is highly parallelizable. We exploited this using a 48 cores Xeon Platinium 8168 processor which speeded up the attack by a significant factor since the implementation of the least_squares function is not parallelized in itself. Other implementation optimization could be explored such as using the fast GPU version of the LM algorithm proposed in [START_REF] Przybylski | Gpufit: An open-source toolkit for GPU-accelerated curve fitting[END_REF] but this is not in the scope of this paper. To give an order of magnitude, with our setup, running the full JMR procedure as described in subsection 5.3.2 for a d-tuple of time samples, requires around 10 and 15 seconds for respectively a second and third-order attack (assuming one trace for each possible values of the shares: 2 16 and 2 24 respectively).

Generating Datasets

To assess the JMR method and to compare it with state-of-the-art attacks, synthetic trace datasets with linear leakage of the shares have been generated for first and second-order masking (d ∈ {2, 3}). Boolean, arithmetic, multiplicative and affine (only with d = 3) schemes are used to mask the classical sensitive variable of an AES: Z = Sbox[k * ⊕ P] (k * and P are both supposed to be 8 bits long). To be able to average the results of 100 different attacks, performed with 100 different linear leakage models, we have generated a matrix of random coefficients C i for each share To avoid any kind of estimation error (the error coming from sampling), each dataset contains one trace for each of the possible values of the shares (z 1 , . . . , z d ) ∈ Z d (for multiplicative and affine schemes the multiplicative shares can not be 0 so we take them from 1, 255 instead). The trace ℓ (a)

(1 ≤ i ≤ d): C i = α a,b 0≤a≤99
(z 1 ,...,z d ) corresponding to the d-tuple (z 1 , . . . , z d ) is generated by concatenating the leakage of each shares (represented by the a th row of the C i matrices) as follows:

ℓ (a) (z 1 ,...,z d ) = l (a) 1 (z 1 ), • • • , l (a) d (z d ) ( 5
) ∈ Z d do z 1 ← z ⋆ • • • ⋆ z d l ← ℓ (a) (z 1 ,...,z d ) (Equation 5.16) p ← Sbox -1 [z] ⊕ k * Append l to L Append p to P end R ← Draw a (2 8 * d , d) array from N (0, σ 2 ) L ← L + R return L, P with l (a) i (z i ) = C i [i, 0] + 8 ∑ b=1 C i [a, b] • z i [b] + ϵ i (σ)
(5.17) where z i [b] corresponds to the b th bit of z i and ϵ i is drawn from a normal distribution N (0, σ 2 ). The exact procedure that generates the traces considering the the a th leakage model is depicted in algorithm 4.

Results

Second-order attacks results are presented in Figure 3.1. Each point represents the average rank of k * over the 100 datasets for a given value of σ. We recall that we are using exhaustive datasets, therefore, a failed attack for a given value of σ does not mean that the attack is impossible but rather that the adversary would need more traces than one per possible value of the shares. We compare JMR with

• A higher-order CPA, denoted HO-CPA, computed with a Hamming weight prediction model and using the JM of order d as combining function which happens to be the same as the centered product described in [START_REF] Prouff | Statistical Analysis of Second Order Differential Power Analysis[END_REF].

• Higher order LRA, denoted HO-LRA-d max where d max is the assumed degree of φ k * as defined in Equation 5.5. Therefore the basis used in HO-LRA-d max is

(b i ) i = {z u , u ∈ F n 2 , HW(u) ≤ d max }.
The combining function is also the JM of order d which for d = 3 is a straightforward extension of the second order attack described in [START_REF] Dabosville | A New Second-Order Side Channel Attack Based on Linear Regression[END_REF]. • Mutual Information Analysis, denoted MIA-f , where the distinguisher used is MI( f (Z k ), L). MIA requires the use of a non-injective function f to create distinguishability for the correct hypothesis. Since the leakage model is unknown we used very generic models: f = MSB and f = 7B, where MSB stands for the most significant bit of Z k and 7B stands for the 7 most significant bits of Z k .

Joint Moments Regression

The MI has been estimated using the histogram method described in [START_REF] Prouff | Theoretical and Practical Aspects of Mutual Information Based Side Channel Analysis[END_REF].

(a) For the Boolean case, JMR and HO-LRA-1 performs approximately the same which is not surprising since, by Proposition 5, Assumption 1 holds for HO-LRA1. It also holds for HO-LRA-2/3 but HO-LRA-1 perfectly explains the data with fewer parameters, and thus, performs better. One can notice that even without noise the HO-CPA is not converging towards 0 which confirms that it relies on the Hamming weight leakage assumption. Also, MIA strategies do not perform well which is not surprising since the underlying leakage model is unknown and it is, therefore, hard to select a good non-injective function.

(b) For the arithmetic scheme, JMR outperforms all the other attacks even, HO-LRA-2 in which Assumption 1 holds by Proposition 6. Again this is explained by the fact that JMR only needs (9 × 2) parameters to predict the data while HO-LRA-2 needs 37 parameters. Even without noise, the data can not be perfectly explained in an HO-CPA or HO-LRA-1 model since their curves do not converge towards 0.

(c) For the multiplicative scheme, as predicted, none of the state-of-the-art attacks perform better than random even without noise which confirms that Assumption 1 does not hold at all for such masking scheme. JMR is the only sound attack in this case.

Results for third-order attacks are presented in Figure 3.2. In this case, HO-LRAd max represents the generalization of the second-order LRA replacing the covariance by the third-order joint moment. Conclusions are the same than for the secondorder attacks. Among the considered attack strategies, one can observe that, as for the multiplicative case, JMR is the only sound option to attack affine masking under a linear leakage of the shares.

About the Biased Schemes

Both multiplicative and affine schemes are slightly biased which can induce lowerorder leakage. We argue that such leakage has not been exploited in this section since the estimated JM were computed with the leakage of all the shares (thus, the variance of the estimation result from d multiplications of noisy leakages). To confirm this statement, we repeated the previous experiments for the biased schemes removing Z = 0 from the possible values, thus, simulating non-biased schemes. The results being essentially the same than those presented in Figures 3.1c, 5.2c and 5.2d so we do not plot them. Since the multiplicative and affine masking do not seem to have special algebraic properties like the Boolean and arithmetic scheme as shown in propositions 5 and 6, we argue that these results could be extended to any other masking scheme. Indeed, the real added value of JMR is its ability to encode the scheme knowledge in the system's equation making it generic and able to work even for non-biased schemes with a high algebraic degree 2 where other attacks would not. However, in the specific case of biased schemes, lower-order leakage could be exploited with simpler attacks such as a classical CPA with a zero-valued based power model. One could also perform more advanced attacks taking advantage of leakages at multiple orders at the same time. All these attacks are discussed in the next section where we introduce the generalized method of moment paradigm.

Generalized Method of Moments Paradigm

Looking from a broader perspective, it appears that the core of the JMR attack can be seen as part of a more general framework known as the Generalized Method of Moments (GMM) [START_REF] Peter Hansen | Large Sample Properties of Generalized Method of Moments Estimators[END_REF]. This method comes from the field of statistics and economy and its main purpose is to estimate parameters in a statistical model. Embracing this paradigm requires to gain a level of abstraction but it allows to use the powerful mathematical foundations behind it. In particular, it will tell us how to optimally combine information from different orders, which is useful when the masking scheme is biased.

Background on GMM

Let suppose that the available data consists of N observations (L i ) 1≤i≤N of a random variable L ∈ R n . This data is assumed to come from a stochastic process defined up to an unknown parameter vector θ ∈ R p . The goal is to find the true value θ 0 of this parameter or at least a reasonably close estimate.

In order to apply GMM the data must come from a weakly stationary ergodic stochastic process (independent and identically distributed (iid) variables are a special case of these conditions). Then one needs to have c "moment conditions" defined as a function g(ℓ, θ) : R n × R p → R c such that: E[g(L, θ 0 )] = 0 (5.18)

Chapter 5. Fit the Joint Moments: How to Attack any Masking Scheme

The idea is then to replace the theoretical expectation with its empirical analog:

m(θ) = 1 N N ∑ i=1 g(ℓ i , θ) (5.19)
and to minimize the norm of m(θ) with respect to θ. The properties of the GMM estimator depend on the chosen norm and therefore the theory considers the entire family of norms defined up to a positive-definite weighting matrix W ∈ M c (R):

||m(θ)|| W = m(θ) T Wm(θ) (5.20)
The GMM estimator is then defined as:

θ = argmin θ ||m(θ)|| W (5.21)
The way of solving this optimization problem is not specified in the GMM theory. It is left to the numerical optimization field.

The purpose of W is to weigh the different conditions. Choosing W = Id c leads to consider the classical euclidean norm and is equivalent to considering that all conditions should weigh the same. The intuition behind the fact that one may prefer another norm is that some conditions may be less informative, redundant, or more volatile in their empirical estimation. One typically wants to use the norm minimizing the asymptotic variance of the resulting estimator. This problem has a closed-form solution with the following theorem: Theorem 6. [START_REF] Peter Hansen | Large Sample Properties of Generalized Method of Moments Estimators[END_REF] Let θN be the random variable representing the output of the GMM estimator with N data observations. Let also define Ω as the covariance matrix of the conditions function g evaluated at θ 0 : Ω = cov-mat g(L, θ 0 ) . Then, argmin W lim N→∞ var( θN ) = Ω -1

(5.22)

In the particular case where conditions are independent the matrix Ω -1 is diagonal and choosing W = Ω -1 simply means that the moments' condition should be weighted inversely proportionally to their underlying variance. This is in line with the intuition that conditions with high variance are less informative.

Parallel with the JMR Attack

This section exhibits the similarities between the GMM and JMR. The core of the JMR attack relies on an estimation of the true parameters θ 0 ∈ Θ = R d × R r of a chosen statistical model (encoded in the choice of the basis) in order to explain the leakage of each share. Let L = (L 1 , . . . , L d ) represents the observed leakage variable and L θ the predicted leakage variable under the assumption of θ so that, under the assumption that the chosen model is correct, L = L θ 0 .

Since the moment conditions in JMR depend on the value of another public variable X, let define, for each key hypothesis k, a condition function g k : R d × X × Θ → R |X | as:

g k (ℓ, x, θ) = e x • ǰ m (1 d ) L θ |Z= f (x,k) - d ∏ i=1
(ℓ iμi ) (5.23)

where e x = (0, . . . , 1, . . . , 0) ∈ R |X | stands for a vector of 0 with one 1 at position 3 x, 1 d stands for a vector of d ones : 1 d = (1, . . . , 1) and ǰ m (u)

L is defined as in Equation 5.11. This definition of g k may seem very artificial but it is designed so that Equation 5.18 holds for the correct hypothesis k = k * (under the assumption that L = L θ 0 ):

E[g k * (L, X, θ 0 )] = 1 |X | ǰ m (1 d ) L θ 0 |Z= f (x,k * ) -ǰ m (1 d ) L|X=x x∈X = 0
(5.24)

Therefore applying GMM with g k * as condition function is sound while it is not for wrong key hypotheses. In fact this property is the one exploited by JMR since step 1 to 5 of JMR are equivalent to apply |K| GMM estimations, one for each of the g k condition functions, with W = Id |X | .

Improving JMR Using GMM Theory

This section describes two ways of improving JMR using the GMM theory. The first one is generic and the second one focuses on the unbalanced masking schemes.

Using the Optimal Weighting Matrix

Since the GMM theory recommends to use Ω -1 as weighting matrix, one could ask if using the identity matrix was optimal. Indeed, the adversary typically wants to minimize the variance of the GMM estimator for the correct key k = k * . Therefore it would be natural to replace the identity matrix with Ω -1 where Ω = cov-mat g k * (L, X, θ 0 ) . The problem is that Ω is hard to estimate with data since θ 0 is unknown. The solution to this problem is usually to apply the so-called two-step estimator where an estimation of θ 0 is first computed with JMR with a sub-optimal weighting matrix (for example the identity) which allows estimating Ω and eventually apply GMM with the latter estimation as weighting matrix. However, in our case, Ω does not depend on θ 0 which makes the process easier. Indeed, the variance of the components Chapter 5. Fit the Joint Moments: How to Attack any Masking Scheme Boolean masking scheme (ASCAD) [START_REF] Benadjila | Study of deep learning techniques for side-channel analysis and introduction to ASCAD database[END_REF]. The second one embeds an affine scheme and a shuffling countermeasure (ASCADv2) [START_REF] Benadjila | Hardened library for aes-128 encryption/decryption on arm cortex m4 achitecture[END_REF]).

Attack on a First-Order Boolean Masked AES (ASCAD)

As a first experiment, we performed the different stochastic attacks discussed in this paper on the public dataset of ASCAD. It is a common set of side-channel traces, introduced for research purposes on deep learning-based side-channel attacks. The targeted implementation is a software AES, protected with a first-order Boolean masking, running on an 8-bit ATMega8515 board.

We performed guessing entropies for the different attacks, using the training dataset containing 50k traces. We extracted from the dataset, the two Point-of-Interests (PoI) corresponding to the highest signal-to-noise ratio, one for each share.

This step requires the knowledge of the shares and would not be feasible by a nonprofiled adversary. In a real scenario, a visual analysis of the trace combined with knowledge on the implementation can be used to perform a PoI selection to reduce the number of sample combinations to be tested. Our goal here is to assess the security supposing that the adversary is able to apply the methodology on the best sample combination.

Results

Results are depicted in Figure 5.4. We observe similar outcomes than in the firstorder Boolean simulations. As expected the results of JMR ++ and HO-LRA-1 are very close since it is a Boolean masking (and thus, Assumption 1 holds). Similarly to Figure 3.3a, the slight advantage of JMR ++ may be explained by the use of the optimal weighting matrix. One may notice that the HO-CPA performs better than in the simulations. It outperforms all the other attacks for low numbers of traces even though attacks with an average correct key rank higher than 25 does not allow for a successful enumeration in a reasonable time. The better performance of HO-CPA can be explained by the fact that the leakage model of the ASCAD traces is much closer to a Hamming weight leakage model than those used in the simulated experiments.

In such cases, regression-based attacks benefits less from their genericity. As the execution time has a low dependency to the number of traces, running JMR ++ took approximately 10 seconds as in the simulations.

Attack of an open source Hardened AES implementation (ASCADv2)

As a second experiment, we decided to attack the second protected AES implementation proposed by the Agence Nationale de la Sécurité des Systèmes d'Information (ANSSI) [START_REF] Benadjila | Hardened library for aes-128 encryption/decryption on arm cortex m4 achitecture[END_REF]. They published a library implementing an AES-128 on an ARM Cortex-M4 architecture using state-of-the-art counter-measures. Indeed, this implementation uses an affine masking as well as random shuffling of independent in [START_REF] Masure | Side Channel Analysis against the ANSSI's protected AES implementation on ARM[END_REF]. Following their terminology we tried to attack the unmasked variable Z = Sbox[k * ⊕ P] using the leakage of the three shares:

Z 1 = Z ⊗ r mul ⊕ r out Z 2 = r mul Z 3 = r out (5.26)
Unfortunately, the number of traces turned out to be too low to analyze the unsupervised attacks discussed in this paper. Thus, we reproduced a similar experimental setup, described in the next section, in order to collect significantly more traces.

Acquisition Setup

Our setup has the following features:

• The acquisitions have been performed on a NUCLEO-F303RE board, which embeds the same STM32F303 micro-controller as used in ASCADv2.

• The device is clocked at 8MHz, while ASCADv2 device is clocked a 4 MHz.

This allows faster acquisitions without altering the execution behavior (e.g., introducing FLASH wait cycles). Being in an evaluation setup, we had the labels of the shares and validated that it did not affect the signal-to-noise ratio of these intermediate variables.

• We measured the magnetic field produced by the circuit with a Langer H-field probe (RF-U 5-2). This differs from ASCADv2 setup, which measures the current of the device through a ChipWhisperer [START_REF] Flynn | ChipWhisperer: An Open-Source Platform for Hardware Embedded Security Research[END_REF]. However, we observed Chapter 5. Fit the Joint Moments: How to Attack any Masking Scheme better signal to noise ratios on the EM field. The probe covers a large portion of the CPU and no specific tuning of the probe placement was performed.

• The scope was configured at 3.125 GS/s and acquired a window of 8µs, which represents 25,000 time samples.

• The masked AES implementation was taken "as-is" from the SecAESSTM32 repository [START_REF] Benadjila | Hardened library for aes-128 encryption/decryption on arm cortex m4 achitecture[END_REF]. We only made the following changes to the assembly code:

a GPIO is raised in the Load_random function, which manipulates r mul and r out .

a GPIO is raised in the first round of the AES, just after the Xor_Word operation.

To further speed up the acquisitions, we do not transfer the plaintext and masking inputs through the serial port. Indeed, this represents 54 bytes (16 + 19 × 2) per encryption, which quickly becomes a bottleneck for acquisitions. Instead, the device runs a PCG32 Pseudo-Random Number Generator (PRNG) [O'N14] to generate those data on the fly. This PRNG is re-seeded randomly (by sending 8 bytes on the serial port) every 250 acquisitions. This allows to regenerate (from the stored seeds) the plaintexts and random masks offline, to label the dataset.

For each encryption, the scope triggers twice and acquires 50,000 samples. The final dataset contains 100M traces and took 14 days to acquire. In summary, we used the same AES implementation and micro-controller as in the ASCADv2 setup. We only made some changes in the instrumentation and measurement chain to reduce the number of traces needed and improve the speed of acquisition.

Simulating an Unshuffled Version

The implementation uses random permutation of the 16 Sboxes applications. However, using the same idea as developed in technical analysis of the ANSSI reposi- where Sh -1 (0) denotes the index of the byte that is computed first through the permutation Sh. Then such an attack would uses Z ( k) = Sbox[ k ⊕ k * [Sh -1 (0)] ⊕ P[Sh -1 (0)]] as hypothesis intermediate variable, the attack being successful if the best hypothesis is 0.

Results

In a similar way to the first experiment from subsection 5.5.1, we extracted from the dataset described in section 5.5.2, the three Point-of-Interests (PoI) corresponding to the highest signal-to-noise ratio, one for each share. We performed the attacks on For each attack, traces are randomly drawn among the 100M dataset. Both JMR ++Full and JMR ++ converge towards a guessing entropy of 0 which provides by the same token, the first unsupervised attack on the secured ANSSI's AES implementation.

Using the scheme bias. Not surprisingly, JMR ++Full and HOCPA-0, which exploits the bias in the masking scheme, gives the best results. These attacks require 30k 4 and 15M traces to converge towards 0 for the unshuffled and shuffled version respectively. This confirms that for high noise value, a lower-order leakage induces attacks with at least one order of magnitude smaller data complexity. Thus, it confirms that even though d shares are used to mask the sensitive value, a biased d-order masking should not be considered of order d as far as security is concerned.

Not using the scheme bias. When this lower-order leakage is not considered in the attack, JMR ++ outperforms the other state-of-the-art attacks and is the only attack able to converge toward a guessing entropy of 0 with the considered number of traces. As in the simulations, the amount of time required to run this attack is approximately 15 seconds.

For biased masking schemes, there is no interest to perform this attack over CPA-0. However, we argue that this result is interesting since it shows how JMR would perform on a generic (with a high algebraic degree) unbiased second-order masking schemes.

Discussion

Results obtained on the real traces collected on AES implementations (proposed by the ANSSI) protected with boolean and affine masking are in line with the simulation results. It confirms that JMR gives a sound methodology, able to work with flexible leakage model assumptions (linear, quadratic...), which is applicable to any 4

It should be noted that even if some of the presented attacks require less than 800k traces, they have not been successful on the original ASCADv2 dataset. We have confirmed that our traces have a better SNR on the leakage of each of the shares which could explain this difference.

Chapter 5. Fit the Joint Moments: How to Attack any Masking Scheme

Conclusion

This chapter introduced a new unsupervised strategy, JMR, which embeds the masking structure within it, allowing it to defeat arbitrary masking schemes. It is based on a non-linear system regression which allows to derive the leakage model of each share by carefully exploiting higher-order joint moments conditions. JMR outperforms state-of-the-art attacks which are limited to Boolean and arithmetic masking, especially when the Hamming weight leakage assumption does not hold. We reduced the core of JMR into a more general framework: the generalized method of moments and derived optimizations of JMR from it. Experiments performed on synthetic data confirmed the effectiveness of the proposed attack, especially against multiplicative and affine masking schemes. Eventually, this new strategy has been confirmed on real traces, allowing a fully unsupervised attack of the ANSSI's protected AES implementation which embeds an affine masking and shuffling countermeasures.

The JMR method described in this chapter is not highly multi-dimensional in the sense that it only exploits d times sample when applied on a d th -order masking. It is well known that sensitive variables can leak several times in a single trace. Section 4.4.1 suggests that the EVIL machine produce an estimation of the joint moment per class under a key hypothesis. It is therefore possible in theory to bridge the two strategies to mount an unsupervised attack, able to work with a flexible a priori, agnostic to the masking scheme and which benefits from the advantage of deep learning techniques. Such a strategy would deserve a full analysis in a dedicated work which constitutes an interesting and stimulating line of research for future works.

Chapter 6

General Conclusion

This thesis investigated new unsupervised methods for side-channel analysis based on mutual information estimated in a high dimensional way. The starting point is that the mutual information between the full traces and the secret is a key quantity for SCA since it provides an absolute leakage quantification. Such a quantity has not really been studied before due to its computational intractability in high dimensional spaces: traces usually contains too many time samples for classical MI estimators to stay sound. However recent works from the pure machine learning community proposed a new MI estimator (MINE), based on deep learning techniques, that is supposed to scale with high dimensional variables.

The first contribution of this thesis, from Chapter 2, is to provide an analysis of MINE in an SCA context. We showed that with the correct representation of the input variable MINE is effectively able to estimate the MI between sensitive variables and full (or a significant portion of) traces. It is therefore able to automatically combines samples making the tool sound for masked implementations or for low signal cases where multiple sources have to be accumulated to detect a significant leakage.

MINE appears to be a generic tool allowing to have an objective leakage evaluation from traces. As a result, it could be used by designers/evaluators as a sound leakage metric during their development/evaluation process. EMA applied in the context of masking raised questions about higher-order generalizations of stochastic attacks. The last contribution, provided by Chapter 5, is an analysis of such generalizations along with a new proposal based on non-linear regressions of the joint moments of the leakage distribution (JMR). Its main advantage is to be agnostic to the masking scheme. We showed that state-of-the-art attack exploits specificities of the Boolean and arithmetic scheme and do not provide a generic strategy. JMR is based on an estimation of the joint moment per class. We showed that EMA applied on masked traces produces a representation of such joint moment per class while benefiting from the deep learning advantages. Therefore, EMA and JMR can be combined in an unsupervised attack strategy able to use the potential of deep learning with a flexible leakage model a priori and whatever the type of masking scheme. We provided a proof of concept of such a combination.

However, such a combination deserves a more in-depth characterization and may constitute an interesting and challenging path for future research.

One of the main objectives of this thesis was to provide theoretical bases as well as new unsupervised attack propositions which satisfied certain properties (aka.

multidimensional treatment of the traces, deep-learning potential, flexibility on the leakage model a priori, genericity regarding the masking scheme...). Throughout this thesis, neural networks have been seen mostly as a black box that accomplishes the task encoded in their loss function. We have kept the network architectures as simple as possible and did not dive into fine parameters tuning or analysis of the different architectures related to the latest deep-learning progress. A more practical study, focused on the DL side, would be valuable and may improve the real case performances. Indeed such techniques help the networks to converge better and faster towards their objectives, reducing the so called optimization error in the learning process.

3. 3

 3 Comparison of I Z k * , L and I HW(Z k * ), L on masked synthetic traces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Analysis of the ASCAD leakage model: a) Test from remark 5 -b) & c) Coeficients of a linear regression on the given variable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Guessing entropies for the considered attacks on ASCAD with added noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 The EVIL Machine Architecture . . . . . . . . . . . . . . . . . . . . . . . 4.2 Evolution of the encoder's output: E(z), ∀z ∈ Z versus epochs (Hamming weight leakage model). . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Evolution of the encoder's output: E(z), ∀z ∈ Z versus epochs (linear leakage model). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Evolution of the encoder's output: E(z), ∀z ∈ Z versus epochs (multidimensional leakage model). . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Evolution of the encoder's output: E(z), ∀z ∈ Z versus epochs (nonlinear leakage model). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Evolution of the encoders' output for the correct and a wrong key guess. xii 4.7 Evolution of the distinguisher D(k) versus epochs for all the key candidates. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.8 Guessing entropies of EMA and LRA. . . . . . . . . . . . . . . . . . . . 4.9 Evolution of the encoder's output: E(z), ∀z ∈ Z on masked synthetic traces (linear leakage model of the shares). . . . . . . . . . . . . . . . . 4.10 Attack results on ASCAD with 10k traces. . . . . . . . . . . . . . . . . . 5.1 Guessing entropies versus standard deviation of the noise for the considered second-order attacks after the processing of A) 2 16 , B) 2 16 , C) 2 8 × 255 traces. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Guessing entropies versus standard deviation of the noise for the considered third-order attacks after the processing of A) 2 24 , B) 2 24 , C) 2 8 × 255 2 , D) 2 16 × 255 traces. . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Guessing entropies for the improved JMR attacks, using the GMM theory, and for (HO)CPA-0 after the processing of A) 2 16 , B) 2 16 , C) 2 8 × 255, D) 2 16 × 255 traces. . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Comparison of different attacks' guessing entropies on ASCAD . . . . 5.5 Comparison of different attacks' guessing entropies on the secured ANSSI's AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.1 Network architecture for MINE . . . . . . . . . . . . . . . . . . . . . . . B.2 Network architecture for the classifiers (Supervised and DDLA) . . . . C.1 Architecture of the encoder E . . . . . . . . . . . . . . . . . . . . . . . . C.2 Architecture of MINE A and B . . . . . . . . . . . . . . . . . . . . . . . xiii Assessment Through Neural Estimation of the Mutual Information -Valence Cristiani, Maxime Lecomte & Philippe Maurine -Published in International Conference on Applied Cryptography and Network Security (ACNS) 2020. 2. Revisiting Mutual Information Analysis: Multidimensionality, Neural Estimation and Optimality Proofs -Valence Cristiani, Maxime Lecomte & Philippe Maurine -Submitted to Journal of Cryptology (JoC). 3. The EVIL Machine: Encode, Visualize and Interpret the Leakage -Valence Cristiani, Maxime Lecomte & Philippe Maurine -Submitted to Symposium On Applied Computing (SAC) 2023. 4. Fit the Joint Moments: How to Attack any Masking Schemes -Valence Cristiani, Maxime Lecomte, Thomas Hiscock & Philippe Maurine submitted -Submitted to IEEE Open Access. Side Works 5. A Bit-Level Approach to Side Channel Based Disassembling -Valence Cristiani, Maxime Lecomte & Thomas Hiscock -Published to CARDIS 2019. 6. Don't Learn What You Already Know: Grey-Box Modeling for Profiling Side-Channel Analysis against Masking -Loïc Masure, Valence Cristiani, Maxime Lecomte & Fançois-Xavier Standaert -Published to Cryptographic Hardware and Embedded Systems (CHES) 2023. xiv À mon père, qui m'a énormément inspiré, et avec qui j'aurais adoré partager les découvertes et les questionnements qui m'ont été offerts durant ces trois années.

  FIGURE 1.1: Generic cryptographic scheme

  FIGURE 1.2: Electromagnetic trace of an AES

  techniques have been proposed for that purpose. Most of them aim at randomizing the power consumption of the device by arbitrarily altering the processing time of the sensitive variables, making the traces desynchronized with respect to their interesting part. Such misalignment techniques reduce the dependency between the leakage and the secret and complexify the attacks, especially the ones based on univariate statistics. Software-level methods for randomizing the power consumption include the shuffling of independent operations [VC+12], the insertion of dummy instructions [CK09; CK10] or the code polymorphism [Bel+18b] which combines many interesting techniques. Hardware-level methods include instruction randomization through the use of non-deterministic processors [IPS02; MMS01] or the enhancement of a jittering effect via a clock with unstable frequency, or via an asynchronous logic style [Moo+02; Moo+04].

FIGURE 1

 1 FIGURE 1.3: A simple neural network architecture

  how to exploit it to retrieve a secret. If such an upper bound may be approached in the context of supervised attacks, it is much less straightforward for unsupervised attacks. Since MINE constitutes a new leakage assessment technique, we naturally derive it as an unsupervised model-based attack, the Neural Estimation Mutual Information Analysis (NEMIA) in Chapter 3. It revisits the classical MIA, mitigating some common misconceptions about its genericity with respect to the adversary's leakage model a priori, and conducting an in-depth analysis related to the optimal choice of the model in a multidimensional context. While NEMIA bridges the good properties of mutual information and the power of the latest DL techniques, it appears that it has two major practical drawbacks: the time complexity (it requires as many network trainings as there are key candidates) and the need for an explicit model which requires a strong a priori. In Chapter 4, we derive from the mathematical framework developed for NEMIA, a new deep learning architecture, denoted the EVIL machine, able to automatically recover the leakage model of a device. Such a machine is then turned into an unsupervised attack: the EVIL Machine Attack (EMA). It combines the good properties of the stochastic attacks (flexibility on the a priori) and the potential of DL techniques while requiring only one network training, thus overcoming the two main issues of NEMIA and of DL model-based attack in general.

  parameters Choose b a batch size such that b | n repeat Generate B = {(z 1 , ℓ σ(1) ), . . . , (z n , ℓ σ(n) )} with a random permutation σ Divide A and B into n b packs of b elements: A 1 , . . . , A n b and B 1 , . . . , B n b

FIGURE 2 . 1 :

 21 FIGURE 2.1: Evolution of MINE's loss function over time

  Figure 2.5 shows this phenomenon: training has been intentionally let running for a longer time in these experiments and MINE overestimates the MI at the end of the training.

2. 3 .

 3 FIGURE 2.5: Over estimation of MINE at the end the training (overfitting)

  FIGURE 2.6: Two possible strategies against overfitting

FIGURE

  FIGURE 2.7: Leakage evaluation of an unprotected AES

  FIGURE 2.9: Cartography of the MI between instructions and traces estimated by MINE on a PIC16F

  tried to use the Hamming weight as well as the identity function for f (they were attacking the output of a DES S-box, therefore a non-injective intermediate variable). The Hamming weight produced better results. Their justification is that the Hamming weight is closer to the underlying leakage Chapter 3. Revisiting Mutual Information Analysis: Multidimensionality, Neural Estimation and Optimality Proofs model of the circuit. We do not find this justification straightforward especially in a multivariate context since even in the ideal case where the leakage could be expressed as: L = [HW(Z k * ⊕ M), HW(M)] (3.41)

3. 4 .

 4 Neural Estimated Mutual Information Analysis (NEMIA) 57 Since, Theorem 5 tells that P( L = [a n , b n ] | z) = P( L = [a n , b n ] | HW(z)): P(l | z) = ∑ n∈N c P(n) • P( L = [a n , b n ] | HW(z)) P(l | z) = ∑ n∈N c P(n) • P( L = ln | HW(z)) P(l | z) = P(l | HW(z)) (3.65)which concludes the proof.

3.

  Compute I(H k , L), for all k, with MINE 3 . This implies to run 256 neural network trainings. 4. Rank the key hypotheses. For masked implementation, the only step that changes is the construction of H k . If the shares have a Hamming weight leakage model, Theorem 5 proves that it is sound to use the Hamming weight of the corresponding unmasked intermediate variable in H k (one may do this for multiple intermediate variables). For a generic leakage model of the shares, the best strategy to adopt remains an open question.

  6. A classical deep learning supervised attack [MPP16], denoted DL-supervised, where a network is train to classify amoung the 256 classes. The total number of traces is divided into 80% for training and 20% for the actual attack. The architechture of the network is depicted in Appendix B.

Figure 3 .

 3 Figure 3.2 shows the evolution of the average rank of k * for each attack. Each point represents the average over 100 attacks computed with traces randomly drawn from the 100k traces dataset. It appears that for low numbers of traces, CPA performs the best amoung the unsupervised attacks but this is not very meaningful since attacks with such guessing entropies (greater than 20 on a single key byte) are not really exploitable for a full key recovery. Deep learning attacks behave more like if they had a threshold: after a certain number of traces, one can observe a quick drop in their guessing entropies.As predicted by the theory, NEMI A Full converges faster towards a ranking of 0 than NEMI A Partial , and both converge faster than CPA. NEMI A Partial outperforms DDLA and also the supervised DL attack with a restricted number of traces for profiling. This may seem counter-intuitive but in this case we argue that the learning

  3.72)which is surprising since HW is highly non-injective and should at first glance, decrease the information. Corollary 2 says that this is even true when multiple samples leak a noised version of the Hamming weight of the shares. To verify this claim, 100k synthetic traces have been generated considering the following leakage:L = HW(Z k * ⊕ M) + N 1 , . . . , HW(Z k * ⊕ M) + N10 , HW(M) + N 11 , . . . , HW(M) + N 20 (3.73) with Z k * = Sbox(k * ⊕ P), N i = N (0, 1) and M being uniformly distributed in Z/256Z.

Figure 3 .

 3 Figure3.3a shows the evolution of the loss function for both the HW and the identity function for the correct key hypothesis. As predicted, both converge towards the same value which confirms experimentally that the application of the HW

  FIGURE 3.4: Analysis of the ASCAD leakage model: a) Test from remark 5 -b) & c) Coeficients of a linear regression on the given variable

  Figures 3.4b and 3.4c show the evolution of the α i coefficients, on a leakage window for both shares. Since the implementation is protected by a Boolean masking, a mono-bit leakage is exploitable only if it is present on the same bit of both shares. Out of the 8 bits, bit 0 (LSB) is clearly the one that leaks the most information since its coefficients are among the greatest ones in both shares. Thus, we computed with MINE I(Z k * [0], L) where Z k * [0] represents the LSB of Sbox(k * [3] ⊕ P[3]). It returned 0.09 bit, which is two times more than the information left with the Hamming weight (see Figure 3.4a).

  2. A second-order MIA with a LSB model computing the MI with the histogram method described in[START_REF] Batina | Mutual Information Analysis: A Comprehensive Study[END_REF] with 9 bins. 3. NEMIA with LSB as a partition function. The architechture of the network is depicted in Appendix B. 4. The Differential Deep Learning Analysis (DDLA) using the accuracy as distinguisher and with LSB as partition function. The architechture of the network is depicted in Appendix B.

  FIGURE 3.5: Guessing entropies for the considered attacks on ASCAD with added noise

Figure 3 . 5 .

 35 Figure 3.5. They confirm that NEMIA is able to succeed in situations where the considered state of the art attacks would not.As for the experiment in subsection 3.5.3, the DL-Supervised attack performs worse than the unsupervised attack which is non-intuitive. However, an adversary performing a supervised attack would likely have an unlimited amount of traces for profiling which will give rise to the best attack in terms of attack traces. We lack traces to compute the equivalent of DL-Supervised ∞ for such noise level. It appears that the application of the partition function (the LSB which only has two classes) makes the training easier for the networks which explain why a DL model, with a restricted number of traces for profiling, underperforms compared to the supervised attacks. Obvioulsy the partition function could be applied even in the supervised case (i.e. building a two classes classifier) but one would then loose the interest of being in a supervised context where no assumption has to be done on the leakage model.

"

  whose goal is to derive the optimal MI-based attack working with high-dimensional traces. Combined with recent breakthroughs on neural MI estimation techniques, this allows to mount a new attack: the NEMIA, which benefits from both the strength of deep learning and information theory. Being able to exploit at the same time multiple leakage sources, it pushes the amount of effectively used information (depending on the strength of the attacker a priori) closer to the actual existing information between traces and secret. Simulations and real case experiments are presented to support the mathematical theory developed in this chapter. They also show that NEMIA outperforms classical uni/bivariate side-channel attacks and that this strategy may be worth to consider in lowinformation/high-noise situations, where all (or a large part of) the available information contained in traces need to be used to mount a successful attack.Several lines of research emerge from this chapter. The mathematical analysis could be further extended, especially in the context of masking, in order to develop strategies for generic leakage model of the shares or for other masking schemes such as arithmetic masking. On the practical side, integrating the latest optimization on neural estimation techniques, as well as deep learning research on optimal networks architecture and hyper-parameters would allow to mount more efficient attacks, taking as input larger portion of the traces, leading to better/easier attacks.The two main difficulties of conducting a NEMIA in practice is the choice of the partition function, which can be hard when the adversary has very low knowledge on how the device leaks, and the time complexity of the attack since it requires 256 neural network trainings. The next chapter proposes a solution to tackle both problems at the same time. Insanity is applying a singular dimensional answer to a multi dimensional experience."David AultUnsupervised side-channel attacks allow extracting secret keys manipulated by cryptographic primitives through leakages of their physical implementations. As opposed to supervised attacks, they do not require a preliminary profiling of the target, constituting a broader threat since they imply weaker assumptions on the adversary model. Their downside is their requirement for some a priori knowledge on the leakage model of the device. On one hand, stochastic attacks such as the Linear Regression Analysis (LRA) allow for a flexible a priori, but are mostly limited to a univariate treatment of the traces. On the other hand, model-based attacks require an explicit formulation of the leakage model but have been extended to multidimensional versions allowing to benefit from the potential of Deep Learning (DL) techniques (see NEMIA in the preceding chapter). The EVIL Machine Attack (EMA), introduced in this chapter, aims at taking the best of both worlds. Inspired by generative adversarial networks, its architecture is able to recover a representation of the leakage model, which is then turned into a key distinguisher allowing flexible a priori. In addition, state-ofthe-art DL techniques require 256 network trainings to conduct the attack. EMA requires only one, scaling down the time complexity of such attacks by a considerable factor. Simulations and real experiments show that EMA is applicable in cases where the adversary has very low knowledge on the leakage model, while significantly reducing the required number of traces compared to a classical LRA. Eventually, a generalization of EMA, able to deal with masked implementation, is introduced.

  Another type of strategy, denoted the model-based attacks, requires the a priori on the model to be expressed as an explicit function (a.k.a. the partition function in Chapter 3). A famous example would be the classical Mutual Information Analysis (MIA) [Gie+08]. Some attacks of this category have recently been extended in order to use deep learning techniques (NEMIA or [Tim19; ZLG21]) allowing to take advantage of the multidimensional treatment of the traces. It reduces at the same time the need for preprocessing with for example filtering or realignment techniques. The preceding chapter showed that such attacks can exploit a larger part of the information contained in the traces and may outperform state-of-the-art stochastic attacks. However, they suffer from two major drawbacks: • The choice of the partition function which is closely related to the leakage model a priori. Indeed, each bit of the intermediate variable can have very different leakage behavior (especially when it comes to Electro-Magnetic (EM) 4.2. Learning a Leakage Model Representation 71 measurements) and even sign inversions of their coefficients [CLH20]. In these cases, a classical Hamming weight a priori may lead to unsuccessful attacks where an LRA would work.

FIGURE 4

 4 FIGURE 4.1: The EVIL Machine Architecture

  which estimate both MI terms of Equation 4.4. Their difference is used as an objective function for the encoder. If all the objective functions are correctly optimized (with usual deep learning techniques), E should converge toward an element of F opt , potentially close to a bijection of φ. In theory, on entire execution of MINE A and B should be run after each epoch of E which would be very long. So we decided to mimic the idea found in the field of GANs [Goo+14] and run successively one epoch of E and one epoch of A and B (in parallel) hoping that this strategy accelerates the convergence without worsening the results.

  ing the TensorFlow library[al.15]. The precise architecture of each network is depicted in Appendix C. In order to validate the methodology and gain intuition about the network behavior, this section provides simulation experiments on synthetic traces generated with different leakage models. The idea is to observe the evolution of the output of E over the training epochs and to compare it to the known underlying leakage model to assess if that is converging toward a bijection of φ.

  Figure 4.2. For each epoch, we plot E(z) for all z ∈ Z. Each of these 256 values are colored according to their Hamming weight. The first observation is that the encoder is learning to cluster the different values of Z according to their Hamming weight. It thus correctly learns a bijection of the true leakage model. It should be noted that E clusters the Hamming weight classes inorder which was not guaranteed by the mathematical analysis. The latter result being robust over multiple simulations, we conjectured that such a representation is "simpler" in a way and naturally emerges from the gradient descent algorithm.

FIGURE 4. 2 :

 2 FIGURE 4.2: Evolution of the encoder's output: E(z), ∀z ∈ Z versus epochs (Hamming weight leakage model).

FIGURE 4. 3 :

 3 FIGURE 4.3: Evolution of the encoder's output: E(z), ∀z ∈ Z versus epochs (linear leakage model).

(

  FIGURE 4.4: Evolution of the encoder's output: E(z), ∀z ∈ Z versus epochs (multidimensional leakage model).

FIGURE 4. 5 :

 5 FIGURE 4.5: Evolution of the encoder's output: E(z), ∀z ∈ Z versus epochs (non-linear leakage model).

FIGURE 4. 6 :

 6 FIGURE 4.6: Evolution of the encoders' output for the correct and a wrong key guess.

  )

FIGURE 4. 7 :

 7 FIGURE 4.7: Evolution of the distinguisher D(k) versus epochs for all the key candidates.

  ulations and real case experiments aiming at comparing both attacks in order to assess to what extent the deep learning step is valuable. Both attacks are unsupervised and require very limited knowledge on the leakage model of the target. The main advantage of EMA over LRA is the multidimensional treatment of the traces.

  3.3 for each value of 0 ≤ σ ≤ 25. Results are presented in Figure 4.8a. Each point represents the average rank of the Algorithm 3: Generate Traces Input: σ Output: L, a (10k, 100) array Output: P, a (10k) array P ← Draw 10k plaintext uniformly from 0, 255 Z ← Sbox[P ⊕ k * ] L ← Draw a (10k, 100) array from a Gaussian N (0, σ 2 ) R ← Draw a (20, 8) array of random coefficients from U [-1, 1]

  FIGURE 4.8: Guessing entropies of EMA and LRA.

  FIGURE 4.9: Evolution of the encoder's output: E(z), ∀z ∈ Z on masked synthetic traces (linear leakage model of the shares).

  tations[START_REF] Dabosville | A New Second-Order Side Channel Attack Based on Linear Regression[END_REF]. Authors presents a higher-order version of the LRA, the HO-LRA, by proposing to perform the LRA on the estimated joint moment per class instead of the raw traces. In Chapter 5, we highlight some limitations of the previous works and propose a new strategy which directly regresses the leakage model of each share with the Joint Moment Regression (JMR) strategy. Both attacks use an estimation of the jm L function calculated under a key assumption as input to the method. Therefore we argue that these attacks could be conducted on the output of the encoders of the EVIL machine. Indeed, as suggested in the previous section, E k * (Z) could be seen as a representation of the jm L function under the correct key assumption. The trick introduced in subsection 4.3.1 still apply and all the E k can be derived from only one network training.Again, the main advantage of the EMA is that these representations benefit from all the deep learning techniques. In addition, in classical d-variate attacks, the adversary should select the d samples from the traces to combine and perform the joint moment estimation. In a complete black-box setting, with no information on the point of interests, the latter has to enumerate all the possible d-(upplet) samples and select the best one which can be very long and scale exponentially with d. The EMA does not suffer from the same problem since the whole (or at least a big part of) traces can be fed to the network.

  [START_REF] Benadjila | Study of deep learning techniques for side-channel analysis and introduction to ASCAD database[END_REF]. It is a common set of side-channel traces, introduced for research purposes on deep learning-based side-channel attacks. The targeted implementation is a software AES, protected with a first-order Boolean masking, running on an 8-bit ATMega8515 board. Since JMR and the HO-LRA are equivalent for the second-order Boolean case, as shown in the next chapter, we adopt the HO-LRA strategy which is simpler. It just consists in conducting an LRA on the estimated covariance or on E k for the EMA case. It is therefore the exact same attack as for the first-order case described in subsection 4.3.3. We ran the EMA on 10k of the training traces which consist of 700 samples targeting the first Sbox. Results are presented in Figure4.10a. The attack is successful with a clear distinguishability for the correct key.

(

  A) Evolution of the distinguisher D(k) versus epochs for all the key candidates. (B) Evolution of the encoder's output: E(z), ∀z ∈ Z colored according to the LSB of z.

FIGURE 4 .

 4 FIGURE 4.10: Attack results on ASCAD with 10k traces.

  This chapter presents a new unsupervised side-channel key recovery strategy denoted the EVIL Machine Attack (EMA). It is built on a GAN-like structure that aims at converging towards a representation of the leakage model of the device under a key assumption. Occam's razor's principle allows to derive from this tool an actual attack enabling the utilization of deep learning's potential while requiring very few knowledge on the leakage model. For example, a simple linear leakage assumption is enough as in a classical LRA. It requires only one network training where classical unsupervised deep learning strategies require as many trainings as key guesses (256 when targeting a key byte). Thus EMA reduces significantly the time complexity while being more flexible in the leakage model a priori than unsupervised DL based attack. This may lower the barrier for conducting such kind of attacks in practice. Simulations and real cases experiments suggest that the additional information brought by the multidimensional treatment of traces is beneficial and translates into more data-efficient attacks than the classical LRA. For example, it lower by more than 400% the number of required traces in the real case scenario targeting the openSLL implementation of the AES running on a SoC.

1. 1 |L x | ∑ ℓ∈L x ℓ 3 .

 13 Partitioning. Partition the traces into |X | classes: L x = {ℓ i , x i = x}. 2. Averaging. Compute the average trace for each class L = ( lx ) x∈X with lx = Basis choice. Choose a basis of functions (b i ) 1≤i≤r such that b i : Z → R.

Proposition 5 .

 5 (Boolean masking) Let * = ⊕. Let l 1 : Z → R and l 2 : Z → R be two leakage functions of degree 1. Let φ Bool

Procedure 1 .

 1 Partitioning. Partition the traces into |X | classes:

0≤b≤8( 5

 5 .15) where all the α a,b are uniformly drawn from [-1, 1]. Each row represents a different linear leakage model.

  FIGURE 5.1: Guessing entropies versus standard deviation of the noise for the considered second-order attacks after the processing of A) 2 16 , B) 2 16 , C) 2 8 × 255 traces.

2

  FIGURE 5.2: Guessing entropies versus standard deviation of the noise for the considered third-order attacks after the processing of A) 2 24 , B) 2 24 , C) 2 8 × 255 2 , D) 2 16 × 255 traces.

  of g k * (and therefore the covariance matrix) only comes from the right term of Equation 5.23 which does not depend on θ. Therefore the equation of Ω can be re-written as:Ω = cov-mat e X d ∏ i=1 (L iμi ) (5.25) 3Here x ∈ X = F m 2 is seen as an element of Z/2 m Z.

FIGURE 5 . 4 :

 54 FIGURE 5.4: Comparison of different attacks' guessing entropies on ASCAD

tory [ Ben+19 ]

 Ben+19 , one can simulate (through the knowledge of the key and the permutation Sh being used) an attack on an unshuffled version even if the acquired traces are shuffled. Instead of targeting the first byte Z = Sbox[k * [0] ⊕ P[0]] one may target:Z = Sbox[k * [Sh -1 (0)] ⊕ P[Sh -1 (0)]](5.27)

  both the shuffled and unshuffled versions. The attacks on the shuffled version only use the leakage of the first Sbox computation. Shuffling adds a lot of noise since even for the correct key hypothesis the predicted value of Z is only correct once out of 16 in average. Results are presented in Figure 3.4. Each point represents the mean ranking of the correct key over 100 attacks performed with the corresponding number of traces.

FIGURE 5 . 5 :

 55 FIGURE 5.5: Comparison of different attacks' guessing entropies on the secured ANSSI's AES

  As a second contribution, Chapter 3 presents NEMIA which is an extension of this new tool to the context of unsupervised attacks, aiming at recovering a cryptographic key. It revisits the classical mutual information analysis, in a multidimensional paradigm. It provides rigorous proofs whose goal are to derive the optimal MI-based attacks that deal with high-dimensional traces. NEMIA is the first unsupervised attack able to benefit at the same time from the framework of information theory and the potential of deep learning (multidimensional treatment of traces, reduces the need for preprocessing, adaptable architectures...). Being able to combine information from multiple sources, NEMIA outperforms classical strategies and may be worth considering especially in low information/high noise scenarios, where all (or most) of the available information contained in the trace needs to be exploited to conduct a successful attack.Chapter 6. General ConclusionFrom a practical point of view, the two main drawbacks of NEMIA are: its computational complexity, requiring as many network trainings as there are key candidates, and its requirement for a strong leakage model a priori. Chapter 4 proposes, as a third contribution, a new attack strategy, the EVIL Machine Attack (EMA), which is built to overcome these two problems. The EVIL machine is a network architecture, inspired by generative adversarial networks, whose aim is to produce a representation of the leakage model of the device. It is derived as an unsupervised attack combining techniques from the stochastic attacks which allows for a more flexible a priori. In addition, EMA requires only one network training, which may be a game changer regarding unsupervised deep learning-based attacks. Simulations and real case experiments confirmed its practicable applicability showing significant improvement compared to classical stochastic attacks.

  since the denominator P(L) is independent from the key and would not change the ranking. A classical example of generative models used in supervised attacks is the Gaussian template attacks[START_REF] Chari | Template attacks[END_REF] which estimates each class P(L|Z = z) assuming that it is a multivariate Gaussian distribution. Deep neural network based attacks, mentioned in subsection 1.3.2, constitutes a common example of discriminative model.

  Another type of strategy, denoted the Model-Based Attack (MBA) in this thesis, partitions the set of traces into classes, collapsing traces that should have a similar leakage according to an a priori model M. Such partition is done under a key hypothesis k and it corresponds to re-label the traces with M(Z k ) instead of Z k . Then a leakage assessment technique S

	M(Z k ) L	can be used as
	a distinguisher considering the new labels. If the model is sound the maximum
	leakage should be reached when the partition has been done with the correct key
	hypothesis.

1.2. Side-Channel Analysis

Model-Based Attacks.

  Information Theory good theoretical properties of neural networks into practical results, for example, by providing new architectures or optimizations in the learning process. Such improvements in the DL techniques directly impact the DL-based SCA. For example,[START_REF] Cagli | Convolutional Neural Networks with Data Augmentation Against Jitter-Based Countermeasures[END_REF] showed that the Convolutional Neural Networks (CNN), originally developed for computer vision due to their shift-invariant properties, can be applied to counter misalignment in side-channel traces.Many works (not always reproducible...) have followed essentially in the field of supervised attacks. However, such a classification method could very well be turned into a leakage assessment technique. Indeed, a network predicting the Z variable from L better than random indicates that a leakage occurs in L with respect to Z. This is essentially what is done in[START_REF] Moos | DL-LA: Deep Learning Leakage Assessment: A modern roadmap for SCA evaluations[END_REF] except that they fix only 2 classes for Z and try to predict them. Since any leakage assessment technique can be turned

tion theorem

[START_REF] Hornik | Multilayer feedforward networks are universal approximators[END_REF]

that even a one (hidden) layer Multi Layer Perceptron (MLP) can approximate any given function with an arbitrary precision (provided that the layer size is not bounded). This means that neural networks can deal, in theory, with big parts of the traces, automatically learning how to combine multiple samples if necessary, while reducing the need for preprocessing techniques. The initial work from Maghrebi et al.

[START_REF] Maghrebi | Breaking Cryptographic Implementations Using Deep Learning Techniques[END_REF]

introduced them to SCA in order to deal with potential non-Gaussian distributions, especially in the context of masking and showed they were a sound alternative to Gaussian template attacks in practice.

The advantage of DL techniques is not only theoretical. Indeed, DL has been a very active field for this last few years and many works focus on turning the 1.4. into an unsupervised model-based attack, such DL-based leakage assessment have their corresponding unsupervised attack introduced in [Tim19] (one may notice the inconsistency in the date of publication of these two papers). The main problem of

  previous chapter took advantage of a new deep learning technique called Mutual Information Neural Estimation (MINE)[START_REF] Ishmael | Mutual Information Neural Estimation[END_REF] to develop a side-channel tool able to reliably estimate the MI between the secret and full traces. It drastically reduces the impact of high dimensionality on the estimation reliability compared to classical estimators. This tool allows one to get an absolute leakage quantification from raw traces which is helpful for designers or evaluators to perform leakage assessment. However, knowing how much information is potentially usable is different from actually exploit it. This chapter analyzes the impact of this tool from the attacker's point of view. Is an adversary also able to use the inherent multidi-second version of the MIA allowing to target any intermediate variables (and is therefore applicable in many more contexts) has also been developed. These two versions are not separated in the literature but we decided to do so in this paper to clarify the relationship between MIA and leakage model a priori. Indeed, this second version is not leakage model free i.e. it requires an a priori on the leakage model to work. However, one of the main advantages of this attack is that it is not limited to linear leakage model and more generally, does not require any assumption on the leakage distribution (as long as the adversary's a priori is sufficiently correct).However, this gain in genericity comes at the cost of efficiency: CPA has always been proved to work better than MIA in classical attack scenarios since leakage models are often linear. Therefore MIA is more seen as a great tool in theory that does not offer much in practice.

	The Linear Regression Analysis (LRA) [Dog+12] also assumes a linear dependency
	but can handle different weights for each bit of the intermediate variable.
	Mutual Information Analysis (MIA), however, has been introduced as a generic
	strategy able to capture any kind of dependencies. Papers addressing the theoretical
	background behind MIA [Gie+08; PR09; VCS09; Bat+11] all present MIA as SCA
	distinguisher able to recover the correct key without any knowledge on the target
	nor on its leakage model. However, this leakage model free strategy only works to

mensional properties of MINE to exploit at the same time all the potential leakage sources ? And if so, what is the optimal way to do it ? This chapter aims at answering these questions.

Side-channel attacks are mainly divided into two categories: supervised SCA, where the adversary can first perform a characterization of the target, and unsupervised SCA in which this profiling step is not possible. For profiled SCA, one is theoretically able to exploit all the information I(Z, L) by perfectly learning the target's leakage model during the characterization phase. Deep learning attacks have been shown to effectively extract all the available information when using the negative log likelihood as loss function

[START_REF] Masure | A Comprehensive Study of Deep Learning for Side-Channel Analysis[END_REF]

. Therefore the problem is closed, at least in theory, for profiled SCA. However, this is not the case for unsupervised attacks, where the true leakage model of the target is unknown to the adversary. In this situation, only a fraction of I(Z, L), which value depends on the correctness of one's a priori on the leakage model, can be exploited. For example, the Correlation Power Analysis (CPA)

[START_REF] Brier | Correlation Power Analysis with a Leakage Model[END_REF]

is efficient for linear dependencies between the leakage and a certain function of the intermediate variable (often being the Hamming weight function). target non-bijective intermediate variables which makes it well suited for the DES (as the DES S-boxes are not bijectives) but less suited for more recent algorithms such as the AES. This explains why MIA has not often been used in practice. A However, one of the main advantages of MIA is that it generalizes well to higher dimension variables and offers a way to potentially use a bigger part of the information contained in a side-channel trace. This has not really been used in the literature (except to extend MIA for masked implementation [PR09; Bat+11]) due to MI estimators limitations. But recent breakthroughs regarding neural estimation encourages to revisit classical MIA in order to make it highly multidimensional, to get closer to an optimal attack regarding the amount of information being used from the traces.

Even if neural estimation techniques can be applied in the leakage model free version of the MIA, we are more interested in the second version of MIA since it does not impose restrictions on the targeted algorithm. However, we argue that the mathematical framework behind this version (developed in [Gie+08; PR09; VCS09;

  Now using the independence of N and the fact that φ(Z k * ) is entirely determined by Z k This strategy does not require any assumption on the leakage model of the target. However, it only works if the correct key hypothesis is distinguishable from the other ones, or, in other words, if D(k) < D(k * ), ∀k ̸ = k * , which is not guaranteed by Proposition 1. An important property of the MI is that it is preserved by injective transformations of the input variables. So if different key hypotheses yield Z

	≥ 0	(3.5)
	which concludes the proof.

* : D(k * ) -D(k) ≥ H(N) -H(N) k variables differing from each other only by a permutation (for example if the g k functions are bijective), I(Z k , L) would be constant for all k and the distinguisher could not discriminate key candidates. Therefore, g k has to be non-injective. For example, one could target the output of the first round DES S-box.

While this form of MIA is effectively leakage model free, it comes with a huge constraint since in many interesting cases g k is bijective. In the AES case, this means that one cannot target the output of the first S-box since Sbox[k * ⊕ P] is bijective with P. In

[START_REF] Prouff | Theoretical and Practical Aspects of Mutual Information Based Side Channel Analysis[END_REF]

and

[START_REF] Reparaz | Generic DPA Attacks: Curse or Blessing?[END_REF]

, authors suggest to target the bitwise addition between two S-box outputs during the MixColumns operation. This requires making hypotheses on 16 bits of the key (leading to 2 16 MI computations). Moreover, it is only feasible if this operation leaks enough information which may not be the case in practice. Indeed, for hardware implementations, this step is usually fully combinatorial and does not use any register. This explains why most of the MIA experiments in the literature have been performed on the DES.

  is unknown, the adversary can still use Equation 3.28 estimating I φ(Z k ), L for all k, and comparing the maximum with I Z k 0 , L (k 0 can be chosen randomly since all the Z k variables are just permutation of each other which does not affect MI). Note that this test is only a rejection test since passing the test does not guarantee a good estimation of φ: for example, the identity function always passes the test.

.28) Then, if k * is known (for example in an evaluation setup) one can use Equation 3.27 and estimate I Z k * , L and I φ(Z k * ), L and compare them. If the latest is too far from I Z k * , L , one may reject φ as being a good approximation of the true underlying leakage model. If k *

  34) Chapter 3. Revisiting Mutual Information Analysis: Multidimensionality, Neural Estimation and Optimality Proofs Using H(A | B) ≥ H(A | C) -H(B | C) which can be shown through information Venn diagram:

  The d -1 shares Z 2 , ..., Z d are randomly chosen and the last one, Z of at least d samples of the traces (assuming masks do not leak at the same time). Higher-order correlation attacks[START_REF] Messerges | Using Second-Order Power Analysis to Attack DPA Resistant Software[END_REF] exploit a combining function, C : R d → R , which transforms a multidimensional leakage into a single value such that the output of C correlates with Z. The optimal combining function is unknown but most of the time, the centered product between the shares is used[START_REF] Prouff | Statistical Analysis of Second Order Differential Power Analysis[END_REF].

1 , is processed such that Equation 3.38 is satisfied. Assuming the masks are uniformly distributed, the knowledge of d -1 shares does not tell anything about Z. However, partial knowledge on the d shares can be exploited to retrieve information on Z. That is why, to defeat masking, one should use a distinguisher able to combine 3.3. MIA Against Masked Implementations 51 the leakage

  . Define an a priori φ on the leakage model. It can be multidimensional if mul-

	tiple intermediate variables related to the key leak information. Also, a single
	intermediate variable can have different leakage models at different times. The
	test described in subsection 3.2.6 can be used to detect wrong a priori. Even if
	MIA is tolerant regarding estimation errors on φ, better a priori lead to more
	efficient attacks.

2. Compute, for all k, the hypothesis vectors:

H k = φ(Z k ).

  Partial , only considering the Hamming weight leakage (A k ) to construct the hypothesis vectors H k = A k : 4. NEMIA Full , considering both leakages (A k and B k ) to construct the hypothesis vectors H k = [A k , B k ].

	Chapter 3. Revisiting Mutual Information Analysis: Multidimensionality, Neural
	Estimation and Optimality Proofs
	Compared Strategies
	We used the generated dataset to compute and compare guessing entropies for the
	following attack strategies:
	1. A classical CPA [BCO04] with a Hamming weight model.
	2. A classical MIA with a Hamming weight model computing the MI with the
	histogram method described in [Bat+11] with 9 bins.
	3. NEMIA
	Algorithm 2: Generate Traces
	Output: L, a (100k, 1010) array
	Output: P, a (100k array
	P ← Draw 100k plaintexts uniformly from 0, 255
	end
	end
	R ← Draw an array (100k, 1010) of random number from a Gaussian
	N (0, 20 2 )
	end
	return L, P

A ← HW(Sbox[P ⊕ k * ]) B ← HW(Sbox[k * ⊕ P] ⊕ (k * ⊕ P)) S ← Draw 1010 samples from a GaussianN (0, 10 2 ) // Generate a baseline shape L ← Repeat S 100k times to form a (100k, 1010) array for 1 ≤ i ≤ 100k do for 1 ≤ j ≤ 50 // Add leakage one every 10 samples do L[i, 10 * j] ← L[i, 10 * j] + A[i] L[i, 10 * j + 500] ← L[i, 10 * j + 500] + B[i] L ← L + R // Add some noise for 1 ≤ i ≤ 100k do sh ← Draw a random integer uniformly from 0, 10 L[i] ← Roll(L[i], sh) // Apply the jitter (Roll shift the array by sh) 5. The Differential Deep Learning Analysis (DDLA) introduced in [Tim19]. It is sound to compare NEMIA to DDLA since both methods use deep learning with an unsupervised approach. It builds 256 classifiers, one for each key hy-

TABLE 5

 5

	.1: Masking schemes studied in this work

The centered product is related to the d-order centered joint moment of a distribution and thus, may keep d-order statistical information.

Note that other criterion such as the distance with the mean of the wrong hypotheses could also have been used without modifying the analysis as discussed in remark 4.

For robustness, the MI estimation is not set to be the supremum of the validation loss, but instead, the supremum of a moving average along the epochs off the validation loss with a window size of w which depends on the variability between epochs (w = 10 in this chapter)

through the relation: Z = g(X, k * ) where g : X × K → Z is a known function

Cryptographic algorithms should embed highly non-linear transformations to avoid algebraic attacks and we assume here that the targeted sensitive variable has undergone this non-linear transformation, for example, Z = SBOX(X ⊕ k * ).

For reproducibility reasons and potential use in the SCA community, the dataset with the associated labels is accessible on this link: removed for blind reviews.

Higher-order moments being harder to estimate due to noise amplification.

One may notice that the other attacks perform better than in the simulated experiments. We explain this by the fact that in this case, the leakage model is fixed and may be closer to a Hamming weight model.

Acknowledgements

Acknowledgements v

, if HW(m) + HW(z) -HW(z ⊕ m) ∈ 2N

-1, otherwise (3.51) so that ∀m ′ ∈ M, n m ′ = n.

Reciprocally, one can see that each byte m ′ such that HW(m ′ ) = HW(m) and n m ′ = n is in M. So to form a valid m ′ ∈ M one has to choose first the position of the n '1s' superposing with the '1s' in z, which lead to ( HW(z) n ) possibilities. Then, choose the positions of the remaining '1s', which lead to ( 8-HW (z) HW(m)-n ) possibilities. Therefore, with the convention ( l k ) = 0 when k is strictly negative:

Injecting this into Equation 3.47 gives: Now using result from Equation 3.52:

since all the terms are constant in the sum and there are exactly ( 8 HW(z) ) of them. Now plugging this into Equation 3.54 gives:

Proposition 6. (Arithmetic masking) Let * = + mod 2 n . Let l 1 : Z → R and l 2 : Z → R be two leakage functions of degree 1. Let φ Arith (z) = cov l 1 (z + Z 2 [2 n ]), l 2 (Z 2 ) . Then, deg(φ Arith ) ≤ 2 (5.7)

Proof can be found in Appendix D.

These two propositions explain the success of the attacks presented in [START_REF] Dabosville | A New Second-Order Side Channel Attack Based on Linear Regression[END_REF].

However, we could not find equivalent propositions for other masking schemes, suggesting that Boolean and arithmetic masking are, in fact, exceptions. This will be empirically confirmed in subsection 5.3.4 where it is shown that even without noise, the higher-order LRA fails against multiplicative or affine masking with a linear leakage of the shares. Therefore, to the best of our knowledge, there is no strategy in the literature able to defeat a generic masking scheme in an unsupervised context, with a simple linear leakage assumption of the shares. We introduce such a strategy in the next section.

Joint Moments Regression

We first introduce the concept of Joint Moment (JM) which generalizes to any masking order the idea of the covariance, found in the previous section.

Joint Moments

Moments of probability distributions are quantitative measures related to the shape of the distribution. The moment of order d, denoted µ d , of the variable X is defined as:

For second and higher orders, the centered moments μd of order d are often used instead and are defined as:

Joint moments are the generalization of moments to multivariate variables. Let X = (X 1 , . . . , X n ) ∈ R n be a multivariate random variable. Let u = (u 1 , . . . , u k ) ∈ N n be a vector of positive integers such that ∑ u i = d. The JM of order d with respect to vector u, denoted jm u , is defined as:

Centered JM are also defined as:

(5.11)

Chapter 5. Fit the Joint Moments: How to Attack any Masking Scheme leakage of the shares and is therefore directly related to the physical a priori. These assumptions are then combined to build a parameterized system of unknown θ ∈ R d×r :

where each line represents a condition on the JM knowing that X = x. Note that by the independence assumption, the noise terms ϵ j are canceled from the theoretical equations of the JM per class, listed in the J M k (θ) vectors. The goal is then to find the solution θ (k) that fits the most the system and to use a measure of fitness as distinguisher. Note that the knowledge of the underlying masking scheme is embedded in the system through the A x sets which describe the possible values (z 1 , . . . , z d ) of the shares given the value of Z. This is what ensures the genericity of JMR regarding the masking scheme.

When the number of traces N tends towards infinity, the estimated JM per class J M tends towards the true JM per class. If the leakage assumptions are correct there exists θ (k * ) ∈ R d×r such that J M k * (θ (k * ) ) is equal to the true JM per class. Therefore:

while it is unlikely to be the case for k ̸ = k * due to cryptographic property of f , which assures the soundness of the attack.

However, this multi-shares assumption comes at the cost of linearity. Indeed, even if all the shares are assumed to leak linearly, the system that JMR regresses is not linear anymore: it is of degree d. Therefore there is no closed-form solution and one has to use numerical optimization tools to find an approximation of the solution.

Numerical optimization is a research field in itself and is out of the scope of this paper. There exist multiple ready-to-use implementations in different programming languages, which is enough for our concern. Note that since the system is of degree d, the uniqueness of the solution of step 5 is not guaranteed. This is not a problem for the attack: as long as one solution can be found and that equation 5.14 holds only for the correct key hypothesis, the attack will succeed for a sufficient number of traces.

Simulation Experiments

This section provides simulation experiments to assess the feasibility of JMR in practice against the masking schemes presented in table 5.1. Its efficiency is compared with state-of-the-art attacks at second and third order.

Implementation

We implemented the core of the JMR attack using the least_squares function from the python scipy.optimize package [START_REF] Virtanen | SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python[END_REF]. In addition, since for a fixed x, only one component of g k * (ℓ, x, θ) is non-zero, Ω is diagonal. Then, one can estimate the diagonal terms of Ω using the observed data and then apply GMM. We denote by JMR ++ the JMR attack with W = Ω -1 where Ω is an estimation of the optimal weighting matrix.

To confirm the soundness of this approach, we performed the same experiments as those described in subsection 5.3.4 to compare JMR and JMR ++ . Figures 3.3a and 3.3b show the results for the second-order Boolean and arithmetic masking and, according to the theory, JMR ++ performs a little better than JMR. It can be noticed that in the case of Boolean masking JMR ++ also outperforms HO-LRA-1, which has approximately the same performance as JMR, despite having more parameters to estimate.

The Case of Biased Schemes

Some masking schemes, such as the multiplicative or the affine one, violate the assumption of shares uniformity. Therefore the resilience to (d -1) th -order attack is not guaranteed anymore. For example, Z = 0 implies Z 1 = 0 in a multiplicative scheme inducing a first-order leakage. As well, when Z = 0, the affine scheme becomes a Boolean scheme of order 2 inducing second-order leakages. Since lower order JM are informative in these cases, a first idea to exploit this weakness is to apply JMR but at a lower-order. This means that the considered conditions concern only the first-order moments for a multiplicative scheme and the second-order JM 5.5. Experiments on Real Traces 109 for an affine scheme. Such an attack is denoted JMR Lower . Since this would only exploit the difference between the class Z = 0 and Z ̸ = 0 this attack would be very close to a CPA computed with a zero-valued model considering only two classes: Z = 0 and Z ̸ = 0, denoted CPA-0 (or HOCPA-0 in the affine case) afterward.

Figures 5.3c and 5.3d confirm this intuition by showing that both CPA-0 and JMR Lower behave very similarly and have better results than JMR for high noise values but worse results for low noise values. Indeed, since the main advantage of masking is to amplify the impact of the noise exponentially with the order of the mask [START_REF] Prouff | Masking against Side-Channel Attacks: A Formal Security Proof[END_REF] or more accurately, with the order of the attack required to defeat it.

For low values of σ the JM conditions used in JMR Lower are less informative than the one used by JMR (they only exploit a difference between the class Z = 0 and the other classes) but the impact of the noise is amplified by a lower order which explains the better results of JMR Lower for high σ.

A natural challenge is to design an attack benefiting from the best of both worlds:

JMR and JMR Lower . To this aim, we propose to use the flexibility of the GMM paradigm to develop an attack with conditions from both informative orders at the same time. This corresponds to building a system with 512 conditions instead of 256 when attacking a key byte. In this case, the weighting matrix is very important since each half of the system concerns conditions with very different variances (estimating joint moments is exponentially hard with the order). To highlight this fact we denote by JMR Full and JMR ++Full the version of JMR with both order conditions respectively with W = Id 512 and W = Ω -1 .

Results are presented in figures 5.3c and 5.3d. As expected, JMR Full outperforms JMR but is impacted by the variance of the d-order conditions and therefore performs worse than JMR Lower for high values of σ. However, JMR ++Full benefits from the advantage of exploiting the d-order conditions for low values of σ but still converges towards JMR Lower for high noise values thanks to the well-chosen weighting of these conditions. Indeed, it is proven in [START_REF] Peter Hansen | Large Sample Properties of Generalized Method of Moments Estimators[END_REF] that adding more moments conditions can only improve the performance of the GMM estimator (by lowering its variance) when using the optimal weighting matrix Ω -1 .

We highlight the fact that for the multiplicative scheme, there is an interest in using JMR ++Full over CPA-0 since for example it would give a successful attack at σ = 1 where CPA-0 would rank the correct key at the 20 th position which is not enumerable considering the full 16 bytes key. However, for the affine case, the curves look very similar and we argue that the overhead in time complexity of using JMR ++Full (or JMR Lower ) over CPA-0 is not worth it.

Experiments on Real Traces

Proof. Let us create a partition of Z = ⊔ n i=1 P i where two elements z 1 , z 2 ∈ Z are in the same P i if and only if:

Then, one may define f 1 as f 1 (z) = i, ∀z ∈ P i . Since f 1 only collides for z that already collides through φ, there exists f 3 such that f 3 • f 1 = φ. As f is constant on P i , let us denote by v i its output on elements of P i . Then f 2 can be defined as

which means that z a and z b are in the same P i and thus collides through f 1 . So a = b which proves that f 2 | f 1 (φ -1 ({φ(z)})) is injective. Then, considering its set of destination being its image, one can say that this function is bijective with reciprocal function:

A.2 Proof of Corollary 1

Definition 1. A function f is said wider-than g if there exists another function h such that:

Corollary 1. Let L be defined as in Equation 3.43. Then, for any function h wider than HW, S HW ≥ S¯h.

Proof. There exists h such that h • h = HW. So:

Since removing h in the second term can only increase the information:

By Theorem 5, HW maximizes over g the quantity: I g(Z k * ), L , so removing h in the first term cannot increase the information:

A.3 Complementary material on the entropy

Lemma 2. Let A and B be a two discrete random variables. Let f : A → R n be any function.

Then:

Proof. The data processing inequality [START_REF] Beaudry | An intuitive proof of the data processing inequality[END_REF] ensures that applying f to any variables can not increase its mutual information with another variable so:

Lemma 3. Let A and B be a two discrete random variables. Let f : A → R n be any function.

Then:

Proof. Again, using the data processing inequality [START_REF] Beaudry | An intuitive proof of the data processing inequality[END_REF]:

Proof. Since bijective transformations do not impact mutual information, one can consider without loss of generality that:

Now let us evaluate I f (Z k * ), L :

One can split the first sum by summing on z instead of f :

Since the identity function is bijective and maximizes this quantity, it would be enough to show that P(l | HW(z)) = P(l | z).

Let define the following propositions P n for n ≥ 1:

Let us prove P n for any n by induction. P 1 is true by Th.2. Let suppose that P n is true for a given n. Now, ∀z, m 1 , . . . , m n+1 ∈ Z let us define l:

Now by independence of the shares:

z, HW(m 1 ), . . . HW(m n-1 ),

let us evaluate the right term by summing over all the possible value of HW( m):

One can remove K 2 in A since K 2 does not add any information when HW( m) is known:

by induction property P n . Plug-in this into eq. A.15 and then in eq. A.14 gives:

which concludes the proof.

Appendix B

Networks Architecture for chapter 3

Proof. Since both l 1 and l 2 are of degree 1, there exist two unique sets of coefficients

i ) 1≤i≤n ∈ R such that:

where z[i] stands for the i th bit of z. Since the covariance involves a centered product, one can suppose without loss of generality that α (j) 0 = 0 (we removed α (j) 0 for readability reasons but it does not change anything to the proof). Injecting Equation D.2 into the expression of φ Bool :

Using the identity :

) where ∧ stands for the Boolean AND:

which is of degree at most 1 since the z[i] terms are not mixed.

D.2 Proof of Proposition 6

Proposition 6. (Arithmetic masking) Let * = + mod 2 n . Let l 1 : Z → R and l 2 : Z → R be two leakage functions of degree 1. Let φ Arith (z

Proof. We give a proof by induction. Let define the property P n :

P n : For any l 1 and l 2 of degree 1, deg(φ n ) ≤ 2, where for z ∈ Z = F n 2 :

Initialisation. The case n = 1 is trivial since deg(φ Arith ) is at most 1 in this case.

Induction. Let suppose that P n holds. We are going to prove that P n+1 also holds. Since both l 1 and l 2 are of degree 1, there exists two unique sets of coefficients (α

(1)

i ) 0≤i≤n+1 ∈ R such that:

where z[i] stands for the i th bit of z. Since the covariance involves a centered product, one can suppose without loss of generality that α (j) 0 = 0 (we removed α (j) 0 for readability reasons but it does not change anything to the proof). Injecting this into the expression of φ n+1 one has:

for i ∈ 1, n + 1 , the following identity holds:

Indeed, the modulo corresponds to either doing nothing or subtracting 2 n+1 when z + z 2 ≥ 2 n+1 . Then:

Again, one can add a [2 n ] in the (z + z 2 )[i] terms since it does not change anything for i ∈ 1, n . Then:

The second line of Equation D.9 can be re-indexed summing from 0 to 2 n -1. Then, by P n , the first two line of Equation D.9 are of degree at most 2. So let us focus on Appendix D. Proofs for chapter 5 the last term denoted A and prove that it is also of degree at most 2:

since z 2 [n + 1] = 0 implies that all the term in the sum are equal to 0. One can notice that the latter sum has two expression depending on the (n + 1) th bit of z:

11)

Therefore:

which is of degree at most 2 since developing the latter sum involves product of at most 2 bits of z together.

Injecting this into Equation D.9 show that deg(φ n+1 ) ≤ 2 and therefore that P n+1 holds. This concludes the induction and therefore the proof of Proposition 6.

For the interested reader, we give as a bonus the coefficients of φ Arith in terms of α (j) i :

With:

Abstract

Side-Channel Analysis (SCA) is defined as the process of gaining information on a device holding a secret through its physical leakage such as power consumption or Electromagnetic (EM) emanations. Whatever the utilized strategy, the amount of information one could gain from a side-channel data, called a trace, is always bounded by the Mutual Information (MI) between the secret and the trace. This makes it, all punning aside, a key quantity for leakage evaluation. Unfortunately, traces are usually of too high dimension for classical statistical estimators to stay sound when computing the MI over full traces. However, recent works from the machine learning community have shown that it is possible to evaluate the MI in high dimensional space thanks to newest deep learning techniques. This thesis explores how this new estimator impacts the side-channel domain.

The first part is dedicated to an analysis of the Mutual Information Neural Estimation (MINE) technique in a side-channel context which aim is to derive the best way of using such tool in practice. It shows that the intrinsic multi-dimensional aspect of the technique is highly valuable for SCA since there are often multiple leakage sources in side-channel traces. The method is derived as a generic leakage assessment tool that can be used whatever the type of data, device or implementation.

Knowing how much information is contained in the traces is different from knowing how to exploit it optimally to recover a secret such as a cryptographic key, especially in an unsupervised context when no profiling of the target is allowed.

Therefore, the second part of this thesis presents a new mathematical framework, designed to bridge classical Mutual Information Attacks (MIA) and the multidimensional aspect of neural-based estimators. This allows to derive, to the best of our knowledge, the first unsupervised attack able to benefit from both the power of deep learning techniques and the valuable theoretical properties of MI. In practice this attack suffers from two drawbacks : the time complexity, since it requires as many network trainings as there are key hypotheses (often 256), and a strong a priori on the leakage model of the target device.

The third part of the thesis makes use of the previously introduced mathematical framework to build a deep learning architecture able to recover by itself such a leakage model. It allows to derive a new unsupervised attack, the EVIL Machine Attack, with only one network training solving the two precedent issues at the same time.

The analysis of the EVIL machine in the context of masked implementations gave rise to questions about stochastic attacks and their generalization to higher-order versions. The last part of this thesis is dedicated to an analysis followed by a new unsupervised attack proposition, the Joint Moment Regression, which is agnostic to the underlying masking scheme as opposed to state-of-the-art techniques.