Kriptoanaliza DES-a

[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 L₀R₀ uzeti za otvoreni tekst, a L_nR_n 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 L₀R₀ i L*₀R*₀ sa zadanom XOR vrijednošću L'₀R'₀ = L₀R₀ ⊕ L*₀R*₀.

Definicija: Neka je S_j neka S-kutija (1 ≤ j ≤ 8), te neka je (B_j, B*_j) uređeni par 6-bitnih nizova. Tada B_j ⊕ B*_j zovemo input XOR, a S_j (B_j) ⊕ S_j (B*_j) zovemo output XOR.
Za svaki B'_j ∈ (Z₂)⁶, sa Δ(B'_j) označavamo skup svih uređenih parova (B_j, B*_j) čiji je input XOR jednak B'_j.

Jasno je da vrijedi

Δ(B'_j) = { (B_j, B_j ⊕ B'_j) : B_j ∈ (Z₂)⁶ },

pa skup Δ(B'_j) sadrži 2⁶ = 64 para. Za svaki par iz Δ(B'_j) možemo izračunati output XOR. Dobivamo 64 output XOR-a koji su distribuirani između 2⁴ = 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 S₁ i input XOR 110100. Imamo

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

Za svaki uređeni par iz Δ(110100) izračunamo output XOR. Npr. S₁(000000) = 14₁₀ = 1110, S₁(110100) = 9₁₀ = 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
IN_j (B'_j, C'_j) = { B_j ∈ (Z₂)⁶ : S_j (B_j) ⊕ S_j (B_j ⊕ B'_j) = C'_j },

N_j (B'_j, C'_j) = | IN_j (B'_j, C'_j) |.

Dakle, N_j(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 N₁(110100, C'₁), C'₁ ∈ (Z₂)⁴, dok su skupovi IN₁(110100, C'₁) prikazani u sljedećoj tablici.

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

B ⊕ B* = (E ⊕ J) ⊕ (E* ⊕ J) = E ⊕ E*,

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 = B₁ B₂ B₃ B₄ B₅ B₆ B₇ B₈
        E = E₁ E₂ E₃ E₄ E₅ E₆ E₇ E₈
        J = J₁ J₂ J₃ J₄ J₅ J₆ J₇ J₈
        B* = B*₁B*₂B*₃B*₄B*₅B*₆B*₇B*₈
        E* = E*₁E*₂E*₃E*₄E*₅E*₆E*₇E*₈

Definicija: Neka su E_j i E*_j 6-bitni nizovi, a C'_j 4-bitni niz. Definiramo
test_j (E_j, E*_j, C'_j) = { B_j ⊕ E_j : B_j ∈ IN_j (E'_j, C'_j) },
gdje je E'_j = E_j ⊕ E*_j.

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

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

pa je

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

Tvrdnja 1: Neka je C'_j = S_j (B_j) ⊕ S_j (B*_j). Tada je J_j ∈ test_j (E_j, E*_j, C'_j).

Dokaz: Po definiciji treba provjeriti da je J_j ⊕ E_j ∈ IN_j (E'_j, C'_j). No, J_j ⊕ E_j = B_j i S_j (B_j) ⊕ S_j (B_j ⊕ B'_j) = S_j (B_j) ⊕ S_j (B*_j) = C'_j, pa je J_j ∈ test_j (E_j, E*_j, C'_j).

Tvrdnja 1 nam daje nekoliko mogućnosti za J_j. Primjenom Tvrdnja 1 na nekoliko različitih trojki E_j, E*_j, C'_j, možemo odrediti J_j. Jasno, ovdje je pretpostavka da mi te vrijednosti E_j, 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 L₀R₀, L*₀R*₀ koje smo odabrali tako da je R₀ = R*₀, tj. R'₀ = 00...0, te odgovarajućih šifrata L₃R₃, L*₃R*₃. Vrijedi:

R₃ = L₂ ⊕ f(R₂,K₃) = R₁ ⊕ f(R₂,K₃) = L₀ ⊕ f(R₀,K₁) ⊕ f(R₂,K₃),
R*₃ = L*₀ ⊕ f(R*₀,K₁) ⊕ f(R*₂,K₃),
R'₃ = L'₀ ⊕ f(R₂,K₃) ⊕ f(R*₂,K₃).

Sada je f(R₂,K₃) = P(C) i f(R*₂,K₃) = P(C*), gdje su C i C* outputi od S-kutija. Stoga je

P(C) ⊕ P(C*) = R'₃ ⊕ L'₀,

pa je

C' = C ⊕ C* = P^-1(R'₃ ⊕ L'₀).

Konačno, E = E(R₂) = E(L₃) i E* = E(R*₂) = E(L*₃). Dakle, E, E* i C' su nam poznati.

ALGORITAM:

Ulazni podatci: L₀R₀, L*₀R*₀, L₃R₃ i L*₃R*₃, gdje je R₀ = R*₀

Izračunamo: C' = P^-1(R'₃ ⊕ L'₀)
Izračunamo: E = E(L₃) i E* = E(L*₃)
Za j = 1, 2, ... , 8
računamo test_j (E_j, E*_j, C'_j).

Primjenom ovog algoritma na nekoliko različitih inputa možemo odrediti međuključ K₃, što nam daje 48 bitova ključa K. Preostalih 8 bitova možemo pronaći tako da testiramo svih 2⁸ = 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 R₀ = R^*₀):

  ------------------------------------------------- 
      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 J_j, j = 1, 2, ... , 8, konstruiramo brojač koji broji za koliko parova J_j zadovoljava uvjet iz Tvrdnje 1. Na primjer, u slučaju prvog para i brojača za J₁ imamo E'₁ = 101111, C'₁ = 1001. Nadalje je

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

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

J₁ ∈ test₁ (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 J₁, J₂, ... , J₈. Te pozicije su redom; 47, 5, 19, 0, 24, 7, 7, 49, odnosno binarno

J₁ = 101111
J₂ = 000101
J₃ = 010011
J₄ = 000000
J₅ = 011000
J₆ = 000111
J₇ = 000111
J₈ = 110001

Sada pogledamo kako izgleda raspored bitova ključa u međuključu K₃, 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 K₃. 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'₀ = 00...0. Ova ideja se može poopćiti.

Definicija 4: Neka je n prirodan broj. n-rundna karakteristika je niz oblika
L'₀, R'₀, L'₁, R'₁, p₁, ... , L'_n, R'_n, p_n
sa svojstvima:
(1) L'_i = R'_{i -1} za 1 ≤ i ≤ n,
(2) Neka je 1 ≤ i ≤ n, te neka su L_{i -1}, R_{i -1}, L*_{i -1}, R*_{i -1} izabrani tako da je L_{i -1} ⊕ L*_{i -1} = L'_{i -1} i R_{i -1} ⊕ R*_{i -1} = R'_{i -1}. Pretpostavimo da su L_i, R_i, L*_i, R*_i dobiveni primjenom jedne rudne DES-a. Tada je vjerojatnost da je L_i ⊕ L*_i = L'_i i R_i ⊕ R*_i = R'_i jednaka p_i.

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

L'₀ = prozvoljno, R'₀ = 00000000₁₆, L'₁ = R'₀, R'₁ = L'₀, p₁ = 1.

Jedna druga 1-rundna karakteristika je

L'₀ = 00000000₁₆, R'₀ = 60000000₁₆, L'₁ = R'₀, R'₁ = 00808200₁₆, p₁ = 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 2⁴⁷ 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 2⁵⁵, š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 2⁵⁶. Primijetimo da se taj broj može prepoloviti koristeći svojstvo e_K(x) = e_K(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 2¹⁴, 2²⁴, 2³¹, odnosno 2³⁹ 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[i₁,i₂,...,i_k] = A[i₁] ⊕ A[i₂] ⊕ ... ⊕ A[i_k].

Želimo naći linearne jednadžbe oblika

P[i₁,i₂,...,i_a] ⊕ C[j₁,j₂,...,j_b] = K[k₁,k₂,...,k_c]

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

L₀[3,8,14,25] ⊕ R₀[17] ⊕ R₃[3,8,14,25] ⊕ L₃[17] = K₁[26] ⊕ K₃[26],

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

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

NS_j(α, β) = |{ 0 ≤ x ≤ 63 : ⊕_i (x[i] · α[i]) = ⊕_i (S_j(x)[i] · β[i]) }|.

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

NS₅(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 S₅-kutiju, te sva četiri izlazna bita iz te kutije (jer je α = 16 = 010000₂, β = 15 = 1111₂). 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:

R₀[17] ⊕ K₁[26] = f(R₀,K₁)[3,8,14,25] = L₀[3,8,14,25] ⊕ R₁[3,8,14,25],
R₂[17] ⊕ K₃[26] = f(R₂,K₃)[3,8,14,25] = L₂[3,8,14,25] ⊕ R₃[3,8,14,25].

Uzmemo li u obzir da je L₂ = R₁ i L₃ = R₂, 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.1875² + (1 - 0.1875)² ≈ 0.6953 .

Pomoću linearne kriptoanalize Matsui je opisao napad "poznati otvoreni tekst" koji za razbijanje DES-a treba u prosjeku 2⁴³ 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 2⁵⁵ DES operacija, nego primijeniti napad linearnom kriptoanalizom koji zahtjeva 2⁴³ 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