Data Encryption Standard

Archiu:Board300.jpg

Data Encryption Standard

Data Encryption Standard (DES) és un algoritme de sifrat, és dir, un método per a sifrar informació, triat com un estàndart FIPS en els Estats Units en 1976, i l'us dels quals s'ha propagat àmpliament per tot lo món. L'algoritme va ser controvertit al principi, en alguns elements de disseny classificats, una llongitut de clau relativament curta, i les contínues sospites sobre l'existència d'alguna porta atrassera per a la National Security Agency (NSA). Posteriorment DES va ser somés a un intens anàlisis acadèmic i va motivar el concepte modern del sifrat per blocs i el seu criptoanálisis.

Hui en dia, DES es considera insegur per a moltes aplicacions. Açò es deu principalment a que el tamany de clau de 56 bits és curt; les claus de DES s'han trencat en menys de 24 hores. Existixen també resultats analítics que demostren debilitats teòriques en el seu sifrat, encara que són inviables en la pràctica. Es creu que l'algoritme és segur en la pràctica en la seua variant de Triple DES, encara que existixquen atacs teòrics.

Des de fa alguns anys, l'algoritme ha segut substituït pel nou AES (Advanced Encryption Standard).

En algunes ocasions, DES és denominat també DEA (Data Encryption Algorithm).

L'història de DES

Els orígens de DES es remonten a principis dels 70. En 1972, despuix de terminar un estudi sobre les necessitats del govern en matèria de seguritat informàtica, l'autoritat d'estàndarts nortamericà NBS (National Bureau of Standards), ara rebatejat NIST (National Institute of Standards and Technology), va concloure en la necessitat d'un estàndart a nivell governamental per a sifrar informació confidencial. En conseqüència, el 15 de maig de 1973, despuix de consultar en la NSA, el NBS va solicitar propostes per a un algoritme que complira rigorosos criteris de disseny. A pesar de tot, cap d'elles semblava ser adequada. Una segona petició va ser realisada el 27 d'agost de 1974. En aquella ocasió, IBM va presentar un candidat que va ser considerat acceptable, un algoritme desenrollat durant el periodo 1973–1974 basat en un atre anterior, l'algoritme Lucifer d'Horst Feistel. L'equip de IBM dedicat al disseny i anàlisis de l'algoritme estava format per Feistel, Walter Tuchman, Don Coppersmith, Alan Conheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith, i Bryant Tuckerman.

El paper de la NSA en el disseny

El 17 de març de 1975, la proposta de DES va ser publicada en el Registre Federal. Es varen solicitar comentaris per part del públic, i l'any següent es varen obrir dos tallers lliures per a discutir l'estàndart propost. Va haver algunes crítiques des de certs sectors, incloent als pioners de la criptografia asimètrica Martin Hellman i Whitfield Diffie, mencionant la curta llongitut de la clau i les misterioses S-caixas com una evidència de l'inadequada interferència de la NSA. La sospita era que l'algoritme havia segut debilitat de manera secreta per l'agència d'inteligència de manera que ells, i ningú més, pogueren llegir mensages sifrats fàcilment. Alan Konheim (un dels dissenyadors de DES) va comentar en una ocasió "varen enviar les S-caixes a Washington. Quan varen tornar eren totalment diferents". El Comité d'Inteligència del Senat dels Estats Units va revisar les accions de la NSA per a determinar si havia existit algun comportament inadequat. En el resum desclasificado sobre les seues conclusions, publicat en 1978, el Comité escrivia: "En el desenroll de DES, la NSA va convéncer a IBM de que un tamany de clau reduït era suficient; va participar de forma indirecta en el desenroll de les estructures de les S-caixes; i va certificar que, fins a a on ells coneixien, estaven lliures de qualsevol punt dèbil matemàtic o estadístic.". De totes formes, també va concloure que "La NSA no va eixercir pressió en el disseny de l'algoritme en modo algun. IBM va inventar i va dissenyar l'algoritme, va prendre totes les decisions respecte a ell, i va coincidir que el tamany de la clau era més que apropiat per a totes les aplicacions comercials per a les que estava pensat DES". Un atre membre de l'equip de DES, Walter Tuchman, dia també: "Desenrollem tot l'algoritme DES en IBM i en gent de IBM. ¡La NSA no va dictar ni un sol pas!".

