In the field of the security of the embedded systems, it is necessary to know and understand the possible physical attacks that could break the security of cryptographic components. Since the current algorithms such as Advanced Encryption Standard (AES) are very resilient against differential and linear cryptanalysis, other methods are used to recover the secrets of these components. Indeed, the secret key used to encrypt data leaks during the computation of the algorithm, and it is possible to measure this leakage and exploit it. This technique to recover the secret key is called side-channel analysis.

The main target of this Ph. D. manuscript is to increase and consolidate the knowledge on the side-channel threat. To do so, we apply some information theoretic results to side-channel analysis. The main objective is show how a side-channel leaking model can be seen as a communication channel.

We first show that the security of a chip is dependant to the signal-to-noise ratio (SNR) of the leakage. This result is very useful since it is a generic result independent from the attack.

When a designer builds a chip, he might not be able to know in advance how his embedded system will be attacked, maybe several years later. The tools that we provide in this manuscript will help designers to estimated the level of liability of their chips. iv

Résumé

Dans le cadre de la sécurité des systèmes embarqués, il est nécessaire de connaître les attaques logicielles et physiques pouvant briser la sécurité de composants cryptographiques garantissant l'intégrité, la fiabilité et la confidentialité des données. Étant donné que les algorithmes utilisés aujourd'hui comme Advanced Encryption Standard (AES) sont considérés comme résistants contre la cryptanalyse linéaire et différentielle, d'autres méthodes plus insidieuses sont utilisés pour récupérer les secrets de ces composants. En effet, la clé secrète utilisée pour le chiffrement de données peut fuiter pendant l'algorithme. Il est ainsi possible de mesurer cette fuite et de l'exploiter. Cette technique est appelée attaque par canal auxiliaire.

Le principal objectif de ce manuscrit de thèse est de consolider les connaissances théoriques sur ce type de menace. Pour cela, nous appliquons des résultats de théorie de l'information à l'étude par canal auxiliaire. Nous montrons ainsi comment il est possible de comparer un modèle de fuite à un modèle de transmission de l'information.

Dans un premier temps, nous montrons que la sécurité d'un composant est fortement dépendante du rapport signal à bruit de la fuite. Ce résultat a un impact fort car il ne dépend pas de l'attaque choisie. Lorsqu'un designer équipe son produit, il ne connaît pas encore la manière dont son système embarqué pourra être attaqué plusieurs années plus tard. Les outils mathématiques proposés dans ce manuscrit pourront aider les concepteurs à estimer le niveau de fiabilité de leurs puces électroniques. v En tout premier lieu, je voudrais remercier ma femme, Gabrielle pour le soutien indéfectible dont elle a fait part pendant ces trois années longues et fastidieuses. Elle a su être attentive et patiente surtout dans les moments pendant lesquels il me semblait perdre pied. Merci à mes directeurs de thèse, M. Sylvain Guilley et M. Olivier Rioul qui ont su m'accompagner pendant ces trois années. Merci à Sylvain pour sa créativité et son enthousiasme. Merci à Olivier pour sa rigueur et ses relectures très fines. Merci à eux deux de m'avoir fait gagner en maturité intellectuelle. Je voudrais aussi remercier particulièrement Pablo Piantanida pour tout le temps qu'il m'a consacré dans mes recherches liées à la théorie de l'information. Il s'est très vite intéressé au domaine des attaques par canaux cachés et son aide m'a été très précieuse. Merci également à mes deux rapporteurs de thèse MM. Emmanuel Prouff et Damien Vergnaud qui ont très gentiment accepté de lire et commenter ce présent manuscrit. D'un point de vue plus scientifique, je voudrais remercier tous ceux qui ont créé cette belle discipline des attaques par canaux cachés, en particulier Daniel Bernstein, François-Xavier Standaert et Benedikt Gierlich dont les différents papiers m'ont initié et donné du fil à retordre.

Merci à Annelie Heuser de m'avoir précédé dans cette tâche de formaliser mathématiquement les menaces. Enfin, Merci à Claude Shannon d'avoir créé cette si belle théorie de l'information qui, bien que vieille de plus de 60 ans, trouve toujours de nouvelles applications.

Merci à Chap de Midi Chapi d'avoir agrémenté mes pauses déjeuner, surtout dans les moments où mon cerveau n'était plus disponible pour faire des équations.

On the Importance of Cyber Security

In electronic devices such as embedded systems, personal computers, GPUs, etc, the need of security has grown wildly over the last 20 years. Indeed, millions of threats may compromise the security and therefore the private life of users, companies or state agencies, and one breach of security may alter the privacy of millions of users. For example, when ransomware WannaCry appeared in May 2017, about 200,000 computers were infected over 150 countries. The financial impact of this worldwide attack has been evaluated by cyber-risks modeling firm at $4 billion USD. However, experts of this domain noticed that such an attack could possibly go even worse since more sensible systems could have been affected, such as nuclear plants. This is why state agencies and big companies invest a lot of money to secure such sensible sites.

However, it is difficult to predict how a target will be attacked as the security breaches are very various and are often discovered by attackers. The attackers can have different goals such as:

• take the control of the target device;

• make the target device inoperant;

• catch the private data of the target. In order to protect the systems, the designer should protect their software as well as their hardware systems. The protection of the data can be made thanks to encryption algorithms..

The Rise of Cryptography

The Rise of Cryptography

As mentioned earlier, the protection of sensitive data is therefore crucial. This is why the notion of cryptography appeared.

A Bit of History

The notion of cryptography has appeared more than two thousands years ago. The oldest known ciphered document dates from the 16th century B.C. in Iraq. This is a clay tablet, in which a potter wrote his secret recipe. To make it secret, he removed the consonants, modifying the spelling of the words [START_REF] Kahn | The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet[END_REF].

The Greeks where also using their own methods of encoding. One of them is the scytale.

The scytale is a stick with a strip of parchment wound around it (cf Figure 1.2). The encoder and the decoder must own a stick having the same geometric characteristics to encrypt and Today, it would be considered as a very weak code, but we must not forget that in these times, a lot of people where not even able to read and write.

INTRODUCTION

During the first century B.C., Caesar ciphers appeared. They were the first letter substitution codes that appeared. In a message, every letter was changed into the n-th letter after. This method was used by the Roman army. Once again, this code is weak as one only has to check 26 possibilities to recover the message.

In 1586, French diplomat Blaise de Vigenère, published a book in which he exposed his own method of ciphering. This was called the Vigenère cipher. The method is still simple to encode and decode a message but the strength of the code is much higher than a Caesar cipher. Indeed, the code is based on a password and every letter of the message can be changed into different letter, depending on its place. The Vigenère cipher was broken in 1863 by Friedrich Kasiki.

During the Second World War, cryptography and cryptanalysis played a crucial role as Alan Turing managed to break the German encoding algorithm Enigma, supposed to be fully secured by the Wehrmacht. The impact of this was so important that today's historians agree that the war would have been at least two years longer if Enigma had not been broken [START_REF] Kozaczuk | Enigma: how the German machine cipher was broken, and how it was read by the Allies in World War Two[END_REF].

Cryptography Today

Nowadays, codes are more sophisticated, but the idea is still the same: protect secrets from malicious threats.

The Rise of Cryptography

For a greater security, Auguste Kerckhoffs showed that the security and the secret of a crypto-system should only be based on the secret of the encoding key [START_REF] Kerckhoffs | La cryptographie militaire (1)[END_REF]. This means that anyone can know the process leading to encoded data, but in this process, the encoder uses a secret key (therefore only known by him).

Eventually, a "good" coding algorithm is supposed to ensure that the best possible way to recover the secret message is to try every possibility of the key (exhaustive search). For 256 bits long keys, this would take more than 10 billions years with the best current computing power.

We can divide the codes into two big families:

• The symmetric codes where the secret key is the same for both encoding and decoding. This means that the sender and the receiver of the message must know the secret key before.

• The asymmetric codes where there is a key to encode the message (often called a public key) and a secret key to decode the message (often called the private key).

The advantage of symmetric codes is that they are often very easy to compute and to design on hardware. The speed of coding is very high (more than 10 Mb/s). The main drawback is the key exchange. How to share a secret key in a safe manner with someone?

On the contrary, asymmetric codes are much slower, but the sharing of the key is absolutely not a problem because the public key is used to encode the message and only the owner of the secret key will be able to decode the message. The only difficulty is to certify the owners of the public keys.

On the adversary's side, the goal is to recover the secret key. Obviously, the longer the key is, the more difficult it will be for the attacker to get it. The most naive way to recover a key is the brute force, i.e. to check every possible key. This process is very fast when the size of the key is low (today's machines can treat more than a billion operations per second). However, when keys are longer (for example 128 or 256 bits), it would take years to examine all the possibilities, even with the best processing units of the world. Other possibilities may exist to decrease to number of possibilities. They are called differential and linear cryptanalysis.

• In the differential cryptanalysis, the attacker is able to choose the input text. He exploits the differences at the input and sees how these differences behave at the output. A "good" algorithm transforms small differences into big ones. • In linear cryptanalysis, the attacker approximates the algorithm as a linear function, and by carefully choosing the plaintext, the secret key can be recovered if the algorithm presents some linearities.

A small list of the existing encryption methods is given Table 1.1. This list is not exhaustive since there are many ways to encrypt data but is shows the main standards that are used or have been used.

AES

Currently, the most used algorithm is called AES [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF] (for Advanced Encryption Standards).

AES was invented by Joan Daemen and Vincent Rijmen in 1997. In 2001, the National Institute of Standards and Technologies (NIST) chooses AES as the main encoding standard. Since then, AES has acquired a very good reputation of being a very secure algorithm. It has been built so that differential and linear cryptanalysis have no effect on its security. The only known attack on a full AES algorithm has been published in 2011 by a team working for Microsoft [START_REF] Bogdanov | Biclique cryptanalysis of the full AES[END_REF]. However, this attack recovers the key in 2 126 operations, while exhaustive search takes 2 128 operations.

This attack is therefore four times faster than the exhaustive search, but it is still a very long. This is why AES is still considered as safe.

AES is a block encoding algorithm. This means that it cuts the message to be encoded into blocks of 16 bytes. Then each block is encoded separately with the same secret key. The length of the secret key is either 16, 24 or 32 bytes. From the secret key, the algorithm first generates subkeys, as many as the number of rounds of the algorithm. For the first round, the secret key 1 The security of RSA is based on the difficulty to reduce very big numbers into a product of prime numbers.

The algorithm is simple and can be used for any key size. Nowadays, it is considered as safe to choose keys that are at least 2048 bits long. However, it has been proved that RSA will be very vulnerable to quantum cryptanalysis [START_REF] Shor | Algorithms for Quantum Computation: Discrete Logarithms and Factoring[END_REF]. 2 According to the NSA, AES can be considered as secure. It is however advised to encrypt very sensitive data with keys that are at least 192 bits long.

Side-Channel Analysis

meets the plaintext block through an exclusive or function. Then, for each round, the block passes through linear and non-linear functions such as:

1. SubBytes, a non-linear one-to-one function;

2. ShifRows, a cyclical shift of the rows of the block;

3. MixColumns, an invertible linear transformation.

Then the subkey corresponding to the number of the rounds is added.

Side-Channel Analysis

As we mentioned earlier, without more information than the message to be encoded and its encoded version, there is no better way to recover the key than the exhaustive search. To break the security of a device without performing an exhaustive search, one has therefore to use other type of information than only the plaintext and the ciphertext. These are the side information.

They can be of any type:

• the computation time of the algorithm;

• the electro-magnetic radiations of the device during the algorithm;

• the power consumption of the device;

• the insertion of faults during the computation of the algorithm.

These methods can be classified into two types of attacks: the invasive and non-invasive attacks.

Invasive attacks may alterate the targeted device while non-invasive attacks are more passive.

They only listen the behaviour of the system and try to establish a model of the leakage.

According to François-Xavier Standaert [START_REF] Standaert | A Unified Framework for the Analysis of Side-Channel Key Recovery Attacks[END_REF], we can model a side-channel attack by the framework designed Figure 3.1. During the encryption algorithm, the plaintext that is to be encrypted meets the secret key via an exclusive or function (or xor ). As the secret key is used in the algorithm, a possible leakage may happen since it is possible to measure an image of the secret key.

Secret key Leakage

For example, in AES, the secret key is used during the first round of the algorithm, and in some devices, it is possible to recover the secret key when the substitution box of the secret key xor the plaintext is stored in the register of the target device [START_REF] Mangard | Power Analysis Attacks: Revealing the Secrets of Smart Cards[END_REF].

Vulnerabilities

The main advantage of side-channel analysis compared to classical cryptanalysis, is that it is possible to recover each of the byte of the secret key separately. For attacker, this is a great improvement because, they no more supposed to consider at least 2 128 possibilities but 16 times 2 8 = 256 possibilities to recover the secret key. Therefore, in side-channel, the vulnerabilities come no-more from the algorithm itself, but from the way that this algorithm is implemented in a hardware chip. This means that, form the designer point of view, it is crucial to perfectly know the hardware architecture of the chip and to be very aware of any possible power leakage that may occur.

Nowadays, systems are build with sensors that are able to detect intrusive attacks and algorithms are developed to bring counter-measures to the leakages.

Attack

In practice, an attack happens in the following way as described by François-Xavier Standaert in [START_REF] Standaert | A Unified Framework for the Analysis of Side-Channel Key Recovery Attacks[END_REF]. In this framework, we notice that most of the attack follow the same pattern.

• As mentioned in Section 1.2, the encryption algorithm is known by the attacker. In most of the cases it will be AES (sometimes RSA or DES).

• The first phase of an attack is called the profiling phase. The attacker builds a modelization of the leakage using a copy of the target device. This modelization can be under a leakage model function or via histograms called template. Of course, as this profiling phase is made on a copy of the target device, the secret key of this copy is known. A drawback of this technique is that there may exist a bias between the model obtained with the copy device and the target device.

• Then, the exploitation phase is based on applying the model obtained during the profiling phase to the target device. Example: the DPA Contest In 2008, the DPA contest [START_REF]DPA Contest[END_REF] was launched by Télécom Paristech. The challenge was to recover a secret key used in an encrypting algorithm DES with a very little number of traces. The participants were provided very big sets of data such as:

Side-Channel Analysis

• For each query, the 64 bits plaintext to be encrypted;

• The corresponding 64 bits ciphertext;

• The power consumption of the whole encryption process.

A trace has the shape given in Figure 1. [START_REF] Beaudry | An intuitive proof of the data processing inequality[END_REF]. With one figure like this, it is not possible to recover the secret key. However, if we average them according to existing leakage models such as the hamming weight leakage [START_REF] Mangard | Power Analysis Attacks: Revealing the Secrets of Smart Cards[END_REF], we can notice some points of interest. For example, the SNR of the leakage of one DES substitution box is given in Figure 4.8. In this figure, we notice that given a leakage model, the SNR is relevant in three points. We call these samples points of interest. By selecting only theses points of interest and computing mathematical functions called distinguishers, it is possible to recover the secret key. For the first edition of the DPA contest,

INTRODUCTION

A Look on Information Theory

the best attacking method was provided by Christophe Clavier [START_REF] Clavier | DPA Contest 2008-2009, Less than 50 traces allow to recover the key[END_REF]. In his method, the full key recovery takes only 43 traces in average.

1.4 A Look on Information Theory

Background

The communication of information has benefited from many improvements at the physical level.

However, it is also profitable to optimize the data rate by studying how information shall be preprocessed before being sent. This need has given rise to Information Theory: the science of data transmission. It was created in 1948 by Claude E. Shannon from the Bell labs in his famous article A Mathematical Theory of Communication [START_REF] Shannon | A mathematical theory of communication[END_REF]. In this article, for the first time, the basis of digital communication were drawn. The idea was: how to send some information from a sender to a receiver through a noisy channel? To do so, Shannon proposed a framework for a communication channel, from the message to be sent, to the received message. For the first time, a precise model was proposed to describe distant communications. But Shannon did not only describe the model. With probabilistic considerations, he proved that it is possible to send messages with an arbitrary small error at the decoding phase, as long as the coding rate (i.e. the amount of data per sample) is lower than a given limit. Moreover, this limit has an analytic expression and is called the Mutual Information between the signal and the received signal. As the transmitter has access to the way that the data is sent, it is possible to modify the Mutual Information, and therefore reach the highest possible limit, called the Channel Capacity. When the noisy source is additive and the noise is Gaussian, the capacity of the channel takes the well-known expression C = 1 2 log(1 + SNR), where SNR is the signal to

INTRODUCTION

noise ratio, i.e. the power or the input signal divided by the power power of the noise. This formula is known as the Shannon capacity.

However, Shannon did only predict that there exists ways to transmit data that reach this bound. He did not tell how to find one. For mobile communications, the first time that a team managed to implement a transmission scheme reaching the Shannon capacity, was in 1996 when

Berrou and Glavieux invented the Turbo-codes [START_REF] Berrou | Near optimum error correcting coding and decoding: turbo-codes[END_REF].

Link With Side-Channel Analysis

The attractive point of information theory is that its fields of applications are wide. Indeed, in the case of side-channel analysis, we can consider that the secret key is an information, and that the leakage is a transmission.

In 2014, Annelie Heuser proposed a diagram where both notions of side-channel analysis and information theory are represented [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF]. We have copied this figure in Figure 1.8. The notations are the following:

• K * is the random variable standing for the leaking secret key.

• T is the random vector standing for the plaintext vector.

• Y is the random vector standing for the sensitive variable vector.

• N is the random vector standing for the additive noise (most often supposed as Gaussian).

• X is the random vector standing for the measured traces.

• K is the random variable standing for the estimated key. If the attack is efficient, the estimated key is equal to the secret key.

• The functions f and ϕ are respectively the algorithmic function (for example a SubBytes function and the leakage model function. The leakage model function can be supposed to be known or estimated. The best case for the attacker is of course when the leakage function is known.

• D is the distinguishing rule. It is a mathematical function taking as inputs the traces and the plaintext, and returning an estimation of the secret key.

A Look on Information Theory

Organization of the Manuscript

The manuscript is organized as follows. In Chapter 2, I describe the main contributions of my thesis. Part II deals with a generic upper bound to any type of attack thanks to information theoretic results. In Part III, I consolidate the knowledge of some distinguishers. More specifically, Chapter 5 deals with monobit leakages while Chapter 6 shows that Mutual Information Analysis can be optimal in some scenarios. In Part IV, we discuss about practical issues that may happen in real world devices, in particular for timing attacks.

Notations

All over this manuscript, we will use the following notations for the mathematical derivations.

The sets will be written with calligraphic letters, and elements of such sets in small caps. If possible we will use the same letter. for example x ∈ X. Random variables will be written in capital letter. For example, X is a random variable taking values in X. Probabilities are written with the symbol P. Therefore, the probability that X is x is noted P(X = x). If it is clear that the random variable is X, we will only write P(x). We use bold letters to write vectors. For example x is a vector whose all the element are in X. And X is a random vector taking values in X. If the set X is continuous, the probability distribution function is written as p(x).

We also recall some information theoretic definitions that are used in this manuscript. The

Notations

entropy of a random variable X is defined as:

H(X) = - x∈X P(x) log P(x).
The conditional entropy of X knowing Y is defined as:

H(X | Y ) = y∈Y P(y)H(X | Y = y) = y∈Y P(y) x∈X P(x | y) log P(x | y).
The mutual information between two random variables X and Y is defined as:

I(X; Y ) = H(X) -H(X | Y ) = H(Y ) -H(Y | X) = (x,y)∈X×Y P(x, y) log P(x, y) P(x)P(y)
For these definitions, we have not precised the base of the logarithm since it is mathematically possible to choose any base. However, in communication theory, base 2 is very often used and information is consequently expressed in bits. This is why we will use this base for all the logarithms.

Formal Security Proofs and Studies

During my thesis, my main concern has been: how to unify and understand the link between the different metrics used to evaluate the sensitive information leakage of cryptographic chips? Indeed, various different metrics have been proposed by various authors in respond to specific issues. For example, we can cite:

• The Mutual Information (MI) between measurements and the sensitive variables;

• The Perceived Information computed with the estimated distribution of the leakage, based on template attacks;

• The Success Rate or the Guessing Entropy of an attack exploiting a leakage.

A Generic Bound for Any Leakage With Only SNR

For example, the notion of MI is a widely spread concept in Side-Channel Analysis [START_REF] Durvaux | How to Certify the Leakage of a Chip?[END_REF], and everyone agrees that the larger the MI, the better the attack, or from the defender's side, the weaker the chip. However, the link between MI and the success rate of an attack, has never been established formally yet for generic attacks. Some links have already been made [START_REF] Duc | Making masking security proofs concrete -or how to evaluate the security of any leaking device[END_REF][START_REF] Mangard | One for All -All for One: Unifying Standard DPA Attacks[END_REF] but they have been made for particular types of attacks, especially to show how the masking order impacts the MI [START_REF] Prouff | Masking against Side-Channel Attacks: A Formal Security Proof[END_REF] and are therefore true in a specific context. Moreover, I have noticed that no paper really deals with a tight prediction of the security of a chip. My question was: how can a designer predict the success rate of an attack with a very restricted number of assumptions.

Indeed, a designer does not know how a device will be attacked. New methods may appear

Formal Security Proofs and Studies

several years after the conception of the chip. This is why I have started looking for a framework that can unify any type of attack under simple concepts and notations. This is the beginning of my reflection: if we use some information theoretic metrics, then the answer must be in this field.

In order to better formalize a side-channel attack, I based myself on the framework given by François-Xavier Standaert in [START_REF] Standaert | A Unified Framework for the Analysis of Side-Channel Key Recovery Attacks[END_REF]. This framework presents a simple albeit comprehensive look on what a side-channel attack is.

In 2014, Annelie Heuser has published an article [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF] where she demonstrates that the optimal distinguisher for an attack is the Maximum Likelihood decoder. To obtain this result, she establishes a first formal link between side-channel analysis and information theory. The leakage model is there seen as a communication channel with a message to recover (i.e. the secret key). The method to derive the optimal distinguisher has been to express the expression for the key decoding rule which maximizes the success rate.

As MI is an information theoretic metric, it becomes here natural to study its impact with information theoretic models and theorems. I have therefore worked on this aspect. The main difficulty for me has been to deal with the philosophical differences between information theory and side-channel. Indeed, the purpose of each is clearly different:

• The goal of an information theorist is to send a message with the highest possible rate and with an arbitrary small error rate. To do so, the communication engineer can use correcting codes and choose how the message is encoded.

• In side-channel analysis, the message is the secret key. But the attacker do not have access to it (which is obvious). This means that the input distributions are imposed by the model and that there is not coding possibility to improve the success rate.

However, Shannon's coding theorem and converse coding theorem are still useful to determine bounds. Indeed, the Shannon's converse coding theorem shows that the probability of success of a transmission is upper-bounded by the mutual information of the channel [START_REF] Elwood | A mathematical theory of communication[END_REF]. I have used this major theorem (proved 60 years ago!) and applied it to my side-channel model.

I have therefore applied the theorem to side-channel. The main problem that I have encountered is a formal calculation of the Mutual Information. Indeed, the leakages are not independent and identically distributed (i.i.d.). This means that the Mutual Information between the traces and the sensitive variables cannot be easily estimated via Shannon's formula 21

2. CONTRIBUTIONS C = 1 2 log 2 (1 + SNR).
This one remains only a loose upper-bound of the real MI. Therefore, I had to resort to other methods to estimated the MI as tight as possible.

I therefore proposed two new methods to estimate the MI of large vectors:

1. A mathematical upper-bound that converges to the right value when the number of traces q tends to infinity; 2. A parametric estimation based on empirical results.

The mathematical approach is true for any leakage model and any type of noise. However, the bound is not tight for small values of q. In this case, a good tradeoff is to merge our approach with Shannon's bound. Our parametric estimation is due to empirical observations with Additional White Gaussian Noise (AWGN). Indeed, I have noticed that the MI between two vectors behaves like an error function. With such estimation, the only knowledge of the Signal-to-Noise Ratio (SNR) is enough to approximate the MI. This leads to a computation of the Success Rate (SR) of an attack that can be computed only with the calculation of the SNR and with the assumption of an additive white Gaussian noise. We do not suppose anything on the leakage model. I have then compared the bound obtained by these estimations of the MI, with the best possible distinguisher i.e. the Maximum Likelihood distinguisher (as demonstrated by Heuser et al. in [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF]). The results show that the tighter the estimation of the MI, the tighter the bound is.

Extension to Template Attacks

My work on the best possible success rate for a given number of traces relies on the calculation of the Mutual Information between the sensitive variable and the measured traces. In many cases, the leakage model is not perfectly known and it has to be estimated. This is the case for example, when the attacker has a copy of the targeted device and learns the leakage model from this copy. These are called template attacks. Here the goal is different because we want to know how fast an attacker can break a secret key after a learning phase. This means that the attacker does not know the real leakage model, but an estimation that may even be biased. François-Xavier Standaert proposed the notion of Perceived Information (PI) [START_REF] Durvaux | How to Certify the Leakage of a Chip?[END_REF] to replace a MI that cannot be computed because of the lack of knowledge.

A first formal study about this PI shows that it is obviously lower than the MI and can even be smaller than zero. But we wish a link between PI and SR. I have shown that, when PI is strictly positive, the attack will succeed with a sufficient enough number of traces. This result 2.2 Adapting Theoretical Tools for Practical Issues is based on the demonstration of the Shannon theorem and a proof based on the mismatched decoders by Merhav [START_REF] Merhav | On information rates for mismatched decoders[END_REF].

MIA is Universal ML

On the distinguishing point of view, I have noticed that when the attacker has to profile with on-the-fly data, the Maximum Likelihood distinguisher is perfectly equivalent to a Mutual Information Analysis (MIA).

We have shown with theoretical case-study that MIA is very relevant when the leakage model is not perfectly known. Indeed, we have built an experiment where Correlation Power Analysis (CPA) crashes while MIA works well to recover a secret key.

A Unified Vision of Monobit Leakages

Several papers noticed that some distinguishers related to monobit leakages can be linked with Fei et al.'s confusion coefficient [START_REF] Fei | A Statistical Model for DPA with Novel Algorithmic Confusion Analysis[END_REF]. For example, Heuser et al. derived the Kolmogorov-Smirnov Analysis (KSA) as a function of the confusion coefficient and the SNR [START_REF] Heuser | A Theoretical Study of Kolmogorov-Smirnov Distinguishers -Side-Channel Analysis vs. Differential Cryptanalysis[END_REF]. Moreover, in [START_REF] Mangard | Power Analysis Attacks: Revealing the Secrets of Smart Cards[END_REF], Mangard et al. made the link between Correlation Power Analysis (CPA) and the confusion coefficient.

After reading these articles, we had the feeling that the link between any distinguisher of a monobit leakage, was deeper. Therefore, we first made the link between Mutual Information Analysis (MIA) and the confusion coefficient. We noticed that it also depends on the standard deviation of the noise. We extracted an analytic function linking MIA the confusion coefficient, and the standard deviation of the noise.

Eventually, we have noticed that for monobit leakages, the confusion coefficient can also be seen as the transition probability of a Binary Symmetric Channel (BSC). This has allowed us to prove that any sound distinguisher in monobit leakages is a function of two parameters: the confusion coefficient and the standard deviation of the noise.

Adapting Theoretical Tools for Practical Issues

Another task of my thesis was to adapt some of the theoretical tools for practical issues. I based my studies on an ARM processor edited by ST Microelectronics: the STM32 Discovery Board [START_REF]F4DISCOVERY Discovery kit with STM32F407VG MCU[END_REF].

CONTRIBUTIONS

On this architecture, we compute timing attacks on the AES algorithm. Here, in this practical example, the leakage model is not easy to find and to deal with. A template attack is therefore needed to learn the model. However a learning phase may encounter some problems such as:

• A bias between the learned model and the real leakage;

• A poor learning phase.

Avoid the Empty Bin Issue

One of the issues that we have met is the empty bin issues. The empty bin issue appears when there is a difference between the distribution of the learning phase and the distribution of the attack. We may face a strange case: when we compute the maximum likelihood distinguisher based on the distribution of the templates, we can meet some data such that the probability is null. This appears even for the correct key guess and therefore, the ML distinguisher crashes.

We have therefore imagined several solutions to avoid this empty bin issue but still keeping the notion of maximum likelihood that is supposed to be the best distinguishing rule according to Annelie Heuser's paper [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF].

The solutions that we have imagined are easy to compute and are sound. When the profiling is correct, the best distinguisher is a ML with a small penalty if an empty bin occurs. On the contrary, when the profiling is poor, the best possible distinguisher is to compute an MIA based on the learned model. Indeed, MIA is known to be more robust when the leakage model is not well characterized.

Extract a Model for a Timing Attack

In addition to the empty bin issue, I have worked on the STM32 Discovery board in order to extract a leakage model. In a black box view, we have as inputs the plaintext that is to be encoded and the number of clock cycles to compute AES as the output of this black box.

With this architecture, it is possible to enable or not the data cache (DC) or the instruction cache (IC). We have noticed that, when the DC is enabled, the computation of AES is not time constant, meaning that there is a leakage. A part of this leakage is still difficult to understand but we have managed to find out that the number of cache hits during the computation of the algorithm has a great impact.

Introduction

As a general rule, the most successful man in life is a man who has the best information.

-Benjamin Disraeli.

Side-channel analysis is renown as an effective "eavesdropping" attack technique to extract sensitive secrets from cryptographic chips. In recent literature, many exploits have been put forward. Starting from the seminal timing attack of Kocher [START_REF] Paul | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF], various biases of different kinds have been exhibited. Vertical attacks such as power analysis [START_REF] Paul | Differential power analysis[END_REF] have been shown to be highly efficient. However, from a designer's viewpoint, the exact details of the various attacks are irrelevant. Instead, defenders aim at estimating a security risk in general, e.g., the chance that a major security breach occurs. It is thus highly desired to protect designs against all kinds of SCA attacks in a provable way. When implementing a secure design, the natural question which arises is the quantification of its security, with respect to its architecture and its operational environment. In [START_REF] Durvaux | How to Certify the Leakage of a Chip?[END_REF], the authors present several metrics that can help the designers to secure cryptographic chips. Shannon's mutual information (MI) between measured traces and guessed models has been considered, but is often thought of as theoretical (too far from practical evaluations) and impracticable (too computationally inefficient). In [START_REF] Standaert | Towards security limits in side-channel attacks[END_REF], the authors explain the relative importance of MI and probability of success, but in a separate way. Our aim is to join the two concepts and to show how the knowledge of MI allows to derive an upper bound on the success rate.

