PICSI

Le principe général d'une attaque algébrique a été introduit dans [1]. Cette attaque est une attaque qui exploite la structure algébrique du chiffrement, plus précisément l'idée est d'exprimer les boîtes S utilisées à l'aide d'un ensemble de relations algébriques vraies si possible avec une probabilité 1 et non plus seulement d'en faire une approximation linéaire. Le passage à travers la partie linéaire du chiffrement ne modifie pas la structure générale de ces équations. L'addition de clés peut être prise en compte ou non dans la résolution du système.

Ainsi, un chiffrement par blocs donné peut être exprimer comme un système d'équations algébriques, en combinant les différentes équations de chaque composant du chiffrement. Si il est alors possible de résoudre ce système plus rapidement que la complexité donnée par la recherche exhaustive de la clé, on peut considérer ce chiffrement comme cassé. Dans [1], les auteurs font remarquer que comme la seule opération non-linéaire de l'AES est l'inversion dans GF(2⁸) présente à chaque application d'une boîte S, on peut en déduire que sur GF(2⁸), xy=1,   ∀x ≠ 0, si x représente l'entrée de la boîte S. L'opération suivante étant linéaire, on en déduit sur GF(2), une première série de 8 équations bilinéaires vraie avec probabilité 255/256 (le cas 0 étant pathologique). Ces équations sont données dans [1]. On peut construire d'autres équations à partir des relations suivantes dans GF(2⁸), vraies cette fois ci avec probabilité 1, yx² = x,y²x⁴ = x², …, x¹²⁸ = x y¹²⁸. On peut ainsi en déduire 23 équations linéairement indépendantes qui comportent 81 monômes. D'autres extensions a des équations quadratiques permettent d'obtenir 39 équations en 137 termes. Ainsi, on obtient dans le cas de l'AES sous des clés de 128 bits, un système d'environ 1600 variables et 8000 équations quadratiques. Il s'agit à présent de résoudre le système obtenu. On peut ici utiliser plusieurs méthodes mais la plus commune reste celle comportant deux étapes : la linéarisation et l'utilisation d'un pivot de Gauss. La linéarisation consiste à remplacer chaque terme par une nouvelle variable, le système devient alors linéaire et on utilise un pivot de Gauss pour le résoudre. Les auteurs de [1] propose d'autres méthodes de résolution comme l'utilisation des algorithmes XL et XSL. Ils obtiennent ainsi une complexité de 2²³⁰ pour résoudre le système précédent dans le cas de l'AES 128. Cependant, le calcul de cette complexité et des complexités d'attaques algébriques reste sujet à discussion dans le monde de la cryptographie. D'autres résultats amusants concernant ce type d'attaques sont apparus. Notamment, Ferguson, Schroeppel et Whiting [2] ont exprimé l'AES comme une seule équation de 250 termes. Murphy et Robshaw dans [3] ont proposé le même type d'étude algébrique de l'AES mais cette fois sur le corps GF(2⁸).
Notons cependant que la découverte des attaques algébriques a surtout mis en péril, non pas les chiffrements par blocs (dont la partie non linéaire, si elle est bien choisie, permet de résister à ce type d'attaques) mais les chiffrements à flot et notamment ceux qui utilisent une fonction de remise à jour de l'état linéaire (en général un ou plusieurs LFSRs).

 

Références

[1]

Nicolas Courtois and Josef Pieprzyk. Cryptanalysis of block ciphers with overdefined systems of equations. In ASIACRYPT, volume 2501 of Lecture Notes in Computer Science, pages 267-287, 2002.

[2]

Niels Ferguson, Richard Schroeppel, and Doug Whiting. A simple algebraic representation of rijndael. In Selected Areas in Cryptography, volume 2259 of Lecture Notes in Computer Science, pages 103-111, 2001.

[3]

Sean Murphy and Matthew J. B. Robshaw. Essential algebraic structure within the aes. In CRYPTO, volume 2442 of Lecture Notes in Computer Science, pages 1-16, 2002.