Cifrarea fluxului

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 1 decembrie 2020; verificările necesită 2 modificări .

Un stream [1] [2] sau stream cipher [3] este un cifru simetric în care fiecare caracter text simplu este convertit într-un caracter criptat, în funcție nu numai de cheia utilizată, ci și de locația sa în fluxul de text simplu. Un cifr de flux implementează o abordare diferită a criptării simetrice decât cifrurile bloc .

Istorie

Cifrurile în flux bazate pe registre de deplasare au fost utilizate în mod activ în anii de război, cu mult înainte de apariția electronicii. Au fost ușor de proiectat și implementat.

În 1965, Ernst Selmer, criptograful șef al guvernului norvegian, a dezvoltat teoria secvenței registrului de deplasare . Mai târziu, Solomon Golomb , un matematician al Agenției Naționale de Securitate din SUA , a scris o carte numită „Shift Register Sequences” în care a subliniat principalele sale realizări în acest domeniu, precum și pe cele ale lui Selmer.

Lucrarea lui Claude Shannon , publicată în 1949, a adus o mare popularitate cifrurilor în flux , în care Shannon a dovedit securitatea absolută a cifrului Vernam (cunoscut și sub numele de blocul de unică folosință). În cifrul Vernam , cheia are o lungime egală cu lungimea mesajului transmis în sine. Cheia este folosită ca gamma și, dacă fiecare bit al cheii este ales la întâmplare, atunci este imposibil să spargeți cifrul (deoarece toate textele posibile vor fi la fel de probabile). Până în prezent, au fost creați un număr mare de algoritmi de criptare a fluxului , precum: A3 , A5 , A8 , MUGI , PIKE , RC4 , SEAL .

Modul Gamma pentru cifrurile de flux

Cea mai simplă implementare a cifrului de flux este prezentată în figură. Generatorul gamma produce un flux cheie (gamma): . Să notăm fluxul de biți text simplu ca . Apoi fluxul de biți de text cifrat este obținut prin aplicarea operației XOR : unde . $k_1,k_2,k_3,\dots ,k_L$ $m_1,m_2,m_3,\dots ,m_L$ $c_1,c_2,c_3,\dots ,c_L$ $c_i=m_i\oplus k_i$

Decriptarea se realizează prin operația XOR între același gamma și textul cifrat: . $m_i=c_i\oplus k_i$

Evident, dacă secvența de biți gamma nu are perioadă și este aleasă aleatoriu, atunci este imposibil să spargeți cifrul. Dar acest mod de criptare are și caracteristici negative. Astfel, cheile care sunt comparabile ca lungime cu mesajele transmise sunt greu de utilizat în practică. Prin urmare, se utilizează de obicei o lungime mai mică a cheii (de exemplu, 128 de biți). Folosind-o, este generată o secvență de joc pseudo-aleatorie (trebuie să satisfacă postulatele Golomb ). Desigur, pseudo-aleatoria gamma poate fi exploatată într-un atac asupra unui cifr de flux.

Clasificarea cifrurilor fluxului

Să presupunem, de exemplu, că în modul gamma pentru cifrurile de flux, un caracter al textului cifrat a fost distorsionat în timpul transmisiei pe un canal de comunicație . Evident, în acest caz, toate semnele primite fără distorsiuni vor fi decodificate corect. Se va pierde doar un caracter al textului. Și acum să ne imaginăm că unul dintre caracterele textului cifrat s-a pierdut în timpul transmisiei prin canalul de comunicare. Acest lucru va duce la decodarea incorectă a întregului text care urmează caracterului pierdut.
Practic, toate canalele de transmisie a datelor pentru sistemele de criptare în flux continuu conțin interferențe . Prin urmare, pentru a preveni pierderea de informații, problema sincronizării criptării și decriptării textului este rezolvată. Conform metodei de rezolvare a acestei probleme, sistemele de cifrare sunt împărțite în sisteme sincrone și auto-sincronizate.

Cifruri de flux sincron

Definiție:

Cifrele de flux sincron (SPC) sunt cifruri în care un flux de chei este generat independent de textul simplu și textul cifrat.

Când este criptat, generatorul de flux de cheie produce biți de flux de cheie care sunt identici cu biții de flux de cheie atunci când sunt decriptați. Pierderea semnului de text cifrat va face ca cei doi generatori să nu se sincronizeze, făcând imposibilă decriptarea restului mesajului. Evident, în această situație, emițătorul și receptorul trebuie să se resincronizeze pentru a continua să lucreze.

Sincronizarea se face de obicei prin inserarea unor markeri speciali în mesajul transmis. Ca urmare, un caracter ratat în timpul transmiterii duce la decriptare incorectă numai până când unul dintre jetoane este primit.

