Analyse différentiel de consommation (DPA) et attaque address-bit DPA 

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

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 xz et yz , le triplé (x, y, z) correspond au point représenté en coordonnées projectives.
Les coordonnées XZ sont similaires aux coordonnées projectives à la seule différence que la coordonnée y est ignorée. Par conséquent, un point P est représenté par le couple (x, z).
Les coordonnées jacobiennes sont également constituées d’un triplé (x, y, z) et sont obte-x y nues en substituant, respectivement, les coordonnées x et y par z2 ou z3 .
Tous ces représentations de points, mis à part les coordonnées affines, permettent d’éviter les inversions présentes dans ADD et DBL, les rendant plus performantes. Une normalisation des coordonnées x et y permet de revenir en coordonnées affines, à partir des coordonnées projectives, jacobiennes et XZ.

Multiplication scalaire

La multiplication scalaire (SM) est l’opération principale dans les protocoles ECC à la fois en terme de coût et de sécurité (p. ex. manipulation d’une clé privée). Elle consiste à effectuer [k]P , ce qui équivaut à multiplier un point P par un scalaire k. De nombreuses opérations ADD et DBL sont utilisées pour réaliser la SM. Dans la plupart des cas, [k]P se calcule par une succession de ADD et DBL. De nombreux algorithmes, avec différentes caractéristiques, permettent d’effectuer la SM. Dans cette partie, quelques-uns seront décrits.

Doublement et addition (DA)

L’algorithme le plus simple pour réaliser une SM est le doublement et addition (DA) décrit dans l’algorithme 1. Le scalaire k est considéré en binaire, et s’écrit k = (km−1, . . . , k0)2 où m est la taille de k. À l’étape d’initialisation de DA, le point intermédiaire Q est fixé au point à l’infini (O). Ensuite, le point Q est modifié en fonction de la valeur de ki. Si ki = 0, alors Q est doublé (Q ← 2Q). Alors que si ki = 1, le point Q est doublé puis le point P lui est additionné (Q ← 2Q + P ). Lorsque tous les bits de k ont été utilisés, le résultat de la SM Q est retourné.
Le coût de cette SM est d’environ mDBL+ m2ADD. En effet, une clé k sera considérée comme cryptographiquement robuste si elle contient à peu près autant de bits à 0 et à 1.

Échelle de Montgomery (MLD)

