Conception de DES et chiffrement Lucifer

En 1971, Horst Feistel, du centre de recherche d'IBM, a développé un chiffrement appelé Lucifer dans le cadre d'un projet de sécurité bancaire pour Lloyd's of London. Lucifer était l'un des premiers chiffrements modernes par blocs, utilisant une clé de 128 bits et des blocs de 128 bits.

Lucifer a montré qu'il était possible de construire un chiffrement par blocs robuste à l'aide de la structure de Feistel : des tours alternés de substitution et de permutation appliqués à des demi-blocs. Il est l'ancêtre direct de DES.

DES applique 16 tours de la structure de Feistel à des blocs de 64 bits. À chaque tour, le bloc de 64 bits est divisé en deux moitiés de 32 bits. La moitié droite est étendue à 48 bits, combinée par XOR avec une sous-clé de 48 bits, traitée par les boîtes S, permutée, puis combinée par XOR avec la moitié gauche.

Les deux moitiés sont ensuite échangées et le processus se répète. Après 16 tours, une permutation finale produit le texte chiffré de 64 bits. Le déchiffrement utilise la même structure avec les sous-clés dans l'ordre inverse.

DES chiffre les données par blocs de 64 bits (8 octets). Cette taille de bloc fixe convenait au matériel de 1977, mais elle est devenue un problème de sécurité. Avec suffisamment de données, les collisions liées au paradoxe des anniversaires deviennent probables.

Avec des blocs de 64 bits, des motifs statistiques apparaissent après environ 2^32 blocs (environ 32 Go de données chiffrées avec la même clé). Cette attaque Sweet32 a rendu 3DES non sûr pour les flux à fort volume comme HTTPS.

DES utilise une clé de 64 bits, mais 8 de ces bits sont des bits de parité utilisés pour détecter les erreurs, et non pour le chiffrement. La longueur effective de la clé n'est donc que de 56 bits.

Cela signifie qu'il n'existe que 2^56 clés DES possibles, soit environ 72 billiards. Selon les standards de 1977, ce nombre était considéré comme suffisant. En 1997, il était clairement démontré qu'un adversaire déterminé pouvait casser ce chiffrement.

DES commence par une permutation initiale (IP) qui réorganise les 64 bits du bloc en clair et se termine par une permutation finale (IP^-1), qui est son inverse exact. Ces permutations n'ajoutent aucune force cryptographique.

Elles ont été conçues pour optimiser le matériel de certaines architectures de puces des années 1970 et permettre un chargement plus rapide des bits dans les registres. Les analyses modernes confirment qu'elles n'apportent rien à la sécurité.

Les huit boîtes S (boîtes de substitution) sont au cœur de la non-linéarité de DES. Chaque boîte S prend une entrée de 6 bits et produit une sortie de 4 bits à l'aide d'une table de recherche fixe. Les 2 bits extérieurs sélectionnent la ligne et les 4 bits intérieurs sélectionnent la colonne.

Sans la non-linéarité fournie par les boîtes S, DES serait un chiffrement purement linéaire, facilement cassable par l'algèbre linéaire. La conception particulière des boîtes S de DES résiste à la cryptanalyse différentielle.

Après les boîtes S, DES applique une permutation de boîte P qui réorganise les 32 bits de sortie des boîtes S. Elle assure la diffusion en répartissant la sortie de chaque boîte S afin qu'elle affecte plusieurs boîtes S au tour suivant.

La boîte P a été soigneusement conçue pour maximiser la diffusion : chaque bit de sortie d'une boîte S affecte au moins deux boîtes S différentes au tour suivant, ce qui garantit un effet avalanche rapide.

DES dérive 16 sous-clés différentes de 48 bits à partir de la clé maîtresse de 56 bits, une pour chaque tour. L’ordonnancement des clés commence par l’application d’une sélection permutée (PC-1) afin de supprimer les bits de parité et de réorganiser les bits de la clé.

Les 56 bits sont divisés en deux moitiés de 28 bits, qui subissent une rotation vers la gauche de 1 ou 2 positions à chaque tour. Ensuite, une sélection permutée (PC-2) sélectionne 48 des 56 bits afin de former la sous-clé de chaque tour.

La NSA a collaboré avec IBM pendant le développement de DES, réduisant la longueur de la clé de 128 bits pour le chiffre de Lucifer à 56 bits et modifiant la conception des boîtes S. Cela a suscité plusieurs décennies de controverse sur l’introduction éventuelle de portes dérobées.

Dans les années 1990, des responsables de la NSA ont confirmé avoir renforcé les boîtes S contre la cryptanalyse différentielle, une technique découverte par IBM en 1974. La NSA connaissait la cryptanalyse différentielle depuis plusieurs années avant le milieu universitaire, ce qui laisse penser qu’elle a rendu DES plus résistant, et non plus faible.

DES a été adopté comme Federal Information Processing Standard 46 en janvier 1977, à l’issue d’un processus d’évaluation concurrentiel. Il est devenu le chiffre standard pour les données gouvernementales non classifiées et a été largement adopté par les secteurs bancaire et industriel.

La normalisation de DES a eu une importance historique : il s’agissait du premier algorithme cryptographique accessible au public et approuvé par le gouvernement. Elle a stimulé le développement d’implémentations matérielles et établi le modèle des futurs processus de normalisation des chiffres.

DES est lui-même un chiffrement par blocs qui chiffre exactement 64 bits à la fois. Les messages réels sont plus longs ; les modes opératoires définissent donc comment appliquer le chiffrement à plusieurs blocs. Les modes courants comprennent ECB (chiffrement indépendant de chaque bloc), CBC (application de XOR à chaque bloc avec le texte chiffré précédent avant le chiffrement), CFB, OFB et CTR.

ECB est le mode le plus faible : des blocs de texte en clair identiques produisent des blocs de texte chiffré identiques, ce qui crée des motifs visibles. Les modes CBC et CTR éliminent cette faiblesse et sont privilégiés pour l’utilisation pratique de DES et de 3DES.

Évaluez vos connaissances des paramètres de conception de DES.

DES a évolué à partir du chiffre Lucifer d’IBM pour devenir un chiffrement de Feistel à 16 tours, avec des blocs de 64 bits et des clés effectives de 56 bits. Sa sécurité repose sur 8 boîtes S non linéaires assurant la confusion, sur la boîte P assurant la diffusion et sur 16 tours amplifiant l’effet avalanche.

L’implication de la NSA dans la conception des boîtes S a été controversée, mais a finalement amélioré la résistance à la cryptanalyse différentielle. La clé de 56 bits de DES, conçue pour le matériel de 1977, s’est révélée insuffisante à la fin des années 1990.