Rețineți că sincronizarea trebuie efectuată în așa fel încât să nu se repete nicio parte a fluxului de chei. Prin urmare, nu are sens să transferați generatorul într-o stare anterioară.

Avantajele SPS:

nici un efect de propagare a erorilor (doar un bit distorsionat va fi decodat incorect);
preveni orice inserare și ștergere a textului cifrat, deoarece ar provoca o pierdere a sincronizării și ar fi detectate.

Contra SPS:

vulnerabil la schimbarea biților individuali ai textului cifrat. Dacă atacatorul știe textul simplu , el poate schimba acești biți astfel încât să fie decriptați așa cum dorește.

Cifruri de flux cu auto-sincronizare

Ideea de bază a construcției a fost brevetată în 1946 în SUA .

Definiție:

Cifrele de flux cu auto-sincronizare (cifrele de flux asincrone (ATS)) sunt cifruri în care fluxul de chei este creat de o funcție a cheii și de un număr fix de caractere ciphertext.

Deci, starea internă a generatorului keystream este o funcție a celor N biți anteriori ai textului cifrat. Prin urmare, generatorul de flux de chei de decriptare, după ce a primit N biți, este sincronizat automat cu generatorul de criptare.

Implementarea acestui mod este după cum urmează: fiecare mesaj începe cu un antet aleatoriu de lungime N biți; antetul este criptat, transmis și decriptat; decodarea este greșită, dar după acești N biți ambele generatoare vor fi sincronizate.

Avantajele APS:

Statistici agitate în text simplu. Deoarece fiecare caracter al textului simplu afectează următorul text cifrat, proprietățile statistice ale textului clar sunt extinse la întregul text cifrat. Prin urmare, PNW poate fi mai rezistent la atacurile de redundanță în text simplu decât PNW.

Contra ale APS:

propagarea erorilor (fiecare bit greșit al textului cifrat corespunde la N erori în textul simplu);
sensibil la deschidere prin retransmisie.

Cifruri în flux bazate pe registre de deplasare cu feedback liniar (LFSR)

Baze teoretice

Există mai multe motive pentru utilizarea registrelor de deplasare liniară în criptografie:

algoritmi criptografici de înaltă performanță
utilizarea doar a celor mai simple operații de adunare și înmulțire, implementate în hardware în aproape toate dispozitivele de calcul
proprietăți criptografice bune (secvențele generate au o perioadă lungă și proprietăți statistice bune)
ușurința analizei folosind metode algebrice datorită structurii liniare

Definiție: Un registru de deplasare cu feedback liniar de lungime L este format din L celule numerotate , fiecare dintre acestea fiind capabilă să stocheze 1 bit și are o intrare și o ieșire; și un semnal de ceas , care controlează offset-ul datelor. În fiecare unitate de timp se efectuează următoarele operații: $0,1,2,\dots L-1$

conținutul celulei face parte din secvența de ieșire; $L-1$
conținutul celulei --a este mutat în celulă pentru orice , . $i$ $i+1$ $i$ $0\leq i<L-1$
noul conținut al celulei este determinat de bitul de feedback, care este calculat prin adăugare modulo 2 cu anumiți coeficienți ai biților celulei . $0$ $0,1,2,\dots L-1$

La primul pas: La al doilea pas: Următoarea relație descrie funcționarea LFSR în termeni generali: Dacă scriem biți egali cu zero în toate celulele, atunci sistemul va genera o secvență formată din toate zerourile. Dacă scriem biți diferit de zero, obținem o secvență semi-infinită. Secvența este determinată de coeficienți Să vedem care poate fi perioada unui astfel de sistem: Număr de umpluturi nenule: Prin urmare, . După apariția unei umpleri, care a fost înainte, procesul va începe să se repete. Procesul de completare a registrului, așa cum se arată mai sus, este reprezentat de o ecuație a diferenței liniare. Să transferăm toți termenii într-o singură parte a egalității, obținem: . $S_L=c_1 \cdot S_{L-1}\oplus c_2 \cdot S_{L-2}\oplus \dots \oplus c_L \cdot S_0.$

$S_{L+1}=c_1 \cdot S_L\oplus c_2 \cdot S_{L-1}\oplus \dots \oplus c_L \cdot S_1.$

$S_j=c_1 \cdot S_{j-1}\oplus c_2 \cdot S_{j-2}\oplus \dots\oplus c_L \cdot S_{jL}.$
$c_1,c_2,\dots ,c_L.$
$T$
$2^{L}-1.$ $T\leqslant 2^L-1$

$S_{j}\oplus c_{1}\cdot S_{j-1}\oplus c_{2}\cdot S_{j-2}\oplus \dots \oplus c_{L}\cdot S_{jL }=0$

