Cryptanalyse linéaire

La cryptanalyse linéaire est une technique inventée par Mitsuru Matsui, chercheur chez Mitsubishi. Elle date de 1993 et fut développée à l'origine pour casser l'algorithme de chiffrement symétrique DES. Ce type de cryptanalyse se base sur un concept antérieur à la découverte de Matsui : les expressions linéaires probabilistes. Ces dernières ont été étudiées par Henri Gilbert et Anne Tardy-Corfdir dans le cadre d'une attaque sur FEAL.

La cryptanalyse linéaire est plus efficace que la cryptanalyse différentielle mais moins pratique pour la simple et bonne raison que l'on part du principe que l'attaquant ne dispose pas de la boîte noire symbolisant l'algorithme de chiffrement et qu'il ne peut pas soumettre ses propres textes. Dans le cas de DES, cette attaque nécessitait à l'origine $247$ couples (tous chiffrés avec la même clé) que l'attaquant a pu récupérer par un moyen ou un autre. Par la suite, Matsui améliore son algorithme en 1994 et propose une solution avec $243$ couples. La complexité avec une bonne implémentation est toutefois inférieure et de l'ordre de $239$ opérations DES.

La cryptanalyse linéaire consiste à faire une approximation linéaire de l'algorithme de chiffrement en le simplifiant. En augmentant le nombre de couples disponibles, on améliore la précision de l'approximation et on peut en extraire la clé. Tous les nouveaux algorithmes de chiffrement doivent veiller à être résistants à ce type d'attaque. DES n'était pas conçu pour empêcher ce genre de méthode, les tables de substitution (S-Boxes) présentent en effet certaines propriétés linéaires alors qu'elles étaient justement prévues pour ajouter une non-linéarité à DES.

Elle a par la suite été appliquée avec succès sur plusieurs algorithmes comme LOKI, FEAL ou une version simplifiée de Serpent. Les algorithmes plus récents comme AES(Rijndael), IDEA et bien d'autres encore sont insensibles à une attaque linéaire. La complexité de l'attaque est dans ces cas largement supérieure à celle d'une recherche exhaustive.

Sommaire

1 Équations linéaires et substitutions
- 1.1 Exemple d'équations
2 Exemple
3 Voir aussi

Équations linéaires et substitutions

Soit par exemple une table de substitution avec 8 éléments, la fonction S est la fonction substitution. En effectuant S(X), on effectue une première substitution pour obtenir Y. Lors du déchiffrement, on appliquera l'opération inverse, c’est-à-dire S(Y)=S(S(X))=X.

X	Y
000	010
001	100
010	000
011	111
100	001
101	110
110	101
111	011

Une telle table est non-linéaire mais la combinaison de plusieurs substitutions et opérations peut annuler en partie la non-linéarité; c'est la faille recherchée par la cryptanalyse linéaire. Le terme linéaire se réfère en fait à une expression de la forme suivante (avec $\oplus$ l'opération binaire XOR) :

$X_1 \oplus X_2 \oplus X_3 \oplus \ldots \oplus X_N = Y_1 \oplus Y_2 \oplus Y_3 \oplus \ldots \oplus Y_N$

Le vecteur X est l'entrée et Y la sortie de la fonction que l'on essaie d'approcher avec cette équation booléenne. La variable $X i$ correspond à la valeur du i^ème bit de X.

Cette expression est équivalente à :

$X_1 \oplus X_2 \oplus X_3 \oplus \ldots \oplus X_N \oplus Y_1 \oplus Y_2 \oplus Y_3 \oplus \ldots \oplus Y_N= 0$

Exemple d'équations

La cryptanalyse linéaire vise à attribuer des vraisemblances aux équations possibles. Par exemple, considérons les deux équations suivantes :

$X_1 \oplus X_2 \oplus X_3 = Y_1 \oplus Y_2$
$X_2 \oplus X_3 = Y_3$

On applique maintenant ces équations sur notre table de substitution de la section précédente.

Première équation

X	Y	$X_1 \oplus X_2 \oplus X_3$	$Y_1 \oplus Y_2$
000	010	0	1
001	100	1	1
010	000	1	0
011	111	0	0
100	001	1	0
101	110	0	0
110	101	0	1
111	011	1	1

Deuxième équation

X	Y	$X_2 \oplus X_3$	$Y_3~$
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

Résultats

On voit que la première équation est satisfaite 4 fois sur 8 alors que l'équation (2) ne l'est que 2 sur 8. L'équation (1) est donc une meilleure approximation de la substitution mais ce n'est pas forcément la meilleure, un calcul sur toutes les équations possibles permet de répondre à cette question.

