Contrer l’attaque Simple Power Analysis efficacement dans les applications de la cryptographie asymétrique

Multiplication modulaire de Montgomery mot à mot (MontMul)

   Bosselaers et al. dans [11] donnent un algorithme complet de réduction de Montgomery. Dans le but d’éviter de grandes opérations multiprécision, on peut intégrer cette réduction mot à mot smallRed à la multiplication multiprécision (voir l’algorithme 1.4) et en déduire un algorithme de multiplication modulaire complet. La façon de procéder consiste, dans l’algorithme 1.4 de multiplication n × n, à insérer une réduction d’un mot (smallRed) entre chaque multiplication 1×n, soit à la fin de chaque itération de la boucle for de l’algorithme, afin de maintenir l’accumulateur du résultat dans une taille de n mots. Nous présentons maintenant cette méthode. Soient A, B, N < M trois entiers, et M tel que M = 2w×n où w est la taille (le nombre de bits) d’un mot machine. Comme dans l’algorithme 1.6, la multiplication de Montgomery mot à mot produit X = A · B · M−1 mod N avec X < N.

Attaques par canal auxiliaire, vue générale

   Un canal auxiliaire, de quoi s’agit-il ? Un exemple tiré des films de série B, c’est celui du cambrioleur qui ouvre un coffre-fort en tournant les tambours de sélection de la combinaison. S’il doit essayer toutes les combinaisons possibles, il lui est impossible de parvenir à ouvrir le coffre, à moins d’y passer des heures voire des jours… Mais s’il se munit d’un stéthoscope, il peut entendre les imperceptibles cliquetis mécaniques qui trahissent le passage d’un disque devant la lumière correspondant au chiffre de la combinaison. Et en quelques minutes à peine (dans les films, c’est même plus rapide, les spectateurs ne supportent guère un suspense trop long !), voilà notre cambrioleur qui ouvre le coffre ! C’est possible grâce à cette source supplémentaire d’information que constitue le bruit du mécanisme, et que l’on nomme canal auxiliaire. L’Histoire attribue aux services de renseignements britanniques (voir [34]), le MI-5, la première attaque par canal auxiliaire. En 1956, cette agence de renseignement ne parvenait pas à casser le chiffre utilisé par l’ambassade égyptienne jusqu’au jour où Peter Wright, un de leurs mathématiciens, a proposé de placer un micro près de la machine à chiffrer. Cette dernière était munie de rotors qui déterminaient la clé de chiffrement. Chaque matin, le responsable des communications réglait la machine et le micro transmettait les clics des rotors. Ceci a permis aux services de renseignements britanniques d’espionner les communications de l’ambassade égyptienne, et ce des années durant ! Autrement, la difficulté calculatoire ne permettait pas de trouver la clé et de déchiffrer les messages en temps raisonnable… De nos jours, les communications dont nous parlons sont chiffrées par des ordinateurs ou des calculateurs au sens large. Dans le cas des protocoles cryptographiques, le canal auxiliaire va dépendre de la plate-forme ou de l’appareil qui effectue les calculs. D’après la littérature, on peut dresser une liste de ces différents canaux auxiliaires possibles. Celle que nous donnons ci-après ne prétend nullement être exhaustive :
— courant ou puissance électrique instantanés ;
— rayonnement électromagnétique, y compris émissions lumineuses ;
— informations systèmes telles que défauts de cache, prédiction de sauts valides ou non, temps ou nombre de cycles du calcul…
— bruit émis par le processeur (analogue aux claquements de condensateurs) ;
— chaleur rayonnée ;
— etc.
Tous ces phénomènes physiques sont plus ou moins importants selon la plate-forme attaquée. Ainsi, les systèmes embarqués ou mobiles (cartes à puces, téléphones mobiles) vont être plus vulnérables à des mesures de courant ou électromagnétiques, du fait de leur petite taille, de la faible fréquence d’horloge et de la simplicité de leur système d’exploitation (mono-utilisateur et monotâche, parfois). Au contraire, des attaques par le biais du système deviennent plus pertinentes si on s’en prend à de «grosses» machines, par exemple des serveurs. Dans ce dernier cas, les attaques par le comptage de défauts de cache deviennent de vraies menaces, là où le courant instantané consommé devient difficile voire impossible à mesurer. C’est vrai dans le cas d’une machine importante et travaillant à fréquence d’horloge élevée, avec un système complexe multiutilisateurs et multitâches, ce qui génère beaucoup de bruit. Nous reproduisons dans la figure 3.1 les schémas de Zhou et al. dans [67] qui illustrent la différence entre le modèle de sécurité traditionnel de la cryptographie et le modèle incluant les canaux auxiliaires.

