Data Encryption Standard

Le Data Encryption Standard (DES, prononcer

/dɛs/) est un algorithme de chiffrement DES (Data Encryption Standard)
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 Fonction-F de DES.
dernière version avant l'obsolescence date du
1 Résumé
25 octobre 1999 .
Concepteur(s) IBM
Première 1975 (1977 pour le standard)
Histoire publication
Dérivé de Lucifer
En mai 1973, le National Bureau of Standards
Chiffrement(s) Triple DES, G-DES, DES-X,
américain demande la création d'un algorithme de
basé(s) sur cet LOKI89, ICE
chiffrement utilisable par les entreprises. À cette
algorithme
époque, IBM dispose déjà d'un algorithme appelé
Lucifer, conçu en 1971 par Horst Feistel. Caractéristiques

Taille(s) du bloc 64 bits

En bonne logique, cet algorithme aurait dû être
sélectionné par le NBS. En pratique, ce fut presque Longueur(s) de 56 bits
la clé
le cas : la NSA demanda que Lucifer soit modifié,
par ses soins. Ainsi fut créé le DES, qui fut adopté Structure schéma de Feistel
comme standard en novembre 1976. Cela suscita Nombre de tours 16 tours du DES
des soupçons selon lesquels la NSA aurait Meilleure cryptanalyse
volontairement affaibli l'algorithme, dans le but de
pouvoir le casser. Étrangement, le DES s'est révélé cryptanalyse linéaire, cryptanalyse différentielle, attaque par
résistant à plusieurs attaques ne devant apparaître force brute maintenant envisageable
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
2
techniques de cryptanalyse et qu'elle aurait donc, en réalité, rendu DES plus résistant .
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 à 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 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
3
révèlera le secret en 1994 . À 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 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 [réf. souhaitée]). 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 ([Link]) 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

Notes

Références
1. (en) « Data Encryption Standard (DES) ([Link]
[Link]) » [PDF], 25 octobre 1999 (consulté le 20 octobre 2015).
2. Involvement of NSA in the development of the data encryption standard ([Link]
[Link]/pdfs/[Link])
3. (en) Don Coppersmith, « The Data Encryption Standard (DES) and its strength against
attacks », IBM Journal of Research and Development, vol. 38, no 3,‎mai 1994, p. 243 (lire en
ligne ([Link] [PDF])

Annexes

Articles connexes
Constantes du DES
Cryptographie symétrique
Triple DES
AES
Nombre rien-dans-la-manche

Liens externes
(en) A Tutorialon Linear and Differential Cryptanalysis ([Link]
APERS/ldc_tutorial.pdf) par Howard M. Heys : Document résumant l'analyse linéaire et
différentielle

Ce document provient de « [Link]

title=Data_Encryption_Standard&oldid=214299738 ».