Mise en œuvre matérielle d'un algorithme de chiffrement par blocs (Simon)

Analyse de l'algorithme

L'algorithme que nous allons implémenter est l'algorithme de chiffrement Simon. Simon a été proposé par des chercheurs en cryptographie de la NSA. La description détaillé de l'algorithme est accessible sur le web librement.

Simon est un algorithme de chiffrement symétrique par blocs. Le schéma de calcul utilisé (comme pour DES par exemple) est un schéma de Feistel.

Le chiffrement est décomposé en plusieurs tours. A chaque tour deux blocs sont échangés et un des bloc est combiné avec une version transformée du second bloc et à une clé de tour.

La fonction de transformation est une bijection non linéaire alors que la fonction de combinaison est généralement la fonction ou-exclusif (xor).

La clé de tour et généré à partir d'une clé initiale secrète. Le mécanisme de génération des clés de tour est généralement appelé "key schedule".

Ce schéma assure ainsi les deux propriété de diffusion et de confusion nécessaire dans un algorithme de chiffrement.

Simon est un algorithme destiné à être implémenté matériellement dans des systèmes embarqués fortement contraints. Pour ceci les choix de conception suivants ont été effectués:

  • La taille du bloc et de la clé sont configurables
    • Le nombre de tours nécessaires pour un chiffrement varie alors
  • La fonction non linéaire utilisée à chaque tour est très simple

La figure suivante montre la structure d'un tour de chiffrement:

Chemin de données

Dans cette figure les fonction S(i) représentent une rotation circulaire vers la gauche de i positions. Pratiquement, dans une implémentation matérielle, cette rotation n'utilise pas de ressources logiques et peut être réalisée en routant convenablement les signaux.

La fonction de tour n'utilise, en terme de ressources logiques, que:

  • trois portes "Ou-exclusif" (Xor),
  • une porte "Et" (And),

par bit calculé. La non linéarité est apportée par la seul fonction "Et".

La figure suivante montre la génération d'une clé de tour dans le cas d'une clé composée de trois mots.

génération de la clé de tour

La fonction générant les clés de tour est linéaire. Une séquence pseudo aléatoire connue (salti) est ajouté à la clé pour éviter certaines faiblesses de la clé. Vous remarquez aussi que les rotation sont faites dans un sens opposé à ce qui est fait dans le chemin de donnée.

Mise en évidence du chemin de donnée et du contrôle

Les blocs de données qui sont chiffrées viennent du monde extérieur. Nous devons tout d'abord définir l'interface avec ce monde extérieur:

  • comment les données sont présentées,
  • comment démarré un chiffrement,
  • comment savoir que le chiffrement est fini.

Interface avec le monde extérieur

Ici, nous supposerons que le bloc de données à chiffrer ainsi que la clé sont présentées en "parallèle". Une impulsion du signal "start" indique que le chiffrement peut commencer.

Une fois le chiffrement fini, le signal "done" passe à un indiquant que la valeur présentée sur la sortie "ciphertext" est valide.

En plus de ces signaux, nous avons aussi une entrée pour le signal d'horloge "clk" et de remise à zéro "nrst".

Le module est divisé en trois sous parties:

  • simon_dp: pour le chiffrement des blocs de données
  • simon_ks: pour la génération de la clé de tour
  • simon_ctrl: pour la génération des signaux de contrôle

Déoupage en sous-blocs

Dans la figure précédente, apparaissent les signaux internes suivants:

  • rKey : la clé partielle générée par le key schedule qui est utilisée pour chaque tour de chiffrement
  • compute : signal de contrôle indiquent que le chiffrement peut avancer. Ce signal permet, entre autre, de synchroniser la génération de la clé de tour et le chiffrement.

Le bloc de contrôle a le fonctionnement suivant:

  • Fige le système en attendant l'impulsion start. Le signal compute est maintenu bas (0).
  • Au cycle d'horloge suivant l'arrivée de l'impulsion start, le chiffrement démarre. Le signal compute passe à l'état haut (1).
  • Au bout du nombre de cycles d'horloge nécessaires au chiffrement, le signal compute repasse à l'état bas (0) et le signal done passe à l'état haut (1) indiquant la fin du chiffrement et que le résultat présent sur la sortie ciphertext est valide.

Mise en œuvre

Téléchargez l'archive suivante contenant le code source du projet.

Le répertoire simon contient les sous dossiers suivants:

  • src : contenant les sources SystemVerilog du module
  • sim : contenant un environnement de simulation
  • syn : contenant un environnement pour la synthèse

Durant cette séance, vous travaillerez à la réalisation de deux sous module du module de chiffrement.

  • le contrôleur (correspondant au fichier simon_ctrl.sv)
  • le chemin de données (correspondant au fichier simon_dp.sv)

La configuration de Simon que nous implémenterons aura les paramètres suivants:

  • Taille d'un bloc de données 64 bits
  • Taille de la clé 96 bits
  • Nombre de tours pour un chiffrement 42

Le fichier simon_pkg.sv contient la définition de certaines constantes auxquelles vous pourrez faire appel.

Le répertoire simple_uart contient quant à lui les éléments nécessaires à la mise en œuvre sur le FPGA ainsi qu'à la communication avec le PC.

Réalisation contrôleur

Éditez le fichier simon_ctrl.sv.

module simon_ctrl  (
                       clk,
                       nrst,
                       start,
                       eoc,
                       compute
                      );

// Pour pouvoir utiliser la constante N_ROUNDS correspondant aux nombre de
// tours de chiffrement
import simon_pkg::N_ROUNDS;

