Algoritam šifriranja GOST 28147-89. Jednostavna metoda zamjene. - Arhiva WASM.RU

“Dok si živ, ne umri, pogledaj ovaj svijet.
Mnogi ovdje imaju mrtvu dušu - mrtvi su iznutra.
Ali hodaju i smiju se, ne znajući da nisu,
Ne žuri sa svojim smrtnim časom”, rekla mi je.

Aria, "Visoko tamo"

2.1 Feistelove mreže.
2.2 Blok šifra GOST 28147-89

3.1 Ključne informacije
3.2 Glavni korak kripto transformacije

3.3 Osnovne petlje:“ 32-Z” , “ 32-R” .

4.1 Implementacija glavnog koraka kripto transformacije
4.2 Povećanje brzine algoritma
5. Zahtjevi za ključne informacije
6. Spisak korišćene literature
7. Priznanja.

Uvod.

Ovaj dokument je moj pokušaj da opišem metodu za jednostavnu zamjenu algoritma šifriranja GOST 28147-89 najjednostavnijim, ali ipak tehnički kompetentnim jezikom. Nakon što pročita prvih šest tačaka, čitalac će dati svoje mišljenje o tome kako sam to uradio.

Kako bi moj rad imao više koristi, preporučujem da se naoružate radovima autora navedenih u spisku korišćene literature. Također se preporučuje da kalkulator ima funkciju za izračunavanje operacije. XOR pošto čitanje članka pretpostavlja da je čitatelj namjeravao proučiti ovaj algoritam šifriranja. Iako je pogodan i kao referenca, ovaj članak sam napisao upravo kao trening.

Preliminarne informacije o blok šiframa.

Prije nego počnemo gledati algoritam, moramo se upoznati s istorijom stvaranja ove vrste šifri. Algoritam spada u kategoriju blok šifri, u čijoj arhitekturi su informacije podijeljene na konačan broj blokova, a posljednji naravno ne može biti potpun. Proces šifriranja se odvija preko kompletnih blokova koji formiraju šifru. Završni blok, ako je nepotpun, dopunjen je nečim (u nastavku ću reći o nijansama njegovog dovršavanja) i šifriran je na isti način kao i puni blokovi. Pod šifrom mislim na rezultat funkcije enkripcije koja djeluje na određenu količinu podataka koje je korisnik predao na šifriranje. Drugim riječima, šifra je krajnji rezultat enkripcije.

Povijest razvoja blok šifri vezana je za rane 70-te godine, kada je IBM, uvidjevši potrebu za zaštitom informacija pri prijenosu podataka putem računalnih komunikacijskih kanala, počeo provoditi vlastiti istraživački program posvećen zaštiti informacija u elektronskim mrežama, uključujući kriptografiju.

Grupu istraživača - programera kompanije IBM, koja je počela proučavati sisteme šifriranja sa simetričnom šemom korištenja ključa, predvodio je dr. Horst Feistel.

2.1 Feistelove mreže

Arhitektura nove metode šifriranja koju je Feistel predložio u klasičnoj literaturi naziva se "Feistelova arhitektura", ali se trenutno u ruskoj i stranoj literaturi koristi ustaljeniji termin - "Feistelova mreža" ili Feistelova mreža. Naknadno je na ovoj arhitekturi izgrađena šifra "Lucifer" - koja je kasnije objavljena i izazvala je novi talas interesovanja za kriptografiju uopšte.

Ideja arhitekture "Feistelove mreže" je sljedeća: ulazni tok informacija podijeljen je na blokove veličine n bitova, gdje je n paran broj. Svaki blok je podijeljen na dva dijela - L i R, zatim se ovi dijelovi unose u iterativni blok šifru, u kojoj je rezultat j-te faze određen rezultatom prethodne faze j-1! To se može ilustrirati primjerom:

Rice. 1

Gdje je funkcija A glavna radnja blok šifre. To može biti jednostavna akcija, kao što je operacija XOR, ili može imati složeniji oblik kao niz niza jednostavnih radnji - modulo zbrajanje, pomak ulijevo, zamjena elementa, itd., uzeti zajedno, ove jednostavne akcije formiraju tzv - glavni korak kripto transformacije.

Treba napomenuti da su ključni elementi operacije funkcije nabavka ključnih elemenata i XOR operacija, a po tome koliko je dobro osmišljen rad ovih operacija, govori o kriptografskoj snazi ​​šifre u cjelini.

Kako bi ideja Feistelove mreže bila konačno jasna, razmotrite najjednostavniji slučaj prikazan u pirinač. 1, gdje će u funkciji A - postojati operacije “mod 2” (“xor”), ali ovo najjednostavniji u slučaju, u ozbiljnijoj situaciji, na primjer, skrivanje informacija od nacionalnog značaja, funkcija A može biti složenija (koliko sam vidio, funkcija A je zaista vrlo složena):

Početni podaci:

L = 1110b, R = 0101, K = 1111b

Uzmi šifru

1. (R + K) mod 2 4 = Smod, Smod = 0100b

2. (Smod + L) mod 2 = Sxor, Sxor = 1010b

3. L = R, R = Sxor

L = 0101b, R = 1010b

Objasnimo naše postupke:

1. Ova operacija je dodatak modu 2 4. U praksi se ova operacija svodi na jednostavno sabiranje, gdje moramo sabrati dva broja i zanemariti prijenos na 5. znamenku. Budući da ako stavimo eksponente iznad cifara binarnog prikaza broja, biće eksponent četiri iznad pete znamenke, pogledajmo sliku ispod, koja pokazuje radnje naše operacije:

Rice. 2

Ovdje sam strelicom pokazao na eksponente, kao što vidite, rezultat je trebao biti 10100, ali pošto je prijenos zanemaren tokom mod 2 4 operacije, dobijamo 0100.

2. Ova operacija se u literaturi naziva mod 2, na asemblerskom jeziku implementira se naredbom XOR... Ali njegov tačniji naziv je mod 2 1. Bez ove jedinstvene operacije, teško da je moguće izgraditi brz, lako implementivi algoritam šifriranja, a da u isto vrijeme i dalje bude prilično kriptografski jak. Jedinstvenost ove operacije leži u činjenici da je ona sama suprotna! Na primjer, ako je broj A XOR sa brojem B, kao rezultat ćemo dobiti B, u budućnosti je dovoljno da ponovo XOR brojeve B i C jedan drugog da dobijemo prethodnu vrijednost A!

U ovoj operaciji dobili smo 1010 sa brojevima 1110 i 0100, da bismo dobili natrag 1110, dovoljno je preko XOR brojeva 0100 i 1010! Više detalja o ovoj operaciji možete pronaći u članku koji je priložen uz stranicu. www.wasm.ru, « Elementarni vodič zaCRC_ algoritmi za detekciju grešaka»Autor koji Ross N. Williams... U ovom radu postoji poenta - “ 5. Binarna aritmetika bez crtica". Operacija je opisana u ovom članku. xor! Uzvikujem jer je u ovom članku ova operacija tako zakazana da čitatelj ne samo da razumije kako ova operacija funkcionira, već je čak i pokreće vidi, cuj i oseti!

3. Ova radnja je neophodna kako bi se tokom dešifriranja mogle dobiti početne vrijednosti iz šifre.

2.2 Blok šifra GOST 28147-89

Algoritam šifriranja GOST 28147 - 89 pripada kategoriji blok šifri koje rade prema arhitekturi uravnoteženih Feistelovih mreža, gdje su dva dijela odabranog bloka informacija jednake veličine. Algoritam je razvijen u dubinama osmog odjela KGB-a, sada transformiran u FAPSI i uvršten je kao standard za šifriranje Ruske Federacije još 1989. godine pod SSSR-om.

Da bi ova metoda algoritma funkcionirala, potrebno je podijeliti informacije u blokove veličine 64 bita. Generirajte ili unesite u sistem šifriranja sljedeće ključne informacije: ključ i tablicu zamjene. Izbor ključa i tablice zamjene za šifriranje treba shvatiti vrlo ozbiljno, jer ovo je temelj sigurnosti vaših informacija. Za informacije o tome koji su zahtjevi nametnuti ključu i tabeli zamjena, pogledajte stavku "Zahtjevi za ključne informacije".

Kada razmatramo metodu, nećemo se fokusirati na ovo, jer Ovaj članak, kao što sam već rekao, napisan je s ciljem da čitatelja nauči kako šifrirati podatke metodom jednostavne zamjene ovog algoritma šifriranja, ali ćemo se na ovo pitanje svakako dotaknuti na kraju članka.

Teoretski minimum.

3.1 Ključne informacije

Kao što sam već rekao, sljedeće su aktivno uključene u enkripciju podataka:

3.1.1. Ključ je niz od osam elemenata, svaki od 32 bita. U nastavku ćemo označavati simbolom K, a elementi od kojih se sastoji su k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Tabela zamjene - matrica od osam redova i šesnaest kolona, ​​u daljem tekstu - Hij. Svaki element na preseku reda i i kolone j zauzima 4 bita.

3.2 Osnovni korak kripto transformacije

Glavni korak u procesu enkripcije je - glavni korak kripto transformacije. Ovo nije ništa drugo nego akcija šifriranja podataka prema određenom algoritmu, samo su programeri uveli preglomazno ime.

Prije početka šifriranja, blok se dijeli na dva dijela L i R, svaki po 32 bita. Ključni element je odabran i tek tada se ova dva dijela bloka, ključni element, tabela zamjene, unose u funkciju glavnog koraka, rezultat glavnog koraka je jedna iteracija osnovnog ciklusa, o čemu će biti riječi u sledeći paragraf. Glavni korak se sastoji od sljedećeg:

1. Dodatni dio bloka R se sabira sa ključnim elementom K mod 2 32. Sličnu operaciju sam opisao gore, ovdje je ista stvar samo što eksponent nije "4", već "32" - rezultat ove operacije će u budućnosti biti označen kao Smod.
2. Podijelite prethodno dobiveni rezultat Smod na četverobitne elemente s7, s6, s5, s4, s3, s2, s1, s0 i unesite ga u funkciju zamjene. Zamjena je sljedeća: odabire se element Smod - si, počinjemo ispočetka s najnižim elementom i zamjenjujemo vrijednošću iz tablice zamjena sa i - redom i stupcem na koje ukazuje vrijednost elementa s i. Prelazimo na s i +1 element i nastavljamo na isti način i tako nastavljamo dok ne promijenimo vrijednost posljednjeg elementa Smod - rezultat ove operacije će biti označen kao, Ssimple.
3. U ovoj operaciji pomičemo Ssimple vrijednost ciklički ulijevo za 11 bita i dobijamo Srol.
4. Odaberemo drugi dio L bloka i dodamo ga mod 2 sa Srol, kao rezultat imamo Sxor.
5. U ovoj fazi, dio L bloka postaje jednak vrijednosti R dijela, a R dio se, zauzvrat, inicijalizira rezultatom Sxor, i time je funkcija glavnog koraka završena!

3.3 Osnovni ciklusi: "32-Z", "32-R".

Da biste šifrirali informacije, morate ih podijeliti na blokove veličine 64 bita, naravno posljednji blok može biti manji od 64 bita. Ova činjenica je Ahilova peta ove metode "lake zamjene". Budući da je njegovo dodavanje na 64 bita vrlo važan zadatak za povećanje kriptografske snage šifriranog koda i na ovom osjetljivom mjestu, ako je prisutan u nizu informacija, a možda i ne postoji (na primjer, datoteka od 512 bajtova! ), Treba se odnositi sa velikom odgovornošću!

Nakon što ste podijelili informacije u blokove, trebali biste podijeliti ključ na elemente:

K = k1, k2, k3, k4, k5, k6, k7, k8

Sama enkripcija se sastoji u korištenju takozvanih osnovnih ciklusa. Što, pak, uključuje n-ti broj osnovnih koraka kripto-transformacije.

Osnovni ciklusi su označeni, kako se to kaže: n - m. Gdje je n broj osnovnih koraka kripto-transformacije u osnovnom ciklusu, a m "tip" osnovnog ciklusa, tj. o čemu pričamo, o "Z" enkripciji ili "R" enkripciji podataka.

Osnovni ciklus šifrovanja 32-Z sastoji se od 32 osnovna koraka kripto-transformacije. Blok N i element ključa K se unose u funkciju koja implementira akcije koraka, a prvi korak se javlja sa k1, drugi preko rezultata dobijenog elementom k2 itd. prema sljedećoj shemi:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

Proces dešifriranja za 32-P odvija se na sličan način, ali su ključni elementi dati obrnutim redoslijedom:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Vježbajte.

4.1 Implementacija glavnog koraka kripto transformacije

Nakon što smo se upoznali sa teorijom šifriranja informacija, došlo je vrijeme da vidimo kako se šifriranje odvija u praksi.

Početni podaci:

Uzmite blok informacija N = 0102030405060708h, ovdje su dijelovi L i R jednaki:

L = 01020304h, R = 05060708h, uzmimo ključ:

