INF8505: processeurs embarqués configurables Département de génie informatique et génie logiciel Processeurs configurables et cryptographie

INF8505: processeurs embarqués configurablesDépartement de génie informatique et génie logiciel

Processeurs configurableset cryptographie

Survol de la présentation

Introduction Applications cryptographiques

définitions, système à cryptographie, principes de fonctionnement, algorithmes historiques, algorithmes symétriques, algorithmes asymétriques

Opérations communes en cryptographie opérations logiques (surtout oux), arithmétique modulaire, décalage,

permutations, substitutions, insertion de bits

Besoins pour un processeur cryptographique spécialisé temps réel besoin en flot de données et interfaces mémoires besoins en calculs exercices

Résumé, conclusion, références

2INF8505: processeurs embarqués configurablesDépartement de génie informatique et génie logiciel

Pourquoi parler de cryptographie en INF8505?

La sécurité des communications est une préoccupation constante dans notre monde de plus en plus connecté.

Le chiffrement et déchiffrement des messages nécessite des opérations arithmétiques et logiques très particulières.

Les processus de chiffrement et déchiffrement sont parfois l’étape déterminante dans un système de communication.

L’ajout à un processeur configurable d’instructions spécialisées pour le chiffrement et déchiffrement est une façon efficace d’accélérer les communications.










Modèle de système à cryptographie (1)


Modèle de système à cryptographie (2)

Les clés #1 et #2 peuvent être identiques ou non.


Quelques définitions

cryptogramme (cryptogram ou cyphertext): Message rendu inintelligible grâce au chiffrement, qui ne peut être compris et utilisé que par les seules personnes en possession de la clé permettant de le déchiffrer.

chiffre (cipher): Principe de codage utilisant la substitution d'un caractère par un autre ou éventuellement par plusieurs autres en se servant d'un algorithme de transformation de complexité variable.

chiffrer (encrypt): Transformer une information en un cryptogramme, de manière à la rendre inintelligible à toute personne non autorisée et à en assurer ainsi la confidentialité.

déchiffrer (decrypt): Rétablir en clair un cryptogramme qui nous est destiné, à l'aide d'une clé de chiffrement.

cryptographe (cryptograph): Appareil servant à faciliter les opérations de chiffrement et de déchiffrement des données.


http://w3.olf.gouv.qc.ca/

Quelques principes

La plupart des chiffres peuvent être vaincus avec le temps. Le but du chiffrement est de rendre la tâche la plus difficile possible à

quiconque intercepte un message. Un système vraiment sécuritaire adopte le principe de Kerckhoff (la

maxime de Shannon): l'intrus connaît parfaitement les méthodes de chiffrage et de déchiffrage; l'intrus a accès à tout l'équipement nécessaire pour effectuer le chiffrage

ou le déchiffrage; l'intrus a accès à une grande quantité de textes en clair, de clés et de

textes chiffrés correspondants; seule la clé est secrète.


Comment chiffrer?

Le processus de chiffrement consiste à remplacer un symbole du message par un autre.

Il y a plusieurs approches. Table de correspondance: on garde en mémoire une table à deux

dimensions donnant le symbole chiffré en fonction du symbole original et de la clé.

On choisit une opération arithmétique ou logique à exécuter entre le symbole et la clé pour donner le symbole chiffré, par exemple OU exclusif.


Chiffre à clé unique (one time pad)

C’est le seul chiffre 100% sûr. On prend une clé de la même taille que le message. La clé n’est connue que de Alice et Bob. La clé est parfaitement aléatoire. On n’utilise la clé que pour un seul message.


Chiffre par permutation

Les lettres du message restent intactes, mais l’ordre est inversé. La clé détermine l’ordre des lettres. Ce chiffre va à l’encontre du principe de Kerckhoff. Ce chiffre est facile à vaincre.


Chiffre par substitution simple (1)

La méthode la plus simple pour chiffrer un message. Ce chiffre est très facile à vaincre et va à l’encontre du principe de

Kerckhoff. On assigne une lettre à chacune des 26 lettres de l'alphabet, et on

remplace chaque lettre du message par sa lettre chiffrée correspondante.

Il y a plusieurs variations, adaptables par exemple au code ASCII ou à tout groupe de bits.

Exemple, code de Jules César: A devient D, B devient E, C devient F, …, X devient A, Y devient B, et Z

devient C.


www.wikipedia.org

Chiffre par substitution simple (2)

Le mécanisme d’encodage peut être plus complexe. On peut prendre toute permutation des symboles du code. Par exemple, A → D, B → G, C → Z, etc., pour 26 paires distinctes. Le chiffre reste vulnérable à une analyse basée sur la fréquence des

symboles.


Chiffre par substitution polyalphabétique (1)

Ce chiffre fonctionne comme le chiffre à substitution simple, sauf que l’alphabet de permutation change à chaque symbole.

Cette approche permet de mieux répartir la fréquence des différents symboles et ainsi de réduire l’efficacité d’une attaque basée sur la fréquence.

