Criptoanàlisi lineal

La Criptoanàlisi lineal és una tècnica inventada per Mitsuru Matsui, investigador de Mitsubishi. Data de 1993 i va ser desenvolupada inicialment per trencar l'algorisme de xifratge simètric DES. Aquest tipus de Criptoanàlisi es basa en un concepte anterior al descobriment de Matsui: les expressions lineals probabilistiques. Aquestes últimes han estat estudiades per Henri Gilbert i A. Tardy-Cordfir en el marc d'un atac sobre FEAL.

La Criptoanàlisi lineal és més eficaç que la Criptoanàlisi diferencial però menys pràctica per la senzilla i bona raó que es parteix del principi que l'agressor no disposa de la caixa negra simbolitzant l'algorisme de xifratge i que no pot sotmetre els seus propis texts. En el cas de DES, aquest atac requeria inicialment $2^{47}$ parelles (tots avaluats amb la mateixa clau) del que l'agressor ha pogut recuperar per un mitjà o un altre. Llavors, Matsui millora el seu algorisme el 1994 i proposa una solució amb $2^{43}$ parelles. La complexitat amb una bona implementació és tanmateix inferior i de l'ordre de $2^{39}$ operacions DES.

La Criptoanàlisi lineal consisteix a fer una aproximació lineal de l'algorisme de xifratge simplificant-lo. Augmentant el nombre de parelles disponibles, es millora la precisió de l'aproximació i se'n pot extreure la clau. Tots els nous algorismes de xifratge han de procurar ser resistents a aquest tipus d'atac. DES no estava dissenyat per impedir aquest tipus de mètode, les taules de substitució (caixes S) presenten en efecte certes propietats lineals mentre que estaven precisament previstes per afegir una no-linealitat a DES.

S'ha aplicat amb èxit sobre diversos algorismes com LOKI, FEAL o una versió simplificada de Serpent. Els algorismes més recents com AES (Rijndael) IDEA i d'altres encara són insensibles a un atac lineal. La complexitat de l'atac és en aquests casos àmpliament superior a la d'un cerca exhaustiva.

Equacions lineals i substitucions

Sigui per exemple una taula de substitució amb 8 elements, la funció S és la funció substitució. Efectuant S(X, s'efectua una primera substitució per obtenir Y. En el moment del desxiframent, s'aplicarà l'operació inversa, és a dir S(Y)=S(S(X))=X.

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

Tal taula és no lineal però la combinació de diverses substitucions i operacions pot anul·lar en part la no-linealitat; és la falla que cerca la criptoanàlisi lineal. El terme lineal es refereix de fet a una expressió de la forma següent (amb $\oplus$ l'operació binària 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}$

El vector X és l'entrada i Y la sortida de la funció que s'intenta aproximar amb aquesta equació booleana. La variable $X_{i}$ correspon al valor del i ^èsim bit de X.

Aquesta expressió és equivalent a:

$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'equacions

La Criptoanàlisi lineal apunta a atribuir versemblances a les equacions possibles. Per exemple, es consideren les dues equacions següents:

1. $X_{1}\oplus X_{2}\oplus X_{3}=Y_{1}\oplus Y_{2}$
2. $X_{2}\oplus X_{3}=Y_{3}$

S'apliquen ara aquestes equacions sobre la taula de substitució de la secció precedent.

Primera equació

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

Segona equació

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

Resultats

Es veu que la primera equació és satisfeta 4 vegades sobre 8 mentre que l'equació (2) no ho és més que 2 sobre 8. L'equació (1) és per tant una aproximació millor de la substitució però no és per força la millor, un càlcul sobre totes les equacions possibles permet respondre a aquesta qüestió.

Es repeteix aquest tipus d'estimació sobre diverses porcions de l'algorisme de xifratge, aquesta etapa varia segons la seva arquitectura. Gràcies a aquestes aproximacions, s'intenta trobar porcions de les claus intermediàries (les subkeys).

Exemple

Es considera ara un algorisme de xifratge molt senzill que pren 3 bits en entrada i subministra a 3 bits avaluats en sortida.

El nostre algorisme de xifratge

Notació

Sigui $P~$ la dada en clar de 3 bits. Sigui $C~$, el resultat final i xifrat de 3 bits. Siguin quatre claus intermediàries $K_{1},K_{2},K_{3},K_{4}~$ tretes de la clau principal i fetes servir per als tres etapes intermèdies i el XOR final. Sigui $S_{i}(x)~$, la funció "substitució" amb la taula de substitució n°i. Sigui $K_{i,j}~$ la notació per al bit j de la clau i. Les tres taules són similars a aquella descrita abans.

Xifratge

El procediment de xifratge s'efectua com segueix:

1. $A_{1}=K_{1}\oplus P$
2. $B_{1}=S_{1}(A_{1})~$
3. $A_{2}=K_{2}\oplus B_{1}$
4. $B_{2}=S_{2}(A_{2})~$
5. $A_{3}=K_{3}\oplus B_{2}$
6. $B_{3}=S_{3}(A_{3})~$
7. $C=K_{4}\oplus B_{3}$

En resum, s'aplica un XOR amb una clau intermediària, se substitueix amb una taula diferent cada vegada i es torna a començar.

Creació de l'aproximació lineal

Es consideren ara dues aproximacions lineals següents per a les dues primeres taules de substitució:

• $S_{1}:X_{1}\oplus X_{2}\oplus X_{3}=Y_{2}$
• $S_{2}:X_{2}=Y_{1}\oplus Y_{3}$

Es reconeix, per a aquest exemple, que la primera taula té una probabilitat de 3/4 i la segona una probabilitat de 2/7.

Aquestes equacions lineals poden ara ser incorporades en el procediment de xifratge.

Primera etapa del xifratge

Al començament, es té

$B_{1}=S_{1}(A_{1})~$

Amb l'aproximació sobre la primera substitució S₁, es pot escriure:

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

Ara bé $A_{1}~$ és equivalent a $K_{1}\oplus P$, es reemplacen per tant $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})$

