Cryptanalyse linéaire

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

1. ${\displaystyle X_{1}\oplus X_{2}\oplus X_{3}=Y_{1}\oplus Y_{2}}$
2. ${\displaystyle 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

${\displaystyle X}$	${\displaystyle Y}$	${\displaystyle X_{1}\oplus X_{2}\oplus X_{3}}$	${\displaystyle 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

${\displaystyle X}$	${\displaystyle Y}$	${\displaystyle X_{2}\oplus X_{3}}$	${\displaystyle 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

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

Soit ${\displaystyle P~}$ la donnée en clair de 3 bits. Soit ${\displaystyle C~}$, le résultat final et chiffré de 3 bits. Soit quatre clés intermédiaires ${\displaystyle 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 ${\displaystyle S_{i}(x)~}$, la fonction "substitution" avec la table de substitution n°i. Soit ${\displaystyle K_{i,j}~}$ la notation pour le bit j de la clé i. Les trois tables sont similaires à celle décrite auparavant.

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

1. ${\displaystyle A_{1}=K_{1}\oplus P}$
2. ${\displaystyle B_{1}=S_{1}(A_{1})~}$
3. ${\displaystyle A_{2}=K_{2}\oplus B_{1}}$
4. ${\displaystyle B_{2}=S_{2}(A_{2})~}$
5. ${\displaystyle A_{3}=K_{3}\oplus B_{2}}$
6. ${\displaystyle B_{3}=S_{3}(A_{3})~}$
7. ${\displaystyle 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.

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

• ${\displaystyle S_{1}:X_{1}\oplus X_{2}\oplus X_{3}=Y_{2}}$
• ${\displaystyle 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.

À l'origine, nous avons ${\displaystyle B_{1}=S_{1}(A_{1})~}$.

Avec l'approximation sur la première substitution S₁, on peut écrire ${\displaystyle B_{1,2}=A_{1,1}\oplus A_{1,2}\oplus A_{1,3}}$.

Or ${\displaystyle A_{1}~}$ est équivalent à ${\displaystyle K_{1}\oplus P}$, nous remplaçons donc ${\displaystyle A_{1}~}$ : ${\displaystyle B_{1,2}=(K_{1,1}\oplus P_{1})\oplus (K_{1,2}\oplus P_{2})\oplus (K_{1,3}\oplus P_{3})}$.

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 : ${\displaystyle A_{2,2}=B_{1,2}\oplus K_{2,2}}$ soit ${\displaystyle A_{2,2}={\Big (}(K_{1,1}\oplus P_{1})\oplus (K_{1,2}\oplus P_{2})\oplus (K_{1,3}\oplus P_{3}){\Big )}\oplus K_{2,2}}$.

À ce stade, nous avons l'équation linéaire suivante : ${\displaystyle A_{2,2}={\Big (}(K_{1,1}\oplus P_{1})\oplus (K_{1,2}\oplus P_{2})\oplus (K_{1,3}\oplus P_{3}){\Big )}\oplus K_{2,2}}$.

Nous appliquons maintenant la 2^e substitution ${\displaystyle S_{2}:X_{2}=Y_{1}\oplus Y_{3}}$ : ${\displaystyle A_{2,2}=B_{2,1}\oplus B_{2,3}}$.

En substituant : ${\displaystyle {\Big (}(K_{1,1}\oplus P_{1})\oplus (K_{1,2}\oplus P_{2})\oplus (K_{1,3}\oplus P_{3}){\Big )}\oplus K_{2,2}=B_{2,1}\oplus B_{2,3}}$.

La sortie de l'étape précédente est maintenant chiffrée avec la clé ${\displaystyle K_{3}~}$ donc ${\displaystyle A_{3}=B_{2}\oplus K_{3}}$ , ${\displaystyle B_{2}=A_{3}\oplus K_{3}}$Ceci implique cette équation :

Ceci donne finalement : ${\displaystyle {\Big (}(K_{1,1}\oplus P_{1})\oplus (K_{1,2}\oplus P_{2})\oplus (K_{1,3}\oplus P_{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 : ${\displaystyle (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}\oplus P_{2}\oplus P_{3})\oplus (A_{3,1}\oplus A_{3,3})=0}$.

De manière plus condensée : ${\displaystyle \Sigma K\oplus (P_{1}\oplus P_{2}\oplus P_{3})\oplus (A_{3,1}\oplus A_{3,3})=0}$ avec ${\displaystyle \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 ${\displaystyle \Sigma 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 : ${\displaystyle 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 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 ${\displaystyle 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 ${\displaystyle 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é ${\displaystyle C~}$ et effectuons un XOR avec la dernière clé ${\displaystyle K_{4}~}$ : ${\displaystyle 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 : ${\displaystyle 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 : ${\displaystyle 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.

• [Baignères, Junod et Vaudenay 2004] (en) Thomas Baignères, Pascal Junod et Serge Vaudenay, « How Far Can We Go Beyond Linear Cryptanalysis? », Advances in Cryptology -ASIACRYPT 2004, Springer, lecture Notes in Computer Science, vol. 3329,‎ 2004, p. 432–450 (ISBN 978-3-540-23975-8, ISSN 0302-9743, DOI 10.1007/978-3-540-30539-2_31, lire en ligne [PDF]).
• [Biham 1995] (en) Eli Biham, « On Matsui’s linear cryptanalysis », Advances in Cryptology — EUROCRYPT'94, Springer, lecture Notes in Computer Science, vol. 950,‎ 1995, p. 341–355 (ISBN 978-3-540-60176-0, ISSN 0302-9743, DOI 10.1007/BFb0053449, lire en ligne [PDF]).
• [Collard, Standaert et Quisquater 2007] (en) Baudoin Collard, F. X. Standaert et Jean-Jacques Quisquater, « Improving the Time Complexity of Matsui’s Linear Cryptanalysis », information Security and Cryptology — ICISC 2007, Springer, lecture Notes in Computer Science, vol. 4817,‎ 2007, p. 77–88 (ISBN 978-3-540-76787-9, ISSN 0302-9743, DOI 10.1007/978-3-540-76788-6_7).

• [Matsui 1993] (en) Mitsuru Matsui, « Linear cryptanalysis method for DES cipher », Proc. Eurocrypt '93, Springer, lecture Notes in Computer Science, vol. 765,‎ 1993, p. 386–397 (ISBN 978-3-540-57600-6, ISSN 0302-9743, DOI 10.1007/3-540-48285-7_33, lire en ligne [PDF]).

• Cryptanalyse différentielle
• Attaque Boomerang
• Cryptanalyse χ²

• [Ritter 1997] (en) Terry Ritter, « Linear Cryptanalysis : A Literature Survey », une bibliographie consacrée à la cryptanalyse linéaire, 25 septembre 1997 (consulté le 27 octobre 2016).
• [Junod 2000] (en) Pascal Junod, « Linear cryptanalysis of DES » [PDF], 2000 (consulté le 27 octobre 2016).