Russon Andy
Russon Andy
elliptiques
Andy Russon
L’UNIVERSITÉ DE RENNES 1
Par
Andy RUSSON
Problème du logarithme discret sur des courbes elliptiques
Composition du jury :
Directeur de thèse Sylvain DUQUESNE Professeur, Université de Rennes 1, Rennes
Rapporteur Louis GOUBIN Professeur, Université de Versailles-Saint-Quentin-en-Yvelines
Examinatrice Cécile PIERROT Chargée de recherche, INRIA, Nancy
Examinateur Arnaud TISSERAND Directeur de recherche, CNRS, Lorient
Rapporteur Damien VERGNAUD Professeur, Sorbonne Université, Paris
Co-encadrant de thèse Olivier VIVOLO Directeur, Orange, Cesson-Sévigné
Problème du logarithme discret
sur des courbes elliptiques
Andy Russon
Introduction
La cryptographie est une science qui fournit un ensemble d’outils pour la sécurité
de l’information pour assurer la confidentialité, l’intégrité des données et l’authentifica-
tion. Dans cette thèse on s’intéresse en particulier à la cryptographie à base de courbes
elliptiques et s’intitule Problème du logarithme discret sur des courbes elliptiques. Le titre
fait référence au problème mathématique du même nom sur lequel repose la sécurité
de la cryptographie à base de courbes elliptiques. En particulier, cela fait partie du sous-
ensemble de la cryptographie asymétrique aussi appelée cryptographie à clé publique.
B a = (g b )a = g ab = (g a )b = Ab .
Il est impératif que les valeurs a et b restent secrètes (ce sont les clés privées d’Alice et
Bob), car en cas contraire, une personne tierce qui intercepte A et B serait en mesure
de calculer le secret partagé. De plus, il est aussi nécessaire que a et b ne puissent être
facilement calculés à partir des valeurs A et B : obtenir la clé privée à partir de la clé
publique s’appelle le problème du logarithme discret.
La difficulté de ce problème dépend du choix des paramètres et les travaux de re-
cherches ont sans cesse amélioré les techniques de résolution. En conséquence il est
actuellement recommandé d’utiliser des nombres premiers p de 2048 ou 3072 bits. Le
choix d’un corps aussi grand tient au fait que les meilleurs méthodes de résolution sont
i
ii Introduction
similaires à celles utilisées pour la factorisation, d’où des paramètres de tailles semblables
par rapport à la cryptographie RSA. La complexité de ces méthodes est sous-exponentielle
en la taille des paramètres, donc ces derniers augmentent plus vite que le niveau de
sécurité.
Le partage de clé Diffie-Hellman décrit ci-dessus repose sur la notion de groupe fini
et n’est pas exclusif à un groupe en particulier. Il est ainsi possible d’utiliser des groupes
dont les paramètres sont davantage compacts, ce qui a comme conséquence des clés plus
courtes (pour le stockage et l’échange), et potentiellement une meilleure efficacité dans
les calculs. De toute évidence, il faut s’assurer que le problème du logarithme discret reste
difficile à résoudre.
Courbes elliptiques
L’usage des courbes elliptiques en cryptographie a été proposé par Miller [Mil85] et
Koblitz [Kob87] dans les années 1980. Ces courbes sont dotées d’une structure de groupe
abélien, par une construction géométrique de la loi de groupe, illustré dans la figure
ci-dessous.
P +Q
Depuis leur introduction, il a été montré qu’en dehors de certaines classes de courbes,
les meilleures méthodes de résolution du problème du logarithme discret sont les algo-
rithmes génériques, c’est-à-dire qui s’appliquent à n’importe quel groupe fini abélien. La
complexité de ces méthodes est en la racine carrée de la taille du groupe, donc une courbe
elliptique avec des paramètres de taille 200 bits nécessiterait une capacité de calculs
d’environ 2100 afin de résoudre un logarithme discret. En bref, la structure de groupe sur
une courbe elliptique apparaît comme un candidat idéal.
Les courbes elliptiques ont longuement été étudiées et peuvent prendre plusieurs
formes (données par différentes équations). Par conséquent, la loi de groupe peut être don-
née par de nombreuses formules algébriques, enrichies par l’usage de plusieurs systèmes
de coordonnées pour représenter les points de la courbe. Cette richesse peut devenir une
difficulté pour son utilisation en cryptographie. En effet, les développeurs doivent faire
des choix parmi un ensemble de combinaisons possibles dans les paramètres, formules
ou algorithmes, et cela peut être critique d’un point de vue sécurité de l’implémentation
réalisée.
Introduction iii
Espion passif. Ce type d’attaquant exploite les données obtenues en observant les fuites
occasionnées lors de l’exécution. Le premier exemple est l’analyse du temps d’exécution
du code, lorsque celui-ci dépend de la valeur secrète manipulée. Il y a aussi la possibilité
d’exploiter la consommation de courant ou des émanations électromagnétiques, dont la
corrélation avec les opérations réalisées permettent de déduire éventuellement les valeurs
secrètes. La version classique est Simple Power Analysis (SPA), où le comportement de
l’exécution peut s’observer sur une seule trace. Une version plus complexe est Differential
Power Analysis (DPA) où plusieurs traces sont utilisées lorsqu’un secret constant est
manipulé.
Contributions
Les résultats présentés dans cette thèse sont orientés sur la sécurité des implémenta-
tions de courbes elliptiques. Ces travaux ont été réalisés par une analyse du code source
de plusieurs bibliothèques cryptographiques au regard de critères de sécurités liés aux
différentes attaques citées plus haut, notamment par l’identification des choix effectués
par les développeurs : algorithmes, formules, mécanismes de protection, etc.
Cela a abouti à la publication des quatre articles présentés ci-dessous.
[Rus20] Andy Russon, “Exploiting dummy codes in Elliptic Curve Cryptography im-
plementations”, in: Symposium sur la sécurité des technologies de l’information
et des communications, SSTIC, France, Rennes, June 3-5 2020, 2020, pp. 229–249.
Cet article montre qu’une attaque par injection de faute Safe-Error est possible sur
plusieurs implémentations de courbes elliptiques dans des bibliothèques cryptographiques.
iv Introduction
Pour une protection contre des attaques par un espion passif, des calculs factices sont
introduits afin que l’exécution soit régulière quelle que soit la valeur secrète en entrée. Plus
spécifiquement, il s’agit d’implémentations qui traitent la valeur secrète par morceaux
de plusieurs bits consécutifs. Lorsque tous ces bits sont nuls, les opérations effectuées
(calculs factices) n’ont aucun impact sur le résultat final. Une faute lors de ce moment n’a
alors pas d’effet et révèle ainsi que les bits secrets valent zéro lors de ce moment.
[Rus21a] Andy Russon, “Return of ECC dummy point additions: Simple Power Anal-
ysis on efficient P-256 implementation”, in: Symposium sur la sécurité des
technologies de l’information et des communications, SSTIC, France, Rennes,
June 2-4 2021, 2021, pp. 367–375.
En lien avec le précédent, cet article montre qu’une implémentation en particulier (et
présente dans plusieurs bibliothèques) est vulnérable à un cas particulier d’attaque SPA.
Cela est lié à la façon dont les calculs factices sont réalisés. Ceux-ci utilisent essentielle-
ment des valeurs nulles et l’impact sur la consommation de courant peut être observé sur
une trace.
[Rus21b] Andy Russon, “Threat for the Secure Remote Password Protocol and a Leak in
Apple’s Cryptographic Library”, in: ACNS 2021, ed. by Kazue Sako and Nils Ole
Tippenhauer, vol. 12727, LNCS, Springer, 2021, pp. 49–75, doi: 10.1007/978-
3-030-78375-4_3.
Dans ce troisième article présenté à la conférence Applied Cryptography and Network
Security, on propose une attaque par dictionnaire sur le protocole d’authentification
Secure Remote Password (SRP). Ce protocole est une construction similaire à un échange
de clé Diffie-Hellman, mais en faisant intervenir un mot de passe. On y présente comment
réaliser une attaque en exploitant une fuite éventuelle lors de l’exponentiation modulaire.
Celle-ci fait notamment intervenir une clé privée générée de façon déterministe depuis
un mot de passe et l’exploitation de la fuite permet d’obtenir un indicateur pour filtrer
les potentiels mots de passe dans un dictionnaire.
On montre également une vulnérabilité relevée dans la bibliothèque cryptographique
d’Apple qui peut être exploitée dans le contexte de SRP. Une méthode de protection
contre les attaques DPA est présente : la clé privée est randomisée à chaque exécution
par une division Euclidienne. C’est l’usage de cette méthode qui introduit une variabilité
qui peut être mesurable par une analyse simple de consommation. Le recueil d’un grand
nombre de mesures permet de faire une approximation de la clé privée.
Cette vulnérabilité concerne également les calculs sur courbes elliptiques et son
exploitation est possible sur le protocole d’authentification par mot de passe SPAKE2+
qui est similaire à SRP.
La vulnérabilité a été transmise à Apple Product Security selon leur procédure. Des
correctifs ont été introduits au Printemps 2021 à la suite des communications avec leurs
ingénieurs.
Introduction v
[Rus21c] Andy Russon, “Differential Fault Attack on Montgomery Ladder and in the
Presence of Scalar Randomization”, in: INDOCRYPT 2021, Proceedings, ed. by
Avishek Adhikari, Ralf Küsters, and Bart Preneel, vol. 13143, LNCS, Springer,
2021, pp. 287–310, doi: 10.1007/978-3-030-92518-5_14.
Ce dernier article, présenté à la conférence Indocrypt, porte sur une attaque en faute
différentielle. La première contribution est une nouvelle proposition d’attaque DFA sur
l’algorithme de multiplication scalaire Montgomery ladder avec une faute liée à l’échange
conditionnel des points manipulés au cours de l’exécution. Un regard particulier est
portée vers l’usage de formules d’addition de points spécifiques, où certaines vérification
peuvent ne pas suffire pour détecter la faute.
La seconde contribution principale de l’article met en avant que certaines méthodes
de randomisation pour protéger contre les attaques DPA ne sont pas nécessairement
suffisantes pour protéger contre des attaques DFA.
Présentation du plan
Le chapitre 1 donne une définition des courbes elliptiques et présente les différentes
formes les plus usuelles en cryptographie, ainsi que les représentations de coordonnées.
Des protocoles utilisant des courbes elliptiques sont également présentés.
Le chapitre 2 introduit le problème du nombre caché ou Hidden Number Problem (HNP)
et les méthodes à base de réseau Euclidien pour le résoudre. Cela a une utilité pour, par
exemple, exploiter des vulnérabilités pendant la génération de signatures, comme montré
dans les chapitres 4 et 6.
Le chapitre 3 étudie les formules courantes d’additions de points et les cas exception-
nels. Plusieurs algorithmes de multiplication scalaire sont présentés et on précise si ces
exceptions peuvent avoir lieu ou non.
Le chapitre 4 s’intéresse à la situation d’additions factices de points, qu’elles soient
implicitement ou explicitement introduites au cours de l’exécution du code. Le concept
de l’attaque par un espion actif perturbant le bon déroulement des calculs est présentée
avec une sélection de bibliothèques cryptographiques vulnérables. Pour l’une d’entre elle,
on montre également qu’un espion passif peut être en mesure de détecter une partie de
ces additions factices.
Le chapitre 5 concerne une méthode de randomisation du scalaire pour laquelle une
vulnérabilité nouvelle est présentée. Telle qu’introduite originellement (ainsi que dans
son utilisation dans la bibliothèque cryptographique d’Apple), il est possible d’exploiter
une légère variation d’exécution aboutissant à l’approximation du secret.
Le chapitre 6 détaille une nouvelle attaque en faute différentielle appliquée sur l’algo-
rithme Montgomery ladder, et explore également comment les méthodes de randomisation
du scalaire peuvent être insuffisantes pour protéger contre ce type d’attaque.
Le chapitre 7 présente une attaque par dictionnaire contre SRP et SPAKE2+, deux
protocoles d’authentification basée sur un mot de passe.
vi Introduction
Table des matières
Introduction i
vii
viii Table des matières
Conclusion 113
Bibliographie 117
Cryptographie à base
1
de courbes elliptiques
Dans ce chapitre on introduit les définitions et notations sur les courbes elliptiques qui
sont essentielles pour les chapitres suivants. On y présente notamment la loi de groupe
et quelques propriétés importantes. On termine avec des primitives cryptographiques
basées sur les courbes elliptiques.
Sommaire
1.1 Courbes elliptiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Loi de groupe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Autres systèmes de coordonnées . . . . . . . . . . . . . . . . . . . . 4
1.1.4 Formes alternatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.5 Cardinalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Problème du logarithme discret . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Algorithme de Pohlig-Hellman . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Pas de bébés – pas de géants . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.3 L’algorithme rho de Pollard . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.4 Choix des paramètres pour la cryptographie . . . . . . . . . . . . . . 9
1.3 Primitives cryptographiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Partage de clé Diffie-Hellman . . . . . . . . . . . . . . . . . . . . . . 10
1.3.2 Elliptic Curve Integrated Encryption Scheme . . . . . . . . . . . . . 11
1.3.3 Signature ECDSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1
2 Chapitre 1 Cryptographie à base de courbes elliptiques
1.1.1 Définition
Notons tout d’abord P2 (K) le plan projectif de dimension 2 sur le corps K. Il s’agit
de l’ensemble des classes notées (X : Y : Z) où X, Y , et Z sont dans K non tous nuls,
selon la relation d’équivalence (X, Y, Z) ∼ (X 0 , Y 0 , Z 0 ) s’il existe λ non nul sur K tel
que (X, Y, Z) = (λX 0 , λY 0 , λZ 0 ).
Un point (X : Y : Z) avec Z 6= 0 est identifié dans le plan affine par le point (x, y)
où x = X/Z et y = Y /Z. Les points (X : Y : 0) sont appelés les points à l’infini.
Y 2 Z = X 3 + AXZ 2 + BZ 3 , (1.1)
où les paramètres A et B sont tels que le discriminant ∆ = 4A3 + 27B 2 est non nul. On
note E(K) l’ensemble des points qui satisfont l’équation de cette courbe.
Il est assez facile de voir que le seul point dont la coordonnée projective Z est nulle
est (0 : 1 : 0). Il ne possède donc pas de représentation affine et on le note O. Ainsi on
peut aussi définir la courbe par son équation sous forme affine et l’ensemble des points
est :
E(K) = { (x, y) ∈ K 2 | y 2 = x3 + Ax + B } ∪ { O }. (1.2)
La condition spécifique sur le discriminant ∆ est pour éviter la présence de points dits
singuliers (on dit alors que la courbe est lisse). Dans le cas où celui-ci est effectivement
nul, alors le polynôme x3 + Ax + B possède une racine double ou triple. La raison de
l’exclusion de ce cas dans la définition est que la loi de groupe définie ci-dessous serait
facilement réécrite sous la forme d’une addition ou d’une multiplication dans le corps K
(éventuellement dans une extension de degré 2), ce qui ne serait que peu d’intérêt pour
une utilisation en cryptographie.
Q P P
P
P +P
P +Q −P
Le théorème de Bézout assure que le nombre de points d’intersection entre une droite et
une courbe elliptique donnée par l’équation (1.1) est trois. Ainsi la construction ci-dessus
est correcte.
L’élément neutre est bien le point à l’infini O. En effet, pour cela on utilise la version
projective des équations, dont celle de la droite L est
−P = (X1 : −Y1 : Z1 ).
L’associativité est moins évidente à prouver, mais peut être effectuée formellement.
Cependant il convient de regarder quelques cas particuliers, notamment pour la partie
calculatoire. Pour calculer P + P , la droite L construite est une tangente à la courbe (elle
intersecte la courbe avec une multiplicité double au point P ). Tandis que pour calculer
P + (−P ), il s’agit d’une droite verticale. Le calcul de l’équation de la droite nécessite de
distinguer ces situations pour calculer sa pente.
Ces cas particuliers sont présentés dans la formulation affine de la loi de groupe
ci-dessous, et font également l’objet du chapitre 3 où cela entraîne des cas exceptionnels
(selon les formules et algorithmes utilisés) qui nécessitent d’être traités avec soin pour
une implémentation sécurisée dans les bibliothèques cryptographiques.
Formules affines. Les différentes situations sont illustrées dans la figure 1.1.
Une reformulation de la construction géométrique avec une représentation affine des
points donnent la loi de groupe ci-dessous. Notons P = (x1 , y1 ) et Q = (x2 , y2 ). La loi
de groupe est :
1. P + O = O + P = P pour tout P sur la courbe.
2. Si x1 = x2 et y1 = −y2 alors P + Q = O.
3. Sinon, si x1 6= x2 on pose
y1 − y2
λ= ,
x1 − x2
4 Chapitre 1 Cryptographie à base de courbes elliptiques
et si x1 = x2 alors on pose
3x21 + A
λ= .
2y1
Alors y = λ(x − x1 ) + y1 est l’équation de la droite L passant par P et Q (ou de la
tangente si P = Q) et P + Q = (x3 , y3 ) est donné par
x3 = λ2 − (x1 + x2 )
(
y3 = λ(x1 − x3 ) − y1 .
[k]P = P
|
+P +
{z
· · · + P} .
k fois
Dans la pratique on ne calcule pas une multiplication scalaire par une addition
répétée car cela deviendrait vite impossible pour de grands entiers k. Des algorithmes de
complexité logarithmique par rapport au scalaire k permettent de réaliser cette opération
efficacement. Plusieurs exemples sont donnés dans le chapitre 3.
Y 2 = X 3 + AXZ 4 + BZ 6 .
On en déduit qu’une représentation du point à l’infini est donnée par les triplets de la
forme (λ2 : λ3 : 0) pour λ 6= 0.
Forme de Montgomery. Cette forme a été introduite par Montgomery [Mon87] pour
une utilisation dans la méthode de factorisation à base de courbes elliptiques. Elle est
donnée par l’équation
By 2 = x3 + Ax2 + x,
et la condition sur les paramètres A et B est B(A2 − 4) 6= 0.
Le choix de cette forme tient à l’efficacité des formules pour l’addition de points pré-
sentées dans le même article, qui n’utilisent pas la coordonnée y. Des formules analogues
pour la forme de Weierstraß sont étudiées dans la section 3.1.4.
Cette forme a été introduite pour un usage en cryptographie dans [Ber06] avec une
courbe nommée Curve25519, dont le nom fait référence au nombre premier 2255 − 19
qui définit le corps de base.
Forme d’Edwards. La forme d’Edwards a été introduite dans [Edw07]. Celle-ci est
donnée par une équation de la forme suivante :
x2 + y 2 = 1 + dx2 y 2 ,
où le paramètre d vérifie d(1 − d) 6= 0. Avec le changement de variable x = u/v et
y = (u − 1)/(u + 1) on retrouve l’équation de la forme de Montgomery donnée ci-dessus
avec A = 2(1+d)/(1−d) et B = 4/(1−d). Un avantage est que l’ensemble des points de
la courbe elliptique ont une représentation affine sur la forme d’Edwards. En particulier,
l’élément neutre est le point (0, 1). Un second avantage démontré dans [BL07] est que les
formules !
x1 y2 + x2 y1 y 1 y 2 − x1 x 2
(x1 , y1 ) + (x2 , y2 ) = , .
1 + dx1 x2 y1 y2 1 − dx1 x2 y1 y2
pour la loi de groupe sont complètes : elles donnent le bon résultat pour tous points
P = (x1 , y1 ) et Q = (x2 , y2 ).
1.1.5 Cardinalité
Comme le corps de base est fini, la courbe elliptique possède un nombre fini d’éléments,
dont l’encadrement est donné par le théorème suivant.
Théorème 1 (Hasse). Le cardinal d’une courbe elliptique E(Fp ), noté |E(Fp )| satisfait
l’inégalité
√ √
p + 1 − 2 p ≤ |E(Fp )| ≤ p + 1 + 2 p.
Ainsi il existe un plus petit entier N tel que [N ]P = O et est appelé l’ordre de ce
point. Il est conseillé que cet ordre soit un grand nombre premier pour un usage en
cryptographie, ce qui est justifié dans la section suivante.
La plupart des courbes standardisées sont choisies de cardinal premier et donc tout
point (hormis le point à l’infini) génère tout le groupe. Une exception sont les courbes
sous forme de Montgomery et d’Edwards qui possèdent des points d’ordre 2, donc le
cardinal est nécessairement pair. Avec la forme de Weierstraß courte, ces points sont
ceux avec une ordonnée nulle, ce qui est équivalent à une abscisse racine du polynôme
x3 + Ax + B. Pour la forme de Montgomery, il y a toujours le point (0, 0) comme point
d’ordre 2.
En résumé, le cardinal des courbes elliptiques recommandées en cryptographie est
N = qh où q est un nombre premier et h est le cofacteur qui vaut généralement 1, 4 ou 8.
6 Chapitre 1 Cryptographie à base de courbes elliptiques
(mod q1α1 )
k ≡ k1
..
.
k ≡ ks (mod qsαs ),
k = k0 + k1 q + k2 q 2 + · · · + kα−1 q α−1 ,
avec 0 ≤ ki < q pour 0 ≤ i < α. Les valeurs ki sont calculées au fur et à mesure pour
reconstruire k. En effet, on a
i=0 i=j
Ensuite on peut itérer le mécanisme précédent avec une multiplication scalaire par
q α−j−1 :
P 00 = [q α−1 ]P, Q00 = [q α−j−1 ]Q0 , Q00 = [kj ]P 00 .
Ainsi kj est un logarithme discret dans un groupe d’ordre q.
Combiné avec l’étape précédente, le coût du logarithme discret est donc dominé par
le plus grand facteur premier de l’ordre du point de base. Cela justifie le choix d’utiliser
des courbes elliptiques dont le cofacteur est petit.
{ [i]P | 0 ≤ i < m }.
{ Q − [j]R | 0 ≤ j < m }.
Une collision entre les deux listes donne le logarithme discret recherché si les indices (i, j)
sont conservés :
Une telle solution existe par construction, donc l’algorithme est déterministe et donne
√
la solution en 2d qe opérations dans le groupe au pire cas.
Plusieurs remarques peuvent être faites. Tout d’abord il n’est pas nécessaire de stocker
la liste des pas de géants, car si un élément n’est pas dans la liste des pas de bébés alors il
est inutile de le conserver. Cependant, la liste des pas de bébés est nécessaire donc cela
√
implique un coût mémoire en O( q).
8 Chapitre 1 Cryptographie à base de courbes elliptiques
Ri+1
Ri
Ri−1
Rj
Rj−1
R0
Q − [B1 ]P = [k − B1 ]P.
| {z }
Q0
Ainsi, l’algorithme
√ √ peut être appliqué avec P et Q en posant
pas de bébés – pas de géants 0
Cependant on n’est pas plus avantagé par rapport à l’algorithme pas de bébés – pas de
géants car la collision telle que décrite nécessite de sauvegarder les valeurs déjà calculées
de la suite. Une méthode de recherche de cycle attribué à Floyd permet de s’affranchir du
stockage. Une fois la boucle atteinte, si i est un multiple de la longueur L de la boucle,
alors on a l’égalité Ri = R2i . Il suffit alors de construire deux suites en parallèle :
Dès que ces deux suites sont dans la boucle, on finit par tomber éventuellement sur une
collision Ri = R2i . q
Par le paradoxe des anniversaires, il est estimé que la collision a lieu après O( πq/2)
étapes (à condition d’une fonction f qui agit comme une marche suffisamment aléatoire),
ce qui correspond à la complexité de pas de bébés – pas de géants.
φ : secp256k1 −→ secp256k1
(x, y) 7−→ (βx, y),
Il est évident que si le problème du logarithme discret peut être résolu, alors les
problèmes CDH et DDH peuvent l’être aussi. L’inverse n’est pas nécessairement vrai.
Étant données une clé privée α dans [1, N − 1] et une fonction de hachage H, signer
un message M est effectué selon l’algorithme 1, et la signature est formée par le couple
(r, s). Le processus de vérification consiste en le calcul du point
e = [H(M )s−1 ]P + [rs−1 ]P
Q pub (1.3)
où Ppub = [α]P est la clé publique du signataire. La signature est valide si r est égal à la
coordonnée affine x du point Q e (relevée en tant qu’entier, puis réduite modulo N ).
12 Chapitre 1 Cryptographie à base de courbes elliptiques
Vulnérabilités. D’une signature (r, s) correspond une équation linéaire dont les deux
inconnues sont le nonce et la clé privée. Chaque nouvelle signature générée par une
même clé privée ajoute une équation et une inconnue supplémentaire, il y a donc toujours
une inconnue de plus qu’il n’y a d’équations.
Dans le cas d’un nonce k réutilisé, on obtiendrait deux signatures (r, s1 ) et (r, s2 ), et
donc un système de deux équations à deux inconnues :
(
ks1 ≡ αr + H(M1 ) (mod N )
ks2 ≡ αr + H(M2 ) (mod N ),
La clé privée peut alors s’exprimer directement à partir des données publiques :
Plus généralement, un biais sur le nonce peut être exploité pour reconstituer la clé
privée et cela fait l’objet du chapitre 2.
Problème du nombre caché
2
Ce chapitre présente le problème du nombre caché, ou Hidden Number Problem (HNP).
Il est introduit dans [BV96] pour montrer qu’obtenir les bits de poids fort d’un secret
partagé dans un échange Diffie-Hellman classique à partir des clés publiques est aussi
difficile que de calculer le secret entier.
Ce problème a ensuite été adapté aux schémas de signatures DSA et ECDSA pour
montrer qu’une clé privée peut être reconstituée en temps polynomial lorsque le nonce
est révélé partiellement pour un nombre suffisant de signatures [NS02, NS03]. Cela se
montre efficace pour exploiter les fuites obtenues par canaux auxiliaires ou par injection
de fautes, ce qui sera abordé dans les chapitres 4 et 6.
Le problème en question et son application sur ECDSA sont présentés dans un premier
temps, suivi de sa résolution à base de réseaux Euclidiens (la méthode par analyse de
Fourier est aussi abordée).
Sommaire
2.1 Description du problème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.1 Application à ECDSA . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Résolution par réseaux Euclidiens . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 Réseaux Euclidiens . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Construction pour résolution de HNP . . . . . . . . . . . . . . . . . 17
2.2.3 Nombre de signatures . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Résolution par analyse de Fourier . . . . . . . . . . . . . . . . . . . . . . . . 19
13
14 Chapitre 2 Problème du nombre caché
Définition 3 (HNP). Soit q un nombre premier, k un entier. Soit un oracle Oα (t) qui, à
partir d’une entrée t, calcule les k bits de poids fort de α · t mod q, où α est inconnu.
Le problème HNP consiste à calculer le nombre caché α en temps polynomial (en
log q), étant donné un accès à l’oracle Oα (t).
C 0a ≡ B a · C a (mod q)
≡ α · Ac (mod q).
Il est clair qu’un système linéaire ayant plus de variables que d’équations ne peut
aboutir à une solution unique. La connaissance d’information supplémentaire sur n de
ces variables réduit le nombre de solutions possibles et c’est l’objectif des méthodes par
réseaux Euclidiens ou analyse de Fourier d’exploiter ces biais pour résoudre ce système.
Le cas le plus simple est lorsque les bits de poids fort des variables Yi sont connues, ce
qui correspond à la formulation initiale, mais cela s’adapte également lorsque ce sont les
bits de poids faible qui sont connus en ajustant l’équation : l’important est que la partie
inconnue des variables Yi puisse être encadrée dans un intervalle relativement petit. C’est
le sujet de la partie ci-dessous dans le cadre de ECDSA.
où k un est nonce généré exclusivement pour cette signature, et α est la clé privée du
signataire. Cette dernière est le nombre caché car fixe pour plusieurs signatures réalisées
avec la même clé. Tandis que la valeur éphémère k joue le rôle de la variable Y dont une
partie seulement est inconnue.
On considère plusieurs cas selon la partie connue de k.
Si la valeur k est issue de la méthode de bourrage donnée en section 3.2.2, alors l’enca-
drement de la partie inconnue est
2t − b 2t + q − b
≤a< ,
m m
qui est un intervalle de largeur L = q/m.
Cette situation inclut également le cas où la méthode de randomisation par l’ordre
du groupe est utilisée. Dans ce cas le scalaire k est bien plus large que q. Si la valeur
aléatoire utilisée est un entier de λ bits, alors k est dans l’intervalle [2λ−1 q, (2λ + 1)q]
donc la partie inconnue de k est encadrée par
q−b q + 2λ q − b
≤a< ,
m m
qui est un intervalle de largeur L = 2λ q/m. Il est donc nécessaire que m soit plus grand
que 2λ pour être exploité dans l’attaque par réseau Euclidien. En particulier si m = 2` ,
cela signifie que le nombre ` de bits de poids faible révélés doit être supérieur à λ.
Cas 2 (bits de poids fort). Dans le cas où il s’agit de a et m qui sont connus dans la
division Euclidienne de k par m, alors on a
Y = b,
u = r/s mod q,
v = H(M )/s − am
mod q.
Il y a un cas particulier abordé dans la section 6.3.5 (chapitre sur l’injection de faute
différentielle) où les (` + 1) bits de poids fort a sont presque connus : une valeur µ est
obtenue qui peut valoir soit a soit a + 1. Dans ce cas on a
= k − µ2t−` ,
Y
u = r/s mod q,
v = H(M )/s − µ2t−`
mod q.
La borne sur l’inconnue est −2t−` ≤ Y < 2t−` de largeur 2t−`+1 (qui peut être approximé
par q/2`−1 ).
où la base B est vue comme une matrice dont chaque ligne est un vecteur de la base.
On note λ(L) la longueur du √ plus court vecteur non nul d’un réseau Euclidien L et
elle satisfait l’inégalité λ(L) ≤ n(det L) . À cette valeur est associée le problème du
1/n
vecteur le plus court, Shortest Vector Problem (SVP) qui consiste à trouver un vecteur v de
norme exactement égale à λ(L).
L’algorithme de Gauss permet de résoudre SVP efficacement en dimension 2. Pour
les dimensions supérieures, l’algorithme LLL [LLL82] permet de construire en temps
polynomial une base dont le plus petit vecteur a une norme majorée par 2(n−1)/4 det(L)1/n .
En pratique le plus petit vecteur obtenu a une norme bien inférieure à cette borne, mais
il n’est pas pour autant assuré que ce soit le plus petit vecteur du réseau Euclidien. Un
autre algorithme plus performant pour obtenir une base réduite, mais plus coûteux en
exécution est BKZ [SE94].
2.2. Résolution par réseaux Euclidiens 17
pour tout nombre réel z. Il s’agit d’une réduction modulo q dans l’intervalle [−q/2, q/2]
suivi d’une valeur absolue.
Soit uX + v ≡ Y mod q une équation linéaire en les variables X and Y , où une
approximation de Y vue en tant qu’entier est connue :
B1 ≤ Y < B2 ,
avec B1 et B2 deux entiers qui satisfont l’inégalité (B2 − B1 ) < q/L pour un entier
positif L. La largeur de l’intervalle peut être réduite davantage en le centrant sur 0 :
posons C = (B1 + B2 )/2 le centre de l’intervalle, et on obtient l’inégalité
|Y − C| < q/(2L).
Ainsi en posant v 0 = C − v, on a
|uX − v 0 |q = |Y − C|q = |Y − C|,
car on sait que (Y − C) est situé dans l’intervalle [−q/2, q/2]. En utilisant les bornes on
arrive à l’inégalité
|uX − v 0 |q < q/(2L), (2.2)
qui signifie que lorsqu’elle est vue modulo q, la valeur v 0 est proche d’un multiple de X
(le nombre caché).
Étant données n inégalités de la forme
|ui X − vi0 |q < q/(2Li ),
où X est une variable commune, on peut construire le réseau Euclidien généré par cette
matrice entière :
2L1 q
2L2 q
. .
.
.
2Ln q
2L1 u1 2L2 u2 · · · 2Ln un 1 0
Table 2.1 : Nombre de signatures en fonction du nombre de bits ` de poids faible connus du nonce
dans ECDSA pour reconstruire la clé privée.
Sommaire
3.1 Exceptions dans les formules d’addition de points . . . . . . . . . . . . . . . 22
3.1.1 Formules pour représentation affine . . . . . . . . . . . . . . . . . . 22
3.1.2 Formules pour coordonnées Jacobiennes XYZ . . . . . . . . . . . . . 23
3.1.3 Formules XYcoZ pour coordonnées Jacobiennes . . . . . . . . . . . . 24
3.1.4 Formules XZ pour coordonnées projectives homogènes . . . . . . . 25
3.2 Montgomery Ladder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Description de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.2 Nombre d’itérations fixe . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.3 Les situations exceptionnelles . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Algorithmes à base de fenêtres . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.1 Versions classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.2 Versions avec réencodage du scalaire . . . . . . . . . . . . . . . . . . 35
3.4 Vue d’ensemble des bibliothèques . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.1 Multiplication scalaire dans OpenSSL . . . . . . . . . . . . . . . . . . 39
3.4.2 Multiplication scalaire dans BoringSSL . . . . . . . . . . . . . . . . . 40
3.4.3 Multiplication scalaire dans LibreSSL . . . . . . . . . . . . . . . . . . 41
3.4.4 Multiplication scalaire dans CoreCrypto . . . . . . . . . . . . . . . . 41
3.4.5 Multiplication scalaire dans Mbed TLS . . . . . . . . . . . . . . . . . 42
21
22 Chapitre 3 Multiplication scalaire et exceptions
Table 3.1 : Cas exceptionnels dans les formules pour les courbes elliptiques en forme de Weierstraß
courte.
Formules Exceptions
Affines Add P1 = ±P2 , Pi = O
Dbl P1 = O, y(P1 ) = 0
Jacobiennes XYZ Add P 1 = P 2 , Pi = O
Dbl Aucune
XYcoZ XYcoZ-ADDC, XYcoZ-ADD P1 = ±P2 , Pi = O
XYcoZ-DBL y(P1 ) = 0
Récupération de Z (†) x(P ) = 0, y(P ) = 0
XZ Add diff. P1 = P2
Dbl Aucune
Récupération de y (†) Pi = O, y(P2 − P1 ) = 0
(†) Utilisées avec l’algorithme Montgomery ladder.
Lorsque les deux points ont une représentation affine (Z 6= 0), on retrouve les formules
classiques du cas affine et par conséquent le cas de l’égalité est une exception. Il convient
alors de regarder les situations où le point à l’infini apparaît en entrée ou en sortie. Le
seul cas compatible est lorsque P1 = −P2 (et P1 6= P2 ). Dans ce cas on obtient
(X3 : Y3 : 0) = (µ2 : µ3 : 0), µ = 2Y1 Z13
où X3 et Y3 sont non nuls. Une représentation valide du point à l’infini est obtenue et
cela est bien le résultat attendu de l’addition.
En résumé, les exceptions sont : P1 ou P2 est le point à l’infini ; P1 et P2 sont égaux.
Addition de points avec mise à jour. Ces formules effectuent l’addition entre P1 =
(X1 : Y1 : Z1 ) et P2 = (X2 : Y2 : Z2 ) avec Z1 = Z2 et met également à jour les
coordonnées projectives de P1 vers (X10 : Y10 : Z10 ) de telle sorte que la coordonnée
Z corresponde à celle du résultat de l’addition. Les formules, notées XYcoZ-ADD, sont
données ci-dessous :
Il y a davantage de contraintes par rapport aux formules classiques avec les coordonnées
Jacobiennes à cause de la valeur commune pour la coordonnée Z. En effet, le cas P1 = −P2
implique que la mise à jour de P1 sera faite par des coordonnées nulles.
Les exceptions sont donc les mêmes que pour le cas des formules affines : P1 ou P2
est le point à l’infini, P1 et P2 sont égaux ou opposés.
Addition conjuguée de points. Ces formules pour l’addition calculent en même temps
la différence, notamment car une partie des opérations intermédiaires sont communes.
Les sorties P1 + P2 = (X3 : Y3 : Z3 ) et P1 − P2 = (X4 : Y4 : Z4 ) sont données par les
formules XYcoZ-ADDC ci-dessous :
Comme avec l’addition de points avec mise à jour, ces formules ont les mêmes exceptions
que le cas affine.
Doublement de point et mise à jour. Il s’agit des mêmes formules qu’en cas classique
des coordonnées Jacobiennes, mais avec la mise à jour de l’entrée pour partager la même
3.1. Exceptions dans les formules d’addition de points 25
valeur pour Z que le résultat du doublement. Les formules, notées XYcoZ-DBL, sont
données ci-dessous :
x·Y
Z= . (3.1)
y·X
Si x ou y est nul, alors la coordonnée Z ne peut être reconstruite, ce qui entraîne des cas
exceptionnels pour les courbes elliptiques ayant de tels points.
Addition différentielle de points. Les points n’étant pas différenciés de leurs opposés,
l’addition ne peut être calculée sans une donnée auxiliaire. En effet, l’abscisse du résultat
de l’addition peut être soit x(P1 + P2 ) ou soit x(P1 − P2 ). Ainsi si l’une de ces deux
valeurs est connue à l’avance il ne reste plus qu’une possibilité.
Étant donnés P1 et P2 par leur représentation [X1 : Z1 ] et [X2 : Z2 ], et la coordonnée
affine x de P1 − P2 , alors l’addition de P1 + P2 est donnée par les formules suivantes :
Z3 = (X1 Z2 − X2 Z1 )2 .
Ce qui rend cette addition différentielle intéressante est qu’elle donne des résultats
corrects avec le point à l’infini. Premièrement il y a le cas où l’un des points est le
point à l’infini. Soit P1 6= O et P2 = O, donc on a Z1 6= 0, X2 6= 0 et Z2 = 0. Alors
X3 = 2X1 Z1 X22 − xX22 Z12 , Z3 = X22 Z12 6= 0 et
donc [X3 : Z3 ] est une représentation valide de P1 qui est le résultat attendu de P1 + P2 .
Ensuite, il y a le cas où le point à l’infini est le résultat de l’addition, c’est-à-dire que
P1 et P2 sont opposés. En effet, si P1 = −P2 (et P1 6= P2 ), alors Z3 = 0 et on a la relation
3 !
X3 X1 X1
=4 +A + B 6= 0,
Z12 Z22 Z1 Z1
ce qui signifie que le résultat est une représentation valide du point à l’infini.
La seule exception est lorsque les deux points sont égaux, mais ce cas ne peut arriver
dans son utilisation avec l’algorithme Montgomery ladder comme il est expliqué dans la
section 3.2.3.
Remarque 2. Il y a une autre variante de formules pour l’addition différentielle donnée
à l’entrée mdadd-2002-bj de la base EFD. Dans ces formules, il y a la coordonnée x
en facteur pour le calcul de Z3 . En conséquence le calcul de P1 + P2 est erroné lorsque
x est nul. Un point ayant cette coordonnée nulle utilisé en entrée de l’algorithme de
multiplication scalaire Montgomery ladder n’est pas compatible.
Comme pour les coordonnées Jacobiennes, il n’y a pas de cas exceptionnel pour le
doublement de points.
En effet, si P1 = [λ : 0] pour une valeur λ non nulle, alors X3 = λ2 et Z3 = 0, ce qui
est une représentation valide du point à l’infini. Dans le cas où P1 est un point d’ordre 2,
alors on a X13 + AX1 Z12 + BZ13 = 0. Donc Z3 est nul, et X3 6= 0 sinon cela signifierait
que le discriminant de la courbe est nulle.
3.2. Montgomery Ladder 27
Cette reconstruction est erronée si P1 ou P2 est le point à l’infini ou si y est nul (également
dans le cas où P1 et P2 sont égaux, mais ce cas ne peut arriver au cours de l’utilisation,
voir section 3.2.3).
Échange conditionnel. Pour éviter des branchements conditionnels pour que les
résultats des opérations soit affectés aux bons points R0 ou R1 , un échange conditionnel
est généralement utilisé (avec des masques binaires par exemple). Une première fois pour
échanger les points avant les opérations d’addition et de doublement, puis une seconde
fois après pour rétablir l’ordre des points. Cette variante est donnée dans l’algorithme 3.
Une autre variante est souvent utilisée dans la plupart des implémentations de bi-
bliothèques cryptographiques, où le second échange est fusionné avec le premier de
l’itération suivante. Cette variante est donnée dans l’algorithme 4. Pour cela une variable
pbit est introduite pour garder trace du bit précédent : lorsqu’elle vaut 0, alors l’état
28 Chapitre 3 Multiplication scalaire et exceptions
actuel du couple (R0 , R1 ) est « normal », tandis que si elle vaut 1, alors R0 et R1 sont
inversés (notamment, on a la relation R1 − R0 = −P ). Un dernier échange conditionnel
est nécessaire après la dernière boucle pour s’assurer que l’état soit redevenu normal
avant de fournir la sortie de l’algorithme.
Les échanges des points dans le couple (R0 , R1 ) jouent un rôle essentiel dans l’attaque
en faute différentielle du chapitre 6 ; notamment car l’invariant de boucle devient
R1−pbit − Rpbit = P
Variante XYcoZ. Les formules XYcoZ sont adaptées pour l’algorithme Montgomery lad-
der, qui doit être légèrement modifié en remplaçant l’addition de points et le doublement
par les formules XYcoZ-ADDC et XYcoZ-ADD :
Cela reste équivalent à la variante classique tel qu’on peut le voir dans la figure 3.1 où
une étape aboutit au même résultat.
On peut notamment remarquer que l’invariant apparaît entre les deux opérations.
C’est à partir de cette observation qu’il est possible d’appliquer la récupération de la
coordonnée Z manquante lors du traitement du dernier bit du scalaire en appliquant la
formule de l’équation (3.1) entre les opérations XYcoZ-ADDC et XYcoZ-ADD. Une alter-
native est proposée en annexe A par l’introduction d’une fonction XYcoZ-SUB après la
dernière itération.
ki = 0 ki = 1
R0 = [λ]P R0 = [λ]P
R1 = [λ + 1]P R1 = [λ + 1]P
XYcoZ-ADDC
R0 = [2λ + 1]P R0 = P
R1 = −P R1 = [2λ + 1]P
XYcoZ-ADD
Le résultat est un scalaire qui est toujours de longueur (t + 1) bits, donc il y a toujours t
itérations de la boucle.
On peut encadrer le scalaire kpad plus précisément. Si k < 2t − q, alors kpad = k + 2q
et 2q ≤ kpad < 2t + q. Tandis que si k ≥ 2t − q, alors kpad = k + q et 2t ≤ kpad < 2q.
Globalement, le nouveau scalaire satisfait l’inégalité
Vue que q est l’ordre du point de base, le résultat final de la multiplication scalaire est
inchangé.
Clamping. Cette technique est spécifique pour les courbes sous forme de Montgomery.
Prenons la courbe Curve25519 comme exemple : le bit 2254 est fixé à 1 et tout bit supérieur
est mis à zéro, de telle sorte que tout scalaire est un entier d’exactement 255 bits.
Cette méthode ne devrait pas être utilisée pour générée des signatures, car cela
introduirait un biais exploitable pour résoudre le problème HNP (voir le chapitre 2).
La proposition d’Apple. Dans les versions les plus récentes de la bibliothèque crypto-
graphique d’Apple (à partir de iOS 14.5 et macOS 11.3) l’implémentation de l’algorithme
Montgomery ladder pour les courbes elliptiques a été modifiée pour gérer des scalaires de
longueur variable (notamment pour corriger la vulnérabilité décrite dans le chapitre 5).
Les idées générales sont décrites ci-dessous.
Dans la section 3.2.1 il a été décrit que l’état est initialisé par (P, [2]P ) sous l’hypothèse
que le bit kn−1 est 1. Dans la situation où ce bit vaut 0, une négation conditionnelle peut
être effectuée pour transformer l’état en (−P, [2]P ). Il devient (−P, P ) après l’addition
de points, puis ([−2]P, P ) après le doublement. Avec une autre négation et un échange,
le couple (R0 , R1 ) revient à son état originel. Ensuite, dès qu’un bit du scalaire vaut 1
alors la version classique de l’algorithme peut être exécutée.
Dans le code d’Apple, cela est réalisé avec plusieurs variables booléennes et est
entièrement décrit dans l’algorithme 5, basé sur les formules XYcoZ. Cependant, il est
assez difficile de vérifier la validité sous cette forme. Pour voir le comportement, on note
(R0 , R1 ), (nbit, zbit, pbit) l’état des variables à chaque itération. L’évolution de cet état
en fonction des bits du scalaire est donnée dans la figure 3.2.
3.2. Montgomery Ladder 31
start
0 1
1 0
(−2, −3), (0, 1, 0) (−4, −3), (0, 1, 1) (2, 3), (0, 1, 0) (4, 3), (0, 1, 1)
Figure 3.2 : État interne des variables (R0 , R1 ) et (nbit, zbit, pbit) dans la variante de Montgomery
ladder de l’algorithme 5.
32 Chapitre 3 Multiplication scalaire et exceptions
On aperçoit clairement la boucle tant que que les bits du scalaires rencontrés sont 0.
Cependant, dès qu’un bit vaut 1, et que le bit qui suit a été traité alors les variables nbit
et zbit prennent une valeur fixe jusqu’à la fin de l’exécution. On arrive dans une des deux
situations suivantes :
• Le nombre de bits nuls avant le premier bit 1 est pair, et on retrouve la situation
classique de l’algorithme ;
• Le nombre de bits nuls avant le premier bit 1 est impair, alors la situation est similaire,
à ceci près de la présence d’un facteur −1 pour les points R0 et R1 : par exemple, si
les trois premiers bits sont (0, 1, 0), on obtient R0 = [−2]P et R1 = [−3]P .
Dans le second cas, continuer l’exécution de l’algorithme aboutit à R0 = [−k]P qui n’est
pas le résultat attendu. Cependant, un effet est produit lors de la reconstruction de la
coordonnée Z. En effet, la fonction XYcoZ-recoverZ reconstruit la coordonnée partagée
des points R0 et R1 , en utilisant l’invariant qui apparaît après le calcul de R0 − R1 dans
la fonction XYcoZ-ADDC. Ce point est utilisé dans l’équation (3.1) sous l’hypothèse qu’il
s’agisse de l’invariant attendu qui est P . Dans la situation où le nombre de bits nuls
est impair avant le premier bit à 1, les deux points R0 et R1 sont tous deux changés
en leur opposé, donc la valeur utilisée à la place de l’invariant est −P . Par conséquent,
la coordonnée reconstruite de [−k]P en fin d’algorithme est −Z. En notant (x, y) la
représentation affine de ce point et (X : Y : Z) celle en coordonnée projective Jacobienne
complète, alors sa forme affine sera calculée comme
!
X Y
, = (x, −y) = [k]P.
(−Z) (−Z)3
2
• kj vaut 1, donc le résultat de l’étape est (R0 , R1 ) = (O, P ) ; ainsi les bits de poids fort
valent λq pour un entier λ > 0 impair (pour des raisons de parité), donc
Exceptions avec les formules Jacobiennes XYcoZ. Par rapport aux formules utilisant
les coordonnées complètes, les formules XYcoZ ont davantage d’exceptions, notamment
toutes celles des équations (3.4) et (3.5).
Il y a également d’autres points exceptionnels en plus du point à l’infini en entrée
d’algorithme. Cela est dû à la récupération de la coordonnée manquante Z à la fin de la
multiplication scalaire. En effet, la formule de l’équation
√ (3.1) requiert que le point P n’ait
pas de coordonnée nulle : donc les points (0, ± b) sont exceptionnels pour les courbes
elliptiques ayant de tels points.
Exceptions avec les formules projectives XZ. Les seules exceptions avec ces formules
ont lieu lors de la récupération de la coordonnée y de la sortie (si celle-ci est nécessaire).
Cela se produit alors lorsque R0 ou R1 est le point à l’infini après la dernière itération,
donc lorsque k mod q vaut 0 ou q − 1.
34 Chapitre 3 Multiplication scalaire et exceptions
Réencodage de Booth. Cet algorithme est une variante qui utilise la négation de
point en passant par le réencodage des fenêtres en une valeur relative : chaque fenêtre
est formée à partir de w + 1 bits consécutifs et convertie en entier dans l’intervalle
[−2w−1 , 2w−1 ]. Cette méthode est basée sur le réencodage de Booth [Boo51] et est donnée
dans l’algorithme 7.
où les bits ki valent 0 pour i = −1 ou i ≥ n. On peut remarquer que chaque fenêtre est
composée d’un bit de la fenêtre qui précède et celle qui suit. L’algorithme de multiplication
scalaire traite chaque fenêtre l’une après l’autre, dont l’ordre est généralement de la gauche
vers la droite comme dans l’algorithme 8 (un exemple de la droite vers la gauche est
donné dans la section 4.1.4).
Cependant, cet encodage n’empêche pas les fenêtres nulles. En effet, les valeurs 0 et
2w+1
−1 sont toutes les deux converties vers la valeur 0, donc il y a un nombre conséquent
de scalaires provoquant l’exception de l’addition avec le point à l’infini.
Il est également possible que l’exception d’égalité se produise au cours de l’exécution,
nécessitant l’utilisation des formules de doublement.
Proposition 1. Soit k un scalaire tel que 0 < k < q. Le cas de l’égalité dans l’addition
de la ligne 5 de l’algorithme 8 (en dehors de l’égalité avec le point à l’infini) ne peut se
produire qu’au cours de la dernière itération pour le scalaire k = q − 2(q mod 2w ) lorsque
q mod 2w ≤ 2w−1 .
Démonstration. Supposons que l’égalité R = [(−1)s0 d0 ]P est vraie lors de la dernière
itération, nécessitant un doublement de point en place de l’addition. Cela signifie que
k ≡ (−1)s0 2d0 mod q. Si s0 vaut 0, alors cela devient l’égalité k = 2d0 , mais d’après
l’encodage on obtiendrait d0 = k mod 2w , et on en déduit que k = d0 = 0. Maintenant,
si s0 vaut 1, alors on obtiendrait l’égalité k = q − 2d0 . Il faut alors que la dernière fenêtre
réencodée de q − 2d0 soit −d0 . Cela se produit si q mod 2w est un entier inférieur ou
égal à 2w−1 et le scalaire correspond à k = q − 2(q mod 2w ). En effet, la fenêtre avant
l’encodage est 2w+1 − 2(q mod 2w ), et est plus grand que 2w , donc l’encodage donne
d0 = q mod 2w et s0 = 1. Par conséquent, on a k = q − 2d0 et l’exception d’égalité
apparaît lors de la dernière addition de points.
Il reste à montrer que l’égalité ne peut arriver dans un tour précédent. Soit j tel que
1 ≤ j ≤ m − 2 et R = [(−1)sj dj ]P , alors on a
m−1
(−1)sj dj ≡ (−1)si di 2w(i−j)
X
mod q,
i=j+1
d’où la relation
j−1
(−1)si di 2iw + (−1)sj dj 2iw+1
X
k≡ mod q.
i=0
L’expression de droite peut être prouvée inférieure à q en valeur absolue. Si elle est
négative alors on aurait
j−1
(−1)si di 2wl + (−1)sj dj 2wj+1 ,
X
k=q+
i=0
donc k ≡ 1+d0 mod 2, mais on a aussi k ≡ d0 mod 2, donc c’est impossible. Au contraire,
si l’expression est positive alors
j−1
2iw (−1)si di + (−1)sj 2jw+1 ,
X
k=
i=0
Table 3.3 : Scalaires exceptionnels pour la multiplication scalaire fenêtrée avec le réencodage de
Booth.
Courbe 3 4 5 6 7
secp224r1 q − 122
secp256r1 q−1 q−2 q − 34
secp521r1 q−2 q − 18 q − 18 q − 18
Méthode comb avec réencodage relatif impair. Cet algorithme est une variante de
la méthode comb, où chaque fenêtre est codée telle quelle est toujours impaire et peut être
négative. L’encodage est une variante de celui proposée dans [HPB04] et est notamment
utilisé par Mbed TLS (voir section 3.4.5).
Un inconvénient est qu’il est nécessaire que le scalaire en entrée k soit impair, car
la première fenêtre comb doit être impaire et contient le bit de poids faible de k. Mais
si k est pair, alors q − k est impair, donc cela peut être géré avec précaution avec une
sélection conditionnelle sécurisée au début de l’algorithme. Pour la suite de cette partie
on suppose que k est impair et dans l’intervalle [1, q].
Le découpage du scalaire k en fenêtres comb peut être vu ci-dessous :
La première fenêtre K[0] est impaire, et la méthode suivante encode les suivantes en
valeur impaire. Supposons que les fenêtres K[j] sont impaires pour 0 ≤ j ≤ i − 1. Si la
fenêtre K[i] est paire, alors on ajoute les bits représentant K[i − 1] à ceux représentant
K[i] bit par bit. Les retenues sont sauvegardées pour chacune des w positions, et la fenêtre
K[i − 1] est changée en −K[i − 1]. Les retenues sont ajoutées à la fenêtre K[i + 1]. Cette
opération signifie que K[i − 1] + 2K[i] est changé en −K[i − 1] + 2(K[i − 1] + K[i])
dans l’équation (3.3.2) ce qui n’en change pas la valeur. Les retenues se propagent jusqu’à
atteindre une nouvelle fenêtre K[m] qui est positive.
En notant K 0 [i] les valeurs des nouvelles fenêtres comb et si un indicateur du signe
(avec 0 pour positif et 1 pour négatif), le scalaire réencodé est
m
(−1)si K 0 [i]2i ,
X
k=
i=0
8: R ← Pdm
9: pour i ← m − 1 à 0 faire
10: R ← [2]R
11: R ← R + (−1)si Pdi
12: si k est pair alors
13: y(R) ← −y(R)
retourner R
La suite est dédiée à la preuve que les exceptions des formules pour coordonnées
Jacobiennes ne peuvent se produire que sous certaines conditions assez restrictives.
Démonstration. Pour simplifier les notations, le signe des fenêtres est inclus directement
dans la notation Ci = (−1)si K 0 [i]. On note M0 et M1 les valeurs telles que k = M0 +2j M1
où M0 = j−1 i=0 Ci 2 et M1 = . Les deux bornes suivantes sont utiles pour la
P i Pm i−j
i=j Ci 2
preuve :
1 ≤ |Ci | < 2(w−1)m+1 et 2(m−1)w < q < 2mw .
Apparition du point à l’infini dans une itération. Supposons que j ≥ 1 et que le résultat
de l’addition au cours de cette itération est le point à l’infini. Cela signifie qu’on a
l’égalité R = −[Cj ]P , ce qui donne la relation M1 ≡ 0 mod q, ainsi que la majoration
|M1 | < 2mw−j+2 .
Si j ≥ w +2, cette majoration devient |M1 | < q, donc M1 est nul, ce qui est impossible
car M1 est impair. Maintenant supposons que j < w + 2. On a k ≡ M0 mod q et la
majoration |M0 | < 2(w−1)m+w+3 . Vu qu’on a supposé que m ≥ 2w + 5, alors on obtient
|M0 | < q. Alors soit k = M0 ce qui implique que M1 est nul, soit k = M0 + q ce qui est
impossible pour des raisons de parité.
Le résultat de l’addition ne peut donc pas être le point à l’infini, excepté lors de la
dernière itération, ce qui ne peut arriver que si le scalaire en entrée est q, ce qui serait le
résultat attendu.
3.4. Vue d’ensemble des bibliothèques 39
Cas de l’égalité dans la dernière itération. Avant l’addition dans la dernière itération de
la boucle, on a R = [ m i=1 Ci 2 ]P et ne peut être le point à l’infini comme il vient d’être
i
P
montré ci-dessus. La seule exception serait le cas où R = [C0 ]P , et donc k ≡ 2C0 mod q.
Comme m est suffisamment large, on a |2C0 | < q, alors soit k = 2C0 ou soit k =
q + 2C0 . Le premier cas est impossible puisque k est impair. Dans le second, C0 est négatif,
donc la fenêtre non encodée K[1] est paire selon le procédé d’encodage : le second bit de
poids faible k1 vaut 0. Ainsi on a k ≡ 1 mod 4, et on en déduit que q ≡ 3 mod 4.
Si l’ordre q satisfait cette condition, il est possible qu’un scalaire produise l’exception
au cours de la dernière itération.
Cas de l’égalité dans une précédente itération. Supposons que l’égalité se produise dans
une boucle précédente, c’est-à-dire que R = [Cj ]P pour un valeur j ≥ 1, et donne la
relation M1 ≡ 2Cj mod q. On obtient la borne |M1 − 2Cj | < 2mw−j+2 à partir de celles
sur Ci et q.
Si j ≥ w + 2, alors on a |M1 − 2Cj | < q, et donc M1 = 2Cj ce qui est impossible pour
des raisons de parité. Maintenant supposons j < w + 2. On a k ≡ M0 + 2j+1 Cj mod q,
et la borne |M0 + 2j+1 Cj | < 2(w−1)m+w+5 . Comme il a été supposé que m ≥ 2w + 5, on
a donc |M0 + 2j+1 Cj | < q. Alors soit k = M0 + 2j+1 Cj qui implique l’égalité M1 = 2Cj ,
ou soit k = M0 + 2j+1 Cj + q, ce qui est impossible dans les deux cas pour cause de
parité.
2. https://www.openssl.org/source/.
40 Chapitre 3 Multiplication scalaire et exceptions
Table 3.4 : Vue d’ensemble des algorithmes et formules pour la multiplication scalaire dans les
bibliothèques cryptographiques.
Par défaut, l’algorithme est Montgomery ladder avec les formules projectives homo-
gènes vues en section 3.1.4, ainsi que la méthode de bourrage. D’après le tableau 3.2 les
scalaires 0 et q − 1 produisent une exception pour la reconstruction de la coordonnée
affine y et ce cas est géré par des branchements conditionnels.
Les courbes du NIST secp224r1, secp256r1 et secp521r1 possèdent une implé-
mentation spécifique et optimisée pour une architecture 64 bits. Celles-ci utilisent la
méthode comb avec w = 4 lorsque le point en entrée est fixe, et la méthode fenêtrée avec
rééencodage de Booth et w = 5 lorsque le point d’entrée est variable. Dans les deux cas,
l’exception liée aux fenêtres nulles est gérée avec une addition factice de points, dont
les conséquences pour la sécurité est abordée dans le chapitre 4. Quant à l’exception
liée au cas d’égalité qui ne peut intervenir que dans la dernière itération de la boucle
avec le réencodage de Booth, on peut noter que le choix de fenêtre implique que cela
ne peut jamais se produire pour les courbes secp224r1 et secp256r1. Par contre le
scalaire q − 18 produit l’exception pour la courbe secp521r1 et cela est attesté par les
commentaires du code source 3 (voir listing 3.1).
La courbe secp256r1 possède également une implémentation spécifique supplémen-
taire utilisée par défaut (nécessite une option à la compilation pour désactiver). Elle est
issue des travaux présentés dans [GK15] où l’arithmétique modulaire est implémentée
en assembleur et optimisée en tirant profit du nombre premier spécifique qui définit le
corps fini pour cette courbe. La différence principale est lorsque le point d’entrée est fixe,
l’algorithme avec réencodage de Booth est utilisé avec une taille de fenêtre w = 7 et en
traitant les fenêtres dans l’autre sens.
3. https://github.com/openssl/openssl/blob/master/crypto/ec/ecp_nistp521.c.
3.4. Vue d’ensemble des bibliothèques 41
1 if ( points_equal ) {
2 /*
3 * This is obviously not constant - time but it will almost - never happen
4 * for ECDH / ECDSA . The case where it can happen is during scalar - mult
5 * where the intermediate value gets very close to the group order .
6 * Since | o s s l _ e c _ G F p _ n i s t p _ r e c o d e _ s c a l a r _ b i t s | produces signed digits
7 * for the scalar , it ’s possible for the intermediate value to be a small
8 * negative multiple of the base point , and for the final signed digit
9 * to be the same value . We believe that this only occurs for the scalar
10 * 1 fffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
11 * ffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb
12 * 71 e913863f7 , in that case the penultimate intermediate is -9 G and
13 * the final digit is also -9 G . Since this only happens for a single
14 * scalar , the timing leak is irrelevant . ( Any attacker who wanted to
15 * check whether a secret scalar was that exact value , can already do
16 * so .)
17 */
18 point_double ( x3 , y3 , z3 , x1 , y1 , z1 ) ;
19 return ;
20 }
Listing 3.1 : Cas exceptionel d’égalité dans OpenSSL pour la courbe elliptique secp521r1.
Il est conseillé de lire la section 5.3 avant de lire ce paragraphe « danger ». Il y a un cas
exceptionnel supplémentaire qui peut se produire avec la méthode de randomisation. La
méthode de bourrage créé le scalaire kpad = k + εq − 232 où ε vaut 1 ou 2, puis celui-ci est scindé
par une division Euclidienne par un entier m aléatoire de 32 bits :
kpad = am + b
Un premier point R = [am]P est calculé et un second S = [b + 232 ]. Une addition finale R + S
est nécessaire pour obtenir le bon résultat. C’est lors de cette addition qu’une égalité est possible.
Par exemple sur la courbe secp224r1 avec
k = 8816999876 et m = 2267504508.
Listing 3.2 : Mbed TLS sur l’addition de points : le cas (3) est possible malgré le commentaire.
5. https://github.com/ARMmbed/mbedtls/blob/development/library/ecp.c.
3.4. Vue d’ensemble des bibliothèques 43
K[1] = 264 .
La fenêtre K[1] étant paire, elle est remplacée par K[0] + K[1], tandis que K[0] est
remplacée par −K[0]. La dernière addition de points dans l’algorithme est donc
h i
R + −K[0] P = [k]P,
h i
or on a k ≡ −2K[0] mod q donc R = −K[0] P et la fonction de doublement est
nécessaire.
44 Chapitre 3 Multiplication scalaire et exceptions
Additions factices de points
4
Le contenu de ces chapitres est issu des travaux présentés dans [Rus20] et [Rus21a] à
la conférence Symposium sur la sécurité des technologies de l’information et des communi-
cations, éditions 2020 et 2021.
Les additions factices de points sont une réponse à la problématique de la gestion
de certains cas exceptionnels présentés dans le chapitre 3. Les conséquences de l’utilisa-
tion de cette méthode dans des implémentations présentes dans plusieurs bibliothèques
cryptographiques sont abordées dans ce chapitre. Il y a deux contributions :
• D’un côté on présente une attaque par injection de faute ;
• De l’autre une attaque par analyse simple de consommation de courant dans une
implémentation spécifique.
Dans les deux cas, les attaques sont combinées avec une attaque par réseau Euclidien
afin de reconstituer une clé privée dans le contexte de signature ECDSA.
Sommaire
4.1 Additions factices et attaque Safe-Error . . . . . . . . . . . . . . . . . . . . . 46
4.1.1 Principe général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.1.2 Algorithmes fenêtrés et additions factices . . . . . . . . . . . . . . . 47
4.1.3 Montgomery ladder et additions factices . . . . . . . . . . . . . . . . 48
4.1.4 Simulation d’attaque Safe-Error sur l’implémentation efficace de la
courbe secp256r1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.1.5 Simulation d’attaque Safe-Error sur Montgomery ladder . . . . . . . 51
4.2 Additions factices et consommation de courant . . . . . . . . . . . . . . . . . 53
4.2.1 Modèle et étapes de l’attaque . . . . . . . . . . . . . . . . . . . . . . 53
4.2.2 Addition factice dans l’implémentation efficace de secp256r1 . . . . . 54
4.2.3 Simulation de consommation de courant . . . . . . . . . . . . . . . . 55
4.3 À propos des contremesures . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3.1 Formules complètes . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3.2 Encodage non nul pour algorithmes fenêtrés . . . . . . . . . . . . . . 57
4.3.3 Montgomery ladder avec formules spécifiques . . . . . . . . . . . . . 57
45
46 Chapitre 4 Additions factices de points
Modèle et étapes de l’attaque. Pour réaliser cette attaque, il est nécessaire de pouvoir
produire une faute pendant une instruction parmi un ensemble d’opérations potentielle-
ment factices.
La localisation de la faute est importante, mais n’a pas besoin d’être complètement
précise quand les opérations potentiellement factices sont composées de nombreuses
instructions (telles que des calculs sur de grands entiers). De plus, la nature exacte de la
faute n’est pas pertinente tant qu’une erreur a été produite. Ainsi, toute faute aléatoire
transitoire qui produit une erreur calculatoire peut suffire.
Pour cibler ECDSA, l’attaque doit être répétée plusieurs fois quand une même clé pri-
vée est utilisée. Finalement, les valeurs publiques doivent être récupérées par l’attaquant
(clé publique, signatures et messages signés).
Les étapes principales sont résumées ci-dessous :
1. Produire une faute sur une des instructions supposées factices pendant la génération
d’une signature ECDSA ;
2. Récupérer la signature et le message correspondant, vérifier avec la clé publique et
conserver en cas de validité ;
3. Répéter les étapes 1 et 2 jusqu’à ce que le nombre de signatures valides atteint un
quota minimal (quelques dizaines, variable selon les caractéristiques de l’algorithme
et paramètres de la courbes, voir le tableau 2.1) ;
4. Appliquer l’attaque à base de réseau Euclidien pour tenter une reconstruction de la
clé privée à partir des signatures valides ;
5. Si la clé privée n’est pas reconstruite, ajouter des signatures valides à partir de l’étape 1.
L’attaque par réseau Euclidien fonctionne bien si le nombre de signatures est suffisant,
mais il est probable que cela échoue en cas d’une signature injustement incluse.
Cible pour l’injection de faute. On rappelle que dans les méthodes fenêtrées, le
scalaire k est séparé en plusieurs fenêtres d0 , d1 , . . . , où chaque di provient de plusieurs
bits du scalaire. Chaque addition se déroule entre un accumulateur et un point précalculé
sélectionné dans un tableau selon la valeur de la fenêtre.
L’attaque Safe-Error est possible si les conditions suivantes sont remplies :
• Les valeurs di sont calculées à partir de plusieurs bits consécutifs du scalaire et peuvent
être nulles (après encodage s’il y en a un) ;
• L’addition de points dans la boucle principale est factice quand l’un des points repré-
sente le point à l’infini.
La seconde condition est la conséquence de l’exception du point à l’infini dans les formules.
Cela se passe lorsqu’une des fenêtre di vaut zéro, d’où la première condition.
L’attaque Safe-Error consiste à cibler la dernière addition de points dans la phase
d’évaluation de l’algorithme. Il y a deux raisons de faire ce choix :
48 Chapitre 4 Additions factices de points
1. Elle est liée soit aux bits de poids fort, soit au bits de poids faible du scalaire, ce qui
est important pour l’attaque par réseau Euclidien ;
2. Elle se déroule entre un point qui dépend de toutes les fenêtres précédentes et un
point qui dépend uniquement de la dernière, donc une addition factice de points est
hautement probable d’être la conséquence de la dernière fenêtre valant zéro.
Enfin, on note en particulier que les instructions à cibler dans la dernière addition
doivent être liées au calcul de la coordonnée x de la sortie, vu que seule cette coordonnée
est utilisée dans une génération de signature ECDSA.
R0 R1
[k]P
b [kb + 1]P
×2 k2 = 0
[2k]P
b [2kb + 1]P
×2 k1 = 0
[4k]P
b [4kb + 1]P
×2 k0 = 0
Q = [8k]P
b [8kb + 1]P
Figure 4.1 : Additions factices implicites dans Montgomery ladder (les quatre dernières valeurs
de R1 n’ont pas d’influence sur le résultat final).
• Si une faute sur le doublement de point pendant le traitement du bit ki n’a pas d’effet,
alors cela révèle que (ki , ki−1 , . . . , k0 )2 = (1, 0, . . . , 0)2 ;
• Si une faute sur l’addition de point pendant le traitement du bit ki n’a pas d’effet,
alors cela révèle que (ki , ki−1 , . . . , k0 )2 = (0, 0, . . . , 0)2 .
Dans le cas où les formules projective XZ sont utilisées, le point R1 est nécessaire
dans la reconstruction de la coordonnée affine y du point de sortie, mais celle-ci n’est
généralement pas utilisée dans les primitives cryptographiques telles que ECDSA. Une
faute pourrait tout de même être détectée par une validation de point.
Pour les formules XYcoZ, une perturbation de n’importe quelle formule aura un
impact à la fois sur R0 et R1 , et empêche une reconstruction correcte de la coordonnée
projective Z, qui est nécessaire pour obtenir la forme affine. Ces formules peuvent être
considérées comme étant immunes face à une attaque Safe-Error.
Listing 4.1 : Simulation d’attaque Safe-Error sur OpenSSL pendant une génération de signature
ECDSA (implémentation efficace de secp256r1).
Reconstruction de la clé. L’attaque produit une signature valide lors d’une addition
factice de points et cela arrive en moyenne toutes les 25 = 32 signatures. D’après le
tableau 2.1, 54 signatures sont suffisantes dans la moitié des cas pour reconstruire la clé
privée avec un réseau Euclidien, donc on s’attend à devoir effectuer plus de 1700 fautes.
Il a été choisi de simuler la faute sur 2000 signatures. Seules 75 sont valides ce qui
est cohérent avec ce qui est attendu. La méthode pour résoudre le problème HNP du
chapitre 2 est appliquée avec les signatures valides correspondant au cas où les bits de
poids fort du nonce sont connus.
La clé privée a été reconstruite avec les 55 premières signatures valides.
Listing 4.2 : Simulation d’attaque C Safe-Error sur OpenSSL pendant une génération de signature
ECDSA (Montgomery ladder).
4.2. Additions factices et consommation de courant 53
Remarque 5. Lorsque la seconde fenêtre d1 est nulle, cela signifie que (x2 , y2 ) = (0, 0) et
que l’addition de points est aussi factice. Cependant, seules quatre opérations mettent en
jeu un opérande nul (deux multiplications et deux soustractions) sur les 18 opérations
arithmétiques. Il est donc attendu que ce cas soit plus difficile à distinguer des autres
situations, et surtout ne pas être confondu avec le cas d0 = 0.
Une dernière remarque est que pour que l’accumulateur soit (0, 0, 0) pendant le
traitement de la fenêtre di , il serait nécessaire que toutes les précédentes fenêtres soient
nulles. Cela arrive seulement pour très peu de scalaires : d0 est nul si les 7 bits de poids
4.2. Additions factices et consommation de courant 55
faible sont nuls, mais pour que d1 le soit aussi, il faudrait que les 7 bits suivants le soient
aussi, et ainsi de suite. D’où l’intérêt de se focaliser sur la première addition.
https://github.com/orangecertcc/ecdummyrpa.
Listing 4.3 : Ligne de commande pour capturer la trace mémoire avec l’outil TracerGrind.
Ensuite, le modèle du poids de Hamming a été appliqué sur ces valeurs. Un exemple de
trace est donnée dans la figure 4.2.
scalar multiplication
Simulated power consumption
125
100
75
50
25
0
1.845 1.850 1.855 1.860
1e6
Time
Figure 4.2 : Simulation de consommation de courant pendant la génération d’une signature avec
OpenSSL sur l’implémentation efficace de la courbe secp256r1.
Analyse. La simulation a été réalisée pour obtenir 6000 traces. Dans cette configuration
précise, la partie relative à la première addition est facile à extraire car elle est toujours
située dans la même position. Dans la figure 4.3 sont données deux traces représentant
les quatre premières additions au cours de la génération de signature.
Comme on peut le remarquer, la première addition de points dans la second trace a
un creux considérablement plus bas que les autres, ce qui indique qu’une addition factice
de points a eu lieu (plus particulièrement, les 7 bits de poids faible du nonce sont nuls
comme il est expliqué ci-dessous).
1. https://github.com/SideChannelMarvels/Tracer.
56 Chapitre 4 Additions factices de points
Time
Figure 4.3 : Zoom sur le début de multiplication scalaire de deux générations de signatures
avec l’implémentation efficace de la courbe secp256r1 dans OpenSSL (en évidence : la première
addition de points).
La classification des traces en deux catégories peut être réalisée à partir de la moyenne
sur la partie concernée. Une autre façon est de laisser un outil faire ce classement lui-
même, comme par exemple la bibliothèque Python Scikit-learn [SCIKIT11]. Dans cette
situation, la classe GaussianMixture de l’outil convient très bien. Il parvient à identifier
un ensemble de 50 traces parmi les 6000 et ce ratio est cohérent avec la probabilité que
les 7 bits de poids faible d’un nonce valent simultanément 0.
Avec cette quantité de bits par nonce connus, on s’attend à ce que la clé privée
puisse être reconstruire avec un nombre de signatures compris entre 36 et 40 d’après le
tableau 2.1. Dans ce cas précis, la clé a été retrouvée avec les 38 premières signatures.
Sommaire
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2 Fuite avec la scission Euclidienne . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2.2 Variation de la taille du quotient . . . . . . . . . . . . . . . . . . . . 61
5.2.3 Approximation du scalaire . . . . . . . . . . . . . . . . . . . . . . . . 62
5.3 Scission Euclidienne dans CoreCrypto . . . . . . . . . . . . . . . . . . . . . . 63
5.3.1 Multiplication scalaire dans CoreCrypto . . . . . . . . . . . . . . . . 63
5.3.2 Exponentiation modulaire dans CoreCrypto . . . . . . . . . . . . . . 65
5.4 Scission Euclidienne avec l’algorithme de Strauss-Shamir . . . . . . . . . . . 70
5.4.1 Description de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . 70
5.4.2 Vulnérabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.5 Contremesures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.5.1 Protection pour Strauss-Shamir . . . . . . . . . . . . . . . . . . . . . 71
5.5.2 Protection pour l’exponentiation modulaire . . . . . . . . . . . . . . 72
5.5.3 Protection pour la multiplication scalaire . . . . . . . . . . . . . . . . 73
5.6 Exploitation de la vulnérabilité . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.6.1 Exposant ou scalaire fixe . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.6.2 Exposant ou scalaire éphémère . . . . . . . . . . . . . . . . . . . . . 74
5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
59
60 Chapitre 5 Scission Euclidienne du scalaire
5.1 Introduction
Les attaques mesurant le temps d’exécution ou par analyse de consommation de
courant peuvent être évitées par l’utilisation d’algorithmes au comportement régulier
par un flot d’opération indépendant du secret. Dans le cas où le scalaire est fixe (tel que
dans les protocoles décrits en chapitre 7), les algorithmes de multiplication scalaire ou
plus généralement d’exponentiation sont vulnérables à des attaques plus complexes qui
nécessitent la capture de plusieurs traces d’exécution [KJJ99].
Des mécanismes basés sur la randomisation furent introduits pour protéger contre
ces attaques. Un des plus connus est l’ajout au scalaire d’un multiple de l’ordre du
groupe [Cor99], tandis que d’autres consistent à scinder le scalaire en plusieurs mor-
ceaux [CJ01, TB02, CJ03]. Cependant, ce type de contremesures ne protège pas nécessai-
rement contre toutes les attaques. Par exemple la technique de randomisation qui ajoute
un multiple de l’ordre du groupe ne masque pas entièrement le scalaire pour certaines
courbes elliptiques dû à la nature particulière de l’ordre du groupe [FRV14, RIL19]. En ce
qui concerne les méthodes de scission du scalaire il a été montré une corrélation entre les
morceaux pour la version additive [MV06] et une attaque par profilage a été appliquée
sur la version Euclidienne [GRV16].
Ce chapitre se concentre sur la méthode de scission Euclidienne.
L’organisation du chapitre est la suivante. La méthode de scission Euclidienne est
présentée dans la section 5.2 avec la variation que celle-ci introduit qui peut mener à
une vulnérabilité. Ensuite, la section 5.3 décrit l’utilisation de cette méthode dans la
bibliothèque d’Apple pour la multiplication scalaire sur des courbes elliptiques, ainsi
que dans l’exponentiation modulaire, avec des éléments de preuves que cette variation
est observable par canaux auxiliaires. La section 5.4 analyse la vulnérabilité lorsque la
scission Euclidienne est utilisée avec l’algorithme de double multiplication scalaire de
Strauss-Shamir. Enfin, les contremesures sont discutées dans la section 5.5.
5.2.1 Description
Soit k un scalaire de n bits dont la représentation binaire est
n−1
ki 2i .
X
k=
i=0
Cette valeur est randomisée par une valeur aléatoire m de λ bits en effectuant la division
Euclidienne de k by m : le quotient est a = bk/mc et le reste est b = k mod m. Ainsi, la
multiplication scalaire [k]P est réécrite comme
Cette méthode est la scission Euclidienne et fut introduite dans [CJ03] comme une
alternative à d’autres méthodes de masquage. Les auteurs proposent de calculer simul-
tanément la multiplication scalaire avec le quotient a et le reste b par l’algorithme de
Strauss-Shamir [Coh+05, algorithme 9.23] pour des raisons d’efficacité.
de a est n − λ + 1. Dans ce cas il y a β + 1 valeurs possibles pour m sur les 2λ−1 , d’où la
probabilité.
L’autre cas est lorsque m > 2λ−1 + β, alors on a
2n−λ (2λ−1 + β + 1) − b
a< ≤ 2n−λ ,
m
et la longueur en bit de a est n − λ.
La conséquence est que si m est généré aléatoirement de façon uniforme et de longueur
en bits λ, alors la probabilité que le quotient fasse n − λ + 1 bits dépend de quel intervalle
I(n, λ, β) contient le scalaire k. C’est illustré dans la figure 5.1 avec λ = 4 pour mettre
en évidence la fonction en escalier, et λ = 32 (le cas de la bibliothèque d’Apple présenté
dans les sections suivantes). Dans ce second cas, les intervalles sont petits et cela est
proche d’une corrélation linéaire entre scalaire et probabilité.
62 Chapitre 5 Scission Euclidienne du scalaire
1 1
probabilité
probabilité
0 0
n−1
2 2n 2n−1 2n
scalaire scalaire
Figure 5.1 : Corrélation entre un scalaire de n bits et la probabilité que la longueur en bits du
quotient de la division Euclidienne avec un diviseur de λ bits est n − λ + 1 (à gauche : λ = 4, à
droite : λ = 32).
1 // Main loop
2 // Assumes that MSB is set : d_dbitlen -1 is == 1
3 // This algo does not read it to verify it is indeed one .
4 for ( size_t i = dbitlen - 2; i > 0; --i ) {
5 dbit ^= ccn_bit (d , i ) ;
6 // Use buffer copy instead of pointer handling to prevent cache attacks
7 cond_swap_points (n , dbit , R0 , R1 ) ;
8 XYCZaddC_ws ( ws , cp , R0 , R1 ) ;
9 XYCZadd_ws ( ws , cp , R0 , R1 ) ;
10 // Per Montgomery Ladder :
11 // Invariably , R1 - R0 = P at this point of the loop
12 dbit = ccn_bit (d , i ) ;
13 }
1 // a . S
2 cc_ requir e_acti on ( ccn_is_zero (n , ccec_point_x (S , cp ) ) == 0 , errOut , status =
CCERR_PARAMETER ) ;
3 dbitlen = ccn_bitlen ( n + 1 , dtmp1 ) ;
4 status = ccec_mult_ws ( ws , cp , Q , dtmp1 , dbitlen , S ) ;
5 cc_require ( status == 0 , errOut ) ;
6
7 // mask . a . S
8 cc_ requir e_acti on ( ccn_is_zero (n , ccec_point_x (Q , cp ) ) == 0 , errOut , status =
CCERR_PARAMETER ) ;
9 dbitlen = SCA_MASK_BITSIZE ;
10 status = ccec_mult_ws ( ws , cp , R , & mask , dbitlen , Q ) ;
11 cc_require ( status == 0 , errOut ) ;
12
13 // b . S
14 dbitlen = SCA_MASK_BITSIZE + 1; // equivalent to b +(2* SCA_MASK_MSBIT )
15 status = ccec_mult_ws ( ws , cp , Q , &b , dbitlen , S ) ;
16 cc_require ( status == 0 , errOut ) ;
scalaires. Cela a été répétée 50000 fois pour chacun d’entre eux et les résultats sont
donnés dans la figure 5.2, où les scalaires sont rangés dans l’ordre croissant.
Deux temps d’exécutions sont observables avec une différence de proportion entre
les pics, avec un second pic plus élevé pour les scalaires les plus grands. Cela est cohérent
avec la description donnée ci-dessus.
(a) log2 (k) ≈ 254.060 (b) log2 (k) ≈ 254.477 (c) log2 (k) ≈ 255.039
(d) log2 (k) ≈ 255.353 (e) log2 (k) ≈ 255.720 (f) log2 (k) ≈ 255.924
Figure 5.2 : Temps d’exécution pour 50000 multiplications scalaires sur la courbe secp256r1
avec un scalaire fixe sur CoreCrypto.
peuvent se produire pour différentes valeurs de m, mais il n’est pas toujours possible de
distinguer les deux cas avec l’algorithme SSMA. En effet, si n − λ est impair alors
& ' & '
n−λ n−λ+1 n−λ+1
= = ,
2 2 2
donc la longueur en bits du quotient ne fuite pas, mais n peut malgré tout être déduit de
la formule. Au contraire, si n − λ est pair, alors
& ' & '
n−λ+1 n−λ
= + 1, (5.3)
2 2
donc l’algorithme est exécuté avec un nombre différent d’itérations pour chacune des
valeurs possibles pour la taille du quotient en bits (et la longueur en bits n de l’exposant
peut être déduit aussi). Malgré cela, il est nécessaire d’effectuer plusieurs observations de
l’exponentiation pour être certain d’être dans l’un ou l’autre cas. Par conséquent, une
seule mesure n’est pas suffisante pour connaître exactement la valeur n.
La variation liée au quotient peut être révélée en comptant le nombre de motifs sur
une trace de consommation de courant. Le Raspberry Pi Zero a été sélectionné car il
offre un bon compromis entre les performances de calculs, la complexité matérielle, et
la configuration de l’alimentation électrique. Premièrement, pour obtenir une capacité
constante de calcul et minimiser le bruit sur la ligne électrique, la fréquence processeur a
été figée à 700 MHz et la sortie HDMI/TV désactivée (ce qui a permis d’avoir des traces
plus nettes). En partant d’une nouvelle installation du Raspberry Pi OS (auparavant nommé
Raspbian car basé sur la distribution GNU/Linux Debian), la bibliothèque CoreCrypto a
été compilée à partir des sources. Ensuite, un programme écrit en C bascule la ligne GPIO
du Raspberry Pi Zero avant et après l’exécution de la fonction ccdh_power_blinded.
Ainsi, l’oscilloscope peut mesurer la consommation de courant avec une première
sonde connectée en série à une résistance (3,3 Ohms dans notre cas) sur la ligne à 5 V.
Ensuite il peut déclencher le début du calcul avec une seconde sonde connectée à la ligne
GPIO.
Finalement, le processus a été automatisé avec un script Python pour lancer le calcul
sur le Raspberry Pi Zero avec la console série UART (moins de perturbations comparé à une
connexion USB ou une console SSH/telnet), et télécharger les données de l’oscilloscope
après chaque exécution par une console TCP à distance.
Le groupe de 2048 bits donné dans RFC 5054 [Tay+07] a été choisi pour cette expéri-
mentation, avec l’exposant
x = d3afa905fededc64bc907b809da3dcb
(5.4)
484763c25c3b4728bb081a97cf9f0a5
donné ici sous forme hexadécimale. Pour chaque exécution, le générateur pseudo-aléatoire
de CoreCrypto utilisé dans la fonction ccdh_power_blinded a été initialisé avec une
graine aléatoire (pour les techniques de randomisation). L’ensemble a été réalisé 10000
fois.
Deux échantillons de traces sont donnés dans la figure 5.5 où l’on peut voir que la
majeure partie de la trace correspond à l’exponentiation avec le quotient (des lignes
68 Chapitre 5 Scission Euclidienne du scalaire
Probe 1 Probe 2
(serial console)
test program
U=5V
control
R=3.3
DC GPIOs UART
in
Raspberry Pi Zero
140
120
100
Power consumption
80
140
120
100
80
100000 150000 200000 250000 300000 350000
Measured sample
Figure 5.5 : Traces de deux exponentiations masqués avec la scission Euclidienne avec un exposant
identique (les lignes verticales indiquent le début des exponentiations avec le quotient, le diviseur
et le reste).
precomp.
120
Power consumption
precomp.
120
Figure 5.6 : Zoom sur la fin de l’exponentiation avec le quotient, et le début de celle avec le
diviseur aléatoire.
70 Chapitre 5 Scission Euclidienne du scalaire
importantes, mais cette méthode s’est révélée suffisamment efficace : 6099 traces sur 9356
ont été identifiés comme appartenant au groupe « 109 ». Ainsi, la fréquence observée est
environ 0,6519 ce qui est proche de la probabilité cherchée qui vaut environ 0,6538.
En utilisant l’intervalle de Wilson pour l’approximation avec un niveau de confiance
de 95 %, on détermine que l’exposant x est situé dans un intervalle de largeur environ
2241,3049 et qui contient bien l’exposant donné dans l’équation (5.4).
5.4.2 Vulnérabilité
Pour exploiter la fuite et réaliser l’approximation, il est nécessaire de connaître les
longueurs en bits de k, de a et et de m. On peut supposer que la longueur λ de m est
connue (elle peut fuiter de la multiplication scalaire [m]P ). Cependant, dans la double
multiplication scalaire la longueur d := dlog2 (a)e du quotient a peut être masquée par
e := dlog2 (b)e, celle du reste b. En effet, le nombre d’itérations de la boucle dépend de
` = max(d, e), et e peut être plus grand que d.
Malgré cela, il peut être possible dans certains cas d’observer la variation sur la
longueur en bits du quotient. Si un bourrage est appliqué sur le scalaire k, alors sa
longueur n devient fixe et connue et il ne reste qu’à connaître d. Dans le cas où λ est
5.5. Contremesures 71
5.5 Contremesures
Dans cette section, des techniques sont proposées pour éviter la fuite avec la scission
Euclidienne, ainsi que les mesures proposées par Apple dans le correctif déployé.
Le correctif d’Apple. Une analyse de la mise à jour effectuée par Apple montre que la
solution apportée est l’utilisation de l’algorithme Montgomery ladder en place de SSMA.
1 ccn_set (n , r1 , s ) ;
2 ccn_seti (n , r , 1) ;
3 cczp_to_ws ( ws , zp , r , r ) ;
4
5 cc_unit ebit = 0;
6 for ( int bit = ( int ) ebitlen - 1; bit >= 0; -- bit ) {
7 ebit ^= ccn_bit (e , bit ) ;
8 ccn_cond_swap (n , ebit , r , r1 ) ;
9 cczp_mul_ws ( ws , zp , r1 , r , r1 ) ;
10 cczp_sqr_ws ( ws , zp , r , r ) ;
11 ebit = ccn_bit (e , bit ) ;
12 }
13
14 // Might have to swap again .
15 ccn_cond_swap (n , ebit , r , r1 ) ;
Listing 5.3 : Extrait de l’algorithme Montgomery ladder dans la mise à jour de CoreCrypto.
Contrairement aux versions données dans la section 3.2, l’algorithme est initialisé
par le couple (1, g) de telle sorte que si les premiers bits de l’exposant sont nuls alors une
étape de l’algorithme ne change pas l’état du couple :
Cependant, cela implique une multiplication par 1 et une élévation au carré de 1, ce qui
pourrait être facile à détecter sur une trace comme il a été montré sur les captures dans
la section 5.3.2. Pour éviter cet écueil, l’arithmetique modulaire a été remplacée par la
représentation de Montgomery, donc l’unité n’est plus représentée par une valeur de
poids de Hamming faible. Cela est réalisé avec la fonction cczp_to_ws avant la boucle
dans le listing 5.3.
5.7 Conclusion
Dans ce chapitre on a présenté une vulnérabilité sur la méthode de randomisation par
division Euclidienne d’un scalaire (ou d’un exposant) avant une multiplication scalaire
(ou une exponentiation modulaire). Elle introduit une variation qui peut être observée
par canaux auxiliaires pendant l’exécution et mène à l’approximation d’un scalaire fixe si
un grand nombre d’observations peut être effectué.
La méthode fut originellement proposée pour être utilisée avec la double multiplication
scalaire de Strauss-Shamir et on montre que la vulnérabilité reste malgré tout possible.
5.7. Conclusion 75
Sommaire
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.1.1 Travaux similaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.2 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.2.1 Principe de base d’une attaque DFA . . . . . . . . . . . . . . . . . . . 80
6.2.2 Signature ECDSA avec faute . . . . . . . . . . . . . . . . . . . . . . . 80
6.2.3 Diffie-Hellman statique avec faute . . . . . . . . . . . . . . . . . . . 81
6.3 Attaque DFA sur Montgomery ladder . . . . . . . . . . . . . . . . . . . . . . 82
6.3.1 Impact d’une faute . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.3.2 Doublement ou addition ignorés . . . . . . . . . . . . . . . . . . . . 82
6.3.3 Nouvelle attaque : changement de signe de l’invariant . . . . . . . . 84
6.3.4 DFA avec les formules XZ pour coordonnées projectives . . . . . . . 85
6.3.5 DFA avec les formules XYcoZ pour coordonnées Jacobiennes . . . . 85
6.4 DFA avec randomisation du scalaire . . . . . . . . . . . . . . . . . . . . . . . 87
6.4.1 Randomisation par l’ordre du groupe . . . . . . . . . . . . . . . . . . 87
6.4.2 Randomisation par scission Euclidienne . . . . . . . . . . . . . . . . 89
6.4.3 Randomisation par scission multiplicative . . . . . . . . . . . . . . . 90
6.4.4 Randomisation avec la scission additive . . . . . . . . . . . . . . . . 91
6.5 Évaluation pratique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
6.5.1 Implémentations de Montgomery ladder . . . . . . . . . . . . . . . . 92
6.5.2 Réalisation de la faute . . . . . . . . . . . . . . . . . . . . . . . . . . 93
6.5.3 Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
77
78 Chapitre 6 Attaque en faute différentielle
6.6 Contremesures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.1. Introduction 79
6.1 Introduction
Les premières attaques en faute différentielle, Differential Fault Analysis en anglais
(DFA), ont été introduites sur des algorithmes de chiffrements par blocs [BS97], et sur
RSA [BDL97]. La faute injectée modifie le comportement de l’exécution et résulte en une
sortie erronée. Les effets de la faute sur la sortie sont comparés avec le résultat correct
afin de compromettre la clé secrète.
On s’intéresse à appliquer une attaque DFA sur l’algorithme Montgomery ladder avec
une faute dont l’objectif est de perturber l’échange conditionnel qui a lieu lors de chaque
itération. L’effet de l’usage des formules spécifiques à cet algorithme (les formules XZ et
XYcoZ) est envisagé. On montre ainsi qu’une validation de point ou une vérification de
l’invariant ne sont pas des mesures suffisantes contre cette nouvelle attaque.
Ensuite, on montre que les méthodes de randomisation du scalaire ne protègent
pas contre des attaques DFA lorsque l’aléa généré est trop petit. La première méthode
analysée est la première contremesure de Coron [Cor99] qui ajoute un multiple de l’ordre
du groupe pour masquer le scalaire, tandis que les autres scindent le scalaire en plusieurs
morceaux, soit de façon additive, multiplicative ou par une division Euclidienne [CJ01,
TB02, CJ03].
Les attaques sont considérées dans le contexte de signatures ECDSA ainsi que le cas
d’un scalaire fixe comme par exemple un échange de clé Diffie-Hellman statique. Entre
autre, cela peut être combiné avec une attaque par réseau Euclidien pour reconstituer
une clé privée en suivant les méthodes du chapitre 2.
L’organisation est la suivante. Dans la section 6.2 on introduit le principe de base
d’une attaque DFA et comment elle peut être appliquée dans le cadre de génération de
signatures ECDSA ou dans des échanges Diffie-Hellman statiques. Ensuite, la section 6.3
décrit l’attaque sur l’algorithme Montgomery ladder, puis dans la section 6.4 les méthodes
de randomisation du scalaire et leur vulnérabilité contre une attaque DFA. Une évaluation
pratique de la réalisation de la nouvelle attaque est donnée en section 6.5. Enfin, des
contremesures sont discutées dans la section 6.6.
Dans la même lignée, des attaques DFA telles que la validation de point ne détecte pas
de faute ont été présentées dans [SM09, SM10] sur l’algorithme Montgomery ladder. Les
fautes en questions sont le saut d’une ou plusieurs opérations de l’algorithme de façon à
ce qu’un bit du scalaire ne soit pas traité (dans le premier article), ou par le saut d’une
multiplication ou d’un carré avec RSA (dans le second article, mais adaptable avec les
courbes elliptiques en remplaçant avec le doublement et l’addition de points). À la suite
de la faute, il est possible de retrouver les bits du scalaire traités après (ou avant) que la
faute soit injectée.
La nouvelle attaque présentée dans ce chapitre est analogue aux précédentes sur
Montgomery ladder, avec une faute qui ne fait pas quitter le point de la courbe. Mais elle
partage également des similarités avec l’attaque du changement de signe de [BOS06], car
l’objectif est de changer le signe de l’invariant de boucle implicite de l’algorithme.
6.2 Préliminaires
Dans cette section, on présente le principe d’une attaque DFA et comment elle peut
s’appliquer dans le contexte de signature ECDSA ou d’un échange Diffie-Hellman statique.
Alice Bob
Clé privée : a ∈ [2, q − 2] Clé privée : b ∈ [2, q − 2]
Clé publique : PA = [a]P Clé publique : PB = [b]P
PA , PB
E Q = [a]PB Q = [b]PA
0
Q = [δ1 ]Q − [δ2 ]P
K = KDF(Q0 )
c = EncK (msg)
c
La signature fautée ne permet pas de reconstruire la signature complète (r, s), mais le
point Q, de qui r est dérivé, peut l’être en utilisant le point public du signataire à partir
de la relation de la vérification de signature :
[H(M )s0−1 ]P + [r0 s0−1 ]Ppub = [k]P = Q.
Le point Q0 peut lui aussi être obtenu en relevant l’entier r0 vers un point de la courbe
elliptique. Cependant, la valeur xQ0 a été réduite modulo le nombre premier q. Il a été
montré qu’en dehors de Q0 , il y a au plus quelques points possibles [Bar+16]. Comme le
nombre premier q est généralement le cardinal de la courbe et est très proche de celui du
corps de base, alors il est probable qu’il n’y ait que deux points possibles : Q et Q0 .
Par conséquent, il est possible de récupérer à la fois la sortie correcte et celle erronée,
ce qui est un aspect central d’une attaque en faute différentielle.
exhaustive sur δ1 et δ2 jusqu’à ce que le point erroné Q0 soit trouvé (ce qui est confirmé
lors d’un déchiffrement réussi).
Un cas classique est lorsque δ1 vaut 1 et δ2 sont les bits de poids faible de la clé privée
d’Alice. Dans ce cas, l’attaque peut être répétée de façon itérative pour cibler d’autres
portions du secret jusqu’à ce qu’il soit entièrement reconstruit.
où k = (kj−1 , . . . , k0 )2 sont les bits de poids faible du scalaire traités après la faute.
Cette description générique d’une perturbation facilite l’analyse en fonction du modèle
de faute considéré.
Remarque 7. Dans le cas où la faute a pour effet que l’un des points R0 ou R1 n’est plus sur
la courbe ou perturbe l’application des formules, les additions suivantes ne correspondent
pas à la loi de groupe de la courbe elliptique (mais peut être vue comme une pseudo-
addition). Excepté dans un cas particulier ci-dessous, on examine généralement des
situations où la faute « maintient » les points sur la courbe elliptique.
kj = 0 kj = 1 kj = 0 kj = 1
R0 = [k]P
b R0 = [k]P
b R0 = [k]P
b R0 = [k]P
b
R1 = [kb + 1]P R1 = [kb + 1]P R1 = [kb + 1]P R1 = [kb + 1]P
R0 = [k]P
b R0 = [2kb + 1]P R0 = [2k]P
b R0 = [k]P
b
R1 = [2kb + 1]P R1 = [kb + 1]P R1 = [kb + 1]P R1 = [2kb + 2]P
Figure 6.2 : Une étape de Montgomery ladder avec une opération ignorée (à gauche : doublement
ignoré ; à droite : addition ignorée).
Dans cette partie on note kb = (kn−1 , . . . , kj+1 )2 les bits de poids fort du scalaire
traités avant la faute, en excluant kj .
Si seule l’addition est effectuée lors du traitement du bit kj , alors à l’issue de la boucle
on a R0 = [k]Pb et I = [kb + 1]P lorsque kj vaut 0, ou R0 = [2kb + 1]P et I = [−k]P b
lorsque kj vaut 1 (voir figure 6.2). Donc le résultat final de la multiplication scalaire est
si kj = 0,
b j
[k2 + (kb + 1)k]P
Q0 =
[(2kb + 1)2j − kk]P
b si kj = 1.
Il est ainsi possible d’éliminer la dépendance aux bits de poids fort en calculant une
différence avec les points Q et Q0 :
2
[2j+1 ]Q0 − [2j + k]Q = [k2j − k ]P si kj = 0,
2
j+1 0
− [2j+1 − k]Q = [k − k2j ]P si kj = 1.
[2 ]Q
Une recherche exhaustive sur les bits de poids faible est réalisée jusqu’à obtention de
l’égalité (ou rejet si la faute n’a pas eu l’effet escompté).
La même méthode peut être appliquée dans le cas où c’est l’addition de points qui est
ignorée lors du traitement du bit kj . À l’issue de la multiplication scalaire on obtient :
si kj = 0,
b j
[(2k)2 + (1 − k)k]P
b
0
Q =
b j + (k
[k2 b + 2)k]P si kj = 1.
Les différences ci-dessous entre les points Q et Q0 ne dépendent que des bits de poids
faible du scalaire :
2
[2j+1 ]Q0
− [2j+1 − k]Q = [k ]P si kj = 0,
2
[2j+1 ]Q0 − [2j + k]Q = [2j+1 k − 22j − k ]P si kj = 1.
84 Chapitre 6 Attaque en faute différentielle
Pour simplifier les formules ci-dessous, la notation kb correspond à l’ensemble des bits de
poids fort jusqu’au bit kj inclus.
La valeur R0 pour le traitement du bit suivant est R0 = [kb + 1]P , et l’invariant pour
le restant de la multiplication scalaire est le point I = −P . Ainsi, le résultat final est :
Selon que l’étape j où la faute a eu lieu est plus proche du début ou de la fin, l’une de ces
formules peut être utilisée pour retrouver soit les bits de poids faible dans le premier cas,
soit les bits de poids fort dans le second. Une recherche exhaustive peut être réalisée ou
éventuellement une recherche de logarithme discret dans un intervalle restreint (on peut
facilement isoler k et kb dans chacune des formules).
Bien que ce type de faute ne peut être détecté par une validation de point, une
vérification de l’invariant révèle qu’un mauvais calcul a eu lieu. Mais cela n’est vrai que
pour des formules classiques : dans la suite on étudie le cas des formules spécifiques à
l’algorithme Montgomery ladder où en particulier la vérification de l’invariant ne peut
pas détecter la faute.
Remarque 8. Dans le cas particulier où k = 2j−1 les points Q and Q0 sont égaux, donc la
faute n’a aucun effet.
Étape inconnue. Les équations (6.3) et (6.4) montrent que les points obtenus ne dé-
pendent pas seulement des bits de poids faible ou fort du scalaire secret, mais également
de l’étape où la faute a lieu. Cela peut résulter en plusieurs valeurs candidates si plusieurs
étapes j sont considérées dans l’analyse.
Des choix conservateurs peuvent être faits pour lever l’indéterminée, en perdant
quelques bits du scalaire. Supposons que le logarithme discret d = 2k − 2j du point
différentiel de l’équation (6.3) a été obtenu, mais avec j inconnu. On peut calculer d/2 mod
2i pour un entier i dont on s’attend à être plus petit que j (par exemple 5 pour i alors
que j vaut 10), et ainsi les i bits de poids faible sont récupérés.
Dans le cas où d est négatif, alors le plus petit i tel que d/2 + 2i soit positif peut être
choisi, car k est censé être positif.
6.3. Attaque DFA sur Montgomery ladder 85
La perte de précision n’a pas un impact si important pour une attaque contre ECDSA,
car la méthode à base de réseau Euclidien peut réussir avec quelques bits par nonce
seulement.
kj = 0 kj = 1 kj = 0 kj = 1
R0 = [k]P
b R0 = [k]P
b R0 = [k]P
b R0 = [k]P
b
R1 = [kb + 1]P R1 = [kb + 1]P R1 = [kb + 1]P R1 = [kb + 1]P
XYcoZ-ADDC XYcoZ-ADD
Figure 6.3 : Une étape de Montgomery ladder avec les formules XYcoZ et une opération ignorée
(à gauche : XYcoZ-ADD ignoré ; à droite : XYcoZ-ADDC ignoré).
1. Faire une recherche exhaustive sur µ pour construire une liste de valeurs candidates
pour xQ0 à partir de l’équation (6.6) et l’invariant (xI , yI ) = [µ]P ;
2. Calculer la valeur candidate pour xQ00 à partir de l’équation (6.5) pour chacun des
candidats calculés pour xQ0 .
6.4. DFA avec randomisation du scalaire 87
Dans les deux situations décrites dans la section 6.2, soit la valeur r de la signature pour
ECDSA ou soit un déchiffrement correct pour ECDH statique confirme quelle valeur pour
µ est correcte.
Il n’est pas encore possible à ce moment de savoir si µ correspond à kb ou kb + 1.
Dans le cas de l’attaque contre ECDH, réaliser la faute à nouveau sur une étape quelques
boucles plus loin permet de révéler laquelle des valeurs est correcte (tout en permettant
de continuer à reconstruire le scalaire morceau par morceau). Dans le cas de l’attaque
contre ECDSA, il n’est pas nécessaire de faire la distinction, car µ2j+1 est une bonne
approximation du nonce k :
Changement de signe de l’invariant. Les effets sont similaires au cas des formules
XZ pour l’attaque proposée en section 6.3.3. Les calculs restent valides tant que les points
partagent la même coordonnée projective Z et cette propriété n’est pas changée par
l’attaque. Il ne reste donc qu’à observer l’effet sur la coordonnée Z. Le nouvel invariant
est (xP , −yP ) et d’après la formule (3.1), cela provoque l’apparition d’un facteur −1
dans la coordonnée Z reconstruite pour les points R0 et R1 . Mais lors de la mise sous
forme affine, cela ne modifie que le signe de la coordonnée y (à cause des coordonnées
Jacobiennes). Donc la valeur erronée Q0 obtenue en sortie est un point valide de la courbe
elliptique.
Enfin, comme avec les formules projectives XZ, vérifier l’invariant ne peut pas détecter
la faute. On a R1 − R0 = −P après la faute, et les points sont reconstruits en tant que
R00 = −R0 et R10 = −R1 donc la différence R10 − R00 produit l’invariant d’origine.
Remarque 9. Une façon alternative de voir les choses pour les formules XZ et XYcoZ est
que l’invariant n’est plus le point P , mais seulement sa coordonnée affine x. Comme
celle-ci reste intacte même en cas de changement de signe, cela ne peut être détecté.
donc cela ne change pas le résultat final, mais cela implique un surcoût pour traiter les
bits supplémentaires.
? ?
Notons k ? = kb ? 2j + k , où k sont les j bits de poids faible du scalaire randomisé
?
(et kb ? ses bits de poids fort). On suppose qu’une attaque DFA révèle k (comme dans les
situations de la section précédente).
Attaque contre ECDSA. Dans la section 2.1.1, on a vu qu’il est nécessaire que k soit
plus élevé que λ de façon à encadrer la partie inconnue du scalaire dans un intervalle de
largeur q/2j−λ .
En conséquence l’attaque devient difficile à réaliser lorsque le paramètre λ est élevé
pour retrouver les bits de poids faible. Selon les situations, on peut se ramener à résoudre
un logarithme discret dans un intervalle plus réduit (comme par exemple la situation
de l’attaque présentée en section 6.3.3), qui, au mieux, est de largeur 2j . Dans ce cas un
algorithme tel que pas de bébés – pas de géants ou l’algorithme kangourou de Pollard (voir
section 1.2) dont le coût est O(2j/2 ) peut être utilisé.
Lorsque λ est 20, alors une faute à l’étape j = 24 donne un logarithme discret facile
à calculer et est suffisant pour l’attaque contre ECDSA. Ainsi, le paramètre λ doit être
choisi assez grand pour rendre l’attaque difficile voire impossible à réaliser.
Attaque contre un scalaire fixe. Si une attaque DFA permet de récupérer les bits de
poids faible d’un scalaire randomisé, cela ne donne pas directement ceux de l’original.
Cependant, il est possible de les trouver et de construire de façon itérative les bits
suivants morceaux par morceaux avec des fautes en différentes positions en utilisant
l’algorithme 19.
L’idée est similaire à celle présentée dans [SW15], où elle est appliquée avec des
scalaires randomisés bruités. Tandis que dans le cas présenté ici, on possède un point qui
dépend partiellement d’un scalaire randomisé.
Lorsque le point différentiel dépend des i+w bits de poids faible, calculer un logarithme
discret pour des valeurs de i élevées devient difficile. Cette dépendance est supprimée en
utilisant la connaissance des i bits de poids faible : on teste toutes les valeurs possibles
pour m et pour la bonne valeur le point construit en ligne 3 de l’algorithme 19 ne dépend
que de w bits du scalaire randomisé. À partir de m et de ces bits, on en déduit les w bits
suivant du scalaire d’origine.
Pour chaque position i le coût de l’algorithme dépend du paramètre λ et de la fenêtre w,
soit un coût en O(2λ−1+w/2 ) et doit être répété pour reconstruire k intégralement.
6.4. DFA avec randomisation du scalaire 89
L’inconvénient est que les premiers λ bits de k doivent être connus pour que l’algo-
rithme fonctionne. À partir de plusieurs scalaires randomisés où les λ bits de poids faible
sont obtenus, on peut calculer une liste des valeurs possibles pour k mod 2λ : la bonne
valeur sera à l’intersection des listes. Il pourrait nécessiter de nombreux scalaires randomi-
sés pour réduire le nombre de possibilités. Cependant, l’exécution de l’algorithme 19 avec
une mauvaise valeur pour k mod 2i pourrait ne pas aboutir à un résultat pour produire
le morceau suivant du scalaire, donc il pourrait être rejeté assez rapidement.
[m̃]R
e + [b̃]P = [m]R + [b]P, (6.7)
Le quotient a est retrouvé, donc le scalaire k peut être entièrement reconstruit et vérifié
avec la relation Q = [k]P . Ce cas semble peu probable.
Si b = b̃, on peut déduire de l’équation (6.7) que mδ̃ ≡ m̃δ (mod q). Posons m̃0 =
m̃ − δ̃, et la relation devient
mm̃0 = m0 m̃,
car on a supposé que les valeurs sont suffisamment petites donc l’égalité est vraie sur les
entiers.
Soit m = µg où g = gcd(m, m0 ), alors on déduit que µ divise m̃. Par conséquent, s’il y
a plusieurs candidats de la forme (m̃1 , b), . . . , (m̃N , b), alors µ divise g̃ = gcd(m̃1 , . . . , m̃N )
qui divise m à son tour. Finalement, on a
k ≡ b (mod g̃)
avec g̃ un facteur de m.
Q − Q0 = [2m − 2j ]R,
et la valeur δ = 2m − 2j ne dépend que des bits de poids faible de m. Ainsi, pour la partie
pas de bébés – pas de géants de l’attaque ne nécessite une recherche exhaustive seulement
sur les bits de poids fort de m. Au total, le coût est alors O(2λ ).
k ≡ mγ (mod q).
L’attaque DFA peut être appliquée avec une faute sur la seconde multiplication
scalaire. Supposons qu’une faute a modifié le calcul de [γ]R en [γ 0 ]R où la différence
δ = γ − γ 0 appartient à un ensemble de taille B. Alors le résultat de la multiplication
scalaire Q = [γm]P est altéré en un point Q0 = [γ 0 m]P , et leur différence est
Q − Q0 = [δm]P.
k − mγ
≡ γb (mod q), (6.9)
m2j
où γb est relativement petit comparé à l’ordre q (au moins j bits de moins). Lorsqu’il est
possible de séparer m de (2γ − 2j ) dans le logarithme discret calculé (par exemple si m
est un nombre premier de la taille adéquate), alors un réseau Euclidien peut être construit.
Dans le cas où le scalaire k est fixe, une attaque par réseau Euclidien peut également
être utilisée. En effet, l’équation (6.9) est une équation linéaire où les variables inconnues
sont la clé privée k et la valeur γb qui est différente à chaque exécution. En posant
u = 1/(m2j ) mod q et v = −γ/2j mod q, alors on a
k = m + γ.
92 Chapitre 6 Attaque en faute différentielle
Le résultat final est calculé avec deux multiplications scalaires Q = [m]P + [γ]P et
combiné avec une addition de points.
Une analyse de cette méthode a été réalisée dans [MV06], et un biais statistique a été
démontré entre les bits des deux morceaux. Plusieurs attaques par injection de fautes ont
été proposées mais qui nécessitent deux fautes par exécution (une sur un bit de m et une
sur un bit de γ).
Une attaque différentielle par injection de faute pourrait être appliquée de façon
similaire en réalisant la même faute sur chacun des deux multiplications scalaires aux
mêmes positions.
Table 6.1 : Vue d’ensemble de l’algorithme Montgomery ladder dans quelques bibliothèques
cryptographiques.
On peut noter que dans certains cas une attaque par canaux auxiliaires peut être
suffisante, mais ces dernières sont liées à la façon dont l’échange conditionnel est mis en
œuvre. Il y a la méthode avec un masque binaire, où l’échange est réalisé avec un masque
composé de bits valant tous 1 ou tous 0. Un attaque par profilage a été appliquée sur la fuite
6.5. Évaluation pratique 93
venant de l’opérateur binaire AND [Nas+16]. Dans le cas de Mbed TLS, une multiplication
par 0 ou par 1 est utilisée pour réaliser l’échange, et est également vulnérable à une
attaque par profilage [LLF20]. Dans les deux cas cités, une seule trace révèle le scalaire
entier.
Sous l’hypothèse d’une implémentation protégée contre ces attaques, une attaque par
injection de faute devient pertinente. Dans la suite on présente une stratégie pour réaliser
l’attaque présentée dans la section 6.3.3 sur une implémentation basée sur l’algorithme 4.
Saut d’instruction. Le premier modèle de faute considéré est le saut d’instruction qui
fut appliqué avec succès en pratique sur une exponentiation RSA pour ignorer l’exécution
d’un carré [SH08]. Plus récemment, ce modèle de faute a été appliqué sur l’algorithme de
décompression de point pour que ce dernier appartienne à une courbe où le logarithme
discret est plus facile à calculer [BG15, TT19].
L’effet décrit dans la section 6.3.3 peut être réalisé si la ligne 5 de l’algorithme 4 est
ignorée lors d’une itération de la boucle. En effet, la variable pbit au début de la boucle
contient la valeur du bit précédemment traité et garde trace du l’état actuel du couple
(R0 , R1 ) si bien que l’invariant de boucle est :
R1−pbit − Rpbit = P.
Ainsi, si la ligne « pbit ← pbit ⊕ ki » n’est pas exécutée et que le bit ki vaut 1, alors la
variable pbit n’est pas mise à jour :
• Si pbit valait 0, on a R1 − R0 = P , les points ne sont pas échangés, donc on a encore
R1 − R0 = P ;
• Si pbit valait 1, on a R0 − R1 = P , les points sont échangés, donc on a désormais
R1 − R0 = P .
Dans les deux cas, pbit récupère la valeur 1 en fin de boucle, donc à partir du tour suivant
on a
R1−pbit − Rpbit = R0 − R1 = −P,
et l’invariant de boucle a changé de signe.
Une alternative est de viser la ligne « pbit ← ki ». Si le bit ki est différent de la valeur
dans pbit, alors à nouveau cette variable ne sera pas cohérente avec l’état actuel du couple
(R0 , R1 ), mais ne sera effectif qu’à partir du tour suivant.
Remarque 10. Dans la moitié des cas, sauter l’une des instructions citées n’a aucun effet
(si le scalaire k est effectivement aléatoire) et donc cela produit un résultat final correct.
Faute dans un registre. Une méthode couramment utilisée pour effectuer un échange
conditionnel est d’utiliser des masques binaires comme présenté dans l’algorithme 20.
La partie qui nous intéresse ici est la façon dont le masque est construit. Généralement,
94 Chapitre 6 Attaque en faute différentielle
celle-ci est réalisée en exploitant la représentation binaire de l’entier −1, qui n’est autre
qu’un mot machine composé uniquement de bits à 1. Ainsi, la quantité −b donne un
masque nul si b vaut 0, et donne un masque binaire composés de 1 si b vaut 1.
Cependant il existe aussi des constructions telles que toute valeur non nulle b aboutit
à un masque binaire composé de 1. Si n est le nombre de bits des mots machine alors il
est possible de construire le masque avec l’une des deux formules suivantes (la première
est celle utilisée dans Mbed TLS et la seconde dans OpenSSL) :
− (b ∨ (−b)) >> (n − 1) ou (¬b ∧ (b − 1)) >> (n − 1) − 1.
Une faute modifiant le bit b en une valeur quelconque non nulle va donc avoir l’effet de
forcer la réalisation de l’échange conditionnel si la valeur d’origine est 0. Cela peut être
réalisé par le modèle de faute aléatoire sur un registre. Il faut tout de même s’assurer que
la modification effectuée n’impacte pas aussi la mise à jour de la valeur pbit pour le tour
suivant.
6.5.3 Simulations
Plusieurs simulations ont été mises en place pour illustrer l’attaque et évaluer les
différentes situations présentées. La première teste les deux modèles de fautes précédents
sur l’implémentation de Montgomery ladder dans OpenSSL avec des fautes simulées avec
GDB, le débogueur du projet GNU. La seconde utilise l’émulateur Unicorn 1 pour tester
les effets de mauvaises instructions ignorées. Enfin, des simulations sont aussi disponible
en Python avec la bibliothèque fpylll pour réaliser l’attaque par réseau Euclidien.
Toutes ces simulations sont disponibles publiquement sur le lien suivant :
https://github.com/orangecertcc/dfa-ladder.
1. https://www.unicorn-engine.org/.
6.5. Évaluation pratique 95
Listing 6.2 : Simulation d’injection de faute par saut d’instruction avec GDB dans OpenSSL.
de réaliser le modèle du saut d’instruction : l’instruction suivante est lue, puis et ignorée
en reprenant à l’instruction située juste après (grâce au nombre d’octets de l’instruction
ignorée).
L’arithmétique modulaire de grands entiers de la courbe secp256r1 écrit en assem-
bleur a été choisie (à partir d’OpenSSL), car elle n’a pas de dépendance externe et est plus
facile pour fonctionner avec l’émulateur.
Deux exécutables ont été créés avec une implémentation de Montgomery ladder de
l’algorithme 4 : la première utilise les formules pour coordonnée Jacobiennes complètes,
et la seconde les formules XYcoZ.
Les instructions liées aux lignes « pbit ← pbit ⊕ ki » et « pbit ← ki » sont bien
présentes dans le code assembleur généré. Lorsqu’elles sont ignorées pendant une itération
l’analyse aboutit et les bits de poids faible du scalaire sont obtenus.
Cependant une situation d’un faux positif a été repérée lorsque la faute touche la
fonction qui extrait un bit du scalaire en début de boucle. La conséquence est que le bit
extrait est erroné : le bit kj est remplacé par 1 − kj , mais le reste de la multiplication
scalaire est correctement effectué. Cela est équivalent à un bitflip sur le scalaire et en
conséquence on a
[−2j ]P si kj = 0,
Q − Q0 =
[2j ]P si kj = 1.
Si l’on regarde l’équation (6.3), l’analyse va aboutir et révéler que les bits de poids faible
du scalaire sont nuls (alors que ce n’est pas nécessairement le cas). Pour éviter qu’une
mauvaise signature soit prise en compte pour l’attaque contre ECDSA, il est préférable
d’ignorer ce résultat (si j vaut 16, il n’y a qu’une chance sur 65536 que les 16 bits de
poids faible soient effectivement nuls, donc de toute façon le rejet d’un résultat correct
serait rare).
Un autre faux positif a été observé avec les formules pour coordonnées Jacobiennes :
après un saut d’une instruction spécifique dans la fonction d’addition de points, un des
points en entrée n’est pas chargé correctement et l’addition est effectuée avec le même
point. La fonction de doublement est alors appelée, et l’analyse aboutit et donne une
valeur incorrecte.
Enfin, pour les formules XYcoZ, une vérification de l’invariant a été appliquée en fin
d’exécution basé sur une proposition donnée dans [VS12]. La fonction XYcoZ-ADD a été
adaptée pour que la différence des entrées soit calculée (l’invariant) au lieu de la somme.
Une fois la coordonnée Z récupérée et les points convertis sous leur représentation affine,
l’opération binaire XOR est appliquée entre l’invariant calculé I, l’invariant correct P et
la sortie Q :
Q ⊕ I ⊕ P.
Si l’invariant calculé est correct, alors il devrait s’annuler avec P . Comme attendu d’après
la section 6.3.5, I et l’invariant P coïncident lorsque la faute est correctement injectée
(ou lorsqu’il n’y a pas de faute), donc la sortie est valide et n’empêche pas la réalisation
de l’attaque.
Simulation avec Python. Les simulations Python incluent des tests pour l’attaque
par réseau Euclidien avec ou sans randomisation du scalaire, avec les formules pour
6.6. Contremesures 97
coordonnées Jacobiennes classiques, XYcoZ ou les formules projectives XZ. La faute est
réalisée en omettant la ligne « pbit ← ki » en fin de boucle.
Bien que l’attaque par réseau Euclidien a un coût négligeable dans les différentes
configurations, on note une différence dans l’efficacité dans le cas de la scission multi-
plicative. En effet, l’attaque contre un scalaire fixe nécessite un réseau Euclidien plus
large par rapport à l’attaque contre ECDSA lorsque le même nombre de bits du scalaire
randomisé est obtenu. Rappelons que dans ce cas le scalaire k est randomisé en une
valeur γ avec un entier aléatoire m tel que k ≡ mγ mod q. L’analyse DFA révèle m et j
bits de γ. Lorsque j vaut 5 il est nécessaire d’avoir 54 signatures fautées en moyenne
(comme dans le cas d’un scalaire non randomisé, voir tableau 2.1), tandis que pour un
scalaire fixe environ 70 points fautés doivent être récupérés.
Un explication partielle viendrait de la construction d’une des lignes dans la matrice
de la base du réseau Euclidien, qui ne dépend que des j bits récupérés dans le cas d’un
scalaire fixe, tandis que pour ECDSA ces entrées sont davantage diversifiées.
6.6 Contremesures
Dans certains cas présentés, une validation de point en fin d’algorithme suffit à
détecter qu’une faute a eu lieu. Par contre dans le cas de l’attaque sur le changement de
signe de l’invariant cette protection ne suffit pas, même dans le cas des formules XZ ou
XYcoZ (il fut suggéré dans [EL09] de reconstruire la coordonnée manquante et ensuite
réaliser la vérification, mais dans le contexte de l’attaque présentée dans [Fou+08]).
La vérification de l’invariant fut proposée dans [DHA11, VS12] contre des attaques en
faute. D’après la section 6.3.3, cela reste vrai en général, sauf dans les cas des formules
XZ et XYcoZ (l’invariant reconstruit est celui attendu).
Cependant, une autre idée présentée dans [DHA11] peut empêcher l’attaque du
changement de signe de l’invariant dans le cas des formules spécifiques. Elle est basée
sur une randomisation du point de base (seconde contremesure de Coron [Cor99]) :
l’algorithme est initialisé avec R0 = P + R et R1 = [2]P + R pour un point aléatoire R,
et l’invariant est toujours égal à l’entrée P . À la fin de la multiplication scalaire on a
R0 = [k]P + [2n−1 ]R, donc une soustraction par [2n−1 ]P est nécessaire pour obtenir le
bon résultat. Dans l’attaque les points R0 et R1 sont inversés et l’invariant devient −P :
R0 = [k̃]P + [2n−1 ]R
R1 = R0 − P.
Sans faute, le résultat attendu est le couple ([k]P, k) où k est le scalaire secret. Cette
méthode devrait détecter la faute de l’attaque du changement de signe de l’invariant car
la valeur auxiliaire est cohérente avec le point donc un changement dans ce dernier a
aussi un effet sur cette valeur.
Enfin, dans le cadre de l’attaque contre ECDSA, il reste toujours possible de vérifier
la signature à la fin des calculs.
6.7 Conclusion
Dans ce chapitre on a présenté une nouvelle attaque en faute différentielle sur l’algo-
rithme Montgomery ladder. Selon deux modèles de fautes considérés (saut d’instruction
ou modification aléatoire d’un registre), le flot d’exécution d’un programme est altéré
ayant pour effet principal d’interchanger deux points. En conséquence, plusieurs bits
consécutifs du scalaire secret peuvent être déterminés à partir de la différence du résultat
correct avec celui qui est erroné.
Aussi, cette attaque contourne certaines des mesures de protections contre des at-
taques par injection de faute sur les courbes elliptiques. En conséquence, un soin parti-
culier est nécessaire dans le choix des contremesures lorsque ce genre d’attaquant fait
partie du modèle de sécurité.
Enfin, des éléments sont présentés prouvant que la randomisation du scalaire par les
méthodes les plus usuelles n’est pas suffisante pour déjouer des attaques DFA. Pour cela,
il est nécessaire que les valeurs aléatoires utilisées dans ces méthodes soient suffisamment
petites pour que l’attaque soit réalisable. Cependant, on peut noter que c’est souvent le
cas pour limiter le coût supplémentaire qu’elles impliquent.
Attaque par dictionnaire
7
sur les protocoles SRP et SPAKE2+
Sommaire
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.2 Le protocole Secure Remote Password . . . . . . . . . . . . . . . . . . . . . . 100
7.2.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.2.2 Sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
7.3 Attaque par dictionnaire sur SRP . . . . . . . . . . . . . . . . . . . . . . . . . 102
7.3.1 Modèle d’attaque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.3.2 Attaquant passif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.3.3 Attaquant actif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.3.4 Considérations pratiques . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.3.5 iCloud Keychain Recovery . . . . . . . . . . . . . . . . . . . . . . . . 106
7.3.6 Expérimentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
7.4 Le protocole SPAKE2+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.4.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.4.2 Sécurité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.4.3 Présence dans CoreCrypto . . . . . . . . . . . . . . . . . . . . . . . . 110
7.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
99
100 Chapitre 7 Attaque par dictionnaire sur SRP et SPAKE2+
7.1 Introduction
Les protocoles SRP et SPAKE2+ appartiennent à la classe des protocole d’authen-
tification et d’échange de clé basé sur un mot de passe, Password-based Authenticated
Key-Exchange (PAKE) en anglais. En particulier, ils attribuent un rôle asymétrique dans
un modèle où seul le client connaît le mot de passe, tandis que le serveur détient un
vérificateur. Les avantages par rapport à un échange de clé Diffie-Hellman est que leur
conception assure une authentification mutuelle et protège le mot de passe contre un
espionnage des communications entre le client et le serveur.
Les calculs dans le protocole SRP nécessitent plusieurs exponentiations modulaires
dans un corps fini défini par un grand nombre premier. Il en est de même pour SPAKE2+,
mais ce dernier est également compatible avec les courbes elliptiques. Les exposants sont
secrets et certains sont spécifiquement dérivés d’un mot de passe. La connaissance de ces
exposants est suffisante pour se faire passer pour un client.
Récemment, il a été montré que des implémentations d’un protocole PAKE mènent à
des différences de temps d’exécutions directement liés au mot de passe [VR20, BFS20].
Les auteurs utilisent cette fuite comme critère pour filtrer des mots de passe dans un
dictionnaire. Bien qu’il ne s’agit pas d’un exposant qui est dérivé du mot de passe, l’ap-
proche peut être adaptée aux protocoles SRP ou SPAKE2+ si l’algorithme d’exponentiation
ou de multiplication scalaire est vulnérable à des attaques par canaux auxiliaires. Cela
est notamment l’objet de l’attaque PARASITE [BFS21], exploitant une vulnérabilité par
attaque cache contre le protocole SRP.
La section 7.2 donne une description générale du protocole SRP. L’attaque contre le
protocole est introduite dans la section 7.3, où le client est supposé utiliser un algorithme
d’exponentiation vulnérable, même dans le cas d’une fuite mineure. Enfin, la section 7.4
présente le protocole SPAKE2+ et l’adaptation de l’attaque.
Client Server
secret : pw secret : v := g x
autre : salt
B, salt
Vérification de M1
M2 ← H(A, M1 , sk )
M2
Vérification de M2
passer pour le client (si le mot de passe est fort, car dans cette situation une attaque par
dictionnaire serait toujours possible).
La description du protocole est donnée ci-dessous, ainsi que dans la figure 7.1.
7.2.1 Description
Initialisation. Tous les calculs sont réalisés sur un corps fini premier avec un grand
nombre premier p et un élément g qui génère un grand sous-groupe d’ordre q. En parti-
culier, il est recommandé que p soit un nombre premier sûr pour une meilleure sécurité
(i.e. p = 2q + 1 avec q premier). De tels paramètres sont définis dans [Tay+07] pour être
utilisé dans l’authentification TLS.
Avant une authentification, un mot de passe pw et un sel doivent être choisis par le
client, et un exposant secret x en est dérivé comme suit :
où H est une fonction de hachage sécurisée et « | » une concaténation. Par simplicité, les
constructions spécifiques en entrée de la fonction de hachage seront omises et seules les
valeurs qui influent sur la sortie seront indiquées. Le client calcule v := g x mod p, et le
102 Chapitre 7 Attaque par dictionnaire sur SRP et SPAKE2+
serveur conserve le vérificateur v et le sel. Le client n’a pas besoin de conserver l’expo-
sant x. La façon dont le serveur récupère le vérificateur et le sel dépend de l’application
qui utilise le protocole et ne fait pas partie de la description.
Calcul du secret partagé et preuve. Les deux entités peuvent calculer une valeur u à
partir des valeurs publiques échangées A et B. Ensuite, on a l’égalité suivante :
Le client peut calculer l’expression de gauche (en utilisant le sel pour obtenir x), tandis
que le serveur peut calculer celle de droite. Une clé de session sk est construite à partir
de ce secret partagé. Une dernière étape est nécessaire pour prouver à l’un et à l’autre
que la clé est identique en échangeant des preuves. L’authentification échoue en cas de
désaccord.
7.2.2 Sécurité
Pour se faire passer pour un client il est nécessaire de connaître l’exposant x pour
construire le secret partagé avec le serveur. Cette valeur n’est ni échangée, ni stockée,
et ne peut être dérivée des communications. Dans le cas où le serveur est compromis,
l’attaquant obtient v := g x mod p (et le sel) et x peut être récupéré avec une attaque
par dictionnaire si le mot de passe est faible (l’attaquant calcule des candidats x0 pour x
0
jusqu’à ce que g x mod p soit à égal à v). Une alternative serait de résoudre le problème
du logarithme discret qui est un problème difficile lorsque les paramètres du groupe sont
sûrs (le record actuel est un logarithme discret dans un corps fini de 795 bits [Bou+20]).
Du côté du client, la valeur x est reconstruite lorsque le client entre son mot de passe,
et est suivi par le calcul de l’exponentiation g x mod p. Par conséquent, cette opération
est susceptible d’être réalisée plusieurs fois et est le sujet de l’attaque présentée dans la
section suivante.
Observation par canaux auxiliaires. Une fuite observable à distance comme la mesure
du temps d’exécution est difficile à obtenir dans ce protocole : les calculs qui mettent
en jeu l’exposant secret ne sont qu’une part de la procédure, donc l’analyse du temps
d’exécution pourrait être difficile voire impossible à exploiter. D’autres moyens d’attaques
nécessitent un accès physique à l’appareil du client, que ce soit un téléphone ou un
ordinateur. Cela limite la réalisation de l’attaque car l’observation fait suite à l’entrée
d’un mot de passe sur l’appareil.
Néanmoins, les auteurs de [Gen+16] ont montré comment réaliser une attaque par
canaux auxiliaire avec une sonde magnétique proche de l’appareil, ou une sonde d’ali-
mentation sur le port USB d’un chargeur de téléphone.
On peut aussi citer les attaques par cache qui passent par un programme espion qui
partage le cache de l’application comme dans l’attaque PARASITE [BFS21].
7.3. Attaque par dictionnaire sur SRP 105
Man in the Middle. Le problème principal de la second variante de l’attaque est une
communication chiffrée par TLS entre le client et le serveur qui rend plus difficile de
modifier les valeurs transmises. Donc une attaque Man in the Middle nécessiterait de
se faire passer pour le serveur. Une modification du sel a pour conséquence un échec
d’authentification, et le client pourrait croire à une erreur de frappe de sa part. Il est
nécessaire de réaliser une modification quelques fois seulement, l’attaquant peut espacer
dans le temps l’attaque pour rester inaperçu.
Il y a d’autres possibilités pour rendre cette seconde variante possible telle qu’une
injection de faute pour altérer la valeur du sel de l’identifiant sur l’appareil du client.
Ces solutions ont également leurs difficultés ; le point important est que l’effet doit être
maîtrisé pour que la valeur modifiée soit prévisible pour l’attaquant.
En particulier, la situation où deux utilisateurs ont le même mot de passe est équivalente
à la possession de deux valeurs distinctives de largeurs w1 et w2 .
Si la valeur distinctive est la longueur en bits n de l’exposant, alors celui-ci se situe
dans un intervalle de largeur w = 2n−1 . Par conséquent, environ 1/2`−n+1 des mots de
passe du dictionnaire correspondent, et, dans le pire cas, la moitié des mots de passe seront
éliminés. Quelques dizaines de valeurs distinctives de la longueur en bits de l’exposant
sont généralement suffisants (en fonction de la taille du dictionnaire). On peut se référer
106 Chapitre 7 Attaque par dictionnaire sur SRP et SPAKE2+
aux articles sur l’attaque Dragonblood [BFS20, VR20] pour ce cas particulier : bien que ce
ne soit pas lié à la longueur en bits de l’exposant, la fuite suit elle aussi une distribution
géométrique.
Remarque 11. La fiabilité de la valeur distinctive est importante. Par exemple, il n’est pas
garanti que l’exposant se situe dans l’intervalle obtenu après l’analyse de la fuite dans
l’exponentiation modulaire de la bibliothèque cryptographique d’Apple, ce qui éliminerait
le bon mot de passe.
Listing 7.1 : Phase d’initialisation du protocole SRP côté client dans iCloud Keychain Recovery.
1 <? xml version ="1.0" encoding =" UTF -8" standalone =" yes "? >
2 <! DOCTYPE plist PUBLIC " -// Apple // DTD PLIST 1.0// EN " " http :// www . apple . com / DTDs /
PropertyList -1.0. dtd " >
3 < plist version ="1.0" >
4 < dict >
5 <key > status </ key >
6 < string >0 </ string >
7 <key > message </ key >
8 < string > Success </ string >
9 <key > version </ key >
10 < integer >1 </ integer >
11 <key > dsid </ key >
12 < string >28 (...) </ string >
13 <key > ClubTypeID </ key >
14 < integer >0 </ integer >
15 <key > respBlob </ key >
16 < string > A A A B i A A A A K Q A A A A A P b Z Q r X (...) js xg 48 nk nP ybR NH kT M = </ string >
17 </ dict >
18 </ plist >
Listing 7.2 : Phase d’initialisation du protocole SRP côté serveur dans iCloud Keychain Recovery.
7.3.6 Expérimentation
Le cas où plusieurs valeurs distinctives donnant la longueur en bits de l’exposant
a déjà été étudié dans [BFS20, VR20], donc on se concentre ici sur l’indicateur donné
par la vulnérabilité liée à la scission Euclidienne de l’exposant telle qu’implémentée par
Apple exposée dans le chapitre 5. Celle-ci a l’avantage que l’indicateur devient plus précis
lorsqu’on observe de plus en plus d’exponentiations avec le même secret.
L’expérimentation a été menée avec les conditions suivantes :
• SHA-256 comme fonction de hachage (les exposants sont dans l’intervalle [0, 2256 −1]) ;
• Le groupe de 2048 bits dont les paramètres sont dans la RFC 5054 ;
• Un sel de 16 octets ;
• Un mot de passe composé de 6 chiffres.
Étant donnés un sel et mot de passe aléatoire, l’exposant secret a été dérivé selon le
protocole SRP (avec « id » comme identité du client). La fuite a été simulée pour N = 1000
exponentiations telle que décrite par le code source d’Apple, puis une approximation a été
réalisée sous la forme [xmin , xmax ] par l’intervalle de Wilson avec un niveau de confiance
de 95 %. Tous les mots de passe dont l’exposant se situe dans cet intervalle sont gardés
comme candidats.
Cela a été répété pour 10000 mots de passe différents, et les exposants, nombre de
mots de passe candidats et si le bon mot de passe est inclus dans les candidats ont été
conservés. Les résultats sont donnés dans la figure 7.2.
On rappelle ici que la vulnérabilité n’est pas observable pour les exposants de taille
impaire en bits et donc le nombre de mots de passe candidats n’apparaît pas (sauf pour les
exposants de longueur 251 bits ou moins représentés dans les points isolés sur la gauche
de la figure).
Au total, il y a seulement 6846 cas avec moins de 32000 mots de passe candidats, et
le bon mot de passe est inclus dans la liste dans 95,5 % des cas, ce qui est cohérent avec
le niveau de confiance sur l’intervalle calculé.
On note au passage la remarque faite dans la section 5.2.3 où les exposants proche
7.4. Le protocole SPAKE2+ 109
32000
password candidates
0
0 2253 2254 2255 2256
exponent
Figure 7.2 : Nombre de mots de passe candidats pour N = 1000 mesures en fonction de l’exposant.
d’une puissance de 2 sont plus faciles à approximer et par conséquent l’attaque par
dictionnaire est plus efficace.
Le meilleur résultat est un mot de passe dont l’exposant correspondant vaut environ
2243,17 et fut inclus dans une liste de 8 candidats.
7.4.1 Description
Étant donné un mot de passe pw et des données liées à l’identité des deux entités,
deux valeurs secrètes w0 et w1 sont créées par une fonction de dérivation simplement
notée H ici. Un point de base P et deux points additionnels M et N sur une courbe
elliptique font parties des paramètres publics. La première entité est un client qui connaît
w0 et w1 , qu’il calcule à partir d’un mot de passe, tandis que la seconde entité est un
serveur qui n’a besoin que de w0 et L := [w1 ]P .
Les deux entités calculent des points publics X et Y qu’il s’échangent, créés à partir
de valeurs éphémères et w0 , puis calculent un secret partagé de manière similaire à un
échange de clé Diffie-Hellman classique.
Les différentes étapes sont résumées dans la figure 7.3.
7.4.2 Sécurité
Tout comme dans le protocole SRP, l’espionnage des communications ne peuvent
permettre d’obtenir le mot de passe, et une compromission du serveur ne révèle que
w0 et L. Si le mot de passe a une entropie élevé, alors w1 ne peut être retrouvé, et un
attaquant ne peut pas se faire passer pour un client vu qu’il serait nécessaire de calculer
110 Chapitre 7 Attaque par dictionnaire sur SRP et SPAKE2+
Les multiplications scalaires en gras sont réalisées avec un scalaire fixe (pour un mot de
passe et identités des entités identiques).
Du côté du serveur, on a :
0
S = [w0 ]M
S = [y]P
T 0= X − S0
T = [w0 ]N
Z = [y]T 0
Y =S+T
V = [y]L.
Une multiplication scalaire vulnérable, telle que celle présentée dans le chapitre 5, fait
fuiter de l’information à la fois sur w0 et w1 du côté du client. L’attaque par dictionnaire
3. Avant les correctifs appliqués en 2021, voir le chapitre 5.
7.5. Conclusion 111
décrite dans la section 7.3 est alors applicable mais avec deux critères pour filtrer les
mots de passe. De plus, d’après la description du protocole, les identités du client et du
serveur font partie des valeurs pour la dérivation du mot de passe, alors une modification
malveillante peut amener à l’obtention de nouveaux critères et améliorer la filtration.
7.5 Conclusion
Dans ce chapitre on a présenté une attaque contre les protocoles SRP et SPAKE2+
lorsque l’exponentiation modulaire ou la multiplication scalaire est vulnérable à une
attaque par canaux auxiliaires. Ainsi, par la fuite observée il est possible de construire un
indicateur pour filtrer les mots de passe.
Les contraintes pour réaliser l’attaque sur le protocole SRP ont été présentées et
un cas pratique a été étudié. Celui-ci est l’utilisation de SRP comme authentification
supplémentaire sur le service iCloud Keychain Recovery d’Apple. Une expérimentation
a été réalisée en reprenant la vulnérabilité du chapitre 5 afin d’illustrer le concept de
l’attaque.
112 Chapitre 7 Attaque par dictionnaire sur SRP et SPAKE2+
Conclusion
Dans cette thèse, les travaux qui ont été présentés concernent essentiellement les
soucis d’implémentations de courbes elliptiques en vue de leur usage en cryptographie.
Cela s’est manifesté par une analyse en premier lieu des différentes formules, algorithmes
et courbes elliptiques utilisées en pratique, ce qui a abouti à la présentation des cas
exceptionnels dans leur utilisation. Plus précisément, on a montré pour plusieurs formules
les situations où celles-ci ne donnent pas le bon résultat, puis si ces cas particuliers
pouvaient apparaître en fonction de l’algorithme de multiplication scalaire.
La gestion de ces exceptions est importante pour garantir une exécution résistante à
des attaquants plus ou moins fort. En premier exemple on montre les conséquences de
l’utilisation de calculs factices par l’introduction d’additions de points inutiles pour rendre
une exécution régulière. Plusieurs implémentations reposent sur cette technique et celles-
ci peuvent être visées par une attaque Safe-Error qui, par l’injection d’une perturbation,
permet de détecter la présence de ces calculs factices. Ce type d’attaque a déjà établi par
le passé et on a identifié plusieurs implémentations qui y sont vulnérables, accompagné
de simulations pour montrer le concept de l’attaque. Une nouvelle proposition a été faite
pour identifier ces calculs factices dans le cas spécifique d’une implémentation où ils sont
réalisés essentiellement avec des opérandes nuls. En effet, le faible poids de Hamming de
ces valeurs est suffisamment visible pour apparaître sur une trace de consommation de
courant, ce qui révèle leur position ainsi qu’un morceau assez large pour être exploité.
Dans la suite, on a montré qu’une méthode de protection basée sur une division
Euclidienne pour randomiser les calculs introduit un biais dans l’exécution. Cette légère
variation permet de réaliser une approximation du scalaire secret manipulé, à condition
que cette valeur soit fixe et que plusieurs observations peuvent être faites. Un exemple
d’application peut se trouver dans les protocoles d’authentification par mot de passe tels
que SRP (pour l’exponentiation modulaire) ou SPAKE2+ (compatible avec les courbes
elliptiques). Le mot de passe est utilisé pour générer un exposant ou scalaire, donc une
approximation ou d’autres types de fuites peuvent être utilisées comme indicateurs pour
appliquer une attaque par dictionnaire.
Cette méthode de randomisation est notamment utilisée dans la bibliothèque cryp-
tographique présente dans les appareils Apple, ce qui a conduit à des communications
avec les ingénieurs afin d’échanger sur ces découvertes. Les correctifs proposés ont
été analysés et présentés, en particulier les modifications apportées à l’algorithme de
multiplication scalaire.
Enfin, une dernière contribution de cette thèse est l’étude d’une attaque par injection
de faute DFA. Une partie de ces travaux poursuivent l’étude des techniques de randomisa-
tion comme celle basée sur la scission Euclidienne. Des stratégies pour exploiter une faute
113
114 Chapitre 7 Conclusion
dans ces contextes sont présentées ce qui montre qu’elles n’apportent pas nécessairement
une protection contre ce type d’attaquants. Aussi, on a proposé une nouvelle attaque DFA
sur l’algorithme Montgomery ladder qui a l’avantage de contourner certaines protections
comme la validation de point, voire une vérification de l’invariant lorsque des formules
spécifiques n’utilisant par toutes les coordonnées sont utilisées.
Invariant et formules XYcoZ
A
Dans l’expérimentation du chapitre 6, un exécutable a été créé qui effectue une multi-
plication scalaire avec les formules XYcoZ et qui intègre une vérification de l’invariant.
Pour cela il est nécessaire dans un premier temps de reconstruire la coordonnée Z des
points R0 et R1 manipulés pendant l’exécution et de calculer l’invariant. Ceci a été réalisé
avec l’introduction des formules XYcoZ-SUB.
115
116 Chapitre A Invariant et formules XYcoZ
[AH21] Martin R. Albrecht and Nadia Heninger, “On Bounded Distance Decoding with
Predicate: Breaking the "Lattice Barrier" for the Hidden Number Problem”, in:
EUROCRYPT 2021, ed. by Anne Canteaut and François-Xavier Standaert, vol. 12696,
LNCS, Springer, 2021, pp. 528–558, doi: 10.1007/978-3-030-77870-5_19.
[ANS20] ANSSI, Guide des mécanismes cryptographiques – Règles et recommandations concer-
nant le choix et le dimensionnement des mécanismes cryptographiques, version 2.04,
voir www.ssi.gouv.fr, 2020.
[Ara+14] Diego F. Aranha et al., “GLV/GLS Decomposition, Power Analysis, and Attacks
on ECDSA Signatures with Single-Bit Nonce Bias”, in: ASIACRYPT 2014, ed. by
Palash Sarkar and Tetsu Iwata, vol. 8873, LNCS, Springer, 2014, pp. 262–281, doi:
10.1007/978-3-662-45611-8_14.
[Ara+20] Diego F. Aranha et al., “LadderLeak: Breaking ECDSA with Less than One Bit of
Nonce Leakage”, in: CCS ’20: 2020 ACM SIGSAC, ed. by Jay Ligatti et al., ACM, 2020,
pp. 225–242, doi: 10.1145/3372297.3417268.
[Bar+16] Alessandro Barenghi et al., “A Fault-Based Secret Key Retrieval Method for ECDSA:
Analysis and Countermeasure”, in: ACM J. Emerg. Technol. Comput. Syst. 13.1
(2016), 8:1–8:26, doi: 10.1145/2767132.
[BDL97] Dan Boneh, Richard A. DeMillo, and Richard J. Lipton, “On the Importance of
Checking Cryptographic Protocols for Faults (Extended Abstract)”, in: EUROCRYPT
’97, ed. by Walter Fumy, vol. 1233, LNCS, Springer, 1997, pp. 37–51, doi: 10.1007/3-
540-69053-0_4.
[Ber06] Daniel J. Bernstein, “Curve25519: New Diffie-Hellman Speed Records”, in: PKC
2006, ed. by Moti Yung et al., vol. 3958, LNCS, Springer, 2006, pp. 207–228, doi:
10.1007/11745853_14.
[BFS20] Daniel De Almeida Braga, Pierre-Alain Fouque, and Mohamed Sabt, “Dragonblood
is Still Leaking: Practical Cache-based Side-Channel in the Wild”, in: ACSAC ’20,
ACM, 2020, pp. 291–303, doi: 10.1145/3427228.3427295.
[BFS21] Daniel De Almeida Braga, Pierre-Alain Fouque, and Mohamed Sabt, “PARASITE:
PAssword Recovery Attack against Srp Implementations in ThE wild”, in: CCS
’21: 2021 ACM SIGSAC, ed. by Yongdae Kim et al., ACM, 2021, pp. 2497–2512, doi:
10.1145/3460120.3484563.
[BG15] Johannes Blömer and Peter Günther, “Singular Curve Point Decompression Attack”,
in: FDTC 2015, ed. by Naofumi Homma and Victor Lomné, IEEE Computer Society,
2015, pp. 71–84, doi: 10.1109/FDTC.2015.17.
117
118 Bibliographie
[BJ02] Eric Brier and Marc Joye, “Weierstraß Elliptic Curves and Side-Channel Attacks”,
in: PKC 2002, ed. by David Naccache and Pascal Paillier, vol. 2274, LNCS, Springer,
2002, pp. 335–345, doi: 10.1007/3-540-45664-3_24.
[BL07] Daniel J. Bernstein and Tanja Lange, “Faster Addition and Doubling on Elliptic
Curves”, in: ASIACRYPT 2007, ed. by Kaoru Kurosawa, vol. 4833, LNCS, Springer,
2007, pp. 29–50, doi: 10.1007/978-3-540-76900-2_3.
[Ble00] Daniel Bleichenbacher, “On the generation of one-time keys in DL signature sche-
mes”, in: Presentation at IEEE P1363 working group meeting, 2000, p. 81.
[BMM00] Ingrid Biehl, Bernd Meyer, and Volker Müller, “Differential Fault Attacks on Elliptic
Curve Cryptosystems”, in: CRYPTO 2000, ed. by Mihir Bellare, vol. 1880, LNCS,
Springer, 2000, pp. 131–146, doi: 10.1007/3-540-44598-6_8.
[Boo51] Andrew D. Booth, “A signed binary multiplication technique”, in: The Quarterly
Journal of Mechanics and Applied Mathematics 4.2 (Jan. 1951), pp. 236–240, issn:
0033-5614, doi: 10.1093/qjmam/4.2.236.
[BOS06] Johannes Blömer, Martin Otto, and Jean-Pierre Seifert, “Sign Change Fault Attacks
on Elliptic Curve Cryptosystems”, in: FDTC 2006, ed. by Luca Breveglieri et al.,
vol. 4236, LNCS, Springer, 2006, pp. 36–52, doi: 10.1007/11889700_4.
[Bou+20] Fabrice Boudot et al., “Comparing the Difficulty of Factorization and Discrete
Logarithm: A 240-Digit Experiment”, in: CRYPTO 2020, ed. by Daniele Micciancio
and Thomas Ristenpart, vol. 12171, LNCS, Springer, 2020, pp. 62–91, doi: 10.1007/
978-3-030-56880-1_3.
[BS97] Eli Biham and Adi Shamir, “Differential Fault Analysis of Secret Key Cryptosystems”,
in: CRYPTO ’97, ed. by Burton S. Kaliski Jr., vol. 1294, LNCS, Springer, 1997, pp. 513–
525, doi: 10.1007/BFb0052259.
[BT11] Billy Bob Brumley and Nicola Tuveri, “Remote Timing Attacks Are Still Practical”,
in: ESORICS 2011, ed. by Vijay Atluri and Claudia Díaz, vol. 6879, LNCS, Springer,
2011, pp. 355–371, doi: 10.1007/978-3-642-23822-2_20.
[BV96] Dan Boneh and Ramarathnam Venkatesan, “Hardness of Computing the Most
Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes”, in: CRYPTO
’96, ed. by Neal Koblitz, vol. 1109, LNCS, Springer, 1996, pp. 129–142, doi: 10.1007/
3-540-68697-5_11.
[CJ01] Christophe Clavier and Marc Joye, “Universal Exponentiation Algorithm”, in: CHES
2001, ed. by Çetin Kaya Koç, David Naccache, and Christof Paar, vol. 2162, LNCS
Generators, Springer, 2001, pp. 300–308, doi: 10.1007/3-540-44709-1_25.
[CJ03] Mathieu Ciet and Marc Joye, “(Virtually) Free Randomization Techniques for Elliptic
Curve Cryptography”, in: ICICS 2003, ed. by Sihan Qing, Dieter Gollmann, and
Jianying Zhou, vol. 2836, LNCS, Springer, 2003, pp. 348–359, doi: 10.1007/978-
3-540-39927-8_32.
[CKS09] David Cash, Eike Kiltz, and Victor Shoup, “The Twin Diffie-Hellman Problem and
Applications”, in: J. Cryptol. 22.4 (2009), pp. 470–504, doi: 10.1007/s00145-009-
9041-6.
[Coh+05] Henri Cohen et al., eds., Handbook of Elliptic and Hyperelliptic Curve Cryptog-
raphy, Chapman and Hall/CRC, 2005, isbn: 978-1-58488-518-4, doi: 10.1201/
9781420034981.
Bibliographie 119
[Cor99] Jean-Sébastien Coron, “Resistance against Differential Power Analysis for Elliptic
Curve Cryptosystems”, in: CHES’99, ed. by Çetin Kaya Koç and Christof Paar,
vol. 1717, LNCS, Springer, 1999, pp. 292–302, doi: 10.1007/3-540-48059-5_25.
[DH76] Whitfield Diffie and Martin E. Hellman, “New directions in cryptography”, in: IEEE
Trans. Inf. Theory 22.6 (1976), pp. 644–654, doi: 10.1109/TIT.1976.1055638.
[DHA11] Agustin Dominguez-Oviedo, M. Anwar Hasan, and Bijan Ansari, “Fault-Based
Attack on Montgomery’s Ladder Algorithm”, in: J. Cryptol. 24.2 (2011), pp. 346–374,
doi: 10.1007/s00145-010-9087-5.
[DHB17] Jeremy Dubeuf, David Hély, and Vincent Beroulle, “Enhanced Elliptic Curve Scalar
Multiplication Secure Against Side Channel Attacks and Safe Errors”, in: COSADE
2017, ed. by Sylvain Guilley, vol. 10348, LNCS, Springer, 2017, pp. 65–82, doi:
10.1007/978-3-319-64647-3_5.
[Edw07] H. Edwards, “A normal form for elliptic curves”, in: Bulletin of the American Mathe-
matical Society 44 (2007), pp. 393–422, doi: 10.1090/S0273-0979-07-01153-6.
[EL09] Nevine Maurice Ebeid and Rob Lambert, “Securing the Elliptic Curve Montgomery
Ladder against Fault Attacks”, in: FDTC 2009, ed. by Luca Breveglieri et al., IEEE
Computer Society, 2009, pp. 46–50, doi: 10.1109/FDTC.2009.35.
[Fou+08] Pierre-Alain Fouque et al., “Fault Attack on Elliptic Curve Montgomery Ladder
Implementation”, in: FDTC 2008, ed. by Luca Breveglieri et al., IEEE Computer
Society, 2008, pp. 92–98, doi: 10.1109/FDTC.2008.15.
[Fou+16] Pierre-Alain Fouque et al., “Safe-Errors on SPA Protected Implementations with
the Atomicity Technique”, in: The New Codebreakers - Essays Dedicated to David
Kahn on the Occasion of His 85th Birthday, ed. by Peter Y. A. Ryan, David Naccache,
and Jean-Jacques Quisquater, vol. 9100, LNCS, Springer, 2016, pp. 479–493, doi:
10.1007/978-3-662-49301-4_30.
[FPLLL21] The FPLLL development team, “fpylll, a Python wraper for the fplll lattice reduction
library, Version: 0.5.6”, Available at https://github.com/fplll/fpylll, 2021.
[FRV14] Benoit Feix, Mylène Roussellet, and Alexandre Venelli, “Side-Channel Analysis
on Blinded Regular Scalar Multiplications”, in: INDOCRYPT 2014, ed. by Willi
Meier and Debdeep Mukhopadhyay, vol. 8885, LNCS, Springer, 2014, pp. 3–20, doi:
10.1007/978-3-319-13039-2_1.
[Gau09] Pierrick Gaudry, “Index calculus for abelian varieties of small dimension and the
elliptic curve discrete logarithm problem”, in: J. Symb. Comput. 44.12 (2009),
pp. 1690–1702, doi: 10.1016/j.jsc.2008.08.005.
[Gen+16] Daniel Genkin et al., “ECDSA Key Extraction from Mobile Devices via Nonintrusive
Physical Side Channels”, in: SIGSAC 2016, ed. by Edgar R. Weippl et al., ACM, 2016,
pp. 1626–1638, doi: 10.1145/2976749.2978353.
[GHS02] Pierrick Gaudry, Florian Hess, and Nigel P. Smart, “Constructive and Destructive
Facets of Weil Descent on Elliptic Curves”, in: J. Cryptol. 15.1 (2002), pp. 19–46,
doi: 10.1007/s00145-001-0011-x.
[GJ21] Robert Granger and Antoine Joux, Computing Discrete Logarithms, Cryptology
ePrint Archive, Report 2021/1140, 2021.
[GK15] Shay Gueron and Vlad Krasnov, “Fast prime field elliptic-curve cryptography with
256-bit primes”, in: J. Cryptogr. Eng. 5.2 (2015), pp. 141–151, doi: 10.1007/s13389-
014-0090-x.
120 Bibliographie
[Gou+11] Raveen R. Goundar et al., “Scalar multiplication on Weierstraß elliptic curves from
Co-Z arithmetic”, in: J. Cryptogr. Eng. 1.2 (2011), pp. 161–176, doi: 10.1007/
s13389-011-0012-0.
[Gou03] Louis Goubin, “A Refined Power-Analysis Attack on Elliptic Curve Cryptosystems”,
in: PKC 2003, ed. by Yvo Desmedt, vol. 2567, LNCS, Springer, 2003, pp. 199–210,
doi: 10.1007/3-540-36288-6_15.
[GRV16] Dahmun Goudarzi, Matthieu Rivain, and Damien Vergnaud, “Lattice Attacks Against
Elliptic-Curve Signatures with Blinded Scalar Multiplication”, in: SAC 2016, ed. by
Roberto Avanzi and Howard M. Heys, vol. 10532, LNCS, Springer, 2016, pp. 120–139,
doi: 10.1007/978-3-319-69453-5_7.
[GV10] Christophe Giraud and Vincent Verneuil, “Atomicity Improvement for Elliptic
Curve Scalar Multiplication”, in: CARDIS 2010, ed. by Dieter Gollmann, Jean-Louis
Lanet, and Julien Iguchi-Cartigny, vol. 6035, LNCS, Springer, 2010, pp. 80–101, doi:
10.1007/978-3-642-12510-2_7.
[HPB04] Mustapha Hedabou, Pierre Pinel, and Lucien Bénéteau, “A comb method to render
ECC resistant against Side Channel Attacks”, in: IACR Cryptol. ePrint Arch. 2004
(2004), p. 342.
[IT02] Tetsuya Izu and Tsuyoshi Takagi, “A Fast Parallel Elliptic Curve Multiplication
Resistant against Side Channel Attacks”, in: PKC 2002, ed. by David Naccache and
Pascal Paillier, vol. 2274, LNCS, Springer, 2002, pp. 280–296, doi: 10.1007/3-540-
45664-3_20.
[Joy12] Marc Joye, “A Method for Preventing “Skipping” Attacks”, in: 2012 IEEE Symposium
on Security and Privacy Workshops, IEEE Computer Society, 2012, pp. 12–15, doi:
10.1109/SPW.2012.14.
[JY02] Marc Joye and Sung-Ming Yen, “The Montgomery Powering Ladder”, in: CHES 2002,
ed. by Burton S. Kaliski Jr., Çetin Kaya Koç, and Christof Paar, vol. 2523, LNCS,
Springer, 2002, pp. 291–302, doi: 10.1007/3-540-36400-5_22.
[KJJ99] Paul C. Kocher, Joshua Jaffe, and Benjamin Jun, “Differential Power Analysis”, in:
CRYPTO ’99, ed. by Michael J. Wiener, vol. 1666, LNCS, Springer, 1999, pp. 388–397,
doi: 10.1007/3-540-48405-1_25.
[Kob87] Neal Koblitz, “Elliptic Curve Cryptosystems”, in: Mathematics of computation 48.177
(1987), pp. 203–209, doi: 10.1090/S0025-5718-1987-0866109-5.
[LLF20] Antoine Loiseau, Maxime Lecomte, and Jacques J. A. Fournier, “Template Attacks
against ECC: practical implementation against Curve25519”, in: HOST 2020, IEEE,
2020, pp. 13–22, doi: 10.1109/HOST45689.2020.9300261.
[LLL82] Arjen K. Lenstra, Hendrik W. Jr. Lenstra, and László¸Lovász, “Factoring polynomials
with rational coefficients”, in: Mathematische Annalen 261 (1982), pp. 515–534, issn:
0025–5831, doi: 10.1007/BF01457454.
[Mer+21] Robert Merget et al., “Raccoon Attack: Finding and Exploiting Most-Significant-
Bit-Oracles in TLS-DH(E)”, in: USENIX Security 21, USENIX Association, Aug. 2021,
pp. 213–230, isbn: 978-1-939133-24-3.
[Mil85] Victor S. Miller, “Use of Elliptic Curves in Cryptography”, in: CRYPTO ’85, ed. by
Hugh C. Williams, vol. 218, LNCS, Springer, 1985, pp. 417–426, doi: 10.1007/3-
540-39799-X_31.
Bibliographie 121
[Möl01] Bodo Möller, “Securing Elliptic Curve Point Multiplication against Side-Channel
Attacks”, in: ISC 2001, ed. by George I. Davida and Yair Frankel, vol. 2200, LNCS,
Springer, 2001, pp. 324–334, doi: 10.1007/3-540-45439-X_22.
[Mon87] Peter L. Montgomery, “Speeding the Pollard and Elliptic Curve Methods of Factoriza-
tion”, in: Mathematics of Computation 48 (1987), pp. 243–264, doi: 10.1090/S0025-
5718-1987-0866113-7.
[MOV93] Alfred Menezes, Tatsuaki Okamoto, and Scott A. Vanstone, “Reducing elliptic curve
logarithms to logarithms in a finite field”, in: IEEE Trans. Inf. Theory 39.5 (1993),
pp. 1639–1646, doi: 10.1109/18.259647.
[MPP20] Gabrielle De Micheli, Rémi Piau, and Cécile Pierrot, “A Tale of Three Signatures:
Practical Attack of ECDSA with wNAF”, in: AFRICACRYPT 2020, ed. by Abderrah-
mane Nitaj and Amr M. Youssef, vol. 12174, LNCS, Springer, 2020, pp. 361–381, doi:
10.1007/978-3-030-51938-4\_18.
[Mul+14] Elke De Mulder et al., “Using Bleichenbacher’s solution to the hidden number
problem to attack nonce leaks in 384-bit ECDSA: extended version”, in: J. Cryptogr.
Eng. 4.1 (2014), pp. 33–45, doi: 10.1007/s13389-014-0072-z.
[MV06] Frédéric Muller and Frédéric Valette, “High-Order Attacks Against the Exponent
Splitting Protection”, in: PKC 2006, ed. by Moti Yung et al., vol. 3958, LNCS, Springer,
2006, pp. 315–329, doi: 10.1007/11745853_21.
[Nas+16] Erick Nascimento et al., “Attacking Embedded ECC Implementations Through cmov
Side Channels”, in: SAC 2016, ed. by Roberto Avanzi and Howard M. Heys, vol. 10532,
LNCS, Springer, 2016, pp. 99–119, doi: 10.1007/978-3-319-69453-5_6.
[Nat13] National Institute of Standards and Technology, FIPS PUB 186-4 Digital Signature
Standard (DSS), 2013.
[NS02] Phong Q. Nguyen and Igor E. Shparlinski, “The Insecurity of the Digital Signature
Algorithm with Partially Known Nonces”, in: J. Cryptol. 15.3 (2002), pp. 151–176,
doi: 10.1007/s00145-002-0021-3.
[NS03] Phong Q. Nguyen and Igor E. Shparlinski, “The Insecurity of the Elliptic Curve
Digital Signature Algorithm with Partially Known Nonces”, in: Des. Codes Cryptogr.
30.2 (2003), pp. 201–217, doi: 10.1023/A:1025436905711.
[OT03] Katsuyuki Okeya and Tsuyoshi Takagi, “The Width-w NAF Method Provides Small
Memory and Fast Elliptic Scalar Multiplications Secure against Side Channel At-
tacks”, in: CT-RSA 2003, ed. by Marc Joye, vol. 2612, LNCS, Springer, 2003, pp. 328–
342, doi: 10.1007/3-540-36563-X_23.
[PH78] Stephen C. Pohlig and Martin E. Hellman, “An Improved Algorithm for Computing
Logarithms over GF(p) and Its Cryptographic Significance (Corresp.)”, in: IEEE
Trans. Inf. Theory 24.1 (1978), pp. 106–110, doi: 10.1109/TIT.1978.1055817.
[PM16] Proton Technologies AG, ProtonMail v3.6 Release Notes, 2016.
[Pol78] J. Pollard, “Monte Carlo methods for index computation ()”, in: Mathematics of
Computation 32 (1978), pp. 918–924.
[RCB16] Joost Renes, Craig Costello, and Lejla Batina, “Complete Addition Formulas for
Prime Order Elliptic Curves”, in: EUROCRYPT 2016, ed. by Marc Fischlin and Jean-
Sébastien Coron, vol. 9665, LNCS, Springer, 2016, pp. 403–428, doi: 10.1007/978-
3-662-49890-3_16.
122 Bibliographie
[Res09] Certicom Research, Standards for Efficient Cryptography, SEC 1: Elliptic Curve
Cyptography, version 2, Disponible à l’adresse https://secg.org, 2009.
[RIL19] Thomas Roche, Laurent Imbert, and Victor Lomné, “Side-Channel Attacks on
Blinded Scalar Multiplications Revisited”, in: CARDIS 2019, ed. by Sonia Belaïd and
Tim Güneysu, vol. 11833, LNCS, Springer, 2019, pp. 95–108, doi: 10.1007/978-3-
030-42068-0_6.
[Ron13] Franck Rondepierre, “Revisiting Atomic Patterns for Scalar Multiplications on
Elliptic Curves”, in: CARDIS 2013, ed. by Aurélien Francillon and Pankaj Rohatgi,
vol. 8419, LNCS, Springer, 2013, pp. 171–186, doi: 10.1007/978-3-319-08302-
5_12.
[Rus20] Andy Russon, “Exploiting dummy codes in Elliptic Curve Cryptography imple-
mentations”, in: Symposium sur la sécurité des technologies de l’information et des
communications, SSTIC, France, Rennes, June 3-5 2020, 2020, pp. 229–249.
[Rus21a] Andy Russon, “Return of ECC dummy point additions: Simple Power Analysis
on efficient P-256 implementation”, in: Symposium sur la sécurité des technologies
de l’information et des communications, SSTIC, France, Rennes, June 2-4 2021, 2021,
pp. 367–375.
[Rus21b] Andy Russon, “Threat for the Secure Remote Password Protocol and a Leak in
Apple’s Cryptographic Library”, in: ACNS 2021, ed. by Kazue Sako and Nils Ole
Tippenhauer, vol. 12727, LNCS, Springer, 2021, pp. 49–75, doi: 10.1007/978-3-
030-78375-4_3.
[Rus21c] Andy Russon, “Differential Fault Attack on Montgomery Ladder and in the Presence
of Scalar Randomization”, in: INDOCRYPT 2021, Proceedings, ed. by Avishek Ad-
hikari, Ralf Küsters, and Bart Preneel, vol. 13143, LNCS, Springer, 2021, pp. 287–310,
doi: 10.1007/978-3-030-92518-5_14.
[SA98] T. Satoh and Kiyomichi Araki, “Fermat quotients and the polynomial time discrete
log algorithm for anomalous elliptic curves”, in: Commentarii Math. Univ. St. Pauli.
47 (1998), https://ci.nii.ac.jp/naid/110007696197/en/, pp. 81–92, issn:
0010258X.
[SCIKIT11] F. Pedregosa et al., “Scikit-learn: Machine Learning in Python”, in: Journal of
Machine Learning Research 12 (2011), pp. 2825–2830.
[SE94] Claus-Peter Schnorr and M. Euchner, “Lattice basis reduction: Improved practical
algorithms and solving subset sum problems”, in: Math. Program. 66 (1994), pp. 181–
199, doi: 10.1007/BF01581144.
[Sem98] Igor A. Semaev, “Evaluation of discrete logarithms in a group of p-torsion points of
an elliptic curve in characteristic p”, in: Math. Comput. 67.221 (1998), pp. 353–356,
doi: 10.1090/S0025-5718-98-00887-4.
[SH08] Jörn-Marc Schmidt and Christoph Herbst, “A Practical Fault Attack on Square and
Multiply”, in: FDTC 2008, ed. by Luca Breveglieri et al., IEEE Computer Society,
2008, pp. 53–58, doi: 10.1109/FDTC.2008.10.
[Sha71] Daniel Shanks, “Class number, a theory of factorization, and genera”, in: Proceedings
of Symposia in Pure Mathematics, ed. by Donald J. Lewis, vol. 20, 1971, doi: 10.
1090/pspum/020.
Bibliographie 123
[SM09] Jörn-Marc Schmidt and Marcel Medwed, “A Fault Attack on ECDSA”, in: FDTC
2009, ed. by Luca Breveglieri et al., IEEE Computer Society, 2009, pp. 93–99, doi:
10.1109/FDTC.2009.38.
[SM10] Jörn-Marc Schmidt and Marcel Medwed, “Fault Attacks on the Montgomery Power-
ing Ladder”, in: ICISC 2010, ed. by Kyung Hyune Rhee and DaeHun Nyang, vol. 6829,
LNCS, Springer, 2010, pp. 396–406, doi: 10.1007/978-3-642-24209-0_26.
[Sma99] Nigel P. Smart, “The Discrete Logarithm Problem on Elliptic Curves of Trace One”,
in: J. Cryptol. 12.3 (1999), pp. 193–196, doi: 10.1007/s001459900052.
[ST20] Massimiliano Sala and Daniele Taufer, The group structure of elliptic curves over
Z/NZ, 2020, arXiv: 2010.15543 [math.NT].
[Sun+21] Chao Sun et al., “Guessing Bits: Improved Lattice Attacks on (EC)DSA”, in: IACR
Cryptol. ePrint Arch. 2021 (2021), p. 455, url: https://eprint.iacr.org/2021/
455.
[SW15] Werner Schindler and Andreas Wiemers, “Efficient Side-Channel Attacks on Scalar
Blinding on Elliptic Curves with Special Structure”, in: NIST Workshop on ECC
Standards, 2015.
[Tay+07] David Taylor et al., “Using the Secure Remote Password (SRP) Protocol for TLS
Authentication”, in: RFC 5054 (2007), pp. 1–24, doi: 10.17487/RFC5054.
[TB02] Elena Trichina and Antonio Bellazza, “Implementation of Elliptic Curve Cyptogra-
phy with Built-In Counter Measures against Side Channel Attacks”, in: CHES 2002,
ed. by Burton S. Kaliski Jr., Çetin Kaya Koç, and Christof Paar, vol. 2523, LNCS,
2002, pp. 98–113, doi: 10.1007/3-540-36400-5_9.
[TT19] Akira Takahashi and Mehdi Tibouchi, “Degenerate Fault Attacks on Elliptic Curve
Parameters in OpenSSL”, in: EuroS&P 2019, IEEE, 2019, pp. 371–386, doi: 10.1109/
EuroSP.2019.00035.
[VR20] Mathy Vanhoef and Eyal Ronen, “Dragonblood: Analyzing the Dragonfly Hand-
shake of WPA3 and EAP-pwd”, in: SP 2020, IEEE, 2020, pp. 517–533, doi: 10.1109/
SP40000.2020.00031.
[VS12] Ihor Vasyltsov and Gökay Saldamli, “Fault detection and a differential fault analysis
countermeasure for the Montgomery power ladder in elliptic curve cryptography”,
in: Math. Comput. Model. 55.1-2 (2012), pp. 256–267, doi: 10.1016/j.mcm.2011.
06.017.
[Wil27] Edwin B. Wilson, “Probable Inference, the Law of Succession, and Statistical Infer-
ence”, in: Journal of the American Statistical Association 22.158 (1927), pp. 209–212,
doi: 10.1080/01621459.1927.10502953.
[Wu00] Thomas Wu, “The SRP Authentication and Key Exchange System”, in: RFC 2945
(2000), pp. 1–8, doi: 10.17487/RFC2945.
[Wu98] Thomas D. Wu, “The Secure Remote Password Protocol”, in: NDSS 1998, The Internet
Society, 1998, url: https://www.ndss-symposium.org/ndss1998/secure-
remote-password-protocol/.
[Yen+01] Sung-Ming Yen et al., “A Countermeasure against One Physical Cryptanalysis May
Benefit Another Attack”, in: ICISC 2001, ed. by Kwangjo Kim, vol. 2288, LNCS,
Springer, 2001, pp. 414–427, doi: 10.1007/3-540-45861-1_31.
124 Bibliographie
[YJ00] Sung-Ming Yen and Marc Joye, “Checking Before Output May Not Be Enough
Against Fault-Based Cryptanalysis”, in: IEEE Trans. Computers 49.9 (2000), pp. 967–
970, doi: 10.1109/12.869328.
Titre : Problème du logarithme discret sur des courbes elliptiques
Résumé : L’usage des courbes elliptiques en d’abord plusieurs formules et algorithmes cou-
cryptographie s’est largement répandu pour as- ramment utilisés dans des implémentations pour
surer la sécurité des communications ou des tran- montrer les difficultés qui font face à un dévelop-
sactions financières. Cela est dû notamment au peur afin de réaliser une implémentation sécuri-
fait que la sécurité repose sur la difficulté du pro- sée. Nous montrons ensuite que certaines tech-
blème du logarithme discret qui permet d’utiliser niques de protection peuvent amener une vulné-
les courbes elliptiques avec des paramètres qui rabilité, dont l’une d’entre elles est nouvelle et a
assurent une efficacité. été signalée aux développeurs. Enfin, nous pro-
Dans cette thèse, nous abordons principa- posons également une nouvelle attaque par in-
lement l’aspect sécurité d’implémentations des jection de faute sur un algorithme et nous mon-
courbes elliptiques. L’utilisation de données auxi- trons également que certaines méthodes de pro-
liaires par le biais de fuites liées à l’exécution tection basées sur l’introduction d’une randomi-
du code informatique peut remettre en cause sation de la valeur secrète n’immunisent pas né-
la sécurité des protocoles. Nous analysons tout cessairement contre ce type d’attaques.
Abstract: The use of elliptic curves in cryptogra- eral formulas and algorithms commonly used in
phy has become widespread to ensure the secu- implementations to show the difficulties that a de-
rity of communications or financial transactions. veloper can face in order to realize a secure im-
This is mainly due to the fact that its security re- plementation. Then we show that some protec-
lies on the difficulty of the discrete logarithm prob- tion techniques can lead to a vulnerability, one of
lem which allows the use of elliptic curves with which is new and has been reported to develop-
parameters that ensure efficiency. ers. Finally, we propose a new fault injection at-
In this thesis, we mainly address the security tack on an algorithm and we also show that some
aspect of elliptic curves implementations. The protection methods based on the introduction of
use of auxiliary data obtained through leaks re- a randomization of the secret value are not nec-
lated to the execution of the code can compro- essarily immune to this type of attack.
mise protocols security. First, we analyze sev-