Segona etapa del xifratge

L'etapa següent en el xifratge consisteix a fer un XOR entre B₁ i la clau K₂. S'integraa directament aquest resultat amb l'última equació obtinguda en l'etapa precedent

$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}$

Tercera etapa del xifratge

En aquest estadi, es té l'equació lineal següent:

$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}$

S'aplica ara la segona substitució $S_{2}:X_{2}=Y_{1}\oplus Y_{3}$:

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

Substituint:

${\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}$

Quarta etapa

La sortida de l'etapa precedent és ara xifrada amb la clau $K_{3}~$ per tant $A_{3}=B_{2}\oplus K_{3}$:

Això dona finalment:

${\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})$

S'arregla aquesta equació per reagrupar els 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 manera més condensada:

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

amb $\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})$

Ara es té una aproximació lineal que depèn de:

• una part de les tres claus intermediàries
• el text en clar
• una part de l'entrada de l'última taula de substitució

Per l'aplicació del lema Piling-Up de Matsui i fixant $\Sigma K$ a 0 o a 1, es pot descobrir la probabilitat que aquesta equació sigui vàlida. Es tenen dues aproximacions de les quals es coneixen les probabilitats (gràcies a l'anàlisi de les capses de substitució). Amb dues aproximacions n = 2:

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

L'aproximació té aproximadament 3 oportunitats sobre 5 de ser vàlida. Intentant millorar aquesta probabilitat, s'afina l'aproximació lineal i es recuperen cada vegada més informacions sobre l'algorisme. Per això, és necessari disposar d'un nombre de missatges en clar i els seus equivalents avaluats. Sent els efectes de les capses de substitució una vegada combinades difícils d'estimar, les dades importants són en condicions de millorar el model.

Una etapa fonamental en la Criptoanàlisi lineal és la recuperació de l'última clau, la que lliga el xifratge després d'una última substitució.

Recuperació de les claus

Recuperació de la clau començant pel final i confrontant els resultats a l'estimació lineal

Es té a mà una aproximació de les 3 primeres voltes de l'algorisme de xifratge però manca la clau de l'última volta, sigui $K_{4}~$ en el nostre cas. És aquí que intervenen els missatges avaluats a la nostra disposició. Es pren un missatge i s'intenta desxifrar-lo provant totes les claus $K_{4}~$ possibles. S'interessa més particularment pels resultats al final del xifratge. Més precisament, es pren un missatge avaluat $C~$ i s'efectua un XOR amb l'última clau $K_{4}~$: $C\oplus K_{4}$. Això correspon a la sortida de l'última taula de substitució. S'efectua ara la substitució inversa, la taula és coneguda: $S_{3}^{-1}(C\oplus K_{4})$.

Ara bé aquest valor correspon de fet al membre de l'esquerra de la nostra equació lineal. Es té així: $S_{3}^{-1}(C\oplus K_{4})=A_{3}$. Es pot per tant tenir una estimació de la validesa de les claus provades comparant el valor exacte tornat per la substitució inversa i l'aproximació lineal sobre tots o una part dels bits. Amb un gran nombre de parells de missatges, es pot assolir més precisió de les estimacions. Per descobrir les altres claus intermèdies, s'ataca l'algorisme pujant progressivament les voltes fins a arribar a la primera clau.

Sobre xifratges més complexos com DES, no s'interessa més que per una part de les subclaus per tal de disminuir la complexitat de l'atac. Un estudi més profund permet determinar quins bits de l'última subclau tenen verdaderament una influència sobre l'aproximació lineal. En el seu exemple amb un DES de 8 rondes, Matsui indica que, malgrat la presència de l'última clau (de 48 bits) en l'equació, sols 6 bits d'aquesta última clau influencien el terme on apareix.

S'han desenvolupat altres tècniques diverses per millorar les prestacions d'aquesta criptoanàlisi.

Referències i enllaços

Vegeu també

• Criptoanàlisi diferencial
• Atac Bumerang
• Criptoanàlisi χ²

Referències

• Sr. Matsui. Linear cryptanalysis method fur DES cipher. Proc. Eurocrypt '93, volum 765 of LNCS, pàgines 386--397. Springer, 1993.

Enllaços externs

• (anglès) Versió escanejada del article de Matsui Arxivat 2010-07-25 a Wayback Machine.
• (anglès) Una llista DES articles dedicats a la criptoanàlisi lineal
• (anglès) Tesi de Pascal Junod sobre la Criptoanàlisi lineal i una implementació ràpida per a DES
• (anglès) "How far can we go beyond linear cryptanalysis", Pascal Junod, Thomas Baignères et Serge Vaudenay
• (anglès) "On Matsui's linear cryptanalysis", anàlisi de l'atac per Eli Biham Arxivat 2007-08-24 a Wayback Machine.

• (anglès) "Improving the Time Complexity of Matsui's Linear Cryptanalysis", millora de la Criptoanàlisi lineal per mitjà de la FFT