K = as28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(ovo su ASCII kodovi, da biste vidjeli heksadecimalni prikaz, možete otvoriti ovu datoteku u načinu prikaza u Total Commanderu pritiskom na tipku F3"A onda ključ" 3 "). U ovom ključu vrijednosti elemenata će biti:

k1 = ‘as28’, k2 = ‘zw37’, k3 = ‘q839’, k4 = ‘7342’

k5 = 'ui23', k6 = '8e2t', k7 = 'wqm2', k8 = 'ewp1'

Uzmite i sljedeću tablicu zamjene:

Rice. 3

Ovdje su redovi numerirani od 0 do 7, kolone od 0 do F.

upozorenje: Sve informacije, uključujući ključ sa tablicom zamjene, uzimaju se kao primjer za razmatranje algoritma!

Koristeći "Početne podatke", potrebno je dobiti rezultat akcije glavnog koraka kripto transformacije.

1. Odaberite dio R = 05060708h i ključni element k1 = 'as28', u heksadecimalnom obliku ključni element će izgledati ovako: 61733238h. Sada radimo operaciju sumiranja mod 2 32:

Rice. 4

Kao što možete vidjeti na slici, nismo imali prijenos u 33 bita označena crvenom bojom i sa eksponentom “ 32 ". A da smo imali druge vrijednosti R i ključnog elementa, ovo bi se moglo dogoditi, a onda bismo to zanemarili i dalje koristili samo bitove označene žutom bojom.

Ovu operaciju izvodim sa komandom asemblera dodati:

; eax = R, ebx = 'as28'

Rezultat ove operacije Smod = 66793940h

2. Sada najzamršenija operacija, ali ako je bolje pogledate, više nije tako strašno kao što se na prvi pogled čini. Zamislimo Smod na sljedeći način:

Rice. 5

Pokušao sam vizualizirati Smod elemente na slici, ali ću ipak objasniti:

s0 = 0, s1 = 4, s2 = 9, itd.

Sada, počevši od najnižeg elementa s0, vršimo zamjenu. Sjećajući se paragrafa “ 3.2 Osnovni korak kripto transformacije»I - red, s i - kolona, ​​potražite vrijednost u nultom redu i nultom stupcu:

Slika 6

Dakle, trenutna vrijednost Smod-a nije 6679394 0 h i 6679394 5 h.

Nastavljamo sa zamjenom s1, tj. četiri. Koristeći prvi red i četvrti stupac (s1 = 4!). Gledamo sliku:

Rice. 7

Sada je vrijednost Smod, a ne 667939 4 5h, 667939 2 5h. Pretpostavljam da je sada algoritam zamjene jasan čitaocu, i mogu reći da će nakon konačnog rezultata Ssimple imati sljedeću vrijednost - 11e10325h.

O tome kako je ovo najlakše implementirati u obliku asemblerskih naredbi govoriću kasnije u sljedećem pasusu, nakon što budem govorio o proširenoj tabeli.

1. Moramo pomaknuti rezultujuću Ssimple vrijednost 11 bita ulijevo.

Rice. osam

Kao što vidite, ova akcija je prilično jednostavna i implementirana je jednom naredbom asemblerskog jezika - rol a rezultat ove Srol operacije je 0819288Fh.

4. Sada dio L našeg bloka informacija treba biti XOR sa Srol vrijednošću. Uzimam kalkulator iz w2k sp4 i dobijam Sxor = 091b2b8bh.

5. Ova akcija je konačna i mi jednostavno dodjeljujemo, čistimo R, vrijednost L dijela, i inicijaliziramo L dio sa Sxor vrijednošću.

Konačan rezultat:

L = 091b2b8bh, R = 01020304h

4.2 Povećanje brzine algoritma

Sada razgovarajmo o optimizaciji algoritma za brzinu. Prilikom realizacije projekta treba uzeti u obzir da najbrže radi program koji radi sa registrima češće nego sa memorijom, a tu je i ova prosudba veoma važna, jer preko jednog bloka informacija čak 32 akcije enkripcije!

Kada sam implementirao algoritam šifriranja u svoj program, uradio sam sljedeće:

1. Odabrani dio bloka L u eax registar, a R u edx.

2. U esi registru, inicijaliziranom adresom proširenog ključa, više o tome u nastavku.

3. U registru ebx dodeljena je vrednost adrese proširene tabele zamena, više o tome u nastavku

4. Preneo informacije stavki 1, 2, 3 u funkciju osnovnog ciklusa 32 - Z ili 32 - R, zavisno od situacije.

Ako pogledate dijagram toka ključnih elemenata u paragrafu " Osnovni ciklusi: "32-Z", "32-R"", Tada se naš ključ za osnovni ciklus 32 - Z može predstaviti na sljedeći način:

K 32-Z =

'As28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1',

'As28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1',

'Ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'

One. od početka su k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28 ','zw37 ’,’q839 ',' 7342 ','ui23 ',' 8e2t ','wqm2 ','ewp1 ' ovaj niz se ponavlja tri puta. Tada elementi idu obrnutim redoslijedom, tj.: k8, k7, k6, k5, k4, k3, k2, k1 - 'Ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'.

Unaprijed sam rasporedio elemente u nizu redoslijedom kojim treba da se unose u 32 - Z. Tako sam povećao potrebnu memoriju po principu ključ u ruke, ali sam se spasio nekih procesa razmišljanja koji mi nisu bili potrebni i povećao brzinu algoritma, jer smanjenjem vremena pristupa memoriji! Ovdje sam opisao samo ključ za 32 - Z, za ciklus 32 - R uradio sam isto, ali koristeći drugačiju shemu napajanja elemenata, koju sam također opisao u paragrafu " Osnovni ciklusi: “32-W”, “32-P».

Sada je vrijeme da opišemo implementaciju zamjenske funkcije, kao što sam obećao gore. Nisam mogao ranije da opišem, jer ovo zahteva uvođenje novog koncepta - proširene tabele zamena. Ne mogu vam objasniti šta je to. Umesto toga, pokazaću vam, a vi sami formulišite, šta je to - proširena tabela zamena?

Dakle, da bismo razumjeli šta je proširena tablica zamjene, potrebna nam je tablica zamjene, na primjer, uzet ću onu prikazanu na Sl. 3.

Na primjer, trebali smo zamijeniti broj 66793940h. Predstaviću ga na sledeći način:

Rice. devet

Sada ako uzmemo elemente s1, s0, tj. najmanje značajan bajt, rezultat funkcije zamjene će biti 25h! Nakon što sam pročitao članak Andreja Vinokurova, koji sam citirao u paragrafu " Spisak korišćene literature", Vi zapravo otkrijete da ako uzmete dva reda možete dobiti niz, što vam omogućava da brzo pronađete zamjenske elemente koristeći komandu asemblera xlat. Kažu da je moguće na drugi način brže, ali Andrej Vinokurov je proveo oko četiri godine na istraživanju brzih algoritama za implementaciju GOST-a! Mislim da ne biste trebali ponovo izmisliti točak kada ga već imate.

Dakle, o nizu:

Uzmimo prva dva reda nula i prvi, napravimo niz od 256 bajtova. Sada uočavamo jednu posebnost da ako je potrebno transformisati 00h, onda će rezultat biti 75h (na osnovu slike 3) - ovu vrijednost stavljamo u niz na ofsetu 00h. Uzimamo vrijednost 01h, rezultat zamjenske funkcije 79h, stavljamo je u niz na pomaku 01, i tako dalje do 0FFh, što će nam dati 0FCh, koje ćemo staviti u niz na offsetu 0FFh. Tako smo dobili proširenu tablicu zamjene za prvu grupu redova: prvi i nulu. Ali i dalje postoje tri grupe: druga strana 2, strana 3, treća strana 4, strana 5, četvrta strana 6, strana 7. Sa ove tri grupe se bavimo na isti način kao i sa prvom. Rezultat je proširena tablica zamjene!

Sada možemo implementirati algoritam koji će izvršiti zamjenu. Da bismo to učinili, uzimamo izvorne kodove koje je Andrej Vinokurov objavio na svojoj stranici, pogledajte " Bibliografija».

lea ebx, extented_table_simple

mov eax, [stavite broj koji treba zamijeniti]

dodajte ebx, 100h; skočite na sljedeća dva čvora

sub ebx, 300h; tako da u budućnosti ebx pokazuje na tabelu

Sada još jedna karakteristika, sa prethodnim radnjama ne samo da smo zamenili, već smo i pomerili broj za 8 bita ulevo! Moramo samo pomaknuti broj još 3 bita ulijevo:

i dobijamo rezultat operacije rol eax, 11!

Ne mogu ništa više da dodam o optimizaciji, jedino što mogu da naglasim je ono što sam rekao gore - češće koristite registre nego pristup memoriji. Mislim da su ove riječi samo za početnike, iskusne i bez mojih riječi ovo savršeno razumiju.

Zahtjevi za ključne informacije.

Kako je navedeno u članku Andreja Vinokurova, ključ se bira prema dva kriterija:

Kriterijum za jednakovjerovatnu distribuciju bitova između vrijednosti 1 i 0. Obično je kriterij za jednakovjerovatnu distribuciju bitova Pearsonov kriterij („hi-kvadrat“).

To znači da ključ, u principu, može bilo koji broj. To jest, kada se formira sljedeći bit ključa, vjerovatnoća njegove inicijalizacije za jedan ili nula je 50/50!

Imajte na umu da se ključ sastoji od osam elemenata, svaki od 32 bita, tako da u ključu ima 32 * 8 = 256 bita, a broj mogućih ključeva je 2 256! Zar te to ne pogađa?

Kriterijum serije.

Ako pogledamo naš ključ, koji sam dao u paragrafu " 4.1 Implementacija glavnog koraka kripto transformacije», Tada ćete primijetiti da je sljedeća notacija važeća:

Rice. deset

U jednoj frazi, vrijednost k 1 ne treba ponavljati ni u k 2, ni u bilo kojem drugom elementu ključa.

Odnosno, ključ koji smo odabrali kao razmatranje algoritma šifriranja u potpunosti zadovoljava dva gornja kriterija.

Sada o izboru tablice zamjena:

Sada razgovarajmo o tome kako odabrati pravu tablicu zamjene. Glavni zahtjev za odabir zamjenskih tablica je fenomen "neponovljivosti" elemenata, od kojih je svaki 4 bita veličine. Kao što ste videli gore, svaki red tabele zamene sastoji se od vrednosti 0h, 1h, 2h, 3h,…, 0fh. Dakle, glavni zahtjev je da svaki red sadrži vrijednosti 0h, 1h, 2h, ..., 0fh i svaku takvu vrijednost u jednom primjerku. Na primjer, slijed:

1 2 3 4 5 6 7 8 9 A B C D E F

U potpunosti ispunjava ovaj zahtjev, ali ipak! Ne preporučuje se odabir takvog niza kao niza. Budući da ako unesete vrijednost na ulaz funkcije koja se oslanja na takav niz, onda ćete dobiti istu vrijednost na izlazu! Ne vjerujete mi? Zatim uzmite broj 332DA43Fh i osam takvih linija kao tablicu zamjene. Izvršite operaciju zamjene i uvjeravam vas, izlaz će biti broj 332DA43Fh! Odnosno isto ono što ste predali na ulaz operacije! A ovo nije znak dobre forme kod enkripcije, zar ne?

Ovo je bio jedan zahtjev, sljedeći kriterij kaže da - svaki bit izlaznog bloka mora biti statistički nezavisan od svakog bita ulaznog bloka!

Kako to izgleda jednostavnije? A evo kako smo, na primjer, iz gornjeg broja izabrali element s0 = 0Fh, 01111b. Vjerovatnoća da ćemo sada zamijeniti prvi bit sa jedan ili nulu je 0,5! Vjerovatnoća zamjene drugog, trećeg i četvrtog bita, svaki bit, razmatramo posebno, sa jedinicama ili nulama je također 0, 5. Prilikom odabira s1 = 0Eh, vjerovatnoća da smo nulti bit, a ovo je "0" , bit će zamijenjen nulom ili jedan je previše jednak - 0,5! Dakle, prema ovom kriteriju, ne postoji pravilnost između zamjene nulti bitova elemenata s0, s1! Da, možete zamijeniti jedinice, ali možete zamijeniti i nule.

Da biste procijenili tabelu prema ovom kriteriju, možete napraviti tablicu koeficijenata korelacije izračunatih po formuli:

Ako je p = 1, tada je vrijednost bita j na izlazu jednaka vrijednosti bita i na ulazu za bilo koju kombinaciju bita na ulazu;

Ako je p = -1, tada je vrijednost bita j na izlazu uvijek inverzna od ulaznog bita i;

Ako je p = 0, tada izlazni bit j sa jednakom vjerovatnoćom uzima vrijednosti 0 i 1 za bilo koju fiksnu vrijednost ulaznog bita i.

Uzmimo primjer jednog reda:

Podijelimo ga na "komponente":

Izračunajmo jedan koeficijent prema gornjoj formuli. Da biste lakše razumjeli kako se to radi, objasnit ću detaljnije:

Uzimamo 0. bit 0. broja (0) na ulazu i 0. bit 0. broja na izlazu (1) izvodimo operaciju 0 XOR 1 = 1.

Uzimamo 0. bit prvog broja (1) na ulazu i 0. bit 1. broja na izlazu (1) izvodimo operaciju 1 XOR 1 = 0.

Uzimamo 0. bit 2. broja (0) na ulazu i 0. bit 2. broja na izlazu (0) izvodimo operaciju 0 XOR 0 = 0.

Uzimamo 0. bit 3. broja (1) na ulazu i 0. bit 3. broja na izlazu (1) i izvodimo operaciju 1 XOR 1 = 0.

Provodeći uzastopne XOR operacije u takvom nizu, brojimo broj svih nenultih vrijednosti, dobijamo vrijednost 6. Otuda P 00 = 1- (6/2 4-1) = 0,25. Dakle, pokazalo se da je vrijednost bita 0 na izlazu jednaka vrijednosti bita 0 na ulazu u 4 slučaja od 16;

Konačna tabela kvota:

Kao što se vidi iz tabele koeficijenata korelacije, bit 3 na ulazu je invertovan u odnosu na bit 0 na izlazu u 14 slučajeva od 16, što je 87,5%, što više nije prihvatljivo za normalne sisteme šifrovanja. Uzmimo još jedan primjer za promjenu:

Tabela koeficijenata će biti sljedeća (kome nije lijeno da preračuna)

Pa, u ovoj tabeli stvari su još gore - bitovi 1 i 2 grupe ostaju nepromijenjeni! Kriptoanalitičar ima gdje da se okrene Uzimajući u obzir sve ove zahtjeve, jednostavnom pretragom ("head-on") pronađene su permutacijske tablice koje odgovaraju naznačenoj teoriji (danas - 1276 kombinacija) Evo nekih od njih:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Spisak korišćene literature.

1. Članak Andrey Vinokurov:

Algoritam šifriranja GOST 28147-89, njegova upotreba i implementacija

za računare na Intel x86 platformi.

Tu su i izvorni kodovi za implementaciju algoritma šifriranja.

1. Članak Horsta Feistela:

Kriptografija i kompjuterska sigurnost.

(može se naći na istoj adresi kao i prethodni članak)

1. Ross N. Williams:

Elementarni vodič za CRC algoritme za otkrivanje grešaka

Objavljeno na sajtu www.wasm.ru.

Priznanja.

Želeo bih da izrazim svoju zahvalnost svim posetiocima foruma www.wasm.ru. Ali posebno bih želeo da se zahvalim ChS-u, koji je trenutno poznat kao SteelRat, pomogao mi je da razumem stvari koje verovatno nikada ne bih razumeo, kao i pomoć u pisanju pasusa: “ Zahtjevi za ključne informacije“, glavni dio ovog pasusa napisao je on. Takođe sam duboko zahvalan zaposleniku KSTU po imenu A.N. Tupoljev Anikin Igor Vjačeslavovič i bio bi grijeh ne spomenuti Chrisa Kasperskog zbog činjenice da je on i Volodya / wasm.ru zbog njegovih instrukcija. Oh, i ja to dobijam od njega. Takođe želim da primetim Sega-Zero/Callipso, ali to mi je palo na pamet malo matematičke džungle.

Ovo je, možda, sve što bih želeo da vam kažem.

Bio bih zahvalan za bilo kakvu kritiku ili pitanja vezana za ovaj članak ili samo savjet. Moji kontakt detalji: [email protected], ICQ - 337310594.

Srdačan pozdrav, Evil`s Interrupt.

P.S.: Ovim člankom nisam pokušao nikoga nadmašiti. Napisano je s namjerom, da olakša proučavanje GOST-a, a ako imate poteškoća, to ne znači da sam ja kriv za ovo. Budite razumni i strpljivi, svako dobro!

“Dok si živ, ne umri, pogledaj ovaj svijet.
Mnogi ovdje imaju mrtvu dušu - mrtvi su iznutra.
Ali hodaju i smiju se, ne znajući da nisu,
Ne žuri sa svojim smrtnim časom”, rekla mi je.

Aria, "Visoko tamo"

1. Uvod

1. Preliminarne informacije o blok šiframa

2.1 Feistelove mreže.
2.2 Blok šifra GOST 28147-89

1. Teoretski minimum

3.1 Ključne informacije
3.2 Glavni korak kripto transformacije

3.3 Osnovne petlje:“ 32-Z” , “ 32-R” .

1. Vježbajte

4.1 Implementacija glavnog koraka kripto transformacije
4.2 Povećanje brzine algoritma
5.
6. Spisak korišćene literature
7. Priznanja.

Uvod.

Ovaj dokument je moj pokušaj da opišem metodu za jednostavnu zamjenu algoritma šifriranja GOST 28147-89 najjednostavnijim, ali ipak tehnički kompetentnim jezikom. Nakon što pročita prvih šest tačaka, čitalac će dati svoje mišljenje o tome kako sam to uradio.

Kako bi moj rad imao više koristi, preporučujem da se naoružate radovima autora navedenih u spisku korišćene literature. Također se preporučuje da kalkulator ima funkciju za izračunavanje operacije. XOR pošto čitanje članka pretpostavlja da je čitatelj namjeravao proučiti ovaj algoritam šifriranja. Iako je pogodan i kao referenca, ovaj članak sam napisao upravo kao trening.

Preliminarne informacije o blok šiframa.

Prije nego počnemo gledati algoritam, moramo se upoznati s istorijom stvaranja ove vrste šifri. Algoritam spada u kategoriju blok šifri, u čijoj arhitekturi su informacije podijeljene na konačan broj blokova, a posljednji naravno ne može biti potpun. Proces šifriranja se odvija preko kompletnih blokova koji formiraju šifru. Završni blok, ako je nepotpun, dopunjen je nečim (u nastavku ću reći o nijansama njegovog dovršavanja) i šifriran je na isti način kao i puni blokovi. Pod šifrom mislim na rezultat funkcije enkripcije koja djeluje na određenu količinu podataka koje je korisnik predao na šifriranje. Drugim riječima, šifra je krajnji rezultat enkripcije.

Povijest razvoja blok šifri vezana je za rane 70-te godine, kada je IBM, uvidjevši potrebu za zaštitom informacija pri prijenosu podataka putem računalnih komunikacijskih kanala, počeo provoditi vlastiti istraživački program posvećen zaštiti informacija u elektronskim mrežama, uključujući kriptografiju.

Grupu istraživača - programera kompanije IBM, koja je počela proučavati sisteme šifriranja sa simetričnom šemom korištenja ključa, predvodio je dr. Horst Feistel.

2.1 Feistelove mreže

Arhitektura nove metode šifriranja koju je Feistel predložio u klasičnoj literaturi naziva se "Feistelova arhitektura", ali se trenutno u ruskoj i stranoj literaturi koristi ustaljeniji termin - "Feistelova mreža" ili Feistelova mreža. Naknadno je na ovoj arhitekturi izgrađena šifra "Lucifer" - koja je kasnije objavljena i izazvala je novi talas interesovanja za kriptografiju uopšte.

Ideja arhitekture "Feistelove mreže" je sljedeća: ulazni tok informacija podijeljen je na blokove veličine n bitova, gdje je n paran broj. Svaki blok je podijeljen na dva dijela - L i R, zatim se ovi dijelovi unose u iterativni blok šifru, u kojoj je rezultat j-te faze određen rezultatom prethodne faze j-1! To se može ilustrirati primjerom:

Rice. 1

Gdje je funkcija A glavna radnja blok šifre. To može biti jednostavna akcija, kao što je operacija XOR, ili može imati složeniji oblik kao niz niza jednostavnih radnji - modulo zbrajanje, pomak ulijevo, zamjena elementa, itd., uzeti zajedno, ove jednostavne akcije formiraju tzv - glavni korak kripto transformacije.

Treba napomenuti da su ključni elementi operacije funkcije nabavka ključnih elemenata i XOR operacija, a po tome koliko je dobro osmišljen rad ovih operacija, govori o kriptografskoj snazi ​​šifre u cjelini.

Kako bi ideja Feistelove mreže bila konačno jasna, razmotrite najjednostavniji slučaj prikazan u pirinač. 1, gdje će u funkciji A - postojati operacije “mod 2” (“xor”), ali ovo najjednostavniji u slučaju, u ozbiljnijoj situaciji, na primjer, skrivanje informacija od nacionalnog značaja, funkcija A može biti složenija (koliko sam vidio, funkcija A je zaista vrlo složena):

Početni podaci:

L = 1110b, R = 0101, K = 1111b

Uzmi šifru

1. (R + K) mod 2 4 = Smod, Smod = 0100b
2. (Smod + L) mod 2 = Sxor, Sxor = 1010b
3. L = R, R = Sxor

L = 0101b, R = 1010b

Objasnimo naše postupke:

1. Ova operacija je mod 2 4 dodavanje. U praksi se ova operacija svodi na jednostavno sabiranje, gdje moramo sabrati dva broja i zanemariti prijenos na 5. znamenku. Budući da ako stavimo eksponente iznad cifara binarnog prikaza broja, biće eksponent četiri iznad pete znamenke, pogledajmo sliku ispod, koja pokazuje radnje naše operacije:

Rice. 2

Ovdje sam strelicom pokazao na eksponente, kao što vidite, rezultat je trebao biti 10100, ali pošto je prijenos zanemaren tokom mod 2 4 operacije, dobijamo 0100.

1. Ova operacija se u literaturi naziva mod 2, a na asemblerskom jeziku implementira se naredbom XOR... Ali njegov tačniji naziv je mod 2 1. Bez ove jedinstvene operacije, teško da je moguće izgraditi brz, lako implementivi algoritam šifriranja, a da u isto vrijeme i dalje bude prilično kriptografski jak. Jedinstvenost ove operacije leži u činjenici da je ona sama suprotna! Na primjer, ako je broj A XOR sa brojem B, kao rezultat ćemo dobiti B, u budućnosti je dovoljno da ponovo XOR brojeve B i C jedan drugog da dobijemo prethodnu vrijednost A!

U ovoj operaciji dobili smo 1010 sa brojevima 1110 i 0100, da bismo dobili natrag 1110, dovoljno je preko XOR brojeva 0100 i 1010! Više detalja o ovoj operaciji možete pronaći u članku koji je priložen uz stranicu. www.wasm.ru, « Elementarni vodič zaCRC_ algoritmi za detekciju grešaka»Autor koji Ross N. Williams... U ovom radu postoji poenta - “ 5. Binarna aritmetika bez crtica". Operacija je opisana u ovom članku. xor! Uzvikujem jer je u ovom članku ova operacija tako zakazana da čitatelj ne samo da razumije kako ova operacija funkcionira, već je čak i pokreće vidi, cuj i oseti!

1. Ova radnja je neophodna kako bi se tokom dešifriranja mogle dobiti početne vrijednosti iz šifre.

2.2 Blok šifra GOST 28147-89

Algoritam šifriranja GOST 28147 - 89 pripada kategoriji blok šifri koje rade prema arhitekturi uravnoteženih Feistelovih mreža, gdje su dva dijela odabranog bloka informacija jednake veličine. Algoritam je razvijen u dubinama osmog odjela KGB-a, sada transformiran u FAPSI i uvršten je kao standard za šifriranje Ruske Federacije još 1989. godine pod SSSR-om.

Da bi ova metoda algoritma funkcionirala, potrebno je podijeliti informacije u blokove veličine 64 bita. Generirajte ili unesite u sistem šifriranja sljedeće ključne informacije: ključ i tablicu zamjene. Izbor ključa i tablice zamjene za šifriranje treba shvatiti vrlo ozbiljno, jer ovo je temelj sigurnosti vaših informacija. Za informacije o tome koji su zahtjevi nametnuti ključu i tabeli zamjena, pogledajte stavku "Zahtjevi za ključne informacije".

Kada razmatramo metodu, nećemo se fokusirati na ovo, jer Ovaj članak, kao što sam već rekao, napisan je s ciljem da čitatelja nauči kako šifrirati podatke metodom jednostavne zamjene ovog algoritma šifriranja, ali ćemo se na ovo pitanje svakako dotaknuti na kraju članka.

Teoretski minimum.

3.1 Ključne informacije

Kao što sam već rekao, sljedeće su aktivno uključene u enkripciju podataka:

3.1.1. Ključ je niz od osam elemenata, svaki od 32 bita. U nastavku ćemo označavati simbolom K, a elementi od kojih se sastoji su k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Tabela zamjene - matrica od osam redova i šesnaest kolona, ​​u daljem tekstu - Hij. Svaki element na preseku reda i i kolone j zauzima 4 bita.

Glavni korak u procesu enkripcije je - glavni korak kripto transformacije. Ovo nije ništa drugo nego akcija šifriranja podataka prema određenom algoritmu, samo su programeri uveli preglomazno ime :).

Prije početka šifriranja, blok se dijeli na dva dijela L i R, svaki po 32 bita. Ključni element je odabran i tek tada se ova dva dijela bloka, ključni element, tabela zamjene, unose u funkciju glavnog koraka, rezultat glavnog koraka je jedna iteracija osnovnog ciklusa, o čemu će biti riječi u sledeći paragraf. Glavni korak se sastoji od sljedećeg:

1. Dodatni dio bloka R se sabira sa ključnim elementom K mod 2 32. Sličnu operaciju sam opisao gore, ovdje je ista stvar samo što eksponent nije "4", već "32" - rezultat ove operacije će u budućnosti biti označen kao Smod.
2. Podijelite prethodno dobiveni rezultat Smod na četverobitne elemente s7, s6, s5, s4, s3, s2, s1, s0 i unesite ga u funkciju zamjene. Zamjena je sljedeća: odabire se element Smod - si, počinjemo ispočetka s najnižim elementom i zamjenjujemo vrijednošću iz tablice zamjena sa i - redom i stupcem na koje ukazuje vrijednost elementa s i. Prelazimo na s i +1 element i nastavljamo na isti način i tako nastavljamo dok ne promijenimo vrijednost posljednjeg elementa Smod - rezultat ove operacije će biti označen kao, Ssimple.
3. U ovoj operaciji pomičemo Ssimple vrijednost ciklički ulijevo za 11 bita i dobijamo Srol.
4. Odaberemo drugi dio L bloka i dodamo ga mod 2 sa Srol, kao rezultat imamo Sxor.
5. U ovoj fazi, dio L bloka postaje jednak vrijednosti R dijela, a R dio se, zauzvrat, inicijalizira rezultatom Sxor, i time je funkcija glavnog koraka završena!

3.3 Osnovni ciklusi: "32-Z", "32-R".

Da biste šifrirali informacije, morate ih podijeliti na blokove veličine 64 bita, naravno posljednji blok može biti manji od 64 bita. Ova činjenica je Ahilova peta ove metode "lake zamjene". Budući da je njegovo dodavanje na 64 bita vrlo važan zadatak za povećanje kriptografske snage šifriranog koda i na ovom osjetljivom mjestu, ako je prisutan u nizu informacija, a možda i ne postoji (na primjer, datoteka od 512 bajtova! ), Treba se odnositi sa velikom odgovornošću!

Nakon što ste podijelili informacije u blokove, trebali biste podijeliti ključ na elemente:

K = k1, k2, k3, k4, k5, k6, k7, k8

Sama enkripcija se sastoji u korištenju takozvanih osnovnih ciklusa. Što, pak, uključuje n-ti broj osnovnih koraka kripto-transformacije.

Osnovni ciklusi su označeni, kako se to kaže: n - m. Gdje je n broj osnovnih koraka kripto-transformacije u osnovnom ciklusu, a m "tip" osnovnog ciklusa, tj. o čemu pričamo, o "Z" enkripciji ili "R" enkripciji podataka.

Osnovni ciklus šifrovanja 32-Z sastoji se od 32 osnovna koraka kripto-transformacije. Blok N i element ključa K se unose u funkciju koja implementira akcije koraka, a prvi korak se javlja sa k1, drugi preko rezultata dobijenog elementom k2 itd. prema sljedećoj shemi:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

Proces dešifriranja za 32-P odvija se na sličan način, ali su ključni elementi dati obrnutim redoslijedom:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Vježbajte.

Nakon što smo se upoznali sa teorijom šifriranja informacija, došlo je vrijeme da vidimo kako se šifriranje odvija u praksi.

Početni podaci:

Uzmite blok informacija N = 0102030405060708h, ovdje su dijelovi L i R jednaki:

L = 01020304h, R = 05060708h, uzmimo ključ:

K = as28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(ovo su ASCII kodovi, da biste vidjeli heksadecimalni prikaz, možete otvoriti ovu datoteku u načinu prikaza u Total Commanderu pritiskom na tipku F3"A onda ključ" 3 "). U ovom ključu vrijednosti elemenata će biti:

k1 = ‘as28’, k2 = ‘zw37’, k3 = ‘q839’, k4 = ‘7342’

k5 = 'ui23', k6 = '8e2t', k7 = 'wqm2', k8 = 'ewp1'

Uzmite i sljedeću tablicu zamjene:

Rice. 3

Ovdje su redovi numerirani od 0 do 7, kolone od 0 do F.

upozorenje: Sve informacije, uključujući ključ sa tablicom zamjene, uzimaju se kao primjer za razmatranje algoritma!

Koristeći "Početne podatke", potrebno je dobiti rezultat akcije glavnog koraka kripto transformacije.

1. Odabiremo dio R = 05060708h i ključni element k1 = 'as28', u heksadecimalnom obliku ključni element će izgledati ovako: 61733238h. Sada radimo operaciju sumiranja mod 2 32:

Rice. 4

Kao što možete vidjeti na slici, nismo imali prijenos u 33 bita označena crvenom bojom i sa eksponentom “ 32 ". A da smo imali druge vrijednosti R i ključnog elementa, ovo bi se moglo dogoditi, a onda bismo to zanemarili i dalje koristili samo bitove označene žutom bojom.

Ovu operaciju izvodim sa komandom asemblera dodati:

; eax = R, ebx = 'as28'

Rezultat ove operacije Smod = 66793940h

1. Sada je najzamršenija operacija, ali ako bolje pogledate, više nije tako strašno kao što se na prvi pogled čini. Zamislimo Smod na sljedeći način:

FIGURA NIJE SAČUVANA

Rice. 5

Pokušao sam vizualizirati Smod elemente na slici, ali ću ipak objasniti:

s0 = 0, s1 = 4, s2 = 9, itd.

Sada, počevši od najnižeg elementa s0, vršimo zamjenu. Sjećajući se paragrafa “ 3.2 Osnovni korak kripto transformacije»I - red, s i - kolona, ​​potražite vrijednost u nultom redu i nultom stupcu:

Slika 6

Dakle, trenutna vrijednost Smod-a nije 6679394 0 h i 6679394 5 h.

Nastavljamo sa zamjenom s1, tj. četiri. Koristeći prvi red i četvrti stupac (s1 = 4!). Gledamo sliku:

Rice. 7

Sada je vrijednost Smod, a ne 667939 4 5h, 667939 2 5h. Pretpostavljam da je sada algoritam zamjene jasan čitaocu, i mogu reći da će nakon konačnog rezultata Ssimple imati sljedeću vrijednost - 11e10325h.

O tome kako je ovo najlakše implementirati u obliku asemblerskih naredbi govoriću kasnije u sljedećem pasusu, nakon što budem govorio o proširenoj tabeli.

1. Moramo pomaknuti rezultujuću Ssimple vrijednost 11 bita ulijevo.

Rice. osam

Kao što vidite, ova akcija je prilično jednostavna i implementirana je jednom naredbom asemblerskog jezika - rol a rezultat ove Srol operacije je 0819288Fh.

1. Sada ostaje L dio našeg bloka informacija koji treba biti XOR sa Srol vrijednošću. Uzimam kalkulator iz w2k sp4 i dobijam Sxor = 091b2b8bh.
2. Ova akcija je konačna i mi jednostavno dodjeljujemo, čistimo R, vrijednost L dijela, i inicijaliziramo L dio sa Sxor vrijednošću.

Konačan rezultat:

L = 091b2b8bh, R = 01020304h

4.2 Povećanje brzine algoritma

Sada razgovarajmo o optimizaciji algoritma za brzinu. Prilikom realizacije projekta treba uzeti u obzir da najbrže radi program koji radi sa registrima češće nego sa memorijom, a tu je i ova prosudba veoma važna, jer preko jednog bloka informacija čak 32 akcije enkripcije!

Kada sam implementirao algoritam šifriranja u svoj program, uradio sam sljedeće:

1. Odabrani dio bloka L za registraciju eax, a R za edx.
2. U esi registru, inicijaliziranom adresom proširenog ključa, više o tome u nastavku.
3. U registru ebx je dodeljena vrednost adrese proširene tabele zamena, više o tome u nastavku
4. Prenesene informacije stavki 1, 2, 3 u funkciju osnovnog ciklusa 32 - Z ili 32 - R, zavisno od situacije.

Ako pogledate dijagram toka ključnih elemenata u paragrafu " Osnovni ciklusi: "32-Z", "32-R"", Tada se naš ključ za osnovni ciklus 32 - Z može predstaviti na sljedeći način:

K 32-Z =

'As28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1',

'As28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1',

'Ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'

One. od početka su k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28 ','zw37 ’,’q839 ',' 7342 ','ui23 ',' 8e2t ','wqm2 ','ewp1 ' ovaj niz se ponavlja tri puta. Tada elementi idu obrnutim redoslijedom, tj.: k8, k7, k6, k5, k4, k3, k2, k1 - 'Ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'.

Unaprijed sam rasporedio elemente u nizu redoslijedom kojim treba da se unose u 32 - Z. Tako sam povećao potrebnu memoriju po principu ključ u ruke, ali sam se spasio nekih procesa razmišljanja koji mi nisu bili potrebni i povećao brzinu algoritma, jer smanjenjem vremena pristupa memoriji! Ovdje sam opisao samo ključ za 32 - Z, za ciklus 32 - R uradio sam isto, ali koristeći drugačiju shemu napajanja elemenata, koju sam također opisao u paragrafu " Osnovni ciklusi: “32-W”, “32-P».

Sada je vrijeme da opišemo implementaciju zamjenske funkcije, kao što sam obećao gore. Nisam mogao ranije da opišem, jer ovo zahteva uvođenje novog koncepta - proširene tabele zamena. Ne mogu vam objasniti šta je to. Umesto toga, pokazaću vam, a vi sami formulišite, šta je to - proširena tabela zamena?

Dakle, da bismo razumjeli šta je proširena tablica zamjene, potrebna nam je tablica zamjene, na primjer, uzet ću onu prikazanu na Sl. 3.

Na primjer, trebali smo zamijeniti broj 66793940h. Predstaviću ga na sledeći način:

FIGURA NIJE SAČUVANA

Rice. devet

Sada ako uzmemo elemente s1, s0, tj. najmanje značajan bajt, rezultat funkcije zamjene će biti 25h! Nakon što sam pročitao članak Andreja Vinokurova, koji sam citirao u paragrafu " Spisak korišćene literature", Vi zapravo otkrijete da ako uzmete dva reda možete dobiti niz, što vam omogućava da brzo pronađete zamjenske elemente koristeći komandu asemblera xlat. Kažu da je moguće na drugi način brže, ali Andrej Vinokurov je proveo oko četiri godine na istraživanju brzih algoritama za implementaciju GOST-a! Mislim da ne biste trebali ponovo izmisliti točak kada ga već imate.

Dakle, o nizu:

Uzmimo prva dva reda nula i prvi, napravimo niz od 256 bajtova. Sada uočavamo jednu posebnost da ako je potrebno transformisati 00h, onda će rezultat biti 75h (na osnovu slike 3) - ovu vrijednost stavljamo u niz na ofsetu 00h. Uzimamo vrijednost 01h, rezultat zamjenske funkcije 79h, stavljamo je u niz na pomaku 01, i tako dalje do 0FFh, što će nam dati 0FCh, koje ćemo staviti u niz na offsetu 0FFh. Tako smo dobili proširenu tablicu zamjene za prvu grupu redova: prvi i nulu. Ali i dalje postoje tri grupe: druga strana 2, strana 3, treća strana 4, strana 5, četvrta strana 6, strana 7. Sa ove tri grupe se bavimo na isti način kao i sa prvom. Rezultat je proširena tablica zamjene!

Sada možemo implementirati algoritam koji će izvršiti zamjenu. Da bismo to učinili, uzimamo izvorne kodove koje je Andrej Vinokurov objavio na svojoj stranici, pogledajte " Bibliografija».

lea ebx, extented_table_simple

mov eax, [stavite broj koji treba zamijeniti]

dodajte ebx, 100h; skočite na sljedeća dva čvora

sub ebx, 300h; tako da u budućnosti ebx pokazuje na tabelu

Sada još jedna karakteristika, sa prethodnim radnjama ne samo da smo zamenili, već smo i pomerili broj za 8 bita ulevo! Moramo samo pomaknuti broj još 3 bita ulijevo:

i dobijamo rezultat operacije rol eax, 11!

Ne mogu ništa više da dodam o optimizaciji, jedino što mogu da naglasim je ono što sam rekao gore - češće koristite registre nego pristup memoriji. Mislim da su ove riječi samo za početnike, iskusne i bez mojih riječi ovo savršeno razumiju :).

Zahtjevi za ključne informacije.

Kako je navedeno u članku Andreja Vinokurova, ključ se bira prema dva kriterija:

- kriterij za jednakovjerovatnu distribuciju bitova između vrijednosti 1 i 0. Obično je kriterij za jednakovjerovatnu distribuciju bitova Pearsonov kriterij („hi-kvadrat“).

To znači da ključ, u principu, može bilo koji broj. To jest, kada se formira sljedeći bit ključa, vjerovatnoća njegove inicijalizacije za jedan ili nula je 50/50!

Imajte na umu da se ključ sastoji od osam elemenata, svaki od 32 bita, tako da u ključu ima 32 * 8 = 256 bita, a broj mogućih ključeva je 2 256! Zar te to ne pogađa? 🙂

- kriterijum serije.

Ako pogledamo naš ključ, koji sam dao u paragrafu " 4.1 Implementacija glavnog koraka kripto transformacije», Tada ćete primijetiti da je sljedeća notacija važeća:

Rice. deset

U jednoj frazi, vrijednost k 1 ne treba ponavljati ni u k 2, ni u bilo kojem drugom elementu ključa.

Odnosno, ključ koji smo odabrali kao razmatranje algoritma šifriranja u potpunosti zadovoljava dva gornja kriterija.

Sada o izboru tablice zamjena:

Sada razgovarajmo o tome kako odabrati pravu tablicu zamjene. Glavni zahtjev za odabir zamjenskih tablica je fenomen "neponovljivosti" elemenata, od kojih je svaki 4 bita veličine. Kao što ste videli gore, svaki red tabele zamene sastoji se od vrednosti 0h, 1h, 2h, 3h,…, 0fh. Dakle, glavni zahtjev je da svaki red sadrži vrijednosti 0h, 1h, 2h, ..., 0fh i svaku takvu vrijednost u jednom primjerku. Na primjer, slijed:

1 2 3 4 5 6 7 8 9 A B C D E F

U potpunosti ispunjava ovaj zahtjev, ali ipak! Ne preporučuje se odabir takvog niza kao niza. Budući da ako unesete vrijednost na ulaz funkcije koja se oslanja na takav niz, onda ćete dobiti istu vrijednost na izlazu! Ne vjerujete mi? Zatim uzmite broj 332DA43Fh i osam takvih linija kao tablicu zamjene. Izvršite operaciju zamjene i uvjeravam vas, izlaz će biti broj 332DA43Fh! Odnosno isto ono što ste predali na ulaz operacije! A ovo nije znak dobre forme kod enkripcije, zar ne? 🙂

Ovo je bio jedan zahtjev, sljedeći kriterij kaže da - svaki bit izlaznog bloka mora biti statistički nezavisan od svakog bita ulaznog bloka!

Kako to izgleda jednostavnije? A evo kako smo, na primjer, iz gornjeg broja izabrali element s0 = 0Fh, 01111b. Vjerovatnoća da ćemo sada zamijeniti prvi bit sa jedan ili nulu je 0,5! Vjerovatnoća zamjene drugog, trećeg i četvrtog bita, svaki bit, razmatramo posebno, sa jedinicama ili nulama je također 0, 5. Prilikom odabira s1 = 0Eh, vjerovatnoća da smo nulti bit, a ovo je "0" , bit će zamijenjen nulom ili jedan je previše jednak - 0,5! Dakle, prema ovom kriteriju, ne postoji pravilnost između zamjene nulti bitova elemenata s0, s1! Da, možete zamijeniti jedinice, ali možete zamijeniti i nule. 🙂

Da biste procijenili tabelu prema ovom kriteriju, možete napraviti tablicu koeficijenata korelacije izračunatih po formuli:

- ako je p = 1, tada je vrijednost bita j na izlazu jednaka vrijednosti bita i na ulazu za bilo koju kombinaciju bita na ulazu;

- ako je p = -1, tada je vrijednost bita j na izlazu uvijek inverzna od ulaznog bita i;

- ako je p = 0, tada izlazni bit j sa jednakom vjerovatnoćom uzima vrijednosti 0 i 1 za bilo koju fiksnu vrijednost ulaznog bita i.

Uzmimo primjer jednog reda:

D	B	4	1	3	F	5	9	0	A	E	7	6	8	2	C

Podijelimo ga na "komponente":

Izračunajmo jedan koeficijent prema gornjoj formuli. Da biste lakše razumjeli kako se to radi, objasnit ću detaljnije:

- uzimamo 0. bit 0. broja (0) na ulazu i 0. bit 0. broja na izlazu (1) izvodimo operaciju 0 XOR 1 = 1.

- uzimamo 0. bit 1. broja (1) na ulazu i 0. bit 1. broja na izlazu (1) izvodimo operaciju 1 XOR 1 = 0.

- uzimamo 0. bit 2. broja (0) na ulazu i 0. bit 2. broja na izlazu (0) izvodimo operaciju 0 XOR 0 = 0.

- uzimamo 0. bit 3. broja (1) na ulazu i 0. bit 3. broja na izlazu (1) izvodimo operaciju 1 XOR 1 = 0.

Provodeći uzastopne XOR operacije u takvom nizu, brojimo broj svih nenultih vrijednosti, dobijamo vrijednost 6. Otuda P 00 = 1- (6/2 4-1) = 0,25. Dakle, pokazalo se da je vrijednost bita 0 na izlazu jednaka vrijednosti bita 0 na ulazu u 4 slučaja od 16;

Konačna tabela kvota:

Tabela koeficijenata će biti sljedeća (kome nije lijeno da preračuna)

	ulaz
Izlaz		0	1	2	3
	0	-0,25	0,00	0,00	0,00
	1	0,00	1,00	0,00	0,00
	2	0,00	0,00	1,00	0,00
	3	0,00	0,00	0,00	-0,50

Pa, u ovoj tabeli stvari su još gore - bitovi 1 i 2 grupe ostaju nepromijenjeni! Kriptoanalitičar ima gdje da se okrene 🙂 Uzimajući u obzir sve ove zahtjeve, jednostavnom pretragom ("head-on") pronađene su permutacijske tablice koje odgovaraju naznačenoj teoriji (danas - 1276 kombinacija) Evo nekih od njih:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Spisak korišćene literature.

1. Članak Andrey Vinokurov:

Algoritam šifriranja GOST 28147-89, njegova upotreba i implementacija

za računare na Intel x86 platformi.

(može se naći na: http://www.enlight.ru/crypto/frame.htm).

Tu su i izvorni kodovi za implementaciju algoritma šifriranja.

1. Članak Horsta Feistela:

Kriptografija i kompjuterska sigurnost.

(može se naći na istoj adresi kao i prethodni članak)

1. Ross N. Williams:

Elementarni vodič za CRC algoritme za otkrivanje grešaka

Objavljeno na sajtu www.wasm.ru.

Priznanja.

Želeo bih da izrazim svoju zahvalnost svim posetiocima foruma www.wasm.ru. Ali posebno bih želeo da se zahvalim ChS-u, koji je trenutno poznat kao SteelRat, pomogao mi je da razumem stvari koje verovatno nikada ne bih razumeo, kao i pomoć u pisanju pasusa: “ Zahtjevi za ključne informacije“, glavni dio ovog pasusa napisao je on. Takođe sam duboko zahvalan zaposleniku KSTU po imenu A.N. Tupoljev Anikin Igor Vjačeslavovič i bio bi grijeh ne spomenuti Chrisa Kasperskog zbog činjenice da je on i Volodya / wasm.ru zbog njegovih instrukcija. Oh, i dobijam od njega :). Takođe želim da primetim Sega-Zero/Callipso, ali to mi je palo na pamet malo matematičke džungle.

Ovo je, možda, sve što bih želeo da vam kažem.

Bio bih zahvalan za bilo kakvu kritiku ili pitanja vezana za ovaj članak ili samo savjet. Moji kontakt detalji: [email protected], ICQ - 337310594.

Srdačan pozdrav, Evil`s Interrupt.

P.S.: Ovim člankom nisam pokušao nikoga nadmašiti. Napisano je s namjerom, da olakša proučavanje GOST-a, a ako imate poteškoća, to ne znači da sam ja kriv za ovo. Budite razumni i strpljivi, svako dobro!

Ovaj algoritam je obavezan za korištenje kao algoritam za šifriranje u vladinim organizacijama Ruske Federacije i nizu komercijalnih.

Opis algoritma

Dijagram algoritma je prikazan na sl. 3.1. Kao što vidite, shema ovog algoritma je prilično jednostavna, što nedvosmisleno pojednostavljuje njegovu softversku ili hardversku implementaciju.

GOST 28147-89 algoritam šifrira informacije u blokovima od 64 bita, koji su podijeljeni u dva podbloka od 32 bita (N1 i N2). Podblok N1 se obrađuje na određeni način, nakon čega mu se dodaje vrijednost

sa vrijednošću podbloka N2 (sabiranje se vrši po modulu 2), tada se podblokovi zamjenjuju. Takva transformacija se izvodi za određeni broj rundi: 16 ili 32, ovisno o načinu rada algoritma (opisano u nastavku). U svakom krugu se izvode sljedeće operacije:

1. Preklapanje tastera. Sadržaj podbloka / VI se dodaje po modulu 2 32 sa dijelom Kx ključa.

Ključ za šifriranje algoritma GOST 28147-89 ima dimenziju od 256 bita, a Kx je njegov 32-bitni dio, odnosno 256-bitni ključ za šifriranje je predstavljen kao konkatenacija 32-bitnih potključeva (slika 3.2). :

SH ATI, AG2, YU, AG4, K5, KB, K7.

U procesu enkripcije koristi se jedan od ovih potključeva, ovisno o okruglom broju i načinu rada algoritma.

Rice. 3.1. Algoritamska shema GOST 28147-

Rice. 3.2. Algoritamski ključ za šifriranje GOST 28147-89

2. Zamjena tablice. Nakon što se ključ preklopi, podblok / VI se dijeli na 8 dijelova od 4 bita, od kojih se vrijednost svakog pojedinačno zamjenjuje u skladu sa zamjenskom tablicom za ovaj dio podbloka. Zamjenske kutije (S-kutije) se često koriste u modernim algoritmima šifriranja, pa ih vrijedi detaljnije razmotriti.

Zamjena tablice se koristi na ovaj način: blok podataka određene dimenzije (u ovom slučaju 4-bitni) se dovodi na ulaz, čiji numerički prikaz određuje broj izlazne vrijednosti. Na primjer, imamo S-box sljedećeg oblika:

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

Neka na ulaz dođe 4-bitni blok "0100", odnosno vrijednost 4. Prema tabeli, izlazna vrijednost će biti 15, tj. "1111" (0 se zamjenjuje sa 4, 1 se zamjenjuje sa 11, vrijednost 2 je nepromijenjena, itd.).

Kao što vidite, shema algoritma je vrlo jednostavna, što znači da najveće opterećenje enkripcije podataka pada na zamjenske tablice. Nažalost, algoritam ima svojstvo da postoje „slabe“ tabele supstitucije, pri korišćenju kojih se algoritam može otkriti kriptoanalitičkim metodama. Slabi uključuju, na primjer, tablicu u kojoj je izlaz jednak ulazu:

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

3. Pobitno ciklično pomak ulijevo za 11 bita.

Algoritamski režimi rada

GOST 28147-89 algoritam ima 4 načina rada:

□ jednostavan način zamjene;

□ gama mod;

P gama mod sa povratnom spregom;

□ način proizvodnje simulatora.

Ovi načini se donekle razlikuju od općeprihvaćenih (opisanih u odjeljku 1.4), pa ih vrijedi detaljnije razmotriti.

Ovi načini imaju različite svrhe, ali koriste istu transformaciju šifriranja opisanu gore.

Jednostavan način zamjene

U načinu jednostavne zamjene, 32 kruga opisana gore se jednostavno izvode za šifriranje svakog 64-bitnog bloka informacija. 32-bitni potključevi se koriste u sljedećem redoslijedu:

□ KO, Kl, K2, KZ, K4, K5, Kb, AG7, KO, ATI itd. - u krugovima od 1. do 24.;

□ K1, Kb, K5, K4, KZ, K2, K \, KO — u krugovima od 25. do 32.

Dešifriranje u načinu jednostavne zamjene izvodi se na potpuno isti način, ali s malo drugačijim slijedom potključeva:

□ KO, K \, K2, KZ, K4, K5, Kb, KP - u krugovima od 1 do 8;

□ KP, Kb, K5, K4, KZ, K2, K \, KO, K1, Kb itd. - u krugovima od 9. do 32.

Slično standardnom ECB modu, zbog odvojenog šifriranja blokova, način jednostavne zamjene se ne preporučuje da šifrira same podatke; trebalo bi da se koristi samo za šifrovanje drugih ključeva za šifrovanje u šemama sa više ključeva.

Gama mod

U gama modu (slika 3.3), svaki blok otvorenog teksta se dodaje po bitu po modulu 2 sa 64-bitnim gama blokom šifre. Šifra gama je poseban niz koji se generira korištenjem gore opisanih transformacija kako slijedi:

1. U registre N1 i N2 upisuje se njihovo početno popunjavanje - 64-bitna vrijednost, nazvana "sinhro-burst" (sinhro-burst, u praksi, je analog vektora inicijalizacije u CBC, CFB i OFB modovima).

2. Šifrovanje sadržaja registara / VI i N2 (u ovom slučaju - sinhronizovane poruke) vrši se u režimu jednostavne zamene.

3. Sadržaj N1 se dodaje po modulu (2 32 - 1) sa konstantom CI = 2 24 + 2 16 + 2 8 + 4, rezultat sabiranja se upisuje u registar / VI.

4. Sadržaj N2 se dodaje po modulu 2 sa konstantom C2 = 2 24 + 2 16 + 2 8 +1, rezultat sabiranja se upisuje u registar N2.

5. Sadržaj registara / VI i N2 izlaze kao 64-bitni gama blok šifre (tj. u ovom slučaju / VI i N2 čine prvi gama blok).

6. Ako je potreban sljedeći blok gama (tj. trebate nastaviti šifriranje ili dešifriranje), vraćate se na korak 2.

Za dešifriranje, gama se generiše na sličan način, a zatim se operacija XOR ponovo primjenjuje na šifrirani tekst i gama bitove.

Za generiranje istog raspona šifre, korisnik koji dešifrira kriptogram mora imati isti ključ i istu sinkroniziranu vrijednost koje su korištene za šifriranje informacija. U suprotnom, neće biti moguće dobiti originalni tekst iz šifrovanog.

U većini implementacija algoritma GOST 28147-89, poruka za sinhronizaciju nije tajni element, međutim, poruka za sinhronizaciju može biti tajna kao i ključ za šifrovanje. U ovom slučaju možemo pretpostaviti da je efektivna dužina ključa algoritma (256 bita) povećana za još 64 bita sinhronizacione poruke, što se može smatrati dodatnim elementom ključa.

Gama način rada sa povratnim informacijama

U gama modu sa povratnom spregom, kao popunjavanje registara /VI i L/2, počevši od 2. bloka, ne koristi se prethodni gama blok, već rezultat šifriranja prethodnog bloka običnog teksta (slika 3.4) . Prvi blok u ovom načinu rada se generira potpuno slično prethodnom.

Rice. 3.4. Generisanje gama šifre u gama modu povratne sprege

Način proizvodnje simulatora

Prefiks je kriptografska kontrolna suma izračunata pomoću ključa za šifriranje za provjeru integriteta poruka. Za njegovo izračunavanje postoji poseban način algoritma GOST 28147-89.

Generiranje simulatora se izvodi na sljedeći način:

1. Prvi 64-bitni blok informacija, za koji se izračunava prefiks, upisuje se u registre N1 i N2 i šifrira u reduciranom načinu jednostavne zamjene, u kojem se izvodi prvih 16 krugova od 32.

2. Dobijeni rezultat se sumira po modulu 2 sa sljedećim blokom informacija, pohranjujući rezultat u N1 i N2.

3. M i N2 se ponovo šifriraju u reduciranom načinu jednostavne zamjene, i tako do posljednjeg bloka informacija.

Imitator je 64-bitni rezultujući sadržaj registara N1 i N2, ili njegov dio. Koristi se najčešće korišćeni 32-bitni prefiks, odnosno polovina sadržaja registra. Ovo je dovoljno, jer, kao i svaki kontrolni zbroj, simulator je prvenstveno dizajniran za zaštitu od slučajnog izobličenja informacija. Za zaštitu od namjerne izmjene podataka koriste se i druge kriptografske metode - prije svega, elektronski digitalni potpis (vidi odjeljak 1.1).

Imitator se koristi na sljedeći način:

1. Prilikom šifriranja bilo koje informacije, prefiks otvorenog teksta se izračunava i šalje zajedno sa šifriranim tekstom.

2. Nakon dešifriranja, prefiks se ponovo izračunava i upoređuje sa poslanim.

3. Ako se izračunati i poslani prefiksi ne poklapaju - šifrirani tekst je izobličen tokom prijenosa ili su korišteni netačni ključevi tokom dešifriranja.

Prefiks je posebno koristan za provjeru ispravnog dešifriranja ključnih informacija kada se koriste sheme s više ključeva.

Imitator je neki analog koda za autentifikaciju MAC poruke koji se izračunava u CBC modu; razlika je u tome što se poruka sinhronizacije ne koristi u izračunavanju prefiksa, dok se vektor inicijalizacije koristi u izračunavanju MAC-a.

Kriptografska snaga algoritma

Godine 1994., opis algoritma GOST 28147-89 preveden je na engleski i objavljen; nakon toga su se počeli pojavljivati ​​rezultati njegove analize koju su izvršili strani stručnjaci; međutim, tokom značajnog perioda nije utvrđeno da se napadi približavaju izvodljivim.

□ velika dužina ključa - 256 bita; zajedno sa tajnom sinhronizacionom porukom, efektivna dužina ključa se povećava na 320 bita;

□ 32 kruga transformacija; nakon 8 rundi postiže se puni efekat disperzije ulaznih podataka: promjena jednog bita bloka otvorenog teksta utječe na sve bitove bloka šifriranog teksta, i obrnuto, odnosno postoji višestruka sigurnosna margina.

Razmotrite rezultate kriptoanalize algoritma GOST 28147-89.

Analiza zamjenskih tablica

Pošto tabele zamene nisu date u standardu, brojni radovi (na primer, c) sugerišu da "kompetentna organizacija" može proizvesti i "dobre" i "loše" tabele zamene. Međutim, najpoznatiji stručnjak Bruce Schneier takve pretpostavke naziva "glasinama". Jasno je da kriptografska snaga algoritma u velikoj mjeri ovisi o svojstvima korištenih zamjenskih tablica, shodno tome, postoje slabe zamjenske tablice (vidi primjer iznad), čija upotreba može pojednostaviti napad na algoritam. Ipak, mogućnost korištenja različitih zamjenskih tablica čini se vrlo vrijednom idejom, u prilog kojoj se mogu navesti sljedeće dvije činjenice iz istorije standarda DES enkripcije (pogledajte odjeljak 3.15 za detalje):

□ napadi koji koriste i linearnu i diferencijalnu kriptoanalizu DES algoritma koriste specifične karakteristike zamjenskih tablica; kada koristite druge tabele, kriptoanaliza će morati da počne iznova;

□ Učinjeni su pokušaji da se ojača DES u odnosu na linearnu i diferencijalnu kriptoanalizu korištenjem robusnijih tablica zamjene; takve tabele, koje su zaista robusnije, predložene su, na primer, u algoritmu s 5 DES; ali, nažalost, bilo je nemoguće zamijeniti DES sa s 5 DES, pošto su zamjenske tablice strogo definirane u standardu, odnosno implementacija algoritma vjerovatno ne podržava mogućnost promjene tabela na druge.

U brojnim radovima (na primjer, i) pogrešno se zaključuje da tajne tablice zamjena algoritma GOST 28147-89 mogu biti dio ključa i povećati njegovu efektivnu dužinu (što je beznačajno, budući da algoritam ima veoma veliki 256-bitni ključ). Međutim, rad je pokazao da se tajne tabele zamjene mogu izračunati korištenjem sljedećeg napada, koji se može primijeniti u praksi:

1. Postavlja se nulti ključ i vrši se traženje "nulte vektora", odnosno vrijednosti z = / (0), gdje je / () funkcija kruga algoritma. Ova faza traje oko 2 operacije šifriranja.

2. Koristeći nulti vektor izračunavaju se vrijednosti zamjenskih tablica, što ne traje više od 2 11 operacija.

Modifikacije algoritama i njihova analiza

U radu je izvršena kriptoanaliza modifikacija algoritma GOST 28147-89:

□ GOST-H algoritam, u kojem se u odnosu na originalni algoritam mijenja redoslijed korištenja potključeva, naime, u krugovima od 25. do 32. potključevi se koriste u direktnom redoslijedu, odnosno na isti način kao u prethodne runde algoritma;

□ GOST® algoritam sa 20 krugova, koji koristi XOR za ključanje umjesto sabiranja po modulu 32.

Na osnovu rezultata analize, zaključeno je da su GOST-H i GOST © slabiji od originalnog algoritma GOST 28147-89, budući da oba imaju klase slabih ključeva. Vrijedi napomenuti da u dijelu GOST © kriptoanalize, rad ponavlja od riječi do riječi odjeljak posvećen kriptoanalizi algoritma GOST 28147-89, koji je 2000. godine objavio dobro poznato djelo (bez ikakvih referenci na original) . To dovodi u sumnju profesionalnost autora rada i ostalih njegovih rezultata.

U radu je predložena vrlo zanimljiva modifikacija algoritma: tabele S \… Ss moraju biti različite; u svakom krugu algoritma, moraju se preurediti prema određenom zakonu. Ova permutacija može ovisiti o ključu za šifriranje ili može biti tajna (to jest, može biti dio ključa za šifriranje veći od originalnog 256-bitnog ključa). Obje ove opcije, prema njihovim autorima, značajno povećavaju otpornost algoritma na linearnu i diferencijalnu kriptoanalizu.

I još jedna modifikacija koja se odnosi na tabele zamene data je u radu, koja analizira jednu od mogućih metoda za izračunavanje tabela supstitucije na osnovu ključa za šifrovanje. Autori rada su zaključili da takva zavisnost slabi algoritam, jer dovodi do prisustva slabih ključeva i do nekih potencijalnih ranjivosti algoritma.

Kompletna analiza algoritma

Postoje napadi na kompletan GOST 28147-89 bez ikakvih modifikacija. Jedan od prvih javnih radova u kojem je izvršena analiza algoritma - dobro poznato djelo - posvećen je napadima koji iskorištavaju slabosti postupka proširenja ključa niza poznatih algoritama za šifriranje. Konkretno, potpuni algoritam GOST 28147-89 može se razbiti korištenjem diferencijalne kriptoanalize na povezanim ključevima, ali samo ako se koriste slabe tablice zamjene. Varijanta algoritma od 24 kruga (u kojoj nedostaje prvih 8 rundi) otvara se na isti način za bilo koju tablicu zamjene, ali jake tablice zamjene (na primjer, prikazane u c) čine takav napad potpuno nepraktičnim.

Domaći naučnici A.G. Rostovtsev i E.B. Makhovenko su 2001. godine u svom radu predložili fundamentalno novu metodu kriptoanalize (prema autorima, mnogo efikasniju od linearne i diferencijalne kriptoanalize) formiranjem objektivne funkcije iz poznatog otvorenog teksta koji mu odgovara šifrovanom i željenom ključnu vrijednost i pronalaženje njenog ekstrema koji odgovara pravoj vrijednosti ključa. Također su pronašli veliku klasu slabih ključeva za algoritam GOST 28147-89, koji omogućavaju razbijanje algoritma koristeći samo 4 odabrana obična teksta i odgovarajuće šifrirane tekstove prilično niske složenosti. U radu je nastavljena kriptoanaliza algoritma.

Grupa stručnjaka iz Koreje je 2004. godine predložila napad kojim je, koristeći diferencijalnu kriptoanalizu na povezanim ključevima, moguće dobiti sa 91,7% vjerovatnoće 12 bitova tajnog ključa. Za napad je potrebno 2 35 odabranih otvorenih tekstova i 2 36 operacija šifriranja. Kao što vidite, ovaj napad je praktično beskoristan za pravi napad na algoritam.

Algoritam GOST 28147-89 i šifra "Magma" (GOST R 34.12-2015)

Opća šema algoritma. Algoritam opisan u GOST 28147-89 „Sistemi za obradu informacija. Kriptografska zaštita. Algoritam kriptografske transformacije“ je domaći standard za simetrično šifrovanje (pre 1. januara 2016.) i obavezan je za implementaciju u sertifikovane alate za zaštitu kriptografskih informacija koji se koriste u državnim informacionim sistemima i, u nekim slučajevima, u komercijalnim sistemima. Certifikacija sredstava kriptografske zaštite informacija potrebna je za zaštitu informacija koje predstavljaju državnu tajnu Ruske Federacije i informacija čija se povjerljivost mora osigurati u skladu s važećim zakonodavstvom. Takođe u Ruskoj Federaciji preporučuje se upotreba algoritma GOST 28147-89 za zaštitu bankarskih informacionih sistema.

GOST 28147-89 algoritam (slika 2.21) se zasniva na Feistelovoj šemi i šifruje informacije u blokovima od 64 bita, koji su podeljeni u dva podbloka od 32 bita (I, i R). Podblok R, se obrađuje pomoću funkcije okrugle transformacije, nakon čega se njegova vrijednost dodaje vrijednosti podbloka Lj, a zatim se podblokovi zamjenjuju. Algoritam ima 16 ili 32 runde, ovisno o načinu šifriranja (proračun imitacije inserta ili drugi načini šifriranja).

Rice. 2.21.

U svakom krugu algoritma izvode se sljedeće transformacije.

1. Preklapanje ključa. Podblok sadržaja R i dodat modulo 2 32 sa okruglim ključem K. Kj je 32-bitni dio originalnog ključa koji se koristi kao okrugli. GOST 28147-89 ns algoritam koristi proceduru proširenja ključa, originalni 256-bitni ključ za šifriranje je predstavljen kao konkatenacija (konkatenacija) osam 32-bitnih potključeva (slika 2.22): K 0, K (, K t K, K A, K 5, K 6, K 7.

Proces šifriranja koristi jedan od ovih potključeva. TO

Od 1. do 24. kola - direktno:

Od 25. do 32. kola - obrnutim redoslijedom:

Rice. 2.22. Struktura ključa za šifriranje algoritma GOST 28147-89

2. Zamjena tablice. Nakon što je ključ primijenjen, podblok R i podijeljen je na osam dijelova ali 4 bita, od kojih se vrijednost svakog pojedinačno zamjenjuje u skladu sa svojom zamjenskom tablicom (S-box). Koristi se ukupno osam S-kutija - S 0, S, S 2, S 3, S 4, S 5, S 6, S 7. Svaki S-blok algoritma GOST 28147-89 je vektor (jednodimenzionalni niz) sa ^ elementima numeriranim od 0 do 15. Vrijednosti S-bloka su 4-bitni brojevi, tj. cijeli brojevi od 0 do 15.

Iz tabele S-box se uzima element čiji se redni broj poklapa sa vrednošću koja je došla na supstitucijski ulaz.

Primjer 2.6.

Neka postoji S-blok sljedećeg oblika:

Neka se na ulaz ovog S-kutija zada vrijednost 0100 2 = 4. Izlaz S-kutije će biti 4. element tabele zamjene, tj. 15 = 1111 2 (elementi su numerisani počevši od nule).

supstitucijske osobe nisu definisane standardom, kao što je to učinjeno, na primjer, u DES šifri. Promjenjive vrijednosti tablica zamjene značajno komplikuju kriptoanalizu algoritma. Istovremeno, robusnost algoritma suštinski zavisi od njihovog pravilnog izbora.

Nažalost, algoritam GOST 28147-89 ima "slabe" tablice zamjene, pri korištenju kojih se algoritam može lako otkriti kriptoanalitičkim metodama. Među "slabima" je, na primjer, trivijalna tablica zamjena, u kojoj je ulaz jednak izlazu (tabela 2.16).

Tabela 2.16

Primjer slabog S-boxa

Smatra se da specifične vrijednosti zamjenskih tablica treba čuvati u tajnosti i da su dugoročno ključni element, tj. vrijede mnogo duže od pojedinačnih ključeva. Međutim, tajne vrijednosti zamjenskih tablica nisu dio ključa i ne mogu povećati njegovu efektivnu dužinu.

Zaista, tabele tajnih zamjena mogu se izračunati korištenjem sljedećeg napada, koji se može primijeniti u praksi:

• postavlja se nulti ključ i vrši se pretraga "nulti vektora", tj. značenje z = F ( 0), gdje Ž - funkcija kružne transformacije algoritma. Ovo zahtijeva oko 2 32 testne operacije šifriranja;
• pomoću nultog vektora izračunavaju se vrijednosti tablica zamjene, što ne traje više od 2 11 operacija.

Međutim, čak i ako se naruši povjerljivost tablica zamjene, snaga šifre ostaje izuzetno visoka i ne pada ispod prihvatljive granice.

Također se pretpostavlja da su zamjenske tablice zajedničke za sve čvorove šifriranja unutar jednog sistema kriptografske zaštite.

Poboljšanje strukture S-boksova jedan je od najintenzivnije istraženih problema u oblasti simetričnih blok šifri. U osnovi, potrebno je da se sve promjene na ulazima S-kutija izlije u nasumično naizgled mijenja izlaz. S jedne strane, što su S-kutije veće, to je algoritam otporniji na metode linearne i diferencijalne kriptoanalize. S druge strane, veliki zamjenski stol je teže dizajnirati.

U modernim algoritmima, S-kutije su obično vektor (jednodimenzionalni niz) koji sadrži 2 "t- bit elementi. Ulaz bloka definira broj elementa čija vrijednost služi kao izlaz S-bloka.

Za dizajn S-kutija postavljen je niz kriterija. Tablica zamjene mora zadovoljiti:

• strogi kriterijum lavine;
• kriterijum nezavisnosti bitova;
• zahtjev nelinearnosti od ulaznih vrijednosti.

Da bi se ispunio posljednji zahtjev, predloženo je specificiranje linearne kombinacije i bitovi ( i = 1, ..., T) vrijednosti tabele zamjene savijene funkcije(eng, savijen - odstupajući, u ovom slučaju - od linearnih funkcija). Bent funkcije čine posebnu klasu Booleovih funkcija koje karakterizira najviša klasa nelinearnosti i usklađenost sa strogim kriterijem lavine.

U nekim radovima se za S-boksove predlaže provjera ispunjenosti garantovanog lavinskog efekta reda y - kada se promijeni jedan ulazni bit mijenjaju se barem izlazni bitovi S-kutije. Svojstvo garantovanog lavinskog efekta reda y od 2 do 5 obezbeđuje dovoljno dobre karakteristike difuzije S-boksova za bilo koji algoritam šifrovanja.

Prilikom dizajniranja dovoljno velikih zamjenskih stolova, mogu se koristiti sljedeći pristupi:

• slučajni odabir (za male S-kutije, može dovesti do stvaranja slabih tablica zamjene);
• slučajni odabir praćen provjerom usklađenosti sa različitim kriterijima i odbacivanjem slabih S-kutija;
• ručni odabir (previše naporan za velike S-blokove);
• matematički pristup, na primjer, generiranje korištenjem savijenih funkcija (ovaj pristup se primjenjuje u CAST algoritmu).

Može se predložiti sljedeći postupak za projektovanje pojedinačnih S-blokova algoritma GOST 28147-89:

• svaki S-box može biti opisan sa četiri logičke funkcije, svaka od funkcija mora imati četiri logička argumenta;
• ove funkcije moraju biti dovoljno složene. Ovaj zahtjev složenosti ne može se formalno izraziti, međutim, kao neophodan uslov, može se zahtijevati da odgovarajuće logičke funkcije, napisane u minimalnom obliku (tj. sa minimalnom mogućom dužinom izraza) koristeći osnovne logičke operacije, ne budu kraće od određena potrebna vrijednost;
• pojedinačne funkcije, čak i korištene u različitim tablicama zamjene, moraju biti dovoljno različite jedna od druge.

Godine 2011. predložen je novi napad „refleksivni sastanak u sredini“, koji neznatno smanjuje otpor GOST 28147-89 (sa 2256 na 2225). Najbolji rezultat kriptoanalize algoritma iz 2012. omogućava smanjenje njegove snage na 2 192, što zahtijeva relativno veliku veličinu šifriranog teksta i količinu unaprijed formiranih podataka. Uprkos predloženim napadima, GOST 28147-89 ostaje praktično stabilan na trenutnom nivou razvoja računarske tehnologije.

Šifra "Magma" (GOST R 34.12-2015). Standard GOST 28147-89 je na snazi ​​u Rusiji više od 25 godina. Tokom ovog vremena, pokazao je dovoljnu izdržljivost i dobru efikasnost softverskih i hardverskih implementacija, uključujući i one na uređajima sa niskim resursima. Iako su predloženi kriptoanalitički napadi koji smanjuju procjenu njegovog otpora (najbolja je do 2.192), oni su daleko od izvodljivih. Stoga je odlučeno da se algoritam GOST 28147-89 uključi u novorazvijeni standard simetričnog šifriranja.

U radnji 2015. usvojena su dva nova nacionalna kriptografska standarda: GOST R 34.12-2015 „Informaciona tehnologija. Zaštita kriptografskih informacija. Blok šifre "i GOST R 34.13-2015" Informaciona tehnologija. Zaštita kriptografskih informacija. Načini rada blok šifri“, koji stupaju na snagu 1. januara 2016.

Standard GOST R 34.12-2015 sadrži opis dvije blok šifre s dužinom bloka od 128 i 64 bita. GOST 28147-89 šifra sa fiksnim nelinearnim supstitucijskim blokovima uključena je u novi GOST R 34.12-2015 kao 64-bitna šifra pod nazivom "Magma".

Ispod su zamjenski blokovi fiksirani u standardu:

Skup S-kutija dat u standardu daje najbolje karakteristike koje određuju otpornost kriptoalgoritma na diferencijalnu i linearnu kriptoanalizu.

Prema tehničkom komitetu za standardizaciju "Kriptografska zaštita informacija" (TC 26), fiksiranje nelinearnih zamjenskih blokova učinit će algoritam GOST 28147-89 ujedinjenijim i pomoći u eliminaciji upotrebe "slabih" nelinearnih zamjenskih blokova. Osim toga, fiksiranje u standard svih dugoročnih parametara šifre zadovoljava prihvaćenu međunarodnu praksu. Novi standard GOST R 34.12-2015 terminološki je i konceptualno povezan sa međunarodnim standardima ISO/IEC 10116 „Informaciona tehnologija. Sigurnosne metode. Načini rada za "-bitne blok šifre" (ISO / IEC 10116: 2006 Informaciona tehnologija - Sigurnosne tehnike - Načini rada za n-bitnu blok šifru) i serije ISO / IEC 18033 "Informaciona tehnologija. Metode i sredstva za osiguranje sigurnosti. Algoritmi šifriranja ": ISO / IEC 18033-1: 2005" Dio 1. Općenito "(ISO / IEC 18033-1: 2005 Informacijska tehnologija - Sigurnosne tehnike - Algoritmi šifriranja - Dio 1: Općenito) i ISO / IEC 18033-3: 2010 "Dio 3. Blok šifre" (ISO / IEC 18033-3: 2010 (Informaciona tehnologija - Sigurnosne tehnike - Algoritmi šifriranja - Dio 3: Blok šifre)).

Standard GOST P 34.12-2015 također uključuje novu blok šifru ("Skakavac") s veličinom bloka od 128 bita. Očekuje se da će ova šifra biti otporna na sve danas poznate napade blok šifre.

Načini rada blok šifri (jednostavna zamjena, gama, gama s povratnom spregom na izlazu, gama s povratnom spregom šifriranog teksta, jednostavna zamjena sa uključivanjem i razvoj imitacije umetka) uključeni su u poseban standard GOST R 34.13-2015, koji odgovara prihvaćena međunarodna praksa. Ovi načini su primjenjivi i na šifru Magma i na novu šifru Grasshopper.

• Izvodi se bitovski kružni pomak ulijevo za 11 bita. Dešifriranje se vrši po istoj šemi, ali s drugačijim rasporedom korištenja ključeva: od 1. do 8. kruga dešifriranja - direktnim redoslijedom: od 9. do 32. kruga dešifriranja - obrnutim redoslijedom: U poređenju sa DES šifra u GOST 28147-89 ima sledeće prednosti: značajno duži ključ (256 bita naspram 56 za DES šifru), napad na koji se bruteforce nabrajanjem skupa ključeva čini nemogućim u ovom trenutku; jednostavan raspored za korištenje ključa, koji pojednostavljuje implementaciju algoritma i povećava brzinu izračunavanja. Dizajn S-blokova GOST 28147-89. Očigledno je da je shema algoritma GOST 28147-89 vrlo jednostavna. To znači da najveće opterećenje enkripcije pada na tablice zamjene. Vrijednosti kartice
• Panasepko S.P. Algoritmi šifriranja: poseban priručnik. SPb.: BHV-Peterburg, 2009.
• Kara O. Odraz napada na šifre proizvoda. URL: http://eprint.iacr.org/2007/043.pdf
• Ruski standard šifriranja: smanjena snaga. URL: http://cryptofaq.ru/index.php/2010-12-23-18-20-21/2010-12-23-18-22-09/90-2011-02-01-07-47- 27
• Achekseev E. K., Smyshlyaev S. V. GOST 28147-89: "Ne žurite da ga sahranite."

Poznati istraživač, osnivač algebarske kriptoanalize, Nicolas Courtois, tvrdi da je GOST blok šifra, koja je u bliskoj budućnosti trebala postati međunarodni standard, zapravo pokvarena i da u budućnosti čeka mnoge publikacije 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 preterivanjama u odnosu na AES, ali je njegov rad tada imao veliki teorijski utjecaj na kriptoanalizu, ali je nije dovelo do praktičnih napada na sam AES). Ali, možda je ovo i pravo upozorenje o početku faze "letelice poniranja u zalet", koja bi mogla završiti urušavanjem nacionalnog standarda šifriranja, kao što je bio slučaj sa algoritmom za heširanje SHA-1 i de facto MD5 algoritam heširanja.

GOST 28147-89 je standardizovan 1989. godine i po prvi put je postao službeni standard za zaštitu povjerljivih informacija, ali je specifikacija šifre ostala zatvorena. 1994. godine standard je deklasifikovan, objavljen i preveden na engleski jezik. Po analogiji sa AES-om (i za razliku od DES-a), GOST-u je dozvoljeno da štiti poverljive informacije bez ograničenja, u skladu sa načinom na koji je to navedeno u ruskom standardu. To. GOST nije analog DES-a, već je konkurent 3-DES-u sa tri nezavisna ključa ili AES-256. Očigledno, GOST je prilično ozbiljna šifra koja zadovoljava vojne kriterije, stvorena s očekivanjem najozbiljnijih aplikacija. Najmanje dva seta GOST S-kutija su identifikovana na osnovu aplikacija koje koriste ruske banke. Ove banke moraju voditi tajnu komunikaciju sa stotinama filijala i zaštititi milijarde dolara od lažne krađe.

GOST je blok šifra sa jednostavnom Feistelovom strukturom, sa veličinom bloka od 64 bita, 256-bitnim ključem i 32 runde. Svaka runda sadrži modulo 2 ^ 32 dodavanja ključa, set od osam 4-bitnih S-kutija i jednostavan 11-bitni ciklički pomak. Karakteristika GOST-a je mogućnost čuvanja S-blokova u tajnosti, što se može predstaviti kao drugi ključ koji povećava efektivni materijal ključa na 610 bita. Jedan set S-kutija objavljen je 1994. godine kao dio specifikacije heš funkcije GOST-R 34.11-94 i, kako je napisao Schneier, koristila ga je Centralna banka Ruske Federacije. Takođe je uključen u RFC4357 u delu "id-GostR3411-94-CryptoProParamSet". Postojala je greška u izvornim kodovima na kraju Schneierove knjige (u S-box redoslijedu). Najpreciznija referentna implementacija izvornog ruskog porijekla sada se može naći u OpenSSL biblioteci. Ako se negdje koriste tajne S-kutije, onda se mogu izvući iz softverskih implementacija i iz mikro krugova, u stvari, objavljeni su odgovarajući radovi.

GOST je ozbiljan konkurent

Pored veoma velike veličine ključa, GOST ima znatno niže troškove izvršenja u poređenju sa AES i drugim sličnim sistemima za šifrovanje. U stvari, košta mnogo manje od AES-a, koji zahtijeva četiri puta više hardverskih logičkih kapija za mnogo nižu deklariranu sigurnost.

Nije iznenađujuće što je GOST postao internet standard, a posebno je uključen u mnoge kripto biblioteke kao što su OpenSSL i Crypto++, i postaje sve popularniji izvan zemlje porijekla. Godine 2010. GOST je proglašen za ISO standardizaciju kao svjetski standard za šifriranje. Izuzetno mali broj algoritama je uspio 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. GOST se predlaže da se doda istom standardu ISO / IEC 18033-3.

Po prvi put u istoriji industrijske standardizacije imamo posla sa ovako konkurentnim algoritmom u smislu optimalnosti između cene i nivoa bezbednosti. GOST ima 20 godina napora u kriptoanalizi i donedavno njegova sigurnost vojnog nivoa nije dovedena u pitanje.

Kako je autor nedavno saznao iz privatne prepiske, većina zemalja se usprotivila GOST-u na ISO glasanju u Singapuru, ali će se rezultati ovog glasanja ipak razmatrati na plenarnom sastanku ISO SC27, tako da je GOST još uvijek u procesu standardizacije u vrijeme objavljivanje ovog rada.

Stručna mišljenja o GOST-u

Nijedna od dostupnih informacija i literature o GOST-u ne daje osnove za vjerovanje da šifra može biti nesigurna. Naprotiv, velika veličina ključa i veliki broj krugova čine GOST na prvi pogled pogodnim za višedecenijsko korištenje.

Svako ko poznaje Mooreov zakon shvata da će, u teoriji, 256-bitni ključevi ostati sigurni najmanje 200 godina. GOST su opsežno istraživali vodeći stručnjaci iz oblasti kriptografije, poznati u oblasti analize blok šifre, kao što su Schneier, Biryukov, Dankelman, Wagner, mnogi australski, japanski i ruski naučnici, stručnjaci za kriptografiju iz ISO-a i svi istraživači. izrazio da sve izgleda ovako da može ili treba da bude bezbedan. Iako je došlo do širokog shvaćanja da je sama struktura GOST-a izuzetno slaba, na primjer, u poređenju sa DES-om, posebno, difuzija nije tako dobra, međutim, to je uvijek bilo zbog činjenice da bi to trebalo nadoknaditi veliki broj krugova (32), kao i dodatnu nelinearnost i difuziju koju obezbjeđuje dodavanje modula.

Biryukov i Wagner su napisali: „Veliki broj krugova (32) i dobro proučena Feistelova konstrukcija, u kombinaciji sa uzastopnim Šenonovim permutacijama, daju čvrstu osnovu za GOST bezbednost.“ U istom djelu čitamo: "nakon značajnog ulaganja vremena i truda, nije postignut napredak u kriptoanalizi standarda u otvorenoj literaturi." Dakle, nije bilo značajnih napada koji bi omogućili dešifriranje ili oporavak ključa u realnom scenariju gdje se GOST koristi u šifriranju s mnogo različitih nasumičnih ključeva. Nasuprot tome, postoji mnogo radova poznatih o napadima na slabe ključeve u GOST-u, napadima sa povezanim ključevima, napadima na vraćanje tajnih S-kutija. Na Crypto-2008 predstavljeno je hakovanje hash funkcije zasnovane na ovoj šifri. U svim napadima, napadač ima znatno veći nivo slobode nego što je uobičajeno dozvoljeno. Do sada nisu pronađeni ozbiljni kriptografski napadi na GOST u tradicionalnim primjenama enkripcije korištenjem nasumično odabranih ključeva, što je 2010. bilo izraženo posljednjom frazom: „uprkos značajnim naporima kriptoanalitičara u posljednjih 20 godina, GOST još nije cracked" (Axel Poschmann, San Ling i Huaxiong Wang: 256-bitni standardizirani kripto za 650 GE GOST ponovo pregledan, u CHES 2010, LNCS 6225, str. 219-233, 2010).

Linearna i diferencijalna analiza GOST

U Schneierovoj dobro poznatoj knjizi čitamo: "Protiv diferencijalne i linearne kriptoanalize, GOST je vjerovatno robusniji od DES-a." Glavnu procjenu sigurnosti GOST-a dali su 2000. Gabidulin i dr. Njihovi rezultati su vrlo impresivni: sa postavljenim nivoom sigurnosti od 2 ^ 256, pet rundi je dovoljno da se GOST zaštiti od linearne kriptoanalize. Štoviše, čak i nakon zamjene S-kutija identičnim i jedine operacije nelinearne šifre - dodavanja mod 2 ^ 32 - šifra je i dalje otporna na linearnu kriptoanalizu nakon 6 krugova od 32. GOST diferencijalna kriptoanaliza izgleda relativno lakše i privlači više pažnje. Za nivo 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. aprila 2001.) pretpostavili su dovoljnu izdržljivost pri 7 rundi . Prema njihovim riječima, razbijanje GOST-a u više od pet rundi je "izuzetno teško". Štaviše, dva japanska istraživača su pokazala da klasični direktni diferencijalni napad s jednom diferencijalnom karakteristikom ima izuzetno malu vjerovatnoću prolaska kroz veliki broj rundi. Na osnovu činjenice da se proučava dovoljno "dobre" iterativne diferencijalne karakteristike za ograničen broj rundi (koja sama po sebi ima vjerovatnoću da prođe ne bolju od 2-11,4 po rundi), vrijednost skupa odgovarajućih ključeva je manja od polovine . Za puni GOST, takav napad s jednom karakteristikom će raditi samo sa zanemarljivim dijelom ključeva reda 2-62 (a čak i u ovom malom dijelu imat će vjerovatnoću da prođe ne više od 2-360 ).

