DES

De Viquipèdia
Dreceres ràpides: navegació, cerca
Data Encryption Standard
La funció de Feistel (Funció F) del DES

La funció de Feistel (Funció F) del DES
General
Dissenyadors IBM
Data primera publicació 1975 (estàndard el gener de 1977)
Desenvolupat a partir de Lucifer
Successors Triple DES, G-DES, DES-X, LOKI89, ICE
Detall de xifratge
Mida de la clau 56 bits
Mida del bloc 64 bits
Estructura xarxa de Feistel
Rondes 16
Millor criptoanàlisi pública
Avui el DES es considera insegur perquè pot cedir davant d'atacs per la força bruta (vegeu EFF DES cracker). El 2004, el millor atac analític conegut era la criptoanàlisi lineal, que necessita 243 textos clars coneguts i té una complexitat temporal que oscil·la entre 239 i 243 (Junod, 2001); amb la hipòtesi que es tenen textos clars escollits, la complexitat es pot reduir a un factor de 4 (Knudsen i Mathiassen, 2000).

El Data Encryption Standard (DES, Estàndard de Xifratge de Dades) és un mètode de xifratge de dades. El 1976, la Federal Information Processing Standard (FIPS) el va seleccionar com a mètode oficial als Estats Units, i més tard el seu ús s'ha estès arreu del món. L'algorisme va ser motiu de controvèrsia per tres motius: perquè en el seu disseny hi havia elements classificats com a informació confidencial, perquè tenia una clau relativament curta, i perquè se sospitava que l'Agència de Seguretat Nacional (NSA) dels Estats Units tenia una porta falsa per desxifrar-lo. En conseqüència, el DES va ser sotmès a un estudi i una anàlisi acadèmica molt intensos que van impulsar el coneixement modern del xifratge per blocs i la seva criptoanàlisi.

Avui es considera que el DES no és segur per moltes aplicacions, principalment perquè la mida de la clau de 56 bits és massa petita; el gener de 1999, distributed.net i l'Electronic Frontier Foundation van col·laborar públicament per desxifrar una clau del DES, i ho van aconseguir en 22 hores i 15 minuts (vegeu la cronologia del DES). Alguns resultats analítics també demostren algunes febleses teòriques en el xifratge, tot i que a la pràctica no és factible d'aprofitar-les. Es creu que en la forma de Triple DES l'algorisme és pràcticament segur, tot i que en teoria els atacs continuen sent possibles. En els últims anys, aquest xifratge ha estat superat per l'Advanced Encryption Standard (AES) (Estàndard Avançat de Xifratge).

Alguna documentació distingeix entre el DES com a estàndard i l'algorisme DES, que es coneix com DEA (Data Encryption Algorithm, Algorisme de Xifratge de Dades). Quan se'n parla, les sigles DES es poden pronunciar o bé llegint les lletres de l'abreviatura (de, e, essa), o bé pronunciant l'acrònim com una única síl·laba (des).

Història del DES[modifica | modifica el codi]

Els orígens del DES es remunten als començaments de la dècada del 1970. El 1972, en acabar un estudi sobre les necessitats de seguretat informàtica, l'Oficina Nacional d'Estàndards dels Estats Units (NBS, National Bureau of Standards, que avui es diu NIST, National Institute of Standards and Technology, Institut Nacional d'Estàndards i Tecnologia) va detectar que calia un estàndard per totes les institucions governamentals per xifrar informació sensible no confidencial.[1] En conseqüència, el 15 de maig de 1973, després d'haver-ho consultat amb l'NSA i la NBS, va demanar propostes per un sistema de xifratge que havia de complir uns rigorosos criteris de disseny, però cap de les que es van presentar no va resultar adequada. El 27 d'agost de 1974 va tornar a demanar-ho, i aquest cop IBM va presentar un candidat que es va considerar acceptable: un sistema de xifratge desenvolupat durant el període 1973-1974 que es basava en un algorisme previ de Horst Feistel, el xifratge Lucifer. En l'equip d'IBM que va participar en el disseny i anàlisi del sistema de xifratge hi van participar Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith i Bryant Tuckerman.

Participació de l'NSA en el disseny[modifica | modifica el codi]

El 17 de març de 1975 la proposta del DES es va publicar al Registre Federal, i es va obrir un període per recollir aportacions externes. Durant els dos anys següents es van mantenir diverses sessions de treball obertes per discutir l'estàndard que s'havia proposat i es van rebre diverses crítiques, incloses algunes de pioners del xifratge de claus públiques com ara Martin Hellman i Whitfield Diffie, que es van queixar que l'NSA havia interferit de manera inadequada en punts com la mida de la clau, que es va escurçar, i les misterioses caixes-S. Se sospitava que, d'amagat, l'agència d'espionatge havia afeblit l'algorisme, de manera que ells —però ningú més— podrien llegir fàcilment els missatges xifrats. Alan Konheim (un dels dissenyadors del DES) va comentar: «Vam enviar les caixes-S a Washington. En tornar eren totes diferents.»[2] La comissió parlamentària d'Intel·ligència del Senat dels Estats Units va examinar l'actuació de l'NSA per determinar si havien actuat de manera inadequada; en el resum públic de les seves conclusions, aparegut el 1978, deia:

«En el desenvolupament del DES, l'NSA va convèncer IBM que amb una mida reduïda de la clau n'hi havia prou; els van ajudar indirectament en el desenvolupament de les estructures de les caixes-S, i van certificar que, segons el seu millor saber i entendre, l'algorisme DES definitiu estava lliure de qualsevol feblesa estadística o matemàtica.»[3]

Tanmateix, també s'afirmava que:

«La NSA no va manipular el disseny de l'algorisme de cap manera. IBM va inventar i va dissenyar l'algorisme, va prendre totes les decisions pertinents al respecte, i va estar d'acord que una clau amb aquella mida era més que adequada per totes les aplicacions comercials per les quals el DES estava pensat.»[4]

Un altre membre de l'equip del DES, Walter Tuchman, va dir: «Nosaltres vam desenvolupar l'algorisme DES sempre dins d'IBM, fent servir IBMeros. La NSA no va moure ni un sol fil!»[5]

Algunes de les sospites sobre les febleses amagades a les caixes–S es van dissipar el 1990, amb el descobriment i la publicació, fetes de manera independent per Eli Biham i Adi Shamir, de la criptoanàlisi diferencial, un mètode general per trencar els xifratges en bloc. Les caixes-S del DES eren molt més resistents als atacs que si s'haguessin triat a l'atzar, cosa que fa suposar que IBM ja coneixia aquesta tècnica abans, a la dècada dels 1970. En efecte, aquest era el cas: el 1994, Don Coppersmith va publicar els criteris de disseny originals de les caixes-S; segons Steven Levy, els investigadors del centre de recerca Watson d'IBM van descobrir els atacs per criptoanàlisi diferencial el 1974 i l'NSA els va demanar que mantinguessin la tècnica en secret.[6] Coppersmith explica la decisió d'IBM de mantenir el secret dient que ho van fer «perquè, utilitzada contra bona part dels esquemes de xifratge, la criptoanàlisi diferencial podia ser una eina molt potent, i hi havia la preocupació que si aquesta informació era de domini públic podia perjudicar la seguretat nacional». Levy cita Walter Tuchman: «Ens van demanar que poséssim a tots els nostres documents el segell de confidencial... De fet, donàvem un nombre a cada document i els tancàvem en caixes fortes, perquè estaven considerats secrets del govern dels Estats Units. Ens deien: "Feu això", i jo ho feia.»[7] El mateix Shamir va comentar: «Diria que, al contrari del que creu alguna gent, no hi ha cap prova que es manipulés el DES per afeblir-ne el disseny bàsic.»

L'altra crítica —que la clau era massa curta— es basava en l'argument de l'NSA per reduir la mida de la clau de 64 a 56 bits: l'agència d'espionatge deia que així els altres vuit bits podrien servir com a bits de paritat, cosa que semblava una mica sospitosa. És per això que es va estendre la creença que l'NSA actuava d'aquesta manera perquè creia que l'agència podria llançar un atac per la força bruta a una clau de 56 bits uns quants anys abans que la resta del món.

L'algorisme com a estàndard[modifica | modifica el codi]

Tot i les crítiques, el DES va ser aprovat com a estàndard federal el novembre de 1976, i es va publicar el 15 de gener de 1977 amb el nom de FIPS PUB 46 i l'autorització per utilitzar-lo en totes les dades no secretes. Posteriorment va ser confirmat com a estàndard els anys 1983, 1988 (revisat com a FIPS-46-1), 1993 (FIPS-46-2) i altre cop el 1999 (FIPS-46-3); en aquest últim cas es recomanava fer servir el Triple DES (vegeu més avall). El 26 de maig de 2002, després d'un concurs públic, finalment el DES va ser superat per l'Advanced Encryption Standard (AES, estàndard d'encriptació avançada). Vegeu procés d'estandardització de l'AES). El 19 de maig de 2005, el FIPS 46-3 es va retirar oficialment, però tot i així l'Institut Nacional d'Estàndards i Tecnologia americà té previst fer servir el Triple DES fins a l'any 2030 per protegir la informació governamental sensible.[8]

