PICSI

Cryptanalyse différentielle

La cryptanalyse différentielle

La cryptanalyse différentielle a été introduite par E. Biham et A. Shamir en 1991 [1], c'est une attaque à message clair choisi applicable aux algorithmes de chiffrement par blocs itératifs. Le principe général de cette attaque consiste à considérer des couples de clairs X et X′ présentant une différence ∆X fixée et à étudier la propagation de cette différence initiale à travers le chiffrement. Les différences sont définies par une loi de groupe, en général le x-or bit à bit. Cette attaque utilise la faiblesse potentielle de la fonction itérée f dans une dérivation à l'ordre 1.

1  Un exemple simple pour bien comprendre

Tous les exemples présentés ici sont tirés du Stinson [5] (une bonne approche est également proposée dans [2]) et sont des cryptosystèmes qui ne sont pas sûrs mais qui servent à comprendre les attaques. On considère le chiffrement suivant (voir figure 1).

Figure 1: schéma à attaquer
C'est donc un algorithme de chiffrement par blocs qui prend en entrée des blocs de 16 bits sous des clés de 32 bits. Il est composé de 4 étages identiques et d'une transformation finale qui ne comporte pas de partie linéaire. Les boîtes S₁, S₂, S₃ et S₄ sont identiques et donnés par la table suivante (en héxadécimal) :

x	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
S(x)	e	4	d	1	2	f	b	8	3	a	6	c	5	9	0	7

La partie linéaire, quand à elle, est juste une permutation des bits du mot de 16 bits : le bit le plus à droite ne bouge pas, le deuxième bit devient le premier bit du deuxième mot de quatre bits, etc. comme décrit sur le schéma 1. Puis on fait un simple x-or entre le bloc de 16 bits et la sous-clés de 16 bits de l'étage. Ses sous-clés sont générés à partir de la clé maître K de 32 bits de la façon suivante : si on note K=(k₁, …, k₃₂) la représentation binaire de K alors, on a K_i = (k_4i−3, …, k_4i+12) pour i variant de 1 à 5. Ce keyschedule est on ne peut plus linéaire !
Maintenant que nous venons de construire un chiffrement par blocs, nous allons essayer de l'attaquer en utilisant la cryptanalyse différentielle. Pour cela, on cherche des textes clairs X et X′ qui sont tels que X ⊕X′ = ∆X soit une différence fixe qui est un bon comportement à travers notre chiffrement. Ces deux textes clairs vont produire deux chiffrés différents Y et Y′. Ensuite on chiffre un certain nombre m de clairs vérifiant (X,X′ = X ⊕∆X) et on récupère tous les chiffrés correspondants Y et Y′. On déchiffrera alors sur un étage ces chiffrés en faisant des hypothèses sur des bits de clés de K₅. Pour chaque valeur possible des bits de K₅, on déchiffre et on obtient une valeur f⁻¹_K5(Y) ⊕f⁻¹_K5(Y′) pour chaque couple (Y, Y′) obtenu. (On espère alors que cette valeur est égale à celle que l'on a calculé en théorie.) Si c'est le cas, on incrémente le compteur de la clé candidate de 1. La bonne clé (on l'espère) sera celle qui aura le compteur le plus haut (en fait, le plus proche de notre biais attendu, le reste se comportant, on espère, de manière aléatoire), c'est à dire celle pour laquelle l'attaque différentielle aura le mieux fonctionné.
Cette démarche est théorique, intéressons nous à présent à notre exemple. Le principe générale de la cryptanalyse différentielle est que le passage de la différence ∆X à travers la partie linéaire d'un chiffrement se fait avec probabilité 1 (mais par contre la différence est en principe diffusée par cette partie); (de même que le passage dans l'addition de la sous-clé de l'étage comme nous le verrons plus loin). Le problème essentiel reste donc le passage de la différence à travers les boîtes S. Précisons que cette boîte S prend en entrée/sortie des mots de 2ⁿ bits. Pour cela on a besoin de calculer les valeurs suivantes pour toutes les valeurs possibles de α et β : D(α, β) = # {S(X) ⊕S(X′) = β| X ⊕X′ = α, ∀X ∈ {0,1 }ⁿ } pour toutes les valeurs de X. C'est à dire qu'on calcule le nombre de X qui pour une différence d'entrée α vont donner une certaine différence β. Ces coefficients qui vont fournir un tableau pour toutes les valeurs α possibles et toutes les valeurs β possibles permettent ensuite de calculer la meilleure probabilité de passage à travers la boîte S. Dans notre exemple, avec la boîte S précédemment donnée, on regarde le cas particulier où α = (3)_h = (0011)_b afin de construire le coefficient correspondant. On parcours donc toutes les valeurs de X possibles :

