Architectures Reconfigurables et Cryptographie

Définitions

   Le terme « architecture reconfigurable » suscite toujours d’intenses débats. Partant du principe que reconfiguration signifie le changement des fonctionnalités d’une architecture après le processus de fabrication, on peut considérer que le processeur générique est le plus reconfigurable des systèmes numériques, car il peut changer de comportement à chaque cycle d’horloge. Pourtant il est possible de dire qu’il est l’un des moins flexibles, car son architecture câblée ne se modifie pas après sa fabrication. De plus, les processeurs génériques n’exploitent que faiblement le parallélisme. Dans ce document les architectures numériques ne seront considérées comme reconfigurables que si elles comportent plusieurs composants de base tels que éléments de calculs reconfigurables, interconnectés par un moyen d’interconnexion lui aussi reconfigurable. L’exemple classique d’un dispositif avec cette caractéristique est le FPGA1 , mais d’autres circuits en font partie. Le FPGA est un exemple d’architecture reconfigurable à petit grain. Dans ce domaine le grain est l’unité de calcul de base. La taille du grain est donnée par la taille des données atomiques qui l’architecture en question est capable de manipuler à chaque opération. Dans un FPGA les données sont représentées bit à bit, et calculées à l’aide des tables de vérité (LUT – look-up tables). Un dispositif reconfigurable comprenant des opérateurs comme multiplieurs, additioneurs, multiplexeurs, par exemple, peut être considéré comme appartenant à la catégorie des architectures reconfigurables à grain moyen. Cependant, un dispositif composé par des unités logiques et arithmétiques interliées par un réseau intra-circuit peut être considéré comme étant une architecture reconfigurable à gros grain. Cette définition de taille de grain peut être étendue par rapport au fichier de configuration des architectures reconfigurables. Une architecture à petit grain est configurée normalement par un bitstream (flot de bits). De l’autre côté, la configuration d’une architecture à gros grain est faite à l’aide d’un fichier comprenant la programmation de toutes les unités de calcul. Une architecture reconfigurable peut être reconfigurable de manière statique ou dynamique, complète ou partielle. La reconfiguration dynamique est celle qui permet que le comportement d’un circuit soit modifié sans que l’application qu’il tourne soit complètement arrêtée. Au contraire, la reconfiguration statique demande que le circuit soit mis hors tension pour que la nouvelle configuration puisse être chargée. Une reconfiguration, qu’elle soit statique ou dynamique, peut être totale ou partielle. Dans le premier cas, tout le fichier de configuration est téléchargé vers le circuit. Dans le deuxième, seule la partie du fichier de configuration correspondant à des modifications de fonctionnalité nécessaires est envoyée au circuit. Les systèmes dynamiquement reconfigurables (SDR) permettent la spécialisation de la logique implantée et/ou du routage des ressources de calcul en cours de fonctionnement. La Figure 1.1 illustre la reconfiguration dynamique au travers d’un graphique en trois axes. Les axes X et Z indiquent le plan spatial, dans lequel le routage et le placement de la logique sont réalisés. Les systèmes reconfigurables de façon statique ne peuvent qu’être vus dans ce plan. Pour les SDR il est nécessaire d’effectuer une analyse temporelle des reconfigurations, car le comportement du dispositif change dans le temps, sans l’arrêt du système. Pour cela, il a été introduit l’axe Y, qui indique les différentes implantations de modules fonctionnels (cœurs) dans le dispositif, par rapport au moment d’arrivée

L’objectif de l’architecture

   Selon [78], une architecture reconfigurable peut avoir comme objectif, l’une des deux caractéristiques ci-dessous :
