PICSI

Boites S résistantes à la cryptanalyse

Peu après la découverte des attaques différentielle et linéaire, la recherche en cryptographie s'est tout naturellement orientée vers l'investigation de méthodes permettant de résister à ces attaques. Nous présenterons donc ici différentes techniques de preuves qui permettent de prémunir les algorithmes contre ces attaques.

De l'importance des boîtes S

  Vue générale

Les cryptologues se sont intéressés aux conditions que devaient remplir la fonction d'étage itérée f, considérée ici comme une fonction de GF(2)^m dans GF(2)ⁿ, pour résister aux cryptanalyses différentielle et linéaire. Dans le cas de la cryptanalyse différentielle, on cherche à rendre le coefficient

δf = maxα ≠ 0, β DPf(α,β)

le plus petit possible. Dans le cas linéaire, on s'intéresse au coefficient

λf = maxα, β ≠ 0 LPf(α,β).

Précisons qu'en règle générale, le caractère non linéaire de la fonction d'étage f provient de la ou des boîtes S utilisées. Il suffit donc d'étudier les coefficients δ_S et λ_S uniquement pour la ou les boîtes S. De plus, on a les propriétés suivantes :

• Les valeurs δ_f et λ_f restent inchangées si l'on compose f à gauche et à droite avec des permutations linéaires.
• Si f est bijective, on a :
  

  δf−1 = δf et λf−1 = λf

Dans de nombreux algorithmes comme l'AES ou MISTY, la ou les boîtes S sont en général la ou les composées d'une permutation linéaire et d'une exponentiation, c'est à dire d'une permutation de GF(2^m) qui à la variable x fait correspondre la sortie x^α avec pgcd(α, 2^m−1)=1 afin de conserver le caractère bijectif de l'opération. L'étude de la résistance de la fonction étage f aux cryptanalyses différentielle et linéaire se ramène donc souvent à l'étude des exposants particuliers utilisés dans les boîtes S en cherchant toujours à rendre minimum les coefficients δ_S et λ_S.

  Un peu de théorie...

On a les résultats suivants sur les meilleures bornes qui puissent être atteintes (voir par exemple [4]) : Théorème Pour toute fonction f de GF(2)^m dans GF(2)ⁿ, on a :

• δ_f ≥ 2⁻ⁿ. En cas d'égalité, f est dite parfaitement non-linéaire (PN).
• λ_f ≥ 2^−m. En cas d'égalité, f est dite courbe (B).

Les fonctions qui atteignent l'une ou l'autre des deux bornes sont identiques. En effet, d'après [8], on a : Théorème Une fonction est parfaitement non-linéaire si et seulement si elle est courbe.

Des fonctions qui atteignent ces bornes n'existent que pour certaines valeurs de m et n [8] : Théorème Les fonctions B ou PN n'existent que si m est pair et si m ≥ 2n.

On s'intéresse également à des fonctions ayant des propriétés légèrement moins fortes, étudiées notamment dans [4]. Théorème Pour toute fonction f de GF(2)^m dans GF(2)ⁿ, on a :

• δ_f ≥ 2^1−m. En cas d'égalité, f est dite presque parfaitement non-linéaire (APN).
• λ_f ≥ 2^1−m ( 1 +[((2^n−m−1)(2^m−1))/(2ⁿ−1)] ). En cas d'égalité, f est dite presque courbe (AB).

Les conditions sur l'existence de telles fonctions sont les suivantes [8] : Théorème   

• Des fonctions AB n'existent que si m=n et n est impair et ces fonctions vérifient également la propriété APN.
• Des fonctions APN n'existent que si m=2 et n=1 ou n ≥ m.

  Une fonction presque parfaitement non-linéaire utilisée dans MISTY

Un exemple de fonction presque parfaitement non-linéaire et presque courbe est la fonction f(x) = x^22i−2i+1 sur GF(2ⁿ) avec n impair et pgcd(n, i) = 1, dont les propriétés ont été étudiées par T. Kasami dans [6]. Dans le cas où n=7 et i=2, on obtient l'exposant d=13 auquel on associe la classe C de ses conjugués (c'est à dire l'ensemble des valeurs 2ⁱd et 2ⁱd⁻¹ modulo (2⁷−1) pour i variant de 0 à 6) qui définissent également des fonctions presque parfaitement non-linéaires et presque courbes d'après les propriétés vues précédemment. On a donc

Cn=7,13={81,35,70,13, 26, 52, 104, 69, 11, 22, 44,88,49,98}