X	X′=X ⊕α	Y=S(X)	Y′=S(X′)	β = Y⊕Y′
0	3	e	1	f
1	2	4	d	9
2	1	d	4	9
3	0	1	e	f
4	7	2	8	a
5	6	f	b	4
6	5	b	f	4
7	4	8	2	a
8	b	3	c	f
9	a	a	6	c
a	9	6	a	c
b	8	c	3	f
c	f	5	7	2
d	e	9	0	9
e	d	0	9	9
f	c	7	5	2

N'oubliez pas que dans la construction de cette table, l'opération élémentaire est le x-or, donc si X = (a)_h = (1010)_b alors X′ = X ⊕α = (a)_h ⊕(3)_h = (1010)_b ⊕(0011)_b = (1001)_b = (9)_h. Donc on obtient que si α = (3)_h, alors β vaut 2 dans 2 cas sur 16, β vaut 4 dans 2 cas sur 16, β vaut a dans 2 cas sur 16, β vaut c dans 2 cas sur 16. Mais aussi, β vaut 9 dans 4 cas sur 16 et β vaut f dans 4 cas sur 16. On généralise ce résultat en calculant les valeurs correspondantes pour tous les α possibles afin d'obtenir la table de distribution des différences D(α, β) (voir table 2).

	β
α	0 1 2 3 4 5 6 7 8 9 a b c d e f
0	16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1	0 0 0 2 0 0 0 2 0 2 4 0 4 2 0 0
2	0 0 0 2 0 6 2 2 0 2 0 0 0 0 2 0
3	0 0 2 0 2 0 0 0 0 4 2 0 2 0 0 4
4	0 0 0 2 0 0 6 0 0 2 0 4 2 0 0 0
5	0 4 0 0 0 2 2 0 0 0 4 0 2 0 0 2
6	0 0 0 4 0 4 0 0 0 0 0 0 2 2 2 2
7	0 0 2 2 2 0 2 0 0 2 2 0 0 0 0 4
8	0 0 0 0 0 0 2 2 0 0 0 4 0 4 2 2
9	0 2 0 0 2 0 0 4 2 0 2 2 2 0 0 0
a	0 2 2 0 0 0 0 0 6 0 0 2 0 0 4 0
b	0 0 8 0 0 2 0 2 0 0 0 0 0 2 0 2
c	0 2 0 0 2 2 2 0 0 0 0 2 0 6 0 0
d	0 4 0 0 0 0 0 4 2 0 2 0 2 0 2 0
e	0 0 2 4 2 0 0 0 6 0 0 0 0 0 2 0
f	0 2 0 0 6 0 0 0 0 4 0 2 0 0 2 0

