Mme M Michel Agoyan

Mme Svetla Nikova

Elisabeth Oswald

M Emmanuel Prouff

M Olivier Rioul

M François-

Xavier Standaert

M Yannick Teglia

et à la participation de nombreuses personnes, celle ci ne fait pas exception.

Les caractéristiques de ces "distingueurs" peuvent varier en fonctions des différents prérequis nécessaires à leurs calculs ou encore des fuites à exploiter.

Contre-mesures contre les attaques par canaux auxiliaires. Afin de protéger les implémentations cryptographiques contre les attaques par canaux auxiliaires différentes contre-mesures ont été développées. Les contre-mesures les plus utilisées sont les schémas de masquage. En effet, leur sécurité peut être formellement prouvée. Dans ces schémas chacune des variables sensibles Z est "découpée" en Ω parties dans le cas d'un schéma d'ordre Ω -1 en utilisant Ω nombres aléatoires appelés les masques. Les implémentations cryptographiques peuvent être également protégées en utilisant une contre-mesure appelée "shuffling". Cette contre-mesure consiste à x exécuter dans un ordre aléatoire les différentes opérations indépendantes d'un algorithme. Ces contre-mesures sont elles mêmes la cible d'un type particulier d'attaques par canaux auxiliaires appelé attaques d'ordre élevé. Ces attaques reposent sur la combinaison de différents points de fuites dépendant de différentes variables.

Il convient donc dans l'optique de construire des attaques efficaces voir optimales de prendre en compte différents points de fuite. Dans ce manuscrit nous montrons comment exploiter ces multiples fuites que ce soit dans le cas d'attaque contre des implémentations non protégées ou dans le cas d'implémentations protégées.

Chapitre 2 Réduction de dimensionnalité optimal.

Réduire la dimensionnalité des mesures est un problème important dans les analyses par canaux auxiliaires.

En effet les fuites exploitables sont souvent multi-dimensionnelles il y a donc en général un intérêt à réduire leur dimension afin de réduire la masse de données à traiter lors des attaques. De manière générale cela permet des capturer les fuites multi-dimensionnelles en un seul échantillon compressé, et donc de réduire la complexité calculatoire. Le revers de la médaille est que de telles méthodes peuvent réduire l'efficacité des attaques en termes de probabilité de succès. En effet la question se pose de savoir quel est l'impact de la réduction de dimensionnalité en termes d'information exploitable dans les attaques et par conséquent en terme de probabilité de succès.

Dans ce chapitre nous analysons mathématiquement la réduction de dimensionnalité. Nous montrons que l'attaque optimale reste optimale après une première passe de prétraitement qui prend la forme d'une projection linéaire des échantillons. C'est à dire que la réduction de dimensionnalité peut se faire sans perte d'information. Nous étudions l'état de l'art des méthodes de réduction de dimensionnalité et trouvons que asymptotiquement, la stratégie optimale coïncide avec l'analyse discriminante linéaire. Nous prouvons également qu'en général l'analyse en composantes principales ne coïncide pas avec la réduction de dimensionnalité optimale.

Chapitre 3 Réduction de dimensionnalité dans le cas du masquage.

Les attaques multivariées permettent « d'attaquer » les schémas de masquage d'ordre élevé en combinant plusieurs points de fuites. Mais dès lors la question se pose de savoir quelle est la xi meilleur façon d'extraire l'information répartie dans tous les Ω-uplets de points. Dans ce chapitre nous proposons l'outil de pré-traitement qui répond à cette question. Nous montrons d'abord qu'il est équivalent de résoudre le problème de la maximisation du coefficient des attaques par corrélation notées CPA d'ordre élevé et le problème de maximisation de la covariance. Nous pouvons alors, dans un premier temps, appliquer cette équivalence au problème de réduction de dimensionnalité des traces par combinaisons linéaires, les pondérations de cette combinaison sont notées par le vecteur α. Cela nous permet ensuite de lier ce problème avec l'Analyse en Composante Principale notée PCA. Dans un second temps nous présentons la solution optimale au problème de maximisation de la covariance comme présentée en Figure 2.

Nous montrons ensuite théoriquement que ces deux méthodes donnent des résultats équivalents lorsque les traces attaquées sont « modulées ». Nous comparons théoriquement et empiriquement ces méthodes.

Pour finir nous appliquons ces résultats sur les traces du DPA Contest V4 afin d'évaluer combien les techniques proposées améliorent les attaques du second ordre.

Comme nous pouvons le voir sur la Figure 3 les attaques construites sur une étape de réduction de dimensionnalité ont de meilleurs résultats. De plus nous remarquons que les deux méthodes de réduction de dimensionnalité c'est à dire l'analyse en composantes principales et la méthode de covariance donnent des résultats identiques. Ceci prouve que les traces du DPA Contest V4 sont proches de traces modulées.

Chapitre 4 Attaque Optimale contre le recalcul de table.

Les parties non linéaires des schémas de masquage sont souvent construites en utilisant des méthodes de recalcul de table. De tels algorithmes sont caractérisés par leurs nombreuses fuites pouvant être exploitées afin de réaliser des attaques par canaux auxiliaires. Par conséquent différentes attaques ont été proposées dans l'état de l'art afin d'exploiter ces fuites. Dans ce chapitre nous étudions de façon théorique la méthode optimale, au sens de la méthode maximisant la probabilité de succès, exploitant ces multiples fuites.

Nous montrons en particulier que l'attaque optimale, notée OPT surpasse en terme de probabilité de succès les différentes attaques de l'état de l'art. En effet nous pouvons voir en Figure 4 que les attaques multi-variées exploitant le recalcul de table sont plus efficaces (ont une meilleure probabilité de succès) que les attaques exploitant uniquement les fuites hors de l'étape de recalcul, comme par exemple l'attaque en corrélation du second ordre notée 2O-CPA. Projection by linear combination

(1') max k,d∈ 1,D 1 × 1,D 2 max k ρ(α • X; Ψ(Z)) (0') (1') α • X (scalar)
ρ(X (d) ; Ψ(Z))

D 1 D 2 (1)
(2)

d 1 d 2 1 1 d 1 d 2 d 2 d 1 ( 2

')

Figure 2: Presentation de la « méthode de covariance » . L' attaque 2O-CPA calcule la corrélation pour chaque paire (d1, d2) de la fuite (étape (1)), ensuite le maximum sur chacune des clefs et des instants temporels est recherché (étape (2)). Notre méthode obtient un « vecteur de covariance » sur un composant d'apprentissage (étape (0')), et ensuite projette la fuite X sur α (étape (1')), avant de chercher la meilleure clef lors de la maximisation du distingueur. Remarquons que le modèle Ψ(Z) dépend implicitement de l'hypothèse de clef k.

Cela montre qu'il y a toujours un intérêt à augmenter le nombre de points de fuites exploités pour les attaques, dans la mesure où ceux ci sont exploités de façon optimale.

De plus l'utilisation du distingueur optimal contre des schémas de masquage avec recalcul de table permet également d'améliorer le résultat des attaques exploitant les fuites du recalcul de table en plus des fuites classiques de l'algorithme cryptographique. En effet nous montrons que les attaques de l'état de l'art exploitant les fuites du recalcul en deux étapes, une première pour retrouver le masque, la seconde pour retrouver la valeur secrète ne sont pas aussi efficaces, comme illustré en Les schémas de masquage basés sur le recalcul de table sont des contre-mesures classiques contre les analyses par canaux auxiliaires d'ordre élevé. Néanmoins ils sont connus pour être attaquables à l'ordre Ω dans le cas où le masquage utilise Ω parties. Dans ce chapitre nous montrons mathématiquement qu'une attaque d'ordre strictement plus grand que Ω peut être plus efficace qu'une attaque d'ordre Ω. Pour se faire nous étendons l'idée de Tunstall, Whitnall et Oswald de FSE 2013: en effet nous montrons des attaques utilisant les multiples fuites liées à un masque durant le recalcul de table. En particulier dans le cas d'une implémentation d'un recalcul de table effectué dans un ordre aléatoire, nous montrons qu'il existe une fenêtre d'opportunité en termes de variance de bruit, dans laquelle une nouvelle attaque multivariée du troisième ordre est plus efficace que la classique attaque bi-variée du second ordre. L'attaque présentée dans ce cas d'étude utilise, à son avantage, les multiples fuites des différentes variables lors du recalcul de table. En effet nous montrons dans ce cas là qu'il est possible d'extraire du recalcul une variable dépendante du masque. Cette nouvelle variable, issue donc de la combinaison des différentes variables du recalcul, est elle même combinée à la variable secrète. C'est cette combinaison finale qui permet de retrouver la valeur de la variable secrète. intervalle particulier que nous appelons intervalle de variance utile.

Afin de comparer les résultats de cette nouvelle attaque à ceux de l'état de l'art et de vérifier de façon empirique nos résultats théoriques, différentes simulations ont été effectuées. Pour chacune nous avons supposé que les variables fuitaient leur poids de Hamming, nous avons de plus supposé un bruit blanc gaussien. L'attaque de référence utilisée est l'attaque du second ordre par corrélation notée 2O-CPA. Nous pouvons dans un premier temps observer en Figure 5 qu'aux bornes de l'interval de variance utile la 2O-CPA et notre nouvelle attaque MVA T R coïncident, ce qui valide nos résultats théoriques. Dans un deuxième temps nous pouvons observer en Figure 6 qu'entre ces bornes l'attaque MVA T R montre de meilleurs résultats. En effet, son taux de succès est plus élevé que la 2O-CPA. Cette nouvelle attaque notée MVA Ω CS va dépendre de l'ordre utilisé par le masquage de Coron. Comme précédemment nous avons évalué ces résultats théoriques en utilisant des simulations.

Nous supposons toujours que les variables fuitent en poids de Hamming avec un bruit blanc gaussien. On peut remarquer sur la Figure 7 que non seulement l'attaque MVA Ω CS surpasse l'attaque de référence qu'est l'attaque par corrélation d'ordre élevé notée ici ΩO-CPA, mais que cet avantage augmente avec l'ordre du schéma de masquage.

Dans ce chapitre nous étudions également le cas de différents modèles de fuite de degré un et montrons formellement que le modèle en poids de Hamming est le cas le moins favorable à l'attaquant. Nous montrons en effet que lorsque le modèle de fuite est une pondération des bits de la valeur sensible, le meilleur cas pour notre nouvelle attaque multivariée est lorsque tout les bits sont à zéro sauf un, inversement le pire cas est lorsque la pondération est la même pour tout les bits. Ainsi, l'ensemble des analyses effectuées précédemment en poids de Hamming sont une borne inférieure des résultats que nous pouvons obtenir avec l'attaque MVA T R . Dans ce chapitre nous approximons le distingueur d'une attaque "Template" basée sur le maximum de vraisemblance en attaques de degrés inférieurs. En exploitant cette décomposition nous montrons qu'il est possible de construire des attaques hautement multivariées qui restent efficaces quand la vraisemblance ne peut pas être calculée du faite de sa complexité. Un algorithme basé sur un recalcul de table aléatoire est utilisé comme illustration pour construire une nouvelle attaque qui surpasse les attaques de l'état de l'art. Cette nouvelle attaque combine deux degrés d'attaque et est capable d'exploiter des fuites multi-dimensionnelles ce qui explique son efficacité.

Le maximum de vraisemblance est le distingueur qui maximise la probabilité de succès.

En ce sens nous le considérons donc comme le distingueur optimal. Cette vient néanmoins avec une complexité calculatoire importante. En effet, dans le cas d'une attaque contre une implémentation masquée et calculée dans un ordre aléatoire (« shufflée »), cette complexité dépends de différents paramètres dont le factoriel de la taille des permutations utilisées pour construire l'ordre aléatoire. Cette valeur peut être extrêmement importante quand la taille des permutations augmente. Dans ce cas du fait de sa complexité le distingueur optimal ne peut être calculé. Dès lors il convient de trouver une alternative au maximum de vraisemblance dans ces cas. L'idée de notre approche est d'utiliser les premier termes de la décomposition du distingueur xviii optimal en sa série de Taylor. Nous définissons par ROPT L cette nouvelle attaque exploitant les L premiers termes de la série de Taylor. Notre approche basée sur l'approximation de Taylor va être efficace d'un point de vue calculatoire (réduction de la complexité) mais reste également efficace du point de vue du nombre de traces nécessaires pour construire les attaques.

Nous prenons comme exemple pour illustrer cette nouvelle attaque le cas de d'une implémentation d'un schéma masquage avec recalcul de table dans lequel le recalcul de table est effectué dans un ordre aléatoire. Le gain en termes d'efficacité calculatoire comparé au distingueur optimal est évident puisque cette attaque est calculable ce qui n'était pas le cas du distingueur optimal. Afin d'évaluer son efficacité en terme de nombre de traces nécessaires pour effectuer les attaques nous avons utilisé des simulations. Nous supposons ici un modèle de fuite en poids de Hamming. Nous appliquons une attaque en utilisant les trois premiers termes de la série de Taylor. En effet, nous savons grâce au chapitre précédent qu'une attaque d'ordre trois est efficace. Pour comparer notre attaque aux attaques antérieures nous choisissons comme attaques de référence l'attaque 2O-CPA et l'attaque MVA T R . Nous remarquons que pour les faibles bruits comme par exemple pour un bruit d'écart type σ = 1 (Figure 9a) que l'attaque ROPT 3 est proche de l'attaque MVA T R . Cela veut dire que le terme dominant dans la série de Taylor est le terme de degré trois. Inversement lorsque le bruit est élevé σ = 13 (Figure 9d) l'attaque

Introduction to the cryptography

Cryptography aims at ensuring the security of the communications between several parties.

Historically mainly used for military or diplomatic purposes, it has seen its uses exponentially grow up with the development of the communication technologies.

To ensure the security, cryptographic tools (primitives) provide one or more of the following properties:

Confidentiality. This property guarantees that the information transmitted during the communication will be only intelligible by authorized parties. The confidentiality of data will be

INTRODUCTION

obtained by encryption schemes. Such schemes transform an initial message called the plain-text to an unreadable, for any unauthorized party, message called the cipher-text. This transformation process is called the encryption. The algorithms which perform the revers process are called decryption algorithms. This process is called decryption.

Data integrity. This property guarantees that the data have not been modified by a malicious party. To ensure the Data integrity a hash function may be used. A hash function can be roughly defined as a one way mapping from a string of arbitrary length to a binary string of fixed length. The security of such schemes depends on the difficulty to find two binary strings with the same output. Then the data integrity is constructed as follows: first the hash value of some data is initially computed. To verify that the data have not been altered the hash value of these data is computed and compared to the original one. Noticed that the integrity of the hash value has to be ensured in some manners.

Authentication. This property can be applied both on data and parties. The entity authentication ensures that the communication is made between the expected parties. The data authentication could ensure the origin of the message, the emission date of the message. The Authentication is often provided by digital signature schemes. A digital signature depends on, a secret only known by the signer and the message. Exploiting this secret the signer is the only one able to generate the digital signature. Then anyone else should be able to verify if this number has been generated by the signer, in general a digital signature is provided with a public value to allow the verification.

Non repudiation. This property ensures that parties will not deny actions or commitments.

This property can also be ensured by digital signature schemes.

Regarding these properties different kinds of primitive have been developed.

Symmetric Cryptography

The symmetric cryptography also called secret key cryptography is based on the fact that all the parties involved in the communication share the same secret (unknown by anyone else) called the secret key. In a symmetric key primitive only one key is involved and as a consequence the encryption and decryption algorithms take as input the same key. Symmetric encryption schemes ensure the confidentiality of the data. Block cipher algorithms are often used in symmetric cryptography. Formally the block ciphers can be defined as functions which take as input Notice that for any key and for any block cipher, the block cipher restricted to this key is a bijection. In a classical usage the secret key is randomly generated and shared between the two parties and the security will depend on the secrecy of the key. Several block ciphers have been proposed, non exhaustively we can cite: Rijndael [START_REF]AES Proposal: Rijndael (now FIPS PUB 197)[END_REF], Serpent [START_REF] Biham | Serpent: A new block cipher proposal[END_REF], Twofish [START_REF] Schneier | The Twofish Encryption Algorithm: A 128-bit Block Cipher[END_REF], RC6 Advance Encryption Standard [START_REF]AES Proposal: Rijndael (now FIPS PUB 197)[END_REF]. In order to replace the DES, the NIST lunched in In modern block ciphers the security against statistical attacks is provided by two main properties the confusion and the diffusion (151).

Diffusion. The diffusion property hides the relationship between the plain-text and the ciphertext. In general this property is implemented using permutations. The diffusion will impress on each output bit information provided by each input bit. Generally the diffusion property

INTRODUCTION

comes from manipulations of the order of bits and is provided in the AES by the ShiftRows and

MixColumns.

Confusion. The confusion property hides the relationship between the cipher-text and the secret key. The confusion property ensures that each bit of the cipher-text is related to the secret key by a complex function. In general this property is implemented using substitutions.

The confusion comes from non linear operations provided by the SubBytes in the AES. The operations providing the confusion are often the target of the side-channel analysis. Indeed the substitutions often manipulated several bits of the key in one operation.

As the length of data may be higher than the plain-text length different mechanisms can be used to encrypt data using a block cipher. In these cases the way the block cipher are used on the different parts is called the cipher mode (see [START_REF] Menezes | Handbook of Applied Cryptography[END_REF] for details).

The Electronic CodeBook (ECB) mode. In this mode the whole text to cipher is split into words which have as size the input size of the block cipher. Then each word is ciphered with the same key.

The Cipher-Block Chaining (CBC) mode. Similarly to the ECB mode the text is split into words. The first word is xored with an Initialization Vector (IV) and the result of this xor is ciphered. The other words are proceed in an iterative process where the i-th word is xored with the result of the (i -1)-th step.

These two modes are often used in practice nevertheless other modes exist such as the CBC with counter (CBCC), the Cipher FeedBAck (CFB), the Output FeedBack (OFB), the counter mode (CTR), the counter based CTR (CTRC)...

As no random IV is used in the ECB mode this mode is often the one used to perform side-channel analysis.

Asymmetric Cryptography

At the opposite of the symmetric cryptography in asymmetric cryptography, also called public cryptography, a public key, derived from a secret key, only known by one party, is shared to other parties. It is this asymmetry in the information held by the different parties which gives the name of asymmetric cryptography. Asymmetric cryptography provides two kinds of primitive ensuring the confidentiality (asymmetric encryption) and the data integrity (digital signature). While symmetric schemes are based on a sequence of substitutions and permutations the asymmetric On the other hand the problem can be easily solved knowing extra-information.

Diffie and Hellman key exchange

One of the main drawback of symmetric primitives is that an a priori shared secret is needed.

In order to allow secure communications without this shared secret Diffie and Hellman have presented in [START_REF] Diffie | New Directions in Cryptography[END_REF] Definition 3 (RSA Problem). Given a positive integer n that is a product of two distinct odd primes p and q, a positive integer e such that gcd e (p -1) (q -1) = 1 , and an integer c find a m such that m e ≡ c mod n.

Definition 4 (Factoring Problem). Given a positive integer n find its prime factorization; that is written n = p e1 1 p e2 2 ...p e k k where the p i are pairwise distinct primes and e i ≥ 1. These implementations are vulnerable to particular attacks the so called Physical Attacks.

Such attacks exploit the interaction of the DUT with its environment.

Physical Attacks can be decomposed into two main categories [START_REF] Mangard | Power Analysis Attacks: Revealing the Secrets of Smart Cards[END_REF]. theirs electromagnetic emanations [START_REF] Gandolfi | Electromagnetic Analysis: Concrete Results[END_REF][START_REF] Quisquater | ElectroMagnetic Analysis (EMA): Measures and Counter-Measures for Smard Cards[END_REF], the duration of the algorithm (84) but also more exotic ones such as the acoustic emanations, optical emanations or even the heat.

Following this first characterization of Physical Attacks another complementary decomposition is possible. An attack is defined as

• Semi-invasive when the attacker can modify the external package of the DUT but does not modify the internal structure.

• Invasive when it needs permanent modifications of the DUT.

• Non invasive when the attacker only observes the physical emanation generated by the

DUT.

Depending on the context (mostly the way to inject fault) Fault Attack can be Semi-invasive active attacks or Invasive active attacks. The rest of this manuscript deals with SCA which in this nomenclature are Non-invasive passive or Semi-invasive passive attacks when the package is removed in order to help the attack.

INTRODUCTION

Side Channel Attacks

A first example of SCA was provided by the program TEMPEST led by the US government to study the possible compromising emanations. One of the first scientific presentation about SCA is due to Kocher in [START_REF] Paul | Timing attacks on implementations of diffie-hellman, rsa, dss, and other systems[END_REF] in which an attacker is able to recover sensitive data by exploiting the time of execution of asymmetric cryptographic algorithms such as Diffie-Hellman [START_REF] Diffie | New Directions in Cryptography[END_REF] and RSA [START_REF] Rivest | A Method for Obtaining Digital Signatures and Public-Key Cryptosystems[END_REF].

The first paper dealing with the exploitation of power consumption is due to Kocher et al.

and published in (83).

The general setup for building SCA works as follows. An attacker will run a cryptographic algorithm one time or more with different inputs. During these executions the attacker acquires (e.g. using an oscilloscope) the physical leakages he targets. Such acquisitions are often called traces or measurements. Exploiting these measurements he can directly recover the key in Simple Power Analysis (84) (SPA). In other approaches (83) the attacker extracts the value of the secret key by comparing a set of measurements and a guessed value called the prediction model using a statistical tool the distinguisher. Since the first publications about SCA many different distinguishers have been proposed. There is an incentive to choose the optimal distinguisher.

This "optimality" depends on a value to maximize. In practice it is often the probability of success.

The distinguishers are ones of the core tools of SCA. They allow to compare the measurements and the prediction model. Thus the secret key is recovered based on this comparison. Through the literature many different distinguishers have been presented. A Side Channel Attack can be seen as the overall process which allows to recover the secret key based on physical measurements.

This exploitation often uses measurements assuming a specific leakage and using a particular distinguisher.

Notations

General notations

In this thesis uppercase letters are used for random variables (e.g. U ) and the corresponding lowercase letters for their realizations (e.g. u), calligraphic capital letters denote sets (e.g. U).

Bold symbols are used to denote vectors that have length Q, the number of measurements.

The empirical mean (resp the empirical standard deviation) of a vector u is denoted by u (resp.

( σ u )).

Side Channel Attacks

Namely, X denotes a set of Q random variables i.i.d. with the same law as X. X represents a leakage measurement. So, X is a Q × D matrix which represents a set of Q measurements (also named the queries) each measurement being of length D i.e. composed of D leakage samples.

Some cryptographic algorithms involve random values. R denotes a set of random variables i.i.d. with the same law as R which represents this value. t denotes the set of input-texts of the measurements X with t ∈ T where T is the set of possible input-texts. Let k be the secret key. k ∈ K where K is the set of the possible keys. In this manuscript we suppose that the computations are done on n-bit words which means that these words can be seen as elements of

F n 2 .
As a consequence both k and t belong to F n 2 . Notations X q and X (d) are used to denote the d-th column and the q-th line of the matrix X, respectively. Definition 6 (Sensitive variable). A sensitive variable is an internal variable proceeded by the cryptographic algorithm which depends on a subset of the inputs not known by the attacker (e.g. the secret key but also the secret random value).

Definition 7 (Selection Function). Let g be a mapping which maps the input data to a sensitive variable. This function is called selection function.

g : F n 2 × F n 2 × R -→ (F n 2 ) D k , T, R -→ g (k , T, R) .
(1.1)

Definition 8 (Leakage Function). The way that the sensitive values leak in the measurements depends on a leakage function that is a specific characteristic of the target device:

Ψ : (F n 2 ) D -→ R D V -→ Ψ (V ) . (1.2)
Based on this definition a measured leakage is modeled by:

X = Ψ (g (k , T, R)) + N, (1.3)
where the random variable N denotes an independent additive noise. This noise is assumed to be independent between each measurement.

The function g depends on the algorithm while the function Ψ is a characteristic of the device. The function Ψ is in general not known by the attacker. As a consequence in order to perform SCA an attacker will often has to make a prediction on the unknown leakage function by selecting a specific leakage model. Let denote by Ψ this leakage model Ψ :

(F n 2 ) D → R D .

INTRODUCTION

In order to simplify our notations we introduce the function y = Ψ • g, where • denotes the composition law. Additionally we introduce the following notations for the prediction model :

Y = y (k , T, R) = Ψ (g (k , T, R)) , (1.4)
Y k = y (k, T, R) = Ψ (g (k, T, R)) . (1.5)
The prediction model denotes the association of a leakage model and a key guess k and gives an estimation of a possible values for the leakages. The key index will often be removed where there is no ambiguity.

Depending on the DUT the attacker can used some classical leakage models.

In software implementations the Hamming weight is often used. The Hamming weight (HW) is simply the sum of the bits and is given by:

HW : F n 2 -→ R g (k , T, R) (d) -→ b≤n g (k , T, R) (d) b , (1.6)
where

[•] b : F n 2 -→ F 2 is the projection onto th b-th bit.
A more precise model is to assume weights on each value of the bit decomposition. Let us denote by WHW (for weighted Hamming Weight) this kind of functions which take as input a vector of weight α:

WHW : R × F n 2 -→ R α, g (k , T, R) (d) -→ b≤n α b g (k , T, R) (d) b
.

(1.7)

In a hardware implementation the classical model prediction is the Hamming Distance HD which is simply the HW of the Exclusive Or (XOR) of internal values.

Leakages descriptions

The SCA are closely linked to the measurements they exploit. In this section we present an overview of possible kinds of measurements. As already mentioned SCA exploit the additional information which can leak during the execution of the cipher through a side channel. In order to exploit the physical emanations the attacker acquired them using an acquisition chain. The chain represents all the tools which transform the physical leakages into the digital data which are exploited by the attackers.

Side Channel Attacks

Example 1 (DPA contest V4 (169) acquisition chain). An example of an acquisition chain for ElectroMagnetic emanation (EM) acquisitions can be as follows: the EM are acquired using an EM near-field probe, then the signal is increased using a Preamplifier and finally digitalized using an oscilloscope.

After the step of digitalization each measurement can be seen as a vector where the components are the leakage samples.

The shape of the measurements will differ from an acquisition setup to another. They will also differ depending on the target. Indeed the measurements acquired from a hardware coprocessor may often be "smaller" and "noisier" than measurements acquired from a software implementation executed on smart-card. Indeed the length of software measurements can exceed the million of points whereas the hardware may not exceed thousands. Nevertheless in both cases the number of possible exploitable samples may be small compared to the size of the measurements.

The leakage function may vary from an experiment to another. Indeed it can be efficiently modeled by a modulation of a leakage model.

Definition 9 (Modulated Traces).

Let us now define a modulated trace as a trace in which each time sample can be expressed as a modulation of a model (static in time) plus an independent noisy part:

X = β (d) Ψ(g(k , T, R)) + N (d) d≤D = β • Ψ(g(k , T, R)) + N (d) d≤D , (1.8)
where β is a vector in R D and each N (d) is drawn from an independent identical distribution N.

In specific, the variance of the noise does not depend on the time sample d ≤ D.

This notion is illustrated in Fig. 1.1.

Of course in other cases the same model does not appear in several time samples. Indeed the leakages may be impacted by many external factors such the activation of external peripheral which is typically the case on System on Chip (SOC). The values manipulated during the execution of the algorithm may be also manipulated by different combinational logic parts which have specific leakage functions.

Distinguisher

As already mentioned a common way to perform SCA is to compare a prediction model and the measurements. In these cases distinguishers are used. The different distinguishers can be divided into categories depending on the a priori knowledge they required. Nevertheless in some cases direct exploitations of the measurements are possible. In some cryptographic implementations the operations proceeded depend on the value of the key. In these cases a "simple" observation of the side channel can allow to recover the key. These attacks called Simple Side Channel Analysis (SSCA) can reveal directly the entire key. A first example of such attacks has been presented by Kocher in [START_REF] Paul | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF]. In this attack the attacker takes advantage of the non constant time execution of operations of the algorithm.

INTRODUCTION

Simple Power Analysis (SPA) will exploit the dependencies between the secret key and the power leakages. An example was proposed by Coron (38) where an attacker exploits the fact that a point addition is performed only if the current bit is one. As a consequence by identifying the sequence of points addition and points doubling the attacker is able to recover the scalar.

Profiled attacks

The profiled attacks assume a powerful attacker which has a full control of a clone device of the DUT often called open sample. Exploiting this clone device the attacker is able to build an accurate estimation of the leakage function. These attacks are generally multivariate (D > 1)

and are seen as the most powerful kind of attacks. To do so profiled attacks are computed into two steps:

• profiling phase: during this phase the attacker uses his clone device to estimate the leakage function. In order to estimate this function he generally needs the knowledge of k and the ability to change it. It is in generally not possible on commercial devices.

Side Channel Attacks

• attack phase: during the attack phase the attacker exploits the knowledge of the leakage function to build a powerful attack to recover the secret key k .

A first example of Profiled attack the so called template attacks has been given by Chari et al. in [START_REF] Chari | Template Attacks[END_REF]. They are known to be the most powerful attacks in an information theoretic sense;

in the context of side-channel analysis, this means that they minimize the error probability, that is they maximize the probability of success (provided templates are estimated without error).

They consist in estimating the likelihood for a key guess. In the learning phase the probability density function p (X|T, K ) of the leakages X knowing T and K is computed. Then in the attack phase using the Bayes' theorem the likelihood is computed. In the original publication the noise N is assumed to be Gaussian, and as a consequence p (X|T, K ) is the density of a Gaussian distribution.

Following this first example of Profiled Attacks several other Profiled Attacks have been proposed [START_REF] Heuser | Intelligent Machine Homicide -Breaking Cryptographic Devices Using Support Vector Machines[END_REF][START_REF] Hospodar | Machine learning in side-channel analysis: a first study[END_REF][START_REF] Lerman | Template attacks vs. machine learning revisited (and the curse of dimensionality in side-channel analysis)[END_REF][START_REF] Schindler | A Stochastic Model for Differential Side Channel Cryptanalysis[END_REF].

Recently the optimal distinguisher has been presented depending on the knowledge of the attacker about the leakage function [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF]. When the attacker has a full knowledge of the leakage function the optimal distinguisher is the Maximum Likelihood (ML) of a Template attacks scenario.

Definition 10 (Maximum Likelihood Attacks ML). When the leakage function Ψ is known the optimal distinguisher is given by:

ML : F n 2 × R D×Q → F n 2 y, x → argmax k∈K Q q=1 p N (x q -y q ) , (1.9)
where p N is the density function of the noise, and where y q is the qth realization of the prediction model Y k (Eqn. (1.5)).

Non profiled Attacks

The non profiled attacks scenario assumes a less powerful attacker. Such attacks are generally univariate D = 1 and take into account all the leakage samples independently (i.e. the distinguisher is applied successively on each leakage sample). These attacks are generally applied on a set of traces and are often called differential attacks.

The first distinguisher which has been presented is the difference of mean used in the mono-bit DPA. The data set is split into two with respect to one bit of the result of the selection function. The key is recovered by taking the argmax of the distance between the mean of these two sets.

INTRODUCTION

Definition 11 (Differential Power Analysis (DPA)). The DPA attacking the b th bit is :

DPA : F 2 × F n 2 × R Q → F n 2 b, t, x → argmax k∈K Q q=1 xq×1 {[ g(k ,tq ,R)] b =1 } Q q=1 1 {[ g(k ,tq ,R)] b =1 } - Q q=1 xq×1 {[ g(k ,tq ,R)] b =1 } Q q=0 1 {[ g(k ,tq ,R)] b =0 } . (1.10)
Extended version of this attack has been proposed in order to take into account several bits [START_REF] Bevan | Ways to Enhance Differential Power Analysis[END_REF][START_REF] Messerges | Power Analysis Attacks and Countermeasures for Cryptographic Algorithms[END_REF].

CPA : F n 2 × R Q → F n 2 y, x → argmax k∈K ρ [x, y] , (1.11)
where ρ denotes the estimator of the Pearson Correlation Coefficient.

A classical model prediction for the CPA is the HW, or the HD. Nevertheless if the actual leakage function is different and close to WHW, the results of the CPA decrease.

As a consequence new distinguishers have been proposed to take into account this kind of leakage functions.

The Linear Regression Analysis (95) (LRA) uses the coefficient of determination as distinguisher. In this attack the weights which impact each bit of the sensitive value are recovered using a Liner Regression approach. The sketch of this attack is as follows, an attacker makes an estimation of the coefficients α for each key hypothesis k let us denote by α these estimated weights. These estimated weights are taken such that they minimize the euclidean distance.

Finally the good key is the one maximizing the coefficient of determination.

Definition 13 (Linear Regression Analysis (LRA)). The LRA using the coefficient of determination as distinguisher is given by:

LRA : F n 2 × R Q → F n 2 t, x → argmax k∈K 1 -x-y• α 2 x-x 2 ,
(1.12)

where y denotes the Q × n + 1 matrix which represents the bit decomposition of the sensitive variables (with a constant term), and α = (y t • y) -1 • y • x.

Samples Selection and Dimensionality Reduction

Many other distinguishers have been presented depending on a partition variance as distinguisher [START_REF] Batina | Differential Cluster Analysis[END_REF][START_REF] Standaert | Partition vs. Comparison Side-Channel Distinguishers: An Empirical Evaluation of Statistical Tests for Univariate Side-Channel Attacks against Two Unprotected CMOS Devices[END_REF] Another approach to relax the constraints linking the leakage function and the prediction model is the use of the Mutual Information (MI) as distinguisher. The use of the MI has been presented in the field of side channel analysis by Gierlichs et al. in (59) to build the so called Mutual Information Analysis (MIA). The main advantage of such approach is that the a priori knowledge needed to build Ψ could be small, the only assumption needed on Ψ is to be non-injective [START_REF] Gierlichs | Mutual information analysis[END_REF][START_REF] Prouff | Theoretical and Practical Aspects of Mutual Information Based Side Channel Analysis[END_REF].

The MI allows to evaluate the dependence between two random variables and is given by:

I[X; Y ] = H[X] -H[X|Y ],
where (1.13)

H[X] = -∞ -∞
p(x) log p(x) dx and where (1.14)

H[X|y] = - y -∞ -∞ p(x, y) log p(x|y) dx . (1.15)
Definition 14 (Mutual Information Analysis (MIA) ). The MIA exploiting the MI as distinguisher is given by:

MIA : F n 2 × R Q → F n 2 y, x → argmax k∈K I[x; y] .
(1.16)

Remark 1. The computation of the empirical MI needs to compute the empirical probability density functions of x.

Samples Selection and Dimensionality Reduction

As presented in Sec. 1.3.2 the number of exploitable leakage samples may be small compared to the length of the measurements. As the Templates Attacks are naturally multivariate they can be applied directly on the whole traces but this leads to excessive computational loads and memory consumption [START_REF] Chari | Template Attacks[END_REF]. To reduce the number of points on which the attacks will be proceed a variety of methods exits. Such methods can be divided into two main categories: the sample selection methods and the dimensionality reduction methods.

Those two kinds of method are conceptually closed as they lead to smaller traces. The sample selection methods aim at finding in the traces the most relevant samples and select them. Sample selection methods lead as a consequence to a data selection. The dimensionality reduction methods aim at recombining the different samples in order to increase the possible exploitable samples in an exploitable one and as a consequence better results can be expected.

Sample Selection

Different metrics for sample selection have presented in the field of SCA. They allow to classify the samples in order to identify the most relevant ones. The attacker selecting an arbitrary number of samples maximizing the sample selection metric.

In their original article on Template Attacks Chari et al. [START_REF] Chari | Template Attacks[END_REF] used the difference of mean in order to recover the sample points which are linked to the key.

In the rest of this manuscript x (d) [y] =

Q q=1 x (d) q ×1 { g(k ,tq ,R) (d) =y } Q q=1 1 { g(k ,tq ,R) (d) =y } .
Definition 15 (Difference of Mean (31) (DOM)). The DOM sample selection method is given by:

DOM : F 2 × F n 2 × R Q → F n 2 b, t, x → argmax d≤D y =y x (d) [y] -x (d) [y ] .
(1.17)

An extension of this method based on Sum Of Square Difference has been proposed in [START_REF] Gierlichs | Templates vs. Stochastic Methods[END_REF],

where the square of the difference of means is computed.

Definition 16 (Sum Of Square Difference (60) (SOSD)). The SOSD sample selection method is given by:

SOSD : F 2 × F n 2 × R Q → F n 2 b, t, x → argmax d≤D y =y x (d) [y] -x (d) [y ] 2 .
(1.18)

An extension which takes into account the variance the so called Sum Of Square pairwise T-differences (SOST) has also been proposed in [START_REF] Gierlichs | Templates vs. Stochastic Methods[END_REF].

One can notice that this selection method is closed to the DPA distinguisher. Similarly other distinguishers have been adapted to select samples in the context of Template Attacks.

Samples Selection and Dimensionality Reduction

Definition 17 (Pearson Correlation (98) (CPA)). The CPA sample selection method is given by:

CPA : F n 2 × R Q → F n 2 y, x → argmax d≤D ρ x (d) , y , (1.19)
where ρ denotes the estimator of the Pearson Correlation Coefficient.

Similarly other distinguishers can be used as metric for sample selection. An overview of the different methods can be found in [START_REF] Fan | How to Choose Interesting Points for Template Attacks[END_REF].

Dimensionality Reduction

While Sample Selection aims at selecting one or more relevant samples the Dimensionality Reduction aims at recombining the data in a way that information spread over multiple samples will be combined in only one. In the area of SCA such methods have been presented as preprocessing for Template Attacks (as the selection samples) but also for differential attacks.

Different dimensionality methods have been proposed. The Principal Component Analysis (PCA)) is a classical statistical tool for dimensionality reduction [START_REF] Jolliffe | Principal Component Analysis[END_REF].