On répète ce type d'estimation sur diverses portions de l'algorithme de chiffrement, cette étape varie selon son architecture. Grâce à ces approximations, on tente de retrouver des portions des clés intermédiaires (les subkeys).

Exemple

Considérons maintenant un algorithme de chiffrement très simple qui prend 3 bits en entrée et fournit 3 bits chiffrés en sortie.

Notre algorithme de chiffrement

Notation

Soit $P~$ la donnée en clair de 3 bits. Soit $C~$ , le résultat final et chiffré de 3 bits. Soit quatre clés intermédiaires $K_1, K_2, K_3, K_4~$ tirées de la clé principale et utilisées pour les trois stages intermédiaires et le XOR final. Soit $S_i(x)~$ , la fonction "substitution" avec la table de substitution n°i. Soit $K_{i,j}~$ la notation pour le bit j de la clé i. Les trois tables sont similaires à celle décrite auparavant.

Chiffrement

La procédure de chiffrement s'effectue comme suit :

$A_1 = K_1 \oplus P$
$B_1 = S_1(A_1)~$
$A_2 = K_2 \oplus B_1$
$B_2 = S_2(A_2)~$
$A_3 = K_3 \oplus B_2$
$B_3 = S_3(A_3)~$
$C = K_4 \oplus B_3$

En résumé, on applique un XOR avec une clé intermédiaire, on substitue avec une table différente à chaque fois et on recommence.

Création de l'approximation linéaire

On considère maintenant deux approximations linéaires suivantes pour les deux premières tables de substitution. :

$S_1 : X_1 \oplus X_2 \oplus X_3 = Y_2$
$S_2 : X_2 = Y_1 \oplus Y_3$

Nous convenons, pour cet exemple, que la première table a une probabilité de 3/4 et la deuxième une probabilité de 2/7. Ces équations linéaires peuvent maintenant être incorporées dans la procédure de chiffrement.

Première étape du chiffrement

A l'origine, nous avons

$B_1 = S_1(A_1)~$

Avec l'approximation sur la première substitution S₁, on peut écrire :

$B_{1,2}= A_{1,1} \oplus A_{1,2} \oplus A_{1,3}$

Or $A_1~$ est équivalent à $K_1 \oplus P$ , nous remplaçons donc $A_1~$ :

$B_{1,2} = (K_{1,1} \oplus P_{1,1}) \oplus (K_{1,2} \oplus P_{1,2}) \oplus (K_{1,3} \oplus P_{1,3})$

Deuxième étape du chiffrement

L'étape suivante dans le chiffrement consiste à faire un XOR entre B₁ et la clé K₂. Nous intégrons directement ce résultat avec la dernière équation obtenue à l'étape précédente

$A_{2,2} = B_{1,2} \oplus K_{2,2}$

$A_{2,2} = \Big( (K_{1,1} \oplus P_{1,1}) \oplus (K_{1,2} \oplus P_{1,2}) \oplus (K_{1,3} \oplus P_{1,3})\Big ) \oplus K_{2,2}$

Troisième étape du chiffrement

A ce stade, nous avons l'équation linéaire suivante :

$A_{2,2} = \Big( (K_{1,1} \oplus P_{1,1}) \oplus (K_{1,2} \oplus P_{1,2}) \oplus (K_{1,3} \oplus P_{1,3}) \Big ) \oplus K_{2,2}$

Nous appliquons maintenant la 2^e substitution $S_2 : X_2 = Y_1 \oplus Y_3$ :

$A_{2,2} = B_{2,1} \oplus B_{2,3}$

En substituant :

$\Big( (K_{1,1} \oplus P_{1,1}) \oplus (K_{1,2} \oplus P_{1,2}) \oplus (K_{1,3} \oplus P_{1,3}) \Big ) \oplus K_{2,2} = B_{2,1} \oplus B_{2,3}$

Quatrième étape

La sortie de l'étape précédente est maintenant chiffrée avec la clé $K_3~$ donc $A_3 = B_2 \oplus K_3$ :

Ceci donne finalement :

$\Big( (K_{1,1} \oplus P_{1,1}) \oplus (K_{1,2} \oplus P_{1,2}) \oplus (K_{1,3} \oplus P_{1,3}) \Big) \oplus K_{2,2} = (A_{3,1} \oplus K_{3,1}) \oplus (A_{3,3} \oplus K_{3,3})$

Nous arrangeons cette équation pour regrouper les termes :

$(K_{1,1} \oplus K_{1,2} \oplus K_{1,3} \oplus K_{2,2} \oplus K_{3,1} \oplus K_{3,3}) \oplus (P_{1,1} \oplus P_{1,2} \oplus P_{1,3}) \oplus (A_{3,1}\oplus A_{3,3}) = 0$

