Criptoanàlisi lineal

De Viquipèdia
Dreceres ràpides: navegació, cerca

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[modifica | modifica el codi]

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 èssim 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[modifica | modifica el codi]

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ó[modifica | modifica el codi]

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ó[modifica | modifica el codi]

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[modifica | modifica el codi]

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[modifica | modifica el codi]

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ó[modifica | modifica el codi]

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 intermedies 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[modifica | modifica el codi]

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[modifica | modifica el codi]

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 reconeixem, 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[modifica | modifica el codi]

Al començament, es té

B_1 = S_1(A_1)~

Amb l'aproximació sobre la primera substitució S1, 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[modifica | modifica el codi]

L'etapa següent en el xifratge consisteix a fer un XOR entre B1 i la clau K2. 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[modifica | modifica el codi]

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[modifica | modifica el codi]

La sortida de l'etapa precedent és ara xifrada amb la clau K_3~ per tant A_3 = B_2 \oplus K_3:

Això dóna 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[modifica | modifica el codi]

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 del 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 intermedies, 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[modifica | modifica el codi]

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

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

Enllaços externs[modifica | modifica el codi]