• Tolérance aux fautes :Il s’agit d’un des premiers buts du domaine de la reconfiguration. Durant la fabrication et l’utilisation d’un circuit, il y a une probabilité que ce circuit devienne défectueux. A l’époque de la publication de l’article de Radunovic [78], dans des architectures classiques, un problème de ce genre implique que le système entier soit inutilisable. Néanmoins, dans une architecture reconfigurable la partie défectueuse du système peut être détectée et remplacée.
• Accélération : L’utilisation des architectures reconfigurables pour accélérer les performances des systèmes a vu le jour dans les années 80, principalement due à sa capacité d’implanter des algorithmes d’une manière plus performante que sur des processeurs génériques, en exploitant par exemple le parallélisme.

Réseau d’interconnexion pour les architectures reconfigurables à gros grain

    En 2001 Reiner Hartenstein a réalisé une discussion à propos des architectures reconfigurables à gros grain. Dans [44] il parle des problématiques liées à la façon de programmer (configurer) une architecture reconfigurable, mais il montre aussi différentes manières de connecter les éléments qui la composent. Dans cette section ces caractéristiques sont prises comme des critères de classification. Architectures en maille Architectures mesh-based (en maille) organisent ses éléments de calcul dans une matrice rectangulaire 2-D, avec des connexions horizontales et verticales, qui supportent un riche réseau de communication, privilégiant les échanges voisin à voisin, de façon à privilégier le parallélisme. Typiquement sont ajoutés des lignes longues établissant les connexions de longueur supérieure à 1.
Architectures en vecteur linéaire Quelques architectures reconfigurables sont basées sur des vecteurs linéaires (linear arrays), avec une communication voisin à voisin, envisageant le mapping de pipelines. Si les pipelines ont des divergences, alors des ressources de routage additionnelles sont nécessaires, comme des lignes plus longues, souvent nécessitant une segmentation.
Architectures en croisillon La ressource de routage le plus performant est un commutateur en croix (crossbar ), car il facilite le routage parmi tous les éléments de calcul. Aux critères de Hartenstein il est possible d’ajouter celui du réseau sur puce, moyen de communication intra circuit(NoC) qui se développe de manière accéléré dernièrement. 3Network on Chip.
Architectures basées sur un réseau sur puce Récemment les réseaux sur puce ont vu le jour comme une alternative pour connecter des cœurs hétérogènes. Pourtant ces réseaux peuvent servir de média de communication pour une matrice homogène d’éléments de calcul, permettant la construction d’architectures à gros grain très flexibles.

Niveaux de reconfiguration

   Conformément à ce qui est avancé dans la Section 1.1, il existe différents niveaux d’abstraction selon lesquels il est possible de classiffier le degré de reconfiguration d’une architecture. Raphaël David [30] propose une classification selon le potentiel de reconfiguration qui reflète notamment les caractéristiques des microprocesseurs, des FPGAs et des architectures reconfigurables à gros grain.
Niveau système Ce niveau de reconfiguration traite le changement de fonctionnalité des processeurs via la modification de l’orientation du chemin de données. Les données sont acheminées vers des unités de calcul (ou vers les registres, ou la mémoire) selon les besoins de l’application, en modifiant des bits dans les commutateurs et multiplexeurs dans l’architecture. Cela permet une très grande flexibilité logicielle, pourtant, les unités de calcul ne se modifient pas, ce que entraîne une certaine rigidité matérielle.
Niveau fonctionnel Pour assouplir cet effet, des nouvelles architectures orientées flot de données ont été proposées. Une architecture reconfigurable au niveau fonctionnel suppose une multitude d’unités de calcul interconnectés par un réseau d’interconnexion. Étant donné la taille du chemin de données de ces architectures, elles sont souvent appelées architectures reconfigurables à gros grain. Le problème de cet approche est la difficulté de trouver un modèle fiable de programmation, au contraire des architectures du type processeur.
Niveau logique Une architecture est dite reconfigurable au niveau logique quand elle est composée de plusieurs unités de calcul et avec un riche réseau d’interconnexion, avec un chemin de données de faible largeur. Les unités de calcul opèrent au niveau logique, implantant des fonctions booléenes. Normalement, pour implanter une application, il est nécessaire de disposer d’une grande quantité de ressources, aussi bien que l’utilisation d’un complexe réseau de communication. Cela induit une faible fréquence de reconfiguration, malgré son apport en flexibilité matérielle.