L'any 1994 es va publicar un altre atac teòric, la criptoanàlisi lineal, que tot i ser un atac per la força bruta es podia fer servir contra el DES amb força èxit, com es va demostrar el 1998; això va fer patent la necessitat d'utiltzar un nou algorisme per substituir-lo. Aquest i altres mètodes de criptoanàlisi s'expliquen amb més detall en aquest mateix article, més endavant.

En un altre ordre de coses, es considera que la introducció del DES va ser un catalitzador per l'estudi acadèmic de la criptografia, en particular dels mètodes per trencar xifratges en bloc. Segons un informe de l'Institut Nacional d'Estàndards i Tecnologia sobre el DES, vist en perspectiva

«... es pot dir que el DES va ser el "salt inicial" de l'estudi i desenvolupament no militars dels algorismes de xifratge. A la dècada del 1970 hi havia molt pocs criptògrafs, excepte els que treballaven a l'exèrcit i o als serveis secrets, i l'estudi acadèmic de la criptografia era molt reduït. Ara hi ha molts criptòlegs acadèmics actius, departaments de matemàtiques amb programes potents de criptografia, i consultors i empreses de seguretat dedicats a la informació comercial. S'ha forjat tota una generació de criptoanalistes analitzant (és a dir, intentant "trencar") l'algorisme DES. En paraules del criptògraf Bruce Schneier,[9] "el DES va fer més per impulsar el camp de la criptoanàlisi que cap altra cosa. Llavors hi havia un algorisme per estudiar." És sorprenent el gran nombre d'obres sobre criptografia de les dècades dels setanta i dels vuitanta que tracten sobre el DES, i des d'aleshores el DES és l'estàndard amb què s'ha comparat tot algorisme de clau simètrica.»[10]

Cronologia[modifica | modifica el codi]

