Data encryption standard
Le Data Encryption Standard (DES) est une méthode de chiffrement utilisant des clés de 56 bits. Son emploi n'est plus recommandé aujourd'hui, du fait de sa lenteur en logiciel 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.
Inventé par IBM sous la coupelle du NSA en 1977, c'est un algorithme à clé symétrique, c'est-à-dire que l'on utilise la même clé pour chiffrer et pour déchiffrer. Son utilisation dans une transmission suppose que la personne émettrice qui chiffre et la réceptrice qui déchiffre possèdent la même clé.
| Sommaire |
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 d'IBM à 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 ou-exclusif). 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 dispersées au début des années 90 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.
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. Elle a été découverte lors de la conception du DES par les chercheurs d'IBM et révelée par Don Coppersmith au milieu des années 90. Pendant une vingtaine d'années, le silence a été complet sur cette découverte. À 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 disponible, 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 80. 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érabyte (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 crypter 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.
[- Document en anglais résumant l'analyse linéaire et différentielle]
Status
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).
Voir aussi
| Image manquante Key-crypto-sideways.png | Portail Cryptologie - Accédez d'un seul coup d’œil à toute la série des articles « Cryptologie » de Wikipédia. |