Attaques physiques contre la cryptographie sur les courbes elliptiques

Télécharger le fichier pdf d’un mémoire de fin d’études

Cryptographie moderne

L’ere moderne de la cryptographie a ete initiee par Claude E. Shannon, apres la 2nd Guerre Mondiale, via la publication de deux articles fondateurs, [Sha49b, Sha49a]. Dans ces articles, Shannon developpe di erents grands principes conduisant a la formalisation des fondements de la cryptographie. Il de nit la notion de secret (secrecy) [Sha49b].
Par secret, Shannon entend un ensemble de transformations d’un espace (celui des messages possibles) dans un second espace (celui des chi res possibles). Ainsi, chaque transformation de l’espace correspond a un chi rement pour une clef donnee.
Shannon suppose aussi que chaque transformation est non singuliere, i.e. inver-sible. Il de nit aussi la probabilite a priori d’une clef et donc d’une transformation. De m^eme, chaque message possible a, a priori, une probabilite. Alors, un attaquant qui intercepte un chi re peut calculer a posteriori les probabilites associees corres-pondant aux messages et clefs possibles. Le calcul de ces probabilites a posteriori est le probleme relatif a la cryptanalyse d’un chi rement. Il demontrera ainsi qu’une methode de chi rement invulnerable ne peut ^etre qu’un systeme de chi rement dont l’espace de clefs est de m^eme cardinal que l’espace des messages, dans ce cas Shan-non parle de secret parfait. Le chi rement de Vernam [Kah96] ou masque jetable est un secret parfait selon la de nition de Shannon si la clef est aussi longue que le message, la clef est totalement aleatoire et la clef n’est utilisee qu’une seule fois.
Simmons [Sim81, Sim85] etend la notion de secret de Shannon en de nissant l’authenticit (authenticity). La theorie de l’authenticit de Simmons est tres proche de celle de la theorie du secret de Shannon. Ces deux theories di erent sur les possibilites d’attaques d’un attaquant. L’attaquant dans la theorie de Shannon est completement passif alors que selon Simmons, il a la possibilite de construire de faux chi res (attaque par imitation) ou en intercepter et les modi er (attaque par substi-tution). Ainsi, par analogie a la theorie du secret, Simmons de nit les probabilites d’un attaquant de former un faux chi re et de modi er un chi re. L’etude de ces probabilites et leurs calculs est le centre de la theorie de l’authenticit de Simmons. Nous pouvons developper les notions de secret de Shannon et d’authenticit de Simmons en trois grandes proprietes :
De nition 1.1 (Con dentialite). La con dentialit est l’assurance de la protec-tion contre des acces non autorises a l’information.
De nition 1.2 (Integrite). L’integrit est l’assurance qu’une information n’a pas et modi ee.
De nition 1.3 (Authenticite). L’authenticit est l’assurance de l’origine de l’in-formation.
Ainsi, la notion de con dentialit decoule naturellement des proprietes de l’at-taquant de Shannon qui cherche seulement a acceder a l’information protegee par le secret. Tandis que les notions d’integrit et d’authenticit sont tirees des deux proprietes d’interference qu’a l’attaquant dans la theorie de l’authenticit de Sim-mons. Plus precisement, le concept d’integrit suit la possibilite de l’attaquant de Simmons d’e ectuer des attaques par substitution. Tandis que le concept d’authen-ticite est plus precis que celui de Simmons et decoule de la capacite qu’a l’attaquant de construire de faux chi res. Nous pouvons donc associer une probabilite de succes pour chacune des attaques:
PC : la probabilite qu’un attaquant de Shannon a de reussir a resoudre la cryptanalyse d’un chi rement. Cette probabilite est relative a la con dentialit .
PI : la probabilite qu’un attaquant de Simmons a de pouvoir forger un faux chi re. Cette probabilite est relative a l’integrit .
PA : la probabilite qu’un attaquant de Simmons a de modi er un chi re. Cette probabilite est relative a l’authenticit .
Ainsi, si une methode de chi rement permet d’avoir l’une de ces probabilites inferieures a un certain , lorsque sera proche de zero, nous dirons que cette methode de chi rement garantit la con dentialite, l’integrit et/ou l’authenticit . En pratique, nous prendrons = 1=2128 comme expliqu dans la section 1.2.3. Le choix de cet est grandement in uenc par la puissance de calcul o erte par les ordinateurs actuels. Ainsi, plus la puissance de calcul des ordinateurs augmente plus cet doit diminuer.
Pour garantir ces grandes proprietes, il existe deux familles de chi rement : la cryptographie symetrique et la cryptographie asymetrique.