SPA : Simple Power Analysis

   La première attaque que nous examinons en détail est du type Simple Side-Channel Analysis. Cette attaque est décrite par Kocher et al. en [39] et en [38]. Nous reprenons cette description. Elle consiste à mesurer l’énergie consommée par un appareil effectuant une opération cryptographique (chiffrement, déchiffrement, signature…) Le principe est d’utiliser ces traces pour en tirer des informations sur les paramètres, notamment une clé secrète. Cette attaque ne nécessite aucune connaissance préalable d’un texte clair ou chiffré. Quand elle est possible, elle semble donc extrêmement puissante. Avec peu de moyens et quasiment instantanément, on accède à des informations secrètes impossibles à obtenir par des moyens calculatoires (en temps raisonnable). Des appareils qui échantillonnent à 20 MHz ou plus et qui transférent leurs mesures dans un simple PC se trouvent pour moins de 400 US$ d’après les auteurs dans [38], tandis que des instruments de laboratoire mesurent des signaux de l’ordre du GHz avec des précisions de l’ordre de 1%. Ceci est possible pour tous types de plates-formes, depuis les cartes à puces jusqu’aux machines de bureau et autres serveurs d’institutions, en passant pour les FPGA, ASICs… Nous ne décrivons pas en détail la sœur quasi jumelle de la SPA, la Simple Electro Magnetic Analysis (SEMA). Cette attaque ne diffère de la SPA que par le canal auxiliaire. Il ne s’agit pas de la puissance électrique consommée, mais du rayonnement électromagnétique de l’appareil en cours de calcul, comme son nom l’indique. Si la forme du signal et les motifs diffèrent quelque peu, l’interprétation qu’on en tire est identique. Et les contre-mesures s’appliquent de façon identique à la SPA comme à la SEMA.

Stratégies d’implantation des opérations sur les corps F2233 et F2409

   Les stratégies d’implantation des opérations sur le corps sont souvent similaires à celles présentées au chapitre précédent, en particulier dans la section 5.4.2. Néanmoins, certaines différences sont à mentionner sur certains points et qui concernent principalement le cas de l’implantation sur la Nexus 7 équipée du Qualcomm Snapdragon, du fait de l’architecture 32 bits de ce processeur. Nous insistons donc essentiellement sur ces spécificités. Quand nous ne mentionnons rien, c’est que la démarche est strictement celle appliquée en section 5.4.2 et le lecteur peut s’y reporter si besoin.
