Le chiffrement symétrique : de DES à AES
Partie 2 sur 5
3Comment fonctionne le DES
Comprendre le DES, même sans entrer dans toutes les tables, est utile : presque tous les chiffrements par blocs reprennent ses idées. Le détail repose sur des tables numériques ; nous en gardons l’architecture et les raisons, et renvoyons aux tables de la norme pour qui voudrait les reproduire.
3.1Blocs de 64 bits, clé de 56 bits
Le DES est un chiffrement symétrique par blocs de 64 bits (8 octets). La clé est fournie sur 64 bits, mais huit de ces bits sont des bits de parité : un par octet, ajusté pour que le nombre de 1 dans l’octet soit impair (« parité impaire »). Ils servent à détecter une erreur de saisie ou de transmission de la clé, pas à chiffrer. La clé « utile » ne compte donc que 56 bits. Il existe ainsi 256 clés possibles, soit environ 7,2 × 1016 (soixante-douze millions de milliards).
On lit parfois que « la clé est codée sur 64 bits et formée de 16 blocs de 4 bits », ce qui est inexact : la clé de 64 bits sert à fabriquer seize sous-clés de 48 bits, une par ronde (partie 3.3). On parle aussi de « 8 clés diversifiées de 48 bits » ; c’est bien seize.
3.2Seize rondes de substitutions et de permutations
Le principe général est celui d’un code produit : on enchaîne des substitutions et des permutations, sous le contrôle de la clé. Claude Shannon avait énoncé en 1949 les deux effets recherchés : la confusion (rendre la relation entre clé et chiffré aussi compliquée que possible, par des substitutions) et la diffusion (répartir l’influence de chaque bit du clair sur tout le chiffré, par des permutations). Un bon chiffrement a un « effet avalanche » : changer un seul bit du message ou de la clé modifie environ la moitié des bits du résultat.
Les grandes lignes du DES tiennent en cinq étapes :
- le message est découpé en blocs de 64 bits ;
- chaque bloc subit une permutation initiale (un simple brassage des positions des bits, fixé par une table) ;
- le résultat est coupé en deux moitiés de 32 bits, notées G (gauche) et D (droite) ;
- on applique seize fois une même opération appelée ronde (partie suivante), chacune avec une sous-clé différente ;
- les deux moitiés sont recollées et subissent la permutation initiale inverse, qui défait la première : le résultat est un bloc chiffré de 64 bits.
3.3Une ronde, pas à pas
La ronde suit un schéma inventé par Horst Feistel, appelé réseau de Feistel (figure 2). Elle prend deux moitiés G et D et en produit deux nouvelles :
- la nouvelle moitié gauche est simplement l’ancienne moitié droite ;
- la nouvelle moitié droite est le résultat d’un « ou exclusif » entre l’ancienne moitié gauche et une fonction f appliquée à l’ancienne moitié droite avec la sous-clé de la ronde.
La fonction f comprend quatre opérations :
- une expansion : les 32 bits de la moitié droite sont étendus à 48 bits par une table, qui mélange les bits et en duplique seize ;
- un ou exclusif avec la sous-clé de 48 bits de la ronde ;
- huit boîtes de substitution (« boîtes S », aussi appelées fonctions de sélection), qui transforment chacune un groupe de 6 bits en un groupe de 4 bits : 48 bits entrent, 32 sortent. C’est la seule étape qui n’est pas linéaire (qui n’est pas une simple combinaison de bits) ; elle fait la force du DES ;
- une permutation des 32 bits obtenus, par une table fixe.
Prenons un exemple pour la première boîte de substitution. Chaque boîte est un tableau de 4 lignes et 16 colonnes. Pour un groupe de 6 bits, le premier et le dernier bit désignent la ligne, les quatre bits du milieu désignent la colonne. Avec le groupe 101110, le premier et le dernier bit donnent 10, soit la ligne 2 ; les bits du milieu donnent 0111, soit la colonne 7. Dans la boîte S1, la valeur à la ligne 2, colonne 7, est 11, soit 1011 en binaire sur 4 bits. (On écrit parfois « 111 », en oubliant le zéro de tête : la sortie fait toujours quatre bits.) Chaque ligne d’une boîte contient les nombres de 0 à 15 une seule fois, dans un ordre qui a été choisi avec soin.
Une propriété remarquable du schéma de Feistel : la fonction f n’a pas besoin d’être réversible. Pour déchiffrer, on repart du bloc chiffré et on exécute les mêmes rondes en prenant les sous-clés dans l’ordre inverse. La moitié gauche d’avant la ronde se retrouve en combinant, par « ou exclusif », la moitié droite d’après avec f appliquée à la moitié gauche d’après. Voici un exemple jouet sur 4 bits, avec pour f un simple XOR avec la sous-clé : G₀ = 1010, D₀ = 0110, sous-clé K = 0011. On calcule f(D₀) = 0110 XOR 0011 = 0101, puis D₁ = G₀ XOR f(D₀) = 1010 XOR 0101 = 1111, et G₁ = D₀ = 0110. Pour inverser : D₀ = G₁ = 0110, puis G₀ = D₁ XOR f(G₁) = 1111 XOR (0110 XOR 0011) = 1111 XOR 0101 = 1010. On retrouve bien le point de départ. C’est ce qui permet d’utiliser le même circuit pour chiffrer et déchiffrer.
3.4Les sous-clés
La sécurité repose sur la clé, puisque l’algorithme est public ; la clé de 64 bits fournit les seize sous-clés de 48 bits par un procédé de « diversification » :
- on retire les 8 bits de parité et on permute les 56 bits restants par une première table (souvent nommée CP-1) ;
- on les coupe en deux moitiés de 28 bits ;
- à chaque ronde, chaque moitié subit une rotation vers la gauche de un ou deux crans selon la ronde (les bits du début passent à la fin), ce qui fait que chaque sous-clé est différente ;
- on réunit les deux moitiés et on en choisit 48 bits par une seconde table (CP-2) : c’est la sous-clé de la ronde.
Au total, les rotations des seize rondes font exactement un tour complet de 28 positions, de sorte que la clé revient à son point de départ à la fin.
Pour s’exercer
Exercice 2 : le temps de recherche
Une machine teste 90 milliards de clés par seconde. Combien de temps pour parcourir toutes les clés du DES (256 ≈ 7,2 × 1016) ? Et celles de l’AES-128 (2128 ≈ 3,4 × 1038) ?
Voir la réponse
DES : 7,2 × 1016 / 9 × 1010 = 8 × 105 secondes, soit environ 9 jours pour tout parcourir, 4,5 jours en moyenne. AES-128 : 3,4 × 1038 / 9 × 1010 ≈ 3,8 × 1027 secondes, soit plus de 1020 années (l’univers a environ 1,4 × 1010 ans). Même avec un million de machines identiques, la recherche resterait hors de portée. Chaque bit supplémentaire de clé double le travail.
Exercice 3 : une boîte de substitution
La première ligne de la boîte S1 est : 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7. Quelle est la sortie pour le groupe de 6 bits 000000 ? Et, sachant que la quatrième ligne (numéro 3) commence par 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13, pour 111111 ?
Voir la réponse
Pour 000000 : premier et dernier bits = 00, ligne 0 ; bits du milieu = 0000, colonne 0 ; la valeur est 14, soit 1110 en binaire. Pour 111111 : premier et dernier bits = 11, ligne 3 ; bits du milieu = 1111, colonne 15 ; la valeur est 13, soit 1101. La sortie fait toujours 4 bits.
Exercice 4 : une ronde de Feistel
Avec la fonction f(D, K) = D XOR K sur 4 bits, G₀ = 1100, D₀ = 1010 et K = 0110, calculez G₁ et D₁, puis retrouvez G₀ à partir de G₁ et D₁.
Voir la réponse
f(D₀, K) = 1010 XOR 0110 = 1100. D₁ = G₀ XOR f = 1100 XOR 1100 = 0000. G₁ = D₀ = 1010. Pour inverser : D₀ = G₁ = 1010 ; G₀ = D₁ XOR f(G₁, K) = 0000 XOR (1010 XOR 0110) = 0000 XOR 1100 = 1100. On retrouve G₀ : le schéma est réversible quelle que soit f.
4Pourquoi le DES est tombé
4.1Une clé devenue trop courte
La faille du DES n’est pas dans sa conception, qui est solide, mais dans la taille de sa clé. On le pressentait : « même si une clé de 56 bits donne un nombre énorme de possibilités, de nombreux processeurs permettent de calculer plus de 106 clés par seconde » ; avec beaucoup de machines en parallèle, « un grand organisme (un État par exemple) » pourrait trouver la clé. La réalité a dépassé cette crainte, et plus vite :
- en juillet 1998, l’association américaine de défense des libertés numériques EFF (Electronic Frontier Foundation) présente une machine, surnommée Deep Crack, construite pour moins de 250 000 dollars, qui teste plus de 90 milliards de clés par seconde et retrouve la clé d’un défi public en 56 heures ;
- en janvier 1999, la même machine, aidée par des milliers d’ordinateurs de volontaires reliés par Internet (projet distributed.net), retrouve une clé en 22 heures et 15 minutes ;
- aujourd’hui, des cartes graphiques ou des circuits reprogrammables parcourent l’espace de clés en quelques heures ou moins, pour un coût modeste.
Le calcul est simple : 256 ≈ 7,2 × 1016 clés, divisés par 9 × 1010 clés par seconde, donnent environ 8 × 105 secondes, soit un peu plus de neuf jours pour tout essayer, et moitié moins en moyenne. Le DES, conçu pour résister des décennies, n’a donc tenu qu’une vingtaine d’années.
4.2Les cryptanalyses savantes
On cite souvent la cryptanalyse différentielle de Eli Biham et Adi Shamir (publiée en 1990-1991), qui « recherche des paires de texte en clair et des paires de texte chiffrées » et fonctionne pour un nombre de rondes inférieur à celui du DES complet. Il faut préciser deux choses. Contre le DES à seize rondes, cette méthode demande un nombre astronomique de messages choisis par l’attaquant (de l’ordre de 247), ce qui la rend théorique. Et on a su depuis que les concepteurs d’IBM connaissaient déjà cette technique dès 1974 et avaient conçu les boîtes de substitution pour lui résister, la NSA leur ayant demandé de ne rien en dire. Le Japonais Mitsuru Matsui a présenté en 1993-1994 une autre méthode, la cryptanalyse linéaire, qui demande environ 243 couples de messages connus : utile surtout pour mesurer la solidité des chiffrements suivants.
La leçon à retenir : les attaques « intelligentes » ont montré que le DES était très bien conçu, mais la force brute, c’est-à-dire l’essai de toutes les clés, a suffi à le battre, faute de clé assez longue.