Présentation darticles scientifiques Ecole des Mines de Nantes1

Ecole des Mines de Nantes 1

INFORMATIQUE DIFFUSE

Présentation d’articles scientifiques


3. « Cryptography on a Speck of a Dust »

De la cryptographie dans un grain de poussière

Thomas GUERINFlorent WEBER


Problématique - Etat de l’art

Les différents algorithmes cryptographiques

Les paramètres à prendre en compte

Recommandations – Conclusion

Plan


Les technologies sans-fil miniatures deviennent omniprésentes.

Exemple : les radio-étiquettes (RFID tags)

Ce développement récent amène avec lui son lot de problèmes, notamment éthiques :

Respect de la vie privée Confidentialité Sécurisation des transactions …

Problématique de départ


Besoin de cryptographie certain Les méthodes de cryptographie sont relativement

bien maîtrisées. Mais elles sont coûteuses en calculs et donc grosses

consommatrices d’énergie.

PROBLEME : la technologie RFID est basée sur une alimentation électrique très faible.

Du coup, les processeurs utilisés ont de faibles capacités de calcul.

Problématique inhérente


Respecter les fortes contraintes de sécurité en utilisant des algorithmes de cryptographie « légers », implantables sur les « RFID tags ».

Aujourd’hui, il existe 2 options : Avec batterie Sans batterie (utilisation de l’énergie ambiante)

Enjeu


Les « extracteurs » d’énergie utilisent les diverses sources de leur environnement : Lumière Chaleur Vibration

Puissance (standard) : Aujourd’hui : ~8µW Futur : ~50µW

Pour les « RFID tags », le lecteur fournit également de l’énergie (sous la forme d’un champ électromagnétique) : Normes actuelles : ~20µW

Quelques ordres de grandeur…


Il existe 4 grandes méthodes permettant le cryptage des données :

Cryptage symétrique 1. Chiffrement par bloc 2. Chiffrement de flux

Cryptage asymétrique 3. Systèmes à clé publique

Fonctions de hachage (4.)

Etude d’algorithmes cryptographiques


Aussi appelée cryptographie à clé secrète, elle est la plus ancienne forme de chiffrement (2000 ans av. J.-C.)

2 types d’utilisation sont à considérer : Il est nécessaire de connaître l’algorithme de chiffrement sans lequel la clé

devient inutile -> le secret réside alors dans l’algorithme. Il est possible de divulguer l’algorithme à condition d’avoir satisfait à la

condition de « sécurité calculatoire » (résistance aux attaques exhaustive) et de s’assurer de l’envoi sur de la clé -> ici la sécurité repose sur l’envoi de la clé.

De nos jours les algorithmes chiffrent des suites de bits et non le texte en lui même, et on peut distinguer 2 types d’algorithme : Les algorithmes en blocs Les algorithmes à flots

La cryptographie symétrique


Ce modèle utilise une fonction F qui prend une clé k et un message M de longueur fixe n bits (aussi appelé bloc souvent 64 ou 128 bits). On itère sur F un certain nombre de tours.

Il existe différent mode de chiffrement par bloc afin de pouvoir encoder un message M de longueur quelconque.

Le principe de base de ce chiffrement suit le schéma : C1 = F(k1,M) ; C2 = F(k2,C1) ; ... Cr = F(kr,Cr − 1) ;

Les clés ki (min. 80 bits) utilisées sont déduites d'une clé maître K , cette clé doit être connue de l’émetteur et du destinataire.

L’algorithme permettant de générer les clés ki à partir de K s’appelle « algorithme de cadencement ».

1. Chiffrement par bloc (1/2)


Pour que l’algorithme soit utilisable, il faut que F soit une permutation i.e. : G tel que G(k,F(k,M)) = M

2 points critiques sont à prendre en compte pour ce type de chiffrement: L’algorithme de cadencement : s’il est mal conçu on pourrait déduire

les clés les unes des autres ou elle pourrait être mal répartie. La robustesse de la fonction F : cela signifie qu’il est difficile de

trouver son inverse sans connaître la clé k ayant servi dans le calcul de C = F(k,M).

Finalement dans le cas où C,F et G sont connus il n’est possible de déchiffrer un message M qu’en réalisant un test exhaustif des clés k : X = G(k,C); Y = F(k,X); Si pour un k donné Y=C, on est assuré de pouvoir déchiffrer M