Dart

   DART [28] est une architecture reconfigurable développée dans le but d’apporter à la fois puissance de calcul et faible consommation aux applications mobiles de troisième génération. Cette architecture est composée par des grappes d’unités de calcul, comme décrit la Figure 1.6. Ces grappes peuvent fonctionner indépendamment où en combinaison avec les autres. Cela diminue la complexité du contrôle de l’ensemble du système. Donc la priorité du contrôleur du système n’est pas de gérer chaque grappe, mais d’agencer des tâches qui seront exécutées par les grappes, selon sa priorité et la disponibilité des ressources. Ainsi le contrôleur n’a pas à ordonnancer les instructions de chaque tâche, mais simplement spécifier aux grappes quel tâche elles doivent exécuter. L’organisation hiérarchique de DART permet, au delà de la distribution du contrôle, la répartition du calcul. Par conséquent, il est possible de joindre un grand nombre de ressources sans augmenter le coût d’interconnexion. En effet, cela entraîne une amélioration de la performance et de la consommation. De plus, cette organisation facilite le développement d’outils de programmation. Pour donner plus de flexibilité, tout en restant simple à programmer, les grappes comprennent des unités de calcul appelées DataPath Reconfigurable (DPR), et un petit cœur FPGA (voir Figure 1.4. 1.7). Les DPRs peuvent être connectés les uns avec les autres à travers d’un réseau du type maille segmenté, ce qui permet un calcul massivement parallèle ; mais ils peuvent aussi agir comme des unités indépendantes, opérant sans liaison les uns avec les autres, sur différentes flots de tâches. Toutes les primitives de calcul accèdent à la même mémoire, et la reconfiguration est gérée par un contrôleur local. La reconfiguration de la zone FPGA est faite de façon série, pendant que la reconfiguration des DPR arrive de manière semblable à celle des microprocesseurs. La différence c’est que le schéma de configuration du DART évite des lectures excessives de la mémoire d’instructions, en stockant les microinstructions dans des registres dans chaque DPR. Par conséquent, l’architecture devient efficace du point de vue consommation d’énergie. Les primitives de calcul arithmétiques du DART sont les DPRs. Chaque DPR est organisé autour de ressources fonctionnelles et de mémoires, liés selon un flexible réseau de communication. Chaque DPR possède quatre unités fonctionnelles suivies d’un registre et supportant des calculs SWP (Sub-Word Parallelism). Ce concept est justifié par la nécessité d’opérer sur des différents tailles de données, notamment codage d’audio et de video sur 8 et 16 bits. Les concepteurs de DART ont donc opté pour implanter des opérateurs arithmétiques optimisés pour les formats de données les plus ordinaires (16 bits), mais supportant SWP pour pouvoir traiter des données plus petits. Les résultats présentés en [29] montrent que les DPRs ont été synthétisés, atteignant une fréquence de 130MHz. Basés sur ce résultat, les auteurs estiment que DART peut atteindre 10, 9 GOPS par grappe. Par rapport à la consommation, DART réalise 32M0PS/mW pour des opérations sur 16 bits.