Dia i mes Any Fet
15 de maig 1973 L'Oficina Nacional d'Estàndards dels Estats Units publica la primera petició per trobar un algorisme de xifratge estàndard.
27 d'agost 1974 L'Oficina Nacional d'Estàndards dels Estats Units publica la segona petició per trobar un algorisme de xifratge.
17 de març 1975 El Registre Federal publica el DES i s'obre el període per fer-hi aportacions públiques.
agost 1976 Primera sessió pública de treball sobre el DES.
setembre 1976 Segona sessió pública de treball sobre el DES.
novembre 1976 S'aprova el DES com a estàndard.
15 de gener 1977 Es publica el DES com un estàndard FIPS, el FIPS PUB 46.
1983 Es confirma per primer cop l'ús del DES.
1986 La cadena de televisió de pagament HBO comença a utilitzar el Videocipher II, un sistema de xifratge de televisió per satèl·lit basat en el DES.
22 de gener 1988 Es torna a confirmar el DES per segona vegada com a FIPS 46-1, superant el FIPS PUB 46.
juliol 1990 Biham i Shamir redescobreixen la criptoanàlisi diferencial, i l'apliquen a un criptosistema de tipus DES de 15 voltes.
1992 Biham i Shamir publiquen el primer atac teòric més senzill que un atac per la força bruta: la criptoanàlisi diferencial. Tot i així, per fer aquest atac es necessita la poc realista quantitat de 247 textos clars escollits.
30 de desembre 1993 Es confirma per tercer cop el DES com a estàndard, aquesta vegada com a FIPS 46-2.
1994 Es fa la primera criptoanàlisi experimental del DES aplicant la criptoanàlisi lineal.[11]
juny 1997 El projecte DESCHALL desxifra per primer cop en públic un missatge xifrat amb el DES.
juliol 1998 El DES cracker de l'EFF desxifra una clau DES en 56 hores.
gener 1999 Junts, Deep Crack i distributed.net desxifren una clau DES en 22 hores i 15 minuts.
25 d'octubre 1999 Es confirma per quart cop el DES com a FIPS 46-3, especificant que s'ha d'utilitzar preferentment el Triple DES. El DES simple es permet només en sistemes antics.
26 de novembre 2001 Es publica l'Advanced Encryption Standard com a FIPS 197.
26 de maig 2002 L'estàndard AES esdevé efectiu.
26 de juliol 2004 El Registre Federal rep la proposta de retirar el FIPS 46-3 i un parell d'estàndards relacionats.[12]
9 de maig 2005 L'Oficina Nacional d'Estàndards dels Estats Units retira el FIPS 46-3.[13]
15 de març 2007 La màquina paral·lela basada en l'FPGA COPACOBANA de la Universitat de Bochum i Kiel, Alemanya, desxifra el DES en 6,4 dies amb un cos de maquinari de deu mil dòlars.
Figura 1. Estructura general de Feistel del DES

Algorismes alternatius[modifica | modifica el codi]

Les preocupacions sobre la seguretat i el fet que el DES sigui relativament lent a l'hora d'operar amb programari van fer que des del final de la dècada dels vuitanta diversos investigadors proposessin una àmplia varietat de dissenys alternatius de xifratge en bloc; és el cas d'algorismes com l'RC5, el Blowfish, l'IDEA, el NewDES, el SAFER, el CAST5 i el FEAL. La majoria d'aquests dissenys conserven el bloc de 64 bits del DES i podrien actuar com a peces de recanvi, tot i que normalment fan servir una clau de 64 o de 128 bits. A l'URSS es va presentar l'algorisme GOST 28147-89, amb una mida de bloc de 64 bits i una clau de 256 bits, que més endavant es faria servir a Rússia.

El mateix DES es pot adaptar i reutilitzar en un esquema més segur. Molts antics usuaris del DES ara fan servir el Triple DES (TDES), que va ser descrit i analitzat per un dels inventors del DES;[14] implica aplicar el DES tres cops amb dues (2TDES) o tres (3TDES) claus diferents. Es considera que el Triple DES ofereix una seguretat adequada, però és força lent. Una alternativa computacionalment menys costosa és el DES-X, que augmenta la mida de la clau fent una operació XOR amb material extra per la clau abans i després del DES. El GDES és una variant del DES que es va proposar com a manera d'accelerar el xifratge, però s'ha demostrat que es pot desxifrar amb la criptoanàlisi diferencial.

El 2001, a través d'un concurs internacional, l'Institut Nacional d'Estàndards i Tecnologia va escollir un nou algorisme per substituir el DES: l'AES (Advanced Encryption Standard), que en un primer moment es deia Rijndael. Altres finalistes del concurs van ser l'RC6, el Serpent, el MARS i el Twofish.

Descripció[modifica | modifica el codi]

El DES és el xifratge per bloc arquetípic: un algorisme que agafa una cadena de bits de text clar amb una longitud fixa i que, a través d'una sèrie d'operacions complicades, la transforma en un altre text xifrat de la mateixa longitud. En el cas del DES, la mida del bloc és de 64 bits. El DES també fa servir una clau per personalitzar la transformació, de manera que, en teoria, només poden desxifrar l'algorisme les persones que coneixen la clau concreta que s'ha fet servir per al xifratge. La clau aparentment és de 64 bits, però de fet l'algorisme en fa servir només 56. Els altres vuit bits només s'utilitzen per verificar la paritat i després es descarten. Per tant, la longitud efectiva de la clau és de 56 bits, i aquesta és la manera més habitual de referir-s'hi.

