Algoritam GOST 28147 89 je. Domaći standard šifriranja podataka. Varijacije na temu gosta
Za razliku od američkog DES-a, domaći standard koristi duži ključ - 256 bita. Osim toga, ruski standard predlaže korištenje 32 runde enkripcije, dok DES zahtijeva samo 16.
Dakle, glavni parametri algoritma za kriptografsku transformaciju podataka GOST 28147-89 su sljedeći: veličina bloka je 64 bita, veličina ključa je 256 bita, broj krugova je 32.
Algoritam je klasična Feishtelova mreža. Enkriptirani blok podataka podijeljen je na dva identična dijela, desni R i lijevi L. Desni dio se dodaje okruglom podključu i pomoću nekog algoritma šifrira lijevi dio. Prije sljedećeg kruga, lijevi i desni dio se mijenjaju. Ova struktura omogućuje korištenje istog algoritma i za šifriranje i za dešifriranje bloka.
Algoritam šifriranja koristi sljedeće operacije:
- zbrajanje riječi po modulu 2 32;
- ciklički pomaknuti riječ ulijevo za određeni broj bitova;
- zbrajanje po bitovima modulo 2;
- zamjena prema tablici.
U različitim koracima GOST algoritama, podaci na kojima rade tumače se i koriste na različite načine. U nekim se slučajevima podatkovni elementi tretiraju kao nizovi neovisnih bitova, u drugim slučajevima kao cijeli broj bez predznaka, u trećima kao da imaju strukturu složeni element, koji se sastoji od nekoliko jednostavnijih elemenata.
Okrugla struktura GOST 28147-89
Struktura jednog kruga GOST 28147-89 prikazana je na sl. 5.1.
Šifrirani blok podataka dijeli se na dva dijela, koji se zatim obrađuju kao zasebni 32-bitni cijeli brojevi bez predznaka. Prvo se desna polovica bloka i potključ kruga dodaju modulo 2 32. Zatim se izvodi zamjena blok po blok. 32-bitna vrijednost dobivena u prethodnom koraku (nazovimo je S) tumači se kao niz od osam 4-bitnih kodnih blokova: S=(S0,S1,S2,S3,S4,S5,S6,S7). Zatim se vrijednost svakog od osam blokova zamjenjuje novom, koja se bira iz tablice zamjene na sljedeći način: vrijednost bloka S i zamjenjuje se S i -tim elementom po redu (numeriranje od nule) i-tog zamjenskog čvora (tj. zamjenske tablice i-tog reda, numeriranje također od nule). Drugim riječima, element s brojem retka jednakim broju bloka koji se zamjenjuje i brojem stupca jednakim vrijednosti bloka koji se zamjenjuje kao 4-bitni nenegativan cijeli broj odabire se kao zamjena za vrijednost Gradska četvrt, kvart. Svaki red zamjenske tablice sadrži brojeve od 0 do 15 slučajnim redoslijedom bez ponavljanja. Vrijednosti elemenata tablice supstitucije uzimaju se od 0 do 15, budući da četiri bita koja se supstituiraju mogu sadržavati cijeli broj bez predznaka u rasponu od 0 do 15. Na primjer, prvi redak S-kutije može sadržavati sljedeće vrijednosti: 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11 . U ovom slučaju, vrijednost bloka S 0 (četiri najmanje značajna bita 32-bitnog broja S) bit će zamijenjena brojem na poziciji čiji je broj jednak vrijednosti bloka koji se zamjenjuje. Ako je S 0 = 0, tada će biti zamijenjen s 5, ako je S 0 = 1, tada će biti zamijenjen s 8 itd.
Riža. 5.1.
Nakon što se izvrši zamjena, svi 4-bitni blokovi ponovno se spajaju u jednu 32-bitnu riječ, koja se zatim rotira 11 bitova ulijevo. Na kraju, koristeći bitwise operaciju "zbroj modulo 2" rezultat se kombinira s lijevom polovicom, što rezultira novom desnom polovicom R i . Nova lijeva strana L i uzima se jednakom donjem dijelu pretvorenog bloka: L i = R i-1 .
Rezultirajuća vrijednost pretvorenog bloka smatra se rezultatom jednog kruga algoritma šifriranja.
Postupci šifriranja i dešifriranja
GOST 28147-89 je dakle blok šifra pretvorba podataka provodi se u blokovima u tzv osnovni ciklusi. Osnovne petlje sastoje se od ponovljenog izvođenja glavne runde o kojoj smo ranije govorili za blok podataka, koristeći različite ključne elemente i razlikuju se jedna od druge po redoslijedu kojim se ključni elementi koriste. Svaki krug koristi jedan od osam mogućih 32-bitnih podključeva.
Pogledajmo proces stvaranja okruglih podključeva. U GOST-u je ovaj postupak vrlo jednostavan, posebno u usporedbi s DES-om. 256-bitni ključ K podijeljen je na osam 32-bitnih podključeva, označenih kao K0, K1, K2, K3, K4, K5, K6, K7. Algoritam uključuje 32 kruga, tako da se svaki potključ tijekom enkripcije koristi u četiri kruga prema slijedu prikazanom u tablici 5.1.
| Krug | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Kompletna izgradnja | K 0 | K 1 | K2 | K 3 | K 4 | K5 | K 6 | K 7 |
| Krug | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| Kompletna izgradnja | K 0 | K 1 | K2 | K 3 | K 4 | K5 | K 6 | K 7 |
| Krug | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| Kompletna izgradnja | K 0 | K 1 | K2 | K 3 | K 4 | K5 | K 6 | K 7 |
| Krug | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
| Kompletna izgradnja | K 7 | K 6 | K5 | K 4 | K 3 | K2 | K 1 | K 0 |
Proces dešifriranja provodi se istim algoritmom kao i kodiranje. Jedina razlika je redoslijed kojim se K i potključevi koriste. Prilikom dešifriranja potključevi se moraju koristiti obrnutim redoslijedom, naime kako je navedeno u
Ovaj algoritam je obvezan za korištenje kao algoritam šifriranja u vladinim organizacijama Ruske Federacije i nizu komercijalnih.
Opis algoritma
Dijagram algoritma prikazan je na sl. 3.1. Kao što vidite, dizajn ovog algoritma je prilično jednostavan, što jasno pojednostavljuje njegovu softversku ili hardversku implementaciju.
Algoritam GOST 28147-89 šifrira informacije u blokovima od 64 bita, koji su podijeljeni u dva podbloka od 32 bita (N1 i N2). Podblok N1 se obrađuje na određeni način, nakon čega se njegova vrijednost zbraja
s vrijednošću podbloka N2 (zbrajanje se izvodi modulo 2), tada se podblokovi zamjenjuju. Ova se transformacija izvodi u određenom broju krugova: 16 ili 32, ovisno o načinu rada algoritma (opisano u nastavku). U svakom krugu izvode se sljedeće operacije:
1. Primjena ključa. Sadržaj podbloka /VI dodaje se modulo 2 32 s dijelom ključa Kx.
Ključ za šifriranje algoritma GOST 28147-89 ima dimenziju od 256 bita, a Kx je njegov 32-bitni dio, tj. 256-bitni ključ za šifriranje predstavljen je kao spoj 32-bitnih potključeva (slika 3.2):
Shch ATI, AG2, Yu, AG4, K5, Kb, K7.
Tijekom procesa enkripcije koristi se jedan od ovih podključeva, ovisno o okruglom broju i načinu rada algoritma.
Riža. 3.1. Dijagram algoritma GOST 28147-
Riža. 3.2. Ključ šifriranja algoritma GOST 28147-89
2. Zamjena stola. Nakon ključanja, /VI podblok se dijeli na 8 dijelova od po 4 bita, od kojih se vrijednost svakog pojedinačno zamjenjuje u skladu sa zamjenskom tablicom za ovaj dio podbloka. Zamjene tablica (Substitution box, S-box) često se koriste u modernim algoritmima šifriranja, pa ih vrijedi detaljnije razmotriti.
Zamjena tablice koristi se na ovaj način: blok podataka određene veličine (u ovom slučaju 4-bitni) se dovodi na ulaz, čiji numerički prikaz određuje broj izlazne vrijednosti. Na primjer, imamo S-box sljedećeg oblika:
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.
Neka na ulaz dođe 4-bitni blok “0100”, tj. vrijednost 4. Prema tablici izlazna vrijednost će biti jednaka 15, tj. “1111” (0 se zamjenjuje s 4, 1 s 11, vrijednost 2 ostaje nepromijenjena itd.).
Kao što vidite, dizajn algoritma je vrlo jednostavan, što znači da najveći teret enkripcije podataka pada na zamjenske tablice. Nažalost, algoritam ima svojstvo da postoje "slabe" zamjenske tablice pomoću kojih se algoritam može riješiti kriptoanalitičkim metodama. Slabi uključuju, na primjer, tablicu u kojoj je izlaz jednak ulazu:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
3. Bitski ciklički pomak ulijevo za 11 bita.
Načini rada algoritma
Algoritam GOST 28147-89 ima 4 načina rada:
□ jednostavan način zamjene;
□ gama način rada;
P gama mod sa Povratne informacije;
□ način razvoja privrženosti oponašanju.
Ovi načini se donekle razlikuju od općeprihvaćenih (opisanih u odjeljku 1.4), pa ih vrijedi detaljnije razmotriti.
Ovi načini imaju različite svrhe, ali koriste istu transformaciju enkripcije opisanu gore.
Jednostavan način zamjene
U jednostavnom načinu zamjene, svaki 64-bitni blok informacija jednostavno je šifriran korištenjem 32 runde opisane gore. 32-bitni podključevi koriste se u sljedećem nizu:
□ KO, Kl, K2, KZ, K4, K5, KB, AG7, KO, ATI itd. - u 1. do 24. kolu;
□ K1, Kb, K5, K4, KZ, K2, K\, KO - u rundama od 25. do 32.
Dešifriranje u načinu jednostavne zamjene izvodi se na potpuno isti način, ali s nešto drugačijim slijedom korištenja podključeva:
□ KO, K\, K2, KZ, K4, K5, Kb, KP - u 1. do 8. kolu;
□ KP, Kb, K5, K4, KZ, K2, K\, KO, K1, Kb itd. - u krugovima od 9 do 32.
Slično standardnom ECB načinu rada, zbog odvojene enkripcije blokova, jednostavni način zamjene strogo se ne preporučuje za šifriranje samih podataka; trebao bi se koristiti samo za šifriranje drugih ključeva šifriranja u shemama s više ključeva.
Gama način rada
U gama modu (Sl. 3.3), svaki blok otvorenog teksta dodaje se bit po bit modulo 2 u 64-bitni šifrirani gama blok. Gama šifra je posebna sekvenca koja se generira pomoću transformacija opisanih gore kako slijedi:
1. Njihovo početno punjenje zapisuje se u registre N1 i N2 - 64-bitna vrijednost koja se naziva "sinkronizacija poruka" (sinkronizacija je praktički analogna vektoru inicijalizacije u CBC, CFB i OFB modovima).
2. Sadržaj registara /VI i N2 (u ovom slučaju sinkronizirane poruke) šifriran je u jednostavnom načinu zamjene.
3. Sadržaji N1 zbrajaju se modulo (2 32 – 1) uz konstantu CI = 2 24 + 2 16 + 2 8 + 4, rezultat zbrajanja upisuje se u /VI registar.
4. Sadržaji N2 zbrajaju se modulo 2 uz konstantu C2 = 2 24 + 2 16 + 2 8 +1, rezultat zbrajanja upisuje se u registar N2.
5. Sadržaj /VI i N2 registara izlazi kao 64-bitni šifrirani gama blok (tj., u ovom slučaju, /VI i N2 tvore prvi gama blok).
6. Ako je potreban sljedeći gama blok (tj. potrebno je izvršiti daljnje šifriranje ili dešifriranje), vratite se na korak 2.
Za dešifriranje, gama se generira na sličan način, a zatim se šifrirani tekst i gama bitovi ponovno XOR-uju.
Da bi se generirao isti raspon šifre, korisnik koji dešifrira kriptogram mora imati isti ključ i istu vrijednost poruke sinkronizacije koji su korišteni prilikom šifriranja informacija. U suprotnom, neće biti moguće dobiti izvorni tekst iz šifriranog.
U većini implementacija algoritma GOST 28147-89, sinkronizacija nije tajni element, međutim, sinkronizacija može biti tajna kao i ključ za šifriranje. U ovom slučaju možemo smatrati da se efektivna duljina ključa algoritma (256 bita) povećava za još 64 bita sinkronizacijske poruke, što se može smatrati dodatnim ključnim elementom.
Gama način rada s povratnom spregom
U gama načinu rada s povratnom spregom, rezultat šifriranja prethodnog bloka otvorenog teksta koristi se za popunjavanje registara /VI i L/2, počevši od 2. bloka, ne prethodnog gama bloka, već rezultat šifriranja prethodnog bloka otvorenog teksta. (Slika 3.4). Prvi blok u ovaj način rada generira se potpuno slično prethodnom.
Riža. 3.4. Generiranje gama šifre u gama modu s povratnom spregom
Način proizvodnje imitacije priloga
Prefiks je kriptografski kontrolni zbroj izračunat pomoću ključa za šifriranje i dizajniran za provjeru integriteta poruka. Da biste ga izračunali, postoji poseban način algoritma GOST 28147-89.
Generiranje prefiksa imitacije izvodi se na sljedeći način:
1. Prvi 64-bitni blok informacija za koji se izračunava prefiks imitacije zapisuje se u registre N1 i N2 i šifrira u reduciranom načinu jednostavne zamjene, u kojem se izvodi prvih 16 krugova od 32.
2. Dobiveni rezultat se zbraja modulo 2 sa sljedećim blokom informacija, pohranjujući rezultat u N1 i N2.
3. M i N2 se ponovno šifriraju u skraćenom načinu jednostavne zamjene, itd. do posljednjeg bloka informacija.
Prefiks imitacije smatra se 64-bitnim rezultirajućim sadržajem registara N1 i N2 ili njihovim dijelom. Najčešće se koristi 32-bitni imitacijski prefiks, odnosno polovica sadržaja registara. Ovo je dovoljno, budući da je, kao i svaki kontrolni zbroj, privitak imitacije namijenjen, prije svega, zaštiti od slučajnog iskrivljavanja informacija. Za zaštitu od namjerne izmjene podataka koriste se druge kriptografske metode - prvenstveno elektroničke digitalni potpis(vidi odjeljak 1.1).
Prefiks imitacije koristi se na sljedeći način:
1. Prilikom šifriranja bilo koje informacije, prefiks imitacije otvorenog teksta se izračunava i šalje zajedno sa šifriranim tekstom.
2. Nakon dešifriranja, prefiks imitacije ponovno se izračunava i uspoređuje s poslanim.
3. Ako se izračunati i poslani prefiksi imitacije ne podudaraju, šifrirani tekst je iskrivljen tijekom prijenosa ili su korišteni netočni ključevi tijekom dešifriranja.
Prefiks imitacije posebno je koristan za provjeru točne dešifriranja ključnih informacija kada se koriste sheme s više ključeva.
Prefiks imitacije je neki analogni kod za provjeru autentičnosti MAC poruke, izračunat u CBC načinu rada; Razlika je u tome što se pri izračunavanju imitacijskog prefiksa ne koristi poruka sinkronizacije, dok se pri izračunavanju MAC-a koristi inicijalizacijski vektor.
Kriptografska snaga algoritma
Godine 1994. opis algoritma GOST 28147-89 preveden je na engleski i objavljen; nakon toga su se počeli pojavljivati rezultati njegove analize koju su proveli strani stručnjaci; međutim, dulje vrijeme nisu pronađeni napadi koji bi se približili izvedivosti.
□ velika duljina ključa - 256 bita; zajedno s tajnom porukom sinkronizacije efektivna duljina ključa raste na 320 bita;
□ 32 kruga transformacija; već nakon 8 krugova postiže se puni učinak disperzije ulaznih podataka: promjena jednog bita bloka otvorenog teksta utjecat će na sve bitove bloka šifriranog teksta, i obrnuto, tj. postoji višestruka margina snage.
Razmotrimo rezultate kriptoanalize algoritma GOST 28147-89.
Analiza supstitucijskih tablica
Budući da zamjenske tablice nisu navedene u standardu, brojni radovi (na primjer, u) sugeriraju da "nadležna organizacija" može izdati i "dobre" i "loše" zamjenske tablice. Međutim, poznati stručnjak Bruce Schneier takve pretpostavke naziva “glasinama”. Jasno je da kriptografska snaga algoritma uvelike ovisi o svojstvima korištenih zamjenskih tablica; sukladno tome, postoje slabe zamjenske tablice (vidi gornji primjer), čija upotreba može pojednostaviti napad algoritma. Ipak, mogućnost korištenja različitih zamjenskih tablica čini se kao vrlo vrijedna ideja, u prilog čemu se mogu navesti sljedeće dvije činjenice iz povijesti standarda šifriranja DES (za detalje, vidi odjeljak 3.15):
□ napadi koji koriste i linearnu i diferencijalnu kriptoanalizu DES algoritma koriste specifične značajke zamjenskih tablica; kada koristite druge tablice, kriptoanaliza će morati početi ispočetka;
□ pokušano je ojačati DES u odnosu na linearnu i diferencijalnu kriptoanalizu korištenjem robusnijih supstitucijskih tablica; takve tablice, koje su doista robusnije, predložene su, na primjer, u algoritmu s 5 DES; ali, nažalost, bilo je nemoguće zamijeniti DES sa s 5 DES, jer su zamjenske tablice strogo definirane u standardu, i sukladno tome, implementacije algoritma vjerojatno ne podržavaju mogućnost promjene tablica u druge.
Brojni radovi (na primjer, i ) pogrešno zaključuju da tajne tablice zamjene algoritma GOST 28147-89 mogu biti dio ključa i povećavaju njegovu efektivnu duljinu (što nije značajno, budući da algoritam ima vrlo veliku 256 -bitni ključ). Međutim, rad dokazuje da se tajne tablice zamjene mogu izračunati korištenjem sljedećeg napada, koji se može koristiti u praksi:
1. Postavlja se nulti ključ i traži se “nulti vektor”, tj. vrijednost z = /(0), gdje je /() okrugla funkcija algoritma. Ova faza traje oko 2 operacije šifriranja.
2. Koristeći nulti vektor, izračunavaju se vrijednosti zamjenskih tablica, što ne traje više od 2 11 operacija.
Modifikacije algoritama i njihova analiza
Rad je izvršio kriptoanalizu modifikacija algoritma GOST 28147-89:
□ GOST-H algoritam, u kojem je, u odnosu na izvorni algoritam, promijenjen redoslijed korištenja podključeva, naime u rundama se od 25 do 32 podključa koriste izravnim redoslijedom, tj. potpuno isto kao u prethodnim rundama algoritma;
□ 20-kružni GOST® algoritam, u kojem krug koristi XOR umjesto modulo-2 zbrajanja za preklapanje ključa.
Na temelju rezultata analize zaključeno je da su GOST-H i GOST© slabiji od izvornog algoritma GOST 28147-89, budući da oba imaju klase slabih ključeva. Vrijedno je napomenuti da se u smislu GOST© kriptoanalize rad ponavlja od riječi do riječi odjeljak posvećen kriptoanalizi algoritma GOST 28147-89, dobro poznatog rada objavljenog 2000. (bez ikakvih referenci na izvornik). Time se dovodi u pitanje profesionalnost autora rada i njegovi drugi rezultati.
U radu je predložena vrlo zanimljiva modifikacija algoritma: tablice S\…Ss nužno moraju biti različite; u svakom krugu algoritma moraju se preurediti prema određenom zakonu. Ova permutacija može ovisiti o ključu za šifriranje ili također može biti tajna (tj. biti dio većeg ključa za šifriranje od izvornog 256-bitnog ključa). Obje ove opcije, prema njihovim autorima, značajno povećavaju otpornost algoritma na linearnu i diferencijalnu kriptoanalizu.
I još jedna modifikacija vezana za supstitucijske tablice je dana u radu, u kojoj je jedan od moguće metode izračun zamjenskih tablica na temelju ključa za šifriranje. Autori rada zaključili su da takva ovisnost slabi algoritam, budući da dovodi do prisutnosti slabih ključeva i do nekih potencijalnih ranjivosti algoritma.
Kompletna analiza algoritma
Također postoje napadi na cijeli GOST 28147-89 bez ikakvih izmjena. Jedan od prvih otvoreni radovi, u kojem je provedena analiza algoritma, poznato djelo, posvećeno je napadima koji iskorištavaju slabosti postupka proširenja ključa niza poznatih algoritama šifriranja. Konkretno, cjeloviti algoritam GOST 28147-89 može se razbiti pomoću diferencijalne kriptoanalize na povezanim ključevima, ali samo ako se koriste slabe zamjenske tablice. Verzija algoritma s 24 runde (u kojoj nedostaje prvih 8 rundi) otvara se na sličan način sa svim zamjenskim tablicama, ali jake zamjenske tablice (na primjer, ona dana) čine takav napad potpuno nepraktičnim.
Domaći znanstvenici A.G. Rostovtsev i E.B. Makhovenko 2001. godine u svom su radu predložili da nova metoda kriptoanaliza (prema autorima znatno učinkovitija od linearne i diferencijalne kriptoanalize) formiranjem objektivne funkcije iz poznatog otvorenog teksta, odgovarajućeg šifranta i željene vrijednosti ključa te pronalaženjem njezinog ekstrema koji odgovara pravoj vrijednosti ključa. Također su pronašli veliku klasu slabih ključeva algoritma GOST 28147-89, koji omogućuju otvaranje algoritma korištenjem samo 4 odabrana otvorena teksta i odgovarajućih šifriranih tekstova s prilično niskom složenošću. Kriptoanaliza algoritma se nastavlja u radu.
Godine 2004. skupina stručnjaka iz Koreje predložila je napad koji pomoću diferencijalne kriptoanalize na povezanim ključevima može dobiti 12 bitova tajnog ključa s vjerojatnošću od 91,7%. Napad zahtijeva 2 35 odabranih otvorenih tekstova i 2 36 operacija šifriranja. Kao što vidite, ovaj napad je praktički beskoristan za razbijanje algoritma.
). Istodobno, u ruskim medijima i blogovima ruskih korisnika raste broj bilješki o ovom algoritmu: oba pokrivaju rezultate napada na ruski standard s različitim stupnjevima pouzdanosti i sadrže mišljenja o njegovim operativnim karakteristikama. Autori (a time i čitatelji) ovih bilješki često stječu dojam da je domaći algoritam šifriranja zastario, spor i ima ranjivosti koje ga čine znatno podložnijim napadima od stranih algoritama šifriranja slične duljine ključa. Ovom serijom bilješki željeli bismo pristupačan oblik govoriti o trenutnom stanju stvari s ruskim standardom. Prvi dio će pokriti sve napade na GOST 28147-89 poznate međunarodnoj kriptografskoj zajednici i trenutne procjene njegove snage. U budućim publikacijama također ćemo pobliže pogledati svojstva standarda sa stajališta sposobnosti izgradnje učinkovitih implementacija.
Nicolas Courtois - "veliki i strašni"
Počnimo s pričom o aktivnostima Nicolasa Courtoisa, koji je autor čitavog niza radova posvećenih ruskom standardu šifriranja blokova ().
U listopadu 2010. započeo je proces razmatranja uključivanja algoritma GOST 28147-89 u međunarodnu normu ISO/IEC 18033-3. Već u svibnju 2011. na elektroničkom arhivu ePrint pojavio se članak poznatog kriptografa Nicolasa Courtoisa, obilježen vrlo dvosmislenim stavom svjetske kriptografske zajednice prema njemu. Courtoisove publikacije tužan su primjer manipulacije pojmovima, koja ne otkriva nikakva nova svojstva predmetnog predmeta, već s pretenzijom na senzaciju izaziva širenje pogrešnih mišljenja o njegovim stvarnim svojstvima u nekompetentnoj sredini.
Algebarska metoda
Courtoisovo razmišljanje izgrađeno je oko dvije klase metoda kriptoanalize: algebarskih metoda i diferencijalnih metoda. Pogledajmo prvu klasu metoda.
Pojednostavljeno, metoda algebarske kriptoanalize može se opisati kao sastavljanje i rješavanje velikog sustava jednadžbi, od kojih svako rješenje odgovara cilju kriptoanalitičara (na primjer, ako je sustav sastavljen pomoću jednog para otvorenog teksta i šifriranog teksta, tada sva rješenja ovog sustava odgovaraju ključevima na kojima se ovaj otvoreni tekst pretvara u ovaj kriptiran). Odnosno, u slučaju problema kriptoanalize blokovne šifre, bit algebarske metode kriptoanalize je da se ključ nalazi kao rezultat rješavanja sustava polinomskih jednadžbi. Glavna poteškoća je sastaviti što je više moguće, uzimajući u obzir karakteristike određene šifre. jednostavan sustav tako da proces rješavanja traje što kraće. Ovdje ključnu ulogu igraju značajke svake specifične šifre koja se analizira.
Algebarska metoda koju je koristio Courtois može se ukratko opisati na sljedeći način. U prvoj fazi koriste se takva svojstva GOST 28147-89 kao postojanje fiksne točke za dio transformacije šifriranja, kao i takozvana točka refleksije. Zahvaljujući ovim svojstvima, odabire se nekoliko parova iz dovoljno velikog broja parova otvoreni tekst-šifrirani tekst, što omogućuje razmatranje transformacija ne na 32, već samo na 8 rundi. Druga faza je da se na temelju rezultata 8 kružnih transformacija dobivenih u prvoj fazi konstruira sustav nelinearnih jednadžbi u kojem su ključni bitovi nepoznanice. Zatim se ovaj sustav rješava (ovo zvuči jednostavno, ali u stvarnosti je dio metode koji oduzima najviše vremena, jer se sustav sastoji od nelinearnih jednadžbi).
Kao što je već navedeno, nigdje u radu nema detaljnog opisa i analize složenosti druge i glavne faze određivanja ključa. Složenost druge faze određuje složenost cijele metode u cjelini. Umjesto toga, autor iznosi notorne “činjenice” na temelju kojih donosi procjene intenziteta rada. Kaže se da se te "činjenice" temelje na eksperimentalnim rezultatima. Analiza “činjenica” iz Courtoisova djela u cjelini data je u radovima domaćih autora. Autori ovog rada napominju da su mnoge Courtoisove "činjenice" predstavljene bez ikakvih dokaza tijekom eksperimentalnog testiranja pokazale lažnima. Autori članka otišli su dalje i, slijedeći Courtoisa, proveli analizu složenosti druge etape koristeći dobro utemeljene algoritme i procjene. Dobivene procjene složenosti pokazuju potpunu neprimjenjivost prikazanog napada. Osim domaćih autora, veliki problemi koje Courtois ima s procjenama i opravdanjem svojih metoda također su uočeni, primjerice, u radu.
Diferencijalna metoda
Razmotrimo drugu Courtoisovu metodu, koja se temelji na diferencijalnoj kriptoanalizi.
Opća metoda diferencijalne kriptoanalize temelji se na iskorištavanju svojstava nelinearnih preslikavanja korištenih u kriptografskim primitivima, povezanih s utjecajem vrijednosti ključa na ovisnosti između razlika između parova ulaznih i parova izlaznih vrijednosti tih preslikavanja. . Opišimo glavnu ideju diferencijalne metode kriptografske analize blok šifre. Tipično, blokovne šifre transformiraju ulazne podatke u fazama koristeći brojne takozvane okrugle transformacije, a svaka kružna transformacija ne koristi cijeli ključ, već samo neki njegov dio. Razmotrimo malo "skraćenu" šifru, koja se razlikuje od originalne po tome što nema posljednju rundu. Pretpostavimo da je bilo moguće utvrditi da će šifriranje dvaju otvorenih tekstova koji se razlikuju u nekim fiksnim pozicijama pomoću takve "krnje" šifre najvjerojatnije rezultirati šifriranim tekstovima koji se također razlikuju u nekim fiksnim pozicijama. Ovo svojstvo pokazuje da "skraćena" šifra najvjerojatnije ostavlja ovisnost između nekih otvorenih tekstova i rezultata njihove enkripcije. Kako bismo vratili dio ključa korištenjem ove očite mane, potrebno je moći šifrirati unaprijed odabrane otvorene tekstove na ključu koji želimo vratiti (tzv. "napad odabranim otvorenim tekstom"). Na početku postupka "otvaranja ključem", nasumično se generira niz parova otvorenih tekstova, koji se razlikuju po tim istim fiksnim pozicijama. Svi tekstovi su šifrirani korištenjem "pune" šifre. Rezultirajući parovi šifriranih tekstova koriste se za obnavljanje onih ključnih bitova koji su korišteni u posljednjoj rundi transformacije, kako slijedi. Korištenjem neke nasumično odabrane vrijednosti željenih bitova ključa, transformacija inverzna transformaciji posljednje runde primjenjuje se na sve šifrirane tekstove. Zapravo, ako smo pogodili željenu vrijednost bitova ključa, dobit ćemo rezultat "krnje" šifre, a ako nismo pogodili, zapravo ćemo "još više šifrirati podatke", što će samo smanjiti gore navedena ovisnost između blokova (razlika je u nekim fiksnim pozicijama). Drugim riječima, ako je među rezultatima takve "dodatne obrade" šifriranih tekstova bilo dosta parova koji se razlikuju u fiksnim pozicijama koje su nam poznate, to znači da smo pogodili potrebne bitove ključa. Inače će takvih parova biti znatno manje. Budući da se samo dio ključa koristi u svakoj rundi, nema toliko traženih bitova (tj. ključnih bitova korištenih u zadnjoj rundi) koliko ima bitova u u punom ključu a možete ih jednostavno sortirati ponavljanjem gornjih koraka. U ovom slučaju, sigurno ćemo jednog dana naići na ispravno značenje.
Iz gornjeg opisa proizlazi da je najvažnija stvar u metodi diferencijalne analize upravo broj onih pozicija u otvorenim tekstovima i šifriranim tekstovima, čije razlike igraju ključnu ulogu u vraćanju ključnih bitova. Temeljna prisutnost ovih pozicija, kao i skup njihovih brojeva, izravno ovisi o svojstvima onih nelinearnih transformacija koje se koriste u bilo kojoj blok šifri (obično je sva "nelinearnost" koncentrirana u tzv. S-kutijama ili zamjenski čvorovi).
Courtois koristi malo modificiranu verziju diferencijalne metode. Odmah napomenimo da Courtois svoju analizu provodi za S-kutije koje se razlikuju od sadašnjih i onih koje predlaže ISO. Rad daje diferencijalne karakteristike (one brojeve u kojima bi se blokovi trebali razlikovati) za mali broj krugova. Opravdanje za proširenje karakteristika za više krugova se, kao i obično, temelji na "činjenicama". Courtois izražava, opet, ničim osim svojim autoritetom, nepotkrijepljenu pretpostavku da promjena S-kutija neće utjecati na otpornost GOST 28147-89 na njegov napad (dok su iz nepoznatih razloga S-kutije iz 1. radnog nacrta dodatak standardu ISO/IEC 18033-3 nije razmatran). Analiza koju su proveli autori članka pokazuje da čak i ako uzmemo na vjeru Courtoisove neutemeljene "činjenice" i analiziramo GOST 28147-89 s drugim S-blokovima, opet se ispostavlja da napad nije ništa bolji od potpune pretrage.
Detaljna analiza Courtoisovih radova s detaljnim obrazloženjem neutemeljenosti svih izjava o smanjenju otpornosti ruskog standarda provedena je u radovima [,].
U isto vrijeme, čak i sam Courtois priznaje apsolutni nedostatak točnosti u izračunima! Sljedeći slajd preuzet je iz Courtoisove prezentacije na FSE 2012 odjeljak kratkih obavijesti.
Valja napomenuti da je Courtoisov rad također više puta kritiziran od stranih istraživača. Na primjer, njegov rad na konstruiranju napada na algoritam blokovske enkripcije AES koristeći XSL metodu sadržavao je iste temeljne nedostatke kao i rad na analizi ruskog standarda: većina procjena intenziteta rada pojavljuje se u tekstu potpuno neutemeljeno i nepotkrijepljeno - detaljno kritika se može naći npr. u radu. Osim toga, sam Courtois priznaje široko rasprostranjeno odbijanje objave svog rada na velikim konferencijama o kriptografiji iu etabliranim recenziranim časopisima, često ostavljajući mu samo priliku da govori u odjeljku s kratkim najavama. Na primjer, o tome možete pročitati u 3. odjeljku djela. Evo nekoliko citata samog Courtoisa koji se odnose na njegov rad:
- “Mislim da publika Asiacrypta neće osjetiti da je zanimljiv.” Recenzent Asiacrypt 2011.
- “… postoji veliki, veliki, veliki problem: ovaj napad, koji je glavni doprinos rada, već je objavljen na FSE’11 (bio je čak i najbolji rad), …”. Recenzent za Crypto 2011.
Dakle, profesionalni dio međunarodne kriptografske zajednice gleda na kvalitetu Courtoisovog rada s ništa manje sumnje nego, recimo, izjave nekih ruskih stručnjaka o njihovoj sposobnosti da provale AES za 2100, što nije potvrđeno nikakvim dosljednim izračunima, ili najnoviji “dokaz” hipoteze na dvije stranice o nejednakosti klasa složenosti P i NP.
Napadi Isobe i Dinur-Dankelman-Shamira
Opća ideja Isobe () i Dinur-Dankelman-Shamir napada (u daljnjem tekstu: DDS napad) () je konstruirati za određeni (ovisni o ključu) uski skup otvorenih tekstova ekvivalentne transformacije na ovom skupu, koji ima struktura jednostavnija od same transformacije šifriranja. U slučaju Isobe metode, ovo je skup 64-bitnih blokova x tako da je F 8 -1 (Swap(F 8 (z))) = z, gdje je z = F 16 (x), do F 8 ( x) i F 16 ( x) označavaju prvih 8 i prvih 16 rundi enkripcije GOST 28147-89, redom, kroz Swap - operaciju zamjene polovica riječi od 64 bajta. Ako je otvoreni tekst uključen u ovaj skup, rezultat pune 32-kružne transformacije GOST 28147-89 podudara se s rezultatom 16-kružne, što je ono što autor napada iskorištava. U slučaju DDS metode, to je skup x takav da je F 8 (x) = x (fiksna točka transformacije F 8). Za bilo koji otvoreni tekst iz ovog skupa, transformacija GOST 28147-89 radi potpuno isto kao i zadnjih 8 krugova, što pojednostavljuje analizu.
Složenost Isobe napada je 2.224 operacije šifriranja, DDS napada je 2.192. Međutim, sva pitanja o tome uvode li Isobe i DDS napadi nova ograničenja na uvjete korištenja našeg algoritma uklanjaju se procjenom zahtjeva za količinom materijala potrebnog za izvođenje svakog od napada: Isobe metoda zahtijeva 2 32 para otvorenog teksta i šifrirani tekst, a za DDS metodu - 2 64. Obrada takvih volumena materijala bez promjene ključa a priori je neprihvatljiva za bilo koju blokovnu šifru s duljinom bloka od 64: na materijalu volumena 2 32 , uzimajući u obzir problem rođendana (vidi, na primjer, ), vjerojatnost pojavljivanja ponovljenih blokova je blizu 1/2, što će omogućiti napadaču da može izvući određene zaključke o otvorenim tekstovima iz šifriranih tekstova bez određivanja ključa. Prisutnost 2 64 para čistih i šifriranih tekstova dobivenih na jednom ključu zapravo omogućuje neprijatelju izvođenje operacija šifriranja i dešifriranja bez da uopće zna ovaj ključ. To je zbog čisto kombinatornog svojstva: neprijatelj u ovom slučaju ima cijelu tablicu pretvorbe šifriranja. Ova situacija je apsolutno neprihvatljiva pod bilo kojim razumnim radnim uvjetima. Na primjer, u CryptoPro CSP Postoji tehničko ograničenje količine šifriranog materijala (bez konverzije ključa) od 4 MB (vidi). Stoga je stroga zabrana korištenja ključa na materijalu takvog volumena svojstvena bilo kojoj blok šifri s duljinom bloka od 64 bita, pa prema tome Isobe i DDS napadi ni na koji način ne sužavaju opseg upotrebe GOST 28147-89 algoritma uz zadržavanje najveće moguće snage od 2.256.
Naravno, treba napomenuti da su istraživači (Isobe i Dinur-Dankelman-Shamir) pokazali da neka svojstva algoritma GOST 28147-89 omogućuju pronalaženje putova analize koje tvorci algoritma nisu uzeli u obzir. Jednostavan oblik rasporeda ključeva, koji značajno pojednostavljuje zadatak konstruiranja učinkovitih implementacija, također dopušta nekim rijetkim slučajevima ključeva i otvorenih tekstova da konstruiraju više jednostavni opisi transformacije koje izvodi algoritam.
Rad pokazuje da se ovo negativno svojstvo algoritma može lako eliminirati uz potpuno očuvanje operativnih karakteristika, ali je, nažalost, sastavni dio algoritma u uobičajenom obliku.
Napominjemo da je određena nebriga u procjenama prosječnog intenziteta rada prisutna iu radu Dinura, Dunkelmana i Shamira. Dakle, kada se konstruira napad, ne obraća se dužna pažnja na sljedeću točku: za značajan udio ključeva, skup otvorenih tekstova x, takav da je F 8 (x) = x, je prazan: možda jednostavno nema fiksnih točaka za 8 krugova transformacije. Postojanje fiksnih točaka također ovisi o izboru zamjenskih čvorova. Stoga je napad primjenjiv samo za određene zamjenske čvorove i ključeve.
Također je vrijedno spomenuti još jedan rad s napadom na GOST 28147-89. U veljači 2012. pojavio se elektronički arhiv ePrint međunarodne kriptografske udruge ažurirana verzijačlanak (iz studenog 2011.), koji je sadržavao novi napad na GOST 28147-89. Karakteristike prikazanog napada su sljedeće: volumen materijala je 2 32 (kao Isobe), a intenzitet rada 2 192 (kao DDS). Stoga je ovaj napad poboljšao DDS napad s vremenskim zapisom u smislu količine materijala s 2 64 na 2 32. Posebno napominjemo da su autori pošteno prikazali sve izračune s obrazloženjem složenosti i volumena materijala. Nakon 9 mjeseci pronađena je temeljna pogreška u gornjim izračunima, a od studenog 2012. ažurirana verzija članka u elektroničkoj arhivi više ne sadrži nikakve rezultate u vezi s domaćim algoritmom.
Napadi pod pretpostavkom da napadač zna "nešto" o ključevima
Na kraju, napominjemo da u literaturi također postoji niz radova (vidi, na primjer, i ) posvećenih napadima na GOST 28147-89 u takozvanom modelu povezanog ključa. Ovaj model u osnovi sadrži pretpostavku da napadač može dobiti pristup za analizu ne samo parovima otvorenog teksta i šifriranog pomoću željenog ključa, već i parovima otvorenog teksta i šifriranog teksta dobivenog korištenjem (također nepoznatih) ključeva koji se razlikuju od traženog u poznatom regularnom ključu. način (na primjer, na fiksnim položajima bitova). U ovom modelu stvarno je moguće dobiti zanimljive rezultate o GOST 28147-89, međutim, u ovom modelu ne mogu se dobiti ništa manje jaki rezultati o, na primjer, koji se najčešće koristi u modernim mrežama uobičajena uporaba AES standard (vidi, na primjer,). Imajte na umu da uvjeti za izvođenje ove vrste napada nastaju korištenjem šifre u određenom protokolu. Treba napomenuti da rezultati ove vrste, iako su od nedvojbenog akademskog interesa sa stajališta proučavanja svojstava kriptografskih transformacija, zapravo nisu relevantni za praksu. Na primjer, svi alati za kriptografsku zaštitu informacija certificirani od strane FSB-a Rusije ispunjavaju najstrože zahtjeve za sheme generiranja ključeva šifriranja (vidi, na primjer,). Kao što je navedeno u rezultatima analize, ako postoji 18 pridruženih ključeva i 2 10 parova otvorenog teksta i blokova šifriranog teksta, složenost potpunog otvaranja privatnog ključa, s vjerojatnošću uspjeha od 1-10 -4, zapravo je 2 26 . Međutim, ako su ispunjeni gore navedeni zahtjevi za razvoj materijala ključeva, vjerojatnost pronalaska takvih ključeva je 2 -4352, odnosno 24096 puta manja nego ako jednostavno pokušate pogoditi tajni ključ iz prvog pokušaja.
Radovi vezani uz model s povezanim tipkama također uključuju rad koji je 2010. godine izazvao mnogo buke u ruskim elektroničkim publikacijama, koje ne pate od navike pažljivog provjeravanja materijala u utrci za senzacijama. Rezultati predstavljeni u njemu nisu bili potkrijepljeni nikakvim rigoroznim obrazloženjem, ali su sadržavali glasne izjave o mogućnosti hakiranja državnog standarda Ruska Federacija na slabom prijenosnom računalu za nekoliko sekundi - općenito, članak je napisan u najboljim tradicijama Nicolasa Courtoisa. No, usprkos apsolutno očitoj neutemeljenosti članka čitatelju koji je koliko-toliko upoznat s osnovnim principima znanstvenih publikacija, Rudski je upravo da bi umirio rusku javnost nakon rada napisao detaljan i temeljit tekst koji je sadržavao opsežnu analizu ovog nedostatka. Članak samoobjašnjavajućeg naslova “O nultom praktičnom značaju rada “Key recovery attack on full GOST block cipher with zero time and memory”” daje opravdanje da prosječna složenost metode koja je dana u nije ništa manja od složenosti potpune pretrage.
Suhi ostatak: što je trajnost u praksi?
Zaključno, predstavljamo tablicu koja sadrži podatke o svim rezultatima strogo opisanih i opravdanih napada na GOST 28147-89 poznatih međunarodnoj kriptografskoj zajednici. Imajte na umu da je složenost navedena u operacijama šifriranja algoritma GOST 28147-89, a memorija i materijal navedeni su u blokovima algoritma (64 bita = 8 bajtova).
| Napad | Intenzitet rada | Memorija | Potreban materijal |
| Isobe | 2 224 | 2 64 | 2 32 |
| Dinur-Dankelman-Shamir, FP, 2DMitM | 2 192 | 2 36 | 2 64 |
| Dinur-Dankelman-Shamir, FP, slabo pamćenje | 2 204 | 2 19 | 2 64 |
| 2 224 | 2 36 | 2 32 | |
| Dinur-Dankelman-Shamir, Odraz, 2DMitM | 2 236 | 2 19 | 2 32 |
| Dovršite pretragu | 2 256 | 1 | 4 |
| Broj nanosekundi od nastanka svemira | 2 89 |
Unatoč prilično velikom ciklusu istraživanja u području stabilnosti algoritma GOST 28147-89, ovaj trenutak Ne postoji niti jedan poznat napad koji bi bio izvediv prema operativnim zahtjevima 64-bitne duljine bloka. Ograničenja količine materijala koji se može obraditi na jednom ključu koja proizlaze iz parametara šifre (duljina bita ključa, duljina bita bloka) znatno su stroža od minimalne količine potrebne za izvođenje bilo kojeg trenutno poznatog napada. Posljedično, pri ispunjavanju postojećih operativnih zahtjeva, niti jedna od metoda kriptoanalize predloženih do danas GOST 28147-89 ne dopušta određivanje ključa s intenzitetom rada manjim od iscrpnog pretraživanja.
