Salajase võtme krüptosüsteem DES

Ajalugu

Salajase võtme krüpteerimis/dekrüpteerimissüsteemi DES ajalugu ulatub tagasi 1970. aastate algusesse, kui IBM-is otsustati luua oma krüptosüsteem, mille kasutajatena nähti eraettevõtteid. Paariaastase töö tulemusena valmis neil "Luciferiks" kutsutud süsteem. See müüdi maha inglise kindlustusseltsile LLoyd's. Aastaks 1974. valmis "Luciferist" uus variant, milles võeti kasutusele võti pikkusega 128 bitti.
Samal ajal otsis Standardite ja Tehnoloogia Rahvuslik Instutuut (National Institute of Standards and Technology, NIST) krüpteerimisalgoritmi, mida kuulutada uueks riiklikuks standardiks. Sobivaks osutuski eelpool mainitud "Luciferi" uus versioon. Väidetavalt tutvus samal ajal sama "Luciferiga" ka Rahvusliku Julgeoleku Agentuur (National Security Agency, NSA), kus avastati suure ehmatusega, et juhul kui süsteem tuleb kasutusele kogu maailmas, ei ole nende kasutuses olevad ressursid võimelised "Luciferiga" ðifreeritud tekste mitte mingil moel lahti murdma. NSA nõudmisel vähendati tulevase DESi koodivõtme bittide arvu 56-le. Nüüd oli NSA oma arvutuste kohaselt võimeline 10-12 miljoni dollari eest ehitama masina, mis lahendaks võtme 20 tunniga. 1977. aasta juulis kuulutas NIST välja riikliku standardi DES (Data Encryption Standard).
Alates DESi avaldamisest on teda pidevalt (ja põhjalikult) uuritud. Samal ajal temast saanud maailmas kõige enam levinud krüptosüsteem, mida NIST on korduvalt (täpsemalt: iga 5 aasta tagant) üle vaadanud ja parandanud/täiendanud. Viimane ülevaatus toimus 1993. aastal ja jääb nähtavasti viimaseks, kuna arvutustehnika pidevalt kasvav võimsus on muutnud DESi ebaturvaliseks.

DESi olemus

DES on salajase võtmega sümmeetriline krüpteerimissüsteem: s.t. krüpteerimiseks ja dekrüpteerimiseks kasutatakse sama võtit. DES opereerib 64-bitiste andmeblokkidega kasutades 56-bitist võtit. Siinkohal mainiks ära, et tegelikult on kasutatav võti siiski 64-bitine, kuid iga üheksas bitt on eelneva 8 biti paarsuskontrolliks ja jääb seetõttu kasutusest välja.

Kasutatav võti

Võti koosneb 64 kahendnumbrist, millest 56 bitti genereeritakse juhuarvude generaatori abil ja on algoritmis otseselt kasutusel. Ülejäänud kaheksa bitti, mida algoritm ei kasuta, on kasutusel vigade avastamiseks. Need 8 vigu avastavat bitti saavad väärtuse "1", kui iga 8-bitise baidi paarsus on negatiivne (s.t. selles 8-bitises baidis omab väärtust "1" paaritu arv bitte). Krüpteeritud andmete autoriseeritud kasutajad peavad teadama võtit, mida kasutati andmete krüpteerimisel, juhul, kui soovitakse andmeid dekrüpteerida. Kuna kasutusel olev algoritm on teada kõigile, kes DESi kasutavad, peab võti olema unikaalne. Unikaalse võtme valik iga konkreetse programmi puhul kindlustab, et tulemuseks saadud krüptogramm on unikaalne. Erineva võtme valik põhjustab erineva krüptogrammi saamise suvaliste sisendaandmete korral. Krüpteeritud andmeid saab taastada ainult kasutades täpselt seda sama võtit, mida kasutati andmete krüpteerimisel. Algoritmiliselt ei ole võimalik krüptogrammi des^ifreerida: seega ei saa suvalised isikud, kes on pääsenud ligi krüpteeritud andmetele, teadmata võtit, andmeid dekrüpteerida. Kehtib ka vastupidine: isikud, kes teavad kasutatud võtit, saavad krüpteeritud andmed kerge vaevaga endale kasutuskõlbulikuks teha.

Kokkuvõtteks: krüpteeritud andmete turvalisus sõltub otseselt sellest, kui kaitstud on andmete krüpteerimiseks ja dekrüpteerimiseks kasutatav võti.