input        clk;
input        nrst;
input        start;
output logic eoc;
output logic compute;

... A completer ...

endmodule
 

Complétez le pour générer correctement les signaux eoc et compute.

Réalisation du chemin de donnée

Éditez le fichier simon_dp.sv.

module simon_dp (
                    clk,
                    nrst,
                    plaintext,
                    rkey,
                    compute,
                    ciphertext
                  );

// Pour pouvoir utiliser les types de données prédéfini dans le paquetage
import simon_pkg::*;

input  clk;
input  nrst;
input  compute;
input  data_t plaintext;
output data_t ciphertext;
input  rkey_t rkey;


// Registre de données
data_t Dreg;
// Signal interne
data_t Dnext;

// La sortie correspond au registre de donnée
assign ciphertext =  Dreg;

... A completer ...

endmodule

Complétez le module en ajoutant les éléments suivants:

  • Le registre de données Dreg :
    • Changement d'état au front montant de l'horloge
    • Remise à zéro asynchrone.
  • Le bloc combinatoire permettant le calcul de la valeur suivante du registre Dnext
    • Si compute est bas on chargera le registre avec l'entrée plaintext
    • Si compute est haut on chiffre

Simulation

Dans le répertoire sim vous trouverez un environnement de simulation pour votre module. Un testbench simule le fonctionnement du module et compare le résultat en sortie avec un modèle de référence.

Pour lancer la simulation, exécutez la commande:

make simon

Plusieurs tirages aléatoires des blocs de données et de la clé sont injectés en entrée du module et les résultats des simulations sont affichés dans le terminal. Si le résultat est diffèrent de la valeur obtenue avec le modèle de référence, un message d'erreur est affiché.

Vous pouvez aussi lancer la simulation en mode graphique pour observer l'état des signaux internes en utilisant la commande:

make simon_gui

Dans ce cas la simulation ne démarre pas automatiquement, vous pouvez alors sélectionner les signaux à observer avant de la démarrer.

Synthèse

Pour faire la synthèse du module pour le FPGA cible, vous pouvez utiliser les scripts présents dans le répertoire syn. Dans ce répertoire, lancer la commande:

make

L'outil de synthèse precision synthesis est utilisé ici.

Prenez le temps d'analyser le résultat de cette synthèse:

  • schémas RTL et technologique
  • rapport de surface et de timing
  • chemin critique ...

Interface avec l'hôte

Pour pouvoir tester pratiquement le module de chiffrement, modifier ses entrées, déclencher un chiffrement et récupérer le résultat à partir d'un PC, nous utiliserons une interface série. Cette interface permet de transférer octet par octet les données à destination et venant du module.

Au dessus de cette interface un protocole permet d'adresser de façon individuelle des registres liés au module de chiffrement.

  • 8 registres pour les 64 bits du bloc de données à chiffrer,
  • 12 registres pour les 96 bits de clé,
  • 8 registres pour les 64 bits du résultat du chiffrement
  • Un registre pour déclencher le chiffrement.

interface uart et registres

La communication série fonctionne à une vitesse de 115200 bits/s. Chaque octet transféré est précédé d'un bit (start) marquant le début d'un transfert et d'un bit (stop) marquant la fin.

Notez qu'ici la vitesse de transfert lente par rapport à la fréquence de fonctionnement du module de chiffrement sur le FPGA.

Le protocole implémenté est le suivant:

  • une première écriture permet de sélectionner le registre cible,
    • les 7 bits de poids faibles correspondent à l'indice du registre cible
    • le bit de poids fort indique s'il s'agit d'une lecture ou d'une écriture
  • Puis:
    • En cas de lecture, le module renvoie automatiquement le contenu du registre
    • En cas d'écriture, une seconde écriture modifie le contenu du registre sélectionné

Séquence d'écriture

Séquence de lecture

Le répertoire soft contient un exemple de code en Python qui montre une implémentation de ce protocole ainsi qu'une séquence complète de chiffrement.

Mise en œuvre sur la carte DE2

Présentation de la structure générale d'un projet FPGA

Dans le répertoire syn vous pouvez lancer la synthèse du projet complet. Ce projet contient en plus du module de chiffrement et de l'interface uart les éléments suivants:

  • un module définissant toutes les entrées/sorties de la carte
    • en plus de ce que nous avons vu jusqu'ici ce module inclue l'installation d'une PLL pour pouvoir générer une horloge à 24MHz à partir de l'oscillateur de 50MHz disponible sur la carte.
  • Des fichiers de contraintes pour:
    • des contraintes sur le modèle de FPGA utilisé,
    • définir la relation entre les noms des signaux utilisés et les pins du FPGA,
    • des contraintes de timings

Pour lancer la synthèse il suffit de faire make!

Pour analyser le résultat de la synthèse et du placement routage vous pouvez ouvrir le projet généré. Lancez la commande:

quartus DE2_TOP

quartus est un outil intégré de développent fourni par Altera le fabriquant du FPGA utilisé.

Test Sur la maquette:

Si tout c'est bien passé un fichier binaire destiné à programmer le FPGA a du être généré (DE2_TOP.sof). Ce fichier n'est pas un programme, il ne sera pas exécuté par le FPGA!

Ce fichier contient la configuration des différents blocs internes du FPGA:

  • les LUTs,
  • les interconnexions,
  • ...

Pour programmer le FPGA, vérifiez tout d'abord que la carte est alimentée et que le câble usb la reliant au PC est branché: Puis lancez la commande:

quartus DE2_TOP

Pour tester le module de chiffrement, vérifiez que le câble série relie bien la carte FPGA au PC puis utilisez l'exemple de code précédemment vu.