Să desemnăm: . Apoi: $S_{j}=D^{-j)$
$(1 \oplus c_1\cdot D \oplus c_2\cdot D^2 \oplus \dots \oplus c_L\cdot D^L )\cdot D^{-j}.$

$C(D) = 1 \oplus c_1\cdot D \oplus c_2 \cdot D^2 \oplus \dots \oplus c_L\cdot D^L.$

O proprietate importantă a acestui polinom este reductibilitatea.
Definiție: Un
polinom se numește reductibil dacă poate fi reprezentat ca produs a două polinoame de grade mai mici cu coeficienți dintr-un câmp dat (în cazul nostru, cu coeficienți binari). Dacă o astfel de reprezentare nu are loc, atunci se spune că polinomul este ireductibil .
Dacă polinomul este ireductibil și primitiv , atunci perioada va fi aceeași cu perioada maximă posibilă, egală cu $C(D)$ $2^{L}-1.$

Exemplu: Luați un polinom primitiv ireductibil Acest polinom poate fi scris ca - se scriu grade la care există coeficienți nenuli. Scriem în starea inițială în celule și determinăm lungimea perioadei generatorului: $C(D)=D^{3}+D^{2}+1(c_{3}=1,c_{2}=1,c_{1}=0).$ $(3,2,0)$
$001$

Masa. Determinarea perioadei generatorului

Părere	Celula 0	Celula 1	celula 2
unu	0	0	unu
0	unu	0	0
unu	0	unu	0
unu	unu	0	unu
unu	unu	unu	0
0	unu	unu	unu
0	0	unu	unu
unu	0	0	unu

Perioada generatorului este Ieșirea generatorului va fi secvența: Să dăm exemple ale unor polinoame primitive modulo 2: $7(2^{3}-1=7).$ $1001011 1001011 1001011\dots$

$(1.0), (2.1.0), (3.1.0), (4.1.0), (5.2.0), (6.1.0), (7.1 ,0), (7,3,0), (8) ,4,3,2,0), (9,4,0)\puncte$

Complexitate liniară

Complexitatea liniară a unei secvențe binare este una dintre cele mai importante caracteristici ale operației LFSR. Prin urmare, ne oprim asupra acestui subiect mai detaliat.
Înainte de a defini complexitatea liniară, introducem câteva notații. - o secvență infinită cu membri - o secvență finită de lungime , ai cărei membri sunt LFSR se spune că generează o secvență dacă există o stare inițială în care secvența de ieșire LFSR coincide cu . În mod similar, se spune că LFSR generează o secvență finală dacă există o stare inițială pentru care secvența de ieșire LFSR are ca primii termeni membrii secvenței . În cele din urmă, oferim o definiție a complexității liniare a unei secvențe binare infinite. Definiție: Complexitatea liniară a unei secvențe binare infinite este numărul , care este definit după cum urmează:
$S$ $S1,S2,S3,\puncte$
$S_{n}$ $n$ $S_1,S_2,S_3,\dots,S_{n-1}.$
$S$ $S$ $S_{n}$ $n$ $S_{n}$

$S$ $L(S)$

Dacă este secvența zero , atunci $S$ $S=0,0,0,0,\dots ,$ $L(S)=0.$
Dacă nu există LFSR care să genereze , atunci este egal cu infinitul . $S$ $L(S)$
În caz contrar, există lungimea celui mai scurt LFSR care generează . $L(S)$ $S$

Definiție:
Complexitatea liniară a unei secvențe binare finite este numărul , care este egal cu lungimea celui mai scurt LFSR care generează o secvență care are ca primi termeni . Proprietăți de complexitate liniară: Fie și fie secvențe binare. Atunci: 1. Pentru orice complexitate liniară a subsecvenței satisface inegalitățile 2. dacă și numai dacă este o succesiune zero de lungime . 3. dacă și numai dacă . 4. Dacă este periodic cu o perioadă , atunci 5. Un algoritm eficient pentru determinarea complexității liniare a unei secvențe binare finite este algoritmul Berlekamp-Massey . $S_{n}$ $L(S_n)$ $n$ $S_{n}$
$S$ $K$
$n>0$ $S_{n}$ $0\leqslant L(S_n) \leqslant n.$
$L(S_{n})=0$ $S_{n}$ $n$
$L(S_{n})=n$ $S_{n}=0,0,0,\dots ,1$
$S$ $N$ $L(S_{n})\leqslant N.$
$L(S \oplus K)\leqslant L(S) + L(K).$

Cifruri în flux bazate pe LFSR. Complicație