Figure 2: La table des distributions des différences pour la boîte S.
La valeur correspondante du tableau D(α, β) nous permet de calculer la probabilité de passage à travers une boîte S. Cette probabilité se calcule comme une probabilité conditionnelle : P( β| α) = [D(α, β)/(2ⁿ)] où n est le nombre de bits d'entrée/sortie de la boîte S. Maintenant qu'on sait calculer cette probabilité reste à savoir comment se comporte notre différence lors du passage par la transformation linéaire et par l'addition de clé. Pour cette dernière les choses sont très simples : si d'un coté j'ai un premier texte au i-ème tour qui est X_i alors après addition de la sous-clé de l'étage i, il deviendra Y_i=X_i⊕K_i. De même le deuxième texte clair X′_i deviendra Y′_i=X′_i ⊕K_i. Donc la différence entre les deux sorties du tour i sera : Y_i ⊕Y′_i = X_i ⊕K_i ⊕X′_i ⊕K_i = X_i ⊕X′_i. Ainsi, la valeur de la différence ne sera pas modifiée pendant le passage dans l'addition de la sous-clé. Ceci est vrai pour tous les étages et dès que l'addition de clé et le calcul de la différence utilisent la même opération (ici le x-or). Reste le passage le plus délicat, celui à travers la partie linéaire. Pour cela, on cherche le meilleur chemin pour la différence à travers le chiffrement. C'est en fait celui qui traverse le moins de boîtes S pour pouvoir maximiser la probabilité de la différentielle. C'est également en général celui qui contient beaucoup de 0 dans la valeur de différence car dans ce cas, on traverse les boîtes S avec une probabilité 1 si la différence d'entrée/sortie vaut bien 0. Dans notre attaque, nous aurons besoin des différences suivantes données par la table 2 :

• Pour le premier étage, on traverse la boîte S₂ avec la probabilité P(β = (0010)_b | α = (1001)_b) = 1/2. Ce qui est une très bonne probabilité.
• Pour le deuxième étage, on traverse la boîte S₃ avec la probabilité P(β = (0110)_b | α = (0100)_b) = 3/8. La probabilité α d'entrée nous est directement donnée par le passage dans la transformation linéaire qui indique où se diffuse les bits (voir figure 3).
• Pour le troisième étage, on traverse la boîte S₂ avec la probabilité P(β = (0101)_b | α = (0010)_b) = 3/8 mais également la boîte S₃ avec une probabilité : P(β = (0101)_b | α = (0010)_b) = 3/8

Toutes ces différentielles peuvent se combiner pour former un chemin de différences comme illustré à la figure 3.


Figure 3: schéma général d'une cryptanalyse différentielle
Le chemin de la différence est ici représenté en rouge. Ainsi, on peut obtenir une probabilité sur tout le chemin de la différence sur les trois premiers étages du chiffrement égale à P(β = (0000   0101   0000   0101 )_b | α = (0000   1011   0000   0000)_b) = [1/2] ×[3/8]³ = [27/1024]. On obtient ainsi que la probabilité d'obtenir à l'entrée du dernier tour une différence égale à (0000   0101   0000   0101 )_b sachant que la différence d'entrée était (0000   1011   0000   0000)_b. On ne prend pas en compte ici le dernier étage car c'est celui qui va nous permettre de retrouver la bonne sous-clé K₅ en testant toutes les valeurs possibles de K₅ ou plus exactement d'une partie de celle-ci. Afin d'obtenir de l'information sur des bits de la clé K₅, on chiffre un certain nombre M de couples de textes clairs de la forme (x, x′ = x ⊕α) avec α = (0000   1011  0000   0000)_b et on récupère tous les couples de chiffrés correspondants (y,y′). On sait également que les différences qui respectent notre chemin de différence sont celles qui sont de la forme (0000   0101   0000   0101)_b à l'entrée du dernier tour. C'est donc le critère d'égalité à 0101 du deuxième et du quatrième mot de 4 bits que nous allons tester pour retrouver la bonne clé. On peut également remarquer en plus que le premier et le troisième mot de 4 bits de l'entrée du dernier étage doivent être égaux à 0, ce qui implique que y et y′ sont égaux à la sortie du dernier étage sur leur premier et leur troisième mot de 4 bits. Ceci nous donne un critère de test supplémentaire appelé une opération de filtrage. La bonne clé sera celle qui vérifie ces deux hypothèses et qui apparaît le plus grand nombre de fois pour l'ensemble des couples de chiffrés à tester. On utilise pour cela l'algorithme présenté à la figure 4. Ici, on ne teste pas toute la clé (ce qui reviendrait à faire une recherche exhaustive !) mais le deuxième mot de 4 bits L₂ de cette clé ainsi que le quatrième mot L₄. Notons également que des couples d'entrées/sorties (x, x′) et (y, y′) pour lesquels la différence attendue se produit sont appelés "des bonnes paires", il existe également des couples qui ne sont pas bons et qui produisent du bruit aléatoire.