Definition 18. The PCA is an orthonormal linear projection of the data, which maximizes the variance of the projected subspace of dimension D ≤ D. More formally, we search the projection which maximizes the variance of the projected data. For the first dimension of the subspace this leads to:

max u1 =1 Var [Xu 1 ] = max u1 =1 t u 1 S T u 1 ,
where S T is the covariance matrix given by t (xx) (xx). For the second dimension, as we want an orthonormal projection, this yields:

max u2 =1 u2•u1=0 t u 2 S T u 2 .
The process is iterated for each dimension D ≤ D.

This method has been introduced in the area of SCA by Archambeau et al. in (2) in the context of the template attacks. It has been also presented in order to improve the results of differential attacks in (5).

Remark 2. In the context of SCA the PCA is generally used to maximize the between-class variance. In this case the covariance matrix computed that is y∈F n

2 x (d) [y] -x (d) x (d) [y] -x (d) t .

INTRODUCTION

Recently a new dimensionality reduction tool has been introduced in the context of SCA, the so called Linear Discriminant Analysis (158) (LDA). While the PCA aims at maximizing the variance of the projected subspace the LDA maximizes the ratio between the between-class variance and the within-class variance. This means that compared to the approach using the PCA is that the within-class is taken into account.

Definition 19. The LDA is an orthonormal linear projection of the data, which maximizes the ratio between the between-class variance and the within-class variance of the projected subspace of dimension D ≤ D.

For the first dimension of the subspace this leads to:

max u1 =1 t u 1 S B u 1 t u 1 S W u 1 .
where S B and S W are respectively the between-classes scatter matrix and the within-classes scatter matrix.

S B = y∈F n 2 x (d) [y] -x (d) x (d) [y] -x (d) t , (1.20)
S W = y∈F n 2 Q q=1 x (d) q × 1 {g(k ,tq,R) d =y} -x (d) [y] x (d) q × 1 {g(k ,tq,R) d =y} -x (d) [y] t .
(1.21)

The process is iterated for each dimension D ≤ D.

Nevertheless even if these methods have already been compared (see for example [START_REF] Choudary | Efficient template attacks[END_REF]) there is no clear and systematic analysis of their overall behaviors in the context of SCA.

Protection methods

In order to protect cryptographic algorithms in embedded devices different countermeasures have been developed. A first approach is to mitigate the part depending on sensitive variables in the measured leakages.

Adding Noise. A designer can increase the noise in leakages by adding some operations in parallel of the execution of sensitive variables. As the sensitive variables, these dummy operations will leak. Another approach is to execute dummy operations between the execution of sensitive operations. The consequence is a misalignment in the traces which can be seen as noise.

1.5 Protection methods Specific Logic. On the other hand a designer can reduced the signal available. A way to attend this goal is to use dual rail logic. In such implementations the same logic is implemented twice and during the execution of the algorithm the second logic takes as input the complementary values.

The two methods lead to a diminution of the Signal to Noise Ratio (SNR) which represents an evaluation of the ratio between information and noise.

Whereas the both methods provide security by increasing the number of traces needed to perform the attacks, their respective behaviors are device dependent. As a consequence a formal analysis of the security provided by these countermeasures is a difficult task. Therefor other countermeasures have been study for which the security characteristic can be formally grounded.

Data Masking Scheme

Data Masking schemes [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF][START_REF] Goubin | DES and Differential Power Analysis -The "Duplication[END_REF] are one of the most used protection method against SCA as the provided security can be formally grounded. The aim of data masking is to make the sensitive data independent from the variables manipulated and then independent from the measured leakages. Intuitively, masking aims at increasing the order of the statistical moments (in the leakage distributions) that reveal sensitive information [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF][START_REF] Ishai | Private Circuits: Securing Hardware against Probing Attacks[END_REF].

Interestingly the consequence of such protections is closed to a noise addition as the exploitable information will be melt into more noisy information. As a consequence we will often see the SNR as a useful tool to study implementations and specifically protected implementations.

The rationale of masking schemes goes as follows: each sensitive variable is randomly split into Ω shares (using Ω-1 masks), in such a way that any tuple of Ω-1 shares manipulated during the masked algorithm is independent from any sensitive variable. A masking scheme which reaches this property is called perfect masking scheme. This splitting is done using an invertible operation ⊥ and random values as masks. Let y be the sensitive values and y i , Ω > i > 0 being the (Ω -1) random values drawn from a uniform law. Then the values manipulated in the data masking schemes are the masks and the masked value : y 0 = y⊥y 1 ⊥...⊥y Ω-1 .

Different operations ⊥ have been presented in the literature. The boolean maskings are the most classical one, they use the XOR denoted by ⊕ as invertible operation. They are often used in practice as the XOR operation is easy to implement both in hardware and in software, moreover in many of the classical block ciphers the permutation operations are linear with the XOR. The arithmetic or additive masking schemes [START_REF] Coron | Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems[END_REF] using the modular addition can also be used in order to protect cryptographic algorithms in which some operations are linear with the

INTRODUCTION

Input text y

Boolean splitting ⊕ addition. It is for example the case with IDEA, SHA-1 or SHA-2. Another type of masking schemes are the multiplicative (61) ones using the modular multiplication. They can be used to compute the substitution part of some block ciphers. Affine masking schemes (57) combine a multiplicative and a boolean masking scheme.

m 1 y ⊕ m 1 ⊕ ... ⊕ m Ω-1 m 2 m Ω-1 ⊕ key: k y ⊕ k ⊕ m 1 ⊕ ... ⊕ m Ω-1 L L L L L (m 1 ) L (y ⊕ k ⊕ m 1 ⊕ ... ⊕ m Ω-1 ) L (m 2 ) L (m Ω-1 ) L (m Ω-1 ) ⊕ L (y ⊕ k ⊕ m 1 ⊕ ... ⊕ m Ω-1 ) ⊕ L (m 1 ) ⊕ L (m 2 ) ⊕ ... ⊕ L (m Ω-1 ) = L (y ⊕ k)
The linear operations (with respect to ⊥) are easy to implement. These operations are applied on all the shares and the results are combined by ⊥ (see Fig. 1.

2).

At the opposite it could be particularly challenging to compute non-linear parts of the algorithm, such as for example the S-Box of AES (a function from n bits to n bits).

A classical approach to compute the non-linear parts is to used masked tables. The idea

Protection methods

is to store a masked version of the non-linear part in a look up table which removes the input mask and remasks by the output mask. As those masks change for each encryption a possibility is to precompute off-line the table for each possible input and output mask in a global Look-up Table [START_REF] Prouff | A Generic Method for Secure SBox Implementation[END_REF][START_REF] Standaert | The World is Not Enough: Another Look on Second-Order DPA[END_REF] . This approach can be prohibitive (e.g. it could be necessary to store a Variety of hardware implementations can be found using specific mask gates ( 171) and the possible algebraic representation of the block cipher [START_REF] Blömer | Provably Secure Masking of AES[END_REF][START_REF] Rivain | Provably Secure Higher-Order Masking of AES[END_REF]. An example for AES is to use the tower field representation to reduce the inversion problem in a smaller field. The Threshold implementations [START_REF] Nikova | Threshold Implementations Against Side-Channel Attacks and Glitches[END_REF] are a particular kind of hardware implementations which are designed to ensure the security up to a certain order in presence of glitches.

2 n × 2 n × 2 n × 2 n table)

Protection for Asymmetric Cryptography

The Asymmetric Cryptography algorithms can be vulnerable to SPA indeed the classical algorithms used for the modular exponentiation used in RSA or the scalar multiplication for ECC use conditional branches depending on the exponent or the scalar. As an example the classical scalar multiplication algorithm performs a double and an add when the scalar bit is one or just a double when the scalar bit is zero. Therefor by simply looked at the sequence of operations it is possible to recover the entire key within one trace. It exists in the literature many different scalar multiplications/modular exponentiations.

To avoid SPA a first countermeasure makes the scalar multiplication regular meaning that the same operations are performed independently from the value of the current bit. Different algorithms have been proposed to attend this goal such as the Double and Add Always or the Montgomery Ladder algorithm.

Nevertheless this kind of countermeasure does not protect against differential attacks. An example of differential attacks has been proposed in [START_REF] Coron | Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems[END_REF]. Similarly to the protected implementations of symmetric cryptographic algorithms, different randomization countermeasures have been developed, they will differ on the randomized values but their behaviors are similar. Indeed

INTRODUCTION

for each execution of the cryptographic algorithm one value or more is randomized which makes this particular variable not attackable by differential means.

Different types of variable can be targeted and as a consequence different variables can be randomized.

Scalar/Exponent Splitting. In order to be protected the scalar (resp. the exponent) has to be randomized. For ECC a first example of scalar randomization has been proposed in [START_REF] Coron | Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems[END_REF]:

the group scalar randomization. This countermeasure takes advantage of the group structure of the EC. It consists in adding to the scalar a multiple of the order of the curve. Nevertheless this countermeasure is the target of the Carry Leakage Attacks [START_REF] Fouque | The carry leakage on the randomized exponent countermeasure[END_REF]. Therefor different other scalar randomization countermeasures have been proposed. They consist in splitting the scalar into two values. In the additive splitting (34) a scalar multiplication, with the secret scalar minus a random number as scalar, is first computed followed by the scalar multiplication with the random number as scalar. In multiplicative splitting (172) a first scalar multiplication is done with a random number. The result of this multiplication will play the role of the point in a second modular multiplication where the scalar is the secret scalar times the inverse of the random number. An other splitting often used is the Euclidean Splitting [START_REF] Ciet | Virtually) Free randomization techniques for elliptic curve cryptography[END_REF]. Similarly to the multiplicative splitting a first scalar multiplication is performed using a random number. Its result serves as point for two other scalar multiplications. The first one used the rest of the euclidean division between the secret scalar and the random, the second scalar multiplication used the quotient of this euclidean division.

Similar countermeasures can be found in RSA implementation. Different scalar blindings have been proposed in the literature. An example of exponent blinding is provided in [START_REF] Paul | Timing attacks on implementations of diffie-hellman, rsa, dss, and other systems[END_REF]. In this case a random multiple of the Euler's function of the modulus is added to the exponent. The Exponent splitting [START_REF] Clavier | Universal exponentiation algorithm -a first step towards provable spa-resistance[END_REF] divides the exponent into two parts. Then two scalar multiplications are performed.

Data randomization. Specific attacks can target the point on the curve manipulated in the scalar multiplication rather than the scalar itself. To prevent such attacks data randomizations often called Points Blindings have been proposed. The first example of Points Blinding was given in [START_REF] Coron | Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems[END_REF]. In this countermeasure a pseudo-random point on the curve is stored on the chip and updated at each iteration. The scalar multiplication is computed on the sum of the initial point and a random one. Other countermeasures have been proposed in order to protect the ECC 1.6 Attacks on the countermeasures algorithms against the Doubling Attack (55) which consists in the comparison of two traces with the base point and the double of this point. Indeed the same value appears in the two traces if the scalar meets some properties. A first example of countermeasures is the Random Projective

Coordinates [START_REF] Coron | Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems[END_REF]. Using the Jacobian coordinate representation the point is randomized by multiplying each coordinate by a random number. A second countermeasure is the Random Curve Isomorphism [START_REF] Joye | Protections against Differential Analysis for Elliptic Curve Cryptography[END_REF]. In this countermeasure the scalar multiplication is computed on an isomorphic random curve.

In the case of RSA the data randomization can be provided in two different ways. The first way is to randomize the modulus. This randomization can be achieved by multiplying the modulus by a random number. The second way is to randomize the base (84) which consists in a blinding of the message and the modulus. A random multiple of the modulus will be added to the message.

This list represents a non exhaustive presentation of possible attacks and countermeasures against ECC and RSA. A synthesis for ECC can be found in [START_REF] Murdica | Sécurité Physique de la Cryptographie sur Courbes Elliptiques[END_REF].

1.6 Attacks on the countermeasures

High Order Attacks

The masking schemes provide security against the SCA presented in Subsect. 1.3.3 nevertheless a particular kind of SCA has been developed in order to counter the masking schemes the so called High order Side Channel Attacks (HOSCA).

An Ω -1 order masking scheme will ensure that any combination of less than Ω values will not leak any information about the key.

The overall principle to counter the masking scheme is to combine the leakages of the Ω shares [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF]. Based on this principle a whole kind of attacks has been defined the HOSCA (29, 106, 133, 177).

Template Attacks

The Template Attacks have been extended to defeat the masking schemes in [START_REF] Oswald | Template Attacks on Masking -Resistance Is Futile[END_REF]. The rational of the attacks is similar to the unprotected cases. In the first learning phase the attacker learns the density probability p (X|T, K , M ) for all the possible (T, K , M ).

Remark 3. As the target is Ω -1 order masking schemes, X should be at least of size D = Ω.

Remark 4. The profiling step is significantly easier if the masks are known during this step.

INTRODUCTION

In the attack phase the contribution of the masks is taken into account by computing the mean over the possible values of the masks.

p (K|X, T ) = m∈M p (X|T, K , m) p(m) (1.22)
Recently the optimal distinguisher has been derived in the context of a template attacks against protected implementations. In the case of masking the optimal distinguisher which maximizes the success rate is given by ( 23) the Maximum Likelihood.

Definition 20 (Maximum Likelihood). When the y (t, k, R) are known and the Gaussian noise N is i.i.d. across the queries (measurements) and independent across the dimension, then the optimal distinguisher is:

OPT : R DQ × R DQ -→ F n 2 (x, y (t, k, R)) -→ argmax k∈F n 2 Q q=1 log E exp -x q -y(t q , k, R) 2 2σ 2 (1.23)
where the expectation operator E is applied with respect to the random variable R ∈ R, and the norm is the Euclidean norm

x q -y(t q , k, R) 2 = D d=1 (x (d) q -y (d) (t q , k, R)) 2 .

Combination functions

While the Template attacks are multivariate, standard distinguishers are in general monovariate.

Thus in order to combine the leakages of each share specific functions are used. These functions are called combination functions. The Higher Order Differential Power Analysis (HODPA) are based on a combination function and a distinguisher presented in Subsect. 1.3.3.3 (also called differential attacks). In the SCA literature several combination functions have presented taken conjointly with the distinguisher they completely defined the HODPA. They can be applied both on the leakage traces or the models. Formally we have that a combination function C is given by:

C : R D → R X → C (X) . (1.24)
Of course to have a sound HODPA we have that D ≥ Ω.

Several examples have been proposed in the case of a second order masking scheme. Let us denote by X (0) the leakage of the first share and X (1) the leakage of the second one i.e.

X (0) = Ψ (0) (Sbox[T ⊕ M ⊕ k ]) + N (0) , (1.25)
X (1) = Ψ (1) (M ) + N (1) .

(1.26)

Attacks on the countermeasures

Similarly we define by Y (0) and Y (1) their respective prediction model.

Definition 21 (Product Combining Function ( 30)). The product combining function multiplies the shares: 1) .

