PICSI

Nous allons nous intéresser ici à l'exemple de la cryptanalyse linéaire sur 4 étages du DES [7] introduite par M. Matsui dans [5]. Cet exemple est largement emprunté à l'article de vulgarisation [1]. Un autre exemple est donné dans [3].

La cryptanalyse linéaire est une attaque à clairs connus qui cherche des relations linéaires entre des entrées et des sorties. Plus précisément, on cherche ici à lier un ensemble de bits du mot d'entrée i₁,i₂, …, i_u à un ensemble de bits du mot de sorties j₁, j₂, …, j_v vérifiant que la somme des i₁,i₂, …, i_u additionnés avec les j₁, j₂, …, j_v donne la même valeur pour la plupart des entrées possibles. Si on note x[i] le i-ème bit de l'entrée x et y[j] le j-ème bits de la sortie correspondante, on cherche donc des relation de la forme :

x[i1] ⊕x[i2] ⊕…x[iu] ⊕y[j1] ⊕y[j2]⊕…y[jv] = 0 ou 1

qui soit vrai pour la plupart des valeurs d'entrées x et pour toutes les valeurs de clé dont pourrait dépendre y. Ainsi, comme dans le cas de la cryptanalyse différentielle, il faut s'intéresser à la probabilité de passer la partie non linéaire du chiffrement c'est à dire la ou les boîte(s) S avec une telle relation linéaire qui permet de faire "diminuer" la non-linéarité de la boîte S. Afin de bien comprendre comment on calcule ces probabilités nous allons donner l'exemple d'un tel calcul tiré d'un exemple simple donné dans [8]. La boîte S utilisé prend trois bits en entrée et trois bits en sortie et est donnée par la table :

x	y
000	010
001	100
010	000
011	111
100	001
101	110
110	101
111	011

On s'intéresse donc à former des équations linéaires et ici, on va précisément s'intéresser à la relation x[1] ⊕x[2] = y[1]   (1), x[1] étant le bit de poids faible de x. On calcule donc pour combien de valeurs de x cette équation est vérifiée avec y=S(x). On obtient donc le tableau de distribution suivant :

x	y	x[1] ⊕x[2]	y[1]
000	010	0	0
001	100	1	0
010	000	1	0
011	111	0	1
100	001	0	1
101	110	1	0
110	101	1	1
111	011	0	1

Les valeurs en gras sont celles pour lesquelles l'équation (1) est bien vérifier. Ainsi dans 2 cas sur 8, l'égalité est vrai. Il faut comparer ce résultat au résultat moyen que donnerait une permutation aléatoire parfaite et qui aurait un comportement égal partout c'est à dire que le nombre de cas où cette équation serait vrai est 4 cas sur 8. Le biais obtenu pour l'équation (1) est donc Pr(x[1] ⊕x[2] = y[1]) = 2/8 − 4/8 = −2/8 = −1/4. On peut généraliser ce résultat particulier à toutes les équations linéaires possibles. Pour simplifier alors l'écriture du tableau on note a la valeur binaire de la partie de l'équation impliquant des x[i] : dès qu'un x[i] vaut 1, la valeur du bit correspondant dans a est passée à 1. On note de même cette valeur b pour les sorties y. Ainsi pour l'équation (1), x[1] et x[2] sont impliqués donc a=(011)_b = 3 et y[1] également donc b=(001)_b = 1. On peut donc construire la table générale qui donne toutes les probabilités de transition pour la boîte S (voir figure 1).

				b
a	0	1	2	3	4	5	6	7
0	4	0	0	0	0	0	0	0
1	0	0	2	-2	2	2	0	0
2	0	2	0	-2	0	-2	0	-2
3	-2	-2	-2	-2	1	-1	-1	-3
4	0	2	0	2	0	2	0	-2
5	-2	1	-2	-1	1	0	-1	0
6	-2	0	-1	-1	-1	-1	-4	-2
7	-3	-2	-4	-3	-2	-1	-3	-2

