SVEUČILIŠTE U ZAGREBU
FAKULTET ELEKTROTEHNIKE I RAČUNARSTVA









DIPLOMSKI RAD BR. 1698

NAPADI NA DES KRIPTOSUSTAV

Nikola Škorić









Zagreb, studeni, 2007







Sažetak

U ovom radu detaljno je opisan DES kriptoalgoritam. Opisani su napadi na simetrične kriptosustave a posebno diferencijalna i linearna kriptoanaliza te napad grubom silom. Utvrđeno je da je napad grubom silom jedini u praksi izvediv napad na DES. U praktičnom dijelu rada izvedene su tri implementacije DES kriptosustava: objektna, funkcijska i sklopovska implementacija. Svaka od ovih implementacija potom je korištena kako bi se razvio jednostavni sustav za napad na DES.

Abstract

In this paper DES cyrptalgorithm is described in detail. Attacks on symmetric cryptsystems are described, with emphasis on differential and linear cryptanalysis and brute force attack. It is established that brute force attack is the only feasible attack on DES. In practical part of this paper three implementations of DES cryptosystem are devised: object, functional and hardware implementation. Each of those implementations was then used to develop simple brute force attack on DES.

Sadržaj

1  Uvod
2  Data Encryption Standard
    2.1  Opis algoritma
        2.1.1  Feistel funkcija
        2.1.2  Generiranje podključeva
    2.2  Kriptoanaliza
        2.2.1  Neka kriptoanalitička svojstva
3  Kriptoanaliza simetričnih kriptosustava
    3.1  Vrste napada na simetrične kriptosustave
    3.2  Napad grubom silom
    3.3  Integralna kriptoanaliza
    3.4  Meet-in-the-Middle napad
    3.5  Diferencijalna kriptoanaliza
    3.6  Bumerang napad
        3.6.1  Inside-out napad
        3.6.2  Pojačani bumerang napad
    3.7  Slide napad
    3.8  Napad povezanim ključevima
        3.8.1  Bihamov napad povezanim ključem
        3.8.2  Diferencijalni napad povezanim ključem
    3.9  Linearna kriptoanaliza
    3.10  Kriptoanaliza razdjeljivanjem
        3.10.1  Mod n kriptoanaliza
    3.11  Daviesov napad
    3.12  XSL napad
4  Diferencijalna kriptoanaliza DES kriptosustava
    4.1  Opis napada
        4.1.1  Utvrđivanje diferencijalne karakteristike
        4.1.2  Utvrđivanje ključa
        4.1.3  Složenost napada
    4.2  Primjer: napad na DES od 3 runde
        4.2.1  Algoritam
        4.2.2  Kriptoanaliza
        4.2.3  Primjer
        4.2.4  Dodatno razmatranje
    4.3  Proširenja diferencijalne kriptoanalize
        4.3.1  Krnja diferencijalna kriptoanaliza
        4.3.2  Diferencijalna kriptoanaliza višeg reda
5  Linearna kriptoanaliza DES kriptosustava
    5.1  Opis napada
        5.1.1  Linearna karakteristika
        5.1.2  Piling-up lema
        5.1.3  Postojanje linearne karakteristike
        5.1.4  Utvrđivanje ključa
        5.1.5  Složenost napada
    5.2  Primjer: napad na DES od 3 runde
6  Napad grubom silom
    6.1  Složenost napada
    6.2  Neostvareni prijedlozi napada grubom silom
    6.3  RSA DES Challenge
        6.3.1  Prvi DES Challenge
        6.3.2  RSA DES Challenge II-1
        6.3.3  RSA DES Challenge II-2
        6.3.4  RSA DES Challenge III
    6.4  COPACOBANA
    6.5  Tajne implementacije
7  Praktični rad
    7.1  Testna okolina
    7.2  Funkcijska implementacija
        7.2.1  Brzina izvođenja
    7.3  Objektno orijentirana implementacija
        7.3.1  Brzina izvođenja
    7.4  Sklopovska implementacija
        7.4.1  Brzina izvođenja
    7.5  Zaključno razmatranje
8  Zaključak
9  Literatura

1  Uvod

Potreba za povjerljivošću komunikacije jedna je od osnovnih uvjeta opstanka ljudske civilizacije. Ljudskim bićima upravo je nepojmljiva društvena organizacija u kojoj bi svaka komunikacija bila potpuno otvorena i u kojoj ne bi postojala privatnost. Zbog tog razloga u računalnim znanostima bitno mjesto zauzima kriptografija.
Prvi algoritam za kriptiranje, koji je u cijelom svijetu prihvaćen kao standard, bio je Digital Encryption Standard - DES. Kao standard korišten je od 1977. do 2001. godine, dakle preko 20 godina. U svijetu računarstva, gdje je nestalnost pravilo, ovoliki radni vijek upravo je fascinantan. Kad je DES postao standard najpopularniji operativni sustav bio je Unix verzije 6, a u godini kada je DES zamijenjen AES-om izašao je Microsoft Windows XP. Dok je računarstvo prolazilo razdoblje golemih razlika, vjerojatno je samo DES ostao konstanta.
U tom razdoblju od preko 20 godina ovaj kriptoalgoritam je istraživan, napadan i analiziran na razne načine, no niti jedan od tih napada nije bio uspješan. Nakon silnih godina sa trona ga je srušilo - vrijeme. DES nije uspio odoljeti napretku tehnologije koja raste eksponencijalno s vremenom. Godine 1977. Intelov najbolji procesor bio je 8-bitni 8085 sa frekvencijom rada od 3 MHz. Godine 2001. aktualan je bio Pentium 4 sa četiri puta širom sabirnicom i tisuću puta višom frekvencijom rada. Moderna računala postala su odviše brza da bi se DES mogao mjeriti s njima i DES-a je oborio jedini napad protiv kojeg nema obrane: napad grubom silom.
Upravo ta postojanost označava DES kao jedan od najbitnijih algoritama uopće. Njegovo proučavanje može nam donijeti mnoga korisna saznanja o kriptografiji i računarstvu uopće.
U ovom radu opisani su napori uloženi da se DES uspješno napadne. Prvo iznosimo opis algoritma, a zatim ukratko opisujemo napade na DES-u slične kriptoalgoritme: na simetrične kriptosustave. Potom slijede detaljni opisi tri napada relevantna za DES: diferencijalna kriptoanaliza, linearna kriptoanaliza i napad grubom silom. Na samom kraju iznesen je opis praktičnog pokušaja da se DES napadne grubom silom. Napad na DES ostvaren je u jezicima C# (kao predstavniku objektne paradigme), Common Lisp (kao predstavniku funkcijske paradigme) i VHDL (kao predstavniku jezika za oblikovanje sklopovlja). Zaključak ukratko sažima rezultate ovog rada i ukazuje na razloge zbog kojih je DES zamijenjen kao standard u računarstvu.

2  Data Encryption Standard

Data Encryption Standard (u daljem tekstu DES) jest algoritam za kriptiranje podataka. Osmislilo ga je tim IBM-ovih stručnjaka periodu od 1973. do 1974. godine i od svojeg prihvaćanja kao službenog standarda postao je najkorišteniji javno dostupni kriptoalgoritam u 20. stoljeću.
U ranim 1970-im godinama IBM-u se obratio klijent iz područja bankarstva i tražio IBM da razvije sustav za kriptiranje podataka za bankomate. IBM je formirao tim koji je, na čelu sa Horstom Feistelom, razvio kriptoalgoritam "Lucifer".[7]
Godine 1973. tadašnji National Bureau of Standards (danas National Institute of Standards and Technology - NIST) objavio je informaciju da prima prijedloge za kriptoalgoritam koji bi zadovoljavao vrlo stroge kriterije koje je NIST sastavio u suradnji sa National Security Agency (NSA). IBM je na natječaj poslao algoritam "Lucifer". Nakon detaljne analize zaprimljenih kandidata, niti jedan nije izabran kao dovoljno siguran. Novi natječaj objavljen je 1974. i ovaj put je tvrtka IBM predložila kriptoalgoritam koji je bio prihvatljiv.
Nakon godinu dana javne rasprave i radionica na kojima se algoritam analizirao, 15. siječnja 1977. DES je potvrđen kao Federal Information Processing Standard za kriptiranje podataka koji nisu tajni (FIPS PUB 46). Time je taj algoritam postao standardni algoritam u cijelom svijetu, da bi tek 2001. bio zamijenjen s algoritmom Advanced Encryption Standard (AES) kao novim standardom. Radni vijek od 25 godina čini DES jednim od najkorištenijih algoritama u povijesti računarstva i definitivno najbitnijim algoritmom u povijesti kriptografije.

2.1  Opis algoritma

Slika 2.1: Ilustracija DES algoritma
DES spada u vrstu blokovnih šifri. To znači da se podatci primaju u blokovima određene veličine, u slučaju DES-a to je 64 bita. Dakle, DES prima 64 bita ulaznih podataka i 64 bita ključa, obavlja niz kompliciranih operacija koristeći te ulazne, podatke a na izlazu daje 64 bita izlaznih podataka. Važno je napomenuti to da se od 64 bita ključa koristi samo 56 bita, dok su ostalih 8 bitova paritetni bitovi (po jedan paritetni bit na svaki byte ključa).
Nad ulaznim podacima obavljaju se 3 operacije: inicijalna permutacija IP, zatim 16 Feistel rundi te na kraju finalna permutacija FP.
Inicijalna permutacija prima 64 bitni ulazni podatak, permutira ga te ga razbija na dva 32-bitna dijela. Ti dijelovi zatim prolaze kroz 16 Feistel rundi koje imaju sljedeći oblik:
Nakon što se obavi 16 ovakvih rundi, krajnja dva 32-bitna podatka se zatim grupiraju u jedan 64-bitni podatak nad kojim se zatim obavlja finalna permutacija. Izlaz iz finalne permutacije ujedno je i izlaz iz algoritma.

2.1.1  Feistel funkcija

Slika 2.2: Ilustracija Feistel funkcije
U gornjem opisu algoritma navedeno je da se nad desnom polovicom podatka obavlja Feistel funkcija čiji se izlaz zatim XOR-a sa lijevom polovicom podatka. Feistel funkcija je srce DES algoritma.
Kao što je gore opisano, Feistel funkcija kao ulaz prima 32 bita. Osim tog podatka, koristi se još i podključ, čije će formiranje kasnije biti opisano.
Nad ulaznih 32 bita podatka prvo se obavlja ekspanzija i dobiva se 48-bitni podatak. Nad tim podatkom zatim se obavlja XOR operacija sa podključem. Tako dobiveni podatak zatim prolazi operaciju supstitucije u S-kutijama.
48 bita podatka rastavlja se na 8 skupina od po 6 bita. Svaka skupina zatim prolazi identičnu transformaciju. Prvi i zadnji bit određuju vrijednost retka, a 2, 3, 4. i 5. bit određuju vrijednost stupca. Polje u stupcu i retku S-kutije, koje je određeno bitovima ulaza, postaje izlaz.
Ilustracija primjerom: ulazni podatak neka je 011011. Vrijednost retka je 01, a vrijednost stupca je 1101. Recimo da taj podatak ulazi u petu S-kutiju. Kao što se vidi na slici 2.1., izlazni podatak je 1001.
Tablica 2.1: Binarni prikaz kutije S5
Tablica 2.2: Prikaz kutije S5
0123456789101112131415
02124171011685315130149
11411212471315015103986
24211110137815912563014
31181271142136150910453
Na ovaj način 8 puta po 6 bita se pretvara u 8 puta po 4 bita, što opet daje 32-bitni podatak. Taj podatak se zatim još jednom permutira. Tako permutirana 32 bita čine izlaz Feistel funkcije.

2.1.2  Generiranje podključeva

Slika 2.3: Postupak generiranja podključeva
Kao što je u gornjem tekstu opisano, u Feistel funkciji koristi se 48-bitni podključ. Taj podključ je za svaku rundu drugačiji, stoga je potrebno generirati 16 različitih podključeva. Podključevi se generiraju iz ključa koji je jedan od dva ulazna podatka u algoritam.
Od 64 bita ključa, njih 8 su paritetni bitovi. Stoga ključ prvo prolazi permutaciju koja od ulaznih 64 bita vraća 56 bita u obliku dvije 28-bitne polovice. Ti bitovi zatim 16 puta prolaze kroz sljedeći algoritam:
Ovako dobivenih 16 podključeva zatim se koristi u Feistel funkciji, kako je ranije opisano.

2.2  Kriptoanaliza

Ovako opisani algoritam je u uporabi kao standard od 1977. Sve do 1987. jedini poznati napad na DES bio je napad grubom silom. Tek te godine Donald Davies otkriva neka statistička svojstva DES algoritma koja bi (teoretski) mogla dovesti do pribavljanja ključa, uz trud manji nego to zahtjeva napad grubom silom. Davies napad objavljuje 1993, a iste godine Mitsuru Matsui objavljuje vlastiti napad: linearnu kriptoanalizu. Tri godine ranije, još 1990. Eli Biham i Adi Shamir objavljuju diferencijalnu kriptoanalizu. Dakle, od 1976. pa sve do 1990. nije bio javno poznat niti jedan napad na DES koji bi otkrio ključ brže od napada grubom silom.
Početkom devedesetih godina 20. stoljeća dolazi do naglog razvoja kriptoanalize i središnja tema ovog diplomskog rada su dva najuspješnija i najpoznatija rezultata tog razvoja: diferencijalna i linearna kriptoanaliza.

2.2.1   Neka kriptoanalitička svojstva

DES ima neka svojstva koja su bitna pri kriptoanalizi ovog algoritma.
Prvo takvo svojstvo postojanje je "slabih ključeva" (engl. weak keys). Slabi ključevi su takvi ključevi koji dvostrukim kriptiranjem čistog teksta daju opet taj čisti tekst (dakle: DES(DES(P, K),K) = P). Razlog tome je činjenica da slabi ključevi generiraju 16 identičnih podključeva za 16 rundi DES-a. Popis slabih ključeva dan je u tablici .
Tablica 2.3: Slabi ključevi
00000000000000
FFFFFFFFFFFFFF
0000000FFFFFFF
FFFFFFF0000000
Osim slabih ključeva postoje i poluslabi ključevi. Ti ključevi proizvode samo dva podključa i koriste ih naizmjenično, što znači to da, ako se čisti tekst kriptira prvo jednim takvim ključem, pa drugim takvim ključem, dobiva se opet isti čisti tekst (dakle: DES(DES(P, K1),K2) = P. Postoji 6 takvih parova i dani su u tablici  .
Tablica 2.4: Poluslabi ključevi
011F011F010E010E i 1F011F010E010E01
01E001E001F101F1 i E001E001F101F101
01FE01FE01FE01FE i FE01FE01FE01FE01
1FE01FE00EF10EF1 i E01FE01FF10EF10E
1FFE1FFE0EFE0EFE i FE1FFE1FFE0EFE0E
E0FEE0FEF1FEF1FE i FEE0FEE0FEF1FEF1
Treće bitno svojstvo DES-a je svojstvo komplementarnosti:

DES(P, K) = C ⇔ DES(
P
 
 ,
K
 
 ) =
C
 
(2.1)
gdje je [(X)] komplement od X. Ovo svojstvo može se iskoristiti za ubrzanje napada grubom silom za faktor 2 [4] i stoga je detaljno obrađen u poglavlju o napadu grubom silom (poglavlje  6.1.).
Posljednje svojstvo DES kriptoalgoritma koje će biti razmatrano jest pitanje je li DES grupa[6]. Grupa je algebarska struktura koja (između ostalog) ima svojstvo zatvorenosti. To znači, ako su čisti tekst P i ključ K elementi skupa G, tada je i kriptirani tekst T = DES(P, K) također element skupa G.
Pitanje je li DES grupa izrazito je bitno obzirom na to je li odgovor potvrdan. Ako jest, DES bi se mogao razbiti sa prosječno svega 228 čistih tekstova. Osim toga, višestruka enkripcija ne bi povećavala sigurnost DES-a, obzirom na to da bi se za svaka dva ključa K1 i K2 mogao naći takav ključ K za koji vrijedi DES(DES(P, K1),K2) = DES(P, K).
Godine 1988. grupa autora objavila je rad [17] u kojem su eksperimentalno pokazali da DES vrlo vjerojatno nije grupa, no nisu tu tezu uspjeli formalno dokazati. Tek pet godina kasnije Keith W. Campbell and Michael J. Wiener u radu [6] formalno dokazuju da DES nije grupa.

3  Kriptoanaliza simetričnih kriptosustava

Prije razmatranja napada na DES kriptosustav, ukratko će biti opisani napadi na kriptosustave srodne DES-u. DES je simetrični kriptosustav i kao takav s ostalim simetričnim kriptosustavima dijeli mnoga svojstva. Stoga, prije napada na DES kriptosustav, razmotrit će se napadi na simetrične kriptosustave općenito.

3.1  Vrste napada na simetrične kriptosustave

Simetrični kriptosustavi su kriptosustavi kod kojih su isti ključ za kriptiranje i za dekriptiranje. To znači da stranke uključene u razmjenu kriptiranih podataka trebaju raspolagati istim tajnim ključem kako bi uspješno kriptirali i dekriptirali podatke.
Simetrični kriptosustavi trenutno su najpopularniji način tajnog prenošenja veće količine podataka, te je stoga kriptoanaliza simetričnih kriptosustava izrazito bitno područje modernog računarstva.
U modernoj kriptografiji najčešće se poštuje Kerckhoffsov princip koji kaže: "Kriptosustav bi trebao biti siguran i u slučaju da su sve informacije o sustavu (osim ključa) javno poznate" [34]. Stoga se pri kriptoanalizi podrazumijeva da je algoritam koji se kriptoanalizira u potpunosti poznat i potrebno je otkriti samo ključ kako bi se neki kriptirani tekst mogao pročitati.
Obzirom na to da je kriptoalgoritam poznat, jedini materijali koji su neophodni za kriptoanalizu su čisti i kriptirani tekst (pretpostavlja se da je ključ u svakom slučaju nepoznat jer inače ne bi bilo potrebe za kriptoanalizom). Stoga se metode kriptoanalize simetričnih kriptosustava (napadi na kriptosustave) dijele prema podacima koji su dostupni prije napada:[33]
Napadi su poredani uzlazno - po težini pribavljanja potrebnih materijala i silazno - po težini izvođenja. Najlakše je izvesti napad s odabranim čistim tekstom, no u praksi je gotovo nemoguć odabir parova čisti tekst - kriptirani tekst. U praksi su kriptirani tekstovi najdostupniji, no zato je napad s poznatim kriptiranim tekstom najteže izvesti.
Tri glavne metode kriptoanalize simetričnih kriptosustava su: napad grubom silom, diferencijalna kriptoanaliza i linearna kriptoanaliza. Uz te tri metode kriptoanalitičari su razvili razne druge napade koji su mnogo manje općeniti jer najčešće iskorištavaju neko svojstvo algoritma koje se javlja samo kod nekih algoritama. Uz to, postoje i metode koje su proširene verzije diferencijalne i linearne kriptoanalize, ali daju slabije rezultate. Neki od tih ostalih napada su: integralna kriptoanaliza, bumerang napad, slide napad, napad povezanim ključevima, kriptoanaliza razdjeljivanjem, Daviesov napad, XSL napad.
U ovom poglavlju slijedi kratki opisi svakog od navedenih napada, a u kasnijim poglavljima slijedi detaljni opis napada grubom silom, diferencijalne i linearne kriptoanalize na primjeru DES kriptoalgoritma.

3.2  Napad grubom silom

Napad grubom silom najjednostavnija je vrsta napada na kriptosustav i koristi se kao referentna točka pri utvrđivanju uspješnosti nekog kriptoanalitičkog napada. Ukoliko je neki napad u stanju pribaviti ključ u manjem vremenu i uz manje podataka nego napad grubom silom, onda se taj algoritam smatra razbijenim.
Napad grubom silom funkcionira tako da isprobava svaki mogući ključ kako bi otkrio čisti tekst poruke. To znači da napad grubom silom može biti napad poznatim kriptiranim tekstom ili napad poznatim čistim tekstom. U slučaju napada poznatim čistim tekstom, metoda napada grubom silom svodi se na isprobavanje velike količine ključeva (u najgorem slučaju svih ključeva) kako bi se kriptirani tekst dekriptirao u pripadni čisti tekst. Kako bi napad poznatim kriptiranim tekstom bio moguć, potrebno je poznavati neka svojstva čistog teksta. Primjerice, ako je poznato da je čisti tekst poruka koja je napisana ASCII znakovima na engleskom jeziku, onda je moguće provesti napad grubom silom poznatim kriptiranim tekstom obzirom na to da je izrazito malena vjerojatnost da se od istog kriptiranog teksta dobije dva smislena engleska teksta.
Obzirom na to da je napad grubom silom jedan od 3 najbitnija napada na DES kriptosustav, detaljno će biti razmotren u kasnijim poglavljima.

3.3  Integralna kriptoanaliza

Integralnu kriptoanalizu razvio je Lars Knudsen kao napad na Square kriptosustav.
Square kriptosustav razvili su autori AES (Rijndael) kriptosustava i objavili ga 1997. Iz tog sustava kasnije se i razvio sam AES. U članku u kojem su autori objavili strukturu Square algoritma nalazila se i kriptoanaliza tog sustava. Uz diferencijalnu i linearnu kriptoanalizu, Square kriptosustav napadnut je i novom vrstom napada osmišljenom kako bi pokazala snagu tog kriptosustava. Stoga se taj napad ponekad naziva i Square napad.[9]
Napad je osmislio Lars Knudsen, suradnik autora Square kriptosustava i pokazao da je verzija Square kriptosustava od 6 Feistel rundi ranjiva na taj napad (napad je efikasniji od napada grubom silom), ali da potpuna verzija od 8 rundi nije ranjiva.
Za napad je potrebno 256 parova čisti tekst - kriptirani tekst. Čisti tekstovi trebaju biti tako odabrani da jedan bajt poprima sve moguće vrijednosti, dok su svi ostali bajtovi svih 256 čistih tekstova jednaki. Dakle, radi se o napadu odabranim čistim tekstom.[22]
Stefan Lucks je 2000. na primjeru napada na Twofish algoritam prikazao saturation attack koji je u biti proširenje i generalizacija integralne kriptoanalize.[26]

3.4  Meet-in-the-Middle napad

W. Diffie i M. Hellman 1977. u radu [11] objavljuju Meet-in-the-Middle napad. Ovaj napad bio je odgovor na prijedloge nekih kriptografa da se sigurnost DES-a može povećati ukoliko se nakon prvotne enkripcije DES-om obavi još jedna sa različitim ključem, čime je efektivno ključ povećan sa 56 na 112 bita. Ovakvo povećanje kvadriralo bi prostor ključeva i onemogućilo napad grubom silom. Diffie i Hellman u svom radu pokazuju da dvije enkripcije za redom ne dovode do kvadriranja prostor ključeva.
Ovaj napad pokušava pronaći jednaku vrijednost u kodomeni i domeni dviju funkcija koje kompozicijom čine originalni kriptoalgoritam. Dakle, ukoliko se kriptoalgoritam može opisati kao:
C = E(P, K)=E(E(P, K1), K2)
(3.2)
tada napad pokušava pronaći vrijednost M za koju vrijede izrazi:
E(P, K1) = M1
(3.3)
E−1(C, K2) = M2
(3.4)
M1 = M2 = M.
(3.5)
Napad koji su razvili Diffie i Hellman započinje izračunom svih mogućih vrijednosti M1 koristeći sve moguće vrijednosti ključa K1. Zatim se obavlja dekripcija kriptiranog teksta koristeći sve moguće vrijednosti ključa K2. Kada se dekripcija M2 poklopi sa M1, pronađeni su ključevi enkripcije.
Prva polovica ovog algoritma obavlja 2N enkripcija (gdje je N broj bitova ključa), a druga polovica u prosjeku [1/2]*2N, a u najgorem slučaju 2N enkripcija. Ukupno je to u prosjeku 1,5*2N enkripcija, a u najgorem slučaju 2N+1 enkripcija. Dakle, dvostruka enkripcija DES-om ne kvadrira vrijeme potrebno za pretragu prostora ključeva, nego ga prosječno povećava samo za faktor 1,5.

3.5  Diferencijalna kriptoanaliza

Diferencijalna kriptoanaliza (uz linearnu kriptoanalizu) jedna je od dva najpopularnija kriptoanalitička napada. Godine 1974. otkrili su ga dizajneri DES-a (iz tvrtke IBM) tijekom razvoja algoritma i nazvali T-attack, što je vjerojatno skraćenica od Tickle Attack. Analitičari NSA za ovaj napad vrlo vjerojatno znali su čak i prije zaposlenika IBM-a, no obje grupacije tajile su svoje otkriće obzirom na to da je NSA prezentiranje diferencijalne kriptoanalize smatrala prijetnjom nacionalnoj sigurnosti SAD-a.
Prvi su diferencijalnu kriptoanalizu javno "otkrili" Eli Biham i Adi Shamir krajem osamdesetih godina prošlog stoljeća i objavili ju 1990. u radu [4]. Stoga ne čudi da su gotovo svi simetrični kriptoalgoritmi više ili manje neotporni na diferencijalnu kriptoanalizu (primjerice, originalna verzija FEAL-a koja je imala 4 runde može se razbiti sa svega 8 odabranih čistih tekstova), dok je DES dizajniran tako da bude otporan na diferencijalnu kriptoanalizu. Unatoč tome, DES sa manje rundi od standardnog DES-a nije otporan na taj napad i broj parova čisti-kriptirani tekst potrebnih za razbijanje algoritma opada sa brojem rundi. Obzirom na to da je taj napad statistički, ne postoji čvrsta korelacija između broja rundi i broja parova potrebnih za razbijanje, ali se pokazuje da je za razbijanje DES-a od 3 runde, u većini slučajeva, dovoljno 6 odabranih parova čistih i kriptiranih tekstova.
U ovom kratkom pregledu kriptoanalitičkih napada na simetrične kriptosustave diferencijalna kriptoanaliza neće biti detaljno razmatrana, već će istoj pažnja biti posvećena u narednim poglavljima.

3.6  Bumerang napad

Bumerang napad predložio je 1999. David Wagner. Taj napad nastao je kao proširenje diferencijalne kriptoanalize i Wagner opisuje napad na COCONUT98 kriptoalgoritam koji je otporan na klasičnu diferencijalnu kriptoanalizu. Osim toga, on u kratkim crtama opisuje napade i na još neke algoritme koji su inače otporni na diferencijalnu kriptoanalizu: Khufu-16, FEAL-6 i CAST-256 od 16 rundi.[31]
Diferencijalna kriptoanaliza koristi diferencijalne karakteristike kriptoalgoritma kako bi povezala ulaz i izlaz iz algoritma. Svi noviji kriptoalgoritmi konstruirani su tako da ne postoje nikakvi diferencijali koji povezuju ulaz i izlaz kriptoalgoritma. No, dijelovi algoritma ponekad pokazuju diferencijalne karakteristike i bumerang napad koristi upravo te diferencijale: karakteristike koje se javljaju unutar algoritma, a ne mogu se zamijetiti izvana.
Bumerang napad diferencijalni je napad koji pokušava generirati četveročlanu strukturu na pola puta kroz kriptoalgoritam. Napad promatra 4 čista teksta P, P′, Q, Q′ zajedno sa njihovim kriptiranim tekstovima `C, C′, D, D′. To znači da bumerang napad spada u klasu odabrani čisti tekst/prilagodljivi odabrani kriptirani tekst (engl. chosen-plaintext/adaptive chosen-ciphertext attack). Odabrani kriptirani tekst je "prilagodljiv" jer se par D,D′ bira na osnovu kriptiranog para C, C′.
Slijedi prikaz tog napada. Oznaka E predstavlja operaciju enkripcije pa se kriptoalgoritam može rastaviti na dva dijela E0 i E1: E = E1 °E0, gdje je E0 prvi dio kriptoalgoritma, a E1 drugi dio. E1−1 je onda inverzni algoritam od E1. Diferencijalna karakteristika od E0 označena je sa ∆* → ∆, a diferencijalna karakteristika od E1−1 označena je sa ∇→ ∇*.
Slika 3.4: Ilustracija bumerang napada
Cilj napada je prekriti par P, P′ sa karakteristikom za E0 i prekriti parove P, Q i P′, Q′ sa karakteristikom za E1−1. Wagner iznosi dokaz da u tom slučaju par Q, Q′ pokazuje karakteristiku ∆* → ∆ za E0−1.
Napad slijedi ovako:
  1. Kao ulaz za E0 izabran je par P, P′ takav da vrijedi P ⊕P′ = ∆.
  2. Kao izlaz iz E0 dobiva se par tekstova M, M′ koji imaju odnos M ⊕M′ = ∆*. Taj par je ujedno i ulaz za E1, a kao izlaz dobiva se par C, C′ koji nema nikakav diferencijalni odnos.
  3. Kao ulaz u E1−1 uzima se par D, D′ koji je dobiven koristeći diferencijal ∇: D = C ⊕∇, D′ = C′⊕∇.
  4. Kao izlaz iz E1−1 dobiva se par N, N′ za koji vrijedi N ⊕M = ∇* i N′⊕M′ = ∇*.
  5. Iz M ⊕M′ = ∆*, M ⊕N = ∇* i M′⊕N′ = ∇* slijedi N ⊕N′ = ∆*.
  6. Provede li se sada E0 na paru N, N′, zbog N ⊕N′ = ∆* dobiva se par Q, Q′ za koji vrijedi Q ⊕Q′ = ∆*.

3.6.1  Inside-out napad

U istom radu u kojem je predložio bumerang napad, Wagner predlaže i inside-out napad (engl. inside-out attack) [31]. Taj je napad u biti komplement bumerang napadu. Dok bumerang napad djeluje izvana, inside-out napad djeluje iznutra prema van.
U inside-out napadu traže se parovi čisti - kriptirani tekst koji imaju željenu diferenciju ∆ prema međuvrijednosti na polovici kriptoalgoritma (nakon polovice obavljenih Feistel rundi). Ukoliko za parove vrijede diferencijali ∆→∆′ (za E1) i ∆→ ∆* (za E0−1), mogu se u paru čisti - kriptirani tekst prepoznati razlike ∆* i ∆′. Ako je prikupljeno dovoljno parova sa razlikom ∆* na polovici kriptoalgoritma, trebao bi se pojaviti najmanje jedan par za koji vrijede oba diferencijala.

3.6.2  Pojačani bumerang napad

Slika 3.5: Ilustracija pojačanog bumerang napada
Na temelju Wagnerovog rada na bumerang napadu, 2000. John Kelsey, Tadayoshi Kohno i Bruce Schneier predlažu novi napad koji nazivaju pojačani bumerang napad (engl. amplifed boomerang attack).[18]
Bumerang napad spada u klasu odabrani čisti tekst/prilagodljivi odabrani kriptirani tekst, što je poprilično zahtjevan i nepraktičan napad. Autori stoga kombiniraju bumerang napad i inside-out napad da bi smanjili zahtjeve i dobili napad odabranim čistim tekstom.
Slijedi opis napada na 128-bitni kriptoalgoritam. Zatraži se 256 nasumično odabranih parova čistog teksta X2i, X2i+1, takvih da vrijedi X2i ⊕X2i+1 = ∆0. Kriptiraju li se ti parovi, dobiva se 256 parova Y2i, Y2i+1, takvih da vrijedi Y2i⊕Y2i+1 = ∆1. Zbog rođendanskog paradoksa očekuju se otprilike 2 para (i, j), takva da vrijedi Y2i ⊕Y2i+1 = ∆0. Nakon pribavljanja takvog para (i, j) koristi se bumerang efekt:

Y2i ⊕Y2i+1 = ∆1
(3.6)
Y2j ⊕Y2j+1 = ∆1
(3.7)
Y2i ⊕Y2j = ∆0
(3.8)
iz toga slijedi:
Y2i+1 ⊕Y2j+1 = ∆0
(3.9)
i na kraju:
Z2i ⊕Z2j = ∆1
(3.10)
Z2i+1 ⊕Z2j+1 = ∆1
(3.11)
Autori su ovaj napad nazvali pojačani bumerang napad jer bumerang struktura pojačava efekt događaja Y2i ⊕Y2j = ∆0, koji je inače malo vjerojatan, do razine da lako može biti detektiran.
Ovaj napad autori su uspješno primijenili na MARS algoritam od 11 rundi i Serpent algoritam od 8 rundi.

3.7  Slide napad

Slide napad objavili su 1999. Alex Biryukov i David Wagner. Napad je inspiriran vjerovanjem mnogih kriptografa da sigurnost kriptoalgoritma raste s brojem Feistel rundi koji algoritam ima. Autori su stoga osmislili napad odabranim čistim tekstom koji je u mnogim slučajevima nezavisan od broja rundi koje kriptoalgoritam ima.[5]
Povećanje broja rundi kriptoalgoritma otežava diferencijalnu kriptoanalizu algoritma, na što najbolje ukazuje činjenica da je DES od 6 rundi ranjiv na diferencijalnu kriptoanalizu, dok puni DES od 16 rundi to nije. Umjesto da se analizira način na koji algoritam randomizira ulazne bitove, slide napad analizira slabosti načina na koji algoritam raspoređuje podključeve. Najčešća slabost takve vrste jest cikličko ponavljanje podključeva.
Prvi napad ove vrste opisali su 1977. Edna Grossman i Bryant Tuckerman. Oni su osmislili i analizirali kriptoalgoritam kojem su svi ključevi jednaki, dakle ciklus ponavljanja ključeva dugačak je svega jedan ključ. Taj napad bio je preteča modernog slide napada i autori slide napada se pozivaju na Grossman-Tuckermanove rezultate.
Napad funkcionira tako da se algoritam podjeli na dijelove koji se mogu predstaviti identičnim permutacijskim funkcijama F. Funkcija F može se sastojati od više rundi algoritma; broj rundi algoritma koje ulaze u funkciju F određen je načinom na koji algoritam raspoređuje podključeve. Funkcija F se ponaša kao Feistel runda sa fiksiranim ključem. Obzirom na to da je ključ fiksiran, funkcija F djeluje kao obična permutacija.
Nakon što se runde algoritma podjele na nekoliko uzastopnih funkcija F, promatraju se dva algoritma od kojih je jedan u odnosu na drugog pomaknut (engl. slid) za jednu F funkciju (vidjeti sliku  3.3.).
Slika 3.6: Ilustracija slide napada
Ulaz u prvi niz F funkcija označi se sa X0, a ulaz u drugi niz funkcija sa X′0. Očito je da ako je X1 = X′0, onda je i Xr = X′r−1. Iz toga slijedi Xj+1 = F(Xj) = F(X′j−1) = X′j. Zatim se izabire par čisti - kriptirani tekst (P, C) i takav par (P', C') da vrijedi F(P)=P′ i F(C)=C. Takav par parova naziva se "pomaknuti par" (engl. "slid pair"). Ukoliko napadač pribavi 2n/2 parova čisti - kriptirani tekst, zbog rođendanskog paradoksa će dobiti jedan "pomaknuti par". Nakon što pribavi "pomaknuti par", napadač lako otkriva neke bitove podključeva, a ako je funkcija F relativno slaba, čak i cijeli ključ.

3.8  Napad povezanim ključevima

Napad povezanim ključevima (engl. Related-key attack) moguć je kada su napadaču dostupni parovi čistog i kriptiranog teksta koji su nastali korištenjem različitih ključeva među kojima postoji neka matematička veza. Primjerice, napadač može posjedovati parove koji su nastali korištenjem različitih ključeva koji imaju neke bitove jednake. Ovaj napad je nezavisan od broja Feistel rundi koje kriptoalgoritam ima.
Prvi opis ovakve vrste napada dao je Eli Biham 1994. [2], a njegov rad znatno su proširili John Kelsey, Bruce Schneier i David Wagner u svom radu 1996.[19]

3.8.1  Bihamov napad povezanim ključem

Biham razlikuje dvije vrste napada povezanim ključem:
Bitno je naglasiti da napadač ne poznaje ključeve kojima su parovi kriptirani, već samo njihovu vezu. Ovaj preduvjet se na prvi pogled može činiti besmislen u praski, no neki moderni kriptosustavi ponekad imaju loše dizajniran algoritam generiranja glavnih ključeva, što dovodi do toga da postoji matematička veza između dva glavna ključa kojim se kriptiraju dva različita čista teksta.
Biham opisuje bit napada povezanim ključevima ovako: ako su algoritmi za dobivanje podključeva u različitim rundama isti, onda, poznavajući ključ, svi podključevi mogu se pomaknuti jednu rundu unatrag. Tako je dobiven novi niz valjanih podključeva koji mogu biti dobiveni iz nekog drugog ključa. Takva dva ključa (čiji su podključevi pomaknuti za jednu rundu) nazivaju se povezanim ključevima.
Biham je ovaj napad uspješno primijenio na LOKI i Lucifer algoritme. Autor tvrdi da napad odabranim povezanim ključevima i odabranim čistim tekstom na Lucifer algoritam traje svega nekoliko sekundi na osobnom računalu (radi se o godini 1994!). U svom radu autor iznosi detaljan opis napada na LOKI89 i LOKI91.
No, DES se pokazao otpornim na napad povezanim ključevima obzirom na to da algoritam dobivanja podključa nije jednak za sve runde: u rundama 1, 2, 9 i 16 podključ se dobiva posmakom za jedno mjesto, a u ostalima posmakom za dva mjesta. Biham je također utvrdio i da su algoritmi IDEA i FEAL otporni na ovaj napad.

3.8.2  Diferencijalni napad povezanim ključem

John Kelsey, Bruce Schneier i David Wagner 1996. proširuju Bihamov rad i u napad povezanim ključem uvode metodologiju diferencijalne kriptoanalize. Kao motivaciju za daljnje istraživanje napada povezanim ključem autori navode dva primjera:
Ideja diferencijalnog napada povezanim ključem (engl. differential related-key attack) bliska je ideji diferencijalne kriptoanalize: kriptiraju se dva čista teksta P i P⊕∆ različitim ključevima K i K⊕∆K. Tako su dobiveni parovi čisti - kriptirani tekst (P, C) i (P⊕∆,C′) za koje vrijedi C=F(P,K) i C′=F(P⊕∆,K⊕∆K). Ovime se bitno proširuje područje djelovanja kako diferencijalne kriptoanalize, tako i napada povezanim ključem.

3.9  Linearna kriptoanaliza

Linearnu kriptoanalizu otkrio je 1993. Mitsuru Matsui [27]. Ovaj napad pokušava iskoristiti prednost visoko vjerojatnih linearnih izraza koji uključuju bitove čistog teksta, bitove kriptiranog teksta i bitove podključeva. Linearna kriptoanaliza je napad poznatim čistim tekstom, dakle napadač raspolaže nasumično odabranim parovima čistog i kriptiranog teksta.
Matsui je ovakav napad primijenio na FEAL-4 i dobio ključ sa svega 5 parova čisti - kriptirani tekst, dok linearna kriptoanaliza DES-a zahtjeva 243 parova. Detaljan opis linearne kriptoanalize slijedi u narednim poglavljima.

3.10  Kriptoanaliza razdjeljivanjem

Kriptoanalizu razdjeljivanjem (engl. Partitioning cryptanalysis) razvio je 1995. Carlo Harpes pod nazivom "Napad generalizacijom linearne kriptoanalize" (engl. Attack by the Generalization of Linear Cryptanalysis). Linearnu kriptoanalizu je generalizirao tako što je linearne izraze zamijenio sa I/O sumama. I/O suma je XOR (suma) uravnotežene (engl. balanced) binarne funkcije ulaza u Feistel rundu (input funkcije) i uravnotežene binarne funkcije izlaza iz runde (output funkcije).[14]
Harpes koristi sumu prvih r-1 rundi kako bi dobio podključ posljednje runde. Za taj napad potrebno mu je stanoviti broj parova čisti - kriptirani tekst (broj parova nije fiksiran, kao i kod linearne kriptoanalize) takvih da su čisti tekstovi nasumično izabrani. Napad se izvodi tako da se za svaki par čisti - kriptirani tekst računa imbalans (engl. imbalance) I/O funkcije za svaki mogući podključ zadnje runde. Time se dobivaju najvjerojatniji podključevi zadnje runde. Ponavljanjem ovog postupka za svaki par čisti - kriptirani tekst dobiva se skup kandidata za posljednji podključ te se kandidati koji se pojavljuju uz najviše parova čisti - kriptirani tekst zatim provjeravaju u praksi. Autor dokazuje da uz dovoljno parova čisti - kriptirani tekst ovaj napad otkriva podključ posljednje runde i time omogućava uspješno kriptoanaliziranje simetričnih kriptoalgoritama.
Kako bi pokazao da je njegova generalizacija linearne kriptoanalize smislena, autor konstruira kriptoalgoritam QRweak koji nije ranjiv na linearnu kriptoanalizu, ali je ranjiv na njegovu generalizaciju.
Nekoliko godina kasnije Harpes primjenjuje svoj napad (sada ga nazivajući partitioning cryptanalysis) na DES od 6 rundi i dobiva rezultate koji su usporedivi sa efikasnošću diferencijalne kriptoanalize Bihama i Shamira.[15]

3.10.1  Mod n kriptoanaliza

Mod n kriptoanaliza specijalan je slučaj kriptoanalize razdjeljivanjem koja koristi nejednakost u načinu na koji kriptoalgoritam barata klasama ekvivalencije modulo n. Metodu su 1999. predložili John Kelsey, Bruce Schneier i David Wagner.[20]
U tom radu autori su pokazali da u nekim slučajevima vrijednost ulaza u zadnju Feistel rundu modulo n korelira sa vrijednošću čistog teksta modulo n. U tom slučaju napadač može iskoristiti tu korelaciju kako bi prikupio informacije o podključu posljednje runde. Autori su pokazali da kriptoalgoritmi koji poništavaju statističke pravilnosti koje se koriste u nekim drugim napadima (primjerice linearne aproksimacije u linearnoj kriptoanalizi ili diferencijalne karakteristike u diferencijalnoj kriptoanalizi) nisu nužno neranjivi na korelacije modulo n.
Kriptoanalizom algoritma RC5P (varijanta RC5 kriptoalgoritma) autori su pokazali kako se mod 3 napadom mogu dobiti bolji rezultati nego napadom grubom silom, obzirom na to da se rotacija za jedan bit može jednostavno opisati jednadžbom modulo 3. Prikazali su i napade na algoritam M6 (koji je predložen za korištenje u FireWire standardu): M6 algoritam može se izvrsno aproksimirati mod 5 napadom, dok se mod 257 napadom mogu dobiti i neke informacije o podključevima.

3.11  Daviesov napad

Godine 1987. [3] Donald Davies pronašao je statističko svojstvo DES kriptoalgoritma koje je ovisno o ključu i koje bi, teoretski, moglo dovesti do otkrivanja ključa na osnovi parova čisti - kriptirani tekst. No, sam autor naglašava da je napad interesantan samo teoretski jer je broj enkripcija, potreban kako bi se iskoristila ova slabost, usporediv sa brojem enkripcija potrebnih za napad grubom silom.[10]
Daviesov napad zasniva se na neuniformnosti distribucije izlaza iz parova susjednih S-kutija. Ovim napadom teoretski bi se moglo doznati paritet do 16 bitova ključa. No, primjena Daviesovog napada izrazito je nepraktična jer je distribucija izlaza odviše uniformna, tako da varijanta napada, bazirana na zadnje dvije S-kutije (koje su najpovoljnije za ovaj napad,) zahtjeva 256,6 poznatih čistih tekstova i pronalazi dva paritetna bita ključa uz vjerojatnost uspjeha od 95,5%.
Napad koristi činjenicu da se u svakoj Feistel rundi na ulaznom podatku najprije obavlja ekspanzija. To znači da neke S-kutije primaju isti ulazni bit. Primjerice, 5. ulazni bit u kutiju S1 i 1. ulazni bit u kutiju S2 su prije XOR-a sa podključem bili isti bit - 4. bit ulaza u Feistel rundu. To znači da je XOR 5. ulaznog bita u kutiju S1 i 1. ulaznog bita u kutiju S2 jednak XOR-u 49. i 33. bita podključa. U općenitom slučaju, ulaz u par susjednih S-kutija ovisi o paritetu (XOR-u) dva bita podključa.
Nadalje, može se utvrditi distribucija 8-bitnog izlaza iz para S-kutija u ovisnosti o ta dva zajednička bita i ta distribucija je uvijek neuniformna. Distribucija izlaza iz para susjednih S-kutija ovisi samo o XOR-u ovih dva bita podključa. Pod pretpostavkom nezavisnih ulaza, distribucija XOR-a n izlaza iz parova susjednih S-kutija je n-terostruka konvolucija distribucije izlaza iz susjednih S-kutija, a Davies pokazuje da distribucija XOR-ova izlaza ovisi samo o XOR-u svih bitova podključa koji su gore opisani. Za velik broj parova čisti - kriptirani tekst dobiva se 16 empirijskih distribucija za XOR parova S-kutija, pa promatranje izlaza gore opisane forme potencijalno daje statističku informaciju o 16 linearno nezavisnih kombinacija bitova podključa.

3.12  XSL napad

XSL napad (od engl. eXtended Sparse Linearization attack) predložili su 2002. Nicolas Courtois i Josef Pieprzyk. Njihov rad istog je trena izazvao velike kontroverze jer su u njemu predložili način na koji bi se teoretski moglo razbiti AES kriptoalgoritam (koji je baš te 2002. zamijenio DES kao NIST-ov standard) brže nego napadom grubom silom. Do danas ostaje nejasno je li XSL napad izvediv ili nije obzirom na to da su se svjetski kriptoanalitički stručnjaci podijelili oko pitanja funkcionira li XSL napad uopće.[30]
AES algoritam poseban je po tome što ima vrlo jednostavan algebarski opis. Algoritam dizajniran je tako da se da lako algebarski opisati, ali da je korištena struktura izrazito neotporna na sve (do tada) poznate oblike kriptoanalize. Courtois i Pieprzyk su upravo činjenicu da je matematička struktura AES-a jednostavna pokušali iskoristiti kako bi matematički povezali ulaz i izlaz AES-a, što do tada nije bilo pokušavano. Predložili su teoriju da se AES može opisati sustavom od 8000 kvadratnih jednadžbi sa 1600 binarnih nepoznanica [1]. Rješavanje ovog sustava teoretski je moguće jer kvadratnih jednadžbi ima dovoljno (i previše) da bi se ovaj sustav riješio. No ne postoji eksplicitan algoritam koji bi riješio ovoliku količinu jednadžbi. Stoga, da bi napad na AES uspio, potrebno je pronaći način da se riješe ove jednadžbe.
Jedan od načina rješavanja ovih jednadžbi jest linearizacija sustava te zatim rješavanje sustava Gaussovom eliminacijskom metodom. Da bi ova metoda uspjela potrebno je linearizacijom dobiti određeni broj linearno nezavisnih jednadžbi. Ovaj problem pokazao se nepremostivim u ranim (prije 2000.) pokušajima rješavanja ovakvih sustava.
Courtois je već 2000. zajedno sa Patarinom, Klimovom i Shamirom objavio rad Efficient algorithms for solving overdefined systems of multivariate polynomial equations gdje je predložio algoritam proširene linearizacije (engl. eXtended Linearization algorithm - XL algorithm) koja je povećala broj linearno nezavisnih jednadžbi dobivenih linearizacijom. Procjene kompleksnosti XL algoritma pokazale su da primjena XL-a na AES također ne daje dobre rezultate.
Courtois i Pieprzyk, u svom radu 2002. predložili su unapređenje XL algoritma: XSL algoritam (od engl. eXtended Sparse Linearization algorithm). Dok je XL algoritam općeniti matematički algoritam za linearizaciju sustava kvadratnih jednadžbi, XSL algoritam uzima u obzir svojstva AES-a i time pospješuje rezultate linearizacije. Autori u svom radu tvrde da je kompleksnost XSL algoritam dovoljno mala da omogućava razbijanje AES algoritma efikasnije od napada grubom silom.[35]
No, ova tvrdnja je naišla na žestoka osporavanja u kriptoanalitičkoj zajednici. Vincent Rijmen, jedan od autora AES-a izjavio je "XSL nije napad, to je san" [35]. Neosporna činjenica jest da je utvrđivanje efikasnosti XSL napada izrazito kompliciran problem i postoji nekoliko radova koji tvrde da je i XSL napad (kao i XL algoritam) nedovoljan za razbijanje AES-a [29], no s druge strane, Courtois i Pieprzyk nisu usamljeni u svojim tvrdnjama [21] i pred kriptoanalitičarima predstoji još mnogo posla dok se ne utvrdi je li XSL napad izvediv i ako jest izvediv, je li bolji od napada grubom silom. No, čak i ako se pokaže da je XSL napad bolji od napada grubom silom, čak i najoptimističnija projekcija efikasnosti XSL napada daje dovoljno slabe rezultate da nema mjesta zabrinutosti za podatke kriptirane AES-om.

4  Diferencijalna kriptoanaliza DES kriptosustava

Kako je već opisano u poglavlju o DES-u, taj algoritam razvili su zaposlenici tvrtke IBM. Za vrijeme razvoja DES-a pokušavani su razni kriptoanalitički napadi na algoritam u razvoju, a jedan od tih napada bio je i T-attack ili tickle-attack (obzirom da se ulazni podatci "golicaju" (engl. tickle) pa se promatra kako to utječe na izlaz). Taj napad analitičari su koristili kako bi odredili optimalan sadržaj S-kutija. Kako je DES bio kandidat za NIST-ov natječaj, IBM je algoritam poslao u NSA na razmatranje. Analitičari NSA zatim su predložili sasvim drugu konfiguraciju S-kutija koja se pokazala još otpornijom na IBM-ov T-attack. Analitičari NSA zatim su zatražili od IBM-a da sve podatke o kriptoanalizi DES-a proglasi tajnima kako podatci o T-attacku ne bi postali javno dostupni. U tom trenutku Sjedinjene američke države imale su pred ostatkom svijeta veliku prednost u računalnoj kriptoanalizi i NSA je smatrala da je za nacionalnu sigurnost SAD-a najbolje da diferencijalna kriptoanaliza ostane tajna.[7]
T-attack ostao je tajan sve do 1991. kada su ga u radu [4] objavili Eli Biham i Adi Shamir pod imenom "diferencijalna kriptoanaliza". Neposredno nakon objave ovog rada autori koriste opisani napad kako bi razbili cijeli niz do tada sigurnih kriptoalgoritama: već iste godine razbijaju Snefru, Khafre, REDOC-II, LOKI i Lucifer. Diferencijalna kriptoanaliza potiče pravu eksploziju kriptoanalitičkih metoda u devedesetim godinama - pojavljuje se velik broj proširenja ili modifikacije diferencijalne kriptoanalize (primjerice bumerang i inside-out napadi, slide napad, diferencijalni napad povezanim ključem, itd.). I Mitsuru Matsui, autor linearne kriptoanalize, naveo je diferencijalnu kriptoanalizu kao inspiraciju za svoj napad, makar linearna kriptoanaliza nije direktno zasnovana na diferencijalnoj.

4.1  Opis napada

Slijedi opis diferencijalne kriptoanalize prema [7] i [16].

4.1.1  Utvrđivanje diferencijalne karakteristike

Napad se započinje sa dva čista teksta, m i m′, koji se razlikuju za razliku ∆m, gdje je ∆m = m ⊕m′. Slijedi analiza razlike polovica poruka koje se javljaju u i-toj rundi: ∆mi = mi ⊕mi′. Prije ulaska u S-kutiju, bitovi polovice poruke prvo prolaze kroz operaciju ekspanzije, a zatim se nad njima obavlja XOR sa bitovima podključa. Za S-kutiju S1 to izgleda ovako:
Općenito vrijedi:

(a ⊕c) ⊕(b ⊕c) = (a ⊕b) ⊕(c ⊕c) = (a ⊕b)
(4.12)
Iz identiteta  4.1. slijedi:

(mi[32,1,2,3,4,5] ⊕k(i)[1,2,3,4,5,6]) ⊕
(m′i[32,1,2,3,4,5] ⊕k(i)[1,2,3,4,5,6])
(4.13)
=
mi[32,1,2,3,4,5] ⊕m′i[32,1,2,3,4,5]
(4.14)
=
∆mi[32,1,2,3,4,5]
(4.15)
Ovisnost izraza o podključu je nestala.
Temelj diferencijalne kriptoanalize jest pretpostavka da postoji odnos između input i output XOR-ova za neke S-kutije. Od 64 moguća 6-bitna inputa u S1 može biti podijeljeno u 32 para tako da XOR inputa u svakom paru daje vrijednost ∆mi[32,1,2,3,4,5] različitu od nule. Ta vrijednost je označena sa ∆Ii,1 obzirom na to da je to promjena inputa u i-toj rundi za S1. Za svaki takav par inputa postoji 4-bitni par outputa i XOR tih outputa je označen sa ∆Oi,1. Diferencijalna kriptoanaliza zasniva se na činjenici da mnogi input XOR-ovi sa razlikom ∆Ii,j na izlazu iz S-kutije daju isti output XOR ∆Oi,j. Na primjer, iz tablice 4.1. vidljivo je da, ako je ∆Ii,1 jednako 110100, ∆Oi,1 može poprimiti samo 8 od 16 mogućih vrijednosti, a vrijednost 0010 se pojavljuje čak 16 puta kao vrijednost ∆Oi,1.
Tablica 4.5: Raspodjela output XOR-ova za neke input XOR-ove za prvu S-kutiju
Permutirani izlazi iz S-kutija označeni su sa f(k(i), mi) i f(k(i), m′i). Za svaku Feistel rundu vrijedi:

mi+1
=
mi−1 ⊕f(k(i), mi)
(4.16)
m′i+1
=
m′i−1 ⊕f(k(i), m′i)
(4.17)
XOR ove dvije jednakosti glasi:

∆mi+1
=
mi+1 ⊕m′i+1
(4.18)
=
[mi−1 ⊕f(k(i), mi)] ⊕[m′i−1 ⊕f(k(i), m′i)]
(4.19)
=
∆mi−1 ⊕[f(k(i), mi) ⊕f(k(i), m′i)]
(4.20)
Dakle, ako ∆mi−1 i ∆mi može se odrediti sa velikom vjerojatnošću i ako ∆mi izaziva visoku vjerojatnost da se pojavi neka određena razlika f(k(i), mi) ⊕f(k(i),m′i), onda sa visokom vjerojatnošću može se odrediti ∆mi+1.
Diferencijalna kriptoanaliza započinje sa parom čistih tekstova (m,m′) koji imaju određenu razliku ∆m = (∆m0, ∆m1) koja je sa sigurnošću poznata. Zatim se prati promjena razlika kroz runde: ∆m2, ∆m3, ... , ∆m16, ∆m17. Autori ovaj uzorak nazivaju vjerojatni uzorak, jer postoji određena vjerojatnost da će se za isti input XOR pojaviti isti uzorak i na izlazu dati isti output XOR.
Kriptirani tekstovi Ek(m) i Ek(m′) dobivaju se inverznom permutacijom izlaza iz posljednje dvije runde:

Ek(m) = IP−1(m17, m16)
(4.21)
Ek(m′) = IP−1(m′17, m′16).
(4.22)
Obzirom na to da vrijedi
Ek(m) ⊕Ek(m′) = IP−1(∆m17, ∆m16),
(4.23)
očito je da output XOR ovisi samo o output XOR-u posljednje dvije S-kutije, dakle o vjerojatnom uzorku. Stoga, ako je na izlazu dobivena određena razlika sa određenom vjerojatnošću, za pretpostaviti je da su vrijednosti ∆mi slijedile uzorak. U tom slučaju može se dobiti informacija o bitovima podključa i tako otkriti puni ključ.

4.1.2   Utvrđivanje ključa

Kada je pronađena diferencijalna karakteristika sa dovoljno velikom vjerojatnošću pojavljivanja, moguće je napasti kriptoalgoritam otkrivanjem bitova posljednjeg podključa. Taj proces uključuje parcijalnu dekripciju zadnje runde algoritma i razmatranje ulaza u zadnju rundu.
S-kutiju koja prima ulazne podatke sa input XOR-om jednakim nuli naziva se neaktivna kutija. Bitove podključa zadnje runde koji utječu na ulaze u aktivne S-kutije naziva se ciljni parcijalni podključ. Parcijalna dekripcija posljednje runde uključuje (za sve aktivne S-kutije) XOR kriptiranog teksta sa ciljnim parcijalnim podključem i provlačenje tako dobivenog podatka unatrag kroz S-kutije, tako da se iskušaju sve moguće vrijednosti za ciljni parcijalni podključ.
Parcijalna dekripcija se obavlja za svaki par kriptiranih tekstova koji imaju neki određeni input XOR ∆m. Dekripcija se obavlja za sve moguće vrijednosti ciljnog parcijalnog podključa i za svaku vrijednost postavlja se brojač. Brojač se inkrementira kada parcijalnom dekripcijom dobivena vrijednost input XOR-a zadnje runde odgovara vrijednosti očekivanoj prema diferencijalnoj karakteristici. Vrijednost parcijalnog podključa koja ima najveći brojač ukazuje na ispravnu vrijednost bitova podključa.
Ovaj algoritam funkcionira zato jer se očekuje da će ispravna vrijednost parcijalnog podključa rezultirati time da se diferencije koje se očekuju prema diferencijalnoj karakteristici stvarno i pojave obzirom na to da karakteristika ima visoku vjerojatnost pojavljivanja. Kada se pojavi par koji ne odgovara karakteristici i koji ne bi trebao biti uzet u obzir, vrlo je velika vjerojatnost da brojač ispravnog podključa neće biti inkrementiran, obzirom na to da će u tom slučaju biti pogođena neka nasumična vrijednost podključa. Stoga krivi par neće mnogo utjecati na brojanje.

4.1.3  Složenost napada

Poanta svakog kriptoanalitičkog napada jest da zahtijeva manje rada od napada grubom silom, obzirom na to da se svaki kriptoalgoritam može napasti grubom silom. U slučaju diferencijalne kriptoanalize količina rada uložena u napad proporcionalna je sa brojem parova odabranih čistih tekstova koje je potrebno obraditi za uspješan napad. S druge strane, broj potrebnih parova ovisi o vjerojatnosti diferencijalne karakteristike koja se koristi za napad. Ukoliko karakteristika ima veću vjerojatnost, potrebno je manje parova i napad se izvodi u manjem vremenu. Stoga, kad se razmatra složenost diferencijalne kriptoanalize, u biti se razmatra količina podataka potrebnih za uspješan napad.
Općenito, što je veća diferencijalna vjerojatnost aktivnih S-kutija, to je veća vjerojatnost diferencijalne karakteristike cijelog kriptoalgoritma. Također, što je manji broj aktivnih S-kutija, to je veća vjerojatnost diferencijalne karakteristike (pD). Broj parova odabranih čistih tekstova (ND) definitivno ovisi o vjerojatnosti diferencijalne karakteristike, ali je vrlo teško precizno odrediti ND potreban za uspješan napad.
Može se pokazati da dobro aproksimativno pravilo za određivanje broja ND glasi:

ND ≈ c / pD
(4.24)
gdje je pD vjerojatnost diferencijalne karakteristike kroz cijeli kriptoalgoritam, a c je neka malena konstantna vrijednost. Pretpostavi li se da je pojava parova koji zadovoljavaju diferencijalnu karakteristiku nezavisna za svaku S-kutiju, vjerojatnost diferencijalne karakteristike je dana sa:

pD = γ
∏
i=1 
 βi
(4.25)
gdje je γ broj aktivnih S-kutija, a βi je vjerojatnost pojavljivanja određenog para input i output XOR-a na i-toj aktivnoj S-kutiji. Ova jednadžba ukazuje na to da je nekoliko pojavljivanja parova koji se poklapaju sa diferencijalnom karakteristikom (zovu se ispravni parovi) dovoljno da vrijednost brojača koji pripada ispravnom ciljnom parcijalnom podključu bude znatno veća od vrijednosti brojača koji pripada neispravnom ciljnom parcijalnom podključu. Obzirom na to da se jedan ispravan par očekuje otprilike svakih 1/pD parova koje razmotrimo, u praksi je razumno očekivati da će neki produkt 1/pD sa malim prirodnim brojem biti dovoljan za uspješno izvođenje diferencijalne kriptoanalize.
Kako vjerojatnost karakteristike ovisi o broju rundi vidljivo je u tablici  4.2., a konkretan izračun vrijednosti ND dan je u tablici  4.3. (oboje prema [4]).
Tablica 4.6: Vjerojatnost diferencijalne karakteristike u odnosu na broj rundi
broj rundipD
3[1/234]
5[1/55000]
7 ≈ 2−24
9 ≈ 2−32
11 ≈ 2−40
13 ≈ 2−48
15 ≈ 2−56
Tablica 4.7: Kompleksnost diferencijalne kriptoanalize DES-a u odnosu na broj rundi
broj rundiND
424
628
8216
9226
10235
11236
12243
13244
14251
15252
16253
Podatak da je za razbijanje punog DES-a potrebno 253 operacija govori da je DES u biti neotporan na diferencijalnu kriptoanalizu. Naime, od 64 bita ključa, njih 56 je korisno, što znači da mogućih ključeva ima 256. Za pretraživanje svih mogućih ključeva potrebno je izvršiti samo pola od tog broja pretraga obzirom na to da DES ima svojstvo komplementarnosti (za detalje vidjeti poglavlje 2.2.1.). Kako će, u prosjeku, napad grubom silom pronaći ključ nakon 50% enkripcija, u općem slučaju broj operacija može se smanjiti za još pola. To znači da, u općem slučaju, napad grubom silom zahtjeva 254 operacija, a diferencijalna kriptoanaliza 253. Iz toga proizlazi: uspjeh diferencijalne kriptoanalize sumjerljiv je sa uspjehom napada grubom silom, što znači da diferencijalna kriptoanaliza nije razbila DES.

4.2   Primjer: napad na DES od 3 runde

Teoretski opis iz prethodnog poglavlja sada će biti prikazan na primjeru. Varijanta DES-a koju će biti kriptoanalizirana imat će svega 3 Feistel runde. Koristeći isti princip, no u nešto kompliciranijoj izvedbi, Biham i Shamir razbili su potpuni DES, no kao što je već rečeno, uz više truda nego što bi zahtijevalo jednostavno pretraživanje prostora ključeva. Napad koji će biti izveden spada u napade odabranim čistim tekstom, ali se može poopćiti i na napad poznatim čistim tekstom.[12]
Diferencijalna kriptoanaliza DES-a relativno je komplicirana i za malen broj rundi, dok za velik broj rundi postaje neupotrebljiva, upravo zato jer su dizajneri DES-a tu vrstu napada pokušavali spriječiti. Diferencijalno kriptoanaliziranje punog DES-a predstavlja prilično zahtjevan zadatak pa će u ovom primjeru biti prikazana ograničena verzija diferencijalne kriptoanalize DES-a.

4.2.1  Algoritam

Iz algoritma DES bit će izbačene inicijalna permutacija IP koja se primjenjuje na početku algoritma i njen inverz IP−1 koji se primjenjuje na kraju algoritma iz razloga što su te permutacije u načelu beskorisne protiv diferencijalne kriptoanalize, a samo kompliciraju prikaz. Naime, ako je poznat permutirani tekst, vrlo je jednostavno naći originalni tekst, tako da je zanemarivanje permutacija sasvim opravdano. Dakle, naš DES se u načelu sastoji samo od Feistel rundi. Ulazni podatak od 64 bita razbija se odmah na dva 32-bitna dijela (L0 i R0), a na izlazu algoritma dobivaju se dva 32-bitna dijela koja se spajaju u 64-bitni izlaz.

4.2.2  Kriptoanaliza

Za kriptoanalizu potrebni su parovi čistih tekstova i pripadni parovi kriptiranih tekstova. Čisti tekstovi označeni su kao L0R0 (prvi čisti tekst) i L*0R*0 (drugi čisti tekst), a kriptirani tekstovi kao L3R3 (prvi čisti tekst) i L*3R*3 (drugi čisti tekst). Njihove XOR vrijednosti označene su sa X′, dakle, X′=X⊕X* (npr. L′0 = L0 ⊕L*0). Definicija input XOR-a i output XOR-a (prema [12]) glasi:
Neka je Sj neka S-kutija (1 ≤ j ≤ 8), te neka je (Bj, B*j) uređeni par 6-bitnih nizova. Tada Bj ⊕B*j se naziva "input XOR", a Sj(B) ⊕Sj(B*j) se naziva "output XOR".
Za svaki input XOR (B′j ∈ (Z2)6) skup svih uređenih parova (Bj, B*j) čiji je input XOR jednak B′j je označen sa ∆(B′j).
Dakle, ∆(B′j) je u načelu skup od 26=64 uređena para koji sadrže na prvom mjestu sve moguće kombinacije od 6 bita (sve moguće Bj), a na drugom mjestu pripadne 6-bitovne vrijednosti koje sa prvom vrijednošću daju input XOR B′j (dakle, na drugom mjestu se nalazi Bj ⊕B′j):

∆(B′j) = (Bj, Bj ⊕B′j): Bj ∈ (Z2)6.
(4.26)
Kao što znamo, S-kutija ulaznu 6-bitnu vrijednost pretvara u izlaznu 4-bitnu vrijednost. Dakle, input XOR dugačak je 6 bita, dok je output XOR dugačak svega 4 bita. Stoga, izračuna li se za svaki od 64 parova iz ∆(B′j) output XOR, dobit će se najviše 24=16 različitih vrijednosti. Osnova za napad diferencijalnom kriptoanalizom jest činjenica da te vrijednosti neće biti uniformno raspoređene.
U tablici  4.4. izneseno je nekoliko primjera koji prikazuju kako se raspoređuju output XOR-ovi za zadani input XOR, koristeći prvu S-kutiju.
Tablica 4.8: Primjer raspodjele output XOR-ova
Input XOR:
101010

Raspodjela
output XOR-ova:
0000 4
0001 2
0010 4
0011 6
0100 0
0101 2
0110 8
0111 2
1000 2
1001 14
1010 2
1011 6
1100 2
1101 6
1110 2
1111 2
Input XOR:
010101

Raspodjela
output XOR-ova:
0000 0
0001 4
0010 6
0011 4
0100 2
0101 2
0110 4
0111 10
1000 6
1001 2
1010 0
1011 10
1100 0
1101 4
1110 6
1111 4
Input XOR:
110100

Raspodjela
output XOR-ova:
0000 0
0001 8
0010 16
0011 6
0100 2
0101 0
0110 0
0111 12
1000 6
1001 0
1010 0
1011 0
1100 0
1101 8
1110 0
1111 6
Slika 4.7: Raspodjela output XOR-ova za neke input XOR-ove za prvu S-kutiju
Iz grafičkog prikaza na slici  4.1. očito je da se output XOR-ovi ne raspodjeljuju uniformno.
Slijede definicije termina kojima ćemo obuhvatiti dobivene podatke.[12]
Za j ∈ 1, 2, ... , 8, 6-bitni niz B′j i 4-bitni niz C′j definira se:
INj(B′j, C′j)
=
Bj ∈ (Z2)6 : Sj(Bj) ⊕Sj(Bj ⊕ B′j) = C′j ,
(4.27)
Nj(B′j, C′j)
=
| INj (B′j, C′j) |.
(4.28)
Matematičkim jezikom ovdje je rečeno da je Nj(B′j, C′j) broj ulaznih parova koji daju input XOR B′j za koje vrijedi da daju output XOR C′j, dok je INj(B′j, C′j) skup 6-bitnih vrijednosti koje čine prvi element ulaznih parova koji čine vrijednost Nj(B′j, C′j).
Dakle, Nj(110100, 0001)=8, što je vidljivo iz masno otisnutog retka raspodjele output XOR-ova, dok je

INj(110100, 0001) =
000011, 001111, 011110, 011111, 101010, 101011, 110111, 111011.
(4.29)
Skup testj definira se na sljedeći način :
Neka su Ej i E*j 6-bitni nizovi, a C′j 4-bitni niz. Vrijedi

testj(Ej, E*j, C′j) = Bj ⊕Ej : Bj ∈ INj(Ej ⊕E*j, C′j) .
(4.30)
Jednostavnim rječnikom rečeno, skup testj dobiva se tako da se izračuna skup INj(Ej ⊕E*j, C′j) te se nad tako dobivenim vrijednostima obavi XOR sa Ej. Obzirom na to da se testj skup gradi nad INj skupom, taj skup isto nasljeđuje svojstvo nejednolike raspodjele vrijednosti na kojoj se temelji diferencijalna kriptoanaliza.
Sada je moguće dobiti bitove ključa pomoću test skupova. Ulaz u S-kutiju su 6-bitne vrijednosti koje se dobivaju ekspanzijom 32-bitne vrijednosti na 48-bita, obavljanjem XOR-a te vrijednosti sa 48 bita podključa za tu rundu te rastavljanjem na 8 dijelova od po 6 bita. Analogna situacija postiže se i odvojenim rastavljanjem ekspandirane vrijednosti na 8 dijelova od po 6 bita (označenih sa E1,... E8) te rastavljanjem podključa na 8 dijelova od po 6 bita (označenih sa J1,... J8) i zatim obavljanja XOR-a nad svakim dijelom posebno: Bj=Ej ⊕Jj. Za tako definirane Bj, Ej,Jj vrijedi tvrdnja[12]:
Neka je C′j = Sj(Bj) ⊕Sj(B*j). Tada je Jj ∈ testj(Ej, E*j, C′j).
Ova tvrdnja izrazito je bitna jer omogućava da se iskoristi činjenica da se vrijednosti skupa test nejednoliko raspoređuju te da se, uz nekoliko parova ulaznih tekstova, odrede presjeci pripadnih skupova test koji sadrže samo jednu vrijednost – traženi dio podključa. Obavi li se ta operacija nad svih 8 dijelova podključa dobiva se cijeli podključ koji daje 48 bitova ključa, što predstavlja razbijanje cijelog algoritma. Slijedi dokaz te tvrdnje:
Prema definiciji za testj, tvrdnja koju treba dokazati ekvivalentna je sljedećoj relaciji:

Jj ⊕Ej ∈ INj(E′j, C′j)
(4.31)
Obzirom na to da je
Jj ⊕Ej = Bj
(4.32)
te da vrijedi
Sj(Bj) ⊕Sj(Bj ⊕B′j) = Sj(Bj) ⊕Sj(B*j) = C′j
(4.33)
slijedi da je
Jj ∈ testj(Ej, E*j, C′j).
(4.34)
Dakle, ukoliko se pribavi više vrijednosti za Ej, E*j i C′j, trebalo bi biti moguće izolirati jednočlani presjek skupova testj koji bi bio upravo j-ti dio podključa. Slijedi prikaz kako pribaviti te vrijednosti na primjeru DES-a od 3 runde bez inicijalnih permutacija.
Obzirom na to da se obavlja napad odabranim čistim tekstom, parovi čistog i kriptiranog teksta odabrani su tako da zadovoljavaju izraz R0=R*0 (tj. R′0=00...0). Dakle, na raspolaganju su odabrani čisti i kriptirani tekstovi: L0R0, L*0R*0, L3R3,L*3R*3. Iz tih podataka lako se računa E i E*:

E
=
E(L3)
(4.35)
E*
=
E(L*3)
(4.36)
Još preostaje izračunati C′. C′ se dobiva kao XOR od C i C*, a te dvije vrijednosti dobivaju se permutacijom izlaza iz zadnje Feistel runde:

P(C)=f(R2,K3)P(C*)=f(R*2,K3)
(4.37)
Iz toga slijedi:

P(C) ⊕P(C*) = f(R2,K3) ⊕f(R*2,K3)
(4.38)
a, obzirom na to da permutacija ne utječe na operaciju XOR:

P(C ⊕C*) = f(R2,K3) ⊕f(R*2,K3)
(4.39)
Uvodi se operacija inverzne permutacije P−1 za koju vrijedi P(P−1(x))=x. Sada vrijedi:

C′ = P−1(f(R2,K3) ⊕f(R*2,K3))
(4.40)
Kako bi se izračunala vrijednost u zagradi, kriptirani tekst se izražava kao funkcija čistog:

R3
=
L2 ⊕f(R2,K3) = R1 ⊕f(R2,K3) = L0 ⊕f(R0,K1) ⊕f(R2,K3)
(4.41)
R*3
=
L*2 ⊕f(R*2,K3) = R*1 ⊕f(R*2,K3) = L*0⊕f(R*0,K1) ⊕f(R*2,K3)
(4.42)
R′3
=
R3 ⊕R*3
=
(L0 ⊕f(R0,K1) ⊕f(R2,K3)) ⊕(L*0 ⊕f(R*0,K1) ⊕f(R*2,K3))
=
(L0 ⊕L*0) ⊕(f(R0,K1) ⊕f(R*0,K1)) ⊕ (f(R2,K3) ⊕f(R*2,K3))
=
L′0 ⊕f(R2,K3) ⊕f(R*2,K3)
(4.43)
Izraz (f(R0,K1) ⊕f(R*0,K1)) može se zanemariti zbog pretpostavke da je R0=R*0, pa je i f(R0,K1) = f(R*0,K1), pa je f(R0,K1) ⊕f(R*0,K1) = 0, a x ⊕0 = x.
Iz izraza za R′3 slijedi:

R′3 ⊕L′0 = f(R2,K3) ⊕f(R*2,K3)
(4.44)
Dakle, konačno se dobiva izraz za C′:

C′ = P−1(R′3 ⊕L′0).
(4.45)
Ovime su dobivene sve vrijednosti potrebne za računanje test skupova i računanje podključa K3. Izračunavši K3 pomoću test skupova dobiveno je 48 od 56 bita izvornog ključa. Time je veličina ključa u biti smanjena na preostalih 8 bita i kako bi se izračunalo potpuni ključ potrebno je samo pretražiti tih 28=256 bita ključa.[12]

4.2.3  Primjer

Nasumce je izabran neki ključ K i tri para čistih tekstova (L0R0,L*0R*0) za koje vrijedi R0=R*0:

K = 7c34b6e98f523854
(L0R0)1 = 3b92ade058430402
(L*0R*0)1 = b0461a5858430402
(L0R0)2 = c8adf738ab761c20
(L*0R*0)2 = d302e329ab761c20
(L0R0)3 = ef928525e61f62f1
(L*0R*0)3 = d63da834e61f62f1
Kako bi se dobili L3R3 i L*3R*3, moraju se kriptirati zadani čisti tekstovi. Tako su dobiveni parovi dani u tablici 4.5.
Tablica 4.9: Popis čistih i kriptiranih tekstova za primjer napada
Čisti tekstovi:Kriptirani tekstovi:
3b92ade058430402a84d9040984d336b
b0461a58584304025b1c15c8c66ab3c4
c8adf738ab761c20aac1c1fb612511d2
d302e329ab761c20ee1a40982858724a
ef928525e61f62f190955c3e9e35d6f6
d63da834e61f62f1b65a99409ea40565
E, E* i C′ računaju se na sljedeći način:

E
= E(L3)
E*
= E(L*3)
C′
= P−1(R′3 ⊕L′0)
E1 = 55025bca0201
E*1 = 2f68f80abe50
C′1 = b6f78be2 		E2 = d55603e03ff7
E*2 = 75c0f42014f1
C′2 = a3862df2 		E3 = 4a14aaaf81fd
E*3 = 5ac2f54f2a01
C′3 = 7904fb6b 2
Ovako izračunati podaci koriste se zatim za računanje 3 puta po 8 test skupova. Dakle, za svaki od tri seta ulaznih podataka računaju se skupovi test1, test2,... test8 i obavlja se presjek skupova sva tri seta podataka.
Za naš primjer test skupovi su dani u tablici  4.6.
Tablica 4.10: Prikaz test skupova
2 Prvi set:

24 27 26 5 4 6 51 45
18 20 26 27 12 50 52 60 61 42
19 18 22 57 56 60
21 54
51 54 63 60 33 17 3 6 15 12
48 52 55 59 60 63
10 29 17 18 44 32 35 59
13 28 32 49
Drugi set:

51 32 45 27 5 8
23 18 30 27 53 49 60 56 34 43
28 29 6 7 56 60 35 39
13 12 21 20 35 34 59 58
61 55 44 33 28 17 13 7
3 1 19 17 63 61
44 0
52 50 47 46 41 40 29 28 27 26
Treći set:

19 23 24 28 51 55
34 47 48 61 2 15 16 18 29 31
49 56 33 40
46 32 63 49 10 8 3 4 27 28 23 21
41 40 45 44 55 15 17 16 21 20
63 53 9 3
3 44
49 47 33 32 29 28 19 13
Dakle, dekatske vrijednosti 6-bitnih dijelova podključa K3 glase redom: 51, 18, 56, 21, 17, 63, 44, 28. Da je algoritam obavljen na još jednom paru čistih tekstova, dakle da je bilo četiri seta podataka, i četvrti set bi sadržavao dane brojeve. No, da su na raspolaganju bila samo dva seta podataka, recimo drugi i treći, pojavio bi se problem. Skupovi test5, test6 i test8 ne bi imali jedinični presjek, već bi presjek imao 2 člana i ne bi bilo moguće jednoznačno utvrditi cijeli podključ.
Spoje li se tako dobiveni 6-bitni odsječci u cjeloviti podključ, dobiva se podključ K3 = cd2e1547fb1c. Zatim se obavlja algoritam za generiranje podključeva unatrag. Prvo se nad ključem K3 obavlja inverz permutacije PC2. Obzirom na to da permutacija PC2 od 56-bitnog materijala formira 48-bitni podključ, neki bitovi će biti postavljeni na proizvoljnu vrijednost, no neophodno je zapamtiti koji su to bitovi kako bi kasnije bilo moguće pronaći pravu vrijednost tih bitova grubom silom. Zatim se obavljaju tri koraka za generiranje ključa unatrag pa zatim inverz permutacija PC1. Permutacija PC1 također povećava broj bita, ovaj put sa 56 na 64 bita, no tih dodatnih 8 bita su paritetni bitovi koje se lako izračunaju ako je ostalih 56 bita poznato.
Tako dobiven ključ za ovaj primjer glasi:
01111100 00110100 10x10x10 1x101000 10001110 0101xx10 001x10x0 x1010100
Bitovi koji ne sudjeluju u ključu K3 označeni su sa "x", a svi paritetni bitovi (svaki osmi bit) postavljeni su na nule.
Sada preostaje samo postaviti nedostajuće bitove na sve moguće vrijednosti i provjeriti odgovara li ključ za neki od parova čisti-kriptirani tekst. Tako se dobivaju svi bitovi ključa:
01111100 00110100 10110110 11101001 10001111 01010010 00111000 01010100
Diferencijalnom kriptoanalizom za DES sa 3 runde dobiva se ključ koji glasi K = 7c34b6e98f523854, što je upravo vrijednost koju je i postavljena na početku primjera. Dakle, potvrđeno je da se danim algoritmom problem pronalaženja ključa može svesti na pretraživanje prostora ključeva veličine 256 ključeva.

4.2.4  Dodatno razmatranje

Primjer iz prethodnog poglavlja ukazuje na potencijalan problem u diferencijalnoj analizi. Naime, da su na raspolaganju bila samo dva para čistih tekstova, napad ne bi uspio jer presjek test skupova ne bi bio skup od jednog člana. Postavlja se pitanje vrijedi li to općenito, je su li dva para čistih tekstova uvijek premalo, a 3 para uvijek dovoljno. Kao što je već nekoliko puta napomenuto, diferencijalna kriptoanaliza je statistički napad. To znači da isti algoritam ne mora za svaki primjer dati iste rezultate. Stoga je tako i sa brojem parova čistih tekstova: za neke kombinacije ključeva i čistih tekstova napad će uspjeti sa svega dva para, za neke neće uspjeti ni sa pet ili šest parova. No, logično je zaključiti da će broj uspješno izvršenih napada rasti sa brojem parova čistih tekstova. U tablici 4.7. izneseni su rezultati dobiveni kriptoanaliziranjem 1000 slučajno izabranih ključeva.
Tablica 4.11: Odnos broja parova čistih tekstova i broja neuspješnih napada
broj parova čistih tekstovabroj neuspješnih napada
2986
3435
489
56
64
70
Slika 4.8: Postotak neuspješnih napada u odnosu na broja tekstova
Kao što vidimo, zavisnost je eksponencijalna, broj neuspješnih napada jako brzo pada s porastom broja čistih tekstova. Grafički prikaz to jako dobro ilustrira.
Dakle, može se zaključiti da je vrlo izvjesno razbijanje DES algoritma od 3 runde s više od 7 parova čistih tekstova sa pripadnim kriptiranim tekstovima.
Porastom broja rundi raste i kompleksnost ovog algoritma, a time i broj tekstova potrebnih kako bi se razbio DES. Tako je za razbijanje DES-a od 8 rundi potrebno 214 tekstova, za DES od 10 rundi 224, za DES od 12 rundi 231, a za DES od 14 rundi 239 tekstova. Vidljivo je da broj potrebnih tekstova jako brzo raste, što je još jedna posljedica otpornosti DES-a na diferencijalnu kriptoanalizu.

4.3  Proširenja diferencijalne kriptoanalize

Otkriće diferencijalne kriptoanalize dovelo je do cijelog niza novih napada temeljenih na istoj. Najznačajniji od tih napada su krnja diferencijalna kriptoanaliza (engl. truncated differential cryptanalysis), diferencijalna kriptoanaliza višeg reda (engl. higher order differential cryptanalysis), nemoguća diferencijalna kriptoanaliza (engl. impossible differential cryptanalysis) i diferencijalno-linearni napad (engl. differential-linear attack). Prva dva napada polučila su neke značajne rezultate, stoga će biti ukratko opisani.

4.3.1  Krnja diferencijalna kriptoanaliza

U originalnoj diferencijalnoj kriptoanalizi kako su ju predložili Biham i Shamir, koristi se činjenica da neke diferencijalne karakteristike nisu slučajne. Te diferencijalne karakteristike dovode u vezu XOR 64 bita čistog teksta i 64 bita kriptiranog teksta. U svom radu [23] objavljenom 1994., Lars Knudsen predlaže korištenje diferencijalnih karakteristika koje povezuju samo dijelove XOR-ova, ponekad samo jedan jedini bit. Takve diferencijalne karakteristike Knudsen naziva "krnji diferencijali" (engl. truncated differentials) i pomoću njih izvodi napad nazvan "krnja diferencijalna kriptoanaliza" (engl. truncated differential cryptanalysis).
Autor iznosi primjer kriptoalgoritma koji je otporan na običnu diferencijalnu kriptoanalizu, ali ne i na krnju diferencijalnu kriptoanalizu. To je kriptoalgoritam od 5 rundi oblika:
f(x,k) = (x ⊕k)−1.
(4.46)
Autor je u svojem ranijem radu pokazao da je ovaj kriptoalgoritam neotporan na diferencijalnu kriptoanalizu zato jer diferencijalna karakteristika sa najboljom vjerojatnošću ima vjerojatnost 23−2n, gdje je n širina diferencijala, dakle broj bita čistog teksta. U slučaju 64-bitnih čistih tekstova ovaj diferencijal ima vjerojatnost 2−125, što ga čini neupotrebljivim.
No, za isti taj algoritam moguće je pronaći karakteristiku koja povezuje cijeli ulazni diferencijal sa jednim bitom izlaznog diferencijala i to sa vjerojatnošću 1. Ovaj diferencijal zatim se koristi za pronalaženje bitova ključa kao i kod pune diferencijalne kriptoanalize.
Ovaj slučaj sa jednostavnim kriptoalgoritmom od 5 rundi može se prenijeti na DES. Autor pokazuje da za DES postoje krnji diferencijali sa vjerojatnošću 1. Svojstvo permutacije na izlazu iz Feistel runde u DES-u je da izlaz iz jedne S-kutije utječe na maksimalno 6 S-kutija u sljedećoj rundi. Ova činjenica može se iskoristiti za konstrukciju krnjeg diferencijala za 4 runde DES-a sa vjerojatnošću 1. Taj diferencijal daje informaciju o razlici 8 bitova nakon 4 runde.
Autor razmatra sada par čistih tekstova gdje su desne polovice teksta jednake, a lijeve se razlikuju tako da su ulazi u samo jednu S-kutiju različiti (izabrana je kutija S1). Izlazi iz prve runde su jednaki, a izlazi iz druge runde razlikuju se samo za S-kutiju S1. Pri ulazu u treću rundu, ulazi u S-kutije S1 i S7 su jednaki jer izlazi iz S-kutije S1 ne utječu na ove dvije S-kutije. Stoga su izlazi iz te dvije S-kutije jednaki i XOR 8 bita u desnim polovicama kriptiranog teksta nakon tri runde je poznat obzirom na to da je poznat XOR na ulazu u drugu rundu. Desne polovice nakon tri runde su jednake lijevim polovicama nakon četiri runde, stoga je XOR 8 bita nakon četiri runde enkripcije poznat sa vjerojatnošću 1. Ovaj diferencijal može se iskoristiti za napad na DES od 6 rundi. Za takav napad potrebno je svega nekoliko odabranih čistih tekstova. Autor detaljno prikazuje taj napad koristeći 46 odabranih čistih tekstova i obavljajući oko 3500 enkripcija.

4.3.2  Diferencijalna kriptoanaliza višeg reda

U istom radu ([23]) Knudsen predstavlja još jedan napad: diferencijalnu kriptoanalizu višeg reda (engl. higher order differential cryptanalysis). Da bi se definirao diferencijal višeg reda, potrebno je prvo formalno definirati diferencijal prvog reda:
∆a f(x) = f(x + a) − f(x).
(4.47)
Diferencijal i-tog reda zatim se definira rekurzivno:
∆(i)a1, ..., ai f(x) = ∆ai(∆(i)−1a1, ..., ai−1f(x)).
(4.48)
Autor zatim (kao i u prošlom poglavlju) prikazuje kriptosustav za koji vrijedi da su sve diferencijalne karakteristike uniformne za Feistel rundu, dakle nije moguće saznati nikakav podatak o ključu koristeći diferencijale prvog reda. Takva Feistel funkcija dana je sljedećim izrazom:
f(x,k) = (x +p k)2   mod   p
(4.49)
gdje je p prost. Za ovakvu Feistel funkciju vrijedi da je vjerojatnost svakog diferencijala kroz jednu rundu jednaka 1/p. U binarnom sustavu proizlazi da je vjerojatnost svakog diferencijala jednaka 1/2, što znači da je jednako vjerojatno da diferencijal vrijed i da ne vrijedi pa je neupotrebljiv.
Knudsen zatim pokazuje da je napad na ovaj kriptosustav moguć ako se umjesto diferencijala prvog reda koriste diferencijali drugog reda. Njegov dokaz pokazuje da je za razbijanje ovakvog kriptoalgoritma od 5 rundi potrebno svega 8 odabranih čistih tekstova.
Poopćavajući ovaj kriptosustav Knudsen dolazi do napada koji se može primijeniti na svaki kriptoalgoritam koji koristi Feistel runde. Ako se pretpostavi da se Feistel funkcija nekog kriptosustava može opisati nelinearnim izrazom stupnja r, tada se diferencijalni napad koristeći diferencijal stupnja r može izvesti sa 2r+1 odabranih čistih tekstova.
Schaumüller-Bichl je pokazao da je stupanj nelinearnosti bilo koje S-kutije DES-a jednak 5. Ostaje otvoreno pitanje koji je stupanj nelinearnosti punog DES-a od 16 rundi.

5  Linearna kriptoanaliza DES kriptosustava

Diferencijalna kriptoanaliza zasniva se na promatranju utjecaja koji kriptoalgoritam ima na razlike među čistim i kriptiranim tekstovima, dakle na diferencijalnim karakteristikama. Proučavajući diferencijalnu kriptoanalizu Mitsuru Matsui došao je na ideju da izvidi postoje li u kriptoalgoritmima linearne karakteristike i da li se iste mogu iskoristiti u kriptoanalizi. Prvi rad na temu linearne kriptoanalize objavio je 1992.[28].1 U tom radu primjenjuje metodu linearne kriptoanalize na FEAL-4 i dobiva ključ sa svega 5 parova čisti - kriptirani tekst.
Manje od godinu dana nakon toga Matsui primjenjuje ovaj napad na DES [27] i pokazuje da se linearnom kriptoanalizom DES-a ključ može pribaviti brže nego grubom silom. U tom radu autor opisuje napad poznatim čistim tekstom. Svrha tog napada je pribaviti približne linearne izraze danog kriptoalgoritma. U tu svrhu konstruiraju se prvo statističke linearne staze između ulaznih i izlaznih bitova svake S-kutije. Zatim se te staze proširuju na cijeli algoritam i na kraju se dobivaju statističke linearne staze bez ikakvih međuvrijednosti.
Autor je implementirao linearnu kriptoanalizu DES-a u C programskom jeziku, izveo taj program na PA-RISC računalu radnog takta 66 MHz i dobio sljedeće rezultate:

5.1  Opis napada

Opis napada iznesen je prema [16] i [27].

5.1.1   Linearna karakteristika

Osnovna ideja linearne kriptoanalize je približno opisati dio kriptoalgoritma pomoću izraza koji je linearan u odnosu na operaciju XOR. Da je izraz linearan znači da ima sljedeći oblik:
Xi1 ⊕Xi2 ⊕... ⊕Xiu ⊕Yj1 ⊕Yj2 ⊕... ⊕Yjv = 0
(5.50)
gdje Xi predstavlja i-ti bit ulaza X = [X1, X2, ...] a Yj predstavlja i-ti bit izlaza Y = [Y1, Y2, ...]. Jednakost 5.1. predstavlja XOR-sumu u ulaznih bitova i v izlaznih bitova.
Pristup linearne kriptoanalize je pronalaženje izraza ovog oblika koji imaju visoku ili nisku vjerojatnost da vrijede za neke bitove (vjerojatnost pojavljivanja). Ukoliko se neki izraz ovog oblika primijeni na nasumično odabrane bitove, vjerojatnost da taj izraz vrijedi biti će 1/2. Ukoliko vjerojatnost da neki izraz vrijedi odstupa od 1/2, tada je taj izraz upotrebljiv u linearnoj kriptoanalizi: što više vjerojatnost pojavljivanja izraza odstupa od vrijednosti 1/2, to je izraz upotrebljiviji za linearnu kriptoanalizu. To odstupanje naziva se "odstupanje linearne vjerojatnosti" i označava se sa pL − 1/2, gdje je pL vjerojatnost da linearni izraz vrijedi. Što je veća apsolutna vrijednost odstupanja linearne vjerojatnosti, to je veća upotrebljivost tog izraza u linearnoj kriptoanalizi i manje čistih tekstova će biti potrebno za izvođenje napada. Izraz koji ima upotrebljivu vrijednost |pL − 1/2| naziva se "linearna karakteristika".
U radu [27] Matsui izraz 5.1. zapisuje ponešto drugačije:
Xi1 ⊕Xi2 ⊕... ⊕Xiu ⊕Yj1 ⊕Yj2 ⊕... ⊕Yjv = Kk1 ⊕Kk2 ⊕... ⊕Kkz.
(5.51)
Ukoliko vrijedi
Kk1 ⊕Kk2 ⊕... ⊕Kkz = 0
(5.52)
tada izrazi 5.1. i 5.2. postaju ekvivalentni i imaju jednaku vjerojatnost pojavljivanja. No, ukoliko izraz 5.3. ne vrijedi, tada je 5.1. vrijedi kada 5.2. ne vrijedi i obrnuto. Označi li se vjerojatnost da izraz 5.2. vrijedi sa pM, tada za slučaj da ne vrijedi 5.3. vrijede sljedeće jednakosti:
pL
=
1 − pM
(5.53)
pL − 1/2
=
1/2 − pM
|pL − 1/2|
=
|1/2 − pM|
|pL − 1/2|
=
|pM − 1/2|.
(5.54)
Dakle, jasno je da izrazi 5.1. i 5.2. imaju jednako odstupanje linearne vjerojatnosti i da je pojednostavljenje 5.1. za naše potrebe ekvivalentno originalnom izrazu 5.2.
Vjerojatnost pL = 1 znači da izraz 5.1. savršeno opisuje kriptoalgoritam. S druge strane, pL = znači da je kriptoalgoritam u biti afina funkcija. Oba slučaja znače da je algoritam izrazito slab i u praksi se nikad ne susreće karakteristika koja ima vjerojatnost 0 ili 1.

5.1.2  Piling-up lema

Prije razmatranja konstrukcije linearne karakteristike, mora se prvo razmotriti matematička pozadina. Varijable X1 i X2 su dvije slučajne binarne varijable. Sa P(A) je vjerojatnost da je izraz A istinit. Sa pi se označi vjerojatnost da je Xi jednako 0. Tada vrijedi:
P(X1 = i)
=




p1,
i = 0
1 − p1,
i = 1
(5.55)
P(X2 = i)
=




p2,
i = 0
1 − p2,
i = 1
(5.56)
Ukoliko su varijable X1 i X2 nezavisne, tada vrijedi:
P(X1 = i, X2 = j)
=






p1p2,
i = 0, j = 0
p1(1 − p2),
i = 0, j = 1
(1 − p1)p2,
i = 1, j = 0
(1 − p1)(1 − p2),
i = 1, j = 1
(5.57)
Vjerojatnost izraza 5.1. za dvije varijable glasi:
P(X1 ⊕X2 = 0)
=
P(X1 = X2)
=
P(X1 = 0, X2 = 0) + P(X1 = 1, X2 = 1)
=
p1p2 + (1 − p1)(1 − p2).
(5.58)
Označi li se odstupanje linearne vjerojatnosti sa εi, tada vrijedi:
ε1
=
p1 − 1/2
(5.59)
ε2
=
p2 − 1/2
(5.60)
ε1,2
=
P(X1 ⊕X2 = 0) − 1/2
(5.61)
Iz 5.9., 5.10., 5.11. i 5.12. slijedi:
p1
=
ε1 + 1/2
(5.62)
p2
=
ε2 + 1/2
(5.63)
ε1,2
=
p1p2 + (1 − p1)(1 − p2) − 1/2,
(5.64)
a iz ovoga zatim:
ε1,2
=
2ε1ε2.
(5.65)
Na temelju ovdje opisanog zaključivanja, Matsui je došao do leme koju je nazvao "lema o nakupljanju" (engl. piling-up lemma). Ta lema glasi:
Za n nezavisnih slučajnih binarnih varijabli X1, X2, ..., Xn vrijedi:
P(X1 ⊕X2 ⊕... ⊕Xn = 0) = 1/2 +2n−1 n
∏
i=1 
 εi
(5.66)
ili, ekvivalentno:
ε1,2,...,n = 2n−1 n
∏
i=1 
 εi
(5.67)
gdje ε1,2,...,n predstavlja odstupanje linearne vjerojatnosti za X1 ⊕X2 ⊕... ⊕Xn = 0.
Ovu lemu može se koristiti za spajanje linearnih karakteristika kroz kriptoalgoritam. Primjerice, ako vrijede sljedeće linearne karakteristike i njihova odstupanja:
P(X1 ⊕X2 = 0) = 1/2 + ε1,2
(5.68)
P(X2 ⊕X3 = 0) = 1/2 + ε2,3
(5.69)
potrebno je utvrditi vezu između X1 i X3. Unutarnji član X2 odstranjuje se pomoću piling-up leme:
P(X1 ⊕X3 = 0)
=
P([X1 ⊕X2] ⊕[X2 ⊕X3] = 0)
(5.70)
=
1/2 + 2ε1,2ε2,3.
(5.71)
Koristeći ovu metodologiju mogu se povezati linearne karakteristike koje se javljaju unutar kriptoalgoritma i može se dobili linearna karakteristiku za cijeli algoritam.

5.1.3  Postojanje linearne karakteristike

Pri konstruiranju upotrebljive linearne karakteristike razmatrat će se povezanost bitova ulaza u S-kutiju (koji su u izrazu 5.1. označeni sa X) i bitove izlaza iz S-kutije (u izrazu 5.1. ti bitovi su označeni sa Y). Promatraju se svi mogući ulazi i njihovi izlazi.
Funkcija NSa(α, β) definira se na sljedeći način:
Za danu S-kutiju Sa (a = 1, 2, ..., 8), 1 ≤ α ≤ 63 i 1 ≤ β ≤ 15, definira se NSa(α, β) kao broj setova ulaznih bitova u Sa takvih da je XOR vrijednosti ulaznih bitova maskiranih s α jednaka XOR-u vrijednosti izlaznih bitova maskiranih s β, tj. da vrijedi:

NSa(α, β) def
=
 
 #{x | 0 ≤ x < 63, ( 5
⊕
s=0 
 (x[s] ·α[s])) = ( 3
⊕
t=0 
 (Sa(x)[t] ·β[t]))}
(5.72)
Ukoliko S-kutija nema nikakve linearne karakteristike, tada je NSa(α, β) za svaki α i β jednak 32 (što je polovica ukupnog broja ulaznih setova bitova). No, tome često nije tako. Na primjer, vrijedi sljedeća jednakost:
NS5(16, 15) = 12
(5.73)
gdje α = 16 označava 4. ulazni bit, a β = 15 označava sva 4 izlazna bita. Stoga 4. ulazni bit ima jednaku vrijednost kao XOR sva 4 izlazna bita sa vjerojatnošću 12/64 = 0,19. Uzme li se sada u obzir činjenicu da ekspanzija i permutacija ne utječu na linearnu karakteristiku, dobiva se jednakost koja vrijedi za nasumično odabrani čisti tekst X i fiksirani ključ K i Feistel funkciju F sa vjerojatnošću 0,19:
X[15] ⊕F(X,K)[7, 18, 24, 29] = K[22].
(5.74)
Tablica 5.1. najbolje pokazuje da NSa(α,β) nije uvijek jednak 32. U tablici 5.1. dane su razlike NSa(α, β) − 32 za svaki β i prvih 7 α. Kada ne bi postojala nikakva linearna karakteristika, ova tablica bila bi popunjena nulama, no tome nije tako.
Tablica 5.12: Dio distribucijske tablice za S5
α/ β123456789101112131415
1000000000000000
24-22-22-40402-22-20-4
30-26-2-24-400-26-2-24-4
42-2002-200224-4-2-20
522-4010-6-402-1004-224
6-2-4-6-2-4200-20-2-6-820
7202-2860-460-6-20-6-4
U svom radu [27] Matsui iznosi linearne karakteristike za DES od 3 pa do 20 rundi i odstupanja linearne vjerojatnosti tih karakteristika. Iz tih podataka vidljivo je da odstupanja linearne vjerojatnosti eksponencijalno opadaju s brojem rundi. Ovaj fenomen ilustriran je na slici 5.1.
Slika 5.9: Odnos odstupanja linearne vjerojatnosti i broja rundi
Najbolja linearna karakteristika za puni DES od 16 rundi prema Matsuiju glasi:
PH [7, 18, 24] ⊕PL [12, 16] ⊕CH [15] ⊕
(5.75)
⊕
CL [7, 18, 24, 29] ⊕F16(CL, K16)[15] =
=
K1 [19, 23] ⊕K3 [22] ⊕K4 [44] ⊕K5 [22] ⊕K7 [22] ⊕K8 [44] ⊕
⊕
K9 [22] ⊕K11 [22] ⊕K12 [44] ⊕K13[22] ⊕K14 [22]
pL = 1
2
 − 1,19 * 2−22
(5.76)
U istom radu autor iznosi i izraz za izračunavanje broja potrebnih tekstova za izvođenje linearne kriptoanalize s određenim uspjehom. Rezultate tog izraza prenesen je u tablici 5.2.
Tablica 5.13: Odnos broja tekstova i uspjeha linearne kriptoanalize
N2|p − 1/2|−28|p − 1/2|−28|p − 1/2|−216|p − 1/2|−2
Uspjeh48,6%78,5%96,7%99,9%
Dakle, ukoliko napad linearnom kriptoanalizom treba uspjeti sa sigurnošću većom od 95%, potrebno je pribaviti 8|p − 1/2|−2 parova čisti - kriptirani tekst. Uvrsti li se u ovaj izraz jednadžbu 5.27., dobiva se vrijednost od otprilike 247 poznatih čistih tekstova. Dakle, ukoliko se želi obaviti uspješan napad linearnom kriptoanalizom na DES od 16 rundi, potrebno je imati na raspolaganju 247 poznatih čistih tekstova.

5.1.4  Utvrđivanje ključa

Kao i kod diferencijalne kriptoanalize (poglavlje 4.1.2.), nakon što se pronađe linearna karakteristika s dovoljno velikim odstupanjem linearne vjerojatnosti, moguće je utvrditi neke bitove ključa. Proces je sličan diferencijalnoj kriptoanalizi: kriptoalgoritam je moguće napasti otkrivanjem bitova posljednjeg podključa. Taj proces uključuje parcijalnu dekripciju zadnje runde algoritma i razmatranje ulaza u zadnju rundu.
Izraz ciljni parcijalni podključ u ovom poglavlju ima drugačije značenje nego u poglavlju 4.1.2.: ciljni parcijalni podključ je skup bitova posljednjeg podključa koji utječu na bitove sadržane u linearnoj karakteristici. Nastavak algoritma je sličan onom u diferencijalnoj kriptoanalizi.
Parcijalna dekripcija se obavlja za svaki par čisti - kriptirani tekst koji posjedujemo. Dekripcija se obavlja za sve moguće vrijednosti ciljnog parcijalnog podključa i za svaku se vrijednost postavlja brojač. Brojač Ti za određeni parcijalni podključ Ki se inkrementira kada parcijalnom dekripcijom dobivena vrijednost ulaza u posljednju rundu i bitovi kriptiranog teksta zadovoljavaju linearni izraz. Ukoliko postoji N potencijalnih vrijednosti ciljnog parcijalnog podključa, tada je potrebno i toliko brojača Ti.
Minimalna i maksimalna vrijednost skupa koji čine brojači Ti glase:
Tmax = max{Ti}
(5.77)
Tmin = min{Ti}
(5.78)
Matsui u [27] iznosi algoritam za pronalaženje ciljnog parcijalnog podključa na temelju ove dvije vrijednosti. Matsui u tom radu koristi oblik linearne karakteristike dan jednadžbom 5.2. (za konkretan primjer vidjeti jednadžbu 5.25.). Algoritam je iznesen u ispisu 5.1.:
  AKO |Tmax − [1/2]| >   |Tmin − [1/2]| ONDA
     CPP = Kmax
     AKO pL > [1/2] ONDA Kk1 ⊕Kk2 ⊕ ... ⊕Kkz = 0
     AKO pL < [1/2] ONDA Kk1 ⊕Kk2 ⊕ ... ⊕Kkz = 1
  AKO |Tmax − [1/2]| < |Tmin − [1/2]| ONDA
     CPP = Kmin
     AKO pL > [1/2] ONDA Kk1 ⊕Kk2 ⊕ ... ⊕Kkz = 1
     AKO pL < [1/2] ONDA Kk1 ⊕Kk2 ⊕ ... ⊕Kkz = 0
Ispis 5.1: Matsuijev algoritam za pronalaženje ključa
U ispisu 5.1. sa CPP je označen ciljni parcijalni podključ, sa Kmax ključ koji odgovara brojaču Tmax, a sa Kmin ključ koji odgovara brojaču Tmin. Izrazi pL i Kk1 ... Kkz definirani su ranije (u poglavlju 5.1.1.).
Ovdje vrijedi diskusija slična iznesenoj u zadnjem odlomku poglavlja 4.1.2.: ukoliko linearna karakteristika ima dovoljno veliko odstupanje linearne vjerojatnosti, brojač koji pripada ispravnom (Tmax ili Tmin) podključu imat će bitno veću ili manju vrijednost od ostalih ključeva. Ova tvrdnja zasniva se na hipotezi o nasumičnosti neispravnog ključa (engl. wrong key randomisation hypothesis) koja je ilustrirana jednadžbom 5.30.:

pG − 1
2
pW − 1
2
 >> 1
(5.79)
Vjerojatnost da linearna karakteristika vrijedi ako se posljednja runda dekriptira ispravnim ključem označena je sa pG, dok je vjerojatnost da linearna karakteristika vrijedi ako se posljednja runda dekriptira neispravnim ključem označena sa pW. Izraz 5.30. posljedica je činjenice da svi neispravni ključevi imaju otprilike jednaku vjerojatnost zadovoljavanja linearne karakteristike. To znači da će neispravni ključevi koji (slučajno) zadovoljavaju linearnu karakteristiku biti jednoliko raspoređeni preko cijelog prostora parcijalnih podključeva i niti jedan brojač koji pripada neispravnom podključu neće se isticati u mjeri u kojoj će se isticati brojači Tmax i Tmin.

5.1.5  Složenost napada

U poglavlju 4.1.2. definiran je izraz "aktivna S-kutija". Aktivne S-kutije bitne su i za određivanje složenosti linearne kriptoanalize, slično kao i za diferencijalnu kriptoanalizu. Vjerojatnost da linearni izraz vrijedi je ovisna o odstupanju linearne vjerojatnosti u aktivnim S-kutijama i o broju aktivnih S-kutija. Općenito vrijedi: što je veća vrijednost odstupanje linearne vjerojatnosti u S-kutijama, veća je vrijednost odstupanje linearne vjerojatnosti cijelog linearnog izraza. Uz to, što je manje aktivnih S-kutija, to je veća vrijednost ukupnog odstupanja vjerojatnosti cijelog linearnog izraza.
Sa ε je označeno odstupanje vjerojatnosti da neki linearni izraz vrijedi za cijeli kriptoalgoritam. Matsui je pokazao da je broj potrebnih poznatih čistih tekstova proporcionalan sa ε−2. Ako se sa NL označi broj potrebnih čistih tekstova, NL se može aproksimirati sa ε−2:
NL ≈ 1
ε2
(5.80)
U praksi, za očekivati je da neki mali faktor od ε−2 bude broj potrebnih poznatih čistih tekstova. Kod napada linearnom kriptoanalizom, razlikuju se vremenska (vrijeme potrebno za izvođenje napada) i prostorna (broj potrebnih tekstova) složenost napada. Složenost koja je upravo razmatrana je prostorna složenost.
Obzirom na to da se odstupanje linearne vjerojatnosti određuje koristeći piling-up lemu gdje se svaki faktor u produktu odnosi na karakteristiku S-kutije, lako je vidjeti da ukupno odstupanje ovisi o odstupanjima S-kutija i broju aktivnih S-kutija. Pristupi zaštiti od linearne kriptoanalize zasnivaju se na optimiranju S-kutija (tj. na minimiziranju najvećeg odstupanja linearne vjerojatnosti) i na pronalaženju strukture koja će maksimizirati broj aktivnih S-kutija.

5.2  Primjer: napad na DES od 3 runde

Kao što je u poglavlju o diferencijalnoj kriptoanalizi prikazan primjer napada diferencijalnom kriptoanalizom na DES od 3 runde (poglavlje 4.2.), tako je pokušan i napad linearnom kriptoanalizom na DES od 3 runde.
Napad je pokušan prema [27]. U tom radu autor iznosi linearnu karakteristiku za DES od 3 runde koja ima vjerojatnost od 70 posto. U originalnoj notaciji ta karakteristika glasi:
PH [7,18,24,29] ⊕CH [7,18,24,29] ⊕PL [15] ⊕CL [15] = K1 [22] ⊕K3 [22]
(5.81)
Oznake su ilustrirane na slici 5.2.
Slika 5.10: Prikaz DES-a od 3 runde preuzet iz [27]
Za implementaciju napada linearnom kriptoanalizom korištena je C# implementacija DES algoritma opisana u poglavlju 7.3. Broj rundi je smanjen na 3, a algoritam za generiranje ključeva korišten je za pribavljanje ključeva K1 i K3. Pokušana je implementacija linearne karakteristike na nekoliko načina, no svaki pokušaj dao je neupotrebljive rezultate.
Na ispisima 5.2. i 5.3. prikazane su dvije različite implementacije linearne karakteristike 5.32. Varijabla 45 binplainL označava lijevu polovicu čistog teksta, a varijabla 45 binplainR desnu. Analogno, 45 bincypherL i 45 bincypherR su lijeva i desna polovica kriptiranog teksta. Varijable 45 binplain i 45 bincypher označavaju čisti i kriptirani tekst.
text_bits.Add(binplainL[15]);
text_bits.Add(binplainR[7]);
text_bits.Add(binplainR[18]);
text_bits.Add(binplainR[24]);
text_bits.Add(binplainR[29]);
text_bits.Add(bincypherL[15]);
text_bits.Add(bincypherR[7]);
text_bits.Add(bincypherR[18]);
text_bits.Add(bincypherR[24]);
text_bits.Add(bincypherR[29]);
Ispis 5.2: Prvi pokušaj implementacije linearne karakteristike 5.32.
text_bits.Add(binplain[31+15-1]);
text_bits.Add(binplain[7-1]);
text_bits.Add(binplain[18-1]);
text_bits.Add(binplain[24-1]);
text_bits.Add(binplain[29-1]);
text_bits.Add(bincypher[31+15-1]);
text_bits.Add(bincypher[7-1]);
text_bits.Add(bincypher[18-1]);
text_bits.Add(bincypher[24-1]);
text_bits.Add(bincypher[29-1]);
Ispis 5.3: Drugi pokušaj implementacije linearne karakteristike 5.32.
Obje ove implementacije iskušane su po nekoliko puta na uzorku od 1000 slučajno izabranih čistih tekstova i svaki puta je vjerojatnost karakteristike bila između 48% i 52%, što je daleko od 70%, koliko bi vjerojatnost trebala biti. Ova prepreka onemogućila je daljnju implementaciju primjera i ostaje otvoreno pitanje zašto nije moguće dobiti ispravnu vjerojatnost linearne karakteristike.

6  Napad grubom silom

Nakon što je prikazano kako diferencijalna i linearna kriptoanaliza daju rezultate koji su brzinom usporedivi s napadom grubom silom, slijedi detaljan prikaz tog napada, s naglaskom na DES algoritam.
Napad grubom silom funkcionira tako da isprobava svaki mogući ključ kako bi otkrio čisti tekst poruke. To znači da napad grubom silom može biti napad poznatim kriptiranim tekstom ili napad poznatim čistim tekstom. U slučaju napada poznatim čistim tekstom, metoda napada grubom silom svodi se na isprobavanje velike količine ključeva (u najgorem slučaju svih ključeva) kako bi se kriptirani tekst dekriptirao u pripadni čisti tekst. Kako bi napad poznatim kriptiranim tekstom bio moguć, potrebno je poznavati neka svojstva čistog teksta. Primjerice, ako je poznato da je čisti tekst poruka koja je napisana ASCII znakovima na engleskom jeziku, onda se može provesti napad grubom silom poznatim kriptiranim tekstom obzirom na to da je vjerojatnost da se dobiju dva smislena engleska teksta od istog kriptiranog teksta izrazito malena.
Napad grubom silom, za veliku većinu kriptoalgoritama nemoguće je spriječiti napadača jer ne možete spriječiti da provjeri svaki mogući ključ ukoliko mu je algoritam poznat. No, napad poznatim kriptiranim tekstom za neke vrlo rijetke algoritme nemoguće je izvesti. Jedan takav primjer jest one-time pad. Ukoliko se obavi napad grubom silom n-bitni tekst kriptiran one-time pad algoritmom, kao kandidati za čisti tekst dobiju se sve moguće n-bitne tekstove. Taj skup sadržavat će i traženi čisti tekst. No, sadržavat će i sve ostale čiste tekstove koji čine smisleni tekst dugačak n-bita, tako da je ne moguće razlučiti pravi čisti tekst od pogrešnih. S druge strane, napad poznatim čistim tekstom na one-time pad je trivijalan: potrebno je obaviti XOR operaciju nad čistim i kriptiranim tekstom i time se dobiva ključ.
Za razliku od diferencijalne i linearne kriptoanalize, grubom silom se napada jedan jedini čisti tekst (ili par čisti - kriptirani tekst). Broj čistih ili kriptiranih tekstova koji su na raspolaganju u potpunosti je nebitan - prostor ključeva može se pretraživati na bilo kojem paru, kriptiranom ključem koji tražimo.
Ovo je velika prednost pred drugim, naprednijim vrstama kriptoanalize. Primjerice, Daviesov napad (prvi predloženi napad na DES različit od napada grubom silom) zahtijeva 256,6 parova čisti - kriptirani tekst. Osim što je nemoguće pribaviti ovoliko parova (jer ključeva ima samo 256), za skladištenje 256,6 64-bitnih parova bilo bi potrebno preko 1,6 milijardi gigabajta. Diferencijalna kriptoanaliza, sa 253 potrebnih parova, zahtijevala bi disk od skoro 135 milijuna gigabajta.

6.1   Složenost napada

U slučaju DES-a, pretraživanje cijelog prostora ključeva zahtijeva 256 enkripcija obzirom na to da ključ u DES algoritmu ima 56 korisnih bitova. Ovaj broj može se smanjiti za pola ako se iskoristi svojstvo komplementarnosti definirano u poglavlju 2.2.1. [4]. Kriptoanaliza može iskoristiti ovo svojstvo ako su na raspolaganju dva para čisti - kriptirani tekst (P1, T1) i (P2, T2) takva da je P1 = [(P2)]. Napadač kriptira P1 koristeći svih 255 ključeva K čiji je najmanje značajan bit 0. Ako je tako dobiveni kriptirani tekst T jednak T1, onda je ključ K ključ koji tražimo. No, ako je T = [(T2)], tada je [(K)] ključ kojim su parovi kriptirani. U ostalim slučajevima niti K niti [(K)] nisu traženi ključ. Obzirom na to da je testiranje T = [(T2)] mnogo brža operacija od operacije enkripcije, vrijeme potrebno za napad grubom silom se upola smanjuje.
Dakle, za pretraživanje cijelog prostora ključeva algoritma DES potrebno je 255 enkripcija. Ukoliko se obavlja napad grubom silom na velik broj nasumično odabranih ključeva, zbog nasumičnosti tih ključeva prosječan broj enkripcija potrebnih za pronalazak ključa pada za faktor 2 (jer 50% ključeva bit će pronađeno prije nego li napad grubom silom uopće dođe do polovice prostora ključeva). Dakle, prosječna složenost napada na DES grubom silom je 254.

6.2  Neostvareni prijedlozi napada grubom silom

Nakon što je DES javno objavljen, a prije nego li je prihvaćen kao standard, kriptoanalitička zajednica toga vremena trudila se pronaći način da se DES razbije. Najbolji rezultat koji potječe iz tog vremena je korištenje svojstva komplementarnosti koje omogućuje da se vrijeme napada grubom silom prepolovi. No, čak i prepolovljeno, vrijeme potrebno za napad grubom silom preveliko je da bi se mogućnost takvog napada uopće razmatrala. Prvi koji su ozbiljno razmotrili mogućnost otkrivanja ključa grubom silom bili su Whit Diffie i Martin Hellman koji su 1977. objavili rad [11] i predložili stroj koji bi u roku od jednog dana otkrio ključ. Cijena predloženog stroja bila je 20 milijuna dolara.
Sljedećih petnaestak godina objavljena je nekolicina radova na istu temu, no prvi značajniji pomak napravio je Michael Wiener godine 1993. u radu [32]. Njegov prijedlog stroja bio je za jedan do dva reda veličine brži od dotadašnjih prijedloga i za razliku od sličnih analiza sadržavao je detaljan opis stroja i detaljan izračun cijene cijelog projekta. Minimalna cijena do koje je došao bila je 600 tisuća dolara. Od toga bi 500 tisuća dolara bilo potrošeno na dizajn čipova (plaće dizajnerima/programerima i pomoćnom osoblju, troškovi testiranja i slično), dok bi 100 tisuća dolara bilo potrošeno na izgradnju samog stroja. Takav stroj bio bi u stanju pronaći ključ u roku od 35 sati. Ako bi se na samu izgradnju (dakle, bez troškova dizajna) utrošilo više novaca, ključ bi se dobio brže (za detalje vidjeti tablicu 6.1.).
Tablica 6.14: Odnos cijene i predviđenog vremena pretraživanja za Wienerov stroj
cijena strojapredviđeno vrijeme potrage
100.000 $35 sati
1.000.000 $3.5 sati
10.000.000 $21 minuta

6.3  RSA DES Challenge

Obzirom na sve veći broj prigovora da je DES moguće razbiti grubom silom u nekom razumnom vremenu, pojavila se potreba da se tako nešto i dokaže stvarnim primjerom. Stoga je tvrtka RSA Data Security Inc. krajem devedesetih godina 20. stoljeća pokrenula seriju od nekoliko natječaja u kojima je nudila novčane nagrade onima koji uspješno napadnu DES kriptosustav.

6.3.1  Prvi DES Challenge

Na svojoj konferenciji u siječnju 1997. tvrtka RSA Data Security Inc. pokrenula je prvi takav natječaj. Objavili su jedan kriptirani tekst od 320 bita, inicijalizacijski vektor od 64 bita i ponudili 10 tisuća dolara prvoj osobi ili grupi koja objavi sadržaj čistog teksta koji odgovara njihovom kriptiranom tekstu[8]. Kriptirani tekst objavljen je 28. siječnja 1997. u 9 ujutro po pacifičkom vremenu.
Dana 17. lipnja 1997. u 10:39, RSA je zaprimila točan čisti tekst koji je poslao čovjek po imenu Rocke Verser. To je bilo prvi puta da je neki kriptirani tekst javno otkriven bez poznavanja ključa. Time je pokazano da je definitivno vrijeme da se DES zamjeni kao standard.
Rocke Verser bio je vođa projekta DESCHALL koji se okupio upravo u svrhu sudjelovanja na RSA DES Challenge. Uz njega, projekt su vodili Justin Dolske, tada student na Ohio State University i Matt Curtin, tada glavni znanstvenik u tvrtci Megasoft Online Inc. Njihova ideja bila je iskoristiti snagu Interneta kako bi uz pomoć velikog broja osobnih računala provjerili svaki ključ u prostoru rješenja i tako pronašli ključ.
DESCHALL sustav sastojao se od jednog servera koji je obavljao raspodjelu ključeva (key server) i mnoštva klijenata rasprostranjenih po cijelom Internetu. Zanimljivo je da je key server sa Internetom bio spojen vezom brzine od svega 28.8 kbps, što je zaista mala brzina za današnje pojmove.
Server je sa klijentima komunicirao UDP protokolom kojim su razmijenjivali jednu od 5 mogućih poruka: "initial", "not found", "answer", "message", "kill". Ovih 5 poruka korišteno je redom: za inicijalizaciju klijenta, za klijentovu prijavu pretraženog bloka ključeva, za slanje narednog paketa ključeva od servera ka klijentu te za slanje važnih tekstualnih poruka od servera ka klijentu, za zaustavljanje servera. Klijent bi prvo obradio mali paket ključeva, a zatim bi postepeno povećavao paket ključeva koji zahtijeva. Paket ključeva se ne bi povećavao iznad broja ključeva koji klijent može obraditi u 30 minuta. Statistike pokazuju da su veličine paketa bile između 222 i 230 (veličina paketa uvijek je bila u obliku 2n).
Čak i za pojmove onog vremena serversko računalo bilo je prilično sporo: IBM PS/2 Server sa 56 MB RAM-a. To računalo bilo je u stanju raditi sa otprilike 10 tisuća klijenata u isto vrijeme. U trenucima kad je promet bio veći od te granice uključivano je i jedno Pentium računalo.
U projektu sudjelovala su klijentska računala raznih arhitektura. Na kraju projekta bilo je dostupno 40 različitih klijentskih programa za različite arhitekture. Klijenti za Intelove procesore i za Macintoshove PowerPC procesore bili su optimirani u asembleru, dok su klijenti za ostale arhitekture pisani u programskom jeziku C. Autori klijentskih programa izrazito su se trudili optimirati kod kako bi što ranije prepoznao neodgovarajuće čiste tekstove. Rezultati te optimizacije bili su izvrsni jer je klijentsko računalo sa procesorom Pentium na 200 MHz bilo u stanju obraditi oko 1 milijun ključeva u sekundi dok je PowerPC 604e na 25 MHZ mogao obraditi i do 1.5 milijuna ključeva u sekundi.
Klijentski programi koristili su procesor računala samo u trenucima kada niti jedan drugi proces nije koristio procesor. Posljedica toga bila je nagli porast broja procesiranih ključeva tijekom vikenda.
Arhitektura DESCHALL projekta, dakle, bila je izrazito ovisna o odzivu volontera koji su bili spremni ustupiti svoje računalo na korištenje dok procesor nije zauzet. Odziv volontera bio je izrazito velik: u jednom danu zabilježeno je maksimalno 14 tisuća različitih klijenata, a tijekom projekta zabilježeno je 78 tisuća različitih IP adresa. Najveća brzina kojom su ključevi provjeravani bila je malo ispod 7 * 109 ključeva u sekundi ili 600 * 1012 ključeva u danu sa najviše aktivnosti.
Nakon 89 dana kontinuiranog rada i pretraženog 51,8% prostora ključeva, DESCHALL projekt pronašao je traženi ključ. Traženi ključ glasio je: 84B220DB191458, a čisti tekst "Strong cryptography makes the world a safer place". Vlasnik klijenta koji je pronašao ključ (Michael Sanders) nagrađen je sa 4 tisuće dolara.
Prema prosječnoj brzini kojom je DESCHALL distribuirani sustav radio formirana je tablica 6.2. u kojoj su prikazane procijenjena vremena potrebna da se istom metodologijom pronađe ključ određene duljine. Obzirom na to da je broj računala uključenih u projekt vremenom rastao, ova vremena bi se vjerojatno znatno smanjila nakon nekog vremena.
Tablica 6.15: Vrijeme potrebno da DESCHALL projekt pronađe ključ određene duljine
broj bitova ključavrijeme pronalaženja ključa
4078 sekundi
485 sati
5689 dana
6441 godina
7210.696 godina
802.738.199 godina
88700.978.948 godina
96179.450.610.898 godina
11211.760.475.235.863.837 godina
128770.734.505.057.572.442.069 godina
Iako nije bio prvi distribuirani Internet projekt, DESCHALL je pokazao kako se snaga rastućeg Interneta može upregnuti i iskoristiti za pretragu prostora rješenja, naime da su korisnici Interneta zaista zainteresirani za ovakav projekt. A u svijetu kriptografije to je značilo samo jedno: dužina DES-ovog ključa od 56 korisnih bita definitivno je postala premala.[8]

6.3.2  RSA DES Challenge II-1

Godinu dana nakon prvog DES Challengea, RSA se odlučuje za još jedan. I ovaj natječaj završio je isto kao i prethodni: distribuirani volonterski sustav računala povezanih preko Interneta distributed.net krenuo je u pretragu cijelog prostora rješenja i ključ je pronađen.
Neprofitnu organizaciju Distributed Computing Technologies, Inc. (poznatiju jednostavno kao distributed.net) osnovao je Jeff Lawson nakon što je propao raniji projekt genx.net čiji je cilj bio riješiti RSA RC5-56 Challenge. Genx.net bio je zasnovan na TCP transportnom protokolu koji je ranjiv na napade uskraćivanjem resursa, što je grupa zlobnika i iskoristila. Nakon propasti tog projekta grupa predvođena Lawsonom osniva distributed.net koji kao transportni protokol koristi UDP (kao i DESCHALL) i 24. ožujka 1997. prvi poslužitelj ključeva počinje sa radom. Nakon 212 dana kontinuiranog rada, 22. listopada 1997. distributed.net pronalazi ključ za RSA RC5-56 Challenge.
Dana 13. siječnja 1998. u 9 sati po pacifičkom vremenu objavljen je kriptirani tekst za drugi po redu DES Challenge, nazvan RSA DES Challenge II-1. Osam minuta kasnije distributed.net započeo je sa radom na pronalaženju ključa. Nakon 39 dana i 88,4% pretraženog prostora ključeva, distributed.net pronalazi ispravan ključ. Pretraga trajala je kraće nego DESCHALL i u manjem vremenu je pretražila preko 3,5 puta više ključeva. Traženi ključ glasio je: 76 9E 8C D9 F2 2F 5D EA, a čisti tekst: "The secret message is: Many hands make light work." U 39 dana distributed.net isprobao je preko 63 * 1015 ključeva, a u trenutku najvećeg prometa obavio je pretragu 34,4 *109 ključeva u sekundi (što je oko 5 puta brže od DESCHALL projekta).

6.3.3   RSA DES Challenge II-2

Sljedeći natječaj započeo je 13. srpnja 1998. Distributed.net sudjelovao je i ovaj put, no nakon svega 2 i pol dana ključ je pronašla organizacija Electronic Frontier Foundation (EFF) koristeći DES cracker, stroj posebno dizajniran za ovaj posao.[13]
Slika 6.11: Jedna od matičnih ploča sa AWT-4500 čipovima (vidljiva samo polovica čipova)
EFF DES cracker dizajnirali su zajednički Cryptography Research, Inc., Advanced Wireless Technologies i EFF. Glavni dizajner bio je Paul Kocher, predsjednik Cryptography Research, Inc.. Stroj se sastojao od 1856 čipova AWT-4500 (nazvanih "Deep Crack") raspoređenih u 6 kućišta od po 29 matičnih ploča (jedna je prikazana na slici 6.1.) sa 64 čipova na svakoj. Svako kućište imalo je posebno osobno računalo koje je služilo kao poslužitelj ključeva. Takav stroj stajao je nešto ispod 250 tisuća dolara i mogao je pretražiti preko 90 * 109 ključeva u sekundi. To je skoro 3 puta više od najveće brzine koju je distributed.net razvio u prethodnom DES Challengeu, no još uvijek za tri reda veličine sporije od Wienerovog stroja od 100 tisuća dolara. Tom brzinom bilo bi mu potrebno oko 5 dana za pretragu cijelog prostora 56-bitnih ključeva. No, ključ je pronašao u svega 56,05 sati pretraživši 24,8 posto prostora ključeva. Ključ je glasio: 3E CD A1 5E 70 4F B3 1C, a čisti tekst: "The unknown message is: It's time for those 128-, 192-, and 256-bit keys"
DES Cracker se, kao što je već rečeno, sastojao od osobnih računala i posebno dizajniranih čipova. Za razliku od distributed.net sustava u kojem postoji poslužitelj ključeva koji samo distribuira ključeve klijentima, poslužitelj ključeva u DES Cracker sustavu obavljao je i dio dekripcija. Naime, AWT-4500 čipovi pretraživali su dijelove prostora ključeva i eliminirali ključeve koji nedvojbeno ne daju čisti tekst koji se sastoji samo od ASCII znakova. Osobna računala spojena na kućišta sa čipovima imala su zadatak da čipovima daju dijelove prostora ključeva koje trebaju pretražiti i da od čipova uzimaju potencijalne čiste tekstove. Ovaj način rada prihvaćen je jer je kompliciraniju logiku, koja je potrebna za provjeravanje je li neki čisti tekst prihvatljiv, jednostavnije programirati u višim programskim jezicima nego direktno u sklopovlju.
Obzirom na to da prihvatljivih ASCII znakova ima 69, a byte ima 256 vrijednosti, to znači da je prihvatljivih vrijednosti otprilike jedna četvrtina. U kriptiranom tekstu ima 8 byteova, što znači da prihvatljivi čisti tekstovi čine ([1/4])8=[1/65536] prostora ključeva. Kako je RSA u svom Challengeu dao kriptirani tekst dugačak 2 puta po 64 bita, onda se ovaj omjer može udvostručiti i proizlazi da sklopovski dio sustava eliminira sve osim 224 = 16777216 ključeva, što su tadašnja osobna računala mogla obraditi u razumnom vremenu.
DES Cracker je i najvećim skepticima toga vremena dokazao ono u što su mnogi već godinama bili sigurni: moguće je izgraditi stroj koji će obaviti napad grubom silom u prihvatljivom vremenu. Obzirom na to da je cijena ovog stroja bila sasvim prihvatljiva za jednu vladinu agenciju ili bilo koju organizaciju koja raspolaže sa proračunom koji se mjeri u milijunima dolara, postalo je sasvim jasno da je DES u potpunosti beskoristan kao zaštita od napadača koji raspolaže sa većim proračunom.

6.3.4  RSA DES Challenge III

Posljednji DES Challenge započeo je skoro dvije godine nakon prvog, 18. siječnja 1999. u 9 sati ujutro po pacifičkom vremenu. Obzirom na to da je ključ u prethodnom DES Challengeu pronađen u roku od 56 sati, RSA je odlučila ponuditi nagrade samo za rješenja u kraćem roku. Nagrade su popisane u tablici 6.3.
Tablica 6.16: Odnos vremena pretraživanja i nagrada za RSA DES Challenge III
Vrijeme pronalaska rješenjaNagrada
Manje ili jednako 24 sata10.000 $
Više od 24 sata ali manje ili jednako od 48 sati5.000 $
Više od 48 sati ali manje ili jednako od 56 sati1.000 $
Točan ključ RSA dobila je nakon svega 22 sata i 15 minuta. Novi rekord postavili su distributed.net i EFF DES Cracker zajedno, tako što je distributed.net uključio DES Cracker u svoj sustav kao još jednog klijenta. Traženi ključ bio je 92 2C 68 C4 7A EA DF F2, a čisti tekst kriptirane poruke glasio je "The unknown message is: See you in Rome (second AES conference, March 22-23, 1999)". Ključ je pronađen nakon provjerenih 16 * 1015 ključeva, što čini 22,2% prostora ključeva.
U prošlim Challengeima DES Cracker pokazao se kao mnogo brži od distributed.net sustava: u DES Challenge II-2 DES Cracker konstantno obrađivao je 3 puta više ključeva u sekundi od najveće brzine koju je razvio distributed.net. No, svega malo više od 4 sata nakon što su distributed.net i DES Cracker paralelno počeli tražiti ključ, distributed.net dostigao je EFF-ov stroj i do kraja pretrage je obrađivao skoro dvostruko više ključeva nego DES Cracker (vidjeti sliku 6.2.). Prosječna brzina pretrage ključeva bila je 199 milijardi ključeva u sekundi, a najveća postignuta brzina bila je 250 milijardi ključeva u sekundi.
Slika 6.12: Brzina pretrage za distributed.net i DES Cracker
Traženi ključ pronašao je DES Cracker, no to ne govori ništa o brzini ili kvaliteti algoritama kojima se služio distributed.net klijent. Kako je brzina pretraživanja DES Crackera bila otprilike jednaka brzini pretraživanja ostatka distributed.net sustava, vjerojatnost da upravo DES Cracker pronađe ključ bila je oko 50%.

6.4   COPACOBANA

Slika 6.13: Izgled COPACOBANA sustava sa 19 modula
Završetkom posljednjeg DES Challengea postalo je apsolutno jasno da DES više nije upotrebljiv obzirom na to da je razbijen u manje od jednog dana. Daljnji natječaji nisu bili potrebni i na polju napada na DES grubom silom nije bilo novosti sve do 2006. kada je predstavljen A Cost-Optimized Parallel Code Breaker (COPACOBANA).[25]
COPACOBANA-u je dizajnirala skupina znanstvenika sa dvaju njemačkih sveučilišta: Sveučilišta Ruhr iz Bochuma i Sveučilišta Christian-Albrechts iz Kiela[24]. Ovaj sustav dizajniran je kako bi se koristio za obavljanje zadataka koje je moguće paralelizirati, a koji zahtijevaju velik broj operacija. Težište je stavljeno na pretraživanje prostora ključeva simetričnih kriptoalgoritama, tako da je sklopovlje COPACOBANA sustava optimirano za napade grubom silom. Za prvu prezentaciju ovog sustava korišten je napad na DES.
Osnovna ideja vodilja pri dizajnu ovog sustava bila je niska cijena. Što je više moguće korištena su već gotova rješenja kako bi se smanjio trošak izrade. Stoga je kao osnova korištena FPGA arhitektura, tako da cijeli COPACOBANA sustav stoji manje od 9 tisuća eura. Prednosti korištenja FPGA pored niske cijene je i reprogramabilnost, tako da je COPACOBANA-u moguće koristiti za napad na razne kriptosustave, ne nužno samo za napad na DES. S druge strane, FPGA sustavi podosta su sporiji od ASIC sustava koji bi bili neusporedivo brži, ali i neusporedivo skuplji od sustava temeljenih na FPGA.
COPACOBANA sustav sastoji se od 120 FPGA-ova (Spartan-3 xc3s1000) organiziranih u 20 modula (6 FPGA po modulu). Sustav ima USB port tako da je moguće više COPACOBANA sustava spojiti na isto računalo i koristiti ih paralelno. Svaki od 6 FPGA na modulu ima četiri DES enginea i svaki od njih u jednom periodu clocka može obaviti jednu enkripciju. To znači da pri taktu od 100MHz jedan FPGA može obaviti 400 milijuna enkripcija u sekundi. Cijeli sustav pronalazi ključ za DES-om kriptirani tekst u prosječnom roku od 8,7 dana.
Usporedi li se COPACOBANA sustav sa DES crackerom opisanim u poglavlju 6.3.3., primjećuje se znatan napredak. U svega 8 godina cijena sustava koji razbija DES u nekoliko dana pala je za oko 30 puta. Da se COPACOBANA prijavila na DES Challenge i pobijedila, nagrada od 10 tisuća dolara pokrila bi njihove troškove rada, dok je EFF morao uložiti znatna sredstva u izradu DES crackera.

6.5  Tajne implementacije

Osim COPACOBANA sustava, javno nije poznato je li još netko pokušao implementirati sustav za napad grubom silom na DES, no s velikom sigurnošću može se pretpostaviti da postoje tajne implementacije takve vrste. Autori COPACOBANA sustava u [24] iznose tvrdnju da bi ASIC sustav, koji stoji 1 milijun dolara, mogao pronaći ključ dužine 112 bita u prosječno 1,3 dana (COPACOBANA sustavu od 1 milijun dolara trebalo bi 262 dana). Logično je očekivati da si svjetske tajne službe mogu priuštiti takav sustav za napad na DES grubom silom.
Vrlo je vjerojatno da su tajni sklopovski sustavi za napad na DES postojali i ranije. Više puta iz raznih izvora potvrđena je činjenica da je NSA pomogla IBM-u da učini DES maksimalno otpornim na diferencijalnu kriptoanalizu. Vrlo česta interpretacija ove činjenice kaže da je NSA već sredinom sedamdesetih godina 20. stoljeća posjedovala potrebnu tehnologiju za napad na DES u prihvatljivo kratkom vremenu.

7  Praktični rad

U prethodnim poglavljima pokazano je da je napad grubom silom jedini u praksi provodivi napad poznatim čistim tekstom na DES kriptosustav. Kada je bilo potrebno izvesti stvarni napad na DES, napadači su se bez iznimke odlučili za napad grubom silom: DESCHALL i distributed.net projekti pretraživali su prostor ključeva koristeći distribuirani sustav od više tisuća računala, dok je EFF dizajnirao i proizveo stroj koji je bio prilagođen napadu na DES na sklopovskoj razini. U praksi nije zabilježen niti jedan pokušaj napada na puni DES kriptosustav od 16 rundi koji nije bio inačica napada grubom silom.
Dakle, kod napada na DES jedina strategija koja ima smisla jest napad grubom silom. Zbog toga, u praktičnom dijelu ovog rada izvedene su tri implementacije DES kriptosustava: objektna, funkcijska i sklopovska implementacija. Svaka od ovih implementacija potom je korištena kako bi se razvio jednostavni sustav za napad na DES.

7.1  Testna okolina

Brzine izvođenja napada grubom silom mjerena su na Compaq Evo N160 prijenosnom računalu opremljenom sa Intelovim Mobile Pentium III procesorom frekvencije rada 1 GHz, 256 MB RAM-a i operativnim sustavom Windows XP.

7.2  Funkcijska implementacija

Kao primjer funkcijske paradigme odabran je jezik Common Lisp (CL). CL jest standard koji ima razne implementacije. U ovom diplomskom radu korištena je jedna od tri najpopularnije implementacije CL standarda: clisp.
Pri implementaciji naglasak je stavljen na čisto funkcionalnu paradigmu. CL kao standard podržava imperativno, objektno orijentirano i funkcionalno programiranje, no za potrebe ovog rada pri implementaciji naglasak je stavljen na čisto funkcionalni podskup CL standarda. Od imperativnih svojstava CL-a korišteno je pridruživanje vrijednosti globalnoj varijabli, ali samo sa svrhom jasnoće koda. Primjerice, sadržaji S-kutija prvo su pridruženi varijabli, a zatim se ta varijabla koristi u funkcijama umjesto eksplicitnog navođenja sadržaja S-kutije. Nuspojave (engl. side effects), drugo obilježje imperativnog programiranja, u potpunosti su izbjegnute. Cijela implementacija DES algoritma u CL-u uzima 268 linije koda bez komentara.
Implementacija je izrazito jednostavna za korištenje: ima dvije glavne funkcije: 45 DES-encrypt i 45 DES-encrypt-dec. Obje primaju podatak kao string od 16 heksadecimalnih znamenki i vraćaju kriptirani tekst u istom takvom obliku. Prva funkcija prima ključ isto kao i podatak (kao string od 16 heksadecimalnih znamenki), dok je druga prilagođena korištenju za napad grubom silom: kao ključ prima cjelobrojnu vrijednost. Primjer korištenja tih dviju glavnih funkcija dan je u ispisu 7.1.
(print (DES-encrypt "0123456789ABCDEF" "133457799BBCDFF1"))
(print (DES-encrypt-dec "0123456789ABCDEF" 1383827165325090801))
Ispis 7.1: Primjer korištenja glavnih funkcija CL implementacije

7.2.1  Brzina izvođenja

Napad grubom silom, u osnovi, sastoji se od velikog broja enkripcija ili dekripcija (ovisno o tome radi li se o napadu poznatim kriptiranim ili poznatim čistim tekstom). Mjerenje brzine implementacije izvodi se petljom koja iterira ključeve od vrijednosti do 18446744073709551615, što je maksimalna vrijednost koju 64-bitni ključ može imati. Program koji je korišten za mjerenje brzine dan je u ispisu 7.2.
(defun cycle (key step start-time)
(if (= (mod key step) 0)
(print-time key start-time))
(DES-encrypt-dec "0123456789ABCDEF" key))
(defun brute-force (min max step start-time)
(loop for key from min to max
do (cycle key step start-time)))
;main:
(setq *start* (get-internal-real-time))
(brute-force 0 18446744073709551615 2048 *start*)
Ispis 7.2: Program za mjerenje brzine brute force napada
Vrijeme izvođenja napada bilo je 1 dan. Nakon 24 sata kontinuiranog rada program je prekinut. Prosječno su obavljene 34,33 enkripcije u sekundi. Na slici 7.1. vidi se kako se brzina rada programa mijenjala kroz dan. Obzirom na to da je mjerilo prilično sitno, prvi sat obrade izdvojen je u slici 7.2.
Slika 7.14: Brzina CL implementacije kroz 1 dan
Slika 7.15: Brzina CL implementacije kroz 1 sat

7.3   Objektno orijentirana implementacija

Kao primjer objektno orijentiranog jezika za implementaciju DES-a odabran je C#. Ovaj jezik dizajnirala je tvrtka Microsoft Corporation i 2001. predložila kao standard, iste godine C# je postao ECMA standard, a 2003. i ISO standard.
C# je čisto objektni jezik. Svi tipovi podataka naslijeđuju klasu 45 System.Object i time je svaki tip podataka u C#u objekt. Na prvi pogled vidjiva je razlika između čisto funkcijskog jezika, kao što je funkcijski podskup CL-a i čisto objektnog jezika, kao što je C#. Za razliku od jednostavnosti i matematičkog opisa procesa koji se dešavaju između ulaznih i izlaznih podataka, C# nudi strukturalnu dekompoziciju sustava, ali uz ponešto kompliciraniji zapis samog algoritma. Implementacija DES algoritma u C# jeziku dugačka je 312 linija koda bez komentara.
I ova implementacija izrazito je jednostavna za korištenje. Sastoji se od klase 45 DES koja ima metodu 45 Kriptiranje. Isto kao i kod implementacije u CL-u, postoje dvije različite implementacije te metode koje se razlikuju samo u načinu na koji primaju ključ. Primjeri korištenja tih metoda dani su u ispisu 7.3.
Console.WriteLine(
des.Kriptiraj("0123456789ABCDEF", "133457799BBCDFF1", 16));
Console.WriteLine(
des.Kriptiraj("0123456789ABCDEF", 1383827165325090801, 16));
Ispis 7.3: Primjer korištenja glavnih funkcija C# implementacije

7.3.1  Brzina izvođenja

Napad grubom silom izveden je jednako kao i kod CL implementacije. Brzina izvođenja C# implementacije (367,8 enkripcija u sekundi) znatno je veća od one koju je imala CL implementacija zato što se C# kompilira u Common Intermediate Language, jezik prilično niske razine koji direktno zahvaća komponente Common Language Runtimea koje su već optimirane i kompilirane. S druge strane, CL je klasični interpreterski jezik koji kompilaciju i optimizaciju koda obavlja pri samom izvršavanju programa, što ga čini znatno sporijim od C# jezika.
Podatci su obrađeni na isti način, jedina razlika je u tome što je za detaljniji prikaz (slika 7.4.) uzeto razdoblje od samo 10 minuta (umjesto jednog sata kao u slučaj CL-a) zbog toga što je C# implementacija znatno brža.
Slika 7.16: Brzina C# implementacije kroz 1 dan
Slika 7.17: Brzina C# implementacije kroz 10 minuta

7.4  Sklopovska implementacija

Najčešći oblik enkripcije danas je računalna enkripcija. Kriptoalgoritmi se koriste u programima, pa su stoga i sami računalni programi. Kada je DES dizajniran, dakle sredinom 70-ih godina 20. stoljeća, dominantan način enkripcije bio je sklopovska enkripcija. Dizajnirani su sklopovi koji su primali bitove ulaznog podatka i ključa, a na izlazu davali kriptirane bitove. Stoga je DES dizajniran tako da bude pogodan za sklopovsku implementaciju. Primjerice, način na koji su osmišljene S-kutije izrazito je pogodan za paralelizaciju. Operacija nad svakom S-kutijom može se izvoditi zasebno. Stoga je za treći način implementacije DES algoritma izabrana sklopovska implementacija.
Sklop je dizajniran u jeziku VHSIC hardware description language (VHDL). To je, uz Verilog, najpopularniji industrijski standard za jezik za opis sklopovlja (engl. hardware description language). Za razliku od Veriloga koji se zasniva na C programskom jeziku, VHDL se zasniva na programskom jeziku Ada.
Sklop je dizajniran u Xilinxovim razvojnim alatima. Sam kod pisan je u Xilinx Project Navigatoru, rad sklopa simuliran je u ModelSimu dok je konačni sklop dizajniran u Xilinx Floorplaneru. Za simulaciju je korišten FPGA čip Spartan-3 xc3s1000. Kako bi taj sklop izgledao, kada bi se ovdje prikazana implementacija izvela u sklopovlju, vidljivo je na slici 7.5. Siva pozadina je sami Spartan-3 čip dok roza područje označava sklopovlje koje se koristi za enkripciju. Na slici 7.6. prikazan je detalj implementacije na kojem se vide osnovne ćelije i ulazno/izlazne jedinice FPGA sklopa i veze među nekima od njih.
Slika 7.18: Prikaz FPGA čip Spartan-3 xc3s1000 čipa pripremljenog za DES enkripciju
Slika 7.19: Detalj sklopovske implementacije DES-a
Pri dizajniranju sklopa korištena je bottom-up metoda izgradnje i sklop je od samog početka opisivan uglavnom strukturalno. To nije običaj pri dizajniranju u VHDL-u, strukturalnom opisu obično prethodi faza ponašajnog opisivanja cijelog sustava, no kao što je već napomenuto, DES je bio zamišljen tako da se sklopovski ostvaruje pa mu je strukturalnost inherentna. Ponašajno opisivanje cijelog algoritma samo bi kompliciralo stvari jer DES nije niti predviđen za ponašajno opisivanje.
Stoga su ponašajno opisane samo one komponente koje sintetizator zna sam implementirati u sklopovlju. Komponente koje su u VHDL-u opisane ponašajno ili prospajanjem signala su: registri "45 SR_registar" i "45 registar", posmačni registri "45 left_shifter_1", "45 left_shifter_2", permutacije "45 initial_permutation", "45 reverse_initial_permu-tation", "45 perm_choice_1", "45 perm_choice_2", "45 expansion", "45 perm_p", kombinacijske funkcije "45 parity_byte", "45 round_decoder", look-up tablice "45 sbox1" ... "45 sbox8" i 4-bitno brojilo "45 brojilo". Sve ove komponente ukratko su opisane u svojem izvornom kodu.
Jedna runda DES algoritma opisana je komponentom 45 round_n. Struktura te komponente prikazana je na slici 7.7. Crvenim obrubom označene su podkomponente koje čine 45 runda_n i naznačeno je ime VHDL entiteta kojim su opisane. Radi jednostavnosti signal clock nije prikazan.
Slika 7.20: Struktura komponente round_n
Slika 7.21: Struktura cijele implementacije
Na slici 7.8. prikazano je kako se komponenta 45 round_n uklapa u cijeli sustav i kako sustav funkcionira. Ulaz u sustav su bitovi ključa i bitovi ulaznog podatka koji se pohranjuju u ulazni registar. Kad signal reset prestane biti aktivan kreće rad brojila koje broji runde od 0 do 15. Ovisno o broju runde određuje se za koliko će se obaviti posmak materijala ključa kako bi se dobio podključ za tu rundu. Nakon što obavi 16 iteracija, brojilo staje i daje signal da je algoritam gotov. Registar za kašnjenje usporava taj signal za jedan clock, kako bi se signal na izlazu stabilizirao i zatim daje signal izlaznom registru da postavi bitove izlaza.
Kako to izgleda u praksi vidi se na slici 7.9. Nakon što je podatak postavljen na ulaz, podiže se signal 45 start. Inverz tog signala spojen je na ulazni signal 45 reset i u trenutku kada start postane aktivan, reset pada u nulu, što pokreće brojilo. Nakon 20 ciklusa clocka na izlazu se pojavljuje kriptirani tekst, a jedan clock kasnije signal 45 finished postaje aktivan i podatak na izlazu je konačan.
Slika 7.22: Prikaz signala pri enkripciji jednog bloka podataka

7.4.1  Brzina izvođenja

Cijeli gore opisani proces traje 21 signal clocka (skraćeno 21 CLK). Dakle, brzina enkripcije jednog čistog teksta ovisi o trajanju 1 CLK. Obzirom da vodiči kojima su povezani blokovi imaju određenu duljinu, signalu je potrebno neko vrijeme za propagiranje od jedne do druge ćelije. Signalu neko vrijeme treba i za prolaz kroz FPGA ćeliju. Stoga je jasno da se sklopovske operacije ne mogu obavljati trenutno, te da CLK ne može biti beskonačno kratak. Ukoliko se CLK skrati previše, prijelazne pojave postaju vidljive na izlazima iz sklopa i simulator javlja nedefiniranu vrijednost na izlaznim signalima.
Vlastita implementacija sklopa iskušana je na raznim trajanjima CLK-a i utvrđeno je da CLK od 16 ns daje prihvatljive rezultate, no da kod trajanja CLK-a od 15 ns prijelazne pojave izlaze na vidjelo. Stoga je kao duljina CLK-a uzeta vrijednost od 20 ns, kako bi se ostavila određena sigurnosna margina do u praksi utvrđenog limita od 16 ns. Duljini CLK-a od 20 ns odgovara frekvencija rada od 62,5 MHz.
Kako je duljina jednog CLK-a 20 ns, a jedna enkripcija traje 21 CLK, onda je ukupno vrijeme jedne enkripcije jednako 420 ns. Tom brzinom moguće je u sekundi obaviti 2,38 milijuna enkripcija.
U poglavlju 6.3.3. iznesen je podatak da Deep Crack sa svojih 1825 čipova može obaviti 90 * 109 enkripcija u sekundi. To daje brzinu od 49,32 milijuna enkripcija u sekundi po jednom čipu, što je samo 20,7 puta brže od ovdje prikazane implementacije.
Sustav COPACOBANA, opisan u poglavlju 6.4. ostvaren je u istoj tehnologiji (Spartan-3 xc3s1000) koja je korištena za simulaciju sklopa opisanog u ovom poglavlju. Jedan FPGA u COPACOBANA sustavu može obaviti 400 milijuna enkripcija u sekundi na taktu od 100 MHz. To je 6,4 puta brže od ovdje prikazane implementacije. Uzme li se u obzir to da jedan COPACOBANA FPGA ima četiri DES enginea, tada brzina samo jednog DES enginea iznosi 100 milijuna enkripcija u sekundi, što je samo 1,6 puta brže od u ovom radu prikazane implementacije. Ukoliko bi se radni takt ove implementacije podignuo sa 62,5 MHz na 100 MHz, to bi značilo porast od 1,6 puta i brzina našeg ovdje opisanog sklopa bila bi jednaka brzini jednog COPACOBANA DES enginea.

7.5  Zaključno razmatranje

Niti diferencijalna niti linearna kriptoanaliza nisu uspjele kompromitirati DES, makar su ukazale na slabosti u mnogim drugim algoritmima. Razlog tome je velik broj podataka potreban da bi se puni DES od 16 rundi uspješno napao. Da bi se uspješno obavio napad diferencijalnom kriptoanalizom, potrebno je 247 odabranih čistih tekstova. Prevedeno u prostor na disku, to je skoro 135 milijuna gigabajta. Linearna kritpoanaliza punog DES-a zahtjeva nešto manje tekstova: 243 poznatih čistih tekstova, no to je još uvijek preko 8 milijuna gigabajta. Cijena samo pribavljanja tolikog memorijskog prostora bila bi za nekoliko redova veličina veća od cijene sklopovske implementacije napada grubom silom.
Tek sa RSA DES Challengeom pokazano je da DES više nije prihvatljiv kao standard. U tablici 7.1. prikazane su brzine kojima je pronađen ključ napadom grubom silom. Vidljivo je da je svakim novim napadom bitno smanjeno potrebno vrijeme za pronalaženje ključa. Posljednji napad trajao je manje od 24 sata što je bila definitivna potvrda da je DES kriptoalgoritam sa ključem od 56 korisnih bitova zastario.
Tablica 7.17: Usporedni prikaz svih DES Challengea
DES ChallengePočetak natječajaVrijeme pretragePretraženoNajveća brzina
pretrage
I28.1.1997.89 dana51,8%7 * 109
II-113.1.1998.39 dana88,4%34,4 * 109
II-213.7.1998.56 sati i 3 minute24,8%90 * 109
III18.1.1999.22 sata i 15 minuta22,2%250 * 109
Kao rezultat RSA DES Challengeova iz 1997. i 1998. godine, u listopadu 1999. godine DES je potvrđen kao standard, ali u inačici Triple DES. Već dvije godine kasnije za standard je izabran potpuno novi algoritam, Rijndael.
Unatoč tome što DES Challengei nisu nastavljeni, trend pojednostavljivanja napada grubom silom nije se zaustavio, tako da je manje od 10 godina nakon predstavljanja DES Crackera ponovo javno predstavljen sličan sklop, COPACOBANA. Uz usporedivu brzinu cijena uređaja je smanjena za 30 puta.
Tablica 7.18: Usporedni prikaz brzine implementacija danih u praktičnom radu
ImplementacijaProsječno enkripcija
u sekundi		Prosječno trajanje
napada grubom silom
Funkcijska3417*109 godina
Objektna3671,6*109 godina
Sklopovska2380000246*103 godina
U tablici 7.2. sažeti su rezultati praktičnog rada. Praktičnim radom pokazano je da su osobna računala još uvijek prespora da bi implementacije koje se zasnivaju na njima bile upotrebljive. No, isto je tako pokazano da je uz relativno oskudne resurse moguće razviti upotrebljiv sklop za napad na DES, kao što je to učinio projekt COPACOBANA.
To govori još jednu bitnu stvar o DES-u. U vrijeme kada se kriptoalgoritmi koriste najviše u svrhu kriptiranja podataka u računalnim programima, kriptoalgoritam predviđen za izvođenje na sklopovlju nema smisla upotrebljavati. Naime, izvođenje DES-a u programskim paketima usporeno je činjenicom da je algoritam optimiran za izvođenje u sklopovlju, dok ista ta činjenica ubrzava izvođenje napada grubom silom koji se mahom implementiraju u sklopovlju. Tako svojstva samog algoritma rade upravo suprotno od onog što bi algoritam trebao činiti.
No, uzme li se u obzir činjenicu spomenutu u uvodu ovog rada, da je DES imao radni vijek od preko 20 godina, sve ove zamjerke postaju nebitne. U vremenu kad je osmišljen, DES je bio izvanredno dobar algoritam. Napadi (različiti od trivijalnog napada grubom silom) pojavili su se u javnosti tek petnaestak godina nakon što je proglašen standardom, no čak ni tada nisu uspjeli razbiti ga brže nego napad grubom silom.

8  Zaključak

U ovom radu detaljno je opisan DES algoritam i napadi na njega. Glavni rezultat ovog rada može se sažeti kao: pokazano je da ne postoji bolji napad na DES od napada grubom silom. Kada god je (javno) uspješno izveden napad na DES, radilo se o napadu grubom silom. Upravo to i jest razlog što je DES bio standard preko 20 godina.
Niti diferencijalna niti linearna kriptoanaliza nisu uspjele srušiti DES, makar su ukazale na slabosti u mnogim drugim algoritmima. Razlog tome je velik broj podataka potreban da bi se puni DES od 16 rundi uspješno napao.
Praktičnim radom pokazano je da su osobna računala još uvijek prespora da bi implementacije koje se zasnivaju na njima bile upotrebljive. No, isto je tako pokazano da je uz relativno oskudne resurse moguće razviti upotrebljiv sklop za napad na DES, kao što je to učinio projekt COPACOBANA.

9. Literatura

[1]
R. Ashruf. The AES targeted on the MOLEN processor. Master's thesis, Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, 2004.
[2]
E. Biham. New types of cryptanalytic attacks using related keys. Lecture Notes in Computer Science, 765:398-??, 1994.
[3]
E. Biham and A. Biryukov. An improvement of Davies' attack on DES. Journal of Cryptology: the journal of the International Association for Cryptologic Research, 10(3):195-205, Summer 1997.
[4]
E. Biham and A. Shamir. Differential cryptanalysis of DES-like cryptosystems (invited talk), (extended abstract). Lecture Notes in Computer Science, 537:2-??, 1991.
[5]
A. Biryukov and D. Wagner. Slide attacks. Lecture Notes in Computer Science, 1636:245-259, 1999.
[6]
K. W. Campbell and M. J. Wiener. DES is not a group. In CRYPTO '92: Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, pages 512-520, London, UK, 1993. Springer-Verlag.
[7]
D. Coppersmith. The Data Encryption Standard (DES) and its strength against attacks. IBM Journal of Research and Development, 38(3):243-250, May 1994.
[8]
M. Curtin and J. Dolske. A brute force search of DES keyspace. ;login: The USENIX Magazine, May 1998.
[9]
J. Daemen, L. Knudsen, and V. Rijmen. The block cipher SQUARE. Lecture Notes in Computer Science, 1267:149+, 1997.
[10]
D. Davies and S. Murphy. Pairs and triplets of DES s-boxes. Journal of Cryptology, 8(1):1-25, 1995.
[11]
W. Diffie and M. Hellman. Exhaustive cryptanalysis of the NBS Data Encryption Standard. IEEE Computer, 10:74-84, 1977.
[12]
A. Dujella. Kriptografija. Priručnik za studente Prirodoslovno-matematičkog fakulteta.
[13]
E. F. Foundation. Cracking DES: Secrets of Encryption Research, Wiretap Politics and Chip Design. O'Reilly & Associates, Inc., Sebastopol, CA, USA, 1998.
[14]
C. Harpes, G. G. Kramer, and J. L. Massey. A generalization of linear cryptanalysis and the applicability of Matsui's piling-up lemma. Lecture Notes in Computer Science, 921:24-??, 1995.
[15]
C. Harpes and J. L. Massey. Partitioning cryptanalysis. Lecture Notes in Computer Science, 1267:13-??, 1997.
[16]
H. M. Heys. A tutorial on linear and differential cryptanalysis. Cryptologia, XXVI(3):189-221, 2002.
[17]
B. S. K. Jr., R. L. Rivest, and A. T. Sherman. Is the data encryption standard a group? In Proc. of a workshop on the theory and application of cryptographic techniques on Advances in cryptology-EUROCRYPT '85, pages 81-95, New York, NY, USA, 1988. Springer-Verlag New York, Inc.
[18]
J. Kelsey, T. Kohno, and B. Schneier. Amplifed boomerang attacks against reduced-round MARS and Serpent, 2000.
[19]
J. Kelsey, B. Schneier, and D. Wagner. Key-schedule cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES. Lecture Notes in Computer Science, 1109:237-251, 1996.
[20]
J. Kelsey, B. Schneier, and D. Wagner. Mod n cryptanalysis, with applications against RC5P and M6. Lecture Notes in Computer Science, 1636:139-155, 1999.
[21]
E. Kleiman. The XL and XSL attacks on Baby Rijndael. PhD thesis, Iowa State University, 2005.
[22]
L. Knudsen and D. Wagner. Integral cryptanalysis (extended abstract).
[23]
L. R. Knudsen. Truncated and higher order differentials. In Fast Software Encryption, pages 196-211, 1994.
[24]
S. Kumar, C. Paar, J. Pelzl, G. Pfeiffer, and M. Schimmler. COPACOBANA a cost-optimized special-purpose hardware for code-breaking. fccm, 0:311-312, 2006.
[25]
S. Kumar, C. Paar, J. Pelzl, G. Pfeiffer, and M. Schimmler. How to break DES for 8,980 euros in 9 days. In Proc. of the 2nd International Workshop on Special-Purpose Hardware for Cryptanalytic Applications (SHARCS'06), Cologne, Germany, April 2006.
[26]
S. Lucks. The saturation attack - a bait for Twofish. In Preproceedings of FSE.
[27]
M. Matsui. Linear cryptanalysis method for DES cipher. Advances in Cryptology - EUROCRYPT '93, 765/1994:386-397, 1994.
[28]
M. Matsui and A. Yamagishi. A new method for known plaintext attack of FEAL cipher. In Advances in Cryptology - EUROCRYPT '92, volume 658/1993 of Lecture Notes in Computer Science, pages 81-91. Springer Berlin / Heidelberg, 1992.
[29]
S. Murphy and M. Robshaw. Comments on the security of the AES and the XSL technique, 2002.
[30]
J. J. G. Savard. Quadratic cryptanalysis.
[31]
D. Wagner. The boomerang attack. Lecture Notes in Computer Science, 1636:156-170, 1999.
[32]
M. J. Wiener. Efficient DES key search, technical report TR-244, carleton university. In William Stallings, Practical Cryptography for Data Internetworks. IEEE Computer Society Press, 1996.
[33]
Wikipedia. Cryptanalysis - wikipedia, the free encyclopedia, 2007. [Online; accessed 27-September-2007].
[34]
Wikipedia. Kerckhoffs' principle - wikipedia, the free encyclopedia, 2007. [Online; accessed 27-September-2007].
[35]
Wikipedia. XSL attack - Wikipedia, the free encyclopedia, 2007. [Online; accessed 27-September-2007].

Footnotes:

1rad nije dostupan na Internetu, dostupna je samo referenca

File translated from TEX by TTH, version 3.78.
On 8 Nov 2007, 12:28.