Com passa amb els altres xifratges per bloc, el DES en si mateix no és un sistema de xifratge segur, perquè cal que l'emissor i el receptor comparteixin una mateixa clau i el sistema no garanteix un mètode segur per enviar-la; per això s'ha de fer servir en un mode d'operació. El FIPS-81 especifica diversos modes per utilitzar amb el DES.[15] El FIPS-74 conté comentaris addicionals per la utilització del DES.[16]

Estructura general[modifica | modifica el codi]

L'estructura general de l'algorisme es presenta a la Figura 1. Hi ha setze etapes de processament idèntiques, que es diuen rondes, i una permutació inicial i una altra de final anomenades IP i FP, que són inverses (la FP «desfà» la IP, i a l'inrevés). Les permutacions IP i FP gairebé no tenen significat criptogràfic, però segurament es van incloure per facilitar la càrrega i descàrrega de blocs al maquinari dels anys setanta, i per fer que el DES anés més lent si s'executava per programari.


Abans de començar les rondes principals, el bloc es divideix en dues meitats de 32 bits cada una i es processen de forma alternativa. D'aquest entrecreuament se'n diu xifratge de Feistel. L'estructura de Feistel garanteix que els processos de xifratge i desxifratge siguin molt similars; l'única diferència és que en el desxifratge les claus s'apliquen en ordre invers, però la resta de l'algorisme és idèntic. Això en simplifica força la implementació, en particular en maquinari, ja que no calen algorismes separats de xifratge i desxifratge.

El símbol vermell \oplus denota l'operació O exclusiu (XOR). La funció-F barreja la meitat d'un bloc amb una part de la clau. Llavors la sortida de la funció es combina amb l'altra meitat del bloc i s'intercanvien les meitats abans de la ronda següent. Finalment, en l'última ronda no s'intercanvien les meitats; aquesta característica fa que el xifratge i el desxifratge siguin processos similars.

Figura 2. La funció de Feistel (funció-F) del DES

La funció (F) de Feistel[modifica | modifica el codi]

La funció-F, que es descriu a la Figura 2, treballa cada vegada sobre la meitat d'un bloc (32 bits) i té quatre etapes:

  1. Expansió: els 32 bits del mig bloc s'expandeixen a 48 bits fent servir la permutació d'expansió (representada en el diagrama amb la lletra E) a base de duplicar alguns dels bits.
  2. Barreja amb la clau: el resultat es combina amb una subclau fent servir l'operació XOR. De la clau principal se'n dedueixen setze subclaus de 48 bits —una per cada ronda—; per això es fa servir la programació de claus, que es descriu més avall.
  3. Substitució: després de barrejar-hi la subclau, el bloc es divideix en vuit bocins de sis bits i després es processa amb les caixes-S o caixes de substitució. Cada una de les vuit caixes-S substitueix els seus sis bits d'entrada per quatre bits de sortida seguint una transformació no lineal que ve donada per una taula indexada. Les caixes-S són el nucli de seguretat del DES; si no hi fossin, el xifratge seria lineal i molt fàcil d'atacar.
  4. Permutació: finalment, les trenta-dues sortides de les caixes-S es reordenen seguint una permutació fixa, la caixa-P.

L'alternança entre les substitucions de les caixes-S i les permutacions de la caixa-P és el que s'anomena confusió i difusió, un concepte identificat per Claude Shannon a la dècada del 1940 com una condició necessària per un xifratge segur i pràctic.




Figura 3 — La programació de claus del DES

Programació de claus[modifica | modifica el codi]

La Figura 3 il·lustra la programació de claus per al xifratge, l'algorisme que genera les subclaus. Al començament, se seleccionen 56 bits entre els 64 que té la clau inicialment. Això es fa amb el que s'anomena Permuted Choice 1 (PC-1, Selecció Permutada 1), i els vuit bits restants o bé es descarten o bé es fan servir com a comprovació de paritat. Llavors els 56 bits es divideixen en dues meitats de 28 bits; a partir d'aquí cada meitat es tracta per separat. En les successives rondes s'aplica a les dues meitats una rotació cap a l'esquerra d'un o dos bits (d'acord amb la taula de rotacions, que indica a cada ronda li correspon rotar un bit o dos), i llavors se seleccionen els 48 bits de la subclau amb la Permuted Choice 2 (PC-2, Selecció Permutada 2): 24 bits procedeixen de la meitat esquerra, i 24, de la dreta. Les rotacions (que al diagrama es marquen amb el símbol «<<<») provoquen que a cada subclau es faci servir un conjunt diferent de bits; cada bit s'empra aproximadament en 14 de les 16 subclaus.

Per al desxifratge la programació de claus és similar: les subclaus vénen en l'ordre invers del xifratge. A banda d'això, el procés és el mateix que per al xifratge.


Seguretat i criptoanàlisi[modifica | modifica el codi]

Tot i que s'ha publicat més informació sobre la criptoanàlisi del DES que sobre cap altre xifrat de bloc, encara avui l'atac més pràctic continua sent la força bruta. Es coneixen diverses propietats criptoanalítiques menors, i en principi són possibles tres tipus d'atacs, però, tot i que requereixen menys complexitat teòrica que un atac per la força bruta, per poder-los dur a la practica requereixen una quantitat irreal de textos clars coneguts o escollits. Per això, a la pràctica aquests mètodes no es tenen en compte.

Atac per la força bruta[modifica | modifica el codi]

Per qualsevol tipus de xifratge, el mètode d'atac més simple és l'atac per la força bruta, és a dir, provar totes les claus possibles una per una. La longitud de la clau determina el nombre possible de claus, i per tant les possibilitats d'èxit de l'atac. En el cas del DES, ja des del començament es van plantejar dubtes perquè la seva clau era massa curta, fins i tot abans de ser adoptat com a estàndard, i de fet va ser això, més que la criptoanàlisi teòrica, el que va fer necessari substituir-lo. Se sap que l'NSA va animar o fins i tot va persuadir IBM perquè reduís la mida de clau de 128 bits a 64, i d'allà a 56 bits; sovint això s'ha interpretat com una prova que l'NSA tenia prou capacitat de computació per trencar claus d'aquesta mida ja a mitjans de la dècada del 1970.

La màquina de l'Electronic Frontier Foundation (EFF) tenia 1.536 xips i podia trencar una clau DES per la força bruta en dies. La foto mostra un circuit amb diversos xips Deep Crack.

Acadèmicament, es van avançar diverses propostes per desxifrar el DES. L'any 1977, Diffie i Hellman van proposar una màquina amb un cost estimat de vint milions de dòlars que podria trobar una clau DES en un sol dia. El 1993, Wiener va proposar una màquina de recerca de claus amb un cost d'un milió de dòlars que trobaria una clau en set hores. La vulnerabilitat del DES es va demostrar a la pràctica el 1998, quan l'Electronic Frontier Foundation (EFF), un grup dedicat als drets civils al ciberespai, va construir una màquina a mida per desxifrar el DES, amb un cost aproximat de 250.000 dòlars (vegeu EFF DES cracker). La seva motivació era demostrar que es podia trencar el DES tant en la teoria com a la pràctica: «Hi ha molta gent que no es creu les veritats fins que les poden veure amb els seus propis ulls. Mostrar-los una màquina física que pugui desxifrar el DES en uns quants dies és l'única manera de convèncer-les que realment no li poden confiar la seva seguretat.» La màquina va trencar una clau per la força bruta, en una recerca que va durar poc més de dos dies; gairebé alhora, un advocat del Departament de Justícia dels Estats Units proclamava que el DES era indesxifrable.

A part d'aquesta, l'única màquina per trencar el DES de la qual es té coneixement confirmat és COPACOBANA (acrònim de cost-optimized parallel code breaker, 'trencador de codi paral·lel optimitzat en cost'), construïda per equips de les Universitats de Bochum i de Kiel, les dues a Alemanya. A diferència de la màquina de l'EFF, COPACOBANA es basa en circuits integrats reconfigurables que estan disponibles comercialment. Hi treballen en paral·lel 120 FPGA de tipus XILINX Spartan3-1000. S'agrupen en vint mòduls DIMM, cadascun dels quals conté sis FPGA. La utilització de maquinari reconfigurable fa que la màquina es pugui fer servir també per altres tasques de desxiframent de codis. La figura mostra un COPACOBANA de mida real. Un dels aspectes més interessants de COPACOBANA és el cost, ja que es pot construir per aproximadament deu mil dòlars. La reducció de costos (aproximadament vint-i-cinc vegades menys que la màquina de l'EFF, i unes trenta vegades menys tenint en compte la inflació) és un exemple impressionant de la contínua millora en maquinari digital. És interessant observar que aplicant la llei de Moore s'obté un resultat similar, ja que d'acord amb aquesta llei el costa hauria de ser trenta-dues vegades més baix. En efecte, van passar aproximadament vuit anys entre el disseny de les dues màquines; això representaria que la potència computacional s'hauria duplicat unes cinc vegades, i per tant, que el cost de fer el mateix càlcul s'hauria reduït cinc vegades un 50 per cent cada vegada.

Atacs més ràpids que la força bruta[modifica | modifica el codi]

Hi ha tres atacs coneguts que poden trencar les setze rondes completes del DES amb menys complexitat que un atac per la força bruta: la criptoanàlisi diferencial, la criptoanàlisi lineal i l'atac de Davies. De totes maneres, aquests atacs només són teòrics i no és factible dur-los a la pràctica; de vegades s'anomenen febleses certificacionals.

  • La criptoanàlisi diferencial va ser descoberta a finals de la dècada de 1980 per Eli Biham i Adi Shamir, encara que tant l'NSA com IBM l'havien descobert abans i ho havien mantingut en secret. Per trencar les setze rondes completes, la criptoanàlisi diferencial necessita 247 textos clars escollits. El disseny del DES ja està pensat per resistir la criptoanàlisi diferencial.
  • La criptoanàlisi lineal va ser descoberta per Mitsuru Matsui, i necessita 243 textos clars coneguts;[17] el mètode va ser implementat,[11] i va ser la primera criptoanàlisi experimental del DES que es va donar a conèixer. No hi ha proves que el DES fos adaptat per resistir aquest tipus d'atac. L'any 1994 Kaliski i Robshaw van proposar una generalització de la criptoanàlisi lineal —la criptoanàlisi lineal múltiple—, que al seu torn va ser millorada per Biryukov i altres l'any 2004; l'anàlisi suggereix que es podrien utilitzar múltiples aproximacions lineals per reduir els requisits de dades de l'atac almenys un factor de 4 (és a dir, 241 en lloc de 243). Amb una variant de la criptoanàlisi lineal de textos clars escollits es pot obtenir una reducció similar en la complexitat de dades.[18] Junod (2001) va fer diversos experiments per determinar la complexitat real de la criptoanàlisi lineal, i va descobrir que era una mica més ràpida del que s'havia predit, ja que requeria un temps d'entre 239 i 241 avaluacions DES.
  • 'L'atac millorat de Davies: mentre que l'anàlisi lineal i l'anàlisi diferencial són tècniques generals que es poden aplicar a multitud d'esquemes diferents, l'atac de Davies és una tècnica especialitzada per al DES. Proposada per primera vegada per Davies a la dècada dels vuitanta, i millorada per Biham i Biryukov (1997), la forma més potent de l'atac necessita 250 textos clars coneguts, té una complexitat computacional de 250 i un 51% de probabilitat d'èxit.

També s'han proposat atacs per versions de l'algorisme amb menys rondes, és a dir, versions del DES amb menys de setze rondes. Aquestes anàlisis permeten valorar quantes rondes són necessàries per aconseguir una seguretat determinada, i quin marge de seguretat proporciona la versió completa. La criptoanàlisi diferencial-lineal, proposada per Langford i Hellman el 1994, combina criptoanàlisi diferencial i lineal en un mateix atac. Una versió millorada de l'atac pot trencar un DES de nou rondes amb 215,8 textos clars coneguts i té una complexitat temporal de 229,2.[19]

Propietats criptoanalítiques menors[modifica | modifica el codi]

El DES presenta la propietat complementària, ja que

E_{K}\left( P \right)=C\Leftrightarrow E_{\overline{K}}\left( \overline{P} \right)=\overline{C}

on \overline{x} és el complement a bit de x. E_K és el xifratge amb la clau K. P i C són el text net i el text xifrat respectivament. La propietat complementària implica que el factor de treball per un atac per la força bruta es podria reduir en un factor de 2 (o d'un únic bit) i es fa un atac amb text net escollit.

El DES també té quatre claus anomenades febles. El xifratge (E) i el desxiframent (D) amb una clau feble tenen el mateix efecte (vegeu involució):

E_K(E_K(P)) = P o, de manera equivalent, E_K = D_K

També hi ha sis parells de claus semifebles. El xifratge amb una de les claus d'un parell de claus semifebles, K_1, funciona de la mateixa manera que el desxiframent amb l'altra, K_1:

E_{K_1}(E_{K_2}(P)) = P o el que és equivalent, E_{K_2} = D_{K_1}.

És bastant fàcil evitar les claus febles i semifebles en la implementació, ja sigui provant-les explícitament, o simplement escollint-les aleatòriament; les probabilitats de triar una clau feble o semifeble són menyspreables. De totes maneres, aquestes claus no són més febles que qualsevol altra clau, ja que no donen cap avantatge a l'atacant.

S'ha demostrat també que el DES no té estructura de grup, o més concretament, que el conjunt \{E_K\} (per totes les claus possibles K) no és un grup, ni tan sols no és a prop de ser un grup.[20] Aquesta va ser una qüestió oberta durant algun temps. Si el DES hagués tingut estructura de grup hauria estat possible trencar-lo, i les modalitats de xifratge múltiple com el Triple DES no n'haurien incrementat la seguretat.

La màxima seguretat criptogràfica del DES es va limitar a 56 bits. Si s'haguessin triat independentment les claus de cada una de les rondes en comptes de generar-les a partir de la clau primària, s'hauria arribat a una seguretat de 768 bits.

Vegeu també[modifica | modifica el codi]

Bibliografia[modifica | modifica el codi]

Referències[modifica | modifica el codi]

  1. Walter Tuchman (1997). "A Brief History of the Data Encryption Standard". Internet Besieged: Countering Cyberspace Scofflaws: 275-280, ACM Press/Addison-Wesley Publishing Co. Nova York, NY, USA.  
  2. Schneier. Applied Cryptography. segona edició, p. 280. 
  3. Davies, D. W.; W. L. Price. Security for Computer Networks, segona edició. John Wiley & Sons, 1989. 
  4. Robert Sugarman (editor). «On Foiling Computer Crime». IEEE Spectrum. IEEE, juliol de 1979.
  5. P. Kinnucan. «Data Encryption Gurus: Tuchman and Meyer». Cryptologia, vol. 2, 4, octubre de 1978.
  6. Levy, Crypto, pàg. 55
  7. Levy, pàg. 55
  8. [enllaç sense format] http://csrc.nist.gov/publications/nistpubs/800-67/SP800-67.pdf
  9. Bruce Schneier, Applied Cryptography, Protocols, Algorithms, and Source Code in C, segona edició, John Wiley and Sons, Nova York, 1996, pàg. 267.
  10. William E. Burr, «Data Encryption Standard», dins de: Institut Nacional d'Estàndards i Tecnologia (ed.), A Century of Excellence in Measurements, Standards, and Technology: A Chronicle of Selected NBS/NIST Publications, 1901–2000. HTML PDF
  11. 11,0 11,1 Matsui, 1994
  12. FR Doc 04-16894
  13. Vegeu Registre Federal, volum 70, número 96 (anglès)
  14. Vegeu FIPS Pub 46-3.
  15. FIPS 81 - Des Modes of Operation
  16. FIPS 74 - Guidelines for Implementing and Using the NBS Data
  17. Matsui, 1993
  18. Knudsen i Mathiassen, 2000
  19. Biham 'et al., 2002
  20. Campbell i Wiener, 1992

Enllaços externs[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: DES Modifica l'enllaç a Wikidata