We wish to estimate the success rate with very few assumptions, based on simple and easy-to-compute tools, such as the signal to noise ratio (SNR). The calculation of the SNR can be made without the knowledge of the leakage model as the SNR is the ratio between the power of the useful signal and the power of the noise. The power of the noise is easily measured as is is the measurement noise, and as the power of the useful signal is the difference between the power of the measured signal and the power of the noise, the SNR is obtained.

Related Work

As our main goal is to find an estimation of the success rate of an attack that can be as accurate as possible. Using Information theoretic tools, [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF] extracted the best possible distinguishing rule. However, this does not give any clue to estimate the success rate of an attack. In practice, the success rate is estimated by repeating a sufficient number of simulations.

Moreover, this is dependent of the knowledge of the leakage model. In practice, it is difficult to know exactly this model. Indeed, the estimation may be biased, the learning phase of the model, may be too short, the model, may be too complicated, etc. This is why, we wish to use general information theoretic tools in order to be as generic as possible, and to give bounds that are true whatever the attacker may do or may know.

In [START_REF] Mangard | Hardware Countermeasures against DPA -A Statistical Analysis of Their Effectiveness[END_REF], a link between the success rate and the number of traces to succeed in a correlation power analysis [START_REF] Brier | Correlation power analysis with a leakage model[END_REF] has been studied, and an analytical formula has been derived. However, this results is untrustworthy in practice because of the assumption that incorrect key guesses lead to independent distinguishers, which is not true. Subsequent work on this topic therefore consider the joint distribution of all values of the distinguisher (correct key and all remaining incorrect key guesses).

In [START_REF] Sylvain Guilley | A Key to Success -Success Exponents for Side-Channel Distinguishers[END_REF][START_REF] Lomné | How to Estimate the Success Rate of Higher-Order Side-Channel Attacks[END_REF][START_REF] Rivain | On the Exact Success Rate of Side Channel Analysis in the Gaussian Model[END_REF], the authors propose an estimation of the success rate of specific distinguishers. Namely, Rivain [START_REF] Rivain | On the Exact Success Rate of Side Channel Analysis in the Gaussian Model[END_REF] studies the distribution of two examples of distinguishers (correlation and template) in the presence of normal noise. Lomné et al. [START_REF] Lomné | How to Estimate the Success Rate of Higher-Order Side-Channel Attacks[END_REF] extend this work for masked implementations, while however still focusing on correlation and template attacks. Guilley et al. [START_REF] Sylvain Guilley | A Key to Success -Success Exponents for Side-Channel Distinguishers[END_REF] extend the approach from additive to some non-additive distinguishers (such as the mutual information analysis), but through the approximation that the number of traces tends to the infinity. To summarize, all three papers [START_REF] Sylvain Guilley | A Key to Success -Success Exponents for Side-Channel Distinguishers[END_REF][START_REF] Lomné | How to Estimate the Success Rate of Higher-Order Side-Channel Attacks[END_REF][START_REF] Rivain | On the Exact Success Rate of Side Channel Analysis in the Gaussian Model[END_REF] have in common that the knowledge of the leakage model, or at least an estimation via a learning phase with templates, is needed to predict the success rate. In addition, this estimation, in the three cases, is based on the central limit theorem, meaning that it is relevant for a large number of traces and only for additive distinguishers. We wish a bound valid for any distinguisher, for any number of traces (even small).

A bound on the Mutual Information is proposed in [START_REF] Prouff | Masking against Side-Channel Attacks: A Formal Security Proof[END_REF]. The MI involved is based on one trace, supposing that every leakage is independent from each other. We show in this part that this is not the case in practice. In this paper, the bound is valid for MI with only one measurement. We will see in this part of the manuscript that calculating MI with the probability functions of all the traces is crucial.

In [START_REF] Duc | Making masking security proofs concrete -or how to evaluate the security of any leaking device[END_REF]Theorem 2], the authors proposed a link between success rate and the number of measurements. This bound is based on the the link between MI and random probing. Therefore, it is valid only for leakages with very low SNR and the bound is very loose For instance (see Figure 4.6), with SNR > 10 -4 , the bound of Duc et al. [START_REF] Duc | Making masking security proofs concrete -or how to evaluate the security of any leaking device[END_REF] is trivial (the success rate is smaller than one), and for SNR = 10 -5 , it predicts a number of traces 4, which is much smaller than our result of 1.3 × 10 6 (where the best attack using ML predicts 1.5 × 10 6 , which is in the order of magnitude of our prediction). In fact, the main contribution of the bound of Duc et al. [START_REF] Duc | Making masking security proofs concrete -or how to evaluate the security of any leaking device[END_REF] is to show that the masking order of an attack has an exponential impact on the success rate, but not to yield an accurate link between number of traces and success rate.

In the field of information theory, Arimoto [START_REF] Arimoto | On the converse to the coding theorem for discrete memoryless channels (corresp.)[END_REF] proved a lower bound of the error rate (hence an upper-bound of the success rate) in terms of a so-called Gallager coefficient. However, not only requires intensive computations, but also the model assumes a freely chosen input distribution.

In our case, that input distribution is set by the leakage model and therefore, cannot be freely chosen. Arimoto's main result (Equation 24 of [START_REF] Arimoto | On the converse to the coding theorem for discrete memoryless channels (corresp.)[END_REF]) remains true because it represents the best possible case for an attacker for all possible input distributions; but the resulting bound is very loose in our side-channel context. Equation 9 of [START_REF] Arimoto | On the converse to the coding theorem for discrete memoryless channels (corresp.)[END_REF] could be used instead but depends on a parameter β. With our notations (presented in section 3.1), Arimoto's Equation 9 becomes:

∀β > 0, P e ≤ 1 -2 n(β-1)
t∈T q P(t)

x∈X q 2 n -1 k=0 P(k)P(x | k, t) 1/β β .
The minimization of the r.h.s is practical untraceable for q > 1. Indeed, it consists in sums over |X| q elements; the complexity is even worse when the output is continuous.

Overall, we can sum up the related work with the following table 2.1. The table classifies the state-of-the-art according various criteria, such as the way the results are derived and whether or not the mutual information is involved in the estimation of the success rate. The last two columns show whether a closed form bound exists and whether it is generic in the attack method.

Our method provided an analytic expression for the lower bound (Theorem 3.1) and is agnostic in the attack method.

Contributions In this chapter, we derive bounds on the success rate of any attack, irrespective to the exact attack. Thus we can consider our bounds as universal. To do so, we address this problem using rigorous information theoretic tools. This is why we revisit the use of MI as a conservative security metric. traces where a given success level can be reached, based only on theoretical assumptions on the channel. The actual value of MI is important to estimate and such an estimation is not immediate because random vectors of very high dimensions are involved in its expression. Therefore, we propose several ways to simply estimate the MI by mathematically proved upper bounds and by numerical estimations. Our results are applied to the most common type of noise, namely the additive white Gaussian noise. We show that, in the case of additive Gaussian noise, the only calculation of the SNR is sufficient enough predict accurately the security of a device. Last, the main result on success rate is translated in terms of guessing entropy, another informative criterion in side-channel analysis.

Organization This part is organized as follows. In Chapter 3, we provide the mathematical computaions to prove this bound and we apply them in the case of additive white Gaussian noise. Section 3.1 describes the side-channel and shows how a leakage can be modeled with a Markov chain. Section 3.2 provides our main result and three different ways to exploit it. An application to leakages with additive Gaussian noise is carried out in Section 3.3, where we show at the end that the SNR is enough to predict the security of a device. The link to the guessing entropy is done in Section 3.4. In Chapter 4, we show how we can tighten the bound with numerical estimations of the mutual information. We give a general conclusion of both chapters in Section 4.4. Technical computations involved in proofs are in Appendix.

Notations Throughout this paper we use the following notations. Calligraphic letters (e.g. X) denote sets. Uppercase letters (e.g. X) denote random variables taking their values in the corresponding set (e.g. X). Lowercase letters (e.g. x) denote realizations of this random variable.

Vectors are written in bold characters. By default, the length of a vector is q ∈ N. Thus, a random vector is denoted with a bold capital letter (e.g. X = (X 1 , X 2 , . . . , X q )) and a vector of realizations on this random vector is denoted with a small bold letter (e.g. x = (x 1 , x 2 , . . . , x q )).

Given the random variable X taking its values in X and x ∈ X, the probability that X equals x is noted P(X = x) or simply P(x).

We also define some information theoretic tools. The entropy of a random vector X of length q is defined by:

H(X) = - x∈X q P(x) log 2 P(x).
The conditional entropy of a random vector X knowing vector Y is defined by:

H(X | Y) = - y∈Y q P(y)H(X | Y = y) = - y∈Y q P(y) x∈X q P(x | y) log 2 P(x | y).
The Mutual Information between two random vectors X and Y is defined as I(X; Y) = H(X) -H(X | Y). The conditional Mutual Information I(X; Y | T) where X, Y and T are random vectors is defined as I(X; Y | T) = H(X | T) -H(X | Y, T). Last, the Kullback-Leibler divergence between two distributions P and Q over the same set X is defined as:

D(P Q) = x∈X P(x) log 2 P(x) Q(x) .
Chapter 3

Side-Channel Seen as a Communication Channel

The link between side-channel analysis and information theory has been proposed by [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF] to derive the optimal distinguisher. In this section, we review how the side-channel can be seen as a communication channel. The secret key byte that the attacker wants to recover is denoted as k * and is n bits long (typically n = 8). We assume that the attacker inputs q text bytes t = (t 1 , t 2 , . . . , t q ) and receives that many traces in a vector x = (x 1 , x 2 , . . . , x q ), with the following leakage model :

x i = f (t i ⊕ k * ) + n i (i = 1, 2, . . . , q) (3.1)
where n = (n 1 , n 2 , . . . , n q ) is an additive noise independent of x and f (.) is some leakage function.

We assume that f is deterministic but not necessary known to the attacker. This assumption will make our calculations generic and therefore true for any type of attack. This is the worst possible case for the security designers. Define the sensitive variable y(k) = y t (k) as

y t (k) = f (t ⊕ k) = (f (t 1 ⊕ k), . . . , f (t q ⊕ k)) (3.2)
so that the leakage can be written in compact form as

x = y t (k * ) + n.
Such vectors t, y and x are realizations of random vectors noted T, Y and X. In the case of one particular sample, t, y and x are realizations of random variables T, Y and X. We assume that 3.1 Side-Channel Seen as a Communication Channel the channel is memoryless, which means that each trace x i depends on the input y only from y i .

In particular x i and y j are independent for all if i = j. We also make the natural assumption that the secret key is independent from all text bytes: the secret key random variable K is independent from T. In other words, the text bytes do not give any information about the secret key (at least in a design which adheres to Kerckhoffs's principle).

Following [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF] we make the following hypotheses:

• K is uniformly distributed over K = {0, . . . , 2 n -1}. K is a scalar (there is one key-byte to break), and is therefore not written in bold font.

• T is uniformly distributed over T = {0, . . . , 2 n -1}. Moreover, we suppose that vector T is balanced, meaning that the number of occurrences of each symbol in the vector is the same.

• As seen above, the random variable Y is such that Y = f (T ⊕ K), with f a known deterministic function.

• As q textbytes are sent and therefore q traces are received, we consider the random vectors T, Y and X.

Thus from (3.1), we can write

X = f (T ⊕ K) + N = Y + N.
Considering only scalars, this writes for random variables

X = f (T ⊕ K) + N = Y + N.
After acquiring q traces, the attacker applies a function called distinguisher D to obtain an estimate K = D(X, T) of the secret key from X and T. This allows us to define the communication channel as depicted in Figure 3.1:

• the "encoder" models the leakage from the device: not only the composition of the algorithm which mixes the unknown key K with the known text T into a sensitive variable, but also the way the device leaks the sensitive variable (function f ); • the (side) channel consists in noise addition, arising from the untargeted parts of the design and from the measurement setup; and

• the "decoder" implements the distinguishing rule with allows the attacker to get a key guess K from the measured leakage X and the knowledge of public text bytes T. The realizations t of the random vector T are known by the attacker.

From the model we can deduce Lemma 3.1 dealing with Markov chains.We recall that a Markov chain is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event.

Lemma 3.1. The communication channel just described admits the following Markov chains:

(K, T) -→ (Y, T) -→ (X, T) -→ K (3.3) K -→ Y -→ X -→ K (K, T) -→ Y -→ X.
Proof. The first case is easily seen by re-drawing Figure 3.1 into the different constitutive blocks as shown in Figure 3.2, where all the variables pass through different blocks corresponding to the Markov Chain. The two other cases are proved similarly.

K Encoder Y Channel X Decoder K T N T T Block 1 Block 2 Block 3 Figure 3.2: The Markov chain (K, T) -→ (Y, T) -→ (X, T) -→ K.
3.2 Theoretical Bounds on Mutual Information

Theoretical Bounds on Mutual Information

One of the important properties of a Markov chain is the data processing inequality [START_REF] Cover | Elements of Information Theory[END_REF], which is used to prove the following theorem in this section, which is our main result.

Main Result

Let P s = P( K = K) be the probability of success of an attack and H 2 (P s ) its binary entropy1 [START_REF] Cover | Elements of Information Theory[END_REF]:

H 2 (P s ) = -P s log 2 (P s ) -(1 -P s ) log 2 (1 -P s ).
The following theorem is fundamental because it provides a trade-off for any possible type of attack.

Theorem 3.1. The following inequality is always true for any distinguishing rule:

H(K) -(1 -P s ) log 2 (2 n -1) -H 2 (P s ) ≤ q • I(X; Y | T ). (3.4)
The probability of success of an attack also follows the following inequality:

H(K) -(1 -P s ) log 2 (2 n -1) -H 2 (P s ) ≤ E T E K1 log 2 E K2 exp -D(P X|K1,T P X|K2,T ) ; (3.5)
where D(P P ) is the Kullback-Leibler divergence [START_REF] Cover | Elements of Information Theory[END_REF] and K 1 , K 2 are identically distributed as K.

Merging these two equations we can write:

H(K) + (P s -1) log 2 (2 n -1) -H 2 (P s ) ≤ min(E T E K1 log 2 E K2 exp -D(P X|K1,T P X|K2,T ) , qI(X; Y | T )). (3.6)
This theorem shows that the success rate of an attack is directly linked to the Mutual Information between the leakage and the model. Furthermore, as we consider generic attacks, this inequality remains true whatever the attacker does with the traces. In the next subsections we prove both inequalities and we show that (3.4) is more interesting for low values of q while (3.5) is a better approximation for high values of q.

To do so, we first demonstrate a preliminary lemma in Section 3.2.2 that will be useful for both Equation (3.4) and (3.5).

Lemma 3.2. With the notations of Theorem 3.1, we have:

H(K) -(1 -P s ) log 2 (2 n -1) -H 2 (P s ) ≤ I(X; Y | T). (3.7)
Proof. Using the Markov Chain (3.3) we compare two MI values thanks to the data processing inequality [START_REF] Beaudry | An intuitive proof of the data processing inequality[END_REF]. Indeed, this is a direct consequence of Lemma 3.1. This inequality states that the further two random variables are in a Markov Chain, the less MI between these variables. Here we have

I((K, T) ; (X, T)) ≤ I((Y, T) ; (X, T)). (3.8)
Let us expand both sides of this inequality. In the l.h.s., since the channel is memoryless and K and T are independent, we have:

I((K, T); (X, T)) = H(K, T) -H((K, T) | (X, T)) = H(K) + H(T) -H(K | T, X).
As K is a deterministic function of T and X, adding the knowledge of K does not change the entropy:

I((K, T); (X, T)) = H(K) + H(T) -H(K | T, X, K); ≥ H(K) + H(T) -H(K | K).
The latter inequality holds since conditioning reduces entropy [START_REF] Cover | Elements of Information Theory[END_REF]. Now by Fano's inequality1 [23, Page 43],

H(K | K) ≤ H 2 (P e ) + P e log 2 (|K| -1)
where P e is the probability of error P e = P(K = K). Since P s = 1 -P e and H 2 (P e ) = H 2 (P s ) = -P e log 2 (P e ) -P s log 2 (P s ), this is rewritten as

H(K | K) ≤ H 2 (P s ) + (1 -P s ) log 2 (2 n -1).
Plugging this inequality into the previous one gives

I((K, T); ( K, T)) ≥ H(K) + qH(T ) -H 2 (P s ) -(1 -P s ) log 2 (2 n -1). (3.9)
On the other hand, the r.h.s. of the data processing inequality (3.8) is:

I((Y, T); (X, T)) = H(X, T) -H(X, T | Y, T); = H(X, T) -H(X | Y, T); = I(X; Y | T) + H(T).
(3.10)

Theoretical Bounds on Mutual Information

Combining Equations (3.9) and (3.10), we obtain the following fundamental inequality:

H(K) -H 2 (P s ) -(1 -P s ) log 2 (2 n -1) ≤ I(X; Y | T), (3.11)
And proving Lemma 3.2.

The same l.h.s. of (3.11) will be used to prove for both inequalities (3.4) and (3.5), the difference being the way that I(X; Y | T) is evaluated. Indeed, the next part of the proofs for Equations (3.4) and (3.5) is about finding an upper-bound for I(X; Y | T). We have to do so because there is no analytic expression for this conditional Mutual Information computed with vectors of q dimensions. Remark 3.1. A quick analysis of the value n + (P s -1) log 2 (2 n -1) -H 2 (P s ) reveals that it is always non-negative for any P s in the range (0, 1) and vanishes if and only if P s = 1/2 n .

Therefore, when there are no traces, I(X; Y | T) = 0, the only probability that can respect inequality (3.11) is P s = 1/2 n , meaning that without information, that attacker can not have a better success rate than 1/2 n obtained with an equiprobable random guess, as expected. Every trace will bring additional information and therefore increase the probability of success.

First Upper Bound on I(X; Y | T): Proof of Inequality (3.4)

Thanks to Lemma 3.2, the l.h.s. of Theorem 3.1 is given. Inequality (3.4) is a straightforward consequence of the following lemma. Lemma 3.3. Let X and Y be two random vectors with joint distribution P X,Y , P X be the marginal distribution of X, and P X be the marginal of one element X of vector X. Define the distribution P X = q i=1 P Xi . We have

I(X; Y) = qI(X; Y ) -D P X P X ; ≤ qI(X; Y ).
This Lemma means that the Mutual Information of two random vectors made of identically distributed random variables is lower than q times the Mutual Information of the marginal distribution of these random vectors.

I(X; Y) = E X,Y log 2 P X|Y (X | Y) P X (X) = E X,Y log 2 P X|Y (X | Y) P X (X) + E X,Y log 2 P X (X) P X (X) = E X,Y log 2 i P X|Y (X i | Y i ) i P X (X i ) -D P X P X = i E X,Y log 2 P X|Y (X i | Y i ) P X (X i ) -D P X P X = qI(X; Y ) -D P X P X .
The inequality follows since the divergence is always non-negative.

This upper bound on MI is easily derived but is linear in q, and, therefore, will not converge to a finite value as the number of measurements increases (q → ∞). This will be in contradiction with Lemma 3.4. Therefore, it is interesting to propose another bound that converges to a finite value. This will be made in the next section.

Second Upper Bound on I(X; Y | T) -Proof of Inequality (3.5)

Before proving (3.5) we first notice that in our side-channel model, as there is a finite number of keys, the MI is always bounded by H(K).

Lemma 3.4.

I(X; Y | T) = I(K; X | T) ≤ H(K)
Proof. We use the Markov chain defined in Equation (3.3). Notice that, adding the knowledge of T, K when T, Y are already known does not change the entropy of X. Therefore,

H(X | T, Y) = H(X | T, Y, K, T); = H(X | T, Y, K).
As Y is a deterministic function of K and T, it can be removed, so we get:

H(X | T, Y) = H(X | T, K).
Therefore, we obtain I(X;

Y | T) = I(X; K | T). Since I(X; K | T) = H(K) -H(K | T, X) in follows that I(X; K | T) ≤ H(K).
Here H(K) is a constant that depends only on the distribution of K; it reaches its maximum value for a uniform distribution: H(K) = n bit. As a consequence, since I(X; Y | T) increases

Theoretical Bounds on Mutual Information

with q, it must converge to a finite value when q → ∞. This explains why the upper-bound given by (3.4) is poor when q → ∞.

Therefore, we provide another bound that is more accurate for large values of q because it converges to a finite value when K is finite. First we need the following Lemma 3.5. For any random variables X and Y and real-valued function (x, y) → f (x, y),

-E Y log 2 E X [exp(f (X, Y ))] ≤ -log 2 E X [exp(E Y f (X, Y ))].
Proof. See Appendix A.2.

Corollary 3.1. For any random variables X and Y and positive function (x, y) → g(x, y),

exp E Y log 2 E X [g(X, Y )] ≥ E X [exp(E Y log g(X, Y ))] Proof. See Appendix A.3.
Equipped with Lemma 3.5, we compute MI as follows:

I(X; K | T) = E T E X,K|T log 2 P(X | KT) P(X | T) ; = E T E K E X|K,T log 2 P(X | KT) P(X | T) ;
We introduce here K 2 , a random variable following the same distribution as K.

I(X; K | T) = E T E K E X|K,T log 2 P(X | K, T) E K2 P(X | K 2 , T) ; = -E T E K E X|K,T log 2 E K2 P(X | K 2 , T) P(X | K, T) ; = -E T E K E X|K,T log 2 E K2 exp log 2 P(X | K 2 , T) P(X | K, T) .
By Lemma 3.5 we obtain

I(X; K | T) ≤ -E T E K log 2 E K2 exp E X|K,T log 2 P(X | K 2 , T) P(X | K, T) ; = -E T E K log 2 E K2 exp -D(P X|K,T || P X|K2,T ) .
This proves inequality (3.5) and Theorem 3.

1 1 . σ 2
. Moreover, at the end of this section, we will extract a parametric estimation of the Mutual Information where the only parameter to know is the SNR.

Remark 3.2. With additive white Gaussian noise, the SNR of the traces can also been written as:

SNR = Var(Y ) σ 2
, where σ is the standard deviation of the noise.

Shannon's Channel Capacity

Under the additive white Gaussian noise (AWGN) assumption, it is easily seen that the scalar mutual information I(X; Y | T ) does not exceed Shannon's capacity. Indeed, we have:

I(X; Y | T ) = E T I(X; Y | T = t); = E T [H(X | T = t) -H(X | Y, T = t)] ; = E T [H(f (T ⊕ K) + N | T = t)] -H(X | Y ); = E T [H(f (t ⊕ K) + N )] -H(X | Y ); = H(f (K) + N ) -H(X | Y ); ≤ 1 2 log 2 (2πe(Var K (f (K)) + Var(N ))) -H(X | Y ); = 1 2 log 2 (1 + SNR).
Combining this with inequality (3.4) yields a lower bound on the number of traces to reach a given probability of success:

q ≥ n + (P s -1) log 2 (2 n -1) -H 2 (P s ) 1 2 log 2 (1 + SNR) (3.12)
Remark 3.3. The number of traces q to be sure to recover the key is lower-bounded by: lim

Ps→1 q ≥ n 1 2 log 2 (1 + SNR) . (3.13)
However, since as we have seen the MI can never be higher than H(K), the above constant bound is not accurate for real attacks. The next subsection provides a much more accurate estimation.

Evaluation of the Kullback-Leibler Divergence

Inequality (3.5) gives an upper bound with a divergence term that depends on P X|Ki,T (i = 1, 2).

In the AWGN model, P X|Ki,T follows a multivariate normal distribution N(y(K i , T), σ 2 I q ). For such distributions, the divergence is very easy to compute as the covariance matrix is diagonal.

It is easily found that

D(P X|K,T P X|K2,T ) = y(K, T) -y(K 2 , T) 2 2 2σ 2 .
Inequality (3.5), when applied to the AWGN model, becomes

n + (P s -1) log 2 (2 n -1) -H 2 (P s ) ≤ -E T E K log 2 E K2 exp - y(K, T) -y(K 2 , T) 2 2 2σ 2 .
In order to make a precise evaluation of the r.h.s., we need several lemmas.

Lemma 3.6. Let t = (t 1 , . . . , t q ) ∈ T q and (k 1 = k 2 ) ∈ K 2 . One has lim q→∞ y(k 1 , t) -y(k 2 , t) 2 2 = +∞ (3.14)
and more precisely:

y(k 1 , t) -y(k 2 , t) 2 2 ∼ q→∞ q.α(k 1 , k 2 ), (3.15)
where

α(k 1 , k 2 ) = 1 2 n 2 n -1 t=0 (y(k 1 , t) -y(k 2 , t)) 2 .
Proof. We make use of the assumption made in Section 3.1 that T is balanced. For k 1 = k 2 , we have

y(k 1 , t) -y(k 2 , t) 2 2 = q i=1 (y(k 1 , t i ) -y(k 2 , t i )) 2 ; = q q i=1 (y(k 1 , t i ) -y(k 2 , t i )) 2 q ; = q t∈T n t (y(k 1 , t i ) -y(k 2 , t i )) 2 q ;
where n t is the number of times that a particular t ∈ T appears in vector t. As t is balanced, nt q → 1 |T| and therefore:

y(k 1 , t) -y(k 2 , t) 2 2 ∼ q→∞ q t∈T (y(k 1 , t i ) -y(k 2 , t i )) 2 |T| . 2σ 2 = n (3.16) -log 2 E K2 exp - y(k, t) -y(K 2 , t) 2 2 2σ 2 ∼ q→∞ -log 2 E K2 exp - q.α(k, K 2 ) 2σ 2 .
(3.17)

Proof. One has

-log 2 E K2 exp - y(k, t) -y(K 2 , t) 2 2 2σ 2 = -log 2 k2 1 2 n exp - y(k, t) -y(k 2 , t) 2 2 2σ 2
When q is a multiple of 2 n we have exactly

y(t, k 1 ) -y(t, k 2 ) 2 2 = q.α(k 1 , k 2 )
and the proof of Equation (3.17) is trivial. Otherwise, for k = k 2 we have exp(-q α(k,k2) 2σ 2 ) → 0 as q → ∞; and for k = k 2 we have exp(-q α(k,k2)

2σ 2 ) = 1. Therefore -log 2 k2 1 2 n exp - y(k, t) -y(k 2 , t) 2 2 2σ 2 -→ n.
Lemma 3.8. With the assumptions made in Section 3.1, we have as q → ∞:

E T E K log 2 E K2 exp -D(P X|K ||P X|K2 ) ∼ q→∞ n - n min 2 n exp(-q. min k1 =k2 α(k 1 , k 2 )) (3.18)
where n min is the number of indexes

k 1 = k 2 reaching the minimum value of α(k 1 , k 2 ).
This simple asymptotic expression can be used to upper-estimate the MI for high values of q.

Notice that for any

k 1 = k 2 , α(k 1 , k 2 ) = α(k 2 , k 1 )
, hence n min is an even number.

Proof. Let t = (t 1 , . . . , t q ) be a balanced vector. By Lemma 3.7, we have

-E K log E K2 exp -D(P X|Kt ||P X|K2t ) ∼ q→∞ -E K log E K2 exp - q.α(K, K 2 ) 2σ 2
where

-E K log E K2 exp - q.α(K, K 2 ) 2σ 2 = -E K log 1 2 n k2 exp - q.α(K, k 2 ) 2σ 2 ; = n -E K log   1 + k2 =K exp - q.α(K, k 2 ) 2σ 2   .
As the value inside the logarithm vanishes as q → ∞, consider its first-order Taylor expansion:

-E K log E K2 exp - q.α(K, K 2 ) 2σ 2 ∼ q→∞ n -E K   k2 =K exp - q.α(K, k 2 ) 2σ 2   ; = n - 1 2 n k1 =k2 exp - q.α(K, k 2 ) 2σ 2 .
Let

k 1 = k 2 be a couple such that α(k 1 , k 2 )
is the minimum of all the possible α. For any other couple k 3 = k 4 , there are two possibilities:

1. either α(k 3 , k 4 ) = α(k 1 , k 2 )
and the corresponding exponentials will converge at the same rate;

2. or α(k 3 , k 4 ) > α(k 1 , k 2 ) and exp -q 2σ 2 α(k 3 , k 4 ) is negligible w.r.t. exp -q 2σ 2 α(k 1 , k 2 ) .
Hence we can simply count the number of occurrences of the minimum value of α. We have proven that:

-E K log E K2 exp -D(P X|Kt ||P X|K2t ) ∼ q→∞ n - n min 2 n exp - q. min k1 =k2 α(k 1 , k 2 ) 2σ 2 .
As this expansion is true for any vector t that is balanced, and is independent of it, this proves the lemma.

Remark 3.4. The simplification of Lemma 3.8 is useful to obtain a simple equivalent form for high values of q. However, it is also possible to compute a tight approximation of the numerical value of

E T E K log 2 E K2 exp -D(P X|K ||P X|K2 ) .
Remark 3.5. Interestingly, we notice that parameter α(k 1 , k 2 ) is proportional to the confusion coefficient κ(k 1 , k 2 ) defined first in [START_REF] Fei | A Statistical Model for DPA with Novel Algorithmic Confusion Analysis[END_REF] for binary leakages, and extended in [START_REF] Sylvain Guilley | A Key to Success -Success Exponents for Side-Channel Distinguishers[END_REF]Equation (45)] for any leakage:

κ(k 1 , k 2 ) = 4α(k 1 , k 2 ).

Link with Guessing Entropy

Another way to quantify the quality of an attack is the Guessing Entropy [START_REF] James | Guessing and entropy[END_REF], defined as

H(K | X, T
). This metric quantifies the complexity of the exclusive search to recover K knowing the side-channel measurements. Besides, let N K be the average number of tries to retrieve the secret key K with the knowledge of X and T. Mathematically, we have:

N K = E XT k δ XT (k)P(k | X, T) ,

Link with Guessing Entropy

The lemma can be exploited by replacing

H(K | X, T) by log 2 (eN K ) in Subsection 3.2.2.
Therefore, instead of using Fano's inequality, we directly have

I((K, T); (X, T)) ≥ H(K) + H(T) -log 2 (eN K ),
leading to:

N K ≥ 2 -I(X;Y|T)+H(K) e . (3.20)
Once more, we can use Theorems (3.4) and (3.5) to estimate the mutual information.

For example, we suppose that we have a Gaussian channel, with SNR = 1/8 and q = 40 traces. We apply Equation (3.4) to obtain that I(X; T | T) ≤ q 1 2 log(1 + SNR). For a n = 8 bits leakage, the average number of tries is lower-bounded by:

N K ≥ -2 20 * log 2 (1+1/8)+8 e ≈ 2 4.6 e ≈ 8.9
This means that, for such a channel, it would take at least 8 tries to recover one byte of the secret key with 40 traces. However, a secret key is made of 16 or even 32 bytes. Supposing that the attacker has only 40 traces for each key-byte, after the attack, one would need at least 8.9 16 ≈ 1.6 × 10 15 tries in average to recover the entire key as there is no way to check only byte per byte.

In this Chapter, we apply the results of Lemma 3.2 and Theorem 3.1 to practical cases. In addition, we also discuss about the difficulty to estimate the mutual information I(X; Y | T) and therefore, we provide numerical estimations based on the law of grat numbers. With these estimations, we then notice that that they fit well with a parametric estimation. Theorem 3.1 gave analytic bounds to the success rate. However, one may need to obtain a precise value of I(X; Y|T) making the bound tighter. In this section, we propose numerical tools to obtain an accurate value of the Mutual Information as a function of the number of queries q. A full estimation of I(X; Y | T) by numerical integration becomes impossible for q-dimensional distributions, and we have recourse to simplifying approximations of MI. Since

I(X; Y | T) = H(X | T) -H(X | Y, T) = H(X | T) -H(X | Y)
we can estimate only the entropy

H(X | T) because H(X | Y) = qH(X | Y ) is easily computable with classical numerical tools.
One possible approximation is from the law of large numbers [START_REF] Cover | Elements of Information Theory[END_REF]Chapter 3]:

H(X | T) = lim J→∞ - 1 J t∈T q J j=1 P(t) log 2 P(x j | t). (4.1)

Numerical Approximations for Mutual Information

Unfortunately, such a computation is not tractable since it involves the sum over all balanced vectors t, which represents q! possibilities. However, we can obtain a good approximation of H(X | T) with only one vector t form the following Lemma 4.1 (A Symmetry Property). Let t = (t 1 , . . . , t q ) ∈ T and τ be a permutation in {1, . . . , q}. Noting τ (t) = (t τ (1) , . . . , t τ (q) ), we have:

H(X | T = t) = H(X | T = τ (t)). (4.2) Proof. See Appendix A.1.
As a consequence of the symmetry of Lemma 4.1, one needs only one balanced vector t to estimate H(X | T). Therefore, by the law of large numbers,

H(X | T) ≈ lim J→∞ - 1 J J j=1 log 2 P(x j | t). (4.3)
This leads to Algorithm 1 to evaluate the entropy H(X | T).

Algorithm 1: Computation of the entropy using the law of large numbers. input : A balanced vector t An integer J The probability distribution P(x | t) output : An approximation of H(X | T) 1 Hxt ← 0 ; 2 Generate a secret key byte k * ; 3 for j ← 0 to J do 4 Generate the traces x with the model ;

5 Hxt ← Hxt -1 J log 2 P(x | t); 6 end 7 return Hxt
When the leakage models are not perfectly known (e.g. template attacks), a possible way to estimate Mutual Information is to approximate numerically the distributions. An example is given in [START_REF] Grosso | Masking Proofs Are Tight and How to Exploit it in Security Evaluations[END_REF].

Other estimation methods can be used, depending on the distribution of the noise. As an example, for Gaussian noise, we may consider Gaussian mixtures as discussed in [START_REF] Min | On the Entropy Computation of Large Complex Gaussian Mixture Distributions[END_REF].

Such numerical estimations are all the more accurate as J is taken large, which means that they make take a tremendous amount of time to compute. Having I(X; T|T) as a function of q, even numerically estimated, is very useful as we have the link between the success rate and the minimum number of traces to reach such probability of success.

Graphical Comparison

In order to visualize the difference between the two upper bounds given above, we have plotted the mutual information I(X; Y | T = t), where t is a fixed balanced vector. The leakage model chosen is given by the equation

y(k, t i ) = H w (S box (t i ⊕ k)) (i = 1, 2, . . . , q)
where H w (•) is the Hamming weight (of the value written in binary), and S box (•) is the AES substitution box [START_REF] Daemen | AES Proposal: Rijndael[END_REF]. We suppose that the zero-mean additive white Gaussian noise (AWGN) has standard deviation σ = 4. This gives a signal-noise ratio SNR = 1/8.

I(q) ≈ n. erf(q.α), (4.4)
where α is a constant, and erf the error function defined as:

erf(x) = 2 √ π x 0 e -t 2 dt.
In order to verify this hypothesis numerically, for a Hamming weight leakage with additive

Gaussian noise, we have plotted in Figure 4.2 the estimated parameter α for different values of σ and different number of traces. The mutual information is estimated using the law of large numbers and therefore, the parameter α is obtained by:

α = erf -1 (I(X; Y | T)/n) q
Notice that for each value of σ, α is constant, which suggest that our empirical model fits the MI well.

We can go even further and find the analytic value of α. Indeed, the first order derivative of our model is nα 2 √ π e -q 2 , therefore, the slope at the origin is nα 2 √ π . We know that I(0) = 0 and

I(1) = I(X; Y | T ) ≈ 1 2 log 2 (1 + SNR).
This means that if we approximate ∂I(q) ∂q (0) by I(1) -I(0), we have:

1 2 log 2 (1 + SNR) = nα 2 √ π , (4.5)
and therefore,

α = √ π 4n log 2 (1 + SNR). (4.6)
Therefore, given the value of the SNR, one can predict the value of MI for additive Gaussian noise. We can see that the approximation (4.4) holds very well for σ > 2. This happens for low values of SNR as we encounter in practice when evaluating cryptographic devices. The number of traces needed to reach a given success rate P s is therefore lower-bounded by:

q ≥ 4n √ π log 2 (1 + SNR) erf -1 n -H 2 (P s ) -(1 -P s ) log 2 (2 n -1) n (4.7)
The interest of such bound is that it requires only the knowledge of an additive Gaussian noise and the calculation of the SNR to be exploited and to therefore predict a tight bound on the number of traces to reach a given success rate. In this subsection, we consider a monobit leakage model:

f (t i ⊕ k) = LSB(S box (t i ⊕ k)) (i = 1, 2, . . . , q)
where S box is the AES substitution box and LSB is the least significant bit of a number. Figure 4.3 represents the success rate of a monobit leakage with additive Gaussian noise (standard deviation σ = 4). The distinguisher used is the maximum likelihood distinguisher which is optimal [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF].

The other curves are the bounds obtained with:

• a numerical estimation of I(X; Y | T) (using the law of large numbers, as described in

Comparison with Duc's Bound

In order to show that our bounds are tight, we have plotted the number of traces needed to reach a success rate of 90% for a monobit leakage with additional Gaussian noise (same leakage as Section 4.2.1). In this figure, we compare our bound with the ML distinguisher and the success rate proposed by Duc et al. in [START_REF] Duc | Making masking security proofs concrete -or how to evaluate the security of any leaking device[END_REF].

To compute our bound, we only suppose that the noise is AWGN and we apply the parametric estimation of the SNR, proposed in the previous subsection (cf. Equation (4.7)).

In Figure 4.6, we notice that our bound is always very close to the real success rate, calculated for the best case for the attacker. This means that our predictions give a good idea of the security of any device, and we recall that this prediction has been made with the only knowledge of a Gaussian noise. Therefore, with very low assumptions and very few measurements (needed to calculate the SNR), we are able to predict the number of traces to reach a given success rate with a good approximation.

Practical Applications

In practice, the estimation of the SNR is therefore crucial to estimate the protection level of a device. In this section, we propose an algorithm that extracts the SNR of a leakage. Then, in order to compare our results with real world data sets, we apply our methods to that obtained within the framework of the "DPA Contest" challenge.

The SNR estimation

In order to apply Theorem 3.1 or Equation 4.4 with the parametric estimation of the Mutual Information, one shall estimate the SNR of the leakage. When the leakage is monovariate, meaning that the attacker has at her disposal one share of the leakage, it is possible to estimate the SNR on-the-fly. The SNR of the leakage can be written as follows:

SNR = Var(Y ) Var(N ) = Var(Y ) Var(X -Y ) = Var(Y ) Var(X) -Var(Y )
.

We also notice that since X = Y + N , where the noise N is independent from the signal Y (which depends only on the plain/cipher-text T ), we have

Y = E[X | T ].
This means that the SNR can be estimated with:

SNR = Var(E[X | T ]) Var(X) -Var(E[X | T ]) . (4.8)
This equation is valid for algorithms such as AES, since the leakage model of AES does not depend on anything else than the 8 bits of the plaintext T .

When the leakage is multivariate, it is possible to compute dimensionality reduction (c.f. [15, Corollary 4]). In such case, a profiling phase is needed to estimate the noise covariance matrix.

Besides, other methods to estimate the SNR can be used such as Linear Discriminant Analysis (LDA) [START_REF] Standaert | Using Subspace-Based Template Attacks to Compare and Combine Power and Electromagnetic Information Leakages[END_REF].

A Real World Case: the DPA Contest

In order to compare our theoretical results with practical evaluations, we used the data set of the DPA Contest v1 [START_REF]DPA Contest[END_REF]. In the first version of this contest, the goal is to recover the 56-bit key of the DES encrypting algorithm. The device is a Side-channel Attack Standard Evaluation Board (SASEBO) developed by the Japan AIST / RCIS.

According to the data given in the DPA contest, the attacker has at her disposal a high number of traces, each made up of 20003 samples. An example is given in Fig. 4.7. We will consider here the first round of the algorithm (some attacks consider the last round but the results are very similar).

For example, we have plotted in Fig. 4.8 the SNR of this leakage considering the first substitution box. In this figure, we notice that the maximum value of the SNR is 0.144 but we notice that other points of interest may be used.

We have computed a simple CPA on the first round of DES with this data set to recover 6 bits of key. Figure 4.9 shows the partial success rate for all the substitution boxes. This success rate has been obtained with 100 experiments. We have plotted the CPA for the best time sample (the one that maximizes the SNR) in the green curve and the CPA over all the time samples (the blue curve). The red curves corresponds to the bound of Equation 4.7.

According to the figures of the table, without any pre-processing the attacker will need at least 243 traces to recover the secret key with one sample and 138 traces with two samples. This corresponds to the results obtained without pre-processing or Build-up Sub-keys.

However, in practice, other methods may help the attacker to increase the SNR of the leakage such as BS-CPA [START_REF] Komano | Built-in determined sub-key correlation power analysis[END_REF] where the attacker takes into account one broken subkey to recover others.

For such method, the upper-bound is the best SNR i.e. 0.151 for one sample leading to 107 traces for key extraction.

Conclusion

In this chapter, we have linked two metrics used in the field of side-channel analysis: the probability of success of an attack (also known as the success rate) and the mutual information between the leaked traces and the secret key. With such links, designers will be given more precise tools to secure their cryptographic chips. Our results are of interest to better understand the different factors that impact the success rate of an attack. This is the first time that a study gives universal tight bounds to the success rate, in the sense that these bounds are independent of what the attacker may exploit with the measurements. This is therefore a great improvement for designers. Indeed, in practice they are not able to know how their devices will be attacked in the future, but here, we allow them that to ensure the minimal security of their device in any adversarial context.

Conclusion

(a) Sbox # 0 (b) Sbox # 1 (c) Sbox # 2 (d) Sbox # 3
In addition, the link that we have made with the notion of guessing entropy gives an idea of how many attempts have to be made to recover the key after an attack.

Part

Introduction

Today's ciphering algorithms such as AES are considered resistant to cryptanalysis. This means that the best possible way to recover a 128 bit key is about as complex as to compute an exhaustive search over the 2 128 possibilities. With our current computational power, this is not achievable within a reasonable amount of time. However, it is possible to use plaintexts, ciphertexts, along with additional side information in order to recover the secret key of a device. Indeed, the secret key may leak via side-channels, such as the time to compute the algorithm, the power consumption of the device during the computation of the algorithm, or the electro-magnetic radiations of the chip.

In order to secure chips from side-channel attacks, designers have to understand how these work and what could be the future security breaches in the cryptographic algorithm as well as in the hardware computation. A preliminary step is to identify how the secret keys leak and deduce leakage models. Then, there are mathematical functions-called distinguishers-that take the leakage as argument and return an estimation of the secret key. They come in many flavours 1Leakage model SNR device acquisition platform crypto algo and have different figures of merit in different contexts. A given context not only involves the cryptographic algorithm and the device through the leakage model, but also the side-channel acquisition setup through the measurement characterized by its signal-to-noise ratio (SNR). This is illustrated in Fig. 5.1 borrowed from Heuser et al. [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF] (with our annotations in red).

In practice one may encounter monobit leakages, meaning that the output of the leakage model can only take two values. In this case, as we shall see, the mathematical computations turn to be simpler and information theoretic tools may be used to precisely describe the link between the leakage model and the real-world leaking traces. From another perspective, considering monobit leakages can also be seen as an "abstraction" trick meant to intentionally ignore the complex effect of the way the device leaks, thereby keeping only the contribution from the cryptographic algorithm in the leakage model.

A related question is how the choice of the substitution box in the cryptographic algorithm may "help" the attacker. The standard AES substitution box was designed to be very secure against linear and differential cryptanalysis [START_REF] Daemen | Rijndael for AES[END_REF]. On the contrary, under side-channel analysis, the substitution box may be helpful for the attacker, especially for monobit leakages as shown below.

Related Work. Distinguishers were often studied empirically, yet such an approach does not allow for generalizations to other contexts and measurement campaigns. A theoretical approach consists in analyzing the formal expressions of the distinguishers as mathematical functions.

WHEN MONOBIT LEAKAGES ARE DEFINED WITH THE CONFUSION COEFFICIENT

Fei et al. have shown that distinguishers such as DoM and CPA can be expressed in terms of a confusion coefficient [START_REF] Fei | A Statistical Model for DPA with Novel Algorithmic Confusion Analysis[END_REF]. They gave the impetus to extend this formal analysis to other types of distinguishers. In 2014, Heuser et al. [START_REF] Heuser | A Theoretical Study of Kolmogorov-Smirnov Distinguishers -Side-Channel Analysis vs. Differential Cryptanalysis[END_REF] relate KSA to the confusion coefficient, and also noticed that the confusion coefficient can be related to the resistance of a substitution box against differential cryptanalysis.

Whitnall and Oswald [START_REF] Whitnall | A Fair Evaluation Framework for Comparing Side-Channel Distinguishers[END_REF] have proposed the relative distinguishing margin metric to compare distinguishers. However, it has been shown [START_REF] Reparaz | A note on the use of margins to compare distinguishers[END_REF] that this metric may not be relevant in all contexts. Another way to compare distinguishers is to contrast how their success rate (SR)

in key recovery depends on the number q of side-channel traces. However, even if works such as [START_REF] Fei | A Statistical Model for DPA with Novel Algorithmic Confusion Analysis[END_REF] and [START_REF] Lomné | How to Estimate the Success Rate of Higher-Order Side-Channel Attacks[END_REF] were able to provide mathematically models for the SR, the comparison between different distinguishers has never been actually carried out based on such frameworks. We shall leverage instead on the so-called success exponent (SE) [START_REF] Sylvain Guilley | A Key to Success -Success Exponents for Side-Channel Distinguishers[END_REF] which allows to compare the SR of various distinguishers based on only one exponent parameter.

Our Contributions. In this chapter we consolidate the knowledge on side-channel attacks exploiting monobit leakages. We provide a rigorous proof that any distinguisher acting on monobit leakages depends on only two parameters: the confusion coefficient and the standard deviation of the noise. Some distinguishers, namely DoM, CPA and KSA, have already been expressed as a function of those two parameters [START_REF] Fei | A Statistical Model for DPA with Novel Algorithmic Confusion Analysis[END_REF][START_REF] Heuser | A Theoretical Study of Kolmogorov-Smirnov Distinguishers -Side-Channel Analysis vs. Differential Cryptanalysis[END_REF]. In this chapter, we derive this expression for MIA and we obtain a simple analytic function when the non zero values of the confusion coefficient are near 1 /2 (which is the case of leakages occurring at cryptographically strong substitution boxes [START_REF] Carlet | Trade-Offs for S-Boxes: Cryptographic Properties and Side-Channel Resilience[END_REF]).

Success exponents allow to characterize the efficiency (in terms of number of traces) of distinguishers to recover the key. We derive the success exponent of these distinguishers in Organization. The paper is organized as follows. In Section 5.2, we recall the main definitions.

In Section 5.3, we mathematically unify all the distinguishers and we show that they are only functions of two parameters. In Section 5.4, we compare the distinguishers thanks to the success exponent. Section 8.3 concludes. Appendices provide proofs for technical lemmas.

Modelization and Definitions

Distinguishers:

DoM [START_REF] Paul | Differential power analysis[END_REF], CPA [START_REF] Brier | Correlation power analysis with a leakage model[END_REF], Euclidean distance [39, §3], KSA [START_REF] Whitnall | An Exploration of the Kolmogorov-Smirnov Test as a Competitor to Mutual Information Analysis[END_REF], and MIA [START_REF] Gierlichs | Mutual information analysis[END_REF] How to study?

Empirical simulations [START_REF] Whitnall | A Fair Evaluation Framework for Comparing Side-Channel Distinguishers[END_REF] Theoretical formalization Asymptotic or Concrete q → ∞ and/or SNR → 0 [START_REF] Mangard | One for all -all for one: unifying standard differential power analysis attacks[END_REF] Which results?

Finite q and SNR. See Table 5.1 Accurate equation of q → SR(q) [START_REF] Yunsi Fei | A statistics-based success rate model for DPA and CPA[END_REF][START_REF] Lomné | How to Estimate the Success Rate of Higher-Order Side-Channel Attacks[END_REF][START_REF] Rivain | On the Exact Success Rate of Side Channel Analysis in the Gaussian Model[END_REF] Compare SR using SE. See Table 5.2 Notations. Throughout this chapter, we use calligraphic letters to denote sets and lower-case letters for elements in this set (e.g. x ∈ X). Capital letters denote random variables. For example, X is a random variable taking values in X and x ∈ X is a realization of X. The probability that X is x is noted P(X = x) or simply P(x) when there is no ambiguity. The expectation of a random variable is noted E[X] and its variance Var(X). The differential entropy h(X) of a random variable X following distribution p(x) is defined as

h(X) = - R p(x) log 2 p(x) dx.
(5.1)

The mutual information between two random variables X and Y is defined as

I(X; Y ) = h(X) -h(X|Y ) = E log 2 P(X, Y ) P(X)P(Y ) . (5.2)

Modelization and Definitions

The Leakage Model

In order to compare the different distinguishers for monobit leakages, we need a leakage model upon which our computations will be based. A plaintext t meets the secret key k * through a leakage function f (t, k * ). The resulting variable y(k * ) is called the sensitive variable. The dependence in the plaintext t will be omitted to make equations easier to read when there is no ambiguity.

The attacker measures a noisy version of y(k * ) called trace and denoted by x. When the key is unknown, the attacker computes a sensitive variable with a key hypothesis k, that is,

y(k) = f (t, k
). Thus our model takes the form

y(k) = f (t, k) x = y(k * ) + n (5.3)
where n is an independent measurement noise.

As we consider monobit leakages, we suppose that y(k) can take only two values. In practice, t (resp. k) are subsets of the full plaintext (resp. key). Typically, in the case of AES where attacks can be conducted using a divide-and-conquer approach on a per substitution box basis, t and k are 8-bit works (i.e., bytes).

The above leakage model can also be written using random variables. Let T the random variable for the plaintext, Y (k) for the sensitive variable, X for the measurement, and N for the Gaussian noise. We have:

Y (k) = f (T, k) X = Y (k * ) + N. (5.4)
In a view to simplify further mathematical computations, we suppose that the leakage random variable is reduced, that is, centered (E[Y (k)] = 0 for all k) and of unit variance (E[Y (k) 2 ] = 1 for all k). The noise is also assumed Gaussian of zero mean and its standard deviation is noted σ > 0. Moreover, we assume that for any key hypothesis the sensitive variable is balanced, that is, P(y(k)) = 1 2 . Since Y (k) is a binary random variable, we necessarily have that Y (k) ∈ {±1} in our model, and consequently the signal-to-noise ratio equals SNR = 1/σ 2 .

Last, we suppose that the attacker has at his disposal a number of q traces x 1 , . . . , x q obtained from leaking sensitive variables y 1 (k * ), . . . , y q (k * ) under additive noise n 1 , . . . , n q .

The Confusion Coefficient

In the side-channel context, the confusion coefficient was defined by Fei Mathematically, the confusion coefficient is written as

κ(k, k * ) = P(Y (k) = Y (k * )).
(5.5)

As the secret key k * is constant and understood from the context, we can write κ(k, k * ) = κ(k).

Notice that in practical situations, the EIS (Equal Images under different Subkeys [77, Def. 2]) assumption holds, therefore κ is actually a function of the key bitwise XOR difference k ⊕ k * . ) and ⊕ is the bitwise exclusive or. We notice that except for k = k * (here taken = 178), the confusion The original definition of the confusion coefficient [START_REF] Fei | A Statistical Model for DPA with Novel Algorithmic Confusion Analysis[END_REF] considers only monobit leakages. An extension for any type of leakage was proposed in [START_REF] Sylvain Guilley | A Key to Success -Success Exponents for Side-Channel Distinguishers[END_REF] where κ(k) is defined by

Modelization and Definitions

κ(k) = E Y (k * ) -Y (k) 2 2 .
(5.6) Equation (5.5) can be easily recovered from this more general expression by noting that when

Y (k) and Y (k * ) ∈ {±1}, Y (k * )-Y (k) 2 2 is 0 or 1 according to whether Y (k) = Y (k * ) or Y (k) = Y (k * ).

Distinguishers

Distinguishers aim at recovering the secret key k * from the traces and the model. For every key k, the attacker computes the associated distinguisher. The key hypothesis that gives the highest value of the distinguisher is the estimated key. The attack is successful if the estimated key is equal to the secret key.

For every key hypothesis k, a distinguisher is noted D(k) and the estimated key is k = arg max k D(k). Five classical distinguishers are:

• Difference of Means (DoM) [START_REF] Fei | A Statistical Model for DPA with Novel Algorithmic Confusion Analysis[END_REF], also known as the Differential Power Analysis (DPA) [START_REF] Paul | Differential power analysis[END_REF] where the attacker computes

D(k) = i|yi(k)=+1 x i i|yi(k)=+1 - i|yi(k)=-1 x i i|yi(k)=-1
.

(5.7)

• Correlation Power Analysis (CPA) [START_REF] Brier | Correlation power analysis with a leakage model[END_REF] where the attacker computes the absolute value of the Pearson coefficient

D(k) = 1 q q i=1 x i y i (k) -1 q q i=1 x i • 1 q q i=1 y i (k) Var(X)Var(Y i (k)) . (5.8)
Notice that Var(Y i (k)) do not depend on the index i, since repeated measurements are i.i.d.

• Euclidean distance, which corresponds to the Maximum Likelihood (ML) attack under the Gaussian noise hypothesis, where the attacker actually computes the negative Euclidean distance between the model and the trace

D(k) = - 1 q q i=1 (x i -y i (k)) 2 .
(5.9)

Maximizing the value of the distinguisher amounts to minimizing the Euclidean distance.

According to [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF], as the noise is Gaussian and additive, the Euclidean distance is the optimal distinguishing rule (ML rule) that maximizes the success probability.

• Kolmogorov-Smirnov Analysis (KSA) [START_REF] Whitnall | An Exploration of the Kolmogorov-Smirnov Test as a Competitor to Mutual Information Analysis[END_REF] where the traces are used to build an estimation of the cumulative density function F (x), and the distinguisher is

D(k) = -E Y (k) F (x|Y (k)) -F (x) ∞ (5.10)
where the infinite norm is defined as

F (x) ∞ = sup x | F (x)|.
Maximizing the value of the distinguisher amounts to minimizing the expected infinite norm.

Modelization and Definitions

• Mutual Information Analysis (MIA) [START_REF] Gierlichs | Mutual information analysis[END_REF] where the attacker computes the mutual information between the traces and each model. The traces are used to build an estimation of the joint distribution of X and Y (k), denoted by p(X, Y (k)), and with this estimation, we calculate the mutual information

D(k) = x,y(k) p(x, y(k)) log 2 p(x, y(k)) p(x) • p(y(k))
.

(5.11)

Given the available data, the attacker computes the distinguisher as a function of x 1 , . . . , x q and y 1 (k), . . . , y q (k). To emphasize the dependence on the data, we may write D(k) = D(X 1 , . . . , X q , Y 1 (k), . . . , Y q (k)). As these traces are realizations of random variables, we may also consider D(k) as a random variable which is a function of X 1 , . . . , X q and Y 1 (k), . . . , Y q (k),

with expectation E[ D(k)] and a variance Var( D(k)).

When the number of queries q tends to infinity, we assume that the distinguisher converges in the mean-squared sense:

Definition 5.1 (Theoretical Distinguisher [START_REF] Sylvain Guilley | A Key to Success -Success Exponents for Side-Channel Distinguishers[END_REF]). The theoretical value of the distinguisher is defined as the limit in the mean square sense when q → ∞ of the distinguisher. The notation for the theoretical distinguisher is D(k), which is therefore implicitly defined as:

E[( D(k) -D(k)) 2 ] -→ 0 as q → ∞.
(5.12)

Put differently, D(k) can be seen as an estimator of D(k). An illustration of theoretical distinguishers is provided in the lower right graph of Figure 5.4. It is easily seen that as q → +∞ the distinguishers presented previously have the following theoretical distinguishers:

• For DoM, the theoretical distinguisher is

D(k) = E[XY (k)]. (5.13)
• For CPA, the theoretical distinguisher is

D(k) = E[XY (k)] -E[X]E[Y (k)] 1 + σ 2 .
(5.14)

• For Euclidean distance (ML) distinguisher, we have:

D(k) = -E (X -Y (k)) 2 .
(5.15)

• For KSA, we have:

D(k) = E Y (k) F (x|Y (k)) -F (x) ∞ .
(5.16)

• For MIA, it is the mutual information

D(k) = I(X; Y (k)). ( 5

Theoretical Expressions for Distinguishers

In this section, we show that all distinguishers for monobit leakages are functions of only two parameters: the confusion coefficient κ(k) and the SNR = 1/σ 2 . This is confirmed by the closed-form expressions for classical distinguishers. In particular we derive the one corresponding to MIA. -1 Proof. To prove that the channel is symmetric, we show that both transition probabilities coincide: p = p . In fact, from Fig. 5.5, .20) This proves that the BSC has transition probability equal to κ(k).

