1 Blok dijagram algoritma kriptografska pretvorba 1

2 Jednostavan način zamjene 4

3 Gama način rada 8

4 Gama mod s Povratne informacije 11

5 Način generiranja umetka simulacije 14

Dodatak 1 Pojmovi korišteni u ovom standardu i njihove definicije 16

Dodatak 2. Vrijednosti konstanti C1, C2 18

Dodatak 3 Sheme programska implementacija kriptografski algoritam

transformacije. 19

Dodatak 4 Pravila za zbrajanje modulo 2 32 i modulo (2 32 -I) 25

DRŽAVNI STANDARD

SAVEZ SSSR-a

SUSTAVI ZA OBRADU INFORMACIJA. KRIPTOGRAMSKA SIGURNOST

Algoritam kriptografske pretvorbe

Datum uvođenja 01.07.90

Ova norma uspostavlja jedinstveni algoritam kriptografske transformacije za sustave obrade informacija u mrežama elektroničkih računala (računala), pojedinačnih računalnih sustava i računala, koji definira pravila za šifriranje podataka i razvoj imitacija.

Algoritam kriptografske transformacije dizajniran je za hardversku ili softversku implementaciju, zadovoljava kriptografske zahtjeve i, u svojim mogućnostima, ne nameće ograničenja na stupanj tajnosti zaštićenih informacija.

Norma je obvezna za organizacije, poduzeća i ustanove koje koriste kriptografska zaštita podaci pohranjeni i preneseni u računalnim mrežama, u zasebnim računalnim sustavima ili u računalima.

Izrazi korišteni u ovoj normi i njihove definicije dani su u Dodatku 1.

I. BLOK DIJAGRAM ALGORITMA ZA KRIPTOGRAFSKU TRANSFORMACIJU

1.1. Blok dijagram algoritma kriptografske transformacije (kripto-shema) sadrži (vidi sliku 1):

Službena objava ★

256-bitni uređaj za pohranu ključeva (KSD), koji se sastoji od osam 32-bitnih pogona (X0, Xt. X2, A3 L4, X$, X6, Xu); četiri 32-bitna pogona (/V (, N 2, Nj, /V 4);

Umnožavanje je zabranjeno

© Izdavačka kuća za standarde, 1989. © Izdavačka kuća za standarde IPK, 1996.

dva 32-bitna pogona L/$,) s trajnim ispunama C 2, C\\ snimljenim u njima

dva 32-bitna modulo 2 32 zbrajala (SM|, SL/3);

32-bitno zbrajalo bitovnog zbrajanja modula 2 (SL/2);

32-bitni modulo zbrajalo (2 32 - 1) (SL/ 4);

modulo 2(SL/5) zbrajalo, nema ograničenja u kapacitetu SL/$ zbrajala;

supstitucijski blok (A);

ciklički posmični registar jedanaest koraka prema najznačajnijoj znamenki (R).

1.2. Supstitucijski blok A" sastoji se od osam supstitucijskih čvorova A'j,

A 2, A“z, K 4, A5, A7, A 8 sa 64-bitnom memorijom svaki. Post

32-bitni vektor primijenjen na supstitucijski blok podijeljen je u osam sekvencijalnih 4-bitnih vektora, od kojih je svaki konvertiran u 4-bitni vektor pomoću odgovarajućeg supstitucijskog čvora, što je tablica od šesnaest redaka koji sadrže četiri bita punjenja po retku. . Ulazni vektor određuje adresu retka u tablici, popuna tog retka je izlazni vektor. 4-bitni izlazni vektori se zatim sekvencijalno spajaju u 32-bitni vektor.

1.3. Kod zbrajanja i cikličkog pomicanja binarnih vektora najvažnijim bitovima smatraju se bitovi uređaja za pohranu s velikim brojevima.

1.4. Pri pisanju ključa (I", W 2 ..., W q e (0,1), d = N256, u

Vrijednost KZU W\ upisuje se u i-tu znamenku pogona Xq, vrijednost W 2 upisuje se u 2. znamenku pogona L#, ..., vrijednost W^ 2 upisuje se u 32. znamenku pogona. pogon Xq; vrijednost W33 upisuje se u 1. znamenku pogona X\ y, vrijednost se unosi u 2. znamenku pogona X\ y..., vrijednost W M unosi se u 32. znamenku pogona X\\ vrijednost W 6 5 unosi se u 1. znamenku pogona X 2 itd., vrijednost 1U 2 5b unosi se u 32. bit pogona Xy.

1.5. Prilikom prepisivanja informacija, sadržaj p-te znamenke jednog pogona (zbrajača) prepisuje se u p-tu znamenku drugog pogona (zbrajača).

1.6. Vrijednosti konstantnih punjenja Cj, C 2 (konstante) skladišnih uređaja /V 6, /V5 date su u Dodatku 2.

1.7. Ključevi koji određuju popunjenost KZU i tablica supstitucijskog bloka K su tajni elementi i dostavljaju se na propisani način.

Popunjavanje tablica supstitucijskog bloka K dugoročni je ključni element zajednički računalnoj mreži.

Organizacija različite vrste komunikacija se ostvaruje izgradnjom odgovarajućeg ključnog sustava. U tom slučaju može se koristiti mogućnost generiranja ključeva (ispunjavanje KZU) u jednostavnom zamjenskom modu i njihovo šifriranje u jednostavnom zamjenskom modu uz pružanje imitacijske zaštite za prijenos komunikacijskim kanalima ili pohranu u memoriju računala.

1.8. Kripto shema omogućuje četiri vrste rada: šifriranje (dešifriranje) podataka u jednostavnom načinu zamjene; šifriranje (dešifriranje) podataka u gama modu;

šifriranje (dešifriranje) podataka u gama modu s povratnom spregom;

način generiranja umetka simulacije.

Sheme programske implementacije algoritma kriptografske transformacije dane su u Dodatku 3.

2. JEDNOSTAVNI NAČIN PROMJENE

2.1. Šifriranje čistih podataka korištenjem jednostavnog načina zamjene

2.1.1. Kriptoshema koja implementira algoritam enkripcije u načinu jednostavne zamjene trebala bi imati oblik prikazan na slici 2.

Otvoreni podaci koji se šifriraju podijeljeni su u blokove od po 64 bita. Unos bilo kojeg bloka T () = (D|(0), ^(O), ..., d 3 1(0), i 32 (0), £|(0), b 2 (0) y. ., Z> 32 (0)) binarnih informacija u pogone N\ i N 2 provodi se tako da se vrijednost D|(0) unese u 1. bit N|, unese se vrijednost a 2 (0). u 2. bit/ Vj itd., vrijednost i 32 (0) unosi se u 32. znamenku iVj; unosi se vrijednost />|(0).

1. znamenka L/ 2, u 2. znamenku N 2 upisuje se vrijednost b 2 (0) itd., u 32. znamenku N 2 upisuje se vrijednost >> 32 (0). Kao rezultat dobiva se stanje (i 32 (0), i 3 |(0), ..., i 2 (0) y<7|(0)) накопителя yVj и состояние (/>32 (0), b 2 1(0), ... , />|(0)) skladišna jedinica N 2.

2.1.2. 256 bita ključa se unosi u RCU. Sadržaj osam 32-bitnih pogona Aq, X\ t ..., Xj ima oblik:

^0 = (^32^3.....

*1 =(^64^63, . ^34^33)

*7 = (^56> ^255. ... , I/ 226, ^ 225)

2.1.3. Algoritam šifriranja za 64-bitni blok običnih podataka u načinu jednostavne zamjene sastoji se od 32 ciklusa.

U prvom ciklusu se početno punjenje spremišta zbraja modulo 2 32 u zbrajaču CM\ s punjenjem spremišta Xq, dok se punjenje spremišta Nj održava.

Rezultat zbrajanja pretvara se u supstitucijskom bloku K i dobiveni vektor se šalje na ulaz registra /?, gdje se ciklički pomiče za jedanaest koraka prema najvažnijim bitovima. Rezultat pomaka zbraja se bit po bit modulo 2 u zbrajaču CM 2 s 32-bitnim punjenjem pogona yV 2 . Dobiveni rezultat u CM 2 ispisuje se u N\%, sa starim punjenjem N| prepisano u N 2. Prvi ciklus završava.

Sljedeći ciklusi se provode na sličan način, sa

U 2. ciklusu, punjenje X\ se očitava iz RCU, u 3. ciklusu iz RCU

očitava se punjenje X2 itd., u 8. ciklusu očitava se punjenje Xj iz RCU. U ciklusima od 9 do 16, kao iu ciklusima od 17 do 24, ispune iz RCU čitaju se istim redoslijedom:

U posljednjih osam ciklusa od 25. do 32. redoslijed očitavanja RCD punjenja je obrnut:

dovraga, dovraga, dovraga, dovraga.

Dakle, kod šifriranja u 32 ciklusa, provodi se sljedeći redoslijed odabira punjenja memorije:

dovraga, ^2,^),^4>^5,^6"^7, dovraga, ^2,^3"^4,^5,-^6,^7, dovraga, dovraga, dovraga, dovraga, dovraga ,pakao,pakao,pakao.

U 32. ciklusu rezultat iz zbrojnika SL/ 2 upisuje se u spremište UU 2, a staro punjenje pohranjuje se u spremište N\.

Primljeno nakon 32. ciklusa enkripcije popunjavanja N| i N2 su šifrirani blok podataka koji odgovara bloku čistih podataka.

2.1 4 Jednadžbe šifriranja u načinu jednostavne zamjene imaju oblik:

J*Cr> "(

I b(/) = a(/~ I)

pri y = I -24;

G"

\bO) - a O - O na / 8* 25 -g 31; a(32) = a(31)

A (32) = (d (31) ffl X 0)KRG> b (31)

gdje je d(0) = (a 32 (0), «z|(0), ... , D|(0)) početno punjenje N\ prije prvog ciklusa šifriranja;

6(0) = (632(0), 63j(0), ... , 6j(0)) - početno punjenje /U 2 prije prvog ciklusa šifriranja;

a(j) = (032(7), 0z|(/) e... , 0|(/)) - punjenje kontrolne jedinice, nakon y-tog ciklusa šifriranja;

b(j) = (6z 2 (/), 63j(/"), ... , 6|(/)) - popunjavanje /V 2 nakon y-tog ciklusa šifriranja, y = 032.

Znak φ označava bitni zbroj 32-bitnih vektora po modulu 2.

Znak Š označava zbroj 32-bitnih vektora po modulu 2 32. Pravila za zbrajanje po modulu 2 32 dana su u Dodatku 4;

/? - operacija cikličkog pomaka od jedanaest koraka prema najvišim znamenkama, tj.

^(g 32"O|>g 30>g 29>g 28>g 27>g 26"g 25>g 24>g 23'G 22"G 2b G 20>"g 2* g |)~

= (g 21" g 20> - "g 2* g 1 * G 32>G31 *GzO" g 29* g 28*, 27e"26e/"25>, 24>G23", 22)*

2.1.5. 64-bitni blok šifriranih podataka Tsh izlazi iz pogona L^, VU 2 sljedećim redoslijedom: od 1., 2., ..., 32. bita pogona L7|, zatim od 1., 2., ... , 32. bit memorije W 2, tj.

t w - (a,<32),0 2 (32),0 32 (32), 6,(32), 6 2 <32),6 32 <32».

Preostali blokovi otvorenih podataka u načinu jednostavne zamjene šifrirani su na isti način.

2.2. Dešifriranje šifriranih podataka korištenjem jednostavnog načina zamjene

2.2.1. Kriptoshema koja implementira algoritam dešifriranja u modu jednostavne zamjene ima isti oblik (vidi Chsrt.2) kao i kod enkripcije. 256 bita istog ključa koji se koristi za enkripciju unosi se u RCU. Šifrirani podaci koji se dešifriraju podijeljeni su u blokove od po 64 bita. Unesite bilo koji blok

T w - (0,(32),o 2 (32), ..., 0 32 (32), 6,(32), 6 2 (32), ..., 6 32 (32))

u akumulatore L', i N 2 proizvode se tako da se vrijednost dj(32) upisuje u 1. znamenku /V, vrijednost o 2 (32) upisuje se u 2. znamenku /V itd., vrijednost a 32 (32) upisuje se u 32. znamenku /V,; vrijednost 6,(32) upisuje se u 1. znamenku N2 itd., vrijednost 6 32 (32) unosi se u 32. znamenku N2.

2.2.2. Dešifriranje se provodi prema istom algoritmu kao i enkripcija otvorenih podataka, s tom razlikom što se punjenja pogona Xq, X\y..., Xj čitaju iz RCU-a u ciklusima dešifriranja sljedećim redoslijedom:

dovraga, dovraga 3, dovraga, dovraga, dovraga, dovraga, dovraga, dovraga 0,

pakao 6, pakao 4, pakao 2, pakao, pakao, pakao, pakao 2, pakao.

2.2.3. Jednadžbe dešifriranja izgledaju ovako:

G d (32 - /) = (d (32 - / + 1) SHLG,.,) *LF6(32 - / + 1) b (32 - /) = d (32 - / + 1) at, / = 1+8;

I o(32- /) = (a(32-/M)SHDG (32 _ /)(tod8))KLFL(32./M) |6(32-/) = d (32 - / + 1)

na /= 9 + 31;

b(0) = (a (1) ŠDGo) OFj(1)

2.2.4. Pogoni W i N 2 dobiveni nakon 32 ciklusa rada čine blok otvorenih podataka.

Tada je = (fli(O), a 2 (0), ... , Az 2 (0)» 6, (0), 6 2 (0), ... , 6 32 (0)), što odgovara blok šifriranih podataka, dok vrijednost o,(0) bloka 7o odgovara sadržaju 1. bita yV, vrijednost 02(0) odgovara

P. 8 GOST 28147-89

odgovara sadržaju 2. bita N\ itd., vrijednost Dz2(0) odgovara sadržaju 32. bita N\; vrijednost 6j(0) odgovara sadržaju 1. bita; vrijednost ^(0) odgovara sadržaju 2. bita N2, itd., vrijednost £zg(0) odgovara sadržaju 32. bita N2. -

Preostali blokovi šifriranih podataka dekriptiraju se na isti način.

2.3. Algoritam šifriranja u načinu jednostavne zamjene 64-bitnog bloka G 0 označen je s A y tj.

A (T 0) = A (a (0), b (0)) = (a (32), b (32)) = T w.

2.4. Način jednostavne zamjene može se koristiti za šifriranje (dekriptiranje) podataka samo u slučajevima navedenim u točki 1.7.

3. NAČIN IGRANJA

3.1. Šifriranje otvorenih podataka u gama načinu rada

3.1.1. Kriptoshema koja implementira algoritam šifriranja u gama modu ima oblik prikazan na slici 3.

Otvoreni podaci, podijeljeni u 64-bitne blokove T\)\ 7), 2) ..., 7)) m “, 1 7[) M), šifrirani su u gama modu bitovnim zbrajanjem po modulu 2 u zbrajaču SL/ 5 sa šifrom gama Gš, koja se proizvodi u blokovima od 64 bita, tj.

G _/L1) R2) Lm-1) LM)\

"bolest V 1 w e * w * » " Sh » " * * * " 111 /»

gdje je M određen volumenom šifriranih podataka.

Tjj) - Yth 64-bitni blok, /“ broj binarnih znamenki u bloku 7J) M) može biti manji od 64, dok se dio raspona šifre koji se ne koristi za šifriranje iz bloka G\^] odbacuje.

3.1.2. 256 bita ključa se unosi u RCU. 64-bitna binarna sekvenca (sinkronizacija) S = (5*1, S 2, ..., 5^4) uvodi se u pogone iVj, N 2, što je početno punjenje ovih pogona za sljedeću generaciju M-blokova gama šifre. Poruka sinkronizacije unosi se u jV| i L^tako da se vrijednost 5[ upisuje u 1. znamenku VU), vrijednost S 2 upisuje se u 2. znamenku N\ itd., vrijednost ^unosi se u 32. znamenku 7V|; vrijednost S33 upisuje se u 1. znamenku N2, vrijednost 4S34 upisuje se u 2. znamenku N2 itd., vrijednost se upisuje u 32. znamenku N2.

3.1.3. Početno punjenje pogona /Vj i N 2 (sinkronizacija poruke.5) šifrirano je u jednostavnom načinu zamjene u skladu s

Poznati istraživač, utemeljitelj algebarske kriptoanalize, Nicolas Courtois, tvrdi da je GOST blok šifra, koja je uskoro trebala postati međunarodni standard, zapravo probijena i očekuje mnoge publikacije u budućnosti koje bi trebale razviti njegove ideje o nestabilnosti ovog algoritma.

Slijede kratki izvodi iz ovog rada, koji se može smatrati alarmantnim napadom usred međunarodne standardizacije (autor je bio poznat po sličnim pretjerivanjima u vezi s AES-om, ali je njegov rad tada imao veliki teorijski utjecaj na kriptoanalizu, ali nije vodio do praktičnih napada na sam AES). No, možda je ovo pravo upozorenje o početku faze "poniranja aviona u vrtoglavicu", koja bi mogla završiti kolapsom nacionalnog standarda šifriranja, kao što je bio slučaj s algoritmom za raspršivanje SHA-1 i "de facto" MD5 algoritam raspršivanja.

GOST 28147-89 standardiziran je 1989. i postao je prvi službeni standard za zaštitu povjerljivih informacija, ali je specifikacija šifre ostala zatvorena. 1994. standard je deklasificiran, objavljen i preveden na engleski. Po analogiji s AES-om (i za razliku od DES-a), GOST-u je dopušteno štititi klasificirane podatke bez ograničenja, u skladu s načinom na koji je navedeno u ruskom standardu. Da. GOST nije analog DES-a, već konkurent 3-DES-u s tri neovisna ključa ili AES-256. Očito je da je GOST prilično ozbiljna šifra koja zadovoljava vojne kriterije, stvorena za najozbiljnije primjene. Najmanje dva skupa GOST S-boxova identificirana su na temelju aplikacija koje koriste ruske banke. Te banke moraju održavati tajnu komunikaciju sa stotinama podružnica i zaštititi milijarde dolara od lažnih krađa.

GOST je blok šifra s jednostavnom Feistelovom strukturom, s veličinom bloka od 64 bita, 256-bitnim ključem i 32 kruga. Svaka runda sadrži modulo 2^32 zbrajanje ključa, skup od osam 4-bitnih S-kutija i jednostavan 11-bitni kružni pomak. Značajka GOST-a je mogućnost tajnog pohranjivanja S-blokova, koji se mogu smatrati drugim ključem, povećavajući efektivni materijal ključa na 610 bita. Jedan set S-kutija objavljen je 1994. kao dio specifikacije hash funkcije GOST-R 34.11-94 i, kako je napisao Schneier, koristila ga je Središnja banka Ruske Federacije. Također je uključen u standard RFC4357 u dijelu "id-GostR3411-94-CryptoProParamSet". Došlo je do pogreške u izvornim kodovima na kraju Schneierove knjige (u redoslijedu S-kutije). Najtočnija referentna implementacija izvornog ruskog podrijetla sada se može pronaći u biblioteci OpenSSL. Ako se negdje koriste tajne S-kutije, onda se mogu izdvojiti iz softverskih implementacija i iz mikrosklopova, o čemu su objavljeni odgovarajući radovi.

GOST je ozbiljan konkurent

Uz vrlo veliku veličinu ključa, GOST ima značajno nižu cijenu izvršenja u usporedbi s AES i drugim sličnim sustavima šifriranja. Zapravo, košta puno manje od AES-a, koji zahtijeva četiri puta više hardverskih logičkih vrata za značajno nižu navedenu razinu sigurnosti.

Nije iznenađujuće da je GOST postao internetski standard, posebno je uključen u mnoge kripto biblioteke kao što su OpenSSL i Crypto++, te postaje sve popularniji izvan svoje zemlje porijekla. Godine 2010. GOST je podvrgnut ISO standardizaciji kao svjetski standard šifriranja. Iznimno mali broj algoritama uspio je postati međunarodni standard. ISO/IEC 18033-3:2010 opisuje sljedeće algoritme: četiri 64-bitne šifre - TDEA, MISTY1, CAST-128, HIGHT - i tri 128-bitne šifre - AES, Camellia, SEED. Predlaže se da se GOST doda istom standardu ISO/IEC 18033-3.

Po prvi put u povijesti industrijske standardizacije, imamo posla s tako konkurentnim algoritmom u smislu optimalnosti između cijene i razine sigurnosti. GOST iza sebe ima 20 godina pokušaja kriptoanalize, a donedavno njegova vojna sigurnost nije bila upitna.

Kako je autor nedavno doznao putem privatne korespondencije, većina zemalja glasala je protiv GOST-a na glasovanju ISO-a u Singapuru, no rezultati ovog glasovanja ipak će se razmatrati na plenarnom sastanku ISO SC27, tako da je GOST još uvijek u procesu standardizacije na vrijeme izdanja ovog djela.

Stručna mišljenja o GOST-u

Nijedna od dostupnih informacija i literature u vezi s GOST-om ne daje razloga vjerovati da bi šifra mogla biti nesigurna. Naprotiv, velika veličina ključa i veliki broj krugova čine GOST, na prvi pogled, pogodnim za desetljeća uporabe.

Svatko tko je upoznat s Mooreovim zakonom razumije da će, u teoriji, 256-bitni ključevi ostati sigurni najmanje 200 godina. GOST su naširoko proučavali vodeći stručnjaci za kriptografiju poznati u području analize blok šifara, kao što su Schneier, Biryukov, Dunkelman, Wagner, mnogi australski, japanski i ruski znanstvenici, stručnjaci za ISO kriptografiju, i svi su istraživači izrazili da izgleda ovako da može ili treba biti sigurno. Iako je široko shvaćeno da je sama GOST struktura izuzetno slaba, na primjer, u usporedbi s DES-om, posebno difuzija nije tako dobra, ali to je uvijek bilo zbog činjenice da se to mora nadoknaditi velikim brojem krugova (32), kao i dodatna nelinearnost i difuzija dobivena modulo zbrajanjem.

Biryukov i Wagner napisali su: "Veliki broj metaka (32) i dobro proučena Feistelova konstrukcija, u kombinaciji s uzastopnim Shannonovim permutacijama, pružaju solidnu osnovu za GOST sigurnost." U istom radu čitamo: "nakon značajnog ulaganja vremena i truda, nije postignut napredak u standardu kriptoanalize u otvorenoj literaturi." Stoga nije bilo značajnih napada koji bi omogućili dešifriranje ili oporavak ključa u realističnom scenariju gdje se GOST koristi u enkripciji s mnogo različitih slučajnih ključeva. Nasuprot tome, postoji mnogo radova o napadima na slabe ključeve u GOST-u, napadima s povezanim ključevima, napadima na oporavak tajnih S-kutija. Na Crypto 2008. predstavljeno je hakiranje hash funkcije temeljene na ovoj šifri. U svim napadima napadač ima znatno veću razinu slobode nego što mu je inače dopušteno. U tradicionalnim primjenama enkripcije pomoću nasumično odabranih ključeva do danas nisu pronađeni ozbiljni kriptografski napadi na GOST, što je 2010. izraženo sažetom frazom: „unatoč značajnim naporima kriptoanalitičara u proteklih 20 godina, GOST još nije krekiran” (Axel Poschmann, San Ling i Huaxiong Wang: 256-bitna standardizirana kripto za 650 GE GOST Revisited, u CHES 2010, LNCS 6225, str. 219-233, 2010.).

Linearna i diferencijalna analiza GOST

U dobro poznatoj Schneierovoj knjizi čitamo: "U odnosu na diferencijalnu i linearnu kriptoanalizu, GOST je vjerojatno robusniji od DES-a." Glavnu procjenu sigurnosti GOST-a dali su 2000. godine Gabidulin i dr. Njihovi rezultati su vrlo impresivni: uz predviđenu razinu sigurnosti od 2^256, pet rundi je dovoljno da zaštiti GOST od linearne kriptoanalize. Štoviše, čak i kada se S-blokovi zamjenjuju identičnima i jedina nelinearna operacija šifre - zbrajanje po modulu 2^32 - šifra je još uvijek otporna na linearnu kriptoanalizu nakon 6 rundi od 32. GOST diferencijalna kriptoanaliza izgleda relativno lakša i privlači više pažnje. Za razinu sigurnosti 2^128, istraživači (Vitaly V. Shorin, Vadim V. Jelezniakov i Ernst M. Gabidulin: Linearna i diferencijalna kriptoanaliza ruskog GOST-a, Preprint dostavljen Elsevier Preprintu, 4. travnja 2001.) pretpostavili su dovoljan otpor na razini od 7 rundi. Prema njima, hakiranje GOST-a u više od pet krugova je "izuzetno teško". Štoviše, dva japanska istraživača pokazala su da klasični diferencijalni napad naprijed s jednom diferencijalnom karakteristikom ima izuzetno nisku vjerojatnost preživljavanja velikog broja rundi. Na temelju činjenice proučavanja prilično "dobre" iterativne diferencijalne karakteristike za ograničeni broj rundi (koja sama po sebi ima vjerojatnost prolaska ne bolju od 2-11,4 po rundi), vrijednosti skupa odgovarajućih ključeva su manje nego pola. Za cijeli krug GOST-a, takav napad s jednom karakteristikom radit će samo sa zanemarivim dijelom tipki reda veličine 2-62 (a čak i u ovom malom dijelu imat će vjerojatnost prolaska ne više od 2- 360).

Složeniji napadi uključuju višestruke diferencijale koji slijede specifične obrasce, kao što je korištenje pojedinačnih S-kutija koje imaju nulte razlike dok drugi bitovi imaju različite od nule. Govorimo o diskriminirajućim napadima na temelju loših svojstava difuzije GOST-a. Najbolji od ovih napada radi protiv 17 rundi GOST-a, ovisi o ključu i ima izuzetno slab diskriminator nasumičnih podataka na izlazu, tako da se nekako može koristiti za dobivanje informacija o ključu.

Klizeći i reflektirajući napadi

Prema Biryukovu i Wagneru, struktura GOST-a, koja uključuje obrnuti redoslijed podključeva u završnim rundama, čini ga otpornim na klizne napade (aka "klizni napadi"). Međutim, zbog prisutnosti velike količine samosličnosti u šifri, dopušta napade inverzijom ključa na kombinacije fiksnih točaka i svojstava "odraza" (aka "reflektirajući napadi") za određene slabe ključeve. Složenost ovog napada je 2^192 i 2^32 podudarnih otvorenih tekstova.

