PICSI

Wild Trail Strategy et Branch Number

Nous présentons ici une deuxième théorie sur les méthodes de diffusion de la partie linéaire développée dans [1], [2] et [3] .
L'idée de départ exposée dans la thèse de J. Daemen [1], connue sous le nom de "Wild Trail Strategy", est de choisir dans un premier temps des boîtes S avec des coefficients DP et LP très petits, puis de choisir une partie linéaire qui propage très bien les différences, c'est à dire qui implique le passage des caractéristiques différentielles ou linéaires dans un grand nombre de boîtes S. La fonction d'étage est alors choisie de telle façon que si, à une certaine étape, le nombre de boîtes S actives est petit, à l'étage suivant il doit être beaucoup plus grand.

Cette idée formulée en 1995 reste floue mais a été formalisée plus précisément dans [2] et dans [3]. Dans toute cette section, on notera F la transformation linéaire agissant sur un vecteur d'octets à n composantes dont on étudie les propriétés. F sera composée de deux transformations : θ une permutation linéaire de n octets qui garantit la plus haute diffusion possible et π une transformation qui garantit une très grande dispersion, c'est à dire qui "éloigne" les éléments actifs les uns des autres. Nous nous intéresserons tout d'abord aux critères de choix de θ qui dans le cas de l'AES correspond à la transformation MixColumns. Pour cela, on définit alors le poids d'un vecteur d'octets a comme étant son nombre d'octets non nuls. On note ce poids W(a). On définit alors : Le nombre de branches d'une transformation linéaire φ est

Nb = mina ≠ 0(W(a) + W(φ(a))).

Cette valeur peut être vue comme une mesure de la puissance de diffusion de l'application φ. Lorsque ce nombre est maximal, on dit qu'il vérifie la propriété MDS (Maximal Distance Separable), c'est à dire que Nb = n+1. Dans le cas de l'AES, le design de la transformation MixColumns répond aux différents impératifs de cette stratégie de construction. MixColumns ici égale à θ est la donnée de la matrice M, qui définit un code MDS. En effet, la matrice circulante M de taille 4 ×4, construite comme une matrice de code cyclique à partir d'un polynôme de degré 3, prend en entrée/sortie un vecteur d'octets de taille n=4. On peut voir cette transformation comme un code linéaire sur le corps GF(2⁸) dont les mots de code sont les éléments (x, M ·x)^T où x est un vecteur d'octets de taille 4. Les paramètres de ce code sont donc [8,4,d]. Ce code est MDS et atteint la borne de Singleton : d=5. Sa matrice génératrice est de la forme [I M] où I est la matrice identité de taille 4 ×4. Le nombre de branches associé à la transformation MixColumns est, d'après [3], égal à la distance minimum du code généré, on a donc ici Nb=d=5 qui est maximum. On peut également voir cette transformation comme une (4,4)-multipermutation. Quant à la transformation π qui compose également la partie linéaire, elle correspond à l'opération ShiftRows et consiste en un décalage des lignes de la matrice à chiffrer. Le but d'une telle application est une dispersion maximale. Précisons également que dans [3], une borne inférieure est démontrée en ce qui concerne le nombre de boîtes S actives sur 4 tours d'un algorithme composé à chaque étage d'une série de boîtes S, d'une partie linéaire composée des deux transformations décrites précédemment et d'une addition de clé classique. Cette borne vaut (Nb)². L'AES qui satisfait à toutes ces conditions a donc un nombre de boîtes S actives sur 4 étages au moins égal à 25 ce qui rend impossibles les attaques différentielle et linéaire compte tenu des très petits coefficients DP et LP des boîtes S choisies.
La stratégie présentée ici permet une bonne résistance aux cryptanalyses linéaire et différentielle. Cependant, la structure orientée octet de l'AES liée au choix de cette stratégie de construction rend ce dernier vulnérable à d'autres attaques, notamment les attaques par saturation. Celles-ci seront décrites dans le chapitre 2 de la deuxième partie de cette thèse.

 

Références

[1]

J. Daemen. Cipher and Hash Function Design Strategies Based on Linear and Differential Cryptanalysis. PhD thesis, Katholieke Universiteit Leuven, Belgique, Mars 1995.

[2]

J. Daemen and V. Rijmen. Aes proposal : Rijndael. In The Second Advanced Encryption Standard Candidate Conference. N.I.S.T., téléchargeable à l'adresse : http://csrc.nist.gov/encryption/aes/, 1999.

[3]

J. Daemen and V. Rijmen. The Design of Rijndael. Springer-Verlag, 2002.