PICSI

Constructions résistantes aux attaques connues

1  Principe de diffusion

Les critères présentés dans et portent essentiellement sur les propriétés de confusion que doit remplir une bonne fonction étage. Nous nous sommes plus particulièrement intéressés au rôle de la boîte S dans la résistance aux attaques connues. L'autre grand critère que doit respecter un bon algorithme de chiffrement par blocs, déjà défini par Shannon en 1949, est la diffusion. Nous allons donc présenter ici deux méthodes qui permettent de garantir à la fonction étage une bonne diffusion. La première méthode introduite par S. Vaudenay dans [1] fait appel à ce qu'il nomme des multipermutations, généralisation du graphe FFT dont une illustration est le réseau de la partie linéaire de l'algorithme SAFER. S. Vaudenay utilise le principe des multipermutations dans l'algorithme CS-Cipher. La deuxième méthode est la théorie nommée "Wild Trail Strategy" dont l'idée principale est de rendre maximal le nombre de boîtes S äctives", c'est à dire d'assurer une diffusion maximale des caractéristiques différentielles ou linéaires. C'est cette théorie qui a conduit au choix de la partie linéaire de l'AES.

2  Les Multipermutations

Le concept de multipermutation a été introduit par S. Vaudenay et C. Schnorr dans un article présenté à Eurocrypt'94 [1], l'idée étant de créer des boîtes de diffusion parfaite. Son lien avec ce qu'on nomme le graphe FFT (transformation de Fourier rapide) semble évident. Le graphe FFT ou schéma papillon fait dans sa forme la plus simple correspondre 2 entrées à 2 sorties, chaque sortie étant influencée à travers des permutations par les deux entrées. La diffusion est donc ici maximale : toute sortie est liée au nombre maximal d'entrées. On peut généraliser ce graphe à 2ⁿ entrées et 2ⁿ sorties à l'aide d'un réseau de connexions reliant n étages de 2ⁿ⁻¹ boîtes 2 ×2 tel que celui utilisé dans la partie linéaire de SAFER. ======================================================================= Cependant, les critères que doivent vérifier les multipermutations sont plus forts que ceux vérifiés dans le cas particulier de SAFER où la boîte élémentaire 2×2 n'est pas une multipermutation, L'idée principale des multipermutations étant de maximiser le nombre de sorties modifiées lors de la modification d'un certain nombre d'entrées. On définit donc une multipermutation comme suit : Soit f une fonction de l'ensemble Z^r dans Zⁿ. On dit que f est une (r,n)-multipermutation sur Z si deux (r+n)-uplets différents de la forme (x,f(x)) ne peuvent coïncider sur r positions différentes. Cela signifie en particulier que si deux entrées x et x′ de taille r diffèrent sur une position, les sorties correspondantes de taille n doivent être différentes sur n positions, c'est à dire que toutes les entrées influencent toutes les sorties. La diffusion est donc bien maximum. Plus généralement, la modification de m entrées entraîne la modification d'un nombre de sorties au moins égal à n+1−m.
On peut également donner la définition équivalente suivante liée aux codes correcteurs d'erreurs : Une (r,n)-multipermutation sur Z est une fonction f de Z^r dans Zⁿ telle que l'ensemble des (r+n)-uplets de la forme (x, f(x)) soit un code de distance minimale n+1. Rappelons qu'un code correcteur d'erreur de distance d sur Z est un sous-espace de dimension k de l'espace Zⁿ où deux vecteurs de l'espace d'arrivée ont une distance de Hamming au moins égale à d, d étant le plus petit nombre vérifiant cette propriété. On caractérise donc un code par la donnée de l'espace Z et du triplet [n,k,d]. Pour un code de longueur n et de dimension k données, la distance minimale est majorée par la borne dite de Singleton :

d ≤ n−k+1

Dans le cas où l'ensemble Z est un corps de caractéristique q, si on note f une (r,n)-multipermutation linéaire, la donnée de l'ensemble des mots (x, f(x)) définit un code MDS (Maximal Distance Separable) de longueur (n+r) et de taille q^r, c'est à dire un code qui atteint la borne de Singleton et dont la distance minimale est maximale. Pour une meilleure compréhension de ce qu'est une multipermutation, l'exemple le plus simple est une multipermutation à une entrée et à n sorties qui est en fait une famille de n permutations de l'entrée.
Figure 1: Un Étage de CS-Cipher
Un exemple de mise en oeuvre de la notion de multipermutation est le chiffrement CS-Cipher décrit dans [2], composé de 8 étages, qui prend en entrée/sortie des mots de 64 bits découpés en octets. Un étage (voir figure 1) se compose de trois transformations répétées trois fois. La première est un x-or avec une sous-clé pour le premier sous-étage et avec des constantes pour les deux autres sous-étages. La deuxième transformation M est une (2,2)-multipermutation prenant en entrée/sortie des couples d'octets, suivie d'une permutation P sur les octets tenant le rôle de boîte S. La troisième transformation est une permutation des octets selon un graphe FFT sur les octets qui permet une diffusion maximale de l'information. La fonction M prend en entrée une chaîne de 16 bits x scindée en deux octets x_l||x_r et calcule M(x)=y_l||y_r avec y_l = P(φ(x_l) ⊕x_r) et y_r = P(R_l(x_l) ⊕x_r) où φ(x_l) = (R_l(x_l) ∧55_hex) ⊕x_l), R_l étant la rotation à gauche de 1 bit. Il s'agit bien d'une (2,2)-multipermutation. La modification d'une entrée entraîne la modification de toutes les sorties. La fonction inverse nécessaire au déchiffrement définie par (x_l || x_r) = M⁻¹(y_l || y_r) peut être calculée de la manière suivante :

xl = φ′(yl) ⊕P(yr) et xr = Rl(xl) ⊕P(yr)

avec φ′(x) = (R_l(x) ∧aa_hex) ⊕x. La diffusion dans CS-Cipher est donc maximale, car elle combine les propriétés des multipermutations à celles d'un schéma FFT.

 

Références

[1]

C. P. Schnorr and S. Vaudenay. Black box cryptanalysis of hash networks based on multipermutations. In Advances in Cryptology -EUROCRYPT'94, Pérouse, Italie, pages 47-57. Lecture Notes in Computer Science 950, Springer-Verlag, 1994.

[2]

J. Stern and S. Vaudenay. Cs-cipher. In Fast Software Encryption'98, Paris, France, pages 189-205. Lectures Notes in Computer Science 1372, Springer-Verlag, 1998.