Architectures à Petit Grain

   Les architectures reconfigurables à petit grain sont des dispositifs contenant des composants logiques et un réseau d’interconnexion programmable. Les unités logiques sont programmables afin d’émuler les fonctions logiques tels que AND, OR, XOR, NOT, ou même des fonctions plus complexes comme des decodeurs. Dans la plupart des dispositifs à petit grain, notamment les FPGAs, ces éléments programmables (blocs logiques) incluent des éléments de mémoire, qui vont des simples bascules jusqu’à des blocs complets de mémoire. La hiérarchie d’interconnexion permet au concepteur de circuits une flexibilité très importante. Dans le cas des FPGAs, cette flexibilité reste au-delà de la manufacture du dispositif, et pour cela il est utilisé le terme « reconfigurable » à ce genre de dispositifs. Les dispositifs reconfigurables à petit grain, comme les FPGAs sont généralement plus lents que les ASICs ou que les architectures à gros grain, et aussi ils consomment plus d’énergie. Cependant, ils offrent des avantages intéressants. Par rapport aux ASICs, les FPGAs ont un temps plus court pour arriver sur le marché, coûtent moins cher pour faibles quantités, et restent flexibles après la fabrication. En comparaison avec les architectures à gros grain, les FPGAs offrent un ensemble d’outils de configuration et de programmation beaucoup plus mûr que les premiers. Les FPGAs ont été conçus au départ pour substituer les CPLDs comme « logique de colle » pour les PCBs. Toutefois, due à l’évolution des technologies de synthèse de silicium, la taille et la complexité des FPGAs ont augmenté, les menant au rôle de compétiteurs sur le marché des systèmes sur puce. Aujourd’hui le domaine d’applications des architectures à petit grain s’étend aux algorithmes pour l’industrie spatial, imagerie médicale, vision par ordinateur, cryptographie, au delà d’une vaste étendue d’autres domains de recherche et de développement. Dans la suite deux architectures à petit grain représentatives du marché industriel actuel sont présentées. Les FPGAs Virtex et FPSLIC ont été choisis pour ses capacités de reconfiguration dynamique, implantées de manière différent en chacun.

ARDOISE

  Le projet ARDOISE (Architecture Reconfigurable Dynamiquement Orientée Image Signal Embarquable) vise à démontrer l’intérêt des architectures matérielles à reconfiguration dynamique (RD) dans les systèmes associant contraintes temps réel fortes et versatilité des traitements. À l’heure actuelle, ARDOISE est la seule architecture développée en France, dont un prototype a effectivement été réalisé et testé en situation réelle, qui mette en oeuvre ce concept [34]. L’idée de base de cette architecture est d’enchaîner des algorithmes nécessaires au traitement d’images dans la même structure matérielle, en utilisant la reconfiguration à petit grain à quelques reprises, pendant le calcul d’une seule image. Cela équivaut à s’en servir d’un FPGA afin d’exécuter une séquence d’algorithmes selon un agenda pre-établi. Ce concept permet l’implantation d’applications sur FPGA avec une performance raisonnable, tout en gardant la flexibilité d’un microprocesseur. L’architecture d’ARDOISE est basée sur trois modules identiques (Figure 1.18). Chacun contient un FPGA à 45k portes connectés à deux mémoires locales qui stockent les résultats intermédiaires. Ces blocs identiques sont appelés MARD (Modules ARDoises) et sont contrôlés par le module GCC (Gestion des Configurations et des Communications). Le GCC permet à ARDOISE de fonctionner soit en stand alone, soit en liaison avec un DSP. Le FPGA, la mémoire et la connexion à une liaison en série autorisent la configuration du FPGA et le chargement de la mémoire flash à partir d’un PC.

La fonction de Feistel

   La fonction F observée dans la Figure 2.5 opère dans une moitié d’un bloc (donc 32-bits). Cette fonction consiste de quatre étages :
1. Expansion : Le demi-bloc de 32-bits est étendu à 48 bits en faisant usage de la permutation d’expansion, dénoté E dans le diagramme ;
2. Mixage de la clé : Le résultat est combiné avec une sous-clé utilisant le XOR. Seize sousclés de 48-bits (une pour chaque itération) sont dérivées de la clé principale à travers d’un ordonnancement de clés.
3. Substitution : Après avoir mixé à la sous-clé, le bloc est alors divisé dans huit parties de six-bits ; avant de passer par les boîtes de substitution (S-boxes – Substitution Boxes). Chacune de ces 8 S-boxes transforment les six bits d’entrées vers 4 bits de sortie, avec une transformation non-linéaire. Les S-Boxes fournissent le cœur de la sécurité du DES. Sans les S-box les transformations seraient linéaires, et par conséquent l’algorithme serait facilement cassé.
4. Permutation :Finalement, les sorties à 32-bits à partir des S-boxes sont disposées en accord avec un tableau fixe de permutation, appelée P − Box. L’alternance de substitutions, permutations et expansions provoquent le concept de « confusion et diffusion » respectivement ; concept identifié par Shannon dans les années 40 comme étant des conditions nécessaires pour un algorithme de cryptographie sûr.