Cryptographie asymetrique

La cryptographie asymetrique ou cryptographie a clef publique fut introduite par Di e et Hellman en 1976 au travers de deux publications [DH76a, DH76b], qui de nissent les principaux concepts de la cryptographie asymetrique. Cette nouvelle forme de cryptographie fut creee a n de repondre a certains problemes que la crypto-graphie symetrique n’arrivait pas a resoudre. Les principaux enjeux etant de trouver une solution au probleme d’echange de clefs et a l’authenti cation entre deux enti-tes, Alice et Bob. Pour ce faire, chacun possede une paire de clef dite publique et privee liees entre elles, la clef publique se construit a partir de la clef privee. La clef publique peut ^etre di usee a toute personne voulant communiquer tandis que la clef privee doit rester secrete. Si Bob souhaite envoyer un message de maniere securis a Alice, il lui su t de le chi rer avec la clef publique d’Alice. Alice pourra le dechi rer en utilisant sa clef privee.
Mathematiquement, la cryptographie asymetrique utilise des fonctions a sens unique avec trappe dont leur construction repose sur des problemes mathematiques di ciles a resoudre. Ces fonctions E sont simples a calculer, mais leur inverse E 1 ne peut pas ^etre calcule dans un temps raisonnable. Ainsi, la securit de cette cryp-tographie repose sur la di culte de calculer E 1. Di e et Hellman proposent alors, [DH76a, DH76b], l’utilisation d’un probleme de mathematique connu : le probleme du logarithme discret (DLP) dans un corps ni de grande caracteristique. Le pro-bleme vient du fait qu’etant donnes X; Y 2 Fp avec p un nombre premier, il est alors di cile de trouver a tel que Y = Xa[p]. Di e et Hellman proposent une fonction a sens unique qui va calculer Y en fonction de X et de a, a etant la clef privee et Y la clef publique associee.
Il existe de nombreux problemes di ciles pouvant ^etre exploites a des ns crypto-graphiques. Le plus celebre est sans doute la primitive cryptographique inventee par Rivest, Shamir et Adleman (RSA) [RSA78]. Cette primitive repose sur la di culte de factoriser les grands nombres. Il existe d’autres alternatives au DLP classique. En e et, sur le groupe d’une courbe elliptique que nous detaillerons au chapitre 2, le probleme du logarithme discret devient plus complexe pour une taille de clef equi-valente. Ce probleme du logarithme discret sur courbes elliptiques ou ECDLP a et introduit independamment par Miller [Mil86] et Koblitz [Kob87].
Ainsi, la cryptanalyse en cryptographie asymetrique va reposer sur la resolution d’un probleme mathematique par exemple factoriser un grand nombre representant le produit de deux nombres premiers inconnus dans le cas du chi rement RSA. La resolution de ces problemes mathematiques est di cile lorsque l’on considere seule-ment les algorithmes classiques et la puissance de calcul o erte par les ordinateurs classiques. Des les annees 70 emerge l’idee d’un calculateur quantique, en 1994 Peter Shor va demontrer la possibilite de factoriser e cacement un nombre a l’aide d’un ordinateur quantique [Sho94]. L’algorithme de Shor permet egalement de resoudre le probleme du logarithme discret.
Ainsi, sous l’hypothese de l’existence d’un calculateur quantique assez puissant, un systeme de chi rement tel que le RSA ne serait plus securise, il en va de m^eme pour la cryptographie basee sur les courbes elliptiques et l’ECDLP.
En 2019, IBM annonce le premier calculateur quantique de 20 qubits physiques [noa19]. Cependant, les capacites de cet ordinateur sont encore loin de pouvoir re-soudre facilement les problemes di ciles utilises en cryptographie asymetrique que l’on evalue a 50 qubits logiques. D’autant que, les experts estiment qu’il faudrait entre 1000 et 100000 qubits physiques pour avoir un qubits logique [CTV17].
Avec la menace d’un calculateur quantique des problemes mathematiques alter-natifs sont utilises a n de pouvoir leur resister. Une nouvelle cryptographie asy-metrique appelee cryptographie post-quantique a ainsi vu le jour. Les principaux problemes consideres pour la construction de primitives cryptographiques post-quantique, sont :
le probleme de vecteurs courts dans un reseau euclidien [BDK+18, DKL+18] le decodage de codes lineaires [ABB+17]
le probleme de parcours dans les isogenies des courbes elliptiques supersingu-lieres [DFJP14] l’inversion de polyn^omes multivaries [CFMR+17]
En 2016 que le NIST lance un nouvel appel d’o res [CJL+16] pour l’etablisse-ment d’un nouveau standard de cryptographie asymetrique resistant aux calculateurs quantiques.
Pour resoudre le probleme de l’echange de clefs, on s’appuie sur la cryptographie asymetrique permettant a Alice et Bob d’echanger une clef secrete symetrique. Dans l’absolue on pourrait traiter tous les echanges de cette maniere. Cependant, ces primitives cryptographiques etant tres co^uteuses en ressources et en temps de calcul leur utilisation sera limite et restreinte a l’echange de la clef secrete qui pourra par suite ^etre utilisee par la cryptographie symetrique [Res18].
Cette cryptographie permet egalement de repondre au probleme de l’authenti – cation. De la m^eme maniere que dans le probleme de l’echange de clef, il est di cile d’authenti er une entit de facon securisee sans avoir echange au prealable une clef avec celle-ci. Cependant, pour echanger une clef secrete, il faut au prealable s’assurer de l’identit de l’entit avec laquelle l’echange est e ectu . Ainsi, la cryptographie a clef publique o re la possibilite d’authenti er une entit sans avoir a echanger en amont une clef secrete via un mecanisme de signature. Si Alice veut alors authenti-er Bob, elle va transmettre un nombre aleatoire que Bob signera avec sa clef privee. Alice pourra ensuite veri er la signature en utilisant la clef publique de Bob.