Din păcate, secvența de ieșire LFSR este ușor de previzibil. Deci, cunoscând 2L caractere ale secvenței de ieșire, este ușor să găsiți umplerea inițială a registrului prin rezolvarea unui sistem de ecuații liniare (vezi paragraful „Cifuri de flux bazate pe registre de deplasare cu feedback liniar”).

Se crede că, pentru utilizare criptografică, secvența de ieșire LFSR trebuie să aibă următoarele proprietăți:

perioada mare
complexitate liniară mare
proprietăți statistice bune

Există mai multe metode de proiectare a generatoarelor de flux de cheie care distrug proprietățile liniare ale LFSR și, prin urmare, fac astfel de sisteme mai sigure din punct de vedere criptografic:
1. folosind o funcție neliniară care combină ieșirile mai multor LFSR
2. folosind o funcție de filtrare neliniară pentru conținutul fiecărei celule a unui singur LFSR
3. folosind ieșirea unui LFSR pentru a controla semnalul de ceas al unuia (sau mai multor) LFSR.

Combinație neliniară de generatoare

Se știe că fiecare funcție booleană poate fi scrisă ca o sumă modulo 2 a produselor de ordine ale variabilelor independente , . Această expresie se numește forma normală algebrică a funcției . Ordinea neliniară a unei funcții este ordinea maximă a termenilor în notația formei sale normale algebrice. De exemplu, o funcție booleană are o ordine neliniară de 3. Ordinea neliniară maximă posibilă a unei funcții booleene este egală cu numărul de variabile.Să presupunem că acum avem registre de deplasare cu feedback liniar, lungimile lor sunt diferite pe perechi și mai mare de doi. Toate registrele sunt combinate cu o funcție neliniară , așa cum se arată în figură. Funcția este reprezentată în formă normală algebrică. Atunci complexitatea liniară a fluxului cheie este . Dacă sunt numere coprime perechi, atunci lungimea perioadei fluxului de chei este egală cu: . De exemplu, dacă , atunci . Și lungimea perioadei fluxului cheie este . $f(x_{1},x_{2},\dots,x_{n})$ $m$ $0 \leqslant m \leqslant n$ $f$ $f$
$f(x_1,x_2,x_3,x_4 )=x_1 \oplus x_2 \oplus x_4 \oplus x_1 x_3 \oplus x_2 x_3 x_4$ $n.$
$n$ $L_1, L_2, L_3, \dots , L_n$ $f(x_1,x_2,\dots,x_n)$ $f$ $f(L_1,L_2,\dots,L_n)$
$L_1, L_2,\dots, L_n$ $(2^{L_1}-1)\cdot(2^{L_2}-1) \cdots (2^{L_n }-1)$ $L_{i}=10$ $(2^{L_1}-1)\aproximativ 10^3$ $(10^{3})^{n}$

Exemplu (generator Geff):
Acest generator folosește trei LFSR-uri combinate într-un mod neliniar. Lungimile acestor registre sunt numere prime perechi. Funcția neliniară pentru un generator dat poate fi scrisă după cum urmează: ${\displaystyle L_{1},L_{2},L_{3))$

$f(x_1, x_2, x_3 )=x_1 x_2 \oplus (1+x_2 ) x_3=x_1 x_2 \oplus x_2 x_3 \oplus x_3.$

Durata perioadei: $(2^{L_1}-1)\cdot(2^{L_2}-1)\cdot(2^{L_3}-1).$

Complexitate liniară: $L=L_{1}\cdot L_{2}+L_{2}\cdot L_{3}+L_{3}.$

Generatorul Geff este slab criptografic deoarece informațiile despre stările generatoarelor LFSR 1 și LFSR 3 sunt conținute în secvența sa de ieșire. Pentru a înțelege acest lucru, să notăm cei --i biți de ieșire ai LFSR 1,2,3 și , respectiv, fluxul de chei . Atunci probabilitatea de corelare a secvenței în raport cu secvența : $x_{1}(t),x_{2}(t),x_{3}(t),z(t)$ $t$ $x_1(t)$ $z(t)$

$P(z(t)=x_{1}(t))=P(x_{2}(t)=1)+P(x_{2}(t)=0)\cdot P(x_{ 3}(t)=x_{1}(t))=1/2+1/2\cdot 1/2=3/4.$

În mod similar, din acest motiv, în ciuda perioadei lungi și a complexității liniare destul de ridicate, generatorul Geff se pretează la atacuri de corelație. $P(z(t)=x_{3}(t))=3/4.$

Generatoare pe filtre neliniare

Ieșirea fiecărei celule este transmisă la intrarea unei funcții de filtrare booleană neliniară . Să presupunem că funcția de filtrare este de ordine , atunci complexitatea liniară a fluxului cheie este de cel mult . $f$ $m$ $L_m=\sum^{m}_{i=1} {L \alege i}$