1.Chiffrement par bloc (2/2)


Le Chiffrement de flux suit le schéma suivant :

Génération de pseudo-aléa, appelé flux de clé (keystream) que l’on combine (souvent par XOR) avec le flux de données.

La clé est aussi longue que le message.

2. Chiffrement de flux (1/2)


2 grandes catégories de chiffrement de flux :◦ Le chiffrement synchrone : la sortie du GPA ne

dépend que de son état interne.◦ Le chiffrement asynchrone: la sortie du GPA

dépend de son état interne et de plusieurs symboles du message.

Sécurité difficile à atteindre (pas de preuve).

2. Chiffrement de flux (2/2)


Méthode de chiffrement s’opposant à la cryptographie symétrique.

Repose en général sur le principe de système clé publique/clé privée.

Elle requiert l’utilisation de fonction : A sens unique : facile à calculer mais extrêmement

difficile à inverser. A brèche secrète : qui dispose en plus d'une

information secrète (souvent une clé), permettant de revenir facilement en arrière.

Cryptographie asymétrique


On génère une paire de clés (publiques et privées) La clé publique est diffusée à tout le monde et

permet d’encoder le message. La fonction de décodage (ou clé privée) quant à elle

doit rester secrète. Cependant le schéma de base présente des

problèmes d’authentification du fait de la diffusion de la clé publique.

Des mécanismes d’authentification ont du être mis en place pour résoudre ce problème (chiffrement du condensat avec la clé privée).

Les certificats numériques reposent sur ce système

3. Système à clé publique/privée


Entrée : 1 message long. Sortie : 1 empreinte (message plus court). En général utilisé pour vérifier l’intégrité d’un

fichier. Une fonction de hachage est dite

cryptographique si : Il est difficile de trouver le contenu du message à partir de la

signature (attaque sur la première pré image). A partir d'un message donné et de sa signature, il est très

difficile de générer un autre message qui donne la même signature (attaque sur la seconde pré image).

il est très difficile de trouver deux messages aléatoires qui donnent la même signature (résistance aux collisions).

4. Fonction de hachage (1/2)


Attaque sur la première pré image : suivant une signature donnée, trouver un message m tel que : hash(m) = h.

Attaque sur la seconde pré image : suivant un message m1 donné, trouver un message m2 tel que hash(m1)=hash(m2).

Attaque de collision : trouver 2 messages ayant le même h sauf que dans ce cas l’attaquant ne peut prédire la valeur de h.

4. Fonction de hachage (2/2)


Structure des algorithmes Méthodes primitives de cryptage Besoins en mémoire Choix d’implémentation

2 éléments à prendre en compte : Consommation statique : nécessaire au

fonctionnement du circuit (avec ou sans opération). Consommation dynamique : énergie utilisé à chaque

opération.

Analyse : les paramètres à prendre en compte


Idée : étudier la capacité de l’algorithme à utiliser : La « parallélisation » La « sérialisation »

La « parallélisation » diminue le temps de calcul global (simultanéité des opérations) MAIS augmente la surface du circuit et donc la consommation d’énergie (statique).

La « sérialisation » peut permettre, dans le cas où les données arrivent peu fréquemment, d’effectuer certaines étapes de calcul au préalable (gain de temps au moment de l’opération).

1. Structure des algorithmes (1/4)


« Scalability » : aptitude, pour un algorithme, à pouvoir être appliqué « à la chaîne » sur plusieurs séries de bites.

Avantage : parallélisation des calculs. Exemple :

Le chiffrement par bloc (structure circulaire, itérative)

Les systèmes à clé publique se prêtent généralement bien à la sérialisation (avec des limitations cependant).



« Modularity » : modularité. Similaire à « Scalability ».

Aptitude à pouvoir utiliser simultanément un même élément d’entrée afin de pouvoir effectuer différentes opérations EN PARALLELE.



« Regularity » : régularité. Au niveau logique :

Permet un paramétrage / réutilisation efficaces Au niveau algorithmique :

Traduit l’uniformité des opérations (peu d’opérations atomiques différentes)

Conclusion : il n’y a pas de recette miracle. Il faut faire des compromis. Il faut étudier les structures au cas par cas et

déterminer (par exemple, graphiquement) quelle configuration minimise la consommation d’énergie.



Les fonctions logiques simples (XOR…)

Les décalages et permutations fixes