Arithmetiques sur les corps nis de caracte-ristique 2

Dans cette these nous orienterons nos travaux sur les corps nis de caracteris-tiques 2. Les resultats precedents restent toujours valides dans ce cas particulier.

Nous decrirons la representation polyn^omiale de ces corps d’un point de vue informatique. Nous detaillerons l’arithmetique des corps nis, necessaire pour ef-fectuer des calculs sur les courbes elliptiques. Dans le cas de la caracteristique 2, l’arithmetique est tres di erente de l’arithmetique en grande caracteristique. Cette di erence provient de la representation des elements dans F2d et de l’arithmetique simple de F2. Il en decoule une arithmetique beaucoup plus simple a implementer, car en caracteristique 2, les elements sont non signes et nous n’avons pas a propager la retenue. Ce dernier point est essentiel dans d’une implementation sur RISC V car comme nous l’avons vu, cf. section 1.1, l’architecture du RISC V ne possede pas de bit de contr^ole de la retenue. Ainsi, la necessit de programmer la gestion de la retenue peut rendre l’implementation complexe et plus di cilement optimisable. Cela conduira a deux consequences, le ralentissement signi catif des performances et une securit plus faible contre les attaques physiques basees sur la propagation de la retenu, cf. section 3.2.

Representation polynomiale des elements de F2d