Figure 1: La table des distributions des relations linéaires pour la boîte S.
Comme ce sont des biais à la moyenne, il est normal d'obtenir des valeurs négatives dans certains cas. Pour obtenir la probabilité associée à la distribution, il suffit ici de diviser par le nombre de cas total (c'est à dire 8 ici).
Après avoir décrit cet exemple simple de calcul de probabilités de relation linéaire, revenons à présent au cas du DES à 4 étages. Comme dans le cas différentielle nous cherchons la meilleure relation linéaire sur un DES à trois étages. Comme décrit dans [5], l'une des meilleures approximation linéaire sur 3 étages du DES utilise la boîte S₅ donnée par la table suivante :

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	2	12	4	1	7	10	11	6	8	5	3	15	13	0	14	9
1	14	11	2	12	4	7	13	1	5	0	15	10	3	9	8	6
2	4	2	1	11	10	13	7	8	15	9	12	5	6	3	0	14
3	11	8	12	7	1	14	2	13	6	15	0	9	10	4	5	3

Nous rappelons ici le principe de lecture dans la boîte S₅. L'entrée sur 6 bits est découpée en deux morceaux, le premier et le dernier bit sont concaténés et forme un chiffre entre 0 et 3 qui donne l'indice ligne du tableau tandis que les quatre bits du milieu donnent l'indice de colonne. Ainsi le mot de 6 bits (27)_d=(011011)_b, la concaténation du premier et du dernier bit nous donne (01)_b=(1)_d, soit la deuxième ligne à lire dans la table tandis que les quatre bits du milieu sont égales à (1101)_b=(13)_d. L'image de 27 par la boîte S S₅ est donc 3. On cherche donc à calculer les valeurs de a et de b qui maximise la probabilité P(a,b) sachant que a peut prendre les valeurs de 0 à 63 (comme l'entrée x de la boîte S₅) et que b peut varier sur 4 bits donc de 0 à 15. Voici dans le tableau qui suit un morceau des distributions des relations linéaires pour la boîte S₅ (voir figure 2).

								b
a	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2	4	-2	2	-2	2	-4	0	4	0	2	-2	2	-2	0	-4
3	0	-2	6	-2	-2	4	-4	0	0	-2	6	-2	-2	4	-4
4	2	-2	0	0	2	-2	0	0	2	2	4	-4	-2	-2	0
5	2	2	-4	0	10	-6	-4	0	2	-10	0	4	-2	2	4
6	-2	-4	-6	-2	-4	2	0	0	-2	0	-2	-6	-8	2	0
7	2	0	2	-2	8	6	0	-4	6	0	-6	-2	0	-6	-4
8	0	2	6	0	0	-2	-6	-2	2	4	-12	2	6	-4	4
9	-4	6	-2	0	-4	-6	-6	6	-2	0	-4	2	-6	-8	-4
10	4	0	0	-2	-6	2	2	2	2	-2	2	4	-4	-4	0
11	4	4	4	6	2	-2	-2	-2	-2	-2	2	0	-8	-4	0
12	2	0	-2	0	2	4	10	-2	4	-2	-8	-2	4	-6	-4
13	6	0	2	0	-2	4	-10	-2	0	-2	4	-2	8	-6	0
14	-2	-2	0	-2	4	0	2	-2	0	4	2	-4	6	-2	-4
15	-2	-2	8	6	4	0	2	2	4	8	-2	8	-6	2	0
16	2	-2	0	0	-2	-6	-8	0	-2	-2	-4	0	2	10	-20
17	2	-2	0	4	2	-2	-4	4	2	2	0	-8	-6	2	4
18	-2	0	-2	2	-4	-2	-8	4	6	4	6	-2	4	-6	0
19	-6	0	2	-2	4	2	0	4	-6	4	2	-6	4	-2	0
20	4	-4	0	0	0	0	0	-4	-4	4	4	0	4	-4	0
21	4	0	-4	-4	4	-8	-8	0	0	-4	4	8	4	0	4
22	0	6	6	2	-2	4	0	4	0	6	2	2	2	0	0
23	4	-6	-2	6	-2	-4	4	4	-4	-6	2	-2	2	0	4
24	6	0	2	4	-10	-4	2	2	0	-2	0	2	4	-2	-4
25	2	4	-6	0	-2	4	-2	6	8	6	4	10	0	2	-4
26	2	2	-8	-2	4	0	2	-2	0	4	2	0	-2	-2	0
27	2	6	-4	-6	0	0	2	6	8	0	-2	-4	-6	-2	0
28	0	-2	2	4	0	-6	2	-2	6	-4	0	2	-2	0	0
29	4	-2	6	-8	0	-2	2	10	-2	-8	-8	2	2	0	4
30	-4	-8	0	-2	-2	-2	2	-2	2	-2	6	4	4	4	0
31	-4	8	-8	2	-6	-6	-2	-2	2	-2	-2	-8	0	0	-4
20	4	-4	0	0	0	0	0	-4	-4	4	4	0	4	-4	0
32	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Figure 2: La table des distributions des relations linéaires pour la boîte S₅.
Maintenant que nous avons construit la table de relation linéaire de la boîtes S₅ du DES dont une partie est décrite dans la figure 2, il faut à présent trouver une relation linéaire sur trois étages du DES afin de construire une attaque sur quatre étage par déchiffrement du dernier tour. Cette approximation linéaire doit être satisfaite avec une probabilité élevée. On recherche donc une équation linéaire qui est une bonne probabilité de se produire pour un tour du DES, le tour numéro i. On s'intéresse ici essentiellement à la partie droite de l'entrée notée R_i de 32 bits. On cherche donc une relation linéaire qui tient pour cette entrée avec une bonne probabilité. Après une étude plus poussée de la fonction d'étage, on se rend compte que (voir figure 0.1.1 ):

Figure 3: Approximation linéaire sur l'étage i du DES
Le bit numéro 17 de l'entrée R_i devient après passage dans la fonction E le bit numéro 26, qu'il reste toujours le bit numéro 26 après addition de la sous-clé de l'étage. Ce bit particulier du mot noté ici x_i rentre alors dans la boîte S S₅ et dans ce cas avec une probabilité égale à 3/16, on a la relation à travers S₅ : x_i[26] = S(x_i)[17] ⊕S(x_i)[17] ⊕S(x_i)[18] ⊕S(x_i)[19] ⊕S(x_i)[20]. Les bits influencés sont notés en rouge dans la figure 0.1.1. On peut donc écrire cette relation en fonction de l'entrée R_i et du 26-ème bit de la sous-clé K_i de la manière suivante :

xi[26] = Ri[26] ⊕Ki[26] = S(xi)[17] ⊕S(xi)[17]⊕S(xi)[18] ⊕S(xi)[19] ⊕S(xi)[20]

Cette relation se produit avec une probabilité de 3/16. Reste à passer la permutation P qui transforme ces bits en les bits 3, 8, 14 et 25. Le mot ainsi obtenu devient alors la partie droite de l'étage i+1. On obtient donc la relation suivante, qui se produit avec un probabilité 3/16 et qui lie les parties droite R_i et gauche L_i de l'entrée de l'étage i à la partie droite de l'entrée de l'étage i+1.

Ri[17] ⊕Ki[26] ⊕Li[3] ⊕Li[8] ⊕Li[14] ⊕Li[25] = Ri+1[3] ⊕Ri+1[8] ⊕Ri+1[14] ⊕Ri+1[25]

On écrit alors cette expression pour les tours numéro 1 et 3 (i=1 et i=3). Avec une probabilité 3/16, on a donc :

R1[17] ⊕K1[26] ⊕L1[3] ⊕L1[8] ⊕L1[14] ⊕L1[25] = R2[3] ⊕R2[8] ⊕R2[14] ⊕R2[25]

et

R3[17] ⊕K3[26] ⊕L3[3] ⊕L3[8] ⊕L3[14] ⊕L3[25] = R4[3] ⊕R4[8] ⊕R4[14] ⊕R4[25]

Or, dans le cas du DES et de tout schéma de Feistel, la partie droite R₂ de l'entrée du deuxième tour est égal à la partie gauche de l'entrée du troisième étage L₃. De même, la partie droite de l'entrée du troisième étage R₃ est égale à la partie gauche de l'entrée du quatrième étage L₄. En sommant les deux équations précédentes, on obtient donc :

R1[17] ⊕L4[17] ⊕L1[3] ⊕L1[8] ⊕L1[14] ⊕L1[25] ⊕R4[3] ⊕R4[8] ⊕R4[14] ⊕R4[25] = K1[26] ⊕K3[26]

Le résultat de cette expression est binaire, ainsi, l'égalité est vérifiée si les deux termes valent 0 mais également si ils valent 1. La probabilité d'obtenir une telle relation est donc égale à Pr = (3/16)² + (1−3/16)² ≈ 0.7. Nous avons donc obtenu une équation linéaire qui a une bonne probabilité de se produire et qui lie des bits du texte clair X=(L₁, R₁) à des bits du texte chiffré Y=L₄, R₄). Cette relation est égale au x-or de deux bits des sous-clés 1 et 3 : K₁[26] ⊕K₃[26]. On a ainsi construit ce que l'on appelle un distingueur sur trois étages du DES qui permet d'obtenir un bit d'information sur les valeurs des sous-clés. Pour retrouver la valeur de K₁[26] ⊕K₃[26], on chiffre un nombre N de textes clairs X₁, …,X_N et on récupère les chiffrés correspondants Y₁, …,Y_N. Puis on compte le nombre de couple qui vérifie la relation X_j[17] ⊕Y_j[17] ⊕X_j[3] ⊕X_j[8] ⊕X_j[14] ⊕X_j[25] ⊕Y_j[3] ⊕Y_j[8] ⊕Y_j[14] ⊕Y_j[25] = 0 pour tout j parcourant 1, …,N. Si le compteur ainsi obtenu dépasse [N/2], cela signifie que K₁[26] ⊕K₃[26]=0, si au contraire il est plus petit que [N/2] alors, K₁[26] ⊕K₃[26]=1. Si au lieu de tester 4 étages du DES, on avait testé une permutation aléatoire, la répartition calculée précédemment aurait dû être très proche de [N/2] alors que dans notre cas, on s'attend à ce que cette répartition possède un biais de l'ordre Pr ×N ou (1−Pr) ×N. Pour calculer le nombre N de messages à chiffrer pour détecter le biais, on prend en général N de l'ordre de c ×(Pr)⁻² où c est une constante en général égale à 8 ou 16. Dans notre cas, pour détecter le biais on peut prendre N compris entre 16 et 32. M. Matsui dans [5] a proposé une généralisation de cette attaque pour cryptanalyser le DES complet à 16 étages. On cherche alors une équation linéaire qui lie les entrées et les sorties de 15 étages du DES et qui soit vraie avec une probabilité élevée. La meilleure approximation proposée par Matsui tient avec une probabilité égale à 1/2 + 2⁻²² dans ce cas et elle permet d'attaquer le DES à l'aide de 2⁴³ couples de clairs/chiffrés. Cette attaque a été améliorée expérimentalement par P. Junod et S. Vaudenay (voir [4]) : si la complexité reste la même que celle de l'attaque de Matsui, à savoir 2⁴³ chiffrements DES, alors seulement 2^42.5 clairs connus suffisent à cette attaque. On peut également en utilisant 2⁴³ clairs connus obtenir une attaque de complexité 2³⁹ chiffrements DES.

 

