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, prononcer /dɛs/) est un algorithme de chiffrement symétrique (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^[1].

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 que Lucifer soit modifié, par ses soins. Ainsi fut créé le DES, qui fut adopté comme standard en novembre 1976. Cela suscita des soupçons selon lesquels 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. Ceci permet de penser que la NSA avait connaissance dès cette époque de ces techniques de cryptanalyse et qu'elle aurait donc, en réalité, rendu DES plus résistant^[2].

L'équipe d'IBM impliquée dans la conception et l'analyse du chiffrement comprenait Feistel, Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith et Bryant Tuckerman.

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 tour d'une autre clé partielle de 48 bits. Cette clé de tour 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 tour, 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 64) subira une transformation ;
• le résultat du dernier tour 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 à ${\displaystyle 2^{55}}$ opérations en moyenne. Certaines de ces méthodes ne sont plus efficaces avec des algorithmes de chiffrement 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 ${\displaystyle 2^{47}}$ 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^[3]. À 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 Henri Gilbert et indépendamment 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 ${\displaystyle 2^{43}}$ 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 $ 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

Annexes