Algunes de les sospites sobre punts dèbils amagats en les S-caixes varen ser descartades en 1990, en el descobriment independent i la publicació lliure per Eli Biham i Adi Shamir del criptoanálisis diferencial, un método general per a trencar sifrats de bloc. Les S-caixes de DES eren molt més resistents a l'atac que si hagueren segut triades a l'encert, lo que sugeria que IBM coneixia la tècnica allà en els 70. Est era de fet, el cas, en 1994, Don Coppersmith va publicar els criteris de disseny originals per a les S-caixes. IBM havia descobert el criptoanálisis diferencial en els 70 i, despuix d'assegurar DES, la NSA els va ordenar mantindre en secret la tècnica. Coppersmith explica: "Açò era aixina perque el criptoanálisis diferencial pot ser una ferramenta molt potent, contra molts esquemes diferents, i hi havia la preocupació de que aquella informació en domini públic podia afectar negativament a la seguritat nacional". Shamir també va comentar "Yo diria, al contrari de lo que alguns creuen, que no hi ha evidències d'influència alguna en el disseny de DES per a que la seua estructura bàsica estiga debilitada."

Les atres crítiques, sobre que la llongitut de clau era massa curta, es fundaven en el fet de que la raó donada per la NSA per a reduir la llongitut de la clau de 64 bits a 56 era que els 8 bits restants podien servir com bits de paritat, lo que en cert modo resultava sospitós. És àmpliament acceptat que la decisió de la NSA estava motivada per la possibilitat de que ells podrien portar a terme un atac per força bruta contra una clau de 56 bits varis anys abans que el restant del món.

L'algoritme com a estàndar

A pesar de la polèmica, DES va ser aprovat com a estàndart federal en novembre de 1976, i publicat el 15 de giner de 1977 com FIPS PUB 46, autorisat per a l'us no classificat de senyes. Va ser posteriorment confirmat com a estàndar en 1983, 1988 (revisat com FIPS-46-1), 1993 (FIPS-46-2), i de nou en 1999 (FIPS-46-3), definint-se en esta última publicació el "Triple DES" (vore més avall). El 26 de maig de 2002, DES va ser finalment reemplaçat per AES (Advanced Encryption Standard), despuix d'una competició pública (vore Procés de Advanced Encryption Standard). El 19 de maig de 2005, FIPS 46-3 va ser oficialment retirat, pero el NIST va aprovar l'us de Triple DES fins a l'any 2030 per a informació governamental sensible.

Un atre atac teòric, el criptoanálisis llineal, va ser publicat en 1994, pero va anar un atac per força bruta en 1998 el que va demostrar que DES podria ser atacat en la pràctica, i es va destacar la necessitat d'un algoritme de recanvi. Estos i atres métodos de criptoanálisis es comenten en més detall posteriorment en este artícul.

L'introducció de DES és considerada com un desencadenador de l'estudi acadèmic de la criptografia, en particular dels métodos per a trencar sifrats de bloc. Bruce Schneier escriu:

"De portes cap a dins, la NSA ha vist a DES com un dels seus grans errors. Si hagueren sabut que els detalls serien publicats per a que la gent poguera escriure software, mai hagueren estat d'acort. DES va fer més per a galvanizar el camp de la criptografia que mai res abans. Ara hi havia un algoritme que estudiar: un que la NSA dia que era segur."^{cita requerida}

Canviant

Cronologia

Data	Any	Event
15 de maig	1973	NBS publica una primera petició per a un algoritme estàndar de sifrat
27 d'agost	1974	NBS publica una segona petició per a algoritmes de sifrat
17 de març	1975	DES és publicat en el Registre Federal per a comentaris
Agost	1976	Primer taller sobre DES
Setembre	1976	Segon taller, sobre fonaments matemàtics de DES
Novembre	1976	DES és aprovat com a estàndart
15 de giner	1977	DES és publicat per el FIPS com a estàndar FIPS PUB 46
	1983	DES és confirmat per primera volta
22 de giner	1988	DES és confirmat per segona volta com FIPS 46-1, reemplaçant a FIPS PUB 46
	1992	Biham i Shamir publiquen el primer atac teòric en menys complexitat que el de força bruta: el criptoanálisis diferencial. De qualsevol modo, requerix una cantitat irreal de 247 texts plans triats (Biham and Shamir, 1992).