De manière plus condensée :

$\Sigma K \oplus (P_{1,1} \oplus P_{1,2} \oplus P_{1,3}) \oplus (A_{3,1}\oplus A_{3,3}) = 0$

avec $\Sigma K = (K_{1,1} \oplus K_{1,2} \oplus K_{1,3} \oplus K_{2,2} \oplus K_{3,1} \oplus K_{3,3})$

Nous avons maintenant une approximation linéaire qui dépend de :

une partie des trois clés intermédiaires
le texte en clair
une partie de l'entrée de la dernière table de substitution

Par l'application du lemme Piling-Up de Matsui et en fixant $Σ K$ à 0 ou 1, nous pouvons découvrir la probabilité que cette équation soit valable. Nous avons deux approximations dont nous connaissons les probabilités (grâce à l'analyse des boîtes de substitution). Avec deux approximations, n= 2 :

$1/2 + 2^{n-1}(1/2 - 3/4)(1/2 - 2/7) \approx 0.607$

Notre approximation a environ 3 chances sur 5 d'être valable. En essayant d'améliorer cette probabilité, on affine l'approximation linéaire et on récupère de plus en plus d'informations sur l'algorithme. Pour cela, il est nécessaire de disposer d'un nombre de messages en clair et de leurs équivalents chiffrés. Les effets des boîtes de substitution une fois combinées étant difficiles à estimer, des données importantes sont à même d'améliorer le modèle.

Une étape cruciale dans la cryptanalyse linéaire est la récupération de la dernière clé, celle qui boucle le chiffrement après une dernière substitution.

Récupération des clés

Récupération de la clé en commençant par la fin et en confrontant les résultats à l'estimation linéaire

Nous avons sous la main une approximation des 3 premiers tours de notre algorithme de chiffrement mais il manque la clé du dernier tour, soit $K_4~$ dans notre cas. C'est ici qu'interviennent les messages chiffrés à notre disposition. Nous prenons un message et essayons de le déchiffrer en testant toutes les clés $K_4~$ possibles. On s'intéresse plus particulièrement aux résultats à la fin du chiffrement. Plus précisément, nous prenons un message chiffré $C~$ et effectuons un XOR avec la dernière clé $K_4~$ : $C \oplus K_4$ . Cela correspond à la sortie de la dernière table de substitution. Nous effectuons maintenant la substitution inverse, la table étant connue : $S_3^{-1}(C \oplus K_4)$ .

Or cette valeur correspond en fait au membre de gauche de notre équation linéaire. Nous avons ainsi : $S_3^{-1}(C \oplus K_4) = A_3$ . On peut donc avoir une estimation de la validité des clés testées en comparant la valeur exacte retournée par la substitution inverse et notre approximation linéaire sur tout ou une partie des bits. Avec un grand nombre de paires de messages, on peut rendre plus précise les estimations. Pour découvrir les autres clés intermédiaires, on attaque l'algorithme en remontant progressivement dans les tours jusqu'à arriver à la première clé.

Sur des chiffrements plus complexes comme DES, on ne s'intéresse qu'à une partie des sous-clés afin de diminuer la complexité de l'attaque. Une étude plus poussée permet de déterminer quels bits de la dernière sous-clé ont vraiment une influence sur l'approximation linéaire. Dans son exemple avec un DES de 8 tours, Matsui indique que, malgré la présence de la dernière clé (de 48 bits) dans l'équation, seuls 6 bits de cette dernière clé influencent le terme où elle apparaît.

Plusieurs autres techniques ont été développées pour améliorer les performances de cette cryptanalyse.

Voir aussi

Bibliographie

M. Matsui, Linear cryptanalysis method for DES cipher, Proc. Eurocrypt '93, volume 765 of LNCS, pages 386--397, Springer, 1993.

Liens externes

v · Fonctions de hachage cryptographiques
Algorithmes	APR1 · AR · Boognish · FFT-hash · HAS-160 · Haval · MD2 · MD4 · MD5 · MD6 · N-hash · PANAMA · RIPEMD · RIPEMD-128 · RIPEMD-160 · RIPEMD-256 · Famille SHA (SHA-0 · SHA-1 · SHA-224 · SHA-256 · SHA-384 · SHA-512) · Snefru · StepRightUp · Tiger · VSH · Whirlpool
Cryptanalyse	Paradoxe des anniversaires · Linéaire · Différentielle · Attaque par force brute · Effet avalanche · Pseudo-collision
Architecture	Remplissage · Fonction de compression · Construction de Merkle-Damgård · Construction de Miyaguchi-Preneel · Construction de Matyas-Meyer-Oseas · Construction de Davies-Meyer

