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 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 parelles. La complexitat amb una bona implementació és tanmateix inferior i de l'ordre de 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 l'operació binària XOR):
El vector X és l'entrada i Y la sortida de la funció que s'intenta aproximar amb aquesta equació booleana. La variable correspon al valor del i èsim bit de X.
Aquesta expressió és equivalent a:
Exemple d'equacions
La Criptoanàlisi lineal apunta a atribuir versemblances a les equacions possibles. Per exemple, es consideren les dues equacions següents:
S'apliquen ara aquestes equacions sobre la taula de substitució de la secció precedent.
Primera equació
X | Y | ||
---|---|---|---|
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 | ||
---|---|---|---|
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Linear_cryptanalysis_fake_cipher_dual.png/220px-Linear_cryptanalysis_fake_cipher_dual.png)
Notació
Sigui la dada en clar de 3 bits. Sigui , el resultat final i xifrat de 3 bits. Siguin quatre claus intermediàries tretes de la clau principal i fetes servir per als tres etapes intermèdies i el XOR final. Sigui , la funció "substitució" amb la taula de substitució n°i. Sigui 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:
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ó:
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é
Amb l'aproximació sobre la primera substitució S1, es pot escriure:
Ara bé és equivalent a , es reemplacen per tant :
Segona etapa del xifratge
L'etapa següent en el xifratge consisteix a fer un XOR entre B1 i la clau K₂. S'integraa directament aquest resultat amb l'última equació obtinguda en l'etapa precedent
Tercera etapa del xifratge
En aquest estadi, es té l'equació lineal següent:
S'aplica ara la segona substitució :
Substituint:
Quarta etapa
La sortida de l'etapa precedent és ara xifrada amb la clau per tant :
Això dona finalment:
S'arregla aquesta equació per reagrupar els termes:
De manera més condensada:
amb
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 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:
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Linear_cryptanalysis_fake_cipher_keyrecover.png/220px-Linear_cryptanalysis_fake_cipher_keyrecover.png)
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 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 possibles. S'interessa més particularment pels resultats al final del xifratge. Més precisament, es pren un missatge avaluat i s'efectua un XOR amb l'última clau : . Això correspon a la sortida de l'última taula de substitució. S'efectua ara la substitució inversa, la taula és coneguda: .
Ara bé aquest valor correspon de fet al membre de l'esquerra de la nostra equació lineal. Es té així: . 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.