PICSI

Principe.   Les attaques algébriques sont des attaques à clair connu qui exploitent des relations algébriques entre les bits du clair, ceux du chiffré et ceux de la clef secrète. La connaissance de plusieurs couples clairs-chiffrés fournit donc un système d'équations dont les inconnues sont les bits de la clef secrète. Ces derniers peuvent alors être retrouvés en résolvant le système, ce qui est possible s'il est de degré faible, de petite taille ou qu'il possède une structure particulière.

Attaque algébrique élémentaire.   Une attaque algébrique immédiate, décrite par Shannon [15,Page 711], consiste simplement à écrire les équations de chiffrement, c'est-à-dire à exprimer les bits du chiffré en fonction des bits de clair et des bits de clef. On peut alors résoudre le système obtenu par une méthode simple, appelée linéarisation ; il s'agit d'identifier chacun monôme dans lequel interviennent des bits de clef à une nouvelle variable. Pour un système de degré maximal d, on obtient ainsi un système linéaire en au plus

d ∑ i=1    i n   variables

où n est le nombre de bits de la clef secrète. Ce gros système linéaire peut alors être inversé par une simple élimination de Gauss ou des techniques d'inversion un peu plus sophistiquées comme la méthode de Strassen, dont la complexité est donnée par le nombre d'équations du système, élevé à un exposant ω avec ω = 3 dans le cas du pivot de Gauss, ou ω = 2,37 [6]. Il existe d'autres techniques beaucoup plus efficaces pour résoudre de tels systèmes algébriques : il s'agit des algorithmes de calcul de bases de Gröbner, largement étudiés en calcul formel. Les algorithmes de base de Gröbner les plus utiles dans le contexte de la cryptanalyse sont décrits et étudiés dans [12,3], notamment les algorithmes F4 et F5 de Jean-Charles Faugère. Cette attaque algébrique simple peut s'avérer extrêmement performante par exemple contre les générateurs pseudo-aléatoires constitués d'un unique LFSR filtré par une fonction booléenne f de degré faible. Ainsi, si l'on note z₀, …, z_n−1 les n bits de l'état initial du LFSR et L la fonction linéaire qui exprime l'état interne du registre en fonction de l'état précédent, la connaissance de N bits de la suite chiffrante s conduit au système d'équations

       s0 = f (z0,…, zn−1) s1 = f (L(z0,…, zn−1)) s2 = f (L2(z0,…, zn−1)) :