L'exposant 11 qui appartient à cette classe représente la fonction puissance de Welch définie par f(x) = x^2[n−1/2]+3 qui est également presque parfaitement non-linéaire et presque courbe [5]. L'exposant le plus intéressant de C_n=7,13 reste pourtant 81 qui est celui utilisé par M. Matsui dans la boîte S₇ de Misty [7]. D'après ce qui précède, il est évident que cet exposant garantit à la boîte S₇ une bonne résistance aux cryptanalyses différentielle et linéaire. Cependant, d'autres propriétés indésirables de ces fonctions optimales utilisées dans les boîtes S notamment celles de MISTY rendent des versions réduites des algorithmes de chiffrement par blocs reposant sur ces boîtes vulnérables à d'autres formes de cryptanalyses, notamment la cryptanalyse différentielle d'ordre supérieur, MISTY ne dérogeant pas à la règle. Rappelons ici que les attaques différentielles d'ordre supérieur ne sont possibles que dans le cas où le degré de non-linéarité des valeurs intermédiaires est faible. On obtient une borne supérieure de ce degré grâce au spectre de Walsh, comme démontré dans [3]. Dans le cas particulier de MISTY, la fonction utilisée dans la boîte S₇ est AB, on en déduit donc d'après [4] et comme rappelé dans [3] que les valeurs contenues dans son spectre de Walsh sont 0 et 2^[(n+1)/2] uniquement et que celui-ci est donc 2⁴-divisible. On en déduit donc que le degré du produit de deux composantes booléennes de la boîte S₇ de MISTY est inférieur ou égal à 5. Ce résultat est également démontré dans [2]. C'est cette propriété particulière de la boîte S₇ (voir [2] et [3]) qui rend M'1, version réduite de MISTY, vulnérable à l'attaque différentielle d'ordre 7. Précisons également comme prouvé dans [3] que l'exposant choisi dans la boîte S de l'AES (l'inversion dans le corps GF(2⁸)) est l'une des rares fonctions a ne pas avoir cette propriété indésirable, à savoir que tout en étant une fonction APN, elle n'a pas un spectre de Walsh 2^l-divisible, ce qui prémunit l'AES contre une attaque différentielle d'ordre supérieur.

  Résistance aux attaques algébriques

Si les propriétés APN et AB garantissent une protection efficace contre les cryptanalyses différentielle et linéaire, il ne faut pas oublier que d'autres attaques existent. Il est également nécessaire lorsque l'on construit une boîte S à l'aide d'une fonction puissance de choisir un exposant dont le degré algébrique est suffisamment grand pour se prémunir contre une attaque par interpolation ou une attaque algébrique. Dans le cas d'une attaque algébrique, si on note (y₀, …,y_n−1) les sorties d'une boîte S sur n bits et (x₀,…, x_m−1) ses entrées sur m bits, il faut s'assurer que le degré algébrique liant les entrées et les sorties est suffisamment grand, c'est à dire que la plus petite valeur du degré de g telle que g(y₀, …, y_n−1,x₀, …,x_m−1)=0 soit grand. Comme prouvé dans [1], dans le cas de l'AES où m=n=3, le degré algébrique d'une telle fonction est au plus 3. Dans le cas de l'AES, ce degré est bien évidemment 2. Des études ont été menées sur les différents exposants habituellement utilisés dans la construction des boîtes S, on peut cependant se poser la question de la conduite générale de fonctions trop parfaites. Dans ce cas, ne vaut-il mieux pas prendre des boîtes S aléatoires ?

 

Références

[1]

F. Armknecht On the Existence of low-degree Equations for Algebraic Attacks. eprint, 2004, http://eprint.iacr.org/2004/185.pdf.

[2]

S. Babbage and L. Frisch. On misty1 higher order differential cryptanalysis. In Information Security and Cryptology, ICISC'00, Seoul, Corée, pages 23-37. Lectures Notes in Computer Science 2015, Springer-Verlag, 2000.

[3]

A. Canteaut and M. Videau. Degree of composition of highly functions and applications to higher order differential cryptanalysis. In Advances in Cryptology -EUROCRYPT'2002, Amsterdam, Hollande, pages 518-533. Lecture Notes in Computer Science 2332, Springer-Verlag, 2002.

[4]

F. Chabaud and S. Vaudenay. Links between differential and linear cryptanalysis. In Advances in Cryptology -EUROCRYPT'94, Pérouse, Italie, pages 256-265. Lecture Notes in Computer Science 950, Springer-Verlag, 1994.

[5]

H. Dobbertin. Almost perfect nonlinear power functions on gf(2ⁿ): The welch case. IEEE Transactions on Information Theory, 45(4), Mai 1999.

[6]

T. Kasami. The weight enumerators for several classes of subcodes of the second order binary reed-muller codes. Information and Control, 18:369-394, 1971.

[7]

M. Matsui. New block encryption algorithm misty. In Fast Software Encryption'97, Haifa, Israël, pages 54-68. Lectures Notes in Computer Science 1267, Springer-Verlag, 1997.

[8]

K. Nyberg. Perfect nonlinear s-boxes. In Advances in Cryptology -EUROCRYPT'91, Brighton, Royaume Uni, pages 378-385. Lecture Notes in Computer Science 547, Springer-Verlag, 1991.