Les décalages dépendants des données d’entrées

L’arithmétique « entière »

L’arithmétique « polynomiale »

Les fonctions de substitution

2. Méthodes primitives de cryptage


Exemple : le « OU » exclusif (XOR)

Peu de paramètres en entrée

Le nombre de portes logiques croît linéairement avec la « largeur » des données d’entrée.

2.1 Les fonctions logiques simples


Fixe = indépendant des données d’entrée

Utilisé dans : Le chiffrement par bloc Les fonctions de hachage

Ne demandent pas de « calcul » à proprement parler.

Sont implémentés « matériellement ».

2.2 Les décalages et permutations fixes


Très solides.

Utilisés dans le chiffrement par bloc.

Demandent beaucoup de surface de circuit.

Peu adaptés dans le cadre des très basses alimentations.

2.3 Les décalages dépendants des données d’entrée


Exemple : addition, multiplication…

Généralement les plus coûteuses en cryptographie.

Problème majeur : les retenues, qu’il faut propager. Forte consommation dynamique

Des alternatives existent, mais elles augmentent la surface du circuit. Forte consommation statique

A éviter dans le cadre des très basses alimentations.

2.4 L’arithétique « entière »


A privilégier dans le cadre des très basses alimentations car la propagation des retenues est limitée.

La régularité est améliorée.

De ce fait, beaucoup d’algorithmes de cryptographie sont ajustés pour fonctionner avec l’arithmétique « polynômiale ».

Relativement bien adaptée dans le cadre de l’étude.

2.5 L’arithmétique « polynômiale »


Appelées « S-boxes » en anglais.

Elles peuvent être implémentées de plusieurs manières : Comme une fonction arithmétique (en utilisant sa « structure

algébrique inhérente ») Comme une table de recherche (en utilisant la logique combinatoire)

BILAN : la logique combinatoire permet une consommation dynamique plus faible (meilleur rendement) mais sa taille (en terme de surface de circuit) est plus importante (consommation statique plus forte)

Dans le cadre de l’étude : privilégier l’implémentation algébrique (dans la mesure du possible).

2.6 Les fonctions de substitution


Les besoins en mémoire des algorithmes de cryptage sont multiples :

Paramètres de configuration Constantes pré-calculées Tables de substitution (S-boxes) Données temporaires …

La mémoire : Prend de la place Consomme de l’énergie

Il faut donc l’utiliser avec parcimonie.

3. Besoins en mémoire


Le « multi-cryptage » consiste à appliquer plusieurs fois de suite le même algorithme.

Avantages : Le niveau de sécurité (initialement faible) augmente

FORTEMENT avec le nombre de répétitions. La consommation d’énergie (initialement faible)

n’augmente que FAIBLEMENT.

4. Choix d’implémentation (1/2)


Dans les applications embarquées, la communication se limite généralement à un lien entre des capteurs et une station-base.

Avantage : On peut fixer des paramètres tels que la clé

publique. Les besoins en mémoire sont minimisés.

4. Choix d’implémentation (2/2)


Processeur d’étude : circuit imprimé de 13 micromètre avec une horloge cadencée à 500KHz.

Comparaison d’algorithme

Implementation Power (μW)

Area Delay (ns)

Clock cycles

NtruEncrypt (1 arithmetic unit)

19.1 2.85 0.69 29.225

NtruEncrypt (8 arithmetic units)

27.5 3.95 0.69 3,682

NH (integer) 33.6 5.29 9.92 64

PH (polynomial) 15.5 2.36 1.35 64

AES S-box (logic) 8.10 1.39 1.61 1

AES S-box (algebraic) 4.07 431 4.68 1


« Scability » est une condition essentielle pour les générations futures

L’algorithme devra être régulier et avoir un nombre réduit de primitives

Possibilité de calculs offline pour diminuer le temps de connexion

Nécessité de plusieurs tailles de clés Utilisation possible du multi hachage et du

multi cryptage

Recommandations pour les futurs algorithmes


Le choix de la méthode de chiffrement est essentiel et fortement conditionné par l’architecture sous jacente

A l’heure actuelle, aucun algorithme ne convient à 100%

L’enjeu des années à venir est de fournir un algorithme à la fois robuste et peu couteux en ressource

CONCLUSION


FINAvez-vous des questions ?

Documents

Présentation darticles scientifiques Ecole des Mines de Nantes1