Table des matières

Introduction
1 Architectures reconfigurables 
1.1 Définitions
1.2 Classification 
1.2.1 La Taxonomie de Radunovic [78]
1.2.2 Les critères de Page [76]
1.2.3 Statique versus Dynamique [85]
1.2.4 Réseau d’interconnexion pour les architectures reconfigurables à gros grain
1.2.5 Modèles de reconfiguration
1.2.6 Niveaux de reconfiguration
1.3 Métriques
1.3.1 La densité fonctionnelle
1.3.2 La Rémanence
1.4 État de l’art 
1.4.1 Architectures à Gros Grain
1.4.2 Architectures à Grain Moyen
1.4.3 Architectures à Petit Grain
1.5 Tendances 
1.6 Le Reconfigurable pour la cryptographie
2 Introduction à la Cryptographie 
2.1 Introduction à la cryptographie 
2.2 Types d’algorithmes de Cryptographie
2.2.1 Cryptographie à Clé Symétrique
2.2.2 Cryptographie Asymétrique
2.3 Exemples d’algorithmes de Cryptographie
2.3.1 Data Encryption Standard
2.3.2 Algorithme RSA
2.4 Nombres Premiers 
2.5 Fonctions à sens unique 
2.5.1 Fonctions à sens unique avec une trappe
2.5.2 Fonctions de hachage à sens unique
2.6 Arithmétique Modulaire
2.6.1 Congruence
2.6.2 L’Algorithme d’Euclide
2.6.3 L’inverse modulaire
2.6.4 Residue Number System
2.7 Multiplication Modulaire – L’algorithme de Montgomery
2.8 Leak Resistant Arithmetic 
2.9 Conclusion du Chapitre
3 Attaques et contremesures 
3.1 Attaques Matérielles
3.1.1 Considérations à propos de sécurité et types d’attaques SCA
3.2 Contremesures
3.2.1 État de l’art
3.2.2 Une contremesure originale : le CMG
3.2.3 Aspects de sécurité liés à la LRA
3.3 Conclusion du Chapitre
4 Vers une Implantation Matérielle du LRA 
Vers une Architecture Reconfigurable pour la Cryptographie
4.1 Démarches architecturales 
4.2 Leak Resistant Reconfigurable Architecture : Vue d’ensemble 
4.3 La composition de la LR2A 
4.3.1 Le contrôleur
4.3.2 Les éléments de calcul
4.3.3 Réseau d’Interconnexion
4.3.4 Le modèle de configuration
4.3.5 La gestion de la mémoire
4.4 Validations 
4.5 L’intérêt de la reconfiguration
4.6 Conclusion du Chapitre 
Considérations Finales
Bibliographie
Table des figures
Liste des tableaux
Annexes
Abréviations
RSA
B.1 La description succinte de l’algorithme
B.2 Le choix des nombres
B.3 Un example avec un message textuel
DES
C.4 S boxes
C.4.1 S boxes comme matrices
C.4.2 S boxes comme tableaux
C.5 Constantes de Permutation
C.6 Conversion entre différents types de données
C.7 Permutation de vecteurs et XOR
C.8 S-Boxes et la Fonction de Feistell
C.9 Commandes en ligne
C.10 Sauvegarde des fonctions et des constantes
C.11 Setup Initial
C.12 Une étape de cryptage
C.13 Les 15 étapes suivantes de cryptage
C.14 Pour decrypter
Algorithme de Montgomery
LRA
Current Mask Generator

Télécharger le rapport complet