Data Encryption Standard

Funcţia Feistel din cadrul algoritmului

Standardul de Criptare a Datelor (în engleză Data Encryption Standard, DES) este un cifru (o metodă de criptare a informaţiei), selectat ca standard federal de procesare a informaţiilor în Statele Unite în 1976, şi care s-a bucurat ulterior de o largă utilizare pe plan internaţional. Algoritmul a fost controversat iniţial, având elemente secrete, lungimea cheii scurtă şi fiind bănuit că ascunde de fapt o portiţă pentru NSA. DES a fost analizat intens de către profesionalişti în domeniu şi a motivat înţelegerea cifrurilor bloc şi criptanaliza lor.

DES este astăzi considerat nesigur pentru multe aplicaţii. Acest lucru se datorează în principiu cheii de 56 de biţi, considerată prea scurtă; cheile DES au fost sparte în mai puţin de 24 de ore. De asemenea, există unele rezultate analitice care demonstrează slăbiciunile teoretice ale cifrului, deşi nu este fezabilă aplicarea lor. Se crede că algoritmul este practic sigur în forma Triplu DES, deşi există atacuri teoretice şi asupra acestuia. În ultimii ani, cifrul a fost înlocuit de Advanced Encryption Standard (AES).

În unele documentaţii, se face distincţie între DES ca standard şi algoritmul de la baza lui, numit DEA (Algoritmul de Criptare a Datelor - în engleză, Data Encryption Algorithm).

Istorie

Originile DES sunt în anii 1970. În 1972, după concluziile unui studiu asupra nevoilor de securitate pentru calculatoare a guvernului Statelor Unite, NBS (National Bureau of Standards) — acum numit NIST (National Institute of Standards and Technology) — a identificat necesitatea unui standard de criptare a datelor importante, nesecrete, care să fie folosit de toate statele. În consecinţă, pe 15 mai 1973, după consultarea cu NSA, NBS a solicitat propuneri pentru un cifru care să fie conform criteriilor de design riguroase. Nici una dintre înregistrări însă nu s-a dovedit a fi corespunzătoare. O a doua cerere a fost emisă pe 27 august 1974. De această dată, IBM a înscris un candidat considerat acceptabil, un cifru dezvoltat în perioada 1973–1974, bazat pe un algoritm existent, cifrul Lucifer al lui Horst Feistel. Echipa de la IBM implicată în dezvoltarea şi analiza cifrului îi include pe Feistel, Walter Tuchman, Don Coppersmith, Alan Konheim, Carl Meyer, Mike Matyas, Roy Adler, Edna Grossman, Bill Notz, Lynn Smith, şi Bryant Tuckerman.

Algoritmul ca standard

În ciuda criticilor, DES a fost aprobat ca standard federal în noiembrie 1976 şi publicat pe 15 ianuarie 1977 ca FIPS PUB 46, utilizarea sa fiind autorizată pentru toate datele care nu sunt secrete de stat. A fost reafirmat ca standard în 1983, 1988 (revizuit ca FIPS-46-1), 1993 (FIPS-46-2) şi încă o dată în 1998 (FIPS-46-3), ultima variantă recomandând "Triplu DES" (vezi mai jos). Pe 26 mai 2002, DES a fost înlocuit de AES, Advanced Encryption Standard, după o competiţie publică. Chiar şi din 2004, DES încă a rămas folosit pe scară largă. Pe 19 mai 2005, FIPS 46-3 a fost retras oficial, dar NIST a aprobat Triplu DES până în anul 2030 pentru informaţii guvernamentale. [1]

Un alt atac teoretic, criptanaliză liniară, a fost publicat în 1994, dar un atac prin forţă brută a demonstrat în 1998 că DES poate fi spart practic, şi a evidenţiat nevoia unui algoritm de înlocuire. Acestea şi alte metode de criptanaliză sunt discutate mai jos.

Introducerea lui DES este considerată un catalizator pentru studiul academic al criptografiei, mai ales al metodelor de spargere a cifrurilor bloc. Conform unei retrospective din partea NIST despre DES,

Despre DES se poate spune că a "iniţiat" studiul nemilitar şi dezvoltarea algoritmilor de criptare. În anii 1970 erau puţini criptografi, cu excepţia celor din organizaţii militare sau de inteligenţă, iar studiul academic al criptografiei nu era dezvoltat. Acum există mulţi criptologi academicieni activi, departamente de matematică care susţin programe de criptografie puternice şi companii şi consultanţi de securitate a informaţiilor comerciale. O generaţie de criptanalişti s-a chinuit să spargă algoritmul DES. În cuvintele criptografului Bruce Schneier [9], "DES a galvanizat mai mult domeniul criptografiei mai mult decât orice altceva. Acesta este un algoritm de studiat". O mare parte a literaturii din criptografie din anii 1970 şi 1980 s-a ocupat de DES, iar DES este standardul faţă de care toţi algoritmii cu cheie simetrică au fost evaluaţi de atunci.