30 de decembre	1993	DES és confirmat per tercera volta com FIPS 46-2
	1994	Es porta a terme el primer criptoanálisis experimental de DES utilisant criptoanálisis llineal (Matsui, 1994).
Juliol	1998	El DES cracker de l'EFF (Electronic Frontier Foundation) conegut com Deep Crack trenca una clau DES en 56 hores.
Giner	1999	De forma conjunta, Deep Crack i distributed.net trenquen una clau DES en 22 hores i 15 minuts.
25 d'octubre	1999	DES és confirmat per quarta volta com FIPS 46-3, que específica la preferència d'us de Triple DES, en DES simple permés solament en sistemes heretats.
26 de novembre	2001	L'algoritme AES (Advanced Encryption Standard) es publica com FIPS 197
26 de maig	2002	L'estàndart AES es fa efectiu
26 de juliol	2004	Es propon la retirada de FIPS 46-3 (i un parell d'estàndarts relacionats) en el Registre Federal

Algoritmes de tongada

Molts dels anteriors usuaris de DES ara utilisen Triple DES (3DES) que va ser descrit i analisat en una de les paleses de DES (vore FIPS PUB 46-3); consistix en l'aplicació de DES tres voltes consecutives amprant dos (2TDES, la primera clau en els passos 1 i 3) o tres (3TDES) claus. 3DES ha segut àmpliament reconegut com segur per ara, encara que és prou llent. Una alternativa més econòmica en térmens computacionals és DES-X, que incrementa el tamany de clau fent un XOR llògic sobre els elements extra de la clau abans i despuix de DES. GDES va ser una variant de DES proposta per a accelerar el procés de sifrat, pero es va demostrar que era susceptible de ser somés al criptoanálisis diferencial.

En 2001, despuix d'un concurs internacional, el NIST va triar un nou algoritme: l'AES (Advanced Encryption Standard), per a reemplaçar a DES. L'algoritme elegit per a ser la tongada va ser proposta pels seus dissenyadors baix el nom de Rijndael. Atres finalistes en la competició AES de el NIST varen ser RC6, Serpent, MARS, i Twofish.

En general, no hi ha cap algoritme que s'adapte perfectament a tots els usos. Un algoritme per a us en màquines d'us general (per eixemple, SSH, o alguns tipos de sifrat de correu electrònic), no sempre funciona be en sistemes embebidos o targetes inteligents, i viceversa.

Bibliografia

• 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. Cryptologs 10(3): pp. 195-206 (1997)
• Eli Biham, Orr Dunkelman, Nathan Keller: Enhancing Differential-Linear Crypdstanalysis. ASIACRYPT 2002: pp254–266
• A. Biryukov, C. De Canniere, M. Quisquater, "On Multiple Linear Approximations", CRYPTO 2004 (to appear); preprint (PDF).
• Keith W. Campbell, Michael J. Wiener: DES is not a Group. CRYPTO 1992: pp. 512–520
• Dò Coppersmith. (1994). The data encryption standard (DES) and its strength against attacks. IBM Journal of Research and Development, 38(3), pp. 243–250. [1]
• Witfield Diffie, Martin Hellman, "Exhaustive Cryptanalysis of the NBS Data Encryption Standard" IEEE Computer 10(6), June 1977, pp. 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. Selected Areas in Cryptography", 2001, pp. 199-211.
• Burton S. Kaliski Jr., Matthew J. B. Robshaw: Linear Cryptanalysis Using Multiple Approximations. CRYPTO 1994: pp26–39

• Lars R. Knudsen, John Erik Mathiassen: A Chosen-Plaintext Linear Attack on DES. FSE 2000: pp262–272
• Susan K. Langford, Martin E. Hellman: Differential-Linear Cryptanalysis. CRYPTO 1994: pp. 17–25
• Steven Levy, Crypto: How the Code Rebels Beat the Government Saving Privacy in the Digital Age (ISBN 0-14-024432-8)
• Mitsuru Matsui: Linear Cryptanalysis Method for DES Cipher. EUROCRYPT 1993: pp. 386-397
• Mitsuru Matsui: The First Experimental Cryptanalysis of the Data Encryption Standard. CRYPTO 1994: pp1-11
• National Bureau of Standards, Data Encryption Standard, FIPS-Pub.46. National Bureau of Standards, U.S. Department of Commerce, Washington D.C., January 1977.

Vore també

• Criptografia simètrica
• IDEA
• Triple DES