Implémentation du DES et cryptanalyse sur FPGA

Université Catholique de Louvain
Faculté des Sciences Appliquées
Département d'Electricité [pic]
Implémentation du DES et cryptanalyse sur FPGA Promoteurs: Pr. J-D. LEGAT
Pr. B. MACQ Pr. J-J. QUISQUATER Septembre 1999 Université Catholique de Louvain
Faculté des Sciences Appliquées
Département d'Electricité [pic]
Implémentation du DES et cryptanalyse sur FPGA Promoteurs: Pr. J-D. LEGAT
Pr. B. MACQ Pr. J-J. QUISQUATER Septembre 1999 |Remerciements | Nous tenons à remercier certaines personnes pour leur aide, grâce à
laquelle nous avons pu accomplir ce mémoire dans les meilleures conditions. En premier lieu, remercions Messieurs Jean-Didier Legat, Benoît Macq
et Jean-Jacques Quisquater, les promoteurs de ce mémoire, pour leur suivi,
leurs conseils judicieux et leurs remarques perspicaces. Grâce à eux, nous
avons pu acquérir rapidement une méthode de travail efficace. Leurs
conseils ont été utiles dans les orientations à prendre. Merci également à Tanguy Gilmont pour son aide précieuse, pour le
temps et le travail qu'il nous a consacrés au jour le jour, pour son
soutien dans la résolution de certains problèmes techniques, de même que
pour avoir supporté nos questions quotidiennes. Grâce à lui, nous avons
gagné un temps vraiment précieux ainsi qu'une expérience incontestable. Nous remercions aussi spécialement Jean-Pierre David pour le temps
qu'il a passé et la patience dont il a fait preuve lors de l'utilisation de
l'outil de synthèse et de la carte multi-FPGA. Merci à François Koeune qui nous a consacré quelques heures de son
temps pour nous expliquer les points obscurs de l'article de Matsui, et
nous procurer la documentation nécessaire à la compréhension générale de la
cryptanalyse.
Enfin, remercions tous les membres de l'unité DICE pour leur
disponibilité à répondre à toute question ainsi que pour leur patience et
leur compréhension lors de nos nombreuses heures d'occupation des stations
de travail. Le 23 août 1999
Sébastien Martin |Résumé |
L'objet de ce travail est la conception d'une unité de cryptanalyse du
DES, l'implémentation de cette unité sur circuits programmables, et la
réalisation d'attaques par une méthode de cryptanalyse linéaire en vue
d'évaluer les performances de ce type d'attaques. Le DES est un standard de
chiffrement répandu dans le monde entier et se retrouvant dans de
nombreuses applications utilisées principalement pour maintenir la
confidentialité d'informations. Ainsi, notre travail consiste en une étude du DES, de ses différentes
implémentations et aboutit à une réalisation concrète sur circuit
programmable (FPGA) qui a été simulée. Le travail fait également appel aux
techniques de cryptanalyse linéaire, notamment à l'algorithme de Matsui qui
a été utilisé ici. Ces méthodes ont été testées et validées par des
simulations. La méthode de cryptanalyse selon Matsui nous a permis
concrètement de trouver un bit de clé en 122 heures. L'implémentation sur circuit programmable est le résultat de deux
démarches consécutives : d'abord, la compréhension et la maîtrise du DES et
des algorithmes de cryptanalyse utilisés ; ensuite, une optimisation de
l'implémentation elle-même. Toutes les implémentations réalisées dans le
cours de ce travail ont été réalisées en langage VHDL, permettant notamment
la programmation de circuits programmables et la synthèse de circuits ASIC. L'implémentation concrète a été effectuée sur des FPGA FLEX 10K100 de
la société Altera. Un facteur important lors de la réalisation a été
l'optimisation (depuis une comparaison d'architectures jusqu'à une
optimisation au niveau de la synthèse) quant à la taille de notre unité de
cryptanalyse, afin d'être totalement intégrable sur un seul FPGA. Le
laboratoire possède une carte multi-FPGA de quatre FPGA pouvant fonctionner
soit de manière interactive, soit en parallèle et indépendamment les uns
des autres. Cette carte a donc été utilisée, ce qui multipliait par quatre
notre puissance de calcul. Finalement, nous avons réussi à implémenter une unité de cryptanalyse
en pipe-line par FPGA, le tout fonctionnant à 20 MHz, ce qui nous
procurait, à raison d'un message traité par coup d'horloge, 80 millions de
messages traités à chaque seconde. |Abstract |
The purpose of this work is the design of a DES cryptanalysis unit ,
the implementation of this unit on programmable circuits, and the
realization of attacks by a method of linear cryptanalysis in view to
evaluate the performances of this type of attacks. DES is an encryption
standard which is well known in the whole world and can be found in many
applications, mainly used to maintain information confidentiality. Thus, our work consists in a study of the standard, its different
implementations and leads to a concrete realization on programmable circuit
(FPGA) that has been simulated. This work also requires linear
cryptanalysis techniques, notably the algorithm of Matsui that has been
used here. These methods have been tested and validated by simulations.
Practically, Matsui's cryptanalysis method allows us to find one key bit in
122 hours. The implementation on programmable circuit is the result of two
consecutive steps : first, the understanding and mastery of DES and
cryptanalysis algorithms used ; then, an optimization of the implementation
itself. All the implementations realized in the course of this work have
been realized in VHDL, which is notably used for programming programmable
circuit and for synthesis of ASICs. The concrete implementation has been undertaken on FLEX 10K100 FPGAs
of the Altera company. During the realization, an important factor has been
the optimization (since an architecture comparison until a synthesis
optimization) of the size of our cryptanalysis unit, so as to be totally
integrable in a single FPGA. The laboratory possesses a multi-FPGA board
that supports four FPGAs being able to operate interactively or
independently from each others. This board has therefore been used,
multiplying by four our computational power. Finally, we have succeeded to implement a cryptanalysis pipe-line unit
in a FPGA, being able to operate at 20 MHZ. With one message processed at
each clock cycle, this gives 80 million messages processed at each second.
|Table des matières |
Introduction 1 1 Les enjeux 1 2 Les objectifs 3
Chapitre 1 : Le Data Encryption Standard 5 1.1 Généralités 5 1.2 Le fonctionnement du DES 6
1.2.1 Encrypt round 8
1.2.2 Key round 9 1.3 Le déchiffrement 12 1.4 Les différents modes possibles du DES 13 1.5 Le triple DES 15 1.6 Conclusion 16
Chapitre 2 : La cryptanalyse 17 2.1 Introduction 17 2.2 Recherche exhaustive de clé 19 2.3 Cryptanalyse différentielle 21 2.4 Cryptanalyse linéaire 22
2.4.1 Notations utilisées 22
2.4.2 Principe de la cryptanalyse linéaire 23
2.4.3 Approximation linéaire des S-boxes 24
2.4.4 Approximation linéaire du DES 25
2.4.5 Attaque du DES par textes en clair connus 27 2.5 Conclusion 30
Chapitre 3 : Implémentation sur FPGA 31 3.1 Généralités 31 3.2 Fonctionnement du FPGA 33
3.2.1 Principes du FPGA 33
3.2.2 Caractéristiques du FPGA utilisé 33
3.2.3 Autres types de FPGA 36 3.3 Implémentation du DES 38
3.3.1 Réalisations possibles du DES 38
3.3.1.1 Version séquentielle 38
3.3.1.2 Version étalée ou pipe-line 40
3.3.1.3 Autres versions pipe-line 40
3.3.2 Choix de l'implémentation 41
3.3.3 Optimisation sur FPGA 41 3.4 Implémentation de l'unité de cryptanalyse 49
3.4.1 Principe de l'unité de cryptanalyse 49
3.4.2 Logique de calcul 50
3.4.3 Générateur de nombres aléatoires 52
3.4.4 Optimisation 55 3.5 Réalisation pratique 57
3.5.1 Carte hardware utilisée 57
3.5.2 Performances obtenues 58
Chapitre 4 : Résultats et améliorations possibles 62 4.1 Résultats 62 4.2 Améliorations possibles 64
4.2.1 Utilisation d'autres composants 64
4.2.2 Augmentation de la fréquence 64
4.2.3 Attaque sur deux bits 64
4.2.4 Optimisations plus importantes 66
Conclusion 67
Bibliographie 69
|Introduction |
1 Les enjeux La cryptologie[1] est aussi vieille que l'écriture, et a été utilisée
pendant des milliers d'années pour garantir les communications militaires
et diplomatiques. Par exemple, Jules César utilisait déjà le chiffrement[2]
pour protéger les messages adressés à ses troupes. De nos jours, la
cryptographie est présente dans bien des domaines. Que ce soit pour
communiquer en toute confidentialité, pour s'authentifier, pour la
vér