Damien Marion

Directeur De

Professeur Sylvain Guilley

M Louis Goubin

Jean-Louis Lanet

Professeur Rapporteur

Examinateur M Guillaume Bouffard

PhD Anssi M Christophe Clavier

Annelie Mme

Examinatrice Heuser

Invité M Adrien Facon

Cédric, Chloë, Florent, Franz Janie Brice

Karine Kais

Michaël, Michel, Olivier, Pierre, Rachid Margaux Martin

Romain Ronan

Théo, Thomas (×2 Sylvie Thuy

Yannick, Yannis. . . Vincent Valentin

Lucia Loic

Stefano Lucrezia

Multidimensionality of the Models and the Data in the Side-Channel Domain

Keywords: XOR eXclusive OR 7, 27, 51 AES Advanced Encryption Standard 7, 8, 11, 12

HAL is a

Ce manuscrit de thèse débute par une première section décrivant un ensemble de connaissances nécessaires à la bonne compréhension des notions abordées. Une première sous-section décrit en détail l'Advanced Encryption Standard (AES). Cet algorithme cryptographique a fait l'objet d'analyses poussées tout au long de la thèse pour illustrer les contributions proposées. Cette fonction de chiffrement prend en entrée des blocs de 16 octets ainsi qu'une clé secrète. Cette clé secrète est identique pour le chiffrement et le déchiffrement. L'algorithme se décline sous trois formes, chacune d'elle prenant respectivement des clés de 16, 25 et 32 octets. Chacune des ces formes divergent par leurs nombres de tours dont est composé l'algorithme, respectivement 10, 12 et 14. Chacun

1.1 Chapitre 1 : Introduction des tours de l'AES est divisé en quatre sous-fonctions appliquées successivement sur l'état interne :

• un OU-exclusif avec clé de tour, dérivant de la clé secrète ;

• un décalage par rotation ;

• une transformation linéaire dans un corps de Galois ;

• une permutation non-linéaire relative à une table connue publiquement.

Des schémas explicatifs sont fournis dans le manuscrit pour décrire avec précision l'ensemble de ces sous-fonctions.

La seconde sous-section introduit le principe des attaques par canaux auxiliaires, domaine auquel l'ensemble des contributions de la thèse est rattaché. Les attaques par canaux auxiliaires ont été introduites par Kocher et al. en 1999 dans l'article intitulé "Differential Power Analysis" [START_REF] Paul | Differential power analysis[END_REF] 1 . Depuis cette date, elles sont connues pour être vecteur d'attaques particulièrement efficaces contre les algorithmes cryptographiques exécutés sur des systèmes embarqués. Ces attaques consistent en l'utilisation d'informations inhérentes à l'exécution de l'algorithme sur un système physique. Ces canaux auxiliaires peuvent être le temps d'exécution, les émanations électromagnétiques, la consommation de courant. . . Ces attaques ciblant principalement des algorithmes cryptographiques, leur objectif est généralement de retrouver des clés secrètes. Cependant, elles permettent aussi, dans certain cas de réaliser de la rétro-ingénierie de système. Dans le cadre de cette thèse, les contributions proposées sont relatives aux fuites d'informations provenant de la consommation électrique et des émanations électromagnétiques.

Pour faciliter la compréhension, une section introduit l'ensemble des notations utilisées. Ces notations sont les même pour l'ensemble du manuscrits et sont toutes des notations matricielles. Ainsi les fuites d'informations collectées par un attaquant seront stockées dans une matrice noté 𝑋 𝐷,𝑄 = {𝑋 𝑑,𝑞 } 𝑑<𝐷, 𝑞<𝑄 , avec 𝑄 le nombre de traces (nombres d'exécutions de l'algorithme attaqué) et 𝐷 le nombre d'échantillons de ces traces. Les fuites d'informations sont modélisées de la façon suivante : 𝑋 𝐷,𝑄 = 𝛼 𝐷,𝑆 𝑌 𝑆,𝑄 (𝑘 ⋆ ) + 𝑁 𝐷,𝑄 (1.1) où 𝑌 𝑆,𝑄 (𝑘 ⋆ ) est la modélisation d'une fuite relative à la manipulation de la donnée secrète 𝑘 ⋆ . 𝛼 𝐷,𝑆 représente l'influence physique de la manipulation ces données et

RÉSUMÉ DE LA THÈSE EN FRANÇAIS

𝑁 𝐷,𝑄 le bruit (dont la matrice de covariance est notée Σ 𝐷,𝐷 ). La figure 1.1 représente un modèle de fuite théorique avec un bruit nul. Dans ce cas, le modèle est le poids de Hamming, c'est à dire la somme des bits de la valeur manipulée. Le modélisation de la fuite est centrale dans l'ensemble des contributions proposées dans le manuscrit. La dimension du modèle 𝑆, le nombre d'échantillons de la fuite 𝐷, Une fois les fuites 𝑋 collectées, l'objectif est d'en extraire l'information secrète 𝑘 ⋆ . Pour se faire, on utilise ce qu'on appelle un distingueur noté D. Il permet de comparer un modèle supposé 𝑌 et les données 𝑋. 𝑌 est fonction de données connues, messages en clair (ou messages chiffrés) noté 𝑇 et d'une donnée secrète supposée, noté 𝑘. Ainsi exprimé, l'objectif du distingueur est de maximiser la probabilité de succès de 𝐷(𝑋, 𝑌 = 𝑘 ⋆ ). Cela peut être formalisé de la façon suivante, proposé dans [START_REF] Heuser | Good is not good enough -deriving optimal distinguishers from communication theory[END_REF] :

D(𝑋 𝐷,𝑄 , 𝑇 𝑄 ) = argmax 𝑘 ( 𝑝(𝑋 𝐷,𝑄 |𝑇 𝑄 , 𝑘 = 𝑘 ⋆ ) ) . (1.2)
L'introduction aux analyses par canaux auxiliaires s'achève par la présentation de différentes attaques. Ces attaques résultent de la participation à une compétition ayant été organisée lors de la conférence CHES-2016 1 . Les analyses proposées ont permis d'atteindre la seconde place du classement étudiant et la vingt-et-unième du général. L'introduction du manuscrit s'achève par l'explicitation des contributions et la présentation de l'organisation du manuscrit. Celle-ci s'organise en trois chapitres principaux présentant les trois contributions majeures, suivis d'un chapitre de conclusion. La première contribution, intitulée "moins c'est plus" répond à la problématique suivante : Comment peut-on compresser de façon optimale l'ensemble des points de fuite en un seul échantillon sans perte d'efficacité ? Ce travail collaboratif avec Nicolas Bruneau, Sylvain Guilley, Annelie Heuser et Olivier Rioul a donné lieu à une publication à CHES-2015 [START_REF] Bruneau | Less is more -dimensionality reduction from a theoretical perspective[END_REF].

La seconde contribution intitulée "Fuites Multivariées et Modèles Multiples" répond à la problématique suivante :

Comment peut-on tirer avantage d'un ensemble de points de fuite dans le cadre de modèles multiples ? Ce travail collaboratif avec les mes auteurs que le précédent a donné lieu à une première publication à PROOF-2016 [START_REF] Bruneau | Optimal side-channel attacks for multivariate leakages and multiple models[END_REF], ainsi qu'à un poster à CHES-2016 puis à la publication d'un version étendue dans le journal journal of cryptographic engineering [START_REF] Bruneau | Optimal side-channel attacks for multivariate leakages and multiple models[END_REF].

RÉSUMÉ DE LA THÈSE EN FRANÇAIS

La dernière contribution intitulée "Analyse Binaire pour L'évaluation des Fuites d'un Code Source" répond à problématique suivante : Comment peut-on identifier et caractériser des fuites d'informations en exploitant des "traces logiciels" tridimensionnelles ? Ce travail collaboratif avec Antoine Bouvet, Nicolas Bruneau, Adrien Facon, Sylvain Guilley, Matthieu Lec'Hvien et Thomas Perianin a donné lieu à deux publications, la première à DTIS-2018 [START_REF] Bouvet | Give Me Your Binary, I'll Tell You If It Leaks[END_REF] et la seconde à SecITC-2018 [START_REF] Facon | Binary data analysis for source code leakage assessment[END_REF].

L'ensemble des contributions s'organise autour de la multidimensionnalité. La première contribution traite de celle des fuites, dimension 𝐷 de 𝑋. La seconde ajoute à la précédente la problématique de la dimension des modèles, dimension 𝑆 de 𝑌 et 𝛼. La dernière, quand à elle, aborde la multidimentionnalité des données en ajoutant une dimension 𝑅 aux données.

Chapitre 2 : Moins C'est Plus

Ce chapitre aborde le problème de la réduction de dimension des fuites. En effet il est connu que dans le cadre d'une acquisition de données, les informations sensibles fuitent au cours du temps. L'objectif de la réduction de dimension est de projeter l'ensemble des points de fuite en un seul sans perdre d'information. C'est ce qui est proposé via l'expression "moins c'est plus" : une réduction de dimension et donc une accélération calculatoire sans diminution de la probabilité de succès de l'attaque.

Le résultat principal de ce chapitre est résumé dans le Théorème 1.1 : Théorème 1.1. L'attaque optimale sur des traces multivariées 𝑋 𝐷,𝑄 est équivalente à l'attaque optimale sur des traces univariées X𝑄 , obtenues depuis 𝑋 𝐷,𝑄 via la formule :

X𝑞 = ( 𝛼 𝐷 ) T Σ -1 𝑋 𝐷 𝑞 (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 (𝑞 = 1, . . . , 𝑄). (1.3)
Dans le cadre de ce chapitre, nous proposons une étude complémentaire de la réduction de dimension en présence de deux modèles de bruit particulier. Le bruit blanc et le bruit autorégressif, dont les formules de projection sont respectivement explicitées Un cas réel de bruit localement autorégressif, illustré en figure 1.3 a été identifié dans des traces de la compétition du DPA contest V2 [START_REF]DPA Contest[END_REF] utilisées pour la validation des résultats.

La méthode de réduction de dimension proposée est ensuite comparée à deux méthodes bien connues de l'état de l'art : l'analyse discriminante linéaire (ALD ou Linear Discriminant Analysis (LDA) en anglais) et l'analyse en composante principale (ACP ou Principal Component Analysis (PCA) en anglais). Les différentes méthodes de réduction de dimension sont comparées à l'aide de la métrique du rapport de signal sur bruit (Signal-to-Noise Ratio (SNR) en anglais). Ces comparaisons ont donné lieu aux Théorèmes 1.2 et 1.3. L'ensemble des théorèmes de ce chapitre et du suivant font tous l'objet de démonstrations détaillées.

Pour finir, une validation pratique des résultats est proposée, en premier lieu sur des données simulées, puis sur des traces fournies lors de la compétition du DPA contest V2 [START_REF]DPA Contest[END_REF] .

Chapitre 3 : Fuites Multivariées et Modèles Multiples

En lien direct avec le chapitre précédent, ce chapitre traite lui aussi de la multidimentionnalitées des fuites. Mais ici, nous allons plus loin et traitons le cas de modèles multiple, lorsque 𝑆 ≥ 1. L'ensemble des résultats obtenus dans ce chapitre est résumé en figure 1.4. Cette figure explicite les distingueurs optimaux dans le cas de fuites multivariées (𝐷 ≥ 1) et de modèles multiples (𝑆 ≥ 1). Is α known?

D M L (x, t) = argmin k tr (x -αy) T Σ -1 (x -αy) yes
Leakage model:

Optimal distinguisher: Ce chapitre propose également des algorithmes permettant une implémentation efficace du calcule des différents distingueurs. De plus, une méthode de caractérisation du bruit est également proposée.

x = αy ⋆ + n ∀q, n q ∼ N (0, Σ) y ⋆ = φ(t, k ⋆ ) y = φ(t, k) no α ∈ R D×S , Σ ∈ R D×D x ∈ R D×Q , y ∈ R S×Q D M L,sto (x, t) = argmax k tr y T (yy T ) -1 y x T Σ -1 x
Pour finir, plusieurs expérimentations sont proposées pour évaluer l'efficacité des distingueurs proposés. L'une des évaluation est réalisée sur des traces réelles fournies lors de la compétition du DPA contest V4 [START_REF]DPA Contest[END_REF] . Les résultats sont résumés en figure 1.5. On y retrouve l'utilisation des distingueurs D ML,sto et D ML . De plus, on y compare l'efficacité du distingueur 𝐷𝑖𝑚𝑙 lors de deux cas d'usage. Le premier D ML (self ), lorsque le modèle est parfaitement connu, c'est à dire que 𝛼 est calculé directement sur les traces analysées. Le second D ML , lorsque 𝛼 est calculé sur des trace distinctes. • les seize registres de 64-bits : rax, rbx, rcx, rdx, rsi, rdi, rbp, rsp, r8, r9, r10, r11, r12, r13, r14, r15, • les six registres de 16-bits : cs, ss, ds, es, fs, gs, • les 64-bits du registre de drapeaux, • le pointeur d'instruction, noté PC (Program Counter en anglais).

Les informations listées correspondent à une exécution sur une architecture x86 de 64bits. Les données ainsi récoltées sont stockées, comme dans les chapitres précédents, dans une matrice noté 𝑋 𝐷,𝑅,𝑄 ∈ (F 2 ) 𝐷,𝑅,𝑄 , avec 𝐷 le nombre de changements du pointeur d'instruction, 𝑅 le nombre de bits de registres enregistrés et 𝑄 le nombre de traces. Un exemple de trace logiciel est illustré en figure 1.6. Cette trace provient de l'exécution d'un algorithme cryptographique en boîte blanche fourni lors de la compétition de CHES-2016. En blanc, sont représentés les bits à zéro et en noir les bits à un.

Une fois les données enregistrées, nous proposons dans ce chapitre deux algorithmes de prétraitement permettant une analyse efficace. Un premier algorithme permet de resynchroniser les traces. En effet, la présence de choix conditionnels dans les implémentations peut engendrer des désynchronisations entre les différentes traces. Si des traces ne sont pas alignées il devient alors impossible des les analyser. L'algorithme proposé permet de resynchroniser rapidement les données en se basant uniquement sur les différentes valeurs du pointeur d'instructions.

Un second algorithme permet, quand à lui, de sélectionner les points pouvant révéler 1. RÉSUMÉ DE LA THÈSE EN FRANÇAIS de l'information. En effet, de nombreux éléments enregistrés ne sont pas pertinents pour l'analyse. L'algorithme, dit de débruitage, utilise deux matrices particulières. La première, la matrice d'activité 1.1, permet de déterminer l'ensemble des points invariants relativement à l'axe 𝑄. Definition 1.1. La matrice d'activité 𝐴 𝐷,𝑅 d'un ensemble de données 𝑋 𝐷,𝑅,𝑄 est définie comme :

𝐴 𝐷,𝑅 = [ 𝐴 𝑑,𝑟 = ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ 1, if 𝑄-1 ∑ 𝑞=0 𝑋 𝑑,𝑟,𝑞 / ∈ {𝑄, 0} 0, sinon ]

𝑑<𝐷, 𝑟<𝑅

La seconde est la matrice de transition 1.2, elle permet de déterminer les invariants d'un ensemble de données relativement à l'axe 𝐷. Definition 1.2. La matrice de transition 𝑇 𝐷,𝑅 d'un ensemble de données 𝑋 𝐷,𝑅,𝑄 est définie comme :

𝑇 𝐷,𝑅 = [ 𝑇 𝑑,𝑟 = ⎧ ⎪ ⎨ ⎪ ⎩ 1, if 𝑑 = 0 ∨ 𝑄 𝑞=1 𝑋 𝑑-1,𝑟 ⊕𝑋 𝑑,𝑟 sinon ]

𝑑<𝐷, 𝑟<𝑅

L'utilisation de l'algorithme de débruitage permet de fortement diminuer l'ensemble des donnés à analyser. En effet, l'application de cet algorithme à l'implémentation cryptographique en boîte blanche de CHES-2016 permet d'obtenir les résultats illustrés en figure 1.7. On observe ainsi que le débruitage permet d'identifier les 0.29% des données de départ pouvant fuiter de l'information.

Une fois les données resynchronisées et débruitées, une analyse par corrélation permet de retrouver les clés secrètes d'implémentations cryptographiques en boîte blanche. De plus, l'analyse proposée permet, grâce aux pointeurs d'instructions, de retrouver les lignes de codes et les registres d'où proviennent les fuites. CHAPTER 2 • the add round key applies a eXclusive OR (XOR) between the current state and the subkey round. The round keys are computed applying the Rijndael keyschedule to the input key (also called master key), • the S-box is publicly known 8-bit substitution function with good non-linearity properties,

• the shiftRows lets the first row unmodified, shifts the second one by one to the left, the third one by two and the last one by three as displayed in the following • the mixColumns is a linear function applied on each column of the input state, is represented as matrix product in the The complete subfunctions' schedule of an AES-128 is provided in Fig. 2.3, it starts off by a XOR between the 128-bit of the plaintext and the master key (𝑘 ⋆ 0 ) ; followed by ninth rounds composed of the four subfunctions, previously described, and a last one without the mixColumns. Almost all practical validations we present are done on

INTRODUCTION

Plaintext

SubBytes

ShiftRows

MixColumns

Ciphertext

𝑘 ⋆ 𝑖=0 if 𝑖 == 10 if 𝑖 < 10 if 𝑖 < 10 𝑖 + + 𝑘 ⋆ 𝑖 Figure 2.3: AES complete schedule.
the AES implementation. This choice is motivated by its robustness, as it remains cryptographically secure after more than twenty years of evaluation ; and by its wide use in many sorts of applications. Further more, the implementations and the set of traces used are publicly available allowing the repoductibility.

Introduction to the Side-Channel Analysis (SCA)

Since ′ 99 and the seminal paper of Kocher et al. [START_REF] Paul | Differential power analysis[END_REF] called Differential Power Analysis (DPA), embedded systems (smartcards, smartphones, Internet of Thing (IoT). . . ) are known to be vulnerable to the Side-Channel Analysis (SCA). This kind of attacks use leakage of information from non-conventional communications channels (ElectroMagnetic (EM), execution time, power consumption. . . ) to extract secret information. The main application of the SCA is the recovery of secret keys manipulated by symmetric or asymmetric cryptographic algorithms.

Prior Knowledge

Others exploitation of the SCA have been proposed as the Side-Channel Analysis for Reverse Engineering (SCARE) [START_REF] Clavier | An improved SCARE cryptanalysis against a secret A3/A8 GSM algorithm[END_REF][START_REF] Clavier | Complete reverse-engineering of AES-like block ciphers by SCARE and FIRE attacks[END_REF][START_REF] Novak | Side-channel attack on substitution blocks[END_REF][START_REF] Rivain | SCARE of secret ciphers with SPN structures[END_REF], with the objective to reveal secrets characteristics of the implementation. For examples SCARE could be used to recover secret S-box. Indeed, it could happen that manufacturers secretly change functions of public cryptosystem even if Kerckhoffs's principle advises that a cryptosystem "must not require secrecy" (except the key) [START_REF] Kerckhoffs | La Cryptographie Militaire[END_REF] to be secure.

In the case of key recovering, the objective is to discriminate 𝑘 ⋆ between 𝑘 comparing recorded leakage 𝑋 and models 𝑌 . But 𝑘 have been presented as an 𝑛-bit vector (usually, 𝑛 = 8) that is much more less than a real cryptographic key size. Indeed, some institutions, summarized in Tab. 2.1, advise to use a key length between 84-bit and 3072-bit according to the chosen cryptographic primitives. That is why the SCA adopts "divide-and-conquer" approach, splitting the entire key in words of 𝑛-bit 𝑘, with 𝑛 enough small to be exhaustively iterated. Then each sub key is independently analyzed. For example, in the case of the AES-128 , the 128-bit of the secret key are generally split in sixteen 8-byte words. In this way, to recover the whole secret, 𝑋 is compared to

{𝑌 𝑄 𝑏 (𝑘)} 𝑏<16 𝑘<256
. But in order to simplify the notations and without loss of generality, the formula are usually given only for one 𝑛-bit words, so 𝑘 ⋆ , 𝑘 and 𝑇 denote 𝑛-bit words and the generalization to the entire key recovering is trivial.

INTRODUCTION

Notations

Matrices

Whatever the target and regardless of the acquisition method, an attacker will record traces and additional data as inputs and/or outputs values. Matrix is the perfect mathematical object to store and manipulate these collected data. That is why we adopt in the whole thesis matrix notations. The queries are indexed by 𝑞 = 1, . . . , 𝑄, where 𝑄 is the number of traces. The samples in a given trace are indexed by 𝑑 = 1, . . . , 𝐷.

Any matrix containing 𝐷 samples from 𝑄 queries is denoted by:

𝑀 𝐷,𝑄 = (𝑀 𝑑,𝑞 ) 𝑑<𝐷,

𝑞<𝑄

, where 𝑑 = 1, . . . , 𝐷 is a row index and 𝑞 = 1, . . . , 𝑄 is a column index. We also denote all 𝑑th samples for all traces as (𝑀 𝑑,𝑞 ) 𝑞<𝑄 = 𝑀 𝑄 𝑑 , and all the samples for the 𝑞th trace as (𝑀 𝑑,𝑞 ) 𝑑<𝐷 = 𝑀 𝐷 𝑞 . Thus, 𝑀 𝑄 𝑑 is a row vector and 𝑀 𝐷 𝑞 is a column vector. Two matrices noted side-by-side are implicitly multiplied.

The notation (•) T is for transpose. For instance, if 𝑢 = 𝑢 𝐷 is 𝐷 × 1 matrix, then 𝑢 T = (𝑢 𝐷 ) T is a 1 × 𝐷 matrix. The usual scalar product on R 𝐷 is denoted by

⟨𝑢|𝑣⟩ = 𝑢 T 𝑣 ∈ R. The 2-norm (also called Euclidean norm) of 𝑢 is ‖𝑢‖ 2 = √ ⟨𝑢|𝑢⟩.
Then let ‖.‖ 𝐹 denote the Frobenius norm of a matrix (square root of the sum of its squared elements), such that ‖𝑀 ‖ 𝐹 = √ tr (𝑀 𝑀 T ) where we denote by tr (•) the trace of a square matrix, that is the sum of its diagonal terms. Note that tr (𝐴𝐵) = tr (𝐵𝐴) for compatible matrix dimensions. Random variables will be denoted by capital letters. The probability density function of a random variable 𝑋, as a function of 𝑥, is denoted by 𝑝 𝑋 (𝑥) or simply 𝑝(𝑥) if the context is clear.

Signals

Let 𝑋 denote the leakage measurements, 𝑌 the model, 𝑁 the measurement noise, and 𝛼 the link between the model and the measurements. Notations 𝑋, 𝑌 are consistent

Notations

with the usual convention in machine learning, where 𝑋 is for the collected data and 𝑌 for the classification labels. The model 𝑌 depends on a key guess 𝑘, an 𝑛-bit vector (as usual 𝑛 = 8), and on some known plaintexts 𝑇 (usually also an 𝑛-bit vector, it could also be the ciphertext). In a view not to overload the notations, we write 𝑌 instead of 𝑌 (𝑘). As it is customary in SCA, the correct key is denoted by 𝑘 ⋆ . The corresponding model using the correct key 𝑌 (𝑘 ⋆ ) is denoted by 𝑌 ⋆ . A sensitive variable that depends on the unknown secret key 𝑘 is leaking through a leakage function 𝜑. Let 𝑆 be the model dimensionality and 𝜑 :

F 2 𝑛 × F 2 𝑛 → R 𝑆 a vectorial function, with 𝑆 components.
Typically, 𝜑 is the Hamming Weight (HW) function, a sum of weighted bits, or its composition with a S-box. In order to further simplify the mathematical derivations, we assume that 𝜑 is centered. The model for a given key byte hypothesis 𝑘 is given by

𝑌 𝑞 (𝑘) = 𝜑 (𝑇 𝑞 ⊕ 𝑘), (2.1)
a well-known example is 𝑌 = HW (𝑇 ⊕ 𝑘), where HW is the Hamming Weight function.

The actual leakage can be written as

𝑋 𝑑,𝑞 = 𝛼 𝑑,𝑆 𝑌 𝑆,𝑞 (𝑘 ⋆ ) + 𝑁 𝑑,𝑞 , (2.2)
where the weights 𝛼 𝑑,𝑆 are not all zero, and 𝑁 𝑑,𝑞 is some random measurement noise.

In matrix notation, we can summarize the equations for different values of 𝑑 and 𝑞 by a single matrix equation

𝑋 𝐷,𝑄 = 𝛼 𝐷,𝑆 𝑌 𝑆,𝑄 (𝑘 ⋆ ) + 𝑁 𝐷,𝑄 (2.3)
where 𝛼 𝐷,𝑆 is a 𝑆-column matrix and 𝑌 𝑆,𝑄 (𝑘 ⋆ ) is a 𝑆-row matrix, whose product is a 𝐷 × 𝑄 matrix. Notice that our convention to consider traces as lines and dimensions as rows allows us to write the deterministic part of the leakage as 𝛼𝑌 ⋆ which writes more naturally than the opposite order where traces would be viewed as a vertical time series. We make the stationary assumption that the noise distribution does not depend on the particular query, that is, the 𝑁 𝐷 𝑞 are independent and identically distributed independently of the value of 𝑞. For a given 𝑞, however, the noise samples of 𝑁 𝐷 𝑞 can very well be correlated. We assume that 𝑁 𝐷 𝑞 follows a 𝐷-dimensional zero-mean multivariate normal distribution N(0, Σ,), where covariance matrix Σ is a symmetric positive definite 𝐷 × 𝐷 matrix. Therefore, there exists a matrix Σ 1/2 , which is such that Σ 1/2 Σ 1/2 = Σ. We refer to Σ 1/2 as the standard deviation noise matrix.

INTRODUCTION

Models Illustrations

With the aim of illustrating the signals notations previously introduced, we provide some concrete examples for distinct values of 𝑆. The leakage signal may be represented as a continuous curve as illustrated in Fig. 2.4. The practical acquisition is done through a temporal series of 𝐷 "discrete samples" within one clock period. For 𝑆 = 1, the traces [START_REF] Bruneau | Boosting Higher-Order Correlation Attacks by Dimensionality Reduction[END_REF][START_REF] Bruneau | Less is more -dimensionality reduction from a theoretical perspective[END_REF]. When considering traces that are not only modulated but also have an offset term we have 𝑆 = 2. We then write the 2-dimensional model as

( 𝑌 1 𝑄
)

, where 𝑌 and 1 𝑄 are 1 × 𝑄 matrices (𝑌 1 , 𝑌 2 , . . . , 𝑌 𝑄 ) and (1, 1, . . . , 1). The 𝐷 × 2 matrix 𝛼 in Eq. 2.3 actually takes the special form (𝛼 𝛽) where 𝛽 is the offset value. An illustration is provided in Fig. 2.5 where the parameter 𝛽 ∈ R 𝐷 is the waveform when there is no signal, whereas 𝛼 ∈ R 𝐷 is the signal envelope. The complete model is the sum 𝛼𝑌 + 𝛽, where 𝑌 is the HW of some intermediate variable (such as the XOR operation 𝑇 ⊕ 𝑘 ⋆ ) on 𝑛 = 4 bits. While the leakage signal may be represented as a continuous curve as illustrated in Fig. 2.5, the practical acquisition is done through the temporal series of 𝐷 "discrete samples", typically within one clock period. For 𝑆 = 2, we thus write Eq. 2.3 as

Notations

𝑋 = 𝛼𝑌 ⋆ + 𝛽1 𝑄 + 𝑁 (2.4)
where 𝑋 is 𝐷 ×𝑄, 𝛼 and 𝛽 are 𝐷 ×1, 𝑌 ⋆ and 1 𝑄 = (1, . . . , 1) are 1×𝑄, and 𝑁 is 𝐷 ×𝑄.

Here 𝑌 is assumed centered: E(𝑌 ) = 0 𝑄 = (0, . . . , 0) (since the non-centered part is captured by the 𝛽1 𝑄 term) and of unit variance for every 𝑞: var(𝑌 𝑞 ) = E(𝑌 2 𝑞 ) = 1. For 𝑆 ≥ 2, the actual value of 𝑆 reflects the complexity of the model. For example, in the weighted sum of bits model, the model for each trace can be written as

𝑛 ∑ 𝑠=1 𝛼 𝑠 𝑌 𝑠 + 𝛽,
where 𝑌 𝑠 is the 𝑠 th bit of the 𝑛-bit sensitive variable 𝑌 . Accordingly, we have

𝑆 = 𝑛 + 1,
and thus:

𝛼 = ( 𝛼 1 . . . 𝛼 𝑛 𝛽 ) , 𝑌 = 𝑌 1 . . . 𝑌 𝑛 1 T . (2.5)
This leakage model is more complex than before but may arise in practice. For example, Fig. 2.6 plots the coefficients 𝛼 1 , . . . , 𝛼 8 estimated of the traces taken from an ATMega smartcard-the datasets are available from the DPA contest V4 [START_REF]DPA Contest[END_REF] team. In particular one can observe that samples around [START_REF] Maghrebi | Breaking cryptographic implementations using deep learning techniques[END_REF]80] are ordered by HW: this part of the trace resembles the upper left part of Fig. 2.5 for 𝑆 = 2. By analyzing the (𝑛 + 1)variate model of Eq 2.5, one can indeed see that around [START_REF] Maghrebi | Breaking cryptographic implementations using deep learning techniques[END_REF]80], the vectors 𝛼 1 , . . . , 𝛼 8 are almost identical. However, samples in intervals [170, 250] or [330, 400] have a more complex model. These times, the eight vectors 𝛼 1 , . . . , 𝛼 8 are clearly different, so the leakage is 9-variate.