Najnoviji rezultati

Novi napadi također koriste refleksiju i zapravo su razbili GOST, koji je predstavljen na konferenciji FSE 2011. Ove napade je također samostalno otkrio autor ovog rada. Napad zahtijeva 2^132 bajta memorije, što je zapravo gore od sporijih napada s manjim zahtjevima za memoriju.

Mnogi novi napadi temeljeni na samosličnosti rade protiv svih GOST ključeva i omogućuju vam da probijete cijeli GOST s 256-bitnim ključem, a ne samo za slabe ključeve, kao što je ranije bio slučaj. Svi ovi napadi zahtijevaju znatno manje memorije i znatno su brži.

Ovi novi napadi mogu se promatrati kao primjeri nove opće paradigme za kriptoanalizu blok šifri nazvane "algebarsko smanjenje složenosti", generalizirajući ove napade na mnoge posebne slučajeve napada s poznatim fiksnim točkama, proklizavanjem, involucijama i ciklusima. Važno je da u obitelji svih ovih napada postoje oni koji omogućuju GOST kriptoanalizu bez ikakvih refleksija i bez ikakvih simetričnih točaka koje se pojavljuju tijekom izračuna. Jedan primjer je jednostavan GOST hakerski napad bez odraza u ovom radu.

Algebarska kriptoanaliza i napadi niske složenosti na šifre smanjenog kruga

Algebarski napadi na blokovske i tokovne šifre mogu se predstaviti kao problem rješavanja velikog sustava Booleovih algebarskih jednadžbi koje slijede geometriju i strukturu vlasničke kriptografske sheme. Sama ideja seže do Shannon. U praksi je uveden za DES (prvi ga je uveo autor ovog rada) kao formalna metoda kodiranja i može razbiti 6 rundi na samo jednom poznatom otvorenom tekstu. Manipulacija jednadžbama odvija se na temelju XL algoritama, Gröbnerovih baza, ElimLin metode i SAT solvera.

U praksi su algebarski napadi implementirani protiv vrlo malog broja krugova blok šifara, ali su već doveli do razbijanja tokovnih šifara, a također je bilo uspjeha u razbijanju ultra-laganih šifara za mikrohardver. Zbog poteškoća u memorijskom prostoru i procjenama računalnih troškova, kombiniraju se s drugim napadima.

Kako hakirati GOST?

Algebarski napad na cjeloviti GOST detaljnije je predstavljen u publikaciji koja se razmatra. U prethodnom radu, autor je već naveo 20 algebarskih napada na GOST i očekuje veliki broj njih u bliskoj budućnosti. Napad predložen u ovom radu nije najbolji od njih, ali otvara jednostavan (barem za kriptografe da razumiju) put za kasniji razvoj kako bi se stvorila posebna metodologija za razbijanje GOST-a.

Praktični rezultat je još uvijek skroman: 2^64 poznatih otvorenih tekstova i 2^64 memorije za pohranjivanje parova otvoreni tekst/šifrirani tekst omogućuju probijanje GOST-a 2^8 brže od jednostavne grube sile. Ali u smislu kriptoanalize, to čini izjavu da je "GOST hakiran" potpuno istinitom.

zaključke

GOST je osmišljen kako bi osigurao vojnu razinu sigurnosti u narednih 200 godina. Većina vodećih stručnjaka koji su proučavali GOST složila se da "unatoč značajnim kriptoanalitičkim naporima tijekom 20 godina, GOST još nije probijen." Godine 2010. GOST je promoviran u ISO 18033 kao globalni standard šifriranja.

Osnova ideja o algebarskoj kriptoanalizi nastala je prije više od 60 godina. Ali tek u posljednjih 10 godina razvijeni su učinkoviti softverski alati za (djelomično) rješavanje raznih NP-potpunih problema. Brojne šifre toka su razbijene. Samo je jedna blok šifra razbijena ovom metodom - sam slabi KeeLoq. U ovom radu autor razbija važnu, stvarno korištenu GOST šifru. Napominje da je ovo prvi put u povijesti da je standardizirana vladina šifra razbijena algebarskom kriptoanalizom.

Jednostavan "MITM s refleksijom" napad na GOST već je predstavljen na konferenciji FSE 2011. U radu o kojem se raspravlja u ovom članku, predstavljen je još jedan napad samo da ilustrira činjenicu koliko se napada na GOST već pojavilo, mnogi od njih. koji su brži, a algebarski napad zahtijeva mnogo manje memorije i otvara praktički neiscrpan prostor mogućnosti da protivnik napadne šifru na različite načine. Ovaj rad također pokazuje da nema potrebe koristiti svojstvo refleksije za hakiranje.

Autor navodi: očito je da GOST ima ozbiljne nedostatke i više ne pruža razinu otpornosti koju zahtijeva ISO. Mnogi napadi na GOST prikazani su kao dio potvrde paradigme redukcije algebarske složenosti.

Na kraju, istraživač posebno ističe neke činjenice koje još nisu dostupne čitatelju, ali su mu poznate, a koje su važne u procesu ISO normizacije. Ovaj napad nije samo "certifikacijski" napad na GOST, koji je brži od grube sile. Zapravo, standardizirati GOST sada bi bilo izuzetno opasno i neodgovorno. To je tako jer su neki od napada izvedivi u praksi. Neki GOST ključevi se čak mogu dešifrirati u praksi, bilo da su slabi ključevi ili ključevi iz određenih stvarnih aplikacija GOST-a. U prethodnom radu autor daje detaljan pregled slučajeva u kojima su praktični napadi mogući. Ono što je također važno jest da je "ovo prvi put u povijesti da je ozbiljna, standardizirana blok šifra, dizajnirana za zaštitu vojnih tajni i dizajnirana za zaštitu vladinih tajni za vlade, velike banke i druge organizacije, probijena matematičkim napadom ."

). 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 samim tim 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 želimo vam u pristupačnom obliku reći 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 stvoriti što jednostavniji sustav, uzimajući u obzir karakteristike određene šifre, tako da proces rješavanja traje što je moguće manje vremena. 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 opravdavanjem 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 svakom krugu, traženi bitovi (tj. bitovi ključa korišteni u zadnjem krugu) nisu brojni kao bitovi u punom ključu i mogu se jednostavno ponoviti 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 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 objavljivanja 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 krugova šifriranja 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 transformacije od 32 kruga GOST 28147-89 podudara se s rezultatom transformacije od 16 krugova, što je ono što autor napada iskorištava. U slučaju DDS metode, to je skup od 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 volumena š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 za konstruiranje jednostavnijih opisa transformacija koje proizvodi 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. ažurirana verzija članka (iz studenog 2011.) pojavila se u elektroničkoj arhivi ePrint međunarodne kriptografske udruge, koja je sadržavala 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 otvorenih tekstova i šifriranih željenim ključem, već i parovima otvorenih i šifriranih tekstova dobivenih korištenjem (također nepoznatih) ključeva koji se razlikuju od željenog. poznatim regularnim putem (na primjer, u fiksnim položajima bitova). U ovom modelu doista je moguće dobiti zanimljive rezultate o GOST 28147-89, ali u ovom modelu moguće je dobiti ništa manje jake rezultate o, na primjer, AES standardu, koji se najviše koristi u modernim javnim mrežama ( 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 koje je certificirao FSB 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 opravdanjem, ali su sadržavali glasne izjave o mogućnosti hakiranja državnog standarda Ruske Federacije na slabom prijenosnom računalu u 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 načelima znanstvenih publikacija, Rudski je upravo da bi nakon rada umirio rusku javnost, 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).

Unatoč prilično opsežnom ciklusu istraživanja u području otpornosti algoritma GOST 28147-89, trenutno nije poznat niti jedan napad za čiju bi se provedbu mogli ostvariti uvjeti uz prateće operativne zahtjeve za blok duljine 64 bita. 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.

Popularno poznati izraz "performanse procesora" je objektivan, izračunati parametar koji se mjeri u flopsima. Međutim, većina ljudi to mjeri u gigahercima, naivno vjerujući da je to ista stvar. Nitko ne poznaje pojam "izvedba koda", a odmah ću objasniti zašto.

Razlog je taj što sam se toga tek nedavno dosjetio i još nikome nisam rekao za to. Međutim, performanse koda, kao i performanse procesora, imaju objektivne karakteristike koje se mogu mjeriti. Ovaj se članak posebno odnosi na izvedbu koda koji izvršava jezgra procesora.

Kako se mjeri izvedba koda? Budući da sam ja prvi govorio o tome, po pravu pronalazača ću to mjeriti u RTT jedinicama;).

Sad ozbiljno. U modernim procesorima glavne transformacije su operacije na 32-bitnim brojevima; sve ostalo je uglavnom egzotično. Stoga ćemo uzeti u obzir glavnu stvar - operacije s 32-bitnim brojevima. Što mislite, koliko 32-bitnih operacija moderna procesorska jezgra može izvesti istovremeno?

Učenik će odgovoriti - jedan, njegov učitelj će pomisliti i reći da su četiri, profesionalac - da je do sada samo dvanaest operacija.

Dakle, programski kod koji učitava sve izvršne jedinice procesora istovremeno tijekom cijelog vremena izvršavanja koda imat će izvedbu od 12 RTT-ova. Maksimum! Da budem iskren, nikada prije nisam napisao takav kod, ali u ovom ću se članku potruditi.

Dokazat ću da je moguć kod s simultanim izvođenjem dvanaest 32-bitnih operacija

Programski kod koji koristi jedan aktuator u jezgri procesora prirodno će imati izvedbu od 1 RTT. Programi koje generiraju prevoditelji jezika visoke razine i interpreteri virtualnih strojeva mogu se pohvaliti takvim performansama koda. Nema potrebe pretpostavljati da pokazatelj opterećenja procesora, koji se može vidjeti u upravitelju zadataka OS-a, može poslužiti kao objektivan kriterij za učinkovitost koda. Opterećenje jezgre procesora može biti 100%, ali će programski kod u sebi koristiti jednu izvršnu jedinicu (izvedba 1 RTT). U ovom slučaju, pri 100% opterećenja, jezgra procesora će raditi na 1/12 svoje maksimalne performanse. Drugim riječima, kada Windows Task Manager prikazuje maksimalno opterećenje procesora, njegova stvarna izvedba može varirati od 1 do 12 RTT. Ako vidite 100% opterećenja bilo koje jezgre procesora u prozoru performansi, pogrešno je pretpostaviti da svi aktuatori rade u ovoj jezgri, uopće ne!

Jedini kriterij za neizravnu procjenu rada jezgre procesora pri maksimalnim performansama može biti njegova potrošnja energije i, kao posljedica toga, buka hladnjaka. Sada, ako je hladnjak bučan, onda da, opterećenje je otišlo na maksimum. Međutim, vrijeme je da završimo s općim konceptima i prijeđemo na oštru praksu.

Tradicionalna provedba GOST 28147-89

Nisam profesionalac u području informacijske sigurnosti, ali sam ipak upoznat s temom enkripcije. Za proučavanje šifriranja simetričnog toka posebno su me inspirirali razgovori s profesionalnim kriptografom kojeg duboko poštujem. I, uzevši ovu temu, pokušao sam to učiniti dobro, i ne samo dobro, već i brzo, izvodeći maksimalan broj operacija u jedinici vremena. Drugim riječima, suočio sam se sa zadatkom da napišem programski kod s maksimalnom RTT vrijednošću.

Kriptografska transformacija u skladu s GOST 28147-89 koristi se za šifriranje toka informacija u komunikacijskim kanalima i na diskovnim pogonima.

Trenutno se naširoko koristi softverska implementacija ovog GOST-a na RON središnjeg procesora. U poznatim metodama implementacije GOST-a, sve tajne informacije (ključevi za šifriranje, zamjenski blokovi) nalaze se u RAM-u. To smanjuje pouzdanost enkripcije, budući da RAM dump može potpuno otkriti sve tajne elemente kripto-transformacije. Osim toga, metoda ima ograničenja izvedbe zbog lokacije glavnih objekata kripto konverzije u OP-u i nepotpunog učitavanja izvršnih jedinica ALU-a. Suvremeni procesori, koji provode kripto postupak koristeći dobro poznatu metodu, mogu osigurati brzine šifriranja od 40-60 megabajta u sekundi. A ako stvarno shvatimo do kraja, razlog slabe izvedbe i slabe sigurnosti kripto konverzije je softverska implementacija supstitucijskog bloka. Za njegov opis u GOST-u, pogledajte Sl. 1.

Prema klauzuli 1.2 GOST-a, ovaj blok implementira permutacije tetrada (četiri bita) u 32-bitnoj riječi, ali arhitektura procesora x86/64 i njegov sustav instrukcija nisu sposobni učinkovito manipulirati tetradama.

Za programsku implementaciju supstitucijskog bloka koriste se posebne tablice u RAM-u, pripremljene u fazi inicijalizacije kriptofunkcije. Ove tablice kombiniraju zamjenske čvorove susjednih tetrada u tablice od 8 × 8-bitnih bajtova, postavljajući tako četiri 256-bajtne tablice u RAM.

U naprednijim implementacijama, ove tablice su veličine 1024 bajta (256 riječi od četiri bajta). To je učinjeno kako bi se u tablicama implementirao dodatni ciklički pomak za 11 pozicija 32-bitne riječi dobivene kao rezultat zamjene (sljedeća operacija algoritma konverzije prema GOST-u). Primjer implementacije GOST-a ovom metodom prikazan je u Dodatku 1 (na disku).

Informacije supstitucijskog bloka su tajna komponenta kriptofunkcije (kako je formulirano u GOST-u, vidi sliku 2).

Postavljanje ovih tablica s ključevima zamjenskih blokova u OP proturječi zahtjevima GOST-a (klauzula 1.7), jer tajne informacije postaju dostupne programima trećih strana koji se pokreću na računalnoj instalaciji. FSB, koji također certificira softverske implementacije enkripcije prema GOST-u, na ovo kršenje gleda, blago rečeno, snishodljivo. Ako za postavljanje ključeva u OP, FSB i dalje zahtijeva "smokvin list" - maskiranje ključeva pomoću operacije XOR, tada ništa nije potrebno za zamjenske blokove u OP; oni su pohranjeni u jasnom obliku.

Ukratko, FSB dopušta prolazak takvih softverskih implementacija kriptoprocedura, unatoč očitom smanjenju sigurnosti takvog rješenja i izravnom kršenju vlastitih zahtjeva prema GOST-u (klauzula 1.7). I to usprkos dobro poznatim metodama razbijanja šifara snimanjem memorijskog dumpa...

Vratit ćemo se na pitanje pohranjivanja ključeva i zamjenskih blokova u internim registrima procesora malo kasnije (postoji lijepo i brzo rješenje), ali za sada ćemo ključeve šifriranja pohranjivati ​​samo u MMX registre, to je pouzdanije.

Ali dosta teksta, ono što je bitno za temu koja se razmatra je da ovaj programski kod ima izvedbu 1 RTT. Sada napišimo kod s performansama 2 RTT-a.

Višenitna implementacija GOST 28147-89

Jedini način da se ubrzaju kripto procedure u poznatom algoritmu je uvođenje multithreadinga. Smisao ove promjene u implementaciji algoritma je paralelno izračunavanje nekoliko blokova podataka.

Većina programera pod paralelnim procesiranjem podrazumijeva isključivo rad više procesorskih jezgri, sinkroniziranih prekidima i semaforima u memoriji.

Međutim, postoji još jedna opcija za paralelnu obradu podataka na jednoj jezgri procesora. Dopustite mi da objasnim ovu neočitu ideju.

Suvremeni procesori uključuju najmanje dvije, pa čak i tri do šest aritmetičko-logičkih jedinica. Ovi ALU-ovi (FPU-ovi, adresne aritmetičke jedinice i tako dalje) mogu raditi neovisno jedan o drugom; jedini uvjet za njihov paralelni rad je da softverski objekti na kojima rade nisu povezani. Drugim riječima, u uputama koje istovremeno izvršavaju ALU, memorijske adrese i brojevi registara moraju biti različiti. Ili, ne bi se trebalo izvoditi pisanje u zajedničke registre i memorijske adrese kojima pristupaju različite izvršne jedinice procesora.

Učitavanje svih ALU-ova kontrolira posebna hardverska jedinica unutar jezgre procesora - planer, koji skenira izvršni kod naprijed, do dubine od 32-64 bajta. Ako planer otkrije instrukcije koje se mogu izvoditi na ALU bez sukoba, tada ih pokreće istovremeno na različitim uređajima za izvršavanje. U ovom slučaju, brojač izvršenih naredbi označava naredbu koja se izvršava (postoji ih nekoliko u takvoj shemi), nakon čega su sve naredbe već izvršene.

Većina programskih sekvenci generiranih automatski (od strane prevoditelja) ne može učitati sve ALU i FPU koji se nalaze u jezgri procesora. U ovom slučaju hardver procesora je u stanju mirovanja, što značajno smanjuje njegove rezultirajuće performanse. Programeri procesora to razumiju i uvode načine za povećanje frekvencije jezgre kada hardver nije u potpunosti iskorišten. Sustavi za hipertrgovinu također su dizajnirani za to, a ja ću koristiti ovaj sustav da maksimalno "pritisnem" kod u budućnosti.

Kompajleri, čak i oni najoptimiziraniji, a još više motori virtualnih strojeva, ne mogu generirati optimizirani kod u smislu performansi. Ovako optimizirani kod može napisati samo programer s inženjerskim znanjem, a alat za pisanje je isključivo asembler.

Tipična ilustracija mogućnosti izvođenja nekoliko nezavisnih programskih niti na jednoj procesorskoj jezgri je GOST implementacija, koja se izvodi u dvije niti na jednoj procesorskoj jezgri. Ideja koda je jednostavna: postoje dva bloka podataka za šifriranje/dekriptiranje, ali jedna procesorska jezgra koja će izvršiti konverziju. Moguće je izvršiti konverziju na ta dva podatkovna bloka sekvencijalno, i to se radi do danas. U tom se slučaju vrijeme potrebno za dovršetak transformacija udvostručuje.

Ali možete to učiniti drugačije: alternativne naredbe povezane s obradom različitih blokova podataka. Ove opcije su grafički prikazane na sl. 3.

Na slici, gornji primjer prikazuje uobičajeni redoslijed obrade dva neovisna bloka podataka. Prvo se obrađuje prvi blok, a zatim procesor nastavlja s obradom drugog bloka. Naravno, dobiveno vrijeme jednako je dvostrukom vremenu potrebnom za obradu jednog bloka, a aktuatori procesorske jezgre nisu potpuno opterećeni.

Slijedi primjer ispreplitanja naredbi iz različitih niti za obradu. U ovom slučaju, naredbe koje se odnose na različite blokove podataka su isprepletene. Planer odabire instrukcije koje su neovisne jedna o drugoj i šalje ih na izvršenje ALU1 i ALU2. Grupiranje naredbi prve i druge niti na tim ALU-ovima provodi se automatski, budući da algoritam rada planera uključuje grupiranje naredbi povezanih sa zajedničkim podacima na istom izvršnom uređaju.

Da bi takav programski kod radio bez zastoja ALU-a, potrebno je da svaka programska nit radi sa svojim skupom registara. Predmemorija u ovoj shemi postaje usko grlo (ima samo dva ulaza za izlaz podataka), pa ključeve spremamo u MMX registre. Budući da se u ovom slučaju čvorovi zamjene (i pomaka) u memoriji samo čitaju, oni mogu biti zajednički za obje programske niti.

Ovo je, naravno, vrlo pojednostavljeno objašnjenje principa paralelnog izvođenja programskih niti na jednoj jezgri; u stvarnosti je sve mnogo kompliciranije. U praksi morate uzeti u obzir cjevovodnu arhitekturu aktuatora, ograničenja istovremenog pristupa predmemoriji i bloku registra RON, prisutnost adresnih aritmetičkih čvorova, prekidača i još mnogo toga... Dakle, ovo je tema za profesionalce, koji se mogu nabrojati na prste... jedne ruke.

Metoda paralelne enkripcije učinkovito se provodi samo za 64-bitni način rada procesora, budući da u ovom načinu rada postoji dovoljan broj RON-a (čak 16 komada!). Primjer implementacije GOST-a ovom metodom prikazan je u Dodatku 2 (na disku).

Jasno je da ova implementacija GOST-a ima izvedbu koda od 2 RTT koda. Sada da vidimo kako to utječe na vrijeme izvršenja.

Ciklus šifriranja za jednu nit (Dodatak 1) iznosi 352 ciklusa takta, a za to vrijeme izračunava se 8 bajtova podataka za dvonitnu implementaciju GOST-a (Dodatak 2) potrebno je 416 procesorskih ciklusa, ali se izračunava 16 bajtova. Tako se rezultirajuća brzina pretvorbe povećava s 80 na 144 megabajta za procesor od 3,6 GHz.

Nastaje zanimljiva slika: kod sadrži točno dvostruko više naredbi, a izvršava se samo 15% dulje, ali mislim da su čitatelji već shvatili razlog ove pojave...

Teoretski, kod iz drugog primjera trebao bi se izvršiti u jednakom broju ciklusa kao i kod iz prvog primjera, no čvor planera razvili su Intelovi inženjeri, ali i oni su ljudi, a svi smo daleko od savršenstva. Tako je moguće procijeniti učinkovitost njihovog stvaranja. Ovaj kod će također raditi na AMD procesoru, a možete usporediti njihove rezultate.

Ako mi netko ne vjeruje na riječ, onda su za takve nevjernike na disku uključeni programi za testiranje s brojačima sati. Programi su u izvornom kodu, naravno u asembleru, tako da postoji mogućnost provjere mojih riječi, a ujedno i uvid u neke od trikova profesionalnog kodiranja.

Korištenje SSE registara i AVX naredbi modernih procesora za implementaciju GOST 28147-89

Moderni procesori x86/64 arhitekture uključuju skup SSE registara veličine 16 bajtova i specijalizirane FPU-ove (najmanje dva) za izvođenje različitih operacija na tim registrima. Moguće je implementirati GOST na ovu opremu, au ovom slučaju zamjenski čvorovi mogu se postaviti ne u obliku tablica u RAM-u, već izravno na namjenske SSE registre.

Jedan SSE registar može smjestiti dvije tablice od 16 redaka odjednom. Tako će četiri SSE registra u potpunosti primiti sve zamjenske tablice. Jedini uvjet za takvo postavljanje je zahtjev za isprepletanjem, prema kojem se tetradi istog bajta moraju smjestiti u različite SSE registre. Dodatno, preporučljivo je nisku i visoku tetradu ulaznih bajtova smjestiti u nisku i visoku tetradu bajtova SSE registara.

Ovi zahtjevi su određeni optimizacijom za postojeći skup AVX naredbi. Stoga će svaki bajt SSE registra sadržavati dvije tetrade koje odgovaraju različitim bajtovima ulaznog registra supstitucijskog bloka, dok položaj bajta u SSE registru jedinstveno odgovara indeksu u supstitucijskoj tablici supstitucijskog bloka.

Dijagram jednog od mogućih smještaja zamjenskih čvorova na SSE registrima prikazan je na sl. 4.

Postavljanje tajnih informacija zamjenskih čvorova na SSE registre povećava sigurnost kripto procedure, ali potpuna izolacija tih tajnih informacija moguća je ako su ispunjeni sljedeći uvjeti:

• Jezgra procesora se prebacuje u način rada hosta hipervizora, a blok prekida (APIC) je u njemu prisilno onemogućen. U tom je slučaju jezgra procesora potpuno izolirana od OS-a i aplikacija koje se izvode na računalnoj instalaciji.
• SSE registri se učitavaju i računalna jezgra se izolira prije pokretanja OS-a; optimalno je izvršiti ove postupke iz pouzdanog modula za pokretanje (TLM).
• Programi za kriptoprocedure u skladu s GOST-om nalaze se u neizmjenjivom memorijskom području računalne instalacije (bilo u BIOS-u ili u flash memoriji MDZ-a).

Usklađenost s ovim zahtjevima osigurat će potpunu izolaciju i nepromjenjivost programskog koda kriptoprocedura i tajnih informacija koje se u njima koriste.

Za učinkovito uzorkovanje tetradnih SSE registara koriste se višeulazni bajtni prekidači uključeni u FPU blokove. Ovi prekidači omogućuju prijenose iz bilo kojeg izvornog bajta u bilo koji odredišni bajt, koristeći indekse koji se nalaze u posebnom registru SSE indeksa. Štoviše, prijenos se izvodi paralelno za svih 16 bajtova SSE prijemnog registra.

Imajući zamjenske čvorove za pohranu na SSE registrima i sklopku s više ulaza u FPU blokovima, moguće je organizirati sljedeću transformaciju u zamjenskom bloku (slika 5).

U ovoj shemi, ulazni registar u svakoj tetradi specificira adresu za odgovarajuću sklopku, koja prenosi informacije od pogona zamjenskih čvorova do izlaznog registra preko sabirnice podataka. Ova se shema može organizirati na tri načina:

• Napravite odgovarajući dizajn čipa, ali ovo je za nas fantastično.
• Reprogramiranje mikrokoda i kreiranje vlastite procesorske naredbe za implementaciju ove funkcije na postojeće procesore više nije fantazija, ali je, nažalost, u sadašnjim uvjetima nerealno.
• Napišite program koristeći službene AVX naredbe. Opcija možda nije vrlo učinkovita, ali se može implementirati "ovdje i sada". To je ono što ćemo sljedeće učiniti.

Radom prekidača upravlja se posebnom troadresnom naredbom AVX VPSHUFB. Njegov prvi operand je primatelj informacija od prekidača, drugi je izvor na koji su spojeni ulazi prekidača. Treći operand je kontrolni registar za prekidače, čiji je svaki bajt pridružen odgovarajućem prekidaču; vrijednost u njemu specificira broj smjera iz kojeg prekidač čita informacije. Za opis ove naredbe iz službene Intelove dokumentacije pogledajte sl. 5. Na sl. Slika 6 prikazuje dijagram rada ove naredbe - prikazana je samo polovica SSE registara, za drugu polovicu sve je slično.

Prekidač koristi samo najniža četiri bita za određivanje smjera komutacije, zadnji bit u svakom bajtu se koristi za prisiljavanje odgovarajućeg prijamnog bajta na nulu, ali ova funkcija preklopnika još nije tražena u našem slučaju.