— Multiplication des polynômes binaires : Sur processeur Snapdragon, l’architecture ARM ne fournit pas d’instruction de multiplication sans retenue. Nous utilisons donc l’approche de Lopez et Dahab présentée dans l’algorithme 1.12 page 40, mais adaptée à la taille des mots de cette architecture, qui est de 32 bits seulement.
— Élévation au carré : Sur processeur Snapdragon, nous appliquons la technique d’insertion des zéros par l’utilisation de table que nous avons décrite dans l’algorithme 1.14 page 43, en adaptant simplement à la taille de mots de 32 bits de cette architecture.
— Opérations modulo r : Sur les deux plates-formes, nous avons implanté la multiplication multiprécision avec l’approche schoolbook et la réduction modulo r en utilisant l’approche de Montgomery [46]. Pour l’inversion, nous avons utilisé la fonction de bas niveau pour l’algorithme d’Euclide étendu de la bibliothèque GMP dans [2].

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 rapport-gratuit.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 tables
Liste des figures
Liste des algorithmes
Introduction
I État de l’art 
1 Arithmétique des anneaux Z/NZ et corps finis Fp et F2m 
1.1 Opérations sur l’anneau des entiers modulo N
1.1.1 Quelques rappels sur l’anneau (Z/NZ, +, 0, ×, 1)
1.1.2 Addition/soustraction modulaire
1.1.3 Multiplication modulaire dans Z/NZ
1.1.4 Inversion modulaire
1.2 Opérations sur le corps binaire F2m
1.2.1 Brefs rappels sur le corps F2m
1.2.2 Addition
1.2.3 Multiplication
1.2.4 Inversion
2 Protocoles, exponentiations modulaires et multiplications scalaires de point de courbe elliptique 
2.1 Protocoles
2.1.1 Protocoles basés sur le problème de la factorisation
2.1.2 Protocoles basés sur le problème du logarithme discret
2.2 Exponentiation modulaire
2.2.1 Principaux algorithmes d’exponentiation
2.3 Multiplication de point de courbe elliptique
2.3.1 Qu’est une courbe elliptique ?
2.3.2 Opérations sur le groupe des points de la courbe elliptique sur corps fini en grande caractéristique Fp
2.3.3 Opérations sur le groupe des points de la courbe elliptique sur corps fini en caractéristique 2
2.3.4 Multiplication scalaire
2.3.5 Bilan final
3 Revue des attaques par canal auxiliaire et contre-mesures 
3.1 Attaques par canal auxiliaire, vue générale
3.1.1 Classification générale
3.1.2 Attaques passives
3.1.3 Attaques actives
3.2 SPA : Simple Power Analysis
3.2.1 Description de l’attaque
3.2.2 Principales contre-mesures
3.3 Timing Attack
3.3.1 Description de l’attaque
3.3.2 Contre-mesures et conclusion
3.4 DPA : Differential Power Analysis
3.4.1 Description de l’attaque
3.4.2 Principales contre-mesures
II Contrer l’attaque SPA plus efficacement 
4 Combiner les opérations dans l’exponentiation modulaire 
4.1 Multiplications de Montgomery multiples partageant un opérande commun
4.1.1 Deux multiplications combinées de type A · B, A · C
4.1.2 Multiplications multiples partageant un opérande commun
4.1.3 Comparaison des différentes complexités
4.2 Exponentiation modulaire avec multiplications multiples partageant un opérande commun
4.2.1 Échelle binaire de Montgomery avec CombinedMontMul
4.2.2 Regular right-to-left 2γ-ary Exponentiation avec CombinedMontMul
4.2.3 Regular left-to-right 2γ-ary Exponentiation avec MultByComOp
4.2.4 Comparaisons des complexités
4.2.5 Implantations logicielles, résultats et conclusion
5 Combiner les opérations dans la multiplication scalaire de point de courbe elliptique sur F2m 
5.1 Optimisations AB, AC et AB + CD dans le cas de la multiplication CombMul
5.1.1 Optimisation AB, AC
5.1.2 Optimisation AB + CD
5.2 Optimisations AB, AC et AB + CD dans le cas de l’approche KaratRec
5.2.1 Complexité de KaratRec_ABAC
5.2.2 Complexité de KaratRec_ABpCD
5.3 Complexités et performances
5.4 Implantations de la multiplication scalaire basée sur les optimisations AB, AC et AB + CD
5.4.1 Arithmétique des courbes elliptiques
5.4.2 Stratégies d’implantation
5.4.3 Performances des implantations sur plate-forme Intel Core 2
5.4.4 Performances des implantations sur Intel Core i5
5.4.5 Conclusion sur la multiplication scalaire de point de courbe elliptique
6 Paralléliser l’échelle binaire de Montgomery 
6.1 Échelle binaire de Montgomery à base de halving et parallèle
6.1.1 Montgomery-halving
6.1.2 Approche parallèle
6.2 Implantations logicielles
6.2.1 Stratégies d’implantation des opérations sur les corps F2 233 et F2409
6.2.2 Performances des implantations logicielles
6.3 Conclusion sur l’échelle binaire de Montgomery parallélisée
7 Protection par la parallélisation 
7.1 Parallélisation, algorithme de Moreno et Hasan [48], résistance à l’attaque SPA
7.1.1 Généralités sur la parallélisation de l’approche Double-and-add
7.1.2 Présentation de l’algorithme parallèle de Moreno et Hasan [48]
7.2 Algorithmes parallèles et implantations logicielles
7.2.1 Parallélisation
7.2.2 Performances
7.3 Conclusion de ce chapitre
Conclusion
8 Annexe 
8.1 Annexe : Paramètres des courbes elliptiques
8.1.1 Courbes elliptiques sur corps binaires F2m
8.1.2 Courbe de Weierstrass sur corps premier Fp
8.1.3 Courbe Jacobi Quartic sur corps premier Fp
Bibliographie

Rapport PFE, mémoire et thèse PDFTélécharger le rapport complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *