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

2.5. Kriptoanaliza DES-a

U ovom poglavlju opisat ćemo tri napada na DES: diferencijalnu kriptoanalizu, linearnu kriptoanalizu i EFF-ov DES Cracker. Iako prva dva napada nisu dovela do razbijanja DES-a, njihova je važnost u tome što su primjenjivi na bilo koji simetrični blokovni kriptosustav. Tako su kod većine mogućih nasljednika DES-a operacije i broj rundi odabrani upravo tako da bi dobiveni kriptosustav bio što otporniji na diferencijalnu i linearnu kriptoanalizu.

Metodu diferencijalne kriptoanalize prvi su javno opisali izraelski kriptolozi Eli Biham i Adi Shamir 1990. godine. No, po svemu sudeći, ta je metoda bila poznata konstruktorima DES-a već 1974. godine, te su je imali u vidu kod dizajna S-kutija i permutacije P. Metoda spada u napade "odabrani otvoreni tekst".

Prikazat ćemo kako ova metoda može biti primjenjena na DES s n rundi (n ≤ 16). Slijedeći [Stinson: Cryptography. Theory and Practice; Poglavlje 3.6, 1. izdanje], metodu ćemo potom ilustrirati prikazom napada na DES s 3 runde. U tu svrhu možemo ignorirati inicijalnu permutaciju IP i njezin inverz (oni nemaju nikakav efekt na kriptoanalizu). Stoga ćemo L0R0 uzeti za otvoreni tekst, a LnRn za šifrat u DES-u s n rundi. Osnovna ideja diferencijane kriptoanalize jest usporedba XOR-a od dva otvorena teksta sa XOR-om od odgovarajuća dva šifrata. Općenito, promatrat ćemo dva otvorena teksta L0R0 i L*0R*0 sa zadanom XOR vrijednošću L'0R'0 = L0R0L*0R*0.

Definicija: Neka je Sj neka S-kutija (1 ≤ j ≤ 8), te neka je (Bj, B*j) uređeni par 6-bitnih nizova. Tada BjB*j zovemo input XOR, a Sj (Bj) ⊕ Sj (B*j) zovemo output XOR.

Za svaki B'j(Z2)6, sa Δ(B'j) označavamo skup svih uređenih parova (Bj, B*j) čiji je input XOR jednak B'j.

Jasno je da vrijedi

Δ(B'j) = { (Bj, BjB'j) : Bj ∈ (Z2)6 },

pa skup Δ(B'j) sadrži 26 = 64 para. Za svaki par iz Δ(B'j) možemo izračunati output XOR. Dobivamo 64 output XOR-a koji su distribuirani između 24 = 16 mogućih vrijednosti za output XOR. Činjenica da ovih 64 output XOR-ova nije uniformno distribuirano predstavlja osnovu za kriptoanalitički napad.

Primjer 4: Promotrimo prvu S-kutiju S1 i input XOR 110100. Imamo

Δ(110100) = {(000000,110100), (000001,110101), ... , (111111,001011)}.

Za svaki uređeni par iz Δ(110100) izračunamo output XOR. Npr. S1(000000) = 1410 = 1110, S1(110100) = 910 = 1001, pa je output XOR para (000000,110100) jednak 0111. Nakon što izračunamo output XOR-ove za sva 64 para, dobivamo sljedeću distribuciju:

 -------------------------------------------------------
  0000   0001   0010   0011   0100   0101   0110   0111
 -------------------------------------------------------
    0      8     16      6      2      0      0     12 
 ------------------------------------------------------- 


 -------------------------------------------------------
  1000   1001   1010   1011   1100   1101   1110   1111
 -------------------------------------------------------
    6      0      0      0      0      8      0      6 
 -------------------------------------------------------

U Primjeru 4 pojavilo se samo 8 od mogućih 16 output XOR-ova i to s vrlo različitim frekvencijama. Općenito, u prosjeku se pojavljuje 75-80% mogućih XOR-ova.