Napisan je program za uzorkovanje tetrada kroz FPU prekidače, ali ga nisam ni stavio u aplikaciju - previše je jadno. Imati 128-bitni registar i koristiti samo 32 bita u njemu je neprofesionalno.

Kao što kažu, "Naša ciljna linija je horizont", pa cijedite, cijedite ... mi ćemo ga stisnuti i staviti u vreće!

Ovo nije igra riječi, već surova FPU realnost - SSE registri se mogu podijeliti na jednake dijelove i na tim dijelovima jednom naredbom izvršiti iste transformacije. Da bi procesor ovo razumio, postoji čarobno slovo “P” - paket koji se nalazi ispred mnemotehnike naredbe, i ne manje čarobna slova “Q”, “D”, “W”, “B”, koja stavljaju se na kraj i deklariraju Na koje su dijelove podijeljeni SSE registri u ovoj naredbi?

Zanima nas batch mod sa SSE registrom podijeljenim u četiri 32-bitna bloka; prema tome, sve naredbe će imati prefiks “P” i na kraju simbol “D”. To omogućuje paralelnu obradu četiri 32-bitna bloka jednom procesorskom naredbom, odnosno paralelno izračunavanje četiri bloka podataka.

Program koji implementira ovu metodu dostupan je u Dodatku 3, sa svim objašnjenjima.

Međutim, pritisnite toliko! Moderni procesori imaju najmanje dva FPU-a, a dvije neovisne niti instrukcija mogu se koristiti za njihovo potpuno učitavanje. Ako ispravno mijenjate naredbe iz neovisnih niti, možete u potpunosti učitati oba FPU bloka i dobiti osam paralelno obrađenih tokova podataka odjednom. Takav program je napisan i može se pogledati u Prilogu 4, ali ga morate pažljivo gledati - možete poludjeti. To je ono što se zove “šifra nije za svakoga...”.

Cijena izdanja

Upotreba SSE registara za pohranjivanje zamjenskih čvorova je razumljiva - pruža određeno jamstvo izolacije tajnih informacija, ali značenje izračuna same kriptofunkcije na FPU nije očito. Stoga je vrijeme izvršenja standardnih postupaka mjereno metodom izravne zamjene u skladu s GOST-om za četiri i osam niti.

Za četiri niti dobivena je brzina izvršenja od 472 procesorska ciklusa. Dakle, za procesor s frekvencijom od 3,6 GHz, jedna nit se računa brzinom od 59 megabajta u sekundi, a četiri niti, odnosno, brzinom od 236 megabajta u sekundi.

Za osam niti dobivena je brzina izvršavanja od 580 procesorskih ciklusa. Dakle, za procesor od 3,6 GHz, jedna nit broji 49 megabajta u sekundi, a osam niti 392 megabajta u sekundi.

Kao što čitatelj može vidjeti, kod u primjeru #3 ima izvedbu od 4 RTT, a kod u primjeru #4 ima izvedbu od 8 RTT. U ovim primjerima na SSE registrima obrasci su isti kao kod korištenja RON-a, samo je planer smanjio svoju učinkovitost. Trenutno pruža 20% povećanje trajanja uz udvostručenje duljine koda.

Štoviše, ovi su rezultati dobiveni korištenjem univerzalnih AVX naredbi dostupnih u Intelovim i AMD procesorima. Ako optimizirate za AMD procesor, rezultat će biti puno bolji. Zvuči suprotno od trenda, ali ipak je istina, a evo i zašto: AMD procesori imaju dodatni set instrukcija, tzv. XOP ekstenziju, au tom dodatnom setu instrukcija nalaze se one koje značajno pojednostavljuju implementaciju GOST algoritam.

Ovo se odnosi na naredbe za logički burst pomak bajtova i burst ciklički pomak dvostrukih riječi. U primjerima danim u Dodacima 3 i 4 koriste se sekvence univerzalnih naredbi koje provode potrebnu transformaciju: u prvom slučaju jedna “ekstra” naredba, au drugom slučaju četiri dodatne naredbe odjednom. Dakle, optimizacijske rezerve postoje, i to znatne.

Što se tiče daljnje optimizacije, vrijedi zapamtiti prisutnost 256-bitnih registara (YMM registara), pomoću kojih možete teoretski udvostručiti brzinu izračuna. Ali za sada je to samo izgled; procesori jako usporavaju kada izvršavaju 256-bitne instrukcije (FPU-ovi imaju širinu putanje od 128 bita). Eksperimenti su pokazali da na modernim procesorima brojanje 16 niti na YMM registrima ne daje nikakvu korist. Ali to je samo za sada; performanse 256-bitnih instrukcija će nedvojbeno biti povećane, a zatim će upotreba 16 paralelnih niti postati preporučljiva i dovest će do još većeg povećanja brzine kripto procedure. .

Teoretski, možete računati na brzinu od 600–700 megabajta u sekundi ako procesor ima dva FPU-a sa širinom radnog puta od 256 bita svaki. U ovom slučaju možemo govoriti o pisanju koda s učinkovitošću od 16 RTT, a to nije fantazija, već bliska budućnost.

Mješoviti način rada

Opet se postavlja pitanje broja registara; nema ih dovoljno za promicanje takvog algoritma. Ali način hipertrgovanja će nam pomoći. Jezgra procesora ima drugi skup registara dostupnih u načinu rada logičkog procesora. Stoga ćemo izvršiti isti kod na dva logička procesora odjednom. U ovom načinu rada, naravno, nećemo imati više aktuatora, ali zbog alternacije možemo dobiti puno opterećenje svih aktuatora.

Ovdje ne možete računati na povećanje od 50%; usko grlo je predmemorija u kojoj su pohranjene tehnološke maske, ali još uvijek možete dobiti povećanje od 100 dodatnih megabajta. Ova opcija nije prikazana u dodacima (makronaredbe su slične onima koje se koriste u 8 RTT kodu), ali je dostupna u programskim datotekama. Pa ako netko ne vjeruje u mogućnost enkripcije pri brzini od 500 megabajta u sekundi na jednoj procesorskoj jezgri, neka pusti testne datoteke. Tu su i tekstovi s komentarima da netko ne pomisli da lažem.

Ovaj fokus je moguć samo na Intelovim procesorima; AMD ima samo dvije FPU jedinice po dva procesorska modula (analogno načinu hipertrgovine). Ali postoje još četiri ALU koje bi bilo grijeh ne koristiti.

Module procesora Bulldozer možete staviti u način rada sličan načinu hipertrgovanja, ali pokrenite konverziju u RON na različitim modulima u jednoj niti, a na SSE registrima u drugoj niti i dobijete istih 12 RTT-ova. Nisam testirao ovu opciju, ali mislim da će 12 RTT kod raditi učinkovitije na AMD-u. Zainteresirani mogu isprobati; programi za testiranje mogu se vrlo lako prilagoditi za rad na "Buldožerima".

Kome to treba?

Ozbiljno pitanje, ali s jednostavnim odgovorom - ovo treba svima. Uskoro ćemo svi biti zakačeni za oblake, tamo ćemo čuvati i podatke i programe, a tamo, oh, kako želimo stvoriti svoj, privatni kutak. Da biste to učinili, morat ćete šifrirati promet, a brzina kripto konverzije bit će glavni odlučujući čimbenik udobnog rada u oblaku. Naš izbor algoritama šifriranja je mali - ili GOST ili AES.

Štoviše, začudo, algoritam AES enkripcije ugrađen u procesore pokazao se puno sporijim; testovi pokazuju brzine od 100–150 megabajta u sekundi, a to je uz hardversku implementaciju algoritma! Problem leži u jednonitnom brojanju i zamjenskom bloku koji radi na bajtovima (tablica od 256 redaka). Dakle, GOST se pokazao učinkovitijim kada se implementira na x86/64 arhitekturu, tko bi rekao...

To je ako govorimo o postignutoj razini brzine enkripcije. A ako imamo na umu teorijska usavršavanja u području povećanja učinkovitosti koda, onda to najvjerojatnije nikome ne treba. Praktično nema stručnjaka na razini 3–6 RTT, prevoditelji općenito generiraju kod na razini 1–2.5 RTT, a većina programera ne poznaje asembler, a čak i ako znaju njegov pravopis, ne razumiju dizajn moderan procesor. A bez ovog znanja, nije važno radi li se o asembleru ili kakvom SI-sharpu.

Ali nije sve tako tužno: krajnji rezultat nakon tjedan dana besanih noći je novi algoritam za implementaciju GOST-a, koji bi bio grijeh ne patentirati. A prijave za patente (ukupno tri) već su završene i predane, pa gospodo poslovni ljudi u red - žene i djeca imaju popust.

Povijest ove šifre mnogo je starija. Algoritam, koji je kasnije formirao temelj standarda, rođen je, vjerojatno, u utrobi Osme glavne uprave KGB-a SSSR-a (sada unutar strukture FSB-a), najvjerojatnije, u jednom od zatvorenih istraživanja njemu podređenih instituta, vjerojatno još 1970-ih u sklopu projekata stvaranja softverskih i hardverskih implementacija šifre za različite računalne platforme.

