Data Encryption Standard

(Redirecționat de la DES)

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.

Funcția Feistel din cadrul algoritmului

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

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

modificare

Î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] Arhivat în , la Wayback Machine.

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],[1] "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.[2]

Tabel cronologic

modificare
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

modificare

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

modificare
 
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. Opt 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ă

modificare

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

modificare

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

modificare
 
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ă

modificare

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

modificare

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

 

unde   este complementul pe biți al lui  .   denotă criptarea cu cheia  .   și   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):

  sau echivalent,  

Există și șase perechi de chei semi-slabe. Criptarea cu o pereche de chei semi-slabe,  , operează identic cu decriptarea cu o alta,  :

  sau echivalent,  

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   (a tuturor cheilor posibile  ) 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.

  1. ^ Bruce Schneier, Criptografie Aplicată, Protocoale, Algoritmi și Cod Sursă în C, Ediția a doua, John Wiley și Fiii, New York (1996) p. 267
  2. ^ William E. Burr, "Data Encryption Standard", în antologia NIST "Un secol de excelență în Măsurători, Standarde și Tehnologie: O Cronică de Publicații NBS/NIST Selectate, 1901–2000. HTML Arhivat în , la Wayback Machine. PDF Arhivat în , la Wayback Machine.

Bibliografie

modificare
Cifruri bloc
Algoritmi: 3-Way | AES | Akelarre | Anubis | ARIA | BaseKing | Blowfish | C2 | Camellia | CAST-128 | CAST-256 | CIKS-1 | CIPHERUNICORN-A | CIPHERUNICORN-E | CMEA | Cobra | COCONUT98 | Crab | CRYPTON | CS-Cipher | DEAL | DES | DES-X | DFC | E2 | FEAL | FROG | G-DES | GOST | Grand Cru | Hasty Pudding Cipher | Hierocrypt | ICE | IDEA | IDEA NXT | Iraqi | Intel Cascade Cipher | KASUMI | KHAZAD | Khufu and Khafre | KN-Cipher | Libelle | LOKI89/91 | LOKI97 | Lucifer | M6 | MacGuffin | Madryga | MAGENTA | MARS | Mercy | MESH | MISTY1 | MMB | MWA | MULTI2 | NewDES | NOEKEON | NUSH | Q | RC2 | RC5 | RC6 | REDOC | Red Pike | S-1 | SAFER | SC2000 | SEED | Serpent | SHACAL | SHARK | Skipjack | SMS4 | Square | TEA | Triple DES | Twofish | UES | Xenon | xmx | XTEA | XXTEA | Zodiac
Design: Rețea Feistel | Key schedule | Product cipher | Matrice de substituție | RSP

Atacuri: Brute force | Linear / Differential / Integral cryptanalysis | Mod n | Related-key | Slide | XSL

Standardizare: AES process | CRYPTREC | NESSIE

Diverse: Efectul avalanșă | Block size | IV | Key size | Modes of operation | Piling-up lemma | Weak key

Criptografie
Istoria criptologiei | Criptanaliză | Portalul criptografiei | Subiecte în criptografie
Algoritm cu chei simetrice | Cifru bloc | Cifru stream | Criptografie cu chei publice | Funcție hash criptografică | Cod de autentificare a mesajelor | Număr aleatoriu