Definicija: Za j ∈ {1, 2, ... , 8}, 6-bitni niz B'j i 4-bitni niz C'j definiramo

INj (B'j, C'j) = { Bj ∈ (Z2)6 : Sj (Bj) ⊕ Sj (BjB'j) = C'j },

Nj (B'j, C'j) = | INj (B'j, C'j) |.

Dakle, Nj(B'j, C'j) je broj parova čiji je input XOR jednak B'j, a output XOR je jednak C'j. Distribucije iz Primjera 4 su upravo vrijednosti N1(110100, C'1), C'1 ∈ (Z2)4, dok su skupovi IN1(110100, C'1) prikazani u sljedećoj tablici.

Podsjetimo se da ulazni podatak za S-kutije u i-toj rundi ima oblik B = EJ, gdje je E = E(Ri -1) proširenje od Ri -1, a J = Ki je i-ti međuključ. Sada je

BB* = (EJ) ⊕ (E* ⊕ J) = EE*,

pa input XOR ne ovisi o međuključu J. Zapišimo B, E, J, B* i E* kao spoj od osam 6-bitnih nizova:

        B = B1 B2 B3 B4 B5 B6 B7 B8
        E = E1 E2 E3 E4 E5 E6 E7 E8
        J = J1 J2 J3 J4 J5 J6 J7 J8
        B* = B*1B*2B*3B*4B*5B*6B*7B*8
        E* = E*1E*2E*3E*4E*5E*6E*7E*8

Definicija: Neka su Ej i E*j 6-bitni nizovi, a C'j 4-bitni niz. Definiramo

testj (Ej, E*j, C'j) = { BjEj : Bj ∈ INj (E'j, C'j) },

gdje je E'j = EjE*j.

Primjer 5: Neka je E1 = 000001, E*1 = 110101, C'1 = 1101. Budući da je N1(110100, 1101) = 8, skup test1(000001, 110101, 1101) će imati 8 elemenata. Iz tablice vidimo da je

IN1(110100, 1101) = { 000110, 010000, 010110, 011100, 100010, 100100, 101000, 110010 },

pa je

test1(000001, 110101, 1101) = { 000111, 010001, 010111, 011101, 100011, 100101, 101001, 110011 }.

Tvrdnja 1: Neka je C'j = Sj (Bj) ⊕ Sj (B*j). Tada je Jj ∈ testj (Ej, E*j, C'j).

Dokaz: Po definiciji treba provjeriti da je JjEj ∈ INj (E'j, C'j). No, JjEj = Bj i Sj (Bj) ⊕ Sj (BjB'j) = Sj (Bj) ⊕ Sj (B*j) = C'j, pa je Jj ∈ testj (Ej, E*j, C'j).


Tvrdnja 1 nam daje nekoliko mogućnosti za Jj. Primjenom Tvrdnja 1 na nekoliko različitih trojki Ej, E*j, C'j, možemo odrediti Jj. Jasno, ovdje je pretpostavka da mi te vrijednosti Ej, E*j, C'j znamo. I veliko je pitanje koliko je ta pretpostavka realistična.

Pokažimo sada kako se ove ideje mogu primijeniti u napadu "odabrani otvoreni tekst" na DES s 3 runde. Krećemo od parova otvorenih tekstova L0R0, L*0R*0 koje smo odabrali tako da je R0 = R*0, tj. R'0 = 00...0, te odgovarajućih šifrata L3R3, L*3R*3. Vrijedi:

R3 = L2f(R2,K3) = R1f(R2,K3) = L0f(R0,K1) ⊕ f(R2,K3),
R*3 = L*0f(R*0,K1) ⊕ f(R*2,K3),
R'3 = L'0f(R2,K3) ⊕ f(R*2,K3).

Sada je f(R2,K3) = P(C) i f(R*2,K3) = P(C*), gdje su C i C* outputi od S-kutija. Stoga je

P(C) ⊕ P(C*) = R'3L'0,

pa je

C' = CC* = P-1(R'3L'0).

Konačno, E = E(R2) = E(L3) i E* = E(R*2) = E(L*3). Dakle, E, E* i C' su nam poznati.

ALGORITAM:

    Ulazni podatci: L0R0, L*0R*0, L3R3 i L*3R*3, gdje je R0 = R*0
  1. Izračunamo: C' = P-1(R'3L'0)
  2. Izračunamo: E = E(L3) i E* = E(L*3)
  3. Za j = 1, 2, ... , 8
            računamo   testj (Ej, E*j, C'j).


Primjenom ovog algoritma na nekoliko različitih inputa možemo odrediti međuključ K3, što nam daje 48 bitova ključa K. Preostalih 8 bitova možemo pronaći tako da testiramo svih 28 = 256 mogućnosti.

Primjer 6: Pretpostavimo da imamo sljedeća tri para otvorenih tekstova i šifrata (zapisanih heksadecimalno) šifriranih istim ključem (otvoreni tekstovi su odabrani tako da zadovoljavaju uvjet R0 = R*0):

  ------------------------------------------------- 
      otvoreni tekst                 šifrat
  -------------------------------------------------
     748502CD38451097           03C70306D8A09F10  
     3874756438451097           78560A0960E6D4CB
  -------------------------------------------------
     486911026ACDFF31           45FA285BE5ADC730
     375BD31F6ACDFF31           134F7915AC253457  
  -------------------------------------------------
     357418DA013FEC86           D8A31B2F28BBC5CF
     12549847013FEC86           0F317AC2B23CB944 
  -------------------------------------------------

Primjenom algoritma na prvi par, dobivamo:

     E = 000000000111111000001110100000000110100000001100
     E*= 101111110000001010101100000001010100000001010010
     C'= 10010110010111010101101101100111
Za drugi par dobivamo
     E = 101000001011111111110100000101010000001011110110
     E*= 100010100110101001011110101111110010100010101010
     C'= 10011100100111000001111101010110  
a za treći
     E = 111011110001010100000110100011110110100101011111
     E*= 000001011110100110100010101111110101011000000100
     C'= 11010101011101011101101100101011
Sada za svaki Jj, j = 1, 2, ... , 8, konstruiramo brojač koji broji za koliko parova Jj zadovoljava uvjet iz Tvrdnje 1. Na primjer, u slučaju prvog para i brojača za J1 imamo E'1 = 101111, C'1 = 1001. Nadalje je

IN1 (101111, 1001) = { 000000, 000111, 101000, 101111 }.

Budući da je E1 = 000000, konačno dobivamo

J1 ∈ test1 (000000, 101111, 1001) = { 000000, 000111, 101000, 101111 }.

To znači da brojač povećamo za 1 na pozicijama 0, 7, 40 i 47. Konačne vrijednosti svih 8 brojača, nakon što su obrađena sva tri para, prikazane su u tablicama. Vidimo da u svakom brojaču imamo jedinstvenu poziciju s brojem 3. Te pozicije određuju bitove od J1, J2, ... , J8. Te pozicije su redom; 47, 5, 19, 0, 24, 7, 7, 49, odnosno binarno

J1 = 101111
J2 = 000101
J3 = 010011
J4 = 000000
J5 = 011000
J6 = 000111
J7 = 000111
J8 = 110001

Sada pogledamo kako izgleda raspored bitova ključa u međuključu K3, te na osnovu toga rekonstruiramo 48 bitova ključa K:

     0001101   0110001   01?01?0   1?00100
     0101001   0000??0   111?11?   ?100011
Upitnike imamo na onim mjestima koja ne sudjeluju u međuključu K3. Sada testiranjem preostalih 256 mogućnosti dobivamo da je ključ (zapisan heksadecimalno, s paritetnim bitovima) jednak

1A624C89520DEC46.


U našem napadu na DES s 3 runde pošli smo od zahtjeva da je R'0 = 00...0. Ova ideja se može poopćiti.

Definicija 4: Neka je n prirodan broj. n-rundna karakteristika je niz oblika

L'0, R'0, L'1, R'1, p1, ... , L'n, R'n, pn

sa svojstvima:
    (1) L'i = R'i -1 za 1 ≤ in,
    (2) Neka je 1 ≤ in, te neka su Li -1, Ri -1, L*i -1, R*i -1 izabrani tako da je Li -1L*i -1 = L'i -1 i Ri -1R*i -1 = R'i -1. Pretpostavimo da su Li, Ri, L*i, R*i dobiveni primjenom jedne rudne DES-a. Tada je vjerojatnost da je LiL*i = L'i i RiR*i = R'i jednaka pi.

U našem primjeru mi smo koristili 1-rundnu karakteristiku

L'0 = prozvoljno, R'0 = 0000000016, L'1 = R'0, R'1 = L'0, p1 = 1.

Jedna druga 1-rundna karakteristika je

L'0 = 0000000016, R'0 = 6000000016, L'1 = R'0, R'1 = 0080820016, p1 = 0.21875.

Biham i Shamir su pronašli 13-rundnu karakteristiku pomoću koje se može razbiti DES (pronaći 48 bitova ključa) uz poznavanje šifrata za 247 odabranih otvorenih tekstova. Ukoliko nemamo mogućnosti koristiti napad "odabrani otvoreni tekst" već samo "poznati otvoreni tekst", onda iz većeg broja parova otvoreni tekst-šifrat moramo odabrati one korisne. Možda je zanimljivo napomenuti da je procijenjeno da time broj potrebnih DES operacija u napadu diferencijalnom kriptoanalizom postaje približno 255, što je sasvim usporedivo s brojem DES operacija u napadu "grubom silom" uz jedan poznati par otvoreni tekst-šifrat. Broj ključeva koje treba testirati je 256. Primijetimo da se taj broj može prepoloviti koristeći svojstvo eK(x) = eK(x), gdje    označava komplement, pa se K i K mogu testirati istovremeno.

Spomenimo da je za DES sa 8, 10, 12 i 14 rundi potrebno poznavanje šifrata za 214, 224, 231, odnosno 239 odabranih tekstova. Dakle, ovo nam daje pravo objašnjenje zašto DES ima upravo 16 rundi.



Linearnu kriptoanalizu je uveo japanski kriptolog Mitsuru Matsui 1993. godine i čini se da ova metoda nije bila poznata tvorcima DES-a. Ideja se sastoji u tome da iako bitovi ključa nisu linearne funkcije otvorenog teksta i šifrata, neki se bitovi ključa mogu dobro aproksimirati linearnom funkcijom.

Označimo bitove otvorenog teksta s P[1], P[2], ... , šifrata s C[1], C[2], ... , te ključa s K[1], K[2], ... . Također uvedimo oznaku

A[i1,i2,...,ik] = A[i1] ⊕ A[i2] ⊕ ... ⊕ A[ik].

Želimo naći linearne jednadžbe oblika

P[i1,i2,...,ia] ⊕ C[j1,j2,...,jb] = K[k1,k2,...,kc]

koje za slučajni otvoreni tekst i šifrat vrijede s vjerojatnošću p ≠ 0.5. Što je p dalje od 0.5, to bolje. Tada računamo lijevu stranu za mnogo parova otvoreni tekst-šifrat i tako dobivamo očekivanu vrijednost desne strane. Pretpostavimo da je u više pola slučajeva na lijevoj strani dobivena 0. Ako je p > 0.5, onda za vjerojatnu vrijednost uzimamo 0, a ako je p < 0.5, onda uzimamo 1. Tako dobivamo jednu linearnu jednadžbu u bitovima ključa. Ako nađemo dovoljno takvih jednadžbi, moći ćemo odrediti ključ. Postavlja se pitanje koliko parova otvoreni tekst-šifrat treba uzeti. Odgovor je otprilike |p - 0.5| -2 parova. Preciznije, Matsui je pokazao da ako uzmemo |p - 0.5| -2 parova, vjerojatnost uspjeha je 97.7%, dok je za 2|p - 0.5| -2 parova vjerojatnost uspjeha 99.8%.

Kao primjer navedimo jednadžbu

L0[3,8,14,25] ⊕ R0[17] ⊕ R3[3,8,14,25] ⊕ L3[17] = K1[26] ⊕ K3[26],

za koju je Matsui pokazao da vrijedi s vjerojatnošću 0.695.

Opišimo Matsuijevu konstrukciju. Za S-kutiju Sj, j = 1, 2, ..., 8, te cijele brojeve 0 ≤ α ≤ 63 i 0 ≤ β ≤ 15, definiramo

NSj(α, β) = |{ 0 ≤ x ≤ 63 : i (x[i] · α[i]) = i (Sj(x)[i] · β[i]) }|.

Ukoliko je NSj(α, β) ≠ 32, onda možemo reći da postoji neka korelacija između ulaznih i izlaznih podataka od kutije Sj. Možda bismo očekivali da će NSj(α, β) uvijek biti blizu 32. No, to nije točno. Jedan dosta drastičan primjer odstupanja je

NS5(16, 15)= |{ 2,7,10,14,16, 24,28,29,37,40,59,62 }| =12.

Tu je vjerojatnost podudaranja ulaznih i izlaznih podataka samo 12/64 = 0.1875, što je dosta daleko od 0.5. Ovdje se radi o vezi između 2. bita ulaznog podatka u S5-kutiju, te sva četiri izlazna bita iz te kutije (jer je α = 16 = 0100002, β = 15 = 11112). Ako uzmemo u obzir kako funkcija proširenja E proširuje ulazne podatke, te kako permutacija P raspoređuje izlazne podatke, dobivamo sljedeće jednadžbe:

R0[17] ⊕ K1[26] = f(R0,K1)[3,8,14,25] = L0[3,8,14,25] ⊕ R1[3,8,14,25],
R2[17] ⊕ K3[26] = f(R2,K3)[3,8,14,25] = L2[3,8,14,25] ⊕ R3[3,8,14,25].

Uzmemo li u obzir da je L2 = R1 i L3 = R2, iz ovih jednadžbi dobivamo upravo gore navedenu Matsuievu jednadžbu. Vjerojatnost da vrijedi Matsuieva jednadžba jednaka je zbroju vjerojatnosti da obje ove jednadžbe vrijede i vjerojatnosti da obje jednadžbe ne vrijede, a to je

0.18752 + (1 - 0.1875)2 ≈ 0.6953 .

Pomoću linearne kriptoanalize Matsui je opisao napad "poznati otvoreni tekst" koji za razbijanje DES-a treba u prosjeku 243 otvorenih tekstova. Ovaj napad je implementiran pomoću 12 radnih stanica i za otkrivanje ključa je trebalo 50 dana.


No, ni diferencijalna ni linearna kriptoanaliza nisu razbile DES, već su tu učinili brzi i jeftini čipovi. Naime, pokazalo se da je u praksi lakše napraviti napad "grubom silom" s 255 DES operacija, nego primijeniti napad linearnom kriptoanalizom koji zahtjeva 243 poznatih parova otvoreni tekst-šifrat.

U srpnju 1998., koristeći čipove i osobno računalo, Electronic Frontier Foundation je napravio "DES Cracker". Koštao je $250000, a za njegovu izradu je utrošeno godinu dana. DES Cracker je razbio poruku šifriranu DES-om za 56 sati. Sagrađen je od 1536 čipova koji mogu testirati 88 milijardi ključeva po sekundi. Inače, u samoj konstrukciji ovog stroja nema ništa osobito novo. Sličnih prijedloga bilo je i ranije, no EFF je prvi to sproveo u djelo i tek nakon izrade DES Crackera moglo se definitivno ustvrditi da se DES nije siguran kriptosustav.


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