en n inconnues (les bits de l'état initial), de degré égal au degré de la fonction de filtrage f. L'état initial peut donc être retrouvé en linéarisant ce système. On obtient alors de l'ordre de

d ∑ i=1    i n   ≅ nd

variables. L'attaque nécessite donc la connaissance de n^d bits de suite chiffrante et de l'ordre de

nωn opérations

avec ω ≅ 2,37. Si la taille de l'état initial correspond au double de la taille de la clef k (taille minimale pour résister aux attaques par compromis temps-mémoire), cette attaque algébrique est plus performante que la recherche exhaustive dès que le degré de f vérifie

degf ≤ 0.42   k 1+ log2 k    .

Une condition nécessaire de sécurité pour les tous les générateurs pseudo-aléatoires dont la fonction de transition est linéaire est donc que le degré de la fonction de filtrage doit être élevé.
Attaques algébriques évoluées sur les chiffrements à flot.   En 2003, Courtois et Meier [9] ont proposé une amélioration de l'attaque précédente, qui peut parfois aboutir même lorsque le degré de la fonction de filtrage f est élevé. L'attaque fonctionne dès lors qu'il existe des relations de petit degré entre la sortie de la fonction et ses entrées [14]. Plus précisément, l'attaquant recherche des fonctions g et h de petit degré qui vérifient

• pour tout (x₁, …, x_n), g(x₁, …, x_n) f(x₁, …, x_n) = 0,
• ou pour tout (x₁, …, x_n), h(x₁, …, x_n) [1+ f(x₁, …, x_n)] = 0.

Si de telles fonctions g ou h de degré d existent, on peut engendrer un système d'équations de degré d de la manière suivante :

• si s_t=1, on a g(z_t, …, z_t+n−1) = 0 où (z_t, …, z_t+n−1) est l'état du registre à l'instant t ;
• si s_t=0, on a h(z_t, …, z_t+n−1) = 0.

En exprimant l'état du registre à l'instant t comme une fonction linéaire de l'état initial, on obtient comme précédemment un système d'équations de degré d en n variables (les bits de l'état initial), que l'on peut résoudre par les techniques évoquées plus haut. Pour se mettre à l'abri de ces attaques, il est donc essentiel que toutes les fonctions g et h qui possèdent la propriété décrite ci-dessus soient de degré élevé. Les fonctions g à n variables qui vérifient g(x₁, …, x_n)f(x₁, …,x_n) = 0 forment un idéal de l'anneau des fonctions booléennes à n variables, appelé annulateur de la fonction f, AN(f). Le paramètre essentiel, qui influence la complexité des attaques algébriques, est donc le degré minimal des fonctions (non nulles) de AN(f) et AN(1+f). Ce paramètre est appelé immunité algébrique de f, noté AI(f) :

AI(f) = min deg{g ∈ AN(f) ∪AN(1+f),   g ≠ 0} .

Ainsi, pour un générateur pseudo-aléatoire dont l'état interne est de taille n=2k où k est le nombre de bits de la clef secrète et dont la fonction de transition est linéaire (par exemple, un LFSR filtré), l'attaque précédente sera plus performante que la recherche exhaustive de la clef dès que l'immunité algébrique de la fonction de filtrage vérifie

AI(f) ≥ 0.42   k 1+ log2 k    .

Immunité algébrique des fonctions de filtrage.   L'immunité algébrique de la fonction de filtrage, au même titre que son degré, est donc un paramètre important qui doit être pris en compte lors de la conception d'un générateur pseudo-aléatoire dont la fonction de transition est linéaire. On peut aisément démontrer [9] que l'immunité algébrique d'une fonction booléenne à n variables est toujours inférieure ou égale à

  n+1 2    .

A l'heure actuelle, les rares familles générales de fonctions connues dont l'immunité algébrique est maximale présentent d'autres inconvénients qui rendent leur utilisation directe peu souhaitable dans un chiffrement à flot. En revanche, le fait que les fonctions d'immunité algébrique élevée sont nécessairement éloignées des fonctions de degré 1 (au sens où elles ont une non-linéarité élevée) est une propriété intéressante. Ainsi, les générateurs à base de LFSRs qui résistent aux attaques algébriques ne sont généralement pas vulnérables aux attaques par corrélation rapides. Une caractérisation plus poussée des fonctions d'immunité algébrique élevée, l'établissement d'éventuelles relations entre ce paramètre et d'autres quantités intervenant dans la résistance à d'autres types d'attaques, comme l'ordre de non-corrélation, font actuellement l'objet de recherches plus poussées.
Attaques algébriques rapides.   Il existe une variante plus générale et souvent plus efficace des attaques algébriques contre les chiffrements à flot, introduite par Courtois [7] sous le nom d'attaque algébrique rapide. Une première amélioration de l'attaque précédente, permettant de diminuer le degré du système d'équations à résoudre, consiste à rechercher des équations de petit degré en les bits de l'état initial, qui font intervenir plusieurs bits consécutifs de suite chiffrante. La recherche de ces équations est souvent un problème complexe, dont la complexité augmente considérablement quand le nombre de bits de suite chiffrante intervenant simultanément dans les équations augmente. On peut alors être amené à ne considérer que des relations ayant une forme particulière, obtenues en additionnant plusieurs relations connues de manière à faire baisser le degré [13]. Un exemple d'attaque algébrique rapide est celle qui permet de cryptanalyser le générateur par LFSR filtré Sfinks, candidat à l'appel eSTREAM [8]. Des variantes plus sophistiquées des attaques algébriques s'appliquent également lorsque la fonction de filtrage fait intervenir quelques bits de mémoire mis à jour de manière non linéaire, comme dans le système E0 [2,1], ou lorsqu'il s'agit non pas d'une fonction booléenne, mais d'une fonction qui produit plusieurs bits de sortie à chaque instant [10].
Attaques algébriques sur les chiffrements par blocs.   Le principe de base des attaques algébriques décrit par Shannon s'applique évidemment aussi aux algorithmes de chiffrement par blocs dès lors qu'il est possible d'exprimer le chiffrement par des équations de degré faible en les bits de la clef (ou des sous-clefs). Ainsi, Courtois et Pieprzyk [11] ont suggéré d'appliquer cette technique pour cryptanalyser l'AES, en exploitant le fait que la fonction d'inversion dans le corps fini à 256 éléments employée dans l'AES conduit à des relations de degré 2 entre les bits de l'entrée et ceux de la sortie de chaque tour de l'algorithme. Toutefois, le système résultant de ces équations, même s'il n'est que de degré 2, est de très grande taille car il fait intervenir les bits de toutes les sous-clefs de l'AES. A l'heure actuelle, les méthodes connues de résolution de systèmes algébriques ne semblent donc pas permettre de le résoudre plus efficacement que la recherche exhaustive de la clef. Les attaques algébriques contre les chiffrement par blocs semblent donc encore hors de portée, même si elles ont été mises en uvre récemment sur des systèmes de petite taille [5,3].

 

Références

[1]

F.  Armknecht. << A linearization attack on the Bluetooth keystream generator >>. http://th.informatik.uni-mannheim.de/people/armknecht/E0.ps, 2002.

[2]

F.  Armknecht, M.  Krause. << Algebraic attacks on combiners with memory >>. Advances in Cryptology - CRYPTO 2003, 2729 Lecture Notes in Computer Science, 162-176. Springer-Verlag, 2003.

[3]

G.  Ars. << Applications des bases de Gröbner à la cryptographie >>. PhD thesis, Université de Rennes 1, 2005. http://name.math.univ-rennes1.fr/gwenole.ars/.

[4]

A.  Canteaut. << Open problems related to algebraic attacks on stream ciphers >>. Workshop on Coding and Cryptography - WCC 2005, Lecture Notes in Computer Science. Springer-Verlag, 2006.

[5]

C.  Cid, S.  Murphy,, M.  Robshaw. << Small Scale Variants of the AES >>. Fast Software Encryption - FSE 2005, 3557 Lecture Notes in Computer Science, 145-162. Springer Verlag, 2005.

[6]

D.  Coppersmith, S.  Winograd. << Matrix multiplication via arithmetic programming >>. Journal of Symbolic Computation, (9):251-280, 1990.

[7]

N.  Courtois. << Fast algebraic attacks on stream ciphers with linear feedback >>. Advances in Cryptology - CRYPTO 2003, 2729 Lecture Notes in Computer Science, 177-194. Springer-Verlag, 2003.

[8]

N.  Courtois. << Cryptanalysis of Sfinks >>. IACR Eprint report 2005/243, 2005. http://eprint.iacr.org/2005/243.

[9]

N.  Courtois, W.  Meier. << Algebraic attacks on stream ciphers with linear feedback >>. Advances in Cryptology - EUROCRYPT 2003, 2656 Lecture Notes in Computer Science, 345-359. Springer-Verlag, 2003.

[10]

N.T. Courtois. << Algebraic Attacks on Combiners with Memory and Several Outputs >>. ICISC 2004, Lecture Notes in Computer Science. Springer-Verlag, 2005. http://eprint.iacr.org/2003/125/.

[11]

N.T. Courtois, J.  Pieprzyk. << Cryptanalysis of Block Ciphers with Overdefined Systems of Equations >>. Advances in Cryptology - ASIACRYPT 2002, 2502 Lecture Notes in Computer Science, 267-287. Springer-Verlag, 2002.

[12]

A. Canteaut et  al.. << Open Research Areas in Symmetric Cryptography and Technical Trends in Lightweight Cryptography >>. ECRYPT report, 2005. www.ecrypt.eu.org/documents/D.STVL.3-2.5.pdf.

[13]

P.  Hawkes, G. G. Rose. << Rewriting variables: the complexity of fast algebraic attacks on stream ciphers >>. Advances in Cryptology - CRYPTO 2004, 3152 Lecture Notes in Computer Science, 390-406. Springer-Verlag, 2004.

[14]

W.  Meier, E.  Pasalic,, C.  Carlet. << Algebraic attacks and decomposition of Boolean functions >>. Advances in Cryptology - EUROCRYPT 2004, 3027 Lecture Notes in Computer Science, 474-491. Springer-Verlag, 2004.

[15]

C.E. Shannon. << Communication theory of secrecy systems >>. Bell system technical journal, 28:656-715, 1949.