Cryptanalyse linéaire et tables d’approximation

La cryptanalyse linéaire (Matsui, 1993) est une attaque à texte en clair connu qui recherche des approximations linéaires (XOR de bits précis) d'un chiffrement, vérifiées avec une probabilité p ≠ 1/2. À l'aide de nombreuses paires texte en clair-chiffré, le biais statistique révèle des bits de la clé.

Une approximation linéaire pour une boîte-S : la somme de certains bits d'entrée XOR la somme de certains bits de sortie = 0 (mod 2) avec une probabilité p. Elle s'exprime ainsi : P[a·x XOR b·y = 0] = 1/2 + ε, où a,b sont des masques de bits et ε est le biais (|ε| >> 0 est souhaitable).

La LAT compte, pour chaque masque d'entrée a et masque de sortie b, le nombre d'entrées x pour lesquelles (a·x) XOR (b·S(x)) = 0. Soustraire 2^{n-1} donne le biais. Une bonne boîte-S a un |max_bias| = 1 (probabilité 1/2 ± 1/2^{n/2}) : aussi uniforme que possible.

Pour des approximations linéaires indépendantes sur plusieurs tours, les biais se multiplient : ε_total = 2^{r-1} * ε_1 * ε_2 * ... * ε_r. Chaque approximation de tour réduit de moitié le biais effectif. Après de nombreux tours, le biais total tend vers 0, ce qui exige un nombre exponentiellement plus élevé de paires pour être détecté.

Pour attaquer un chiffrement à r tours : trouver une caractéristique linéaire ε sur r-1 tours. Collecter N = 1/ε^2 textes en clair connus. Pour chaque octet de clé candidate du dernier tour k' : déchiffrer partiellement le dernier tour avec XOR, puis vérifier si l'approximation linéaire est vraie plus de N/2 fois. La bonne valeur k' présente le bon biais.

Matsui a attaqué DES à 16 tours en 1993 à l'aide d'une approximation linéaire sur 14 tours présentant un biais de 2^{-21.4}. L'attaque nécessitait 2^{43} textes en clair connus. Elle a récupéré 26 bits de clé lors de la phase 1 ; les 30 restants ont été trouvés par recherche exhaustive. Il s'agissait de la première attaque pratique plus rapide que la force brute sur DES complet.

La boîte-S d'AES a une entrée LAT maximale |ε| = 4/256 = 1/64 par boîte-S. La stratégie Wide Trail limite à au moins 25 le nombre de boîtes-S actives dans toute caractéristique sur 4 tours. Le biais total est ≤ (1/64)^{25/2} ≈ 2^{-75}. Il faudrait 2^{150} textes en clair connus, ce qui est irréalisable.

Différentielle : paires de textes en clair connus/choisis ; exploite les différences de sortie. Linéaire : textes en clair connus ; exploite les approximations linéaires statistiques. Dans les attaques pratiques, toutes deux utilisent des textes en clair choisis. Toutes deux sont des critères de conception : les boîtes-S doivent résister aux deux (faible maximum de DDT AND faible maximum de LAT).

Utiliser simultanément plusieurs approximations linéaires afin de réduire la complexité des données. Nyberg et Leander ont étendu la méthode de Matsui : combiner M approximations réduit la quantité de données d'un facteur log(M). Cette méthode s'applique à PRESENT, SIMON et à d'autres chiffrements légers.

Approximation linéaire appliquée aux chiffrements par flot : trouver une corrélation entre le flot de clés et une fonction linéaire de la sortie du LFSR. Cette corrélation, si elle est non nulle, permet de récupérer la clé plus rapidement qu'avec une recherche exhaustive. Elle a inspiré la conception de fonctions de combinaison non linéaires dans les chiffrements par flot.

La cryptanalyse intégrale (Knudsen-Wagner) consiste à choisir un ensemble de textes en clair dans lequel certains octets prennent les 256 valeurs tandis que les autres restent fixes. Après plusieurs tours, le XOR de toutes les sorties à certaines positions vaut 0 (équilibré). Cette méthode exploite la structure d'AES et attaque efficacement les versions d'AES à nombre de tours réduit.

Que dit le lemme de cumul au sujet de la combinaison d'approximations linéaires ?

La cryptanalyse linéaire recherche les approximations linéaires biaisées des boîtes-S. AES y résiste grâce à sa boîte-S optimisée pour la LAT et à Wide Trail. Matsui a cassé DES avec 2^43 textes en clair connus en utilisant une caractéristique sur 14 tours. Ensuite : les attaques par anniversaire et la recherche de collisions.