Od objavljivanja GOST-a, označen je restriktivnim žigom "Za službenu upotrebu", a formalno je šifra proglašena "potpuno otvorenom" tek u svibnju 1994. Povijest stvaranja šifre i kriteriji programera nisu objavljeni od 2010.

Opis

GOST 28147-89 je blok šifra s 256-bitnim ključem i 32 ciklusa pretvorbe, koja radi na 64-bitnim blokovima. Osnova algoritma za šifriranje je Feistelova mreža. Postoje četiri načina rada prema GOST 28147-89:

• simulirani način umetanja.

Jednostavan način zamjene

Za šifriranje u ovom načinu rada, otvoreni tekst se prvo dijeli na dvije polovice (najmanji bitovi su A, najvažniji bitovi su B). U i-tom ciklusu koristi se podključ K i:

( = binarno "isključivo ili")

Za generiranje podključeva, originalni 256-bitni ključ je podijeljen u osam 32-bitnih blokova: K 1 ... K 8 .

Ključevi K 9 ... K 24 su cikličko ponavljanje ključeva K 1 ... K 8 (numerirani od najmanjeg do najvišeg bita). Tipke K 25...K 32 su tipke K 8...K 1.

Nakon završetka sva 32 kruga algoritma, blokovi A 33 i B 33 su zalijepljeni zajedno (imajte na umu da najvažniji bit postaje A 33, a najmanje značajan bit postaje B 33) - rezultat je rezultat algoritma.

Dešifriranje se izvodi na isti način kao i šifriranje, ali je redoslijed podključeva K i obrnut.

Funkcija izračunava se na sljedeći način:

A i i K i se zbrajaju po modulu 2 32.

Rezultat je podijeljen u osam 4-bitnih podsekvenci, od kojih je svaka unesena u svoju vlastitu čvor zamjenske tablice(u rastućem redoslijedu prvenstva bita), koji se naziva u nastavku S-blok. Ukupan broj GOST S-blokova je osam, odnosno isti broj kao i podsekvenci. Svaki S-blok je permutacija brojeva od 0 do 15. Prvi 4-bitni podniz ide na ulaz prvog S-kutija, drugi - na ulaz drugog itd.

Ako S-blok izgleda ovako:

1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12

a ulaz S-bloka je 0, tada će izlaz biti 1, ako je 4, tada će izlaz biti 5, ako je ulaz 12, tada će izlaz biti 6, itd.

Izlazi svih osam S-kutija se kombiniraju u 32-bitnu riječ, zatim se cijela riječ ciklički pomiče ulijevo (prema najvažnijim bitovima) za 11 bita.

Način jednostavne zamjene ima sljedeće nedostatke:

• Može se koristiti samo za šifriranje otvorenih tekstova duljine koja je višekratnik 64 bita
• Šifriranjem identičnih blokova otvorenog teksta dobivaju se identični blokovi šifriranog teksta koji mogu pružiti određene informacije kriptoanalitičaru.

U tekstu norme stoji da se isporuka zamjenskih čvorova punjenja (S-kutija) vrši na propisani način, odnosno od strane izrađivača algoritma. Zajednica ruskih CIPF programera složila se oko zamjenskih čvorova koji se koriste na Internetu, pogledajte RFC 4357.

Prednosti GOST-a

• uzaludnost napada silom (XSL napadi nisu uzeti u obzir, budući da njihova učinkovitost još nije u potpunosti dokazana);
• učinkovitu implementaciju i, sukladno tome, visoke performanse na modernim računalima.
• prisutnost zaštite od nametanja lažnih podataka (razvoj imitativnog umetanja) i isti ciklus šifriranja u sva četiri GOST algoritma.

Kriptoanaliza

Vjeruje se (vidi, na primjer, Vitaly V. Shorin, Vadim V. Jelezniakov i Ernst M. Gabidulin: Linearna i diferencijalna kriptoanaliza ruskog GOST-a) da je GOST otporan na tako široko korištene metode kao što su linearna i diferencijalna kriptoanaliza. Obrnuti redoslijed tipki u zadnjih osam rundi pruža zaštitu od napada klizanjem i refleksijom.

U svibnju 2011. poznati kriptoanalitičar Nicolas Courtois dokazao je postojanje napada na ovu šifru koja ima složenost 2 8 (256) puta manju od složenosti izravne pretrage ključeva, pod uvjetom da postoji 2 64 para otvoreni tekst/otvoreni tekst. Ovaj napad nije moguće izvesti u praksi zbog svoje prevelike računalne složenosti. Štoviše, poznavanje 2 64 para otvoreni tekst/privatni tekst vam očito omogućuje čitanje šifriranih tekstova čak i bez izračunavanja ključa. Većina drugih radova također opisuje napade koji su primjenjivi samo pod određenim pretpostavkama, kao što su određena vrsta ključeva ili zamjenskih tablica, neke izmjene izvornog algoritma ili koji zahtijevaju još uvijek nedostižne količine memorije ili računanja. Ostaje otvoreno pitanje postoje li praktični napadi bez iskorištavanja slabosti pojedinačnih ključeva ili zamjenskih tablica.

Kritika GOST-a

Glavni problemi GOST-a povezani su s nepotpunošću standarda u smislu generiranja ključeva i zamjenskih tablica. Vjeruje se da GOST ima "slabe" ključeve i zamjenske tablice, ali standard ne opisuje kriterije za odabir i uklanjanje "slabih". Također, norma ne navodi algoritam za generiranje supstitucijske tablice (S-kutije). S jedne strane, to može biti dodatna tajna informacija (pored ključa), as druge strane, postavlja niz problema:

• nemoguće je odrediti kriptografsku snagu algoritma bez prethodnog poznavanja supstitucijske tablice;
• implementacije algoritama različitih proizvođača mogu koristiti različite zamjenske tablice i mogu biti nekompatibilne jedna s drugom;
• mogućnost namjernog pružanja slabih zamjenskih tablica od strane tijela za izdavanje dozvola Ruske Federacije;
• potencijal (nema zabrane u standardu) korištenja supstitucijskih tablica u kojima čvorovi nisu permutacije, što može dovesti do ekstremnog smanjenja snage šifre.

U listopadu 2010., na sastanku 1. zajedničkog tehničkog odbora Međunarodne organizacije za standardizaciju (ISO/IEC JTC 1/SC 27), GOST je nominiran za uključivanje u međunarodnu normu za blokovsko šifriranje ISO/IEC 18033-3. S tim u vezi, u siječnju 2011. godine formirani su fiksni skupovi zamjenskih čvorova i analizirana su njihova kriptografska svojstva. Međutim, GOST nije usvojen kao standard, a odgovarajuće zamjenske tablice nisu objavljene

Moguće primjene

Bilješke

vidi također

Linkovi

• GOST 28147-89 „Sustavi za obradu informacija. Kriptografska zaštita. Algoritam kriptografske pretvorbe"
• Sergej Panasenko Standard šifriranja GOST 28147-89 (ruski) (15. kolovoza 2007.). Preuzeto 3. kolovoza 2012.

• . - kriptografski projekt tvrtke Cryptocom LLC za dodavanje ruskih kriptografskih algoritama u OpenSSL biblioteku. Arhivirano iz originala 24. kolovoza 2011. Preuzeto 16. studenog 2008.

Književnost

• Melnikov V.V. Zaštita informacija u računalnim sustavima. - M.: Financije i statistika, 1997.
• Romanets Yu V., Timofeev P. A., Shangin V. F. Zaštita informacija u računalnim sustavima i mrežama. - M.: Radio i komunikacije, 1999.
• Kharin Yu S., Bernik V. I., Matveev G. V. Matematičke osnove kriptologije. - Mn. : BSU, 1999.
• Gerasimenko V. A., Malyuk A. A. Osnove informacijske sigurnosti. - M.: MGIFI, 1997.
• Leonov A. P., Leonov K. P., Frolov G. V. Sigurnost automatiziranih bankarskih i uredskih tehnologija. - Mn. : Nacionalni knjiga Komora Bjelorusije, 1996.
• Winter V. M.. Moldovyan A. A., Moldovyan N. A. Računalne mreže i zaštita prenesenih informacija. - St. Petersburg. : Državno sveučilište St. Petersburg, 1998.
• Schneier B. 14.1 Algoritam GOST 28147-89 // Primijenjena kriptografija. Protokoli, algoritmi, izvorni tekstovi u jeziku C = Primijenjena kriptografija. Protokoli, algoritmi i izvorni kod u C. - M.: Triumph, 2002. - str. 373-377. - 816 str. - 3000 primjeraka. - ISBN 5-89392-055-4
• Popov, V., Kurepkin, I. i S. Leontjev Dodatni kriptografski algoritmi za upotrebu s algoritmima GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001 i GOST R 34.11-94 (engleski) // RFC 4357. - IETF, siječanj 2006.

Zaklada Wikimedia. 2010.