Criptoanàlisi diferencial

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

El 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 en un conjunt de tècniques per a 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[modifica | modifica el codi]

El descobriment del criptoanàlisi diferencial s'atribueix generalment a Eli Biham i a Adi Shamir durant els últims anys de la dècada de 1980, quan publicaven 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 al 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 el criptoanàlisi diferencial era conegut per IBM des de 1974, i que defensar-lo del criptoanàlisi diferencial havien estat un objectiu de disseny.[1]

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

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 del 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 competitiu que gaudien els Estats Units altres països en el camp de la criptografia."[1] Dins d'Ibm, el criptoanàlisi diferencial es coneixia com el "T-attack",[1] o "Atac de les pessigolles".[3]

Mentre que Des estava dissenyat amb resistència al criptoanàlisi diferencial en ment, altres sistemes de xifratge contemporànies 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 servirnt 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[modifica | modifica el codi]

El criptoanàlisi diferencial normalment es un atac de textos clars escollits, el 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 247 textos clars escollits. Hi ha, tanmateix, ampliacions que permetrien un atac basat amb textos clars coneguts o fins i tot un atac només amb texts xifrats. El mètode bàsic fa servir parelles de texts 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 texts 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 degut a l'atzar. Variacions més sofisticades permeten que la clau es recuperi més ràpid 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 texts 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 de dites 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 text 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 altre, se suposa que és la clau correcte per 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. S'empra 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 el 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 demostrat matemàticament ser segurs contra l'atac.

Tipus especialitzats[modifica | modifica el codi]

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]

  1. 1,0 1,1 1,2 Coppersmith, Don. «The Data Encryption Standard (DES) and its strength against attacks» (PDF). IBM Journal of Research and Development, vol. 38, 3, May 1994, pàg. 243.
  2. Levy, Steven. "Crypto: How the Code Rebels Beat the Government — Saving Privacy in the Digital Age. Penguin Books, 2001, p. 55–56. ISBN 0-14-024432-8. 
  3. Flamarada Mat, sci.crypt, 15 d'agost de 1996, RE: L'enginyeria inversa i el Clíper s'escantellen"
  • 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)
  • 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[modifica | modifica el codi]