PICSI

Nous présentons dans cette partie une attaque particulière, dédiée à l'AES et décrite dans le document initial de présentation de l'AES [3]. Cette attaque qui exploite l'aspect trop parfait de la diffusion a tout d'abord été appliquée à l'algorithme Square [2], premier chiffrement par blocs proposé par V. Rijmen, J. Daemen et L. Knudsen. Cette cryptanalyse permet d'attaquer jusqu'a 6 étages de l'AES.

1  L'attaque dédiée à l'AES

Nous espérons que le lecteur est familier de la cryptanalyse différentielle sinon, nous lui conseillons de lire car la Square attack est une généralisation d'une cryptanalyse différentielle qui opère par saturation d'un octet. Le principe général est simple et utilise une propriété particulière sur trois étages. Soit Y le texte clair d'entrée, on note alors Z la sortie du premier étage, R la sortie du deuxième étage et T la sortie du troisième étage. Plus précisément, ce n'est pas un seul texte clair que l'on va chiffrer mais 256 et on note : Y(y) =

Y0,0	Y0,1	Y0,2	y
Y1,0	Y1,1	Y1,2	Y1,3
Y2,0	Y2,1	Y2,2	Y2,3
Y3,0	Y3,1	Y3,2	Y3,3

où y prend toutes les valeurs possibles comprises entre 0 et 255 (on sature un octet). Observons à présent ce qui se passe à travers trois étages du chiffrement comme le présente la figure 1 :

