PICSI

Les principales attaques sur les algorithmes de chiffrement par bloc

Sommaire :

Informations sur le parcours

Titre :: Les principales attaques sur les algorithmes de chiffrement par bloc
Profils :: Enseignant & Lycéen, Ingénieur informatique, Enseignant-Chercheur, Etudiant
Thème :: Cryptographie à clé secrète
Finalité :: Théorique
Difficulté :: niveau 2
Auteur(s) :: Marine Minier
Mise à jour :: 02/01/2007 à 11h33

imprimer ce parcours

Règles du jeu de la cryptanalyse

Qu'est ce qu'une attaque ou les règles du jeu en cryptanalyse

Même si la cryptanalyse s'est développée parallèlement à la cryptographie et que la cryptanalyse moderne est née dans les années 70, il est nécessaire de préciser certains concepts spécifiques à cette discipline. Jusqu'à une époque assez récente, la sécurité d'un chiffrement reposait tout autant sur la non-divulgation de l'algorithme utilisé que sur la clé. Ce n'est plus le cas aujourd'hui et on attend d'un algorithme, conformément au principe de Kerckhoff, qu'il reste solide lorsque l'attaquant en connaît la spécification et ignore seulement la clé utilisée.

La cryptanalyse d'un système peut être alors soit partielle (l'attaquant découvre le texte clair correspondant à un ou plusieurs messages chiffrés interceptés), soit totale (l'attaquant peut déchiffrer tous les messages, par exemple en trouvant la clé). Il existe plusieurs types d'attaques selon les moyens dont dispose l'attaquant :

Attaques à chiffré connu : l'attaquant a seulement accès à des messages chiffrés.
Attaques à clair connu : l'attaquant dispose d'un ou plusieurs messages clairs et des chiffrés correspondants.
Attaques à clair choisi : l'attaquant choisit des clairs et peut obtenir les chiffrés correspondants.
Attaques à chiffré choisi : l'attaquant peut déchiffrer les messages de son choix.

L'attaque la plus simple et la plus brutale est la recherche exhaustive. L'attaquant teste l'ensemble des clés possibles sur un cryptogramme donné dont il est supposé connaître au moins partiellement le clair; il a découvert la bonne clé lorsque le déchiffrement redonne le clair attendu. La complexité d'une recherche exhaustive sur un algorithme de chiffrement par blocs dont la taille des clés est n bits est de l'ordre de 2ⁿ chiffrements. Il est donc nécessaire lorsque l'on souhaite créer un algorithme de chiffrement de prendre des clés suffisamment longues pour se prémunir contre ce type d'attaque. Malheureusement, ce n'est pas la seule condition à vérifier.

On suppose donc ici que l'on a le droit de monter des attaques à partir du moment où elles coûtent moins chères que la recherche exhaustive. En pratique, la plupart du temps, on réduit le nombre d'étages à attaquer afin de mettre en lumière une faiblesse particulière de l'algorithme.

Attaque par distingueur

Un peu de théorie...

Le principe général de la cryptanalyse repose sur la notion d'attaques par distingueur. Un distingueur A est en fait une machine de Turing probabiliste qui cherche par un jeu de questions/réponses à distinguer un système de chiffrement C d'un autre système de chiffrement souvent idéal noté C^*. On note p la probabilité que le distingueur, après qu'on lui ait fourni un certain nombre d'informations, renvoie la réponse "1" (c'est à dire que la suite de réponses fournies aux différentes requêtes permettent de dire que le chiffrement étudié est bien l'algorithme C). On note p^* la probabilité correspondante pour C^*. Il s'agit alors d'étudier le biais probabiliste qui existe éventuellement entre ces deux chiffrements, c'est ce qu'on nomme l'avantage du distingueur et qui correspond à la quantité Adv_A(C, C^*)=|p−p^*|.

Lors d'une attaque, on cherche donc un distingueur particulier souvent donné par des relations particulières liant les clairs et/ou les chiffrés de l'algorithme C qui fournit un avantage le plus grand possible, c'est à dire que l'on cherche des relations fournies par le chiffrement C qui ont une probabilité de se produire la plus éloignée possible de la probabilité uniforme. Ces relations peuvent être de tout type (dans le cas de la cryptanalyse différentielle, il s'agit d'un x-or entre deux blocs d'entrée dont on étudie les probabilités de transition pour un certain nombre de tours,...).

Plus le nombre d'étage impliqué dans la relation est grand et plus le biais est important, plus on pourra efficacement obtenir de l'information sur les sous-clés et la clé maître. Pour tester une clé (ou une partie seulement de cette clé selon le type de relation utilisé dans le distingueur), il suffit de regarder, sur un nombre suffisant de messages, si le biais obtenu réellement pour cette clé particulière après passage dans le distingueur est très proche du biais théorique. C'est ce qu'on appelle un test d'hypothèse. Celui-ci fait donc essentiellement appel à des tests statistiques où la probabilité de réussite, liée au biais impliqué par la relation dans le distingueur, permet de calculer la complexité et le nombre de textes nécessaires au succès d'une telle attaque.

Le principal but des attaques est de construire un distingueur à partir d'une relation portant sur les (r−2) étages du milieu ou sur les (r−1) premiers étages, puis, à partir de ce distingueur, de faire des tests d'hypothèse sur tout ou partie des première et/ou dernière clés.

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⁻¹_K₅(Y) ⊕f⁻¹_K₅(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).

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 (L₂, L₄) variant de (0,0) à (f,f) faire

Compteur[L₂,L₄] 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 (L₂, L₄) variant de (0,0) à (f,f) faire

Déchiffrer y avec (L₂, L₄) pour obtenir u

Déchiffrer y′ avec (L₂, L₄) pour obtenir u′

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

Compteur[L₂,L₄] reçoit Compteur[L₂,L₄] + 1

Fin Si

Fin Pour.

Fin Si

Fin Pour

Retourner Max(Compteur[L₂,L₄])

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

α = X₀ − X′₀ = ∆X₀ et β = X_i −X′_i = ∆X_i

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(∆X_i = β| ∆X₀ = α).

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) | ∆X₀ = α₀) =