1 -p -1 +1 1 -p +1 p p Y (k) Y (k * )
1 2 = P(Y (k * ) = 1) = pP(Y (k) = -1) + (1 -p )P(Y (k) = 1) = 1 2 (p + 1 -p ) hence p = p . Now the confusion coefficient κ(k) = P(Y (k) = Y (k * )) can be expanded as κ(k) = 1 2 P(Y (k) = Y (k * )|Y (k) = 1) + P(Y (k) = Y (k * )|Y (k) = -1) (5.18) = 1 2 P(Y (k * ) = -1|Y (k) = 1) + P(Y (k * ) = 1|Y (k) = -1) (5.19) = 1 2 p + p = p = p . ( 5
According to a well-known information theoretic result [23, p. 187], the Shannon's capacity in bits per bit of this channel is

C = 1 -H 2 (κ(k)), (5.21)
where H 2 (x) is the binary entropy function defined by

H 2 (x) = x log 2 1 x + (1 -x) log 2 1 1 -x . (5.22)
This is represented in Fig. 5.6 as a function of κ(k). Interestingly, the value κ(k) = 1 /2 corresponds to null capacity while the capacity is evidently 1 bit per bit for κ(k * ) = 0, since in this case the above communication channel reduces to the identity.

A General Result

We can now explain why all distinguishers for monobit leakages depend only on the two parameters κ(k) and SNR = σ The sum over y(k * ) has two terms and both cases are represented. Moreover, the Gaussian noise is independent from every other random variable. Therefore, we have two possibilities for the joint probability:

p(x, y(k)) =    1 2 ϕ( 1+n σ )κ(k) + ϕ( -1+n σ )(1 -κ(k)) 1 2 ϕ( -1+n σ )κ(k) + ϕ( 1+n σ )(1 -κ(k)) (5.26)
where ϕ(x) is the probability density function of a standard normal random variable. As the noise is centered and Gaussian, the only parameter that characterizes ϕ is its standard deviation σ. Therefore, a joint distribution of a monobit leakage is fully characterized by σ and κ(k).

This proves that the knowledge of the confusion coefficient and the noise power are essential to predict the performances of the side-channel attacks for monobit leakages.

Classical Distinguishers as Functions of κ(k) and σ 2

To highlight the result of section 5.3.2, we compute the classical distinguishers according to the confusion coefficient and the noise power. As we mentioned in the introduction, some of them have already been expressed according to these variables: we recall these results in Table 5.1

with references to the articles where the expression of the distinguisher in terms of κ(k) is proven.

These expressions confirm the strong link between confusion coefficient (recall Fig. 5.3) and the values of the theoretical distinguisher (for all key hypotheses, recall Fig. 5.4).

Distinguisher

Original Theoretical expression Reference paper with κ(k)

DoM [45] D(k) = 2( 1 /2 -κ(k)) [52] CPA [11] D(k) = 2 | 1 /2-κ(k)| √ 1+σ 2 [52] Euclidean distance [39, §3] Lemma 5.2 This chapter KSA [90] D(k) = erf 1 2σ 2 | 1 /2 -κ(k)| [38]
MIA [START_REF] Gierlichs | Mutual information analysis[END_REF] Lemma 5.3 This chapter Table 5.1: Summary of classical distinguishers. Among all the classical theoretical distinguishers, we notice that the expression of the theoretical value of DoM with κ(k) does not depend on σ.

The new results are given by the following lemmas.

Lemma 5.2. For monobit leakages, the Euclidean distance distinguisher can be expressed as:

D(k) = 4( 1 /2 -κ(k)) -(σ 2 + 2).
(5.27)

Proof. We have D(k) = -E (X -Y (k)) 2 = -E (Y (k * )-Y (k)+N ) 2 = -E (Y (k * )-Y (k)) 2 - σ 2 since the noise is independent from Y (k * ) -Y (k). Then by (5.6), D(k) = -4κ(k) -σ 2 = 4( 1 /2 -κ(k)) -2 -σ 2
where we have stressed the dependence in 1 /2κ(k) as in Table 5.1.

Lemma 5.3. For monobit leakages, when κ(k) ≈ 1 /2 for k = k * , the MIA distinguisher can be expressed at first order as:

D(k) = 2 log 2 (e)(κ(k) -1 /2) 2 g(σ) (5.28)
where

g(σ) = 1 2 E tanh 2 Z σ + 1 σ 2 + tanh 2 Z σ - 1 σ 2 (5.29)
and Z ∼ N(0, 1). The function g satisfies

lim σ→0 g(σ) = 1 and lim σ→∞ σ 2 × g(σ) = 1. (5.30)
Proof. See Appendix B.1.

Figure 5.7 plots the shape of g(σ) which tends to 1 when σ → 0 and is equivalent to

1 σ 2
when σ → ∞.

When k = k * the MIA distinguisher also has a simple expression since it reduces to the known expression of the channel capacity for channels with binary input and additive Gaussian noise [9, p. 274]: We also notice that MIA is in bijection with CPA (and therefore KSA). Indeed, according to the value of MIA with κ(k), the distinguisher is a function of ( 2 . This means that for monobit leakages, any attack that works with one of these distinguishers will also work with another, and vice versa.

D(k * ) = 1 σ 2 - R e -1 2 y 2 2π log 2 cosh( 1 σ 2 - y σ 2 )dy. ( 5
1 /2 -κ(k)) 2 which is in bijection with | 1 /2 -κ(k)| = ( 1 /2 -κ(k))

Mathematical Expression of SE

In the previous section, we have computed the theoretical values of the classical distinguishers in terms of κ(k) and σ. Now, we wish to compare their success rate. As we mentioned Section 5.2.3, the attacker computes the estimated distinguisher D(k) to recover the secret key. This is the main reason why all distinguishers do not perform equally in key recovery; indeed, they do not converge at the same speed towards their theoretical value.

In order to compare them, we have computed their success exponent, a metric proposed by Guilley et al. in [START_REF] Sylvain Guilley | A Key to Success -Success Exponents for Side-Channel Distinguishers[END_REF] that evaluates how fast the success rate of a distinguisher converges to 100%. With a Gaussian assumption, they prove that the success rate can be modeled as

SR = 1 -exp(-q × SE), (5.32)
where q is the number of traces and SE ∈ R + is the so-called success exponent. Therefore, the greater the success exponent is, the faster the convergence of the success rate.

We present the theoretical values of the success exponent for the different distinguishers in

(X -Y (k)) 2 = -X 2 + 2XY (k) -1
, and X 2 is independent of the choice of the key.

of κ(k) and σ. Therefore, if the attacker only knows the type of substitution box that is used and the SNR of the leakage, he can predict how fast he recovers the secret key.

Lemma 5.4 (Success exponent of CPA). The success exponent of CPA1 is:

SE = 1 2 min k =k * 1 -2| 1 /2 -κ(k)| 1 + 2σ 2 + 2| 1 /2 -κ(k)| .
(5.33)

Proof. See Appendix B.2.

Lemma 5.5 (Success exponent of KSA). Assuming that the distributions are estimated with the kernel method using Heaviside step function, the success exponent of KSA is

SE = 1 2 min k =k * erf 1 √ 2σ 2 ( 1 /2 -| 1 /2 -κ(k)|) 2 -erf 1 √ 2σ 2 ( 1 /2 -| 1 /2 -κ(k)|) . ( 5
SE = 4 log 2 (e) 2 σ 4 min k =k * κ(k) 2 (1 -κ(k)) 2 .
(5.35)

Proof. See Appendix B.4.
In order to validate our theoretical results, we have simulated attacks within the monobit model presented in Sec. 5.2. The success rates of these attacks are presented in Fig. 5.8. In

Comparison of Distinguishers Based on their Success Exponent

With the theoretical expressions of the Success Exponent, it is now possible to rank distinguishers for a given value of σ and a specific set of confusion coefficients (κ(k)) k =k * .

We first show that for all of the distinguishers presented in Table 5.2, the key that minimizes the expression of the success exponent is either the one that minimizes κ(k) or the one that maximizes κ(k) (for k = k * ). Indeed, there are only two values of κ(k), k = k * , which are relevant for the comparison of distinguishers presented in Table 5.2.

Lemma 5.7. For all value of σ, the value of k = k * which minimizes the formal expressions of monobit distinguishers is either

k min = argmin k =k * κ(k) (nearest rival) or k max = argmax k =k * κ(k) (furthest rival).
Proof. For each distinguisher, let us replace κ(k) by a real-valued variable x ∈ [0, 1] in the formal expression of the theoretical distinguishers given in the second column of Tab. 5.2. If the expression which is a function of x is increasing, then its minimum value over {κ(k), k = k * } ⊂ [0, 1] is κ min = κ(k min ). Symmetrically, if the function of x is decreasing, than its minimum value over {κ(k), k = k * } ⊂ [0, 1] is κ max = κ(k max ). The argument of the minimum operator is always either strictly increasing or decreasing with x. Indeed, we take the derivative of each function and we notice that it is always positive for any value of x ∈ [0, 1]:

• For DoM and Euclidean distance:

∂ ∂x 1 2 x 1+σ 2 -x = 1 2 1+σ 2 (1+σ 2 -x) 2 > 0.
• For CPA, we distinguish to cases. Either, the minimum is reached for a value k 0 such that ( 1 /2κ(k 0 )) is greater than 0, and in this case, the value of the success exponent is equal to the Success Exponent of DoM (and thus k 0 = κ min ), or ( 1 /2κ(k 0 )) is lower than 0. In this last case, the value of the Success Exponent is

1 2 1-κ(k) σ 2 +κ(k) . The derivative of this function is ∂ ∂x 1 2 1-x σ 2 +x = -σ 2 +1
(σ 2 +x) 2 < 0. This means that the higher x is, the smaller the success exponent is. Hence, k 0 = κ max .

• For KSA, the computation is similar to the case of CPA. Either the value which minimizes the expression in Lemma 5.5 is k 0 , such that ( 1 /2κ(k 0 )) is greater than 0, in which case the Success Exponent is equal to

erf 1 √ 2σ 2 2 κ(k0) 2-erf 1 √ 2σ 2 κ(k0)
, or ( 1 /2κ(k 0 )) is negative, in which case the Success Exponent is equal to

erf 1 √ 2σ 2 2 1-κ(k0) 2-erf 1 √ 2σ 2 (1-κ(k0))
. Now,

∂ ∂x erf 1 √ 2σ 2 2 x 2-erf 1 √ 2σ 2 x = erf 1 √ 2σ 2 (2-x) 2 > 0, hence κ(k 0 ) = κ min , and ∂ ∂x erf 1 √ 2σ 2 2 1-x 2-erf 1 √ 2σ 2 (1-x) = - erf 1 √ 2σ 2 (2-x) 2 < 0, hence κ(k 0 ) = κ max . • For MIA, ∂ ∂x x 2 (1 -x) 2 = 4x(1 -x)( 1 2 -x)
, which has the sign of 1 2x. As 0 ≤ x ≤ 1, the Success Exponent for MIA is thus increasing on [0, 1 /2] and decreasing on [ 1 /2, 1]. Thus, the minimum value of the Success Exponent is either occurring for κ min (if κ min < 1κ max ) or for κ max . This means that the wrong key k that determines the minimum value in the closed form of the Success Exponent in the expressions from Tab. 5.2:

• (regarding DoM and Euclidean distance): is also the one which happens to minimize κ(k), k = k * , i.e., the nearest rival of the correct key k * ;

• (regarding CPA, KSA and MIA): is also the one which corresponds to the nearest confusion coefficient from its bounds (either 0 or 1). Lemma 5.7 validates the role of Relative Distinguishing Margin (RDM [START_REF] Whitnall | A Fair Evaluation Framework for Comparing Side-Channel Distinguishers[END_REF]) metric while comparing distinguishers. Indeed, the distinguishers DoM and Euclidean distance (resp. CPA, and at first order, KSA and MIA) only consider the nearest rivals (resp. nearest or furthest) in terms of confusion coefficient. This is general property of the distinguisher, since it does not depend on the noise variance σ 2 .

However, we will highlight other factors that determine the efficiency in terms of "datacomplexity" of the classical distinguishers. To illustrate Lemma 5.7, we have reported in Table 5.3 the 32 κ min and κ max for the 32 possible fanout bits of Data Encryption Standard (DES) substitution boxes (sboxes). These values correspond to the 8 sboxes in DES multiplied by the 4 bits of the output of the LUT. In this table, we notice that each sbox has a particular behaviour. The value which determines the success exponent represented with a grey background color. It is interesting to see that CPA, KSA and MIA are actually limited by κ max most of the time (i.e., 1κ max < κ min , for about 89% of the bits, excluding ties).

Remark 5.2. It was previously unnoticed that, in the case of DES, distinguishers with "absolute values", such as CPA, were better than without the absolute values.

Regarding AES, we notice that for the AES SubBytes function, the values of κ min and κ max are always the same regardless to the leaking bit. Moreover, we also notice that κ min = 1κ max .

Indeed, for all output bits of SubBytes, we have:

• κ min = 0.4375 • κ max = 0.5625. vice-versa.
Proof. It is easy to check that 1 2

κ min 1 + σ 2 -κ min < 1 2 1 -κ max σ 2 + κ max ⇐⇒ κ min (σ 2 + κ max ) < (1 + σ 2 -κ min )(1 -κ max ) ⇐⇒ κ min < 1 -κ max .
Lemma 5.9 (KSA expression of SE). The expression of the Success Exponent for KSA (for large values of σ) is:

         erf 1 √ 2σ 2 2 κmin 2-erf 1 √ 2σ 2 κmin if κ min < 1 -κ max , erf 1 √ 2σ 2 2 1-κmax 2-erf 1 √ 2σ 2 (1-κmax) if κ min > 1 -κ max . Proof. It is a direct consequence of the fact the function x ∈ [0, 1] → erf 1 √ 2σ 2 2 x 2-erf 1 √ 2σ 2
x is increasing (recall Lemma 5.7).

Lemma 5.10 (MIA expression of SE). The expression of the Success Exponent for MIA (for large values of σ) is:

4 log 2 (e) 2 σ 4 κ 2 min (1 -κ min ) 2 if κ min < 1 -κ max , 4 log 2 (e) 2 σ 4 κ 2 max (1 -κ max ) 2 if κ min > 1 -κ max .
Proof. We have:

4 log 2 (e) 2 σ 4 κ 2 min (1 -κ min ) 2 < 4 log 2 (e) 2 σ 4 κ 2 max (1 -κ max ) 2 ⇐⇒ κ min (1 -κ min ) < κ max (1 -κ max ) ⇐⇒ (κ max -κ min ) [κ max + κ min -1] < 0 ⇐⇒ κ min < 1 -κ max .
Corollary 5.1 (Revised expressions of the Success Expoennt for the 5 distinguishers). With κ min and κ max defined in Lemma 5.7, the success exponents of the 5 distinguishers are written in Table 5.4. For CPA, KSA and MIA, there are two expressions depending whether κ min ≶ κ max .

Now, we can proceed to compare distinguishers:

Proposition 5.1 (DoM is always better than CPA). For any value of σ, the success exponent of DoM is always greater than the success exponent of CPA.

Comparing Distinguishers with the Success Exponent

Distinguisher Condition κ min < 1 -κ max κ min > 1 -κ max DoM 1 2 κmin 1+σ 2 -κmin CPA 1 2 κmin 1+σ 2 -κmin 1 2 1-κmax σ 2 +κmax
Euclidean distance Proof. The expression of CPA is either with κ min or with κ max . We therefore have two cases:

1 2 κmin 1+σ 2 -κmin KSA 1 2 erf 1 √ 2σ 2 κmin 2-erf 1 √ 2σ 2 κmin 1 2 erf 1 √ 2σ 2 (1-κmax) 2-erf 1 √ 2σ 2 (1-κmax) MIA 4 log 2 (e) 2 σ 4 κ 2 min (1 -κ min ) 2 4 log 2 (e) 2 σ 4 κ 2 max (1 -κ max ) 2
• If κ min < 1κ max , then the expression of CPA is the same as the expression of DoM (cf. Table 5.4). Therefore, the success exponents of the two distinguishers are the same in this case.

• In the other case, the expression of the success exponent is1 2 1-κmax σ 2 +κmax . However, as 1κ max < κ min , we have 1 2 1-κmax σ 2 +κmax < κmin 1+σ 2 -κmin , which is the expression of DoM. Therefore, in this case, the success exponent of CPA is smaller than the success exponent of DoM.

Overall, DoM is therefore a better distinguisher than CPA in terms of success exponent. Proposition 5.2 (CPA vs KSA). When σ 1 the success exponent of CPA is always higher than the success exponent of KSA.

Proof. We consider that σ 1. This means that the success exponent of CPA (we consider the formula with κ min ) is equivalent to 1 2 κmin σ 2 . For KSA, the success exponent is equivalent to

1 2 κmin πσ 2 . Indeed, when σ 1, 1 √ 2σ
2 is equivalent to 2 πσ 2 . Therefore, when σ 1, the success exponent of CPA is always higher than the success exponent of KSA. The calculations are the same if we consider κ max . Proposition 5.3 (MIA vs DoM). For σ > 1, the success exponent of MIA is always smaller than the success exponent of CPA.

Proof. For DoM, the expression of the success exponent is proportional to 1 σ 2 while the expression of the success exponent for MIA is proportional to 1 σ 4 .

To highlight these lemmas, we have plotted in Figure 5.10 the success exponents obtained for every distinguisher with respect to the value of σ. We notice that the order obtained in the previous lemmas is verified 1 In this case, the value of κ min is lower than the value of 1κ max .

Therefore, the Success Exponent based on the value κ min will be used. In the state-of-the-art, the only assertion which could be done was that the optimal distinguisher is performing the best, i.e., it is better than all others. However, in general, it was difficult to formal and numerical comparison between distinguishers was not possible. We enable that. More precisely, we rate distinguishers according to whether they match for minimum or maximal values of κ. Then, we classify them when there is one distinguisher better than another one over the full range of σ > 0. Finally, we show that depending on the values of κ min and κ max , some distinguishers might be better than others.

Conclusion

Conclusion

In this chapter, we have mathematically proven that only two parameters, the confusion coefficient and the SNR, determine the side-channel distinguishing efficiency for monobit leakages. Both of

Introduction

Many embedded systems implement cryptographic algorithms, which use secret keys that must be protected against extraction. Side-channel analysis (SCA) is one effective threat: physical quantities, such as instant power or radiated electromagnetic field, leak outside the embedded system boundary and reveal information about internal data. SCA consists in exploiting the link between the leakage signal and key-dependent internal data called sensitive variables.

The cryptographic algorithm is generally public information, whereas the implementation details are kept secret. For high-end security products, the confidentiality of the design is mandated by certification schemes, such as the Common Criteria [START_REF]Common Criteria (aka CC) for Information Technology Security Evaluation[END_REF]. For instance, to comply with ALC_DVS (Life-Cycle support -Development Security) requirement, the developer must provide a documentation that describes "all the physical, procedural, personnel, and other security measures that are necessary to protect the confidentiality and integrity of the TOE (target of evaluation) design and implementation in its development environment" [22, clause 2.1 C at page 141]. In particular, an attacker does not have enough information to precisely model the leakage of the device. On commercial products certified at highest evaluation assurance levels (EAL4+ or EAL5+), the attacker cannot set specific secret key values hence cannot profile

Introduction

the leakage1 Therefore, many side-channel attacks can only be performed online using some distinguisher.

Correlation Power Analysis (CPA) [START_REF] Brier | Correlation Power Analysis with a Leakage Model[END_REF] is one common side-channel distinguisher. It is known [39, Theorem 5] that its optimality holds only for a specific noise model (Gaussian) and for a specific knowledge of the deterministic part of the leakage-namely it should be perfectly known up to an unknown scaling factor and an unknown offset.

Linear Regression Analysis (LRA) [START_REF] Doget | Univariate side channel attacks and leakage modeling[END_REF] has been proposed in the context where the leakage model is drifting apart from a Hamming weight model. Its parametric structure and ability to include several basis functions makes it a very powerful tool, that can adjust to a broad range of leakage models when the additive noise is Gaussian. Incidentally, CPA may be seen as a 2-dimensional LRA [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF].

When both model and noise are partially or fully unknown, generic distinguishers have been proposed, such as Mutual Information Analysis (MIA) [START_REF] Gierlichs | Mutual information analysis[END_REF], Kolmogorov-Smirnov test [START_REF] Veyrat-Charvillon | Mutual Information Analysis: How, When and Why?[END_REF][START_REF] Whitnall | An Exploration of the Kolmogorov-Smirnov Test as a Competitor to Mutual Information Analysis[END_REF] or Cramér-von-Mises test [START_REF] Veyrat-Charvillon | Mutual Information Analysis: How, When and Why?[END_REF]Sec. 3.3.]. Thorough investigations have been carried out (e.g., [START_REF] Carbone | On adaptive bandwidth selection for efficient MIA[END_REF][START_REF] Moradi | A Comparative Study of Mutual Information Analysis under a Gaussian Assumption[END_REF][START_REF] Whitnall | A Comprehensive Evaluation of Mutual Information Analysis Using a Fair Evaluation Framework[END_REF]) to identify strengths and weaknesses of various distinguishers in various scenarios, including empirical comparisons. In keeping with these results, we aim at showing some mathematical justification regarding MIA versus CPA and LRA. Our goal is thus to structure the field of attacks, by providing theoretical motivations why attacks strength may differ, irrespective of the particular traces datasets.

Contributions. In this chapter, we derive MIA anew as the distinguisher which maximizes the success rate when the exact probabilities are replaced by online estimations. In order to assess the practicability of this mathematical result, we show two scenarios where MIA can outperform its competitors CPA and LRA, which themselves do not estimate probabilities.

In these scenarios, we challenge the two hypotheses needed for CPA to be optimal: additive Gaussian noise and perfect knowledge of the model up to an affine transformation. This is illustrated in Fig. 6.1.

Last, we extend the fast computation trick presented in [START_REF] Lomné | Behind the Scene of Side Channel Attacks[END_REF] to MIA: the distinguisher is only computed from time to time based on histograms obtained by accumulation, where the accumulated histograms are shared for all the key guesses.

WHEN MIA IS A MAXIMUM LIKELIHOOD AND BETTER THAN CPA

CPA is optimal [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF]:

• known model,

• Gaussian noise. Section 6.3: MIA > CPA:

• known model,

• non-Gaussian noise. Section 6.4: MIA > CPA, LRA:

• unknown model,

• Gaussian noise.

Optimality of Mutual Information Analysis

Notations and Assumptions

We assume that the attacker has at his disposal q independent online leakage measurements1

x = ( x 1 , . . . , x q )2 for some sequence of independent and uniformly distributed text n-bit words t = ( t 1 , . . . , t q ) (random but known). The n-bit secret key k * is fixed but unknown.

We do not make any precise assumption on the leakage model-in particular the attacker is not able to estimate the actual probability density in a profiling phase. Instead we choose an algorithmic-specific function f and a device-specific function ϕ to compute, for each key hypothesis k, sensitive values y = ( y 1 , . . . , y q ) by the formula y = ϕ(f (k, t)), (6.1)

Optimality of Mutual Information Analysis

that is, y i = ϕ(f (k, t i )) for all i = 1, . . . , q. In practice, a suitable choice of ϕ should be optimized depending on some leakage model but in what follows, f and ϕ can be taken arbitrarily such that they fulfill the following Markov condition. Thus, while the conditional distribution P k ( x| t) depends on the value k of the secret key, the expression P( x| y) depends on k only through y = ϕ(f (k, t)). If we let P k ( x, t) be the joint probability distribution of x and t when k * = k, one has the Fisher factorization [START_REF] Casella | Statistical Inference[END_REF] P k ( x, t) = P( t)P k ( x| t) = P( t)P( x| y) where y = ϕ(f (k, t)). (6.2)

In the latter expression we have P( t) = 2 -qn since all text n-bit words are assumed independent and identically distributed (i.i.d.) and uniformly distributed.

In the case of an additive noise model, we simply have x = y + n where n is the noise vector, and the Markov condition is obviously satisfied. In general, in order to fulfill the Markov condition the attacker needs some knowledge on the actual leakage model. We give two examples regarding the Markov condition:

Example 6.1. If leakage x i is linked to t i and k * through the relationship x i = w H (k * ⊕ t i ) + n i for all i = 1, . . . , q, where w H is the Hamming weight and n i is the noise (independent of t i ), then both models y i = k ⊕ t i and y i = w H (k ⊕ t i ) satisfy the Markov condition.

In order to uniquely distinguish the correct key, some conditions on the expressions of y are required. Specifically, let us denote by y k the function t → y k (t) = y(k, t), and let B the set of bijections on the leakage space X. We have:

if ∀k, ∃k = k, ∃β ∈ B s.t. y k = β • y k , then the distinguisher features a tie, (6.3) if ∀k, ∀k = k, ∃β ∈ B s.t. y k = β • y k , then the distinguisher is not sound . (6.4)
Indeed, in Eq. ( 6.3), there is no way for the distinguisher to tell k * from k , and in Eq. ( 6.4), the distinguisher yields the same value for all the key guesses1 . Sections 6.3 and 6.4 give other, more sophisticated, examples that satisfy the Markov condition.

Example 6.2. In the same scenario as in Example 6.1, consider the bit-dropping strategy (called 7LSB in [START_REF] Gierlichs | Mutual information analysis[END_REF] and used in [START_REF] Reparaz | Generic DPA Attacks: Curse or Blessing?[END_REF][START_REF] Whitnall | A Fair Evaluation Framework for Comparing Side-Channel Distinguishers[END_REF]). Then e.g., y i = (k ⊕ t i ) [1 : 7] (the first seven bit components) does not satisfy the Markov condition. Note that the leakage model in this example intentionally discards some information, hence may not be satisfactory [START_REF] Reparaz | Generic DPA Attacks: Curse or Blessing?[END_REF].

WHEN MIA IS A MAXIMUM LIKELIHOOD AND BETTER THAN CPA

Let k be the key estimate that maximizes a distinguisher D given x and t, i.e.,

k = arg max k∈K D( x, y) (6.5)
where K is the key space.

We also assume that leakage values are quantized 1 in a suitable finite set X. Letting Y denote the discrete sensitive value space, we have x ∈ X q and y ∈ Y q . The actual probability densities being unknown, the attacker estimates them online, during the attack, from the available data in the sequences x and y (via t), by counting all instances of possible values of x ∈ X and y ∈ Y:

P(x) = 1 q q i=1
1 xi=x , (6.6)

P(y) = 1 q q i=1
1 yi=y , (6.7)

P(x, y) = 1 q q i=1 1 xi=x, yi=y , (6.8)
P(x|y) = q i=1 1 xi=x, yi=y q i=1 1 yi= y = P(x, y) P(y) , (6.9)
where 1 A denotes the indicator function of A: 1 A = 1 if A is true and = 0 otherwise. which can also be written as

I( x, y) = H( x) -H( x| y), (6.11)
where the empirical entropies are defined as These quantities are functions of the sequences x and y since P(x, y) is a function of x and y.

H( x) = x∈X P(x) log 2 1 P(x) (6.
They also depend on the key guessed value k, via the expression of y.

1 Some side-channels are discrete by nature, such as the timing measurements (measured in units of clock period). In addition, oscilloscopes or data acquisition appliances rely on ADCs (Analog to Digital Converters), which usually sample a continuous signal into a sequence of integers, most of the time represented on 8 bits (hence X = F 8 2 ). 100 6.2 Optimality of Mutual Information Analysis

Mathematical Derivation

In this subsection, we show that MIA coincides with the maximum likelihood expression where leakage probabilities P are replaced by online estimated probabilities P. Definition 6.2 (Success Rate [START_REF] Standaert | A Unified Framework for the Analysis of Side-Channel Key Recovery Attacks[END_REF]Sec. 3.1]). The success rate (averaged over all possible secret key values) is defined as:

SR = 1 2 n 2 n -1 k=0 P k ( k = k). (6.14)
Here we follow a frequentist approach. An equivalent alternative Bayesian approach would be to assume a uniform prior key distribution [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF].

Theorem 6.1 (Maximum Likelihood [START_REF] Chari | Template Attacks[END_REF]). Let y = ϕ(f (k, t)). The optimal key estimate that maximizes the success rate (6.14) is:

k = arg max k P( x| y). (6.15)
Proof. We give here a formal proof, which nicely relates to Definition 6. Here P, defined in Equations (6.9), (6.8), (6.7) and (6.6), is estimated directly from the available data, that is, from the actual values in the sequences x and y. Theorem 6.2 (UML is MIA). The universal maximum likelihood key estimate is equivalent to the mutual information analysis (MIA) [START_REF] Gierlichs | Mutual information analysis[END_REF]:

P( x| y = ϕ(f (k, t))) 1 k= k (6.18) = 1 2 n( q+1) x, t P( x| y = ϕ(f (k = k, t))). ( 6
k = arg max k P( x| y) = arg max k I( x, y), (6.24)
where I( x, y) is the universal mutual information (definition 6.1).

Proof. Rearrange the likelihood product according to values taken by the x i and y i 's:

P( x| y) = q i=1 P( x i | y i ) =
x∈X,y∈Y P(x|y) nx,y (6.25)

where n x,y is the number of components ( x i , y i ) equal to (x, y), i.e., n x,y = q i=1 1 xi=x, yi=y = q P(x, y). (6.26)

The second inequality in Eqn. (6.25) is based on a counting argument: some events collide, i.e., we have (x i , y i ) = (x i , y i ) for i = i . The exponent n x,y is meant to enumerate all such possible collisions. This gives

P( x| y) = x∈X,y∈Y P(x|y) q P(x,y) = 2 -q H( x| y) , (6.27)
(see Definition 6.1). Therefore, maximizing P( x| y) amounts to minimizing the empirical conditional entropy H( x| y). Since H( x) is key-independent, this in turn amounts to maximizing the empirical mutual information I( x, y) = H( x) -H( x| y).

Optimality of Mutual Information Analysis

From Theorem 6.2 we can conclude that MIA is "optimal" as a universal maximum likelihood estimation. This constitutes a rigorous proof that mutual information is a relevant tool for key recovery when the leakage is unknown (in the case where the model satisfies the Markov condition) as was already hinted in [START_REF] Gierlichs | Mutual information analysis[END_REF][START_REF] Prouff | Theoretical and practical aspects of mutual information-based side channel analysis[END_REF][START_REF] Reparaz | Generic DPA Attacks: Curse or Blessing?[END_REF][START_REF] Whitnall | A Comprehensive Evaluation of Mutual Information Analysis Using a Fair Evaluation Framework[END_REF].

Corollary 6.1. MIA coincides with the ML distinguisher as q → ∞.

Proof. By the law of large numbers, the online probability P converges almost surely to the exact probability of the leakage as q → ∞. For any fixed values of x ∈ X, y ∈ Y,

P( x| y) -→ q→∞ P( x| y) a.s.
Thus in the limit, MIA coincides with the maximum likelihood rule.

Remark 6.1. It is well known [START_REF] Prouff | Theoretical and practical aspects of mutual information-based side channel analysis[END_REF] that if the mapping t → y = ϕ(f (k, t)) is one-to-one (for all values of k), then MIA cannot distinguish the correct key. This is also clear from Eq. ( 6.4) in footnote 1: given two different keys k, k , there is a bijection between y k and y k , which is simply

β = y k • y -1 k .
In our present setting this is easily seen by noting that when y = ϕ(f (k, t)),

P(x|y) = q i=1 1 xi=x, yi=y q i=1 1 yi=y = q i=1 1 xi=x, ti=t q i=1 1 ti=t (6.28)
is independent of the value k. Note that this is true for any fixed number of measurements q during the attack.

MIA Faster Than ML Distinguisher

Now that we have shown that the Universal Maximum Likelihood distinguisher is strictly equivalent to the MIA distinguisher, we show that the use of the MIA Distinguisher is cheaper in terms of calculations than the ML distinguisher. Both distinguishers require the knowledge of P, the online estimation of the leakage probability. However, the summation is not exactly the same:

• the ML distinguisher consists in a sum of q logarithms, whereas

• the MIA involves a sum over |X| × |Y| logarithms 1 .
This means that computing a ML requires q logarithm computations while computing a MIA requires |X| × |Y| logarithm computations. As long as |X| × |Y| is smaller than q, which is verified for practical signal-to-noise values, the MIA is faster than the ML in terms of logarithm computations. Furthermore, in section 6.5.2, we present a fast algorithm to compute MIA; it takes advantage of precomputations, which are similar to that already presented in [START_REF] Lomné | Behind the Scene of Side Channel Attacks[END_REF].

WHEN MIA IS A MAXIMUM LIKELIHOOD AND BETTER THAN CPA

Non-Gaussian Noise Challenge

In this section, we show two examples where MIA outperforms CPA due to non-Gaussian noise.

The first example presented in subsection 6.3.1 is an academic (albeit artificial) example built in order to have the success rate of CPA collapse. The second example in subsection 6.3.2 is more practical.

Pedagogical Case-study

We consider a setup where the variables are

X = Y + N , with Y = ϕ(f (k * , T )), where Y ∈ {±1},
and N ∼ U({±σ}) (meaning that N takes values -σ and +σ randomly, with probabilities1 2 and 1 2 ), where σ is an integer. Specifically, we assume that k * , t ∈ F n 2 , with n = 4, and that f :

F n 2 × F n 2 → F m
2 is a (truncated version) of the SERPENT Sbox 1 fed by the XOR of the two inputs (key and plaintext nibbles) and ϕ = w H is the Hamming weight (which reduces to the identity

F 2 → F 2 if m = 1 bit).
The optimal distinguisher (Theorem 6.1) in this scenario has the following closed-form expression:

D( x, t) = arg max k P( x| t, k) = arg max k 1 2 q q i=1 δ( x i , t i , k), (6.29)
where δ :

F m 2 × F n 2 × F n 2 → {0, 1} is defined as: δ(x, t, k) =      1 if x -ϕ(f (k, t)) = -σ, 1 if x -ϕ(f (k, t)) = +σ, 0 otherwise.
The evaluation of this quantity requires the knowledge of σ, which by definition is an unknown quantity related to the noise. Our simulations have been carried out as follows.

1. Generate two large uniformly distributed random vectors t and n of length q;

2. Deliver the pair of vectors ( t, x = ϕ(f (k * , t)) + n) to the attacker;

3. Estimate averages and PMFs (probability mass functions) of this data for q step (= 1), then for 2 q step , 3 q step and so on; 4. At each multiple of q step , carry out CPA and MIA.

Non-Gaussian Noise Challenge

The attacks are reproduced 100 times to allow for narrow error bars on the estimated success rate.

Remark 6.2. We do not consider linear regression analysis because the model is not parametric. The only unknown parameter is related to the noisy part of the leakage, not its deterministic part.

Simulation results are given in Fig. 6.2 for σ = 2 and σ = 4. The success rate of the "optimal" distinguisher (the maximum likelihood distinguisher of Theorem 6.1 -see Eqn. (6.29)) is drawn in order to visualize the limit between feasible (below) and unfeasible (above) attacks. It can be seen that MIA is almost as successful as the maximum likelihood distinguisher, despite the knowledge of the value of σ is not required for the MIA. In addition, one can see that the CPA performs worse, and all the worst as σ increases. In this case, the CPA is not the optimal distinguisher (as e.g., underlined in [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF]Theorem 5]) since the noise is not Gaussian (but discrete).

Remark 6.3. Another attack strategy for the leakage model presented in this subsection would simply be to filter out the noise. One could for instance dispose of all traces where the leakage is negative. The remaining traces (half of them) contain a constant noise N = +σ > 1, hence the signal Y can be read out without noise. Such attack, known as the subset attack [62, Sec. 5.2], is not far from the optimal one (Eqn. (6.29)). It actually does coincide with the optimal attack if the attacker recovers Y from both subsets {i/X i > 0} and {i/X i < 0}. Still it can noted that MIA is very close to being optimal for this scenario.

Asymptotics. We can estimate the theoretical quantities for CPA and MIA as follows. We have Var(Y ) = 1 and Var(N ) = σ 2 , hence a signal to noise ratio SNR = 1/σ 2 . In addition, X can only take four values:

±1 ± σ. Since E(XY ) = E(X 2 ) + E(Y N ) = V ar(X) + E(Y )E(N ) =
1 + 0 × 0 = 1, the correlation is simply ρ(X, Y ) = 1/σ, which vanishes as σ increases. 105

WHEN MIA IS A MAXIMUM LIKELIHOOD AND BETTER THAN CPA

However, for σ > 1, the mutual information

I(X, Y ) = 1 bit. Indeed, H(X) = -x∈{±1±σ} P(X = x) log 2 P(X = x) = -x∈{±1±σ} 1 4 log 2 1 4 = log 2 4 = 2 bit, H(X|y = ±1) = log 2 2 = 1 bit, so I(X, Y ) = log 2 4 -y∈{±1} P(X = x) log 2 2 = log 2 4 -log 2 2 = 1 bit, irrespective of σ ∈ N.
The important fact is that the mutual information does not depend on the value of σ.

Accordingly, it can be seen from Fig. 6.2 that the success rate of the MIA is not affected by the noise variance. This explains why MIA will outperform the CPA for large enough σ.

Application to Bitslice PRESENT

Bitslicing algorithms is a common practice. This holds both for standard [START_REF] Chester Rebeiro | Bitslice implementation of AES[END_REF] (e.g., AES) and lightweight [START_REF] Matsuda | Lightweight Cryptography for the Cloud: Exploit the Power of Bitslice Implementation[END_REF] (PRESENT, Piccolo) block ciphers. Here the distinguishers must be single-bit: Y ∈ {±1}. However, compared to the case of Sec. 6.3.1, the noise takes now more than two values: On an 8-bit computer, the 7 other bits will leak independently. They are, however, not concerned by the attack, and constitute algorithmic noise N which follows a binomial law α × B(7, 1 2 ), where α is a scaling factor.

Partially Unknown Model Challenge

Veyrat-Charvillon and Standaert [86, section 4] have already noticed that MIA can outperform CPA if the model is drifted too far away from the real leakage. However, LRA is able to make up for the model drift of [START_REF] Veyrat-Charvillon | Mutual Information Analysis: How, When and Why?[END_REF] (which considered unevenly weighted bits). In this section, we challenge CPA and LRA with a partially unknown model. We show that, in our example, MIA has a much better success rate than both CPA and LRA.

For our empirical study we used the following setup:

X = ψ(Y (k * )) + N, Y (k * ) = w H (S box (k * ⊕ T )),
where S box is the AES substitution box, ψ is the non-linear function given by:

x 0 1 2 3 4 5 6 7 8 ψ(x) +1 +2 +3 +4 0 -4 -3 -2 -1
which is unknown to the attacker, and N is a centered Gaussian noise with unknown standard deviation σ. The non-linearity of ψ is motivated by [START_REF] Moradi | A Comparative Study of Mutual Information Analysis under a Gaussian Assumption[END_REF], where it is discussed that a linear model favors CPA over MIA.

The leakage is continuous due to the Gaussian noise. In order to discretize the leakage to obtain discrete probabilities, we used the binning method. We conducted MIA with several different binning sizes:

B = {[(i -1) × ∆x, i × ∆x[, i ∈ Z}
for ∆x = {1, 3, 5, 7, 9}. (6.30) In this chapter, we do not try to establish any specific result about binning, but content ourselves to present empirical results obtained with different bin sizes.

WHEN MIA IS A MAXIMUM LIKELIHOOD AND BETTER THAN CPA

We have carried out LRA for the standard basis in dimension d = 9 and higher dimensions One reason why MIA outperforms CPA and LRA in this scenario is that the function ψ was chosen to have a null covariance. Moreover, one can observe that the most efficient binning size depends on the noise variance and thus on the scattering of the leakage. As σ grows larger values of ∆ should be chosen. This is contrary to the suggestions made in [START_REF] Gierlichs | Mutual information analysis[END_REF], which proposes to estimate the probability distributions as good as possible and thus to consider as many bins as there are distinct values in the traces. In our experiments, when noise is absent (σ = 0) the optimal binning size is ∆ = 1 which is equivalent to the step size of Y , while for σ = 2 the optimal binning is ∆ = 5 (see Fig. 6.5(c)). It can be seen that using 40 traces the success rate of MIA with ∆ = 5 reaches 90%, whereas 109 6. WHEN MIA IS A MAXIMUM LIKELIHOOD AND BETTER THAN CPA using ∆ = 1 it is only about 30%. To understand this phenomenon, Fig. 6.6 displays the estimated P(x|y) in a 3D histogram for the correct key and one false key hypothesis, such that MIA is able to reveal the correct key using ∆ = 5 but fails for ∆ = 1. Clearly, the distinguishability between the correct and false key is much higher in case of ∆ = 5 than for

∆ = 1.
More precisely, as the leakage is dispersed by the noise the population of bins of the false key becomes similar to the the ones of the correct key when considering smaller binning size (compare Fig. 6.6a and 6.6b). In contrast, the difference is more visible when the leakage is quantified into larger bins (compare Fig. 6.6c and 6.6d). Therefore, even if the estimation of I( x, y) using P(x|y) for larger ∆ is more coarse and thus looses some information, the distinguishing ability to reveal the correct key is enhanced.

Fast Computations

In this section, we explain how we compute CPA and MIA in a faster way. We first show an algorithm for CPA, then we move to MIA.

Fast computation of CPA

We recall here the definition of empirical CPA:

ρ(X, Y (k)) = 1 m m i=1 x i y i (k) -1 m m i=1 x i 1 m m i=1 y i (k) 1 m m i=1 x 2 i -1 m m i=1 x i 2 1 m m i=1 y 2 i (k) -1 m m i=1 y i (k) 2 = m m i=1 x i y i (k) -( m i=1 x i ) ( m i=1 y i (k)) m m i=1 x 2 i -( m i=1 x i ) 2 m m i=1 y 2 i (k) -( m i=1 y i (k)) 2 , (6.31)
where

y i (k) = ϕ(f (k, t i )).
For the fast computation the following accumulators are required:

• sx[t] = i/ti=t x i , the sum of leakages for a common t;

• sx2[t] = i/ti=t x 2 i , the sum of leakage squares for a common t;

• qt[t] = i/ti=t 1, the number of t which occurred.

We detail the various terms in the two next paragraphs. First, we simply have:

m i=1 x i = t sx[t],
which is key independent. Second:

m i=1 y i = t i/ti=t y i = t i/ti=t ϕ(f (k, t i )) = t ϕ(f (k, t i ))qt[t],
which, quite surprisingly, is key independent.

Scalar product

The scalar product can be written the following way:

m i=1
x i y i = y i/yi=y

x i y i = y y i/yi=y x i = y y i/ϕ(f (k,ti))=y x i = y y sx [y],
where sx [y] = t/ϕ(f (k,t))=y sx[t]. This optimization is certainly useful for long traces, because it minimizes the number of multiplications (precisely, only 2 m multiplications are done). But, we need 2 m temporary accumulators to save the sx [y].

However, in monosample traces, we can also use this more simple computation:

m i=1 x i y i = t i/ti=t x i ϕ(f (k, t i )) = t i/ti=t ϕ(f (k, t i ))x i = t ϕ(f (k, t i )) i/ti=t x i = t ϕ(f (k, t i ))sx[t].

Fast computation of MIA

We setup a structure for the PMF, namely an array of hash tables, denoted as PMF[t][x], where t and x live in the sets F n 2 and Im(ϕ • f ) + supp(N ). So, let us say we have accumulated q leakage pairs (t, x).

At this stage, we have the joint probability given by

P(t, x) = 1 q PMF[t][x].
Now, when using MIA as a distinguisher, we need to compute PMF[y][x], where y ∈ F n 2 (and we expect the (t, k) → y = ϕ(f (k, t)) function to be non-injective [START_REF] Whitnall | The Myth of Generic DPA . . . and the Magic of Learning[END_REF], which is the case in the previous sections). The value PMF[y][x] implicitly depends upon a key guess k, as:

PMF[y][x] = PMF[y = ϕ(f (k, t))][x]. Now, instead of computing P(x, y) through PMF[y][x]
explicitly for each key guess, we are able to reformulate

P(y, x) = t P(t, y, x) = t/ϕ(f (k,t))=y P(t, x) = 1 q t/ϕ(f (k,t))=y PMF[t][x].
Thus, we can reuse the tabulated PMF[t][x] for each key guess, which requires thus much less computations as a straightforward implementation.

Recall the expression of the estimated mutual information:

I( x, y) =
x,y P(x, y) log 2 P(x, y)

P(x) P(y) .

The value for P(x) is identical for all key hypotheses and thus can be factored out. Indeed, this quantity is a scaling constant which could be omitted. But for the sake of completeness, we have

P(x) = t P(t, x) = 1 q t PMF[t][x].
Lastly, we need to evaluate P(y). This is simply done as:

P(y) = x P(x, y),
Algorithm 2 illustrates the fast computation process for MIA while Algorithm 3 computes the success rate of MIA. It calls the function MIA-Distinguisher as a subroutine. This last function corresponds to the of the computation of fast MIA (Alg. 2). However, it is optimized this way:

Fast Computations

Algorithm 2: Fast computation algorithm for MIA input : x a set of q traces which take discrete values, t a corresponding set of q plaintexts/ciphertexts output : ( I( x, y(k))) k∈K // From x and t, build a hash table PMF[t][x] (i.e., an histogram)

1 for i ∈ {1, . . . , q} do 2 PMF[ t i ][ x i ] += 1 3 end 4 for x ∈ X do 5 P(x) = 0
// P(x) holds m P(x), cf. Eqn. (6.6)

6 for t ∈ F n 2 do 7 P(x) += PMF[t][x] 8 end 9 end
for k ∈ K do // Key enumeration ∀x ∈ X, y ∈ Y, P(x, y) = 0 // P(x, y) holds m P(x, y), cf. Eqn. (6.8) • x a set of q traces which take discrete values,

for t ∈ F n 2 do for x ∈ X do P(x, ϕ(f (k, t))) += PMF[t][x] // y = ϕ(f (k, t)),
• t a corresponding set of q plaintexts/ciphertexts,

• k * ∈ K, the correct key,

• q step , typically of the order of q/100 (number of times the success rate is computed),

• M , the number of experiments output : SR k * , the empirical rate of MIA (computed as per Eqn. (6.10))

SR k * = {0, . . . , 0} // Initialization of m/m step values to zero foreach experiment ∈ {1, . . . , M } do PMF[t][x] = 0, ∀t ∈ F n 2 , x ∈ X
foreach step ∈ {1, . . . , q/ q step } do for i ∈ {1 + (step -1) × q step , . . . , step × q step } do • The values of P(x) and q do not impact the result, hence they are not computed. This means that lines 4-8 of Alg. 2 are not part of Alg. MIA-Distinguisher, and that in the accumulation of I( x, y(k)) at line 15 of Function MIA-Distinguisher, the terms P(x) and q (present at line 25 of Alg. 2), are simply dropped.

PMF[t i ][x i ]
• In the line 17 of MIA-Distinguisher, we subtract the term which corresponds to the denominator P(y) of line 25 of Alg. 2. Notice that all the parameters of the logarithms are now integers. We can thus tabulate the logarithms in a table log[i], for i = 1, . . . , q.

Incidentally, the basis of the logarithm can be arbitrarily chosen. If q is really large, say larger than 10 millions, then log[i] can be precomputed from all i < 10 6 , and evaluated otherwise, since anyhow the call of log for large values is restricted to the case of P(y)

which is expected to be way larger than any P(x, y).

Standard computation algorithm for MIA

The standard computation for MIA unfolds as in Alg. 4. This algorithm outputs exactly the same as Alg. 2 but is slower for two reasons:

1. All the q samples are scanned for each key hypothesis;

2. Probability mass functions are normalized. Now, divisions are costly, and also they require a conversion from integer to floating point numbers;

Conclusion

We derived MIA anew as the distinguisher which maximizes the success rate when the exact probabilities are replaced by online estimations. This suggests that MIA is an interesting alternative when the attacker is not able to exactly determine the link between the measured leakage and the leakage model. This situation can either result from an unknown deterministic part or from an unknown noise distribution. We have proved that, if the number of traces is greater than the number of possible values of x and y, the MIA is faster in terms of logarithm computations.

We have presented two practical case-studies in which MIA can indeed be more efficient than CPA or LRA. The first scenario is for non-Gaussian noise but known deterministic leakage model. The second scenario is for Gaussian noise with unknown deterministic leakage model,

Conclusion

Algorithm 4: Standard computation algorithm for MIA input : x a set of m traces which take discrete values, t a corresponding set of m plaintexts/ciphertexts output : ( I( x, y(k))) k∈K

1 I( x, y(k)) = 0, ∀x ∈ X, k ∈ K 2 for k ∈ K do //
3 for i ∈ {1, . . . , m} do 4 PMF[ϕ(f (k, t i ))][x i ] += 1 // y = ϕ(f (k, t)), cf. Eqn. ( 6

WHEN MIA IS A MAXIMUM LIKELIHOOD AND BETTER THAN CPA

where one leverages a challenging leakage function which results in failure for CPA, and in harsh regression using LRA. Incidentally, this example is in line with the work carried out by Whitnall and Oswald [START_REF] Whitnall | A Comprehensive Evaluation of Mutual Information Analysis Using a Fair Evaluation Framework[END_REF] where a notion of relative margin is used to compare attacks. Our findings go in the same direction using the success rate as a figure of merit to compare attacks.

Finally, we extended the computation trick given for CPA to MIA avoiding the histogram estimation of conditional probabilities for each sub key individually, improving the speed of the computation.

We note that all our results are ϕ-dependent. It seems obvious that the closer we are to the actual leakage, the better the success rate will be. An open question is to find an analytic way to determine the function model that will provide the highest success rate.

Last, we note that our analysis is monovariate: we consider a leakage which consists in only one value. A future work would be to extend our results to mutivariate attacks.

Another topic of research is to carry out practical examples where MIA beats CPA. An viable option would be the exploitation of some specific timing attacks where the behaviour of the processor changes at every start-up.

Introduction

The field of cryptography is currently very sensitive as it deals with data protection and safety.

Thus, in order to assess the security of cryptographic devices, it is crucial to know and test their weaknesses. For example, the Advanced Encryption Standard (AES) [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF] is renowned as trustworthy from a mathematical point of view-there is currently no realistic way to cryptanalyze the AES-128. However, it is possible to break the 128-bit secret key byte by byte using side-channel analysis (SCA). SCA exploits the physical fact that the secret key leaks some information out of the device boundary through various "side-channels" such as power consumption or timing-number of clock cycles to perform a given operation. These leakages, correctly analyzed by SCA, yield the secret key of a device.

A good side-channel attack needs a good leakage model. Timing, for example, can be modeled easily when the implementation is unbalanced: Several successful attacks [13, 14, Even when the code is balanced-a recommended secure coding practice-some residual unbalances in timing can result from the hardware which executes the code. Indeed, processors implement speed optimization mechanisms such as memory caching and out-of-order execution.

As a consequence, it is not possible to predict with certainty how timing leaks information. The attacker is then led to make predictions about the way the device leaks.

In this part, we consider side-channel attacks that are performed in two phases:

1. a profiling phase where the attacker accumulates leakage from a device with a known secret key;

2. an attacking phase where the attacker accumulates leakage from the device with an unknown secret key.

This type of attack is known as a template attack [START_REF] Chari | Template Attacks[END_REF]. It has been shown [START_REF] Chari | Template Attacks[END_REF] to be very efficient under three conditions: (a) leakage samples are independent and identically distributed (i.i.d.);

(b) the noise is additive white Gaussian; and (c) the secret key leaks byte by byte, which enables a divide-and-conquer approach. For some side-channels, such as power or electromagnetic radiations, condition (b) is met in practice. However, for timing attacks, the noise cannot be Gaussian as timing is discrete. Moreover, the noise source is non-additive in this case, since it arises from complex replacement policies in caches and processor-specific on-the-fly instructions reordering.

The first proposed profiled timing attack is the seminal timing attack of Kocher [START_REF] Paul | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF]. The same methodology can be used on AES, as noted by Bernstein in 2005 [START_REF] Daniel | Cache-timing attacks on AES[END_REF]. Further works used the same method [START_REF] Bhattacharya | Hardware prefetchers leak: A revisit of SVF for cache-timing attacks[END_REF][START_REF] Rebeiro | Boosting Profiled Cache Timing Attacks With A Priori Analysis[END_REF][START_REF] Weiß | A cache timing attack on AES in virtualization environments[END_REF]. To our best knowledge, all these works consist in profiling moments, such as the average timing under a given plaintext and key. However, it is known [START_REF] Chari | Template Attacks[END_REF] that the best attacks should use maximum likelihood1

In this part, as illustrated in Tab. 6.1, we focus on a profiling where the distribution is characterized and used as such, and is not reduced to its moments. The attacker computes distributions using histogram methods. These distributions are then used to recover the correct secret key. The discrete nature of timing leakage leads to an empty bin issue which appears when a data value in the attacking phase has never been seen during the profiling phase. Based on profiling only, this data should have a zero probability, which can be devastating for the attack.

One known workaround is to use kernel distribution methods [START_REF] Parzen | On estimation of a probability density function and mode[END_REF] to estimate probabilities since the smoothing can be such that no empty bins remain. This method can however be seen as a postprocessing in existing information. This alters therefore the data. In addition, this method has very large computational complexity and its performance highly depends on ad-hoc choices of several parameters such as kernel type and bandwidth. Moreover the estimation via the kernel method depends on other parameters such as the choice of the kernel and the size of the

Mathematical Derivations

Here all sample components of one vector are i.i.d. and belong to some discrete set. Typically, X is a finite subset of N and T is equal to {0, 1} n .

In the profiling stage, the secret key k * is known and variable. In the attacking phase, the secret key k * is unknown but fixed. Further, we assume that x i depends only on t i and k * for all i = 1, 2, . . . , q, in the form:

x i = ψ(t i ⊕ k * ) (i = 1, 2, . . . , q) (7.1)
where ⊕ is the XOR (exclusive or) operator and ψ is an unknown function which may contain noise, masking and other hidden parameters1 .

Furthermore, in this part, we use of the notation n x,t to denote the number of occurrences of (x, t). Thus we can write

n x,t = q i=1 1 xi=x, ti=t n x = q i=1 1 xi=x , n x,t = q i=1 1 xi=x, ti=t n x = q i=1 1 xi=x .
where 1 A = 1 if A is true, = 0 otherwise. Definition 7.1 (Probabilities). We define three2 different types of probabilities P, P and P. P is the actual (real) underlying probability distribution, but it is generally not available and has to be estimated by either P or P.

• P is computed using the profiling data:

P(x, t) = 1 q q i=1 1 xi=x, ti=t = n x,t q , (7.2)
P(x) = 1 q q i=1 1 xi=x = n x q . ( 7.3)
• P is computed using the attacking data:

P(x, t) = 1 q q i=1 1 xi=x, ti=t = n x,t q , (7.4)
P(x) = 1 q q i=1 1 xi=x = n x q .
(7.5)

METHODS TO SOLVE THE EMPTY-BIN ISSUE

In practice, as the secret key leaks through the function via a XOR (Equation (7.1)), we shall often consider P(x, t ⊕ k).

For a fair comparison between distinguishers, Standaert et al. [START_REF] Standaert | A Unified Framework for the Analysis of Side-Channel Key Recovery Attacks[END_REF] have put forward the success rate as a measure of efficiency of a given distinguisher.

Definition 7.2 (Success Rate). The success rate SR is probability, averaged over all possible keys, of obtaining the correct key.

SR = 1 2 n 2 n -1 k * =0 P k * ( k = k * ), (7.6)
where k is the key guess obtained by the distinguisher during the attack.

It has been proven [39, Theorem 1, equation ( 3)] that for equiprobable keys the optimal distinguisher maximizes likelihood:

D Optimal ( x, t) = arg max k∈K P( x| t ⊕ k). (7.7)
In real life, however, the attacker does not know the leakage model perfectly and thus P( x| t ⊕ k)

is not available. In order to get an estimation of P, we use the profiling data to build P defined in Equation (7.2). This is the classical template attack. The distinguisher becomes D Template ( x, t) = arg max k∈K P( x| t ⊕ k). (7.8) This distinguisher is no longer optimal as it does not use the real distribution P. However, if profiling tends to exhaustivity, P and P will be very close since by the law of large numbers, ∀x, t P(x, t) -→ q→∞ P(x, t).

Moreover, we notice that non-optimality is not the only issue with template attacks in the context of discrete leakage. The attacker also faces the problem that the attack is ill-formed.

In practice, it is convenient to use the logarithm arg max k∈K log P( x| t ⊕ k). In fact, since the samples are i.i.d., we have

P( x| t ⊕ k) = q i=1 P( x i | t i ⊕ k) and P( x| t ⊕ k) = q i=1 P( x i | t i ⊕ k).
Therefore, the attacker computes

D Template ( x, t) = arg max k∈K q i=1 log P( x i | t i ⊕ k) (7.9)
where the logarithm is used to transform products into sums for a more reliable computation.

However, we would like to avoid empty bins for which P( x i | t i ⊕ k) = 0; otherwise, Equation (7.9)

would not be well defined.

About Empty Bins

The empty bin issue appears when there exists i ∈ {1, . . . , q} and k ∈ K such that P( x i | t i ⊕k) > 0 and P( x i | t i ⊕ k) = 0. This may even happen for the correct key hypothesis, leading to a wrong key guess during the attack. 2 show how empty bins can look like after a profiling phase 1 . We notice that some parts of the histograms are left blank, some of them indicated by arrows noticed as "holes" in the figures. These timing values x are possible "empty bins". When such a hole is called during the attack, meaning that the attacker gets a trace with corresponding with a hole, we call this an empty bin. Notice that no additional "binning" is needed as in the case of continuous distributions. The figures also show that the noise is not Gaussian as can be observed from the shape of the distribution.

The shortcoming of empty bins can be seen when evaluating the likelihood. The attacker encounters a zero probability, which makes the product vanish for the probability of a given key guess, even if many traces are used. As we wrote earlier, the empty bin may appear even for the correct key guess in template attacks, leading to a null success rate if not taken into account and not well treated. As an example, the number of empty bins for the practical example presented Section 8.1 for the correct key guess is around 500 for a poor learning phase and around 50 for a good learning phase. This multiplication by zero is not inherent to the attack; it is rather a profiling artifact. In fact, with more profiling traces, the empty bin would likely be populated.

Thus, the empty bin issue is a mere side-effect of insufficient profiling, which results in an attack failure if it is encountered in the computation of the likelihood of the correct key.

Distinguishers which Tolerate Empty Bins

Building Distributions or Models

Before presenting the novel distinguishers in Subsection 7.2.2, we need to define yet another other type of distribution known as a Dirichlet a posteriori in a Bayesian approach.

The Dirichlet A Posteriori

In order to avoid zero probabilities, we use a method based on Dirichlet Prior calculations [START_REF] Frigyik | Introduction to the Dirichlet Distribution and Related Processes[END_REF]Section 1]. This method leads to a new distribution denoted by s P α , where α > 0 is a user-defined 7.2 Distinguishers which Tolerate Empty Bins parameter whose value (typically = 1) will be discussed next.

Let X be the set of possible values for x and T be the set of possible values for t. For any x, we set p x,t = P(x, t) their joint probability and p = (p x,t ) x,t . Prior to obtaining any trace, p x,t

is completely unknown and we consider a Bayesian approach to estimate p x,t .

1. We consider the following a priori : without further information, we suppose that for all

x, t,

s P α (x, t) = α x,t x ,t α x ,t
, where α x,t > 0 is an a priori parameter. To simplify, we may choose α x,t = α constant for all x, t. Let us suppose that p follows a Dirichlet (prior) distribution, whose probability density function is

f (p) = Γ( x,t α x,t ) x,t Γ(α x,t ) x,t p αx,t-1 x,t , (7.10)
where Γ is the Gamma function defined for x > 0 as

Γ(x) = +∞ 0 t x-1 e -t dt. (7.11)
The Dirichlet distribution can also be written as

f (p) =N α x,t p αx,t-1 x,t , (7.12)
where N α = Γ( x,t αx,t)

x,t Γ(αx,t) is a normalization factor. Notice that the prior distribution is uniform when α x,t = α = 1 for all x, t.

2. Then suppose we know x, x, t and t. We can now compute the a posteriori probability P(x, t| x, x, t, t) = f (p, x, t| x, x, t, t) dp. By Bayes' rule, f (p, x, t| x, x, t, t) = P(x, t|p, x, x, t, t)f (p| x, x, t, t).

As components x i and t i are i.i.d., we can write f (p, x, t| x, x, t, t) = P(x, t|p) • f (p| x, x, t, t, t) = p x,t • f (p| x, x, t, t) which is known as the Dirichlet a posteriori.

3. The integral can be easily expressed in terms of the Gamma function:

P(x, t| x, x, t, t) = Γ( x ,t α x,t + n x ,t + n x ,t )

x ,t Γ(α x,t + n x ,t + n x ,t ) × x ,t Γ(α x,t + n x ,t + n x ,t + δ x,t ) Γ( x ,t α x,t + n x ,t + n x ,t + δ x,t ) which simplifies to P(x, t| x, x, t, t) = n x,t + n x,t + α x,t q + q + x ,t α x ,t .

This new distribution will now be noted: x n x,t + n x,t + α x,t q + q + x ,t α x ,t = n t + n t + t α x,t q + q + x ,t α x ,t = n t + n t + α t q + q + x α x ,

s P α (x, t) = P(x, t| x, x, t, t) = n x,t + n x,t + α x,t q + q + x ,t α x ,t . ( 7

METHODS TO SOLVE THE EMPTY-BIN ISSUE Hard Drop Distinguisher

The first naive method consists in removing all the traces which, for any key guess, have a zero probability.

Definition 7.3 (Hard Drop Distinguisher). The hard drop distinguisher is defined as followed:

D Hard ( x, t) = arg max k∈K i∈I log P( x i | t i ⊕ k), (7.17)
where set I is defined as

I = i ∈ {1, . . . , q} | ∀k ∈ K, P( x i | t i ⊕ k) > 0 . (7.18)
Recall that P, defined in Equation (7.2), is an empirical histogram estimated on profiled data x (along with corresponding texts t).

The Hard Drop Distinguisher, as the name indicates, drops some data. In very noisy cases, it may even drop most of the data.

Soft Drop Distinguisher

The second possibility is to drop values only for some keys. However, it has to be done carefully because dropping a value in a product implicitly implies a probability value of one. For this reason, instead of removing the trace, we replace the zero probability by a constant which is smaller than the smallest probability.

where γ ∈ R * + is a constant such that ∀i, k ∈ {1, . . . , q} × K, γ ≤ P( x i | t i ⊕ k).
This means that we penalize data with zero probability. The smaller γ, the harder the penalty.

The choice of parameter γ is thus important in order to get a fair result for the distinguisher.

If we choose γ ≥ 1 q , the penalty may be greater than the smallest strictly positive probability. This case would mean that the penalty is less important than some licit probabilities. On the other hand, choosing γ smaller than 1 q means a very strong penalty. In this case, the limit when γ → 0 is a distinguisher for which only the number of empty bins is really matters. This leads to the Empty Bin Distinguisher presented next in Definition 7.8.

Distinguishers which Tolerate Empty Bins

The Dirichlet Prior Distinguisher

The Dirichlet Prior Distinguisher uses the Dirichlet a posteriori distributions presented in Subsection 7.2.1.

Definition 7.5 (The Dirichlet Distinguisher). We define the Dirichlet Distinguisher as:

D Dirichlet ( x, t) = arg max k∈K s P α ( x| t ⊕ k).
(7.20)

Remark 7.1. As can be seen in the construction of the Dirichlet a posteriori, the Dirichlet distinguisher is α-dependent. It is important to evaluate the influence of α over the success rate. In practice, α = 1 seems a natural choice since the corresponding prior is uniform, which minimizes the impact of the a priori. In contrast, another value of α like 1/2 can be interpreted as an a priori bin count. We may also consider scenarios where α ≈ 0 to have the least possible impact to the modified values of the histogram.

Offline-Online Profiling

The Dirichlet Prior Distinguisher is set by α. As we discussed in Remark 7.1, we can choose any α so long as it is strictly positive (the Dirichlet distribution would not be defined if α = 0).

However, it is interesting to study its asymptotical behavior as α vanishes:

lim α→0 s P α (x|t) = n x,t + n x,t n t + n t .
This distribution can be denoted as s P 0 (x|t) and resembles a profiling stage that would start offline and continue online.

Definition 7.6 (Offline-Online Profiling). The Offline-Online Profiled (OOP) distinguisher is defined as:

D OOP ( x, t) = arg max k∈K s P 0 ( x| t ⊕ k) (7.21)
The OOP distinguisher seems easier than the Dirichlet prior distinguisher since α is no longer in use. Of course, it also solves the empty bin issue since for all (x, t) ∈ X × T, one has s P 0 (x, t) > 0.

Learned MIA Distinguisher

The Learned MIA Distinguisher is constructed with the profiled model function ψ presented in Eqn. (7.16)

D MIALearned = arg max k∈K I x; ψ( t ⊕ k) , (7.22)
where I is the empirical mutual information [START_REF] Gierlichs | Mutual information analysis[END_REF].

Empty Bin Distinguisher

The empty bin Distinguisher is yet another intuitive solution based on the idea that instead of avoiding null probabilities, we may take only these into account. It is the key guess with the least number of null probabilities that "should" be the correct key.

Definition 7.8. The Empty Bin Distinguisher is defined as:

D EmptyBin ( x, t) = arg min k∈K q i=1 1 P( xi| ti⊕k)=0 . (7.23)
The Empty Bin Distinguisher assumed that missing data contain more information than actual (measured) data. More precisely, a drop should normally not happen unless the guessed key is wrong; hence, the key guess with the least drops should be the correct key. Obviously, this distinguisher is not effective anymore if no drop occurs for at least two key guesses.

Further Remarks All these distinguishers use a profiling phase. Before comparing them, we would like to make a priori discussion about their respective efficiency. As the Hard Drop Distinguisher does not take into account some data, we may suppose that it will be the one with the least success rate for a given number of traces. The OOP Distinguisher takes into account two types of data: profiling and attacking data. Therefore, it should be more efficient than other distinguishers. Lastly, we build the Learned MIA Distinguisher in order to prevent model errors, such as inaccurate profiling. In that case, we suppose that Learned MIA should work better with few data during the profiling stage.

Simulated Results

In this section, we present the results obtained on a simulated model. With these results, we can give a comparison of the proposed distinguishers.

Results on Real Devices

We have chosen to carry out a timing attack on an STM32F4 discovery board [START_REF]F4DISCOVERY Discovery kit with STM32F407VG MCU[END_REF]. One interesting aspect is that we do not make any assumption on the model. In real life, the leakage model happens to be much more complex than the one employed in simulations (e.g., Equation (7.24)). As will be seen, in practice empty bins appear even for the correct key guess and for a "good" profiling phase. This observation differs from the ideal case of our simulations carried out in the preceding Section 7.3.

The ARM processor

We used a STM32F4 discovery board by STMicroelectronics Coupled Memory (CCM). The CCM has a zero flash wait state and is often used to store critical data such as data from the operating system. Since the RAM is divided into three regions, the users are unable to make use of the 192 KB RAM as a continuous memory block. • This is a weakness for the security of the processor as two different plaintext lead to two different time clock to compute AES.

• Following Figure 8.1, it seems the enabling or not Instruction Cache, does not modify the behaviour of the leakages.

• Data presented Figure 8.1 are obtained using a fixed key and varying one byte of the plaintext.

Figure 8.1 instructs us that caches shall be disabled to reduce the leakage in timing. However, we emphasize that such decision has a strongly negative impact on the AES performance: with DC off, the overall AES execution time is about 27% longer.

Therefore, in a realistic context, we shall assume that both DC and IC are enabled, which we will do in the sequel (see next Sec. 8.2 for some indications how well attacks perform when caches are disabled).

Characterizing the leakages for Data Cache On

As seen earlier, when the Data Cache in enabled, the AES computation is not time constant.

This can be due to the T-boxes called during the computation. Indeed, calling a value in a table also stores this in the Data Cache. If this value is called within the eight next calls, the load will be faster. In Appendix C.1, we have copied the OpenSSL source code for the AES encryption with a 128 bits key. In this code, we notice that there are 160 calls to the T-boxes.

In order find a model of the leakage, we inferred the cache policy of STM32F4 ARM microcontrollers based on a thorough study of their timing response to some adaptively constructed In case of a hit, the time to access such register is 5 or 6 clock cycles faster than a miss. To show this behaviour, we have done a very simple experiment:

• We generate a table of length 256;

• We generate 16 random values between 0x00 and 0xff;

• We call 16 elements of the table corresponding to the 16 values generated previously;

• We measure the time to call these 16 elements of the table.

We have plotted in Figure 8.2 the histogram of the clock cycles. the negative number in the x axis is due to the fact that we have set the 0 at the maximum value of the clock cycles, which is the obtained value for not hit at all 1 . We notice that when a hit occurs, the time is faster by 5 or 6 clock cycles. For two hits, there are three possible values: 10, 11 or 12 clock cycles. Once more, the 0 in the x axis is set to the maximum.

Very interestingly, we can observe in this figure high density levels corresponding to the hits:

1. One hit at -5 and -6;

2. Two hits at -10 and -11;

3. Three hits at -15 and -16.

Below -16 clock cycles, the hits are lost into the noise.

The comparaison of these two figures show that the FIFO model for table hits is correct, but does not explain all the time leakage due to the cache policy of the processor.

Attack Results

As already noticed above, the leakage model is mostly unknown. We only suppose that the text byte is mixed with the key through a XOR operation. As a consequence, the optimal 8. OBTAIN A LEAKAGE MODEL WITH TIMING ATTACKS • The Learned MIA distinguisher is only slightly better than in Figure 8.4. To reach 80% success rate, 1 100 traces are needed as compared to 1 250 traces previously.

• The Soft Drop and Offline-Online distinguishers are the best distinguishers in this scenario, with a small advantage for the Soft Drop distinguisher.

• The Hard Drop distinguisher remains unsuccessful.

Results on Real Devices

order to decide for the reason of Empty Bins, we have drawn the number of empty bins for a

given key according to the number of traces in the profiling stage. We considered q = 1 280 000, and define the number of empty bins as:

x ∈ { q min q=1 x q , . . . , q max q=1 x q }, such that ∃q, x q = x .

We can see that the number of empty bins decreases, but never reaches 0. At the beginning, the high number of empty bins is due to both poor profiling and structural empty bins. With a good profiling, we only keep the structural empty bins.

Study on the Mean-Square Error

An interesting point noticed in Figures 8.4, 8.5, and 8.6 is that the Learned MIA distinguisher is working better than the Soft Drop Distinguisher for a poor learning phase (i.e., q = 25 600).

However, with a better learning phase (i.e., q = 256 000 and q = 2 560 000), the Soft Drop Distinguisher has a much better success rate. In order to understand why the Learned MIA We notice the following aspects:

Results on Real Devices

• For the Soft Drop Distinguisher, the bias is almost equal to zero. In fact, the MSE is the variance.

• For the Learned MIA Distinguisher, it is mainly the opposite: the biggest part of the MSE is the bias.

To conclude with the MSE, the Soft Drop Distinguisher improves because the estimator has a much smaller variance with a better learning phase. Meanwhile, the Learned MIA Distinguisher does not improve because it is a biased estimator and a better learning phase does not reduce this bias.

Effect of Measurement Noise

However, in practice, timing measurements contain a noisy part. Let us give three examples:

1. Measure of a difference of timing between request and response from the AES (over a network of unknown latency);

2. Use of a side-channel signal (such as the power or the electromagnetic field) to observe the AES computation; the beginning and the end of an AES are easy to identify, as they consist in sixteen consecutive operations (namely sixteen XOR making up the AddRoundKey operations). As these patterns have a remarkable signature, they can be extracted with great accuracy thanks to a mere cross-correlation. Still, the AES itself might not be executed in constant time, hence some alignments issues;

3. Use of a cache attack, which would disclose that the program flows entered and exited the AES function. However, the timing for access to cache is non deterministic.

Let us denote the variance of the added noise as σ 2 . Now, it is known that any additive distinguishers (which is the case of our distinguishers), the number of traces to recover the secret for a given success rate is inversely proportional to the inverse of the signal-to-noise ratio (see e.g., [START_REF] Sylvain Guilley | A Key to Success -Success Exponents for Side-Channel Distinguishers[END_REF]Corollary 2]).

As a direct consequence, we can predict the complexity of the attacks when IC and DC are disabled. It can be seen in Figure 8.1 that the timing variation is about divided by three (from ≈ 20 to ≈ 8) when the DC is disabled. Therefore, the number of required traces to recover the key is about multiplied by three.

OBTAIN A LEAKAGE MODEL WITH TIMING ATTACKS

In addition, we can approximate the required number of traces to extract the key in presence of external noise of standard deviation σ. In our case-study of OpenSSL AES on ARM, the algorithmic noise has standard deviation about 20 clock cycles (see Figure 7.1 and 7.2).

So, if the external noise has standard deviation σ < 20, the impact is small. But when σ/20 > 1, the influence of the external noise becomes preponderant. As the algorithmic noise and the external noise are independent, the number of traces required to extract the key will actually grow linearly with σ as soon as σ/20 1.

Comparison with Existing Methods in the Presence of Noise

In this subsection, we aim at comparing our distribution-based method with the existing methods (moment-based method mentioned in Tab. 6.1). In particular, we focus on the representative Bernstein correlation [START_REF] Daniel | Cache-timing attacks on AES[END_REF] with a learned model [the timing expectation for each value of the target AES byte], that we refer to as "CPA". This "CPA" between timing measurements and the learned average of timing per byte of the key does not suffer from the empty bin issue. We start by a comparison with little external noise. In this case, we have plotted in Figure 8.13 the success rate for both the soft drop distinguisher and the CPA. The x axis represents the number of traces for the profiling phase while the y axis is the number of traces needed during the attack to reach 80% of success rate. We notice that the CPA performs better than the soft drop method, for any profiling (even when learning with several million of traces). This can be due to bias between the profiled distribution and the attack distribution.

However, in a practical case, we encounter noisy timing leakages. In order to compare our methods with the existing methods (such as CPA) in the presence of external noise, we plotted Figure 8.14. In this figure, we took a good profiling phase ( q = 3 × 10 6 ), i.e., profiling is performed on sufficiently enough traces. This figure is obtained for a noisy timing, that is the nominal time to compute AES (as in Subsec. 7.1.2), where the noise follows the following law: 0 added time with probability 50%, T added (T ∈ N, a number of clock periods), with probability 50%. (8.2) This models the interruption of the CPU from a peripheral when AES is baremetal, or a descheduling of the AES process during one time slot on systems with an operating system (OS). Indeed, such events have the consequence, when they occur, to add a long period of time (often as long or even longer than the duration of the AES) to the encryption time, so that the interruption can be served, or so that the OS re-schedules the AES process. We notice that, in such case, it is more interesting to compute one of our methods, rather than previous existing

Conclusion and Perspectives

We have derived several "information-theoretic" distinguishers as possible solutions to the empty bin issue. Some of them, like the Dirichlet Prior and the Offline-Online distinguishers, required the computation of novel distributions. We have shown in particular that the empty bins, previously believed to be an annoyance and dropped accordingly, can turn out to be valuable assets for the attacker as long as they are treated carefully. In all the part, real timing data are used, making the results very practical.

We have also compared the various distinguishers under two frameworks: a simulated test with synthetic leakage and real-world timing attacks. In both cases, we noticed that the outcome of the attacks depends on the quality of the profiling stage. A good profiling improves the results, where the best distinguisher seems to be the Soft Drop Distinguisher. A poor profiling makes the traditional distinguishers break down. More sophisticated solutions like Offline-Online Profiling and Learned MIA distinguishers are very useful in this case. A possible way to investigate more on this aspect is to use more powerfull statistical tools in order to extract the most precise model for the Learned MIA Distinguisher.

The interesting aspect on the studied timing attack is that one does not have to make

any assumption on the leakage model. In addition to this, the main advantage of the new distinguishers is that the empty bin issue is completely solved. We also introduced distinguishers which can jointly exploit offline and online side-channel measurements. As an interesting perspective, our approach could advantageously be analyzed using the "perceived information"

OBTAIN A LEAKAGE MODEL WITH TIMING ATTACKS

Another perspective would be to compare our information-theoretic attacks with attacks based on machine learning techniques. Surprisingly and contrary to results reported in other papers, our preliminary results show that SCA based on support vector machines [START_REF] Heuser | Intelligent Machine Homicide -Breaking Cryptographic Devices Using Support Vector Machines[END_REF] has poor performance, even when profiling with very few traces ( q is small), which may be due to the univariate nature of the leakage.

An interesting observation is that writing cryptographic code robust to timing attacks is challenging. While the OpenSSL code for AES has no obvious flaw (such as unbalanced branches which depend on sensitive data), the timing of AES is data-dependent, due to microarchitectural features of the studied ARM core. There seem to exist two classes of solutions against timing attacks: The first aims at randomizing the execution timing, as studied for instance in [START_REF] Daniel | Cache-timing attacks on AES[END_REF]. Such an implementation can still be attacked with high-order distinguishers, albeit with more traces than without any protection. The second would attempt to balance the timing, yet this requires some hardware support such as the CCM feature of the STM32F4 processors. Information between the sensitive variable and the measured traces. When the noise is Gaussian, the Mutual Information is a function of the SNR. However, the main difficulty is that the leakage is not independent. This means that the Mutual Information is more complicated than Shannon's formula. I have therefore investigated on the estimation of Mutual Information for this particularity of side-channel analysis. This is indeed a particularity since in the literature in communication theory, most of the channels are considered with independent random variables.

Part V Conclusion and Perpectives

According to me, this result will give a good bound to the efficiency of a model. Indeed, in side-channel analysis, the SNR is model dependant. With this knowledge of the SNR, we have an upper-bound on the success rate. This gives a first idea of the level of security of a chip without making simulations to calculate the success rate.

It is possible to extend this result to protected implementations but the formula of the mutual information is much more difficult to calculate. A possibility would therefore be to consider the approximation of Independence even if the bound is therefore looser.

On a more personal point-of-view, this thesis has been for me a very intense period. When I arrived at Télécom in 2015, I had never heard of cryptography. Side-channel analysis has therefore been for me a very good mean to enter this particular world. Side-channel analysis is a mixture between cryptography, electronics, mathematics and physics. This is therefore a very beautiful topic of research and I am confident that several talented researchers will invest time in this field.

Further Perspectives

Side Channel analysis has a very large spectrum of applications and studies. This topic is quite new since the first literature on this subject appeared in the 1990s.

The next challenges for the coming years will be focused on the Artificial Intelligence. Indeed, neural networks will be soon able to extract leakage models and furthermore, be able to recover secret keys. On the future of cryptography, post-quantum is a big topic of research. To prepare this quantum revolution, designers are already rethinking asymmetric algorithms (such as RSA)

to be secured against quantum cryptanalysis. These new algorithms will be of course subject to side-channel analysis and it will be interesting to study them on different architectures.

On the study of distinguishers, another interesting topic of research will be the success rate under a wrong leakage model. In communication theory, this is called mismatch decoding. I mentioned this issue in the appendix but I believe that there is a lot to study in order to predict the success rate of an attack under this supposition.

Part VI

Appendix.

A.1 Proof of Lemma 4.1

Let t ∈ T and τ be the considered permutation. We have H(X | T = t) = - A.2 Proof of (3.5)

We study the sign of the difference

∆ = -E Y log 2 E X [exp(f (X, Y ))] + log 2 E X [exp(E Y f (X, Y ))]; = -log 2 exp E Y log 2 E X [exp(f (X , Y ))] + log 2 E X [exp(E Y log 2 exp f (X, Y ))]; = log 2 E X exp(E Y log 2 exp f (X, Y )) exp E Y log 2 E X [exp(f (X , Y ))] ; = log 2 E X exp E Y [log 2 exp f (X, Y ) -log 2 E X [exp(f (X , Y ))]] ; = log 2 E X exp E Y log 2 exp f (X, Y ) E X [exp(f (X , Y ))]
.

Since the log function is concave: In Lemma 3.5, we have proven that:

∆ ≤ log 2 E X exp log 2 E Y exp f (X, Y ) E X [exp(f (X , Y ))] ; = log 2 E X E Y exp f (X, Y ) E X [exp(f (X , Y ))] ; = log 2 E Y E X exp f (X, Y ) E X exp
E Y log 2 E X [exp(f (X, Y ))] ≥ log 2 E X [exp(E Y f (X, Y ))]
or

E Y log 2 E X [exp(f (X, Y ))] ≥ log 2 E X [exp(E Y log exp f (X, Y ))].
Setting g(x, y) = exp(f (x, y)), we have:

E Y log 2 E X [g(X, Y )] ≥ log 2 E X [exp(E Y log g(X, Y ))].
Hence,

exp E Y log 2 E X [g(X, Y )] ≥ exp log 2 E X [exp(E Y log g(X, Y ))] ≥ E X [exp(E Y log g(X, Y ))]
A. This means that, one again, the Mutual Information between the traces and the key is relevant to calculate a bound on the success rate. However, estimating such Mutual Information is a open issue.

A.6 About Mismatched Decoding

The upper-bound obtained by Theorem 3.1 is always true for any distinguisher. Moreover, as we have based our calculations with the best possible case for the attacker. Indeed, the lower bound is obtained because we have supposed that the attacker knows the leakage model and therefore the distributions P.

However, in many cases, the attacker only knows an estimation of the leakage distribution (noted P) that may not be exactly equal to P. In this case, our bound is still correct since the knowledge of P is the best possible case for the attacker. In this filed, François-Xavier

Standaert proposed the notion of Perceived Information [START_REF] Durvaux | How to Certify the Leakage of a Chip?[END_REF] as a metric to measure the impact of the estimation distribution P on the mutual information. In this section, we first re-write the Shannon channel coding theorem to show that it is possible to recover the secret key if perceived information is strictly positive (cf. Subsection A.6.1). Then we discuss about an information theoretic paper written by Neri Merhav and Amos Lapidoth in 1994 that deals with mismatch decoding [START_REF] Merhav | On information rates for mismatched decoders[END_REF](cf. Subsection A.6.2).

A.6.1 The Channel Coding Theorem with Divergence

In Information Theory, the Channel Coding Theorem written and proved by C.E. Shannon in [START_REF] Elwood | A mathematical theory of communication[END_REF] shows that, it is possible to send a message with an arbitrary small amount of error through a channel, as long as the rate of the message (i.e. the number of sent bits) is lower than the mutual information of this channel.

In his demonstration, Shannon supposed that the channel was perfectly known, meaning that the probability P(y|x) was known. In our case, we only have P(y|x) at our disposal. This means that even if Shannon's theory is true, we do not how far we can go with our estimation.

Thus, we will re-write the proof of the channel-coding theorem with the consideration that the attacker makes an error of estimation. where the decoder only knows P(y|x) an estimation of P(y|x). We suppose furthermore that the decoder perfectly knows the distribution of X (i.e. P(x)).

A.6 About Mismatched Decoding 2. We have the following inequality: 1 =

x,y∈X q ×Y q P XY (x, y) ≥

x,y∈A ε This show the second part of the lemma.

3. We consider X and Y defined in the lemma. We have:

P ( X, Y) ∈ A ε P XY =
x,y∈A ε P XY P X (x) P Y (y)

≤ |A ε P XY
|2 -n(H(X)+D(P X || P X )-ε) 2 -n(H(Y )+D(P Y || P Y )-ε)

Putting this with the proof result of item 2, we obtain the inequality.

With all of these tools, we are now able to proof the Channel-Coding Theorem with divergence. This proof will be mainly inspired by the proof of the Coding-Channel Theorem written by Cover and Thomas in [START_REF] Cover | Elements of Information Theory[END_REF]. Our main contribution is to add the divergence into the proof and use typical sets including divergence to do so.

Proof of the Channel-Coding Theorem. To prove the Channel-Coding theorem, Shannon did not consider the probability of error of one particular code, but the average of the probability of error, taken over all the possible codebooks for a given message. Let us consider a rate R and the length q of the sent vector of the message. Shannon proved that the average probability of error over all the codebooks, is equal to the average probability of error over all the codebooks supposing that one particular index was sent. Let us consider a massage modeled by the random equiprobable variable M and the possible set of M is {1, . . . , 2 qR }. Y is therefore a function of M . Let us suppose that we send a 1 over the channel. Then, the average probability of error over all the codebooks knowing that a 1 is sent is noted P(E|M = 1). We consider the following decoding scheme: y(1) is sent over the noisy channel and x is received. The decoder tests for which i ∈ {1, . . . , 2 qR } the y(i) and x are jointly typical with probability P XY . An error occurs if y(1) and x are not jointly typical, or if there is another i = 1 such that y(i) and x are jointly typical. Let us note B i the event: y(i) and x are jointly typical. We notice that if index 1 is sent, then, for any i = 1, Y(i) and X will be independent as the code is chosen randomly. The average probability of error over all the codebooks is therefore:

P(E|M = i) = P [B c 1 ∪ B 2 ∪ . . . ∪ B 2 qR ]
≤ P(B c 1 ) + The first term vanishes since p is even and t odd. We apply a Taylor expansion:

I(X; Y (k)) = p[-εt - ε 2 t 2 2 - ε 3 t 3 3 + O(ε 4 )] -εpt[-εt - ε 2 t 2 2 - ε 3 t 3 3 + O(ε 4 )]. (B.9)
The odd terms of the expansion are null as t is odd and p even. We therefore obtain:

I(X; Y (k)) = p[- ε 2 t 2 2 + O(ε 4 )] -[-ε 2

B.3 Proof of Lemma 5.5

To prove the success rate of KSA, we first need an estimator for the cumulative density function.

We take as kernel a function Φ as simple as possible i.e. the Heaviside function Φ(x) = 0 if

x < 0 and Φ(x) = 1 if x ≥ 0.

With this function and for x ∈ R, we can estimate F (x|Y (k) = 1) -F (x) by the following estimator:

F (x|Y (k) = 1) -F (x) = i|Yi(k)=1 Φ(x -X i ) i|Yi(k)=1 1 -i Φ(x -X i ) q . (B.27)
We suppose that q is large enough to consider that i|Yi(k)=1 1 = q 2 (by the law of large numbers). Therefore we have:

F (x|Y (k) = 1) -F (x) = i|Yi(k)=1 Φ(x -X i ) q -2 i Φ(x -X i ) q .
(B.28)

We notice that i|Yi(k)=1 Φ(x -X i ) = 1 2 i (Y i (k) + 1)Φ(x -X i ). Therefore

F (x|Y (k) = 1) -F (x) = 1 q q i=1 Y i (k)Φ(x -X i ). (B.29)
This estimator is a sum of i.i.d. random variables. We can therefore apply the central limit Keywords: Cryptography, Side-Channel, Information Theory, Optimization

Abstract: In the field of the security of the embedded systems, it is necessary to know and understand the possible physical attacks that could break the security of cryptographic components. Since the current algorithms such as Advanced Encryption Standard (AES) are very resilient against differential and linear cryptanalysis, other methods are used to recover the secrets of these components. Indeed, the secret key used to encrypt data leaks during the computation of the algorithm, and it is possible to measure this leakage and exploit it. This technique to recover the secret key is called sidechannel analysis.

The main target of this Ph. D. manuscript is to increase and consolidate the knowledge on the side-channel threat. To do so, we apply some information theoretic results to side-channel analysis. The main objective is show how a sidechannel leaking model can be seen as a communication channel. We first show that the security of a chip is dependant to the signal-to-noise ratio (SNR) of the leakage. This result is very useful since it is a generic result independent from the attack. When a designer builds a chip, he might not be able to know in advance how his embedded system will be attacked, maybe several years later.

The tools that we provide in this manuscript will help designers to estimated the level of liability of their chips.

Université Paris-Saclay Espace Technologique / Immeuble Discovery Route de l'Orme aux Merisiers RD 128 / 91190 Saint-Aubin, France

xiv LIST OF FIGURES 8 . 6

 86 SR for q = 2 560 000 on real-world measurements . . . . . . . . . . . . . . . . . . 8.7 SR for q = 256 000 with γ = 1 q×10 10 . . . . . . . . . . . . . . . . . . . . . . . . . . 8.8 Empirical number of empty bins . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.9 Average MSE for the Learned MIA Distinguisher . . . . . . . . . . . . . . . . . . 8.10 Average MSE for the Soft Drop Distinguisher . . . . . . . . . . . . . . . . . . . . 8.11 Variance and bias of the Learned MIA Distinguisher . . . . . . . . . . . . . . . . 8.12 Variance and bias of the Soft Drop Distinguisher . . . . . . . . . . . . . . . . . . 8.13 Comparison between CPA and soft drop distinguisher at 80% of success rate . . 8.14 Success rate for soft drop versus CPA for small noise and noise of standard deviation T = 50 (recall (8.2)) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1 Representation of Side-Channel with masks . . . . . . . . . . . . . . . . . . . . . xv LIST OF FIGURES xvi List of Tables 1.1 List of the main encryption standards . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Summary of the related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 SNR for each Sbox for the DPA contest . . . . . . . . . . . . . . . . . . . . . . . 5.1 Summary of classical distinguishers. Among all the classical theoretical distinguishers, we notice that the expression of the theoretical value of DoM with κ(k) does not depend on σ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Success exponents for the classical distinguishers. The numerical values of SE are obtained for AES SubBytes least significant bit leakage model and noise of standard deviation σ = 4. Notice that in the monobit case, Euclidean distance and DoM have strictly the same success rate because -(X -Y (k)) 2 = -X 2 + 2XY (k) -1, and X 2 is independent of the choice of the key. . . . . . . . . . . . . . . . . . . . 5.3 Numerical values of κ min and κ max for DES . . . . . . . . . . . . . . . . . . . . . 5.4 Expression of the Success Exponent for the 5 studied distinguishers . . . . . . . . 6.1 State-of-the-art on profiled timing attacks . . . . . . . . . . . . . . . . . . . . . . xvii 1. INTRODUCTION Contents 1.1 On the Importance of Cyber Security . . . . . . . . . . . . . . . . 1.2 The Rise of Cryptography . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 A Bit of History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Cryptography Today . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Side-Channel Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Vulnerabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 A Look on Information Theory . . . . . . . . . . . . . . . . . . . . 1.4.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2 Link With Side-Channel Analysis . . . . . . . . . . . . . . . . . . . . 1.5 Organization of the Manuscript . . . . . . . . . . . . . . . . . . . . 1.6 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 1 . 1 :

 11 Figure 1.1: Screenshot of an infected system by WannaCry

Figure 1 . 2 :

 12 Figure 1.2: A scytale c CC BY-SA 3.0

Figure 1 . 3 :

 13 Figure 1.3: Representation of a side-channel attack

Figure 1 . 4 :

 14 Figure 1.4: One power consumption trace of DES algorithm

Figure 1 . 5 :

 15 Figure 1.5: The SNR of this leakage according to the Hamming weight model.

Figure 1 Figure 1 . 6 :

 116 Figure 1.6: A communication system by Shannon

Figure 1 . 7 :Figure 1 . 8 :

 1718 Figure 1.7: Claude Shannon c MFO

Figure 3 . 1 :

 31 Figure 3.1: Representation of Side-Channel

Contents 4 . 1 50 4. 1 . 1 50 4. 1 . 2

 4150115012 Numerical Approximations for Mutual Information . . . . . . . . Numerical Estimation of I(X; Y | T) . . . . . . . . . . . . . . . . . . Graphical Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.1.3 A Parametric Estimation of I(X; Y | T) . . . .

Figure 4 .

 4 Figure 4.1 shows the results on I(X; Y | T = t) obtained by Monte-Carlo simulation. We notice that

Figure 4 . 1 :

 41 Figure 4.1: Comparison of the two upper bounds (3.4) and (3.5).

4. 1 . 3 A

 13 Parametric Estimation of I(X; Y | T) An estimation of I(X; Y | T) with a simple analytic expression can be obtained by a parametric estimation of the mutual information. This study is based on an empirical model that fits 4.1 Numerical Approximations for Mutual Information correctly with I(X; Y | T). The information function I(q) = I(X; Y | T) can be approximated by the error function such as

4. 2

 2 Application to Two Leakage Models 4.2 Application to Two Leakage Models 4.2.1 Example for Monobit Leakage

  Section 4.1.1); • MI's upper bound (3.4); • MI's upper bound (3.5).

  (a) σ = 1 (b) σ = 4

Figure 4 . 3 :

 43 Figure 4.3: Success rates with monobit leakage.

4. 3

 3 Practical Applications(a) σ = 1 (b) σ = 4

Figure 4 . 5 :

 45 Figure 4.5: Success rate for a Hamming weight leakage

Figure 4 . 8 :

 48 Figure 4.8: SNR of the first Sbox for the first round of DES.

Figure 4 . 9 :

 49 Figure 4.9: Success rate for each DES Sbox

Figure 4 . 8 :

 48 Figure 4.8: Success rate for each DES Sbox

Figure 5 . 1 :

 51 Figure 5.1: Illustration of the two parts of the side-channel analysis context (in red).

  terms of the confusion coefficient and the standard deviation of the noise. These closed-form expressions of the success exponent enable the comparison of distinguishers based only on these two parameters. The flow chart of Fig. 5.2 situates our contributions in relation to the current state of the art.

Figure 5 . 2 :

 52 Figure 5.2: The state of the art in relation to our contributions (in yellow boxes-see also Tables 5.1 and 5.2 below).

  et al. as the probability that two sensitive variables arising from two different key hypotheses are different [32, Section 3.1].

Figure 5 .

 5 Figure 5.3 illustrates the confusion coefficient for a monobit leakage Y (k) = SubBytes(T ⊕ k) mod 2, where SubBytes is the AES substitution box (application F 8 2 → F 8 2) and ⊕ is the bitwise exclusive or. We notice that except for k = k * (here taken = 178), the confusion

Figure 5 . 3 :

 53 Figure 5.3: Confusion Coefficient for the AES SubBytes

. 17 )Figure 5 . 4 :

 1754 Figure 5.4: Illustration of a theoretical distinguisher

5. 3 . 1 A

 31 Communication Channel Between Y (k) and Y (k * ) To understand the link between any sensitive variable Y (k) and the leaking sensitive variable Y (k * ), consider the following information-theoretic communication channel between these two variables described in Fig. 5.5. This communication channel is simply a theoretical construction that helps explain the link between Y (k) and Y (k * ), which are both binary and equiprobable random variables taking their values in {±1}. The parameters p and p are the transition probabilities defined as p = P(Y (k * ) = +1|Y (k) = -1) and p = P(Y (k * ) = -1|Y (k) = +1).

Figure 5 . 5 :Lemma 5 . 1 .

 5551 Figure 5.5: Abstract communication channel between Y (k) and Y (k * )

Figure 5 . 6 :

 56 Figure 5.6: Representation of the channel capacity according to κ(k)

- 2 . 5 . 1 .y

 251 Theorem Any theoretical distinguisher D(k) for a binary leakage y can be expressed as a function of κ(k) and σ. Proof. Any theoretical distinguisher is defined in terms of the joint probability distribution of X and Y (k), noted p(x, y(k)). Now for any x ∈ R and y(k) = ±1, p(x, y(k)) = P(y(k)) p(x | y(k)) (k * ) p(y(k * ) + n | y(k), y(k * )) P(y(k * ) | y(k)) (5.25) where P(y(k * ) | y(k)) is the transition probability of the channel defined in Fig. 5.5. There are two possibilities. Either y(k) = y(k * ), and in this case P(y(k * )|y(k)) = 1κ(k), or y(k) = y(k * ) and in this case P(y(k * )|y(k)) = κ(k).

. 31 ) 5 . 1 .

 3151 Remark With respect to their theoretical distinguishers, DoM is in bijection with the Euclidean distance, and CPA is in bijection with KSA. Indeed, the Euclidean distance isD(k) = 4( 1 /2κ(k)) -2σ 2and σ is independent from the choice of the key. Therefore, there is a bijection between 4( 1 /2κ(k)) -2σ 2 and 2( 1 /2κ(k)) which is the theoretical value of DoM. Regarding CPA and KSA, both distinguishers are functions of | 1 /2κ(k)|.

Figure 5 . 7 :

 57 Figure 5.7: Representation of g(σ)

Figure 5 . 11 :

 511 Figure 5.11: Success Exponent for DES (κmin = 0.25, κmax = 0.8125)

Figure 6 . 1 :

 61 Figure 6.1: Illustration of two practical situations where MIA can defeat CPA

Assumption 6 . 1 (

 61 Markov condition). The leakage x depends on the actual secret key k * only through the computed model y = ϕ(f (k * , t)).

Definition 6 . 1 (

 61 Empirical Mutual Information). The empirical mutual information is defined as I( x, y) = x∈X,y∈Y P(x, y) log 2 P(x, y)

. 19 )PP

 19 Thus, for each given sequences x, t maximizing the success rate amounts to choosing k = k so as to maximize P( x| y) = P( x| y = ϕ(f (k = k, t))):k = arg max k P( x| y). (6.20)When no profiling is possible the conditional distributionP( x| y) = q i=1 P( x i | y i ) (6.21) 6. WHEN MIA IS A MAXIMUM LIKELIHOOD AND BETTER THAN CPA is unknown to the attacker. Therefore, Theorem 6.1 is no longer practical and we require a universal 1 version of it. Definition 6.3 (Universal Maximum Likelihood). Let y = ϕ(f (k, t)). The universal maximum likelihood (UML) key estimate is defined by k = arg max k ( x i | y i ). (6.23)

