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 ${\displaystyle 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 ${\displaystyle 2^{43}}$ parelles. La complexitat amb una bona implementació és tanmateix inferior i de l'ordre de ${\displaystyle 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 ${\displaystyle \oplus }$ l'operació binària XOR):

${\displaystyle 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 ${\displaystyle X_{i}}$ correspon al valor del i ^èsim bit de X.

Aquesta expressió és equivalent a:

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

Segona equació

X	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

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 ${\displaystyle P~}$ la dada en clar de 3 bits. Sigui ${\displaystyle C~}$, el resultat final i xifrat de 3 bits. Siguin quatre claus intermediàries ${\displaystyle 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 ${\displaystyle S_{i}(x)~}$, la funció "substitució" amb la taula de substitució n°i. Sigui ${\displaystyle 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. ${\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 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ó:

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

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

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

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

Ara bé ${\displaystyle A_{1}~}$ és equivalent a ${\displaystyle K_{1}\oplus P}$, es reemplacen per tant ${\displaystyle A_{1}~}$:

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

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

${\displaystyle 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:

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

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

Substituint:

${\displaystyle {\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 ${\displaystyle K_{3}~}$ per tant ${\displaystyle A_{3}=B_{2}\oplus K_{3}}$:

Això dona finalment:

${\displaystyle {\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:

${\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,1}\oplus P_{1,2}\oplus P_{1,3})\oplus (A_{3,1}\oplus A_{3,3})=0}$

De manera més condensada:

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

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

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 ${\displaystyle \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:

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle K_{4}~}$ possibles. S'interessa més particularment pels resultats al final del xifratge. Més precisament, es pren un missatge avaluat ${\displaystyle C~}$ i s'efectua un XOR amb l'última clau ${\displaystyle K_{4}~}$: ${\displaystyle 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: ${\displaystyle 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í: ${\displaystyle 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.