• On considère donc à l'entrée du premier étage 256 textes clairs Y(y) qui ont la forme précédente avec l'octet actif y (c'est à dire un octet qui prend toutes les valeurs entre 0 et 255).
• Le premier MixColumns transforme l'octet actif en une colonne d'octets actifs.
• Le ShiftRows du deuxième tour diffuse alors cette colonne sur les quatre colonnes de la matrice. Le MixColumns du deuxième étage transforme alors ces 4 octets actifs en une pleine matrice d'octets actifs. Jusqu'à l'entrée du MixColumns du troisième tour, les transformations impliquées constituent une bijection.
• On utilise à présent une propriété due à la semi-bijectivité du MixColumns du troisième tour et à la bonne répartition des éléments d'entrée Y. On note a tout octet actif à l'entrée du troisième MixColumn. On a, pour un octet particulier :
  

  ⊕ b=MixColumn(a),a ∈ GF(256)  b(a) = 0         (1)

Figure 1: Trois étages de l'AES avec un octet saturé
On en déduit donc que tous les octets à l'entrée du quatrième tour sont équilibrés. En particulier, on a si on utilise les notations de la figure 1 :

⊕ S(y),y ∈ {0, …, 255}  S(y) = 0         (1)

On peut donc à partir de cette propriété monter une attaque sur quatre étages de l'AES en considérant que le quatrième tour est le dernier, c'est à dire qu'il ne contient pas de MixColumns. Si on note W(y) les 256 textes chiffrés après 4 tours de la fonction d'étage de l'AES, on peut exprimer chacun des S(y) comme le déchiffré de W(y) dépendant de 1 octet de clé noté ici K⁴₀ et d'un octet de W(y) noté ici W₀(y). On a donc une relation du type S(y)=ByteSub⁻¹(W₀(y) ⊕K⁴₀) entre chaque octet d'entrée et de sortie du dernier étage. On peut alors déterminer la valeur de l'octet K⁴₀ par la boucle suivante :

Chiffrer les 256 textes clairs Y(y) pour y de 0 à 255

Récupérer les 256 textes chiffrés W(y) correspondants

choisir une valeur pour K40

calculer les valeurs des S(y) fonction de W0(y) pour tout y

Si les 256 S(y) vérifient la propriété (1) alors

renvoyer K40

Sinon

refaire pour une autre valeur de K40

Fin Si

On peut, en fait, utiliser cet algorithme pour déterminer tous les octets de la dernière sous-clé K⁴. Cette attaque nécessite le chiffrement de 2⁸ textes clairs, en théorie tout du moins. Pour être sûr d'éliminer toutes les fausses alarmes sur l'octet de clé, on préfère augmenter légèrement la complexité de l'attaque en chiffrant 2⁹ textes clairs choisis, c'est à dire deux séries de textes clairs Y(y).
On peut étendre ce résultat en ajoutant un cinquième tour à la fin. Pour calculer la valeur des S(y) à partir du cinquième tour et non plus du quatrième, on a besoin de connaître 4 octets supplémentaires de la dernière clé. Comme dans l'attaque sur 4 tours, on élimine les mauvaises clés en vérifiant la propriété (1). Pour éviter toutes les fausses alarmes de clés, on utilise 4 ensembles de 256 textes clairs Y(y). On a besoin de tester 2⁴⁰ valeurs de clé. Cette attaque nécessite donc 2¹¹ textes clairs choisis et l'exécution de 2⁴⁰ chiffrements.
On peut également étendre cette attaque en ajoutant un tour au début. L'idée est d'obtenir un ensemble Y(y) à la sortie du premier tour contenant un seul octet actif. Pour ce faire, on a besoin de connaître la valeur de 4 octets de clé utilisés avant l'entrée du deuxième tour. On considère donc un ensemble de 2³² textes clairs et grâce à l'hypothèse sur les quatre octets de clé, on en sélectionne 256 pour former un ensemble Y(y). On peut alors appliquer l'attaque sur 4 étages. On répète ainsi l'attaque pour différentes hypothèses sur les 4 octets de clés. Cette attaque nécessite 2³² textes clairs choisis et l'exécution de 2⁴⁰ chiffrements.
On peut combiner les deux extensions à l'attaque sur 4 étages pour obtenir une attaque sur 6 étages utilisant 2³² textes clairs choisis et l'exécution de 2⁷² chiffrements qui permettent de tester en tout 9 octets de clé.

2  La square attack, un point de vue plus théorique : attaque par saturation ou cryptanalyse intégrale

L'attaque décrite dans la section 0.1.1 peut être vue de manière théorique. En 2001 ce type d'attaque a pris le nom d'attaques par saturation dans un article de S. Lucks [6]. Notons également que le nom proposé par L. Knudsen dans [5] à FSE'02 et plébiscité par les participants de cette conférence est "Cryptanalyse Intégrale". Il s'agit ici de ßaturer" un ou plusieurs octets, c'est à dire de faire prendre à une partie du message toutes les valeurs possibles et d'utiliser les propriétés induites par la fonction itérée (par exemple sa semi-bijectivité, c'est à dire qu'après un certain nombre d'étages, les octets du chiffré obtenu peuvent être vus comme une somme de bijection des octets du clair) pour créer un distingueur. Ces attaques peuvent également être vues comme un cas particulier de la classe des attaques différentielles d'ordre supérieur. Deux attaques de ce type sont à ce jour connues contre Rijndael (la première est décrite dans la section 0.1.1, la deuxième qui est une généralisation de la première est décrite dans [4]). Je prendrai ici l'exemple de trois étages de l'algorithme SAFER décrit dans . Rappelons que SAFER prend en entrée un bloc de 64 bits, découpé en 8 octets. Si on fait prendre à deux octets d'entrée toutes les valeurs possibles comprises entre 0 et 255, les autres octets d'entrée étant fixés, au bout de deux tours, la somme modulo 256 des (256)² valeurs est nulle. En effet, si on ne sature qu'un seul octet à l'entrée du chiffrement, au bout de deux tours, on obtient des ensembles de 32 valeurs pour chacun des huit octets, cela étant lié à l'alternance des x-or avec les clés et des additions classiques et au choix des coefficients de la matrice de la partie linéaire. Il est donc nécessaire de saturer deux octets pour obtenir une propriété exploitable dans un distingueur sur deux tours et ainsi de l'information sur la clé du troisième étage en testant les valeurs de clé pour laquelle la somme précédente est nulle. La valeur de clé qui apparaît le plus souvent est celle recherchée. Une telle attaque nécessite, en théorie, le chiffrement de (256)² clairs choisis. Pour être sûr d'éviter les fausses alarmes, il est plus prudent de répéter deux fois cette opération en changeant la valeur des 6 octets d'entrée constants. Dans leur article [1], A. Biryukov et A. Shamir ont donné une première formalisation de ce type de phénomènes, en étudiant les propriétés des schémas du type S₁A₁S₂A₂S₃ où S_i désigne un étage composé de k boîtes S qui prennent en entrée/sortie des mots de m bits et A_i représente une transformation affine inversible de vecteurs de longueur n=k ·m sur GF(2). On peut donc écrire : A_i(x) = L_i ·x ⊕B_i où L_i est une matrice n ×n de GF(2) et B_i un vecteur de taille n de GF(2). Les auteurs de [1] démontrent, dans ce cas, que la saturation d'un mot de taille m en entrée entraîne en sortie de l'application S₁A₁S₂A₂S₃ la propriété dite d'équilibre, à savoir que ⊕_i=0^2m−1S₃(A₂(S₂(A₁(S₁(((λ₁, λ₂, …, λ_k−1,i)))))) = 0 où les λ_j sont des constantes de GF(2^m). Cette propriété ne peut être appliquée à SAFER, car sa partie linéaire ne peut s'exprimer comme une transformation sur GF(2)ⁿ.

 

Références

[1]

A. Biryukov and A. Shamir. Structural cryptanalysis of sasas. In Advances in Cryptology -EUROCRYPT'2001, Innsbruck, Austria, pages 394-405. Lecture Notes in Computer Science 1807, Springer-Verlag, 2001.

[2]

J. Daemen, L.R. Knudsen, and V. Rijmen. The block cipher square. In Fast Software Encryption'97, Haifa, Israël, pages 149-165. Lectures Notes in Computer Science 1267, Springer-Verlag, 1997.

[3]

J. Daemen and V. Rijmen. Aes proposal: Rijndael. In The First Advanced Encryption Standard Candidate Conference. N.I.S.T., téléchargeable à l'adresse : www.esat.kuleuven.ac.be/ rijmen/rijndael/, 1998.

[4]

N. Ferguson, J. Kelsey, B. Schneier, M. Stay, D. Wagner, and D. Whiting. Improved cryptanalysis of rijndael. In Fast Software Encryption'00, New York, États Unis, pages 213-230. Lectures Notes in Computer Science 1978, Springer-Verlag, 2000.

[5]

L. Knudsen and D. Wagner. Integral cryptanalysis. In Fast Software Encryption'02, volume 2365 of Lectures Notes in Computer Science, pages 112-127. Springer-Verlag, 2002.

[6]

S. Lucks. The saturation attack - a bait for twofish. In Fast Software Encryption'01, volume 2355 of Lectures Notes in Computer Science. Springer-Verlag, 2001.