Figure 6 . 2 :

 62 Figure 6.2: Success rate for σ = 2 (left) and σ = 4 (right), when Y ∼ U({±1}) and N ∼ U({±σ})

Figure 6 . 3 :Figure 6 . 4 :

 6364 Figure 6.3: Success rate for the attack of a bitsliced algorithm on an 8-bit processor, where 7 bits make up algorithmic noise, and have weight 0.5, 1.0 (top) and 0.8 and 2.0 (bottom).

d

  = {37, 93, 163}. More precisely, for d = 9 we have y (k) = ( 1, y 1 (k), y 2 (k), . . . , y 8 (k)) with y j (k) = [Sbox(k ⊕ T )] j where [•] j : F n 2 → F 2 is the projection mapping onto the j th bit. For d = 37 the attacker additionally takes into consideration the products between all possible y j (1 ≤ j ≤ 8), i.e., y 1 • y 2 , y 1 • y 3 , y 1 • y 4 and so on. Consequently, d = 93 considers additionally the product between 3 y's and d = 163 includes also all possible product combinations with 4 columns. See [37] for a detailed description on the selection of basis functions. (a) σ = 0 (b) σ = 1 (c) σ = 2 (d) σ = 3

Figure 6 . 5 :

 65 Figure 6.5: Success rate for σ ∈ {0, 1, 2, 3} when the model is unknown