Võtmete osa lõpetuseks mainiks veel seda, et kasutatava algoritmi tõttu on olemas neli nõrka võtit ja kaksteist poolnõrka võtit. Nõrgad võtmed on sellised, mis antud võtmega juba krüpteeritud teksti krüpteerimisel tegelikult dekrüpteerivad. Poolnõrgad võtmed tulevad aga paarikaupa ja toimivad analoogiliselt nõrkade võtmetega: kui ühe poolnõrga võtmega krüptitud andmeid krüptida selle poolnõrga võtme paarilisega, toimub tegelikult dekrüpteerimine. Nüüd ei tasuks siiski ära ehmatada,sest olemas on 2⁵⁶=72,057,594,037,927,936 võimalikku DESi võtit ja võimalus valida nende seast nõrk või poolnõrk võti on sisuliselt üks 2⁵⁶-st. Seega ei tasu sellest eriti välja teha, kui võti valitakse tõesti juhuslikult. Pealegi ei mõjuta võtme kontrollimine kuigi palju krüpteerimisele kuluvat aega.

Algoritmi tööpõhimõte

Algoritm on disainitud ðifreerima ja deðifreerima 64 bitiseid andmeplokke kasutades selleks 64-bitist võtit. (NB! Plokkides sisalduvad bitid on nummerdatud vasakult paremale s.t. vasakpoolsim bitt on esimene.) Deðifreerimine peab toimuma sama võtmega, millega toimus ðifreerimine.Iga krüpteerimisele tulev plokk allutatakse esmalt algsele permutatsioonile IP, järgneb keeruline võtmest sõltuv arvutamine ja viimaks permuteerimine pööratud algse permutatsiooniga (IP^-1). Võtmest sõltuvat keerulist arvutamist võib lihtsamalt defineerida kui ðifreerimisfunktsiooni f ja võtmejärjekorraks nimetatava funktsiooni KS.
Järgnevalt aga: kuidas toimub ðifreerimine.

Eelnevalt sai lühidalt mainitud, et kõigepealt allutatakse krüpteeritav andmeplokk algsele permutatsioonile IP. See tähendab seda, et andmeploki bitid reastatakse ümber kindlas järjekorras. Järgneb 16 ðifreerimisfunktsiooni f iteratsiooni. Ðifreerimisfunktsiooni f tulemus on 32-bitine plokk (andmed), sisendiks aga kaks plokki; üks on 32-bitine (andmed) ja teine 48-bitine (tsükli alamvõti). Funktsiooni sisendiks olev 32-bitine plokk on moodustatud esimese iteratsiooni korral permuteeritud bittide jadast, võttes sealt lihtsalt 32 vasakpoolsemat bitti. Ülejäänud 32 parempoolse biti alusel koostab f uue 32 bitise ploki. Vasakpoolne plokk ja uus parempoolne plokk liidetakse mooduliga 2 (e. xor). Järgneb vasaku ja parema poole vahetus ning tegevus kordub. Milleks on sisse toodud funktsioon KS? Selle funktsiooni ülesanne on vastavalt iteratsiooni järjekorra numbrile ja krüptimisvõtmele (PEAB olema 64-bitine) koostada 48-bitine tsükli alamvõti, mis on ðifreerimisfunktsiooni f teiseks sisendiks. Kõige lõpuks toimub 16. iteratsiooni tulemuseks saadud ploki (kutsutakse eelväljundiks, pre-output) permuteerimine pööratud algse permutatsiooniga. Sellega on ðifreerimine lõppenud. Ðifreerimisprotsessi on kujutatud ka joonisel 1, et eelnev seletus natuke arusaadavam oleks.
Deðifreerimisel toimub vastupidine tegevus. Kõigepealt toimub nn. eelväljundi loomine rakendades sisendile pööratud algpermutatsiooni. Edasi toimub eelpoolkirjeldatud ðifreerimisalgoritmi täpselt vastupidine rakendamine, mille juures tuleks erilist tähelepanu pöörata sellele, et alati kasutataks õiget alamvõtit. Kui kõik iteratsioonid on läbitud, jääb veel üle rakendada tulemusele algset permutatsiooni ja lähtetekst ongi käes.

Joonis 1. Ðifreerimine

Tegelik algoritm sisaldab veel mõningaid komponente, kuid neid ei hakanud ma ära tooma. Kes on huvitatud algoritmist enesest, sellel soovitan uurida NISTi publikatsiooni FIPS 46-2.
Selle osa lõpetuseks mainin veel ära selle, et DESi on kasulik realiseerida riistvaras, kuna see annab võrreldes tarkvaralise lahendusega ligi 100-kordse kiiruse võidu. Absoluutarvudes: korralik DESi reliseeriv kiip suudab (de)krüpteerida gigabaidi jagu andmeid sekundis ja seda umbes 100 dollari eest..

DESi turvalisus

