2.3. Svojstva DES-a

Kod DES-a znamo tek neke kriterije koji su korišteni u dizajniranju S-kutija:

1. Svaki redak u svakoj S-kutiji je permutacija brojeva od 0 do 15.

2. Niti jedna S-kutija nije linearna ili afina funkcija ulaznih podataka.

3. Promjena jednog bita u ulaznom podatku kod primjene S-kutije ima za posljedicu promjenu barem 2 bita u izlaznom podatku.

4. Za svaku S-kutiju i svaki ulazni podatak x (niz bitova duljine 6), S(x) i S(x ⊕ 001100) razlikuju se za barem 2 bita.

5. Za svaku S-kutiju, svaki ulazni podatak x i sve e, f ∈ {0,1} vrijedi S(x) ≠ S(x ⊕ 11ef00).

Neki od kriterija za permutaciju P bili su sljedeći:

1. Četiri izlazna bita iz svake S-kutije utječu (čine ulazne podatke) na šest različitih S-kutija u idućoj rundi, a nikoja dva ne utječu na istu S-kutiju.

2. Četiri izlazna bita iz svake S-kutije u i-toj rundi su distribuirani tako da dva od njih utječu na središnje bitove u (i+1)-voj rundi, a dva na krajnje bitove (dva najlijevija i dva najdesnija od 6 bitova u ulaznom podatku).

3. Za dvije S-kutije S_j i S_k vrijedi da ako neki izlazni bit od S_j utječe na neki središnji bit od S_k u idućoj rundi, onda niti jedan izlazni bit od S_k ne utječe na središnje bitove od S_j. Za j = k ovo povlači da izlazni bitovi od S_j ne utječu na središnje bitove od S_j.

Ovi kriteriji imaju za zadatak povećati tzv. difuziju kriptosustava, tj. postići da na svaki bit šifrata utječe što više bitova otvorenog teksta. Oni također otežavaju i tzv. diferencijalnu kriptoanalizu o kojoj će biti više riječi nešto kasnije.

Poželjno svojstvo svakog kriptosustava jest da mala promjena bilo otvorenog teksta bilo ključa dovodi do značajne promjene u šifratu. Posebno, promjena jednog bita otvorenog teksta ili jednog bita ključa trebala bi utjecati na mnogo bitova šifrata. Ako je promjena mala, to može značajno smanjiti broj otvorenih tekstova ili ključeva koje treba ispitati.

Kriptosustav DES ima gore opisano svojstvo koje se ponekad naziva i "efekt lavine". Ilustrirat ćemo to s dva primjera (preuzeta iz knjige [Stinson: Cryptography. Theory and Practice]).

Primjer 2.1: Otvoreni tekstovi (zapisani heksadecimalno)

0000000000000000   i   1000000000000000

029749C438313864.

----------------------------------------------------------------------
    runda           0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
----------------------------------------------------------------------
broj bitova koji    1  6 21 35 39 34 32 31 29 42 44 32 30 30 26 29 34  
  se razlikuju
----------------------------------------------------------------------

Primjer 2.2: Otvoreni tekst

68852E7A1376EBA4

E5F7DF313B0862DC   i   64F7DF313B0862DC

----------------------------------------------------------------------
    runda           0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
----------------------------------------------------------------------
broj bitova koji    0  2 14 28 32 30 32 35 34 40 38 31 33 28 26 34 35  
  se razlikuju
----------------------------------------------------------------------

U Shannonovoj terminologiji često se govori o difuziji i konfuziji: difuzija znači da se utjecaj pojedinog bita otvorenog teksta ili ključa raširi na mnogo bitova šifrata, dok konfuzija otežava uočavanje veze između ključa i šifrata.

Postavlja se pitanje zašto u DES-u imamo upravo 16 rundi. Primjeri 1 i 2 sugeriraju da već kod 3. runde efekt lavine dolazi do izražaja. Može se pokazati da se već nakon nekoliko rundi postiže vrlo dobra difuzija: nakon 5. runde svaki bit izlaza ovisi o svakom bitu otvorenog teksta i svakom bitu ključa. Nakon 8 rundi statistička svojstva izlaza već su mnogo bliža svojstvima slučajne funkcije. Razlog da ipak imamo 16 rundi je u zahtjevu da poznati kriptoanalitički napadi (kao što je npr. diferencijalna kriptoanaliza) ne budu efikasniji od napada "grubom silom".

Originalna IBM-ova ponuda NBS-u je imala 112-bitni ključ. Prva IBM-ova realizacija Feistelove šifre - kriptosustav LUCIFER je imao 128-bitni ključ. Međutim, u verziji DES-a koja je prihvaćena kao standard duljina ključa je smanjena na 56 bitova (da bi ključ stao na tadašnje čipove, ali vjerojatno i pod utjecajem NSA). Mnogi kriptografi su bili protiv tako kratkog ključa jer su smatrali da ne pruža dovoljnu sigurnost protiv napada "grubom silom". Uz 56-bitni ključ imamo 2⁵⁶ ≈ 7.2 · 10¹⁶ mogućih ključeva, pa se na prvi pogled napad "grubom silom" čini sasvim nepraktičnim. Međutim, već 1977. godine Diffie i Hellman su ustvrdili da tadašnja tehnologija omogućava konstrukciju računala koje bi otkrivalo ključ za jedan dan, a troškove su procijenili na 20 milijuna dolara. Na osnovu toga su zaključili da je takvo što dostupno samo organizacijama kao što je NSA, ali da će oko 1990. godine DES postati sasvim nesiguran. Godine 1993. Weiner je procijenio da se za 100000 dolara može konstruirati računalo koje bi otkrilo ključ za 35 sati, a za 10 milijuna dolara ono koje bi otkrilo ključ za 20 minuta. Ipak, sve su to bili hipotetski dizajni, a prvo praktično javno razbijanje DES-a dogodilo se 1998. godine. Tada je Electronic Frontier Foundation (EFF) za 250000 dolara zaista napravila "DES Cracker", koji je pronalazio DES ključ za oko 56 sati.

Za fiksni ključ K pomoću DES-a definirana je permutacija skupa {0,1}⁶⁴. Dakle, skup od 2⁵⁶ permutacija dobivenih pomoću DES-a je podskup grupe svih permutacija skupa {0,1}⁶⁴, čiji je red 2⁶⁴!. Postavlja se pitanje je li DES (tj. skup svih njegovih permutacija) podgrupa ove grupe. Odgovor na to pitanje je negativan. Naime, skup svih DES-permutacija nije zatvoren. Preciznije, poznato je da je red podgrupe generirane svim DES-permutacijama veći od 2²⁴⁹⁹. Ova je činjenica jako važna jer pokazuje da se višestrukom upotrebom DES-a može postići veća sigurnost. Posebno je važan tzv. Triple-DES, koji koristi tri primjene DES-a, najčešće u obliku šifriranje–dešifriranje–šifriranje, s dva ili tri ključa. Kad bi DES činio grupu, Triple-DES ne bi bio ništa sigurniji od običnog DES-a.

Neki DES-ključevi su znatno nesigurniji od ostalih, te ih svakako treba izbjegavati. Prvi među njima su tzv. DES slabi ključevi. Kod njih su svi međuključevi K₁, ... , K₁₆ jednaki. To znači da su postupak šifriranja i dešifriranja doslovno jednaki. Dakle, vrijedi e_K(e_K(x)) = x. Drugim riječima, DES sa slabim ključem je involucija. Poznato je da šifriranje sa slabim ključem ostavlja 2³² otvorenih tekstova fiksnim. Postoje točno 4 DES slaba ključa. To su oni kod kojih se u rastavu PC1(K) = C₀D₀, lijeve i desne polovice C₀ i D₀ sastoje ili od samih nula ili od samih jedinica. Par ključeva (K,K') je par DES polu-slabih ključeva ako je kompozicija DES-ova s ključevima K i K' identiteta. Drugim riječima, šifriranje s jednim je isto kao dešifriranje s drugim. Kod poluslabih DES-ključeva, među 16 međuključeva K₁, ... , K₁₆ postoje samo dva različita; svaki od njih se koristi u po 8 rundi. Postoji točno 6 parova DES polu-slabih ključeva. Konačno, neki ključevi generiraju samo 4 različita međuključa. Takvi se ključevi zovu DES potencijalno slabi ključevi i ima ih točno 48. Sve u svemu, od 2⁵⁶ mogućih ključeva samo je 64 potrebno izbjegavati, pa je to lako i učiniti.