DES

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.

Aquest article tracta sobre Data Encryption Standard (DES). Si cerqueu Deep Ecliptic Survey (DES), vegeu «Deep Ecliptic Survey».

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).

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 a 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

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ó confidencial 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

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è eren 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

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 confidencial.^[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'utilitzar 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

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

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ó

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

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.

Permutacions inicial i final

Permutació inicial IP

Aquesta taula especifica la permutació inicial sobre un bloc de 64 bits. El seu significat és el següent: el primer bit de la sortida s'agafa de la posició on és el cinquanta-vuitè bit de l'entrada; el segon bit, de la cinquantena posició, i així successivament fins a l'últim bit de la sortida, que s'agafa de la setena posició de l'entrada.

 |----------------------|
 |58|50|42|34|26|18|10|2|
 |----------------------|
 |60|52|44|36|28|20|12|4|
 |----------------------|
 |62|54|46|38|30|22|14|6|
 |----------------------|
 |64|56|48|40|32|24|16|8|
 |----------------------|
 |57|49|41|33|25|17| 9|1|
 |----------------------|
 |59|51|43|35|27|19|11|3|
 |----------------------|
 |61|53|45|37|29|21|13|5|
 |----------------------|
 |63|55|47|39|31|23|15|7|
 |----------------------|

Permutació final FP

La permutació final és la inversa de la permutació inicial; la taula s'interpreta de manera anàloga.

 |----------------------|
 |40|8|48|16|56|24|64|32|
 |----------------------|
 |39|7|47|15|55|23|63|31|
 |----------------------|
 |38|6|46|14|54|22|62|30|
 |----------------------|
 |37|5|45|13|53|21|61|29|
 |----------------------|
 |36|4|44|12|52|20|60|28|
 |----------------------|
 |35|3|43|11|51|19|59|27|
 |----------------------|
 |34|2|42|10|50|18|58|26|
 |----------------------|
 |33|1|41| 9|49|17|57|25|
 |----------------------|

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

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 a un xifratge segur i pràctic.

Funció d'expansió E

La funció d'expansió es defineix a la taula següent, que s'ha d'interpretar igual que les taules de les permutacions inicial i final. Fixeu-vos que alguns bits de l'entrada es dupliquen a la sortida. Per exemple, el cinquè bit de l'entrada es duplica, copiant-se tant a la posició sisena com a la vuitena de la sortida. Així, els 32 bits del semibloc s'expandeixen a 48 bits.

|-----------------| |32| 1| 2| 3| 4| 5| |-----------------| | 4| 5| 6| 7| 8| 9| |-----------------| | 8| 9|10|11|12|13| |-----------------| |12|13|14|15|16|17| |-----------------| |16|17|18|19|20|21| |-----------------| |20|21|22|23|24|25| |-----------------| |24|25|26|27|28|29| |-----------------| |28|29|30|31|32| 1| |-----------------|

Caixes S

Aquesta taula llista les vuit caixes-S que es fan servir al DES. Cada caixa-S substitueix els sis bits d'entrada per quatre bits de sortida. Donada una entrada de sis bits, els quatre bits de sortida es troben seleccionant la fila amb els dos bits extrems i la columna amb els quatre bits centrals. Fixeu-vos que dos bits codifiquen quatre files i quatre bits codifiquen setze columnes, per això cada caixa té quatre files i setze columnes. Fixeu-vos també que a cada casella hi ha un número que va del 0 al 15; per tant, s'escriu amb quatre bits, que són els quatre bits de sortida. Per exemple, una entrada de «011011» té de bits extrems els «01» i de bits interns, «1101»; com que la primera fila és la «00» i la primera columna és la «0000», la sortida corresponent per la caixa-S₅ ha de ser «1001» (=9), el valor de la casella que hi ha a la segona fila i la catorzena columna. (Vegeu caixa–S.)

S₁

|-----------------------------------------------|
|14| 4|13| 1| 2|15|11| 8| 3|10| 6|12| 5| 9| 0| 7|
|-----------------------------------------------|
| 0|15| 7| 4|14| 2|13| 1|10| 6|12|11| 9| 5| 3| 8|
|-----------------------------------------------|
| 4| 1|14| 8|13| 6| 2|11|15|12| 9| 7| 3|10| 5| 0|
|-----------------------------------------------|
|15|12| 8| 2| 4| 9| 1| 7| 5|11| 3|14|10| 0| 6|13|
|-----------------------------------------------|

S₂

|-----------------------------------------------|
|15| 1| 8|14| 6|11| 3| 4| 9| 7| 2|13|12| 0| 5|10|
|-----------------------------------------------|
| 3|13| 4| 7|15| 2| 8|14|12| 0| 1|10| 6| 9|11| 5|
|-----------------------------------------------|
| 0|14| 7|11|10| 4|13| 1| 5| 8|12| 6| 9| 3| 2|15|
|-----------------------------------------------|
|13| 8|10| 1| 3|15| 4| 2|11| 6| 7|12| 0| 5|14| 9|
|-----------------------------------------------|

S₃

|-----------------------------------------------|
|10| 0| 9|14| 6| 3|15| 5| 1|13|12| 7|11| 4| 2| 8|
|-----------------------------------------------|
|13| 7| 0| 9| 3| 4| 6|10| 2| 8| 5|14|12|11|15| 1|
|-----------------------------------------------|
|13| 6| 4| 9| 8|15| 3| 0|11| 1| 2|12| 5|10|14| 7|
|-----------------------------------------------|
| 1|10|13| 0| 6| 9| 8| 7| 4|15|14| 3|11| 5| 2|12|
|-----------------------------------------------|

S₄

|-----------------------------------------------|
| 7|13|14| 3| 0| 6| 9|10| 1| 2| 8| 5|11|12| 4|15|
|-----------------------------------------------|
|13| 8|11| 5| 6|15| 0| 3| 4| 7| 2|12| 1|10|14| 9|
|-----------------------------------------------|
|10| 6| 9| 0|12|11| 7|13|15| 1| 3|14| 5| 2| 8| 4|
|-----------------------------------------------|
| 3|15| 0| 6|10| 1|13| 8| 9| 4| 5|11|12| 7| 2|14|
|-----------------------------------------------|

S₅

|-----------------------------------------------|
| 2|12| 4| 1| 7|10|11| 6| 8| 5| 3|15|13| 0|14| 9|
|-----------------------------------------------|
|14|11| 2|12| 4| 7|13| 1| 5| 0|15|10| 3| 9| 8| 6|
|-----------------------------------------------|
| 4| 2| 1|11|10|13| 7| 8|15| 9|12| 5| 6| 3| 0|14|
|-----------------------------------------------|
|11| 8|12| 7| 1|14| 2|13| 6|15| 0| 9|10| 4| 5| 3|
|-----------------------------------------------|

S₆

|-----------------------------------------------|
|12| 1|10|15| 9| 2| 6| 8| 0|13| 3| 4|14 |7| 5|11|
|-----------------------------------------------|
|10|15| 4| 2| 7|12| 9| 5| 6| 1|13|14| 0|11| 3| 8|
|-----------------------------------------------|
| 9|14|15| 5| 2| 8|12| 3| 7| 0| 4|10| 1|13|11| 6|
|-----------------------------------------------|
| 4| 3| 2|12| 9| 5|15|10|11|14| 1| 7| 6| 0| 8|13|
|-----------------------------------------------|

S₇

|-----------------------------------------------|
| 4|11| 2|14|15| 0| 8|13| 3|12| 9| 7| 5|10| 6| 1|
|-----------------------------------------------|
|13| 0|11| 7| 4| 9| 1|10|14| 3| 5|12| 2|15| 8| 6|
|-----------------------------------------------|
| 1| 4|11|13|12| 3| 7|14|10|15| 6| 8| 0| 5| 9| 2|
|-----------------------------------------------|
| 6|11|13| 8| 1| 4|10| 7| 9| 5| 0|15|14| 2| 3|12|
|-----------------------------------------------|

S₈

|-----------------------------------------------| |13| 2| 8| 4| 6|15|11| 1|10| 9 |3|14| 5| 0|12| 7| |-----------------------------------------------| | 1|15|13| 8|10| 3| 7| 4|12| 5|6|11| 0|14| 9| 2| |-----------------------------------------------| | 7|11| 4| 1| 9|12|14| 2| 0| 6|10|13|15| 3| 5| 8| |-----------------------------------------------| | 2| 1|14| 7| 4|10| 8|13|15|12| 9| 0| 3| 5| 6|11| |-----------------------------------------------|

Caixa-P

La permutació P remena els 32 bits del semibloc.

|-----------| |16| 7|20|21| |-----------| |29|12|28|17| |-----------| | 1|15|23|26| |-----------| | 5|18|31|10| |-----------| | 2| 8|24|14| |-----------| |32|27| 3| 9| |-----------| |19|13|30| 6| |-----------| |22|11| 4|25| |-----------|

Figura 3 — La programació de claus del DES

Programació de claus

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 venen en l'ordre invers del xifratge. A banda d'això, el procés és el mateix que per al xifratge.

Caixes PC-1, PC-2 i taula de rotacions

Selecció permutada 1 (PC-1)

Les meitats "Esquerra" i "Dreta" indiquen quins bits de la clau formaran la secció dreta i esquerra de l'esquema del programa de claus. Fixeu-vos que només se seleccionen 56 dels 64 bits de l'entrada; els vuit bits restants es fan servir com a bits de paritat.

|--------------------|
| Meitat esquerra |
|57|49|41|33|25|17| 9|
|--------------------|
| 1|58|50|42|34|26|18|
|--------------------|
|10| 2|59|51|43|35|27|
|--------------------|
|19|11| 3|60|52|44|36|
|--------------------|
| Meitat dreta |
|--------------------|
|63|55|47|39|31|23|15|
|--------------------|
| 7|62|54|46|38|30|22|
|--------------------|
|14| 6|61|53|45|37|29|
|--------------------|
|21|13| 5|28|20|12| 4|
|--------------------| 

Rotacions en el programa de claus

Abans de seleccionar la clau de cada ronda, es fa una rotació cap a l'esquerra dels bits de cada meitat de la clau. Aquesta taula indica el nombre de llocs cap a l'esquerra de cada rotació.

|-------------------------------------------------------------------|
|Ronda | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|16| 
|Nombre de rotacions| 1| 1| 2| 2| 2| 2| 2| 2| 1| 2| 2| 2| 2| 2| 2| 1|
|-------------------------------------------------------------------|

Selecció permutada 2 (PC-2)

Aquesta permutació selecciona els 48 bits que formaran la subclau que s'emprarà en cada ronda a partir dels 56 bits establerts pel programa de claus.

|-----------------| |14|17|11|24| 1| 5| |-----------------| | 3|28|15| 6|21|10| |-----------------| |23|19|12| 4|26| 8| |-----------------| |16| 7|27|20|13| 2| |-----------------| |41|52|31|37|47|55| |-----------------| |30|40|51|45|33|48| |-----------------| |44|49|39|56|34|53| |-----------------| |46|42|50|36|29|32|

Seguretat i criptoanàlisi

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 pràctica 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

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

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 2⁴⁷ 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 2⁴³ 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, 2⁴¹ en comptes de 2⁴³). 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 2³⁹ i 2⁴¹ 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 2⁵⁰ textos clars coneguts, té una complexitat computacional de 2⁵⁰ 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 2^15,8 textos clars coneguts i té una complexitat temporal de 2^29,2.^[19]

