Fondamentaux de la cryptanalyse différentielle

La cryptanalyse différentielle (Biham et Shamir, 1990) est une attaque à texte en clair choisi qui analyse la propagation des différences entre des paires de textes en clair à travers un chiffrement. En trouvant des différences d'entrée qui produisent avec une forte probabilité des différences de sortie prévisibles, l'attaquant récupère statistiquement des bits de la clé.

Pour les chiffrements fondés sur XOR : différence ΔX = X XOR X'. Pour les chiffrements fondés sur l'addition : différence ΔX = X - X' mod 2^n. Les différences XOR sont les plus courantes, car XOR commute avec l'utilisation d'une clé XOR (les effets du calendrier de clé s'annulent dans les paires différentielles).

Une paire différentielle (P, P') possède une différence d'entrée ΔP = P XOR P'. Après le chiffrement : (C, C') avec une différence de sortie ΔC = C XOR C'. Une différentielle utile est ΔP → ΔC avec une forte probabilité p — cela signifie que de nombreuses paires (P, P') présentant la différence ΔP produisent la différence de sortie ΔC.

La DDT (table de distribution différentielle) compte, pour chaque différence d'entrée Δx et chaque différence de sortie Δy, combien d'entrées x satisfont S(x) XOR S(x XOR Δx) = Δy. Diviser par 2^n donne la probabilité. Une bonne boîte-S a une valeur maximale de DDT égale à 2 (probabilité 1/2^{n-1}) : aucune différentielle forte.

Pour un chiffrement par blocs à r tours : trouver une séquence ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1} où chaque transition de tour a une probabilité connue. Multiplier les probabilités des différents tours : probabilité globale p = p1 * p2 * ... * p_{r-1}. L'attaque utilise 2/p paires pour récupérer la clé du dernier tour.

Avec une différentielle sur r-1 tours présentant une forte probabilité : collecter N = 2/p paires de textes en clair. Pour chaque clé candidate du dernier tour K', déchiffrer les deux chiffrés sur un tour, appliquer XOR aux résultats et vérifier si la différence correspond à ΔU_{r-1}. La bonne K' correspond environ N/2 fois ; les mauvaises clés correspondent environ N/2^{bit_size} fois.

La boîte-S d'AES est l'inverse multiplicatif sur GF(2^8), suivi d'une transformation affine. Son maximum de DDT est 4 (sur 256), ce qui donne une probabilité différentielle ≤ 4/256 = 1/64 par boîte-S. AES possède 4 boîtes-S par tour, mais la conception Wide Trail garantit que les caractéristiques différentielles complètes sont inférieures à 2^{-100}.

La conception Wide Trail de Joan Daemen (utilisée dans AES/Rijndael) définit le nombre de branches B de MixColumns. Toute caractéristique différentielle non triviale traversant un tour active au moins B boîtes-S. 4 tours × 4 boîtes-S par tour garantissent au moins 25 boîtes-S actives → probabilité < 2^{-100}.

Les différentielles tronquées ne précisent qu'une partie de la différence, par exemple les colonnes qui sont actives, et non les valeurs exactes des différences. Elles permettent des attaques sur un plus grand nombre de tours, lorsque les différentielles complètes sont trop faibles. Elles sont utilisées contre AES à nombre de tours réduit, SERPENT et d'autres chiffrements SPN.

Une différentielle impossible est une paire (ΔP, ΔC) qui ne peut se produire avec aucune clé. Toute clé qui associe une paire observée (P, P') présentant cette différence est éliminée. En collectant suffisamment de paires, toutes les mauvaises clés sont éliminées, ce qui laisse la bonne clé.

L'attaque boomerang (Wagner, 1999) combine deux différentielles courtes en une attaque adaptative à textes en clair/chiffrés choisis. Elle décompose le chiffrement en deux moitiés, chacune présentant une différentielle courte à forte probabilité, ce qui permet d'attaquer un nombre de tours supérieur à celui qu'autoriserait une seule différentielle.

Quel est le rôle de la table de distribution différentielle (DDT) en cryptanalyse ?

La cryptanalyse différentielle exploite la propagation de différences entrée→sortie à forte probabilité. AES lui résiste grâce à sa boîte-S optimisée pour la DDT et à la conception Wide Trail. Ensuite : la cryptanalyse linéaire et les tables d'approximation.