Références

[1]

A. Canteaut. Cryptanalyse des chiffrements à clefs secrète par blocs. Misc, mars 2002, 2001.

[2]

A. Corfdir and H. Gilbert. A known plaintext attack of feal-4 and feal-6. In Advances in Cryptology -CRYPTO'91, Santa Barbara, Californie, États-Unis, pages 172-181. Lectures Notes in Computer Science 576, Springer-Verlag, 1991.

[3]

H. M. Heys. A tutorial on linear and differential cryptanalysis. Technical Report CORR 2001-17, 2001.

[4]

P. Junod. On the complexity of matsui's attack. In Selected Areas in Cryptography - SAC'01, Toronto, Canada, pages 199-211. Lecture Notes in Computer Science 2259, Springer-Verlag, 2001.

[5]

M. Matsui. Linear cryptanalysis method for des cipher. In Advances in Cryptology -EUROCRYPT'93, Lofthus, Norvége, pages 386-397. Lecture Notes in Computer Science 765, Springer-Verlag, 1993.

[6]

M. Matsui. The first experimental cryptanalysis of the data encryption standard. In Advances in Cryptology -CRYPTO'94, Santa Barbara, Californie, États-Unis, pages 1-11. Lecture Notes in Computer Science 839, Springer-Verlag, 1994.

[7]

National Bureau of Standards (États Unis). Data Encryption Standard. Federal Information Processing Standard, 1977. Publication 46.

[8]

Wikipédia. Cryptanalyse linéaire.