Fig. 6 .

 6 Fig.6.5 shows the success rate using 100 independent experiments. Perhaps surprisingly, MIA turns out to be more efficient than LRA. Quite naturally, MIA and LRA become closer as the the variance of the independent measurement noise N increases. It can be seen that LRA using higher dimension requires a sufficient number of traces for estimation (for d = 37 around

  (a) ∆ = 1, correct key guess (b) ∆ = 1, false key guess (c) ∆ = 5, correct key guess (d) ∆ = 5, false key guess

Figure 6 . 6 :

 66 Figure 6.6: Estimated P(X|Y ) using 40 traces for σ = 2 (see Fig. 6.5(c))

2 m 3 :

 23 cf. Eqn. (6.1) end end I( x, y(k)) = 0 for y ∈ Y do P(y) = 0 // P(y) holds m P(y), cf. Eqn. (6.7) for x ∈ X do P(y) += P(x, y) end for x ∈ X do // Nota bene: ( P(x) = 0 ∨ P(y) = 0) =⇒ P(x, y) = 0 if P(x) = 0 and P(y) = 0 then I( x, y(k)) += P(x,y) m log x, y(k))) k∈K // As in Eqn. (6.10) 6. WHEN MIA IS A MAXIMUM LIKELIHOOD AND BETTER THAN CPA Algorithm Computation of the MIA success rate input :

+= 1 end 12 if

 112 for k ∈ K do // Key enumeration + + score k = MIA-Distinguisher(PMF, k) + + // See MIA-Distinguisher 10 score k = MIA-Distinguisher(PMF, k) // Function at page 116 11 end arg max k∈K score k = k * then 13 SR k * [step] += 1 /M

.1) 5 end 6 ∀x 7 for y ∈ Y do 8 for x ∈ X do 9 P 2 P

 567892 ∈ X, y ∈ Y, P(x, y) = 0 // cf. Eqn. (6.8) (x, y) = 1 /m PMF[y][x] end end for y ∈ Y do P(y) = 0 // cf. Eqn. (6.7) for x ∈ X do P(y) += P(x, y) end end for x ∈ X do P(x) = 0 // cf. Eqn. (6.7) for y ∈ Y do P(x) += P(x, y) end end for y ∈ Y do for x ∈ X do // Nota bene: ( P(x) = 0 ∨ P(y) = 0) =⇒ P(x, y) = 0 if P(x) = 0 and P(y) = 0 then I( x, y(k)) += P(x, y) log ( I( x, y(k))) k∈K // As in Eqn. (6.10)