Tabel cronologic

Dată	An	Eveniment
15 mai	1973	NBS publică prima cerere pentru un algoritm de criptare standard
27 august	1974	NBS publică a doua cerere pentru algoritmi de criptare
17 martie	1975	DES este publicat în Federal Register pentru comentarii
august	1976	Primul atelier de lucru pentru DES
septembrie	1976	Al doilea atelier, în care se discută fundamentele matematice ale lui DES
noiembrie	1976	DES este aprobat ca standard
15 ianuarie	1977	DES este publicat ca standardul FIPS PUB 46
	1983	DES este reafirmat pentru prima dată
	1986	Videocipher II, un sistem de criptare a sateliţilor TV bazat pe DES este folosit de HBO
22 ianuarie	1988	DES este reafirmat a doua oară ca FIPS 46-1, înlocuind FIPS PUB 46
iulie	1990	Biham şi Shamir redescoperă criptanaliza diferenţială şi o aplică unui criptosistem asemănător lui DES, cu 15 runde.
	1992	Biham şi Shamir raportează primul atac teoretic cu o complexitate mai mică decât cel prin forţă brută: criptanaliză diferenţială. Totuşi, necesită un număr impresionant de texte normale: 247.
30 decembrie	1993	DES este reafirmat a treia oară ca FIPS 46-2
	1994	Prima criptanaliză experimentală este efectuată asupra lui DES folosind criptanaliza liniară (Matsui, 1994).
iunie	1997	Proiectul DESCHALL sparge un mesaj criptat cu DES pentru prima dată în public.
iulie	1998	EFF construieşte DES cracker (Deep Crack), care sparge o cheie DES în 56 de ore.
ianuarie	1999	Împreună, Deep Crack şi distributed.net sparg o cheie DES în 22 de ore şi 15 minute.
25 octombrie	1999	DES este reafirmat a patra oară ca FIPS 46-3, care specifică utilizarea preferată a variantei Triplu DES, permiţând DES simplu doar în sistemele vechi.
26 noiembrie	2001	Advanced Encryption Standard este publicat în FIPS 197
26 mai	2002	Standardul AES este folosit
26 iulie	2004	Retragerea FIPS 46-3 (şi a altor două standarde înrudite) este propusă în Federal Register [2]
19 mai	2005	NIST retrage FIPS 46-3
13 ianuarie	2007	Maşina paralelă bazată pe FPGA, COPACOBANA, de la Universitatea din Bochum şi Kiel, Germania, sparge DES în 7,2 zile cu un cost hardware de 10.000 de dolari.

Algoritmi de înlocuire

Grijile despre securitatea şi operarea relativ înceată a lui DES în software au motivat cercetătorii să propună o varietate de alternative de cifruri bloc, care au început să apară la sfârşitul anilor 1980 şi la începutul anilor 1990; de exemplu, RC5, Blowfish, IDEA, NewDES, SAFER, CAST5 şi FEAL. Cei mai mulţi dintre aceşti algoritmi au păstrat blocul de 64 de biţi al lui DES şi puteau acţiona ca înlocuitori, deşi foloseau de obicei chei de 64 sau 128 de biţi. În URSS, algoritmul GOST 28147-89 a fost introdus, cu mărimea blocului de 64 de biţi şi cheia de 256 de biţi, iar acesta a fost folosit în Rusia mai târziu.

DES poate fi adaptat şi reutilizat într-o schemă mai complexă. Mulţi foşti utilizatori ai DES folosesc acum Triplu DES (TDES, 3DES) care a fost descris şi analizat de una dintre persoanele care a patentat DES; a implicat aplicarea lui DES de trei ori cu două (2TDES) sau trei (3TDES) chei diferite. 3DES este privit ca adecvat de sigur, deşi este încet. O alternativă computaţional mai ieftină este DES-X, care incrementează mărimea cheii prin aplicarea operaţiei XOR pe material extra înainte şi după DES. GDES a fost o variantă a DES propusă drept metodă de a mări viteza de criptare, dar a fost prea susceptibilă criptanalizei diferenţiale.

În 2001, după o competiţie internaţională, NIST a selectat un cifru nou: Advanced Encryption Standard (AES), ca înlocuitor. Algoritmul care a fost selectat ca AES a fost înscris de către designerii săi sub numele de Rijndael. Alţi finalişti în competiţia NIST pentru AES sunt RC6, Serpent, MARS şi Twofish.