Propietats criptoanalítiques menors

El DES presenta la propietat complementària, ja que

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

on ${\displaystyle {\overline {x}}}$ és el complement a bit de ${\displaystyle x.}$ ${\displaystyle E_{K}}$ és el xifratge amb la clau ${\displaystyle K.}$ ${\displaystyle P}$ i ${\displaystyle 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ó):

${\displaystyle E_{K}(E_{K}(P))=P}$ o, de manera equivalent, ${\displaystyle 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, ${\displaystyle K_{1}}$, funciona de la mateixa manera que el desxiframent amb l'altra, ${\displaystyle K_{1}}$:

${\displaystyle E_{K_{1}}(E_{K_{2}}(P))=P}$ o el que és equivalent, ${\displaystyle 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 ${\displaystyle \{E_{K}\}}$ (per totes les claus possibles ${\displaystyle 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.

Referències

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, 7-1979.
5. P. Kinnucan «Data Encryption Gurus: Tuchman and Meyer». Cryptologia, 2, 4, 10-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 Arxivat 2012-05-04 a Wayback Machine.
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 Arxivat 2009-06-19 a Wayback Machine. PDF Arxivat 2006-08-23 a Wayback Machine.
11. Matsui, 1994
12. FR Doc 04-16894
13. Vegeu Registre Federal, volum 70, número 96 Arxivat 2008-06-25 a Wayback Machine. (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

Vegeu també

• Xifratge de clau simètrica
• Advanced Encryption Standard

Bibliografia

• Josep Domingo Ferrer i Jordi Herrera Joancomartí. Criptografia pels serveis telemàtics i el comerç electrònic. A les pàgines 99 i següents s'explica en detall el criptosistema DES.
• Ehrsam et al. «Product Block Cipher System for Data Security», Filed, 24 de febrer del 1975.
• Eli Biham, Adi Shamir (1990). «Differential Cryptanalysis of DES-like Cryptosystems». Advances in Cryptology — CRYPTO '90. Springer-Verlag, pàg. 2-21.
• Eli Biham, Adi Shamir. Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. ISBN 0-387-97930-1, ISBN 3-540-97930-1.
• Eli Biham, Alex Biryukov. «An Improvement of Davies' Attack on DES». J. Cryptology 10(3): 195-206 (1997).
• Eli Biham, Orr Dunkelman, Nathan Keller. Enhancing Differential-Linear Cryptanalysis. ASIACRYPT 2002: 254-266.
• Eli Biham. «A Fast New DES Implementation in Software Cracking DES: Secrets of Encryption Research, Wiretap Politics, and Chip Design», Electronic Frontier Foundation.
• A. Biryukov, C. De Canniere, M. Quisquater. «On Multiple Linear Approximations», CRYPTO 2004; preimpressió (PDF) Arxivat 2007-06-15 a Wayback Machine..
• Keith W. Campbell, Michael J. Wiener. «DES is not a Group». CRYPTO 1992: pàg. 512-520.
• Don Coppersmith (1994). «The Data Encryption Standard (DES) and its Strength Against Attacks». IBM Journal of Research and Development, 38 (3), 243-250.
• Whitfield Diffie, Martin Hellman, «Exhaustive Cryptanalysis of the NBS Data Encryption Standard», IEEE Computer 10(6), juny del 1977, pàg. 74-84.
• John Gilmore, Cracking DES: Secrets of Encryption Research, Wiretap Politics and Chip Design, 1998, O'Reilly, ISBN 1-56592-520-3.
• Pascal Junod, «On the Complexity of Matsui's Attack». Arxivat 2009-05-27 a Wayback Machine. Selected Areas in Cryptography, 2001, pàg. 199-211.
• Burton S. Kaliski Jr., Matthew J. B. Robshaw. «Linear Cryptanalysis Using Multiple Approximations». CRYPTO 1994, pàg. 26-39.
• Lars R. Knudsen, John Erik Mathiassen. «A Chosen-Plaintext Linear Attack on DES». Fast Software Encryption - FSE 2000: pàg. 262–272.
• Susan K. Langford, Martin E. Hellman. «Differential-Linear Cryptanalysis». CRYPTO, 1994, pàg. 17-25.
• Steven Levy. Crypto: How the Code Rebels Beat the Government Saving Privacy in the Digital Age, 2001, ISBN 0-14-024432-8.
• Mitsuru Matsui. «Linear Cryptanalysis Method for DES Cipher». EUROCRYPT, 1993, pàg. 386-397.
• Mitsuru Matsui. «The First Experimental Cryptanalysis of the Data Encryption Standard». CRYPTO, 1994: pàg. 1-11.
• National Bureau of Standards, Data Encryption Standard, FIPS-Pub. 46. National Bureau of Standards, US Department of Commerce, Washington DC, gener del 1977.

Enllaços externs

• FIPS 46-3: The official document describing the DES standard (PDF); An older version in HTML.
• John Savard's description of DES
• Bit slice implementation of DES
• RFC4772: Security Implications of Using the Data Encryption Standard (DES)