v · Preuve de sécurité • Sécurité inconditionnelle • IND-CPA • IND-CCA • Kerckhoffs • Malléabilité • Sécurité calculatoire • Hypothèses calculatoires • Confusion et diffusion
Cryptanalyse de base	Biais statistique • Corrélation • Dictionnaire • Force brute • Fréquence • Indice de coïncidence • Interpolation • Mot probable
Cryptanalyse par canal auxiliaire	Acoustique • Consommation • Émanations EM • Faute • Sondage • Temporel
Cryptanalyse ciblée	Clé apparentée • Clé faible • EFF • Enigma • Glissement • Intégrale • Linéaire / Différentielle / Différentielle impossible / Différentielle-linéaire / Boomerang • Modes opératoires • Modulo n • Quadratique • Rectangle • Rencontre au milieu • Vigenère • χ²
Systèmes asymétriques	Clé apparentée • Clé faible • Homme au milieu • Sécurité sémantique
Fonctions de hachage	Effet avalanche • Linéaire / Différentielle • Paradoxe des anniversaires • Pseudo-collision
Autres	Anonymat • Confidentialité • Intégrité • Sécurité par l'obscurité

Portail de la cryptologie

Catégorie :

Cryptanalyse

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Cryptanalyse linéaire de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

Cryptanalyse Linéaire — La cryptanalyse linéaire est une technique inventée par Mitsuru Matsui, chercheur chez Mitsubishi. Elle date de 1993 et fut développée à l origine pour casser l algorithme de chiffrement symétrique DES. Ce type de cryptanalyse se base sur un… … Wikipédia en Français
Cryptanalyse lineaire — Cryptanalyse linéaire La cryptanalyse linéaire est une technique inventée par Mitsuru Matsui, chercheur chez Mitsubishi. Elle date de 1993 et fut développée à l origine pour casser l algorithme de chiffrement symétrique DES. Ce type de… … Wikipédia en Français
Cryptanalyse Différentielle-linéaire — Introduite par Martin Hellman et Susan K. Langford en 1994, la cryptanalyse différentielle linéaire combine la cryptanalyse différentielle avec la cryptanalyse linéaire. L attaque différentielle sert à produire une approximation linéaire de l… … Wikipédia en Français
Cryptanalyse differentielle-lineaire — Cryptanalyse différentielle linéaire Introduite par Martin Hellman et Susan K. Langford en 1994, la cryptanalyse différentielle linéaire combine la cryptanalyse différentielle avec la cryptanalyse linéaire. L attaque différentielle sert à… … Wikipédia en Français
Cryptanalyse Différentielle — La cryptanalyse différentielle est une méthode générique de cryptanalyse qui peut être appliquée aux algorithmes de chiffrement itératif par blocs, mais également aux algorithmes de chiffrement par flots et aux fonction de hachage. Dans son sens… … Wikipédia en Français
Cryptanalyse differentielle — Cryptanalyse différentielle La cryptanalyse différentielle est une méthode générique de cryptanalyse qui peut être appliquée aux algorithmes de chiffrement itératif par blocs, mais également aux algorithmes de chiffrement par flots et aux… … Wikipédia en Français
Cryptanalyse Différentielle Impossible — En cryptanalyse, la cryptanalyse différentielle impossible ou cryptanalyse par différentielles impossibles est une technique basée sur la cryptanalyse différentielle (1990), elle a été proposée en 1999 par Eli Biham, Adi Shamir et Alex Biryukov… … Wikipédia en Français
Cryptanalyse differentielle impossible — Cryptanalyse différentielle impossible En cryptanalyse, la cryptanalyse différentielle impossible ou cryptanalyse par différentielles impossibles est une technique basée sur la cryptanalyse différentielle (1990), elle a été proposée en 1999 par… … Wikipédia en Français
Cryptanalyse par différentielles impossibles — Cryptanalyse différentielle impossible En cryptanalyse, la cryptanalyse différentielle impossible ou cryptanalyse par différentielles impossibles est une technique basée sur la cryptanalyse différentielle (1990), elle a été proposée en 1999 par… … Wikipédia en Français
Cryptanalyse Χ² — Méthode de cryptanalyse statistique inventée par Serge Vaudenay et basée sur le test du χ². Elle est plus efficace que la cryptanalyse différentielle pour le même nombre de paires de messages en clair et chiffré. La cryptanalyse χ² permet de s… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Cryptanalyse linéaire

Sommaire