Pour i variant de 1 à m faire

Choisir un couple (x, x ⊕α) et chiffrer ce couple pour obtenir (y, y′).

Fin Pour

Pour (L2, L4) variant de (0,0) à (f,f) faire

Compteur[L2,L4] reçoit 0

Fin Pour

Pour chacun des m couples (y,y′) faire

Si le 1er et le 3ème mot de y et y′ alors

Pour (L2, L4) variant de (0,0) à (f,f) faire

Déchiffrer y avec (L2, L4) pour obtenir u

Déchiffrer y′ avec (L2, L4) pour obtenir u′

Si le 2ème et le 4ème mot de u ⊕u′ valent 0101 alors

Compteur[L2,L4] reçoit Compteur[L2,L4] + 1

Fin Si

Fin Pour.

Fin Si

Fin Pour

Retourner Max(Compteur[L2,L4])

Figure 4: attaque différentielle La bonne clé est celle pour laquelle le plus grand nombre de couples de sorties (y, y′) vérifie la propriété différentielle, c'est donc celle qui a la valeur de compteur maximale. Il reste à calculer le nombre de couples M nécessaire pour détecter cette clé. En général on prend M = c*(P(β|α)⁻¹) où c est une petite constante. Dans l'exemple que nous venons de traiter, P(β| α)⁻¹ ≈ 38 et on détecte la clé pour M entre 50 et 100.

2  Une vision théorique

Introduisons tout d'abord les notations dont nous aurons besoin : on note X=X₀ et X′=X′₀ un couple de textes clairs et X₁,…, X_r−1, Y=X_r les chiffrés des étages intermédiaires (respectivement X′₁,…, X′_r−1, Y′=X′_r) en supposant que la fonction d'étage f prend en entrée/sortie des blocs de n bits. On note ∆X_i=X_i −X′_i les différences des étages intermédiaires et K₁, K₂,…, K_r−1, K_r les sous-clés des différents étages, supposées prises chacune dans un même espace noté K. Ces notations sont présentées à la figure 5

Figure 5: schéma général d'une cryptanalyse différentielle
On cherche donc à construire un distingueur à partir d'une relation liant ∆X₀ et généralement ∆X_(r−1) qui ait une probabilité de se produire aussi éloignée que possible de la probabilité uniforme (égale en général à 1/2). Cette relation doit dans la mesure du possible être indépendante ou peu dépendante des sous-clés de chaque étage. Pour calculer les probabilités liées à ces différences, on utilisera ici la définition proposée par Lai et Massey [4] et ne tient pas compte des valeurs des différences intermédiaires contrairement à celle proposée par Biham et Shamir dans [1]. On appelle différentielle sur i tours la donnée d'un couple (α, β) tel que

α = X0 − X′0 = ∆X0 et β = Xi −X′i = ∆Xi

On définit alors la probabilité conditionnelle associée appelée probabilité de la différentielle en supposant que le texte clair X₀ et les sous-clés k₁, … , k_i sont indépendantes et uniformément distribuées :

P(∆Xi = β| ∆X0 = α).