Le corps de base de l’extension F2d est le corps F2 qui admet pour seuls elements 0 et 1. De ce fait, il est plus aise de representer un element de F2d sous forme polynomiale. Ainsi, les coe cients des mon^omes d’un element a 2 F2d sont soit 0, soit 1. 1 X a = ai i; ai 2 F2 i=0

Nous pouvons alors synthetiser cette representation en une suite de bits repr – sentant les coe cients des mon^omes de a. Cette liste de bits comporte d 1 bits et est facilement integrable dans une implementation logicielle de l’arithmetique en caracteristique 2. Dans la suite de ce travail, nous considererons un element de F2d essentiellement sous la forme d’un vecteur de bits de longueur d 1. De plus, dans le cadre de l’IoT et comme vu a la section 1.1, nous optimiserons notre implementa-tion pour une architecture 32 bits. Il est alors possible de generaliser les algorithmes decrient pour une architecture de taille arbitraire w. Par consequent, le vecteur de 1 bits sera separ en n = ddw1 e mots de w bits et tous les algorithmes de cette section traiterons ce vecteur comme une suite de mots de w bits.

Inversion

En 1985, Wang et al. [WTS+85] introduisent une methode pour calculer l’inverse d’un element a dans F2d . Leur strategie est d’utiliser le petit theoreme de Fermat qui est un cas particulier du theoreme 2.6. Cette methode permet de remplacer le calcul d’inverse par une exponentiation comportant majoritairement des elevations au carre. Ce calcul decoule de l’equation dans F2d suivante : 1 = a2d 2

Il en decoule a2d 1 = 1 par application du theoreme 2.6. Cette methode d’inver-sion a ete en premier lieu creee pour calculer des inverses sur une base normale de F2d puis a et amelioree par Itoh et Tsujii [IT88]. La cha^ne d’addition necessaire au calcul de a2d 2 depend du degr d, nous essayerons de ce fait de limiter le nombre de multiplications dans F2d a son minimum. Le detail de ces algorithmes est donne dans l’annexe B pour les di erents degres d’extensions de corps de nis a la section 4.3.1.

Reduction

Le resultat d’une multiplication dans F2d utilisant l’algorithme 2.2, ou le resultat d’une elevation au carre, fait le double de la taille des operandes d’entrees. Nous devons alors le reduire a n de limiter la taille des calculs des operations a venir. Cette reduction est alors possible a l’aide du polyn^ome irreductible de nissant l’extension de corps dans laquelle sont e ectues les calculs.

Pour ce faire, nous optons pour une implementation dediee a chaque polyn^ome irreductible consider a n de reduire au maximum le temps de calcul de cette ope-ration. Les polyn^omes utilises sont de nis dans la section 4.3.1 tandis que les details des algorithmes de reduction associes sont donnes par l’annexe A.2.

Calcul de la Trace

En considerant la de nition 2.12 de la trace d’un element a de F2d , son calcul peut s’averer co^uteux en termes de performance. Cependant, l’application des for-mules de Newton-Girard a partir de la somme des conjugues i associee au fait que l’application de trace est lineaire conduit a : d 1 d 1 Xi X Si a = ai k 2 F2d ; Tr(a) = a0 + imiad i =0 i=1

Ou les mi sont les coe cients des mon^omes du polyn^ome irreductible dont est une racine. Cette formule simpli e grandement le calcul de la trace notamment en caracteristique 2. En e et, dans ce cas precis, le calcul de la trace revient a e ectuer une suite d’additions dans F2, le polyn^ome irreductible m(X) est generalement choisi creux ce qui limite le nombre d’additions necessaires pour le calcul de la trace.

Par exemple, si m(X) = X233 + X74 + 1 (qui est l’un des polyn^omes irreductible utilise dans la norme du NIST [Gal13]), on obtient alors Tr(a) = a0 + a159 pour tout dans F2233 .

Calcul de la demi-trace