Sofisticiraniji napadi uključuju višestruke diferencijale koji slijede određene obrasce, kao što je korištenje pojedinačnih S-boksova koji imaju nulte diferencijale dok drugi bitovi imaju različite od nule. Govorimo o diskriminirajućim napadima na osnovu loših difuzijskih svojstava GOST-a. Najbolji od takvih napada radi protiv 17 rundi GOST-a, ovisi o ključu i ima izuzetno slab diskriminator od nasumičnih podataka na samom izlazu, tako da se nekako može koristiti za dobivanje informacija o ključu.

Skliznite i odbijte napade

Prema Biryukovu i Wagneru, GOST struktura, koja uključuje obrnuti redoslijed potključeva u posljednjim rundama, čini ga otpornim na napade klizanja (tzv. "slide napadi"). Međutim, zbog prisustva velike samosličnosti u šifri, ovo omogućava napade inverzije ključa na kombinacije fiksnih tačaka i svojstava "refleksije" (tzv. "reflektivni 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đe koriste refleksiju i zapravo su razbili GOST, koji je predstavljen na konferenciji FSE 2011. Ove napade je takođe nezavisno otkrio autor ovog rada. Za napad je potrebno 2 ^ 132 bajta memorije, što je zapravo gore od sporijih napada s manjim zahtjevima za memorijom.

Brojni novi napadi samosličnosti rade protiv svih GOST ključeva i omogućavaju vam da razbijete cijeli GOST sa 256-bitnim ključem, a ne samo za slabe ključeve, kao što je to bilo prije. Svi ovi napadi zahtijevaju znatno manje memorije i znatno su brži.

Ovi novi napadi se mogu posmatrati kao primjeri nove opće paradigme za kriptoanalizu blok-šifara pod nazivom "algebarsko smanjenje složenosti", koja generalizira ove napade na mnoge posebne slučajeve napada s poznatim fiksnim točkama, slajdovima, involucijama i ciklusima. Važno je da u porodici svih ovih napada postoje oni koji omogućavaju kriptoanalizu GOST-a bez ikakvih refleksija i bez ikakvih simetričnih tačaka koje se pojavljuju u toku proračuna. Jedan primjer je jednostavan GOST hakerski napad bez refleksije u ovom radu.

Algebarska kriptanaliza i napadi niske složenosti podataka na šifre redukovanih rundi

Algebarski napadi na blok i stream šifre mogu se predstaviti kao problem rješavanja velikog sistema Bulovih algebarskih jednadžbi koji prati geometriju i strukturu određene kriptografske šeme. Sama ideja seže do Shannon. U praksi je predstavljen za DES (prvi je predstavljen od strane autora ovog rada) kao formalna metoda kodiranja i može razbiti 6 rundi u samo jednom poznatom otvorenom tekstu. Manipulacija jednadžbom je bazirana na XL algoritmima, Gröbnerovim bazama, ElimLin metodi, SAT rješavačima.

U praksi, algebarski napadi su implementirani na vrlo mali broj rundi blok šifri, ali su već doveli do pucanja stream šifri, a ima i uspjeha u razbijanju ultra-lakih šifri za mikro-opremu. Zbog poteškoća u veličini memorije i procjenama troškova računanja, oni se kombiniraju s drugim napadima.

Kako hakovati GOST?

Algebarski napad na potpuni GOST detaljnije je predstavljen u ovoj publikaciji. U prethodnom radu autor je već naveo 20 algebarskih napada na GOST i očekuje ih veliki broj u bliskoj budućnosti. Napad predložen u ovom radu nije najbolji od njih, ali otvara lak (barem za razumijevanje kriptografa) put za kasniji razvoj kako bi se stvorila specifična metodologija za razbijanje GOST-a.

Praktični rezultat je još uvijek skroman: 2 ^ 64 poznatog otvorenog teksta i 2 ^ 64 memorije za pohranjivanje parova otvorenog teksta / šifriranog teksta omogućavaju razbijanje GOST 2 ^ 8 brže od jednostavne grube sile. Ali u smislu kriptoanalize, ovo čini izjavu da je "GOST hakovan" potpuno poštena.

zaključci

GOST je dizajniran da pruži vojni nivo sigurnosti u narednih 200 godina. Većina vodećih stručnjaka koji su proučavali GOST složili su se da "uprkos značajnim kriptoanalitičkim naporima tokom 20 godina, GOST još nije razbijen." 2010. GOST je promovisan u ISO 18033 kao globalni standard za šifrovanje.

Temelj ideja o algebarskoj kriptoanalizi nastao je prije više od 60 godina. Ali tek u posljednjih 10 godina razvijeni su efikasni softverski alati za (djelimično) rješavanje mnogih NP-potpunih problema. Određeni broj stream šifri je razbijen. Samo jedna blok šifra je razbijena ovom metodom - sam slab KeeLoq. U ovom radu autor razbija važnu, stvarno korištenu GOST šifru. On napominje da je ovo prvi put u istoriji da je standardizovana šifra stanja razbijena algebarskom kriptoanalizom.

Jednostavan napad "MITM sa refleksijom" na GOST već je predstavljen na konferenciji FSE 2011. U radu o kojem se govori u ovom članku, predstavljen je još jedan napad samo da bi ilustrovao činjenicu koliko se napada na GOST već pojavilo sada, od kojih su mnogi su brži, a algebarski napad zahtijeva mnogo manje memorije i otvara gotovo neiscrpan prostor mogućnosti da protivnik napadne šifru na različite načine. Takođe u ovom radu je pokazano da nema potrebe za korišćenjem svojstva refleksije za hakovanje.

Autor tvrdi da je očigledno da GOST ima ozbiljne nedostatke i da sada ne obezbeđuje nivo trajnosti koji zahteva ISO. Mnogi napadi na GOST predstavljeni su u okviru potvrde paradigme smanjenja algebarske složenosti.

Na kraju, istraživač posebno ističe neke činjenice koje još nisu dostupne čitaocu, ali su istraživaču poznate, a koje su važne u procesu ISO standardizacije. Ovaj napad nije samo "certifikacijski" napad na GOST, koji je brži od brute force brute force napada. U stvari, standardizacija GOST-a bi sada bila izuzetno opasna i neodgovorna. To je zato što su neki od napada praktični. U praksi, neki GOST ključevi se čak mogu dešifrirati, bilo da su slabi ključevi ili ključevi iz privatnih stvarnih aplikacija GOST-a. U prethodnom radu autor je detaljno razmatrao slučajeve mogućnosti praktičnih napada. Značajno je da je "ovo prvi put u istoriji da je ozbiljna standardizirana blok šifra dizajnirana da zaštiti vojne tajne i dizajnirana da zaštiti državne tajne za vlade, velike banke i druge organizacije bila ugrožena matematičkim napadom."