Algoritem GOST 28147 89 je. Domači standard šifriranja podatkov. Variacije na temo gosta
Za razliko od ameriškega DES domači standard uporablja daljši ključ - 256 bitov. Poleg tega ruski standard predlaga uporabo 32 krogov šifriranja, medtem ko DES zahteva le 16.
Tako so glavni parametri algoritma za kriptografsko pretvorbo podatkov GOST 28147-89 naslednji: velikost bloka je 64 bitov, velikost ključa je 256 bitov, število krogov je 32.
Algoritem je klasično Feishtelovo omrežje. Šifrirani podatkovni blok je razdeljen na dva enaka dela, desni R in levi L. Desni del je dodan okroglemu podključu in z nekim algoritmom šifrira levi del. Pred naslednjim krogom se levi in desni del zamenjata. Ta struktura omogoča uporabo istega algoritma za šifriranje in dešifriranje bloka.
Algoritem šifriranja uporablja naslednje operacije:
- seštevanje besed po modulu 2 32;
- ciklično premakne besedo v levo za določeno število bitov;
- bitni seštevek modulo 2;
- zamenjava po tabeli.
V različnih korakih algoritmov GOST se podatki, s katerimi delujejo, razlagajo in uporabljajo na različne načine. V nekaterih primerih se podatkovni elementi obravnavajo kot polja neodvisnih bitov, v drugih primerih kot celo število brez predznaka, v tretjih pa kot elementi s strukturo kompleksen element, sestavljen iz več enostavnejših elementov.
Okrogla struktura GOST 28147-89
Struktura enega kroga GOST 28147-89 je prikazana na sl. 5.1.
Šifrirani podatkovni blok je razdeljen na dva dela, ki se nato obdelata kot ločena 32-bitna nepredznačena cela števila. Najprej se doda desna polovica bloka in podključ kroga po modulu 2 32. Nato se izvede zamenjava po blokih. 32-bitna vrednost, pridobljena v prejšnjem koraku (imenujmo jo S), se interpretira kot niz osmih 4-bitnih kodnih blokov: S=(S 0, S 1, S 2, S 3, S 4, S 5, S 6, S 7). Nato se vrednost vsakega od osmih blokov zamenja z novo, ki se izbere iz tabele zamenjav na naslednji način: vrednost bloka S i se nadomesti s S i -tim elementom po vrstnem redu (številčenje od nič) i-tega nadomestnega vozlišča (tj. nadomestne tabele i-te vrstice, oštevilčenje tudi od začetka). Z drugimi besedami, element s številko vrstice, ki je enaka številki bloka, ki se zamenja, in številko stolpca, ki je enaka vrednosti bloka, ki se zamenja kot 4-bitno nenegativno celo število, je izbran kot zamenjava za vrednost blok. Vsaka vrstica nadomestne tabele vsebuje številke od 0 do 15 v naključnem vrstnem redu brez ponavljanja. Vrednosti elementov nadomestne tabele so vzete od 0 do 15, saj lahko štirje biti, ki so nadomeščeni, vsebujejo nepredznačeno celo število v območju od 0 do 15. Na primer, prva vrstica polja S lahko vsebuje naslednje vrednosti: 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11 . V tem primeru bo vrednost bloka S 0 (štirje najmanj pomembni biti 32-bitnega števila S) zamenjana s številko na mestu, katere številka je enaka vrednosti bloka, ki ga zamenjamo. Če je S 0 = 0, bo nadomeščen s 5, če je S 0 = 1, bo nadomeščen z 8 itd.
riž. 5.1.
Po opravljeni zamenjavi se vsi 4-bitni bloki znova združijo v eno 32-bitno besedo, ki se nato zasuka za 11 bitov v levo. Končno z uporabo bitne operacije "vsota modulo 2" rezultat se združi z levo polovico, kar povzroči novo desno polovico R i . Nova leva stran L i je enaka spodnjemu delu pretvorjenega bloka: L i = R i-1 .
Končna vrednost pretvorjenega bloka se šteje kot rezultat enega kroga šifrirnega algoritma.
Postopki šifriranja in dešifriranja
GOST 28147-89 je torej blok šifra pretvorbo podatkov izvajajo v blokih v ti osnovni cikli. Osnovne zanke so sestavljene iz ponavljajočega se izvajanja glavnega kroga, o katerem smo prej govorili za podatkovni blok, z uporabo različnih ključnih elementov in se med seboj razlikujejo po vrstnem redu, v katerem so uporabljeni ključni elementi. Vsak krog uporablja enega od osmih možnih 32-bitnih podključev.
Oglejmo si postopek ustvarjanja okroglih podključev. V GOST je ta postopek zelo preprost, zlasti v primerjavi z DES. 256-bitni ključ K je razdeljen na osem 32-bitnih podključev, označenih s K0, K1, K2, K3, K4, K5, K6, K7. Algoritem vključuje 32 krogov, tako da je vsak podključ med šifriranjem uporabljen v štirih krogih v zaporedju, predstavljenem v tabeli 5.1.
| Okrogla | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Polna izgradnja | K 0 | K 1 | K2 | K 3 | K 4 | K5 | K 6 | K 7 |
| Okrogla | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| Polna izgradnja | K 0 | K 1 | K2 | K 3 | K 4 | K5 | K 6 | K 7 |
| Okrogla | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| Polna izgradnja | K 0 | K 1 | K2 | K 3 | K 4 | K5 | K 6 | K 7 |
| Okrogla | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
| Polna izgradnja | K 7 | K 6 | K5 | K 4 | K 3 | K2 | K 1 | K 0 |
Postopek dešifriranja poteka po enakem algoritmu kot šifriranje. Edina razlika je vrstni red uporabe podključev K i. Pri dešifriranju je treba podključe uporabiti v obratnem vrstnem redu, in sicer kot je navedeno v
Ta algoritem je obvezen za uporabo kot algoritem šifriranja v vladnih organizacijah Ruske federacije in številnih komercialnih.
Opis algoritma
Diagram algoritma je prikazan na sl. 3.1. Kot lahko vidite, je zasnova tega algoritma precej preprosta, kar jasno poenostavi njegovo programsko ali strojno izvedbo.
Algoritem GOST 28147-89 šifrira informacije v blokih po 64 bitov, ki so razdeljeni na dva podbloka po 32 bitov (N1 in N2). Podblok N1 se obdela na določen način, nakar se njegova vrednost sešteje
z vrednostjo podbloka N2 (seštevanje se izvede po modulu 2), nato se podbloka zamenjata. Ta transformacija se izvede v določenem številu krogov: 16 ali 32, odvisno od načina delovanja algoritma (opisano spodaj). V vsakem krogu se izvajajo naslednje operacije:
1. Ključna aplikacija. Vsebina podbloka /VI je dodana modulo 2 32 z delom ključa Kx.
Šifrirni ključ algoritma GOST 28147-89 ima dimenzijo 256 bitov, Kx pa je njegov 32-bitni del, tj. 256-bitni šifrirni ključ je predstavljen kot veriženje 32-bitnih podključev (slika 3.2):
Šč ATI, AG2, Yu, AG4, K5, Kb, K7.
Med procesom šifriranja se uporabi eden od teh podključev, odvisno od okrogle številke in načina delovanja algoritma.
riž. 3.1. Diagram algoritma GOST 28147-
riž. 3.2. Šifrirni ključ algoritma GOST 28147-89
2. Zamenjava mize. Po vnosu ključa se podblok /VI razdeli na 8 delov po 4 bite, od katerih se vrednost vsakega posebej zamenja v skladu z nadomestno tabelo za ta del podbloka. Zamenjave tabel (Substitution box, S-box) se pogosto uporabljajo v sodobnih šifrirnih algoritmih, zato jih je vredno razmisliti podrobneje.
Zamenjava tabele se uporablja na ta način: na vhod je dobavljen blok podatkov določene velikosti (v tem primeru 4-bitni), katerega numerična predstavitev določa številko izhodne vrednosti. Na primer, imamo S-box naslednje oblike:
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.
Naj na vhod pride 4-bitni blok “0100”, to je vrednost 4. Po tabeli bo izhodna vrednost enaka 15, tj. “1111” (0 se nadomesti s 4, 1 z 11, vrednost 2 ostane nespremenjena itd.).
Kot lahko vidite, je zasnova algoritma zelo enostavna, kar pomeni, da največje breme šifriranja podatkov pade na nadomestne tabele. Na žalost ima algoritem to lastnost, da obstajajo "šibke" nadomestne tabele, s pomočjo katerih lahko algoritem rešimo s kriptoanalitičnimi metodami. Šibke vključujejo na primer tabelo, v kateri je izhod enak vhodu:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
3. Bitni ciklični premik v levo za 11 bitov.
Načini delovanja algoritma
Algoritem GOST 28147-89 ima 4 načine delovanja:
□ preprost način zamenjave;
□ način gama;
P način gama z povratne informacije;
□ način razvoja posnemalnih navezanosti.
Ti načini se nekoliko razlikujejo od splošno sprejetih (opisanih v razdelku 1.4), zato jih je vredno razmisliti podrobneje.
Ti načini imajo različne namene, vendar uporabite isto šifrirno transformacijo, opisano zgoraj.
Enostaven način zamenjave
V preprostem nadomestnem načinu je vsak 64-bitni blok informacij preprosto šifriran z uporabo 32 krogov, opisanih zgoraj. 32-bitni podključi se uporabljajo v naslednjem zaporedju:
□ KO, Kl, K2, KZ, K4, K5, KB, AG7, KO, ATI itd. - v krogih od 1 do 24;
□ K1, Kb, K5, K4, KZ, K2, K\, KO - v krogih od 25 do 32.
Dešifriranje v načinu enostavne zamenjave se izvede na popolnoma enak način, vendar z nekoliko drugačnim zaporedjem uporabe podključev:
□ KO, K\, K2, KZ, K4, K5, Kb, KP - v 1. do 8. krogu;
□ KP, Kb, K5, K4, KZ, K2, K\, KO, K1, Kb itd. - v krogih od 9 do 32.
Podobno kot pri standardnem načinu ECB, zaradi ločenega šifriranja blokov, način preproste zamenjave strogo ni priporočljiv za šifriranje samih podatkov; uporabljajte ga samo za šifriranje drugih šifrirnih ključev v shemah z več ključi.
Način gama
V načinu gama (slika 3.3) se vsak blok odprtega besedila dodaja bit za bitom po modulu 2 64-bitnemu šifriranemu bloku gama. Šifra gama je posebno zaporedje, ki se ustvari z uporabo zgoraj opisanih transformacij, kot sledi:
1. Njihovo začetno polnjenje je zapisano v registra N1 in N2 - 64-bitna vrednost, imenovana "sinhronizacijsko sporočilo" (sinhronizacijsko sporočilo je praktično analog inicializacijskega vektorja v načinih CBC, CFB in OFB).
2. Vsebina registrov /VI in N2 je šifrirana (v v tem primeru- sinhronizacija sporočil) v preprostem načinu zamenjave.
3. Vsebina N1 se sešteje modulo (2 32 – 1) s konstanto CI = 2 24 + 2 16 + 2 8 + 4, rezultat seštevanja se zapiše v register /VI.
4. Vsebina N2 se sešteje po modulu 2 s konstanto C2 = 2 24 + 2 16 + 2 8 +1, rezultat seštevanja se zapiše v register N2.
5. Vsebina registrov /VI in N2 se izpiše kot 64-bitni šifrirani blok gama (tj. v tem primeru /VI in N2 tvorita prvi blok gama).
6. Če je potreben naslednji blok gama (tj. potrebno je dodatno šifriranje ali dešifriranje), se vrnite na 2. korak.
Za dešifriranje se gama generira na podoben način, nato pa se šifrirano besedilo in gama biti ponovno povežejo z XOR.
Za ustvarjanje istega obsega šifre mora imeti uporabnik, ki dešifrira kriptogram, isti ključ in isto vrednost sinhronizacijskega sporočila, ki sta bila uporabljena pri šifriranju informacij. V nasprotnem primeru ne bo mogoče pridobiti izvirnega besedila iz šifriranega.
V večini izvedb algoritma GOST 28147-89 sinhronizacijsko sporočilo ni skrivni element, vendar je sinhronizacijsko sporočilo lahko tako skrivno kot šifrirni ključ. V tem primeru lahko upoštevamo, da se efektivna dolžina ključa algoritma (256 bitov) poveča za dodatnih 64 bitov sinhronizacijskega sporočila, kar lahko štejemo kot dodaten ključni element.
Način gama s povratnimi informacijami
V načinu gama s povratnimi informacijami se rezultat šifriranja prejšnjega bloka odprtega besedila uporabi za zapolnitev registrov /VI in L/2, začenši od 2. bloka, ne prejšnjega bloka gama, ampak rezultat šifriranja prejšnjega bloka odprtega besedila (slika 3.4). Prvi blok v ta način se ustvari popolnoma podobno kot prejšnji.
riž. 3.4. Generiranje šifre gama v načinu gama s povratno informacijo
Način ustvarjanja imitacije priloge
Predpona je kriptografska kontrolna vsota, izračunana z uporabo šifrirnega ključa in zasnovana za preverjanje celovitosti sporočil. Za izračun obstaja poseben način algoritma GOST 28147-89.
Ustvarjanje imitacijske predpone se izvede na naslednji način:
1. Prvi 64-bitni blok informacij, za katerega se izračuna predpona imitacije, se zapiše v registra N1 in N2 in šifrira v reduciranem preprostem načinu zamenjave, v katerem se izvede prvih 16 krogov od 32.
2. Dobljeni rezultat se sešteje po modulu 2 z naslednjim blokom informacij, rezultat pa se shrani v N1 in N2.
3. M in N2 se znova šifrirata v načinu skrajšane preproste zamenjave itd. do zadnjega bloka informacij.
Za imitacijsko predpono se šteje 64-bitna nastala vsebina registrov N1 in N2 ali njunega dela. Najpogosteje se uporablja 32-bitna imitativna predpona, to je polovica vsebine registrov. To je dovolj, saj je, tako kot vsaka kontrolna vsota, imitacija priloge namenjena predvsem zaščiti pred nenamernim izkrivljanjem informacij. Za zaščito pred namernim spreminjanjem podatkov se uporabljajo druge kriptografske metode – predvsem elektronske digitalni podpis(glejte poglavje 1.1).
Predpona imitacije se uporablja na naslednji način:
1. Pri šifriranju kakršnih koli informacij se predpona imitacije navadnega besedila izračuna in pošlje skupaj s šifriranim besedilom.
2. Po dešifriranju se predpona imitacije ponovno izračuna in primerja s poslano.
3. Če se izračunana in poslana imitacijska predpona ne ujemata, je bilo šifrirano besedilo med prenosom popačeno ali pa so bili med dešifriranjem uporabljeni nepravilni ključi.
Predpona imitacije je še posebej uporabna za preverjanje pravilnega dešifriranja ključnih informacij pri uporabi shem z več ključi.
Predpona imitacije je nekaj analogne kode za preverjanje pristnosti sporočila MAC, izračunane v načinu CBC; Razlika je v tem, da se pri izračunu imitacijske predpone ne uporablja sinhronizacijsko sporočilo, medtem ko se pri izračunu MAC uporablja inicializacijski vektor.
Kriptografska moč algoritma
Leta 1994 je bil opis algoritma GOST 28147-89 preveden v angleščino in objavljen; po tem so se začeli pojavljati rezultati njegove analize, ki so jo opravili tuji strokovnjaki; vendar pa dalj časa niso našli nobenih napadov, ki bi se približali izvedljivosti.
□ velika dolžina ključa - 256 bitov; skupaj s tajnim sinhronizacijskim sporočilom se efektivna dolžina ključa poveča na 320 bitov;
□ 32 krogov transformacij; že po 8 krogih je dosežen polni učinek razpršenosti vhodnih podatkov: sprememba enega bita bloka golega besedila bo vplivala na vse bite bloka šifriranega besedila in obratno, kar pomeni, da obstaja večkratna rezerva trdnosti.
Razmislimo o rezultatih kriptoanalize algoritma GOST 28147-89.
Analiza nadomestnih tabel
Ker nadomestne tabele niso navedene v standardu, številna dela (na primer v) kažejo, da lahko "pristojna organizacija" izda tako "dobre" kot "slabe" nadomestne tabele. Vendar slavni strokovnjak Bruce Schneier takšne domneve imenuje "govorice". Jasno je, da je kriptografska moč algoritma v veliki meri odvisna od lastnosti uporabljenih nadomestnih tabel; zato obstajajo šibke nadomestne tabele (glej primer zgoraj), katerih uporaba lahko poenostavi napad algoritma. Kljub temu se zdi možnost uporabe različnih nadomestnih tabel zelo vredna ideja, v prid kateri lahko navedemo naslednji dve dejstvi iz zgodovine šifrirnega standarda DES (za podrobnosti glej razdelek 3.15):
□ napadi z uporabo linearne in diferencialne kriptoanalize algoritma DES uporabljajo posebne lastnosti nadomestnih tabel; pri uporabi drugih tabel bo treba kriptoanalizo začeti znova;
□ narejeni so bili poskusi okrepiti DES proti linearni in diferencialni kriptoanalizi z uporabo robustnejših substitucijskih tabel; takšne tabele, ki so res robustnejše, so bile predlagane na primer v algoritmu s 5 DES; vendar, žal, ni bilo mogoče zamenjati DES s s 5 DES, saj so nadomestne tabele strogo opredeljene v standardu in v skladu s tem izvedbe algoritma verjetno ne podpirajo možnosti spreminjanja tabel v druge.
Številna dela (na primer , in ) napačno sklepajo, da so skrivne nadomestne tabele algoritma GOST 28147-89 lahko del ključa in povečajo njegovo efektivno dolžino (kar ni pomembno, saj ima algoritem zelo veliko 256 -bitni ključ). Vendar delo dokazuje, da je mogoče skrivne nadomestne tabele izračunati z naslednjim napadom, ki ga je mogoče praktično uporabiti:
1. Nastavi se ničelni ključ in izvede se iskanje »ničelnega vektorja«, to je vrednosti z = /(0), kjer je /() okrogla funkcija algoritma. Ta stopnja traja približno 2 operaciji šifriranja.
2. Z ničelnim vektorjem se izračunajo vrednosti nadomestnih tabel, ki ne trajajo več kot 2 11 operacij.
Modifikacije algoritmov in njihova analiza
Delo je izvedlo kriptoanalizo sprememb algoritma GOST 28147-89:
□ GOST-H algoritem, pri katerem je glede na originalni algoritem spremenjen vrstni red uporabe podključev, in sicer se v krogih uporablja od 25 do 32 podključev v neposrednem vrstnem redu, torej popolnoma enako kot v prejšnjih krogih algoritma;
□ 20-krožni algoritem GOST®, v katerem krog uporablja XOR namesto dodatka modulo-2 za prekrivanje ključa.
Na podlagi rezultatov analize je bilo ugotovljeno, da sta GOST-H in GOST© šibkejša od originalnega algoritma GOST 28147-89, saj imata oba razreda šibkih ključev. Treba je omeniti, da v smislu kriptoanalize GOST© delo dobesedno ponavlja razdelek, posvečen kriptoanalizi algoritma GOST 28147-89, dobro znanega dela, objavljenega leta 2000 (brez kakršnega koli sklicevanja na izvirnik). To postavlja pod vprašaj strokovnost avtorjev dela in njegove druge rezultate.
V delu je bila predlagana zelo zanimiva modifikacija algoritma: tabele S\…Ss morajo biti nujno drugačne; v vsakem krogu algoritma jih je treba preurediti po določenem zakonu. Ta permutacija je lahko odvisna od šifrirnega ključa ali pa je lahko tudi skrivna (tj. je del večjega šifrirnega ključa kot izvirni 256-bitni ključ). Obe možnosti po mnenju avtorjev znatno povečata odpornost algoritma proti linearni in diferencialni kriptoanalizi.
In še ena sprememba v zvezi z nadomestnimi tabelami je podana v delu, v katerem je ena od možne metode izračun nadomestnih tabel na podlagi šifrirnega ključa. Avtorji dela so ugotovili, da takšna odvisnost oslabi algoritem, saj vodi do prisotnosti šibkih ključev in do nekaterih potencialnih ranljivosti algoritma.
Analiza celotnega algoritma
Obstajajo tudi napadi na celoten GOST 28147-89 brez kakršnih koli sprememb. Eden izmed prvih odprta dela, v katerem je bila izvedena analiza algoritma, znano delo, je posvečeno napadom, ki izkoriščajo slabosti postopka razširitve ključa številnih znanih šifrirnih algoritmov. Zlasti celoten algoritem GOST 28147-89 je mogoče razbiti z uporabo diferencialne kriptoanalize na povezanih ključih, vendar le, če se uporabljajo šibke nadomestne tabele. 24-krožna različica algoritma (v kateri manjka prvih 8 krogov) se odpre na podoben način z vsemi nadomestnimi tabelami, vendar zaradi močnih nadomestnih tabel (na primer tista, ki je podana) je tak napad popolnoma nepraktičen.
Domača znanstvenika A. G. Rostovtsev in E. B. Makhovenko sta leta 2001 v svojem delu predlagala, da nova metoda kriptoanalizo (po mnenju avtorjev bistveno učinkovitejšo od linearne in diferencialne kriptoanalize) tako, da iz znanega odprtega besedila, ustreznega šifranta in želene vrednosti ključa oblikujemo objektivno funkcijo in poiščemo njen ekstrem, ki ustreza pravi vrednosti ključa. Našli so tudi velik razred šibkih ključev algoritma GOST 28147-89, ki omogočajo odpiranje algoritma z uporabo samo 4 izbranih odprtih besedil in ustreznih šifriranih besedil z dokaj nizko kompleksnostjo. Kriptoanaliza algoritma se nadaljuje v delu.
Leta 2004 je skupina strokovnjakov iz Koreje predlagala napad, ki lahko z uporabo diferencialne kriptoanalize na povezanih ključih pridobi 12 bitov tajnega ključa z verjetnostjo 91,7%. Napad zahteva 2 35 izbranih odprtih besedil in 2 36 operacij šifriranja. Kot lahko vidite, je ta napad praktično neuporaben za dejansko zlom algoritma.
). Hkrati v ruskih medijih in blogih ruskih uporabnikov narašča število opomb o tem algoritmu: tako z različnimi stopnjami zanesljivosti pokrivajo rezultate napadov na ruski standard kot tudi mnenja o njegovih operativnih značilnostih. Avtorji (in posledično bralci) teh zapisov pogosto dobijo vtis, da je domači šifrirni algoritem zastarel, počasen in ima ranljivosti, zaradi katerih je bistveno bolj dovzeten za napade kot tuji šifrirni algoritmi s podobno dolžino ključa. S to serijo zapiskov bi radi dostopni obliki govoriti o trenutnem stanju z ruskim standardom. Prvi del bo zajemal vse napade na GOST 28147-89, ki jih pozna mednarodna kriptografska skupnost, in trenutne ocene njegove moči. V prihodnjih objavah si bomo lastnosti standarda podrobneje ogledali tudi z vidika zmožnosti gradnje učinkovitih implementacij.
Nicolas Courtois - "veliki in strašni"
Začnimo z zgodbo o dejavnostih Nicolasa Courtoisa, ki je avtor cele vrste del, posvečenih ruskemu blokovnemu standardu šifriranja ().
Oktobra 2010 se je začel postopek razmišljanja o vključitvi algoritma GOST 28147-89 v mednarodni standard ISO/IEC 18033-3. Že maja 2011 se je v elektronskem arhivu ePrint pojavil članek slovitega kriptografa Nicolasa Courtoisa, ki ga zaznamuje zelo dvoumen odnos svetovne kriptografske skupnosti do njega. Courtoisove objave so žalosten primer manipulacije s pojmi, ki ne razkriva nobenih novih lastnosti obravnavanega predmeta, ampak s trditvijo po senzaciji spodbuja širjenje zmotnih mnenj o njegovih dejanskih lastnostih v nekompetentnem okolju.
Algebraična metoda
Courtoisovo razmišljanje je zgrajeno okoli dveh razredov metod kriptoanalize: algebraičnih in diferencialnih metod. Oglejmo si prvi razred metod.
Na poenostavljen način lahko metodo algebraične kriptoanalize opišemo kot sestavljanje in rešitev velikega sistema enačb, od katerih vsaka rešitev ustreza cilju kriptoanalitika (na primer, če je sistem sestavljen z uporabo enega para odprtega in šifriranega besedila, potem vse rešitve tega sistema ustrezajo ključem, na katerih se to odprto besedilo pretvori v to šifrirano). To pomeni, da je v primeru problema kriptoanalize blokovne šifre bistvo algebraične metode kriptoanalize v tem, da se ključ najde kot rezultat reševanja sistema polinomskih enačb. Glavna težava je, da jih je mogoče sestaviti čim več, ob upoštevanju značilnosti določene šifre. preprost sistem tako da postopek reševanja traja čim manj časa. Tu igrajo ključno vlogo značilnosti vsake analizirane šifre.
Algebraično metodo, ki jo uporablja Courtois, je mogoče na kratko opisati na naslednji način. Na prvi stopnji se uporabljajo takšne lastnosti GOST 28147-89, kot je obstoj fiksne točke za del šifrirne transformacije, pa tudi tako imenovana refleksijska točka. Zahvaljujoč tem lastnostim je več parov izbranih iz dovolj velikega števila parov golo besedilo-šifrirano besedilo, kar omogoča upoštevanje transformacij ne pri 32, ampak le pri 8 krogih. Druga stopnja je, da se na podlagi rezultatov 8 okroglih transformacij, pridobljenih na prvi stopnji, sestavi sistem nelinearnih enačb, v katerem so ključni biti neznanke. Nato se ta sistem reši (to se sliši preprosto, a je v resnici najbolj zamuden del metode, saj je sistem sestavljen iz nelinearnih enačb).
Kot je navedeno zgoraj, ni nikjer v delu natančen opis ter analiza zahtevnosti druge in glavne faze določanja ključa. Kompleksnost druge stopnje določa kompleksnost celotne metode kot celote. Namesto tega avtor navaja razvpita »dejstva«, na podlagi katerih ocenjuje delovno intenzivnost. Ta "dejstva" naj bi temeljila na eksperimentalnih rezultatih. Analiza "dejstev" iz Courtoisovega dela kot celote je podana v delu domačih avtorjev. Avtorji tega dela ugotavljajo, da je bilo veliko Courtoisovih "dejstev", predstavljenih brez kakršnih koli dokazov, med eksperimentalnim testiranjem ugotovljeno, da so napačna. Avtorji članka so šli še dlje in po Courtoisu izvedli analizo kompleksnosti druge stopnje z uporabo dobro utemeljenih algoritmov in ocen. Dobljene ocene kompleksnosti kažejo na popolno neuporabnost predstavljenega napada. Poleg domačih avtorjev so bile v delu opažene tudi velike težave, ki jih ima Courtois z ocenami in utemeljitvijo svojih metod.
Diferencialna metoda
Oglejmo si drugo Courtoisovo metodo, ki temelji na diferencialni kriptoanalizi.
Splošna metoda diferencialne kriptoanalize temelji na izkoriščanju lastnosti nelinearnih preslikav, ki se uporabljajo v kriptografskih primitivih, povezanih z vplivom vrednosti ključa na odvisnosti med razlikami med pari vhodnih in pari izhodnih vrednosti teh preslikav. . Opišimo glavno idejo diferencialne metode kriptografske analize blokovne šifre. Običajno blokovne šifre preoblikujejo vhodne podatke v stopnjah z uporabo številnih tako imenovanih okroglih transformacij, pri čemer vsaka okrogla transformacija ne uporablja celotnega ključa, temveč le del njega. Oglejmo si nekoliko »okrnjeno« šifro, ki se od originalne razlikuje po tem, da nima zadnjega kroga. Predpostavimo, da je bilo mogoče ugotoviti, da bo šifriranje dveh odprtih besedil, ki se razlikujeta v nekaterih fiksnih položajih, z uporabo takšne "okrnjene" šifre najverjetneje povzročilo šifrirana besedila, ki se prav tako razlikujejo v nekaterih fiksnih položajih. Ta lastnost kaže, da "okrnjena" šifra najverjetneje pušča odvisnost med nekaterimi odprtimi besedili in rezultati njihovega šifriranja. Da bi obnovili del ključa s to očitno napako, je treba imeti možnost šifriranja vnaprej izbranih odprtih besedil na ključu, ki ga želimo obnoviti (tako imenovani »napad izbranega odprtega besedila«). Na začetku postopka »odpiranja ključev« se naključno ustvari več parov odprtih besedil, ki se razlikujejo po istih fiksnih položajih. Vsa besedila so šifrirana s "polno" šifro. Nastali pari šifriranega besedila se uporabijo za obnovitev tistih ključnih bitov, ki so bili uporabljeni v zadnji krog transformacije, kot sledi. Z uporabo neke naključno izbrane vrednosti želenih ključnih bitov se za vsa šifrirana besedila uporabi transformacija, inverzna transformaciji zadnjega kroga. Pravzaprav, če smo uganili želeno vrednost bitov ključa, bomo dobili rezultat "okrnjene" šifre, in če nismo uganili, bomo dejansko "še bolj šifrirali podatke", kar bo samo zmanjšalo odvisnost med zgoraj navedenimi bloki (razlika je v nekaterih fiksnih položajih). Z drugimi besedami, če je bilo med rezultati takšne "dodatne obdelave" šifriranih besedil precej parov, ki se razlikujejo po fiksnih položajih, ki so nam znani, potem to pomeni, da smo uganili zahtevane ključne bite. V nasprotnem primeru bo takih parov bistveno manj. Ker je v vsakem krogu uporabljen samo del ključa, ni toliko iskanih bitov (tj. ključnih bitov, uporabljenih v zadnjem krogu), kot je bitov v v polnem ključu in jih lahko preprosto razvrstite tako, da ponovite zgornje korake. V tem primeru bomo zagotovo nekoč naleteli na pravi pomen.
Iz zgornjega opisa sledi, da je pri metodi diferencialne analize najpomembnejše število prav tistih pozicij v odprtih in šifriranih besedilih, katerih razlike igrajo ključno vlogo pri obnavljanju ključnih bitov. Temeljna prisotnost teh pozicij, kot tudi niz njihovih številk, je neposredno odvisna od lastnosti tistih nelinearnih transformacij, ki se uporabljajo v kateri koli blok šifri (ponavadi je vsa "nelinearnost" koncentrirana v t.i. S-poljih oz. nadomestna vozlišča).
Courtois uporablja nekoliko spremenjeno različico diferencialne metode. Naj takoj opozorimo, da Courtois izvaja svojo analizo za S-boxe, ki se razlikujejo od sedanjih in tistih, ki jih predlaga ISO. Delo zagotavlja diferencialne značilnosti (tista števila, v katerih naj se bloki razlikujejo) za majhno število krogov. Utemeljitev za razširitev karakteristik za več krogov, kot običajno, temelji na "dejstvih". Courtois spet izraža z ničemer drugim kot s svojo avtoriteto nepodprto domnevo, da sprememba S-polj ne bo vplivala na odpornost GOST 28147-89 proti njegovemu napadu (medtem ko so iz neznanih razlogov S-polja iz 1. delovnega osnutka dodatek k standardu ISO/IEC 18033-3 ni bil upoštevan). Analiza, ki so jo izvedli avtorji članka, kaže, da tudi če vzamemo Courtoisova neutemeljena "dejstva" za vero in analiziramo GOST 28147-89 z drugimi S-bloki, se napad spet izkaže za nič boljšega od popolnega iskanja.
Podrobna analiza Courtoisovih del s podrobno utemeljitvijo neutemeljenosti vseh izjav o zmanjšanju odpornosti ruskega standarda je bila izvedena v delih [,].
Hkrati celo sam Courtois priznava absolutno pomanjkanje natančnosti v izračunih! Naslednji diapozitiv je vzet iz Courtoisove predstavitve na sekciji kratkih obvestil FSE 2012.
Opozoriti je treba, da so Courtoisovo delo večkrat kritizirali tudi tuji raziskovalci. Na primer, njegovo delo pri konstruiranju napadov na blokovni šifrirni algoritem AES z metodo XSL je vsebovalo enake temeljne pomanjkljivosti kot delo pri analizi ruskega standarda: večina ocen delovne intenzivnosti se v besedilu pojavlja popolnoma neutemeljeno in neutemeljeno - podrobno kritiko lahko najdemo na primer v delu. Poleg tega Courtois sam priznava razširjeno zavrnitev objave svojega dela na večjih kriptografskih konferencah in v uveljavljenih strokovno pregledanih revijah, zaradi česar mu pogosto pustijo le priložnost, da govori v kratkem razdelku z napovedmi. O tem lahko na primer preberete v 3. delu dela. Tukaj je nekaj citatov samega Courtoisa v zvezi z njegovim delom:
- "Mislim, da občinstvo Asiacrypta ne bo čutilo zanimivega." Ocenjevalec Asiacrypt 2011.
- “… obstaja velik, velik, velik problem: ta napad, ki je glavni prispevek prispevka, je bil že objavljen na FSE’11 (bil je celo najboljši prispevek), …”. Recenzent za Crypto 2011.
Strokovni del mednarodne kriptografske skupnosti tako ne gleda na kakovost Courtoisovega dela z nič manjšim dvomom kot na primer izjave nekaterih ruskih strokovnjakov o njihovi zmožnosti vdreti v AES za 2100, ki niso potrjene z nobenimi doslednimi izračuni ali zadnji »dokaz« dvostranske hipoteze o neenakosti kompleksnih razredov P in NP.
Napadi Isobe in Dinur-Dankelman-Shamirja
Splošna ideja napadov Isobe () in Dinur-Dankelman-Shamir (v nadaljevanju: napad DDS) () je, da se za določen (od ključa odvisen) ozek nabor odprtih besedil konstruira enakovredna transformacija na tem naboru, ki ima preprostejša od same šifrirne transformacije. V primeru metode Isobe je to niz 64-bitnih blokov x, tako da je F 8 -1 (Swap(F 8 (z))) = z, kjer je z = F 16 (x), do F 8 ( x) in F 16 ( x) označujeta prvih 8 oziroma prvih 16 krogov šifriranja GOST 28147-89 prek Swap - operacije zamenjave polovic 64-bajtne besede. Če je odprto besedilo vključeno v ta sklop, rezultat popolne 32-krožne transformacije GOST 28147-89 sovpada z rezultatom 16-krožne, kar izkorišča avtor napada. V primeru metode DDS je to niz x, tako da je F 8 (x) = x (fiksna točka transformacije F 8). Za vsako odprto besedilo iz tega nabora transformacija GOST 28147-89 deluje popolnoma enako kot zadnjih 8 krogov, kar poenostavlja analizo.
Kompleksnost napada Isobe je 2224 operacij šifriranja, napada DDS 2192. Vendar pa so vsa vprašanja o tem, ali napadi Isobe in DDS uvajajo nove omejitve glede pogojev za uporabo našega algoritma, odpravljena z oceno zahtev glede količine materiala, potrebnega za izvedbo vsakega od napadov: metoda Isobe zahteva 2 32 parov odprtega besedila. in šifrirano besedilo ter za metodo DDS - 2 64. Obdelava takšnih količin gradiva brez spreminjanja ključa je a priori nesprejemljiva za katero koli blokovno šifro z dolžino bloka 64: na gradivu obsega 2 32, ob upoštevanju problema rojstnih dni (glej npr. ), verjetnost pojava ponovljenih blokov je blizu 1/2, kar bo napadalcu omogočilo, da iz šifriranih besedil potegne določene zaključke o odprtih besedilih, ne da bi določil ključ. Prisotnost 264 parov navadnih in šifriranih besedil, pridobljenih na enem ključu, dejansko omogoča sovražniku, da izvaja operacije šifriranja in dešifriranja, ne da bi ta ključ sploh poznal. To je posledica čisto kombinatorne lastnosti: sovražnik ima v tem primeru celotno tabelo pretvorbe šifriranja. To stanje je absolutno nesprejemljivo pod kakršnimi koli razumnimi pogoji delovanja. Na primer, v CryptoPro CSP Obstaja tehnična omejitev količine šifriranega gradiva (brez pretvorbe ključa) 4 MB (glej). Tako je stroga prepoved uporabe ključa na materialu takšnega obsega neločljivo povezana s katero koli blokovno šifro z dolžino bloka 64 bitov, zato napadi Isobe in DDS nikakor ne zožijo obsega uporabe algoritma GOST 28147-89. ob ohranjanju največje možne moči 2.256.
Seveda je treba opozoriti, da so raziskovalci (Isobe in Dinur-Dankelman-Shamir) pokazali, da nekatere lastnosti algoritma GOST 28147-89 omogočajo iskanje analiznih poti, ki jih ustvarjalci algoritma niso upoštevali. Preprosta oblika razporeda ključev, ki bistveno poenostavi nalogo konstruiranja učinkovitih implementacij, omogoča tudi, da nekateri redki primeri ključev in odprtih besedil konstruirajo več preprosti opisi transformacije, ki jih izvaja algoritem.
Delo dokazuje, da je to negativno lastnost algoritma mogoče zlahka odpraviti s popolnim ohranjanjem operativnih značilnosti, vendar je na žalost sestavni del algoritma v svoji splošno uporabljeni obliki.
Upoštevajte, da je določena malomarnost pri ocenah povprečne delovne intenzivnosti prisotna tudi v delu Dinurja, Dunkelmana in Shamirja. Tako pri konstruiranju napada ni dovolj pozoren na naslednjo točko: za pomemben delež ključev je nabor odprtih besedil x, tako da je F 8 (x) = x, prazen: morda preprosto ni fiksnih točk. za 8 krogov transformacije. Obstoj fiksnih točk je odvisen tudi od izbire nadomestnih vozlišč. Tako je napad uporaben le za določena nadomestna vozlišča in ključe.
Prav tako je treba omeniti še eno delo z napadom na GOST 28147-89. Februarja 2012 se je pojavil elektronski arhiv mednarodnega kriptografskega združenja ePrint posodobljena različicačlanek (iz novembra 2011), ki je vseboval nov napad na GOST 28147-89. Značilnosti predstavljenega napada so naslednje: prostornina materiala je 2 32 (kot Isobe), delovna intenzivnost pa 2 192 (kot DDS). Tako je ta napad izboljšal napad DDS s časovnim zapisom v smislu količine materiala z 2 64 na 2 32. Ločeno ugotavljamo, da so avtorji pošteno predstavili vse izračune z utemeljitvijo zahtevnosti in obsega gradiva. Po 9 mesecih je bila ugotovljena temeljna napaka v zgornjih izračunih in od novembra 2012 posodobljena različica članka v elektronskem arhivu ne vsebuje več rezultatov glede domačega algoritma.
Napadi ob predpostavki, da napadalec "nekaj" ve o ključih
Na koncu omenimo, da je v literaturi tudi nekaj del (glej na primer in ), posvečenih napadom na GOST 28147-89 v tako imenovanem modelu povezanega ključa. Ta model v bistvu vsebuje predpostavko, da lahko napadalec pridobi dostop za analizo ne samo do parov odprtega besedila in šifriranega z želenim ključem, temveč tudi do parov odprtega besedila in šifriranega besedila, pridobljenih z uporabo (prav tako neznanih) ključev, ki se od iskanega razlikujejo po znanem pravilnem način (na primer pri fiksnih položajih bitov). V tem modelu je res mogoče dobiti zanimive rezultate o GOST 28147-89, vendar v tem modelu ni mogoče dobiti nič manj močnih rezultatov o, na primer, ki se najbolj uporablja v sodobnih omrežjih običajna uporaba Standard AES (glej na primer). Upoštevajte, da pogoji za izvedbo tovrstnega napada nastanejo pri uporabi šifre v določenem protokolu. Opozoriti je treba, da tovrstni rezultati, čeprav so nedvomno akademskega pomena z vidika proučevanja lastnosti kriptografskih transformacij, dejansko niso relevantni za prakso. Na primer, vsa orodja za zaščito kriptografskih informacij, ki jih je potrdil FSB Rusije, izpolnjujejo najstrožje zahteve za sheme generiranja šifrirnih ključev (glej na primer). Kot je navedeno v rezultatih analize, če obstaja 18 povezanih ključev in 2 10 parov odprtega besedila in blokov šifriranega besedila, je kompleksnost popolnega odpiranja zasebnega ključa z verjetnostjo uspeha 1-10 -4 dejansko 2 26 . Če pa so izpolnjene zgoraj omenjene zahteve za razvoj materiala ključev, je verjetnost, da boste našli takšne ključe, 2 -4352, torej 24096-krat manjša, kot če preprosto poskušate uganiti skrivni ključ v prvem poskusu.
Dela, povezana z modelom s povezanimi ključi, vključujejo tudi delo, ki je leta 2010 povzročilo veliko hrupa v ruskih elektronskih publikacijah, ki ne trpijo zaradi navade skrbnega preverjanja gradiva v tekmi za senzacije. Rezultati, predstavljeni v njem, niso bili podprti z nobeno strogo utemeljitvijo, vendar so vsebovali glasne izjave o možnosti vdora v državni standard Ruska federacija na šibkem prenosniku v nekaj sekundah - na splošno je bil članek napisan v najboljših tradicijah Nicolasa Courtoisa. Toda kljub povsem očitni neutemeljenosti članka za bralca, ki je bolj ali manj seznanjen z osnovnimi načeli znanstvenih publikacij, je Rudski prav zato, da bi pomiril rusko javnost po delu, napisal podrobno in temeljito besedilo, ki vsebuje celovito analizo te pomanjkljivosti. Članek s samoumevnim naslovom »O ničelnem praktičnem pomenu dela »Key recovery attack on full GOST block chipher with zero time and memory«« daje utemeljitev, da povprečna kompleksnost metode, podane v, ni nič manjša od kompleksnosti popolnega iskanja.
Suhi ostanek: kaj je trajnost v praksi?
Na koncu predstavljamo tabelo, ki vsebuje podatke o vseh rezultatih strogo opisanih in utemeljenih napadov na GOST 28147-89, ki so znani mednarodni kriptografski skupnosti. Upoštevajte, da je kompleksnost podana v operacijah šifriranja algoritma GOST 28147-89, pomnilnik in material pa sta navedena v blokih algoritma (64 bitov = 8 bajtov).
| Napad | Intenzivnost dela | Spomin | Potreben material |
| Isobe | 2 224 | 2 64 | 2 32 |
| Dinur-Dankelman-Shamir, FP, 2DMitM | 2 192 | 2 36 | 2 64 |
| Dinur-Dankelman-Shamir, FP, malo spomina | 2 204 | 2 19 | 2 64 |
| 2 224 | 2 36 | 2 32 | |
| Dinur-Dankelman-Shamir, Odsev, 2DMitM | 2 236 | 2 19 | 2 32 |
| Dokončaj iskanje | 2 256 | 1 | 4 |
| Število nanosekund od nastanka vesolja | 2 89 |
Kljub precej obsežnemu ciklu raziskav na področju stabilnosti algoritma GOST 28147-89, ta trenutek Ni znanega niti enega napada, ki bi bil dosegljiv v skladu z operativnimi zahtevami 64-bitne dolžine bloka. Omejitve količine materiala, ki ga je mogoče obdelati na enem ključu, ki izhajajo iz parametrov šifre (dolžina bita ključa, dolžina bita bloka), so bistveno strožje od minimalne količine, potrebne za izvedbo katerega koli trenutno znanega napada. Posledično pri izpolnjevanju obstoječih operativnih zahtev nobena od metod kriptoanalize, predlaganih do danes GOST 28147-89, ne omogoča določitve ključa z delovno intenzivnostjo, manjšo od izčrpnega iskanja.
