- Algorithme DES
-
Data Encryption Standard
Pour les articles homonymes, voir DES.DES (Data Encryption Standard) 
fonction-F de DES Résumé Concepteur(s) IBM Première publication 1975 (1977 pour le standard) Dérivé de Lucifer Chiffrement(s) basé(s) sur cet algorithme Triple DES, G-DES, DES-X, LOKI89, ICE Caractéristiques Taille(s) du bloc 64 bits Longueur(s) de la clé 56 bits Structure schéma de Feistel Nombre de tours 16 tours du DES Meilleure cryptanalyse cryptanalyse linéaire, cryptanalyse différentielle, attaque par force brute maintenant envisageable Le Data Encryption Standard (DES) est un algorithme de chiffrement par bloc utilisant des clés de 56 bits. Son emploi n'est plus recommandé aujourd'hui, du fait de sa lenteur à l'exécution et de son espace de clés trop petit permettant une attaque systématique en un temps raisonnable. Quand il est encore utilisé c'est généralement en Triple DES, ce qui ne fait rien pour améliorer ses performances. DES a notamment été utilisé dans le système de mots de passe UNIX.
Le premier standard DES est publié par FIPS le 15 janvier 1977 sous le nom FIPS PUB 46. La dernière version avant l'obsolescence date du 25 octobre 1999 FIPS PUB 46-3
Sommaire
Histoire
En mai 1973, le National Bureau of Standards américain demande la création d'un algorithme de chiffrement utilisable par les entreprises. À cette époque, IBM dispose déjà d'un algorithme appelé Lucifer, conçu en 1971 par Horst Feistel.
En bonne logique, cet algorithme aurait dû être sélectionné par le NBS. En pratique, ce fut presque le cas : la NSA demanda à ce que Lucifer soit modifié, par ses soins. Ainsi fut créé le DES, qui fut adopté comme standard en novembre 1976.
Cela suscita des rumeurs selon lesquelles la NSA aurait volontairement affaibli l'algorithme, dans le but de pouvoir le casser. Étrangement, le DES s'est révélé résistant à plusieurs attaques ne devant apparaître dans la communauté académique que beaucoup plus tard. Encore plus étonnant, Lucifer, lui, résistait moins bien.
Fonctionnement
L'algorithme DES transforme un bloc de 64 bits en un autre bloc de 64 bits. Il manipule des clés individuelles de 56 bits, représentées par 64 bits (avec un bit de chaque octet servant pour le contrôle de parité). Ce système de chiffrement symétrique fait partie de la famille des chiffrements itératifs par blocs, plus particulièrement il s'agit d'un schéma de Feistel (du nom de Horst Feistel à l'origine du chiffrement Lucifer).
D'une manière générale, on peut dire que DES fonctionne en trois étapes :
- permutation initiale et fixe d'un bloc (sans aucune incidence sur le niveau de sécurité).
- le résultat est soumis à 16 itérations d'une transformation, ces itérations dépendent à chaque ronde d'une autre clé partielle de 48 bits. Cette clé de ronde intermédiaire est calculée à partir de la clé initiale de l'utilisateur (grâce à un réseau de tables de substitution et d'opérateurs XOR). Lors de chaque ronde, le bloc de 64 bits est découpé en deux blocs de 32 bits, et ces blocs sont échangés l'un avec l'autre selon un schéma de Feistel. Le bloc de 32 bits ayant le poids le plus fort (celui qui s'étend du bit 32 au bit 63) subira une transformation.
- le dernier résultat de la dernière ronde est transformé par la fonction inverse de la permutation initiale.
DES utilise huit tables de substitution (les S-Boxes) qui furent l'objet de nombreuses controverses quant à leur contenu. On soupçonnait une faiblesse volontairement insérée par les concepteurs. Ces rumeurs furent dissipées au début des années 1990 par la découverte de la cryptanalyse différentielle qui démontra que les tables étaient bien conçues.
Attaques
Plusieurs attaques ont été découvertes sur DES. Elles permettent de diminuer les coûts d'une recherche exhaustive des clés qui se monte à 255 opérations en moyenne. Certaines de ces méthodes ne sont plus efficaces avec des algorithmes de cryptage plus récents du fait de l'introduction d'un effet avalanche.
- La cryptanalyse différentielle découverte par Eli Biham et Adi Shamir en 1991 permet de trouver la clé en utilisant 247 textes clairs. Le principe est de disposer d'un DES implémenté dans une boîte noire hermétique avec une clé secrète à l'intérieur. En fournissant suffisamment de texte en entrée, on peut statistiquement analyser le comportement des sorties selon les entrées et retrouver la clé. Les entrées utilisées pour cette attaque doivent mutuellement présenter une légère différence (par exemple un bit qui change). En regardant comment la différence affecte la sortie, on peut établir des statistiques et en augmentant le nombre d'entrées, on améliore la fiabilité de l'attaque.
- L'attaque-T (Tickling attack) est une variante de la cryptanalyse différentielle découverte en 1974 lors de la conception du DES par les chercheurs d'IBM. Pendant une vingtaine d'années, le silence a été complet sur cette découverte. C'est Don Coppersmith qui révèlera le secret en 1994[1]. À l'époque, elle avait incité les concepteurs de DES à renforcer le contenu des tables de substitution (au lieu de l'affaiblir comme la rumeur le laissait entendre).
- La cryptanalyse linéaire inventée par Mitsuru Matsui en 1993 est plus efficace mais moins pratique pour la simple et bonne raison que l'attaquant ne dispose pas de la boîte noire et qu'il ne peut pas soumettre ses propres textes. Cette attaque nécessite 243 couples (tous chiffrés avec la même clé) que l'attaquant a pu récupérer par un moyen ou un autre. Elle consiste à faire une approximation linéaire de DES en le simplifiant. En augmentant le nombre de couples disponibles, on améliore la précision de l'approximation et on peut en extraire la clé.
- Le compromis temps-mémoire est un concept inventé par Martin Hellman au début des années 1980. En partant du principe que le même message va être chiffré plusieurs fois avec des clés différentes, on pourrait calculer une immense table qui contient toutes les versions chiffrées de ce message. Lorsque l'on intercepte un message chiffré, on peut le retrouver dans la table et obtenir la clé qui avait été utilisée pour le coder. Cette attaque n'est bien sûr pas faisable car nous avons besoin d'une table de l'ordre du milliard de GB. Le génie d'Hellman a été de trouver un moyen pour réduire cette table à environ 1 téraoctet (soit 1 million de fois moins que la table complète), ce qui est faisable de nos jours.
- D'autres attaques sont spécifiques à des implémentations et ne sont pas forcément spécifiques à DES. Dans le cas d'un DES implémenté dans du matériel, on pourrait analyser la consommation électrique et déduire certaines informations sur la clé (une consommation accrue indique des bits actifs). Le même style d'attaque peut aussi être employé sur un ordinateur en calculant le temps mis pour chiffrer avec des textes différents ou en analysant la mémoire utilisée.
- Toutes les autres attaques sur DES visent à réduire le temps de calcul d'une recherche exhaustive en utilisant des machines spécifiquement conçues pour la tâche (grâce à des FPGA en parallèle par exemple). Une telle machine a été construite en 1998. Deep Crack a coûté environ 200 000 dollars et pouvait casser la clé en moins d'une semaine. Le calcul distribué en utilisant les ordinateurs des particuliers (distributed.net) a prouvé son efficacité en cassant une clé en moins de 24 heures.
Statut
L'algorithme initialement conçu par IBM utilisait une clé de 112 bits. L'intervention de la NSA a ramené la taille de clé à 56 bits. De nos jours, le Triple DES reste très répandu, et le DES « simple » ne subsiste que dans d'anciennes applications. Le standard DES a été remplacé en 2001 par l'AES (Advanced Encryption Standard).
Notes et références
- ↑ Don Coppersmith, « The Data Encryption Standard (DES) and its strength against attacks », dans IBM Journal of Research and Development, vol. 38, no 3, May 1994, p. 243 [[pdf] texte intégral]
Voir aussi
Articles connexes
Liens externes
- (en) A Tutorial on Linear and Differential Cryptanalysis par Howard M. Heys : Document résumant l'analyse linéaire et différentielle
Portail de la cryptologie
Catégories : Algorithme de cryptographie symétrique | Algorithme de chiffrement par bloc
Wikimedia Foundation. 2010.