a

  timing leakage in the conditional extra-reductions of Montgomery modular multiplications. Some conditional operations can also happen in AES, e.g. in field operations, as for instance discussed in [27, Alg. 1].

Figure 7 . 1 :

 71 Figure 7.1: Empirical probability P(x|t ⊕ k) for t = 0 and k = 67 and q = 2 560 000

Figure 7 . 2 :

 72 Figure 7.2: Empirical probability P(x|t ⊕ k) for t = 0 and k = 149 and q = 2 560 000

Figure 8 . 1 :

 81 Figure 8.1: Measuring elapsed time for AES encryption

Figure 8 .

 8 Figure 8.2 has to be compared with a full AES encryption timing in order to see if this model is relevant. Therefore, we have plotted in Figure 8.3 the histogram for a full AES encryption.

Figure 8 . 2 :Figure 8 . 3 :Figure 8 . 4 :Figure 8 . 5 :

 82838485 Figure 8.2: Distribution of the clock cycles for a simple example

Figure 8 . 8 :

 88 Figure 8.8: Empirical number of empty bins

Figure 8 . 9 :Figure 8 . 10 : 8 . 1

 8981081 Figure 8.9: Average MSE for the Learned MIA Distinguisher

Figure 8 . 11 :

 811 Figure 8.11: Variance and bias of the Learned MIA Distinguisher

  metric recently introduced by Standaert et al. in [71, Eqn. (1)].

9. 1 Conclusion

 1 The title of my Ph.D. is "Towards a Better Formalization of the Side-Channel Threat". When I was recruited by Olivier Rioul in 2015 to start my Ph.D., Annelie Heuser was finishing writing her manuscript. During her thesis, she specially focused on the study of distinguishers. I could therefore use her fresh results to work on my thesis.During my thesis, I focused on the similarities between a side-channel leakage model and a communication channel. The main result of these three years is based on a mathematical link between the success rate of an attack and the signal-to-noise ratio of the leakage. To obtain this result, I have used information theoretic tools. More specifically, I focused on the Mutual

  More generally, this three years and a half Ph.D. has made of me a more mature man. When I started in 2015, I had no idea of what I could do after my thesis. During these three years I have learned how to be rigorous and how to self-criticize my work. I believe that I will be very well prepared for my future work.

9. 2

 2 Further Perspectives

xP 2 kP 2 kP

 22 (x | t) log 2 P(x | t)) =x k P(k)P(x | t, k) log 2 k P(k)P(x | t, k) i | t i , k) log i | t i , k)Re-arranging both products so that they are ordered in accordance with the permutation, we obtainH(X | T = t) =τ (i) | t τ (i) , k) log 2 k P(k) q i=1 P(x τ (i) | t τ (i) , k) i | t τ (i) , k) log i | t τ (i) , k) = H(X | T = τ (t))

A. 3 1 A. 3

 313 Proof of Corollary 3.Proof of Corollary 3.1

4

 4 Alternative Proof of (3.5) and Further Comments Consider, for any random vector Y ,∆ = I(X; Y) + E Y log E Y exp E X|Y log P(X | Y ) P(X | Y) = E Y E X|Y log P(X | Y) P(X) + E Y log E Y exp E X|Y log P(X | Y ) P(X | Y) = E Y log exp E X|Y log P(X | Y) P(X) + E Y log E Y exp E X|Y log P(X | Y ) P(X | Y) = E Y log E Y exp E X|Y log P(X | Y) P(X) + E Y log E Y exp E X|Y log P(X | Y ) P(X | Y) = E Y log E Y exp E X|Y log P(X | Y)P(X | Y ) P(X)P(X | Y) = E Y log E Y exp E X|Y log P(X | Y ) P(X)By the concavity of the log function,∆ ≤ E Y log E Y exp log E X|Y P(X | Y ) P(X) = E Y log E X|Y E Y P(X | Y ) P(X) = E Y log E X|Y P(X ) P(X)where the X distribution is given by P(x ) = E Y P(x | Y ).It is important to note that this derivation can be applied for any random vector Y . The derivations made in Section 3.2 were made for Y following the same distribution as Y. In this case P(X ) = P(X) and∆ ≤ E Y log E X|Y Pto take an i.i.d. vector Y having the same marginals as Y.Then ∆ = E Y log E Y exp E X|Y log P(X | Y ) P(X)and by Corollary 3.1,∆ ≤ E Y log exp E X|Y log E Y P(X | Y ) P(X) = E Y E X|Y log E Y P(X | Y ) P(X) = E X,Y log i P(X i ) P(X) × P(X | Y) P(X | Y) = I(X; Y) -qI(X; Y )which is to be compared to Lemma 3.3. This proves that if applying our second bound with such an i.i.d. distribution Y would lead to a bound that would be worse than the first upper bound (3.4).

Theorem 1 . 1 (

 11 Channel Coding with Divergence). Let us consider a channel noted (Y, P(y|x), X),

PP

  XY XY (x, y)≥ |A ε P XY |2 -n(H(X,Y )+D(P XY || P XY )+ε)

B. 1 1 √ 2 + ( 1 2 + ( 1 5 )

 1121215 Proof ofLemma 5.3 The MIA distinguisher is expressed asD(k) = I(Y (k * ) + N ; Y (k)) = h(Y (k * ) + N )h(Y (k * ) + N | Y (k)). (B.1)From Section 5.3.1, Y (k * ) knowing Y (k) is a binary random variable with probability κ(k).As N is Gaussian independent from Y (k), the pdf of Y (k * ) + N knowing Y (k) is a Gaussianmixture that can take two forms:p κ(k) (x) =    2πσ [κ(k)e -(x-1) 2 2σκ(k))e -(x+1) 2 2σ 2 ] 1 √ 2πσ [κ(k)e -(x+1) 2 2σκ(k))e -(x-1) 2 2σ 2 ] , (B.2)By symmetry, their entropy h(Y (k * ) + N | Y (k)) will be the same and we can take any of these pdfs. Letting ϕ be the standard normal density, we can writep κ(k) (x) = p 1/2 (x) -2(1/2κ(k))ϕ(x)e -For notational convenience define ε = 2(1/2κ(k)), p = p 1/2 (x), and t = tanh(x). Then I(X; Y (k)) = h(Y (k * ) + N )h(Y (k * ) + N | Y (k)) (B.6) =p log 2 p + (p(1εt)) log 2 (p(1εt)) (B.7) =εpt log 2 p + p log 2 (1εt)pεt log 2 (1εt). (B.8)

pt 2 + O(ε 4 x σ 2 ) 2 = 2 ( 1 / 2 - 2 . (B. 26 )

 2422212226 tanh 2 ( x σ 2 )dx.(B.12)B. APPENDIX ABOUT THE MONOBIT LEAKAGESThe variance term is the difference of the two following quantitiesE (∓Y (k * )Y (k) + N (Y (k * ) ∓ Y (k))) 2 = 1 + 2σ 2 (1 -2| 1 /2κ(k)|) (B.25) E ∓Y (k * )Y (k) + N (Y (k * ) ∓ Y (k)) κ(k))Combining all the above expressions we obtain (5.33).