Descriere

Figura 1 — Structura Feistel generală din DES

Pentru concizie, descrierea următoare omite transformările şi permutările exacte necesare algoritmului; pentru referinţe, detaliile pot fi găsite la Material suplimentar pentru DES.

DES este cifrul bloc arhetip — un algoritm care ia un şir de lungime fixă de biţi de text normal şi îl transformă print-o serie de operaţii complexe într-un şir de biţi criptaţi de aceeaşi lungime. În cazul DES, mărimea blocului este de 64 biţi. DES foloseşte de asemenea şi o cheie pentru particularizarea transformării, astfel încât numai cei care cunosc cheia folosită să poată efectua decriptarea. Cheia este formată din 64 de biţi; totuşi, numai 56 dintre ei sunt folosiţi propriu-zis de algoritm. Opti biţi sunt utilizaţi ca biţi de paritate şi nu sunt necesari după acest test. Deci cheia efectivă are doar 56 de biţi, şi aşa este citată de obicei.

Ca şi alte cifruri bloc, DES nu este o cale sigură de criptare folosit de sine-stătător. El trebuie folosit într-un mod de operare. FIPS-81 specifică câteva feluri pentru utilizarea cu DES [3]. Alte comentarii despre acest lucru apar în FIPS-74 [4].

Structură generală

Structura generală a algoritmului apare în Figura 1: sunt 16 paşi identici de procesare, numiţi runde. Există şi câte o permutare iniţială şi finală, numite PI and PF, care sunt funcţii inverse (PI "anulează" acţiunea lui PF şi vice versa). PI şi PF nu au aproape nici o importanţă criptografică, dar au fost incluse pentru a facilita încărcarea şi descărcarea blocurilor folosind hardware-ul din anii 1970.

Înaintea rundelor principale, blocul este împărţit în două jumătăţi, de câte 32 de biţi, şi procesate alternativ; această alternare este cunoscută drept Schema Feistel. Structura Feistel asigură că criptarea şi decriptarea sunt procese foarte asemănătoare — singura dieferenţă este ordinea aplicării subcheilor - invers la decriptare. Restul algoritmului este identic. Acest lucru simplifică implementarea, în special cea hardware, deoarece nu e nevoie de algoritmi separaţi.

Simbolul $\oplus$ cu roşu denotă operaţia OR exclusiv (XOR). Funcţia F amestecă jumătate din bloc cu o subcheie. Rezultatului funcţiei F este combinat cu cealaltă jumătate de bloc, iar jumătăţile sunt interschimbate înaintea următoarei runde. După ultima rundă, jumătăţile nu sunt schimbate; aceasta este o trăsătură a structurii Feistel care face din criptare şi decriptare procese similare.

Funcţia Feistel (F)

Funcţia F, care apare în Figura 2, operează pe o jumătate de bloc (32 biţi) la un moment dat şi este formată din patru paşi:

Figura 2 — Funcţia Feistel (F) din DES

1. Expansiune — jumătatea de bloc de 32 de biţi este extinsă la 48 de biţi folosind funcţia de expansiune, notată E în diagramă, prin duplicarea unor biţi.
2. Amestecare — rezultatul este combinat cu o subcheie folosind operaţia XOR. Şaisprezece subchei de 48 de biţi — una pentru fiecare rundă — sunt derivate din cheia principală folosind diversificarea cheilor (descrisă mai jos).
3. Substituţie — după amestecarea cu subcheia, blocul este divizat în opt bucăţi de 6 biţi fiecare înainte de procesarea folosind cutiilor S, sau cutii de substituţie. Fiecare din cele opt cutii S înlocuieşte cei şase biţi de intrare cu patru biţi conform unei transformări neliniare, oferită sub forma unui tabel de căutare. Cutiile S reprezintă securitatea lui DES — fără ele, cifrul ar fi liniar şi uşor de spart.
4. Permutare — în final, cele 32 de ieşiri din matricile S sunt rearanjate conform permutării fixe P.

Alternarea substituţiilor din matricile S şi permutarea biţilor folosind matricea P şi expansiunea E oferă ceea ce se numeşte "confuzie şi difuzie", un concept identificat de către Claude Shannon în anii 1940 ca fiind necesar unui cifru sigur şi practic în acelaşi timp.

Diversificarea cheilor

Figura 3 — Diversificarea cheilor în DES