Une clé consiste en un mot de symboles indiquant quelle permutation utiliser. La clé est répétée de façon à former une phrase de la même longueur que le message.


Chiffre par substitution polyalphabétique (2)

Par exemple, pour la clé « citron », et le message « vivelalimonade », on aurait: clé: citroncitronci message: vivelalimonade cryptogramme: xqo…


www.wikipedia.org

Algorithme symétrique

Pour un algorithme symétrique, la clé de chiffrement et la clé de déchiffrement sont identiques.

Alice et Bob doivent s’être entendus sur la clé préalablement à la communication.

On appelle aussi ce genre d’algorithme ‘à clé privée’. Les chiffres symétriques sont plus rapides que les chiffres

asymétriques. Deux sous-types d’algorithmes symétriques:

par blocs (DES, 3DES, IDEA, Blowfish, Rijndael (AES)); par flux (RC4, A5, SEAL).


Algorithme symétrique par blocs

Plusieurs chiffres symétriques par blocs sont basés sur le réseau de Feistel (e.g. DES).

Le message est décomposé en blocs (ex. 64 bits).

Chaque bloc est décomposé en deux parties égales, L0 et R0 (pour gauche et droite).

Des sous clés Ki sont obtenues de la clé K.

Pour chaque ronde: Li = Ri-1

Ri = Li-1 oux F(Ri-1, Ki)

Le choix de la fonction F est crucial.


www.wikipedia.org

Algorithme DES (Data Encryption Standard, 1976)(chiffre symétrique par blocs)

La fonction F est décomposée en 4 étapes: 1. expansion (E): certains des 32 bits du bloc sont répétés pour former un

nouveau bloc de 48 bits (arrangement connu); 2. mélange avec une sous-clé de 48 bits, ou-exclusif bit par bit; 3. substitution (S): 8 boîtes prennent 6 bits du résultat et produisent 4 bits

par table de correspondance (ces substitutions sont connues); 4. permutation (P): les 32 bits résultants sont permutés selon un

arrangement fixe.


www.wikipedia.org

Algorithme symétrique de flux

Pour un algorithme symétrique de flux, la clé sert de graine pour générer une séquence pseudo-aléatoire de bits.

L’opération ou-exclusif est ensuite effectuée entre le flux de bits pseudo-aléatoires et les bits du message à chiffrer.

Une méthode simple de générer une séquence pseudo-aléatoire consiste à utiliser un registre à décalage rebouclé (Linear Feedback Shift Register – LFSR).

Le registre est chargé avec la clé. La séquence qui suit est pseudo-aléatoire. On doit choisir un registre suffisamment long (un LFSR de 168 bits produit une séquence de 3.7 × 1050 bits sans répétitions).


Algorithme asymétrique (1)

Un algorithme asymétrique utilise deux clés: une clé privée et une clé publique.

Il est difficile de calculer la clé privée à partir de la clé publique. Chiffrage secret:

Le message est chiffré à l’aide de la clé publique. Seule la clé privée peut permettre de déchiffrer le message.

Signature: Le message est chiffré à l’aide de la clé privée. La clé publique permet de démontrer que le message a bien été chiffré par

la clé privée, connue d’une seule personne.

Exemples: RSA, Diffie-Hellman, Rabin.



L’implémentation de chiffres asymétriques est habituellement très lente.

On utilise donc souvent un système à clé publique pour échanger une clé privée, puis le chiffrement et déchiffrement utilisent un algorithme à clé symétrique.



Pour confirmer que le message n’a pas été altéré pendant la transmission, on lui ajoute un ‘résumé de message’ (message digest).

Une fonction de hachage génère le résumé de taille fixe, indépendamment de la longueur du message.

Il est facile de calculer le résumé de message. Il est très difficile de calculer le message à partir du résumé. Il doit être très rare d’avoir deux messages avec le même résumé. L’expéditeur chiffre le résumé de message avec sa clé privée; avec la

clé publique, on confirme alors l’intégrité du message ainsi que son auteur d’un coup.


Algorithme asymétrique (4): comment obtenirune paire de clés privée et publique

Plusieurs approches. Approche basée sur une décomposition en facteurs:

choisir p et q, grands nombres premiers; calculer n = p × q; calculer φ(n) = (p – 1) × (q – 1) choisir e, 1 < e < φ(n) et e sans facteur commun avec φ(n) choisir d tel que (e × d) % φ(n) = 1 la clé publique est formée de n (le module) et e (l’exposant) la clé privée est d

Exemple: p = 7, q = 11, n = 77, φ(n) = 60 choisir e = 13, donc d = 37 la clé publique est formée de 77 et 13; la clé privée est 37

Ici, il est facile de trouver φ(n) et donc d à partir de n et e, parce qu’il est facile de factoriser 77.


Algorithme asymétrique (5):comment chiffrer et déchiffrer un message