Oscilatoare bazate pe ceas

În combinațiile neliniare de oscilatoare și oscilatoare cu filtru neliniar, mișcarea datelor în toate LFSR-urile este controlată de un singur semnal de ceas.
Ideea principală a funcționării tipului de generatoare luate în considerare este introducerea neliniarității în funcționarea generatoarelor de flux cheie bazate pe LFSR prin controlul semnalului de ceas al unui registru prin secvența de ieșire a altuia.
Există 2 tipuri de oscilatoare bazate pe controlul ceasului:
1. oscilator cu pas variabil
2. oscilator de compresie.

Generator de pas variabil

Ideea principală:
LFSR 1 este folosit pentru a controla mișcarea biților celorlalte două LFSR-uri 2 și 3.

Algoritm de operare:
1. Registrul LFSR 1 este sincronizat cu un semnal de ceas extern
2. Dacă ieșirea registrului LFSR 1 este unu , atunci registrul LFSR 2 este furnizat cu un semnal de ceas, iar LFSR 3 își repetă bitul de ieșire anterior (pentru momentul inițial, bitul de ieșire LFSR 3 anterior este luat egal cu 0)
3. Dacă ieșirea registrului LFSR 1 este zero , atunci un semnal de ceas este aplicat registrului LFSR 3, iar LFSR 2 își repetă ieșirea anterioară bit (pentru timpul inițial, bitul de ieșire anterior LFSR 2 este de asemenea luat egal cu 0)
4. Secvența de biți de ieșire a generatorului cu pas variabil este rezultatul aplicării operației XOR pe biți la secvențele de ieșire ale LFSR 2 și registrele LFSR 3.

Creșterea siguranței generatoarelor cu pas variabil:

lungimile registrelor RLOS 1, RLLS 2, RLLS 3 trebuie alese în perechi prin numere prime
lungimile acestor registre trebuie să fie numere apropiate.

Generator compresiv

Registrul de control LFSR 1 este utilizat pentru a controla ieșirea LFSR 2. Algoritm:

Registrele RLOS 1 și RLLS 2 sunt sincronizate printr-un semnal de ceas comun ;
Dacă bitul de ieșire al LFSR 1 este egal cu 1, ieșirea generatorului este formată din bitul de ieșire al registrului LFSR 2;
Dacă bitul de ieșire LFSR 1 este 0, bitul de ieșire LFSR 2 este eliminat.

Generatorul de compresie este simplu, scalabil și are proprietăți de securitate bune. Dezavantajul său este că rata de generare a cheilor nu va fi constantă decât dacă se iau unele măsuri de precauție.

Pentru a crește siguranța generatorului de compresie:

lungimile registrelor LFSR 1 și LFSR 2 trebuie să fie numere coprime ;
este de dorit să se utilizeze o conexiune ascunsă între registrele LFSR 1 și LFSR 2.

Principalele diferențe dintre cifrurile flux și cifrurile bloc

Majoritatea codurilor secrete existente pot fi clasificate fără ambiguitate fie ca fiind cifruri flux, fie ca bloc . Dar granița teoretică dintre ele este destul de neclară. De exemplu, algoritmii de criptare bloc sunt utilizați în modul de criptare flux (de exemplu: pentru algoritmul DES , modurile CFB și OFB ).

Luați în considerare principalele diferențe dintre cifrurile de flux și bloc, nu numai în ceea ce privește securitatea și comoditatea lor, ci și în ceea ce privește studiul lor în lume:

Cel mai important avantaj al cifrurilor în flux față de cifrurile bloc este viteza mare de criptare, proporțională cu viteza de intrare a informațiilor; prin urmare, este furnizată criptarea aproape în timp real, indiferent de volumul și adâncimea de biți a fluxului de date convertit.
în cifrurile cu flux sincron (spre deosebire de cifrurile bloc) nu există niciun efect de propagare a erorilor, adică numărul de elemente distorsionate din secvența decriptată este egal cu numărul de elemente distorsionate ale secvenței criptate care au venit din canalul de comunicație .
structura cheii fluxului poate avea vulnerabilități care permit criptoanalistului să obțină informații suplimentare despre cheie (de exemplu, cu o perioadă mică de cheie, criptoanalistul poate folosi părțile găsite ale cheii fluxului pentru a decripta textul privat ulterior).
PN-urile, spre deosebire de PN-urile, pot fi adesea atacate cu algebră liniară (deoarece ieșirile registrelor individuale de deplasare cu feedback liniar pot fi corelate cu gamma). De asemenea, analiza liniară și diferențială este folosită cu mare succes pentru a sparge codurile de flux .