Figura 3 ilustrează diversificarea cheilor pentru criptare — algoritmul care generează subcheile. Iniţial, 56 de biţi din cheia principală sunt selectaţi din cei 64 prin permutarea PC-1 — ceilalţi 8 biţi sunt ignoraţi sau folosiţi ca biţi de paritate. Cei 56 de biţi sunt apoi împărţiţi în două blocuri de 28 de biţi; fiecare jumătate este tratată ulterior separat. În runde succesive, ambele jumătăţi sunt rotate la stânga cu unul sau doi biţi (specificaţi pentru fiecare rundă), şi apoi sunt selectaţi cei 48 de biţi ai subcheii prin permutarea PC-2 — 24 de biţi din jumătatea stângă, şi 24 din cea dreaptă. Rotaţiile (notate cu "<<<" în diagramă) înseamnă că un set de biţi diferit este folosit în fiecare subcheie; fiecare bit este folosit în circa 14 din cele 16 chei.

Diversificarea cheilor pentru decriptare este similară — trebuie să se genereze subcheile în ordine inversă. Aşadar, rotaţiile sunt la dreapta, şi nu la stânga.

Securitate şi criptanaliză

Deşi despre criptanaliza lui DES s-a publicat mai multă informaţie decât despre cea a oricărui alt cifru bloc, atacul cel mai practic rămâne cel prin forţă brută. Diferite proprietăţi criptanalitice minore sunt cunoscute, iar trei atacuri teoretice sunt posibile. Acestea au complexitatea mai mică decât cea a atacului prin forţă brută, dar numărul de texte necesare este nerealist şi de aceea nu sunt fezabile.

În ciuda tuturor criticilor şi slăbiciunilor lui DES, nu există exemple de persoane care să fi suferit pierderi băneşti din cauza limitărilor de securitate ale lui DES.

Proprietăţi criptanalitice minore

DES deţine proprietatea complementarităţii, adică

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

unde ${\overline {x}}$ este complementul pe biţi al lui $x\,$. $E_{K}\,$ denotă criptarea cu cheia $K\,$. $P\,$ şi $C\,$ sunt textul normal şi, respectiv, textul criptat. Proprietatea complementarităţii înseamnă că munca unui atac prin formţă brută se înjumătăţeşte (un bit) sub prezumpţia unui text ales.

DES are, de asemenea, patru chei slabe. Criptarea (E) şi decriptarea (D) cu o cheie slabă au acelaşi efect (vezi involuţie):

$E_{K}(E_{K}(P))=P\,$ sau echivalent, $E_{K}=D_{K}\,$

Există şi şase perechi de chei semi-slabe. Criptarea cu o pereche de chei semi-slabe, $K_{1}\,$, operează identic cu decriptarea cu o alta, $K_{2}\,$:

$E_{K_{1}}(E_{K_{2}}(P))=P$ sau echivalent, $E_{K_{2}}=D_{K_{1}}$

Este uşor de evitat cheile slabe şi semi-slabe într-o implementare, fie prin testare explicită, fie prina alegerea aleatorie a cheilor; şansele de alegere a unei chei slabe sau semi-slabe sunt neglijabile. Aceste chei nu sunt în realitate mai slabe decât alte chei în nici un fel, pentru că nu avantajează nici un atac.

S-a dovedit că DES nu este un grup, sau mai precis, mulţimea $\{E_{K}\}$ (a tuturor cheilor posibile $K\,$) faţă de compunerea funcţiilor nu este grup, şi nici măcar "aproape" de a fi grup (Campbell şi Wiener, 1992). Aceasta a fost o întrebare pentru un timp, şi dacă aşa era cazul, ar fi fost posibil să se spargă DES, iar modalităţile de criptare multiple, precum Triplu DES nu ar fi mărit securitatea.

Este cunoscut faptul că securitatea criptografică maximă a lui DES este limitată la 64 de biţi, chiar şi când se aleg independent subcheile în locul derivării lor din cheia principală, care ar permite altfel o securitate de 768 de biţi.

Bibliografie

• Ehrsam et al., Product Block Cipher System for Data Security, U.S. Patent 3962539, 24 februarie 1975
• Eli Biham, Adi 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 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: pp 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 (to appear); preprint (PDF).
• Keith W. Campbell, Michael J. Wiener: DES is not a Group. CRYPTO 1992: pp512–520
• Don Coppersmith. (1994). The data encryption standard (DES) and its strength against attacks. IBM Journal of Research and Development, 38(3), 243–250. [5]
• Whitfield Diffie, Martin Hellman, "Exhaustive Cryptanalysis of the NBS Data Encryption Standard" IEEE Computer 10(6), June 1977, pp74–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, pp199–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. Fast Software Encryption - FSE 2000: pp262–272
• Susan K. Langford, Martin E. Hellman: Differential-Linear Cryptanalysis. CRYPTO 1994: 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: pp386–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., ianuarie 1977.