Soutenance mémoire
Dans notre société actuelle, tout le monde (ou presque) utilise la cryptographie, parfois sans s’en rendre compte. Elle est présente au quotidien, lors d’un paiement par carte bancaire ou par internet, de l’envoi d’un email, d’utilisations de réseaux sociaux ou d’applications. Bien évidemment, elle est aussi utilisée dans d’autres contextes tels que la santé ou dans le cadre militaire. Dans l’antiquité, les chefs militaires comprenaient déjà l’importance de cacher des informations à leurs ennemis. À Babylone, les messages étaient inscrits sur le crâne d’esclaves envoyés en messagers après que les cheveux eurent repoussé. Ce type de méthode, tenant plus de la stéganographie que de la cryptographie, atteint rapidement ses limites. En effet, une fois le message découvert, rien n’empêche de le lire et de le comprendre. Pour cela, des techniques ont été développées afin de garantir que seul le (ou les) destinataire(s) légitimes(s) puisse(nt) comprendre le message. Cela correspond à la confidentialité des données. Le message initial est chiffré afin de devenir incompréhensible pour des tierces personnes. Lorsque le destinataire reçoit le message, il doit le déchiffrer pour le comprendre.
Bien évidemment, la confidentialité seule ne suffit pas. Par exemple, Bob (l’un des deux interlocuteurs) reçoit un message lui donnant rendez-vous dans le parc près de chez lui. Il se rend au rendez-vous, en pensant retrouver Alice, sa meilleure amie. Une fois sur place, il constate que la personne lui ayant envoyé le message n’est pas Alice mais est un tueur en série. Ainsi, savoir qui est l’émetteur d’un message est souvent capital et correspond à l’authenticité. Malheureusement, la confidentialité et l’authenticité du message ne suffissent toujours pas. Par exemple, Bob envoie à Alice le message : « Je te dois 10 euros ». Une tierce personne pourrait modifier le message pour qu’Alice reçoive : « Je te dois 1000 euros ». Il est donc important d’être sûr que le message reçu est bien celui qui a été envoyé, ce qui correspond à l’intégrité des données.
La cryptographie peut se scinder en différentes catégories : symétrique et asymétrique (respectivement appelées cryptographique à clé privée et à clé publique), qui ont chacune leurs avantages et leurs inconvénients. Lorsque deux protagonistes utilisent la cryptographie symétrique, un secret commun est utilisé pour chiffrer et déchiffrer les communications. Ce secret commun est appelé la clé secrètes. Cette clé ne doit être connue que des participants de la discussion. Ainsi, une entité n’ayant pas cette clé ne pourra pas comprendre les communications. Ce type de cryptographie permet un chiffrement et un déchiffrement rapide. Cependant, la clé doit être échangée au préalable à chacun des participants de la communication. Les cryptosystèmes tels que DES, 3DES, AES sont des exemples connus de cryptographie symétrique. Contrairement à la cryptographie symétrique, deux protagonistes, se servant de la cryptographie asymétrique, ne possèdent pas de secret commun. Au lieu d’avoir une seule clé, chacun d’eux détient deux clés : une clé publique et une clé privée. La clé privée est gardée précieusement par son propriétaire, alors que la clé publique est connue de tous, ce qui permet d’éviter l’échange de clés préalables. Si un interlocuteur désire envoyer un message à un autre, il lui suffit de le chiffrer avec la clé publique du destinataire. L’exemple le plus connu de cryptographie asymétrique est le cryptosystème RSA [32, 59], dont la sécurité repose sur le problème de la factorisation de grands nombres. La cryptographie basée sur les courbes elliptiques (ECC) [87, 77] est un autre exemple dont la sécurité repose sur le problème du logarithme discret (DLP). Dans les systèmes embarqués, le coût de ECC (surface de silicium et consommation d’énergie) est moindre que celui de RSA. De plus, la taille des clés nécessaires, publiques et privées, est bien plus petite que celles de RSA. Par exemple, pour assurer un niveau de sécurité de 110 bits, RSA demande des clés de taille 2048 bits, contre seulement 224 bits pour ECC. Pour cette raison, ECC tend à remplacer RSA.
CRYPTOGRAPHIE BASÉE SUR LES COURBES ELLIPTIQUES
La cryptographie basée sur les courbes elliptiques (ECC pour elliptic curve cryptography) est introduite dans les années 80 par Miller [87] et Koblitz [77]. Actuellement, ECC tend à remplacer RSA pour fournir un support de cryptographie à clé publique (PKC) en particulier dans les systèmes embarqués. En effet, pour un même niveau de sécurité, ECC est plus performant et nécessite des clés plus petites que RSA [32, 59]. Par exemple, des clés d’environ 220 bits pour ECC assurent une sécurité similaire à RSA avec des clés d’environ 2000 bits. De plus, les coûts, en surface de silicium et en énergie consommée, sont bien moindres que pour RSA. Des protocoles d’échange de clé, de chiffrement ou encore de signature utilisent les courbes elliptiques. En particulier l’échange de clé de Diffie-Hellman (ECDH) [41] et la signature ECDSA [72] (pour elliptic curve digital signature agreement) sont deux protocoles couramment employés.
Lors de l’échange de clé ECDH, entre deux protagonistes Alice et Bob, la courbe E et le point P sont des paramètres publics. Alice et Bob choisissent chacun un grand entier aléatoire, respectivement a et b, et calculent respectivement aP et bP. Alice envoie aP à Bob, lui permettant de calculer abP = b(aP) et Bob transmet bP à Alice, lui permettant de calculer, à son tour, abP = a(bP). Ainsi, Alice et Bob partagent le même secret abP et ils peuvent communiquer en utilisant cette information secrète sans que l’interception des valeurs aP et bP par un attaquant puisse lui donner une quelconque information sur abP.
Une signature numérique permet d’assurer l’authentification de l’expéditeur d’un message. Généralement, elle consiste à chiffrer un message avec la clé privée et à le déchiffrer avec la clé publique. Par exemple, si Alice veux s’authentifier auprès de Bob (c.-à-d. Bob s’assure que Alice est bien son interlocutrice), alors elle chiffre un message m avec sa clé privée. Bob n’aura plus qu’à déchiffrer ce message (chiffré au préalable par Alice) avec la clé publique d’Alice. Le protocole ECDSA fonctionne sur ce principe de base.
Courbes elliptiques
Différents types de courbes elliptiques existent dans la littérature. Ces courbes ont des propriétés qui varient en fonction de leurs types. De plus, certaines sont plus performantes que d’autres en terme de vitesse de calcul d’une SM. Dans cette section, certaines courbes seront décrites, en particulier les courbes de Weierstrass et de Montgomery sur Fp, ainsi que différents types de coordonnées de points de ces courbes et différentes formules d’addition et de doublement de points.
Coordonnées des points d’une courbe elliptique
Un point d’une courbe est défini par ses coordonnées. Différentes représentations, ou types de coordonnées, existent pour écrire les points d’une courbe. Les coordonnées affines sont la plus basique d’entre-elles et consistent à représenter un point par le couple (x, y) où x, y ∈ Fp. En général, elles ne sont pas utilisées pour des implantations pratiques car une inversion est nécessaire lors de ADD et de DBL, les rendant coûteuses. D’autres types de coordonnées permettent d’éviter ces inversions durant la SM. Toutes ne seront pas décrites. Lorsque les coordonnées x et y, d’un point, sont remplacées par x/2 et y/z le triplé (x, y, z) correspond au point représenté en coordonnées projectives.
Courbes de Weierstrass
Les courbes de Weierstrass courtes [59, 32] EW sur Fp sont définies par l’équation:
EW : y2 = x3 + ax + b. (1.1)
Les coordonnées x et y dans Fp correspondent à un point de la courbe en coordonnées affines. Les variables a et b, définies dans Fp, sont des paramètres qui définissent la courbe et qui respectent des conditions spécifiques [59, 32].
Le choix de ces paramètres est capital. En effet, un mauvais choix de ces paramètres peut engendrer une courbe moins robuste que d’autres [10]. Dans certains cas, un choix judicieux permet d’avoir une SM plus efficace (p. ex. a = −3).
L’ensemble défini par EW (Fp) est l’ensemble des points (x, y) qui satisfont l’équation 1.1 et auquel le point O est ajouté. Ce point est appelé l’élément neutre de la courbe. L’ensemble Ew(Fp) possède une structure de groupe. la représentation géométrique cette loi de groupe sur R où deux cas de figure doivent être discernés : P + Q et 2Q. De plus, P + Q n’est possible que si Q ≠ ±P. En général, des formules différentes sont nécessaires pour effectuer ces deux opérations. Dans le premier cas, pour faire P + Q, une formule d’addition (ADD) de points est utilisée. Dans le second cas, une formule de doublement (DBL) de point est employée afin de calculer 2Q.
|
Table des matières
Introduction
I État de l’art
1 Cryptographie basée sur les courbes elliptiques
1.1 Courbes elliptiques
1.1.1 Coordonnées des points d’une courbe elliptique
1.1.2 Courbes de Weierstrass
1.1.3 Courbes de Montgomery
1.1.4 Autres types de courbes
1.2 Multiplication scalaire
1.2.1 Doublement et addition (DA)
1.2.2 Échelle de Montgomery (MLD)
1.2.3 Forme non-adjacente (NAF)
1.2.4 w-NAF
1.3 Conclusion
2 Attaques par observation et contre-mesures
2.1 Grandeurs observables
2.2 Attaques par observation
2.2.1 Analyse simple de consommation (SPA)
2.2.2 Analyse différentiel de consommation (DPA) et attaque address-bit DPA
2.2.3 Analyse corrélée de consommation (CPA)
2.2.4 Analyse d’information mutuelle (MIA)
2.2.5 Attaque du doublement et analyse comparative de consommation
2.2.6 Attaque par analyse de fuite de retenue
2.2.7 Analyse raffinée de consommation et attaque du point zero-value
2.2.8 Attaque horizontale
2.2.9 Attaque par profilage
2.2.10 Conclusion
2.3 Protections contre les attaques par observation
2.3.1 Uniformisation des données
2.3.2 Randomisation des données
2.3.3 Conclusion
3 Attaques par perturbation et contre-mesures
3.1 Comment injecter des fautes ?
3.1.1 Violation de contraintes temporelles
3.1.2 Injection électromagnétique
3.1.3 Variation environnement
3.1.4 Injection laser et par lumière blanche
3.2 Types d’attaques par perturbation
3.2.1 Analyse différentielle de faute (DFA)
3.2.2 Analyse safe-error (SEA)
3.2.3 Autres méthodes
3.3 Attaques hybrides
3.3.1 Analyse de la sensibilité à la faute (FSA)
3.3.2 Analyse comportementale différentielle (DBA)
3.4 Attaques spécifiques aux courbes elliptiques
3.4.1 Faute sur le point d’entrée
3.4.2 Faute sur le point de base après vérification
3.4.3 Faute sur la définition du corps
3.4.4 Faute sur les paramètres de la courbe
3.4.5 Conclusion
3.5 Protections contre les attaques par perturbation
3.5.1 Calculs redondants
3.5.2 Vérification par l’inverse
3.5.3 Détection d’une perturbation sur ECC
3.5.4 Politique d’action en cas de détection de fautes
3.5.5 Conclusion
4 Arithmétique des ordinateurs pour microcontrôleurs
4.1 La réduction modulaire
4.1.1 Réduction de Barrett
4.1.2 Réduction de Montgomery
4.1.3 Réduction avec un module spécifique
4.2 L’addition
4.3 La multiplication
4.3.1 Karatsuba
4.3.2 Toom-Cook
4.3.3 Multiplication de Taylor
4.4 Conclusion
II Contributions
5 Protections combinées contre SCA et FA
5.1 Vérification de point (PV)
5.1.1 Uniformisation grâce à la PV sur les courbes de Weierstrass
5.1.2 Vérification de point uniforme pour les courbes de Montgomery
5.2 Compteur d’itération
5.2.1 Tentatives de protection du scalaire
5.2.2 Protection du scalaire avec un registre
5.2.3 Protection du scalaire avec plusieurs registres
5.3 Politique de détection de faute
5.4 Implantations et résultats expérimentaux
5.4.1 Implantation des courbes de Montgomery
5.4.2 Implantation des courbes de Weierstrass
5.4.3 Résultats expérimentaux
5.5 Conclusion
6 Simulateur d’activité au niveau arithmétique
6.1 Construction du simulateur
6.1.1 Unités arithmétiques dans le simulateur
6.1.2 Monitoring des opérations
6.1.3 Intégration des formules
6.1.4 Ordonnancement
6.1.5 Génération des fichiers et données
6.1.6 Exécution et fusion des traces
6.2 Génération et exploitation de traces
6.2.1 Impact des opérandes sur les opérations de corps
6.2.2 Attaques SPA
6.2.3 Attaques DPA grâce au simulateur
6.3 Conclusion
7 Conclusion et perspectives
Conclusion
Bibliography