On suppose alors pour calculer cette probabilité différentielle que le texte clair X₀ et les sous-clés associées K₀,..., K_r sont indépendants et uniformément distribués et que cette probabilité est à peu près la même quelques soient les valeurs des sous-clés. On suppose également souvent qu'un algorithme de chiffrement possède la propriété de Markov c'est à dire que la probabilité de toute différentielle est indépendante du choix du texte clair. Dans la plupart des cas, cette propriété est vérifiée. Citons cependant le cas du DES qui ne vérifie pas cette propriété. Cette dernière propriété est la base du théorème suivant fondé sur les propriétés des chaînes de Markov [4] (à savoir que les distributions de probabilités de sortie d'un étage ne dépendent que des distributions de probabilités d'entrée de cet étage); ce qui permet de calculer réellement les probabilités mises en jeu par une différentielle. On peut donc ainsi sous les hypothèses précédentes calculer la probabilité d'une différentielle sur (r−1) étages est :

P(∆X(r−1) = α(r−1) | ∆X0 = α0) = ∑ α1  ∑ α2  … ∑ α(r−2)  r−1 ∏ i=1  p[αi−1, αi]

Une fois que l'on a obtenu une relation différentielle (α,β), notée R sur (r−1) tours qui a de bonnes chances de se produire, on peut créer le distingueur utilisant cette relation et tester les hypothèses de clé pour un algorithme à r étages :

Pour i variant de 1 à m faire

Choisir un couple (X0, X0 +α) et chiffrer ce couple.

Déterminer toutes les valeurs possibles k de Kr

pour lesquelles ∆X(r−1) = β.

compteur[k] reçoit compteur[k] + 1.

Fin Pour.