Dans le cadre d’une implementation de l’arithmetique des courbes elliptiques, nous serons amenes a resoudre des equations quadratiques dans F2d du type : x2 + x = A (2.1)

Ou A est un element de F2d . Si la trace de A est nulle, alors une telle equation admet pour solution x et x + 1. Le calcul de la demi-trace (HT) de A, de ni en fonction de la parite de d, conduit a une solution de l’equation 2.1.

Si d est impair, alors : (d 3)=2 HT(A) = A22i+1 (2.2)

Xi =0 Si d est pair, alors :d=0j=0 A2j ! HT(A) = (2.3)

Courbes Elliptiques

L’utilisation des courbes elliptiques en cryptographie (ECC) a et introduit en premier par Miller [Mil86] et Koblitz [Kob87]. Cette cryptographie repose sur la di culte de resoudre le probleme du logarithme discret sur le groupe des points d’une courbe elliptique. Les ECC ont fait l’objet d’une norme du NIST [Gal13] a partir d’une proposition de Vanstone [Van92]. Dans cette derniere, l’auteur presente l’ECDSA (Elliptic Curve Digital Signature Algorithm) qui est un algorithme de signature dont la securit repose sur l’ECDLP Elliptic Curve Di e-Hellman. Ce schema de signature est plus avantageux que le schema RSA de par la petite taille des clefs utilisees qui permettent de realiser des calculs de signatures performant, notamment dans un environnement contraint tel que l’IoT.

Dans cette section, nous detaillerons la geometrie et l’arithmetique des courbes elliptiques.

Generalit sur les courbes elliptiques

Il existe de nombreuses facons d’aborder la theorie des courbes elliptiques. Nous pouvons les considerer comme un pan de la theorie des varietes algebriques ou comme l’etude des equations de Weierstrass. Nous l’aborderons sous cet angle qui se rap-proche des applications cryptographiques. De maniere generale, nous pouvons de nir une courbe elliptique comme suit : De nition 2.13 (Courbes elliptiques). Une courbe elliptique E sur un corps K est une courbe algebrique projective lisse de genre 1 possedant un point rationnel.

Cette premiere de nition peut se traduire a l’aide des equations de Weierstrass. Ainsi, une courbe elliptique E sur un corps K est de nie par l’ensemble des points projectifs veri ant l’equation de Weierstrass : E : Y 2Z + a1XY Z + a3Y Z2 = X3 + a2X2Z + a4XZ2 + a6Z3 (2.4)

Par soucis de clarte, il est commun d’e ectuer le changement de variable x = X=Z et y = Y =Z a n d’obtenir une equation non-homogene. Dans ce cas une courbe elliptique est de nie par :

De nition 2.14 (Courbes elliptiques (Weierstrass)). Une courbe elliptique E sur un corps K est de nie par l’ensemble des points a nes veri ant l’equation de Weierstrass : E : y2 + a1xy + a3y = x3 + a2x2 + a4x + a6 (2.5)

Ou a1; ::; a6 K. A cet ensemble de point nous ajoutons le point projectif = [0 : 1 : 0], dit point a l’in ni. De plus, nous avons comme condition que les derivees partielles de la courbe E ne s’annulent pas simultanement.