C p : R × R → R X → X (0) × X (
(1.27)

Definition 22 (Absolute Difference Combining Function ( 107)). The Absolute Difference Combining Function computes the absolute difference of the two shares:

C ad : R × R → R X → |X (0) -X (1) | , (1.28)
In the two previous examples the combination function is only applied on the leakages. More exotic high order attack functions have been proposed where two different combination functions are used for the leakages and the prediction models (121).

Prouff et al. shown in ( 133) that the best approach, when the leakage function is the Hamming Weight, is to used the centered product combination function in order to combine the leakages and the prediction model.

Definition 23 (Centered Product Combining Function ( 133)). The centered product combining function computes the centered product of the two shares:

C cp : R × R → R X → X 0 -E X (0) × X (1) -E X (1) | , (1.29)
Additionally Prouff et al. shown in (133) that for a given combination function C X applied on the measurements to maximize the absolute value of the correlation the prediction models have to be combined by:

C Y : F n 2 × R → R X → E Y (0) -E Y (0) × Y (1) -E Y (1) , (1.30)
where C Y is the same function as C X but defined over F n 2 .

High Order Differential Attacks

Definition 24 (2O-CPA ( 133)). We denote by 2O-CPA the CPA using the centered product as combination function. Namely:

2O-CPA : R Q × R Q × R Q -→ F n 2 (x 0 , x 1 , y) -→ argmax k∈F n 2 ρ x (0) -x (0)
x (1)x (1) , y , (1.31)

INTRODUCTION

where

y = E M y (0) (t, k, R) -E y (1) (t, k, R) y (1) (t, k, R) -E y (1) (t, k, R)
, is the element wise product and ρ is an estimator of the Pearson coefficient.

Then this definition can be straightforward extended to any masking scheme of order Ω.

Definition 25. The "classical" ΩO-CPA is the HOCPA built by combining the Ω shares using the centered product combination function.

ΩO-CPA :

R

Ω × R -→ F n 2 x (i) i∈ 0,Ω-1 , Y -→ argmax k∈F n 2 ρ Ω-1 i=0 x (i) , Y , where y = E M d-1 i=0 y (i) (t, k, R) -E y (i) (t, k, R)
, and the product is the element wise product and ρ is an estimator of the Pearson coefficient.

As already mentioned a HOSCA is completely defined by the distinguisher and the combination function. Then all the properties of these attacks can be expressed using the properties of the combination function or the distinguisher.

Definition 26 (Attack order). The order of an HODPA is given by the polynomial degree of its combination function.

Remark 5. In this definition the order of ΩO-CPA is the number of shares combined that is Ω. Proposition 1. The number of measurements needed to recover the secret key increases exponentially with respect to the order of the masking schemes.

Proof. A first proof of this proposition was given in (108) for a Gaussian noise and DPA distinguisher.

Therefor the general assumption is that the better attack against a masked scheme is the minimal order attack.

Recently several HOSCA have been presented which exploit additional leakages (additionally to the masks and the masked sensitive values). In [START_REF] Bruneau | Masks Will Fall Off: Higher-Order Optimal Distinguishers[END_REF][START_REF] Pan | You cannot hide behind the mask: Power analysis on a provably secure S -box implementation[END_REF][START_REF] Tunstall | Masking Tables -An Underestimated Security Risk[END_REF] presented an attack which takes into account the leakages which occur during the table recomputation of a masked block cipher with table recomputation steps. Exploiting the multivariate leakages of such algorithms, the results of the HOSCA are greatly increased.

Let us define the leakages of the table recomputation:

X (2) = Ψ (2) (M ) + N (2)
(1.32)

X (3) = Ψ (3) (M ⊕ 1) + N (3) (1.33) . . . X (2 n +1) = Ψ (2 n +1) (M ⊕ (2 n -1)) + N (2 n +1) .
(1.34)

Attacks on the countermeasures

One example of an attack exploiting these leakages has been exposed in [START_REF] Tunstall | Masking Tables -An Underestimated Security Risk[END_REF], which we label as 2-stage CPA attack.

Definition 27 (2-stage CPA attack ( 174)).

2×CPA mt (x, t) = arg max k∈K ρ(x (0) , y (0) (t, k, m)), (1.35)
where ∀i m i is the mask that maximizes the correlation between x

(ω) i and y

(ω) i = ω ⊕ m i for ω ∈ [2, 2 n+1
]. This attack is a synergy between a horizontal and a vertical attack. For each trace (separately ∀i), the first attack in Eq. (4.7) consists in recovering the mask during the precomputation. Second, a regular CPA using a model in which both the plain-text t and the mask m are assumed as public knowledge is launched. Even if the mask m is not recovered correctly for each trace (since 2 n leakage samples during the precomputation can be seen as small), it can be expected that the value of the mask is recovered by the first horizontal attack probabilistically well enough for it to be biased, i.e., better guessed than random.

In order to mitigate the impact of these attacks some countermeasures have been developed [START_REF] Pan | You cannot hide behind the mask: Power analysis on a provably secure S -box implementation[END_REF] , they are based on random shuffles. These shuffles make the loop index ω unknown by the attacker. This kind of masking are called in this manuscript shuffled table recomputation masking scheme.

Dimensionality parameters of the attacks

The SCA often deal with the combinations of several leakage samples. It is the case of SCA with dimensionality reduction methods for differential attacks or template attacks. The HOSCA often combine different leakage samples to recover key depend values. In this subsection we present three definitions (numbered 28, 29 and 30) which allow to classify the attacks depending on the way they exploit the multiple leakages.

Definition 28 (Dimension). The dimension D of the attack is the number of leakage samples jointly used to establish one key guess.

Let X be a leakage measurement. We have that X = Ψ (g (k , T, R)) + N . The set of all distinct sensitive variables is given by ∆ = {g (k , T, R)

(i) |∀j = i, g (k , T, R) (i) = g (k , T, R) (j) } .
Definition 29 (δ-variate attacks). An attack is said δ-variate when δ = #∆ .

Notice that this definition does not take into account the possible duplicate variables but highlights the diversity of exploitable variables.

1. INTRODUCTION R R function g function Ψ Leakage Selection w H w H w H w H Measured leakage X with δ = 3 Multi-target Multi-variate Dimensionality D = 31 with τ = 1, 1, 2 S(T ⊕k ⋆ )⊕R T ⊕k ⋆ ⊕R Figure 1.3: Example of multiple leakages
Another approach which combines leakage samples, is the exploitation of the leakages of different target operations. For example an attacker can recover a byte of key during the AddRoundKey, SubBytes or ShiftRows and combined the different key guesses obtained in order to improve the results of these attacks. Such attacks presented in ( 101) are called Multi-target.

In this thesis we give a closed definition: Definition 30 (τ -target attacks). An attack is said τ -variate when τ is the number of subset of ∆ which depends on the secret key.

In other words this means that an attacker can build τ different and independent attacks. Of course a better approach is to exploit all these results in one to improve the success probability of the attacks. In this thesis we will investigate how to improve the results of the SCA by increasing these three parameters.

An overview of the three previous definitions is given in

Horizontal Attack

Similarly to the symmetric case some new attacks have been developed to counter the protections in the case of asymmetric cryptography. A classical kind of methods to defeat countermeasure

Attacks evaluation

Attack

Dimension δ τ

CPA 1 1 1 CPA with dimensionality reduction D 1 1 2O-CPA 2 2 1 ΩO-CPA Ω Ω 1 Multi-target DPA τ τ τ Table 1.1: Dimension parameter
is the so called Horizontal Attacks. These attacks recover the secret key in only one trace and as a consequence are not impacted by the randomization countermeasures. They exploit the regularity in the power laddering to extract information within one trace.

Remark 6. In presence of scalar/exponent Horizontal Attacks blinding allows to recover the blinded secret key. As this value allows to forge correct outputs it is sufficient for an attacker point of view to recover only this value.

A first example of Horizontal Attack the so called Big Mac Attack can be found in [START_REF] Walter | Sliding Windows Succumbs to Big Mac Attack[END_REF].

This attack on RSA implementation consists in finding if the same operand appears into two different multiplications. The rational is as follows, the attacker first select two leakage windows X (1) and X (2) corresponding to two different multiplications. If the Euclidean distance is small then the same operand are manipulated in the two multiplications. Formally if we have the X (1) -X (2) 2 < t where t is a threshold we have the same operand. This attack has been improved in [START_REF] Clavier | ROSETTA for single trace analysis[END_REF] where the Pearson coefficient is used instead of the Euclidean distance. This attack has also been extended to ECC in [START_REF] Bauer | Horizontal collision correlation attack on elliptic curves -extended version[END_REF].

Of course Template Attacks are also available against this protection but they require the knowledge of the secret values during the profiling phase ( 102).

An other approach exploiting cluster algorithms has recently been presented. This kind of attacks allows to recover the secret key in one trace [START_REF] Heyszl | Clustering Algorithms for Non-Profiled Single-Execution Attacks on Exponentiations[END_REF][START_REF] Perin | Attacking Randomized Exponentiations Using Unsupervised Learning[END_REF]. These attacks allow to target directly the bit-values of the secret key.

Attacks evaluation

As already mentioned different distinguishers and preprocessing methods can be used to build SCA. Then the question arises to know which distinguisher or which combination distinguisher/preprocessing method leads to the better efficiency. Two approaches can be chosen. A

INTRODUCTION

first way is to exploit actual results of attacks to build the comparisons. The other possibility is to theoretically evaluate the results of the attacks based on the expression of the distinguishers.

Empirical Evaluations

In this approach the different attacks are compared using their respective results. Different metrics have been proposed in order to exploit theses results to build comparisons. These metrics are often based on the results of several repetitions of the same attacks over different sets of traces. This means that the empirical distinguisher D is applied I times on I different sets of traces i X and i T with i ≤ I build with the same secret key k . Notice that the index is before the capital bold letter to avoid ambiguity with the column notation. In the rest of this section let us denote by i k the result of the i-th one with i

≤ I i.e. i k = argmax k D ( i X, i T).
Definition 31 (Empirical Success Rate (161) (SR)). Let i k, i ≤ I be set of I results of I independent attacks. The empirical Success Rate for an empirical distinguisher D is given by:

SR D = 1 I 1≤i≤I 1 k =i k . (1.36)
An approach is to compute Guessing Entropy (GE). The GE is given by the mean rank of the secret key.

Definition 32 (Rank). The rank of the secret key is given by: rank (k ) = min

K S ∈K #K -#{K S |k = argmax k∈K S D ( i X, i T)} + 1 . (1.37)
Definition 33 (Guessing Entropy (89) (GE)). Let i k, i ≤ I be set of I results of I independent attacks. The empirical Guessing Entropy for an empirical distinguisher D is given by:

GE D = 1 I 1≤i≤I rank (k ) . (1.38)
When the attack is followed by a key enumeration [START_REF] Veyrat-Charvillon | An optimal Key Enumeration Algorithm and its Application to Side-Channel Attacks[END_REF] an attacker may used the ranking entropy which takes into account the orders of magnitude of the rank more than the rank of the key itself [START_REF] Daniel | Characterisation and Estimation of the Key Rank Distribution in the Context of Side Channel Evaluations[END_REF].

Definition 34 (Ranking Entropy (100) (RE)). Let i k, i ≤ I be set of I results of I independent attacks. The empirical Ranking Entropy for an empirical distinguisher D is given by:

RE D = 1 I 1≤i≤I log rank (k ) . (1.39)
These empirical metrics provide an efficient way to compare the results of different distinguishers. A distinguisher will be said better than another one if its SR is higher or if its GE is lower when applied on the same set of traces.

Attacks evaluation

Theoretical comparison

The empirical validations do not provide any feedback to explain the behaviors of the success SCA. In order to get a better understanding on relevant parameters, theoretical evaluation can be build. The success of an attack can be expressed using the theoretical Success Rate (SR)

Definition 35 (Theoretical Success Rate (SR)). The theoretical Success Rate for a given distinguisher D is: • The number of measurements Q,

SR [D] = p(k = k) . ( 1
• The Signal to Noise Ratio SNR,

• The confusion coefficient κ.

The confusion coefficient is a parameter which expresses the relationship between the correct key and incorrect key hypothesis for a given leakage model. In the initial publication ( 53 Definition 36 (Confusion Coefficient ( 63)). The confusion coefficient between the secret key k ∈ K and any key hypothesis k ∈ K for a leakage model is given by:

κ (k , k) = p(Y (k ) = Y (k)) = E   Y (k ) -Y (k) 2 2   . (1.41)
Recently these approaches have been extended in the case of HOSCA against masking scheme [START_REF] Ding | A statistical model for higher order DPA on masked devices[END_REF][START_REF] Lomné | How to Estimate the Success Rate of Higher-Order Side-Channel Attacks[END_REF].

INTRODUCTION

1.8 Contributions of the Thesis

1.8.

Contributions

This thesis is about the security of the protected implementation of cryptographic algorithms.

Especially we investigate the possible attack path using specific HOSCA designed to target these implementations. In this context we show that the level of security provided by analysis which take into account only monovariate leakages is overestimated.

In particular starting from the observation that many sensitive leakages appear in the side channel measurements we investigate what is their impact in terms of security. Which can be rewritten as:

How far an attack can go by exploiting multiples leakages?

The answer of this question is provided by exploring the different meaning that the term "multiple" can take in the SCA context.

The Fig. 1.4 represents a summary of the contributions of this thesis. Each arrow highlights a way to improve the success of the SCA. The black marks represent the initial attacks which exploit the minimum number of points. In this manuscript we show that increasing the number of leakage samples used for the attacks by adding similar variables, the D axis in Fig. 1.4 is a powerful tool to increase the probability of success. We show theoretically the best approach in case of a first order attack represented by a green arrow. In the case of a second order attack, represented by a blue arrow, against protected implementations we will present a dimensionality reduction tool which improves the results of the attacks. The gain of these methods increases with the order of the implementations. We can easily see in Fig. 1.4 that the previous methods exploit the multiplicity of leakages with respect with only one axis. The other attacks will exploit the two remaining axes. We give an example of a multi-target attack exploiting the table recomputation step of a masking scheme in Chap. 4. We theoretically prove that this method is the optimal way to exploit the multiple leakages. In Chap. 6 we present a new attack which exploits the leakages along the δ axis. This attack presents the interesting property of not being of minimal order as it is a third order attack represented by a red arrow. Nevertheless this attack exploits only two axes. The last attack exploits the three axes and provides better results compare to the previous chapter assuming a full knowledge of the leakage function. Finally attack allows an attacker to select the axis in which he could improve the attacks. We can notice that these axes are numerous, multiple leakages, multiple variables and multiple targets.

Outlines

In a first Part I of this manuscript we investigate how to increase the SR by exploiting the multiple leakages of the same sensitive variable. This question is often presented in the SCA literature and can be expressed into two ways. How to turn multivariate leakages in monovariates ones and how to do this in the best way. The first question was often answered by applying dimension reduction tools. Regarding the classification provided in Subsect. 1.6.3 in this part we will present methods to increase the dimension of the attack.

In Chapter 2 we tackle the question of optimality. We theoretically expressed the best 1. INTRODUCTION dimensionality. In the case of modulated traces with full knowledge of the modulation we gives the optimal dimensionality reduction.

In Chap. 3 we present new dimensionality reduction tools in the context of HOCPA. We detail the impact of multiple leakages in the case of HOCPA. In particular we show that as the number of possible points increases with the order the impact of dimensionality reduction jointly increases with order. Moreover we present a new tool to go from multivariate leakages to monovariate ones. Relaxing the knowledge of the attacker we present an optimal dimensionality reduction for a particular types of noises.

In the second Part II we investigate how to enhance results of HOSCA by taking into account different variables. In particular regarding the classification provided in Subsect. 1.6.3 we will build highly variate and highly target attacks. In other words we increase the parameter τ and δ of the attacks.

In Chap. 4 we extend the first attack against masking schemes with table recomputation step. In this scenario we derive the optimal distinguisher and show that this approach leads to better results than the state-of-the-art attacks.

It is known that such attacks targeting the table recomputation are a critical threat against these implementations. As a consequence countermeasures have been developed. As already mentioned these countermeasures are based on the randomization of the order of execution of the table recomputation.

In Chap. 5 we build an HOSCA which allows to attacks such countermeasures better than any attacks of the state-of-the-art. While being a higher order attack this new attack gives better results than the minimal order ones. Indeed we show that it is possible to combine the multiple different leakages in one to increase the SNR and thus the SR of the attacks. As a consequence we show a first example in which the minimal order monovariate attacks is not the good tool to asset the security of these shuffled table recomputation implementations of masked block cipher.

In Chap. 6 we investigate theoretically the behaviors of the Maximum Likelihood distinguisher in the context of highly multivariate leakages. For instance we take as example the protected table recomputation algorithm. We show that in this case the ML cannot be computed. Additionally we present a new attack with better results in this context than the attacks of the state-of-the-art.

In particular this new attack shows how to combine different order leakages to build efficient HOSCA.

Part I

Dimensionality Reduction a case study in presence of masking CHAPTER 2

Optimal Dimensionality Reduction with Profiling.

Introduction

The large number of samples to feed into the model has always been a problematic issue for multi-dimensional side-channel analysis. One solution is to use techniques to select points of interest. Most of them, such as sum-of-square differences (SOSD) and t-test (SOST) [START_REF] Gierlichs | Templates vs. Stochastic Methods[END_REF], are ad hoc in that they result from a criterion which is independent from the attacker's key extraction objective. Recent criteria, such as leakage maximization by sensitive value [START_REF] Archambeau | Template Attacks in Principal Subspaces[END_REF], avoid this problem.

Other formal criteria, related to non-profiled attacks, have also been proposed [START_REF] Hajra | On the optimal pre-processing for nonprofiling differential power analysis[END_REF][START_REF] Oswald | Improving Side-Channel Analysis with Optimal Linear Transforms[END_REF].

OPTIMAL DIMENSIONALITY REDUCTION WITH PROFILING.

Therefore, there seems to be a converging effort, in both non-profiled and profiled attacks, to reduce the dimensionality of multi-dimensional measurements. This desirable property of dimensionality reduction achieves several goals simultaneously:

• it simplifies the side-channel problem (to a single multivariate pdf);

• it concentrates the information (to distinguish using fewer traces); and

• it improves computational speed.

It can be argued, however, that like every preprocessing technique, dimensionality reduction would lose information.

Contributions. In this chapter, we tackle this problem of dimensionality reduction from a theoretical viewpoint. Provided that the attacker has full knowledge of the leakage model, we find that "less is more": the advantages of dimensionality reduction can come with no impact on the attack success probability, while improving computational speed.

We derive that the optimal dimensionality reduction process consists in a linear combination of samples, which we explicit as a projection on a specific one-dimensional space. For white noise, it turns out that the improved signal-to-noise ratio (SNR) after projection is simply the sum of the signal-to-noise ratios at the various samples before projection.

Finally, we show that the optimal dimensionality reduction technique asymptotically matches the linear discriminant analysis (LDA) preprocessing. We find that LDA generally outperforms principal component analysis (PCA) for which the SNR increases to a lesser extend than LDA, except in the case of white homoscedastic noise where PCA and LDA become equivalent.

We also validate in practice those results on the DPA contest v2 traces [START_REF]DPA Contest[END_REF].

Review of the state-of-the-art. Dimensionality reduction is part and parcel of profiled attacks. The seminal paper on template attacks ( 31) is motivated by keeping covariance matrices involved in the training phase sufficiently well conditioned. Manual selection of relevant leaking points was discussed in (122) as educated guesses. Several automated techniques were proposed, such as sum-of-square differences (SOSD) and t-test (SOST) [START_REF] Gierlichs | Templates vs. Stochastic Methods[END_REF], and also wavelet transforms [START_REF] Debande | Wavelet transform based pre-processing for side channel analysis[END_REF].

Several related metrics were proposed for leakage detection. The ANOVA (ANalysis Of VAriance) F-test is a ratio between the explained variance and the total variance-see e.g. [START_REF] Choudary | Efficient template attacks[END_REF][START_REF] Danger | High-order timing attacks[END_REF] and [START_REF] Bhasin | Side-channel Leakage and Trace Compression Using Normalized Inter-class Variance[END_REF] where it is named Normalized Inter-Class Variance (NICV). Also used for linear

Theoretical Solution in the Presence of Gaussian Noise

regression analysis, it is known as the coefficient of determination, denoted by the symbol "R 2 ".

It is employed in the context of side-channel analysis in [START_REF] Sugawara | Profiling attack using multivariate regression analysis[END_REF] as multivariate regression analysis in the presence of white noise, and in [START_REF] Souissi | On the Optimality of Correlation Power Attack on Embedded Cryptographic Systems[END_REF], where it is used as a distinguisher and as a linearity metric.

PCA has been used to compact traces in ( 5) and templates in [START_REF] Archambeau | Template Attacks in Principal Subspaces[END_REF]. The eigenvalues of PCA can be viewed as a security metric [START_REF] Sylvain Guilley | Security Evaluation of WDDL and SecLib Countermeasures against Power Attacks[END_REF] or even as a distinguisher [START_REF] Souissi | First Principal Components Analysis: A New Side Channel Distinguisher[END_REF]. This technique is particularly attractive as it can be easily and accurately computed with no divisions involved. It is advocated in [START_REF] Karsmakers | Side channel attacks on cryptographic devices as a classification problem[END_REF] that PCA aims at maximizing the inter-class variance, yet it is also important to take the intra-class variance into account. For this reason, LDA has been promoted as an improved alternative. Empirical comparisons were investigated in [START_REF] Mathieu Renauld | A formal study of power variability issues and side-channel attacks for nanoscale devices[END_REF][START_REF] Standaert | Using Subspace-Based Template Attacks to Compare and Combine Power and Electromagnetic Information Leakages[END_REF][START_REF] Strobel | Microcontrollers as (in)security devices for pervasive computing applications[END_REF]. Unfortunately, despite some differences in terms of qualitative efficiency, there is no clear rationale to prefer one method over the other. In fact, it is unclear which of the intrinsic virtue of statistical tools, their implementation, or the dataset is actually responsible for the performance of dimensionality reduction.

Other works attempted to consider different objective functions. In (120), the correct key correlation is taken as the objective to be maximized. A similar goal is pursued in [START_REF] Hajra | Multivariate leakage model for improving non-profiling DPA on noisy power traces[END_REF][START_REF] Hajra | SNR to Success Rate: Reaching the Limit of Non-Profiling DPA[END_REF][START_REF] Hajra | On the optimal pre-processing for nonprofiling differential power analysis[END_REF][START_REF] Hajra | Reaching the limit of nonprofiling DPA[END_REF].

Still other dimensionality reduction techniques exist, such as quadratic discriminant analysis, but have not been studied in the side-channel literature. We mention that similar questions have also been raised in the presence of masking countermeasures [START_REF] Bruneau | Boosting Higher-Order Correlation Attacks by Dimensionality Reduction[END_REF][START_REF] Durvaux | Efficient Selection of Time Samples for Higher-Order DPA with Projection Pursuits[END_REF][START_REF] Reparaz | Selecting Time Samples for Multivariate DPA Attacks[END_REF].

Outline. The remainder of the chapter is as follows. The optimal dimensionality reduction is derived theoretically in Section 2.

Theoretical Solution in the Presence of Gaussian Noise

Notations

We adopt a matrix notation. The different queries are indexed by q = 1, . . . , Q, where Q is the number of traces. The different samples in a given trace are indexed by d = 1, . . . , D. Any matrix containing D samples from Q queries is denoted by:

M D = (M d,q ) d,q ,
2. OPTIMAL DIMENSIONALITY REDUCTION WITH PROFILING.

where d = 1, . . . , D is a row index and q = 1, . . . , Q is a column index. For clarity reason we add in this chapter the index D. Two matrices noted side-by-side are implicitly multiplied.

In this chapter in order to derive the optimal attack, it is assumed that the leakage model Ψ is perfectly known to the attacker. We also assumed without loss of generality that is model is centered.

The actual leakage can be written as

X D = α D Y(k ) + N D , (2.1)
where the components of α are not all zero, k is the (unknown) correct key, and N D is some random measurement noise. The α and noise distribution are assumed known to the attacker.

We make the stationarity assumption that the noise distribution does not depend on the particular query, that is, the N D q are independent and identically distributed independently of the value of q. For a given q, however, the noise samples of N D q can be correlated. We assume that N D q follows a D-dimensional zero-mean Gaussian distribution N(0, Σ), where covariance matrix Σ is a symmetric positive definite D × D matrix. Therefore, there exists a matrix Σ 1/2 , which is such that Σ 1/2 Σ 1/2 = Σ. We assume that the matrix Σ is known by the attacker.

Optimal Attack

We focus on the optimal attack as part of our scientific approach to the problem. It is always possible that for some peculiar reason a suboptimal attack actually performs better in the presence of dimensionality reduction. But by the data processing theorem (41) any preprocessing like dimensionality reduction can only decrease information about the secret, and, therefore, degrade performance of the optimal attack. As a result, it does make sense to minimize the impact of dimensionality reduction on the success rate for this optimal attack so as not to be biased by performance loss or gain due to other factors.

The optimal attack, also known as the template attack [START_REF] Chari | Template Attacks[END_REF], consists in applying the maximum likelihood principle [START_REF] Heuser | Good Is Not Good Enough -Deriving Optimal Distinguishers from Communication Theory[END_REF]. Having collected Q traces of dimensionality D in a matrix x D , where each trace x D q corresponds to a known plaintext t q , the best key guess that maximizes the

Theoretical Solution in the Presence of Gaussian Noise

probability of success is given by

D(x D , t) = arg max k p(x D |t, k = k) (2.2) = arg max k p N D (x D -α D y(k)) (2.3) = arg max k Q q=1 p N D (x D -α D y q (k)) (2.4)
where

p N D q (z D ) = 1 (2π) D | det Σ| exp - 1 2 (z D ) t Σ -1 z D . (2.5)
We have used the independence of the queries in (2.4) and the assumption that at each query, the noise distribution is the same in (2.5).

Notice that, the optimal attack can as well be a simple power attack

(if Q = 1) or a differential power attack (if Q > 1)
, using the terminology from [START_REF] Paul | Differential power analysis[END_REF]. Still, in the sequel, we focus on attacks which require many traces (Q 1).

Optimal Dimensionality Reduction

We state our main result in the following Theorem 2.2.1:

Theorem 2.2.1. The optimal attack on the multivariate traces x D is equivalent to the optimal attack on the monovariate traces x Q , obtained from x D by the formula:

x q = α D t Σ -1 x D q (α D ) t Σ -1 α D (q = 1, . . . , Q). (2.6)
Proof. By taking the logarithm of the expression to be maximized in Eqns. (2.2)-(2.5), the optimal distinguisher D(x D , t) rewrites

D(x D , t) = arg min k Q q=1 x D q -α D y q (k) t Σ -1 x D q -α D y q (k) . (2.7)
For each trace index q, the terms in the sum expand to

(x D q ) t Σ -1 x D q cst. C independent of k -2(α D ) t y q (k)Σ -1 x D q + (y q (k)) 2 (α D ) t Σ -1 α D = C -2y q (k) (α D ) t Σ -1 x D q + (y q (k)) 2 (α D ) t Σ -1 α D = (α D ) t Σ -1 α D y q (k) - (α D ) t Σ -1 x D q (α D ) t Σ -1 α D 2 + C .

OPTIMAL DIMENSIONALITY REDUCTION WITH PROFILING.

The latter division is valid since Σ is positive definite and α D is a nonzero vector. Therefore,

D(x D , t) = arg min k Q q=1 y q (k) - (α D ) t Σ -1 x D q (α D ) t Σ -1 α D 2 (α D ) t Σ -1 α D = arg min k Q q=1 x q -y q (k) 2 σ 2 , (2.8)
where

         x q = (α D ) t Σ -1 x D q (α D ) t Σ -1 α D , σ = (α D ) t Σ -1 α D -1/2 .
(2.9)

We have shown that (2.7) and (2.8) are equivalent expressions for the same optimal distinguisher, computed either:

• on multivariate traces x D q , with a noise covariance matrix Σ, or:

• on monovariate (i.e., scalar) traces x q , with scalar noise of variance σ 2 .

Theorem 2.2.1 shows that in fact, the optimal attack already integrates an optimal dimensionality reduction. The maximal success rate is not altered.

Definition 37 (Projection vector). Let V D be a column of D elements. We call the projection of an acquisition campaign x D on V D the new mono-sample traces (V D ) t x D . That is, every trace

X D q (1 ≤ q ≤ Q) of the initial campaign is summarized as one sample (V D ) t X D q = V D | X D q .
Based on this definition, Theorem 2.2.1 can be interpreted as follows.

Corollary 1. The optimal dimensionality reduction is made by a linear combination of the samples where each multivariate trace is projected on the vector

V D = Σ -1 α D (α D ) t Σ -1 α D , of size D × 1. Proof. By Theorem 2.2.1, x Q 1 × Q matrix = (α D ) t Σ -1 (α D ) t Σ -1 α D 1 × D matrix (V D ) t x D D × Q matrix .
In addition, after this projection, the leakage becomes scalar and can be characterized by a signal-to-noise ratio as shown in the following Corollary 2. After optimal dimensionality reduction, the signal-noise-ratio is given by

1 σ 2 = (α D ) t Σ -1 α D .

Examples

Proof. This is in line with Eqn (2.8). The random leakage x D is protected onto V D to yield X q = Y q (k)+ N (q = 1, . . . , Q) where N is an additive white Gaussian noise (AWGN) distributed as N(0, ((α

D ) t Σ -1 α D ) -1
). Recall that the variance of the leakage model has been assumed normalized = 1. Therefore, the signal-to-noise ratio equals Var(Y q (k))

Var( N ) = 1 ((α D ) t Σ -1 α D ) -1 = (α D ) t Σ -1 α D .
The SNR is an interesting metric on its own, because it quantifies how much the signal has been concentrated (its power increased) for a given noise level. Furthermore, the SNR directly relates to the success rate of optimal attacks (53).

Discussion

It is interesting to note that the optimal dimensionality reduction does not depend on the actual distribution of Y D (k), the deterministic part of the leakage model. This means that irrespective of the leakage function Ψ, the best dimensionality reduction depends only on signal weights α D and on noise covariance Σ.

Similarly, the optimal dimensionality reduction does not depend on the confusion coefficient of the leakage model ( 53): for identical weight and noise distribution, the optimal linear combination of leakages is the same whether an XOR or a substitution box operation is targeted.

Examples

White Noise

One interesting situation is when the noise samples are uncorrelated (see for instance [START_REF] Sugawara | Profiling attack using multivariate regression analysis[END_REF] for an experimental setup). The covariance matrix Σ is diagonal:

Σ =       σ 2 1 0 • • • 0 0 σ 2 2 • • • 0 . . . . . . . . . . . . 0 0 • • • σ 2 D       .
Proposition 2. For white noise, the optimal dimensionality reduction takes the form:

x q = D d=1 α d σ 2 d x (d) q D d=1 α 2 d σ 2 d (q = 1, . . . , Q) (2.10)

OPTIMAL DIMENSIONALITY REDUCTION WITH PROFILING.

Proof. Apply Theorem 2.2.1, where Σ -1 is diagonal with diagonal entries 1/σ 2 d .

Let SNR d = α 2 d /σ 2 d be the initial signal-to-noise ratio at the dth sample before dimensionality reduction.

Proposition 3. For white noise, the equivalent signal-to-noise ratio after optimal dimensionality reduction is given by the sum

SNR = D d=1 SNR d .
(2.11)

Proof. By Corollary 2, SNR = (α D ) t Σ -1 α D = D d=1 α 2 d σ 2 d = D d=1 SNR d .
Thus, combining independent multidimensional samples within one trace increases the signalto-noise as if those samples were captured in D independent traces. In this case having Q traces of D samples each is simply the same as having Q × D independent monovariate traces.

Correlated Autoregressive Noise

A more general situation is when the samples are correlated like an autoregressive process. More precisely, assume that all samples share the same noise distribution of variance σ 2 , and that two consecutive noise samples have correlation factor equal to ρ ∈] -1, +1[. The correlation factors ρ typically models an autoregressive low-pass filtering of the acquisition setup (see Sec. 2.5.2 for a real-world example). The noise covariance matrix takes the Toeplitz form:

Σ = σ 2               1 ρ ρ 2 ρ 3 • • • ρ D-2 ρ D-1 ρ 1 ρ ρ 2 • • • ρ D-3 ρ D-2 ρ 2 ρ 1 ρ • • • ρ D-4 ρ D-3 ρ 3 ρ 2 ρ 1 • • • ρ D-5 ρ D-4 . . . . . . . . . . . . . . . . . . . . . ρ D-2 ρ D-3 ρ D-4 ρ D-5 • • • 1 ρ ρ D-1 ρ D-2 ρ D-3 ρ D-4 • • • ρ 1               = σ 2 ρ |d-d | 1≤d,d ≤D .
We emphasize that |ρ| is strictly smaller than one in keeping with the assumption that Σ be positive definite. When ρ = 0, the noise becomes white as in the preceding subsection.

Proposition 4. For autoregressive noise, the optimal dimensionality reduction takes the form:

x q = 1 σ 2 (1-ρ 2 ) (α 1 -ρα 2 )x q,1 + D-1 d=2 ((1 + ρ 2 )α d -ρ(α d-1 + α d+1 ))x d,q
+ (α Dρα D-1 )x q,D . (2.12)

Examples

Proof. It can easily be checked that Σ -1 is tridiagonal:

Σ -1 = 1 σ 2 (1 -ρ 2 )                 1 -ρ 0 0 • • • 0 0 -ρ 1 + ρ 2 -ρ 0 • • • 0 0 0 -ρ 1 + ρ 2 -ρ • • • 0 0 0 0 -ρ 1 + ρ 2 • • • 0 0 . . . . . . . . . . . . . . . . . . . . . 0 0 0 0 • • • 1 + ρ 2 -ρ 0 0 0 0 • • • -ρ 1                 .
Then apply Theorem 2.2.1:

x q = 1 σ 2 (1-ρ 2 ) α 1 α 2 • • • α D-1 α D           1 -ρ • • • 0 0 -ρ 1 + ρ 2 • • • 0 0 . . . . . . . . . . . . . . . 0 0 • • • 1 + ρ 2 -ρ 0 0 • • • -ρ 1                     x q,1
x q,2 . . .

x q,D-1 x q,D          
and expand.

Notice that in the optimal dimensionality reduction, each leakage sample x (d) q

is not only weighted by its corresponding α d but also by its two neighbor weights α d±1 , provided the latter exist.

Proposition 5. For autoregressive noise, the equivalent signal-to-noise ratio after optimal dimensionality reduction is given by

SNR = 1 σ 2 (1-ρ 2 ) α 2 1 + (1 + ρ 2 ) D-1 d=2 α 2 d + α 2 D -2ρ D-1 d=1 α d α d+1 . (2.13)
Proof. Apply Corollary 2:

SNR = 1 σ 2 (1-ρ 2 ) α 1 α 2 • • • α D-1 α D           1 -ρ • • • 0 0 -ρ 1 + ρ 2 • • • 0 0 . . . . . . . . . . . . . . . 0 0 • • • 1 + ρ 2 -ρ 0 0 • • • -ρ 1                     α 1 α 2 . . . α D-1 α D          
and expand.

Corollary 3. For equal weights

α 1 = • • • = α D = α, i.e.
, when initial signal-to-noise ratios

SNR 1 = • • • = SNR D = SNR are the same, one has SNR = SNR × D(1 -ρ) + 2ρ 1 + ρ . (2.14)
2. OPTIMAL DIMENSIONALITY REDUCTION WITH PROFILING.

Proof. Proposition 5 reduces to

SNR = α 2 σ 2 (1 -ρ 2 ) 2 + (D -2)(1 + ρ 2 ) -2ρ(D -1) = α 2 σ 2 (1 -ρ)(1 + ρ) ((1 -ρ)(D -ρ(D -2))) = α 2 σ 2 1 1 + ρ (D -ρ(D -2)) = SNR × D(1 -ρ) + 2ρ 1 + ρ .
In other words, optimal dimensionality reduction has the effect of multiplying the monovariate SNR by the factor D-ρ(D-2)

1+ρ

. This gain factor is of course equal to 1 for dimension D = 1, but becomes strictly greater than 1 for larger dimensions, since

D-ρ(D-2) 1+ρ > D-(D-2)

2

= 1 where we have used that ρ > -1 or 1 1+ρ > 1 2 . For very small values of correlation ρ, Taylor expansion about ρ = 0 gives D-ρ(D-2)

1+ρ = D -2(D -1)ρ + O(ρ 2 ).

Comparison with PCA and LDA

When the attacker does not precisely know the model given by Eqn. (2.1), the optimal dimensionality reduction cannot be applied directly. In this section, we analyse theoretically two well-known engineering solutions to reduce the dimensionality: PCA and LDA. Both techniques are based on eigen decompositions.

Principal Components Analysis (PCA)

Principal components analysis aims at identifying directions in the centered data set. The directions of PCA are the eigenvectors of t (xx) (xx).

Proposition 6. Asymptotically as Q -→ +∞,

t (x -x) (x -x) -→ α D (α D ) t + Σ. (2.15)
Proof. By the law of large numbers,

t (x -x) (x -x) -→ Cov(X (d) q , X (d ) q )
2.4 Comparison with PCA and LDA almost surely, where the covariance term can be computed as: Cov(X

(d) q , X (d )
q ) = Cov(α d Y q + N (d) q , α d Y q + N (d ) q
). When expanding this expression, cross terms disappear by independence of Y and N D . There remains:

α d α d + Σ d,d
where we have used the hypothesis that Y q has unit variance.

The classical PCA has the drawback that t (xx) (xx) depends both on the signal and on the noise. Inter-class PCA has been introduced in (2). The matrix used in the PCA is traded for a more simple matrix Z D,#Y , where each column, indexed by y, is the centered column

1 1≤q≤Q Yq=y 1 1≤q≤Q Yq=y X D q .
One advantage of this method is that it explicitly takes into account the sensitive variable Y .

It can be easily checked, that, asymptotically, each column

Z D y tends to α D y when Q -→ +∞. Therefore, Z D,#Y (Z D,#Y ) t tends to a D × D matrix proportional to α D (α D ) t .
Here, the noise has been averaged away in each class y, which is a second advantage. Therefore, in the sequel, we shall refer to the inter-class PCA of (2) simply as PCA.

We have the following spectral characterization of the asymptotic PCA:

Proposition 7.
Asymptotically, PCA has only one principal direction, namely the vector α D .

Proof. By Proposition 6, the PCA matrix tends asymptotically to α D (α D ) t . This D × D matrix has rank one, because all its columns are multiple of α D . Since

(α D (α D ) t )α D = α D ((α D ) t α D ) = α D 2 2 × α D , α D is the eigenvector with corresponding nonzero eigenvalue = α D 2 2 .
Notice that the uniqueness of the eigenvector for PCA holds in our model (2.1). However, Proposition 7 would not hold if e.g., the noise were correlated to the signal.

Remark 7. The classical PCA has the same eigenvector α D if the noise is isotropic, i.e., white and of same variance in every dimension.

The paper (2) presents an optimization procedure to find the eigenelements.

Proposition 8. The asymptotic signal-to-noise ratio after projection using PCA is equal to

α D 4 2 (α D ) t Σα D .
Proof. After projection on the (asymptotic) eigenvector α D , the leakage becomes: remains centered. Its variance is equal to the expectation of its square:

(α D ) t α D Y q (k )+ (α D ) t N D q . The projected signal is ((α D ) t α D )Y q (k ). The projected noise is (α D ) t N D q , which 2
Var((α D ) t N D q ) = E (α D ) t N D q 2 = E (α D ) t N D q (N D q ) t α D = (α D ) t E N D q (N D q ) t α D = (α D ) t Σα D .
Therefore,

SNR PCA = Var(((α D ) t α D )Y q (k )) Var((α D ) t N D q ) = Var( α D 2 2 Y q (k )) (α D ) t Σα D = α D 4 2 (α D ) t Σα D .
Example 2. For white noise (Sec. 2.3.1)

SNR PCA = D d=1 α 2 d 2 D d=1 α 2 d σ 2 d . ( 2
SNR PCA = D d=1 α 2 d σ 2 1 1 + 2 D d=1 α 2 d D-1 d=1 ρ d D-d d =1 α d α d +d . (2.17)
We can now compare the performance of the asymptotic PCA to the optimal dimensionality reduction.

Theorem 2.4.1. The SNR of the asymptotic PCA is smaller than the SNR of the optimal dimensionality reduction.

Proof. By assumption the noise covariance matrix is symmetric positive definite, hence there exists a matrix Σ 1/2 , which is such that Σ 1/2 Σ 1/2 = Σ. By Cauchy-Schwarz inequality,

Σ -1/2 α D | Σ 1/2 α D 2 ≤ Σ -1/2 α D 2 2 • Σ 1/2 α D 2 2 .
Therefore,

SNR PCA = ((α D ) t α D ) 2 (α D ) t Σα D ≤ (α D ) t Σ -1 α D = SNR.
Corollary 4. The asymptotic PCA has the same SNR as the the optimal dimensionality reduction if and only if α D is an eigenvector of Σ. In this case, both dimensionality reductions are equivalent.

Proof. Equality holds in Theorem 2.4.1 if and only if there exists a nonzero real number λ such that Σ 1/2 α D = λΣ -1/2 α D , i.e., Σα D = λα D , i.e., α D is an eigenvector of Σ.

In this case, the optimal protection is on the vector Σ -1 α D = 1 λ α D , which is proportional to the projection vector belonging to the asymptotic PCA. In contrast, if σ 1 = • • • = σ D = σ, the covariance matrix has only one eigenvalue, namely (1, 1, • • • , 1), which has multiplicity D. Thus, for white homoscedastic noise, PCA is asymptotically optimal if and only if

α 1 = • • • α D = α, that is, the SNR is the same for each sample.
Still in the case of white noise, we can lower bound the SNR of the asymptotic PCA: Lemma 1. For white noise, the SNR of the asymptotic PCA is not less than the worst SNR among the samples, but can be strictly smaller than the higher SNR among the samples.

Proof. We have

Linear Discriminant Analysis (LDA)

LDA has been introduced in side-channel analysis in [START_REF] Standaert | Using Subspace-Based Template Attacks to Compare and Combine Power and Electromagnetic Information Leakages[END_REF]. With respect to inter-class PCA, it computes the eigenvectors of the matrix S -1 w S b , where:

• S w is the within-class scatter matrix, asymptotically equal to Σ, and

• S b is the between-class scatter matrix, equal to α D (α D ) t .
We have the following spectral characterization of the asymptotic LDA:

Proposition 9. Asymptotically, LDA has only one principal direction, namely the vector

Σ -1 α D .
Proof. The matrix S -1 w S b = Σ -1 α D (α D ) t has rank one. Indeed, α D (α D ) t has rank one, and multiplying by an invertible matrix (namely Σ -1 ) keeps the rank unchanged. Since

(Σ -1 α D (α D ) t )Σ -1 α D = Σ -1 α D ((α D ) t Σ -1 α D ) = (α D ) t Σ -1 α D × Σ -1 α D ,

OPTIMAL DIMENSIONALITY REDUCTION WITH PROFILING.

Σ -1 α D is the unique eigenvector with corresponding eigenvalue (α D ) t Σ -1 α D > 0. This eigenvalue is equal to the SNR of the asymptotic LDA.

By Corollary 2, the SNR of the asymptotic LDA is equal to the SNR of the optimal dimensionality reduction, denoted by SNR. In fact, we have the following.

Theorem 2.4.2. The asymptotic LDA computes exactly the optimal dimensionality reduction.

Proof. Compare Theorem 2.2.1 with Proposition 9: in both cases, the projection vector is collinear with Σ -1 α D .

Numerical Comparison Between Asymptotic PCA and LDA

Numerical comparison between asymptotic PCA and LDA is given in Fig. 2

Practical Validation

In this section, we investigate real traces. Experiments are carried out on the DPA contest

α D = x D (y) t y(y) t .
Proof. The goal (minimizing the fitting error) is similar to that of the optimal distinguisher, namely maximize the probability of p N D (x Dα D y) (Eqn. (2.4)). But in the context of characterization, the correct key is known. Therefore, we wish to minimize in α D and Σ the following objective function:

objective(α D , Σ) = Q q=1 x D q -α D y q (k ) t Σ -1 x D q -α D y q (k ) , (2.19)
which reminds of Eqn. (2.7) (except that now, the key k = k is known). We use the notation

( α D , Σ) = argmin (α D ,Σ) objective(α D , Σ).
We fix Σ and minimize only on α D . The gradient of objective(α D , Σ) w.r.t. (α D ) t writes:

∂ ∂(α D ) t objective(α D , Σ) = Q q=1 -2y q (k ) Σ -1 x D q -y q (k )Σ -1 α D .
(2.20)

OPTIMAL DIMENSIONALITY REDUCTION WITH PROFILING.

The objective function is extremal in α D if and only if its derivative is equal to zero at this point. Let y be an abbreviation for y(k ). This condition takes the form of a normal equation

α D = Q q=1 y q x D q Q q=1 y 2 q = x D (y) t Y Q (y) t . (2.21)
where the numerator is the inter-covariance matrix of x D and y, and the denominator is the covariance matrix of y.

Interestingly, the most likely value α D of α D does not depend on the noise covariance matrix.

As N D = x Dα D y has zero mean, the latter can be evaluated on its own as the well-known unbiased estimator of Σ:

Σ = 1 Q-1 (x D -α D y)(x D -α D y) t . ( 2
Σ = 1 Q-1 x D -x D (y) t y Y Q (y) t x D -x D (y) t y Y Q (y) t t = 1 Q-1 x D I Q,Q - (y) t y Y Q (y) t 2 (x D ) t (2.23) = 1 Q-1 x D I Q,Q - (y) t y Y Q (y) t (x D ) t (2.24) = 1 Q-1 x D (x D ) t - x D (y) t y(x D ) t Y Q (y) t .
In Eqn. (2.23), I Q,Q denotes the Q × Q identity matrix, and we use in Eqn. 2.24 the fact that the matrix

I Q,Q -(y) t y/(Y Q (y) t
) is idempotent, i.e., equal to its square.

Remark 9. We have the following remarkable identity:

x D (x D ) t = α D ( α D ) t y(y) t + (Q -1) Σ.
This equation is the non-asymptotic version of Proposition 6.

Computation of SNRs on the AES Traces from DPA Contest v2 Last Round

The values α D and Σ are represented in Fig. 2.2. We obtain: Interestingly, one can see in Fig. 2.2 that the noise is locally autoregressive, for instance between samples 107 and 117.

• max D d=1 α 2 d / Σ d,d = 1.69 • 10 -3 (no dimensionality reduction) • SNR PCA = (( α D ) t α D ) 2 ( α D ) t Σ α D = 1.36 • 10 -3 (PCA)

Conclusions and Perspectives

Dimensionality reduction is common practice in side-channel analysis. This pre-processing technique has many virtues, such as an elegant multivariate description of the leakages, the concentration of information which reduces the required number of measurements to extract the key, and the increase of computational efficiency. Nonetheless, as any processing, dimensionality reduction can only reduce some information.

Using a mathematical approach, we have shown that dimensionality reduction is actually part of the optimal attack. This proves rigorously that dimensionality reduction can be achieved without loss in terms of attack success probability in extracting a secret key. As it turns out, the optimal dimensionality reduction consists in a linear projection of the trace samples.

We have also shown that the linear discriminant analysis asymptotically achieves the same projection, and hence becomes optimal as the number of traces increases. When the various samples are weakly correlated, we have found that PCA is nearly equivalent to the optimal 2. OPTIMAL DIMENSIONALITY REDUCTION WITH PROFILING.

dimensionality reduction and to LDA. Thus, in realistic contexts, state-of-the-art dimensionality reduction techniques are actually close to the optimal method.

Finally, we show how to estimate the model parameters (modulation vector α D and noise covariance matrix Σ), and compute them on a real traces. An SNR gain factor of 7 can be obtained with respect to sample-wise SNR, which stresses the practical interest of dimensionality reduction.

As a perspective, we note that it should also be possible to obtain similar results when the noise is non-Gaussian (e.g., uniform). It is also desirable to compare dimensionality reduction based on linear projections to machine-learning techniques which are also multidimensional, such as SVM, random forests, K-means, etc.

CHAPTER 3

Dimensionality Reduction a case study in presence of masking.

The results presented in this chapter have been published in collaboration with Jean-Luc Danger, Sylvain Guilley, Annelie Heuser, and Yannick Teglia in the international conference on Security, Privacy and Applied Cryptography Engineering (SPACE 2014) [START_REF] Bruneau | Boosting Higher-Order Correlation Attacks by Dimensionality Reduction[END_REF]. Multi-variate side-channel attacks allow to break higher-order masking protections by combining several leakage samples. But how to optimally extract all the information contained in all possible Ω-tuples of points? In this chapter, we introduce preprocessing tools that answer this question. We first show that maximizing the higher-order CPA coefficient is equivalent to finding the maximum of the covariance. We apply this equivalence to the problem of trace dimensionality reduction by linear combination of its samples. Then we establish the link between this problem and the Principal Component Analysis. In a second step we present the optimal solution for the problem of maximizing the covariance. We also theoretically and empirically compare these methods. We finally apply them on real measurements, publicly

Introduction

In some particular masking implementations, the two shares [START_REF] Nikova | Secure hardware implementation of nonlinear functions in the presence of glitches[END_REF] depending on the same mask leak at different time samples (e.g., in software). Second-order attacks that combine two different time samples are called bi-variate SCA. When the masking scheme uses Ω shares, multi-variate SCA are still able to reveal the secret key by combining leakage samples corresponding to each of the Ω shares. Note that, depending on the implementation and the measurement setup each share may leak in multiple samples.

To enhance the results of SCA several preprocessing tools can be used. In the case of bi-variate SCA it is particularly interesting to take into account all the information spread over the time. Indeed, the number of possible pairs increases quadratically in the number of leakage In order to break (Ω -1)-order masking schemes an attacker should therefor combine first the leakages of each share, this leads to an increase of the number of exploitable samples. In a second times to increase the success of its attack an attacker can exploit all theses leakages in one by combining them. It will be the case when dimensionality reduction methods are applied.

Many methods have been presented in the area of SCA to combine the information spread over time: the Principal Component Analysis (PCA) for dimensionality reduction (2) for Template attacks (31) (see Chapt. 2 for an analysis of dimensionality reduction in a Template

Attacks scenario) but also as a preprocessing tool (5) for DPA [START_REF] Paul | Differential Power Analysis[END_REF]. Recently in (70) Hajra and

Mukhopadhyay present an approach based on match filters to find the optimal preprocessing.

Other methods have been designed to combine samples from different acquisitions ((154, 158)).

Introduction

Additionally, PCA has also been used as a distinguisher in [START_REF] Souissi | First Principal Components Analysis: A New Side Channel Distinguisher[END_REF]. Some other methods could be applied like the Canonical Correlation Analysis (120) to improve CPA [START_REF] Brier | Correlation Power Analysis with a Leakage Model[END_REF]. Interestingly, all these methods lead to a dimensionality reduction.

Another approach to improve the efficiency of SCA is to find the optimal model. A linearregression approach may be used. In (120) Oswald and Paar introduce optimization algorithms to determine numerically the optimal linear combination before CPA. By choosing a different objective we can give a formal expression for the result of the optimization problem, and then have an optimal method without any utilization of sophisticated optimization algorithms that would require "parameter settings", which could be costly in time. Still, we notice that the approach in (120) and our could be advantageously combined.

Contributions.

In this chapter we tackle the question how to optimally combine the information spread over multiple time samples, for HOCPA attacks of arbitrary order? Namely we extend the results of Chapt. 2 in a context of less powerful attacker and attacks against protected implementations.

Specifically in this chapter we assume that the attacker is not able to completely profiled the leakage function. We present the optimal preprocessing method and express it as a generic synthetic formula. By linking the PCA to the problem of maximizing the result of the CPA we are able to evaluate the presented method. We compare these two methods theoretically and prove that they are optimal under some assumptions. We then compare these methods empirically as preprocessing tools to boost 2O-CPA attacks on a first-order masking scheme. In particular, we test these methods on real measurements (DPA contest v4 ( 169)). In summary, we show that taking into account all possible pairs of leakage points will significantly improve the effectiveness of 2O-CPA, in one attack.

Outline of the chapter.

The rest of the chapter is organized as follows. In Sect. 3.2 we present our case study and a theoretical comparison between PCA and the covariance method as a method to obtain the optimal preprocessing for second-order CPA. The attacks are then applied on a real masked implementation in Sect. 3.3. Sect. 3.4 provides another case study to apply these methods as preprocessing tools. Finally, conclusions and perspectives are drawn in Sect. 3.5.

DIMENSIONALITY REDUCTION A CASE STUDY IN PRESENCE OF MASKING.

3.2 Theoretical optimal preprocessing function

Case study

Let us assume that each measurement trace can be seen as a vector of points. So the leakage of the measurements can be defined as:

X = X (d) 1≤d≤D where X (d) = S (d) + N (d) , S (d) = Ψ (d) (g (k , T, R))
being the part of the leakage which is linked to the internal operation processed on the target component and N (d) being the noise that assumed to be independent of S (d) . It can be noted that, we simply refer to interval 1, D as D, whenever there is no risk of confusion.

It can also be assumed that these traces are centered and also reduced, i.e., E X (d) = 0 ∀d and Var X (d) = 1 ∀d. Note that, the attacker is always able to center by removing the empirical mean and reduce by dividing the empirical standard deviation.

Let Z be the internal variable (depending on the sensitive variable) manipulated during the algorithm and let Ψ defines the leakage model. In the case of CPA, a transformation of the initial data (preprocessing) may increase the correlation coefficient. To consider all information contained in X an option would be to use a linear transformation as a prepossessing. Note that, combining all points by a weighted sum leads to a dimensionality reduction. More precisely,

max α |ρ α • X, Ψ(Z) |, (3.1)
where ρ is the Pearson coefficient, α is a vector in R D and • the scalar product.

Remark 10. The solution of max

α |ρ α • X, Ψ(Z) | is also a solution of max α ρ α • X, Ψ(Z) 2 .
Remark 11 (EIS (Equal Images under the Same key) assumption ( 147)). The only part of the correlation that allows to distinguish the key is the covariance.

After the preprocessing we do not need to normalize by the variance of the traces, because we compare key guesses between each other for a given time sample not on a direct scale. So, as seen in Remark 11 the normalization by the variance does not impact the way we distinguish the key. Thus, we can simply focus on maximizing the following equation:

max α =1 Cov α • X; Ψ(Z) 2 . (3.2)
As the covariance is not bounded we introduce the constraint α = 1 where • is the Euclidean norm, namely α = √ α • α.

In this section we assume that the attacker has a "learning device" with a fixed key on which he is unrestricted in the number of acquisitions, which is typically more than the required 3.2 Theoretical optimal preprocessing function number to successfully perform the attack. As a consequence we can reasonably assume that the attacker knows the key on the learning device and he is able to identify the zones of interest in 1, D where the internal variable leaks. Moreover, he is able to estimate the weights of the linear combination (see Eq. (3.2)) on the learning device. In the rest of this study we call this step the "learning phase". In the final step the attacker targets another device that is expected to leak in a similar way as the learning one. However, on the device under attack he is no longer able to acquire an unlimited amount of traces. In particular, in this "attack phase" his main goal is to retrieve the secret key using only the minimum number of traces.

Principal component analysis

A classical way to recombine information with linear combinations is to apply PCA (79).

Remark 12. In general, most of the variance lays within a few dimensions (i.e., much less than D).

Proposition 11. The solution of the problem in Def. 18 is the D eigenvectors of X associated to the D maximal eigenvalues.

Proof. The proof can be found in [START_REF] Jolliffe | Principal Component Analysis[END_REF].

As the problem of maximizing the covariance depends on the expected leakage model the preprocessing is defined such that it takes Ψ(Z) into account. This implies that the given preprocessing methods are model-dependent. We can explicit the Proposition 11:

Proposition 12. If we link our measurements X to their conditional expectations E X| Ψ(Z) knowing a model Ψ(Z), then the PCA yields the principal direction:

max α =1 Var α • E X| Ψ(Z) .
This result means that the eigenvector of the largest eigenvalue is the projection that maximizes the inter-class variance.

Proof. Let Ψ 1 , Ψ 2 , . . . , Ψ N the values that Ψ(Z) can take. Then, the lines of matrix X are

E X| Ψ(Z) = Ψ 1 , E X| Ψ(Z) = Ψ 2 , . . ., E X| Ψ(Z) = Ψ N . Apply Proposition 11.

Preprocessing on modulated side channel traces

In this section we investigate the behaviors of preprocessing methods on modulated side channel traces. Let us first recall the definition of modulated traces given in Def. 9:

DIMENSIONALITY REDUCTION A CASE STUDY IN PRESENCE OF MASKING.

Definition 38 (Modulated Traces). Let us now define a modulated trace as a trace in which each time sample can be expressed as a modulation of a model (static in time) plus an independent noisy part:

X = β (d) Ψ(Z) + N (d) d≤D = β • Ψ(Z) + N (d) d≤D , (3.3)
where β is a vector in R D and each N (d) is drawn from an independent identical distribution N.

In specific, the variance of the noise does not depend on the time sample d ≤ D.

Theorem 3.2.1. In the case of modulated traces the solution of PCA is equivalent to maximizing the covariance (Eqn.

(3.2)). More precisely, if X = β (d) Ψ(Z) + N (d) d∈D then α ∈ argmax α =1 Cov α • X; Ψ(Z) 2 ⇐⇒ α ∈ argmax α =1 Var E α • X| Ψ(Z) .
Proof. The proof is given in Appendix A.1.

Notice that, in Theorem 3.2.1, we consider that many vectors α can maximize the covariance: so, the return value of the argmax operator is a set.

In a particular case of Theorem 3.2.1 we can explicitly describe α.

Lemma 2. If α and β are linearly dependent, we have:

β β ∈ argmax α =1 Cov α • X; Ψ(Z) 2 . (3.4)
Proof. The proof is given in Appendix A.2.

After projection into the new reduced space the covariance matrix will be zero everywhere except at (0, 0). Moreover, all the variance should be contained in the first principal direction, thus, we do not need to take the other eigenvectors into consideration.

As β does not depend on a particular model we also maximize the covariance for wrong keys in the same proportion as the covariance for the good key. Thus we do not change the way we distinguish the good key from the wrong ones (the relative distinguishing margin is unchanged ( 181)). However, the dimensionality reduction leads to an improvement of the attack by increasing the signal-to-noise ratio (SNR). We define the SNR as the variance of the signal divided by the variance of the noise. This definition of SNR coincides with the Normalized Inter-Class Variance (NICV (12, 13)).

Theoretical optimal preprocessing function

Remark 13. In Lemma 3 the traces are modulated (see Def. 9) as a consequence the noise is independent in the time samples. The assumption of modulated traces is a strong assumption, nevertheless the noise can always be standardized by multiplying the traces with the inverse of the noise covariance matrix.

Proposition 13. If the noise N (d) is i.d. for all d, then the signal-to-noise ratio is maximum after the projection:

max d∈D Var β (d) Ψ(Z) Var [N] ≤ max α =1 Var α • E X| Ψ(Z) Var [N] .
Proof. By definition of α we have max

d∈D Var β (d) f (Z) ≤ max α =1
Var α • E X| Ψ(Z) . Besides, by lemma 3, the numerator of the SNR does not depend on our preprocessing, since is satisfies α = 1.

Remark 14. In the case of modulated traces the PCA gives the solution of a matched-filter (109).

Covariance vector as a preprocessing method

In the general case when the model is not known or in the presence of noise, the variance may not only be contained in the first eigenvector [START_REF] Batina | Getting more from PCA: first results of using principal component analysis for extensive power analysis[END_REF]. Therefore, it may be useful to also take the other directions of the PCA into account. Note that, we still obtain an optimal function to reduce the dimensionality before conducting a CPA under the same leakage model assumption.

Proposition 14 (Covariance method).

   Cov X (d) ; Ψ(Z) Cov X (d) ; Ψ(Z) d∈D    d∈D ∈ argmax α =1 Cov α • X; Ψ(Z) 2
Proof. The proof is given in Appendix A.3.

So, the normalized covariance is the optimal preprocessing method to maximize the value of the covariance when using linear combinations of traces points. In the rest of this study we call this method the "covariance method" and the result the "covariance vector".

Remark 15. Note that, the model of the actual leakage of the traces is not used in the proof of Appendix A.3. The results are therefore applicable for any leakage model such as the one presented in (67).

DIMENSIONALITY REDUCTION A CASE STUDY IN PRESENCE OF MASKING.

Discussion

The previous subsection shows that the projection of the differential traces on the covariance vector gives a solution to the problem of maximizing the covariance after dimensionality reduction (i.e., after having learned the best linear form). This method is better than the state-of-the-art, where each tuple of samples is processed on its own (see the big picture in Fig. 3.1); it can be seen as a generalization to higher-order attacks of [START_REF] Hajra | On the Optimal Pre-processing for Nonprofiling Differential Power Analysis[END_REF]. Some other preprocessing tools have been proposed to reduce the dimensionality and enhance the quality of the CPA. The PCA [START_REF] Batina | Getting more from PCA: first results of using principal component analysis for extensive power analysis[END_REF] is a known way to preprocess the data to reduce the dimension and increase the efficiency of attacks. As defined in Sect. 3.2.3, PCA is directly linked to the maximization problem, which is also underlined by our empirical results given in Sect. 3.3.

Oswald and Paar showed in (120) that the best linear combination ("best" in the sense of separating the highest peaks from the nearest rival) can be approached by numerical resolutions.

The model presented in [START_REF] Hajra | On the Optimal Pre-processing for Nonprofiling Differential Power Analysis[END_REF] is not totally applicable to our study case. If we are in the case of modulated traces, the expectation over each sample of the combined traces could be null. In this case the method presented is not directly suitable.

The point of this study is not to exhibit a better method for dimensionality reduction but to show that we can solve this problem in an easier way by using the vector of covariance.

Other preprocessing methods can be used before any dimensionality reduction such as reduction filtering using a Fourier or a Hartley transform [START_REF] Belgarric | Time-Frequency Analysis for Second-Order Attacks[END_REF]. However, when the transformation is linear and invertible, the covariance method applies in a strictly equivalent way. The next subsection clarifies this point on the example of the Fourier transform.

Time vs Frequency domains

Let X a signal in time domain, i.e., X = (X (d) ) d∈D . The representation of X in the frequency domain is the discrete Fourier transform F(X).

Definition 39 (Discrete Fourier transform). Let ß be a square root of -1 in C. The discrete Fourier transform of X is a vector F(X) of same length, defined as

F(X) f = d∈ 1,D X (d) • e -2πßf d/D
, for all f in the interval 1, F (where F = D).

Proposition 14 can also be applied on F(X) instead of X. We then have the following Corollary.

Corollary 5 (Covariance method in the frequency domain). The covariance method in frequency domain yields covariance vectors equal to the Fourier transform of the covariance vectors in the time domain.

Leakage D α = cov(X; Ψ(Z)) ||cov(X; Ψ(Z))|| Correlation |ρ(X; Ψ(Z))| Distinguishers:
Projection by linear combination

(1') max k,d∈ 1,D 1 × 1,D 2 max k ρ(α • X; Ψ(Z)) (0') (1') α • X (scalar) ρ(X (d) ; Ψ(Z)) D 1 D 2 (1) (2)
d 1 d 2 1 1 d 1 d 2 d 2 d 1
(2')

Figure 3.1: Big picture of the "covariance method". The usual 2O-CPA computes a correlation for each pair (d1, s2) of leakage (step (1)), and then searches for a maximum over the keys and the time instances (step (2)). Our new method obtains a "covariance vector" (termed α) on a "learning device" (step (0')), and then first projects the leakage X on α (step (1')), before looking for the best key only while maximizing the distinguisher (step (2')). Notice that the model Ψ(Z) depends implicitly on the key guess k.

Proof. We have α • F(X) = F(α) • X, by interversion of the sums on f and d. Besides, Parseval's theorem states that ||F(α)|| 2 = ||α|| 2 . Thus, the application of Proposition 14 on F(X) instead of X yields F(α), where α are the covariance vectors obtained in the time domain.

Empirical results

In Sect. 3.2 we defined two preprocessing methods (the PCA and the "covariance method").

They were described in general, but can also apply to second-order CPA; the only difference is that the interval 1, D where samples live is replaced by the Cartesian product 1,

D 1 × 1, D 2 ,
where D 1 and D 2 are the window lengths containing the leakage of the two shares. Accordingly, the leakage X is the suitable combination (e.g., the centered product ( 133)) of samples from each window, which is reflected in the model (See for instance Eqn. (3.5) and (3.6)). We

DIMENSIONALITY REDUCTION A CASE STUDY IN PRESENCE OF MASKING.

will now compare these two methods on real measurements. These methods combine in one point the information spread over several points. The more samples to combine, the more the dimensionality reduction increases the success of the attacks.

Implementation of the masking scheme

To evaluate these two methods we use the publicly available traces of the DPA contest v4 [START_REF]DPA Contest[END_REF], which uses a first order low-entropy masking protection applied on AES called Rotating S-box Masking (RSM). In RSM only sixteen Substitution boxes (S-boxes) are used and all the sixteen outputs of SubBytes are masked by a different mask. We take great in this chapter to exploit second-order leakage (in particular, we avoid the first-order leakage identified by Moradi et al. ( 112)). Moreover, the same mask is used for the AddRoundKey operation where it is XORed to one plain-text byte T and in the SubBytes operation where it is XORed with the S-box output depending on another plain-text byte T . As a consequence a bi-variate CPA can be built by combining these two leaks knowing T and T . The leakage model in this case is given by:

Ψ(Z) = E [(HW[T ⊕ M ] -4) • (HW[Sbox[T ⊕ K] ⊕ M ] -4) |T, T , K] , (3.5)
where T , T , K are two bytes of the plaintext and a byte of the key respectively, together noted Z = (T, T , K), and where HW is the Hamming weight function and the expectation is taken over M . We denote this combination as (XOR, S-Boxes).

Moreover, we also define another way to combine points in order to compensate the mask. As only sixteen different masks in RSM are used, also a link between the masks used at the output of the S-boxes exists. Accordingly, the combination of the outputs of two different S-boxes are not well balanced and we could consider an attack depending on two different S-Boxes which use two different masks. In this case the leakage model for the bi-variate CPA is:

Ψ(Z) = E [(HW[Sbox[T ⊕ K] ⊕ M ] -4) • (HW[Sbox[T ⊕ K ] ⊕ M ] -4) |T, T , K, K ] . (3.6)
In this equation, which we denote as (S-Boxes, S-Boxes), T and K (resp. T and K ) are the plain-text and key bytes entering the first (resp. the second) S-Box, and Z is a shortcut for the quadruple (T, T , K, K ). We notice that there exists a deterministic link between M and M ;

M and M belong to some subset {m 0 , m 1 , . . . , m 15 } of F 8 2 . We assume that M enters S-box 0 ≤ i ≤ 15 and M S-box 0 ≤ i ≤ 15. Then when M = m offset for some 0 ≤ offset ≤ 15, we have that M = m offset+i -i mod 16 .

Empirical results

Leakage analysis

We assume that the adversary is able to identify the area where the two operations leak during the "learning phase". In order to analyze the leakage of the two operations, we first calculate the covariance of the traces when the mask is known using 25000 measurements. Figure 3.2a presents the absolute value of the covariance between the points where the mask is XORed with the plain-text and the leakage model HW[T ⊕ M ⊕ K] -4. The covariance is computed for all key guesses K, where the wrong keys are plotted in gray and the correct key in red. Note that, as we target a XOR operation the maximum of the absolute value of the covariance is reached for two key guesses, namely the correct one and its opposite. It is quite clear, in Fig. 3.2a, that the traces are reasonably modulated (as per Def. 9); consequently, the relative distinguishing margin is constant over all the whole trace (as underlined in Sec. 3.2.3).

In the sequel, we use as leakage for the first share HW

[T ⊕ M ] -4 instead of HW[T ⊕ M ⊕ K] -4.
As the second share is key-dependent, this choice allows us to restrict ourselves to one key search instead of two. In both cases the mask leaks over several points; 50 samples represent less than 1 clock cycle.

In this case the leakage is not uniformly spread over the points, thus it is reasonable to use a weighted sum to reduce the dimensionality of the data.

As the two leakages do not depend on the same operations their shapes are different.

Interestingly, the distance between the correct key (red) and the next rival (grey) is much smaller in Figure 3.2a than in Figure 3.2b, Indeed the covariance plotted in Figure 3.2a is computed using a leakage depending on AddRoundKey, whereas the covariance plotted in Figure 3.2b is computed using a leakage caused by SubBytes. More precisely, the second plot corresponds to a time window when the value of the S-box output is moved during the ShiftRows operation that follows SubBytes. It can be noticed that the leakages of two different S-boxes indeed differ. The reason of this difference is that the two leakages are not due to the execution of the same operations.

Experimental protocol

In this experiment we select two windows of 50 points corresponding to the leakage of the two shares. Then all possible pairs of points have been combined using the centered product function [START_REF] Prouff | Statistical Analysis of Second Order Differential Power Analysis[END_REF]. In all the experiments, the preprocessing method and the 2O-CPA are applied on these "combined" traces. We compare 2O-CPA with and without preprocessing. We used the 50000 first traces of the DPA contest v4 for the learning phase and the remaining for the attack phase. To compute the success rate we repeated the experiment as many times as we could due to the restricted amount of traces.

Note that, several attacks using profiling or semi-profiling have been published in the Hall of Fame of the DPA contest v4. Most of these attacks are specially adapted to the vulnerabilities of the provided implementation or the particularities of RSM. However, our proposed preprocessing tools do not particularly target RSM, moreover, they are generic and could be applied to any masking scheme leaking two shares. first eigenvector) and the covariance method (which returns the covariance vector). The larger the value on the z-axis of Fig. 3.5 and 3.7, the higher the contribution (weight) of this point.

The axes "leakage 1" and "leakage 2" represent the part depending on the two leakages of XOR (Fig. 3.2a) and S-box (Fig. 3.2b) operations in the combined traces. We can see in Figure 3.5 that the two methods highlight the same points of the combined traces and have the same shape (approximately the same values). Thus, the two methods give similar results in terms of success rate, which is confirmed by Figure 3.4.

As it can be seen in Figure 3.6, in case of the (S-Boxes, S-Boxes) combination we need around 275 traces to reach 80% of success for the 2O-CPA after the two preprocessing methods, while the raw 2O-CPA needs around 550 traces to succeed. So, using the preprocessing method decreases the number traces to perform the attack by 50%. It can be seen that the two methods yield apparently exactly the same results, which means that we are precisely in the framework of Theorem 3.2.1: the display traces that are almost perfectly modulated by one static leakage model.

One explanation of the effectiveness of the preprocessing can be found in Figure 3.7. There are much more leaking points in the same window size when we combine two S-boxes. It can be seen in Sect. 3.3.5 that another explanation can be the fact that when we apply these preprocessing methods the attacks are less sensitive to the noise.

How is the preprocessing linked to the noise?

We have theoretically shown in Proposition 13 that the presented preprocessing methods improve the SNR. We now empirically verify this results. In each point we add Gaussian noise to mimic real noisy measurements. We perform this experiment on the same points and with the same model as used for Figure 3.4. Figure 3.8a shows that using preprocessing methods improves second-order CPA in presence of noise. In this case we added Gaussian noise with a standard deviation of 3. The attacks after preprocessing need around 225 measurements to reach 80% of success whereas the 2O-CPA needs more than 550 measurements. Thus, preprocessing leads to a gain over 50%. As shown in Figure 3.4 the gain was close to 30% without noise.

In Figure 3.8b we can see that for Gaussian noise with a standard deviation of 5 the gain is more than 75%. Indeed the 2O-CPA after preprocessing needs around 250 traces reach 80% of success rate whereas for 2O-CPA 1000 measurements are not sufficient.

So this kind of preprocessing by dimensionality reduction is well designed against noisy implementation where the noise is not correlated with the time or the data.

On the fly preprocessing

We have defined a case study when the attacker owns a "learning device". As a consequence he is able to acquire a sufficient number of measurements to well estimate the covariance matrix for As seen in Subsect. 3.3.4 even for a small number of traces for the learning phase we have a significant improvement when we use preprocessing methods. We therefore evaluate these tools also as "on the fly" preprocessing methods.

Case study

We now model a less powerful attacker who does not have a "learning device" and estimates the value of the coefficient of the linear transformation directly on the traces used for the attack. Because the key is unknown the preprocessing method has to be computed for each key hypothesis. Finally, the adversary applies the covariance between the transformed data and the model depending on the key hypothesis. In this experiment we use the 10000 first traces of the DPA contest to compute the success rate which results in 25 repetitions.

Empirical results

Figure 3.9 illustrates the success rate after preprocessing for different sizes of the learning set for PCA (green) and the covariance vector (red). One can observe that the covariance method performs better than PCA when a low number of traces is used during the learning phase, accordingly, this method is a good choice as a "on the fly" preprocessing method. The reason why the PCA method needs more measurements for the learning than the covariance method to reach its maximum efficiency during the attack phase could be the fact that the covariance matrix (see the term t XX in Def. 18) needs more traces to be well estimated. Figure 3.10 shows that with the "on the fly" preprocessing we can perform 2O-CPA using 225 measurements. This represents a gain of 18% compared to raw (sample-wise) 2O-CPA.

Conclusions and Perspectives

In this chapter we presented the covariance method as an optimal preprocessing method for second-order CPA. By using all possible leakage points our method improves the efficiency of the attacks and as the number of combined leakage points grow quadratically, thus our preprocessing method is well adapted for bi-variate CPA. We further theoretically linked the PCA to the problem of maximization of the covariance. We demonstrated theoretically the result of the covariance method to be the optimal linear combination for maximizing the covariance and underlined empirically that this method improves the result of bi-variate CPA.

Compared to 2O-CPA, the attack based on the optimal covariance method is significantly improved, particularly in presence of noise and when the number of leaking points is important. This is partly explained by the fact the optimal covariance considers all the relevant sampling points, whereas the 2O-CPA considers only the best pair of samples and does not exploit the other interesting pairs.

We have also shown that the optimal covariance method is more efficient than PCA when the learning phase is performed on the fly. All the results have been validated by experiences on real traces corresponding to masking implementation of the DPA contest v4. As a consequence dimensionality reduction by linear combination is well adapted to the case of multi-variate CPA.

Moreover, the higher the order of masking, the more efficient the attack after preprocessing.

We could extend the previous results on other implementations which are less favorable to attacker, e.g., with more noise. Also we plan to compare the method presented in this chapter and the method presented in (70) in these cases.

Conclusions and Perspectives

Following the results of the previous chapter we could extend these results in a profiled scenario. In this context we could look at the optimal dimensionality reduction in terms of success rate in the case of masking. Following the notations introduced in the introduction we will look at the optimal dimensionality reduction in the case of bi-variate attacks. Then a generalization could be done to extend this result at any order. tables. This attack is highly multi-variate as it exploits many different leakages depending on many different variables. As a consequence following our nomenclature this attack has a high parameter δ. Based on these results we investigate in this chapter the optimal attack in this context. We formally compute the optimal distinguisher against table recomputation masking scheme when the attacker has a full knowledge of the leakage function. This new distinguisher will provide better result in term of probability of success than the attacks of the state-of-the-

Part II

Multivariate Leakages of a Masking Scheme with Table Recomputation

OPTIMAL DISTINGUISHER AGAINST MASKING TABLE

art. Moreover our analysis gives better understanding on the behavior of the attack. Indeed we show that for high noises the optimal distinguisher is closed to a sum of several 2O-CPA. As a consequence this new attack is closed to a highly multi-target attack.

Algorithm of masking tables

In the implementation of masking schemes, it is particularly challenging to compute non-linear parts of the algorithm, such as for example the S-Box of AES (a function from n bits to n bits).

To solve this difficulty different methods have been proposed which can be classified in three categories [START_REF] Maghrebi | A First-Order Leak-Free Masking Countermeasure[END_REF].

• Algebraic methods [START_REF] Blömer | Provably Secure Masking of AES[END_REF][START_REF] Rivain | Provably Secure Higher-Order Masking of AES[END_REF]. The outputs of the S-Box will be computed using the algebraic representation of the S-Box.

• Global Look-up Table [START_REF] Prouff | A Generic Method for Secure SBox Implementation[END_REF][START_REF] Standaert | The World is Not Enough: Another Look on Second-Order DPA[END_REF] method. A table is precomputed off-line for each possible input and output masks.

• The principle of masking tables is illustrated in Alg. 1. Instead of showing a complete masked AES, only the masked computation of AddRoundKey followed by SubBytes is shown.

We have indicated the words length of all data as n, typically, n = 8 bit for AES. Two random masks m and m are drawn initially from F n 2 and all the data manipulated by the algorithm will be exclusive-ored with one of the two masks.

Passing additively masked data through the Sbox is not obvious, as this operation is nonlinear. Therefore, the Sbox is recomputed masked, as shown on lines 2 to 5: a new table S , that has also size 2 n × n bits, is required for this purpose. It can be seen that the addresses are accessed sequentially in the ordinal order. In the Sbox precomputation step, the key byte k is not manipulated. The leakage only concerns the mask.

Then, the masked computation which involves the masked table follows, in lines 7 to 10.

Masking the plaintext is straightforward (see line 7). Key addition can be done safely as a 4.2 Classical Attacks second step, as the plaintext is already masked (see line 8). Of course, if the whole AES were to be evaluated, the demasking step (line 10) would be deferred till the end of the AES.

Algorithm 1: Beginning of a block cipher masked by Sbox precomputation input : t, one byte of plaintext, and k, one byte of key output : The application of AddRoundKey and SubBytes on t, i.e., S(t ⊕ k)

1 m ← R F n 2 , m ← R F n 2 //

Classical Attacks

We now consider the attack of a masking scheme using Sbox recomputation as described in [START_REF] Paul | Differential Power Analysis[END_REF].

It is noteworthy that the traditional approach to reduce the multiplicity of leakage samples by a combination C X : R d → R actually would fail in the setup of masking tables. Indeed, the combination functions are usually considered symmetric into its arguments, meaning that any swap of the inputs does not affect the combination. This (tacit) hypothesis has been made, for instance, for

• the absolute difference C ad (X) = |X (0) -X (1) | = |X (1) -X (0) |, and • the centered product C cp (X) = (X (0) -E X (0) )(X (1) -E X (1) ) = (X (1) -E X (1) )(X (0) - E X (0) ).
We assume here that the attacker applies the combination function on the leakages occurring

OPTIMAL DISTINGUISHER AGAINST MASKING TABLE

during the Sbox recomputation (see Alg. 1), i.e., the attacker gains 2 n leakages

X (0) = Ψ (0) (M ) + N (0) (4.1)
X (1) = Ψ (1) (M ⊕ 1) + N (1) (4.2) . . .

X (2 n -1) = Ψ (2 n -1) (M ⊕ (2 n -1)) + N (2 n -1) , (4.3)
and would apply 1 e.g., C ad (X) or C cp (X). Additionally, he measures the leakage

X (2 n ) = Ψ (2 n ) (T ⊕ k ⊕ M ) + N (2 n
) and finally combines it with the previous combined leakages as

C(X (2 n ) , C(X (0) , . . . , X (2 n -1) )).
Following the methodology in [START_REF] Prouff | Statistical Analysis of Second Order Differential Power Analysis[END_REF] and assuming an equal leakage function on each share2 , i.e., Ψ = Ψ

(0) = • • • = Ψ (2 n
) , the optimal function to combine the predictions would then be Of course, the Sbox precomputation masking scheme can be attacked by the classic means, that ignore the precomputation stage (i.e., lines 7 to 10 in Alg. 1 are already vulnerable alone).

C Y = E{ CX (C X (Ψ(M ), Ψ(M ⊕ 1), . . . , Ψ(M ⊕ (2 n -1))), Ψ(t ⊕ k ⊕ M ))} (4.4) = 1 2 n m∈F n 2 CX (C X (Ψ(m), Ψ(m ⊕ 1), . . . , Ψ(m ⊕ (2 n -1))), Ψ(t ⊕ k ⊕ m)) = 1 2 n m ∈F n 2 CX (C X (Ψ(m ⊕ k), . . . , Ψ(m ⊕ k ⊕ (2 n -1))), Ψ(t ⊕ m )) (4.5) = 1 2 n m ∈F n 2 CX (C X (Ψ(m ), Ψ(m ⊕ 1), . . . , Ψ(m ⊕ (2 n -1))), Ψ(t ⊕ m )). ( 4
More precisely, if several Sboxes are computed with different plaintext bytes and different key bytes, then collision attacks are possible. Also a second-order attack with a combination function can be achieved, for instance, between the addition of the mask to the plaintext and the Sbox call, i.e., between lines 7 and 9 in Alg. 1. Additionally, such second-order attack can also be 1 The centered product combination function naturally extends from two to any number of inputs. However, the absolute difference is inherently a binary combination function. A possible generalization in the context of arity d could thought of as: C ad (X) =

High Order Optimal Distinguisher for Precomputation Masking Tables

achieved between one leakage from the Sbox recomputation (say line 3 in Alg. 1. and line 8 (or preferably with line 9 for a better contrast ( 9)).

However, a better attack would consist in using altogether all the leakages from the Sbox recomputation with one (or more) of the samples used during the computation proper (starting from line 8, when the key is involved). One example of such strategy has been exposed in [START_REF] Tunstall | Masking Tables -An Underestimated Security Risk[END_REF], which we label as 2-stage CPA attack.

Definition 40 (2-stage CPA attack ( 174)).

2×CPA mt (x, t) = arg max k∈K ρ(x (2 n ) , y (2 n ) (t, k, m)), (4.7)
where ∀i m i is the mask that maximizes the correlation between x

(ω) i and y

(ω) i = ω ⊕ m i for ω ∈ [0, 2 n [.
This attack is a synergy between a horizontal and a vertical attack and as a consequence we will call these attacks Horizontal Vertical (HV) attacks. For each trace (separately ∀i), the first attack in Eq. (4.7) consists in recovering the mask during the precomputation (lines 2 to 5 in Alg. 1). Second, a regular CPA using a model in which both the plaintext t and the mask m are assumed as public knowledge is launched. Even if the mask m is not recovered correctly for each trace (since 2 n leakage samples during the precomputation can be seen as small), it can be expected that the value of the mask is recovered by the first horizontal attack probabilistically well enough for it to be biased, i.e., better guessed than random. This gives a rough idea of the proof of soundness for this attack.

Nonetheless, this attack is probably not the most efficient, as it uses separately the information available from the Sbox precomputation and from the leakage of the AES algorithm proper. The next subsection investigates the optimal attack and gives approximation for high and low noise.

High Order Optimal Distinguisher for Precomputation Masking Tables

When using masking tables (Alg. 1) the attacker first has all leaking samples during the precomputation, i.e., y

(ω) i = Ψ(ω ⊕ m) that are independent of i for 0 ≤ ω ≤ (2 n -1)
, and, second, the leakage arising from the combination of the mask m, plaintext t i and the key, i.e., y

(2 n ) i = Ψ(t i ⊕ k ⊕ m).
Thus, all terms for ω = 2 n do not depend on the key and the higher-order optimal distinguisher from Def. 20 can be further deduced.

OPTIMAL DISTINGUISHER AGAINST MASKING TABLE

Theorem 4.3.1 (OPT for masking tables). When Ψ :

F n 2 → R is known, N (ω) i
∼ N(0, σ 2 ω ) and i.i.d. across values of q and independent across the values of ω = {0, . . . , 2 n }, then the higher-order optimal distinguisher against masking tables takes the form

OPT(x, t) = arg max k∈K q i=1 log m∈F n 2 exp ω∈F n 2 1 σ (ω) 2 x (ω) i Ψ(ω ⊕ m) - 1 2 Ψ(ω ⊕ m) 2 + 1 σ (2 n ) 2 x (2 n ) i Ψ(t i ⊕ m ⊕ k) - 1 2 Ψ(t i ⊕ m ⊕ k) 2 . (4.8)
Proof. Straightforward computation from Eq. (1.23) yields

arg max k∈K q i=1 m∈F n 2 ω∈F n 2 exp 1 σ (ω) 2 x (ω) i y (ω) i - 1 2 y (ω) i 2 (4.9) = arg max k∈K q i=1 log    m∈F n 2 exp    ω∈F n 2 1 σ (ω) 2 x (ω) i y (ω) i - 1 2 y (ω) i 2       (4.10)
Now plugging the respective leakages as described in Subsect. 4.3 gives

= arg max k∈K q i=1 log    m∈F n 2 exp    ω∈F n 2 1 σ (ω) 2 x (ω) i Ψ(ω ⊕ m) - 1 2 Ψ(ω ⊕ m) 2 + 1 σ (2 n ) 2 x (2 n ) i Ψ(t i ⊕ m ⊕ k) - 1 2 Ψ(t i ⊕ m ⊕ k) 2 . ( 4

.11)

Proposition 15 (HOOD for masking tables for low SNR). For large Gaussian noise (or low SNR) the distinguisher becomes

OPT-high(x, t) = arg max k∈K ω∈F n 2 1 σ (ω) 2 q i=1        x (ω) i x (2 n ) i m Ψ(ω ⊕ m)Ψ(t i ⊕ k ⊕ m) -1 2 x (2 n ) i m Ψ(t i ⊕ k ⊕ m)Ψ(ω ⊕ m) 2 -1 2 x (ω) i m Ψ(ω ⊕ m)Ψ(t i ⊕ k ⊕ m) 2 + 1 4 m Ψ(ω ⊕ m) 2 Ψ(t i ⊕ k ⊕ m) 2        . ( 4

.12)

Proof. Due to the lack of space we neglect the term arg max k∈K in front of each line. Starting from Eq. (1.23) we use again the first-order Taylor expansion exp{ε} = 1 + ε + O(ε 2 ). So,

q i=1 m∈F n 2 2 n ω=0 1 + 1 σ (ω) 2 x (ω) i y (ω) i - 1 2 y (ω) i 2 + 1 2σ (ω) 4 x (ω) i y (ω) i - 1 2 y (ω) i 2 2 .

High Order Optimal Distinguisher for Precomputation Masking Tables

Furthermore, an expansion at second-order gives

q i=1 m∈F n 2 1 + 2 n ω=0 1 σ (ω) 2 x (ω) i y (ω) i - 1 2 y (ω) i 2 + 1 2σ (ω) 4 x (ω) i y (ω) i - 1 2 y (ω) i 2 2 + 2 n ω =ω 1 σ (ω) 2 σ (ω ) 2 x (ω) i y (ω) i - 1 2 y (ω) i 2 x (ω ) i y (ω ) i - 1 2 y (ω ) i 2 . (4.13)
From the perfect masking condition (see (22, Proposition 1)) the first-order term

m∈F n 2 2 n ω=0 1 σ (ω) 2 x (ω) i y (ω) i - 1 2 y (ω) i 2 = 2 n ω=0 1 σ (ω) 2 x (ω) i m∈F n 2 y (ω) i - 1 2 m∈F n 2 y (ω) i 2
is constant as well as

m∈F n 2 2 n ω=0 1 2σ (ω) 4 x (ω) i y (ω) i - 1 2 y (ω) i 2 2 (4.14) = 2 n ω=0 1 2σ (ω) 4 x (ω) i 2 m∈F n 2 y (ω) i 2 + 1 4 m∈F n 2 y (ω) i 4 -x (ω) i m∈F n 2 y (ω) i 3 . (4.15)
The other terms in ω, ω can be written as

2 2 n ω<ω 1 σ (ω) 2 σ (ω ) 2 x (ω) i x (ω ) i m∈F n 2 y (ω) i y (ω ) i - 1 2 x (ω ) i m∈F n 2 y (ω ) i y (ω) i 2 - 1 2 x (ω) i m∈F n 2 y (ω) i y (ω ) i 2 + 1 4 m∈F n 2 y (ω) i 2 y (ω ) i 2 . (4.16)
Moreover, all terms involving only combinations of ω < d = 2 n do not depend on the key, thus we can further simplify to the required equation

ω∈F n 2 1 σ (ω) 2 q i=1 x (ω) i x (2 n ) i m∈F n 2 y (ω) y (2 n ) - 1 2 x (2 n ) i m∈F n 2 y (2 n ) y (ω) 2 (4.17) - 1 2 x (ω) i m∈F n 2 y (ω) y (2 n ) 2 + 1 4 m∈F n 2 y (ω) 2 y (2 n ) 2   . (4.18)
Proposition 16 (Relationship between HOOD and CPA for masking tables). When all noise variances are equal, i.e., σ = σ (ω) ∀ω, Eq. (4.12) further simplifies to

OPT-high(x, t) = arg max k∈K ω∈F n 2 q i=1 x (ω) i x (2 n ) i m∈F n 2 Ψ(ω ⊕ m)Ψ(t i ⊕ k ⊕ m) - 1 2 x (ω) i m∈F n 2 Ψ(ω ⊕ m)Ψ(t i ⊕ k ⊕ m) 2 , (4.19)

OPTIMAL DISTINGUISHER AGAINST MASKING TABLE

which becomes close to a combination of higher-order CPAs, i.e., C-CPA(x, t) = arg max

k∈K ω∈F n 2 ρ(c n-prod X (x (ω) , x (2 n ) ), c opt Y (y (ω) , y (2 n ) )) (4.20) - 1 2 ρ(x (ω) , c opt Y (y (ω) , y (2 n ) 2 )).
Proof. If all the variances are equal we have

ω∈F n 2 Ψ(ω ⊕ m) 2 σ (ω) = 1 σ ω∈F n 2 Ψ(ω ⊕ m) 2 = 1 σ ω∈F n 2 Ψ(ω) 2 . (4.21)
So, regarding the second term in Eq. ( 4.12) we have

ω∈F n 2 1 σ (ω) 2 q i=1 x (2 n ) i m∈F n 2 Ψ(t i ⊕ k ⊕ m)Ψ(ω ⊕ m) 2 (4.22) = q i=1 x (2 n ) i m∈F n 2 Ψ(t i ⊕ k ⊕ m) ω∈F n 2 1 σ (ω) 2 Ψ(ω ⊕ m) 2 (4.23) = q i=1 x (2 n ) i m∈F n 2 Ψ(t i ⊕ k ⊕ m) ω∈F n 2 1 σ 2 Ψ(ω) 2 (4.24) = q i=1 x (2 n ) i m∈F n 2 Ψ(t i ⊕ m) ω∈F n 2 1 σ 2 Ψ(ω) 2 , (4.25)
which clearly does not depend on the key k. The same goes for the fourth term, which proofs the first part. Now, rewriting Eq. (4. [START_REF] Brier | Correlation Power Analysis with a Leakage Model[END_REF] gives

arg max k∈K ω∈F n 2 x (ω) x (2 n ) | m∈F n 2 Ψ(ω ⊕ m)Ψ(t ⊕ k ⊕ m) - 1 2 x (ω) | m∈F n 2 Ψ(ω ⊕ m)Ψ(t ⊕ k ⊕ m) 2 , (4.26)
and using the same argumentation as in the proof of [START_REF] Bruneau | Less is more -dimensionality reduction from a theoretical perspective[END_REF]Proposition 9) gives the required formula from the second part.

Interestingly, instead of using one CPA to recover the mask and one to recover the secret key (see Def. 40) we recover that the best methodology is to attack each share ω < 2 n with ω = 2 n (minus a regulation term) and then use a combination of all attacks.

In other words a better attack is to build an attack which recover the key in several manners based on different variables and then combined them. As a consequence we have build here an attack which is highly multi-target and as a consequence its parameter τ is also high.

Remark 16. For low noise, we can straightforwardly use [START_REF] Bruneau | Less is more -dimensionality reduction from a theoretical perspective[END_REF]Proposition 10), which is validated in our empirical results.

Experimental Validation

To empirically validate our theoretical results we use simulations of a first order masking scheme with precomputation tables. We target the xor operation in the precomputation phase and the AddRoundKey of the algorithm (see line 3 and line 8 of Alg. 1). For computationally reasons for all distinguishers we only target four bits (n = 4).

Remark 17. Targeting the AddRoundKey phase has some advantages. First, it allows to perform the evaluation on only four bits without the loss of generality of using a four bits Sbox. Second, in the Sbox precomputation algorithm of Coron [START_REF] Coron | Higher Order Masking of Look-Up Tables[END_REF] the output masks are different for each entry of the Sbox and could therefore not be combined with the mask of the precomputation table. However, as in our analysis the attacker can still take advantage of the 2 n leakages of the

OPTIMAL DISTINGUISHER AGAINST MASKING TABLE

masked inputs of the Sbox combined with the leakage of the AddRoundKey operation.

Similarly to the previous experiments, T is uniformly distributed over F 4 2 and the noise is arising from a Gaussian distribution N ∼ N(0, σ 2 ) for σ = σ (0) = ... = σ (16) ∈ {0.5, 1, 3, 5}.

Again to compute the success rate we conducted 500 independent experiments with uniformly distributed k and shaded the success rate with error bars. Figure 4.1 shows the success rate. For low noise (σ = 0.5 and σ = 1) the optimal distinguisher (HOOD) and its approximation for low noise (HOOD-low) perform similar and better than the 2nd-order CPA (2O-CPA) with normalized product combination function and the 2-stage CPA in Eq. 4.7 (2xCPA). Naturally, all distinguishers outperform 2nd-order CPA as it only utilizes two leakages X (0) and X (256) . For higher noise (σ = 3 and σ = 5) the HOOD and its approximation for high noise (HOOD-high) perform better than the 2-stage CPA (2xCPA) and 2nd-order CPA. Moreover it can be noticed that the distinguisher based on combinations of CPA (Eq. (4.20)) (C-CPA) and the optimal ones are equally efficient. Accordingly, we have empirically validated that our new distinguisher approximated from the optimal distinguisher is valid for high noise and more efficient than the two-stage CPA. In particular, it requires around 1000 traces less to reach P S = 90% for σ = 5.

Classical countermeasure

The strategy to protect the table recomputation against HV attacks and the distinguisher presented in [START_REF] Bruneau | Masks Will Fall Off -Higher-Order Optimal Distinguishers[END_REF] is to shuffle the recomputation, i.e., do the recomputation in a random order, as illustrated in Alg. 2.

Different methods to randomize the order are presented in [START_REF] Tunstall | Masking Tables -An Underestimated Security Risk[END_REF]. One of the methods presented is based on a random permutation on a subset of F n 2 . Let S 2 n the symmetric group of 2 n elements, which represents all the ways to shuffle the set {0, . . . , 2 n -1}. If the random permutation over F n 2 is randomly drawn from a set of permutation S ⊂ S 2 n , where card (S) card (S 2 n ), it is still possible for an attacker to take advantage of the table recomputation. Indeed as it is shown in [START_REF] Tunstall | Masking Tables -An Underestimated Security Risk[END_REF] attacks could be built by including all the possible permutations alongside with the key hypothesis. If the permutation is drawn uniformly over the S 2 n the number of added hypothesis is 2 n ! which can be too much for attacks.

For instance, for n = 8, we have

2 8 ! ≈ 2 1684 .
By generating a highly entropic permutation, such as defined in [START_REF] Tunstall | Masking Tables -An Underestimated Security Risk[END_REF] or any pseudo random permutation generator (RC4 key scheduler...), a designer could protect table recomputation

Conclusions and Perspectives

against HV attacks. Indeed using for example five or six bytes of entropy as seed for the permutation generator could be enough to prevent an attacker from guessing all the possible permutations.

The table is recomputed in a random order from line 3 to line 7.

Algorithm

1 m ← R F n 2 , m ← R F n 2
// Draw of random input and output masks

2 ϕ ← R F n 2 → F n 2 , bijective // Draw of random permutation of F n 2 3 for ω ∈ {0, 1, . . . , 2 n -1} do // S-box masking 4 z ← ϕ(ω) ⊕ m // Masked input 5 z ← S[ϕ(ω)] ⊕ m // Masked output 6 S [z] ← z //

Conclusions and Perspectives

In this chapter we used the optimal distinguisher to build the best possible attack.

We provide a new distinguisher based on correlation whose again is as efficient as the optimal distinguisher in case of high noise. Naturally, this new distinguisher outperforms all known (non-profiled) distinguisher for this application. Given all these results we theoretically and empirically show that for high noise the security analysis with non-profiled distinguisher is sufficient as it coincides with the optimal distinguisher. Interestingly this new distinguisher based on correlation as the property to be closed to a sum of high order attacks and as a consequence to be closed to multi-target attack. These results show that non-profiled distinguishers maybe enough to ensure the security of protected implementations at the condition to properly take into account all leakages and specifically the multi-target leakages.

OPTIMAL DISTINGUISHER AGAINST MASKING TABLE

These results raise various new perspectives. First of all, our methodology of starting from the optimal distinguisher and deriving approximated distinguisher could be applied to other scenarios. One application, for example, could be the scenario used in [START_REF] Roche | Collision-Correlation Attack against Some 1st-Order Boolean Masking Schemes in the Context of Secure Devices[END_REF]. Moreover, future work should deal with the exact analysis of the impact of noise on the masking efficiency in a theoretical manner. This comes along with an analysis of the impact of the number of shares, in particular, with an investigation of the arguments done in [START_REF] Prouff | Masking against Side Channel Attacks: a Formal Security Proof[END_REF][START_REF] Waddle | Towards Efficient Second-Order Power Analysis[END_REF] about exponential attack complexity.

CHAPTER 5

Multivariate High Order Attack against shuffled Masking Table

The results presented in this chapter have been published in collaboration with Sylvain Guilley, Zakaria Najm and Yannick Teglia in the international Workshop on Cryptographic Hardware and Embedded Systems (CHES 2015) [START_REF] Bruneau | Multi-variate highorder attacks of shuffled tables recomputation[END_REF]. Masking schemes based on tables recomputation are classical countermeasures against highorder side-channel attacks. Still, they are known to be attackable at order Ω in the case the masking involves Ω shares. In this work, we mathematically show that an attack of order strictly greater than Ω can be more successful than an attack at order Ω. To do so, we leverage the idea presented by Tunstall, Whitnall and Oswald at FSE 2013: we exhibit attacks which exploit the multiple leakages linked to one mask during the recomputation of tables. Specifically, regarding first-order table recomputation, improved by a shuffled execution, we show that there is a window of opportunity, in terms of noise variance, where a novel highly multivariate third-order attack is

MULTIVARIATE HIGH ORDER ATTACK AGAINST SHUFFLED MASKING TABLE

more efficient than a classical bivariate second-order attack. Moreover, we show on the example of the high-order secure table computation presented by Coron at EUROCRYPT 2014 that the window of opportunity enlarges linearly with the security order Ω. Here, we also investigate the case of degree one leakage models, and formally show that the Hamming weight model is the less favorable to the attacker. Eventually, we validate our attack on a real ATMEL smartcard.

Introduction

Contributions.

Our first contribution is to describe a new HODPA tailored to target the table recomputation despite a highly entropic masking (unexploitable by exhaustive search). More precisely, we propose an innovative combination function, which has the specificity to be highly multivariate.

We relate the combination function of state-of-the-art and our new HODPA attacks to their success rate, which allows for a straightforward comparison. In particular, we compare the success rates of our highly multivariate HODPA (exploiting leakages in the table recomputation as well as in the masked algorithm, where the secret key is used) and of a state-of-the-art HODPA (exploiting only the leakages within the masked algorithm).

We build a theoretical analysis of their success rate. Our analysis reveals that there is a window of opportunity, when the noise variance is smaller than a threshold, where our new HODPA is more successful than a straightforward HODPA, despite it is of higher-order. This analysis also allows to identify the relevant parameter which impact the success of the attacks.

In particular the impact of the leakage functions is identified, and as a consequence the best and the worst cases for our new attack are found. Similarly using the success exponent our theoretical analysis gives the best/worst cases in terms of noise variance.

For instance in this chapter we attack a first-order masking scheme based on table recomputation with a (2 n+1 + 1)-variate third-order attack more efficiently than with a classical bivariate second-order attack. In this case HV attacks could not be applied. This is the first time that a non minimal order attack is proved better (in terms of success rate) than the attack of minimal order. Actually, this non intuitive result arises from a relevant selection of leaking samplesthis question is seldom addressed in the side-channel literature. We generalize our attack to a higher-order masking scheme based on tables recomputation (Coron, EUROCRYPT 2014), and prove that it remains better than a classical attack, with a window of opportunity that actually grows linearly with the masking order Ω.

Totally random permutation and attack

Finally we propose a new innovative countermeasure in order to protect masking scheme based on tables recomputation against our new attack.

Outline of the chapter.

The rest of the chapter is organized as follows. In Sect. 5.2 we propose a new attack against the "protected" implementation of the table recomputation, prove theoretically the soundness of the attack and validate these results by simulation. In Sect. 5.3 we apply this attack on a higher-order masking scheme. Sect. 5.4 extends our results to the case where the leakage function is affine in the bits of the targeted sensitive variable. In Sect. 5.5 we validate our results on real traces. Finally in Sect. 5.6 we present a countermeasure to mitigate the impact of our new attack.

Preliminary and notations

In order to conduct a Ωth-order attack an attacker should combine the leakages of Ω shares. To combine these leakages an attacker will use a combination function [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF][START_REF] Messerges | Using Second-Order Power Analysis to Attack DPA Resistant Software[END_REF][START_REF] Oswald | Template Attacks on Masking -Resistance Is Futile[END_REF]. The degree of this combination function must be at least Ω for the attack to succeed. The combination function will then be applied both on the measured leakages and on the model (this is the optimal HODPA). As a consequence, an HODPA is completely defined by the combination function used.

In the rest of the chapter the SNR is given by the following definition:

Definition 41 (Signal to noise ratio). The Signal to Noise Ratio of a leakage denoted by a random variable L depending on informative part denoted I is given by:

SNR [L, I] = Var [E [L|I]] E [Var [L|I]] . (5.1)
An attack is said sound when it allows to recover the key k with success probability which tends to one when the number of measurements tends to the infinity.

Totally random permutation and attack

In this section we present a new attack against shuffled table recomputation shown in Alg. 2 of Chapt. 4. The success of this attack will not be impacted by the entropy used to generate the shuffle. As a consequence this attack will succeed when the HV attacks will fail because the

MULTIVARIATE HIGH ORDER ATTACK AGAINST SHUFFLED MASKING TABLE

quantity of entropy used to generate the shuffle is too large to be exhaustively enumerated. We then express the condition where this attack will outperform the state-of-the-art second order attack.

Defeating the countermeasure

As the permutation ϕ is completely random, the value of the current index in the for loop (line 3 to line 7 in Alg. 2) is unknown. But it can be noticed that this current index ϕ(ω), printed in boldface for clarity, is manipulated twice at each step of the loop (line 4, line 5):

z ← ϕ(ω) ⊕ m , (5.2)
z ← S[ϕ(ω)] ⊕ m . (5.3)
Let U a random variable uniformly drawn over F n 2 and m ∈ F n 2 a constant. Then, it is shown in [START_REF] Prouff | Statistical Analysis of Second Order Differential Power Analysis[END_REF] that:

E [(HW[U ] -E [HW[U ]]) × (HW[U ⊕ m] -E [HW[U ⊕ m]])] = - HW[m] 2 + n 4 . (5.4)
As a consequence, it may be possible for an attacker to exploit the leakage depending on the two manipulations (Eq. (5.2) and (5.3)) of the current random index in the loop. Indeed, at each of the 2 n steps of the loop in the table recomputation, the leakage of the ϕ(ω) in Eq. (5.2) and (5.3) which plays the role of U in Eq. (5.4) will be combined (by a centered product) to recover a variable depending on the mask. Afterwards, these 2 n variables will be combined together (by a sum) in order to increase the SNR as much as possible. Finally, this sum is combined (again by a centered product) with a leakage depending on the key. This rough idea of the attack is illustrated it on Fig. 5.1, which represents the "trace" corresponding to the dynamic execution of Alg. 2, followed by the masked AES AddRoundKey & SubBytes steps.

Remark 18 (Construction of the high-order attack). The construction of the attack depicted in Fig. 5.1 leverages on two building blocks:

1. the centered product, represented as × , which allows to get rid of a mask (recall Eq. (5.4)), albeit at the expense of a smaller SNR (it is squared, as shown in (46) -see Sec. 5.2.3)

2. the sum of variables with the same leakage model, represented as + , which increases the SNR linearly with the number of variables summed together.

An attacker could want to perform the attack on the output of the S-Box. But depending on the implementation of the masking scheme the output masks can be different for each address 5.2 Totally random permutation and attack

× × × + × × × m m ′ ϕ(0) ⊕ m ϕ(0) ϕ (1)
⊕ m ϕ(1) of the S-Box (see for example the masking scheme of Coron ( 39)). To avoid loss of generality we focus our study on the S-Box input mask of the recomputation. Indeed by design of the table recomputation masking scheme, the input mask is the same for each address of the S-Box: the attacker can thus exploit it multiple times. Moreover an attacker can still take advantage of the confusion of the S-Box [START_REF] Fei | A Statistical Model for DPA with Novel Algorithmic Confusion Analysis[END_REF] to better discriminate the various key candidates. Indeed he can target the input the of SubBytes operation of the last round. Notice the use of capital M and capital Φ, which indicates that the leakage is modeled as a random variable.

1 1 4 5 4 5 t ⊕ m t ⊕ m ⊕ k S ′ [t ⊕ k] ⊕ m ′ 4 5 ϕ(ω) ⊕ m ϕ(ω) . . . Sensitive variable: Line in Alg. 1: 5 4 . . . time ϕ(2 n -1) ϕ(2 n -1) ⊕ m new (2 n+1 + 1)-variate 3rd-

Multivariate attacks against table recomputation

In the previous section, it has been shown that at each iteration of the loop of the table recomputation, it is possible to extract a value depending on the mask. As a consequence it is possible to use all of these values to perform a multivariate attack. In this subsection we give the formal formula of this new attack. Let us define the leakages of the table recomputation. The leakage of the masked random index in the loop is given by: HW

[Φ (ω) ⊕ M ] + N (1)
ω . The leakage of the random index is given by: HW[Φ (ω)] + N

ω . In this chapter as no matrix notation is used the bottom index is used to index the step in the loop.

Depending on the knowledge about the model, the leakage could be centered by the "true" expectation or by the estimation of this expectation. We assume this expectation is a known value given by: E HW[Φ (ω

) ⊕ M ] + N (1) ω = E HW[Φ (ω)] + N (2) ω
= n 2 . Then let us denote

MULTIVARIATE HIGH ORDER ATTACK AGAINST SHUFFLED MASKING TABLE

the central leakages as:

X (1) ω = HW[Φ (ω) ⊕ M ] + N (1) ω - n 2 , (5.5)
X (2) ω = HW[Φ (ω)] + N (2) ω - n 2 . (5.6)
Besides, the leakage of the masked AddRoundKey is:

X = HW[T ⊕ M ⊕ k ] + N - n 2 . (5.7)
In a view to use all the leakages of the table recomputation, an original combination function could be defined.

Definition 42. The combination function C T R exploiting the leakage of the table recomputation is given by:

C T R : R 2 n+1 × R -→ R X (1)
ω , X

ω 0 ω 2 n -1 , X -→ -2 × 1 2 n 2 n -1 ω=0 X (2)
ω × X (2) ω × X . (1)
Following the Fig. 5.1 it can be noticed that C T R is in fact the combination of two subcombination functions. Indeed, first of all, the leakages of the table recomputation are combined; the result of this combination is the following value:

X T R = -2 × 1 2 n 2 n -1 ω=0 X (1) ω × X (2) ω . (5.8)
Second, this value is multiplicatively combined with X .

Remark 19. It can be noticed that the random variable X T R does not depend on Φ. Indeed in Eq. (5.8) the sum can be reordered by Φ. Moreover as this sum is computed over all the possible Φ (ω) it implies that 1

2 n 2 n -1 ω=0 X (1) ω × X (2)
ω is exactly the expectation over the Φ (ω). As a consequence X T R is random only through the mask and the noise.

Based on the combination function C T R , a multivariate attack can be built. Definition 43. The MultiVariate Attack (MVA) exploiting the leakage of the table recomputation (TR) is given by the function:

MVA T R : R 2 n+1 × R × R -→ F n 2 X (1) ω , X (2) ω ω
, X , Y -→ argmax

k∈F n 2 ρ C T R X (1) ω , X (2) ω ω
, X , Y ,

where Y = E HW[T ⊕ M ⊕ k] -n 2 • HW[M ] -n 2 |T
and ρ is the Pearson coefficient. According to Eq. (5.4), the model Y is equal to an affine transformation of -HW[T ⊕ k] (note the negative sign for the correlation ρ extremal value when k ∈ F n 2 to be positive).

Totally random permutation and attack

Proposition 17. MVA T R is sound.

Proof. By the law of large numbers, correlation coefficient involved in the expression of MVA T R tends to ρ(-

HW[T ⊕ k ], -HW[T ⊕ k]
) when the number of traces tends to infinity. This quantity is maximal when k = k , by the Cauchy-Schwarz theorem. Then for enough traces the noise will impact all the key guesses similarly and as a consequence the result of MVA T R is maximal when k = k .

Remark 20. The attack presented in Def. 57 is a (2 n+1 + 1)-multivariate third order attack.

Let us denote the leakage of the mask (which occurs at line 1 of Alg. 2) by:

X (3) = HW[M ] + N (3) - n 2 .
(5.9)

Definition 44. We denote by 2O-CPA the CPA using the centered product as combination function. Namely:

2O-CPA : R × R × R -→ F n 2 X (3) , X , Y -→ argmax k∈F n 2 ρ X (3) × X , Y .
A careful look at Def. 42, Def. 57 and Eq. (5.8) reveals that the only difference between the MVA T R and the 2O-CPA is the use of X T R instead of X (3) . Thus X T R will act as the leakage of the mask. Let us call X T R the second order leakage.

Lemma 4. The informative part of the second order leakage is the same as the informative part of the leakage mask i.e.,

E [X T R |M = m] = E X (3) |M = m .
Proof. It is a straightforward application of the results of ( 133): Use Eq. (5.4) and notice the intentional -2 factor in Eq. (5.8). Both expectations are thus equal to HW[m].

Leakage analysis

By using the formula of the theoretical success rate (SR) we show that as the same operations are targeted by the MVA T R and the 2O-CPA. Consequently, it is equivalent to compare the SNR or the SR of these attacks. Based on this fact we can theoretically establish the conditions in which the MVA T R outperforms the 2O-CPA. These conditions are given in Theorem 5.2.1.

Recently A.A Ding et al. (46, §3.4) give the following formula to establish the Success Rate (SR) of second-order attacks:

SR = Φ N k -1 √ b δ 0 δ 1 4 K -1 /2 κ . (5.10)
In this formula:

MULTIVARIATE HIGH ORDER ATTACK AGAINST SHUFFLED MASKING TABLE

• δ 0 denotes the SNR of the first share and δ 1 denotes the SNR of the second one;

• Φ N k -1 denotes the cumulative distribution function of (N k -1)-dimensional standard Gaussian distribution; as underlined by the authors in [START_REF] Ding | A statistical model for higher order DPA on masked devices[END_REF], if the noise distribution is not multi-variate Gaussian, then Φ N k is to be understood as its cumulative distribution function;

• N k denotes the number of key candidates;

• K denotes the confusion matrix and κ the confusion coefficient;

• b denotes the number of traces.

Remark 21. An update version of this formula for first order CPA has been presented in (52) which solves the issue of the non invertible matrix.

This formula allows to establish the link between the SNR and SR of second order attacks against Boolean masking schemes.

Let us apply the A.A Ding et al. formula in the case of our two attacks:

SR 2O-CPA = Φ 2 n -1 √ b SNR X (3) , M SNR [X , (T, M )] 4 K -1 /2 κ , SR MVA T R = Φ 2 n -1 √ b SNR [X T R , M ] SNR [X , (T, M )] 4 K -1 /2 κ .
We target the same operation for the share that leaks the secret key (X ). Moreover by remark 4 the informative parts of the leakages depending on the mask (X T R and X (3) ) is the same in the two leakages. As a consequence, K and κ are the same in the two attacks.

It can be noticed that the only difference in the success rate formula is the use of SNR [X T R , M ] instead of SNR X (3) , M . Therefore, it is equivalent to compare these values and compare the SR of these attacks.

Theorem 5.2.1. The SNR of the "second-order leakage" is greater than the SNR of the leakage of the mask if and only if

σ 2 2 n-2 - n 2 ,
where σ denotes the standard deviation of the Gaussian noise. As a consequence MVA T R will be better than 2O-CPA in the interval

σ 2 ∈ [0, 2 n-2 -n/2].
Proof. See Appendix B.1. Interestingly, the same result is also a byproduct of the demonstration of Proposition 22 (see Appendix B.2.2).

Totally random permutation and attack

Theorem 5.2.1 gives us the cases where exploiting the second-order leakage will give better results than exploiting the classical leakage of the mask. For example if n = 8 (the case of AES)

the second-order leakage is better until σ 2 60.

Figure 5.2 shows when the SNR of X T R is greater than the SNR of X (3) . In order to have a better representation of this interval1 /SNR is plotted.

1 SNR[X T R ,M ] 1 SNR[X (3) ,M ]

Simulation results

In order to validate empirically the results of Sect. 5.2, we test the method presented on simulated data. The target is a first order protected AES with table recomputation. To simulate the leakages we assume that each value leaks its Hamming weight with a Gaussian noise of standard deviation σ. The 512 leakages of the table recomputation are those given in Subsect. 5.2.2.

A total of 1000 attacks are realized to compute the success rate of each experiment. In this part, the comparisons are done on the number of traces needed to reach 80% of success.

It can be seen in Fig. 5.3a and in Fig. 5.3b that the difference between the two attacks is null for σ = 0 and σ = 8 (that is, σ 2 = 64 ≈ 60). It confirms the bound of the interval shown in Fig. 5.2. This also confirms that comparing the SNR is equivalent to comparing the SR.

It can be seen in Fig. 5.3 that in presence of noise the MVA T R outperforms the 2O-CPA.

The highest difference between the MVA T R and 2O-CPA is reached when σ = 3. In this case, the MVA T R needs 2500 traces to mount the attack while the 2O-CPA needs 7500 traces. This represents a relative gain 1 of ≈ 200%. As shown in Fig. 5.3d, the relative gain decreases to 122%

MULTIVARIATE HIGH ORDER ATTACK AGAINST SHUFFLED MASKING TABLE

when σ = 4.

Theoretical analysis of the SR

While the previous analysis of Subsect. 5.2.3 gives the bounds of effectiveness of the MVA T R it does not allow a quantitative comparison of the respective behaviors of the MVA T R and the 2O-CPA between these bounds. In this subsection we propose an approach which allows a deeper analysis of the relevant parameters of their SR. We exploit the results of (63) which presents a closed form formula which links the SR to the SNR for first order attacks. These results have recently been extended to high order attacks (64).

MULTIVARIATE HIGH ORDER ATTACK AGAINST SHUFFLED MASKING TABLE

Exploiting this values it is possible to extract the parameters which impact the respective behavior of the two attacks and especially the ones reaching to a higher difference between the two attacks. Similarly to Subsect. 5.2.4 we will compare the two attacks using the relative gain.

Definition 45 (rel-gain (SR) ). The relative gain between 2O-CPA and MVA T R is given by:

rel-gain (SR) = m (SR) 2O-CPA -m (SR) MVA T R m (SR) MVA T R
, where m

(SR)
2O-CPA and m

(SR)
MVA T R are respectively the number of traces needed by 2O-CPA and MVA T R to reach success rate value SR. And we will also use the difference in number of traces needed to reach SR.

Definition 46 (gain (SR) ). The difference in number of traces needed to reach SR of success is given by the gain: Notice that rel-gain (SR) and gain (SR) are tools to compare attacks after having computed their SR. They differ from relative distinguishing margins metrics (181) which analyses the value of the distinguisher (and not their SR).

gain (SR) = m (SR) 2O-CPA -m (SR) MVA T R ,
Proposition 21. rel-gain (SR) does not depend on the value of SR.

Proof. See Appendix B.2.2.
This means that, in Fig. 5.3, the SR curves for 2O-CPA and MVA T R are the same, modulo a scaling in the X axis. For instance, in Fig. 5.3 (a) and (b), the scaling factor is 1, i.e., the two curves superimpose perfectly. As a result, one can compare these two attacks in terms of traces number to extract the key, irrespective of the SR value chosen for the threshold. Proposition 22. gain (SR) depends on the value of SR, but the value of the noise variance where gain (SR) is maximum not depends on SR.

Proof. See Appendix B.2.3.

Remark 22. While the bounds of Theorem 5.2.1 depend only on the SNR the maximum effectiveness (the maximum of gain (SR) or rel-gain (SR) ) of the MVA T R compare to the 2O-CPA also depends on the operation targets (e.g. AddRoundKey or SubBytes) by the confusion coefficients κ and κ . In order to validate our theoretical analysis we build empirical validation based on simulations.

We reuse the curves generated for Sect. 5.2.4. In Fig. 5.4 the empirical results based simulation are plotted in gray and the Theoretical ones in red pointed lines. The first observation is that the theoretical analysis match well the simulations which validates our model choices.

In Fig 5.4a it can be noticed that for several SR ( different gray lines) the empirical rel-gain (SR) are closed which confirmed the Prop. 21. Exploiting the formula of Def. 45 we can find the noise variance σ 2 where rel-gain (SR) is maximum. Indeed it occurs in a root of the derivative of rel-gain (SR) . In our scenario it occurs for σ 2 = 9.11 (that is σ ≈ 3.02).

The behavior of gain (SR) is different indeed the SR has an impact on it, the gray lines are not superimposed (see Fig. 5.4b). But similarly to rel-gain (SR) the SR does not impact the value of noise where the maximum gain (SR) is reached. This confirms the Prop. [START_REF] Bruneau | Less is more -dimensionality reduction from a theoretical perspective[END_REF]. In our scenario it is reached for σ 2 = 39.67 (that is σ ≈ 6.30).

In order to compute this maximum we have computed the roots of the derivatives (of rel-gain (SR) and gain (SR) w.r.t. σ 2 ) using the MAXIMA software.

An example on a high-order countermeasure

The result of the previous section can be extended to any masking scheme based on table recomputation. In particular the MVA T R can apply to High-Order masking schemes.

MULTIVARIATE HIGH ORDER ATTACK AGAINST SHUFFLED MASKING TABLE

Coron masking scheme attack and countermeasure

The table recomputation countermeasure can be made secure against High-Order attacks. An approach has been proposed by Schramm and Paar (150). However, it happened that this masking scheme can be defeated by a third order attack [START_REF] Coron | Side Channel Cryptanalysis of a Higher Order Masking Scheme[END_REF]. To avoid this vulnerability Coron recently presented [START_REF] Coron | Higher Order Masking of Look-Up Tables[END_REF] a new method based on table recomputation, which guarantees a truly high-order masking. The core idea of this method is to mask each output of the S-Box with a different mask and refresh the set of masks between each shift of the table (masking the inputs by one mask). HV attacks are still a threat against such schemes. Indeed an attacker will recover iteratively each input mask. Afterwards he will be able to perform a first order attack on the AddRoundKey to recover the key. To prevent attacks based on the exploitation of the leakages of the input masks an approach based on a random shuffling of the loop index is possible (see Alg. 3). Algorithm 3 is a (Ω -1)-th order countermeasure, meaning that attacks of order strictly less than Ω fail. In this algorithm, the x i for i < Ω can be seen indifferently as shares or as masks. The original masked S-Box algorithm from Coron [START_REF] Coron | Higher Order Masking of Look-Up Tables[END_REF] is the same as Alg. 3, with ϕ chosen as the identity. It can be noticed that the entropy needed to build the permutation could be low compared to the entropy needed for the masking scheme (especially because of the numerous costly RefreshMasks operations).

Attack on the countermeasure

We apply Alg. 3 on X which is equal to T ⊕ k , i.e., Ω i=1 X i = T ⊕ k . Similarly to the definitions in Subsect. 5.2.2, let us define the leakages of the table recomputation of the masking scheme of Coron where the order of the masking is Ω-1:

X (1) (ω,i,j) = HW[Φ (ω)⊕X i ]+N (1) (ω,i,j) -n 2 and X (2) (ω,i,j) = HW[Φ (ω)] + N (2)
(ω,i,j) -n 2 , where i ∈ 1, Ω -1 will index the Ω -1 masks. The Ω-th share is the masked sensitive value. Besides j ∈ 1, Ω denotes the index of the loop from lines 7 to lines 9 of the Alg. 3. The leakage of the masks is given by X

(3) i = HW[X i ] + N (3) i -n
2 . Finally, we denote by: X = HW[

Ω-1 i=1 X i ⊕ k ⊕ T ] + N -n
2 the leakage of the masked value.

Definition 47. The combination function C Ω CS exploiting the leakage of the table recomputation (Coron Scheme, abridged CS) is given by:

C Ω CS : R Ω×(Ω-1)×2 n+1 × R → R    X (1) (ω,i,j) , X (2) (ω,i,j) ω∈F 2 n i∈ 1,Ω-1 j∈ 1,Ω , X    → Ω-1 i=1     -2 Ω2 n ω∈F 2 n j∈ 1,Ω X (1)
(ω,i,j) ×X

(2) (ω,i,j)     ×X . Similarly to Subsect. 5.2.3, we define for all 1 i Ω -1:

X CS Ω i = -2 Ω2 n ω∈F 2 n j∈ 1,Ω X (1)
(ω,i,j) × X

(ω,i,j) .

This value is the combination of all the leaking values of the table recomputation depending of one share.

Remark 23. The scaling by factor -2/Ω allows to have, for all i ∈ 1, Ω -1 :

E X CS Ω i |X i = x i = E X (3)
i |X i = x i .
Additionally we define for, i = Ω, X CS Ω i = X . Based on the combination function C Ω CS a multivariate attack can be built.

Definition 48. The MultiVariate Attack exploiting the leakage of the table recomputation of the Ω -1 order Coron masking Scheme is given by:

MVA Ω CS : R Ω×(Ω-1)×2 n+1 × R × R → F n 2    X (1)
(ω,i,j) , X

(ω,i,j)

ω∈F 2 n i∈ 1,Ω-1 j∈ 1,Ω , X , Y    → argmax k∈F n 2 ρ Ω i=1 X CS Ω i , Y , where Y = (-1) Ω-1 × HW[T ⊕ k] -n 2 .
Proposition 23. MVA Ω CS is sound.

Proof. The demonstration follows the same lines as that of Proposition 17. In the case of Proposition 23, the expectation of

Ω i=1 X CS Ω i knowing the plaintext T = t is proportional to HW[t ⊕ k]. Indeed by (142) E Ω i=1 X CS Ω i |T = t = -1 2 Ω-1 × HW[t ⊕ k] -n 2
Remark 24. The attack presented in Def. 48 is a (Ω×(Ω -1)×2 n+1 +1)-variate (2×(Ω -1)+1)order attack.

Definition 49. The "classical" ΩO-CPA is the HOCPA build by combining the Ω shares using the centered product combination function.

ΩO-CPA :

R Ω-1 × R × R -→ F n 2 X (3) i i∈ 1,Ω-1 , X , Y -→ argmax k∈F n 2 ρ Ω-1 i=1 X (3) i
× X , Y .

MULTIVARIATE HIGH ORDER ATTACK AGAINST SHUFFLED MASKING TABLE

Simulation results on Coron masking Scheme

In order to validate the theoretical results of Subsect. 5.3.3, the MVA Ω CS has been tested on simulated data and compared to ΩO-CPA. The simulations have been done with the Hamming weight model and Gaussian noise such as the leakages defined in Subsect. 5.3.2. We test these attacks against a second and a third order masking scheme.

To compute the success rate, attacks are redone 500 times for the second order masking and 100 times for the third order masking (because this attack requires an intensive computational power).

In Fig. 5.6a it can be seen that MVA

CS reaches 80% of success rate for less than 20000 traces while the 3O-CPA does not reach 30% for 100000. In Fig. 5.6b it can be seen that MVA

• the inner product in R n , that is α • V = n i=1 α i V i .
A leakage function Ψ α is said affine if this function is a weighted sum of the bits of the leaking value, i.e., Ψ α (V ) = α • V .

In the sequel, we assume sensitive variables are balanced and have each bit independent of the other, as is customary in cryptographic applications.

Proposition 24. Let 1 = (1, . . . , 1) ∈ F n 2 . E [Ψ α [V ]] = 1 2 (α • 1) and Var [Ψ α [V ]] = 1 4 α 2 2 .
Proof. We have

E [Ψ α [V ]] = α • E [V ] = α • 1 2 1 and Var [Ψ α [V ]] = α t Cov [V ] α = 1 4 α 2 2 .
Then it is possible to compute the results of the centered product.

Lemma 5. Let U be a random variable following a uniform law over F n 2 , and z ∈ F n 2 . We have:

E [(Ψ α [U ] -E [Ψ α [U ]]) × (Ψ β [U ⊕ z] -E [Ψ β [U ⊕ z]])] = - 1 2 (α β) • z + 1 4 α • β ,
where denotes the element-wise multiplication, that is (α

β) i = α i β i .
Proof. See in Appendix B.4.1.

Assumption 1. In order to compare the results in case of an affine model and the Hamming weight model (HW = Ψ 1 ) let us assume that the model variance is the same in the two cases i.e., Var [Ψ α (V )] = Var [HW[V ]]; this is equivalent to α 2 2 = n. Let us also assume that all the values manipulated during the algorithm leak in the same way i.e., the weight vector α of the sum is the same for all the variables V of the algorithm. This is realistic because it is likely that sensitive variables transit through a given resource, e.g., the accumulator register.

In the rest of this section, we will denote by α the vector of weight of the leakage model.

Let us redefine the leakage of the table recomputation the (centered) leakage of the random index:

X (1) ω = α•(Φ (ω) ⊕ M )+N (1) ω -1 2 (α • 1)
, the (centered) leakage of the mask random index:

X (2) ω = α • (Φ (ω)) + N (2) ω -1 2 (α • 1)
, the (centered) leakage of the mask:

X (3) = α • M -1 2 (α • 1)
, Besides, let X be the leakage of a sensitive value depending on the key. We have either:

• X = α • (T ⊕ k ⊕ M ) + N -1 2 (α • 1)
, which is similar to Eq. (5.7), or

• X = α • (S(T ⊕ k ) ⊕ M ) + N -1 2 (α • 1), if there is an S-Box S.
In a view to unite both expressions, we denote by Z the sensitive variable, that is either

Z = T ⊕ k , or Z = S(T ⊕ k ). Consequently, we have X = α • (Z ⊕ M ) + N -1 2 (α • 1).

MULTIVARIATE HIGH ORDER ATTACK AGAINST SHUFFLED MASKING TABLE

Lemma 6. In case of affine leakage model the second order leakage X T R is given by:

E [X T R |M = m] = E -2 2 n 2 n -1 ω=0 X (1) ω × X (2) ω | M = m = α 2 • m - 1 2 α 2 2 ,
where α 2 = α α.

Proof. Direct application of Lemma 5. . We have:

E C T R X (1) ω , X (2)
ω ω

, X | T = - 1 2 α 3 • z + 1 4 n i=1 α 3 i , and
E X (3) × X | T = - 1 2 α 2 • z + 1 4 α 2 2 .
Proof. Direct application of Lemma 6 and Lemma 5.

Impact of the model on the confusion coefficient

As the models in the two different attacks are different, the parameters K and κ (recall Eq. (5.10)) also differ. In order to compare the two attacks we first establish the impact of the model on the value of the minimum confusion coefficient min k =0 κ k . Then we show that the impact is not important in case of the targeted sensitive value is proceed in a nonlinear part of the algorithm (an S-Box).

In practice the confusion coefficients are very close. We study the impact of the disparity of α using several distributions (see Fig. 5.7):

•

α i = √ 1 + ε for i even and α i = √ 1 -ε otherwise (abridged α = √ 1 ± ε),
• and the other sign convention (abridged α = √ 1 ∓ ε).

We also randomly generate 1000 α. All those distributions satisfy the assumption 1, namely n i=1 α 2 i = n. The confusion coefficient for α 2 and α 3 are very close (see Fig. 5.7).

Moreover we find that the maximum difference in all the simulations with random weight is max (min k =0 α 2 κ kmin k =0 α 3 κ k ) = 0.019. In terms of number of traces needed to reach 80% of success this represents a small difference of 5%. As motivated in Sect. 5.2.1, we can modify the MVA T R in order to target the last round S-Box input:

min k =0 κ k ε α 2 for α = √ 1 ± ε α 3 for α = √ 1 ± ε α 2 for α = √ 1 ∓ ε α 3 for α = √ 1 ∓ ε
X = α • Sbox -1 [T ⊕ k ] ⊕ M + N -1 2 (α • 1).
Theorem 5.4.1. The SNR of the "second-order leakage" is greater than the SNR of the leakage of the mask if and only if

σ 2 α 4 4 × 2 n-2 n - n 2 ,
where α p = ( n i=1 |α i | p ) 1/p is the p-norm (p 1) of vector α, and where σ denotes the standard deviation of the Gaussian noise.

As a consequence MVA T R is better than 2O-CPA when the noise variance is in the interval [0, α 4 4 2 n-2 /nn/2].

Proof. See Appendix B.4.2.

Corollary 6. The minimal value of α 4 4 subject to α 2 2 = n is reached when all the component of α are equal. This means that the worst case for the MVA T R compared to the 2O-CPA is when the leakage is in Hamming Weight.

Proof. See Appendix B.4.3.

Simulation results

Some simulations have been done in order to validate the results of the theoretical study of the previous sections. The results, presented in this section, confirm that:

• attacks are not impacted by the small differences of the confusion coefficient (κ, recall Sec. 5.4.2).

Practical validation

This section presents the results of the multivariate attack exploiting the table recomputation stage on true traces.

Experimental Setup

The traces are electromagnetic leakages of the execution of an AES-128 assembly implementation with table recomputation. Our implementation has been loaded on ATMEL ATMega163 8-bit to be analyzed. This smartcard is known to be leaky. It contains 16Kb of in-system programmable flash, 512 bytes of EEPROM, 1Kb of internal SRAM and 32 general purpose working registers.

The smartcard is controlled by a computer through the Xilinx Spartan-VI FPGA embedded in a SASEBO-W platform. The ATMega is powered at 2.5 V and clocked at 3.57 MHz.

The measurements were taken using a LeCroy wave-runner 6100A oscilloscope by means of a Langer EMV 0-3 GHz EM probe and PA-303 30 dB Langer amplifier. The acquisition have been acquired with full bandwidth and with a sampling rate of F S = 500 MS/s.

To build our experiments 13000 traces have been acquired. Each trace contains 12 million leakages samples in order to simplify our analysis we only acquired the table recomputation step and the first round of the AES.

Experimental results

Let us first study the results of the attack in terms of success rate. The leakage function as been recovered using a linear regression. For example the normalized vector of weight for the leakage of the first share is α = (0.95, 1.22, 0.98, 1.13, 0.59, 1.01, 1.04, 0.95) .

MULTIVARIATE HIGH ORDER ATTACK AGAINST SHUFFLED MASKING TABLE

Both the MVA T R and the 2O-CPA target Sbox[T ⊕ k ] ⊕ M as in our implementation the input and output masks are the same.

It can be seen in Fig. 5.11a that the results of the two attacks are similar. Both attacks perform similarly because the curves are not noisy.

Indeed the average values of the SNR of the 256 leakages of the masked random index (Φ (ω) ⊕ M ) and the SNR of the 256 leakages of the random index (Φ (ω)) is 5.

If we assume that the variance of the signal is equal to two (such as HW on 8-bit CPUs)

then the variance of the noise is less than 0.5. The mask (M ) and the key-dependent share This two results are specific to the implementation and a clear disadvantage for the MVA T R .

Sbox[T ⊕ k ] ⊕ M ) leak
But even in this case the MVA T R works as well as the 2O-CPA, this shows that there is (generally) a gain to use the MVA T R .

In order to confirm these results let us verify that when the noise increases the MVA T R outperforms the 2O-CPA. Let us add an artificial Gaussian noise with a standard deviation of 0.0040. This models the addition of a countermeasure on top of the table recomputation.

Then it can be seen in Fig. 5.11b that in this case the MVA T R outperforms the 2O-CPA. This confirms the practicality of our attack, and also that the gain is in the SNR.

F n 2 → F n 2 bijection 1 m ← R F n 2 , m ← R F n 2
// Draw of random input and output masks In order to generate a random power of S it is possible to directly compute S r by applying r times the permutation S where r is a random number. Notice that r can be larger than the number of possible power S by the group law property of the combination. But this approach can be time consumptive.

2 ϕ ← R F n 2 → F n 2 , γ ← R F n 2 → F n 2 such that γ • S = S • γ //
To faster it, the use of the cycle decomposition of S may be an interesting approach. Let us recall this well known theorem:

Proposition 27 (Theorem 5.19 [START_REF] Datta | Algebra And Trigonometry[END_REF]). Let S n be the symmetric group of n elements then each element of S n can be expressed as a product of disjoint cycles.

Proposition 28. The maximum number of exponentiations needed to compute S p could be reduced from p to p (mod l 1 ) + p (mod l 2 ) + ... + p (mod l m ) where the l i denote the respective length of the cycles in the cycles decomposition of S. Notice that l 1 + l 2 + . . .

+ l m = 2 n
Proof. We can express S as S = c 1 • c 2 • . . . • c m by Prop. 27. As the order of a cycle is equal to its length l we have that:

S p = c p (mod l1) 1 • c p (mod l2) 2
... • c p (mod lm) m

MULTIVARIATE HIGH ORDER ATTACK AGAINST SHUFFLED MASKING TABLE

Of course another parameter is the security of the permutation generation itself against possible Side Channel Analysis. If an attacker is able for example to recover: p (mod l 1 ), p (mod l 2 ), ..., p (mod l m ), he will be able to recover the random permutation. This means that at least the exponentiation of S should be in constant time.

Conclusions and Perspectives

The table recomputation is a known weakness of masking schemes. We have recalled that practical countermeasures (e.g., shuffling with a high entropy) could be built to protect the table recomputation. In this chapter, we have presented a new multivariate attack exploiting the leakage of the protected table that outperformed classical HODPA even if a large amount of entropy is used to generate the countermeasure. This multivariate attack gives an example of a HODPA of non-minimal order which is more efficient than the corresponding minimal order HODPA. We have theoretically expressed the bound of noise in which this attack outperforms HOCPA using the SNR. Then we have empirically validated this bound. Interestingly, we show that if the leakage model consists in a linear combination of bits, then our attack becomes all the better as the model gets further away from uniform weights (so-called Hamming weight model).

Moreover, we have shown that the relative gain to use the multivariate attack grows linearly with the order of the masking schemes. This result highlights the fact that the study of masking scheme should take into account as second parameter the number of variables exploitable by these attacks. Indeed we have shown in this chapter that when the number of variables used to perform the attacks increases, the order does not alone provide a criterion to evaluate the security of the countermeasure, and that the SNR is a better security metric to consider.

In future works we will investigate how to protect table recomputation against such attacks and investigate the cost of such countermeasures, evaluate the threat of such attacks on high-order masking schemes implemented on real components. We will also investigate how multivariate attacks could be applied on other masking schemes and protection techniques. And then, we will quantify the impact of these attacks.

Introduction

In order to protect embedded systems against side-channel attacks, countermeasures need to be implemented. Masking and shuffling are the most investigated solutions for this purpose [START_REF] Mangard | Power analysis attacks -revealing the secrets of smart cards[END_REF].

Intuitively, masking aims at increasing the order of the statistical moments (in the leakage distributions) that reveal sensitive information [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF][START_REF] Ishai | Private Circuits: Securing Hardware against Probing Attacks[END_REF], while shuffling aims at increasing the noise in the adversary's measurements [START_REF] Herbst | An AES Smart Card Implementation Resistant to Power Analysis Attacks[END_REF]. As a result, an important challenge is to develop sound tools to understand the security of these countermeasures and their combination [START_REF] Rivain | Higher-Order Masking and Shuffling for Software Implementations of Block Ciphers[END_REF].

For this purpose, the usual strategy is to consider template attacks for which one can split the evaluation goals into two parts: offline profiling (building an accurate leakage model) and online attack (recovering the key using the leakage model). As far as profiling is concerned, standard methods range from non-parametric ones (e.g., based on histograms or kernels) of which the cost quite highly suffers from the curse of dimensionality (see e.g., (4) for an application of these methods in the context of non-profiled attacks) to parametric methods, typically exploiting the mixture nature of shuffled and masked leakage distributions [START_REF] Lemke-Rust | Analyzing side channel leakage of masked implementations with stochastic methods[END_REF][START_REF] Lemke-Rust | Gaussian Mixture Models for Higher-Order Side Channel Analysis[END_REF][START_REF] Oswald | Template Attacks on Masking -Resistance Is Futile[END_REF][START_REF] Peeters | Improved Higher-Order Side-Channel Attacks with FPGA Experiments[END_REF][START_REF] Standaert | The world is not enough: Another look on second-order DPA[END_REF], which is significantly easier if the masks (and permutations) are known during the profiling phase. Our premise in this chapter is that an adversary is able to obtain such a mixture model via one of these means, and therefore we question its efficient exploitation during the online attack phase.

In this context, a starting observation is that the time complexity of template attacks exploiting mixture models increases exponentially with the number of masks (when masking) and permutation length (when shuffling [START_REF] Veyrat-Charvillon | Shuffling against Side-Channel Attacks: A Comprehensive Study with Cautionary Note[END_REF]). So typically, the time complexity of an optimal template attack exploiting Q traces against an implementation where each n-bit sensitive value is split into Ω shares and shuffled over

Π different positions is in O Q • (2 n ) Ω-1 • Π! , which
rapidly turns out to be intractable. In order to mitigate the impact of this high complexity, we propose a small, well-controlled and principled relaxation of the optimal distinguisher, based on its Taylor expansion (already mentioned in the field of side-channel analysis in [START_REF] Bruneau | Masks Will Fall Off -Higher-Order Optimal Distinguishers[END_REF][START_REF] Ding | A statistical model for higher order DPA on masked devices[END_REF]) of degree L. Such a simplification leads to various concrete advantages. First, when applied to masked implementations, it allows us to perform the (mixture) computations corresponding to the (2 n ) Ω factor in the complexity formula only once (thanks to precomputation) rather than Q times. Second, when applied to shuffled implementations, it allows us to replace the Π! factor in this formula by Π min( Π 6.1 Introduction distinguisher the complexity of the offline profiling is significantly reduced. In general the complexity of the offline profiling becomes equivalent to the complexity of the online attack.

The resulting "rounded template attacks" additionally carry simple intuitions regarding the minimum degree of the Taylor expansion needed for the attacks to succeed. Namely, this degree L needs to be at least equal to the security order O of the target implementation, defined as the smallest statistical moment in the leakage distributions that are key-dependent.

We then show that these attacks only marginally increase the data complexity (for a given success rate) when applied against a masked (only) implementation. More importantly, we finally exhibit that rounded template attacks are especially interesting in the context of highdimensional higher-order side-channel attacks, and put forward the significant improvement of the attacks against the masked implementations with shuffled table recomputations from CHES 2015 [START_REF] Bruneau | Multi-variate High-Order Attacks of Shuffled Tables Recomputation[END_REF].

Contributions. We show that the expansion of the likelihood allows attacks with a very high computational efficiency, while remaining very effective from a key recovery standpoint. This means that the expanded distinguisher requires only little more traces to reach a given success rate, while being much faster to compute.

We also show how to grasp in a multivariate setting several leakages of different orders. In particular, we present an attack on shuffled table recomputation which succeeds with less traces than [START_REF] Bruneau | Multi-variate High-Order Attacks of Shuffled Tables Recomputation[END_REF]. Notice that the likelihood attack cannot be evaluated in this setting because it is computationally impossible to average over both the mask and the shuffle (the sole number of shuffles is 2 n ! ≈ 2 1684 with n = 8).

Finally, we show that are our rounded version of the maximum likelihood allows better attacks than the state-of-the-art. Namely, our attack is better than the classical 2O-CPA and the recent attack of CHES'15 [START_REF] Bruneau | Multi-variate High-Order Attacks of Shuffled Tables Recomputation[END_REF] in all noise variance settings.

Outline. The remainder of the chapter is organized as follows. Sec. 6.2 provides the necessary notations and mathematical definitions. The theoretical foundation of our method is presented in Sec. 6.3. The case study (shuffled table recomputation) is shown in Sec. 6.4. Sec. 6.5 evaluates the complexity of our method. The performance results are presented in Sec. 6.6. Conclusions and perspectives are presented in Sec. 6.7. Some technical results are deferred to the appendices.

TRUNCATION OF OPTIMAL DISTINGUISHER AGAINST SHUFFLED MASKING TABLE

Notations

Randomization countermeasures consist in masking and shuffling protections. When evaluating randomized implementations, there are a number of important parameters to consider. First, the number of shares and the shuffle length in the scheme, next denoted as Ω and Π, are algorithmic properties of the countermeasure. These numbers generally influence the tradeoff between the implementation overheads and the security of the countermeasures. Second, the order of the implementation protected by a randomization countermeasure, next denoted as O, which is a statistical property of the implementation. It corresponds to the smallest key-dependent statistical moment in the leakage distributions. When only masking is applied and the masked implementation is "perfect" (meaning that the leakage of each share is independent of each other), the order O equals to Ω at best. Finally, the number of dimensions (or dimensionality) used in the traces, next denoted as D, is a property of the adversary. In this respect, adversaries may sometimes be interested by using the lowest possible D (since it makes the detection of POIs in the traces easier). But from the measurement complexity point of view, they have a natural incentive to use D as large as possible. A larger dimension D allows to increase the signal to noise ratio [START_REF] Bruneau | Less is More -Dimensionality Reduction from a Theoretical Perspective[END_REF].

In summary, our notations are:

• Ω: number of shares in the masking countermeasure,

• Π: length of the shuffling countermeasure,

• O: order of the implementation,

• D: dimensionality of the leakages.

Examples. Existing masking schemes combine these four values in a variety of manners.

For example, in a perfect hardware masked implementation case with three shares, we may have Ω = 3, O = 3 and D = 1 (since the three shares are manipulated in parallel). If this implementation is not perfect, we may observe lower order leakages (e.g. Ω = 3, O = 1 and D = 1, that is a first-order leakage). And in order to prevent such imperfections, one may use a Threshold Implementation [START_REF] Nikova | Secure hardware implementation of nonlinear functions in the presence of glitches[END_REF], in which case one share will be used to prevent glitches (so Ω = 3, O = 2 and D = 1). If we move to the software case, we may then have more informative dimensions, e.g. Ω = 3, O = 3, D = 3 if the adversary looks for a single triple of informative POIs. But we can also have a number of dimensions significantly higher than the order (which 6.2 Notations usually corresponds to stronger attacks). Let us also give an example of S-boxes masking with one mask, where the masking process of the S-box (often called recomputation) is shuffled. A permutation Φ of Π = 2 n values is applied while computing the masked table. If the attacker ignores the recomputation step, he can carry out an attack on the already computed table.

Hence parameters Ω = 2, O = 2, D = 2 (also known as "second-order bivariate CPA"). But the attacker can also exploit the shuffled recomputation of the S-box in addition to a table look-up, as presented in [START_REF] Bruneau | Multi-variate High-Order Attacks of Shuffled Tables Recomputation[END_REF]; the setting is thus highly multivariate:

Ω = 2, Π = 2 n , O = 2, D = 2 • 2 n + 1.
Interestingly, the Chapt. 5 shows an attack at degree L = 3 which succeeds in less traces than attacks at minimal degree L = O = 2.

In general, a template attack based on mixture distributions (often used in parametric estimation) would require a summation over all random values of the countermeasure, that is R, which consists in the set of masks and permutations. One can represent R as the Cartesian product of the set of mask and the set of permutations. Let us denote by M the set of mask and S the set of permutations. Then R = M × S. Therefore, the cardinality of R is 2 n(Ω-1) Π!.

Eventually, the security of a masked implementation depends on its order and noise level.

More precisely, the security increases exponentially with the order (with the noise as basis) [START_REF] Duc | Making masking security proofs concrete -or how to evaluate the security of any leaking device[END_REF].

So for the designer, there is always an incentive to increase the noise and order. And for adversary, there is generally an incentive to use the largest possible D (given the time constraints of his attack), so that he decreases the noise.

Model

We characterize the protection level in terms of the most powerful attacker, namely an attacker who knows everything about the design, except the masks and the noise. This means that we consider the case where the templates are known. How the attacker got the templates is related with security by obscurity, somehow he will know the model. Of course depending on the learning phase these estimations can be more or less accurate. For the sake of simplicity we assume in this chapter the better scenario where all the estimations are exact 1 .

Besides, we assume that the noise is independently distributed over each dimension. This is the least favorable situation for the attacker (as there is in this case the most noise entropy).

For the sake of simplicity, we assume that the noise variance is equal to σ2 at each point

TRUNCATION OF OPTIMAL DISTINGUISHER AGAINST SHUFFLED MASKING TABLE

d = 1, 2, . . . , D. This allows for a simple theoretical analysis. Let us give an index q = 1, 2, . . . , Q to each trace. For one trace q, the model is written as:

X = y(t, k , R) + N, (6.1)
where for notational convenience the dependency in q and d has been dropped. Here X is a leakage measurement; y = y(t, k , R) is the deterministic part of the model that depends on the correct key k , some known text (plaintext or ciphertext) t, and the unknown random values (masks and permutations) R. Each sample (of index d) of N is a random noise, which follows a

Gaussian distribution p N (z) = 1 √ 2πσ 2 exp -z 2 2σ 2 .

A Generic Log-Likelihood for Masked Implementations

In this section we derive a rounded version of Template Attack. Namely we expand a particular instantiation of the template attack the so-called optimal distinguisher using its Taylor Expansion.

By rounding this expansion at the Lth degree we are able to build a rounded version of the optimal distinguisher (later defined as ROPT L ). This attack features two advantages: it allows to combine different statistical moments and its complexity becomes manageable.

Maximum Likelihood (ML) Attack

The most powerful adversary knows exactly the leakage model (but the actual key, the masks, and the noise are unknown during the online step) and computes a likelihood. In the case of masking the optimal distinguisher which maximize the success rate is given by ( 23): Theorem 6.3.1 (Maximum Likelihood). When the y (t, k, R) are known and the Gaussian noise N is i.i.d. across the queries (measurements) and independent across the dimension, then the optimal distinguisher is:

OPT : R DQ × R DQ -→ F n 2 (x, y (t, k, R)) -→ argmax k∈F n 2 Q q=1 log E exp -x q -y(t q , k, R) 2 2σ 2 (6.2)
where the expectation operator E is applied with respect to the random variable R ∈ R, and the norm is the Euclidean norm x qy(t q , k, R)

2 = D d=1 (x (d) q -y (d) (t q , k, R)) 2 .
Proof. It is proven in [START_REF] Bruneau | Masks Will Fall Off -Higher-Order Optimal Distinguishers[END_REF] that the Maximum Likelihood distinguisher is:

argmax k∈F n 2 Q q=1 r∈R P (
r) p (x q |y (t q , k, r)) .

A Generic Log-Likelihood for Masked Implementations

Applying (6.1) for Gaussian noise and taking the logarithm yields (6.2).

Remark 26. Notice that for each trace q, the Maximum Likelihood distinguisher involves a summation over #R values, which correspond to #R accesses to precharacterized templates.

If D = 1, then the signal-to-noise ratio (SNR) is defined in a natural way as the ratio between the variance of the model Y and the variance of the noise N . But when the setup is multivariate, it is more difficult to quantify a notion of SNR. For this reason, we use the following quantity

γ = 1 2σ 2 , (6.3)
which is actually proportional to an SNR, in lieu of SNR. In practice, we assume that γ is small.

It is indeed a condition for masking schemes to be efficient (see for instance [START_REF] Duc | Making masking security proofs concrete -or how to evaluate the security of any leaking device[END_REF]).

Proposition 29 (Taylor Expansion of Optimal Attacks in Gaussian Noise). The attack consists in maximizing the sum over all traces q = 1, . . . , Q of

+∞ =1 κ ! (-γ) , (6.4)
where κ is the th-order cumulant of the random variable xy(t, k, R) 2 , which can be found inductively from th-order moments:

µ = E R x -y(t, k, R) 2 , (6.5)
using the relation:

κ = µ - -1 =1 -1 -1 κ µ - ( ≥ 1). (6.6)
Proof. The log-likelihood can be expanded according to the increasing powers of the SNR as:

log E exp -γ x -y(t, k, R) 2 = +∞ =1 κ ! (-γ) , (6.7)
where we have recognized the cumulant generating function [START_REF] Stuart | Kendall's Advanced Theory of Statistics: Distribution Theory[END_REF]. The above relation (6.6) between cumulants and moments is well known [START_REF] Weisstein | Cumulant. From MathWorld-A Wolfram Web Resource[END_REF].

Definition 53. The Taylor expansion of the log-likelihood truncated to the Lth degree LL L in SNR is

LL L = L =1 (-1) κ γ ! . (6.8)
Put differently, we have LL = LL L + o(γ L ) (using the Landau notation). The optimal attack can now be "rounded" in the following way:

TRUNCATION OF OPTIMAL DISTINGUISHER AGAINST SHUFFLED MASKING TABLE

Definition 54 (Rounded OPTimal Attack of Degree L in γ). The rounded optimal Lth-degree attack consists in maximizing over the key hypothesis the sum over all traces of the Lth order Taylor expansion LL L in the SNR of the log-likelihood:

ROPT L : R DQ × R DQ -→ F n 2 (x, y (t, k, R)) -→ argmax k∈F n 2 LL L . (6.9)
Proposition 30. If the degree L is smaller than the order O of the countermeasure then the attack fails to distinguish the correct key.

Proof. One can notice that µ combines (by a product) a most terms following the formula:

µ = k1+...+k D = k 1 , . . . , k D E 0<i<D+1 (x (i) -y (i) ) 2•ki , with k 1 + . . . + k d = .
It implies that it exits at most different k i > 0 and as a consequence there are at most different variables in the expectation. Therefore by definition of a perfect masking scheme µ L does not depend on the key. As a consequence LL L with L < O neither depends on the key. Theorem 6.3.2. Let an implementation be secure at order O -1. The lowest-degree successful attack is the one at degree L = O which maximizes LL L . This is equivalent to summing

µ L = E R x -y(t, k, R) 2L ,
over all traces and

• maximize the result over the key hypotheses, if L is even;

• minimize the result over the key hypotheses, if L is odd.

Proof. Since κ is independent of k for all ≤ L, the first sensitive contribution to the loglikelihood is

(-1) L κ L γ L L! .
Now, κ L = µ L + lower order terms (which do not depend on the key as the implementation is secure at order O -1), and removing constants independent of k the contribution to the log-likelihood reduces to (-1) L µ L .

0 m m ′ 1 1 t ⊕ m t ⊕ m ⊕ k 8 9 S[t ⊕ k] ⊕ m ′ 10 ϕ(0) ⊕ m ϕ(0) 4 5 ϕ(1) ⊕ m ϕ(1) 4
5 ϕ(ω) ⊕ m ϕ(ω) 4 5 ϕ(2 n -1) ⊕ m ϕ(2 n -1) 4

Parameters of the Randomization Countermeasure

In order to validate our results we take as example a first order (O = 2), masking scheme where the sensitive variables are split into two shares (Ω = 2). The nonlinear part of this scheme is computed using a table recomputation stage. This step is shuffled (Π = 2 n ) for protection against some known attacks [START_REF] Pan | You cannot hide behind the mask: Power analysis on a provably secure S -box implementation[END_REF][START_REF] Tunstall | Masking Tables -An Underestimated Security Risk[END_REF]. Then an attacker builds highly multivariate attacks with a dimensionality of D = 2 • 2 n + 1. The beginning of this combined countermeasure is given in Algorithm 2 of Chapt. 4.

We used lower case letter (e.g., m, ϕ) for the realizations of random variables, written upper-case (e.g., M , Φ). For the sake of simplicity in the rest of this case study, we assume that m = m .

An overview of the leakages over time is given in Fig. 6.1.

We detail below the mathematical expression of these leakages. The randomization consists in one mask M chosen randomly in {0, 1} n , and one shuffle (random permutation of {0, 1} n ) denoted by Φ. Thus, we denote R = (M, Φ), which is uniformly distributed over the Cartesian product {0, 1} n × S 2 n (i.e. M = {0, 1} n and S = S 2 n ), where S m is the symmetric group of m elements. We have D = 2 n+1 + 2 leakage models, namely:

6. TRUNCATION OF OPTIMAL DISTINGUISHER AGAINST SHUFFLED MASKING TABLE

Second-Order Attacks

As any other high order masking scheme, our example can be defeated by High Order Attacks [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF][START_REF] Messerges | Using second-Order Power Analysis to Attack DPA resistant Software[END_REF][START_REF] Prouff | Statistical Analysis of Second Order Differential Power Analysis[END_REF][START_REF] Waddle | Towards Efficient Second-Order Power Analysis[END_REF]. As our scheme is a first order masking scheme with two shares it can be defeated using a second order attack [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF][START_REF] Messerges | Using second-Order Power Analysis to Attack DPA resistant Software[END_REF] which combines the leakages of the two shares using a combination function [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF][START_REF] Messerges | Using second-Order Power Analysis to Attack DPA resistant Software[END_REF][START_REF] Oswald | Template Attacks on Masking -Resistance Is Futile[END_REF] such as the second order CPA (2O-CPA) with the centered product as combination function.

Using our notation it implies D = 2.

Definition 55 (2O-CPA ( 133)). We denote by 2O-CPA the CPA using the centered product as combination function. Namely:

2O-CPA : R Q × R Q × R Q -→ F n 2 x (0) , x (1) , y -→ argmax k∈F n 2 ρ x (0) x (1) , y , (6.11)
where y = E M (y 0 (t, k, R) y 1 (t, k, R)), is the element wise product and ρ is an estimator of the Pearson correlation coefficient. It can be noticed that as the terms y (0) (t, k, R) and y (1) (t, k, R) only depend on M the expectation is only computed over M.

Remark 29. Here we have assumed without loss of generality that the leakages and the model are centered.

An attacker can restrict himself in order to ignore the recomputation stage. Since such attacker ignores the table recomputation no random shuffle is involved. As a consequence the optimal distinguisher restricted to these leakages becomes computable. Nevertheless as we will see in Sec. 6.6 this approach is not the best. Indeed a lot of exploitable information is lost by not taking into account the table recomputation.

Definition 56 (OPT 2O Distinguisher -Eq. (6.2) for D = 2). We define by OPT 2O the optimal attack which targets the mask and the masked sensitive value.

OPT 2O : R 2Q × R 2Q → F n 2 x (d) , y (d) (t, k, R) d∈{0,1} → argmax k∈F n 2 Q q=1 log E exp   -γ d∈{0,1} f (d) q   , (6.12)
with f (d) q

as defined in Eq. (6.10).

Exploiting the Shuffled Table Recomputation Stage

It is known that the table recomputation step can be exploited to build better attacks than second order attacks [START_REF] Bruneau | Masks Will Fall Off -Higher-Order Optimal Distinguishers[END_REF][START_REF] Tunstall | Masking Tables -An Underestimated Security Risk[END_REF]. Recently a new attack has been presented which remains better

Case Study: Shuffled Table Recomputation

than the 2O-CPA even when the recomputation step is protected [START_REF] Bruneau | Multi-variate High-Order Attacks of Shuffled Tables Recomputation[END_REF]. Let us recall the definition of this attack:

Definition 57 (MVA T R [START_REF] Bruneau | Multi-variate High-Order Attacks of Shuffled Tables Recomputation[END_REF]). The MultiVariate Attack (MVA) exploiting the leakage of the table recomputation (TR) is given by the function:

MVA T R : R Q(2 n+1 +1) × R Q -→ F n 2 x (d) , y d∈{1}∪I∪J -→ argmax k∈F n 2 ρ         - 1 2 i∈I, j=i+2 n x (i) x (j)     x (1) , y     , (6.13)
where, like for Def. 55, y = E M y (0) (t, k, R) y (1) (t, k, R) , is the element wise product and ρ is an estimator of the Pearson coefficient.

Let us now apply our new ROPT L on a block cipher protected with a shuffled table recomputation. In this case the lower moments are given by:

µ = E d f (d) = E     f (0) S[t⊕k]⊕M + f (1) M + i∈I f (i) Φ(ω)⊕M + j∈J f (j) Φ(ω)     .
Proposition 31. The second degree rounded optimal attack (Def. 54 for L = 2) on the table recomputation is:

ROPT 2 : R 2Q × R 2Q -→ F n 2 x (d) , y (d) (t, k, R) d∈{0,1} -→ argmax k∈F n 2 Q q=1 E(f (0) q × f (1) q ). (6.14)
Proof. Combine Theorem 6.3.2 and Eq. (C.9) of Appendix C.1.2.

Remark 30. The ROPT 2 which targets the second order moment happens not to take into account the terms of the recomputation stage. Naturally the only second order leakages are also the ones used by 2O-CPA and OPT 2O distinguishers.

Proposition 32. The third degree rounded optimal attack (Def. 54 for L = 3) on the table recomputation is:

ROPT 3 : R (2 n+1 +2)Q × R (2 n+1 +2)Q -→ F n 2 x (d) , y (d) (t, k, R) d∈{0,1}∪I∪J -→ argmax k∈F n 2 Q q=1 µ 2q (1 + γµ 1q ) -γ µ 3q 3 , (6.15)
where the values of µ 1q , µ 2q and, µ 3q are respectively provided in Eq. (C.

Complexity

In this section we give the time complexity needed to compute OPT and ROPT L . We also show that when L D the complexity of ROPT L remains manageable whereas the complexity of OPT is prohibitive. In this section all the complexities are computed for one key guess.

Complexity in the General Case

Let us first introduce an intermediate lemma.

Lemma 7. The complexity of computing µ (for one trace) is lower than:

O D + -1 • 2 (Ω-1)n • Π min Π 2 , . (6.16)
Proof. See Appendix C.2.1.

Proposition 34. The complexity of OPT is:

O Q • (2 n ) Ω-1 • Π! • D . (6.17)
The complexity of ROPT L is lower than: This means that for Q large enough i.e. when γ is low enough this computational "trick" allows a speed-up factor of 2 (Ω-1)n Π min( Π 6.6 Simulation Results

O Q • L • D + L -1 L • 2 (Ω-1)n • Π min Π 2 , L . ( 6

Complexity of our Case Study

Let us now compute the complexity of these two distinguishers applied to our case study. Of course an approach could be to use the formula of the previous section 6.5.1. But one can notice that a lot of terms could be independent of the key and as consequence not needed in an attack.

Another approach is to use the formula of the distinguisher.

Proposition 36. The complexity of OPT is:

O Q • (2 n ) • 2 n ! • 2 n+1 + 2 . (6.19)
The complexity of ROPT 2 is:

O (Q • 2 n ) . (6.20)
The complexity of ROPT 3 is lower than:

O Q • 2 4n . ( 6

Simulation Results

In this section we validate in simulation the soundness of our approach for the case study described in Sec. 6.4.1. The results of these simulations are expressed in success rate (defined in [START_REF] Standaert | A Unified Framework for the Analysis of Side-Channel Key Recovery Attacks[END_REF] and denoted by SR). All simulations are computed using the Hamming weight model as a leakage model. As we assume an attacker with a perfect knowledge, the leakages are the model (denoted by y) plus some noise. The noise is Gaussian with a standard deviation of σ.

In Subsec. 6.6.1 we assume that the attacker does not take into account the table recomputation stage. He only targets the leakages of the mask and the masked share (the leakage of masked S-Box). Namely the leakages which occurs in lines 1 and 10 of Algorithm 2. This approach allows to compute the restricted version of the maximum likelihood. We compare the results of the maximum likelihood, our rounded version and the high order attacks.

TRUNCATION OF OPTIMAL DISTINGUISHER AGAINST SHUFFLED MASKING TABLE

In Subsec. 6.6.2 we present our main results. In this subsection the attacker can exploit the leakage of the mask, the masked share and all the leakages of the table recomputation. In this scenario we show that our rounded version of the optimal distinguisher outperforms all the attacks of the state-of-the-art.

Exploiting only Leakage of the Mask and the Masked Share

In this subsection all the attacks are computed using only the leakages of the line 1 and the line 10 of Algorithm 2 of Chapt. 4.

In this case study we assume a perfect masking scheme with: Y (0) = HW[M ] and Y (1) =

HW[S[T ⊕ k] ⊕ M ].
It can be seen in Fig. 6.2 that even for small noise (σ = 1, Fig. 6.2a) the 2O-CPA and ROPT 2 are equivalent. Indeed the two curves superimpose almost perfectly (in order to better highlight a difference, as many as 1000 attacks have been carried out for the estimation of the success rate). Moreover these two attacks are nearly equivalent to the optimal distinguisher (we recover here the results of ( 23)). We can notice that for both σ = 1 and σ = 2, ROPT 4 is not as good as ROPT 2 . This means that the noise standard deviation is not large enough for approximations of higher degrees to be accurate. Indeed when the noise is not low enough the weight of each term of the decomposition can be such that some useful terms vanish due to the alternation of positive and negative terms in the Taylor expansion.

Let us recall that the decomposition of Eq. (6.8) is valid only for low γ = 1/(2σ 2 ) i.e. high noise. The error term ( o(γ L )) in by the Taylor expansion gives the asymptotic evolution of this error when the noise increases but does not provide information about the error for a fixed value of noise variance. This means that the noise is too small for ROPT 4 to be a good approximation of OPT although ROPT 2 is nearly equivalent to OPT.

For σ = 2 the noise is high enough to have a good approximation of OPT by ROPT 4 . For this noise all the attacks are close to OPT (Fig. 6.2b).

In the context where only the mask and the masked share are used it is equivalent to compute the 2O-CPA, ROPT 2 and OPT. As a consequence in the rest of this chapter only the 2O-CPA will be displayed.

To conclude our ROPT L is in this scenario at least as good as the HO-CPA of order L, which validates the optimality of state-of-the-art attacks against perfect masking schemes of order O = L.

Exploiting the Shuffled Table Recomputation

In this subsection the attacker can target the leakage of the mask, the masked share and all the leakages occurring during the table recomputation. As a consequence the attacks of Subsec. 6.6.1 remain possible. It has been shown in [START_REF] Bruneau | Masks Will Fall Off -Higher-Order Optimal Distinguishers[END_REF][START_REF] Standaert | The world is not enough: Another look on second-order DPA[END_REF] that the 2O-CPA with the centered product becomes close to the OPT 2O (the Maximum Likelihood) when the noise becomes high. It is moreover confirmed by our simulation results as it can be seen in Fig. 6.2. We choose as attack reference for the Fig. 6.3 and Fig. 6.4 the 2O-CPA and not the OPT 2O because it performs similarly 6.2 and it is much faster to compute (see Table C.1) which is mandatory for attacks with high noise (e.g. for σ = 12) which involve many traces.

Following the formulas provided previously empirical validations have been done. For σ ≤ 8 the attacks have been redone 1000 times to compute the SR. For σ > 8 the attacks have been done 250 times. Results are plotted in Fig. 6.3 and Fig. 6.4. In these figures the results of the 2O-CPA, the MVA T R and ROPT 3 are plotted. Noticed that the likelihood is not represented because we cannot average over R.

Recall that the cardinality of the support of R is 2 n × 2 n !. It can be first noticed that for all the noises ROPT 3 is the best attack.

Let us analyze how much better ROPT 3 is than 2O-CPA and MVA T R . The comparison with our new attack can be divided in three different categories. For low noise σ = 3 (see Fig. 6.3b) the results of ROPT 3 are similar to the results of MVA T R . This means that the leakage of the shuffled table recomputation is the most leaking term in this case. At the opposite when the noise is high (for σ = 12 see Fig. 6.4c) ROPT 3 becomes close to 2O-CPA which means that

TRUNCATION OF OPTIMAL DISTINGUISHER AGAINST SHUFFLED MASKING TABLE

as expected the most informative part is the second order term. For medium noise 7 ≤ σ ≤ 9 (see Fig. 6.3d, Fig. 6.4a and Fig. 6.4b) the results of ROPT 3 are much better than the result of 2O-CPA and MVA T R . Moreover, the gain compared to the second best attack is maximum when the results of 2O-CPA and MVA T R are the same. Indeed for σ = 7 (see Fig. 6.3d), ROPT 3 needs 35000 traces to reach 80% of success whereas MVA T R (the second best attack) needs 60000 traces. This represents a gain of 71%. For σ = 8 (see Fig. 6.4a), ROPT 3 needs 65000 traces to reach 80% of success whereas the MVA T R and the 2O-CPA needs 120000 traces. This represents a gain of 85%. And when the noise increases to σ = 9 (see Fig. 6.4b), ROPT 3 needs 120000 traces to reach 80% of success whereas 2O-CPA (the second best attack) needs 200000 traces, which is a gain of 66%.

These results can be interpreted as follows: The MVA T R is a third order attack which depends on the third order moment. The 2O-CPA is a second order attack which depends on the second order moment. The new ROPT 3 attack combines these two moments. When the noise is low the MVA T R and the ROPT 3 performs similarly; this shows that the dominant term in the Taylor expansion is the third order one. At the opposite when the noise increases the ROPT 3 becomes close to the 2O-CPA which indicates that the important term in the Taylor expansion is the second order one. As ROPT 3 combines the second and the third order moment weighted by the SNR it is always better than any attack exploiting only one moment.

Conclusions and Perspectives

In this chapter, we derived new attacks based on the Lth degree Taylor expansion in the SNR of the optimal Maximum Likelihood distinguisher. We have shown that this Lth degree truncation allows to target a moment of order L. The new attack outperforms the optimal distinguisher with respect to time complexity. In fact as we have theoretically shown, the Taylor approximation can be effectively computed whereas the fully optimal maximum likelihood distinguisher, was not computationally tractable.

We have illustrated this property by applying our new method in a complex scenario of "shuffled table recomputation" and have compared the time complexity of the new attack and the optimal distinguisher. In addition, we have shown that in this context our attack has a higher success rate than all the attacks of the state-of-art over all possible noise variances.

An open question is how to quantify the accuracy of the approximation LL -→ LL as a function of the noise. In other words, what is the optimal degree of the Taylor expansion of the likelihood for a given SNR? Another interesting extension of this framework would be on hardware devices which are known to leak at various orders (see the real-world examples in [START_REF] Moradi | Statistical tools flavor side-channel collision attacks[END_REF][START_REF] Moradi | Moments-correlating DPA[END_REF][START_REF] Moradi | Assessment of hiding the higher-order leakages in hardware -what are the achievements versus overheads?[END_REF]).

CHAPTER 7

Conclusion

Side-Channel Analysis are still a very dynamic research area in which new results are continuously published. In this manuscript we proposed different ways to improve the results of SCA. We have both explored them in empirical and theoretical manners. We were especially interested in the exploitation of multiple leakages to improve the success of the SCA. We have shown that this behavior of Side channel measurements is a meaningful way to improve the attacks.

In particular in the first part of this manuscript (Part I) we have shown the possible exploitations of multiple leakages of a unique variable. In Chap. 2 we studied the optimal way to exploit this kind of leakages in order to maximize the Success Rate in a profiling scenario.

We have shown that in the context of a powerful attacker with a full knowledge of the leakage function it coincides with a dimensionality reduction. In this context we gave the exact formula of this reduction and linked it with two classical dimensionality reduction tools the PCA and the LRA. Specifically we have shown that our new dimensionality reduction is asymptotically 7.2 Perspectives.

functions and different masking schemes at different orders. Finally we additionally gave some countermeasures. In Chap. 6 we theoretically investigated how far an attacker can exploit these leakages. As a consequence we put themselves in the case of an attacker with full knowledge of the models. In this context we showed that the main issue is the complexity of the optimal attack. In order to avoid this, we presented a new attack based on a truncated version of the Taylor Expansion of the Maximum Likelihood. This new attack retains the efficiency property of the Maximum Likelihood by completely out performing the results of all known attacks. As a truncated version this new attack has a better effectiveness and as a consequence is computable.

Moreover it gives interesting insight on the behavior High Order attacks. Indeed contrary to the state-of-the-art attack a better attack will take into account the leakages at different orders and combined them using the SNR as weight. These features highlight the fact these attacks are close to the combinations of attacks at different orders. They exploit different combination of variables. As a consequence these attacks are multi-target.

In this study we showed that the number of exploitable leakage samples is a fundamental parameter in the evaluation of the security of the implementation of cryptographic algorithms.

Especially we showed that the order of the implementation of the masking scheme is not a sufficient criterion to ensure the security of protected implementations.

7.2 Perspectives.

Under Review.

During this thesis we investigated some other research paths which are not part of this manuscript and are now under review.

Success Exponent. The first one is to identify the relevant parameters of the success of the SCA in cases of protected implementations. In order to investigate these parameters an interesting way is to extent the results of the Success Exponent in the cases of protected implementations. We already extended these results in the case of High Order masking schemes, shuffling implementations and noise addition. In this context we showed that the SNR of each shares play a fundamental role. As in the unprotected cases the confusion coefficient is another important parameter. As already mentioned in the state-of-the-art the impact of the order is in the number of products needed to recover a value depending on the key. As a consequence the maximum degree of the polynomial in the noise variance will depend on the order of the 7. CONCLUSION implementation of the masking schemes. The overall gain of the exploitation of the multiple leakages will be then in the coefficient of the polynomial.

Horizontal Attacks. It is well-known that the leakages of multiple variables are an effective way to attack protected implementations of asymmetric cryptography algorithms. Indeed the so called "horizontal" attacks are ones of the most effective ways to defeat such implementations.

During this thesis we investigated how these attacks can be improved using machine learning methods. We showed that the uses of particular distances in cluster algorithms may improve the results of attacks based on clustering.

Stochastic Collision Attacks. We showed that in order to attack protected implementations multi-target attacks are an efficient tool. These attacks combined the leakages of the key dependent variables but also the variables involved in the countermeasures. A classical kind of attacks which exploit several variables in order to break protected implementation are the so called collision attacks. One our current work introduces the so called stochastic collision which combined the behaviors of collision attacks and stochastic attacks. Interestingly this new attack can be applied on masking schemes. The simulation results show that this new attack gives better results than the state-of-the-art collision attacks.

Research Perspectives.

In this thesis we showed that the exploitation of multiple leakages improves the result of SCA.

Interestingly we showed that the parameters of the multiplicity of leakages have a greater impact than the order of the implementation. As a consequence the order has to be be seen more as a design parameter than a security parameter even if of course it has an impact of the security of the implementation. As the order is not a sufficient parameter to evaluate the security of protected implementations, the security should be established using other parameters.

Specifically it should be based on the number of leakages, the number of variables and their possible combinations. Any security evaluation should be based on a detailed analysis of the masking schemes where all combinations of variables should be considered.

Additionally an interesting perspective is to combined, in the context of protection implementation, the different methods presented in this manuscript with the recent results of multi-target attacks. In this context exploiting the multiple, possibly masked, leakages of the different parts of the cipher algorithm should lead to significant improvements.

Part III

Appendix.

B.4 Affine model

Proof. As Lemma 10 gives us the variance of the noise of the second-order leakage we have ∀i < Ω SNR X CS Ω i , M i SNR X

(3)

i , M i ⇐⇒ Var [HW[M ]] Var X CS Ω i |M i = m Var [HW[M ]] Var N (3) i ⇐⇒ 4 × σ 2 Ω × 2 n × n 2 + σ 4 Ω × 2 n σ 2 ⇐⇒ n -Ω × 2 n-1 σ 2 Ω × 2 n-1 + σ 4 Ω × 2 n-2 0.
The upper bound of the interval are the σ 2 where σ 2 = 0 and:

σ 4 Ω × 2 n-2 = d × 2 n-1 -n σ 2 Ω × 2 n-1 ⇐⇒ σ 2 = d × 2 n-1 -n 2 ⇐⇒ σ 2 = d × 2 n-2 - n 2 .
It implies that the size of Useful Interval of Variance is given by d × 2 n-2 -n 2 .

B.4 Affine model

B.4.1 Proof of Lemma 5

Proof.

E [(Ψ α (U ) -E [Ψ α (U )]) × (Ψ β (U ⊕ z) -E [Ψ β (U ⊕ z)])] = E α • U -α • 1 2 1 × β • (U ⊕ z) -β • 1 2 1 = E α • U - 1 2 1 × β • (U ⊕ z) - 1 2 1 = E 1 2 α • U × 1 2 β • U ⊕ z = 1 4 α t E U U ⊕ z t β ,
where U denotes 2 U -1 2 1 . It can also be noticed that: U = -(-1) U1 , . . . , (-1) Un , and thus (U ⊕ z) = -(-1) U1+z1 , . . . , (-1) Un+zn .

Moreover Let us first prove the following result:

E U U ⊕ z t = Cov U , U ⊕ z t =⇒ E U U ⊕ z t i,j = Cov (-1) Ui , ( -1)
Lemma 12. Let x ∈ R n and let p, q two integers such that p > q > 0. Then:

n 1 p -1 q x q x p x q . (B.6)
These two bounds are tight. Indeed, ∀i, j, x i = x j =⇒ n 1 p -1 q x q = x p ∃i/x i = 0 and ∀i = j, x j = 0 =⇒ x p = x q .

Proof. Let us first prove the lower bound of Eq. (B.6). By the Hölder inequality we have:

i |x i | q i (|x i | q ) P 1 P i (1) Q 1 Q
where P = p q and Q = p pq .

So, we have, i |x i | q x q p n 1-q p , i.e., x p n 1 p -1 q x p . Then let us prove the upper bound. We have i |xi| q x q q = 1. Hence, for all 1 i n, |xi| q x q q 1.

Therefore, for all i, |xi| p x p q |xi| q x q q , hence i |xi| p x p q i |xi| q x q q = 1, which yields the announced inequality: x p p x p q . Let us prove the sufficient conditions when the inequalities become equalities: ∀i, j, x i = x j =⇒ x p = |x i |n 1 p and x q = |x i |n 1 q =⇒ x p = x q n 1 p -1 q ∃i, x i = 0 and ∀i = j, x j = 0 =⇒ x p = |x i | and x q = |x i | =⇒ x p = x q .

These terms (for all j ∈ J) correspond to the MVA T R attack published at CHES 2015 [START_REF] Bruneau | Multi-variate High-Order Attacks of Shuffled Tables Recomputation[END_REF].

Eventually, there are the terms for j = i -2 n . They are actually key dependent, hence must be kept. They are equal to:

E(f (0) f (i) f (j =i+2 n ) ) = 1 2 n m∈F n 2 (x (0) -HW[S[t ⊕ k] ⊕ m]) 2 × 1 2 n 1 2 n -1 (m ,m )∈F n 2 ×F n 2 s.t. m =m (x (i) -HW[m ]) 2 (x (j) -HW[m ⊕ m]) 2 .
Interestingly, without the constraint m = m , this quantity does not depend on the key. So, the leakage which is exploited here is due to the fact Φ is not a random function, but a bijection.

As, in µ 3 , we are only interested in non constant terms, we can rewrite:

E(f (0) f (i) f (j =i+2 n ) ) = cst - 1 2 n m∈F n 2 (x (0) -HW[S[t ⊕ k] ⊕ m]) 2 × 1 2 n 1 2 n -1 (m ,m )∈F n 2 ×F n

C.2.4 Proof of Proposition 36

Proof. In our case study the size of the permutation is Π = 2 n . Then the complexity of OPT is given by a straightforward application of Eq. (6.17). From Eq. (6.14) we have that for ROPT 2 the computation for one key guess and one trace is given by E(f (0) × f (1) . In this equation the expectation is computed over 2 n values (Eq. (C.7)).

From Eq. (6.15) we have that for ROPT 3 the computation for one key guess and one trace is given by µ (q)

2 (1 + γµ (q) 1 )γ µ (q) 3

3 . It can be seen in Eq. (C.2), Eq. (C.3), Eq. (C.4) and Eq. (C.6) that the expectation of µ 1 is computed over 2 n values. The dominant term in µ 3 (Eq. (C.12)) is :

2 n +1 i=2 j∈{2+2 n ,...,2 n+1 +1}\{i+2 n } 2 2n E 2 2n (f (0) f (i) f (j) ).
The expectation in this term is computed over 2 2n values (Eq. (C.11)). The sum is computed on less than 2 2n .

C.2.5 Time and complexity

The times of the section are expressed in seconds. All the attacks have been run on Intel Xeon X5660 running at 2.67 GHz. All the implementations are mono-thread. The model of the simulations is the one describe in Sec. 6.6. For each distinguisher the attacks are computed 1000 times on 1000 traces.

C. APPENDIX OF MIXED ORDER.

Attack

Dimension Time (in seconds) Computational Complexity Recently an open implementation of a masking scheme with shuffling has been presented in the DPA contest v4.2 [START_REF]DPA Contest[END_REF]. In this implementation the execution of the different states is performed in an random order.

2O-CPA 2 39 O (Q) ROPT 2 2 295 O (Q) OPT 2O 2 9473 O (Q • (2 n )) MVA T R 2 n+1 + 1 130 O (Q • 2 n ) ROPT 3 2 n+1 + 2 2495 O Q • 2 2n OPT 2 n+1 + 2 Not computable O Q • (2 n ) • 2 n ! • 2 n+1 + 2
An attacker can target the integrated leakages of the different states in order to counter the shuffling [START_REF] Clavier | Differential Power Analysis in the Presence of Hardware Countermeasures[END_REF][START_REF] Rivain | Higher-Order Masking and Shuffling for Software Implementations of Block Ciphers[END_REF].

A better approach is to take into account the possible leakages of the permutation. In this case the optimal distinguisher will be not computable as it involves an expectation over 16! values. In this case the rounded optimal attack will reduced this complexity.

Let us define the leakages of such implementations.

• X (0) = y (0) (t, k, R) + N (0) with y (0) (t, k, R) = HW[M ],

• X (1) = y (1) (t, k, R) + N (1) with y (1) (t, k, R) = HW[S[π (T ⊕ k)] ⊕ M ],

• X (i) = y (i) (t, k, R) + N (i) , for i = 2, . . . , 18 with y (i) (t, k, R) = HW[Φ(i -2)],

Then similarly to the Appendix C.1 we have that:

µ 1 = E(f (0)
) + E(f (1) ) + Additionally as it is a low entropy masking scheme the secret key can leaked in an univariate high order attack. Depending on the number of masks involve in the masking scheme it could be at order 2, 3 or more. For simplicity let us assume it is at order 3. In such cases C.3 Analysis of the DPAcontest.

µ 3 = E(f (1) 3 ) + 3E(f (0) 2 f (1) ) + 3E(f (0) f (1) 2 ) + 3!

2 n +1 i=2 E(f (0) f (1) f (i) ) + cst. (C.17)
Of course an attacker can additionally exploit all the leakages of the different states in order to increase the success of the attacks.

In some particular low entropy masking schemes the same masks are reused several time or are linked by deterministic relations (e.g the first version of the DPAcontest). In this context it could be interesting to combine the leakages of different states [START_REF] Bruneau | Boosting Higher-Order Correlation Attacks by Dimensionality Reduction[END_REF]. In this case our method could benefit of the multiple possible points combinations.

Figure 1 :

 1 Figure 1: Exemple de trace de consommation

  Leakage D α = cov(X; Ψ(Z)) ||cov(X; Ψ(Z))|| Correlation |ρ(X; Ψ(Z))|Distinguishers:

Figure 4 .

 4 Ces attaques sont notées dans ce manuscrit 2×CPA mt . On en déduit donc que la meilleur approche est d'exploiter l'ensemble des fuites en une en appliquant l'attaque optimale.

Figure 3 :

 3 Figure 3: Comparaison entre une attaque CPA du second ordre classique et une attaque second ordre CPA avec prétraitement utilisant (S-boxes, S-Boxes)

  Du fait des deux combinaisons successives cette nouvelle attaque est une attaque du troisième ordre. Cette attaque est notée MVA T R . Nous pouvons vérifier de plus que cette attaque sera plus efficace que les attaques de l'état de l'art lorsque la variance du bruit est comprise dans un xiv

Figure 4 :

 4 Figure 4: Taux de succès contre les tables masquées.

Figure 5 :

 5 Figure 5: Comparaisons entre 2O-CPA et MVAT R

Finalement

  nous validons ces résultats sur une carte puce. La cible est une implémentation en assembleur d'un AES-128 avec recacul de table. Cette implémentation à été chargée sur une ATMEL ATMega163 8-bit. Cette carte à puce est connue pour fuiter. Les attaques sont xvi

Figure 6 :

 6 Figure 6: Comparaisons entre 2O-CPA et MVAT R

Figure 7 :

 7 Figure 7: Comparaison entre ΩO-CPA et MVA Ω CS

Figure 8 :

 8 Figure 8: Comparaisons des SR des attaques MVAT R et 2O-CPA

ROPT 3

 3 est proche de l'attaque 2O-CPA. Cela veut dire que le terme dominant est le terme de degré deux. Le meilleur cas pour l'attaque ROPT 3 comparé aux attaques de référence est lorsque σ = 8. Dans ce cas les attaques 2O-CPA et MVA T R ont les mêmes résultats et l'attaque ROPT 3 à des résultats deux fois meilleurs.

Figure 9 : 1 . 6 . 3

 9163 Figure 9: Attaque sur le recalcul de table

3. 1 3 . 2 . 2

 1322 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Theoretical optimal preprocessing function . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Case study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxii CONTENTS Principal component analysis . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.2.3 Preprocessing on modulated side channel traces . . . . . . . . . . . . . . . 59 3.2.4 Covariance vector as a preprocessing method . . . . . . . . . . . . . . . . 61 3.2.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.2.6 Time vs Frequency domains . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.3 Empirical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.3.1 Implementation of the masking scheme . . . . . . . . . . . . . . . . . . . . 64 3.3.2 Leakage analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.3.3 Experimental protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.3.4 Comparison of the two preprocessing methods and classical second-order CPA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 3.3.5 How is the preprocessing linked to the noise? . . . . . . . . . . . . . . . . 69 3.4 On the fly preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.4.1 Case study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.4.2 Empirical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.5 Conclusions and Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 II Multivariate Leakages of a Masking Scheme with

2. 2

 2 Estimated α D (left) and Σ (right), for Q = 10, 000 traces . . . . . . . . . . . . . 3.1 Big picture of the "covariance method". The usual 2O-CPA computes a correlation for each pair (d 1 , s 2 ) of leakage (step (1)), and then searches for a maximum over the keys and the time instances (step (2)). Our new method obtains a "covariance vector" (termed α) on a "learning device" (step (0')), and then first projects the leakage X on α (step (1')), before looking for the best key only while maximizing the distinguisher (step (2')). Notice that the model Ψ(Z) depends implicitly on the key guess k. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Covariance absolute value, for (a) XOR and (b) S-box . . . . . . . . . . . . . . . 3.3 Covariance absolute value, for (a) S-box and (b) S-box+ShiftRows . . . . . . . . 3.4 Comparison between the classical second-order CPA and second-order CPA with preprocessing using (XOR, S-Boxes) . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Comparison between the covariance vector and the first eigenvector . . . . . . . . 3.6 Comparison between the classical second-order CPA and second-order CPA with preprocessing using (S-boxes, S-Boxes) . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Comparison between the covariance vector and the first eigenvector . . . . . . . . 3.8 Comparison between 2O-CPA with preprocessing method and without in presence of Gaussian noise, with a standard deviation of 3 for (a) with a standard deviation of 5 for (b) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Comparison between covariance and PCA depending on the size of the learning base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.10 Comparison between covariance in line preprocessing and 2O-CPA . . . . . . . . 4.1 Success Rate for masking table. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 State-of-the-art attack and new attack investigated in this chapter. . . . . . . . . 5.2 Comparison between the variance of the noise for the classical leakage and the second-order and the impact of these noises on the SNR . . . . . . . . . . . . . . 5.3 Comparison between 2O-CPA and MVA T R . . . . . . . . . . . . . . . . . . . . . 5.4 Comparison between the 2O-CPA and the MVA T R . . . . . . . . . . . . . . . . . 5.5 Comparison between the signal to noise ratio of X (3) i and signal to noise ratio of X CS Ω i (where Ω is the attack order). . . . . . . . . . . . . . . . . . . . . . . . . . xxviii LIST OF FIGURES 5.6 Comparison between ΩO-CPA and MVA Ω CS . . . . . . . . . . . . . . . . . . . . . 106 5.7 Comparison of min k =0 κ k for the MVA T R and the 2O-CPA . . . . . . . . . . . . 109 5.8 Comparison between 2O-CPA and MVA T R for ε = 0.9 . . . . . . . . . . . . . . . 111 5.9 Comparison between 2O-CPA and MVA T R for ε = 0.5 . . . . . . . . . . . . . . . 112 5.10 Comparison between the 2O-CPA and the MVA T R in case of one bit model in presence of High Gaussian noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.11 Comparison of the SR of the MVA T R and the 2O-CPA . . . . . . . . . . . . . . . 114 5.12 MVA T R with commutative function as countermeasure. . . . . . . . . . . . . . . 117 6.1 Leakages of the shuffled

1. 1

 1 Introduction to the cryptography two bit-strings: the key and the plain-text and output a bit-string: the cipher-text. The key length and the plain-text length are two parameters associated with the block cipher algorithm.

  , MARS (28) which are the Advanced Encryption Standard finalists, but also the Data Encryption Standard (119) (DES), the Triple Data Encryption Standard (119) (TDES), the International Data Encryption Algorithm (90) (IDEA)... Let us present in more details two of them which are standardized: the Data Encryption Standard (119) (DES) expended from the Lucifer (153) cipher and the Advanced Encryption Standard (AES (118) originally called Rijndael) Data Encryption Standard (119). The DES algorithm is one of the most widely used block cipher algorithm. It was adopted by the National Bureau of Standards (NBS) now known as the National Institute of Standards and Technology (NIST) in 1976 as a standard. The DES takes as input a key of 56 bits and 64 bits of plain-text. The algorithm consists in 16 rounds of a "Feistel network". In order to increase the size of the key an evolution of the DES has been proposed: the Triple DES where three DES are executed sequentially with a three times longer key.

  1998 a new competition to select the new standard block cipher. Fifteen candidates have been proposed and at the end of the selection process the Rijndael algorithm has been chosen to be the AES. This cipher takes as input a key of length 128, 256, 512 depending on the level of security required. The plain-text has a length of 128 bits. The algorithm consists of 10, 12 or 16 rounds depending on the length of the key. Each round is composed of different operations ensuring the diffusion and confusion.

1. 1

 1 schemes are based on one-way functions meaning that they are easy to compute and difficult to invert with a trapdoor meaning that they are easy to invert given an extra information. The TrapDoor One Way Function (TOWF) are relied to a hard problem. In one hand the security of the asymmetric is based on the difficulty to solve this problem without any extra-information.

  an asymmetric cryptography primitive which allows a key exchange without trusted authority. The hard problem is in this case the Diffie-Hellman Problem (DHP) Definition 1 which is itself closed to the Discrete Logarithm Problem (DLP) Def. 2. Nevertheless the DHP is at least as easy as the DLP. Definition 1 (Diffie-Hellman Problem). Given a prime p a generator α of Z * p , and elements α a mod p and α b mod p find α ab mod p. Definition 2 (Discrete Logarithm Problem). Given a prime p a generator α of Z * p , and an element β ∈ Z * p find the integer x 0 ≤ x ≤ p -2 such that α x ≡ β mod p. 1.1.2.2 Rivest Shamir Adleman (RSA) cryptosystem (144) In 1978 Rivest Shamir and Adleman proposed a first example of asymmetric encryption algorithm and signature scheme in (144) it is the well known RSA cryptosystem. This cryptosystem is based on the difficulty of factoring integers which are the products of large primes. The underlying hard problem is the RSA problem (RSAP) Def. 3 which is to find the inverse of the TOWF of the protocol. This problem is closely linked to the factoring problem Def 4. Indeed finding a solution of the factoring problem gives a solution to the RSAP, as a consequence the RSAP is at least as easy as the factoring problem.

. 1 . 2

 12 In 1988 Taher ElGamal has proposed an asymmetric cryptosystem and a signature scheme based on the DLP. While the first publication of Diffie Hellman provides a first example of asymmetric cryptography algorithm for the key exchanges ElGamal algorithms are the first ones to used the DLP to build encryption scheme and digital signature.The previous schemes need to compute a modular exponentiation that is for the given positive integer m the modulus n and an exponent e computing m e mod n. 1.1.2.4 Elliptic Curves cryptosystem (82, 110) In 1985 Neal Koblitz (82) and Victor Miller (110) have independently presented a new cryptosystem based on Elliptic Curves (EC). The EC Cryptography is based on the difficulty to solve the Elliptic Curve Discrete Logarithm Problem (ECDLP). Currently the best known algorithm to solve this problem has an exponential running time. This allows smaller key length compared to RSA. Indeed the factoring problem can be solved in sub-exponential times. Different cryptographic algorithms have been proposed exploiting ECDLP. Smaller keys are a real advantage especially in the embedded systems where the memory can be limited. ECC provides signature, encryption and key exchange primitives. Definition 5 (Discrete Logarithm Problem). Given an elliptic curve E over a finite field K, an integer k and points P ∈ E (K) and Q = [k]P ∈ E (K) find k where [k]P = P + ... + P k times Physical Attacks Classical cryptographic algorithms are guessed to be secured in a black box model where only the algorithm and some couples plain-text cipher-text are known by the attacker. In such models classical cryptanalysis exploit intrinsic properties of the cryptographic algorithms in order to recover sensitive information. Nevertheless cryptographic algorithms never come alone and are implemented on physical devices e.g smart-cards, micro-controllers. In the rest of the manuscript we call the device on which the cryptographic algorithms are running the Device Under Test (DUT).

1. 2

 2 Physical Attacks Active Attacks. In an active attack the attacker could modify the execution of the algorithms executed on the DUT. The Fault Attacks are a classical example of active attacks. They consist in faulting the execution of the algorithms in order to recover the sensitive values. Since their introduction by Boneh et al. in (17) they received many publications introducing different ways to inject fault, different target values and different exploitation steps. To inject fault an attacker can use Optical fault injection (152) (using for example a Light Amplification by Simulated Emission of Radiation), Electromagnetic fault injections (136) or other means (17, 88, 148)... The target of Fault injection can be several kinds of values such as the Input Parameters (10), the Data processing path (126) or the instruction processing path (178)... Finally different methods have been proposed to exploit the faults in order to recover sensitive values: Differential Fault Attacks (DFA) (15), Safe error attacks (183)... Passive Attacks. Contrary to the Active Attacks the Passive Attacks do not interact with the DUT. They may consist in observing some physical informations the so called Side Channel Information emitted by the device during the execution of the cryptographic algorithms. Attacks exploiting such information are called the Side Channel Attacks later denoted by SCA. SCA exploit various type of physical measurements such as the power consumption of the devices (83),

Figure 1 . 1 :

 11 Figure 1.1: Example of a modulated trace

Figure 1 . 2 :

 12 Figure 1.2: Schematic of a linear part of a masking scheme of a block cipher.

Fig. 1 . 3 .

 13 An attacker can target two different operations the AddRoundKey or SubBytes separately or jointly using three different variables: the random values, the mask value during the AddRoundKey and the mask value during SubBytes. These variables may leak through many different time samples (31 in this example). In order to illustrate this property let us give some examples in Tab. 1.1.

. 40 )

 40 Exploiting this formula different analysis have been performed to study the relevant parameters[START_REF] Fei | A Statistical Model for DPA with Novel Algorithmic Confusion Analysis[END_REF][START_REF] Rivain | On the Exact Success Rate of Side Channel Analysis in the Gaussian Model[END_REF][START_REF] Thillard | Success through Confidence: Evaluating the Effectiveness of a Side-Channel Attack[END_REF] of the SR. In (53) Fei et al. provided a closed form expression of the SR for the DPA distinguisher. Exploiting this expression they showed that the SR depends on three main parameters:

  ) as only the DPA was taken into account the leakage model was the one bit one. Thillard et al. extended in (170) the notion of confusion coefficient for any leakage models and then give the closed form expression of the SR for the CPA. Recently an approach based (63) on the Success Exponent (SE) allows to derive the closed form expression of the SR for different distinguishers (DPA MIA and CPA). In this manuscript we used their definition of the confusion coefficient.

Fig. 1 .Figure 1 . 4 :

 114 Fig. 1.4 shows the different axes to improve the results of SCA. Indeed the classification of the

  The SNR gain is equal to the dimension D at first order, which is consistent with Proposition 3. In addition, that gain is never greater than D, since D(1-ρ)+2ρ 1+ρ ≤ D(1-ρ)+2Dρ 1+ρ = D. Therefore, when SNR 1 = . . . = SNR D , nonzero values of correlation ρ decrease the efficiency of dimensionality reduction, the most favorable situation being the case of white noise samples.

  . OPTIMAL DIMENSIONALITY REDUCTION WITH PROFILING.

2. 4

 4 Comparison with PCA and LDA Remark 8. Assume white noise (Sec. 2.3.1) where all values σ 2 d (1 ≤ d ≤ D) are different. Then, by Corollary 4, the asymptotic PCA is optimal only if α D = (0, 0, • • • , 0, 1, 0, • • • , 0), which we may consider unrealistic since only one sample out of D would leak secret information.

2 d 2 . 2 d σ 2 d.

 2222 = min D d=1 SNR d , the expression of the SNR of the asymptotic PCA given by Eqn. (2.16) is such that SNR PCA = Conversely, we can give an example for which SNR PCA < max D d=1 α Take D = 2, α 1 = α 2 = 1, σ 1 = 1 and σ 2 = 10. Then SNR PCA = 4/(1 + 10 2 ) = 4/101, which is strictly smaller than α 2 1 /σ 2 1 = 1.

  .1(a) and (b), for D = 6 samples. The noise is chosen autoregressive, with σ = 1 and different values for ρ (Sec. 2.3.2). The vector α D is chosen equal to (1, 1, 1, 1, 1, 1) t in Fig. 2.1(a) and to 6.0/6.4 • (1.0, 1.1, 1.2, 1.3, 0.9, 0.5) t in Fig. 2.1(b), such that SNR = 6 when ρ = 0. The SNR of the asymptotic LDA is that of the optimal dimensionality reduction (cf. Corollary 2), and that of the asymptotic PCA can be found in Example 3. The first case (Fig. 2.1(a)) fits the situation depicted in Corollary 3. The asymptotic PCA and LDA are almost similar. Besides, when ρ → 1 -, both SNRs tend to 1 (recall Eqn. (2.17) and (2.14)). But, when the SNR varies over the D samples (Fig. 2.1(b)), the asymptotic LDA can be significantly better than the asymptotic PCA. The sample-wise extremal SNRs (SNR d = α 2 d /σ 2 ) are also represented: the SNR of the PCA can be smaller than the largest SNR, namely max 1≤d≤D SNR d , (recall Lemmas 1), which is not the case of the SNR of the LDA. Actually, the SNR of LDA increases to infinity because SNR ≈ 0.164/(1ρ) when ρ → 1 -(see Eqn. (2.13)).

v2 ( 168 )Figure 2 . 1 :Proposition 10 .

 1682110 Figure 2.1: Comparison of the SNR of asymptotic LDA (optimal) and of asymptotic PCA

Figure 2 . 2 :

 22 Figure 2.2: Estimated α D (left) and Σ (right), for Q = 10, 000 traces

Contents 3 . 1 56 3. 2 58 3. 3 63 3. 4 69 3. 5

 31562583634695 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Theoretical optimal preprocessing function . . . . . . . . . . . . . Empirical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . On the fly preprocessing . . . . . . . . . . . . . . . . . . . . . . . . Conclusions and Perspectives . . . . . . . . . . . . . . . . . . . . . . 71

  samples. For example, if the first share leaks over D 1 samples and the second share over D 2 samples, we could perform a bi-variate SCA on D 1 × D 2 possible combined points. So, taking into account all these leaks may undoubtedly increase the efficiency of an attack.More generally, to break (Ω -1)-order masking schemes the attacker needs to combine Ω samples corresponding to Ω shares. So, if D i is the number of samples which leak the i-th share then the attacker could perform multi-variate SCA on 1≤i≤d D i different Ω-tuples. In other words, the number of possible Ω-tuples to perform multi-variate SCA is in O(D Ω ) where D is the number of samples each share leaks (and assuming that each share is leaking the same number of samples, i.e., ∀i ∈ 1, Ω , D i = D).

Lemma 3 .

 3 If the noise N (d) is identically distributed (i.d.) for all d, then the noise is unchanged by any linear combination of unitary norm. Proof. By hypothesis, Var α • N (d) d∈D = α 2 Var [N] = Var [N].

Figure 3 .

 3 Figure 3.2b presents the covariance between the points where the output of an S-box leaks and the leakage model HW[Sbox[T ⊕ K] ⊕ M ] -4.

Figure 3 .

 3 Figure 3.3a (resp. 3.3b) presents the covariance between the points where the output of an S-box leaks and the leakage model HW[Sbox[T ⊕K]⊕M ]-4 (resp. HW[Sbox[T ⊕K ]⊕M ]-4).

Figure 3 .Figure 3 . 2 :

 332 Figure 3.2: Covariance absolute value, for (a) XOR and (b) S-box

Figure 3 . 3 :

 33 Figure 3.3: Covariance absolute value, for (a) S-box and (b) S-box+ShiftRows

Figure 3 . 4 :Figure 3 . 5 :

 3435 Figure 3.4: Comparison between the classical second-order CPA and second-order CPA with preprocessing using (XOR, S-Boxes)

Figure 3 . 6 :

 36 Figure 3.6: Comparison between the classical second-order CPA and second-order CPA with preprocessing using (S-boxes, S-Boxes)

Figure 3 . 7 :

 37 Figure 3.7: Comparison between the covariance vector and the first eigenvector

Figure 3 . 8 :

 38 Figure 3.8: Comparison between 2O-CPA with preprocessing method and without in presence of Gaussian noise, with a standard deviation of 3 for (a) with a standard deviation of 5 for (b)

Figure 3 . 9 :Figure 3 . 10 :

 39310 Figure 3.9: Comparison between covariance and PCA depending on the size of the learning base

CHAPTER 4 Optimal

 4 Distinguisher against Masking TableThe results presented in this chapter have been published in collaboration with Sylvain Guilley, Annelie Heuser and Olivier Rioul in the international Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2014)[START_REF] Bruneau | Masks Will Fall Off -Higher-Order Optimal Distinguishers[END_REF].

Contents 4 . 1 81 4. 4 86 4. 5

 41814865 Algorithm of masking tables . . . . . . . . . . . . . . . . . . . . . . 78 4.2 Classical Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.3 High Order Optimal Distinguisher for Precomputation Masking Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Classical countermeasure . . . . . . . . . . . . . . . . . . . . . . . . Conclusions and Perspectives . . . . . . . . . . . . . . . . . . . . . 87 Masking schemes based on tables recomputation are classical countermeasures against highorder side-channel attacks. Recently Tunstall, Whitnall and Oswald at FSE 2013 have exhibit a new attack which exploits the multiple leakages linked to one mask during the recomputation of

. 6 )

 6 In Eq. (4.5), we change m for m = m ⊕ k and in Eq. (4.6), the input terms at position ζ are replaced with those at position ζ ⊕ k (because of the symmetry property of c). Accordingly, C Y does not depend on the key k and is even constant as the same operation can be done on t ⊕ k, therefore higher-order CPA fails.

  ) -X (ω ) |. Such expression remains unchanged under permutation of the inputs.

4. 3

 3 High Order Optimal Distinguisher for Precomputation Masking Tables

Figure 4 . 1 :

 41 Figure 4.1: Success Rate for masking table.

Contents 5 . 1 90 5. 2 91 5. 3 106 5. 5 115 5. 7

 5190291310651157 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Totally random permutation and attack . . . . . . . . . . . . . . . . An example on a high-order countermeasure . . . . . . . . . . . . . 101 5.4 A note on affine model . . . . . . . . . . . . . . . . . . . . . . . . . Practical validation . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 5.6 Countermeasure. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusions and Perspectives . . . . . . . . . . . . . . . . . . . . . 118

Figure 5 . 1 :

 51 Figure 5.1: State-of-the-art attack and new attack investigated in this chapter.

Figure 5 . 2 :

 52 Figure 5.2: Comparison between the variance of the noise for the classical leakage and the second-order and the impact of these noises on the SNR

Figure 5 . 3 :

 53 Figure 5.3: Comparison between 2O-CPA and MVAT R

  are respectively the number of traces needed by 2O-CPA and MVA T R to reach SR of success rate.

5. 3

 3 An example on a high-order countermeasure 5.2.5.1 Numerical Results.

  Emp rel-gain(SR) Theo rel-gain(SR) (a) rel-gain(SR) Emp gain(SR) Theo gain(SR) (b) gain(SR)

Figure 5 . 4 :

 54 Figure 5.4: Comparison between the 2O-CPA and the MVAT R

5. 3 3 : 2 / 2 for ω ∈ F n 2 doT 10 end 11 for ω ∈ F n 2 do 12 T 5 .

 332221011125 An example on a high-order countermeasure Algorithm Masked and shuffled computation of y = S (x) input :x 1 , . . . , x Ω , such that x = x 1 ⊕ . . . ⊕ x Ω output : y 1 , . . . , y Ω , such that y = y 1 ⊕ . . . ⊕ y Ω = S(x) ϕ ← R F n 2 → F n / Draw of random permutation of F n (ω) ← (S (ω) , 0, . . . , 0) ∈ (F n 2 ) d // ⊕ (T (ω)) = S (ω) end for i = 1 to Ω -1 do for ω ∈ F n 2 do for j = 1 to Ω do T (ϕ( ω )) [j] ← T (ϕ( ω )⊕x i ) [j] // T (ϕ( ω )) ← T (ϕ( ω )⊕x i ) end (ϕ( ω )) ← RefreshMasks (T (ϕ( ω )))// See in Alg. 2 of (39)13 end 14 end // Invariant: ⊕ (T (ϕ( ω ))) = S (ϕ( ω )⊕x 1 ⊕ . . . ⊕ x Ω-1 ) , ∀ω ∈ F n 2 15 (y 1 , . . . , y Ω ) ← RefreshMasks (T (x Ω )) // ⊕ (T (x Ω )) = S (x)16 return y 1 , . . . , y Ω 103 MULTIVARIATE HIGH ORDER ATTACK AGAINST SHUFFLED MASKING TABLE

  CSreaches 80% of success rate for less than 200000 traces while the 4O-CPA does not reach 5%.

Figure 5 . 6 :CS 5 . 4 A

 5654 Figure 5.6: Comparison between ΩO-CPA and MVA Ω CS

Proposition 25 .

 25 In case of affine model, the leakages of the MVA T R (recall Def. 42) and the 2O-CPA are different. Indeed, let us denoteα n = α α • • • α n times

Figure 5 . 7 :

 57 Figure 5.7: Comparison of min k =0 κ k for the MVAT R and the 2O-CPA

Figure 5 . 8 : 9 250%.

 589 Figure 5.8: Comparison between 2O-CPA and MVAT R for ε = 0.9

Figure 5 . 9 :

 59 Figure 5.9: Comparison between 2O-CPA and MVAT R for ε = 0.5

Figure 5 . 10 :

 510 Figure 5.10: Comparison between the 2O-CPA and the MVAT R in case of one bit model in presence of High Gaussian noise

  with a SNR of 14 which corresponds to a noise variance of 0.1, which is very low (compared to the upper bound of the useful interval of variance given in Theorem 5.2.1, namely 60).

Figure 5 . 11 :

 511 Figure 5.11: Comparison of the SR of the MVAT R and the 2O-CPA

4 z 5 z 6 SS p : F n 2 -→ F n 2 xProposition 26 .

 4562226 Draw of random permutations ϕ, γ of F n 2 , γ permuting with S (see Definition 51) 3 for ω ∈ {ϕ(0), ϕ(1), . . . , ϕ(2 n -1)} do // S-Box recomputation loop ← γ(ω) ⊕ m // Masked input ← γ(S[ω]) ⊕ m // Masked output [z] = z // Creating the masked S-Box entry 7 end 8 return S Definition 52. The power p ∈ N of the function S is given by: -→ S • S • . . . • S p (x) , where • denotes the composition law. The functions S p : F n 2 -→ F n 2 and S : F n 2 -→ F n 2 are commutative ∀p ∈ N.

Proposition 35 . 1 L 1 L• 2 (

 35112 .18) Proof. The proof is given in Appendix C.2.2. Prop. 34 allows to compare the complexity of the two attacks. One can notice that there are still terms with Π! or D! in ROPT L such as D+L-1 L or Π min( Π 2 ,L) . Nevertheless these two terms can be seen as constants when L D. As a consequence we have the following remark. Important Remark. When the degree L of the attack ROPT L is such that L D the complexity of OPT is much higher than the complexity of ROPT L . Indeed the main term for OPT is Π! whereas the one for ROPT L is 2 (Ω-1)n . The complexity of ROPT L can be reduced to O Q•L• D+L-with a precomputation in O L • D+L-

2 Figure 6 . 2 :

 262 Figure 6.2: Bivariate attacks

3 (d) σ = 7 Figure 6 . 3 :

 3763 Figure 6.3: Attack on shuffled table recomputation (Low Noises)

Contents 7 . 1 143 7. 3

 711433 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 7.2 Perspectives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . List of publications. . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

(

  Uj +zj ) =⇒ E U U ⊕ z t i,j = 0 if i = j or E U U ⊕ z t i,j = (-1) zj if i = j .B.4 Affine model B.4.3 Proof of Corollary 6

2 s 2 = cst - 1 2 n m∈F n 2 (d i=0 2 d

 2222 .t. m =m (x (i) -HW[m ]) 2 (x (j) -HW[m ⊕ m]) x (0) -HW[S[t ⊕ k] ⊕ m]) 2 × 1 2 n -1 m ∈F2 (x (i) -HW[m ]) 2 (x (j) -HW[m ⊕ m]) 2 . (C.11) E M (x (1)y (1) ) 2 1 • • • (x (D)y (D) ) 2 D . Moreover (x (d)y (d) (t, k, M )) 2 d = 2 i x (d) 2 d -i y (δ) (t, k, M ) ) 2 1-i y (d) (t, k, M )

y

  (d) (t, k, M ) i d can be precomputed .

µ 2 =

 2 E(f (0) × f (1) ) + cst. (C.[START_REF] Blömer | Provably Secure Masking of AES[END_REF]

Table Recom

 Recom Exploiting only Leakage of the Mask and the Masked Share . . . . . . . . 134 6.6.2 Exploiting the Shuffled Table Recomputation . . . . . . . . . . . . . . . . 135 6.7 Conclusions and Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

	7 Conclusion	141
	7.1
		-
	putation	75

4 Optimal Distinguisher against Masking Table 77 4.1 Algorithm of masking tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.2 Classical Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.3 High Order Optimal Distinguisher for Precomputation Masking Tables . . . . . . 81 4.3.1 Experimental Validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.4 Classical countermeasure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.5 Conclusions and Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5 Multivariate High Order Attack against shuffled Masking Table 89 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 5.1.1 Preliminary and notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.2 Totally random permutation and attack . . . . . . . . . . . . . . . . . . . . . . . 91 5.2.1 Defeating the countermeasure . . . . . . . . . . . . . . . . . . . . . . . . . 92 5.2.2 Multivariate attacks against table recomputation . . . . . . . . . . . . . . 93 xxiii CONTENTS 6.5.2 Complexity of our Case Study . . . . . . . . . . . . . . . . . . . . . . . . 133 6.6 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.6.1 7.2 Perspectives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 7.2.1 Under Review. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 7.2.2 Research Perspectives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 7.3 List of publications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 III Appendix. 151 1 Exemple de trace de consommation . . . . . . . . . . . . . . . . . . . . . . . . . . x 2 Presentation de la « méthode de covariance » . L' attaque 2O-CPA calcule la corrélation pour chaque paire (d 1 , d 2 ) de la fuite (étape (1)), ensuite le maximum sur chacune des clefs et des instants temporels est recherché (étape (2)). Notre méthode obtient un « vecteur de covariance » sur un composant d'apprentissage (étape (0')), et ensuite projette la fuite X sur α (étape (1')), avant de chercher la meilleure clef lors de la maximisation du distingueur. Remarquons que le modèle Ψ(Z) dépend implicitement de l'hypothèse de clef k. . . . . . . . . . . . . . . . . xiii 3 Comparaison entre une attaque CPA du second ordre classique et une attaque second ordre CPA avec prétraitement utilisant (S-boxes, S-Boxes) . . . . . . . . . xiv 4 Taux de succès contre les tables masquées. . . . . . . . . . . . . . . . . . . . . . . xv 5 Comparaisons entre 2O-CPA et MVA T R . . . . . . . . . . . . . . . . . . . . . . . xvi 6 Comparaisons entre 2O-CPA et MVA T R . . . . . . . . . . . . . . . . . . . . . . . xvii 7 Comparaison entre ΩO-CPA et MVA Ω CS . . . . . . . . . . . . . . . . . . . . . . . xvii 8 Comparaisons des SR des attaques MVA T R et 2O-CPA . . . . . . . . . . . . . . xviii 9 Attaque sur le recalcul de table . . . . . . . . . . . . . . . . . . . . . . . . . . . . xx 1.1 Example of a modulated trace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2 Schematic of a linear part of a masking scheme of a block cipher. . . . . . . . . . 20 1.3 Example of multiple leakages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.4 Summary of the contributions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 xxvii LIST OF FIGURES 2.1 Comparison of the SNR of asymptotic LDA (optimal) and of asymptotic PCA .

  table recomputation scheme . . . . . . . . . . . . . . . . 128 6.2 Bivariate attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 6.3 Attack on shuffled table recomputation (Low Noises) . . . . . . . . . . . . . . . . 137 6.4 Attack on shuffled table recomputation (High Noises) . . . . . . . . . . . . . . . 138

	LIST OF FIGURES
	CHAPTER 1
	xxix

Introduction Contents 1.1 Introduction to the cryptography . . . . . . . . . . . . . . . . . . . . 1 1.2 Physical Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Side Channel Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Samples Selection and Dimensionality Reduction . . . . . . . . . 15 1.5 Protection methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.6 Attacks on the countermeasures . . . . . . . . . . . . . . . . . . . 23 1.7 Attacks evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.8 Contributions of the Thesis . . . . . . . . . . . . . . . . . . . . . . 32

  and then is not often used in practice. An other approach for software implementations is to use precompute table[START_REF] Akkar | An Implementation of DES and AES Secure against Some Attacks[END_REF][START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF][START_REF] Messerges | Securing the AES Finalists Against Power Analysis Attacks[END_REF]. In such implementation the non linear parts are stored in a lookup table and at each encryption a new table is computed for the specific input and output masks. Recently, Coron presented at EUROCRYPT 2014 (39) a table

recomputation scheme for any Ω. Since this countermeasure aims at high-order security (Ω > 1), it requires one full table precomputation before every S-Box call.

  Draw of random input and output masks 2 for ω ∈ {0, 1, . . . , 2 n -1} do // Sbox masking ← z // Creating the masked Sbox entry 6 end 7 t ← t ⊕ m // Plaintext masking 8 t ← t ⊕ k // Masked AddRoundKey 9 t ← S [t] // Masked SubBytes // ... normally, the full AES is computed here ...

	3	z ← ω ⊕ m // Masked input

4 z ← S[ω] ⊕ m // Masked output 5 S [z] 10 t ← t ⊕ m // Demasking 11 return t

  2: Beginning of computation of a block cipher masked by table recomputation in a random order input : t, one byte of plaintext, and k, one byte of key output : The application of AddRoundKey and SubBytes on t, i.e., S[t ⊕ k] // Table precomputation protected by shuffling ...............................

  Creating the masked S-box entry 7 end // Masked computation ...........................................................

8 t ← t ⊕ m // Plaintext masking 9 t ← t ⊕ k // Masked AddRoundKey 10 t ← S [t] // Masked SubBytes 11 t ← t ⊕ m // Demasking 12 return t

  Theorem 6.3.3 (Mixed Degree Attack). Assuming an implementation secure at order O, the next degree successful attack is the one at degree L + 1 = O + 1 which maximizes LL L+1 .

	6. TRUNCATION OF OPTIMAL DISTINGUISHER AGAINST SHUFFLED
	MASKING TABLE
				This is
	equivalent to summing	µ L (1 + γµ 1 ) -γ	µ L+1 L + 1	,
	over all traces and

  Proposition 33. To compute µ 1 , µ 2 and µ 3 an attacker does not need to compute the prohibitive expectation over S 2 n .

	6. TRUNCATION OF OPTIMAL DISTINGUISHER AGAINST SHUFFLED
	MASKING TABLE
	1) of Appendix C.1.1,
	Eq. (C.9) of Appendix C.1.2 and Eq. (C.12) of Appendix C.1.3.
	Proof. Combining Theorem 6.3.2 and Appendix C.1.
	Proof. Proof given in Appendix C.1.

  .21) Proof. See Appendix C.2.4. Remark 31. As already mentioned an attacker can ignore the leakages of the table recomputation and only target the two shares. In such case the complexity of OPT 2O (Def. 56) is O (Q • (2 n )). With the result of Prop. 35 the complexity of ROPT 2 reduces to O (Q). Remark 32. Using the result of Prop. 35 the complexity of ROPT 3 can be reduced to O Q • 2 2n with a precomputation step of O 2 2n . Remark 33. A summary of the complexity, and the computation time of the distinguishers are provided in Appendix C.2.5 in Table C.1.

Table C . 1 :

 C1 Time and complexity C.3 Analysis of the DPAcontest.

available under the DPA Contest v4, to evaluate how the proposed techniques improve the second-order CPA (2O-CPA).

This assumption is reasonable for software implementation, which is the adequate scenario for masking tables.

The formal definition of the relative gain is given in Def.45.

,L) = Π L , thanks to the bounded degree L. Additionally it can be noticed that an attacker will only build, during the offline profiling, the leakage models needed for the attack. By applying the Taylor expansion of the optimal

We recall that, even if the templates are perfectly known, the online attack phase still requires O(Q •

n(Ω-1) • Π!) computations.

,L) . The idea is to output the values depending on the queries from the computation of the expectations. These expectations only depend on the model which can be computed only once.

Remerciements

Totally random permutation and attack

Proposition 18 ((63, Corollary 1)). The SR of an additive distinguisher is satisfies:

1 -SR ≈ exp (-SE ×q) , (5.11) where SE is the success exponent and q the number of traces used for the attack.

Proof. The proof is given in [START_REF] Sylvain Guilley | A Key to Success -Success Exponents for Side-Channel Distinguishers[END_REF].

Proposition 19. The SE of the 2O-CPA is:

where in our case (which complies to Eqn. (5.1) of Definition 41):

κ (k , k) and κ (k , k) are general confusion coefficients defined in Definition 8 of [START_REF] Sylvain Guilley | A Key to Success -Success Exponents for Side-Channel Distinguishers[END_REF]. Notice that κ (k , k) is a natural extension of the seminal coefficient introduced by Fei et al. in [START_REF] Fei | A Statistical Model for DPA with Novel Algorithmic Confusion Analysis[END_REF].

Proof. See Appendix B.2.1.

We note that α 2 i and σ 2 i respectively represent the power of the signal and of the noise. As Def. 42, Def. 57 and Eq. (5.8) reveals that the only difference between the MVA T R and the 2O-CPA is the use of X T R instead of X (3) . Thus we can directly compute the success exponent of MVA T R .

Proposition 20. The SE of the MVA T R is:

where in our case

Proof. The proof is similar as the proof of Prop. 19 using the values of noise computed in the 5. [START_REF] Batina | Differential Cluster Analysis[END_REF] An example on a high-order countermeasure

Leakage analysis

The difference between the two attacks is the use of X CS Ω i instead of X

(3) i as the leakage of the Ω -1 shares which do not leak the secret key. A.A Ding et al. also provides a formula to compute the SR of HOCPA (46, §3.4).

Similarly to Sect. 5.2, the only differences in the formula are the SNR of the shares which do not leak the key. Then by comparing the SNR X CS Ω i , X i and SNR X

i , X i we compare the success rate of the attacks. It can be noticed that in our model the SNR does not depend on i.

Theorem 5.3.1. The SNR of the "second-order leakage" is greater than the SNR of the leakage of the mask if and only if

where σ denotes the standard deviation of the Gaussian noise. As a consequence MVA Ω CS will be better than ΩO-CPA when the noise variance lays in the interval [0, Ω × 2 n-2n/2]. We can immediately deduce that the size of the Useful Interval of Variance increases linearly with the order of the masking scheme.

Proof. See Appendix B.3. UIoV). We can see that the size of these intervals increases with the order. For example for Ω = 3 the useful interval of variance is [0,188]. In practice, it is very difficult to perform a third order attack with a noise variance of 188. Indeed, recall that the number of traces to succeed an attack with probability 80% is proportional to the inverse of the SNR [START_REF] Sylvain Guilley | A Key to Success -Success Exponents for Side-Channel Distinguishers[END_REF]. 1 /SNR X (3) i , Mi and signal to noise ratio of X CS Ω i (where Ω is the attack order).

MULTIVARIATE HIGH ORDER ATTACK AGAINST SHUFFLED MASKING TABLE

• attacks depend on the SNR as predicted by Theorem 5.4.1.

For the purpose of the simulations, the target considered is the input of the S-Box of the last round; as a consequence we consider

.

The mask M and the plain text T are randomly drawn from F 8 2 . The noises are drawn from a Gaussian distribution with different variances σ 2 . The results of the attacks are expressed using the success rate. To compute the success rates the experiments have been redone 1000 times. For each experiment the secret key k are randomly drawn over F 8 2 . To compare the efficiency of the two attacks we compare the number of traces needed to reach 80% of success.

For the first experiment we choose α = √ 1 ± ε (i.e., ∀i, α i = 1 + (-1) i ε). It can be seen in Fig. 5.9c that when σ = 3 the MVA T R needs around 1000 traces to reach 80% of success whereas the 2O-CPA needs 3500 traces. The relative gain of use the MVA T R is 5.6 Countermeasure.

The MVA T R represents a threat against block ciphers with table recomputation step. In order to mitigate this new vulnerability we present in this section a countermeasure. This countermeasure will ensure the security against the new proposed attack. We present it in the context of a first order masking scheme but this countermeasure is generic and as a consequence can be applied in a higher order masking scheme such as the masking scheme of Coron.

Remark 25. The proposed countermeasure tackles the input masks vulnerability. The protection of the output mask is easier as all the output masks can be different for all the table entries.

Countermeasure Principle

The core idea of this countermeasure is to randomly drawn permutations not all over the possible permutations but only over a particular kind of permutations: the ones which are commutative with S (the SubBytes function).

Exploiting this kind of function the countermeasure principle is as follow: as random permutation a commutative permutation with respect to S is drawn. Let us call the permutation γ. Exploiting the commutative property of the random permutation γ(S[ω]) is computed instead of S[γ (ω)] (line 5 of Alg. 4). Contrast this line with line 5 of Alg. 2. As a consequence if an attacker combines the leakages of the random mask index (line 4) and the random index (line 5) the obtained value depends very little in the masks m and m (see analysis in Sec. 5.6.3).

Implementations

The major issue of the countermeasure in an implementation perspective is to randomly generate a commutative permutation.

A first approach could be to generate off line a set of permutations and store them into the device. At each execution using a random number, a permutation will be selected. Of course such approach can be prohibitive in terms of memory.

A probably better approach is to generate on the fly a commutative permutation. In this subsection we give an example of a such algorithm. The idea is to randomly generate a power (with respect to the combination law) of the SubBytes : S function.

Security Analysis

The security provided by this countermeasure comes from different parameters. Of course the first one is to ensure that the MVA T R is not still available or at least less effective than the 2O-CPA which remains available. We validated this security using simulation with the same set up as in Subsect. 5.2.4. Namely we assume that each value leaks its Hamming weight with a Gaussian noise of standard deviation σ. A total of 1000 attacks has been realized to compute the success rate of each experiment.

The attacker can combine γ (S[ω]) with γ (ω). The results of this combination can be found in Fig. 5.12 for two different noise standard deviations. We can immediately see that in this case the MVA T R does not allow to recover the key. The other parameter is the number of possible commutative permutations. Indeed if this number is too low an attacker can test all the permutations and build attacks such as in [START_REF] Tunstall | Masking Tables -An Underestimated Security Risk[END_REF].

For example using the possible power of S in AES we reach 277182 which is hard to exhaustively test but remains possible. For some specific cases, such as involutional block ciphers (e.g., ICEBERG [START_REF] Standaert | ICEBERG : An involutional cipher efficient for block encryption in reconfigurable hardware[END_REF]), the countermeasure cannot apply because the order of the substitution box S is equal to two.

CHAPTER 6

Truncation of Optimal Distinguisher against shuffled Masking Table The maximum likelihood side-channel distinguisher of a template attack scenario is expanded into lower degree attacks according to the increasing powers of the signal-to-noise ratio (SNR).

By exploiting this decomposition we show that it is possible to build highly multivariate attacks which remain efficient when the likelihood cannot be computed in practice due to its computational complexity. The shuffled table recomputation is used as an illustration to derive a new attack which outperforms the ones presented by Bruneau et al. at CHES 2015, and so across the full range of SNRs. This attack combines two attack degrees and is able to exploit high dimensional leakage which explains its efficiency.

Case Study: Shuffled Table Recomputation

• maximize the result over the key hypotheses, if L is even;

• minimize the result over the key hypotheses, if L is odd.

Proof. The (L + 1)th-order term in the log-likelihood becomes

Now from (6.6) we have, for L > 0

Removing terms that do not depend on k, we obtain:

Compared to a Lth-degree attack, we see that µ L is replaced by a corrected version:

where µ 1 is independent of k. However, µ 1 cannot be removed as it scales the relative contribution of µ L and µ L+1 in the distinguisher.

Remark 27. In contrast to LL L , implementing LL L+1 requires knowledge of the SNR parameter γ = 1/2σ 2 .

Remark 28. In general, when L ≥ O the rounded optimal attack ROPT L exploits all key dependent terms of degree , where O ≤ ≤ L, whereas an LO-CPA [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF] or MCP-DPA [START_REF] Moradi | Moments-correlating DPA[END_REF] only exploits the term of degree L.

Case Study: Shuffled Table Recomputation

In this section we apply the ROPT L formula of Eq. (6.9) in Def. 54 to the particular case of a block cipher with a shuffled table recomputation stage. We show that in this scenario our new method allows to build a better attack than that from the state-of-the-art. By combining the second and the third cumulants we construct an attack which is better than:

• any second-order attack;

• the attack presented at CHES 2015. Following the notations of ( 27) we denote this attack by MVA T R (which stands for Multi-Variate Attack on Table Recomputation) in the rest of this chapter. This is a third-order attack that achieves better results than 2O-CPA when the noise level σ is below a given threshold (namely σ 2 ≤ 2 n-2n/2).

Case Study: Shuffled Table Recomputation

•

•

•

•

We recall that we assume the noises N are i.i.d. Clearly, there is a second-order leakage, as the pair (X (0) , X (1) ) does depend on the key. But there is also a large multiplicity of third-order leakages, such that (X (1) , X (i) , X (j=i+2 n ) ), as will be analyzed in this case study.

The following side-channel attacks are applied on a set of Q realizations. Let us define I and J as I = 2, 2 n + 1 and J = 2 n + 2, 2 × 2 n + 1 . Then the maximal dimensionality is

For any measurement indexed by q ∈ Q:

• We denote by x

q the leakage of the mask (M ).

• We denote by x

q the leakage of the masked SubBytes (S[t q ⊕ k] ⊕ M ).

• The 2 n leakages of the random masked index (Φ (ω) ⊕ M where ω denotes the index of the loop of the recomputation stage) are denoted by x (i)

Let us denote in bold letter the set of leakages of all the queries i.e.

q . The expected leakage model for all queries is given by y

In order to simplify the notations we introduce

with d ∈ {0, 1} ∪ I ∪ J. The q can be omitted where there is no ambiguity.

CONCLUSION

equivalent to the LRA. In Chap. 3 we analyzed the optimal dimensionality reduction in the case of a less powerful attacker. In this scenario the attacker has no a priori knowledge on the leakage function. This generalization of the attacker model comes with a less powerful result. Indeed in this chapter the optimization problem is the maximization of the distinguisher. Moreover we took as case-study the High-Order attacks against masking scheme while the state-of-the-art attack mainly deals with univariate non protected implementations. As a consequence we investigated in this chapter the dimensionality reduction in the case of 2-variate attacks. In this context the rational of the dimension reduction may differ to the univariate one. Especially we showed that the gain of the uses of dimensionality reduction increases with the order. As a consequence such methods are a powerful tool against protected implementations. In these two scenarios the methods presented increase significantly the results of the attack. This means that both in non protected and protected implementations, an increase of the dimension of the attacks improves their results. We showed these results in 1-variate and 2-variate scenario and theoretically extended these results at any orders.

In the second part of this manuscript (Part II) we investigated the possible exploitation of the leakages of multiple variables. In the Chap. 4 we extended the results of the state-of-the-art by deriving the optimal attack against a masking scheme with a table recomputation step. In particular we showed that in this case the exploitation of the multiple leakages of the table recomputation can greatly improve the results of the attacks. Indeed the new attacks offer better results in success probability than the different attacks of the state-of-the-art. This theoretical and empirical analysis provides a better understanding on the construction of highly multivariate attacks. Indeed we showed that the optimal attack takes into account all the leakages in once. Moreover we showed that for high noises this new attack is closed to the "mean" of different attacks. As a consequence the optimal attack is closed to a multi-target attack. The multi-target attacks represent an interesting research path. The implementations of the masking schemes with a table recomputation step can be protected, as a consequence, we presented in Chap. 5 a new multivariate attack tailored to defeat such countermeasures. This new attack is the first example of a non minimal order attack more efficient that the minimum one. In other words we showed that by combining more variables than the minimum number needed to recover a key depend variable, we could build better attacks. This means that in presence of masking scheme it may have an interest to build highly multivariate attacks. As a consequence in order to properly evaluate the security of the masked implementation we showed that the order is not a sufficient metric. In this context we extended this attack for different leakage

List of publications.

In this manuscript we showed that a possible approach is to perform unified attacks using the Maximum Likelihood. An interesting research path would be to generalize this approach for any protected implementations noticing that in some cases it may be not sufficient or not computable. In these cases truncated versions may be an interesting approach.

The theoretical approach based on the Success Exponent can be an interesting first step for further researches. Indeed the expression of the theoretical Success Rate will allow to highlight the different behaviors of different attacks against different implementations. Such approaches will lead to fairer comparisons as it will take into account more parameters than straightforward comparisons based for example only on the order or the SNR.

Another question is how this result can be extended on other secure implementations?

Especially are the others masking schemes vulnerable against attacks exploiting multiple leakages?

If it is the case, how their security is impacted compared to their traditional security parameters?

Generally we showed in this manuscript that the use of the multiple leakages improve the results of the SCA. We introduce different parameters to classify these leakages depending on the multiplicity of different variables or the way there are exploited to recover the key. We saw that the way multiple leakages are exploited depends on these parameters. A possible research path is to optimally derived the way to take into account this multiplicity of type of leakages.

By doing so it may possible to identify a generic framework to exploit the multiple leakages and as a consequence establish a parameter to evaluate the security of protected implementations.

List of publications.

During this thesis I contributed to different publications which are not part of this manuscript.

In the following we list the contributions.

The following contributions are part of this manuscript:

Abstract

The maximum likelihood side-channel distinguisher of a template attack scenario is expanded into lower degree attacks according to the increasing powers of the signal-to-noise ratio (SNR). By exploiting this decomposition we show that it is possible to build highly multivariate attacks which remain efficient when the likelihood cannot be computed in practice due to its computational complexity. Less is More -Dimensionality Reduction from a Theoretical Perspective, Nicolas

Abstract

Second-order side-channel attacks are used to break first-order masking protections.

A practical reason which often limits the efficiency of second-order attacks is the temporal localisation of the leaking samples. Several leakage samples must be combined which means high computational power. For second-order attacks, the computational complexity is quadratic. At CHES '04, Waddle and Wagner introduced attacks with complexity O(n log 2 n) on hardware traces, where n is the window size, by working on traces auto-correlation. Nonetheless, the two samples must belong to the same window which is (normally) not the case for software implementations. In this article, we introduce preprocessing tools that improve the efficiency of bi-variate attacks (while keeping a complexity of O(n log 2 n)), even if the two samples that leak are far away one from the other (as in software). We put forward two main improvements. Firstly, we introduce a method to avoid losing the phase information. Next, we empirically notice that keeping the analysis in the frequency domain can be beneficial for the attack. We apply these attacks in practice on real measurements, publicly available under the DPA Contest v4, to evaluate the proposed techniques. An attack using a window as large as 4000 points is able to reveal the key in only 3000 traces.

Keywords: Bi-variate attacks, zero-offset 2O-CPA, discrete Hartley transform, leakage in phase.

Appendix of Dimensionality Reduction

A.1 Proof of Theorem 3.2.1

Proof. On the one side we have

The other side yields Var α

which proves equivalence.

A.2 Proof of Lemma 2

Proof.

A. APPENDIX OF DIMENSIONALITY REDUCTION

By the Cauchy-Schwarz theorem, we have:

,where equality holds if and only if α and β are linearly dependent, i.e., α = λβ. Accordingly, if α = 1 we have λ = 1 β , which gives us the required solution.

A.3 Proof of Proposition 14

Proof. We have

Similar to the proof of Lemma 2, we use the Cauchy-Schwarz inequality. In particular,

We have the equality,

APPENDIX B

Appendix of Multivariate Attack.

B.1 Proof of Theorem 5.2.1

In order to prove the Theorem 5.2.1 let us first introduce some lemmas. By Remark 19 the only random parts of X T R are the noise and the mask. As a consequence the random variable (X T R |M = m) depends only on the noise, and is equal to:

Proof. (X T R |M = m) can be split into a deterministic part and a random part:

where

where U denotes a random variable drawn uniformly over F n 2 .

Lemma 9.

Let us now prove that C 1 = C 2 = 0. First we have:

ω × N

(2) ω

.

The random variables N (i)

ω , where i ∈ {1, 2} and ω ∈ F n 2 are mutually independent and independent with all the HW[Φ (ω)]. Thus we have:

ω × N

(2) ω .

As

ω , where i ∈ {1, 2} and ω ∈ F n 2 , are mutually independent, we have:

Identically we prove that:

Let us now study C 3 . By the bi-linearity of the covariance C 3 can be rewritten such that:

By definition, N

ω is independent from HW[Φ (ω)]. Thus:

ω × (HW[Φ (ω )]) = 0, the terms in Eq. (B.4) are all null. It can be noticed that E HW[Φ (ω)] -n 2 = 0 as Φ (ω) is uniformly distributed over S 2 n and E N

(1) ω = 0. As a consequence:

Identically, we have

B.2 Proof of the propositions of Sect. 5.2.5

Then let us prove the Theorem 5.2.1.

Proof. Lemma 9 gives us the value of the variance of the noise. Then by the definition of the SNR, we have:

B.2 Proof of the propositions of Sect. 5.2.5

B.2.1 Proof of Prop. 19

Proof. By Theorem 2 in (64, Appendix A.2) (extended version of ( 63)) we have that the SE of is given by

B.2.2 Proof of Prop. 21

Proof.

which indeed does not depend on SR.

B.2.3 Proof of Prop. 22

Let us now compute the difference of traces needed to reach any SR.

B. APPENDIX OF MULTIVARIATE ATTACK.

Let us rewrite using α = α 1 = α 2 . In such case:

The attacks perform similarly when

Notice that we recover here the results of the Subsect. 5.2.3. In order to find the noise when the maximum occurs let us compute the derivative in σ 2 :

The maximum occurs when Similarly to the Remark 19 we have ∀i < Ω:

(ω,j) -

(ω,j) -

As the i is fixed for each share we have removed it from the index position.

Lemma 10.

where Ω is the number of share of the high-order masking scheme and i < Ω.

Proof. Lemma 10 is a straightforward extension of Lemma 9.

Exploiting Lemma 10 let us prove Theorem 5.3.1.

Eventually, we have:

B.4.2 Proof of the Theorem 5.4.1

Similarly to Eq. (B.1) we have:

Proof. Similar to proof of Lemma 9 (see Appendix B.1) using the affine model instead of the Hamming Weight and Assumption 1.

Then we can prove the Theorem 5.4.1.

Proof. Lemma 11 gives us the value of the variance of the noise. Then by the definition of the SNR, we have:

The Corollary 6 is the application of Lemma 12 with p = 4 and q = 2.

Proof. Indeed we have by Theorem 5.4.1 that the useful interval of variance is 0

, where α 2 2 = n (recall Assumption 1). Then by Lemma 12:

Value of Theorem 5.2.1.

Appendix of Mixed Order.

C.1 Computation of the Moments

C.1.1 Computation of µ 1

There is no computational difficulty:

Now, when there is no ϕ in the R.V., then the expectation is only on M (indeed, 1

which cannot further be simplified (in the simulations, it will be computed by the computer).

Similarly

When there is an expectation on Φ, then at order one, it considers only one value Φ(ω).

It is uniformly distributed, hence one can replace the expectation on Φ by an expectation on one value of ϕ, we call M . For instance:

which can thus be computed with the same average method as E(f (0) ).

Lastly, when there is both M and Φ(ω), then whichever variable can absorb the other one, since both are uniformly distributed on F n 2 . This means that:

which is once again a similar computation as done for computing E(f (0) ).

C.1.2 Computation of µ 2

Recall that only the key dependent terms of µ 2 are needed for ROPT 2 and ROPT 3 .

Notice that the square terms are computed as the non-square terms. For instance,

which we drop since it does not depend on k. All in one, the only key-dependent term is:

which cannot be further simplified and will be computed by the computer. So, for the purpose of the attack, we have: We shall consider only terms which depend on the key, hence product of three terms, one of which (at least) is f (0) . Obviously, E(f (0) 3 ) does not depend on k, for the same reason as given in Eqn. (C.7). But the two terms:

1

Notice that they are present 3 2 = 3 times each when developing the cube. Interestingly, those are not the only cases where f (0) and f (1) are selected.

Similarly, we have:

Now, we consider products without f (1) . Obviously, taking only f (0) and f (i) is not enough, since:

) are key independent. The same goes for E(f (0) 2 f (j) ) and E(f (0) f (j) 2 ). We are left with

The term

The term E(f (0) f (j) f (j ) ) can also factorize as E(f (0) )E(f (j) f (j ) )), hence it does not depend on k. The reason is more subtle, so we detail it:

C.2 Complexity Proofs

The non-constant term is similar to Eqn. (C.10) provided a scaling by -(2 n -1)/2 n is done.

So, for the purpose of the attack, we have:

C.2 Complexity Proofs

C.2.1 Proof of Lemma 7

In order to prove Lemma 7 let us first introduce a preliminary result.

Lemma 13. The quantity Π is increasing if < Π/2 and its maximum is

and the factor Π--1

+1

is strictly greater than 1. Indeed,

Finally we can prove Lemma 7.

Proof. Let us first assume that one dimension leaks at most one element of the permutation. We can thus develop the expression of µ , and we denote the complexity under the braces. Each dimensions which leaks an element of the permutation can also leaks the masks. The worst case in terms of complexity is when all the permutation leakages depend also on the masks. Let us denote by i such that 1 ≤ i ≤ min (D, ) the number of those terms. Then

C. APPENDIX OF MIXED ORDER.

the expectation is computed over 2 (Ω-1)n Π! (Π-i)! . Nevertheless by taking into account the commutativity properties of the product one can only compute 2 (Ω-1)n Π i . By Lemma 13 we have that is value Π i is maximum with Π when ≤ Π 2 . When > Π 2 +1 the maximum is Π

C.2.2 Proof of Proposition 34

In order to prove Lemma 34 let us first introduce a preliminary result. Lemma 14. The quantity D-1+ is increasing with if D > 1.

Proof. We have that :

where ∀ , D+ +1 > 1 provided D > 1.

Finally let us prove Prop. 34.

Proof. Complexity of OPT: Following Eq. (6.2) we have that the computation for a key guess of OPT is: We assume that the computation of the log and the exp is constant. As a consequence the complexity of the optimal distinguisher is O Q

Complexity of ROPT L :The computation of ROPT L involves the computation of the µ with ≤ L (Eq. ( 54) and Eq. ( 53)). By Lemma 7 and Lemma 14 all these terms have a complexity lower than O D+L-1 L • 2 (Ω-1)n • Π min( Π 2 ,L) (Eq. (6.16)). As a consequence the complexity of ROPT L is lower than

C.2.3 Proof of Proposition 35

Proof. Let us develop all the product in the term µ in order to compute the expectation in the minimum number of values.

Attaques par Canaux Auxiliaires Multivariées, Multi-cibles et d'ordre élévé

Nicolas BRUNEAU ABSTRACT : Side Channel Attacks are a classical threat against cryptographic algorithms in embedded systems. They aim at exploiting the physical leakages unintentionally emitted by the devices during the execution of their embedded programs to recover sensitive data. As such attacks represent a real threat against embedded systems different countermeasures have been developed. In thesis we investigate their security in presence of multiple leakages. Indeed there often are in the leakage measurements several variables which can be exploited to mount Side Channel Attacks. In particular we show in this thesis the optimal way to exploit multiple leakages of a unique variable. This dimensionality reduction comes with no loss on the overall exploitable information. Based on this result we investigate further how such dimensionality reduction methods can be applied in the case of protected implementations. We show that the impact of such methods increases with the security "level" of the implementation. We also investigate how to exploit the leakages of multiple variables in order to improve the results of Side Channel Analysis. We start by improving the attacks against masking schemes, with a precomputed table recomputation step. Some protections have been developed to protect such schemes. As a consequence we investigate the security provided by these protections. In this context we present results which show that the main parameter to evaluate the security of the masking schemes is not sufficient to estimate the global security of the implementation. Finally we show that in the context of masking scheme with shuffling the optimal attack is not computable. As a consequence we present a truncated version of this attack with a better effectiveness.

KEY-WORDS :

Side Channel Attacks, Masking scheme, Multivariate Attacks, Optimal Attack