∑
α₁

∑
α₂

…

∑
α_(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 (X₀, X₀ +α) et chiffrer ce couple.

Déterminer toutes les valeurs possibles k de K_r

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 :

DP^F_k(α, β) = Pr(F_k(X) − F_k(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 = DP^F(α, β)

Une bonne approximation de m est alors

m ≈ 4.6 ·

DP^F(α,β)

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 ∆⁽ⁱ⁾_{a₁, …,a_i}f(x) = ∆_{a_i}(∆⁽ⁱ⁻¹⁾_{a₁, …,a_i−1}f(x)). Une différentielle d'ordre i est alors la donnée d'un i+1-uplet (α₁, …, α_i, β) tel que ∆⁽ⁱ⁾_{α₁, …,α_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.

La Square attack: une attaque dédiée à l'AES

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) =

Y_0,0	Y_0,1	Y_0,2	y
Y_1,0	Y_1,1	Y_1,2	Y_1,3
Y_2,0	Y_2,1	Y_2,2	Y_2,3
Y_3,0	Y_3,1	Y_3,2	Y_3,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 K⁴₀

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

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

renvoyer K⁴₀

Sinon

refaire pour une autre valeur de K⁴₀

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^{2^m−1}S₃(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.

Attaques par interpolation

L'attaque par interpolation a été introduite par T. Jacobsen et L. Knudsen dans [1]. Cette attaque monovariable est applicable aux algorithmes dont les sorties peuvent être exprimées comme un polynôme de faible degré algébrique n en les entrées, ce qui peut par exemple se produire lorsque le degré de l'algorithme étudié est égal au produit des degrés algébriques des boîtes S de chaque étage.

La propriété d'interpolation ainsi obtenue peut être utilisée comme un distingueur à r étages dans une attaque contre un chiffrement à r+1 étages ou plus. Les attaques par interpolation peuvent être considérées comme un cas particulier monovariable des attaques par linéarisation, applicables lorsque le nombre de monômes des expressions multivariables des sorties en fonction des entrées est suffisamment faible.

Dans l'article initial, T. Jacobsen et L. Knudsen donnent l'exemple d'un chiffrement nommé PURE composé de r étages d'un schéma de Feistel, dont la fonction d'étage F_K est définie de GF(32) dans lui-même par : F_K(x)=f(x ⊕k) avec f(x)=x³ dans GF(32). Ce chiffrement est prouvé sûr contre les cryptanalyses différentielle et linéaire pour un nombre suffisant d'étages. En revanche, l'attaque par interpolation fonctionne pour un nombre d'étages allant jusqu'à 32.

Pour cette attaque par rencontre dans le milieu, on exprime tout d'abord la sortie de l'étage s que l'on notera z (s ≤ r−1) comme un polynôme g(x) fonction du texte clair x composé de au plus n₁ coefficients et dont on peut estimer le degré ici égal à au plus n₁−1 par multiplication du degré des boîtes S successivement traversées. On exprime ensuite cette même sortie z comme un polynôme h(y) en la sortie y du dernier étage composé de au plus n₂ coefficients. On a alors g(x)=h(y). Cette équation dont le nombre de coefficients inconnus est n=n₁+ n₂ permet de construire un système en au plus n−2 inconnues car on suppose que les termes constants valent 0 et que les coefficients de plus haut degré valent 1 afin d'obtenir une solution unique et non-trivial. Le nombre de paires de clairs/chiffrés nécessaires pour résoudre ce système est alors égal à n−2. On chiffre un texte clair de plus afin de vérifier que le système trouvé est le bon. Pour obtenir la valeur de y, on applique l'inverse de la fonction du r-ième étage au chiffré C pour chaque valeur des b bits de la clé k_r impliqués dans la relation entre C et y, et pour chacune de ces valeurs on calcule les coefficients du système. La bonne valeur est celle pour laquelle la vérification faite à partir de la paire supplémentaire de clair/chiffré fonctionne. La complexité d'une telle attaque est donc de 2^b−1(n−1) chiffrements pour (n−1) paires de clairs/chiffrés.

Dans le cas de l'algorithme PURE à 32 étages, on fixe la partie droite de 32 bits de l'entrée et on exprime la sortie de gauche du 22ème étage comme un polynôme de degré au plus 3²⁰ de la partie gauche de l'entrée. Puis, on exprime la sortie du 31ème étage comme un polynôme dont le nombre de coefficients est au plus de 3¹⁹. Le nombre de coefficients de l'équation obtenue par l'égalité des deux polynômes est d'au plus 2³². Cette attaque par interpolation permet de retrouver 32 bits d'information sur la clé du dernier étage. Elle utilise 2³² clairs choisis et sa complexité est de 2⁶³ calculs.

Références

[1]: T. Jacobsen and L.R. Knudsen. The interpolation attack on block ciphers. In Fast Software Encryption'97, Haifa, Israël, pages 28-40. Lectures Notes in Computer Science 1267, Springer-Verlag, 1997.

Attaques algébriques

Le principe général d'une attaque algébrique a été introduit dans [1]. Cette attaque est une attaque qui exploite la structure algébrique du chiffrement, plus précisément l'idée est d'exprimer les boîtes S utilisées à l'aide d'un ensemble de relations algébriques vraies si possible avec une probabilité 1 et non plus seulement d'en faire une approximation linéaire. Le passage à travers la partie linéaire du chiffrement ne modifie pas la structure générale de ces équations. L'addition de clés peut être prise en compte ou non dans la résolution du système.

Ainsi, un chiffrement par blocs donné peut être exprimer comme un système d'équations algébriques, en combinant les différentes équations de chaque composant du chiffrement. Si il est alors possible de résoudre ce système plus rapidement que la complexité donnée par la recherche exhaustive de la clé, on peut considérer ce chiffrement comme cassé.

Dans [1], les auteurs font remarquer que comme la seule opération non-linéaire de l'AES est l'inversion dans GF(2⁸) présente à chaque application d'une boîte S, on peut en déduire que sur GF(2⁸), xy=1, ∀x ≠ 0, si x représente l'entrée de la boîte S. L'opération suivante étant linéaire, on en déduit sur GF(2), une première série de 8 équations bilinéaires vraie avec probabilité 255/256 (le cas 0 étant pathologique). Ces équations sont données dans [1]. On peut construire d'autres équations à partir des relations suivantes dans GF(2⁸), vraies cette fois ci avec probabilité 1, yx² = x,y²x⁴ = x², …, x¹²⁸ = x y¹²⁸. On peut ainsi en déduire 23 équations linéairement indépendantes qui comportent 81 monômes. D'autres extensions a des équations quadratiques permettent d'obtenir 39 équations en 137 termes. Ainsi, on obtient dans le cas de l'AES sous des clés de 128 bits, un système d'environ 1600 variables et 8000 équations quadratiques.

Il s'agit à présent de résoudre le système obtenu. On peut ici utiliser plusieurs méthodes mais la plus commune reste celle comportant deux étapes : la linéarisation et l'utilisation d'un pivot de Gauss. La linéarisation consiste à remplacer chaque terme par une nouvelle variable, le système devient alors linéaire et on utilise un pivot de Gauss pour le résoudre. Les auteurs de [1] propose d'autres méthodes de résolution comme l'utilisation des algorithmes XL et XSL. Ils obtiennent ainsi une complexité de 2²³⁰ pour résoudre le système précédent dans le cas de l'AES 128. Cependant, le calcul de cette complexité et des complexités d'attaques algébriques reste sujet à discussion dans le monde de la cryptographie.

D'autres résultats amusants concernant ce type d'attaques sont apparus. Notamment, Ferguson, Schroeppel et Whiting [2] ont exprimé l'AES comme une seule équation de 250 termes.

Murphy et Robshaw dans [3] ont proposé le même type d'étude algébrique de l'AES mais cette fois sur le corps GF(2⁸).

Notons cependant que la découverte des attaques algébriques a surtout mis en péril, non pas les chiffrements par blocs (dont la partie non linéaire, si elle est bien choisie, permet de résister à ce type d'attaques) mais les chiffrements à flot et notamment ceux qui utilisent une fonction de remise à jour de l'état linéaire (en général un ou plusieurs LFSRs).

Références

[1]: Nicolas Courtois and Josef Pieprzyk. Cryptanalysis of block ciphers with overdefined systems of equations. In ASIACRYPT, volume 2501 of Lecture Notes in Computer Science, pages 267-287, 2002.
[2]: Niels Ferguson, Richard Schroeppel, and Doug Whiting. A simple algebraic representation of rijndael. In Selected Areas in Cryptography, volume 2259 of Lecture Notes in Computer Science, pages 103-111, 2001.
[3]: Sean Murphy and Matthew J. B. Robshaw. Essential algebraic structure within the aes. In CRYPTO, volume 2442 of Lecture Notes in Computer Science, pages 1-16, 2002.