L’algorithme le plus couramment utilisé, pour les courbes de Montgomery, est l’échelle de Montgomery (MLD), décrit dans l’algorithme 2. Tout comme DA, le scalaire est considéré en binaire. À l’étape d’initialisation, deux points intermédiaires Q1 et Q2 sont respectivement fixés à O et à P . Au cours de l’itération, les deux points Q1 et Q2 sont modifiés de manière similaire, comme illustré dans l’algorithme 2.
Comme les mêmes opérations sont effectuées quelle que soit la valeur de ki, la SM est dite régulière et coûte mADD + mDBL. L’intérêt de MLD par rapport à DA est qu’il n’y a plus de dépendance entre les opérations ADD exécutées et les bits ki du scalaire à 1.
Lors de ADD de Q1 et Q2, la valeur de la coordonnée x de Q2 − Q1 doit être connue pour pouvoir effectuer le calcul de Q1 + Q2. Cette contrainte ne pose pas de problème puisque Q2 − Q1 = P à chaque itération dans MLD. En effet, à chaque itération i de la SM, Q1 = αP et Q2 = (α + 1)P . Durant l’itération suivante i + 1, ces valeurs deviennent :— Si ki = 0 : Q1 ← 2Q1 et Q2 ← Q1 + Q2 (Q2 = (2α + 1)P Q1 = 2αP ⇒Q2−Q1=P (1.5).

Grandeurs observables

Lors du fonctionnement d’un circuit intégré, plusieurs types de paramètres physiques sont observables. Dans la littérature, les termes canaux cachés, ou canaux auxiliaires, sont sou-vent utilisés pour parler de ces paramètres observables. Les plus couramment utilisés sont la consommation électrique [85], le rayonnement électromagnétique (EM) [1] et le temps d’exécu-tion [78, 40, 19]. Le rayonnement thermique (ou dissipation de température) [65] et le bruit [51] peuvent aussi être employés pour réaliser des SCA.
Ces paramètres sont mesurables grâce à différents instruments, tel qu’un oscilloscope cou-plés à des dispositifs de mesures (p. ex. des sondes). Un oscilloscope permet de mesurer l’intensité du courant, grâce à une résistance insérée en série dans le circuit d’alimentation. Comme la puissance consommée est proportionnelle à l’intensité du courant, la consomma-tion électrique peut être déduite.
Le principe est similaire pour le rayonnement EM qui nécessite l’utilisation de sondes élec-tromagnétiques. Deux méthodes de mesure sont possibles : mesure globale ou mesure locale. Ces deux méthodes nécessitent deux types de sondes différentes. Une sonde en forme de boucle, illustrée à la figure 2.1(a), permet une mesure globale. Au contraire, une toute petite sonde ou micro-sonde, comme illustrée à la figure 2.1(b), placée à un endroit spécifique du circuit, permet une mesure locale.
Le rayonnement thermique est corrélé avec le modèle électrique. Par conséquent, il peut servir pour réaliser une attaque SCA, comme illustré à la figure 2.2. Cette figure schématise une attaque réalisée dans [65] grâce au rayonnement thermique. La dissipation de température augmente si l’activité du circuit est élevée. Au contraire, elle diminue lorsque l’activité est faible. Comme la variation de la température, dans le circuit et le boîtier contenant le circuit, est en général assez lente, les mesures sont souvent peu précises pour des circuits avec des fréquences d’horloge rapides.
La récupération des mesures est la première étape d’une SCA. Une fois que l’attaquant a en sa possession les traces, il peut appliquer différentes méthodes pour retrouver des informations secrètes.

Attaques par observation

Maintenant que notre adversaire possède des traces mesurées lors de l’exécution du sys-tème, il lui faut les exploiter. Pour cela, plusieurs méthodes s’offrent à lui. Ces méthodes cor-respondent à des attaques différentes qui sont décrites dans cette section où seule la consom-mation électrique est considérée. Néanmoins, la plupart de ces attaques sont réalisables avec les différents paramètres physiques mesurables.

Attaques par observation

Analyse simple de consommation (SPA)

L’analyse simple de consommation [80, 79], ou Simple Power Analysis (SPA), est possible lorsque la séquence d’opérations exécutée dépend d’informations secrètes (p. ex. la clé pri-vée). Dans ce cas, une seule trace (ou très peu) est nécessaire.
ECC, comme RSA, est particulièrement sensible à cette attaque. En effet, lorsque les for-mules d’addition (ADD) et de doublement (DBL) sont différentes, les distinguer sur une trace est possible. Par conséquent, si la multiplication scalaire (SM) est effectuée avec un algorithme comme le doublement et addition (DA), alors l’adversaire peut retrouver la clé par une lec-ture de la trace. La figure 2.3 représente le principe d’une SPA sur ECC. Deux motifs sont distinguables ; d’une part ADD et d’autre part DBL. Ainsi, lorsque deux motifs de DBL sont observés consécu-tivement (aux itérations i et i + 1), l’attaquant sait que le i-ème bit est égal à 0. Malgré sa simplicité, une attaque SPA a des limites, en particulier lorsque les différences (entre les deux motifs) sont bien plus petites que le bruit (fonctionnement et mesure).

Analyse différentiel de consommation (DPA) et attaque address-bit DPA

Une analyse différentielle de consommation (DPA) [80, 79], nécessite un grand nombre de traces de consommation ti pour différents messages mi. Pour réaliser cette attaque, l’attaquant doit être capable de faire rejouer partiellement l’algorithme ciblé avec des hypothèses de clé gérables (p. ex. 1 octet). Cette portion de l’algorithme doit comporter un résultat prédictible rp.
Le déroulement de l’attaque est le suivant :
— Récupération des couples (ti, mi) ;
— Exécution, pour chaque mi, de la portion de l’algorithme pour une hypothèse de clé gérable ;
— Récupération de rp pour chaque mi ;
— Répartition, dans différents groupes, des traces ti en fonction de la valeur de rp ;
— Application de la différence des moyennes ;
— Si un pic de consommation est remarqué, alors l’hypothèse est correcte ;
— Sinon, recommencer avec une nouvelle hypothèse ;
— Recommencer pour une autre partie de la clé gérable.
La figure 2.4 représente le résultat d’une attaque DPA sur 1 octet de clé d’un DES, réalisée, par moi-même, grâce aux traces du « DPA contest » de 2008/2009 [68]. Lors de cette attaque, la fuite utilisée est la distance de Hamming sur des mots de 4 bits, à la sortie de la SBox du premier tour du DES. La portion du code correspondant à cette fuite permet d’obtenir un résultat prédictible rp entre 0 et 4. Les traces ont ensuite été réparties en 5 paquets (un paquet pour chaque valeur de rp) puis moyennées afin d’appliquer la différence des moyennes. La courbe avec le pic le plus important (courbe verte), correspond à la bonne hypothèse de clé. En plus du pic de consommation correspondant à la bonne hypothèse de clé, d’autres pics sont visibles. Ce sont des pics factices. Plus le nombre de traces, utilisées lors de l’attaque, est important, moins de pics factices apparaissent, et donc plus la précision de l’attaque augmente.

Analyse safe-error (SEA)

L’attaque par analyse safe-error (SEA) [115] est une méthode d’exploitation extrêmement simple contre certaines protections. De plus, L’injection de la faute n’a pas besoin d’être très précise. Elle consiste à observer l’impact de la faute sur le calcul final. Si la faute n’a pas d’impact sur le résultat de l’opération cryptographique, alors l’adversaire peut en déduire par exemple que la valeur corrompue n’a pas été utilisée lors du calcul. Ainsi, il peut en déduire des informations sensibles. Inversement, si la faute à un impact sur le résultat alors l’adversaire peut également en déduire des informations sensibles, comme cela est illustré dans l’exemple qui suit.
Exemple 4. Lors d’une SM réalisée avec l’algorithme du doublement et addition toujours, des ADD factices sont faites si le bit de clé est égal à 0. Comme les SEA n’ont pas besoin d’être précises, l’attaquant peut « viser » l’une des sous-opérations durant une opération factice. Par conséquent, il peut choisir le moment où la faute sera injectée et peut essayer de cibler les ADD en particulier. Dans ce cas, si le résultat de la SM est correct, alors la faute injectée durant ADD n’a pas eu d’impact sur le résultat final. Cette ADD est donc une opération factice et alors le bit de clé est égal à 0. Au contraire, si le résultat de la SM est erroné, alors l’opération ADD était utile au calcul de la SM et donc le bit de clé est égal à 1. Finalement, il suffit de répéter l’opération le nombre de fois nécessaire pour retrouver la clé en totalité.

Attaques hybrides

Autres méthodes

De nombreuses autres méthodes, pas forcement applicables à ECC, d’exploitation de faute existent, tels que l’analyse par collision (CFA) ou encore la réduction de ronde (RR). L’objectif de la CFA [13] est de produire une collision entre deux sorties de l’algorithme. Pour cela, l’attaquant choisit un message m0 arbitraire qu’il chiffre en provoquant une erreur lors de l’opé- ration. Ainsi, il obtient cå = Eå(m0). Ensuite, il cherche un message M tel que E(M) = c = cå qu’il compare avec cå = Eå(m0) pour retrouver des informations sur la clé.
Le principe de la RR est de réduire le nombre de tours d’un algorithme. En effet, certains algorithmes sont basés sur la répétition de séquence identique. La sécurité, de ces algorithmes (p. ex. AES), dépend du nombre de tours effectué. Si celui-ci est réduit alors la sécurité diminue.

Attaques hybrides

Les attaques hybrides combinent les attaques par canaux cachés et par injection de fautes. Le principe est de rechercher des conditions pour lesquelles la faute apparaît. La réaction du circuit à l’injection de faute est considérée comme une fuite.

Analyse de la sensibilité à la faute (FSA)

Le stress d’un circuit est la sensibilité de celui-ci vis-à-vis d’une injection de faute. Plus le stress augmente, plus le circuit risque de faire une faute. Le but de l’analyse de la sensibilité à la faute (FSA) [83, 82] est de repérer le stress limite à partir duquel une faute est injectée. L’adversaire applique un stress au circuit. Puis il l’augmente progressivement jusqu’à ce qu’une valeur critique soit détectée. Une corrélation entre cette valeur du stress critique et les données sensibles, manipulées par le circuit, existe. Le principe de cette attaque est similaire à une CPA mais ne nécessite pas la valeur des sorties faussées.
Trois étapes articulent cette attaque. La première est la récupération des valeurs du temps critique T c pour différentes entrées m. L’attaquant obtient des couples (message mn, temps critique T cn). Ensuite, des résultats prédictibles rp(k) sont calculés en fonction des hypothèses sur la clé secrète k. L’adversaire obtient les triplets (mn, k, rp(k)). La corrélation, des n-uplets (mn, T cn) et (mn, k, F(k)), est ensuite calculée avec le coefficient de Pearson.
Cette attaque, initialement proposée pour attaquer un AES, fut adaptée à ECC dans [103]. L’attaque, réalisée sur une carte SASEBO-R avec un FPGA virtex II, cible une SM implantée avec l’algorithme de López-Dahab, sur le corps F263 avec une clé de 63 bits.

Attaques spécifiques aux courbes elliptiques

La plupart des attaques [11, 26, 14], décrites prochainement, reposent sur le fait que le paramètre a6 de la courbe E (cf équation 1.1, chap. 1) n’est pas utilisé pendant la SM. Elles consistent à transférer le problème du logarithme discret (DLP) sur une courbe moins robuste. Dans cette partie, quelques attaques sont décrites.

Faute sur le point d’entrée

Le point de base P est l’une des cibles potentielles d’une attaque. L’attaque, décrite dans [11], perturbe P afin qu’il n’appartienne plus à la courbe E. Ce point devient På tel que P / å ∈ E et P ∈ Eå, où Eå est une courbe définie par (a1, a2, a3, a4, aå6) tel que : aå6 = y2 + a1xy + a3y – x3 – a2x2 – a4x (3.4)
Le calcul de [k] · På sur la courbe Eå remplace celui de [k] · P sur la courbe E. Comme [k] · P = [k] · På sur Eå, le DLP est transféré dans un groupe d’ordre r où r est l’ordre de På et où il est plus aisé de le résoudre. Ainsi, la valeur de k mod r peut être retrouvée. Le théorème chinois des restes (CRT) permet de retrouver la valeur de k en réitérant ce procédé avec différentes valeurs de På. Cette attaque n’est possible que sur des implantations qui ne vérifient pas si le point de base P se trouve sur la courbe au début de la SM.

Faute sur le point de base après vérification

Lorsque le dispositif vérifie les entrées de l’algorithme avant la SM, l’attaque précédente ne fonctionne plus. Cependant, si les sorties de la SM ne sont pas vérifiées alors, une attaque sur un point intermédiaire [11] est faisable.
Une faute est supposée générée sur un bit d’une des coordonnées du point de base P, au début de la SM mais après la vérification de l’appartenance de P à la courbe. Le dispositif calcule alors [k] · På sur Eå avec På. Comme la faute est effectuée sur un bit de P, le point På est tel qu’il ne diffère que d’un bit de P et que På ∈ Eå. Le DLP sur E se réduit alors à un DLP sur Eå et se résoudre pour les points 5rs6 På où r est l’ordre de Eå et s un petit diviseur de r. Par conséquent, la valeur de k mod s peut être retrouvée. Comme précédemment, le CRT permet de retrouver la valeur de k en répétant cette opération pour différentes valeurs de s.

Table des matières

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 
Bibliography 

Télécharger le rapport complet