F

  (x|Y (k) = 1) -F (x)] = E[Y (k)Φ(x -X i )] (B.30) = E[Y (k)Φ(x -Y (k * )the absolute value is for x = 0 and we obtain:E[ F (x|Y (k) = 1) -F (x)] ∞ = |0.5κ(k)| erf 1 σ √ 2 . (B.33) C.1 The OpenSSL AES Encryption Code t2 = Te0 [ s2 >> 24] ^Te1 [( s3 >> 16) & 0 xff ] ^Te2 [( s0 >> 8) & 0 xff ] ^Te3 [ s1 & 0 xff ] ^rk [ 6]; t3 = Te0 [ s3 >> 24] ^Te1 [( s0 >> 16) & 0xff ] ^Te2 [( s1 >> 8) & 0 xff ] ^Te3 [ s2 & 0 xff ] ^rk [ 7]; s0 = Te0 [ t0 >> 24] ^Te1 [( t1 >> 16) & 0 xff ] ^Te2 [( t2 >> 8) & 0 xff ] ^Te3 [ t3 & 0 xff ] ^rk [ 8]; s1 = Te0 [ t1 >> 24] ^Te1 [( t2 >> 16) & 0 xff ] ^Te2 [( t3 >> 8) & 0 xff ] ^Te3 [ t0 & 0 xff ] ^rk [ 9]; s2 = Te0 [ t2 >> 24] ^Te1 [( t3 >> 16) & 0 xff ] ^Te2 [( t0 >> 8) & 0 xff ] ^Te3 [ t1 & 0 xff ] ^rk [10]; s3 = Te0 [ t3 >> 24] ^Te1 [( t0 >> 16) & 0 xff ] ^Te2 [( t1 >> 8) & 0 xff ] ^Te3 [ t2 & 0 xff ] ^rk[START_REF] Brier | Correlation power analysis with a leakage model[END_REF];t0 = Te0 [ s0 >> 24] ^Te1 [( s1 >> 16) & 0 xff ] ^Te2 [( s2 >> 8) & 0 xff ] ^Te3 [ s3 & 0 xff ] ^rk [12]; t1 = Te0 [ s1 >> 24] ^Te1 [( s2 >> 16) & 0 xff ] ^Te2 [( s3 >> 8) & 0 xff ] ^Te3 [ s0 & 0 xff ] ^rk [13]; t2 = Te0 [ s2 >> 24] ^Te1 [( s3 >> 16) & 0 xff ] ^Te2 [( s0 >> 8) & 0 xff ] ^Te3 [ s1 & 0 xff ] ^rk [14]; t3 = Te0 [ s3 >> 24] ^Te1 [( s0 >> 16) & 0 xff ] ^Te2 [( s1 >> 8) & 0 xff ] ^Te3 [ s2 & 0 xff ] ^rk [15]; s0 = Te0 [ t0 >> 24] ^Te1 [( t1 >> 16) & 0 xff ] ^Te2 [( t2 >> 8) & 0 xff ] ^Te3 [ t3 & 0 xff ] ^rk [16]; s1 = Te0 [ t1 >> 24] ^Te1 [( t2 >> 16) & 0 xff ] ^Te2 [( t3 >> 8) & 0 xff ] ^Te3 [ t0 & 0 xff ] ^rk [17]; s2 = Te0 [ t2 >> 24] ^Te1 [( t3 >> 16) & 0 xff ] ^Te2 [( t0 >> 8) & 0 xff ] ^Te3 [ t1 & 0 xff ] ^rk [18]; s3 = Te0 [ t3 >> 24] ^Te1 [( t0 >> 16) & 0 xff ] ^Te2 [( t1 >> 8) & 0 xff ] ^Te3 [ t2 & 0 xff ] ^rk [19]; t0 = Te0 [ s0 >> 24] ^Te1 [( s1 >> 16) & 0 xff ] ^Te2 [( s2 >> 8) & 0 xff ] ^Te3 [ s3 & 0 xff ] ^rk [20]; t1 = Te0 [ s1 >> 24] ^Te1 [( s2 >> 16) & 0 xff ] ^Te2 [( s3 >> 8) & 0 xff ] ^Te3 [ s0 & 0 xff ] ^rk [21]; t2 = Te0 [ s2 >> 24] ^Te1 [( s3 >> 16) & 0 xff ] ^Te2 [( s0 >> 8) & 0 xff ] ^Te3 [ s1 & 0 xff ] ^rk [22]; t3 = Te0 [ s3 >> 24] ^Te1 [( s0 >> 16) & 0 xff ] ^Te2 [( s1 >> 8) & 0 xff ] ^Te3 [ s2 & 0 xff ] ^rk [23]; Titre: Vers une meilleure formalisation des attaques par canaux cachés. Mots clés: Cryptographie, canaux cachés, Théorie de l'information, optimisation Résumé: Dans le cadre de la sécurité des systèmes embarqués, il est nécessaire de connaître les attaques logicielles et physiques pouvant briser la sécurité de composants cryptographiques garantissant l'intégrité, la fiabilité et la confidentialité des données. Étant donné que les algorithmes utilisés aujourd'hui comme Advanced Encryption Standard (AES) sont considérés comme résistants contre la cryptanalyse linéaire et différentielle, d'autres méthodes plus insidieuses sont utilisés pour récupérer les secrets de ces composants. En effet, la clé secrète utilisée pour le chiffrement de données peut fuiter pendant l'algorithme. Il est ainsi possible de mesurer cette fuite et de l'exploiter. Cette technique est appelée attaque par canal auxiliaire. Le principal objectif de ce manuscrit de thèse est de consolider les connaissances théoriques sur ce type de menace. Pour cela, nous appliquons des résultats de théorie de l'information à l'étude par canal auxiliaire. Nous montrons ainsi comment il est possible de comparer un modèle de fuite à un modèle de transmission de l'information. Dans un premier temps, nous montrons que la sécurité d'un composant est fortement dépendante du rapport signal à bruit de la fuite. Ce résultat a un impact fort car il ne dépend pas de l'attaque choisie. Lorsqu'un designer équipe son produit, il ne connaît pas encore la manière dont son système embarqué pourra être attaqué plusieurs années plus tard. Les outils mathématiques proposés dans ce manuscrit pourront aider les concepteurs à estimer le niveau de fiabilité de leurs puces électroniques.Title: Towards a Better Formalisation of the Side-Channel Threat.

Table 1 . 1 :

 11 List of the main encryption standards

	1. INTRODUCTION
	Code	Year and	Size of	Broken?
		type	the key
	DES	1977 -symmetric	56 bits	Yes
	RSA	1983 -asymmetric	2048 bits	No 1
	RC4	1987 -symmetric	40 to 256 bits	Yes
	AES (see 1.2.3) 1999 -symmetric 128, 192 or 256 bits	No 2

  Formal Security Proofs and Studies . . . . . . . . . . . . . . . . . 20 2.1.1 A Generic Bound for Any Leakage With Only SNR . . . . . . . . . . 20 2.1.2 Extension to Template Attacks . . . . . . . . . . . . . . . . . . . . . 22 2.1.3 MIA is Universal ML . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1.4 A Unified Vision of Monobit Leakages . . . . . . . . . . . . . . . . . 23 2.2 Adapting Theoretical Tools for Practical Issues . . . . . . . . . . 23 2.2.1 Avoid the Empty Bin Issue . . . . . . . . . . . . . . . . . . . . . . . 24

	1. INTRODUCTION 2. CONTRIBUTIONS
	Contents
	2.1
	Chapter 2
	Contributions
	19

2.2.2 Extract a Model for a Timing Attack . . . . . . . . . . . . . . . . . 24

Table 2 . 1 :

 21 Summary of the related work

	Our main contribution is to give a clear relationship between MI
	and probability of success. More precisely, we seek a lower bound on the number of available

Table 4 .

 4

	4. APPLICATION
	Sbox # SNR Prediction for 99% CPA 99%
	0	0.144	112	230
	1	0.077	203	350
	2	0.075	208	350
	3	0.071	220	450
	4	0.064	243	300
	5	0.151	107	190
	6	0.079	198	330
	7	0.136	118	270

1: SNR for each Sbox for the DPA contest

  This chapter presents the work accepted at InsCrypt 2018 conference. The conference will take place in Fuzhou, China http://xxhb.fjnu.edu.cn/inscrypt2018/. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.2 Modelization and Definitions . . . . . . . . . . . . . . . . . . . . . 73 5.2.1 The Leakage Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.2.2 The Confusion Coefficient . . . . . . . . . . . . . . . . . . . . . . . . 74 5.2.3 Distinguishers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

	Contents
	5.1
	Chapter 5
	When Monobit Leakages are
	III Defined with the Confusion
	Coefficient
	A Mathematical Study of
	Distinguishers

5.3 Theoretical Expressions for Distinguishers . . . . . . . . . . . . . 79 5.3.1 A Communication Channel Between Y (k) and Y (k * ) . . . . . . . . . 79 5.3.2 A General Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.3.3 Classical Distinguishers as Functions of κ(k) and σ 2 . . . . . . . . . 81 5.4 Comparing Distinguishers with the Success Exponent . . . . . . 83 5.4.1 Mathematical Expression of SE . . . . . . . . . . . . . . . . . . . . . 83 5.4.2 Comparison of Distinguishers Based on their Success Exponent . . . 87 5.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

Table 5 .

 5

	83

2. As a direct consequence of Theorem 5.1, all of these success exponents are function

Table 5 . 2 :

 52 Success exponents for the classical distinguishers. The numerical values of SE are obtained for AES SubBytes least significant bit leakage model and noise of standard deviation σ = 4. Notice that in the monobit case, Euclidean distance and DoM have strictly the same success rate because -

Table 5 . 4 :

 54 Expression of the Success Exponent for the 5 studied distinguishers

  Notations and Assumptions . . . . . . . . . . . . . . . . . . . . . . . 98 6.2.2 Mathematical Derivation . . . . . . . . . . . . . . . . . . . . . . . . 101 6.2.3 MIA Faster Than ML Distinguisher . . . . . . . . . . . . . . . . . . 103 6.3 Non-Gaussian Noise Challenge . . . . . . . . . . . . . . . . . . . . 104

	6. WHEN MIA IS A MAXIMUM LIKELIHOOD AND BETTER THAN CPA
	This chapter covers the work presented at ArticCrypt 2016.
	Contents
	6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	96
	6.2 Optimality of Mutual Information Analysis . . . . . . . . . . . . .	98
	6.2.1

6.3.1 Pedagogical Case-study . . . . . . . . . . . . . . . . . . . . . . . . . 104 6.3.2 Application to Bitslice PRESENT . . . . . . . . . . . . . . . . . . . 106 6.4 Partially Unknown Model Challenge . . . . . . . . . . . . . . . . . 107 6.5 Fast Computations . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.5.1 Fast computation of CPA . . . . . . . . . . . . . . . . . . . . . . . . 110 6.5.2 Fast computation of MIA . . . . . . . . . . . . . . . . . . . . . . . . 112 6.5.3 Standard computation algorithm for MIA . . . . . . . . . . . . . . . 115 6.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

  Key enumeration // From x and y, build a hash table PMF[y][x] (i.e., an histogram)

Table 6 . 1 :

 61 State-of-the-art on profiled timing attacks

	Profiling method	Reference articles
	Moments	[5, 8, 69, 87]
	Distributions	This part (Caution about empty bins)

  7. METHODS TO SOLVE THE EMPTY-BIN ISSUEWe recognize another Dirichlet distribution with parameters n x ,t + n x ,t + α x ,t . LetN α = Γ( x ,t α x ,t + n x ,t +α x ,t )x,t Γ(αx,t+ n x ,t +α x ,t ) be the new normalization constant for this distribution. We, finally, obtain f (p, x, t| x, x, t, t) = p x,t • N α

	Again by Bayes' rule,
	f (p| x, x, t, t) =	P( x, x, t, t|p)f (p) P( x, x, t, t)
	=	n x ,t + n x ,t (k) x ,t P( x, x, t, t) x ,t ∈X×T p	f (p)
	=	N α P( x, x, t, t) x ,t ∈X×T	p n x ,t + n x ,t +α x ,t -1 x ,t	.
			p	n x ,t + n x ,t +α x ,t -1 x ,t	.	(7.13)
			x ,t ∈X×T
	Therefore,
	P(x, t| x, x, t, t) = p x,t • N α	x ,t ∈X×T p n x ,t + n x ,t +α x ,t -1 x ,t	dp.

  Contents 8.1 Results on Real Devices . . . . . . . . . . . . . . . . . . . . . . . . 142 8.1.1 The ARM processor . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 8.1.2 Weaknesses -Non Constant AES Time . . . . . . . . . . . . . . . . . 143 8.1.3 Characterizing the leakages for Data Cache On . . . . . . . . . . . . 144 8.1.4 Attack Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 8.1.5 Nature of Empty Bins . . . . . . . . . . . . . . . . . . . . . . . . . . 152 8.1.6 Study on the Mean-Square Error . . . . . . . . . . . . . . . . . . . . 153 8.2 Success Rate in Presence of External Noise . . . . . . . . . . . . 159 8.2.1 Effect of Measurement Noise . . . . . . . . . . . . . . . . . . . . . . 159 8.2.2 Comparison with Existing Methods in the Presence of Noise . . . . . 160 8.3 Conclusion and Perspectives . . . . . . . . . . . . . . . . . . . . . . 163

  1 . It contains an STM32F407VGT6 microcontroller, which has an ARM cortex-M4 MCU with 1 MB flash memory for instructions and data, and a 192 KB Random Access Memory (RAM). The RAM is divided into three sections: one of 16 KB, another one of 112 KB, and the last one consisting of 64 KB Core

  8.2 Success Rate in Presence of External Noise8.2 Success Rate in Presence of External NoiseThe measurement setup used in simulation (Sec. 7.3) and on real-world traces (Sec. 8.1) is ideal. Indeed, the only considered noise is said algorithmic, i.e., it consists in the varying timing which arise from the parts of the algorithm not under study. In this section, we analyse the effect of noise external to the monitored cryptographic algorithm. Subsection 8.2.1 discusses in general terms the effect of noise addition, and subsection 8.2.2 details quantitatively how distribution-based distinguishers cope efficiently with noise (while moment-based distinguishers fail to resist noise).

  8.2 Success Rate in Presence of External NoiseFigure 8.13: Comparison between CPA and soft drop distinguisher at 80% of success rate8.3 Conclusion and Perspectivesmethods such as CPA. Indeed, distribution-based profiling is more accurate than CPA estimation with noisy signals. For instance, the results from Hassan Aly and Mohammed ElGayyar[START_REF] Aly | Attacking AES Using Bernstein's Attack on Modern Processors[END_REF] show that 222 encryptions are required for a key extraction on a more recent processors (Pentium Dual-Core and Core 2 Duo), which is significantly more than that used by Bernstein CPA in his original attack[START_REF] Daniel | Cache-timing attacks on AES[END_REF]. The authors of this paper remark incidentally that the best method is not to use correlation with the means of each class, but with the minimum value in each class. This confirms that the complexity of the distributions are better suited for distinguishing that simply the average per class. This justifies that our study focuses on distribution-based distinguishers (more robust to binary noise situations encountered while measuring durations) rather than moment-based distinguishers (recall Tab. 6.1).

3.2 Theoretical Bounds on Mutual Information . . . . . . . . . . . .

The binary entropy is the entropy of a binary random variable with probabilities p and 1 -p.

Fano's inequality is an important information-theoretic result about the uncertainty of the transmission of a message, which is due to the error probability and the number of possible errors.

An alternative proof of inequality (3.5), which resorts only on convexity arguments, is given in Appendix A.4.

APPLICATIONFigure 4.6: Comparison of our prediction with Duc's bound

We cover in this chapter the following distinguishers: Difference of Means or DoM[START_REF] Paul | Differential power analysis[END_REF], Correlation Power Analysis or CPA[START_REF] Brier | Correlation power analysis with a leakage model[END_REF], Euclidean distance[39, §3], Kolmogorov-Smirnov Analysis or KSA[START_REF] Whitnall | An Exploration of the Kolmogorov-Smirnov Test as a Competitor to Mutual Information Analysis[END_REF], and Mutual Information Analysis or MIA[START_REF] Gierlichs | Mutual information analysis[END_REF].

In[START_REF] Sylvain Guilley | A Key to Success -Success Exponents for Side-Channel Distinguishers[END_REF], CPA is treated as a distinguisher, but without the absolute values. Those remove false positives which occur in monobit leakages when there are anti-correlations. Our value of the success exponent is, therefore, different from theirs.

We did not plot for values of σ lower than 5, since the lemmas are true for large values on σ.

Figure 5.10: Success Exponent for DES (κmin = 0.125, κmax = 0.75)

Obviously, this hypothesis only holds provided the device manufacturer does not reuse the same cryptographic engine in an open platform, such as a JavaCard, where the user is able to use the cryptographic API at its will.

We comply with the usual notations of[START_REF] Durvaux | How to Certify the Leakage of a Chip?[END_REF] where offline quantities are indicated with a hat, whereas online quantities are indicated with a tilde. In this chapter, there is no profiling phase hence no offline quantities.

We use bold letters to indicate vectors while scalars are presented using small italic letters.

We refer the interested reader to the work done in[START_REF] Whitnall | The Myth of Generic DPA . . . and the Magic of Learning[END_REF] Sec. 3]. We note that y i = k ⊕ t i does not lead to a sound distinguisher, as for all k , x → x ⊕ k is bijective, and maps y k to y k⊕k . On the contrary, there is no bijection β such that for all t, w H (k ⊕ t) = β(w H (k ⊕ k ⊕ t)). So the choice y i = w H (k ⊕ t i ) is sound.

Universal, in the information theoretic sense of the word, means: computed from the available data without prior information.

In practice, logarithms require a high computational power, hence the number of calls to this function shall be minimized.

The least significant bit S 0 of the PRESENT Sbox S is not suitable because one has ∀z ∈ F[START_REF] Beaudry | An intuitive proof of the data processing inequality[END_REF]

, S 0 (z) = S 0 (z ⊕ 0x9) = ¬S 0 (z ⊕ 0x1) = ¬S 0 (z ⊕ 0x8). As in Eq. (6.3) of footnote 1, ties occur: it is not possible to distinguish k * , k * ⊕ 0x9, k * ⊕ 0x1, k * ⊕ 0x8 (the corresponding bijections are respectively x → x and x → 1 -x). Therefore, we consider component 1 instead of 0, which does not satisfy such relationships.

We will explain in Subsec. 8.2.2 that in practice, maximum likelihood might not always perform better than moment-based distinguishers in ideal situations (no noise), because the learning stage for probability mass functions demands too many traces; besides an imperfect profiling is very detrimental to maximum likelihood distinguishers, and affects less the moment-based distinguishers. However, in non-ideal situations, e.g., in the presence of random delay kind of noise, maximum likelihood remains robust, where the model-based distinguishers collapse (since they are value-based).

The AES meets the secret and the text byte through a xor (SubBytes) executed in a fixed number of clock cycles. However, the rest of the AES consists in table look-ups and other miscellaneous operations which are difficult to model and need different amounts of time to execute, hence the use of unknown function ψ.

For the sake of evading the empty bin issue, we will also introduce yet another notation " s Pα" in section 7.2.1 (Equation (7.15)).

Figures obtained with the STM Discovery Board presented in Section 8.1. The unit of x is the "clock cycle".

We emphasize that the attacks we present are not due to a flaw in ARM or STMicroelectronics processors.Instead, as we will discuss next, the CCM feature of STM32F4 processors allows to protect the implementation against timing attacks by granting a constant execution time.

This is a voluntary choice as we only focus on the gap between two picks of distribution. The absolute value has no real sense since we are comparing two computations that are not the same.

Remerciements

The first step of the demonstration of Theorem 3.1 is the following lemma that links the Mutual Information between the random vectors X and Y with the probability of success. INFORMATION Proof. From the memoryless assumption of the channel, one has P X|Y = q i=1 P Xi|Yi . Thus INFORMATION

Application to Additive White Gaussian Noise

In this section, we develop the results of Theorem 3.1 for leakages with additional white Gaussian noise. Indeed, this is the most common case for attacks such as DPA, where the noise comes from the measurement tools.

With this model, we can link the success rate to Shannon's capacity C = 1 2 log(1 + SNR), and therefore, to the SNR, where SNR = VAR(Y ) INFORMATION Lemma 3.7. Let t ∈ T q be fixed and k ∈ K be a fixed key. We have

where δ XT (•) is the permutation that re-orders the probabilities P(k | X, T) into the decreasing order. There exists a relationship between N K and H(K | X, T) called the inequality of Massey [55, Section 2]:

We propose here an improved inequality relating N k with H(K | X, T).

Lemma 3.9 (Improved Inequality of Massey). The average number of tries to recover the correct key is upper-bounded by:

Our inequality improves Massey's inequality as soon as the entropy is greater than log 2 ( e 1-e/4 ).

for all k ∈ N * . As k b k = 1, b k is a distribution (geometric). Moreover, by the Gibbs inequality [START_REF] Cover | Elements of Information Theory[END_REF],

In fact, the inequality is strict since equality would hold if and only if P(k | X, T) = b δ X,T (k) , which is not the case as the support of P is finite and the support of b k is not. Therefore, we have proven that:

Last, we notice that the function f (x) = x log 2 (x) is convex ( f (x) = log 2 (ex) is increasing). Therefore, fore any x in the range ]0, 1[, we have:

x -(x -1) ≤ f (x) = log 2 (ex).

When we apply this for x = N K , we get:

≤ log 2 (eN K ).

Overall, this means that H(K | X, T) < log 2 (eN K ) which proves the lemma. INFORMATION 4. APPLICATION Remark 4.1. For this leakage model, with a balanced vector t, one needs at least 8 traces to obtain 256 different vectors y, since the function k → y(k) is one-to-one.

Example for Hamming Weight Leakage

In practice, the AES algorithms compute SubBytes with 8 bits. The leakage function are therefore different if we take this into account. Our conclusion is the same. We now consider the leakage model based on the Hamming Weight:

where S box is the AES substitution box and H w is the Hamming weight function. Once again, we notice that our bounds are above the optimal distinguisher and that the closest estimation of the MI gives the tightest bound. of [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF]). The KSA is requiring a bit less than the double of traces, compared to Euclidean distance, DoM and CPA. The MIA performs really bad compared to the other distinguishers.

Error bars represent the inaccuracy while estimating the SR (here, we ran 100 simulations). These simulations are therefore in complete coherence with the theoretical results of Table 5.2.

Indeed, the order of the distinguishers is the same w.r.t. the success rate and w.r.t. the success exponent. In addition, according to the definition of the success exponent SE in (5.32), the number of traces q to reach a given success rate (e.g., SR = 80%) is proportional to the inverse of SE. This quantitative law is satisfied in the simulation of Fig. 5.8. For an accurate validation, we have plotted in Fig. 5.9 the success exponent vs the success rate, and indeed points are aligned. them are easy to compute because the confusion coefficient can be calculated with the knowledge of the operating substitution box and the SNR can be measured offline.

Comparing Distinguishers with the Success Exponent

Element

Our work is useful to predict how fast a distinguisher will succeed to recover the secret key.

Long and painful simulations can be advantageously replaced by the computation of the success exponent using closed-form expressions. This chapter also consolidates the state of the art about the classical distinguishers, especially for MIA and KSA. We have derived the success exponent for these two distinguishers as a function of the confusion coefficient and the standard deviation of the noise.

Chapter 6

When MIA is a Maximum Likelihood and better than CPA Contributions In this part, we show that even when all abovementioned requirements (a), (b), and (c) are not present, timing attacks with incomplete profiling can be achieved successfully by adapting the maximum likelihood distinguisher and keeping the histogram method for probabilities estimation. We build six different distinguishers, which are all good answers to the empty bin issue. For some of them, new histograms are built, such that the empty bin issue totally disappears. Furthermore, we compare these distinguishers and show which one of them is the best in every specific context. We underline that, in practice, for a moderate profiling with 256 000 offline measurements, the soft drop and the combined offline-online profiling approaches are clearly the two best strategies: the AES key is typically extracted with only about 2 000 online measurements, i.e., a complete break in about 0.2 ms. Finally, we provide some theoretical results proving how optimal some of the distinguishers can be.

Organization The part is organized according to the following structure. In Chapter 7, we first provide the mathematical tools to deal with the empty bins issue.

Mathematical Derivations

The mathematical notations and assumptions presented here will also be used in Chapter 8.

Notations and Assumptions

We consider a side-channel attack with a profiling stage and use the following notations:

• during the profiling phase, a vector t of q text bytes is sent and the profiler garners a vector of x measurements;

• during the attacking phase, a vector t of q text bytes is sent and the attacker gathers a vector x of leakage measurements-also customarily known as traces;

• we use simplified notations t, q and x when discussing either profiling data or attacking data;

• the probability of a vector x with i.i.d. components x i is denoted by P(x) = i P(x i );

• we define the following sets:

1. X, T, X and T are the sets of possible values of components x, t, x and t, respectively;

2. X = X ∪ X and T = T ∪ T;

3. K is the set of all possible values for the key k.

• k and t are made of n bits (in particular, they are "bytes" when n = 8).

where α t = x α x,t . The resulting conditional probability 1 is

The Learned MIA Model

When q is small, the model cannot be profiled accurately, and P is a bad approximation of P. However, these profiled values x and t can still be useful, yet they require a more robust distinguisher.

Distinguishers that compute models using profiling have already been proposed. For example, [START_REF] Moradi | Moments-correlating DPA[END_REF] computes a correlation on moments. However, correlations analysis may be sensitive to model errors [START_REF] Veyrat-Charvillon | Mutual Information Analysis: How, When and Why? In CHES[END_REF]. Mutual Information Analysis (MIA) yields a distinguisher that can be robust when models are not perfectly known [85, Section 4], but it requires at least a vague estimation of the leakage model.

Since our function ψ is unknown, we can create a first-order model ψ with the profiled data as

The

Step function is a function that ensures the non-injectivity of the model. The simplest way to define Step is the following:

where d > 0-the greater d, the smaller the step size. This parameter d has to be small enough in order to make the model non-injective [START_REF] Gierlichs | Mutual information analysis[END_REF]Sec. 4.1]. In our case, we choose, for all our experiments, d = 1. With such a model, it is possible to compute a MIA, which successfully distinguishes the correct key.

Robust distinguishers

In this subsection, we present six distinguishers that tackle null probabilities. Some of these solutions seem quite obvious while others are deduced from the notions presented in the preceding Subsection 7.2.1.

1 We should normally have used the notation Pα instead of s Pα, but we found this too heavy and confusing;

hence the use of s Pα.

Presentation of the Simulated Model

The simulated model is built as follows:

where u i is a discrete uniformly distributed noise u i ∼ U(-σ, σ), S box is the AES substitution box function, and H w is the Hamming weight of a byte.

This very simple leakage is used to compare distinguishers in the case the attacker has no information about the model.

Remark 7.2 (Optimal Distinguisher). The optimal distinguisher (7.7) can be easily calculated if the model is perfectly known, as

where δ σ is defined such that δ σ (x) = 1 if |x| ≤ σ and 0 otherwise. In Figures 7.3, 7.4 and 7.5, we include the optimal distinguisher for reference, to show how far the other curves are from the fundamental limit of performance.

By construction, the leakage simulation (7.24) generates some traces with zero probability, but notice that there is no i such that P(x i |t i , k) = 0 for the correct key guess. This academic example is useful to compare the distinguishers defined in Section 7.2.

Attack Results

We computed the success rates (7.6) of the various attacks (namely attacks , , , andattack being less efficient than its limit ) for for σ = 24, n = 4 bits, and q ranging from small to high values.

The only difference between Figures 7.3, 7.4, and 7.5, is that we have increased the number of data during the profiling stage. When profiling is bad (Figure 7.3), the best distinguisher is the Offline-Online profiling distinguisher, while the Learned MIA Distinguisher is not as good as was expected. When q = 1 600 (Figure 7.4), all distinguishers improve. Finally, when profiling is good ( q = 4 000, Figure 7.5), the best distinguisher is now the Empty Bin distinguisher, followed by the Soft Drop distinguisher and the Offline-Online profiling.

Remark 7.3. In this very special case, we can show that the Empty Bin Distinguisher can accurately approximate the Optimal Distinguisher. Indeed, the actual probability is such that for all (x, t) ∈ X × T,

which is constant if x is in the appropriate interval. For the Empty Bin Distinguisher,

due to the leakage model. Therefore, we can predict that at least q = (2σ + 1)|Y| 1 min P(y) = 3 920 profiling traces are needed to make sure that the Empty Bin Distinguisher becomes as efficient as the Optimal Distinguisher. As profiling consists in random draws with replacement, the D EmptyBin distinguisher is found very close to the D Optimal distinguisher with q = 4 000 profiling traces.

Chapter 8

Obtain a Leakage Model with Timing Attacks This yields the exact timing of the AES execution (which is about 2 600 clock cycles in average -recall Figure 7.1 and 7.2). In a real attack, an attacker would measure a noisy timing using an external "chronometer". However, our attack models the best case for an attacker; hence, bounds the security of the analyzed implementation. In particular, we underline that our measurement methodology is fully non invasive: the timing measurement is performed in parallel to the AES computation, thereby keeping the victim circuit run at full speed, without interference. Time deviations for different configurations of Instruction Cache (IC) and Data Cache (DC) are shown in Figure 8.1. We observe a huge time difference when data cache is turned Off / On.

When DC is turned off, there is no timing leakage as AES is constant time. Yet, when DC is

Results on Real Devices

We notice that the Soft Drop Distinguisher has been established using the γ parameter defined in Equation 7.19 such that γ = 1/ q. resulting profiling is very good and one may consider that the approximation of P is tight. In this case, Soft Drop and OOP Distinguishers are both very successful, which seems natural regarding the fact that P has converged to the actual probability P. For this attack, we recall that the timing of 10 000 traces can be acquired in one second. Therefore, the attack is successfully in about 0.2 second using Soft Drop or OOP distinguishers.

As a conclusion to this study on the STM32F4 discovery board, we have learned the following comparisons between the proposed distinguishers:

• when the profiling stage is poor, the best distinguisher is the Learn MIA Distinguisher;

• when there is enough data in the profiling stage, the best distinguisher is the Soft Drop Distinguisher, closely followed by the OOP Distinguisher;

OBTAIN A LEAKAGE MODEL WITH TIMING ATTACKS

• the Empty Bin Distinguisher converges to the optimal success rate, but is not as efficient as previously in Section 7.3. This can be explained by the fact that we skip a lot of data in the computation;

• the Hard Drop Distinguisher is the slowest to converge to 100% success rate.

Remark 8.1. When comparing Figures 8.5 and 8.6, we notice that the Empty Bin distinguisher does not improve as the number of profiling traces increases. An explanation that there is no more empty bins to be filled between these two situations; then only a more precise estimation of the probability would make the difference.

Remark 8.2. As discussed in Definition 7.4, the value of γ is important. We have run the same experience as in Figure 8.5 with γ = 1 q×10 10 . The results, we obtained, are presented in Figure 8.7. When comparing this figure with Figure 8.5, we notice that the performance of the Soft Drop Distinguisher has dropped and is now much closer to that of the Empty Bin Distinguisher, as we had forecast. The second possibility is what we call Structural Empty Bins. They are present whatever the profiling under fixed key and do not depend on the number of traces q in the profiling stage. In Distinguisher does not improve that much with a better learning phase, we have computed the Mean-Square Error of these two distinguishers for the three learning phases (i.e., q ∈ {25 600, 256 000, 2 560 000}). Definition 8.1 (MSE, Bias and Variance). Let us consider a random variable X and its expectation θ = E[X]. An estimator of the random variable is noted s X. The MSE is defined as follows:

The bias of the estimator is the expectation of the difference between the estimator and the mean of the random variable:

At last, the variance of the estimator is:

From these definitions, we have the following relation between MSE, bias and variance:

The Mean-Square Error (MSE) is computed using the following method:

1. For the secret key k * , we calculate the value of the distinguisher i.e. the value of P( x| t ⊕ k * ) for the Soft Drop and I( x; ϕ( t ⊕ k * ) for the Learned MIA. We compute this value for different number of traces q. This gives an estimation of the normalized distinguisher for the correct key.

2. The most accurate estimation is obtained for the highest value of q. Therefore, taking the average over a large number of experiences for this highest value of q gives a good estimation of the Expectation of the estimator.

3. Then we calculate, for every value of q the bias and the variance of the estimator, and the Average MSE is obtained using the formula: MSE = Bias 2 + Variance.

We have plotted in Figures 8.9 and 8.10 the Average MSE for the two distinguishers. In order to be more relevant, we have plotted the logarithm of the MSE. Furthermore, we have chosen to plot the MSE separately as the distinguishers are not comparable.

The MSE for the Learned MIA Distinguisher stays almost constant with the improvement of the learning phase whereas the MSE of the Soft Drop Distinguisher is much smaller. This means that a better learning phase gives a much better estimator of the distinguisher. In chapter 3, we supposed that there was no masking in the AES protocols. Nowadays, as side-channel analysis becomes a real threat, designers have started to invent new types of security against side-channel analysis. Masking is a good way to improve the security of a chip. Indeed, the higher the order of masking is, the more difficult it is to break the security of an embedded system.

OBTAIN A LEAKAGE MODEL WITH TIMING ATTACKS

Even if the security of the chip increases, it is though possible to recover the secret key.

Nicolas Bruneau et al. mathematically proved that the best possible attack in case of masking is the maximum likelihood [START_REF] Bruneau | Masks Will Fall Off -Higher-Order Optimal Distinguishers[END_REF]. We can also cite once again Duc's paper where he showed that the order of making exponentially increases the security of a chip in the sens that the number of traces needed to recover the secret key are much higher [START_REF] Duc | Making masking security proofs concrete -or how to evaluate the security of any leaking device[END_REF]Equation (10)].

According to the leakage model of [START_REF] Bruneau | Masks Will Fall Off -Higher-Order Optimal Distinguishers[END_REF], we obtain the following framework for the communication channel. We consider that the masking order is d. In Figure A.1, the notations are the following:

• the d shares of sensitive variables are represented by Y 0 , . . . , Y d .

• N 0 , . . . , N d are the d shares of additive noise.

• The d shares of the traces are X 0 , . . . , X d .

The Markov chain with masking security, therefore becomes:

This means that Lemma 3.2 can be adapted to masking and becomes

Let a message M to be sent taken uniformly in a set M and to be sent over a block of length q. The rate of the transmission is thus R = log 2 (|M| q . Let ε > 0, there exists a code C such that the probability of error is smaller than ε as long as R < I(X; Y ) -D(P(y|x)|| P(y|x))ε.

To prove Theorem 1.1, we first show the law of great numbers for a random variable taken under another distribution.

Lemma 1.1. Let X a random i.i.d. vector of size q following the distribution P and P another distribution taking its values in the same set as X. Then, we have:

This is a convergence in probability.

Proof for Lemma 1.1. We use the Bienaymé-Chebychev inequality to show the convergence. Let ε > 0, we know that:

Therefore, we have:

As this is true for any ε > 0, this proves the lemma.

We have now shown that the law of great numbers leads to a value which is H(X) + D(P|| P).

In order to prove the Channel-Coding Theorem, C.E Shannon defined subsets of X q × Y q called typical sets. All the definitions of the typical sets, and their properties may be found in [START_REF] Cover | Elements of Information Theory[END_REF]Chapter 7]. We define here typical sets related to the estimation P of a random variable.

Definition 1.1 (Typical set related to P). Let X a random i.i.d. vector of size q following the distribution P and P the estimation of this distribution. Let ε > 0. The typical set related to P is defined as:

For two random vectors X and Y, we can also define the joint typical set.

Definition 1.2 (Joint Typical set related to P). Let X and Y two i.i.d. random vectors of length q each. (X, Y) follows the distribution P XY and the estimation is P XY . The marginal distribution of X is P X and the marginal distribution of Y is P Y . Let ε > 0. The joint typical set related to P is noted A ε

if and only if the three conditions below are verified:

In [START_REF] Cover | Elements of Information Theory[END_REF], Cover and Thomas prove that the joint typical set has several very interesting properties. Here, with the joint typical set related to P, we adapt these properties so they can fit with the estimation.

Lemma 1.2 (Properties of the joint typical set related to P). Let (X, Y) a random vector of length q drawn i.i.d. according to P XY and estimated by P XY . Let ε > 0. We have:

3. For X, Y two independent random vectors such that X ∼ P X and Y ∼ P Y the marginals of P XY , we have:

The last property of the Lemma 1.2 seems quite heavy with the number of divergences.

However, in our case, we suppose that the attacker knows the distribution of Y, meaning that D(P y || P Y ) = 0. Furthermore, we have the relation between D(P X || P X ) and D(P XY || P XY ):

Proof of Lemma 1.2. We prove each term of the lemma one by one. Let ε > 0.

1. By the law of large numbers we know that there exist n 1 , n 2 , n 3 such that:

Taking n = max{n 1 , n 2 , n 3 }, and the union of the three probabilities, we obtain, for every q ≥ n:

This proves the first part of the lemma.

Let ε > 0. According to Lemma 1.2, we know that there exists q large enough such that P(B c 1 ) ≤ ε. Moreover, for B i with i = 1, the probabilities are independent. Therefore, we have, according to Lemma 1.2 we have: P(B i ) ≤ 2 -n(I(X;Y )-D(P Y |X || P Y |X )-3ε) Therefore, we have, for ε > 0 and q sufficiently large:

) is equal to the Perceived information metric proposed by François-Xavier Standeart in [START_REF] Durvaux | How to Certify the Leakage of a Chip?[END_REF]. This means that, in a side-channel context, if the perceived information if positive, it is possible to recover the secret key of the device.

However, we are not able to tell how fast the key recovery will be with this approach since this calculation only shows the achievability o fa coding rate.

A.6.2 Discussion About Merhav's Paper

In 1994, Merhav et al. published an article dealing with mismatch decoding in information theory. When the decoding is performed with a maximum likelihood distinguisher based on an estimation of the distribution P instead of P, the article show that the the maximum achievable rate of transmission exists and can be calculated. Moreover, if the coding rate is higher than this limit, the probability of error tends towards 1. In side-channel analysis, to result does not tell how fast the probability of success of the attack P s will converge to 1.

Appendix about the Monobit Leakages

B.2 Proof of Lemma 5.4

There are several ways to express g(σ). For example, we have:

This expression can be reduced to:

where X ∼ N(0, 1). By the dominated convergence theorem (tanh 2 ( X σ + 1 σ 2 ) is always smaller than 1) when σ → 0, we obtain g(0) = 1 and when σ → ∞ we obtain the equivalent 1 σ 2 .

B.2 Proof of Lemma 5.4

The success exponent is defined by

where in our case

First for large q we can consider that

Secondly we have

To remove the absolute values, we distinguish two cases whether the sum is positive or negative.

We consider that q is large enough to have strictly positive or negative values.

To calculate the variance, we consider that x = 0 as it is the value that maximizes the expectation of the distinguisher.

The computation of this variance gives:

Overall, the success exponent is:

B.4 Proof of Lemma 5.6

For MIA, we refer to [START_REF] Sylvain Guilley | A Key to Success -Success Exponents for Side-Channel Distinguishers[END_REF]Section 5.3] for the theoretical justifications. In order to obtain a simple closed-form expression of the success exponent, we suppose that σ 1 and that the probability density functions are all Gaussian. This means that X|Y (k) is a Gaussian random variable of standard deviation 4κ(k)(1κ(k)) + σ 2 . Moreover, we will keep only the first order approximation in SNR = σ -2 of the SE.

The Fisher information of a Gaussian random variable of standard deviation ζ is equal to 1 ζ 2 . Therefore the Fisher information of X knowing Y = y(k) is:

As this value does not depend on the value of Y (k), we have:

Last, we have to calculate Var(-log 2 p(X|Y

the normalization constant. We have: