[Prethodno poglavlje]   [Sljedeće poglavlje]   [Sadržaj]

2.3. Svojstva DES-a

Uočimo da su sve operacije u DES-u linearne (sjetimo se da je ⊕ zapravo zbrajanje u Z2), s izuzetkom S-kutija. Već smo na primjeru Hillove šifre vidjeli da je kod linearnih kriptosustava kriptoanaliza napadom "poznati otvoreni tekst" vrlo jednostavna. Stoga su S-kutije izuzetno značajne za sigurnost DES-a. Od objave algoritma, pa sve do danas, S-kutije su obavijene tajnovitošću. Vidjet ćemo da će se kod nasljednika DES-a upravo taj dio promijeniti: S-kutije će biti generirane eksplicitno navedenim algoritmom.

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

Kriteriji 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 Sj i Sk vrijedi da ako neki izlazni bit od Sj utječe na neki središnji bit od Sk u idućoj rundi, onda niti jedan izlazni bit od Sk ne utječe na središnje bitove od Sj. Za j = k ovo povlači da izlazni bitovi od Sj ne utječu na središnje bitove od Sj.

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 (preuzetim iz knjige [Stinson: Cryptography. Theory and Practice]).

Primjer 1: Otvoreni tekstovi (zapisani heksadecimalno)

0000000000000000   i   1000000000000000

šifrirani su pomoću ključa (također zapisanog heksadecimalno s uključenim paritetnim bitovima)

029749C438313864.

Broj bitova u kojima se razlikuju odgovarajući šifrati nakon svake pojedine od 16 rundi DES-a prikazan je u sljedećoj tablici:

----------------------------------------------------------------------
    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: Otvoreni tekst

68852E7A1376EBA4

šifriran je pomoću ključeva

E5F7DF313B0862DC   i   64F7DF313B0862DC

koji se razlikuju samo u jednom bitu (i jednom paritetnom bitu: prvih 7 bitova su im 1110010 i 0110010). Broj bitova razlike u šifratima, po rundama, prikazan je u sljedećoj tablici:

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


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 nakon 5. runde svaki bit šifrata ovisi o svakom bitu otvorenog teksta i svakom bitu ključa, a nakon 8. runde šifrat je praktički slučajna funkcija bitova otvorenog teksta i ključa. 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 256 ≈ 7.2 · 1016 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 i konačno razbijanje DES-a se dogodilo tek 1998. godine. Tada je Electronic Frontier Foundation (EFF) za 250000 dolara zaista napravila "DES Cracker", koji je razbijao poruke šifrirane DES-om za 56 sati.


Za fiksni ključ K pomoću DES-a definirana je permutacija skupa {0,1}64. Dakle, skup od 256 permutacija dobivenih pomoću DES-a je podskup grupe svih permutacija skupa {0,1}64, čiji je red 264!. Postavlja se pitanje da li je 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 o 22499. Ova je činjenica jako važna jer pokazuje da se višestrukom upotrebom DES-a može postići veća sigurnost. Posebno je popularan tzv. Triple-DES koji koristi tri koraka običnog DES-a s različitim ključevima. 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 K1, ... , K16 jednaki. To znači da su postupak šifriranja i dešifriranja doslovno jednaki. Dakle, vrijedi eK(eK(x)) = x. Drugim riječima, DES sa slabim ključem je involucija. Poznato je da šifriranje sa slabim ključem ostavlja 232 otvorenih tekstova fiksnim. Postoje točno 4 DES slaba ključa. To su oni kod kojih se u rastavu PC1(K) = C0D0, lijeve i desne polovice C0 i D0 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 DES-a s polu-slabim ključem, među 16 međuključeva K1, ... , K16 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, između 256 mogućih ključeva imamo samo 64 ključa koja treba izbjegavati, pa je to lako i učiniti.


[Prethodno poglavlje]   [Sljedeće poglavlje]   [Sadržaj]
Web stranica kolegija Kriptografija Andrej Dujella - osobna stranica