Si la caracteristique de K est di erente de 2, alors nous pouvons reduire l’equa-tion 2.5 en e ectuant une substitution y ! 12 (y a1x a3) ce qui donne l’equation suivante. E : y2 = 4×3 + b2x2 + 2b4x + b6 (2.6).

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Liste des Algorithmes
1 Introduction
1.1 L’Internet des Objets
1.2 Introduction `a la cryptographie
1.2.1 Cryptologie
1.2.2 Cryptographie moderne
1.2.3 Cryptanalyse
1.3 Positionnement de la th`ese
1.4 Plan de la th`ese
1.5 Publications et communications
2 Cryptographie sur Courbes Elliptiques
2.1 Pr´erequis math´ematiques
2.2 Arithm´etiques sur les corps finis de caract´eristique 2
2.2.1 Repr´esentation polynomiale des ´el´ements de F2d
2.2.2 Addition
2.2.3 Multiplication
2.2.4 El´evation au carr´e
2.2.5 Inversion
2.2.6 R´eduction
2.2.7 Calcul de la Trace
2.2.8 Calcul de la demi-trace
2.3 Courbes Elliptiques
2.3.1 G´en´eralit´e sur les courbes elliptiques
2.3.2 Arithm´etique des courbes elliptiques
2.3.3 Les mod`eles alternatifs de Courbes Elliptiques
2.4 Courbes Binaires d’Edwards et leurs impl´ementations
2.4.1 D´efinitions et propri´et´es g´en´erales
2.4.2 Syst`emes de coordonn´ees
2.5 Protocoles cryptographiques sur les courbes elliptiques
2.5.1 Protocoles d’´echange de clefs
2.5.2 Protocoles de signatures
2.5.3 S´ecurit´e des protocoles
3 Attaques physiques contre la cryptographie sur les courbes elliptiques
3.1 Les diff´erentes attaques physiques
3.2 Etat de l’art des attaques par observation
3.2.1 Attaques temporelles
3.2.2 Attaques simples
3.2.3 Attaques verticales
3.2.4 Attaques horizontales
3.2.5 Attaques par profilages
3.3 Etat de l’art des attaques par injections de fautes
3.3.1 Attaques par fausses erreurs ou Safe-error
3.3.2 Attaques par courbes faibles
3.3.3 Attaques diff´erentielles
3.4 Contremesures face aux attaques physiques
3.4.1 Coordonn´ees al´eatoires
3.4.2 Isomorphismes al´eatoires
3.4.3 Point cach´e
3.4.4 Clef cach´ee
3.4.5 S´eparation de la clef
3.4.6 Registres al´eatoires
3.4.7 Multiplication al´eatoire
3.4.8 Validation du point
3.4.9 Validation de la coh´erence
3.5 Synth`ese th´eorique
4 G´en´eration d’un ensemble de Courbes Binaires d’Edwards pour la cryptographie
4.1 Niveau de s´ecurit´e
4.2 Crit`eres de s´ecurit´e
4.2.1 Crit`eres principaux de s´ecurit´es
4.2.2 Crit`eres secondaires de s´ecurit´e
4.3 Algorithme de g´en´eration de Courbes Elliptiques pour la cryptographie
4.3.1 Optimisation de l’arithm´etique F2m
4.3.2 Optimisation du param`etre de la Courbe Binaire d’Edwards
4.3.3 Optimisation du point g´en´erateur
4.4 Un nouvel ensemble de Courbes Binaires d’Edwards
4.5 Int´egration du mod`ele de Courbes Binaires d’Edwards dans les protocoles standards
4.5.1 Coordonn´ees diff´erentielles pour l’´echange de clef
4.5.2 Coordonn´ees diff´erentielles pour la signature
4.6 Impl´ementation et performances
4.7 Conclusion
5 Evaluation de la s´ecurit´e des BECs face aux attaques par canaux ´ auxiliaires
5.1 Evaluation de l’impl´ementation face aux attaques par canaux auxiliaires ´
5.1.1 Attaques temporelles
5.1.2 Attaques simples
5.1.3 Attaques verticales
5.1.4 Attaque par profilage
5.2 Attaque hybride par fautes diff´erentielles
5.3 Conclusion
6 S´ecurisation des impl´ementations ECCs face aux attaques par profilages
6.1 Faiblesse de la fonction d’´echange conditionnel de vecteurs
6.2 Attaque par profilage sur le cswap
6.2.1 Synchronisation des cswap
6.2.2 Construction des profils
6.2.3 R´esultats de l’attaque
6.2.4 Attaque < online >
6.3 Masquage de l’op´eration d’´echange conditionnel de vecteurs
6.3.1 R´esultats de l’attaque sur une impl´ementation masqu´ee
6.4 Conclusion
7 Conclusion et perspectives
References