Distinguishers

Once we have the collected the data 𝑋, and the models 𝑌 , the comparing step use a discriminant function called a distinguisher and noted D. For example, the DPA [START_REF] Paul | Differential power analysis[END_REF] uses the difference between averaged traces, the Correlation Power Analysis (CPA) [START_REF] Brier | Correlation power analysis with a leakage model[END_REF] the Pearson correlation coefficient, the Template Attack (TA) [START_REF] Chari | Template attacks[END_REF] the probability density function of Gaussian distributions. . . A distinguisher D maps a collection of leakages 𝑋 and publicly known plaintexts (or ciphertexts) bytes 𝑇 to an estimation of the secret key 𝑘 ⋆ . Thereafter, Heuser et al. define in [START_REF] Heuser | Good is not good enough -deriving optimal distinguishers from communication theory[END_REF] the notion of optimal distinguisher rewriting the SCA as a communication channel problem. The goal is to maximize the probability of success of D(𝑋, 𝑌 = 𝑘 ⋆ ) and it could be formalized as in the Theorem 2.1 proposed in [START_REF] Heuser | Good is not good enough -deriving optimal distinguishers from communication theory[END_REF].

Examples of Side-Channel Analysis (SCA)

Theorem 2.1 (Optimal distinguishing rule). The optimal distinguishing rule is given by the maximum a posteriori probability (MAP) rule

D(𝑋 𝐷,𝑄 , 𝑇 𝑄 ) = argmax 𝑘 ( P{𝑘} • 𝑝(𝑋 𝐷,𝑄 |𝑇 𝑄 , 𝑘 = 𝑘 ⋆ ) ) . (2.6)
If the keys are assumed equiprobable, i.e., P{𝑘} = 2 -𝑛 , Eq. (2.7) reduces to the maximum likelihood (ML) rule

D(𝑋 𝐷,𝑄 , 𝑇 𝑄 ) = argmax 𝑘 ( 𝑝(𝑋 𝐷,𝑄 |𝑇 𝑄 , 𝑘 = 𝑘 ⋆ ) ) . (2.7)
In the whole thesis we consider the attacker does not inject partial information gathered from the leakage analysis into a possible choice of 𝑇 (nonadaptive attack). The presented results tolerate chosen texts attacks, but consider them only as observed inputs. We do not optimize the attack according to chosen inputs. Thus 𝑌

Examples of Side-Channel Analysis (SCA)

To conclude the introduction of the SCA and to emphasize the efficiency of this kind of analysis we provide in the current section a short presentation of the Capture The Flag (CTF) of CHES-20164 . This Challenge have been subject of our participation during the second year of the thesis for which we finish at the second rank of the student participants and at the 24th (over 79) for the overall ranking. During the CTF two types of cryptographic implementations was submitted:

1. AES-128 running on Atmel XMEGA, with power traces and the secret key not stored in firmware (attack via DPA).

2. AES-128 running on Linux computer, without power traces and the secret key stored in firmware (White Box Cryptography (WBC) implementation).

INTRODUCTION

We focus here on the analysis of the provided power traces, an analysis of the WBC challenge is provided in the Chap. 5. For each power traces challenge, six distinct datasets are provided, four with a known key(s) to let the attacker realizing learning steps and two with the same secret key to recover. All datasets are composed of 𝑄 = 1000 traces with the corresponding plaintexts and ciphertexts. The content of the datasets are given below:

• for the known key datasets:

-"knownfixed-fixed": the key and the plaintext are fix, -"knownfixed-rand": the key is fixed and the plaintexts are random, -"knownrand-fixed": the keys are random and the plaintext is fix, -"knownrand-rand": the keys and the plaintexts are random, • for the unknown key datasets:

-"secretfixed-fixed": the key and the plaintext are fix, -"secretfixed-rand": the key is fix and the plaintexts are random.

The attacks that we proposed in this section only need the "secretfixed-fixed" datasets, and the plaintexts to be mounted. We provide in the following Subsec. 2.4.1 a complete explanation of the analysis mounted to recover the secret key of the first submitted implementation. Then we summarize in the Subsec. 2.4.2 the attacks' methodologies that we used to recover the secret key of some other challenges.

First Key Recovering

The first submitted implementation is described as "A very straight-forward AES-128 implementation written in C5 , Standard CPA attack should work". In fact the CPA focusing the output of the S-box at the first round, on which we apply the HW function, provides very efficient results. Formalizing, we get the following Formula 2.8 for the leakage model (we do not precise the model dimensionality because is equal to one, 𝑆 = 1):

𝑌 𝑄,𝐾,𝐵 = {𝑌 𝑞,𝑘,𝑏 = HW (S-box (𝑇 𝑞,𝑏 ⊕ 𝑘))} 𝑘<256 𝑞<𝑄,𝑏<16 (2.8)
For the CPA, the distinguishing step is the Pearson correlation coefficient that we compute between 𝑋 𝐷,𝑄 and 𝑌 𝑄,𝐾,𝐵 . In the Fig. The entire dataset is not needed to recover the entire secret key. We can see in the Fig. 2.8 the rank of the right key byte, the x-axis represents the number of traces used for the CPA and the y-axis gives the corresponding rank of the right key byte. We show that all the key bytes are recovered in less than forty traces.

The proposed CPA permits us to recover the following secret key: 0x7b 0x56 0x27 0xfa 0x8e 0x4 0x8b 0x57 0x90 0xcd 0xe1 0xdd 0xd9 0x18 0x1d 0x1f

Successfully Mounted Attacks

The following Listing 2.4.2 provides the description of six other attacks that lead us to recover the entire secret key. For each exploit we provide the name of the challenge in bold, a short description of the countermeasure(s) used in the implementation under attack and the methodology of our attack.

• Stagegate #2: "AES in C with a tiny bit of random jitters before the encryption happens":

1. We resynchronize the dataset on a recurrent pattern.

2. We realize a CPA on the resynchronized traces with the models given in the Formula 2.8.

• AES RSI: "AES with Random Starting Index shuffling countermeasure on Sbox":

1. We identify the sixteen S-box computation at the first round:

𝑋 𝐷,𝑄 -> {𝑋 𝐷 ′ =30,𝑄 𝑏 } 𝑏<16 , where 𝑋 𝐷 ′ =30 𝑏,𝑞
is the power leakage of one of the sixteen S-box computation in the trace 𝑞. The shuffling countermeasures on S-box prevents to identify, for a trace 𝑞 0 and a byte 𝑏 0 < 16, the corresponding

Examples of Side-Channel Analysis (SCA)

power leakage of S-box(𝑇 𝑏 0 ,𝑞 0 ⊕𝑘 ⋆ 𝑏 0 ) in {𝑋 𝐷 ′ =30 𝑏,𝑞 0 } 𝑏<16 .
2. We compute the sum of the sixteen S-box computations:

{𝑋 𝐷 ′ =30,𝑄 𝑏 } 𝑏<16 -> 𝑋 𝐷 ′ =30,𝑄 𝑠𝑢𝑚 = ∑ 𝑏<16 𝑋 𝐷 ′ =30,𝑄 𝑏 .
3. We realize a CPA on the summed traces and the models given in the Formula 2.8.

• Confusion: "AES with lots of jitters (dummy operation in all the implementation)":

1. We identify the sixteen S-box computation in each trace. To achieve this we compute the cross-correlation between the power leakage of a manually extracted S-box computation pattern and all the traces. Indeed, we get

𝑋 𝐷,𝑄 -> {𝑋 𝐷 ′ ,𝑄 𝑏 } 𝑏<16 .
2. We realize a CPA on the sixteen S-box executions and the models given in the Formula 2.8:

{D(𝑋 𝐷 ′ ,𝑄 𝑏 , 𝑌 𝑄 𝑘,𝑏 )} 𝑏<16,𝑘<256 .
• AES with lots of jitters: "Who needs masking. . . (shuffling of the S-box computation)":

1. We identify each S-box computation using a recurrent pattern: the huge peak that appears at each S-box computation.

2. We compute the sum and the CPA as in the AES RSI.

• FdLSifu1: "Shuffle and partial random (random S-box execution)": exactly the same attack as for AES RSI. • Plebe1:"Almost state-of-the-art AES (masked and shuffled S-box)":

1. We identify the masking scheme described in Figure 2.9.

2. We visually identify the power leakage of the Leak 1: {𝑋 𝐷 ′ ,𝑄 state,𝑖 } 𝑖<4 and of the Leak 2: {𝑋 𝐷 ′ ,𝑄 mask,𝑖 } 𝑖<4 , as we can see in the Fig. 2.10. 3. We apply the high order CPA proposed in [START_REF] Prouff | Statistical analysis of second order differential power analysis[END_REF], with the following datasets (centered products, where

𝑋 𝐷 ′ ⋆,𝑖 = ( 1 𝑄 ) ∑ 𝑞<𝑄 (𝑋 𝐷 ′ ⋆,𝑖,𝑞 )): {𝑋 𝐷 ′ ,𝑄 𝑖 } 𝑖<4 = {(𝑋 𝐷 ′ ,𝑄 mask,𝑖 -𝑋 𝐷 ′ mask,𝑖 ) × (𝑋 𝐷 ′ ,𝑄 state,𝑖 -𝑋 𝐷 ′ state,𝑖 )} 𝑖<4 ,
and the following model: where tmp 𝑏 = S-box (𝑇 𝑄 𝑏 ⊕ 𝑘), and . the Galois product, and with the following distinguisher step:

{𝑌 𝑄 𝑘,𝑏 = HW(3.
{D(𝑋 𝐷 ′ ,𝑄 ⌊𝑏/4⌋ , 𝑌 𝑄 𝑘,𝑏 )} 𝑘<256,𝑏<16

Contributions

Dimension reduction. It is recognized that a sensitive data leaks over the time, which is manifested by the acquisition of few leaking samples. In this context, we proposed an innovative data reduction approach. The data reduction was usually viewed as a preprocessing. We demonstrate, in the context of univariate model, that the optimal distinguisher directly embed the dimension reduction. Furthermore, we generalize this new paradigm to multivariate models.

Leakage characterization and exploitation. We proposed in this thesis an accurate evaluation of the leakage. The exactness of the characterization leads us to mount stochastic attacks exploiting the whole leakage. This approach permits to take advantage of the huge variety of existing leakage: the data does not only leak through the perpetually used HW model. Complex models exist, each bit but also each combination of bits can leak through its own model. Furthermore, we can easily imagine a model that makes the HW model counterproductive, for examples if the focused byte leaks through the following model:

𝑋 = 7 ∑ 𝑖=0 (-1) 𝑖 𝑌 𝑖 + 𝑁 Software Analysis.
We present a software analysis based on data collected via a debugger, we choose GNU Debugger (GDB) for its capability and its usability but it can be replaced by another data providers. One novelty of this contribution lies in the diversity of the collected data. In fact, we give a methodology that detect leakage from any kind of data manipulated during a code execution. Thus, we bring to light leakage ensue from flags registers. This result shows that leakage could follow from any kind of storage. Additionally, we proposed a pioneering feature of resynchronization. Our proposed realignment algorithm takes advantage of the auxiliary information provided by the program counter. Once traces are resynchronized, we are sure to analyze data

INTRODUCTION

that results from the same operation at the same iteration. Moreover, the realignment process is fast and efficient as it only needs one read of the program counters and is based on accumulation.

The Thesis

The thesis is divided in three main chapters.

Less is more. As we can notice in the Fig. 2.6, whichever the complexity of the model, sensitive data leaks over the time in some samples. In this first Chap. 3 we answer to the following question:

How can we optimally capture multidimensional leakage as one single compressed sample without loose of efficiency? This study shows that optimal attacks remain optimal after a first pass of dimension reduction, which takes the form of a linear projection of the samples. We then investigate the state-of-the-art dimensionality reduction techniques, and find that asymptotically, the optimal strategy coincides with the Linear Discriminant Analysis (LDA). The two main objectives of the dimension reduction are the reduction of computational complexity and the exploitation of the leakage in its entirety. This Chap. 3 gives rise to a first publication at CHES-2015 [START_REF] Bruneau | Less is more -dimensionality reduction from a theoretical perspective[END_REF].

Multivariate Leakages and Multiple Models. Once a solution has been found to the problem of multivariate leakage, the question that naturally follows is:

How can we optimally capture multidimensional leakage exploiting multivariate models? In the state-of-the-art, these two issues have two independent solutions: on the one hand, dimensionality reduction can cope with multivariate leakage; on the other hand, stochastic approach can cope with multiple models. In the Chap. 4, we combine both solutions to derive closed-form expressions of the resulting optimal distinguisher, in all situations where the model can be either profiled offline or regressed online. We recover known results for mono and bivariate models (including CPA), and investigate novel distinguishers for multiple models with 𝑆 ≥ 2. In addition, following ideas from the AsiaCrypt'2013 paper [START_REF] Lomné | Behind the scene of side channel attacks[END_REF], we provide fast computation algorithms in which the traces are accumulated prior to computing the distinguisher values. This Chap. 4 gave rise to

The Thesis

a first publication at PROOFS-2016 [START_REF] Bruneau | Optimal side-channel attacks for multivariate leakages and multiple models[END_REF], to a poster at CHES-2016 and to an extended version in the journal of cryptographic engineering [START_REF] Bruneau | Optimal side-channel attacks for multivariate leakages and multiple models[END_REF].

Binary Data Analysis for Source Code Leakage Assessment. In this Chap. 5, we keep increasing dimension. We treat a case where models 𝑌 are 𝑆 × 𝑄 matrices and the collected data 𝑋 is a 𝐷 × 𝑅 × 𝑄 matrix. We meet this problematic collecting data provided by GDB. In this setting, we proposed an answer to the question: How can we identified and characterize leaking information exploiting 3-dimensional "software traces"? We proposed a methodology of data collection and analysis to identify potential leakage from any software implementation. We introduce a multivariate leakage analysis to extract the leaking points from the data. Then, we leverage on GDB to keep track of the execution context to map the identified leakage to the source code. We succeed to overcome two main difficulties: the misalignment and the multiplicity of leaking resources. Finally, we show how we can identify leakage in the source code applying our solution to a WBC implementation. This Chap. 5 gave rise to a first publication at DTIS-2018 [START_REF] Bouvet | Give Me Your Binary, I'll Tell You If It Leaks[END_REF] and another one at SecITC-2018 [START_REF] Facon | Binary data analysis for source code leakage assessment[END_REF].

CHAPTER 3

Less Is More

Contributions

In this chapter, we tackle the 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 3.2 Review of the State-of-the-Art. 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 SNR 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 [START_REF]DPA Contest[END_REF] traces.

Review of the State-of-the-Art.

Side-Channel Analysis (SCA) exploits leakages from devices. Embedded systems are targets of choice for such attacks. Typical leakages are captured by instruments such as oscilloscopes, which sample power or electromagnetic traces. The resulting leaked information about sensitive variables is spread over time.

In practice, two different attack strategies coexist. On the one hand, the various leaked samples can be considered individually-this is typical of non-profiled attacks such as Correlation Power Analysis [START_REF] Brier | Correlation power analysis with a leakage model[END_REF]. On the other hand, profiled attacks characterize the leakage in a preliminary phase. An efficient leakage modelization should then involve a multidimensional probabilistic representation [START_REF] Chari | Template attacks[END_REF].

The large number of samples to feed into the model has always been a problematic issue for multidimensional SCA. One solution is to use techniques to select Points-of-Interest (PoI). 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 [5], avoid this problem. Other formal criteria, related to non-profiled attacks, have also been proposed [START_REF] Hajra | On the optimal pre-processing for non-profiling differential power analysis[END_REF][START_REF] Oswald | Improving side-channel analysis with optimal linear transforms[END_REF].

Therefore, there seems to be a converging effort, in both non-profiled and profiled

LESS IS MORE

attacks, to reduce the dimensionality of multidimensional measurements. This desirable property of dimensionality reduction achieves several goals simultaneously:

• it simplifies the Side-Channel (SC) problem (to a single multivariate probability density function);

• 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.

Dimensionality reduction is part and parcel of profiled attacks. The seminal paper on Template Attack (TA) [START_REF] Chari | Template attacks[END_REF] is motivated by keeping covariance matrices involved in the training phase sufficiently well conditioned. Manual selection of relevant leaking points was discussed in [START_REF] Oswald | Practical Second-Order DPA Attacks for Masked Smart Card Implementations of Block Ciphers[END_REF] as educated guesses. Several automated techniques were proposed, such as 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 ANalysis Of VAriance (ANOVA) or F-test is a ratio between the explained variance and the total variance-see e.g. [START_REF] Danger | Highorder timing attacks[END_REF][START_REF] Kuhn | Efficient template 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 Regression Analysis (LRA), it is known as the coefficient of determination, denoted by the symbol 𝑅 2 . It is employed in the context of SCA 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 [START_REF] Batina | Getting more from PCA: first results of using principal component analysis for extensive power analysis[END_REF] and templates in [5]. The eigenvalues of PCA can be viewed as a security metric [START_REF] 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 sidechannel 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 [START_REF] Oswald | Improving side-channel analysis with optimal linear transforms[END_REF], the cor-

Theoretical Solution in the Presence of Gaussian Noise

rect 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 non-profiling 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 SC literature. 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 higherorder DPA with projection pursuits[END_REF][START_REF] Reparaz | Selecting time samples for multivariate DPA attacks[END_REF].

Theoretical Solution in the Presence of Gaussian Noise

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 [START_REF] Cover | Elements of information theory[END_REF] 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 TA [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 𝑄 traces of dimensionality 𝐷 in a matrix 𝑋 𝐷,𝑄 , where each trace 𝑋 𝐷,𝑞 corresponds to a known plaintext 𝑇 𝑞 , the best key guess that maximizes the probability of success is given by

D(𝑋 𝐷,𝑄 , 𝑇 𝑄 ) = argmax 𝑘 𝑝(𝑋 𝐷,𝑄 |𝑇 𝑄 , 𝑘 ⋆ = 𝑘) (3.1) = argmax 𝑘 𝑝 𝑁 𝐷,𝑄 (𝑋 𝐷,𝑄 -𝛼 𝐷 𝑌 𝑄 (𝑘)) (3.2) = argmax 𝑘 𝑄 ∏ 𝑞=1 𝑝 𝑁 𝐷 𝑞 (𝑋 𝐷 𝑞 -𝛼 𝐷 𝑌 𝑞 (𝑘)) (3.3)
where

𝑝 𝑁 𝐷 𝑞 (𝑧 𝐷 ) = 1 √ (2𝜋) 𝐷 | det Σ| exp ( - 1 2 (𝑧 𝐷 ) T Σ -1 𝑧 𝐷 ) . (3.4)
We have used the independence of the queries in Eq. 3.3 and the assumption that at each query, the noise distribution is the same in Eq. 3.4.

LESS IS MORE

Notice that, the optimal attack can as well be a Simple Power Analysis (SPA) (if 𝑄 = 1) or a Differential Power Analysis (DPA) (if 𝑄 > 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 (𝑄 ≫ 1).

Optimal Dimensionality Reduction

We state our main result in the following Theorem 3.1: Theorem 3.1. The optimal attack on the multivariate traces 𝑋 𝐷,𝑄 is equivalent to the optimal attack on the univariate traces X𝑄 , obtained from 𝑋 𝐷,𝑄 by the formula:

X𝑞 = ( 𝛼 𝐷 ) T Σ -1 𝑋 𝐷 𝑞 (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 (𝑞 = 1, . . . , 𝑄). (3.5)
Proof. By taking the logarithm of the expression to be maximized in Eqs. 3.1-3.4, the optimal distinguisher D(𝑋 𝐷,𝑄 , 𝑇 𝑄 ) rewrites

D(𝑋 𝐷,𝑄 , 𝑇 𝑄 ) = argmin 𝑘 𝑄 ∑ 𝑞=1 ( 𝑋 𝐷 𝑞 -𝛼 𝐷 𝑌 𝑞 (𝑘) ) T Σ -1 ( 𝑋 𝐷 𝑞 -𝛼 𝐷 𝑌 𝑞 (𝑘) ) . (3.6)
For each trace index 𝑞, the terms in the sum expand to

(𝑋 𝐷 𝑞 ) T Σ -1 𝑋 𝐷 𝑞 ⏟ ⏞ cst. 𝐶 independent of 𝑘 -2(𝛼 𝐷 ) T 𝑌 𝑞 (𝑘)Σ -1 𝑋 𝐷 𝑞 + (𝑌 𝑞 (𝑘)) 2 (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 = 𝐶 -2𝑌 𝑞 (𝑘) [ (𝛼 𝐷 ) T Σ -1 𝑋 𝐷 𝑞 ] + (𝑌 𝑞 (𝑘)) 2 [ (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 ] = [ (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 ] ( 𝑌 𝑞 (𝑘) - (𝛼 𝐷 ) T Σ -1 𝑋 𝐷 𝑞 (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 ) 2 + 𝐶 ′ .
The latter division is valid since Σ is positive definite and 𝛼 𝐷 is a nonzero vector. Therefore,

D(𝑋 𝐷,𝑄 , 𝑇 𝑄 ) = argmin 𝑘 𝑄 ∑ 𝑞=1 ( 𝑌 𝑞 (𝑘) - (𝛼 𝐷 ) T Σ -1 𝑋 𝐷 𝑞 (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 ) 2 [ (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 ] = argmin 𝑘 𝑄 ∑ 𝑞=1 ( X𝑞 -𝑌 𝑞 (𝑘) ) 2 σ2 , (3.7)
where

⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ X𝑞 = (𝛼 𝐷 ) T Σ -1 𝑋 𝐷 𝑞 (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 , σ = ( (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 ) -1/2 .
(3.8)

We have shown that Eq. 3.6 and Eq. 3.7 are equivalent expressions for the same optimal distinguisher, computed either:

• on multivariate traces 𝑋 𝐷 𝑞 , with a noise covariance matrix Σ, or: • on univariate (i.e., scalar) traces X𝑞 , with scalar noise of variance σ2 . Theorem 3.1 shows that in fact, the optimal attack already integrates an optimal dimensionality reduction. The maximal success rate is not altered. Definition 3.1 (Projection vector). Let 𝑉 𝐷 be a column of 𝐷 elements. We call the projection of an acquisition campaign 𝑋 𝐷,𝑄 on 𝑉 𝐷 the new mono-sample traces (𝑉 𝐷 ) T 𝑋 𝐷,𝑄 . That is, every trace 𝑋 𝐷 𝑞 (1 ≤ 𝑞 ≤ 𝑄) of the initial campaign is summarized as one sample

(𝑉 𝐷 ) T 𝑋 𝐷 𝑞 = ⟨𝑉 𝐷 | 𝑋 𝐷 𝑞 ⟩.
Based on this definition, Theorem 3.1 can be interpreted as follows.

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

𝑉 𝐷 = Σ -1 𝛼 𝐷 (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 , of size 𝐷 × 1. Proof. By Therorem 3.1, X𝑄 ⏟ ⏞ 1 × 𝑄 matrix = (𝛼 𝐷 ) T Σ -1 (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 ⏟ ⏞ 1 × 𝐷 matrix (𝑉 𝐷 ) T 𝑋 𝐷,𝑄 ⏟ ⏞ 𝐷 × 𝑄 matrix .

LESS IS MORE

In addition, after this projection, the leakage becomes scalar and can be characterized by a SNR as shown as follow:

Corollary 3.2. After optimal dimensionality reduction, the SNR is given by

1 σ2 = (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 .
Proof. This is in line with Eq. 3.7. The random leakage 𝑋 𝐷,𝑄 is protected onto 𝑉 𝐷 to yield X𝑞 = 𝑌 𝑞 (𝑘) + Ñ (𝑞 = 1, . . . , 𝑄) where Ñ is an additive Additive White Gaussian Noise (AWGN) distributed as N(0, ((𝛼 𝐷 ) T Σ -1 𝛼 𝐷 ) -1 ). Recall that the variance of the leakage model has been assumed normalized = 1. Therefore, SNR equals

var(𝑌 𝑞 (𝑘)) var( Ñ ) = 1 ((𝛼 𝐷 ) T Σ -1 𝛼 𝐷 ) -1 = (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 .
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 [START_REF] Fei | A statistical model for DPA with novel algorithmic confusion analysis[END_REF].

Comment 3.1. Reminder:

• (1 + 𝑥) 𝑛 = 𝑛 ∑ ℎ=0 𝑥 ℎ ( ℎ 𝑛 ) , evaluated in 𝑥 = 1 yields: 𝑛 ∑ ℎ=0 ( ℎ 𝑛 ) = 2 𝑛 .
• Thus:

𝜕 𝜕𝑥 (1 + 𝑥) 𝑛 = 𝑛(1 + 𝑥) 𝑛-1 = 𝑛 ∑ ℎ=1 ℎ𝑥 ℎ-1 ( ℎ 𝑛 ) , evaluated in 𝑥 = 1 yields: 𝑛 ∑ ℎ=1 ℎ ( ℎ 𝑛 ) = 𝑛 ∑ ℎ=0 ℎ ( ℎ 𝑛 ) = 𝑛2 𝑛-1 .
• Thus:

𝜕 2 𝜕 2 𝑥 (1 + 𝑥) 𝑛 = 𝑛(𝑛 -1)(1 + 𝑥) 𝑛-2 = 𝑛 ∑ ℎ=2 ℎ(ℎ -1)𝑥 ℎ-2 ( ℎ 𝑛 ) , evaluated in 𝑥 = 1 yields: 𝑛 ∑ ℎ=2 ℎ(ℎ -1) ( ℎ 𝑛 ) = 𝑛 ∑ ℎ=0 ℎ(ℎ -1) ( ℎ 𝑛 ) = 𝑛(𝑛 -1)2 𝑛-2 . Thus 𝑛 ∑ ℎ=0 ℎ 2 ( ℎ 𝑛 ) = 𝑛 ∑ ℎ=0 (ℎ(ℎ -1) + ℎ) ( ℎ 𝑛 ) = 𝑛(𝑛 -1)2 𝑛-2 + 𝑛2 𝑛-1 = 𝑛(𝑛 + 1)2 𝑛-2
, and:

Var(𝑤 𝐻 (𝑇 ) - 𝑛 2 ) = E(𝑤 𝐻 (𝑇 ) - 𝑛 2 ) 2 = 1 2 𝑛 𝑛 ∑ ℎ=0 ℎ 2 ( ℎ 𝑛 ) - ( 𝑛 2 ) 2 = 𝑛(𝑛 + 1) 4 - 𝑛 2 4 = 𝑛 4 .

Discussion

It is interesting to note that the optimal dimensionality reduction does not depend on the actual distribution of 𝑌 𝐷 (𝑘), the deterministic part of the leakage model. This means that irrespective of the leakage function 𝜑, the best dimensionality reduction depends only on signal weights 𝛼 𝐷 and on noise covariance Σ.

Similarly, the optimal dimensionality reduction does not depend on the confusion coefficient of the leakage model [START_REF] Fei | A statistical model for DPA with novel algorithmic confusion analysis[END_REF]: for identical weight and noise distribution, the optimal linear combination of leakages is the same whether a eXclusive OR (XOR) or a substitution box operation is targeted.

Noise Distributions

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 𝐷 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ . Proposition 3.1.
For white noise, the optimal dimensionality reduction takes the form:

X𝑞 = 𝐷 ∑ 𝑑=1 𝛼 𝑑 𝜎 2 𝑑 𝑋 𝑑,𝑞 𝐷 ∑ 𝑑=1 𝛼 2 𝑑 𝜎 2 𝑑 (𝑞 = 1, . . . , 𝑄) (3.9)
Proof. Apply Theorem 3.1, where Σ -1 is diagonal with diagonal entries 1/𝜎 2 𝑑 .

Let SNR 𝑑 = 𝛼 2 𝑑 /𝜎 2 𝑑 be the initial SNR at the 𝑑 th sample before dimensionality reduction.

Proposition 3.2. For white noise, the equivalent SNR after optimal dimensionality reduction is given by the sum

̃ SNR = 𝐷 ∑ 𝑑=1 SNR 𝑑 .
(3.10)

Proof. By Corollary 3.2, SNR = (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 = 𝐷 ∑ 𝑑=1 𝛼 2 𝑑 𝜎 2 𝑑 = 𝐷 ∑ 𝑑=1 SNR 𝑑 .
Thus, combining independent multidimensional samples within one trace increases the SNR as if those samples were captured in 𝐷 independent traces. In this case having 𝑄 traces of 𝐷 samples each is simply the same as having 𝑄 × 𝐷 independent univariate 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. 3.6 for a real-world example). The noise covariance matrix takes the Toeplitz form:

Σ = 𝜎 2 ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 𝜌 𝜌 2 𝜌 3 • • • 𝜌 𝐷-2 𝜌 𝐷-1 𝜌 1 𝜌 𝜌 2 • • • 𝜌 𝐷-3 𝜌 𝐷-2 𝜌 2 𝜌 1 𝜌 • • • 𝜌 𝐷-4 𝜌 𝐷-3 𝜌 3 𝜌 2 𝜌 1 • • • 𝜌 𝐷-5 𝜌 𝐷-4 . . . . . . . . . . . . . . . . . . . . . 𝜌 𝐷-2 𝜌 𝐷-3 𝜌 𝐷-4 𝜌 𝐷-5 • • • 1 𝜌 𝜌 𝐷-1 𝜌 𝐷-2 𝜌 𝐷-3 𝜌 𝐷-4 • • • 𝜌 1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ = ( 𝜎 2 𝜌 |𝑑-𝑑 ′ | ) 1≤𝑑,𝑑 ′ ≤𝐷 .
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 3.3. For autoregressive noise, the optimal dimensionality reduction takes the form:

X𝑞 = 1 𝜎 2 (1-𝜌 2 ) [ (𝛼 1 -𝜌𝛼 2 )𝑋 𝑞,1 + 𝐷-1 ∑ 𝑑=2 ((1 + 𝜌 2 )𝛼 𝑑 -𝜌(𝛼 𝑑-1 + 𝛼 𝑑+1 ))𝑋 𝑑,𝑞 + (𝛼 𝐷 -𝜌𝛼 𝐷-1 )𝑋 𝐷 𝑞 ] . (3.11)
Proof. It can easily be checked that Σ -1 is tridiagonal, we can do that here, without risk of collision

Σ -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 3.1:

X𝑞 = 1 𝜎 2 (1-𝜌 2 ) ( 𝛼 1 𝛼 2 • • • 𝛼 𝐷-1 𝛼 𝐷 ) × ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 -𝜌 • • • 0 0 -𝜌 1 + 𝜌 2 • • • 0 0 . . . . . . . . . . . . . . . 0 0 • • • 1 + 𝜌 2 -𝜌 0 0 • • • -𝜌 1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 𝑋 𝑞,1 𝑋 𝑞,2 . . . 𝑋 𝑞,𝐷-1 𝑋 𝑞,𝐷 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
and expand.

Notice that in the optimal dimensionality reduction, each leakage sample 𝑋 𝑑,𝑞 is not only weighted by its corresponding 𝛼 𝑑 but also by its two neighbor weights 𝛼 𝑑±1 , provided the latter exist.

LESS IS MORE

Proposition 3.4. For autoregressive noise, the equivalent SNR after optimal dimensionality reduction is given by

 SNR = 1 𝜎 2 (1-𝜌 2 ) [ 𝛼 2 1 + (1 + 𝜌 2 ) 𝐷-1 ∑ 𝑑=2 𝛼 2 𝑑 + 𝛼 2 𝐷 -2𝜌 𝐷-1 ∑ 𝑑=1 𝛼 𝑑 𝛼 𝑑+1 ] . (3.12)
Proof. Apply Corollary 3.2:

SNR = 1 𝜎 2 (1-𝜌 2 ) ( 𝛼 1 𝛼 2 • • • 𝛼 𝐷-1 𝛼 𝐷 ) × ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 1 -𝜌 • • • 0 0 -𝜌 1 + 𝜌 2 • • • 0 0 . . . . . . . . . . . . . . . 0 0 • • • 1 + 𝜌 2 -𝜌 0 0 • • • -𝜌 1 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 𝛼 1 𝛼 2 . . . 𝛼 𝐷-1 𝛼 𝐷 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠
and expand.

SNR = 𝛼 2 𝜎 2 (1 -𝜌 2 ) ( 2 + (𝐷 -2)(1 + 𝜌 2 ) -2𝜌(𝐷 -1) ) = 𝛼 2 𝜎 2 (1 -𝜌)(1 + 𝜌) ((1 -𝜌)(𝐷 -𝜌(𝐷 -2))) = 𝛼 2 𝜎 2 1 1 + 𝜌 (𝐷 -𝜌(𝐷 -2)) = SNR × 𝐷(1 -𝜌) + 2𝜌 1 + 𝜌 .
In other words, optimal dimensionality reduction has the effect of multiplying the univariate SNR by the factor 𝐷 -𝜌(𝐷 -2) 1 + 𝜌 . This gain factor is of course equal to 1 for 54

Comparison with PCA and LDA

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

Principal Component Analysis (PCA)

PCA aims at identifying directions in the centered data set 𝑀 𝐷,𝑄 = (𝑀 𝑑,𝑞 ) 𝑑,𝑞 defined by

𝑀 𝑑,𝑞 = 𝑋 𝑑,𝑞 - 1 𝑄 𝑄 ∑ 𝑞 ′ =1 𝑋 𝑑,𝑞 ′ (1 ≤ 𝑞 ≤ 𝑄, 1 ≤ 𝑑 ≤ 𝐷). (3.14)
The directions of PCA are the eigenvectors of 𝑀 𝐷,𝑄 (𝑀 𝐷,𝑄 ) T .

Proposition 3.5. Asymptotically as 𝑄 -→ +∞, where we have used the hypothesis that 𝑌 𝑞 has unit variance.

1 𝑄 𝑀 𝐷,𝑄 (𝑀 𝐷,𝑄 ) T -→ 𝛼 𝐷 (𝛼 𝐷 ) T + Σ. ( 3
The classical PCA has the drawback that 𝑀 𝐷,𝑄 (𝑀 𝐷,𝑄 ) T depends both on the signal and on the noise. Inter-class PCA has been introduced in [5]. The matrix 𝑀 𝐷,𝑄 used in the PCA is traded for a more simple matrix 𝑍 𝐷,#𝑌 , where each column, indexed by 𝑦, is the centered column

1 ∑ 1≤𝑞≤𝑄 𝑌 𝑞 =𝑦 1 ∑ 1≤𝑞≤𝑄 𝑌 𝑞 =𝑦 𝑋 𝐷 𝑞 .
One advantage of this method is that it explicitly takes into account the sensitive variable 𝑌 .

It can be easily checked, that, asymptotically, each column 𝑍 𝐷 𝑦 tends to 𝛼 𝐷 𝑌 when 𝑄 -→ +∞. Therefore, 𝑍 𝐷,#𝑌 (𝑍 𝐷,#𝑌 ) T tends to a 𝐷 × 𝐷 matrix proportional to 𝛼 𝐷 (𝛼 𝐷 ) T . Here, the noise has been averaged away in each class of 𝑌 , which is a second advantage. Therefore, in the sequel, shall refer to the inter-class PCA of [5] simply as PCA.

We have the following spectral characterization of the asymptotic PCA: Proposition 3.6. Asymptotically, PCA has only one principal direction, namely the vector 𝛼 𝐷 . Proof. By Proposition 3.5, the PCA matrix tends asymptotically to 𝛼 𝐷 (𝛼 𝐷 ) T . This 𝐷 × 𝐷 matrix has rank one, because all its columns are multiple of 𝛼 𝐷 . Since

(𝛼 𝐷 (𝛼 𝐷 ) T )𝛼 𝐷 = 𝛼 𝐷 ((𝛼 𝐷 ) T 𝛼 𝐷 ) = ⃦ ⃦ 𝛼 𝐷 ⃦ ⃦ 2 2 × 𝛼 𝐷 ,
𝛼 𝐷 is the eigenvector with corresponding nonzero eigenvalue = ‖𝛼 𝐷 ‖ 2 2 . 56

Comparison with PCA and LDA

Notice that the uniqueness of the eigenvector for PCA holds in our model Eq. 2.1. However, Proposition 3.6 would not hold if e.g., the noise were correlated to the signal.

Remark 3.1. The classical PCA has the same eigenvector 𝛼 𝐷 if the noise is isotropic, i.e., white and of same variance in every dimension.

The paper [5] presents an optimization procedure to find the eigenelements.

Proposition 3.7. The asymptotic SNR after projection using PCA is equal to

⃦ ⃦ 𝛼 𝐷 ⃦ ⃦ 4 2 (𝛼 𝐷 ) T Σ𝛼 𝐷 .
Proof. After projection on the (asymptotic) eigenvector 𝛼 𝐷 , the leakage becomes:

(𝛼 𝐷 ) T 𝛼 𝐷 𝑌 𝑞 (𝑘 ⋆ ) + (𝛼 𝐷 ) T 𝑁 𝐷 𝑞 . The projected signal is ((𝛼 𝐷 ) T 𝛼 𝐷 )𝑌 𝑞 (𝑘 ⋆ ).
The projected noise is (𝛼 𝐷 ) T 𝑁 𝐷 𝑞 , which remains centered. Its variance is equal to the expectation of its square:

var((𝛼 𝐷 ) T 𝑁 𝐷 𝑞 ) = E ( (𝛼 𝐷 ) T 𝑁 𝐷 𝑞 ) 2 = E ( (𝛼 𝐷 ) T 𝑁 𝐷 𝑞 (𝑁 𝐷 𝑞 ) T 𝛼 𝐷 ) = (𝛼 𝐷 ) T E ( 𝑁 𝐷 𝑞 (𝑁 𝐷 𝑞 ) T ) 𝛼 𝐷 = (𝛼 𝐷 ) T Σ𝛼 𝐷 .
Therefore,

SNR PCA = var(((𝛼 𝐷 ) T 𝛼 𝐷 )𝑌 𝑞 (𝑘 ⋆ )) var((𝛼 𝐷 ) T 𝑁 𝐷 𝑞 ) = var( ⃦ ⃦ 𝛼 𝐷 ⃦ ⃦ 2 2 𝑌 𝑞 (𝑘 ⋆ )) (𝛼 𝐷 ) T Σ𝛼 𝐷 = ⃦ ⃦ 𝛼 𝐷 ⃦ ⃦ 4 2 (𝛼 𝐷 ) T Σ𝛼 𝐷 .
Example 3.1. For white noise (Subsec. 3.4.1)

SNR PCA = ( 𝐷 ∑ 𝑑=1 𝛼 2 𝑑 ) 2 𝐷 ∑ 𝑑=1 𝛼 2 𝑑 𝜎 2 𝑑 . ( 3
SNR PCA = 𝐷 ∑ 𝑑=1 𝛼 2 𝑑 𝜎 2 1 1 + 2 𝐷 ∑ 𝑑=1 𝛼 2 𝑑 𝐷-1 ∑ 𝑑=1 𝜌 𝑑 𝐷-𝑑 ∑ 𝑑 ′ =1 𝛼 𝑑 ′ 𝛼 𝑑 ′ +𝑑 . (3.17)
We can now compare the performance of the asymptotic PCA to the optimal dimensionality reduction.

Theorem 3.2. 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 𝛼 𝐷 | Σ 1/2 𝛼 𝐷 ⟩ ) 2 ≤ ⃦ ⃦ ⃦Σ -1/2 𝛼 𝐷 ⃦ ⃦ ⃦ 2 2 • ⃦ ⃦ ⃦Σ 1/2 𝛼 𝐷 ⃦ ⃦ ⃦ 2 2
.

Therefore, SNR PCA = ((𝛼 𝐷 ) T 𝛼 𝐷 ) 2 (𝛼 𝐷 ) T Σ𝛼 𝐷 ≤ (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 = 𝑆𝑁 𝑅.

Corollary 3.4. The asymptotic PCA has the same SNR as the the optimal dimensionality reduction if and only if 𝛼 𝐷 is an eigenvector of Σ. In this case, both dimensionality reductions are equivalent.

Proof. Equality holds in Theorem 3.2 if and only if there exists a nonzero real number 𝜆 such that Σ 1/2 𝛼 𝐷 = 𝜆Σ -1/2 𝛼 𝐷 , i.e., Σ𝛼 𝐷 = 𝜆𝛼 𝐷 , i.e., 𝛼 𝐷 is an eigenvector of Σ.

In this case, the optimal protection is on the vector Σ -1 𝛼 𝐷 = 1 𝜆 𝛼 𝐷 , which is proportional to the projection vector belonging to the asymptotic PCA. In contrast, if 𝜎 1 = • • • = 𝜎 𝐷 = 𝜎, the covariance matrix has only one eigenvalue, namely (1, 1, • • • , 1), which has multiplicity 𝐷. Thus, for white homoscedastic noise, PCA is asymptotically optimal if and only if 𝛼 1 = • • • 𝛼 𝐷 = 𝛼, 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 3.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

𝐷 ∑ 𝑑=1 𝛼 2 𝑑 𝜎 2 𝑑 = 𝐷 ∑ 𝑑=1 𝜎 2 𝑑 𝛼 2 𝑑 𝛼 4 𝑑 ≤ ( 𝐷 max 𝑑=1 𝜎 2 𝑑 𝛼 2 𝑑 ) 𝐷 ∑ 𝑑=1 𝛼 4 𝑑 . Since ( 𝐷 max 𝑑=1 𝜎 2 𝑑 𝛼 2 𝑑 ) -1 = 𝐷 min 𝑑=1 𝛼 2 𝑑 𝜎 2 𝑑 = 𝐷 min 𝑑=1
SNR 𝑑 , the expression of the SNR of the asymptotic PCA given by Eq. 3.16 is such that

SNR PCA = ( 𝐷 ∑ 𝑑=1 𝛼 2 𝑑 ) 2 𝐷 ∑ 𝑑=1 𝛼 2 𝑑 𝜎 2 𝑑 ≥ ( 𝐷 ∑ 𝑑=1 𝛼 2 𝑑 ) 2 𝐷 ∑ 𝑑=1 𝛼 4 𝑑 𝐷 min 𝑑=1 SNR 𝑑 ≥ 𝐷 min 𝑑=1 SNR 𝑑 (3.18)
where we have used Cauchy-Schwarz inequality LDA has been introduced in SCA 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 𝑆 -1 𝑤 𝑆 𝑏 , where:

𝛼 4 𝑑 = 𝐷 ∑ 𝑑=1 𝛼 2 𝑑 𝛼 2 𝑑 ≤ ( 𝐷 ∑ 𝑑=1 𝛼 2
• 𝑆 𝑤 is the within-class scatter matrix, asymptotically equal to Σ, and • 𝑆 𝑏 is the between-class scatter matrix, equal to 𝛼 𝐷 (𝛼 𝐷 ) T .

We have the following spectral characterization of the asymptotic LDA:

Proposition 3.8. Asymptotically, LDA has only one principal direction, namely the vector Σ -1 𝛼 𝐷 .

Proof. The matrix 𝑆 -1 𝑤 𝑆 𝑏 = Σ -1 𝛼 𝐷 (𝛼 𝐷 ) T has rank one. Indeed, 𝛼 𝐷 (𝛼 𝐷 ) T has rank one, and multiplying by an invertible matrix (namely Σ -1 ) keeps the rank unchanged. Since

(Σ -1 𝛼 𝐷 (𝛼 𝐷 ) T )Σ -1 𝛼 𝐷 = Σ -1 𝛼 𝐷 ((𝛼 𝐷 ) T Σ -1 𝛼 𝐷 ) = ( (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 ) × Σ -1 𝛼 𝐷 ,
Σ -1 𝛼 𝐷 is the unique eigenvector with corresponding eigenvalue (𝛼 𝐷 ) T Σ -1 𝛼 𝐷 > 0. This eigenvalue is equal to the SNR of the asymptotic LDA.

By Corollary 3.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 3.3. The asymptotic LDA computes exactly the optimal dimensionality reduction.

Proof. Compare Theorem 3.1 with Proposition 3.8: in both cases, the projection vector is collinear with Σ -1 𝛼 𝐷 .

Numerical Comparison Between Asymptotic PCA and LDA

Numerical comparison between asymptotic PCA and LDA is given in Fig. 3.1(a) and (b), for 𝐷 = 6 samples. The noise is chosen autoregressive, with 𝜎 = 1 and different values

Practical Validations

for 𝜌 (Subsec. 3.4.2). The vector 𝛼 𝐷 is chosen equal to (1, 1, 1, 1, 1, 1) T in Fig. 3.1(a) and to √ 6.0/6.4 • (1.0, 1.1, 1.2, 1.3, 0.9, 0.5) T in Fig. 3.1(b), such that SNR = 6 when 𝜌 = 0. The SNR of the asymptotic LDA is that of the optimal dimensionality reduction (cf. Corollary 3.2), and that of the asymptotic PCA can be found in Example 3.2. The first case (Fig. 3.1(a)) fits the situation depicted in Corollary 3.3. The asymptotic PCA and LDA are almost similar. Besides, when 𝜌 → 1 -, both SNRs tend to 1 (recall Eq. 3.17 and Eq. 3.13). But, when the SNR varies over the 𝐷 samples (Fig. 3.1(b)), the asymptotic LDA can be significantly better than the asymptotic PCA. The samplewise extremal SNRs (SNR 𝑑 = 𝛼 2 𝑑 /𝜎 2 ) are also represented: the SNR of the PCA can be smaller than the largest SNR, namely max 1≤𝑑≤𝐷 SNR 𝑑 , (recall Lemmas 3.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 Eq 3.12).

(a) Equal SNR

𝑑 = 1, 1 ≤ 𝑑 ≤ 𝐷 (b) Varying SNR 𝑑 , 1 ≤ 𝑑 ≤ 𝐷

Practical Validations

In this section, we investigate real traces. Experiments are carried out on the DPA contest V2 [START_REF]DPA Contest[END_REF] traces. One clock cycle lasts 𝐷 = 200 samples. As traces are captured from a hardware implementation of an AES-128 , we consider the Hamming Distance (HD) leakage model (in accordance with most attacks reported on the analyzed device [START_REF] Clavier | Practical improvements of side-channel attacks on AES: feedback from the 2nd DPA contest[END_REF], namely a SASEBO-GII board with a Xilinx XC5VLX30 FPGA [START_REF] Satoh | Side-channel Attack Standard Evaluation Board[END_REF]). In the sequel, we focus on the HD between the byte 0 of the last round and that of the ciphertext.

That is, the function 𝜑 in Eq. 2.1 is a normalized Hamming Weight (HW); precisely,

𝜑 : 𝑧 ∈ F 2 𝑛 ↦ → 2 √ 𝑛 ( HW(𝑧) - 𝑛 2
)

, where 𝑛 = 8, because AES-128 is a byte-oriented block cipher. In addition, we emphasize that our model (Eq. 2.1) is indeed suitable to leakage dimensionality reduction within one clock period.

Attack with a Precharacterization of the Model Parameters 𝛼 𝐷 and Σ

In order to characterize the model, we need to recover the column matrix 𝛼 𝐷 and the 𝐷 × 𝐷 covariance matrix Σ of the noise.

Proposition 3.9. The parameters of the model Eq. 2.1 which minimize the fitting error are given by α𝐷 = 𝑋 𝐷,𝑄 (𝑌 𝑄 ) T 𝑌 𝑄 (𝑌 𝑄 ) T .

Proof. The goal (minimizing the fitting error) is similar to that of the optimal distinguisher, namely maximize the probability of 𝑝 𝑁 𝐷,𝑄 (𝑋 𝐷,𝑄 -𝛼 𝐷 𝑌 𝑄 ) (Eq. 3.3). But in the context of characterization, the correct key is known. Therefore, we wish to minimize in 𝛼 𝐷 and Σ the following objective function:

objective(𝛼 𝐷 , Σ) = 𝑄 ∑ 𝑞=1 { ( 𝑋 𝐷 𝑞 -𝛼 𝐷 𝑦 𝑞 (𝑘 ⋆ ) ) T Σ -1 ( 𝑋 𝐷 𝑞 -𝛼 𝐷 𝑦 𝑞 (𝑘 ⋆ ) ) } , (3.19)
which reminds of Eq. 3.6 (except that now, the key 𝑘 = 𝑘 ⋆ is known). We use the notation (α 𝐷 , Σ) = argmin

(𝛼 𝐷 ,Σ)
objective(𝛼 𝐷 , Σ).

We fix Σ and minimize only on 𝛼 𝐷 . The gradient of objective(𝛼 𝐷 , Σ) w.r.t. (𝛼 𝐷 ) T writes:

𝜕 𝜕(𝛼 𝐷 ) T objective(𝛼 𝐷 , Σ) = 𝑄 ∑ 𝑞=1 -2𝑌 𝑞 (𝑘 ⋆ ) ( Σ -1 𝑋 𝐷 𝑞 -𝑌 𝑞 (𝑘 ⋆ )Σ -1 𝛼 𝐷 ) . (3.20)
The objective function is extremal in α𝐷 if and only if its derivative is equal to zero at this point. Let 𝑌 𝑄 be an abbreviation for 𝑌 𝑄 (𝑘𝑠). This condition takes the form of a where the numerator is the inter-covariance matrix of 𝑋 𝐷,𝑄 and 𝑌 𝑄 , and the denominator is the covariance matrix of 𝑌 𝑄 .

Interestingly, the most likely value α𝐷 of 𝛼 𝐷 does not depend on the noise covariance matrix. As 𝑁 𝐷,𝑄 = 𝑋 𝐷,𝑄 -α𝐷 𝑌 𝑄 has zero mean, the latter can be evaluated on its own as the well-known unbiased estimator of Σ:

Σ = 1 𝑄-1 (𝑋 𝐷,𝑄 -α𝐷 𝑌 𝑄 )(𝑋 𝐷,𝑄 -α𝐷 𝑌 𝑄 ) T . (3.22)
By plugging Eq. 3.21 into Eq. 3.22, one obtains

Σ = 1 𝑄-1 ( 𝑋 𝐷,𝑄 -𝑋 𝐷,𝑄 (𝑌 𝑄 ) T 𝑌 𝑄 𝑌 𝑄 (𝑌 𝑄 ) T ) ( 𝑋 𝐷,𝑄 -𝑋 𝐷,𝑄 (𝑌 𝑄 ) T 𝑌 𝑄 𝑌 𝑄 (𝑌 𝑄 ) T ) T = 1 𝑄-1 𝑋 𝐷,𝑄 ( 𝐼 𝑄,𝑄 - (𝑌 𝑄 ) T 𝑌 𝑄 𝑌 𝑄 (𝑌 𝑄 ) T ) 2 (𝑋 𝐷,𝑄 ) T (3.23) = 1 𝑄-1 𝑋 𝐷,𝑄 ( 𝐼 𝑄,𝑄 - (𝑌 𝑄 ) T 𝑌 𝑄 𝑌 𝑄 (𝑌 𝑄 ) T ) (𝑋 𝐷,𝑄 ) T (3.24) = 1 𝑄-1 ( 𝑋 𝐷,𝑄 (𝑋 𝐷,𝑄 ) T - 𝑋 𝐷,𝑄 (𝑌 𝑄 ) T 𝑌 𝑄 (𝑋 𝐷,𝑄 ) T 𝑌 𝑄 (𝑌 𝑄 ) T ) .
In Eqn. (3.23), 𝐼 𝑄,𝑄 denotes the 𝑄 × 𝑄 identity matrix, and we use in Eq. 3.24 the fact that the matrix 𝐼 𝑄,𝑄 -(𝑌 𝑄 ) T 𝑌 𝑄 /(𝑌 𝑄 (𝑌 𝑄 ) T ) is idempotent, i.e., equal to its square.

Remark 3.3. We have the following remarkable identity:

𝑋 𝐷,𝑄 (𝑋 𝐷,𝑄 ) T = α𝐷 (α 𝐷 ) T 𝑌 𝑄 (𝑌 𝑄 ) T + (𝑄 -1) Σ.
This equation is the non-asymptotic version of Proposition 3.5.

Comment 3.2. This first characterization approach aims at computing the leakage model parameters. Thanks to the least-square estimation method we start by the computation of ̃ 𝛼 𝐷 that is a estimation of 𝛼 𝐷 :

 𝛼 𝐷 = 𝑋𝑌 T (𝑌 𝑌 T ) -1

LESS IS MORE

then we compute ̃ Σ the estimation of Σ regarding to ̃ 𝛼 𝐷 :

 Σ 𝐷 = E [ ( ̃ 𝑁 -E [ ̃ 𝑁 ] ) ( ̃ 𝑁 -E [ ̃ 𝑁 ] ) T ] ,
where ̃ 𝑁 = 𝑋 𝐷,𝑄 -̃ 𝛼 𝐷 𝑌 𝑄T is a matrix that store an estimation of the noise of each traces.

SNR Computations of DPA Contest V2 [73] Traces of an AES Last Round

The values α𝐷 and Σ are represented in Fig. 3.2. We obtain:

• max 𝐷 α2 𝑑 / Σ𝑑,𝑑 = 1.69 • 10 -3 (no dimensionality reduction) • SNR PCA = ((α 𝐷 ) T α𝐷 ) 2 (α 𝐷 ) T Σα 𝐷 = 1.36 • 10 -3 (PCA) • SNR LDA = (α 𝐷 ) T Σα 𝐷 = 12.78 • 10 -3 (LDA)
Therefore, the LDA has the largest SNR: it is about seven times larger than the maximum sample-wise SNR. The PCA has, in this example, an SNR smaller than the maximum univariable SNR (see Lemma 3.1). Interestingly, one can see in Fig. 3.2 that the noise is locally autoregressive, for instance between samples 107 and 117.

Conclusions and Perspectives

Conclusions and Perspectives

Dimensionality reduction is common practice in SCA. This preprocessing 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 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 𝛼 𝐷 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, . . .

Contributions

attacks are known to use a maximum likelihood principle to ensure the highest possible success probability (see, eg., [START_REF] Heuser | Good is not good enough -deriving optimal distinguishers from communication theory[END_REF]).

In this chapter we study optimal attacks with the best possible success probability when extracting the secret key. The success probability in key recovery is chosen as a figure of merit for optimization. Such an objective is typical of "pure" SCA. Other approaches [START_REF] Glowacz | Simpler and more efficient rank estimation for side-channel security assessment[END_REF][START_REF] Mather | Multi-target DPA attacks: Pushing DPA beyond the limits of a desktop computer[END_REF]79] relax the condition that the key found by the SCA be ranked first and complements it with a key enumeration stage. This yields a data vs. complexity trade-off that is not explored in this chapter. We leverage on such optimal distinguishers to answer the following question: "how to attack with the best probability of success when the leakage is multivariate and the model are multiple?" An initial empirical1 work has already been carried out in [START_REF] Sugawara | Profiling attack using multivariate regression analysis[END_REF] which confirmed that this type of approach can be very fruitful. Multi-target attacks [START_REF] Mather | Multi-target DPA attacks: Pushing DPA beyond the limits of a desktop computer[END_REF]80] have a somewhat different goal, namely the best aggregation of information about several subparts of a key, possibly leaking at different times with different models, in order to recover the full key efficiently. Here we consider only one multivariate leakage model and focus on recovering one subpart of the key. However, our derivation is capable of handling multivariate leakages and models and may still be combined with the multi-target approaches.

We derive closed-form expressions for the optimal distinguishers in all situations where the model is known (e.g., using profiling) or regressed online. In the case of a known univariate model, we recover the results in [START_REF] Bruneau | Less is more -dimensionality reduction from a theoretical perspective[END_REF], However, our "fully matrix" formalism makes equations simpler and proofs shorter. Moreover, compared to [START_REF] Bruneau | Less is more -dimensionality reduction from a theoretical perspective[END_REF] we extend the leakage model to the case where the traces are not necessarily centered, thereby allowing a more natural application on real traces. In the realistic "(on-line) stochastic attack" situation where the model is parametric, i.e. where the coefficients of the model are unknown, we express the optimal distinguisher by maximizing success over the whole set of possible coefficients. Finally, we provide fast computation algorithms for our novel distinguishers, which happen to be remarkably simple and efficient.

MULTIVARIATE LEAKAGES AND MULTIPLE MODELS

Theoretical Results and Implementation

General Mathematical Expressions

In this section we derive the mathematical expression of the optimal distinguisher D in the general case of multivariate leakage (𝐷 ≥ 1), and multiple models (𝑆 ≥ 1). An illustration of our results is given in Fig. 4.1 for the case when the leakage is completely known (or profiled as in the TA) and when the leakage is unknown and estimated online.

Is α known?

D M L (x, t) = argmin k tr (x -αy) T Σ -1 (x -αy) yes
Leakage model:

Optimal distinguisher:

x = αy ⋆ + n ∀q, n q ∼ N (0, Σ) y ⋆ = φ(t, k ⋆ ) y = φ(t, k) no α ∈ R D×S , Σ ∈ R D×D x ∈ R D×Q , y ∈ R S×Q D M L,sto (x, t) = argmax k tr y T (yy T ) -1 y x T Σ -1 x

𝑝(𝑋|𝑇 , 𝛼).

In both cases (Theorems 4.1 and 4.2 below) the result is a distinguisher which is computed using simple matrix operations. While D ML resembles a TA with Gaussian templates [START_REF] Chari | Template attacks[END_REF], D ML,sto is a novel expression that results from a non-trivial maximization over the matrix 𝛼 and may be interpreted as a generalization of a multivariate Correlation Power Analysis (CPA) [START_REF] Brier | Correlation power analysis with a leakage model[END_REF].

Theorem 4.1. The optimal Maximum Likelihood (ML) distinguisher [START_REF] Heuser | Good is not good enough -deriving optimal distinguishers from communication theory[END_REF] for Gaussian noise writes

D ML (𝑋, 𝑇 ) = argmin 𝑘 tr ((𝑋 -𝛼𝑌 ) T Σ -1 (𝑋 -𝛼𝑌 )).
(4.1)

Theoretical Results and Implementation

Proof. From [START_REF] Heuser | Good is not good enough -deriving optimal distinguishers from communication theory[END_REF] we have D ML (𝑋, 𝑇 ) = argmax 𝑘 𝑝(𝑋|𝑌 ) while from Eq. 2.3 we see that 𝑝(𝑋|𝑌 ) = 𝑝 𝑁 (𝑋 -𝛼𝑌 ). From the i.i.d. assumption the noise density 𝑝 𝑁 (𝑛) is given by

𝑝 𝑁 (𝑛) = 𝑄 ∏ 𝑞=1 1 √ (2𝜋) 𝐷 | det Σ| exp - 1 2 𝑛 𝑞 T Σ -1 𝑛 𝑞 = 1 (2𝜋) 𝐷𝑄/2 1 (det Σ) 𝑄/2 exp - 1 2 ( 𝑄 ∑ 𝑞=1 𝑛 𝑞 T Σ -1 𝑛 𝑞 ) = 1 (2𝜋) 𝐷𝑄/2 (det Σ) 𝑄/2 exp - 1 2
tr (𝑛 T Σ -1 𝑛).

Thus 𝑝 𝑁 (𝑋 -𝛼𝑌 ) is maximum when the expression tr (𝑛 T Σ -1 𝑛) for 𝑛 = 𝑋 -𝛼𝑌 is minimum.

In Eq. 4.1 of Theorem 4.1, the trace tr

((𝑋 -𝛼𝑌 ) T Σ -1 (𝑋 -𝛼𝑌 ))
consists in:

• the sum of 𝑄 Mahalanobis [START_REF] Chandra | On the Generalised Distance in Statistics[END_REF] distances (see also Eq. ( 22) of [START_REF] Kuhn | Efficient template attacks[END_REF]),

• the sum of 𝐷 elements (which is useful when 𝐷 ≪ 𝑄), as attested by rewriting tr (

(𝑋 -𝛼𝑌 ) T Σ -1 (𝑋 -𝛼𝑌 ) ⏟ ⏞ 𝑄×𝑄 matrix ) = tr ( Σ -1 (𝑋 -𝛼𝑌 )(𝑋 -𝛼𝑌 ) T ⏟ ⏞ 𝐷×𝐷 matrix ) .
Theorem 4.2. The optimal stochastic multivariate attack is given by

D ML,sto (𝑋, 𝑇 ) = argmax 𝑘∈F 2 𝑛 tr (𝑌 T (𝑌 𝑌 T ) -1 𝑌 𝑋 T Σ -1 𝑋) (4.2)
for which the optimal value of 𝛼 is given by

𝛼 opt = (𝑋𝑌 T )(𝑌 𝑌 T ) -1 . (4.3)

MULTIVARIATE LEAKAGES AND MULTIPLE MODELS

For the proof, we need some known results of linear algebra (Lemma Proof. Let 𝑥 be a 𝑆 × 1 column vector. We have that 𝑥 T 𝑏𝑏 T 𝑥 = ‖𝑏 T 𝑥‖ 2 = 0 implies 𝑏 T 𝑥 = 0 hence 𝑥 = 0. Hence the matrix 𝑏𝑏 T is positive definite.

Lemma 4.2. Let 𝑎, 𝑏 and 𝛼 be respectively 1 × 𝑄, 𝑆 × 𝑄 and 1 × 𝑆 with 𝑆 < 𝑄, where 𝑏 has full rank 𝑆. Then ‖𝑎 -𝛼𝑏‖ 2 reaches its minimum for 𝛼 = 𝑎𝑏 T (𝑏𝑏 T ) -1 .

Proof. Expanding the squared norm gives ‖𝑎 -

𝛼𝑏‖ 2 2 = (𝑎 -𝛼𝑏)(𝑎 -𝛼𝑏) T = 𝑎𝑎 T - 2𝛼𝑏𝑎 T + 𝛼𝑏𝑏 T 𝛼 T .
Therefore, the gradient 𝜕 𝜕𝛼 ‖𝑎 -𝛼𝑏‖ 2 2 = -2𝑏𝑎 T + 2𝑏𝑏 T 𝛼 T vanishes if and only if 𝛼 T = (𝑏𝑏 T ) -1 𝑏𝑎 T , i.e., 𝛼 = 𝑎𝑏 T (𝑏𝑏 T ) -1 where we have used the fact that 𝑏𝑏 T is invertible by Lemma 4.1.

Proof of Theorem 4.2. Let 𝑋 ′ = Σ -1/2 𝑋 and 𝑌 ′ = (𝑌 𝑌 T ) -1/2 𝑌 . The optimal distinguisher minimizes the following expression over 𝛼 ∈ R 𝐷×𝑆 :

tr ((𝑋 -𝛼𝑌 ) T Σ -1 (𝑋 -𝛼𝑌 )) = tr ((𝑋 ′ -𝛼 ′ 𝑌 )(𝑋 ′ -𝛼 ′ 𝑌 ) T ) = 𝐷 ∑ 𝑑=1 ‖𝑋 ′ 𝑑 -𝛼 ′ 𝑑 𝑌 ‖ 2 .
By Lemma 4.2 the minimization over 𝛼 ′ 𝑑 yields 𝛼 ′ 𝑑 = (𝑋 ′ 𝑑 𝑌 T )(𝑌 𝑌 T ) -1 for all 𝑑 = 1, . . . , 𝐷. This gives 𝛼 ′ = (𝑋 ′ 𝑌 T )(𝑌 𝑌 T ) -1 hence 𝛼 = (𝑋𝑌 T )(𝑌 𝑌 T ) -1 , which remarkably does not depend on Σ.

Theoretical Results and Implementation

The minimized value of the distinguisher is thus

min 𝛼 tr ((𝑋 -𝛼𝑌 ) T Σ -1 (𝑋 -𝛼𝑌 )) = tr ((𝑋 -𝛼 opt 𝑌 ) T Σ -1 (𝑋 -𝛼 opt 𝑌 )) = tr ((Id -𝑌 T (𝑌 𝑌 T ) -1 ) 2 𝑋 T Σ -1 𝑋) = tr (𝑋 T Σ -1 𝑋) -tr (𝑌 T (𝑌 𝑌 T ) -1 𝑋 T Σ -1 𝑋)
where Id denotes the 𝐷 × 𝐷 identity matrix and where tr (𝑋 T Σ -1 𝑋) is a constant independent of 𝑘. This proves Theorem 4.2.

The expression of D ML,sto (𝑋, 𝑇 ) given in Theorem 4.2 consists in the trace of a 𝑄 × 𝑄 matrix, which can be admittedly very large. It can be, however, rewritten in a way that is easier to compute when 𝑄 is much greater than 𝑆 and 𝐷: Corollary 4.1 (Alternative Expression of D ML,sto ). Letting 𝑋 ′ = Σ -1/2 𝑋, and 𝑌 ′ = (𝑌 𝑌 T ) -1/2 𝑌 as in the proof of Theorem 4.2, we have

D ML,sto (𝑋, 𝑇 ) = argmax 𝑘∈F 2 𝑛 ‖𝑋 ′ 𝑌 ′T ‖ 𝐹 . (4.4)
Here the Frobenius norm is of a 𝐷 × 𝑆 matrix.

Proof. Let us write (𝑌 𝑌 T ) -1 = (𝑌 𝑌 T ) -1/2 (𝑌 𝑌 T ) -1/2 in Eq. 4.2. By the properties of the trace,

tr (𝑌 T (𝑌 𝑌 T ) -1 𝑌 𝑋 T Σ -1 𝑋) = tr ( (𝑌 𝑌 T ) -1 2 𝑌 (Σ -1 2 𝑋) T ⏟ ⏞ 𝑆×𝐷 ( (𝑌 𝑌 T ) -1 2 𝑌 (Σ -1 2 𝑋) T ) T ⏟ ⏞ 𝐷×𝑆 ) = tr ( (𝑌 ′ 𝑋 ′T )(𝑌 ′ 𝑋 ′T ) T ) = ‖𝑋 ′ 𝑌 ′T ‖ 𝐹 2 .
Remark 4.1. Notice that in Corollary 4.1, 𝑌 ′ is a vector of empirical covariance equal to the identity matrix. Indeed, 𝑌 ′ 𝑌 ′T = (𝑌 𝑌 T ) -1/2 𝑌 𝑌 T (𝑌 𝑌 T ) -1/2 = Id.

Mathematical Expressions for 𝑆 = 2

In order to provide interpretations for the optimal distinguisher expressions, we detail how an optimal attack unfolds when the leakage consists in a sum of a modulated scalar model and an offset (𝑆 = 2). The cases for profiled attacks (denoted D 𝑆=2 ML ) and non-profiled attacks (denoted D 𝑆=2 ML,sto ) are presented in Fig. 4.2.

Interestingly, when 𝑆 = 2, the TA can decompose in two steps (affine projection followed by a Euclidean distance to the model). Remarkably, the projection vector is the same for all key guesses. This extends similar results [START_REF] Bruneau | Less is more -dimensionality reduction from a theoretical perspective[END_REF] where only the linear relationship between leakage and model is explored. As for the online attack, D 𝑆=2 ML,sto consists in a sum of square of CPA on transformed data, aiming at orthogonalizing the noise.

α, β ∈ R D×1 , Σ ∈ R D×D x ∈ R D×Q , y ∈ R 1×Q x = αy ⋆ + β1 + n ∀q, n q ∼ N (0, Σ) y ⋆ = φ(t, k ⋆ ) y = φ(t, k)

Affine projection:

Data transformation:

Leakage model: yes no known? Are α, β

Univariate ML attack:

New multivariate CPA attack:

x = α T Σ -1 α T Σ -1 α (x -β1) ∈ R 1×Q x ′ = Σ -1/2 x D S=2 ML (x, t) = argmin k ||x -y|| 2 2 D S=2 ML,sto (x, t) = argmax k D d=1 Cov(x ′ d ,y) 2 Var(y)

Efficient Implementation

Both D ML and D ML,sto can be optimized using the idea presented in [START_REF] Lomné | Behind the scene of side channel attacks[END_REF]. This article applies a precomputation step in the case the number of traces is larger than the number of possible plaintexts (𝑄 > #𝑇 = 2 𝑛 ). In this case, all summations ∑ 𝑞 can be advantageously replaced by

∑ 𝑇 ∑ 𝑇 𝑞 =𝑡
. In most cases, the sum ∑ 𝑇 𝑞 =𝑡 can be achieved on the fly, and does not involve an hypothesis on the key. Therefore, a speed gain of 2 𝑛 (the cardinality of the key space) is expected.

Such optimization strategy can be applied to D ML . Indeed, let us define 𝑋 ′ = Σ -1/2 𝑋 and 𝛼 ′ = Σ -1/2 𝛼. Then,

D ML (𝑋, 𝑇 ) = argmin 𝑘 𝐷 ∑ 𝑑=1 ‖𝑋 ′ 𝑑 -𝛼 ′ 𝑑 𝑌 ‖ 2 2 (see Corollary 4.1) = argmin 𝑘 𝐷 ∑ 𝑑=1 ∑ 𝑇 ∈F 2 𝑛 ⎛ ⎝ ∑ 𝑞/𝑇 𝑞 =𝑡 𝑋 ′ 𝑑,𝑞 2 -2 ∑ 𝑞/𝑇 𝑞 =𝑡 𝑋 ′ 𝑑,𝑞 𝛼 ′ 𝑑 𝑌 (𝑡, 𝑘) + ( ∑ 𝑞/𝑇 𝑞 =𝑡 1)(𝛼 ′ 𝑑 𝑌 (𝑡, 𝑘)) 2 ⎞ ⎠ = argmin 𝑘 𝐷 ∑ 𝑑=1 ∑ 𝑇 ∈F 2 𝑛 -2 ( ∑ 𝑞/𝑇 𝑞 =𝑡 𝑋 ′ 𝑑,𝑞 ) ⏟ ⏞ denoted as 𝑋 ′ 𝑑,𝑡 𝛼 ′ 𝑑 𝑌 (𝑡, 𝑘) + ( ∑ 𝑞/𝑇 𝑞 =𝑡 1 ) ⏟ ⏞ denoted as 𝑛 𝑇 (𝛼 ′ 𝑑 𝑌 (𝑡, 𝑘)) 2 (4.5) = argmax 𝑘 tr (𝑋 ′ ( 𝛼 ′ 𝑌 (𝑘) ) T ) - 1 2 ∑ 𝑇 ∈F 2 𝑛 𝑛 𝑇 ⃦ ⃦ 𝛼 ′ 𝑌 (𝑇 , 𝑘) ⃦ ⃦ 2 2 . ( 4
4 return argmax 𝑘∈K tr (𝑋 ′ ( 𝛼 ′ 𝑌 (𝑘) ) T ) - 1 2 ∑ 𝑡 𝑛 𝑡 ⃦ ⃦ 𝛼 ′ 𝑌 (𝑡, 𝑘) ⃦ ⃦ 2 2
This means that 𝑋 ′ can be obtained by simple accumulation, exactly as in line 2 of Alg. 4.1. The term 𝑌 ′ 𝑠 (𝑡, 𝑘) requires the computation of 𝑌 𝑌 T . In the case 𝑄 ≫ 1, it can be assumed that the texts 𝑇 are uniformly distributed. Hence, when 𝑄 → +∞, by the law of large numbers,

1 𝑄 𝑌 𝑌 T = 1 𝑄 𝑄 ∑ 𝑞=1 𝑌 𝑞 𝑌 𝑞 T = ∑ 𝑡∈F 2 𝑛 ∑ 𝑞/𝑇 𝑞 =𝑡 1 𝑄 𝑌 (𝑡, 𝑘)𝑌 (𝑡, 𝑘) T -----→ 𝑄→+∞ 1 2 𝑛 ∑ 𝑡∈F 2 𝑛 𝑌 (𝑡, 𝑘)𝑌 (𝑡, 𝑘) T .
Therefore, in (4.7), 𝑌 ′ 𝑠 (𝑡) can also be precomputed. To the best of our knowledge, this optimization has never been discussed previously. The resulting distinguishing procedure is given in Alg. 4.2. At line 3, the argument of the Frobenius norm can be computed by a fast matrix multiplication. Also, we notice that the matrix inversion at line 0 is actually a precomputation which involves only the model. Besides, if the EIS (Equal Images under all Sub-keys) assumption holds [67, Def. 2], e.g., 𝑌 (𝑡, 𝑘) only depends on 𝑡⊕𝑘, then ∑ 𝑡 𝑌 (𝑡, 𝑘)𝑌 (𝑡, 𝑘) T does not depend on 𝑘, hence only one single matrix inversion to compute. Eventually, the computational complexity of the optimal stochastic attack simply consists in traces accumulation per class, and as many matrix products and Frobenius norms as keys to be guessed.

Practical Results

Characterization of Σ

In this chapter, we assume that the attacker knows the noise covariance matrix. We give a straightforward procedure for the estimation.

1. collect 𝑄 traces (i.e., a matrix 𝑋 ∈ R 𝐷×𝑄 ) where the plaintext is fixed to a given value,

2. estimate Σ as Σ = 1 𝑄 -1 ( 𝑋 - 1 𝑄 𝑋1 T 1 ) ( 𝑋 - 1 𝑄 𝑋1 T 1 ) T , where 1 = (1, . . . , 1) ∈ R 1×𝑄
. This estimator is sample covariance matrix, which is unbiased.

Remark 4.2. Notice that Σ cannot be obtained by a direct profiling on the same traces to be used for the attack. Indeed, in those traces, the plaintext is varying, hence the attacker would use for Σ the covariance matrix of 𝑋 -𝛼 opt 𝑌 , where 𝛼 opt is equal to

𝛼 opt = (𝑋𝑌 T )(𝑌 𝑌 T ) -1 (recall Eq. 4.3). Hence, Σ = 1 𝑄 -1 (𝑋 -𝛼 opt 𝑌 )(𝑋 -𝛼 opt 𝑌 ) T .

MULTIVARIATE LEAKAGES AND MULTIPLE MODELS

But the distinguisher D ML,sto is

D ML,sto (𝑋, 𝑇 ) = argmin 𝑘∈F 2 𝑛 min 𝛼∈R 𝐷×𝑆 tr ((𝑋 -𝛼𝑌 ) T Σ-1 (𝑋 -𝛼𝑌 )) = argmin 𝑘∈F 2 𝑛 min 𝛼∈R 𝐷×𝑆 tr ( Σ-1 (𝑋 -𝛼𝑌 )(𝑋 -𝛼𝑌 ) T ) = argmin 𝑘∈F 2 𝑛 tr ( Σ-1 (𝑋 -𝛼 opt 𝑌 )(𝑋 -𝛼 opt 𝑌 ) T ) (4.8) = argmin 𝑘∈F 2 𝑛 tr ((𝑄 -1) Σ-1 Σ) = argmin 𝑘∈F 2 𝑛 𝐷(𝑄 -1). (4.9)
Indeed, at line 4.8, we demonstrated in the proof of Theorem 4.2 in that the minimal value in Eq. 4.3 of 𝛼 is independent on Σ. Eventually, it can be seen at line 4.9 that the distinguisher with Σ instead of Σ does not depend on the key. Indeed, argmin

𝑘 cst = F 2 𝑛 ,
meaning that all keys are equiprobable. Intuitively, when both the noise and the model parameters are regressed at the same time, any key manages to achieve the same match between parametric model and Side-Channel (SC) observations.

Attacks on Synthetic (i.e., Simulated) Traces

In this subsection we present simulations when 𝛼 is known exactly or regressed online.

We consider an attack of PRESENT, where the S-box is 𝑛 = 4 → 𝑛 = 4. For the sake of the simulations, we choose two kinds of 𝛼:

• "identical": all the 𝑛 = 4 bits leak the same waveform, like in the Hamming Weight (HW) model, • "proportional": the waveform has weight 1 for S-box bit 0, and is multiplied by 2 (resp. 3 and 4) for S-box bit 1 (resp. 2 and 3).

The waveform for each bit is that represented in Fig. 2.5 (upper left graph). Specifically, for all 1 ≤ 𝑑 ≤ 𝐷 and 1 ≤ 𝑠 ≤ 𝑆, the envelope consists in damped oscillations:

𝛼 𝑑,𝑠 = 𝑒 -2𝑑 𝐷 cos ( 2𝜋 𝑑 𝐷
) for the "identical" case, (4.10)

𝛼 𝑑,𝑠 = 𝑠 • 𝑒 -2𝑑 𝐷 cos ( 2𝜋 𝑑 𝐷
) for the "proportional" case. (4.11)

The noise is chosen normal, using two distributions:

Practical Results

• "isotropic": the covariance matrix is 𝜎 2 times the 𝐷 × 𝐷 identity,

• "autoregressive": the covariance matrix element at position (𝑑, 𝑑 ′ ), for 1 ≤ 𝑑, 𝑑 ′ ≤ 𝐷, is 𝜎 2 𝜌 |𝑑-𝑑 ′ | . This noise is not independent from sample to its neighbours, but the correlation 𝜌 decreases exponentially as samples get further apart.

Proposition 4.1. The success probability of D ML is greater than that of D ML,sto .

Proof. Indeed, according to [START_REF] Heuser | Good is not good enough -deriving optimal distinguishers from communication theory[END_REF], D ML maximizes the success probability. Thus, the distinguisher D ML,sto has a smaller success probability. The success probability is the same if the minimization over 𝛼 in the proof of Theorem 4.2 yields the exact matrix 𝛼 used in the model provided in Eq. 2.3.

Simulations allow to estimate the loss in terms of efficiency of not knowing the model (Proposition 4.1), by comparing distinguishers D ML (Eq. 4.1) and D ML,sto (Eq. 4.2). The success rate of the optimal distinguisher D ML is drawn in order to materialize the limit between feasible (below) and unfeasible (above) attacks.

Results for low noise (𝜎 = 1) are represented in Fig. 4.3. We can see that the HW model is clearly harder to attack, because the leakage of one bit cannot be distinguished from that of the other bits. Besides, we notice that the stochastic attack is performing much worse than the optimal attack: about 10 times more traces are required for an equivalent success probability in key extraction. Results for high noise (𝜎 = 4) are represented in Fig. 4.4. Again, the "proportional" model is easier to attack than the "identical" model (for each bit). Now, we also see that the gap between the optimal ML attack and the stochastic attack narrows: only about 5 times more traces are needed for the stochastic attack to perform as well as the optimal attack in terms of success probability. Besides, we notice that the autoregressive noise is favorable to the attacker. It is therefore important in practice for the attacker to characterize precisely the noise distribution (recall the methodology presented in Subsec. 4.3.1).

Clearly, these conclusions are in line with the "template versus stochastic" (offline) study carried out in [START_REF] Gierlichs | Templates vs. stochastic methods[END_REF]: for high noise, the (online) learning of the model requires more traces, hence is more accurate. Therefore, the performance of D ML,sto gets closer to that of D ML than for high noise. Simulations When 𝛼 is Estimated Offline.

Furthermore, we used simulated traces to evaluate the influence of the number of traces in the learning set for 𝛼 (when it is profiled offline) over the success rate of our attacks.

The result of this process is illustrated in Fig. 4.5, for a similar case study (Advanced Encryption Standard (AES) S-box is used instead of PRESENT). This study has been done with proportional and identical 𝛼, and isotropic and autoregressive noise. In the case of 𝑆 = 2 the success rate is always higher than in the case of 𝑆 = 9. In addition, for each size of learning set, the mean of the Mean Square Error (MSE) has been computed. The MSE for 𝑆 = 2 converges more quickly to the value of the noise variance than for 𝑆 = 9, which accounts for the fact that when 𝑆 increases, more traces are required for the profiling of the model.

MULTIVARIATE LEAKAGES AND MULTIPLE MODELS

𝛼 identical and Σ isotropic 𝛼 identical and Σ autoregressive 𝛼 proportional and Σ isotropic 𝛼 proportional and Σ autoregressive

Attacks on Real-World Traces

We now compare CPA with D ML and D ML,sto on measurements provided by the DPA contest V4 [START_REF]DPA Contest[END_REF] . These traces have been acquired from an 8-bit processor, hence have a Signal-to-Noise Ratio (SNR) greater than one, reaching 7 at some points in time. The interval for our case-study is [170, 250] from Fig. 2.6, hence 𝐷 = 80. Regarding ML, two learning strategies have been implemented:

1. the model is learned from a disjoint set of 5k traces, which is the operational scenario for a profiled attack;

2. the model is learned from the traces being attacked (denoted self in Fig. 4.6). This case does not represent a realistic attack, but is interesting in that it highlights the best possible attacker.

The attack success rates are plotted in Fig. 4.6. One can see that both variants of D ML and D ML,sto achieve better with 𝑆 = 9 than with 𝑆 = 2. This is consistent with the analysis carried out in Subsec. 2.2.2. Actually, the CPA has a very poor performance because the model is actually very far from the HW: as can be seen in Fig. 2.6, some parameters 𝛼 𝑖 (e.g., for 𝑖 = 2 and 6) are positive in region [180, 200] whereas others 𝛼 𝑗 (e.g., for 𝑗 = 1, 3, 4 and 5) are negative. The compensating signs account why the HW model is inappropriate. The ML with model precharacterization on the traces under attack show that very strong attacks are possible (using a few traces only). Interestingly, when the model used by ML is characterized on 5k traces distinct from the traces being attacked, the performance is almost similar. Eventually, the online stochastic attack derived in this chapter (D ML,sto ) performs better than CPA (the distinguisher being the maximum value of the Pearson correlation over the 𝐷 = 80 samples).

Conclusions and Perspectives

Conclusions and Perspectives

Distinguishing a key from both multivariate leakage samples and multiple models can be done in one step as shown in this chapter. A compact expression of the distin-

MULTIVARIATE LEAKAGES AND MULTIPLE MODELS

guisher is provided, using matrix operations. The strategy is applied to real-world traces in profiled and non-profiled scenarios. The resulting attack is more efficient than the traditional approach "dimensionality reduction then stochastic (linear regression) attack)". The new multivariate distinguisher outperforms the other state-of-the-art attacks. The presented methodology allows for leakage agnostic attacks on vectorial leakage measurements and complex models. In addition, the matrix-based expression of the distinguisher benefits from matrix-oriented software that implements computational optimizations for large dimensions.

A companion future work would consist in determining the optimal model dimensionality and basis from any acquisition campaign. Another perspective is to adapt the methodology to masked implementations, as already done for univariate leakage in [START_REF] Dabosville | A new second-order side channel attack based on linear regression[END_REF], yet for this case the distinguishers will certainly not exhibit simple closed-form expressions. However, we believe that the approach could be fruitful in practice backed with suitable optimization software.

CHAPTER 5

Binary Data Analysis for Source Code Leakage Assessment We have just tackled in the previous Chap. 4 the problem of optimal distinguisher in the context of multivariate leakage and models. In the present Chap. 5 we propose an analysis of multivariate leakage and model on 3-dimensional "software traces" provided by debugger tool.

Introduction

Previous Work

Measuring ElectroMagnetic (EM) or power traces from embedded devices to identify potential leakage of information is a time consuming and challenging process. First,

BINARY DATA ANALYSIS FOR SOURCE CODE LEAKAGE ASSESSMENT

it requires equipment (oscilloscope, probes, signal amplifiers. . . ) that demand prior knowledge to the technician. Secondly, the code to evaluate needs to be embedded on the final product or on an evaluation board, it means that the development has to be finished at the evaluation time. This justifies the interest of the security evaluation community for simulation, both in the industrial and academic world. Aiming to speed-up, facilitate the evaluation, and allowing an evaluation during the development, several works have proposed Side-Channel (SC) trace simulators. The principle is to simulate the leakage that might happen during the code execution. Numerous simulators are available to simulate SC (power or EM) leakage. All present a similar general construction flow illustrated in Fig. 5.1. First, they take a description of the implementation to evaluate as input. For example, the inputs of SILK [78] are tagged C++ source codes. More often, inputs are architecture dependant compiled binaries: Elmo [START_REF] Mccann | ELMO: emulating leaks for the ARM cortex-m0 without access to a side channel lab[END_REF] uses binaries for the ARM Cortex-M0 and OSCAR [START_REF] Thuillet | A smart card power analysis simulator[END_REF] uses binaries for the 8-bit Atmel AVR microcontroller. The Dynamic Binary Analyzer (DBA) framework [START_REF] Allibert | Chicken or the egg -computational data attacks or physical attacks[END_REF] supports more architectures: ARM, x86, MIPS, SPARC and SH4. In the simulation step, the SC-simulators execute the code to record data. For example Elmo [START_REF] Mccann | ELMO: emulating leaks for the ARM cortex-m0 without access to a side channel lab[END_REF] uses the emulator Thumbulator1 , while in [START_REF] Bos | Differential computation analysis: Hiding your white-box designs is not enough[END_REF] the authors use the Valgrind debugger. The choice of the data provider is influenced by the fact that the simulator is specific to an architecture. Another important choice of the simulation step is the selection of the data to record. The authors of [START_REF] Bos | Differential computation analysis: Hiding your white-box designs is not enough[END_REF] proposed to record the memory accesses. The DBA framework [START_REF] Allibert | Chicken or the egg -computational data attacks or physical attacks[END_REF] records the stack, the heap, the CPU-registers and the executed instructions. Elmo [START_REF] Mccann | ELMO: emulating leaks for the ARM cortex-m0 without access to a side channel lab[END_REF] is focused on the values of the operands, the bit-flips of the operations and the operations. The last step is the trace generation, or how to transform the recorded data to obtained traces as similar as possible to real and effective physical leakage. Elmo [START_REF] Mccann | ELMO: emulating leaks for the ARM cortex-m0 without access to a side channel lab[END_REF] provides one of the most realistic and complex model computed with linear regressions (also used in [START_REF] Debande | Profiled Model Based Power Simulator for Side Channel Evaluation[END_REF]) and F-test on real leakage traces recorded on a ARM Cortex-M0. Otherwise, the most commonly used models are the Hamming Weight (HW) and the Hamming Distance (HD), which are simplifications of effective physical leakage as introduced in the Subsec. 2.2.3. Those models have been preferred by the authors of [START_REF] Allibert | Chicken or the egg -computational data attacks or physical attacks[END_REF][START_REF] Thuillet | A smart card power analysis simulator[END_REF].

Introduction

Inputs: C, C++, VHDL, compiled code. . .

Simulation

Additional inputs: target descriptions, emulator, data to record. . .

Traces generation

Additional inputs: leakage models, leakage functions. . .

Outputs: traces

Contributions

In this context, we propose a new methodology of data collection and analysis to identify potential leakages from any software implementation. Our solution takes inspiration from the work proposed by Bos et al. in [START_REF] Bos | Differential computation analysis: Hiding your white-box designs is not enough[END_REF] . An improvement of the analysis step has been proposed in [START_REF] Ahn | Multilateral white-box cryptanalysis: Case study on WB-AES of CHES challenge 2016[END_REF], realizing on three intermediate computations instead of one initially. We investigate the proposed improvement in the Subsec. 5.3.2. As a first difference, we propose a new methodology of data collection. We record all bitmodifications that happen during a code execution (registers, memory content, flags, Program Counter (PC)), while in [START_REF] Bos | Differential computation analysis: Hiding your white-box designs is not enough[END_REF], authors record only the read, written and executed addresses. Furthermore, we do not apply any model to the recorded data in order to generate traces. All the collected data is exhaustively analyzed to avoid information loss. To do so, we introduce a binary analysis to extract the leaking points from the data. Then, we leverage on PC to keep track of the execution context to map the identified leakage to the source code. Indeed, mapping leakages to source code is nowadays an important need for continuous improvement of products; this is particularly true for software implementations, where traces are long and code is complex. To succeed, we need to overcome two main difficulties: misalignment and multiplicity of leaking resources. We show how to characterize and then exploit the PC to realign all the data using a simple accumulative algorithm, and we introduce a methodology of data selection that significantly reduce the size of the data to analyze. Finally, we show how our solution can identify leakage in the source code applying our methodology to White Box Cryptography (WBC) implementation.

Solution Presentation

Notations and Recording Step

Aiming to record all the data manipulated by a given binary, the debugger GNU Debugger (GDB) is used, but alternative software could be used to collect data. The analysis that we propose is independent of the data provider. To identify all potential leakages, the recording process is as exhaustive as possible. Each time the PC changes, all the internal data are saved (PC, registers, flags. . . ). For example, in the case of an x86 architecture in 64-bit execution (properties of the system used for all the results given in the current paper), the internal data are:

• the sixteen 64-bit registers: rax, rbx, rcx, rdx, rsi, rdi, rbp, rsp, r8, r9, r10, r11, r12, r13, r14, r15, • the six 16-bit registers: cs, ss, ds, es, fs, gs, • the 64-bit eflags (with the bit 1, 5, 15, 22-63 reserved).

• the PC (Program Counter, also named rip for register instruction pointer) As in the previous chapters, the matrix notations are used. The recorded data of an execution is stored in a matrix noted 𝑋 𝐷,𝑅 ∈ (F 2 ) 𝐷,𝑅 , with 𝐷 the number of times the PC changes and 𝑅 the number of bit needed to store all the internal data (except the PC that is stored independently, and used in resynchronization process deepened in Subsec. 5.2.2). For a given dataset 𝑋 𝐷,𝑅 , the associated list of successive PC-values is stored in a matrix Pc 𝐷 ∈ (Z) 𝐷 . An illustration of a recorded trace is provided in Fig. 5.2, the black color corresponds to one and the white to zero, the x-axis describes the internal data and the y-axis the index of the PC. The illustrated trace follows from the execution of the WBC algorithm freely provided at the Capture The Flag (CTF) of CHES-20161 . The illustration of the recorded trace provided in Fig. 5.2 shows that only a little part of the registers seems to be used during the execution. This observation inspired us the each secret bytes (256 if no values are forbidden). For example, if the target algorithm is the AES-128 , and if the focused sensitive intermediate value is the output of the S-box at the first round, the distribution for a bit-level model is expressed as in the following Formula 5.1:

𝑌 𝑆,𝑄,𝐾,𝐵 = { (S-box(𝑇 𝑞,𝑏 ⊕𝑘) & 2 𝑠 ) >> 𝑠 } 𝑠<8,𝑘<256 𝑞<𝑄,𝑏<16 (5.1)
The choice of the bit-level model is motivated by the bit representation of the recorded data 𝑋 𝐷,𝑅 ∈ (F 2 ) 𝐷,𝑅 . To lighten the notations, the dimension 𝐵 is not always precised.

Realignment Algorithm

The first problematic met in the proposed study is the misalignment of the data. Indeed, misalignment could be due to the randomization of the execution, or more generally, by the presence of conditional branches. A vertical alignment is a prerequisite point to realize vertical analysis. Most of the vertical analysis techniques, as Correlation Power Analysis (CPA) [START_REF] Brier | Correlation power analysis with a leakage model[END_REF] or Linear Regression Analysis (LRA) [START_REF] Doget | Univariate side channel attacks and leakage modeling[END_REF] need the data 𝑋 𝑅,𝑄 𝑑 manipulated at the sample 𝑑 < 𝐷 to come from the same operation. The resynchronization is a well known and a well studied problem in the SCA domain [START_REF] Debande | re-synchronization by moments": An efficient solution to align side-channel traces[END_REF][START_REF] Guilley | Formal framework for the evaluation of waveform resynchronization algorithms[END_REF][START_REF] Thiebeauld | Scatter : A new dimension in side-channel[END_REF][START_REF] Jasper | Improving differential power analysis by elastic alignment[END_REF]. All the proposed algorithms of resynchronization are based on the leaking values distribution in the temporal or in the frequency domain. In our case we have access to additional information thanks to the PC values. In fact, the PC values can be viewed as an identifier. For example ∀𝑞 < 𝑄, ∀𝑑 𝑞 < 𝐷 𝑞 , Pc 𝑑𝑞,𝑞 is an identifier for the data 𝑋 𝑅 𝑑𝑞,𝑞 . Furthermore, if for 𝑑 0 < 𝐷 0 , 𝑑 1 < 𝐷 1 , Pc 𝑑 0 ,0 = Pc 𝑑 1 ,1 it means that the two datasets 𝑋 𝑅 𝑑 0 ,0 and 𝑋 𝑅 𝑑 1 ,1 are the result of the same operation in the code (at the assembly level). However the presence of a loop in the source code could imply repetitions of PC value. Hence evince, if the two datasets 𝑋 𝑅 𝑑 0 ,0 , 𝑋 𝑅 𝑑 1 ,1 result form the same operation they may come from distinct iterations. Moreover, conditional branching in the code produce misalignment. The goal of the proposed realignment algorithm is to transform the raw dataset {𝑋 𝐷𝑞,𝑅 𝑞 , Pc 𝐷𝑞 𝑞 } 𝑞<𝑄 into the dataset {𝑋 𝐷,𝑅,𝑄 , Pc 𝐷 } where ∀ 𝑑 < 𝐷, ∀ 𝑞 0 < 𝑄, ∀𝑞 1 < 𝑄, 𝑋 𝑅 𝑑,𝑞 0 and 𝑋 𝑅 𝑑,𝑞 1 result in the same operation, at the same iteration. The main constraints are the execution time and memory required. We proposed here a single-pass realignment algorithm detailed in Schedule 5.1. The fact that we only need the PC values to resynchronize the data significantly reduces the computational time and the needed memory. Indeed, our algorithm of resynchronization only have to read one time the 𝐷 𝑞 𝑞<𝑄 64-bit PC values

Solution Presentation

instead of the {𝑋 𝐷𝑞,𝑅 } 𝑞<𝑄 bit of data in the case of an algorithm based on the entire dataset. To provide details on the last assumption of the Eq. 5.2, the two Def. 5.1 are needed. The whole algorithm described in the Schedule 5.1 reveals the fix-points and the pseudo fix-points that are automatically realigned.

Definition 5.1. Fix-point and pseudo fix-point

A fix-point is a PC value with a deterministic presence and a deterministic number of occurrence:

Pc 𝑑 ∈ {Pc 𝐷𝑞 𝑞 } 𝑞<𝑄 is a fix-point ⇐⇒ ∃ 𝑚 ∈ N, 𝐷𝑞 ∑ 𝑑𝑞=1 ⎧ ⎪ ⎨ ⎪ ⎩ 1 if Pc 𝑑𝑞,𝑞 = Pc 𝑑 0 otherwise = 𝑚 ∀𝑞 < 𝑄.
• • A pseudo fix-point is a PC value with a deterministic number of appearance, in the case it appears (so a fix-point is also a pseudo fix-point):

Pc 𝑑 ∈ {Pc 𝐷𝑞 𝑞 } 𝑞<𝑄 is a pseudo fix-point ⇐⇒ ∃ 𝑚 ∈ N, 𝐷𝑞 ∑ 𝑑𝑞=1 ⎧ ⎪ ⎨ ⎪ ⎩ 1 if Pc 𝑑𝑞,𝑞 = Pc 𝑑 0 otherwise ∈ {0, 𝑚} ∀𝑞 < 𝑄.
To illustrate the proposed realignment algorithm, we first start with an application to a simple example. The Fig. 5.3 displays a control flow graph with a conditional branching, a loop and a conditional branching inside. The letters A, B, C, . . . , I are the PC values. The probability associated to each conditional branching are 𝑝 0 and 𝑝 1 . The presented results have been obtained with 𝑝 0 = 1/2 and 𝑝 1 = 1/3. Three distinct executions of the proposed flow graph gave the following PC successions:

{Pc 𝐷𝑞 }𝑞<3 = ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩
Pc 𝐷 0 = 𝐴, 𝐵, 𝐷, 𝐸, 𝐻, 𝐼, 𝐸, 𝐻, 𝐼, 𝐸, 𝐹, 𝐺, 𝐼 Pc 𝐷 1 = 𝐴, 𝐵, 𝐷, 𝐸, 𝐹, 𝐺, 𝐼, 𝐸, 𝐻, 𝐼, 𝐸, 𝐹, 𝐺, 𝐼 Pc 𝐷 2 = 𝐴, 𝐶, 𝐷, 𝐸, 𝐻, 𝐼, 𝐸, 𝐻, 𝐼, 𝐸, 𝐹, 𝐺, 𝐼

(5.2)
The application of the proposed realignment algorithm, described in the Schedule 5.1, to a thousand executions of the flow graph detailed in Fig. 5.3, gives the matrix #Pc 𝐷 ′ ,𝑄 displayed in Fig. 5.4.

get the set of all possible PC values:

Pc 𝐷 ′ = 𝑄-1 ⋃ 𝑞=0 Pc 𝐷𝑞 𝑞
, with 𝐷 ′ the number of distinct values of PC over 𝑄 2. accumulate in the matrix #Pc 𝐷 ′ ,𝑄 the numbers of times each PC appears in each trace:

#Pc 𝐷 ′ ,𝑄 = [ #Pc 𝑑,𝑞 = 𝐷𝑞-1 ∑ 𝑑𝑞=0 ⎧ ⎪ ⎨ ⎪ ⎩ 1, if Pc 𝑑𝑞,𝑞 = Pc 𝑑 0, otherwise ] 𝑑<𝐷 ′ 𝑞<𝑄
3. the fix-points and the pseudo fix-points are stored in F 𝐷 with its associated number of appearance: of PC used for the alignment is created using F 𝐷 ′′ ,2 : The realignment algorithm designates A, D, E and I as fix-points; B, C as pseudo fix-points while the PC F, G and H could not be realigned in the preliminary study. Those PC need more information to be realigned. Finally, the realignment algorithm gives the following output:

F 𝐷 ′′ ,2 = {(
Pc 𝐷 = { F 0,1 𝑡𝑖𝑚𝑒𝑠 ⏞ ⏟ F 0,0 , . . . , F 0,0 , . . . , F 𝐷 ′′ -1,1 𝑡𝑖𝑚𝑒𝑠 ⏞ ⏟ F 𝐷 ′′ -1,0 , . . . , F 𝐷 ′′ -1,0 } = { 𝑚 0 𝑡𝑖𝑚𝑒𝑠 ⏞ ⏟ Pc 0 , . . . , Pc 0 , . . . , 𝑚 𝐷 ′′ -1 𝑡𝑖𝑚𝑒𝑠 ⏞ ⏟ Pc 𝐷 ′′ -1 , . . . , Pc 𝐷 ′′ -1 } Schedule 5.
F 𝐷 ′′ = {(𝐴, 1), (𝐵, 1), (𝐶, 1), (𝐷, 1), (𝐸, 3), (𝐼, 3)} Pc 𝐷 = {𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐸, 𝐸, 𝐼, 𝐼, 𝐼} If we go back to the three execution traces given in the Eq. 5.2, the resynchronization is done as written in Eq. 5.3, with in red the elements affected by the realignment. (5.

{𝑋 𝐷,𝑅 𝑞 } 𝑞<3 = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 𝑋 𝐷,𝑅 0 = {𝑋 𝑅 0,0 , 𝑋 𝑅 0,1 , 0, 𝑋 𝑅 0,2
3)

The algorithm of realignment have been applied to a real-world masked implementation of an AES-128 , the results obtained are displayed in Fig. 5.6. It reveals that some PC, around the index 100 seem to be neither fix-points nor pseudo fix-points. This aspect is confirmed by the results of the computation of the mean and the standard deviation for the non-zero elements of #Pc 𝐷 ′ ,𝑄 over 𝑄 displayed in Fig. 5.6. In fact, this three figures show that two PC values have non-constant number of apparition in all the executions. In addition to give the PC that causes the misalignment and the resynchronized axis of PC, the algorithm helps to find the lines in the source code that provoke the misalignment. This matching from the PC values to the source lines code is made easier by the usage of GDB to record the leakage. Furthermore, the localization of the misalignment origins helps to identify timing leakage. In our example illustrated in Fig. 5.6, the realignment reveals that the misalignment is caused by the function xtime transcribed in Fig. 5.5a. This function multiplies the input 𝑏 by two in F 2 8 , but this implementation contains conditional statement that misalign the data and that could produce time leakage. A possible improvement can be the usage of the constant time implementation of xtime provided in Fig. 5.5b. Our realignment algorithm immediately and precisely identify the non-constant time line in the source code. This information is very useful for a developer that want to implement constant time algorithm aim to protect his code against the timing attacks.

Data Reduction

Once the recorded data are realigned, if necessary, we have now access to the resynchronized data 𝑋 𝐷,𝑅,𝑄 and the associated PC vector Pc 𝐷 . Now that it is possible to analyze vertically the data, two questions arise. Are all the data in 𝑋 𝐷,𝑅,𝑄 relevant? And is it 5. BINARY DATA ANALYSIS FOR SOURCE CODE LEAKAGE ASSESSMENT Definition 5.3. The transition matrix 𝑇 𝐷,𝑅 of a given set 𝑋 𝐷,𝑅,𝑄 is defined as follow:

𝑇 𝐷,𝑅 = [ 𝑇 𝑑,𝑟 = ⎧ ⎪ ⎨ ⎪ ⎩ 1, if 𝑑 = 0 ∨ 𝑄 𝑞=1 𝑋 𝑑-1,𝑟 ⊕𝑋 𝑑,𝑟 otherwise ]

𝑑<𝐷, 𝑟<𝑅

The transition matrix identifies the points ((𝑑, 𝑟) ∈ 𝐷 × 𝑅) that change at least one time between the PC 𝑑 and 𝑑 + 1 over all the traces. Both matrix 𝑇 𝐷,𝑅 and 𝐴 𝐷,𝑄 could be computed in-line accumulating each trace. Then, we identify the points that could leak information as 𝐿 = {(𝑑, 𝑟) ∈ (𝐷 × 𝑅)|𝑇 𝑑,𝑟 ∧ 𝐴 𝑑,𝑟 = 1}. In Fig. 5.7, the matrices 𝐴 𝐷,𝑅 , 𝑇 𝐷,𝑅 and 𝐴 𝐷,𝑅 ∧ 𝑇 𝐷,𝑅 obtain analyzing a data set of 250 traces of execution of an AES-128 WBC implementation. We observe that our algorithm permits to identify the 0.29% from the entire samples that could leak information. Thus we conserve only 20190 PC values over 28277 and 120 bit register over 1472. This data reduction speeds up the analysis and reduce the memory footprint analyzing only the data 𝑋 𝐿,𝑄 . Furthermore we take advantage of the very low density of the sparse matrices {𝑋 𝐷,𝑅 𝑞 } 𝑞<𝑄 to reduce the storage required for the traces. The storage of sparse matrices is a well study problematic in computer science and a lot of solutions are freely provided. The following Tab. 5.1 summarizes the gain in storage that we obtain using a method called Compressed Sparse Column matrix (CSC) present in scipy1 . Thus, the needed memory to store the traces 𝑋 𝐷,𝑅,𝑄 decrease from 9, 7Go to 132Mo using the CSC compression on the matrix 𝑇 𝐷,𝑅,𝑄 defined in Eq. 5.4.

Distinguisher: CPA

The potential leakage points have been identified and stored in the dataset 𝑋 𝐿,𝑄 . To know if some of those points leak sensitive information, we use the CPA proposed by Brier et al. in 2004 [11]. In our case, the guessed intermediate values are stored in 𝑌 𝑆,𝑄,𝐾,𝐵 as explained in the Eq. 5. , where 𝜎 is the variance and cov the covariance both over 𝑄.

(5.5)

Then we identify the leaking samples using the Absolute distinguishing Margin (AbsMarg) proposed by Whitnall et al. in [81] and recalled in the following Eq. 5.6. The usage of the AbsMarg metric is motivated by the presence of ghost peaks in the results of CPA.

We take advantage that we analyze binary dataset to simplify the accumulative formula of the Pearson coefficient given in Eq. 5.7. This simplification speeds up the analysis and reduces the memory footprint.

D(𝑋

Results

In the following analyses, we use the known-plaintext attack model, which means that an attacker only requires access to the random inputs. Additionally, the attack could be performed with just the compiled binary. The source code access is only mandatory to map the leakages to the source code.

WBC Analysis

As explain in the previous Subsec. 5.2.4 we choose the CPA to reveal leakage from 𝑋 𝐿,𝑄 and discriminate the secret key {𝑘 ⋆ 𝑏 } 𝑏<16 from the guesses {𝑘 𝑏 |𝑘 𝑏 ̸ = 𝑘 ⋆ 𝑏 } 𝑏<16 . The Fig. 5.8 illustrates the results obtained by applying the CPA on 𝑄 = 250 recorded traces from the WBC implementation provided at the CTF challenge of CHES-2016. The leakage model focuses the 8bit of the output of the S-box at the first, the corresponding 𝑌 is provided in Formula 5.1. The CPA has been computed for all samples 𝐿 (∼ 120k) but to facilitate the visualization we focus on the first 20k samples where the leaking ones are localized. In grey we display the results obtained with the bad guesses: { max

𝑘 𝑏 <256,̸ =𝑘 ⋆ 𝑏 (D(𝑋 𝐿,𝑄 , 𝑌 𝑄 𝑠,𝑘 𝑏 ,𝑏 )) } 𝑏<16,𝑠<8
and in color the result obtained with the right key:

{ D(𝑋 𝐿,𝑄 , 𝑌 𝑄 𝑠,𝑘 ⋆ 𝑏 ,𝑏 ) } 𝑏<16,𝑠<8
. We observed a lot of colored peaks in the Fig. 5.8

but if we compare with the AbsMarg results displayed in Fig 5 .9 only a small part of them really leak sensitive information. We apply a threshold at 0.25 to AbsMarg results to get the leaking samples.

Then, we take advantage of the PC values to map the identified leaking samples to the source code. We summarize the obtained results in the Tab 5.2. In this way, we accurately link each identified leak to a line code, a bit register and a leaking bit model.

Analysis Improvement

As proposed in [START_REF] Ahn | Multilateral white-box cryptanalysis: Case study on WB-AES of CHES challenge 2016[END_REF], we extend our leakage model 𝑌 provided in Formula 5.1, to take into account the two products computed during the mixColumn execution. In [START_REF] Ahn | Multilateral white-box cryptanalysis: Case study on WB-AES of CHES challenge 2016[END_REF] authors proposed to compute three distinct 8-bit Differential Power Analysis (DPA) while the two products only add ten new bit-distributions to the initial model. Indeed the model extension makes growing the model size 𝑆 from 8 to 18, and not to 24, because 6 bit-distributions are redundant as resumed in the following Proposition 5.1. • the bit 2 of 2.𝑥 is equal to the bit 1 of x • the bit 5 of 2.𝑥 is equal to the bit 4 of x • the bit 6 of 2.𝑥 is equal to the bit 5 of x • the bit 7 of 2.𝑥 is equal to the bit 6 of x • the bit 0 of 2.𝑥 is equal to the bit 7 of x

BINARY DATA ANALYSIS FOR SOURCE CODE LEAKAGE ASSESSMENT

• the bit 0 of 3.𝑥 is equal to the bit 1 of 2.𝑥 100

Results

The Proposition 5.1 permits to construct an extended model expressed in the following formula 5.8. . The discrimination of the leaking samples from the computed CPA uses the AbsMarg displayed in Fig 5 .11, in which we apply a threshold at 0.25. Then, using the PC values we map the identified leaking samples to the source code. We summarize the obtained results in the Tab 5.3 in which we link each leakage to a line code, a bit register and a leaking bit model. First, the extended model lead us to recover the entire secret key {𝑘 ⋆ 𝑏 } 𝑏<16 of the WBC implementation. Second the mapping of the leakage shows the diversity of the registers that could leak information: rcx, rax, rbp, rdi, r8 r9, r10, r11, r13 r14, r15; which justify the necessity to protect all the register of an hardware target. Finally, comparing both Tabs 5.2 and 5.3 notify that a major part of the leakage results from the computing of the multiplication by three computed during the mixColumn execution.

𝑌 𝑆,𝑄,𝐾,𝐵 = [ ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ S-box (𝑇 𝑞,𝑏 ⊕𝑘) & 2 𝑠 , if 𝑠 < 8 (2.S-box (𝑇 𝑞,𝑏 ⊕𝑘)) & 2 𝑣[𝑠-8] , if 7 < 𝑠 < 11, with 𝑣 = {1, 3, 4} (3.

BINARY DATA ANALYSIS FOR SOURCE CODE LEAKAGE ASSESSMENT

Conclusion

We present in this paper a new methodology of SC evaluation for software implementation. We push the state of the art in that field by providing a practical and effective methodology to extract all the data that will be manipulated by a software implementation during its execution. All the recorded data are analyzed independently, at bit level, without any leakage model applied to generate traces as in all the SC simulators presented in the state of the art (as far as we know). These features give to our solution exhaustive properties and suppress the noise that a leakage model could generate. Our exhaustive approach makes it agnostic for the target hardware by focusing the analysis on the manipulated data and not on hardware characteristics. Furthermore, our methodology allows to map leakage of sensitive information to the source code, and this can be of significant help for an evaluator or a developer. Advantageously, we provide two additional new methods to support and improve the SCA assessment. First, we describe an efficient resynchronization algorithm based on the control flow values. Second, we give a methodology to significantly decrease the number of samples to analyze. Both features are crucial when analyzing complex and/or massive software implementations. Furthermore, our solution could be plugged in others data providers than GDB. As example, we applied our methodology to data provided by the Virtulyzr [START_REF] Danger | Analyzing security breaches of countermeasures throughout the refinement process in hardware design flow[END_REF] to analyze hardware implementations. In the case, the PC are replaced by time values and the registers by wires.

CHAPTER 6

Conclusion and Perspectives

Conclusion

Since the explosion of the market connected devices, security became a major preoccupation across domains: military, civil, medical. . . Every day new threats and security breaches are revealed. The Side-Channel (SC) domain is not spared, even more with the blast of the Internet of Thing (IoT). This thesis is in line with this growing need of security increasing the understanding of the leakage. Indeed, understanding the nature of the leakage, in terms of model complexity and leaking samples, is vital to construct countermeasures relevantly.

First, we provide close forms of optimal distinguisher in the context of multivariate leakage and multivariate models. These results are recalled in the two following Fig. 6.1 and 6.2. All the formula gathered there permit to maximize the probability of success in many cases. Thus we provide the optimal distinguishers close forms for distinct profiles of attacker:

• the perfect attacker: the model (𝛼, Σ) is perfectly known, • the intermediate attacker: the model has been computed in a learning set,

Perspectives

from the execution of a software implementation. Additionally, we efficiently solve the two vital problems of resynchronization and of denoising. This end-to-end process starts with a source code implementation and finishes with a mapping leakage to the source code. The relation between the source code and the leakage is a powerful information. Thus, a software developer can quickly identify and understand the leakage that arises from his code.

Perspectives

Linking an optimal analysis of physical leakage resulting from the executing of a software code and a software analysis with GDB of the same implementation should be an interesting perspective. The results that we would get should improve the understanding on the nature of the leakage. Another perspective should be a comparison between the optimal distinguishers we invented [START_REF] Bruneau | Less is more -dimensionality reduction from a theoretical perspective[END_REF][START_REF] Bruneau | Optimal side-channel attacks for multivariate leakages and multiple models[END_REF] and the new distinguishers based on neural network or machine learning [START_REF] Cagli | Convolutional neural networks with data augmentation against jitter-based countermeasures -profiling attacks without pre-processing[END_REF][START_REF] Maghrebi | Breaking cryptographic implementations using deep learning techniques[END_REF]. Improving the data collection should be an inspiring perspective for the software analysis. GDB allows accurate gathering of data. However, GDB is slow, in that it provides a huge amount of features we do not need for our application case. Alternative methods for instance leveraging ptrace (internally used by GDB) can be both faster and easier portable, albeit at the cost of a reduced number of features. Speeding up the data collection will give us the opportunity to analyze bigger codes, not only cryptographic algorithms but complete protocols. Another improvement of the proposed methodology of software analysis should be the application of the optimal distinguishers to the collected data. Furthermore taking advantage of the binary aspect of the multidimensional dataset 𝑋 𝐷,R,𝑄 and the multidimensional model (𝑌 𝑆,𝑄 ) could lead to an improvement of distinguishing step. In fact, as for the Correlation Power Analysis (CPA) (Formula 5.7), the binary format can help to simplify the formula. Lastly, the usage of a "bitmap-format implementation"1 could speed-up the computation and decrease the memory footprint distributions discrimination. Another axis of study is to find an efficient method to exhaustively combine leaking samples to reveal potential high order leakage over our huge binary dataset. Finally, as discussed during the reviewing process, investigations and improvements have to be found to enable the analysis of codes that embed polymorphic countermeasure [START_REF] Couroussé | All paths lead to rome: Polymorphic runtime code generation for embedded systems[END_REF]. At present, our algorithm of resynchronization is beaten by polymorphic codes. A way to analyze such ABSTRACT : Since the publication in 1999 of the seminal paper of Paul C. Kocher, Joshua Jaffe and Benjamin Jun, entitled "Differential Power Analysis", the side-channel attacks have been proved to be efficient ways to attack cryptographic algorithms. Indeed, it has been revealed that the usage of information extracted from the side-channels such as the execution time, the power consumption or the electromagnetic emanations could be used to recover secret keys.

In this context, we propose first, to treat the problem of dimensionality reduction. Indeed, since twenty years, the complexity and the size of the data extracted from the side-channels do not stop to grow. That is why the reduction of these data decreases the time and increases the efficiency of these attacks. The dimension reduction is proposed for complex leakage models and any dimension. Second, a software leakage assessment methodology is proposed ; it is based on the analysis of all the manipulated data during the execution of the software. The proposed methodology provides features that speed-up and increase the efficiency of the analysis, especially in the case of white box cryptography. KEY-WORDS : Side-channel attacks, dimensionality reduction, leakage models, white box cryptography, AES.

4. 3 1 1 . 1 14 1. 2 18 1. 3 20 1. 4 21 1. 1

 3111142183204211 Simulations for 𝐷 = 3, 𝑆 = 5, 𝑛 = 4, 𝜎 = 1 (autoregressive noise with 𝜌 = 0.5). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.4 Simulations for 𝐷 = 3, 𝑆 = 5, 𝑛 = 4, 𝜎 = 4 (autoregressive noise with 𝜌 = 0.5). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.5 Influence of the number of traces in the learning set over the success rate 80 4.6 Success rate of CPA, D ML,sto , and D ML for 𝑆 ∈ {9, 2} . . . . . . . . . . 81 List of Tables 2.1 Key size recommendations from national agencies, academic and industrial groups. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Benchmark of the needed memory to store the traces 𝑋 𝐷,𝑅,𝑄 . . . . . . 5.2 Leakage characterization and mapping to the source code for 𝑆 = 8. . . 5.3 Leakage characterization and mapping to the source code for 𝑆 = 18. . . CHAPTER Résumé de la Thèse en Français Contents Chapitre 1 : Introduction . . . . . . . . . . . . . . . . . . . . Chapitre 2 : Moins C'est Plus . . . . . . . . . . . . . . . . . . Chapitre 3 : Fuites Multivariées et Modèles Multiples . . . Chapitre 4 : Analyse Binaire pour l'Évaluation des Fuites d'un Code Source . . . . . . . . . . . . . . . . . . . . . . . . . Chapitre 1 : Introduction

Figure 1 . 1 : 9 Figure 1 . 2 :

 11912 Figure 1.1: Exemple de modèle de fuite avec 𝑆 = 2, 𝑌 est le poids de Hamming de valeur de 4-bits et un bruit nul.

1. 1

 1 Chapitre 1 : Introduction ainsi que la la nature du bruit 𝑁 ont fait l'objet d'investigations poussées dans les différents chapitres.

1. 2 2 . 1 . 1 .Proposition 1 . 2 . 1 -(( 1 +

 22111211 Chapitre 2 : Moins C'est Plus dans les propositions 1.1 et 1.Proposition Pour le bruit blanc, la réduction de dimension optimale prend la forme suivante : Pour le bruit autorégressif, la réduction de dimension optimale prend la forme suivante :𝜌𝛼 2 )𝑋 𝑞,1 + 𝐷-1 ∑ 𝑑=2 𝜌 2 )𝛼 𝑑 -𝜌(𝛼 𝑑-1 + 𝛼 𝑑+1 ))𝑋 𝑑,𝑞+ (𝛼 𝐷 -𝜌𝛼 𝐷-1 )𝑋 𝐷 𝑞

Théorème 1 . 2 .Figure 1 . 3 :

 1213 Figure 1.3: Éstimation de α𝐷 (gauche) et de Σ𝐷,𝐷 (droite), avec 𝑄 = 10, 000 traces, illustrant un bruit autorégressif.

Figure 1 . 4 :

 14 Figure 1.4: Expressions mathématiques des distingueurs optimaux pour des fuites multivariées (𝐷 ≥ 1) et des modèles multiples (𝑆 ≥ 1).

1. 4 Figure 1 . 5 :

 415 Figure 1.5: Comparaison du taux de succès de l'analyse par corrélation (Correlation Power Analysis (CPA) en anglais), du D ML,sto , et du D ML avec 𝑆 ∈ {9, 2}

1. 4 Figure 1 . 6 :

 416 Figure 1.6: Exemple de trace logiciel de l'exécution d'un algorithme cryptographique en boîte blanche

1. 4 Figure 1 . 7 :

 417 Figure 1.7: Illustration des matrices 𝐴 𝐷,𝑅 (en haut),𝑇 𝐷,𝑅 (au milieu) et 𝐴 𝐷,𝑅 ∧ 𝑇 𝐷,𝑅 (en bas). Les 0 sont représentés en blanc, les 1 en noir.

Fig. 2 Figure 2 . 1 :

 221 Figure 2.1: ShiftRows' effect on the internal state of an AES 2 .

Fig 2 . 2 .

 22 For examples, 𝑜 0 = 0x02.𝑖 0 + 0x03.𝑖 1 + 𝑖 2 + 𝑖 3 , the operation are done in F 2 8 .

Figure 2 . 4 :

 24 Figure 2.4: Example of a modulated trace 𝑋 𝐷 𝑞

Figure 2 . 5 :

 25 Figure 2.5: Example of leakage model with 𝑆 = 2, 𝑌 is the HW of 4-bits values and no noise is added

Figure 2 . 6 :

 26 Figure 2.6: Leakage evaluation of traces from the DPA contest V4 [74] (knowing the mask)

.

  2.7 we summarized the obtained re-sults. In grey we display the best correlation scores obtained with the bad guesses: { max 𝑘 𝑏 <256,𝑘 𝑏 ̸ =𝑘 ⋆ 𝑏 (D(𝑋 𝐷,𝑄 , 𝑌 𝑄 𝑘 𝑏 ,𝑏 )) } 𝑏<16 and in red the result obtained with the right key: { D(𝑋 𝐷,𝑄 , 𝑌 𝑄 𝑘 ⋆ 𝑏 ,𝑏 ) } 𝑏<16 The presented results have been obtained with only one hundred traces (𝑄 = 100) and focusing the first two thousand samples (𝐷 = 2000). The x-axis represents the time samples (𝐷) and the y-axis the absolute value of the Pearson correlation coefficients.

Figure 2 . 7 :

 27 Figure 2.7: Results of the CPA for the first CTF Challenge.

Figure 2 . 8 :

 28 Figure 2.8: Ranks (over 256) of the right key in function of the number of traces used by the CPA for the first CTF challenge.

Figure 2 . 9 :

 29 Figure 2.9: Masking scheme of the Plebe1 implementation.

Figure 2 . 10 :

 210 Figure 2.10: Side-Channel (SC) identification of the mixColumns computations.

Contents 3 . 1

 31 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Review of the State-of-the-Art. . . . . . . . . . . . . . . . . . 3.3 Theoretical Solution in the Presence of Gaussian Noise . . 3.4 Noise Distributions . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Comparison with PCA and LDA . . . . . . . . . . . . . . . . 3.6 Practical Validations . . . . . . . . . . . . . . . . . . . . . . . 3.7 Conclusions and Perspectives . . . . . . . . . . . . . . . . . .

Corollary 3 . 3 .

 33 For equal weights 𝛼 1 = • • • = 𝛼 𝐷 = 𝛼, i.e., when initial SNR 1 = • • • = SNR 𝐷 = SNR are the same, one has  SNR = SNR × 𝐷(1 -𝜌) + 2𝜌 1 + 𝜌 . (3.13) Proof. Proposition 3.4 reduces to

Remark 3 . 2 .

 32 Assume white noise (Subsec 3.4.1) where all values 𝜎 2 𝑑 (1 ≤ 𝑑 ≤ 𝐷) are different. Then, by Corollary 3.4, the asymptotic PCA is optimal only if 𝛼 𝐷 = (0, 0, • • • , 0, 1, 0, • • • , 0), which we may consider unrealistic since only one sample out of 𝐷 would leak secret information.

𝑑 ) 2 . 2 𝑑. Take 𝐷 = 2 ,𝛼 1 = 3 .

 22213 Conversely, we can give an example for which SNR PCA < 𝛼 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. 59 LESS IS MORE 3.5.2 Linear Discriminant Analysis (LDA)

Figure 3 . 1 :

 31 Figure 3.1: Comparison of the SNR of asymptotic LDA (optimal) and of asymptotic PCA

=

  𝑋 𝐷,𝑄 (𝑌 𝑄 ) T 𝑌 𝑄 (𝑌 𝑄 ) T .(3.21)

Figure 3 . 2 :

 32 Figure 3.2: Estimated α𝐷 (left) and Σ𝐷,𝐷 (right), with 𝑄 = 10, 000 traces, for locally autoregressive noise.

Figure 4 . 1 : 1 ) 4 . 1 ( 2 𝑛

 411412 Figure 4.1: Mathematical expression for multivariate (𝐷 ≥ 1) optimal attacks with a linear combination of models (𝑆 ≥ 1) Definition 4.1 (Optimal Distinguisher Knowing or Ignoring 𝛼).

Figure 4 . 2 :

 42 Figure 4.2: Modus operandi for multivariate (𝐷 ≥ 1) optimal attacks with one model 𝑌 associated to envelope 𝛼 ∈ R 𝐷×1 and a constant offset 𝛽 ∈ R 𝐷×1 (𝑆 = 2)

4 .

 4 MULTIVARIATE LEAKAGES AND MULTIPLE MODELS 𝛼 identical and Σ isotropic 𝛼 identical and Σ autoregressive 𝛼 proportional and Σ isotropic 𝛼 proportional and Σ autoregressive

Figure 4 . 3 :

 43 Figure 4.3: Simulations for 𝐷 = 3, 𝑆 = 5, 𝑛 = 4, 𝜎 = 1 (autoregressive noise with 𝜌 = 0.5).

  𝛼 identical and Σ isotropic 𝛼 identical and Σ autoregressive 𝛼 proportional and Σ isotropic 𝛼 proportional and Σ autoregressive

Figure 4 . 4 :

 44 Figure 4.4: Simulations for 𝐷 = 3, 𝑆 = 5, 𝑛 = 4, 𝜎 = 4 (autoregressive noise with 𝜌 = 0.5).

Figure 4 . 5 :

 45 Figure 4.5: Influence of the number of traces in the learning set over the success rate and the corresponding MSE, for 𝐷 = 3, 𝑆 = 5, 𝑛 = 4, 𝜎 = 16, and an autoregressive noise with 𝜌 = 0.5.

Figure 4 . 6 :

 46 Figure 4.6: Success rate of CPA, D ML,sto , and D ML for 𝑆 ∈ {9, 2} (with two distinct learning methods)

Contents 5 . 1

 51 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.2 Solution Presentation . . . . . . . . . . . . . . . . . . . . . . . 86 5.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

Figure 5 . 1 :

 51 Figure 5.1: General flow commonly used by SC simulators.

  Pc 𝑑 , 𝑚 𝑑 ) ∈ (Pc 𝐷 ′ , N)|∃ 𝑚 ∈ N, #Pc 𝑑,𝑞 ∈ {0, 𝑚}, ∀ 𝑞 < 𝑄, } 4. finally the axis Pc

1 :

 1 Step-by-step description of the realignment algorithm.

Figure 5 . 3 :

 53 Figure 5.3: Control flow of the example.

Figure 5 . 4 :

 54 Figure 5.4: #Pc 𝐷 ′ ,𝑄 for 𝑄 = 1000 executions of the example described in Fig. 5.3, with 𝐷 ′ = 8 and Pc 𝐷 ′ = {𝐴, 𝐵, 𝐶, 𝐷, . . . , 𝐼}. The colors refer to the number of time each PC appear in each execution.

Figure 5 . 8 :

 58 Figure 5.8: CPA, for 𝑆 = 8, on recorded data from a WBC implementation.

Figure 5 . 9 :

 59 Figure 5.9: AbsMarg of the CPA for 𝑆 = 8. Only the samples with a positive 𝐴𝑏𝑠𝑀 𝑎𝑟𝑔 are plotted.

(5. 8 )

 8 As in the previous Subsec. 5.3.1, Fig. 5.10 illustrates the results obtained by applying the CPA on 𝑄 = 250 recorded traces.In grey we display the results obtained with the bad guesses: { max 𝑘 𝑏 <256,𝑘 𝑏 ̸ =𝑘 ⋆ 𝑏 (D(𝑋 𝐿,𝑄 , 𝑌 𝑄 𝑠,𝑘 𝑏 ,𝑏 )) } 𝑏<16,𝑠<18 and in color the result obtained with the right key: { D(𝑋 𝐿,𝑄 , 𝑌 𝑄 𝑠,𝑘 ⋆ 𝑏 ,𝑏 ) } 𝑏<16,𝑠<18

Figure 5 . 10 :

 510 Figure 5.10: CPA, for 𝑆 = 18, on recorded data from a WBC implementation.

Figure 5 . 11 :

 511 Figure 5.11: AbsMarg of the CPA for 𝑆 = 18. Only the samples with a positive AbsMarg are plotted.

  Multidimensionality of the Models and the Data in the Side-Channel Domain Damien Marion RÉSUMÉ : Depuis la publication en 1999 du papier fondateur de Paul C. Kocher, Joshua Jaffe et Benjamin Jun, intitulé "Differential Power Analysis", les attaques par canaux auxiliaires se sont révélées être un moyen d'attaque performant contre les algorithmes cryptographiques. En effet, il s'est avéré que l'utilisation d'information extraite de canaux auxiliaires comme le temps d'exécution, la consommation de courant ou les émanations électromagnétiques, pouvait être utilisée pour retrouver des clés secrètes. C'est dans ce contexte que cette thèse propose, dans un premier temps, de traiter le problème de la réduction de dimension. En effet, en vingt ans, la complexité ainsi que la taille des données extraites des canaux auxiliaires n'a cessé de croître. C'est pourquoi la réduction de dimension de ces données permet de réduire le temps et d'augmenter l'efficacité des attaques. Les méthodes de réduction de dimension proposées le sont pour des modèles de fuites complexe et de dimension quelconques. Dans un second temps, une méthode d'évaluation d'algorithmes logiciels est proposée. Celle-ci repose sur l'analyse de l'ensemble des données manipulées lors de l'exécution du logiciel évalué. La méthode proposée est composée de plusieurs fonctionnalités permettant d'accélérer et d'augmenter l'efficacité de l'analyse, notamment dans le contexte d'évaluation d'implémentation de cryptographie en boîte blanche. MOTS-CLEFS : Attaques par canaux auxiliaires, réduction de dimension, modèles de fuites, cryptographie en boîte blanche, AES.

  Deux cas distincts sont abordés. Le premier, lorsque le modèle (𝛼) est connu. Celui-ci peut-être obtenu lors d'une première étape d'apprentissage. Le distingueur est dans ce cas noté D ML . Le second, lorsque le 20 1.4 Chapitre 4 : Analyse Binaire pour l'Évaluation des Fuites d'un Code Source modèle est inconnu, il est alors estimé directement lors de l'attaque, il sera alors noté D ML,sto .

  Prior Knowledge 128, 192 or 256 bits, according to the wanted level of security, and is used to generate the 11, 13 or 15 rounds keys. Indeed, the AES falls in the Substitution-Permutation Network (SPN) algorithms with 10, 12 or 14 rounds as a function of the key size. Each round is divided in four subfunctions:

Introduction

Contents 2.1 Prior Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3 Distinguishers . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.4 Examples of Side-Channel Analysis (SCA) . . . . . . . . . . 35 2.5 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.6 The Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.1 Prior Knowledge

2.1.1 Advanced Encryption Standard (AES)

The Advanced Encryption Standard (AES) is a symmetric cryptographic algorithm, initially called Rijindael, submitted to the National Institute of Standards and Technology (NIST) competition in 1998 and ratified as a standard in 2001

[START_REF]Specification for the Advanced Encryption Standard (AES)[END_REF]

. The algorithm is a block cipher that digests input blocks of 128 bits. The internal state is also made up of 128 bits, where the numbering is visible in Fig.

2

.1. The input master key is sized 2.1

  MixColumns' effect on the internal state of an AES 2 . The product in F 2 8 is symbolized here by a bold dot '.'.

		𝑖 0	𝑖 4	𝑖 8	𝑖 12		𝑜 0	𝑜 4	𝑜 8	𝑜 12
	.	𝑖 1 𝑖 2	𝑖 5 𝑖 6	𝑖 9 𝑖 10	𝑖 13 𝑖 14	=	𝑜 1 𝑜 2	𝑜 5 𝑜 6	𝑜 9 𝑜 10	𝑜 13 𝑜 14
		𝑖 3	𝑖 7	𝑖 11	𝑖 15		𝑜 3	𝑜 7	𝑜 11	𝑜 15
	Figure 2.2:

Table 2 . 1 :

 21 Key size recommendations from national agencies, academic and industrial groups 3 .

	Method	Date	Sym.	Factoring	Discrete Logarithm	Elliptic	Hash
				Modulus			Curve
					Key	Group
	Lenstra/Verheul[48]	2018	84	1771 (1376)	149	1771	158	168
	Lenstra Updated[47]	2018	80	1329 (1478)	160	1329	160	160
	ECRYPT II[31]	2016/20	96	1776	192	1776	192	192
	NIST[6]	2016/30	112	2048	224	2048	224	224
	ANSSI[4]	2014/20	100	2048	200	2048	200	200
	IAD-NSA[56]	-	256	3072	-	-	384	384
	BSI [16]	2017/22	128	2000	250	2000	250	256

  1 , 𝑌 2 , . . . , 𝑌 𝑄 are assumed i.i.d. (denoted by 𝑌 ). Under the adopted leakage model it follows that the leakage measurements 𝑋 1 , 𝑋 2 , . . . , 𝑋 𝑄 are also i.i.d. (denoted by 𝑋).

  𝐷 -2(𝐷 -1)𝜌 + O(𝜌 2 ). The SNR gain is equal to the dimension 𝐷 at first order, which is consistent with Proposition 3.2. In addition, that gain is never Therefore, when SNR 1 = . . . = SNR 𝐷 , nonzero values of correlation 𝜌 decrease the efficiency of dimensionality reduction, the most favorable situation being the case of white noise samples.

							3.5 Comparison with PCA and LDA
	dimension 𝐷 = 1, but becomes strictly greater than 1 for larger dimensions, since
	𝐷 -𝜌(𝐷 -2) 1 + 𝜌	>	𝐷 -(𝐷 -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
	𝐷 -𝜌(𝐷 -2) 1 + 𝜌 = greater than 𝐷, since	𝐷(1 -𝜌) + 2𝜌 1 + 𝜌	≤	𝐷(1 -𝜌) + 2𝐷𝜌 1 + 𝜌	= 𝐷.

  𝑞 𝑀 𝑑 ′ ,𝑞 -→ cov(𝑀 𝑑,𝑞 , 𝑀 𝑑 ′ ,𝑞 ) almost surely, where the covariance term can be computed as: cov(𝑀 𝑑,𝑞 , 𝑀 𝑑 ′ ,𝑞 ) = cov(𝛼 𝑑 𝑌 𝑞 + 𝑁 𝑑,𝑞 , 𝛼 𝑑 ′ 𝑌 𝑞 + 𝑁 𝑑 ′ ,𝑞 ). When expanding this expression, cross terms disappear by independence of 𝑌 𝑄 and 𝑁 𝐷,𝑄 . There remains: cov(𝑀 𝑑,𝑞 , 𝑀 𝑑 ′ ,𝑞 ) = 𝛼 𝑑 𝛼 𝑑 ′ + Σ 𝑑,𝑑 ′

	3. LESS IS MORE
	Proof. By the law of large numbers,
	1 𝑄	𝑄 ∑ 𝑞=1	𝑀 𝑑,
			.15)

  Let 𝑏 an 𝑆 ×𝑄 matrix, with 𝑆 < 𝑄. The 𝑆 ×𝑆 matrix 𝑏𝑏 T is invertible if and only if 𝑏 has full rank 𝑆, i.e., if and only if the 𝑆 lines of 𝑏 are independent.

	4.1) and linear
	regression (Lemma 4.2).
	Lemma 4.1.

  The same optimization applies to D ML,sto . Indeed, in expression (4.4) of D ML,sto (𝑋, 𝑇 ) = argmax Initialize to zero a matrix 𝑋 ′ of size 𝐷 × 2 𝑛 // Initialize to zero a vector 𝑛 𝑡 of length 2 𝑛

	4. MULTIVARIATE LEAKAGES AND MULTIPLE MODELS
	Algorithm 4.1: Fast computation algorithm for D ML
	input : 𝑋, 𝑇
	output: D ML (𝑋, 𝑇 )
	// 1 for 𝑞 ∈ {1, . . . , 𝑄} do 2 𝑋 ′ 𝑇 𝑞 + Σ -1/2 𝑋 𝑞 𝑇 𝑞 ← 𝑋 ′ 3 𝑛 𝑇 𝑞 ← 𝑛 𝑇 𝑞 + 1		// On-the-fly accumulation
	// Single evaluation, as in (4.6)
						.6)
	Notice that at line Eq. 4.5, the term	∑	𝑋 ′ 𝑑,𝑞	2 which does not depend on the key, is
			𝑞/𝑇 𝑞 =𝑡
	simplified. The fast version of this computation is given in Alg. 4.1.
	𝑘	‖𝑋 ′ 𝑌 ′T ‖ 2 𝐹 , one can write
		𝐹 = ‖𝑋 ′ 𝑌 ′T ‖ 2 = ∑ 𝑠,𝑑 ( ∑ 𝑡∈F 2 𝑛	∑ 𝑠,𝑑 ( ∑ ( 𝑄 ∑ 𝑞=1 𝑞/𝑇 𝑞 =𝑡 𝑋 ′ 𝑋 ′ 𝑑,𝑞 𝑌 ′ 𝑠,𝑞 𝑑,𝑡 ) ⏟ 𝑑,𝑡 denoted as 𝑋 ′ denoted as 𝑌 ′ ) 2 𝑠,𝑡 ⏞ ( 𝑌 ′ ⏟ ⏞ 𝑠 (𝑡, 𝑘) )	) 2	.	(4.7)

  Fast computation algorithm for D ML,sto when 𝑇 is balanced input : 𝑋, 𝑇 output: D ML,sto (𝑋, 𝑇 )0 // Precompute #K = 2 𝑛 matrices 𝑌 ′ (𝑇 , 𝑘) of size 𝑆 × 2 𝑛 , s.t. 𝑘)𝑌 (𝑡, 𝑘) T ) -1/2 𝑌 (𝑇 , 𝑘).// Initialize to zero a matrix 𝑋 ′ 𝑑,𝑡 of size 𝐷 × 2 𝑛 1 for 𝑞 ∈ {1, . . . , 𝑄} do

		4.3 Practical Results
	Algorithm 4.2: 𝑌 ′ (𝑇 , 𝑘) = ( 1 2 𝑛 𝑌 (𝑡, 2 ∑ 𝑡 𝑋 ′ 𝑡𝑞 + Σ -1/2 𝑋 𝑞 𝑡𝑞 ← 𝑋 ′ in matrix 𝑋 ′	// In-place accumulation of a column
	3 return argmax

𝑘∈K

‖𝑋 ′ 𝑌 ′ (𝑇 , 𝑘) T ‖ 𝐹 // As in (4.7)

  1. The CPA is based on the computation of the Pearson coefficient between 𝑋 𝐿,𝑄 and 𝑌 𝑆,𝑄,𝐾,𝐵 to discriminate the right key {𝑘 ⋆ 𝑏 } 𝑏<𝐵

	AbsMarg (D(𝑋 𝐿,𝑄 , 𝑌 𝑄 𝑠,𝑏 ))
	=	D(𝑋 𝐿,𝑄 , 𝑌 𝑄 𝑠,𝑘 ⋆ 𝑏 ,𝑏 ) -max 𝑘<256, 𝑘̸ =𝑘 ⋆ 𝑏 ( ( ( ( ( ( ( ( ( ( D(𝑌 𝑄 𝑠,𝑘 ⋆ 𝑏 ,𝑏 , 𝑌 𝑄 𝑠,𝑘 ⋆ 𝑏 ,𝑏 ) ⏟ ⏞ -max 𝑘<256, 𝑘̸ =𝑘 ⋆ 𝑏 {D(𝑌 𝑄 {D(𝑋 𝐿,𝑄 , 𝑌 𝑄 𝑠,𝑘,𝑏 )} 𝑠,𝑘 ⋆ 𝑏 ,𝑏 , 𝑌 𝑄 𝑠,𝑘,𝑏 )}	(5.6)
		=1
	as defined in the following Eq. 5.5.
	D(𝑋 𝐿,𝑄 , 𝑌 𝑆,𝑄,𝐾,𝐵 ) =	{ cov(𝑋 𝐿,𝑄 , 𝑌 𝑄 𝑠,𝑘,𝑏 ) 𝜎(𝑋 𝐿,𝑄 )𝜎(𝑌 𝑄 𝑠,𝑘,𝑏 )	}	𝑘<256,𝑆<8 𝑏<16

Table 5 . 2 :

 52 Leakage characterization and mapping to the source code for 𝑆 = 8.

	line source code	𝑅	𝑅	𝑌	key
		name	bit	bit	byte
	l.4086: v16 = lookup_nibble2(table_4436,v16,v18,0);	rsi	1	7	0
	l.4420: v18=lookup_nibble(table_13890,v4);	r14	3	4	1

  S-box (𝑇 𝑞,𝑏 ⊕𝑘)) & 2 𝑠-10 , if 10 < 𝑠

	]
	𝑠<18,𝑘<256,
	𝑞<𝑄,𝑏<16

Table 5 . 3 :

 53 Leakage characterization and mapping to the source code for 𝑆 = 18.

	line source code	𝑅	𝑅	𝑌	𝑌	key
		name	bit	value	bit	byte
	l.4086: v16=lookup_nibble2(table_4436,v16,v18,0);	rsi	1	x	7	0
	l.4128: v22=lookup_nibble2(table_4499,v22,v23,0);	rbp	0	3.x	4	0
	l.4420: v18=lookup_nibble(table_13890,v4);	r14	3	x	4	1
	l.4417: v2=lookup_nibble2(table_4934,v16,v2,0);	r15	1	3.x	1	1
	l.4417: v2=lookup_nibble2(table_4934,v16,v2,0);	r13	3	x	4	1
	102

analyse différentielle de la consommation de courant, en français

ctf.newae.com

figure inspired by[START_REF] Jean | TikZ for Cryptographers[END_REF]

Data gathered from www.keylength.com and all key sizes are provided in bits.

ctf.newae.com/

For all the submitted implementations the source code is provided

The work in[START_REF] Sugawara | Profiling attack using multivariate regression analysis[END_REF] does not detail the modus operandi result for the regression neither plugs it into the distinguisher, which is incidentally not chosen to be the optimal one.

https://github.com/dwelch67/thumbulator

http://ctf.newae.com/

https://www.scipy.org/

As provided by the python library https://pypi.org/project/bitmap/

Remerciements

CHAPTER 4

Multivariate Leakages and Multiple Models We have just tackled in the previous Chap. 3 the problem of the optimal dimension reduction in the context of univariate model. In the present Chap. 4 we generalize our solution to the multivariate models.

Contributions

Side-Channel Analysis (SCA) allow to extract secret keys from cryptographic devices. Template Attack (TA) [START_REF] Chari | Template attacks[END_REF] have been introduced as the strongest analysis method. They consist in two phases: (i) a profiling offline phase were the leakage model of the device under attack is characterized; (ii) an attack online phase in which the secret key is extracted using fresh measurements along with the precharacterized model. Such possible to reduce the dimension of the data to analyze? To answer these questions, we define the notion of activity matrix in Def. 5.2 and of transition matrix Def. 5.3.

Definition 5.2. The activity matrix 𝐴 𝐷,𝑅 of a given set 𝑋 𝐷,𝑅,𝑄 is defined as follow:

𝑑<𝐷, 𝑟<𝑅

The activity matrix of a given dataset identifies the points ((𝑑, 𝑟) ∈ 𝐷 × 𝑅) with a non-zero variance over 𝑄. • the weak attacker: the attacker has only access to the data set under attack.

Solution Presentation

Additionally, we treat the influence of the noise, studying the autoregressive and the isotropic noise distributions. This complete study gives us a clear methodology to exploit all the leaking information whichever its complexity. Furthermore, we treat the computational aspect giving fast implementation of the optimal distinguisher.

Is α known?

Leakage model:

Optimal distinguisher:

Affine projection:

Data transformation:

Leakage model: yes no known? Are α, β

Univariate ML attack:

New multivariate CPA attack:

Cov(x ′ d ,y) 2 Var(y) Second, we provide a complete framework to collect and analyze data provided by GNU Debugger (GDB). We exhaustively analyze and understand the leakage that could result [80] Nicolas Veyrat-Charvillon, Benoît Gérard, and François-Xavier Standaert. Soft analytical side-channel attacks. In Sarkar and Iwata [START_REF]Advances in Cryptology -ASIACRYPT 2014 -20th International Conference on the Theory and Application of Cryptology and Information Security[END_REF], pages 282-296. → Cited on page 67.

[81] Carolyn Whitnall and Elisabeth Oswald. A fair evaluation framework for comparing side-channel distinguishers. J. Cryptographic Engineering, 1(2):145-160, 2011. → Cited on pages 6 and 96.