Acum despre starea lumii:

cea mai mare parte a lucrărilor privind analizarea și spargerea cifrurilor bloc se ocupă de algoritmi de criptare bazați pe standardul DES ; pentru cifrurile de flux, nu există o zonă de studiu dedicată; metodele de hacking sunt foarte diverse.
pentru cifrurile de flux, se stabilește un set de cerințe care sunt criterii de fiabilitate (perioade mari de secvențe de ieșire, postulate ale lui Golomb , neliniaritate); nu există criterii atât de clare pentru BS .
cercetarea și dezvoltarea cifrurilor de flux este efectuată în principal de centre criptografice europene, cifrurile bloc - de cele americane.
studiul cifrurilor în flux este mai dinamic decât cifrurile bloc; nu au existat descoperiri recente notabile în domeniul algoritmilor DES, în timp ce în domeniul cifrurilor în flux s-au înregistrat multe succese și eșecuri (unele scheme care păreau stabile, în urma unor investigații ulterioare, nu s-au ridicat la nivelul speranțelor inventatorilor) .

Proiectarea cifrurilor de flux

Potrivit lui Rainer Rueppel, există patru abordări principale pentru proiectarea cifrului în flux:

Abordarea teoretică a sistemului se bazează pe crearea unei probleme complexe, neexplorate anterior, pentru criptoanalist.
Abordarea teoretică a complexității se bazează pe o problemă complexă, dar binecunoscută (de exemplu, factorizarea numerelor sau logaritmul discret ).
Abordarea tehnologiei informației se bazează pe o încercare de a ascunde textul simplu de criptoanalist - indiferent cât de mult timp este petrecut pentru decriptare, criptoanalistul nu va găsi o soluție clară.
Abordarea randomizată se bazează pe crearea unei sarcini mari; criptograful încearcă astfel să facă imposibilă fizic rezolvarea problemei de decriptare. De exemplu, un criptograf poate cripta un articol, iar cheia va fi o indicație a părților articolului care au fost utilizate în criptare. Criptanalistul va trebui să încerce toate combinațiile aleatorii de părți ale articolului înainte de a avea noroc și de a determina cheia.

Criteriile teoretice ale lui Reiner Rüppel pentru proiectarea sistemelor în linie:

perioade lungi de secvențe de ieșire;
complexitate liniară mare;
difuziune - dispersia redundantei în substructuri, statistici de „păsărire” în tot textul;
fiecare bit al fluxului de chei trebuie să fie o transformare complexă a majorității biților cheii;
criteriul de neliniaritate pentru funcţiile logice.

Până acum, aceste criterii nu s-au dovedit a fi necesare sau suficiente pentru securitatea unui sistem de criptare în flux. De asemenea, este de remarcat faptul că, dacă criptoanalistul are timp și putere de calcul nelimitate, atunci singurul cifr de flux realizabil care este sigur împotriva unui astfel de adversar este pad-ul unic.

Criptanaliză. Atacurile asupra cifrurilor fluxului

Toate metodele de criptoanaliza a cifrurilor de flux sunt de obicei împărțite în putere (atac „forță brută”), statistice și analitice.

Atacurile de putere

Această clasă include atacuri care realizează o enumerare completă a tuturor opțiunilor posibile. Complexitatea unei căutări exhaustive depinde de numărul tuturor soluțiilor posibile la problemă (în special, dimensiunea spațiului cheie sau spațiul text simplu). Această clasă de atacuri este aplicabilă tuturor tipurilor de sisteme de criptare a fluxurilor. Atunci când dezvoltă sisteme de criptare, dezvoltatorii se străduiesc să facă acest tip de atac cel mai eficient în comparație cu alte metode existente de hacking.

Atacurile statistice

Atacurile statistice se împart în două subclase:

metoda de criptoanaliza a proprietatilor statistice ale intervalului de criptare : care vizeaza studierea secvenței de iesire a criptosistemului; criptoanalistul încearcă să seteze valoarea următorului bit din secvență cu o probabilitate mai mare decât cea de selecție aleatorie, folosind diverse teste statistice.
Metoda de criptoanaliza a complexității secvenței : Un criptoanalist încearcă să găsească o modalitate de a genera o secvență similară cu gama, dar într-un mod mai simplu implementabil.

Ambele metode folosesc principiul complexității liniare.

Atacurile analitice

Acest tip de atac este considerat pe ipoteza că criptoanalistul cunoaște descrierea generatorului, textul public și textul privat corespunzător. Sarcina criptoanalistului este de a determina cheia folosită (umplerea inițială a registrelor). Tipuri de atacuri analitice aplicate cifrurilor de flux sincron:

corelație
compromis „memorie-timp”
inversiune
"sugereaza si determina"
pentru încărcarea cheii și reinițializarea
Atacul XSL

Atacuri de corelare

Sunt cele mai frecvente atacuri pentru spargerea cifrurilor de flux.

Se știe că munca de deschidere a criptosistemului poate fi redusă semnificativ dacă funcția neliniară transmite informații despre componentele interne ale generatorului către ieșire. Prin urmare, pentru a restabili umplerea inițială a registrelor, atacurile de corelare examinează corelația secvenței de ieșire a sistemului de cifrare cu secvența de ieșire a registrelor.

Există următoarele subclase de atacuri de corelare:

Atacurile de corelație de bază
Atacuri bazate pe verificări de paritate cu greutate redusă
Atacuri bazate pe utilizarea codurilor convoluționale
Atacuri folosind tehnica codului turbo
Atacuri bazate pe recuperarea polinoamelor liniare
Atacurile rapide de corelare.

Atacurile de corelație de bază

Să luăm în considerare exemplul atacului de corelație de bază al lui Siegenthaler ("split and open"), care se bazează pe conceptul de distanță Hamming între două secvențe binare de aceeași lungime. Aplicabil la combinarea generatoarelor.

Pentru a dezvălui influența j-al-lea registru de deplasare liniară (cu secvența de ieșire {x (j) } asupra cifrului gamma {g} , o parte a generatorului este modelată ca un canal simetric binar (BSC). Algoritmul de atac constă din două etape (uneori numite faze ):

calcularea probabilității de corelare pe baza funcției de combinare și a celei de-a doua etape. $p_{j}=P(g={x^{(j)))}$ $f$
enumerarea completărilor iniţiale ale registrului. În această etapă, prezența unei corelații a unui fragment gamma dat cu fragmentul corespunzător din este determinată prin calcularea funcției de corelație încrucișată și comparând această valoare cu un anumit număr . $g$ $x_{d}^{(j))$ $C_{x^{j},{g}}(d)={\frac {1}{n}}\cdot \sum _{i=1}^{n}(-1)^{g_ {i}}\cdot (-1)^{x_{i+d}^{(j)}}$ $T$

Dacă comparația are succes, faza se numește adevărată și are loc trecerea la următorul registru . În caz contrar, faza este numită invalidă și mergeți la . Valorile de ieșire ale acestui algoritm sunt stările care contribuie cu informații la gama. $j+1$ $d=d+1,d=1,2,\dots ,2^{L_{j)}$ ${x_{0}^{j)}$

Acum puțin despre selectarea valorii pragului și a numărului de biți gamma necesari pentru o criptoanaliză de succes : $T$ $n$ $P_{f}=P(C_{x^{j}, {g}}(d)\geq T|WrongPhase)$ $P_{m}=P(C_{x^{j}, {g}}(d)<T|RightPhase)$

De exemplu, am ales , unde este lungimea registrului. Și apoi din aceste condiții găsim și . $P_{m}=0,01,P_{f}=2^{-L)$ $L$ $T$ $n$

Atacuri bazate pe verificări de paritate cu greutate redusă

Un exemplu al acestei subclase de atacuri este atacul de corelare rapidă al lui Mayer și Staffelbach. Este aplicabil atât generatoarelor de filtre, cât și generatoarelor combinate și este baza pentru toate celelalte atacuri de corelație rapidă de acest tip. Ideea atacului se bazează pe utilizarea ecuațiilor de verificare a parității pentru un polinom de feedback al registrului liniar .

Atacurile rapide de corelare

Atacurile cu corelație rapidă sunt înțelese ca atacuri, a căror complexitate computațională este mult mai mică decât complexitatea computațională a atacurilor de putere.
Acest tip de atac reduce problema decodării într-un canal binar simetric la o problemă de criptoanaliza și este modelat ca decodificarea unui cod liniar aleatoriu. Similar atacurilor de corelație de bază, această subclasă folosește noțiunea de distanță Hamming . $(N,l)$

Compromisul timp-memorie

Scopul acestui atac este de a restabili starea inițială a registrului de deplasare (găsirea cheii) folosind o schemă de dispozitiv cunoscută și un fragment din secvența de criptare. Complexitatea atacului depinde de dimensiunea cifrului și de lungimea gamma interceptată.

Constă din două etape:

construirea unui dicționar mare în care sunt înregistrate toate perechile stare-ieșire posibile;
ghicirea umplerii inițiale a registrului de deplasare, generarea ieșirii, analizarea secvenței de ieșire capturată și căutarea unei potriviri cu ieșirea generată. Dacă există o potrivire, atunci această umplere estimată cu o probabilitate mare este cea inițială.

Exemple ale acestei clase de atacuri sunt atacul Steve Babbage și atacul Biryukov-Shamir.

„Asumați și determinați”

Atacul se bazează pe presupunerea că criptoanalistul cunoaște gama, polinomul de feedback, numărul de deplasări de registru între ieșirile circuitului și funcția de filtrare. Constă din trei etape:

presupunerea despre completarea unor celule din registru;
determinarea completării integrale a registrului pe baza presupunerii cunoștințelor criptoanalistului;
generarea secvenței de ieșire; dacă coincide cu gamma, atunci ipoteza din prima etapă a fost corectă; dacă nu se potrivește, atunci reveniți la pasul 1.

Complexitatea algoritmului depinde de dispozitivul generatorului și de numărul de ipoteze.

Note

↑ Sursa . Data accesului: 16 ianuarie 2016. Arhivat din original pe 15 februarie 2017. (nedefinit)
↑ Sursa . Consultat la 16 ianuarie 2016. Arhivat din original la 14 februarie 2017. (nedefinit)
↑ Schneier B. Capitolul 16. Generatoare de secvențe pseudo-aleatoare și cifruri de flux // Criptografie aplicată. Protocoale, algoritmi, cod sursă în limbaj C = Criptografie aplicată. Protocoale, algoritmi și cod sursă în C. - M. : Triumph, 2002. - 816 p. - 3000 de exemplare. - ISBN 5-89392-055-4 .

Literatură

Ryabko B. Ya., Fionov AN Metode criptografice de protecție a informațiilor. - Moscova. - Editura Goryach.Line-Telecom, 2005. - ISBN 5-93517-265-8 .

Bruce Schneier . Criptografie aplicată, ediția a doua: protocoale, algoritmi și cod sursă în C (pânză). - John Wiley & Sons, Inc. - Editura Literatură străină, 1996. - ISBN 0471128457 .

A. Menezes, P. van Oorschot, S. Vanstone. Manual de Criptografie Aplicată. — CRC Press, Inc. — 1997.

Prelegeri de E. M. Gabidulin , Institutul de Fizică și Tehnologie din Moscova , 2009

Link -uri

Matt JB Robshaw. Raport tehnic Stream Ciphers TR-701 (engleză) , versiunea 2.0, RSA Laboratories, 1995.
Cifruri în flux. Rezultatele criptologiei deschise străine. . Cea mai completă compilare și traducere a cercetării străine moderne (până în 1997) în domeniul creării și criptoanalizei cifrurilor de flux.
BC Anashin , A.Yu. Bogdanov, I.S. Kizhvetov. eSTREAM: cifruri de flux rapide și puternice .
JA Reeds și NJA Sloane. Sinteză Shift-Registru .
A.V. Yakovlev, A.A. Bezbogov, V.V. Rodin, V.N. Shamkin. Protecția criptografică a informațiilor .
Metode și mijloace de protejare a informațiilor computerizate . Tutorial.
Schema generală a unui sistem de criptare în flux probabilistic
eSTREAM: Copilul monstrului din Loch Ness
A. A. Menyashev, V. A. Monarev, B. Ya. Ryabko, A. N. Fionov. Atacul statistic .
S. Doroșenko, A. Fionov, A. Lubkin, V. Monarev, B. Ryabko, Yu. Eu Shokin. Atacuri statistice experimentale asupra cifrurilor bloc și flux (link indisponibil) .
Yu. V. Stasev, A. V. Potii, Yu. A. Izbenko. Un studiu al metodelor de criptoanaliza pentru stream Ciphers .

Criptosisteme simetrice
Cifruri în flux	A3 A5 A8 Decim F-FCSR Cereale HC-256 KCipher-2 MICKEY MUGI ŞTIUCĂ Phelix RC4 Iepure SIGILIU ZĂPADĂ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Rețeaua Feistel	GOST 28147-89 (Magma) blowfish Camelia CAST-128 CAST-256 CIFERUNICORN-A CIFERUNICORN-E CLEFIA Cobra AFACERE DES DESX DFC E2 ENRUPT FEAL HPC IDEE KASUMI Khafre Khufu LOKI97 MacGuffin MARTE PLASĂ CEȚA1 NewDES NDS RC5 RC6 SEMINTA Simon Sinople lista SM4 Speck CEAI XTEA XXTEA Raiden RTEA Triplu DES Doi pești
Rețeaua SP	Lăcustă 3 căi ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Centura CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer prezent Curcubeu MAI SIGUR RECHIN PĂTRAT Şarpe trei pești
Alte	BROASCĂ NUSH REDOC SC2000 SHACAL CS-Cipher