Rapport Théorie de l’Information |
L’objectif du projet est de réaliser un programme qui permet le chiffrement de fichier à l’aide d’un algorithme de Feistel. Ce projet implémentera l’algorithme Blowfish.
Dans un premier temps nous étudierons le concept de Feistel, puis nous l’étudierons appliquer á l’algorithme Blowfish.
Nous conclurons enfin avec la mise en place d’une interface graphique, qui permettra une utilisation simplifié du programme de chiffrement.
Un réseau de Feistel est une construction utilisée dans les algorithmes de chiffrement par bloc, nommée d’après le cryptologue d’IBM, Horst Feistel. Elle a été utilisée pour la première fois dans les algorithmes nommés Lucifer et DES. Cette structure offre plusieurs avantages, le chiffrement et le déchiffrement ont une architecture similaire voire identique dans certains cas. L’implémentation matérielle est aussi plus facile avec un tel système même si les choses ont passablement changé depuis la fin des années 70. Un réseau de Feistel repose sur des principes simples dont des permutations, des substitutions, des échanges de blocs de données et une fonction prenant en entrée une clé intermédiaire à chaque étage.
Un réseau de Feistel est subdivisé en plusieurs tours ou étages. Dans sa version équilibrée, le réseau traite les données en deux parties de taille identique. A chaque tour, les deux blocs sont échangés puis un des blocs est combiné avec une version transformée de l’autre bloc. Ces opérations sont spécifiques à chaque algorithme. Chaque tour utilise une clé intermédiaire, en général tirée de la clé principale via une génération appelée key schedule.
Une définition formelle d’un réseau de Feistel peut être donnée sous plusieurs formes. Nous reprenons ici la notation utilisée par Knudsen dans Partial and Higher Order Differentials and Applications to DES.
Chaque tour applique plusieurs transformations sur les données provenant du tour précédent :
On utilise les termes de confusion et diffusion pour décrire la propagation des informations dans la structure. En effet, une modification d’un bit en entrée produira des variations très importantes dans les stages intermédiaires et en sortie. Un terme plus récent pour décrire ce phénomène est l’effet avalanche. L’utilisation des permutations permet d’améliorer la diffusion alors que les substitutions ont pour effet d’augmenter la confusion.
Les schémas de Feistel ont été largement analysés et examinés par les experts. Plusieurs attaques sont possibles mais les deux principales sont :
Ces méthodes ont fait leur preuve sur DES et sur d’autres algorithmes similaires. Mais cela ne signifie pas que l’utilisation d’un réseau de Feistel va obligatoirement entraîner des vulnérabilités significatives. Grâce à l’ajout de différentes techniques et avec une conception bien menée, on peut considérablement améliorer la résistance d’un algorithme basé sur Feistel. C’est le cas pour Blowfish qui est encore cryptographiquement sûr.
Blowfish est un algorithme de chiffrement symétrique (i.e. “à clef secrète”) par blocs conçu par Bruce Schneier en 1993. Il tire son nom du poisson-lune japonais (ou fugu), qui en est également l’emblème.
Blowfish utilise une taille de bloc de 64 bits et la clé de longueur variable peut aller de 32 à 448 bits. Elle est basée sur l’idée qu’une bonne sécurité contre les attaques de cryptanalyse peut être obtenue en utilisant de très grandes clés pseudo-aléatoires.
Blowfish présente une bonne rapidité d’exécution excepté lors d’un changement de clé, il est environ 5 fois plus rapide que Triple DES et deux fois plus rapide que IDEA. Malgré son âge, il demeure encore solide du point de vue cryptographique avec relativement peu d’attaques efficaces sur les versions avec moins de tours. La version complète avec 16 tours est à ce jour entièrement fiable et la recherche exhaustive reste le seul moyen pour l’attaquer.
Il est utilisé dans de nombreux logiciels propriétaires et libres (dont GnuPG et OpenSSH).
Blowfish utilise une taille de bloc de 64 bits et la clé, de longueur variable, peut aller de 32 à 448 bits. Blowfish est basé sur un schéma de Feistel avec 16 tours et utilise des S-Boxes de grandes tailles qui dépendent de la clé. Il ressemble à CAST-128 qui a adopté, quant à lui, des S-Boxes au contenu fixé d’avance.
Le schéma montre la structure principale de Blowfish. Chaque ligne représente 32 bits. L’algorithme gère deux ensembles de clés : les 18 entrées du tableau P et les quatre S-Boxes de 256 éléments chacune.
Les S-Boxes acceptent un mot de 8 bits en entrée et produisent une sortie de 32 bits. Une entrée du tableau P est utilisée à chaque tour. Arrivé au tour final, la moitié du bloc de donnée subit un XOR avec un des deux éléments restants dans le tableau P.
La F-fonction de Blowfish sépare une entrée de 32 bits en quatre morceaux de 8 bits et les utilise comme entrées pour accéder aux S-Boxes. Les sorties sont additionnées avec une somme modulo 232 et l’algorithme effectue un XOR entre les deux sous-totaux pour produire la sortie finale de 32 bits.
En tant que schéma de Feistel, Blowfish peut être inversé simplement en appliquant un XOR des éléments 17 et 18 du tableau P sur le bloc chiffré. Il faut ensuite utiliser les entrées du tableau P dans l’ordre inverse.
La préparation de la structure à partir de la clé commence avec l’initialisation du tableau P et des S-Boxes avec des valeurs qui sont tirées du nombre Pi exprimé en hexadécimal.
On opère ensuite un XOR entre la clé secrète et les entrées du tableau P (avec une extension cyclique de la clé si nécessaire). Un bloc de 64 bits, tous à zéro, est ensuite chiffré avec cette version temporaire de Blowfish. Le résultat chiffré remplace ensuite le premier et le deuxième élément du tableau P.
On réitère l’opération de chiffrement avec cette nouvelle version et ceci sur le résultat précédent. On obtient alors le troisième et quatrième élément de P. L’algorithme continue ainsi en remplacant tout le tableau P et les éléments des S-Boxes.
Au final, environ 4 Ko de données doivent être générées et Blowfish effectue 512 itérations pour y parvenir. De part ces contraintes, Blowfish est lent quand il faut changer de clé mais très rapide pour le chiffrement pris séparément.
Note : l’entrée de 64 bits de texte clair est notée “x” et le tableau P est noté Pi/P[i], où “i” est l’itération.
En 1996, Serge Vaudenay a montré que les permutations dans Blowfish s’écartaient sensiblement des permutations complètement aléatoires sur quatorze tours. L’attaque qu’il a forgé nécessite 28r + 1 textes clairs connus, avec r le nombre de tours.
Il a de plus mis en évidence des clés dites faibles, détectables et cassables avec la même attaque en seulement 24r + 1 textes clairs connus. L’attaque ne peut être étendue au Blowfish complet avec ses 16 tours. Vincent Rijmen a publié une attaque sur quatre tours en 1997, elle est basée sur une cryptanalyse différentielle de second degré.
La recherche exhaustive reste la seule solution pour vaincre un Blowfish complet à ce jour.
Le programme possède 2 partie. Une première partie écrit en C, le noyau du programme. C’est cette partie qui permet de crypter les fichiers. La deuxième partie écrit en Java, est l’interface graphique qui simplifie l’utilisation du programme principal.
Il y a plusieurs avantages à avoir deux parties distinctes (écrit dans différents langages) :
Ce programme est donc facilement utilisable sur Linux ou Windows, que ce soit en environnement graphique ou console.
Fonction étage qui prends en entree un bloc de 32 bits (xL). Ce bloc est decoupé en 4 blocs de 8 bits chacun par l’intermédiaire des fonctions de décalage de bits : [ (xL & mask) >> j ].
Et avec chaque blocs de 8 bits (4 au total), on va chercher dans la S-Boxe correspondante le bloc de 32 bits associés. (Il y a 4 S-Boxes, donc 1 S-Boxe par bloc de 8 bits).
Après avoir récupéré chaque bloc de 32 bits dans les S-Boxes (au total 4), on effectue une opération dessus. Cette opération consiste en addition modulo 32, et un Xor. (((xLp[0] + xLp[1]) xLp[2]) + xLp[3])
Le resultat ainsi obtenu est renvoye
Fonction qui consiste simplement à inverser 2 bloc de 32 bits.
Fonction de chiffrement de Feistel qui itere 16 fois sur la fonction étage décrite précédemment (DWORD fonction(DWORD xL)).
Explication plus détaillé de la fonction (ce qui a été expliqué en 3.2 ) : On a une partie gauche xL, et une partie droite xR. Pour calculer les nouvelles parties gauche et droite, il faut :
Faire 16 itérations ( de 1 à 16 ) sur : Pour la partie gauche, il suffit donc d’appliquer un Xor entre xL et le tableau P[i] (i étant la ième itération / la ième entrée du tableau).
Pour la partie droite, on envoie xL à la fonction étage, puis on fait un xor entre le résultat retourné de la fonction et xR.
Avant de continuer sur la nouvelle itération, on permutte les nouvelles parties xR et xL.
Après les 16 itérations faites sur xL, et xR... on permutte une nouvelle fois les 2 parties, puis on fait un xor entre xR et P[17], ainsi que xL et P[18]
Fonction qui permet l’ouverture d’un fichier.
Fonction inverse du chiffrement de Feistel. C’est presque la même fonction que celle de cryptage. Sauf qu’au lieu d’itérer de 1 à 16, on le fait de 18 à 3.
Et après les 16 itérations, plutot que de faire un xor avec les 17 et 18 partie de P, on prends les 2ème, et 1ère partie. (xR xor p[2] et xL xor p[1])
Avant d’itérer sur la fonction de chiffrement, il faut créer les sous clés pour le chiffrement. C’est à dire “créer” les 18 sous clés, ainsi que définir les 4 SBoxes.
Toutes ces variables contiennent au préalables les décimales de Pi. Et pour les mettre en place, il suffit de :
Cette fonction permet la génération des variables (tableau P, ainsi que S-Boxes), et permet le chiffrement d’un fichier complet (en l’écrivant dans un nouveau fichier)
Fonction qui génére une clé entre 32 et 448 bits, et l’écrit dans un fichier.
Pour implémenter l’interface du logiciel, nous avons choisi d’utiliser Java et la bibliothèque SWING. En utilisant la classe RUNTIME de java, nous pouvons démarrer le programme codé en C.
L’interface se compose d’une Jframe principale composée en deux jpanel.
Ainsi, les actionPerformed() de la classe Jbutton déclencherons le mode visible() des interfaces.
L’interface d’affichage, est donc un Jpanel dans lequel on ajoute via la méthode addcomponent() les classes dérivé de Jpanel qui sont: Cryptage, GenereKey et Decryptage.
Nous ne parlerons ici que des composants des ces interfaces, le détail d’utilisation se traité dans le manuel utilisateur.
Le logiciel se comporte en trois parties toutes accessibles via l’interface générale. Une partie génération de clef, une partie cryptage et une partie pour le décryptage.
Dans la partie inférieure du programme, trois boutons respectivement cryptage, génération d’une clé et décryptage permettent de choisir le mode de fonctionnement du logiciel. Cette partie reste toujours visible de manière à circuler entre les différents modes.
Dans la partie supérieure s’affiche, selon le cas du mode, une interface de cryptage, une interface de génération de clé et une interface de décryptage.
A partir de cette interface, l’utilisateur peut choisir de générer une clé manuellement ou automatiquement. Pour cela il sélectionne l’un des deux boutons radio en haut.
Dans le cas d’une génération manuelle, l’utilisateur peut choisir s’il souhaite afficher ou non sa clef lors de la saisie en cochant la case “afficher la clé” ceci lui permet de rester en toute confidentialité. Il saisit ainsi la clé dans la zone prévue à cet effet.
Dans l’autre cas, il a la possibilité de choisir la longueur de la clé en utilisant le slider “Longueur de la clé”.
Une fois une des deux opérations effectuées, l’utilisateur choisi un répertoire de travail et un nom pour sa clé avec le bouton parcourir et le champs de saisi.
Il ne lui reste qu’à cliquer sur le bouton génération pour obtenir sa clé.
Une fois la clé de cryptage générée, l’utilisateur peut crypter ses fichiers.
Il a le choix entre deux modes, soit un mode normal qui permet de crypter n’importe quel fichier, soit un mode permettant le cryptage d’une image au format BitMap et de pouvoir visionner le résultat dans une application de visualisation d’image. Pour cela il sélectionne un mode de cryptage à l’aide du menu déroulant.
Il choisit ensuite le fichier à crypter en cliquant sur le bouton parcourir, puis une clé qu’il a au préalable générer en cliquant sur le bouton parcourir.
Il ne lui reste qu’à saisir le répertoire de sauvegarde du fichier crypté en cliquant sur le dernier bouton parcourir et saisir le nom de fichier crypté dans le champ prévu.
Une fois tous ces champs renseignés, il lui suffit de cliquer sur crypter pour lancer obtenir le fichier crypté.
Il peut à tout moment annuler les paramètres entrés en cliquant sur Raz.
Pour décrypter un fichier, l’utilisateur doit saisir le fichier crypté et la clé qu’il a utilisée pour le crypter. Pour cela, il utilise les boutons parcourir en question.
Il ne lui reste qu’à saisir le répertoire de sauvegarde du fichier décrypté ainsi que le nom du fichier décrypté.
En cliquant sur le bouton décrypter, il retrouve son fichier initial.
Comme pour le cryptage, il peut remettre tout à zéro en cliquant sur Raz.
En conclusion, ce projet a été très intéressant, et très instructif à mettre en place. On peut dire qu’il nous a permis d’étudier plus en profondeur tout ce qui concerne les principe de chiffrement, entre autre grâce à l’étude d’algorithme divers concernant le principe de Feistel. (DES, Blowfish...). Dans une version améliorée, il aurait été intéressant d’implémenter le chiffrement d’autres fichiers de types spécifiques comme de la musique, ou de la vidéo. En appliquant le même principe que pour nos images bitmap. C’est à dire en étudiant l’entête du fichier concerné.
Ce document a été traduit de LATEX par HEVEA