Criptoanàlisi diferencial

La criptoanàlisi diferencial és una forma general de criptoanàlisi aplicable principalment a xifratges per blocs, però també a xifratges de flux i a funcions hash criptogràfiques. En el sentit més ample, és l'estudi de com poden afectar les diferències en una entrada la diferència de resultats en la sortida. En termes d'un sistema de xifratge per blocs, es refereix a un conjunt de tècniques per resseguir les diferències a través de la xarxa de transformacions, descobrint on exhibeix el xifratge comportament no fortuït, i explotant tals propietats per recobrar la clau secreta.

Història

El descobriment de la criptoanàlisi diferencial s'atribueix generalment a Eli Biham i a Adi Shamir durant els últims anys de la dècada de 1980, quan van publicar diversos atacs en contra de sistemes de xifratge per boloc i funcions hash, incloent-hi una debilitat teòrica en el DES. Aquesta la va observar Bamford en el llibre The Puzzle Palace que DES és sorprenentment elàstic a la criptoanàlisi diferencial, en el sentit que modificacions fins i tot petites a l'algorisme el farien molt més vulnerable.

El 1994, un membre de l'equip IBM DES original, Don Coppersmith, publicava un article que manifestava que la criptoanàlisi diferencial era coneguda per IBM des de 1974, i que defensar-la de la criptoanàlisi diferencial havia estat un objectiu de disseny.

Segons l'autor Steven Levy, IBM havia descobert la criptoanàlisi diferencial pel seu compte, i el NSA era aparentment ben conscient de la tècnica.

IBM mantenia alguns secrets, com Coppersmith explica: "Després de discussions amb la NSA, es va decidir que revelar les consideracions de disseny revelaria la tècnica de la criptoanàlisi diferencial, una tècnica potent que es podria fer servir en contra de molts sistemes de xifratge. Això, a canvi, debilitaria l'avantatge competitiva de què gaudien els Estats Units respecte a altres països en el camp de la criptografia." Dins d'Ibm, la criptoanàlisi diferencial es coneixia com a "T-attack", o "Atac de les pessigolles".

Mentre que Des estava dissenyat amb resistència teninr present la criptoanàlisi diferencial, altres sistemes de xifratge contemporanis demostraven que eren vulnerables. Un primer objectiu per a l'atac era el sistema de xifratge per bloc FEAL. La versió proposada original amb quatre rondes (Feal-4) es pot trencar fent-ne servir només vuit textos clars escollits, i fins i tot una versió de 31 rondes de FEAL és susceptible de l'atac.

Mecànica de l'atac

La criptoanàlisi diferencial normalment és un atac de textos clars escollits, cosa que significa que l'atacant ha de ser capaç d'obtenir texts xifrats per a algun conjunt de texts clars triat. L'esquema pot criptoanalitzar DES amb èxit amb un esforç de l'ordre de 2⁴⁷ textos clars escollits. Hi ha, tanmateix, ampliacions que permetrien un atac basat en textos clars coneguts o fins i tot un atac només amb texts xifrats. El mètode bàsic fa servir parelles de textos clars relacionats per una diferència constant; La diferència es pot definir per uns quants camins, però l'O exclusiu és l'operació més habitual. L'atacant llavors calcula les diferències dels textos xifrats corresponents, esperant detectar patrons estadístics en la seva distribució. El parell que resulta de les diferències s'anomena diferencial. Les seves propietats estadístiques depenen de la natura de les Caixes-S que s'han fet servir per a l'encriptació, així l'atacant analitza diferencials $(\Delta _{X},\Delta _{Y})$, on $\Delta _{Y}=S(X)\oplus S(X\oplus \Delta _{X})$ (i $\oplus$ denota o exclusiu per a cada caixa S $S$. En l'atac bàsic s'espera que una diferència del text xifrat particular sigui especialment freqüent; d'aquesta manera, el sistema de xifratge es pot distingir d'un de degut a l'atzar. Variacions més sofisticades permeten que la clau es recuperi més ràpidament que en la recerca exhaustiva (atac per la força bruta).

En la forma més bàsica de recuperació de la clau a través de criptoanàlisi diferencial, un atacant demana els textos xifrats per a un nombre gran de parells de text clar, llavors suposa que el diferencial es conserva durant com a mínim r-1 rondes, on r és el nombre total de rondes. L'atacant llavors dedueix quines claus d'aquestes rondes (per a la ronda final) són possibles assumint la diferència entre els blocs abans de la ronda final. Quan les rondes de claus és curt, això es pot aconseguir simplement desxifrant exhaustivament els parells de textos xifrats una ronda amb cada clau possible. Quan s'ha trobat que una clau d'una ronda té una probabilitat considerablement més gran que qualsevol altra, se suposa que és la clau correcta per a aquella ronda.

Per a qualsevol sistema de xifratge particular, la diferència d'entrades s'ha de seleccionar curosament si es vol que l'atac tingui èxit. Es fa servir una anàlisi de les interioritats de l'algorisme; el mètode estàndard és localitzar un camí de diferències altament comprovables a través de les diverses etapes d'encriptació, anomenada característica diferencial.

Des que la criptoanàlisi diferencial va esdevenir de coneixement públic s'ha convertit en una preocupació bàsica dels dissenyadors de sistemes de xifratge. S'espera que els dissenys nous vagin acompanyats per proves que l'algorisme sigui resistent a aquest atac, i molts, incloent-hi l'AES, han de demostrar matemàticament ser segurs contra l'atac.

Tipus especialitzats

• Criptoanàlisi diferencial d'ordre superior
• Criptoanàlisi diferencial truncat
• Criptoanàlisi diferencial impossible
• Atac bumerang

Vegeu també

• Criptografia
• Criptoanàlisi lineal

Referències

• Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN 0-387-97930-1, ISBN 3-540-97930-1.
• Biham, E. and A. Shamir. (1990). Differential Cryptanalysis of DES-like Cryptosystems. Advances in Cryptology — CRYPTO '90. Springer-Verlag. 2–21.
• Eli Biham, Adi Shamir,"Differential Cryptanalysis of the Full 16-Round DES," CS 708, Proceedings of CRYPTO '92, Volume 740 of Lecture Notes in Computer Science, December 1991. (Postscript) Arxivat 2005-04-05 a Wayback Machine.
• Eli Biham, slides from "How to Make a Difference: Early History of Differential Cryptanalysis"PDF (850 KiB), March 16, 2006, FSE 2006, Graz, Austria

Enllaços externs

• A tutorial on differential (and linear) cryptanalysis
• Helger Lipmaa's links on differential cryptanalysis Arxivat 2009-01-29 a Wayback Machine.
• A description of the attack applied to DES