Spargerea DES-ului

Spargerea DES-ului

DES a fost implicat in numeroase controverse inca din ziua in care a fost lansat. El se baza pe un cifru dezvoltat si brevetat de IBM, numit Lucifer, cu exceptia faptului ca acest cifru al IBM-ului folosea o cheie de 128 de biti in locul uneia de 56 de biti. Atunci cand guvernul federal al SUA a dorit sa standardizeze un cifru ca nefiind secret, el a "invitat" IBM-ul sa "discute aceasta problema cu NSA, agentia spargatoare de coduri a guvernului, care utilizeaza cel mai mare numar de matematicieni si criptologi din lume. NSA este atat de secreta, incat in industrie a aparut urmatoarea gluma:

I Ce inseamna NSA?

R No Such Agency (Nu exista o astfel de agentie).

De fapt, NSA vine de la National Security Agency (Agentia Nationala de Securitate).

Dupa ce au avut loc aceste discutii, IBM a redus cheia de la 128 de biti la 56 de biti si a decis sa pastreze secret procesul prin care a fost proiectat DES-ul. Multi oameni suspecteaza faptul ca lungimea cheii a fost redusa pentru a exista siguranta ca NSA poate sparge DES-ul, dar nici organizatie cu un buget mai mic nu poate face asta. Pastrarea secretului proiectarii a fost facuta probabil pentru a ascunde o trapa (usa ascunsa) care ar putea usura spargerea DES-ului de catre NSA.Cand un angajat al NSA a atentionat discret IEEE sa abandoneze conferinta planificata pe teme de criptografie, acesta nu i-a facut pe oameni sa se simta mai bine.

In 1977, doi cercetatori in criptografie de la Stanford, Diffie si Hellman (1977), au proiectat masina pentru a sparge DES-ul si s-a estimat ca ea poate fi construita cu un buget de 20 de milioane de dolari. Data fiind o mica bucata de text clar si textul cifrat corespunzator, aceasta masina ar putea sa gaseasca cheia, prin cautarea exhaustiva a 2⁵⁶ intrari din spatiul cheilor in mai putin de o zi. In prezent, o astfel de masina ar costa probabil 1 milion de dolari. O proiectare detaliata pentru o masina ce poate sparge DES-ul prin cautare exhaustiva in aproape patru ore este prezentata in (Wiener, 1994).

Aici exista o alta strategie, desi criptarea software este de 1000 de ori mai lenta decat criptarea hardware, cel mai scump calculator personal poate face aproape 250 000 criptari/sec in software si este probabil nefolosit 2 milioane de secunde/luna. In acest timp, in care nu este folosit, el poate fi utilizat pentru a sparge DES-ul. Daca cineva ar trimite un mesaj spre unul dintre cele mai populare grupuri de stiri din Internet, nu ar fi greu sa inrolezi 140 oameni pentru a verifica 7x10¹⁶ chei intr-o luna.

Probabil cea mai inovatoare idee pentru spargerea cifrului DES este Loteria Chinezeasca (Quisquater si Girault, 1991). In acest proiect, fiecare aparat de radio si televizor trebuie echipat cu un cip DES capabil sa realizeze l milion de criptari/secunda in hardware. Presupunand ca fiecare din cei 1.2 miliarde de oameni din China poseda un aparat de radio, ori de cate ori guvernul vrea sa decripteze un mesaj criptat cu DES, el raspandeste perechea text clar/text cifrat si fiecare dintre cele 1.2 miliarde de cipuri incepe cautarea in sectiunea sa prestabilita din spatiul cheilor. In 60 de secunde, vor fi gasite una (sau mai multe) potriviri. Pentru a asigura ca aceste potriviri vor fi raportate, cipurile pot fi programate sa afiseze pe ecran sau sa anunte mesajul:

FELICITARI! TOCMAI ATI CASTIGAT LOTERIA CHINEZEASCA.

PENTRU A RIDICA PREMIUL VA RUGAM SA SUNATI LA 1-900-MARELE-PREMIU

Concluzia care trebuie trasa din aceste argumente este aceea ca DES-ul nu mai trebuie folosit pentru criptarea documentelor importante. Cu toate ca 256 este un nesemnificativ 7 x 10¹⁶, 2¹¹² este un impunator 5 x 10³³. Chiar cu un miliard de cipuri DES executand un miliard de operatii pe secunda, ar trebui 100 de milioane de ani pentru a cauta exhaustiv intr-un spatiu de chei pe 112 biti Astfel apare ideea de a rula DES-ul de doua ori, eu doua chei diferite pe 56 de biti.

Din nefericire, Merkle si Hellman (1981) au dezvoltat o metoda care face ca dubla criptare sa devina suspecta. Aceasta poarta numele de atacul intalnirea-la-mijloc (rneet-in-the-middle) si lucreaza astfel (Hellman, 1980). Sa presupunem ca cineva a dublu-criptat o serie de blocuri de text clar, folosind modul carte electronica de coduri. Pentru cateva valori ale lui i, criptanalistul poseda perechile (P_i, C_i), unde:

Ci=Ek₂(E_k1(P_i))

Daca aplicam acum functia de decriptare D_k2 pentru fiecare membru al ecuatiei, obtinem:

D_k2(C_i)=E_k1(P_i)

deoarece criptarea lui x si decriptarea lui x cu aceeasi cheie dau tot x.

Atacul "intalnirea-la-mijloc" foloseste aceasta ecuatie pentru a gasi cheile DES, K1 si K2, dupa cum urmeaza:

1. Se calculeaza R_i=E_i(P₁) pentru toate cele 2⁵⁶ valori ale lui i, unde E este functia de criptare a DES-ului. Acest tablou se sorteaza crescator dupa R_i.

2. Se calculeaza S_j=D_j(C₁) pentru toate cele 2⁵⁶ valori ale lui j, unde D este functia de decriptare a DES-ului. Acest tablou este sortat crescator dupa S_j.

3. Se parcurge primul tablou cautand un R_i care se potriveste cu un Sj din al doilea tablou. Atunci cand este gasita o potrivire, avem o pereche de chei (i,j), astfel incat D_j(C₁) =E_j(P_i). i este un potential K1 si j este un potential K2.

4. Se verifica daca E_j(E_i(P₂)) este egal cu C₂. Daca da, se incearca toate celelalte perechi (text clar, text cifrat). Daca nu, continua cautarea potrivirilor in cele doua tablouri.

Cu siguranta ca inainte ca adevaratele chei sa fie loca1izate, vor aparea multe alarme false. dar, in cele din urma acestea vor fi gasite. Atacul necesita doar 2⁵⁷ operatii de criptare sau decriptare (pentru a construi cele doua tablouri), mult mai putine decat 2¹¹². Totusi, este de asemenea necesar un total de 2⁶⁰ octeti de memorie pentru cele doua tablouri, astfel ca atacul nu este realizabil in forma de baza, dar Merk1e si Hellman au aratat diferite optimizari si compromisuri ce permit spatiu de memorare mai mic la un cost de calcul mai mare. Avand in vedere toate acestea, probabilca dubla criptare folosind DES nu este mult mai sigura decat criptarea simpla.

Tripla criptare este o alta problema. Chiar din 1979, IBM a realizat ca lungimea cheii DES era prea mica si a conceput un mod de a o creste efectiv, folosind tripla criptare (Tuchman, 1979).

Metoda aleasa care de atunci a fost incorporata in Standardul International 8732, este ilustrata in Figura 2-6. Aici sunt folosite doua chei si trei runde. In prima runda textul clar este criptat cu K₁. In a doua runda, este rulat DES in mod de decriptare, folosind cheia K₂. In final, este efectuata o alta criptare cu K_1.

D

E

D

K₁ K₂ K₁ K₁ K₂ K₁

E

D

E

P C C P

(a) (b)

Fig. 2-6. Tripla criptare folosind DES.

Proiectarea da nastere imediat la doua intrebari. Prima, de ce sunt folosite doar doua chei in loc de trei? A doua este folosita succesiunea de transformari EDE, in loc de EEE? Motivul pentru care sunt utilizate doua chei este acela ca majoritatea criptografilor paranoici admit ca 112 biti sunt suficienti pentru aplicatiile comerciale la momentul actual. A extinde Ia 168 de biti inseamna a adauga o supraincarcare inutila pentru gestiunea si transportul unei alte chei.

Motivul pentru criptare, decriptare si apoi iar criptare este compatibilitatea cu produsele existente ce folosesc sisteme DES cu o singura cheie. Atat functia de criptare cat si cea de decriptare sunt corespondente intre multimi de numere pe 64 de biti. Din punct de vedere criptografic cele doua corespondente sunt la fel de puternice. Totusi, folosind EDE in locul EEE, un calculator ce utilizeaza tripla criptare poate comunica cu unul ce foloseste criptarea simpla, punand K₁=K₂. Aceasta proprietate permite triplei criptari sa fie pusa in practica treptat, lucru care nu intereseaza pe criptografii din mediul academic, dar care este de o importanta considerabila pentru IBM si clientii sai.

Nu este cunoscuta nici o metoda care sa fi spart triplul-DES in modul EDE. Van Oorschot si Wiener (1988) au prezentat o metoda pentru a mari viteza cautari EDE cu un factor al lui 16, dar chiar si cu acest atac, EDE este foarte sigur. Pentru oricine care doreste doar cei mai bun, este recomandat EEE cu trei chei distincte de 56 de biti (168 de biti in total).

Inainte de a parasi subiectul DES, merita cel putin sa mentionam doua progrese recente in criptanaliza. Primul progres este criptanaliza diferentiala (Biham si Shamir, 1993). Aceasta tehnica poate fi folosita pentru a ataca orice cifru bloc. Lucreaza la inceput cu o pereche de blocuri de text clar care difera doar printr-un numar mic de biti si studiaza cu grija ceea ce se intampla la fiecare iteratie interna pe masura ce criptarea avanseaza. In multe cazuri, anumite combinatii apar mai des decat altele si aceasta observatie conduce la un atac probabilistic.

Celalalt progres, mai putin important, este criptanaliza liniara (Matsui, 1994). Aceasta sparge DES-ul cu doar 2⁴³ texte clare cunoscute. Lucreaza prin combinarea XOR a anumitor biti din textul clar si din textul cifrat pentru a genera un bit. Cand aceasta se efectueaza repetat, jumatate din biti trebuie sa fie O si jumatate sa fie 1. Totusi, adeseori, cifrurile introduc o deviatie intr-o directie sau in alta si aceasta deviatie, cu toate ca este mica, poate fi exploatata pentru a reduce factorul de munca. Pentru mai multe detalii a se vedea lucrarea lui Matsui.