Algoritm de criptare GOST 28147-89. Metodă simplă de înlocuire. - Arhiva WASM.RU
„Cât timp ești în viață, nu muri, aruncă o privire la această lume.
Mulți de aici au un suflet mort - sunt morți înăuntru.
Dar ei merg și râd, fără să știe că nu sunt,
Nu-ți grăbi ceasul morții ”, mi-a spus ea.Aria, „Acolo sus”
2.1 rețele Feistel.
2.2 Cifra bloc GOST 28147-893.1 Informatie cheie
3.2 Etapa principală a transformării cripto3.3 Bucle de bază:“ 32-Z” , “ 32-R” .
4.1 Implementarea etapei principale a transformării cripto
4.2 Creșterea vitezei algoritmului
5. Cerințe de informații cheie
6. Lista literaturii folosite
7. Mulțumiri.Introducere.
Acest document este încercarea mea de a descrie o metodă pentru pur și simplu înlocuirea algoritmului de criptare GOST 28147-89 cu cel mai simplu, dar, totuși, limbaj competent din punct de vedere tehnic. După ce a citit primele șase puncte, cititorul își va da cu părerea despre cum am făcut-o.
Pentru ca munca mea să ofere mai multe beneficii, vă recomand să vă înarmați cu lucrările autorilor indicați în lista literaturii folosite. De asemenea, se recomandă ca calculatorul să aibă o funcție pentru calcularea operației. XOR de cand citirea articolului presupune că cititorul a intenționat să studieze acest algoritm de criptare. Deși este potrivit și ca referință, dar am scris acest articol tocmai ca unul de antrenament.
Informații preliminare despre cifrurile bloc.
Înainte de a începe să privim algoritmul, trebuie să ne familiarizăm cu istoria creării acestui tip de cifruri. Algoritmul aparține categoriei de cifruri bloc, în arhitectura cărora informațiile sunt împărțite într-un număr finit de blocuri, cel final poate să nu fie complet. Procesul de criptare are loc pe blocuri complete, care formează cifrul. Blocul final, dacă este incomplet, este completat cu ceva (despre nuanțele completării lui voi spune mai jos) și este criptat la fel ca și blocurile complete. Prin cifru, mă refer la rezultatul funcției de criptare care acționează asupra unei anumite cantități de date pe care utilizatorul le-a trimis pentru criptare. Cu alte cuvinte, un cifru este rezultatul final al criptării.
Istoria dezvoltării cifrurilor bloc este asociată cu începutul anilor 70, când IBM, realizând nevoia de a proteja informațiile atunci când transmite date prin canale de comunicații computerizate, s-a angajat într-un program propriu de cercetare dedicat protecției informațiilor în rețelele electronice, inclusiv criptografie.
Un grup de cercetători - dezvoltatori ai companiei IBM, care a început să studieze sisteme de criptare cu o schemă de utilizare a cheii simetrice, a fost condus de Dr. Horst Feistel.
2.1 Rețele Feistel
Arhitectura noii metode de criptare propusă de Feistel în literatura clasică se numește „Arhitectura Feistel”, dar în prezent în literatura rusă și străină este folosit un termen mai consacrat – „Rețeaua lui Feistel” sau Feistel`s NetWork. Ulterior, pe această arhitectură a fost construit cifrul „Lucifer” - care a fost publicat ulterior și a provocat un nou val de interes în criptografie în general.
Ideea arhitecturii „rețea Feistel” este următoarea: fluxul de informații de intrare este împărțit în blocuri de n biți în dimensiune, unde n este un număr par. Fiecare bloc este împărțit în două părți - L și R, apoi aceste părți sunt introduse într-un cifr de bloc iterativ, în care rezultatul etapei j-a este determinat de rezultatul etapei anterioare j-1! Acest lucru poate fi ilustrat printr-un exemplu:
Orez. 1
Unde, funcția A este acțiunea principală a cifrului bloc. Poate fi o acțiune simplă, cum ar fi o operație XOR, sau poate avea o formă mai complexă ca o secvență a unei serii de acțiuni simple - adăugare modulo, deplasare la stânga, înlocuire de elemente etc., luate împreună, aceste acțiuni simple formează așa-numitul - pasul principal al transformării cripto.
Trebuie remarcat faptul că elementele cheie ale funcționării funcției sunt furnizarea de elemente cheie și operația XOR și, din cât de bine gândită munca acestor operații, se vorbește despre puterea criptografică a cifrului în ansamblu.
Pentru ca ideea rețelelor Feistel să fie în sfârșit clară, luați în considerare cel mai simplu caz prezentat în orez. 1, unde în funcția A - vor exista operații „mod 2” (“xor”), dar aceasta cel mai simplu un caz, într-o situație mai gravă, de exemplu, ascunderea informațiilor de importanță națională, funcția A poate fi mai complexă (din câte am văzut, funcția A este într-adevăr foarte complexă):
Date inițiale:
L = 1110b, R = 0101, K = 1111b
Ia un cifr
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
Să explicăm acțiunile noastre:
1. Această operație este modul de adăugare 2 4. În practică, această operație se rezumă la o simplă adunare, unde trebuie să adunăm două numere și să ignorăm transferul la a 5-a cifră. Deoarece dacă punem exponenți deasupra cifrelor reprezentării binare a unui număr, va exista un exponent patru deasupra celei de-a cincea cifre, să aruncăm o privire la figura de mai jos, care arată acțiunile operației noastre:
Orez. 2
Aici am indicat exponenții cu o săgeată, după cum puteți vedea, rezultatul ar fi trebuit să fie 10100, dar deoarece transferul este ignorat în timpul operațiunii mod 2 4, obținem 0100.
2. Aceasta operatie in literatura de specialitate se numeste mod 2, in limbaj de asamblare este implementata de comanda XOR... Dar numele său mai corect este mod 2 1. Fără această operațiune unică, cu greu este posibil să se construiască un algoritm de criptare rapid, ușor de implementat și, în același timp, astfel încât să fie încă destul de puternic criptografic. Unicitatea acestei operațiuni constă în faptul că ea însăși este opusul! De exemplu, dacă numărul A este XOR cu numărul B, ca rezultat vom obține B, în viitor este suficient să re-XOR numerele B și C între ele pentru a obține valoarea anterioară a lui A!
În această operație, am obținut 1010 având numerele 1110 și 0100, pentru a obține înapoi 1110, este suficient să supraXOR numerele 0100 și 1010! Mai multe detalii despre această operațiune găsiți în articolul, care este atașat site-ului. www.wasm.ru, « Un ghid elementar pentruCRC_ algoritmi de detectare a erorilor»Autorul care Ross N. Williams... Există un punct în această lucrare - „ 5. Aritmetică binară fără silabe". În acest articol este descrisă operația. xor! Exclam pentru că în acest articol această operațiune este atât de programată încât cititorul nu numai că înțelege cum funcționează această operațiune, ci chiar o începe vezi, auzi si simti!
3. Această acțiune este necesară pentru ca, în timpul decriptării, valorile inițiale să poată fi obținute din cifr.
2.2 Cifrul bloc GOST 28147-89
Algoritmul de criptare GOST 28147 - 89 aparține categoriei de cifruri bloc care funcționează conform arhitecturii rețelelor Feistel echilibrate, unde două părți ale blocului de informații selectat sunt de dimensiune egală. Algoritmul a fost dezvoltat în adâncul celui de-al optulea departament al KGB, acum transformat în FAPSI și a fost consacrat ca standard de criptare al Federației Ruse încă din 1989, sub URSS.
Pentru ca această metodă a algoritmului să funcționeze, este necesară împărțirea informațiilor în blocuri de 64 de biți. Generați sau introduceți în sistemul de criptare următoarele informații cheie: cheie și tabel de înlocuire. Alegerea cheii și a tabelului de înlocuire pentru criptare ar trebui luată foarte în serios, deoarece acesta este fundamentul securității informațiilor dvs. Pentru informații despre cerințele impuse cheii și tabelului de substituții, consultați articolul „Cerințe pentru informațiile cheie”.
Când luăm în considerare metoda, nu ne vom concentra asupra acestui lucru, deoarece Acest articol, așa cum am spus mai sus, a fost scris cu scopul de a învăța cititorul cum să cripteze datele prin metoda înlocuirii simple a acestui algoritm de criptare, dar cu siguranță vom aborda această problemă la sfârșitul articolului.
Minimum teoretic.
3.1 Informații cheie
După cum am spus mai sus, următorii sunt implicați activ în criptarea datelor:
3.1.1. O cheie este o secvență de opt elemente, a câte 32 de biți fiecare. În cele ce urmează, vom desemna prin simbolul K, iar elementele din care constă sunt k1, k2, k3, k4, k5, k6, k7, k8.
3.1.2 Tabel de înlocuire - o matrice de opt rânduri și șaisprezece coloane, denumită în continuare - Hij. Fiecare element de la intersecția rândului i și coloanei j ocupă 4 biți.
3.2 Etapa de bază a transformării cripto
Pasul principal în procesul de criptare este - pasul principal al transformării cripto. Aceasta nu este altceva decât o acțiune de criptare a datelor conform unui algoritm specific, doar dezvoltatorii au introdus un nume care este prea greoi.
Înainte de a începe criptarea, blocul este împărțit în două părți L și R, câte 32 de biți fiecare. Elementul cheie este selectat și numai atunci aceste două părți ale blocului, elementul cheie, tabelul de substituție, sunt introduse în funcția pasului principal, rezultatul pasului principal este o iterație a ciclului de bază, care va fi discutată în paragraful următor. Pasul principal constă în următoarele:
- O parte suplimentară a blocului R este însumată cu elementul cheie K mod 2 32. Am descris o operație similară mai sus, aici același lucru doar exponentul nu este „4”, ci „32” - rezultatul acestei operații va fi notat Smod în viitor.
- Împărțiți rezultatul Smod obținut anterior în elemente de patru biți s7, s6, s5, s4, s3, s2, s1, s0 și alimentați-l la funcția de înlocuire. Înlocuirea este următoarea: se selectează elementul Smod - si, începem de la început cu cel mai mic element și înlocuim cu valoarea din tabelul de înlocuiri cu i - rândul și coloana indicate de valoarea elementului s i. Trecem la elementul s i +1 și procedăm în același mod și continuăm așa până când schimbăm valoarea ultimului element Smod - rezultatul acestei operații va fi notat ca, Ssimple.
- În această operație, deplasăm valoarea Ssimple rămasă ciclic cu 11 biți și obținem Srol.
- Selectăm a doua parte a blocului L și o adăugăm mod 2 cu Srol, ca urmare avem Sxor.
- În această etapă, partea blocului L devine egală cu valoarea părții R, iar partea R, la rândul ei, este inițializată cu rezultatul Sxor, iar la aceasta funcția pasului principal este finalizată!
3.3 Cicluri de bază: „32-З”, „32-Р”.
Pentru a cripta informațiile, trebuie să o împărțiți în blocuri de 64 de biți, desigur, ultimul bloc poate fi mai mic de 64 de biți. Acest fapt este călcâiul lui Ahile al acestei metode de „înlocuire ușoară”. Deoarece adăugarea acestuia la 64 de biți este o sarcină foarte importantă pentru a crește puterea criptografică a programului de cifrare și a acestui loc sensibil, dacă este prezent în matricea de informații și este posibil să nu existe (de exemplu, un fișier de 512 octeți! ), Ar trebui tratat cu o mare responsabilitate!
După ce ați împărțit informațiile în blocuri, ar trebui să împărțiți cheia în elemente:
K = k1, k2, k3, k4, k5, k6, k7, k8
Criptarea în sine constă în utilizarea așa-numitelor cicluri de bază. Care, la rândul lor, includ al n-lea număr de pași de bază ai cripto-transformării.
Ciclurile de bază sunt etichetate, cum se spune: n - m. Unde n este numărul de pași de bază ai cripto-transformării în ciclul de bază, iar m este „tipul” ciclului de bază, i.e. despre ce vorbim, despre criptarea „Z” sau criptarea „R” a datelor.
Ciclul de criptare de bază 32-З constă din 32 de pași de bază de cripto-transformare. Blocul N și un element al tastei K sunt introduse în funcția care implementează acțiunile pasului, iar primul pas are loc cu k1, al doilea peste rezultatul obținut cu elementul k2 etc. conform următoarei scheme:
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
Procesul de decriptare pentru 32-P are loc într-un mod similar, dar elementele cheie sunt date în ordine inversă:
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
Practică.
4.1 Implementarea etapei principale a transformării cripto
După ce ne-am familiarizat cu teoria modului de criptare a informațiilor, era timpul să vedem cum are loc criptarea în practică.
Date inițiale:
Luați un bloc de informații N = 0102030405060708h, aici părțile L și R sunt egale:
L = 01020304h, R = 05060708h, să luăm cheia:
K = ca28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(acestea sunt coduri ASCII, pentru a vizualiza reprezentarea hexazecimală, puteți deschide acest fișier în modul vizualizare în Total Commander apăsând tasta F3„Și apoi cheia” 3 "). În această cheie, valorile elementelor vor fi:
k1 = „as28”, k2 = „zw37”, k3 = „q839”, k4 = „7342”
k5 = „ui23”, k6 = „8e2t”, k7 = „wqm2”, k8 = „ewp1”
Luați, de asemenea, următorul tabel de înlocuire:
Orez. 3
Aici, rândurile sunt numerotate de la 0 la 7, coloanele de la 0 la F.
Un avertisment: Toate informațiile, inclusiv cheia cu tabelul de înlocuire, sunt luate ca exemplu pentru luarea în considerare a algoritmului!
Folosind „Date inițiale”, este necesar să se obțină rezultatul acțiunii pasului principal al transformării cripto.
1. Selectați partea R = 05060708h și elementul cheie k1 = 'as28', în formă hexazecimală elementul cheie va arăta astfel: 61733238h. Acum facem operația de însumare mod 2 32:
Orez. 4
După cum puteți vedea în figură, nu am avut un transfer pe 33 de biți marcați cu roșu și cu exponentul „ 32 ". Și dacă am fi avut alte valori ale lui R și elementul cheie, acest lucru s-ar fi putut întâmpla și atunci l-am fi ignorat și am fi folosit în continuare doar biții marcați cu galben.
Efectuez această operație cu comanda assembler adăuga:
; eax = R, ebx = 'as28'
Rezultatul acestei operațiuni Smod = 66793940h
2. Acum cea mai complicată operație, dar dacă te uiți atent la ea, nu mai este atât de groaznică pe cât pare la început. Să ne imaginăm Smod după cum urmează:
Orez. 5
Am încercat să vizualizez elementele Smod din figură, dar voi explica oricum:
s0 = 0, s1 = 4, s2 = 9 etc.
Acum, pornind de la elementul cel mai de jos s0, facem înlocuirea. Amintind paragraful „ 3.2 Etapa de bază a transformării cripto»I - rând, s i - coloana, căutați valoarea în rândul zero și coloana zero:
Fig. 6
Deci valoarea actuală a Smod nu este 6679394 0 h și 6679394 5 h.
Procedăm la înlocuirea s1, adică. patru. Folosind primul rând și a patra coloană (s1 = 4!). Ne uitam la poza:
Orez. 7
Acum valoarea este Smod, nu 667939 4 5h, 667939 2 5h. Presupun că acum algoritmul de înlocuire este clar pentru cititor și pot spune că după rezultatul final al lui Ssimple va avea următoarea valoare - 11e10325h.
Voi vorbi despre modul în care acest lucru este cel mai ușor de implementat sub formă de comenzi de asamblare mai târziu în paragraful următor, după ce voi vorbi despre tabelul extins.
- Trebuie să deplasăm valoarea Ssimple rezultată cu 11 biți la stânga.
Orez. opt
După cum puteți vedea, această acțiune este destul de simplă și este implementată de o comandă a limbajului de asamblare - rol iar rezultatul acestei operațiuni Srol este 0819288Fh.
4. Acum partea L a blocului nostru de informații urmează să fie XOR cu valoarea Srol. Iau un calculator de la w2k sp4 și iau Sxor = 091b2b8bh.
5. Această acțiune este finală și pur și simplu atribuim, curățăm R, valoarea părții L și inițializam partea L cu valoarea Sxor.
Rezultat final:
L = 091b2b8bh, R = 01020304h
4.2 Creșterea vitezei algoritmului
Acum să vorbim despre optimizarea algoritmului pentru viteză. La implementarea unui proiect, trebuie să ținem cont de faptul că un program care funcționează cu registre mai des decât cu memorie funcționează cel mai repede, iar aici această judecată este de asemenea foarte importantă, deoarece peste un bloc de informații până la 32 de acțiuni de criptare!
Când am implementat algoritmul de criptare în programul meu, am făcut următoarele:
1. Partea selectată a blocului L la registrul eax și R la edx.
2. În registrul esi, inițializat cu adresa cheii extinse, mai multe despre aceea de mai jos.
3. În registrul ebx a atribuit valoarea adresei tabelului extins de substituții, mai multe despre aceasta mai jos
4. Transferat informațiile articolelor 1, 2, 3 în funcția ciclului de bază 32 - З sau 32 - Р, în funcție de situație.
Dacă te uiți la diagrama de flux a elementelor cheie din paragraful „ Cicluri de bază: "32-З", "32-Р"", Atunci cheia noastră pentru ciclul de bază 32 - З poate fi reprezentată după cum urmează:
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”
Acestea. de la început sunt k1, k2, k3, k4, k5, k6, k7, k8 - ‘ ca28 ','zw37 ’,’q839 ',' 7342 ','ui23 ',' 8e2t','wqm2 ','ewp1 ' această secvență se repetă de trei ori. Apoi elementele merg în ordine inversă, adică: k8, k7, k6, k5, k4, k3, k2, k1 - „Ewp1”, „wqm2”, „8e2t”, „ui23”, „7342”, „q839”, „zw37”, „as28”.
Am pre-aranjat elementele din matrice în ordinea în care ar trebui să fie alimentate în 32 - Z. Astfel, am crescut memoria necesară la cheie, dar m-am salvat de unele procese de gândire de care nu aveam nevoie și am crescut viteza algoritmului, pentru reducerea timpului de acces la memorie! Aici am descris doar cheia pentru 32 - З, pentru ciclul 32 - Р Am făcut același lucru, dar folosind o schemă diferită de furnizare a elementelor, pe care am descris-o și în paragraful " Cicluri de bază: „32-W”, „32-P».
Acum este momentul să descriem implementarea funcției de înlocuire, așa cum am promis mai sus. Nu aș putea descrie mai devreme, pentru că aceasta necesită introducerea unui nou concept - un tabel extins de substituții. Nu pot să-ți explic ce este. În schimb, ți-o arăt și tu însuți formulezi pentru tine, ce este - un tabel extins de substituții?
Deci, pentru a înțelege ce este un tabel de substituție extins, avem nevoie de un tabel de înlocuire, de exemplu, îl voi lua pe cel prezentat în Fig. 3.
De exemplu, trebuia să înlocuim numărul 66793940h. O voi prezenta astfel:
Orez. nouă
Acum, dacă luăm elementele s1, s0, i.e. octet cel mai puțin semnificativ, rezultatul funcției de înlocuire va fi 25h! După ce am citit articolul lui Andrey Vinokurov, pe care l-am citat în paragraful „ Lista literaturii folosite", De fapt, descoperiți că, dacă luați două linii, puteți obține o matrice, permițându-vă să găsiți rapid elementele de înlocuire folosind comanda de asamblare xlat. Ei spun că este posibil într-un alt mod mai rapid, dar Andrey Vinokurov a petrecut aproximativ patru ani pentru a cerceta algoritmi rapidi pentru implementarea GOST! Nu cred că ar trebui să reinventezi roata când ai deja una.
Deci, despre matrice:
Să luăm primele două linii zero și prima, să creăm o matrice de 256 de octeți. Acum observăm o particularitate că, dacă este necesar să se transforme 00h, atunci rezultatul va fi 75h (pe baza Fig. 3) - punem această valoare în matrice la offset 00h. Luăm valoarea 01h, rezultatul funcției de substituție 79h, o punem în tablou la offset 01 și așa mai departe până la 0FFh, care ne va da 0FCh, pe care îl vom pune în tablou la offset 0FFh. Așa că am obținut un tabel de înlocuire extins pentru primul grup de rânduri: primul și zero. Dar mai sunt trei grupuri: a doua pagina 2, pagina 3, a treia pagina 4, pagina 5, a patra pagina 6, pagina 7. Ne ocupăm de aceste trei grupuri în același mod ca și cu primul. Rezultatul este un tabel de înlocuire extins!
Acum putem implementa un algoritm care va efectua înlocuirea. Pentru a face acest lucru, luăm codurile sursă pe care Andrei Vinokurov le-a postat pe pagina sa, vezi „ Bibliografie».
lea ebx, extented_table_simple
mov eax, [puneți numărul de înlocuit]
adăugați ebx, 100h; săriți la următoarele două noduri
sub ebx, 300h; astfel încât în viitor ebx să indice tabelul
Acum încă o caracteristică, cu acțiunile anterioare nu numai că am înlocuit, dar am mutat și numărul cu 8 biți la stânga! Trebuie doar să mutăm numărul încă 3 biți la stânga:
si obtinem rezultatul operatiei rol eax, 11!
Nu mai pot adăuga nimic despre optimizare, singurul lucru pe care îl pot sublinia este ceea ce am spus mai sus - folosiți mai des registrele decât accesul la memorie. Cred că aceste cuvinte sunt doar pentru începători, cei experimentați și fără cuvintele mele înțeleg perfect acest lucru.
Cerințe pentru informațiile cheie.
După cum se precizează în articolul lui Andrey Vinokurov, cheia este selectată în funcție de două criterii:
Criteriul pentru distribuția equiprobabilă a biților între valorile 1 și 0. De obicei, criteriul pentru distribuția equiprobabilă a biților este criteriul Pearson ("chi-pătrat").
Aceasta înseamnă o cheie, în principiu, orice număr poate. Adică, atunci când următorul bit al cheii este format, probabilitatea inițializării acesteia cu unu sau zero este 50/50!
Vă rugăm să rețineți că cheia este formată din opt elemente, fiecare de 32 de biți, deci există doar 32 * 8 = 256 de biți în cheie și numărul de chei posibile este de 2 256! Asta nu te lovește?
Criteriul seriei.
Dacă ne uităm la cheia noastră, pe care am dat-o în paragraful " 4.1 Implementarea etapei principale a transformării cripto", Apoi veți observa că următoarea notație este valabilă:
Orez. zece
Într-o frază, valoarea lui k 1 nu trebuie repetată nici în k 2, nici în niciun alt element al cheii.
Adică, cheia pe care am ales-o ca luare în considerare a algoritmului de criptare îndeplinește pe deplin cele două criterii de mai sus.
Acum despre alegerea tabelului de substituții:
Acum să vorbim despre cum să alegem tabelul de înlocuire potrivit. Principala cerință pentru selectarea tabelelor de înlocuire este fenomenul de „nerepetabilitate” a elementelor, fiecare dintre ele având o dimensiune de 4 biți. După cum ați văzut mai sus, fiecare rând al tabelului de înlocuire este format din valorile 0h, 1h, 2h, 3h,…, 0fh. Deci, principala cerință este ca fiecare linie să conțină valorile 0h, 1h, 2h, ..., 0fh și fiecare astfel de valoare într-o singură copie. De exemplu, secvența:
1 2 3 4 5 6 7 8 9 A B C D E F
Îndeplinește pe deplin această cerință, dar totuși! Nu este recomandat să selectați o astfel de secvență ca șir. Deoarece dacă introduceți o valoare la intrarea unei funcții care se bazează pe un astfel de șir, atunci veți obține aceeași valoare la ieșire! Nu mă crezi? Apoi luați numărul 332DA43Fh și opt astfel de linii ca tabel de înlocuire. Efectuați operația de înlocuire și vă asigur că ieșirea va fi numărul 332DA43Fh! Adică același lucru pe care l-ați supus la intrarea operațiunii! Și acesta nu este un semn de bună formă în criptare, și nu-i așa?
Aceasta a fost o cerință, următorul criteriu spune că - fiecare bit al blocului de ieșire trebuie să fie independent statistic de fiecare bit al blocului de intrare!
Cum pare mai simplu? Și iată cum, de exemplu, am ales din numărul de mai sus elementul s0 = 0Fh, 01111b. Probabilitatea ca acum să înlocuim primul bit cu unul sau zero este de 0,5! Probabilitatea înlocuirii celui de-al doilea, al treilea și al patrulea bit, fiecare bit, luăm în considerare separat, cu unu sau zero, este de asemenea 0, 5. Când alegem s1 = 0Eh, probabilitatea ca noi să fim un bit zero, iar acesta este „0” , va fi înlocuit cu un zero sau unul prea egal - 0,5! Astfel, conform acestui criteriu, nu există o regularitate între înlocuirea biților zero ai elementelor s0, s1! Da, ai putea înlocui cele, dar ai putea înlocui și zerouri.
Pentru a evalua tabelul conform acestui criteriu, puteți construi un tabel de coeficienți de corelație calculati prin formula:
Dacă p = 1, atunci valoarea bitului j la ieșire este egală cu valoarea bitului i la intrare pentru orice combinație de biți la intrare;
Dacă p = -1, atunci valoarea bitului j la ieșire este întotdeauna inversul bitului i de intrare;
Dacă p = 0, atunci bitul de ieșire j cu probabilitate egală ia valorile 0 și 1 pentru orice valoare fixă a bitului de intrare i.
Să luăm un exemplu de linie:
Să-l împărțim în „componente”:
Să calculăm un coeficient conform formulei de mai sus. Pentru a înțelege mai ușor cum se face acest lucru, voi explica mai detaliat:
Luăm bitul 0 al numărului 0 (0) la intrare și bitul 0 al numărului 0 la ieșire (1) executăm operația 0 XOR 1 = 1.
Luăm al 0-lea bit al primului număr (1) la intrare și al 0-lea bit al primului număr la ieșire (1) efectuăm operația 1 XOR 1 = 0.
Luăm al 0-lea bit al celui de-al 2-lea număr (0) la intrare și al 0-lea bit al celui de-al 2-lea număr la ieșire (0) executăm operația 0 XOR 0 = 0.
Luăm al 0-lea bit al celui de-al 3-lea număr (1) la intrare și al 0-lea bit al celui de-al 3-lea număr la ieșire (1) efectuăm operația 1 XOR 1 = 0.
Efectuând succesiv operații XOR într-o astfel de secvență, numărăm numărul tuturor valorilor nenule, obținem valoarea 6. Prin urmare, P 00 = 1- (6/2 4-1) = 0,25. Deci, s-a dovedit că valoarea bitului 0 la ieșire este egală cu valoarea bitului 0 la intrare în 4 cazuri din 16;
Tabelul final de cote:
După cum se poate observa din tabelul coeficienților de corelație, bitul 3 la intrare este inversat față de bitul 0 la ieșire în 14 cazuri din 16, adică 87,5%.Acest lucru nu mai este acceptabil pentru sistemele de criptare normale. Să luăm un alt exemplu pentru o schimbare:
Tabelul de coeficienți va fi după cum urmează (cui nu le este lene să recalculeze)
Ei bine, în acest tabel, lucrurile stau și mai rău - biții 1 și 2 ai grupului rămân neschimbați! Cryptanalyst are de unde să se întoarcă Ținând cont de toate aceste cerințe, o simplă căutare ("head-on") a găsit tabele de permutări corespunzătoare teoriei indicate (azi - 1276 de combinații) Iată câteva dintre ele:
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
Lista literaturii folosite.
- Articol de Andrey Vinokurov:
Algoritmul de criptare GOST 28147-89, utilizarea și implementarea acestuia
pentru computerele platformei Intel x86.
Există și codurile sursă pentru implementarea algoritmului de criptare.
- Articolul lui Horst Feistel:
Criptografie și securitate informatică.
(poate fi găsit la aceeași adresă ca articolul precedent)
- Ross N. Williams:
Un ghid elementar pentru algoritmii de detectare a erorilor CRC
Postat pe site www.wasm.ru.
Mulțumiri.
Aș dori să-mi exprim recunoștința tuturor vizitatorilor forumului www.wasm.ru. Dar aș dori să îi mulțumesc în special lui ChS, care în prezent este cunoscut sub numele de SteelRat, el m-a ajutat să înțeleg lucruri pe care probabil nu le-aș fi înțeles niciodată, precum și a ajutat la scrierea paragrafului: „ Cerințe de informații cheie”, Partea principală a acestui paragraf a fost scrisă de el. De asemenea, îi sunt profund recunoscător angajatului KSTU care poartă numele UN. Tupolev Anikin Igor Vyacheslavovich și ar fi un păcat să nu mai vorbim de Chris Kaspersky pentru faptul că este și Volodya / wasm.ru pentru instrucțiunile sale. Oh, și am primit-o de la el. Vreau să notez și Sega-Zero / Callipso, dar asta mi-a adus în minte niște junglă matematică.
Acesta este, probabil, tot ceea ce aș vrea să vă spun.
Aș fi recunoscător pentru orice critică sau întrebări legate de acest articol sau doar sfat. Datele mele de contact: [email protected], ICQ - 337310594.
Salutări, Evil's Interrupt.
P.S.: Cu acest articol, nu am încercat să întrec pe nimeni. A fost scris cu intenție, pentru a facilita studiul GOST, iar dacă aveți dificultăți, nu înseamnă că sunt vinovat de acest lucru. Fii rezonabil și ai răbdare, toate cele bune pentru tine!
„Cât timp ești în viață, nu muri, aruncă o privire la această lume.
Mulți de aici au un suflet mort - sunt morți înăuntru.
Dar ei merg și râd, fără să știe că nu sunt,
Nu-ți grăbi ceasul morții ”, mi-a spus ea.
Aria, „Acolo sus”
- Introducere
- Informații preliminare despre cifrurile bloc
2.1
rețele Feistel.
2.2
Cifra bloc GOST 28147-89
- Minimum teoretic
3.1
Informatie cheie
3.2
Etapa principală a transformării cripto
3.3 Bucle de bază:“ 32-Z” , “ 32-R” .
- Practică
4.1
Implementarea etapei principale a transformării cripto
4.2
Creșterea vitezei algoritmului
5.
6.
Lista literaturii folosite
7.
Mulțumiri.
Introducere.
Acest document este încercarea mea de a descrie o metodă pentru pur și simplu înlocuirea algoritmului de criptare GOST 28147-89 cu cel mai simplu, dar, totuși, limbaj competent din punct de vedere tehnic. După ce a citit primele șase puncte, cititorul își va da cu părerea despre cum am făcut-o.
Pentru ca munca mea să ofere mai multe beneficii, vă recomand să vă înarmați cu lucrările autorilor indicați în lista literaturii folosite. De asemenea, se recomandă ca calculatorul să aibă o funcție pentru calcularea operației. XOR de cand citirea articolului presupune că cititorul a intenționat să studieze acest algoritm de criptare. Deși este potrivit și ca referință, dar am scris acest articol tocmai ca unul de antrenament.
Informații preliminare despre cifrurile bloc.
Înainte de a începe să privim algoritmul, trebuie să ne familiarizăm cu istoria creării acestui tip de cifruri. Algoritmul aparține categoriei de cifruri bloc, în arhitectura cărora informațiile sunt împărțite într-un număr finit de blocuri, cel final poate să nu fie complet. Procesul de criptare are loc pe blocuri complete, care formează cifrul. Blocul final, dacă este incomplet, este completat cu ceva (despre nuanțele completării lui voi spune mai jos) și este criptat la fel ca și blocurile complete. Prin cifru, mă refer la rezultatul funcției de criptare care acționează asupra unei anumite cantități de date pe care utilizatorul le-a trimis pentru criptare. Cu alte cuvinte, un cifru este rezultatul final al criptării.
Istoria dezvoltării cifrurilor bloc este asociată cu începutul anilor 70, când IBM, realizând nevoia de a proteja informațiile atunci când transmite date prin canale de comunicații computerizate, s-a angajat într-un program propriu de cercetare dedicat protecției informațiilor în rețelele electronice, inclusiv criptografie.
Un grup de cercetători - dezvoltatori ai companiei IBM, care a început să studieze sisteme de criptare cu o schemă de utilizare a cheii simetrice, a fost condus de Dr. Horst Feistel.
2.1 Rețele Feistel
Arhitectura noii metode de criptare propusă de Feistel în literatura clasică se numește „Arhitectura Feistel”, dar în prezent în literatura rusă și străină este folosit un termen mai consacrat - „Rețeaua lui Feistel” sau Feistel`s NetWork. Ulterior, pe această arhitectură a fost construit cifrul „Lucifer” - care a fost publicat ulterior și a provocat un nou val de interes în criptografie în general.
Ideea arhitecturii „rețea Feistel” este următoarea: fluxul de informații de intrare este împărțit în blocuri de n biți în dimensiune, unde n este un număr par. Fiecare bloc este împărțit în două părți - L și R, apoi aceste părți sunt introduse într-un cifr de bloc iterativ, în care rezultatul etapei j-a este determinat de rezultatul etapei anterioare j-1! Acest lucru poate fi ilustrat printr-un exemplu:
Orez. 1
Unde, funcția A este acțiunea principală a cifrului bloc. Poate fi o acțiune simplă, cum ar fi o operație XOR, sau poate avea o formă mai complexă ca o secvență a unei serii de acțiuni simple - adăugare modulo, deplasare la stânga, înlocuire de elemente etc., luate împreună, aceste acțiuni simple formează așa-numitul - pasul principal al transformării cripto.
Trebuie remarcat faptul că elementele cheie ale funcționării funcției sunt furnizarea de elemente cheie și operația XOR și, din cât de bine gândită munca acestor operații, se vorbește despre puterea criptografică a cifrului în ansamblu.
Pentru ca ideea rețelelor Feistel să fie în sfârșit clară, luați în considerare cel mai simplu caz prezentat în orez. 1, unde în funcția A - vor exista operații „mod 2” (“xor”), dar aceasta cel mai simplu un caz, într-o situație mai gravă, de exemplu, ascunderea informațiilor de importanță națională, funcția A poate fi mai complexă (din câte am văzut, funcția A este într-adevăr foarte complexă):
Date inițiale:
L = 1110b, R = 0101, K = 1111b
Ia un cifr
- (R + K) mod 2 4 = Smod, Smod = 0100b
- (Smod + L) mod 2 = Sxor, Sxor = 1010b
- L = R, R = Sxor
L = 0101b, R = 1010b
Să explicăm acțiunile noastre:
- Această operație este adăugarea modului 2 4. În practică, această operație se rezumă la o simplă adunare, unde trebuie să adunăm două numere și să ignorăm transferul la a 5-a cifră. Deoarece dacă punem exponenți deasupra cifrelor reprezentării binare a unui număr, va exista un exponent patru deasupra celei de-a cincea cifre, să aruncăm o privire la figura de mai jos, care arată acțiunile operației noastre:
Orez. 2
Aici am indicat exponenții cu o săgeată, după cum puteți vedea, rezultatul ar fi trebuit să fie 10100, dar deoarece transferul este ignorat în timpul operațiunii mod 2 4, obținem 0100.
- Această operație în literatură se numește mod 2, în limbajul de asamblare este implementată de comandă XOR... Dar numele său mai corect este mod 2 1. Fără această operațiune unică, cu greu este posibil să se construiască un algoritm de criptare rapid, ușor de implementat și, în același timp, astfel încât să fie încă destul de puternic criptografic. Unicitatea acestei operațiuni constă în faptul că ea însăși este opusul! De exemplu, dacă numărul A este XOR cu numărul B, ca rezultat vom obține B, în viitor este suficient să re-XOR numerele B și C între ele pentru a obține valoarea anterioară a lui A!
În această operație, am obținut 1010 având numerele 1110 și 0100, pentru a obține înapoi 1110, este suficient să supraXOR numerele 0100 și 1010! Mai multe detalii despre această operațiune găsiți în articolul, care este atașat site-ului. www.wasm.ru, « Un ghid elementar pentruCRC_ algoritmi de detectare a erorilor»Autorul care Ross N. Williams... Există un punct în această lucrare - „ 5. Aritmetică binară fără silabe". În acest articol este descrisă operația. xor! Exclam pentru că în acest articol această operațiune este atât de programată încât cititorul nu numai că înțelege cum funcționează această operațiune, ci chiar o începe vezi, auzi si simti!
- Această acțiune este necesară pentru ca în timpul decriptării, valorile inițiale să poată fi obținute din cifr.
2.2 Cifrul bloc GOST 28147-89
Algoritmul de criptare GOST 28147 - 89 aparține categoriei de cifruri bloc care funcționează conform arhitecturii rețelelor Feistel echilibrate, unde două părți ale blocului de informații selectat sunt de dimensiune egală. Algoritmul a fost dezvoltat în adâncul celui de-al optulea departament al KGB, acum transformat în FAPSI și a fost consacrat ca standard de criptare al Federației Ruse încă din 1989, sub URSS.
Pentru ca această metodă a algoritmului să funcționeze, este necesară împărțirea informațiilor în blocuri de 64 de biți. Generați sau introduceți în sistemul de criptare următoarele informații cheie: cheie și tabel de înlocuire. Alegerea cheii și a tabelului de înlocuire pentru criptare ar trebui luată foarte în serios, deoarece acesta este fundamentul securității informațiilor dvs. Pentru informații despre cerințele impuse cheii și tabelului de substituții, consultați articolul „Cerințe pentru informațiile cheie”.
Când luăm în considerare metoda, nu ne vom concentra asupra acestui lucru, deoarece Acest articol, așa cum am spus mai sus, a fost scris cu scopul de a învăța cititorul cum să cripteze datele prin metoda înlocuirii simple a acestui algoritm de criptare, dar cu siguranță vom aborda această problemă la sfârșitul articolului.
Minimum teoretic.
3.1 Informații cheie
După cum am spus mai sus, următorii sunt implicați activ în criptarea datelor:
3.1.1. O cheie este o secvență de opt elemente, a câte 32 de biți fiecare. În cele ce urmează, vom desemna prin simbolul K, iar elementele din care constă sunt k1, k2, k3, k4, k5, k6, k7, k8.
3.1.2 Tabel de înlocuire - o matrice de opt rânduri și șaisprezece coloane, denumită în continuare - Hij. Fiecare element de la intersecția rândului i și coloanei j ocupă 4 biți.
Pasul principal în procesul de criptare este - pasul principal al transformării cripto. Aceasta nu este altceva decât o acțiune de criptare a datelor după un anumit algoritm, doar dezvoltatorii au introdus numele prea greoi :).
Înainte de a începe criptarea, blocul este împărțit în două părți L și R, câte 32 de biți fiecare. Elementul cheie este selectat și numai atunci aceste două părți ale blocului, elementul cheie, tabelul de substituție, sunt introduse în funcția pasului principal, rezultatul pasului principal este o iterație a ciclului de bază, care va fi discutată în paragraful următor. Pasul principal constă în următoarele:
- O parte suplimentară a blocului R este însumată cu elementul cheie K mod 2 32. Am descris o operație similară mai sus, aici același lucru doar exponentul nu este „4”, ci „32” - rezultatul acestei operații va fi notat Smod în viitor.
- Împărțiți rezultatul Smod obținut anterior în elemente de patru biți s7, s6, s5, s4, s3, s2, s1, s0 și alimentați-l la funcția de înlocuire. Înlocuirea este următoarea: se selectează elementul Smod - si, începem de la început cu cel mai mic element și înlocuim cu valoarea din tabelul de înlocuiri cu i - rândul și coloana indicate de valoarea elementului s i. Trecem la elementul s i +1 și procedăm în același mod și continuăm așa până când schimbăm valoarea ultimului element Smod - rezultatul acestei operații va fi notat ca, Ssimple.
- În această operație, deplasăm valoarea Ssimple rămasă ciclic cu 11 biți și obținem Srol.
- Selectăm a doua parte a blocului L și o adăugăm mod 2 cu Srol, ca urmare avem Sxor.
- În această etapă, partea blocului L devine egală cu valoarea părții R, iar partea R, la rândul ei, este inițializată cu rezultatul Sxor, iar la aceasta funcția pasului principal este finalizată!
3.3 Cicluri de bază: „32-З”, „32-Р”.
Pentru a cripta informațiile, trebuie să o împărțiți în blocuri de 64 de biți, desigur, ultimul bloc poate fi mai mic de 64 de biți. Acest fapt este călcâiul lui Ahile al acestei metode de „înlocuire ușoară”. Deoarece adăugarea acestuia la 64 de biți este o sarcină foarte importantă pentru a crește puterea criptografică a programului de cifrare și a acestui loc sensibil, dacă este prezent în matricea de informații și este posibil să nu existe (de exemplu, un fișier de 512 octeți! ), Ar trebui tratat cu o mare responsabilitate!
După ce ați împărțit informațiile în blocuri, ar trebui să împărțiți cheia în elemente:
K = k1, k2, k3, k4, k5, k6, k7, k8
Criptarea în sine constă în utilizarea așa-numitelor cicluri de bază. Care, la rândul lor, includ al n-lea număr de pași de bază ai cripto-transformării.
Ciclurile de bază sunt etichetate, cum se spune: n - m. Unde n este numărul de pași de bază ai cripto-transformării în ciclul de bază, iar m este „tipul” ciclului de bază, i.e. despre ce vorbim, despre criptarea „Z” sau criptarea „R” a datelor.
Ciclul de criptare de bază 32-З constă din 32 de pași de bază de cripto-transformare. Blocul N și un element al tastei K sunt introduse în funcția care implementează acțiunile pasului, iar primul pas are loc cu k1, al doilea peste rezultatul obținut cu elementul k2 etc. conform următoarei scheme:
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
Procesul de decriptare pentru 32-P are loc într-un mod similar, dar elementele cheie sunt date în ordine inversă:
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
Practică.
După ce ne-am familiarizat cu teoria modului de criptare a informațiilor, era timpul să vedem cum are loc criptarea în practică.
Date inițiale:
Luați un bloc de informații N = 0102030405060708h, aici părțile L și R sunt egale:
L = 01020304h, R = 05060708h, să luăm cheia:
K = ca28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(acestea sunt coduri ASCII, pentru a vizualiza reprezentarea hexazecimală, puteți deschide acest fișier în modul vizualizare în Total Commander apăsând tasta F3„Și apoi cheia” 3 "). În această cheie, valorile elementelor vor fi:
k1 = „as28”, k2 = „zw37”, k3 = „q839”, k4 = „7342”
k5 = „ui23”, k6 = „8e2t”, k7 = „wqm2”, k8 = „ewp1”
Luați, de asemenea, următorul tabel de înlocuire:
Orez. 3
Aici, rândurile sunt numerotate de la 0 la 7, coloanele de la 0 la F.
Un avertisment: Toate informațiile, inclusiv cheia cu tabelul de înlocuire, sunt luate ca exemplu pentru luarea în considerare a algoritmului!
Folosind „Date inițiale”, este necesar să se obțină rezultatul acțiunii pasului principal al transformării cripto.
- Selectăm partea R = 05060708h și elementul cheie k1 = 'as28', în formă hexazecimală elementul cheie va arăta astfel: 61733238h. Acum facem operația de însumare mod 2 32:
Orez. 4
După cum puteți vedea în figură, nu am avut un transfer pe 33 de biți marcați cu roșu și cu exponentul „ 32 ". Și dacă am fi avut alte valori ale lui R și elementul cheie, acest lucru s-ar fi putut întâmpla și atunci l-am fi ignorat și am fi folosit în continuare doar biții marcați cu galben.
Efectuez această operație cu comanda assembler adăuga:
; eax = R, ebx = 'as28'
Rezultatul acestei operațiuni Smod = 66793940h
- Acum cea mai complicată operație, dar dacă te uiți atent, nu mai este atât de groaznică pe cât pare la început. Să ne imaginăm Smod după cum urmează:
FIGURA NU S-A SALVAT
Orez. 5
Am încercat să vizualizez elementele Smod din figură, dar voi explica oricum:
s0 = 0, s1 = 4, s2 = 9 etc.
Acum, pornind de la elementul cel mai de jos s0, facem înlocuirea. Amintind paragraful „ 3.2 Etapa de bază a transformării cripto»I - rând, s i - coloana, căutați valoarea în rândul zero și coloana zero:
Fig. 6
Deci valoarea actuală a Smod nu este 6679394 0 h și 6679394 5 h.
Procedăm la înlocuirea s1, adică. patru. Folosind primul rând și a patra coloană (s1 = 4!). Ne uitam la poza:
Orez. 7
Acum valoarea este Smod, nu 667939 4 5h, 667939 2 5h. Presupun că acum algoritmul de înlocuire este clar pentru cititor și pot spune că după rezultatul final al lui Ssimple va avea următoarea valoare - 11e10325h.
Voi vorbi despre modul în care acest lucru este cel mai ușor de implementat sub formă de comenzi de asamblare mai târziu în paragraful următor, după ce voi vorbi despre tabelul extins.
- Trebuie să deplasăm valoarea Ssimple rezultată cu 11 biți la stânga.
Orez. opt
După cum puteți vedea, această acțiune este destul de simplă și este implementată de o comandă a limbajului de asamblare - rol iar rezultatul acestei operațiuni Srol este 0819288Fh.
- Acum rămâne partea L a blocului nostru de informații care urmează să fie XOR cu valoarea Srol. Iau un calculator de la w2k sp4 și iau Sxor = 091b2b8bh.
- Această acțiune este finală și pur și simplu atribuim, curățăm R, valoarea părții L și inițializam partea L cu valoarea Sxor.
Rezultat final:
L = 091b2b8bh, R = 01020304h
4.2 Creșterea vitezei algoritmului
Acum să vorbim despre optimizarea algoritmului pentru viteză. La implementarea unui proiect, trebuie să ținem cont de faptul că un program care funcționează cu registre mai des decât cu memorie funcționează cel mai repede, iar aici această judecată este de asemenea foarte importantă, deoarece peste un bloc de informații până la 32 de acțiuni de criptare!
Când am implementat algoritmul de criptare în programul meu, am făcut următoarele:
- Partea selectată a blocului L pentru a înregistra eax și R pentru edx.
- În registrul esi, inițializat cu adresa cheii extinse, mai multe despre aceea de mai jos.
- În registrul ebx a atribuit valoarea adresei tabelului extins de substituții, mai multe despre asta mai jos
- Transferat informațiile articolelor 1, 2, 3 la funcția ciclului de bază 32 - З sau 32 - Р, în funcție de situație.
Dacă te uiți la diagrama de flux a elementelor cheie din paragraful „ Cicluri de bază: "32-З", "32-Р"", Atunci cheia noastră pentru ciclul de bază 32 - З poate fi reprezentată după cum urmează:
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”
Acestea. de la început sunt k1, k2, k3, k4, k5, k6, k7, k8 - ‘ ca28 ','zw37 ’,’q839 ',' 7342 ','ui23 ',' 8e2t','wqm2 ','ewp1 ' această secvență se repetă de trei ori. Apoi elementele merg în ordine inversă, adică: k8, k7, k6, k5, k4, k3, k2, k1 - „Ewp1”, „wqm2”, „8e2t”, „ui23”, „7342”, „q839”, „zw37”, „as28”.
Am pre-aranjat elementele din matrice în ordinea în care ar trebui să fie alimentate în 32 - Z. Astfel, am crescut memoria necesară la cheie, dar m-am salvat de unele procese de gândire de care nu aveam nevoie și am crescut viteza algoritmului, pentru reducerea timpului de acces la memorie! Aici am descris doar cheia pentru 32 - З, pentru ciclul 32 - Р Am făcut același lucru, dar folosind o schemă diferită de furnizare a elementelor, pe care am descris-o și în paragraful " Cicluri de bază: „32-W”, „32-P».
Acum este momentul să descriem implementarea funcției de înlocuire, așa cum am promis mai sus. Nu aș putea descrie mai devreme, pentru că aceasta necesită introducerea unui nou concept - un tabel extins de substituții. Nu pot să-ți explic ce este. În schimb, ți-o arăt și tu însuți formulezi pentru tine, ce este - un tabel extins de substituții?
Deci, pentru a înțelege ce este un tabel de substituție extins, avem nevoie de un tabel de înlocuire, de exemplu, îl voi lua pe cel prezentat în Fig. 3.
De exemplu, trebuia să înlocuim numărul 66793940h. O voi prezenta astfel:
FIGURA NU S-A SALVAT
Orez. nouă
Acum, dacă luăm elementele s1, s0, i.e. octet cel mai puțin semnificativ, rezultatul funcției de înlocuire va fi 25h! După ce am citit articolul lui Andrey Vinokurov, pe care l-am citat în paragraful „ Lista literaturii folosite", De fapt, descoperiți că, dacă luați două linii, puteți obține o matrice, permițându-vă să găsiți rapid elementele de înlocuire folosind comanda de asamblare xlat. Ei spun că este posibil într-un alt mod mai rapid, dar Andrey Vinokurov a petrecut aproximativ patru ani pentru a cerceta algoritmi rapidi pentru implementarea GOST! Nu cred că ar trebui să reinventezi roata când ai deja una.
Deci, despre matrice:
Să luăm primele două linii zero și prima, să creăm o matrice de 256 de octeți. Acum observăm o particularitate că, dacă este necesar să se transforme 00h, atunci rezultatul va fi 75h (pe baza Fig. 3) - punem această valoare în matrice la offset 00h. Luăm valoarea 01h, rezultatul funcției de substituție 79h, o punem în tablou la offset 01 și așa mai departe până la 0FFh, care ne va da 0FCh, pe care îl vom pune în tablou la offset 0FFh. Așa că am obținut un tabel de înlocuire extins pentru primul grup de rânduri: primul și zero. Dar mai sunt trei grupuri: a doua pagina 2, pagina 3, a treia pagina 4, pagina 5, a patra pagina 6, pagina 7. Ne ocupăm de aceste trei grupuri în același mod ca și cu primul. Rezultatul este un tabel de înlocuire extins!
Acum putem implementa un algoritm care va efectua înlocuirea. Pentru a face acest lucru, luăm codurile sursă pe care Andrei Vinokurov le-a postat pe pagina sa, vezi „ Bibliografie».
lea ebx, extented_table_simple
mov eax, [puneți numărul de înlocuit]
adăugați ebx, 100h; săriți la următoarele două noduri
sub ebx, 300h; astfel încât în viitor ebx să indice tabelul
Acum încă o caracteristică, cu acțiunile anterioare nu numai că am înlocuit, dar am mutat și numărul cu 8 biți la stânga! Trebuie doar să mutăm numărul încă 3 biți la stânga:
si obtinem rezultatul operatiei rol eax, 11!
Nu mai pot adăuga nimic despre optimizare, singurul lucru pe care îl pot sublinia este ceea ce am spus mai sus - folosiți mai des registrele decât accesul la memorie. Cred că aceste cuvinte sunt doar pentru începători, experimentați și fără cuvintele mele înțeleg acest lucru perfect :).
Cerințe pentru informațiile cheie.
După cum se precizează în articolul lui Andrey Vinokurov, cheia este selectată în funcție de două criterii:
- criteriul de distribuție equiprobabilă a biților între valorile 1 și 0. De obicei, criteriul de distribuție equiprobabilă a biților este criteriul Pearson ("chi-pătrat").
Aceasta înseamnă o cheie, în principiu, orice număr poate. Adică, atunci când următorul bit al cheii este format, probabilitatea inițializării acesteia cu unu sau zero este 50/50!
Vă rugăm să rețineți că cheia este formată din opt elemente, fiecare de 32 de biți, deci există doar 32 * 8 = 256 de biți în cheie și numărul de chei posibile este de 2 256! Asta nu te lovește? 🙂
- criteriul seriei.
Dacă ne uităm la cheia noastră, pe care am dat-o în paragraful " 4.1 Implementarea etapei principale a transformării cripto", Apoi veți observa că următoarea notație este valabilă:
Orez. zece
Într-o frază, valoarea lui k 1 nu trebuie repetată nici în k 2, nici în niciun alt element al cheii.
Adică, cheia pe care am ales-o ca luare în considerare a algoritmului de criptare îndeplinește pe deplin cele două criterii de mai sus.
Acum despre alegerea tabelului de substituții:
Acum să vorbim despre cum să alegem tabelul de înlocuire potrivit. Principala cerință pentru selectarea tabelelor de înlocuire este fenomenul de „nerepetabilitate” a elementelor, fiecare dintre ele având o dimensiune de 4 biți. După cum ați văzut mai sus, fiecare rând al tabelului de înlocuire este format din valorile 0h, 1h, 2h, 3h,…, 0fh. Deci, principala cerință este ca fiecare linie să conțină valorile 0h, 1h, 2h, ..., 0fh și fiecare astfel de valoare într-o singură copie. De exemplu, secvența:
1 2 3 4 5 6 7 8 9 A B C D E F
Îndeplinește pe deplin această cerință, dar totuși! Nu este recomandat să selectați o astfel de secvență ca șir. Deoarece dacă introduceți o valoare la intrarea unei funcții care se bazează pe un astfel de șir, atunci veți obține aceeași valoare la ieșire! Nu mă crezi? Apoi luați numărul 332DA43Fh și opt astfel de linii ca tabel de înlocuire. Efectuați operația de înlocuire și vă asigur că ieșirea va fi numărul 332DA43Fh! Adică același lucru pe care l-ați supus la intrarea operațiunii! Și acesta nu este un semn de bună formă în criptare, și nu-i așa? 🙂
Aceasta a fost o cerință, următorul criteriu spune că - fiecare bit al blocului de ieșire trebuie să fie independent statistic de fiecare bit al blocului de intrare!
Cum pare mai simplu? Și iată cum, de exemplu, am ales din numărul de mai sus elementul s0 = 0Fh, 01111b. Probabilitatea ca acum să înlocuim primul bit cu unul sau zero este de 0,5! Probabilitatea înlocuirii celui de-al doilea, al treilea și al patrulea bit, fiecare bit, luăm în considerare separat, cu unu sau zero, este de asemenea 0, 5. Când alegem s1 = 0Eh, probabilitatea ca noi să fim un bit zero, iar acesta este „0” , va fi înlocuit cu un zero sau unul prea egal - 0,5! Astfel, conform acestui criteriu, nu există o regularitate între înlocuirea biților zero ai elementelor s0, s1! Da, ai putea înlocui cele, dar ai putea înlocui și zerouri. 🙂
Pentru a evalua tabelul conform acestui criteriu, puteți construi un tabel de coeficienți de corelație calculati prin formula:
- dacă p = 1, atunci valoarea bitului j la ieșire este egală cu valoarea bitului i la intrare pentru orice combinație de biți la intrare;
- dacă p = -1, atunci valoarea bitului j la ieșire este întotdeauna inversul bitului i de intrare;
- dacă p = 0, atunci bitul de ieșire j cu probabilitate egală ia valorile 0 și 1 pentru orice valoare fixă a bitului de intrare i.
Să luăm un exemplu de linie:
| D | B | 4 | 1 | 3 | F | 5 | 9 | 0 | A | E | 7 | 6 | 8 | 2 | C | |
Să-l împărțim în „componente”:
Să calculăm un coeficient conform formulei de mai sus. Pentru a înțelege mai ușor cum se face acest lucru, voi explica mai detaliat:
- luăm bitul 0 al numărului 0 (0) la intrare și bitul 0 al numărului 0 la ieșire (1) efectuăm operația 0 XOR 1 = 1.
- luăm bitul 0 al primului număr (1) la intrare și al 0-lea bit al primului număr la ieșire (1) efectuăm operația 1 XOR 1 = 0.
- luăm bitul 0 al numărului 2 (0) la intrare și bitul 0 al numărului 2 la ieșire (0) efectuăm operația 0 XOR 0 = 0.
- luăm bitul 0 al numărului 3 (1) la intrare și bitul 0 al numărului 3 la ieșire (1) efectuăm operația 1 XOR 1 = 0.
Efectuând succesiv operații XOR într-o astfel de secvență, numărăm numărul tuturor valorilor nenule, obținem valoarea 6. Prin urmare, P 00 = 1- (6/2 4-1) = 0,25. Deci, s-a dovedit că valoarea bitului 0 la ieșire este egală cu valoarea bitului 0 la intrare în 4 cazuri din 16;
Tabelul final de cote:
Tabelul de coeficienți va fi după cum urmează (cui nu le este lene să recalculeze)
| Intrare | |||||
| Ieșire | 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 | |
Ei bine, în acest tabel, lucrurile stau și mai rău - biții 1 și 2 ai grupului rămân neschimbați! Criptoanalistul are de unde să se întoarcă 🙂 Ținând cont de toate aceste cerințe, o simplă căutare ("head-on") a găsit tabele de permutări corespunzătoare teoriei indicate (azi - 1276 de combinații) Iată câteva dintre ele:
| 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 |
Lista literaturii folosite.
- Articol de Andrey Vinokurov:
Algoritmul de criptare GOST 28147-89, utilizarea și implementarea acestuia
pentru computerele platformei Intel x86.
(poate fi găsit la: http://www.enlight.ru/crypto/frame.htm).
Există și codurile sursă pentru implementarea algoritmului de criptare.
- Articolul lui Horst Feistel:
Criptografie și securitate informatică.
(poate fi găsit la aceeași adresă ca articolul precedent)
- Ross N. Williams:
Un ghid elementar pentru algoritmii de detectare a erorilor CRC
Postat pe site www.wasm.ru.
Mulțumiri.
Aș dori să-mi exprim recunoștința tuturor vizitatorilor forumului www.wasm.ru. Dar aș dori să îi mulțumesc în special lui ChS, care în prezent este cunoscut sub numele de SteelRat, el m-a ajutat să înțeleg lucruri pe care probabil nu le-aș fi înțeles niciodată, precum și a ajutat la scrierea paragrafului: „ Cerințe de informații cheie”, Partea principală a acestui paragraf a fost scrisă de el. De asemenea, îi sunt profund recunoscător angajatului KSTU care poartă numele UN. Tupolev Anikin Igor Vyacheslavovich și ar fi un păcat să nu mai vorbim de Chris Kaspersky pentru faptul că este și Volodya / wasm.ru pentru instrucțiunile sale. Oh, și am primit de la el :). Vreau să notez și Sega-Zero / Callipso, dar asta mi-a adus în minte niște junglă matematică.
Acesta este, probabil, tot ceea ce aș vrea să vă spun.
Aș fi recunoscător pentru orice critică sau întrebări legate de acest articol sau doar sfat. Datele mele de contact: [email protected], ICQ - 337310594.
Salutări, Evil's Interrupt.
P.S.: Cu acest articol, nu am încercat să întrec pe nimeni. A fost scris cu intenție, pentru a facilita studiul GOST, iar dacă aveți dificultăți, nu înseamnă că sunt vinovat de acest lucru. Fii rezonabil și ai răbdare, toate cele bune pentru tine!
Acest algoritm este obligatoriu pentru utilizare ca algoritm de criptare în organizațiile guvernamentale ale Federației Ruse și în unele comerciale.
Descrierea algoritmului
Diagrama algoritmului este prezentată în Fig. 3.1. După cum puteți vedea, schema acestui algoritm este destul de simplă, ceea ce simplifică fără ambiguitate implementarea software sau hardware.
Algoritmul GOST 28147-89 criptează informațiile în blocuri de 64 de biți, care sunt împărțite în două sub-blocuri de 32 de biți (N1 și N2). Subblocul N1 este procesat într-un anumit mod, după care se adaugă valoarea acestuia
cu valoarea subblocului N2 (adăugarea se realizează modulo 2), apoi se schimbă subblocurile. O astfel de transformare se realizează pentru un anumit număr de runde: 16 sau 32, în funcție de modul de funcționare al algoritmului (descris mai jos). În fiecare rundă se efectuează următoarele operații:
1. Suprapunerea tastelor. Conținutul subblocului / VI este adăugat modulo 2 32 cu o parte a tastei Kx.
Cheia de criptare a algoritmului GOST 28147-89 are o dimensiune de 256 de biți, iar Kx este partea sa de 32 de biți, adică cheia de criptare de 256 de biți este reprezentată ca o concatenare a subcheilor de 32 de biți (Fig. 3.2) :
SH ATI, AG2, YU, AG4, K5, KB, K7.
În procesul de criptare, se folosește una dintre aceste subchei, în funcție de numărul rotund și de modul de funcționare al algoritmului.
Orez. 3.1. Schema de algoritm GOST 28147-
Orez. 3.2. Cheie de criptare a algoritmului GOST 28147-89
2. Înlocuire tabulară. După ce cheia este suprapusă, subblocul / VI este împărțit în 8 părți a câte 4 biți, valoarea fiecăruia fiind înlocuită individual în conformitate cu tabelul de înlocuire pentru această parte a subblocului. Cutiile de substituție (S-boxes) sunt adesea folosite în algoritmii moderni de criptare, așa că merită să le luați în considerare mai detaliat.
Înlocuirea tabelară este utilizată în acest fel: un bloc de date de o anumită dimensiune (în acest caz, de 4 biți) este alimentat la intrare, a cărui reprezentare numerică determină numărul valorii de ieșire. De exemplu, avem o S-box de următoarea formă:
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.
Lăsați un bloc de 4 biți „0100” să vină la intrare, adică valoarea 4. Conform tabelului, valoarea de ieșire va fi 15, adică. „1111” (0 este înlocuit cu 4, 1 este înlocuit cu 11, valoarea lui 2 este neschimbată etc.).
După cum puteți vedea, schema algoritmului este foarte simplă, ceea ce înseamnă că cea mai mare sarcină de criptare a datelor cade pe tabelele de înlocuire. Din păcate, algoritmul are proprietatea că există tabele de substituție „slabe”, atunci când se utilizează algoritmul poate fi dezvăluit prin metode criptoanalitice. Cele slabe includ, de exemplu, un tabel în care rezultatul este egal cu intrarea:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
3. Deplasare ciclică la stânga pe biți cu 11 biți.
Moduri de operare a algoritmului
Algoritmul GOST 28147-89 are 4 moduri de operare:
□ mod simplu de înlocuire;
□ modul gamma;
P gamma mod cu feedback;
□ modul de producere a simulatoarelor.
Aceste moduri sunt oarecum diferite de cele general acceptate (descrise în Secțiunea 1.4), așa că merită să le analizăm mai detaliat.
Aceste moduri au scopuri diferite, dar folosesc aceeași transformare de criptare descrisă mai sus.
Mod de înlocuire ușoară
În modul de înlocuire simplă, cele 32 de runde descrise mai sus sunt efectuate pur și simplu pentru a cripta fiecare bloc de informații pe 64 de biți. Subcheile pe 32 de biți sunt utilizate în următoarea secvență:
□ KO, Kl, K2, KZ, K4, K5, Kb, AG7, KO, ATI etc. - în rundele 1 la 24;
□ K1, Kb, K5, K4, KZ, K2, K \, KO — în runde de la 25 la 32.
Decriptarea în modul de înlocuire simplă se realizează exact în același mod, dar cu o secvență de subchei ușor diferită:
□ KO, K \, K2, KZ, K4, K5, Kb, KP - în runde de la 1 la 8;
□ KP, Kb, K5, K4, KZ, K2, K \, KO, K1, Kb etc. - în runde de la 9 la 32.
Similar cu modul standard ECB, datorită criptării separate a blocurilor, modul de înlocuire simplă este puternic descurajat pentru a cripta datele în sine; ar trebui folosit doar pentru a cripta alte chei de criptare în scheme cu mai multe chei.
Modul Gamma
În modul gamma (Fig. 3.3), fiecare bloc de text simplu este adăugat pe biți modulo 2 cu un bloc gamma de 64 de biți. O gamma cifră este o secvență specială care este generată folosind transformările descrise mai sus, după cum urmează:
1. În registrele N1 și N2 se scrie umplerea lor inițială - o valoare de 64 de biți numită „synchro-burst” (synchro-burst este practic analog cu vectorul de inițializare în modurile CBC, CFB și OFB).
2. Criptarea conținutului registrelor / VI și N2 (în acest caz - mesaje sincronizate) se realizează în modul de înlocuire simplă.
3. Conținutul lui N1 se adaugă modulo (2 32 - 1) cu constanta CI = 2 24 + 2 16 + 2 8 + 4, rezultatul adunării se scrie în registrul / VI.
4. Conținutul lui N2 se adaugă modulo 2 cu constanta C2 = 2 24 + 2 16 + 2 8 +1, rezultatul adunării se scrie în registrul N2.
5. Conținutul registrelor / VI și N2 este scos ca un bloc gamma de 64 de biți (adică, în acest caz / VI și N2 formează primul bloc gamma).
6. Dacă este necesar următorul bloc de gamma (adică trebuie să continuați criptarea sau decriptarea), reveniți la pasul 2.
Pentru decriptare, gamma este generată într-un mod similar, apoi operația XOR este aplicată din nou textului cifrat și biților gamma.
Pentru a genera aceeași gamă de criptare, utilizatorul care decriptează criptograma trebuie să aibă aceeași cheie și aceeași valoare de sincronizare care au fost folosite pentru a cripta informațiile. În caz contrar, nu va fi posibil să obțineți textul original din cel criptat.
În majoritatea implementărilor algoritmului GOST 28147-89, mesajul de sincronizare nu este un element secret, cu toate acestea, mesajul de sincronizare poate fi la fel de secret ca și cheia de criptare. În acest caz, putem presupune că lungimea efectivă a cheii algoritmului (256 de biți) este mărită cu încă 64 de biți ai mesajului de sincronizare, ceea ce poate fi considerat ca un element cheie suplimentar.
Modul Gamma cu feedback
În modul gamma cu feedback, ca umplerea registrelor / VI și L / 2, începând cu al 2-lea bloc, nu se utilizează blocul gamma anterior, ci rezultatul criptării blocului anterior de text simplu (Fig. 3.4) . Primul bloc din acest mod este generat complet similar cu cel anterior.
Orez. 3.4. Generarea cifrului gamma în modul feedback gamma
Mod de producere a unui simulator
Un prefix este o sumă de control criptografică calculată folosind o cheie de criptare pentru a verifica integritatea mesajelor. Pentru a-l calcula, există un mod special al algoritmului GOST 28147-89.
Generarea unui simulator se realizează după cum urmează:
1. Primul bloc de informații pe 64 de biți, pentru care se calculează prefixul, este scris în registrele N1 și N2 și criptat în modul redus de înlocuire simplă, în care sunt efectuate primele 16 runde din 32.
2. Rezultatul obținut este însumat modulo 2 cu următorul bloc de informații, stocând rezultatul în N1 și N2.
3. M și N2 sunt criptate din nou în modul redus de înlocuire simplă și așa mai departe până la ultimul bloc de informații.
Un imitator este conținutul rezultat pe 64 de biți al registrelor N1 și N2 sau o parte a acestuia. Este folosit cel mai frecvent prefix de 32 de biți, adică jumătate din conținutul registrului. Acest lucru este suficient, deoarece, la fel ca orice sumă de control, simulatorul este conceput în primul rând pentru a proteja împotriva distorsiunii accidentale a informațiilor. Pentru a proteja împotriva modificării deliberate a datelor, sunt utilizate alte metode criptografice - în primul rând, o semnătură digitală electronică (a se vedea secțiunea 1.1).
Imitatorul este utilizat după cum urmează:
1. La criptarea oricărei informații, un prefix de text simplu este calculat și trimis împreună cu textul cifrat.
2. După decriptare, prefixul este calculat din nou și comparat cu cel trimis.
3. Dacă prefixele calculate și trimise nu se potrivesc - textul cifrat a fost distorsionat în timpul transmiterii sau au fost folosite chei incorecte în timpul decriptării.
Prefixul este util în special pentru a verifica decriptarea corectă a informațiilor cheie atunci când se utilizează scheme cu mai multe chei.
Un imitator este un analog al codului de autentificare a mesajului MAC calculat în modul CBC; diferența este că mesajul de sincronizare nu este utilizat în calculul prefixului, în timp ce vectorul de inițializare este utilizat în calculul MAC.
Puterea criptografică a algoritmului
În 1994, descrierea algoritmului GOST 28147-89 a fost tradusă în engleză și publicată; după aceasta au început să apară rezultatele analizei sale, efectuate de experți străini; cu toate acestea, pentru o perioadă semnificativă de timp, nu s-a găsit niciun atac fezabil.
□ lungime cheie mare - 256 biți; împreună cu mesajul de sincronizare secretă, lungimea efectivă a cheii este mărită la 320 de biți;
□ 32 de runde de transformări; după 8 runde, se obține efectul complet de dispersie a datelor de intrare: o modificare a unui bit din blocul de text simplu va afecta toți biții din blocul de text cifrat și invers, adică există o marjă de securitate multiplă.
Luați în considerare rezultatele criptoanalizei algoritmului GOST 28147-89.
Analiza tabelelor de înlocuire
Deoarece tabelele de substituție nu sunt date în standard, o serie de lucrări (de exemplu, c) sugerează că o „organizație competentă” poate produce atât tabele de substituție „bune”, cât și „rele”. Cu toate acestea, cel mai faimos expert Bruce Schneier numește astfel de presupuneri „zvonuri”. Este clar că puterea criptografică a algoritmului depinde în mare măsură de proprietățile tabelelor de înlocuire utilizate; în consecință, există tabele de înlocuire slabe (a se vedea un exemplu de mai sus), a căror utilizare poate simplifica atacul asupra algoritmului. Cu toate acestea, posibilitatea utilizării diferitelor tabele de înlocuire pare o idee foarte demnă, în favoarea căreia pot fi citate următoarele două fapte din istoria standardului de criptare DES (a se vedea secțiunea 3.15 pentru detalii):
□ atacurile care utilizează atât criptoanaliza liniară, cât și diferențială a algoritmului DES utilizează caracteristici specifice tabelelor de înlocuire; atunci când utilizați alte tabele, criptoanaliza va trebui să o ia de la capăt;
□ Au fost făcute încercări de consolidare a DES împotriva criptoanalizei liniare și diferențiale prin utilizarea unor tabele de substituție mai robuste; astfel de tabele, care sunt într-adevăr mai robuste, au fost propuse, de exemplu, în algoritmul s 5 DES; dar, din păcate, a fost imposibil să se înlocuiască DES cu s 5 DES, deoarece tabelele de înlocuire sunt definite rigid în standard, respectiv, implementarea algoritmului probabil nu suportă capacitatea de a schimba tabelele cu altele.
O serie de lucrări (de exemplu, și) concluzionează în mod eronat că tabelele secrete de substituții ale algoritmului GOST 28147-89 pot face parte din cheie și pot crește lungimea efectivă a acesteia (ceea ce este nesemnificativ, deoarece algoritmul are o valoare foarte mare de 256-). cheie biți). Cu toate acestea, munca a demonstrat că tabelele de substituție secretă pot fi calculate folosind următorul atac, care poate fi aplicat în practică:
1. Tasta zero este setată și se efectuează căutarea „vectorului zero”, adică valorile z = / (0), unde / () este funcția rundei algoritmului. Această etapă necesită aproximativ 2 operațiuni de criptare.
2. Folosind vectorul zero, se calculează valorile tabelelor de substituție, care nu necesită mai mult de 2 11 operații.
Modificări de algoritm și analiza acestora
Lucrarea a efectuat o criptoanaliză a modificărilor algoritmului GOST 28147-89:
□ algoritmul GOST-H, în care, în raport cu algoritmul original, se modifică ordinea de utilizare a subcheilor, și anume, în rundele 25 la 32, subcheile sunt utilizate în ordine directă, adică în același mod ca în rundele anterioare ale algoritmului;
□ Algoritm GOST® cu 20 de runde, care utilizează XOR pentru introducere în loc de adăugare modulo 32.
Pe baza rezultatelor analizei, s-a concluzionat că GOST-H și GOST © sunt mai slabe decât algoritmul GOST 28147-89 original, deoarece ambele au clase de chei slabe. Trebuie remarcat faptul că, în partea criptoanalizei GOST ©, lucrarea repetă cuvânt cu cuvânt secțiunea dedicată criptoanalizei algoritmului GOST 28147-89, publicată în 2000 de o lucrare binecunoscută (fără trimiteri la original) . Acest lucru pune la îndoială profesionalismul autorilor lucrării și restul rezultatelor acesteia.
O modificare foarte interesantă a algoritmului este propusă în lucrare: tabelele S \… Ss trebuie să fie diferite; în fiecare rundă a algoritmului, acestea trebuie rearanjate după o anumită lege. Această permutare poate depinde de cheia de criptare sau poate fi secretă (adică poate face parte din cheia de criptare mai mare decât cheia originală de 256 de biți). Ambele opțiuni, potrivit autorilor lor, cresc semnificativ rezistența algoritmului împotriva criptoanalizei liniare și diferențiale.
Și încă o modificare legată de tabelele de substituție este dată în lucrare, care analizează una dintre metodele posibile de calculare a tabelelor de substituție pe baza cheii de criptare. Autorii lucrării au concluzionat că o astfel de dependență slăbește algoritmul, deoarece duce la prezența unor chei slabe și la unele potențiale vulnerabilități ale algoritmului.
Analiză completă a algoritmului
Există atacuri asupra rundei complete GOST 28147-89 fără modificări. Una dintre primele lucrări publice în care s-a efectuat analiza algoritmului - o lucrare binecunoscută - este dedicată atacurilor care exploatează punctele slabe ale procedurii de extindere a cheilor a unui număr de algoritmi de criptare cunoscuți. În special, algoritmul complet GOST 28147-89 poate fi întrerupt utilizând criptoanaliza diferențială pe chei legate, dar numai dacă sunt utilizate tabele de substituție slabe. Versiunea de 24 de runde a algoritmului (căreia îi lipsesc primele 8 runde) este deschisă în același mod pentru orice tabel de înlocuire, dar tabelele de înlocuire puternice (de exemplu, prezentate în c) fac un astfel de atac complet nepractic.
Oamenii de știință autohtoni A.G. Rostovtsev și E.B. Makhovenko au propus în 2001, în lucrările lor, o metodă fundamental nouă de criptoanaliza (conform autorilor, mult mai eficientă decât criptoanaliza liniară și diferențială) prin formarea unei funcții obiective dintr-un text simplu cunoscut corespunzător textului cifrat și al acestuia. valoarea cheie dorită și găsirea extremului său corespunzător valorii cheie adevărată. Ei au găsit, de asemenea, o clasă mare de chei slabe pentru algoritmul GOST 28147-89, care fac posibilă spargerea algoritmului folosind doar 4 texte simple selectate și textele cifrate corespunzătoare cu o complexitate destul de scăzută. Criptanaliza algoritmului este continuată în lucrare.
În 2004, un grup de specialiști din Coreea a propus un atac prin care, folosind criptoanaliza diferențială pe chei legate, se poate obține cu o probabilitate de 91,7% a 12 biți a cheii secrete. Atacul necesită 235 de texte clare selectate și 236 operațiuni de criptare. După cum puteți vedea, acest atac este practic inutil pentru un atac real asupra algoritmului.
Algoritmul GOST 28147-89 și cifrul „Magma” (GOST R 34.12-2015)
Schema generală a algoritmului. Algoritmul descris de GOST 28147-89 „Sisteme de procesare a informațiilor. Protecție criptografică. Algoritmul de transformare criptografică”, este un standard intern pentru criptarea simetrică (înainte de 1 ianuarie 2016) și este obligatoriu pentru implementarea în instrumentele de protecție a informațiilor criptografice certificate utilizate în sistemele informaționale de stat și, în unele cazuri, în sistemele comerciale. Certificarea mijloacelor de protecție criptografică a informațiilor este necesară pentru a proteja informațiile care constituie un secret de stat al Federației Ruse și informațiile a căror confidențialitate trebuie asigurată în conformitate cu legislația în vigoare. De asemenea, în Federația Rusă, se recomandă utilizarea algoritmului GOST 28147-89 pentru protecția sistemelor de informații bancare.
Algoritmul GOST 28147-89 (Fig. 2.21) se bazează pe schema Feistel și criptează informațiile în blocuri de 64 de biți, care sunt împărțite în două sub-blocuri de 32 de biți (I și R). Subbloc R, este procesat de funcția de transformare rotundă, după care valoarea sa se adaugă la valoarea subblocului Lj, apoi subblocurile sunt schimbate. Algoritmul are 16 sau 32 de runde, în funcție de modul de criptare (calcularea inserției de imitație sau alte moduri de criptare).
Orez. 2.21.
În fiecare rundă a algoritmului, sunt efectuate următoarele transformări.
1. Suprapunere cheie. Subblocarea conținutului R i adăugat modulo 2 32 cu cheie rotundă K. Kj este partea de 32 de biți a cheii originale, folosită ca cea rotundă. Algoritmul GOST 28147-89 ns utilizează o procedură de extindere a cheii, cheia originală de criptare de 256 de biți este reprezentată ca o concatenare (concatenare) a opt subchei de 32 de biți (Fig. 2.22): K 0, K (, Kt K, K A, K 5, K 6, K 7.
Procesul de criptare folosește una dintre aceste subchei. LA
De la runda 1 până la a 24-a - în ordine directă:
Din runda a 25-a până în a 32-a - în ordine inversă:
Orez. 2.22. Structura cheii de criptare a algoritmului GOST 28147-89
2. Înlocuire tabulară. După ce cheia a fost aplicată, subblocul R i este împărțit în opt părți, dar în 4 biți, valoarea fiecăruia fiind înlocuită individual în conformitate cu tabelul său de înlocuire (S-box). Sunt utilizate în total opt cutii S - S 0, S, S 2, S 3, S 4, S 5, S 6, S 7. Fiecare bloc S al algoritmului GOST 28147-89 este un vector (matrice unidimensională) cu ^ elemente numerotate de la 0 la 15. Valorile blocului S sunt numere de 4 biți, adică numere întregi de la 0 la 15.
Din tabelul S-box este luat un element, al cărui număr ordinal coincide cu valoarea care a venit la intrarea de substituție.
Exemplul 2.6.
Să existe un bloc S de următoarea formă:
Fie ca valoarea 0100 2 = 4 să fie dată la intrarea acestei casete S. Ieșirea casetei S va fi al 4-lea element al tabelului de substituție, adică. 15 = 1111 2 (elementele sunt numerotate începând de la zero).
persoanele de substituție nu sunt definite de standard, așa cum se face, de exemplu, în cifrul DES. Valorile modificabile ale tabelelor de substituție complică în mod semnificativ criptoanaliza algoritmului. În același timp, robustețea algoritmului depinde în mod esențial de alegerea corectă a acestora.
Din păcate, algoritmul GOST 28147-89 are tabele de substituție „slabe”, atunci când se utilizează algoritmul poate fi dezvăluit cu ușurință prin metode criptoanalitice. Printre „slabi” se numără, de exemplu, un tabel trivial de substituții, în care intrarea este egală cu rezultatul (Tabelul 2.16).
Tabelul 2.16
Un exemplu de cutie S slabă
Se crede că valorile specifice ale tabelelor de înlocuire ar trebui păstrate secrete și sunt un element cheie pe termen lung, adică. sunt valabile pentru o perioadă mult mai lungă decât cheile individuale. Cu toate acestea, valorile secrete ale tabelelor de înlocuire nu fac parte din cheie și nu pot crește lungimea efectivă a acesteia.
Într-adevăr, tabelele de substituție secretă pot fi calculate folosind următorul atac, care poate fi aplicat în practică:
- se setează o tastă zero și se efectuează o căutare a unui „vector zero”, adică. sens z = F ( 0), unde F - funcţie de transformare rotundă a algoritmului. Acest lucru necesită aproximativ 2 32 de operațiuni de criptare de testare;
- folosind vectorul zero, se calculează valorile tabelelor de substituție, care nu necesită mai mult de 2 11 operații.
Cu toate acestea, chiar dacă confidențialitatea tabelelor de substituție este încălcată, puterea cifrului rămâne extrem de mare și nu scade sub limita acceptabilă.
De asemenea, se presupune că tabelele de substituție sunt comune pentru toate nodurile de criptare din cadrul unui sistem de protecție criptografică.
Îmbunătățirea structurii cutiilor S este una dintre problemele cele mai intens cercetate în domeniul cifrurilor bloc simetrice. Practic, este necesar ca orice modificări aduse intrărilor S-box-urilor să se reverse în Aleatoriu schimbând aparent ieșirea. Pe de o parte, cu cât cutiile S sunt mai mari, cu atât algoritmul este mai rezistent la metodele de criptoanaliza liniară și diferențială. Pe de altă parte, o masă mare de înlocuire este mai dificil de proiectat.
În algoritmii moderni, cutiile S sunt de obicei un vector (matrice unidimensională) care conține 2 "t- elemente de biți. Intrarea blocului definește numărul elementului, a cărui valoare servește ca ieșire a blocului S.
Au fost propuse o serie de criterii pentru proiectarea cutiilor S. Tabelul de înlocuire trebuie să satisfacă:
- criteriu strict de avalanșă;
- criteriul de independență a biților;
- cerința de neliniaritate din valorile de intrare.
Pentru a îndeplini ultima cerință, s-a propus să se specifice o combinație liniară i biți ( i = 1, ..., T) valorile tabelului de substituție funcții îndoite(eng, îndoit - deviind, în acest caz - de la funcțiile liniare). Funcțiile îndoite formează o clasă specială de funcții booleene caracterizate de cea mai înaltă clasă de neliniaritate și de conformitate cu criteriul strict de avalanșă.
În unele lucrări, pentru S-box, se propune verificarea îndeplinirii efectului de avalanșă garantat de ordinul y - atunci când un bit de intrare se modifică, cel puțin biții de ieșire ai S-box-ului se modifică. Proprietatea efectului de avalanșă garantat de ordinul lui y de la 2 la 5 oferă caracteristici de difuzie suficient de bune ale cutiilor S pentru orice algoritm de criptare.
Când se proiectează mese de înlocuire suficient de mari, se pot folosi următoarele abordări:
- selecție aleatorie (pentru cutiile S mici, poate duce la crearea unor tabele de substituție slabe);
- selecție aleatorie urmată de verificarea conformității cu diverse criterii și respingerea S-box-urilor slabe;
- selecție manuală (prea laborioasă pentru blocuri S mari);
- abordare matematică, de exemplu, generarea folosind funcții îndoite (această abordare este aplicată în algoritmul CAST).
Următoarea procedură pentru proiectarea blocurilor S individuale ale algoritmului GOST 28147-89 poate fi propusă:
- fiecare S-box poate fi descrisă de patru funcții logice, fiecare dintre funcții trebuie să aibă patru argumente logice;
- aceste funcții trebuie să fie suficient de complexe. Această cerință de complexitate nu poate fi exprimată formal, totuși, ca o condiție necesară, se poate cere ca funcțiile logice corespunzătoare, scrise în forma minimă (adică, cu lungimea minimă posibilă a expresiei) folosind operații logice de bază, să nu fie mai scurte decât o anumită valoare cerută;
- funcțiile individuale, chiar și utilizate în tabele de substituție diferite, trebuie să fie suficient de diferite unele de altele.
În 2011, a fost propus un nou atac „întâlnire reflexivă la mijloc”, care reduce ușor rezistența GOST 28147-89 (de la 2256 la 2225). Cel mai bun rezultat al criptoanalizei algoritmului din 2012 permite reducerea puterii acestuia la 2 192, necesitând o dimensiune relativ mare a textului cifrat și cantitatea de date preformate. În ciuda atacurilor propuse, GOST 28147-89 rămâne practic stabil la nivelul actual de dezvoltare a tehnologiei informatice.
Cod „Magma” (GOST R 34.12-2015). Standardul GOST 28147-89 este în vigoare în Rusia de peste 25 de ani. În acest timp, a demonstrat o durabilitate suficientă și o eficiență bună a implementărilor software și hardware, inclusiv a celor de pe dispozitive cu resurse reduse. Deși au fost propuse atacuri criptoanalitice care reduc estimările rezistenței sale (cel mai bun este de până la 2.192), acestea sunt departe de a fi fezabile. Prin urmare, s-a decis includerea algoritmului GOST 28147-89 în standardul de criptare simetric nou dezvoltat.
În magazinul din 2015, au fost adoptate două noi standarde criptografice naționale: GOST R 34.12-2015 „Tehnologia informației. Protecția informațiilor criptografice. Cifre bloc „și GOST R 34.13-2015” Tehnologia informației. Protecția informațiilor criptografice. Moduri de operare ale cifrurilor bloc”, care intră în vigoare la 1 ianuarie 2016.
Standardul GOST R 34.12-2015 conține o descriere a două cifruri bloc cu o lungime a blocului de 128 și 64 de biți. Cifrul GOST 28147-89 cu blocuri de substituție neliniare fixe este inclus în noul GOST R 34.12-2015 ca un cifr pe 64 de biți numit „Magma”.
Mai jos sunt blocurile de înlocuire fixate în standard:
Setul de casete S prezentat în standard oferă cele mai bune caracteristici care determină rezistența criptoalgoritmului la criptoanaliza diferențială și liniară.
Potrivit comitetului tehnic pentru standardizare „Protecția criptografică a informațiilor” (TC 26), fixarea blocurilor de substituție neliniară va face algoritmul GOST 28147-89 mai unificat și va ajuta la eliminarea utilizării blocurilor de substituție neliniare „slabe”. În plus, fixarea în standard a tuturor parametrilor pe termen lung ai cifrului îndeplinește practica internațională acceptată. Noul standard GOST R 34.12-2015 este legat terminologic și conceptual de standardele internaționale ISO/IEC 10116 „Tehnologia informației. Metode de securitate. Moduri de operare pentru „cifrurile bloc de biți” (ISO / IEC 10116: 2006 Tehnologia informației - Tehnici de securitate - Moduri de funcționare pentru un cifr de bloc de n biți) și seria ISO / IEC 18033 „Tehnologia informației. Metode și mijloace de asigurare a siguranței. Algoritmi de criptare ": ISO / IEC 18033-1: 2005" Partea 1. General "(ISO / IEC 18033-1: 2005 Tehnologia informației - Tehnici de securitate - Algoritmi de criptare - Partea 1: General) și ISO / IEC 18033-3: 2010 „Partea 3. Cifre bloc” (ISO / IEC 18033-3: 2010 (Tehnologia informației - Tehnici de securitate - Algoritmi de criptare - Partea 3: Cifre bloc)).
Standardul GOST P 34.12-2015 include, de asemenea, un nou cifru bloc ("Grasshopper") cu o dimensiune a blocului de 128 de biți. Se așteaptă ca acest cifru să fie robust împotriva tuturor atacurilor de cifru bloc cunoscute astăzi.
Modurile de funcționare ale cifrurilor bloc (înlocuire simplă, gamma, gamma cu feedback de ieșire, gamma cu feedback text cifrat, înlocuire simplă cu angajare și dezvoltarea unei inserții de imitație) sunt incluse într-un standard separat GOST R 34.13-2015, care corespunde cu practica internațională acceptată. Aceste moduri sunt aplicabile atât cifrului Magma, cât și noului cifru Grasshopper.
- Se efectuează deplasarea circulară la stânga pe biți cu 11 biți. Decriptarea se efectuează conform aceleiași scheme, dar cu un program diferit de utilizare a cheii: de la prima până la a opta rundă de decriptare - în ordine directă: de la a 9-a până la a 32-a rundă de decriptare - în ordine inversă: Comparativ cu DES cifrul în GOST 28147-89 are următoarele avantaje: o cheie semnificativ mai lungă (256 de biți față de 56 pentru cifrul DES), un atac asupra căruia prin enumerarea în forță brută a setului de chei pare imposibil în acest moment; un program simplu de utilizare a cheii, care simplifică implementarea algoritmului și mărește viteza de calcul. Proiectarea blocurilor S GOST 28147-89. Este evident că schema algoritmului GOST 28147-89 este foarte simplă. Aceasta înseamnă că cea mai mare sarcină de criptare cade pe tabelele de înlocuire. Valorile filelor
- Panasepko S.P. Algoritmi de criptare: o carte de referință specială. SPb .: BHV-Peter-burg, 2009.
- Kara O. Reflection Attacks on Product Ciphers. URL: http://eprint.iacr.org/2007/043.pdf
- Standard rusesc de criptare: putere redusă. 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: „Nu vă grăbiți să-l îngropați”.
Celebrul cercetător, fondatorul criptoanalizei algebrice, Nicolas Courtois, susține că cifrul bloc GOST, care urma să devină un standard internațional în viitorul apropiat, a fost de fapt spart și așteaptă multe publicații în viitor care să-și dezvolte ideile despre instabilitatea acestui algoritm.
Următoarele sunt scurte fragmente din această lucrare, care poate fi considerată ca un atac alarmist în plină standardizare internațională (autorul era cunoscut pentru exagerări similare în raport cu AES, dar lucrarea sa a avut atunci o mare influență teoretică asupra criptoanalizei, dar a avut nu a condus la un atac practic asupra AES în sine). Dar, poate, acesta este și un adevărat avertisment cu privire la începutul etapei „aeronavei care se scufundă într-un strop”, care se poate termina cu colapsul standardului național de criptare, așa cum a fost cazul algoritmului de hashing SHA-1 și algoritmul de hashing MD5 de facto.
GOST 28147-89 a fost standardizat în 1989 și a devenit standardul oficial pentru protecția informațiilor confidențiale pentru prima dată, dar specificația cifrului a rămas închisă. În 1994, standardul a fost declasificat, publicat și tradus în engleză. Prin analogie cu AES (și spre deosebire de DES), GOST are permisiunea de a proteja informațiile clasificate fără restricții, în conformitate cu modul în care este specificat în standardul rus. Acea. GOST nu este un analog al DES, ci un concurent al 3-DES cu trei chei independente sau AES-256. Evident, GOST este un cifr destul de serios care îndeplinește criteriile militare, creat cu așteptarea celor mai serioase aplicații. Cel puțin două seturi de cutii GOST S au fost identificate pe baza aplicațiilor utilizate de băncile rusești. Aceste bănci trebuie să conducă comunicații secrete cu sute de sucursale și să protejeze miliarde de dolari de furturile frauduloase.
GOST este un cifru bloc cu o structură Feistel simplă, cu o dimensiune a blocului de 64 de biți, o cheie de 256 de biți și 32 de runde. Fiecare rundă conține module 2 ^ 32 de adăugare a tastelor, un set de opt casete S de 4 biți și o schimbare ciclică simplă de 11 biți. O caracteristică a GOST este capacitatea de a stoca blocuri S în secret, care poate fi reprezentată ca o a doua cheie care crește materialul efectiv al cheii la 610 de biți. Un set de cutii S a fost publicat în 1994 ca parte a specificației funcției hash GOST-R 34.11-94 și, după cum a scris Schneier, a fost folosit de Banca Centrală a Federației Ruse. De asemenea, este inclus în RFC4357 în partea „id-GostR3411-94-CryptoProParamSet”. A existat o eroare în codurile sursă la sfârșitul cărții lui Schneier (în ordinea S-box). Cea mai precisă implementare de referință de origine rusă nativă poate fi găsită acum în biblioteca OpenSSL. Dacă undeva sunt folosite S-box-uri secrete, atunci acestea pot fi extrase din implementări software și din microcircuite, de fapt, lucrările corespunzătoare au fost publicate.
GOST este un concurent serios
Pe lângă dimensiunea foarte mare a cheii, GOST are un cost de execuție semnificativ mai mic în comparație cu AES și alte sisteme de criptare similare. De fapt, costă mult mai puțin decât AES, care necesită de patru ori mai multe porți logice hardware pentru o securitate mult mai mică.
Nu este surprinzător faptul că GOST a devenit un standard de internet, în special, este inclus în multe biblioteci cripto, cum ar fi OpenSSL și Crypto ++, și devine din ce în ce mai popular în afara țării sale de origine. În 2010, GOST a fost declarat pentru standardizarea ISO ca standard de criptare la nivel mondial. Un număr extrem de mic de algoritmi au reușit să devină standarde internaționale. ISO / IEC 18033-3: 2010 descrie următorii algoritmi: patru cifruri pe 64 de biți - TDEA, MISTY1, CAST-128, HIGHT - și trei cifruri pe 128 de biți - AES, Camellia, SEED. Se propune ca GOST să fie adăugat la același standard ISO / IEC 18033-3.
Pentru prima dată în istoria standardizării industriale, avem de-a face cu un astfel de algoritm competitiv din punct de vedere al optimității între cost și nivelul de securitate. GOST are 20 de ani de eforturi de criptoanaliza și până de curând securitatea sa de nivel militar nu a fost pusă sub semnul întrebării.
După cum autorul a aflat recent din corespondența privată, majoritatea țărilor s-au opus GOST la votul ISO din Singapore, dar rezultatele acestui vot vor fi în continuare luate în considerare la reuniunea plenară ISO SC27, așa că GOST este încă în proces de standardizare la momentul publicarea acestei lucrări.
Opiniile experților despre GOST
Niciuna dintre informațiile și literatura disponibile cu privire la GOST nu oferă motive să credem că cifrul ar putea fi nesigur. Dimpotrivă, dimensiunea mare a cheii și numărul mare de runde fac ca GOST, la prima vedere, să fie potrivit pentru decenii de utilizare.
Oricine este familiarizat cu Legea lui Moore realizează că, teoretic, cheile pe 256 de biți vor rămâne în siguranță timp de cel puțin 200 de ani. GOST a fost cercetat pe larg de experți de top în domeniul criptografiei, cunoscuți în domeniul analizei cifrului bloc, precum Schneier, Biryukov, Dankelman, Wagner, mulți oameni de știință australieni, japonezi și ruși, experți în criptografie de la ISO și toți cercetătorii au a exprimat că totul arată așa că el poate fi sau ar trebui să fie în siguranță. Deși opinia a ajuns la o înțelegere largă că structura GOST în sine este extrem de slabă, de exemplu, în comparație cu DES, în special, difuzarea nu este atât de bună, cu toate acestea, acest lucru s-a datorat întotdeauna faptului că aceasta ar trebui compensată prin un număr mare de runde (32), precum și o neliniaritate și difuzie suplimentare oferite de adăugarea de modul.
Biryukov și Wagner au scris: „Numărul mare de runde (32) și construcția Feistel bine studiată, combinate cu permutările succesive ale lui Shannon, oferă o bază solidă pentru securitatea GOST”. În aceeași lucrare citim: „după o investiție considerabilă de timp și efort, nu s-a făcut niciun progres în criptoanaliza standardului în literatura deschisă”. Astfel, nu au existat atacuri semnificative care să permită decriptarea sau recuperarea cheii într-un scenariu realist în care GOST este utilizat în criptarea cu multe chei aleatoare diferite. În schimb, există o mulțime de lucrări cunoscute privind atacurile asupra cheilor slabe în GOST, atacuri cu chei asociate, atacuri privind recuperarea S-box-urilor secrete. La Crypto-2008, a fost prezentată o hacking a unei funcții hash bazată pe acest cifr. În toate atacurile, atacatorul are un nivel de libertate semnificativ mai mare decât este permis de obicei. Până acum, nu s-au găsit atacuri criptografice serioase asupra GOST în aplicațiile tradiționale de criptare folosind chei selectate aleatoriu, ceea ce în 2010 a fost exprimat prin fraza finală: „în ciuda eforturilor semnificative ale criptoanalistilor din ultimii 20 de ani, GOST nu a fost încă cracked” (Axel Poschmann, San Ling și Huaxiong Wang: 256 Bit Standardized Crypto for 650 GE GOST Revisited, În CHES 2010, LNCS 6225, pp. 219-233, 2010).
Analiză liniară și diferențială GOST
În binecunoscuta carte a lui Schneier, citim: „Împotriva criptoanalizei diferențiale și liniare, GOST este probabil mai robust decât DES”. Evaluarea principală a securității GOST a fost dată în 2000 de Gabidulin și colab.. Rezultatele lor sunt foarte impresionante: cu un nivel de securitate de 2 ^ 256 set, cinci runde sunt suficiente pentru a proteja GOST de criptoanaliza liniară. Mai mult, chiar și după înlocuirea S-box-urilor cu altele identice și singura operațiune de cifră neliniară - adăugare mod 2 ^ 32 - cifrul este încă rezistent la criptoanaliza liniară după 6 runde din 32. Criptanaliza diferențială GOST pare relativ mai ușoară și atrage mai multă atenție. Pentru un nivel de securitate de 2 ^ 128, cercetătorii (Vitaly V. Shorin, Vadim V. Jelezniakov și Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST, Preprint submitted to Elsevier Preprint, 4 aprilie 2001) au presupus o durabilitate suficientă la 7 runde. . Potrivit acestora, spargerea GOST în mai mult de cinci runde este „extrem de dificilă”. Mai mult, doi cercetători japonezi au arătat că un atac diferențial direct clasic cu o caracteristică diferențială are o probabilitate extrem de scăzută de a trece printr-un număr mare de runde. Pe baza faptului de a studia o caracteristică diferențială iterativă suficient de „bună” pentru un număr limitat de runde (care în sine are o probabilitate de a trece nu mai bine de 2-11,4 pe rundă), valoarea setului de chei adecvate este mai mică de jumătate. . Pentru un GOST complet, un astfel de atac cu o singură caracteristică va funcționa numai cu o parte neglijabilă a tastelor de ordinul 2-62 (și chiar și în această mică parte va avea probabilitatea de a trece nu mai mult de 2-360). ).
Atacurile mai sofisticate implică diferenţiale multiple care urmează anumite modele, cum ar fi utilizarea S-box-urilor individuale care au diferenţiale zero, în timp ce alţi biţi au diferenţiale diferite de zero. Vorbim despre atacuri discriminatorii bazate pe proprietățile slabe de difuzie ale GOST. Cel mai bun dintre astfel de atacuri funcționează împotriva a 17 runde de GOST, depinde de cheie și are un discriminator extrem de slab de date aleatorii la ieșire în sine, astfel încât să poată fi utilizat cumva pentru a obține informații despre cheie.
Alunecarea și abaterea atacurilor
Potrivit lui Biryukov și Wagner, structura GOST, care include ordinea inversă a subcheilor în ultimele runde, o face rezistentă la atacurile glisante (așa-numitele „atacuri glisante”). Cu toate acestea, din cauza prezenței unei mari auto-asemănări în cifr, acest lucru permite atacuri de inversare a cheilor asupra combinațiilor de puncte fixe și proprietăți de „reflectare” (așa-numitele „atacuri reflective”) pentru anumite chei slabe. Complexitatea acestui atac este de 2 ^ 192 și 2 ^ 32 de texte clare potrivite.
Ultimele rezultate
Noile atacuri folosesc, de asemenea, reflecția și chiar au spart GOST, care a fost prezentat la conferința FSE 2011. Aceste atacuri au fost descoperite și independent de autorul acestei lucrări. Atacul necesită 2 ^ 132 de octeți de memorie, ceea ce este de fapt mai rău decât atacurile mai lente cu cerințe mai puține de memorie.
Numeroase noi atacuri de auto-similaritate funcționează împotriva tuturor cheilor GOST și vă permit să spargeți un GOST complet cu o cheie de 256 de biți, și nu doar pentru cheile slabe, așa cum era înainte. Toate aceste atacuri necesită mult mai puțină memorie și sunt semnificativ mai rapide.
Aceste noi atacuri pot fi văzute ca exemple ale unei noi paradigme generale pentru criptoanaliza cifrurilor bloc numită „reducere al complexității algebrice”, care generalizează aceste atacuri la multe cazuri particulare de atacuri cu puncte fixe, alunecări, involuții și cicluri cunoscute. Este important ca printre familia tuturor acestor atacuri să fie și cele care permit criptoanaliza GOST fără reflexii și fără puncte simetrice care apar în cursul calculelor. Un exemplu este un simplu atac de hacking GOST fără reflectare în această lucrare.
Criptanaliză algebrică și atacuri cu complexitate scăzută a datelor asupra cifrurilor cu runde reduse
Atacurile algebrice asupra cifrurilor bloc și flux pot fi reprezentate ca o problemă de rezolvare a unui sistem mare de ecuații algebrice booleene care urmează geometria și structura unei anumite scheme criptografice. Ideea se întoarce la Shannon. În practică, a fost prezentat pentru DES (prezentat prima dată de autorul acestei lucrări) ca o metodă formală de codificare și poate sparge 6 runde într-un singur text simplu cunoscut. Manipularea ecuațiilor se bazează pe algoritmi XL, baze Gröbner, metoda ElimLin, rezolvatori SAT.
În practică, atacurile algebrice au fost implementate împotriva unui număr foarte mic de runde de cifruri bloc, dar au dus deja la spargerea cifrurilor de flux și există și succese în spargerea cifrurilor ultra-ușoare pentru micro-echipamente. Din cauza dificultății în ceea ce privește dimensiunea memoriei și estimările costurilor de calcul, acestea sunt combinate cu alte atacuri.
Cum să piratați GOST?
Un atac algebric asupra unui GOST complet este prezentat mai detaliat în această publicație. Într-o lucrare anterioară, autorul a subliniat deja 20 de atacuri algebrice asupra GOST și se așteaptă la un număr mare de ele în viitorul apropiat. Atacul propus în această lucrare nu este cel mai bun dintre ele, dar deschide o cale ușoară (cel puțin pentru înțelegerea criptografilor) pentru dezvoltările ulterioare pentru a crea o metodologie specifică pentru spargerea GOST.
Rezultatul practic este încă modest: 2 ^ 64 de text clar cunoscut și 2 ^ 64 de memorie pentru stocarea perechilor de text simplu/cifrat fac posibilă spargerea GOST 2 ^ 8 mai rapid decât forța brută simplă. Dar în ceea ce privește criptoanaliza, acest lucru face ca afirmația că „GOST a fost piratat” este complet corectă.
concluzii
GOST este conceput pentru a oferi un nivel militar de securitate pentru 200 de ani de acum înainte. Majoritatea experților de top care au studiat GOST au ajuns să fie de acord că „în ciuda eforturilor criptoanalitice semnificative de peste 20 de ani, GOST nu a fost încă spart”. În 2010, GOST este promovat la ISO 18033 ca standard global de criptare.
Fundamentul ideilor despre criptoanaliza algebrică a apărut acum peste 60 de ani. Dar numai în ultimii 10 ani au fost dezvoltate instrumente software eficiente pentru rezolvarea (parțială) a multor probleme NP-complete. Un număr de coduri de flux au fost sparte. Doar un cifr de bloc a fost rupt prin această metodă - slabul KeeLoq însuși. În această lucrare, autorul sparge un cifr GOST important, folosit efectiv. El observă că aceasta este prima dată în istorie când un cifr de stare standardizat a fost spart prin criptoanaliza algebrică.
Un simplu atac „MITM cu reflecție” asupra GOST a fost deja prezentat la conferința FSE 2011. În lucrarea luată în considerare în acest articol, un alt atac este prezentat doar pentru a ilustra faptul că multe atacuri asupra GOST au apărut deja acum, dintre care multe sunt mai rapide, iar un atac algebric necesită mult mai puțină memorie și deschide un spațiu aproape inepuizabil de posibilități pentru ca un adversar să atace cifrul în moduri diferite. De asemenea, în această lucrare, se arată că nu este nevoie să folosiți proprietatea reflection pentru hacking.
Autorul susține că este evident că GOST are defecte serioase și acum nu oferă nivelul de durabilitate cerut de ISO. Multe atacuri asupra GOST sunt prezentate în cadrul confirmării paradigmei de reducere a complexității algebrice.
În cele din urmă, cercetătorul notează în special unele fapte care nu sunt încă la îndemâna cititorului, dar sunt cunoscute de cercetător, care sunt importante în cursul procesului de standardizare ISO. Acest atac nu este doar un atac de „certificare” asupra GOST, care este mai rapid decât atacul cu forță brută. De fapt, standardizarea GOST ar fi acum extrem de periculoasă și iresponsabilă. Acest lucru se datorează faptului că unele dintre atacuri sunt practice. În practică, unele chei GOST pot fi chiar decriptate, fie că sunt chei slabe sau chei din aplicații reale private ale GOST. În lucrarea anterioară, autorul oferă o analiză detaliată a cazurilor de posibilitate a atacurilor practice. În mod semnificativ, „aceasta este pentru prima dată în istorie când un cifr bloc standardizat serios conceput pentru a proteja secretele de grad militar și conceput pentru a proteja secretele de stat pentru guverne, bănci mari și alte organizații a fost compromis de un atac matematic”.