Olles nüüd enam-vähem tuttav DESi algoritmiga, kibeleb lugeja kindlasti küsima, et kas DES siiski liiga "kehv" ei ole. Mingit erilist andmete teisendamist nagu ei olekski toimunud, samuti on deðifreerimine sisuliselt sama mis ðifreerimine. Kartus DESi nõrkuse suhtes ei ole põhjendatud, kuna DESi loodi sellisena, et teda on võimalik lahendada ainult nn. ammendava otsingu teel. Vastupidist on püütud tõestada mitmeid kordi, kuid positiivset tulemust ei ole suudetud siiski saavutada. Nüüd aga tekib uus küsimus: kui DES siiski on niivõrd turvaline, siis miks ei uuendanud NIST standardit. Põhjus peitub nähtavasti selles, et tänapäevased arvutid on juba niivõrd võimasad, et nad suudavad mõeldava aja (antud juhul: umbes 1 kuu) jooksul krüpteeritud sõnumi avada. Samuti on võimalik Internetist ainult mõningase otsimisvaevaga leida programme, mis on loodud DESi kräkkimiseks. Samuti on saadaval sama otstarbega kiipide kirjeldusi (näiteks: VHDL-is), vala ainult ränisse ja pane tööle. Sellise kiibi valmistamine pidavat maksma 100 000 dollarit ringis (nüüd juba isegi vähem) ja lahenduse peaks ta leidma 21 päeva jooksul; 10 miljoni dollari eest on aga võimalik luua kiip, mis leiab lahenduse vähem kui ööpäevaga. NB! Need jõudlust näitavad arvud kehtivad ainult ühe kiibi kohta. Tänu DESi olemusele, saab kasutada paralleeltöötlust ja neid numbreid oluliselt vähendada. Toon siinkohal võrdluseks RSA Labs'i korraldatud DES II võistluse tulemused: krüptitud sõnum avati 39 päevaga, kusjuures kasutati tavalisi arvuteid. Mõtlemapanevad arvud...
Mida teha, et saladus siiski saladuseks jääks? Tavaliselt lahendatakse see mitmekordse krüpteerimisega, millest enamlevinud on neli varianti:

EEE-3

Ðifeerimine toimub kolme erineva võtmega.

EDE-3

Krüptimine toimub kolme erineva võtmega, kusjuures esimesel ja viimasel korral toimub ðifreerimine ja teisel korral deðifreerimine (sihilikult vale võtmega).

EEE-2

Ðifreerimine toimub kahe erineva võtmega, kusjuures esimese ja viimase ðifreerimise võtmed on samad.

EDE-2

Krüptimine toimub kahe erineva võtmega, kusjuures ðifreerimine toimub elguses ja lõpus ühe võtmega ning keskmine deðifreerimine teise võtmega

Levinud arvamus on, et kolmekordne DES on sama turvaline, kui kaks korda pikema võtmega DES. Uuritud seda väidet ei ole, nii et otsustamine jaab lugejale.

Aternatiivid DESile

Eelnevalt selgus, et DES ei sobi enam kõige paremini andmete salastamiseks. Seetõttu järgneb väike loetelu alternatiividest:

Kolmik-DES e. kolmekordne krüpteerimine sai juba mainitud
DES-X

DESi edasiarendus, kasutab lisaks tavalisele 56-bitisele võtmele kahte 64-bitist võtit. Turvalisuse kasv ei ole eriti suur, kuid ammendava otsingu läbiviimine on tunduvalt aeglasem.

G-DES

Üks teine DESi edasiarendus. Kasutab suuremat ploki suurust, kuid turvalisem ei ole, pigem vastupidi.

Üks teine DESi modifikatsioon kasutab 16 sõltumatut tsükli alamvõtit. Algoritm tuletab need algsest võtmest. See variant on turvalisem, kui DES ise.
FEAL (Fast Encryption ALgorithm)

Ei paku siiski sellist turvalisust, mis on olemas DESil. Uuemad versioonid pidavat olema kindlamad kasutada.

IDEA

Tundub olevat paljulubav, uuem kui FEAL, kuid ei ole veel pälvinud piisavat usaldusväärsust.

Skipjack

Mõne aasta eest valminud ja '98. aasta lõpus avalikutatud algoritm. Kuulub krüpteerimiskiibi Clipper koosseisu. Nähtavasti uus standard.

Kokkuvõtteks

Tuleb tunnistada, et tänaseks on DES juba vananenud. Ta on edukalt vastu pidanud kaks aastakümmet ja ootab omale uut järeltulijat. Arvata võib, et selleks saab eelnevalt mainitud Skipjack, kuivõrd tema on ainuke algoritm, mis on DESiga võimeline kiiruses võistlema.