Soit un message m, m < n. Le cryptogramme c est donné par c = me % n. Il est ‘facile’ d’effectuer ce calcul. Cependant, il est ‘très difficile’ de calculer m à partir de c, e et n. Le message peut être récupéré par l’opération m = cd % n.

Exemple: soit n = 77 et e = 13 (clé publique), et d = 37 (clé privée) soit m = 50 alors c = 5013 % 77 = 29 (!) et m = 2937 % 77 = 50 (!), ok


Algorithme asymétrique (6):exponentiation modulaire

L’exponentiation modulaire est nécessaire. Une approche naïve ne peut fonctionner même pour des nombres de

tailles modestes à cause de la taille prohibitive des résultats intermédiaires.

Il existe des algorithmes plus efficaces, comme par exemple, en langage Matlab (la valeur m est retournée):


function m = expmod(base, exp, n)% exponentiation modulaire% code inspiré de www.wikipedia.org (Modular_exponentiation)m = 1;while (exp > 0) if (mod(exp, 2) == 1) m = mod(m * base, n); end exp = floor(exp / 2); base = mod(base * base, n);end









Opérations communes en cryptographie

opérations logiques (surtout OUX) arithmétique modulaire

addition exponentiation

décalage permutations substitutions insertion de bits










Besoins en flot de donnéeset interfaces mémoires

Pour un processeur qui doit effectuer des opérations de chiffrement et déchiffrement, il y a deux cas possibles: les données résident en mémoire; ou bien, les données arrivent d’un port d’entrées/sorties.

Dans les deux cas, il est raisonnable de supposer que les données arrivent de façon séquentielle et que les données sont à une seule dimension (du point de vue de l’opération de chiffrement).

Le traitement peut être fait par blocs ou par flot. Les données à traiter sont normalement du type entier non signé. Le nombre de bits des blocs de données est normalement une

puissance de deux (64, 128 bits).


Besoins en calculs (1):chemin des données de base


Besoins en calculs (2):chemin des données amélioré


Besoins en calculs (3):exercice #1

Réseau de Feistel: donner du code en C (ou Matlab) pour implémenter un réseau de Feistel à

16 étages (supposez que la fonction F est Ri-1 xor Ki);

‘compilez’ votre code haut niveau pour une machine RISC à 32 bits; proposez un chemin des données permettant d’accélérer l’exécution de

votre code haut niveau; donnez le nouveau code ‘compilé’; calculez l’accélération attendue; donnez une mesure de complexité ajoutée par rapport à la machine RISC

de base.


Besoins en calculs (4):exercice #2

Exponentiation modulaire: considérez le code Matlab proposé; ‘compilez’ le code Matlab pour une machine RISC à 32 bits; proposez un chemin des données permettant d’accélérer l’exécution du

code Matlab; donnez le nouveau code ‘compilé’; calculez l’accélération attendue; donnez une mesure de complexité ajoutée par rapport à la machine RISC

de base.










Résumé pour la conception du processeur:options à considérer (1)

Accès au données: Pour une application ‘en ligne’, le chiffrement et déchiffrement doit se faire

au moment ou le message est transmis ou reçu. Taille des données … en blocs ou en flot. Combien de données garder dans le (ou très près du) processeur. Ne pas craindre de s’éloigner des modèles traditionnels, **surtout** pour

l’accès à la mémoire.

Calculs: Réorganisation des bits. Substitution à l’aide de tables de correspondance. Opérations logiques de base (OUX). Arithmétique modulo. Quelles sont les opérations à effectuer? Profiler, profiler, profiler. SIMD – applicable si il y a plusieurs flux simultanés. Utiliser un pipeline profond.


Résumé pour la conception du processeur:options à considérer (2)

Un système cryptographique complet devra probablement pouvoir effectuer plusieurs opérations différentes, dont: génération algorithmique d’une clé secrète; chiffrement d’un message à l’aide d’un algorithme symétrique; chiffrement de la clé secrète à l’aide d’un algorithme asymétrique; génération d’une signature et d’un résumé de message, et chiffrement à

l’aide d’un algorithme asymétrique; transmission du message; réception du message; confirmation de l’intégrité et de l’origine du message; déchiffrement de la clé secrète à l’aide d’un algorithme asymétrique; et, déchiffrement du message à l’aide d’un algorithme symétrique.


Attention à la consommation de puissance …

L’attaque dite de l’analyse de la consommation de puissance a été révélée publiquement en 1998.

Elle consiste à étudier le courant consommé par le processeur de chiffrement ou déchiffrement en fonction du temps.

Avec suffisamment de données, et on peut découvrir le fonctionnement interne du processeur et même découvrir la clé, surtout si on connaît l’algorithme implémenté.


Quelques références

P. Wilson, « Design recipes for FPGAs, » Elsevier 2007. M.B. Gokhale et P.S. Graham, « Network Security,» Springer, 2005. Plusieurs excellents articles sur wikipedia.org, à partir de « Topics in

cryptography ».


Documents

INF8505: processeurs embarqués configurables Département de génie informatique et génie logiciel Processeurs configurables et cryptographie