où le compteur compteur[k] est initialisé à 0. Précisons que dans de nombreux cas, on ne détermine pas la clé k_r en entier mais seulement un nombre l de bits de celle-ci déterminé par la relation R, ce qui peut éventuellement suffire pour une attaque complète si l'on peut terminer par une recherche exhaustive ou encore dans le cas où il existe plusieurs distingueurs qui déterminent plusieurs groupes différents de l bits de la clé. On peut parfois n'utiliser qu'un distingueur sur (r−2) étages (selon les cas, les r−2 premiers, les r−2 étages du milieu ou les r−2 derniers) si l'on parvient à effectuer une recherche exhaustive pertinente sur des bits des sous-clés des deux autres étages. Il reste alors à trouver une bonne approximation de la valeur m qui représente le nombre de couples de clairs à chiffrer. On distingue alors deux grands cas pour le calcul de m selon l'ordre de grandeur du rapport signal sur bruit S/N, ici égal à [(p−p^*)/(p^*)]. On souhaite que la probabilité de réussite de l'algorithme soit de plus de 99% et la probabilité de fausses alarmes (c'est à dire de retenir une mauvaise clé) soit très faible. En règle générale, pour la cryptanalyse différentielle, on a S/N >> 1 et donc m ≈ [4.6/p].

3  Une approche simplifiée

Pour permettre des calculs simples de différentielles et du nombre de clairs impliqués dans une attaque différentielle, on définit le coefficient DP^F où F est une fonction d'un ensemble E vers un ensemble E′ par :

DPFk(α, β) = Pr(Fk(X) − Fk(X′) = β| X − X′=α)

avec X, X′ appartenant à E et tirés au hasard, α appartenant à E et β appartenant à E′. La fonction F est paramétrée par la clé k, ce qui est normal dans le cas d'un chiffrement par blocs et donc, en général, on calcule la valeur de DP en faisant une moyenne sur toutes les clés possibles. Lorsque l'on souhaite monter une cryptanalyse différentielle sur la fonction F_k, considérée ici comme le chiffrement à attaquer, on crée un distingueur à partir d'une différentielle (α,β) pour des valeurs α et β maximisant le coefficient DP. La probabilité p que le phénomène attendu ici se produise pour la fonction F_k est :

p = DPF(α, β)

Une bonne approximation de m est alors

m ≈ 4.6 · 1 DPF(α,β) .

En pratique, si on considère que la fonction d'étage f est constituée d'une série de boîtes S S_i, d'une permutation linéaire et d'une addition de clé, on cherchera une propriété de la permutation linéaire pouvant être itérée sur les r−1 premiers étages. Le calcul de la probabilité des différentielles sur un étage ne se fera alors plus qu'au travers des boîtes S_i à l'aide des différents coefficients DP^S_i(α,β) pour des valeurs de α et β à déterminer. La probabilité de caractéristiques sur (r−1) étages est elle-même calculée comme le produit des différentes probabilités sur un étage, c'est à dire comme un produit des coefficients DP^S_i.

4  D'autres attaques inspirées de la cryptanalyse différentielle

Il existe également un certain nombre d'attaques inspirées de la cryptanalyse différentielle. On peut citer ici l'exemple de la cryptanalyse utilisant des différences impossibles. On cherche dans cette attaque à déterminer des différentielles qui n'ont aucune chance de se produire afin de construire un distingueur à partir de ce type de relation. Il en existe d'autres : la cryptanalyse différentielle d'ordre supérieur et la cryptanalyse différentielle tronquée.
Cryptanalyse Différentielle d'Ordre Supérieur   Cette attaque s'inspire largement de la cryptanalyse différentielle. Au lieu de considérer une dérivée d'ordre un selon une seule variable comme c'est le cas de la cryptanalyse différentielle, cette attaque s'intéresse à une dérivée d'ordre supérieur comme son nom l'indique. Cette cryptanalyse peut donc être considérée comme multivariable. Plus formellement et comme défini dans [3], si on a une fonction f : S → T, où (S, +) et (T, +) sont des groupes abéliens, la dérivée de f au point a est définie par ∆_a f(x) = f(x+a) − f(x) et la dérivée i-ème de f aux points a₁, …,a_i est définie de manière récursive par ∆⁽ⁱ⁾_{a1, …,ai}f(x) = ∆_ai(∆⁽ⁱ⁻¹⁾_{a1, …,ai−1}f(x)). Une différentielle d'ordre i est alors la donnée d'un i+1-uplet (α₁, …, α_i, β) tel que ∆⁽ⁱ⁾_{α1, …,αi} f(x) = β. Dans le cas d'une fonction f de GF(2)^m dans GF(2)ⁿ, il est nécessaire d'assurer l'indépendance linéaire des a₁, …,a_i afin d'éviter une dérivée d'ordre i nulle. Pour cela, on définit la différentielle d'ordre i de f sur le sous-espace vectoriel de GF(2)^m V de dimension i par

∆V f(x) = ⊕ ν ∈ V  f(x⊕ν)

L'existence de telles différentielles à travers le chiffrement permet de construire un distingueur même si des exemples d'une telle attaque sur des algorithmes de chiffrement sont peu nombreux. Précisons que ce type de cryptanalyse ne s'applique que lorsque le degré des expressions des valeurs intermédiaires est anormalement bas.

Cryptanalyse Utilisant des Différentielles Tronquées   Cette méthode consiste à considérer non pas des transitions entre des valeurs de différences entièrement spécifiées sous la forme de mots de un bloc mais à regarder des transitions entre des ensembles de valeurs de différences tels que ceux obtenus en fixant une partie des mots de différence et en laissant la valeur du reste de ces mots varier librement.

 

 

Références

[1]

E. Biham and A. Shamir. Differential cryptanalysis of des-like cryptosystems. Journal of Cryptology, 4, no. 1, 1991.

[2]

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

[3]

L. Knudsen. Truncated and higher order differentials. In Fast Software Encryption'95, Leuven, Belgium, pages 196-211. Lectures Notes in Computer Science 1008, Springer-Verlag, 1995.

[4]

X. Lai and J.L. Massey. Markov ciphers and differential cryptanalysis. In Advances in Cryptology -EUROCRYPT'91, Brighton, Royaume Uni, pages 17-38. Lecture Notes in Computer Science 547, Springer-Verlag, 1991.

[5]

Douglas R. Stinson. Cryptography: theory and practice. CRC Press, Boca Raton, Florida, 1995.