Atacul cu text simplu ales

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 4 decembrie 2017; verificările necesită 7 modificări .

Atacul cu text simplu ( CPA ) este una dintre principalele metode de atac criptoanalitic . Criptanalistul are un anumit număr de texte clare și texte cifrate corespunzătoare , în plus, are capacitatea de a cripta mai multe texte clare preselectate [1] .

Descriere

Un criptoanalist , conform principiului Kerckhoffs , are toate informațiile despre sistemul de criptare utilizat, cu excepția unui anumit set de parametri numit cheie . Sarcina criptoanalistului este să găsească cheia sau să creeze un algoritm care să permită decriptarea oricărui mesaj criptat cu această cheie.

Dat: $P_{1},C_{1}=E_{k}(P_{1}),\,P_{2},C_{2}=E_{k}(P_{2}),\,. ..\,P_{i},C_{i}=E_{k}(P_{i}),$

unde textul simplu ales de criptoanalist, textul cifrat, funcția de criptare, cheia. $P-$ $C-$ $E-$ $k-$

Obține: fie , fie algoritm cum să ajungi de la [1] $k$ $P_{i+1}$ $C_{i+1}=E_{k}(P_{i+1}).$

Capacitatea de a efectua un atac în text clar este destul de comună. De exemplu, un atacator ar putea mitui pe cineva pentru a cripta un mesaj selectat. Este posibilă și următoarea situație: atacatorul trimite un mesaj ambasadorului unei anumite țări, iar acesta îl trimite în patria sa în formă criptată [2] .

Atacul în text simplu se referă la atacuri active asupra sistemelor cripto. Astfel de atacuri încalcă integritatea și confidențialitatea informațiilor transmise [3] .

Figura 1 prezintă o diagramă a unui atac bazat pe textul clar ales. Atacatorul (A) primește textul cifrat de la utilizator (C). Sarcina atacatorului este de a „ghici” textul simplu . Deoarece atacatorul are acces la blocul de criptare , el are capacitatea de a-și cripta mesajele și de a analiza textele cifrate primite. . Drept urmare, atacatorul preia mesajul și îl transmite utilizatorului. $C=E(P,K)$ $P^{'}=P$ $E$ $P_{i)$ $C_{i}=E(P_{i},K)$ ${\displaystyle P^{'))$

Tipuri de atacuri

Există două tipuri de atacuri bazate pe textul clar ales:

autonom ( eng. batch chosen-plaintext attack ) - un criptoanalist pregătește un set de texte clare în avans, înainte de a primi texte cifrate.
atac operațional sau adaptiv ales- text clar ( CPA2 ) — criptoanalistul selectează următoarele texte clare pe baza textelor cifrate deja primite. Deoarece selecția blocurilor ulterioare care urmează să fie trimise pentru criptare ține cont de rezultatele anterioare, are loc feedback, care oferă unui atac bazat pe text simplu ales adaptiv un avantaj față de alte tipuri de atacuri. Implementarea acestui tip de atac este posibilă, de exemplu, dacă criptoanalistul are acces la dispozitivul de criptare pentru un timp suficient de lung pentru a analiza rezultatele [4] .

Comparație cu alte tipuri de atacuri

Potrivit lui Bruce Schneier , există 4 căi principale de atac criptoanalitic [1] :

Atacul cu text cifrat
Atac cunoscut în text simplu
Atacul cu text simplu ales
Atac adaptiv de text simplu

În cazul unui atac bazat pe text cifrat, criptoanalistul are acces doar la textul cifrat. Acesta este cel mai dificil tip de atac din cauza cantității reduse de informații disponibile.

Într-un atac de text simplu cunoscut, criptoanalistul cunoaște atât textul simplu, cât și textul cifrat. Acest tip de atac este mai eficient decât un atac bazat pe text cifrat datorită cantității mai mari de informații cunoscute despre criptosistem.

Un atac cu text clar ales este un tip de atac mai puternic decât un atac cu text clar cunoscut. Abilitatea de a preselecta texte clare oferă mai multe opțiuni pentru extragerea cheii de sistem. De asemenea, este adevărat că, dacă un criptosistem este vulnerabil la un atac de text simplu cunoscut, atunci este vulnerabil și la un atac de text simplu ales [5] .

În istorie

Atacul cu text simplu a fost folosit în timpul celui de-al Doilea Război Mondial .

În 1942, criptoanaliştii US Navy au interceptat un ordin criptat de la comandamentul japonez. După ce au descifrat o parte a mesajului, criptoanalistii americani au aflat despre atacul iminent asupra misteriosului „AF”, dar nu au reușit să afle locul atacului. Presupunând că Insula Midway era ținta cea mai probabilă pentru japonezi , americanii au încercat un truc. Ei au întocmit un raport conform căruia insula nu avea apă dulce și a trimis-o printr-un canal neprotejat. Câteva zile mai târziu, ofițerii americani de informații au interceptat un text cifrat japonez, care a raportat că era puțină apă dulce pe AF. Astfel, comandamentul american știa dinainte despre atacul viitor asupra atolului Midway [6] .

Criptoanaliștii britanici de la Bletchley Park au folosit cu succes un atac în text simplu pentru a decripta corespondența germană. Britanicii au provocat inamicul să folosească anumite cuvinte și nume în textele mesajelor. De exemplu, dacă germanii au curățat recent de mine o secțiune din apele de coastă, serviciile britanice de informații ar putea anunța că zona a fost din nou minată. Acest lucru a provocat un flux de mesaje criptate de la comanda germană, inclusiv cuvântul „mine” și numele teritoriului. Astfel, britanicii au reușit să culeagă text simplu și să analizeze texte cifrate destul de eficient pentru a sparge cifrurile germane. Acest atac poate fi calificat ca un atac cu text simplu ales adaptiv , deoarece criptoanalistii britanici ar putea alege următorul text simplu care urmează să fie criptat pe baza rezultatelor deja obținute [7] .

Exemple de atacuri

Criptosisteme cu cheie privată

Atacul asupra cifrului afin

Luați în considerare un exemplu simplu de atac asupra unui cifru afín folosind caractere latine de la A la Z.

A	B	C	D	E	F	G	H	eu	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
0	unu	2	3	patru	5	6	7	opt	9	zece	unsprezece	12	13	paisprezece	cincisprezece	16	17	optsprezece	19	douăzeci	21	22	23	24	25

Funcția de criptare: $y=mx+n\ mod\ 26.$

Criptoanalistul efectuează un atac pe baza textului clar ales. Textul clar ales este „HAHAHA”, textul cifrat corespunzător este „NONONO”. Scopul criptoanalistului este de a găsi forma explicită a funcției de criptare, adică de a calcula coeficienții și . $m$ $n$

Folosind perechea rezultată text clar-text cifrat, vom compune un sistem de ecuații:

${\begin{cases}m\cdot 7+n\equiv 13\mod\26\\m\cdot 0+n\equiv 14\mod\26\end{cases))$

Rezolvând sistemul, găsim: $n=14,\m=11.$

Funcție de criptare: [8] $y=11x+14\ mod\ 26.$

Criptanaliza diferențială

Atacul cu text clar ales este folosit într-o metodă de criptoanaliza diferenţială propusă de criptoanaliştii israelieni Eli Biham şi Adi Shamir în 1990 pentru a sparge criptosistemul DES . Metoda se bazează pe studiul textelor cifrate, ale căror texte clare prezintă anumite diferențe. Analizând evoluția diferențelor de text cifrat în timpul rundelor DES, se determină o listă de chei posibile și i se atribuie o probabilitate fiecărei chei posibile. În procesul de analiză a următoarelor perechi de texte cifrate, una dintre chei va deveni cea mai probabilă [9] . Ulterior, metoda criptoanalizei diferențiale a fost extinsă la astfel de criptosisteme precum FEAL , Khafre , Lucifer , LOKI și altele [10] [11] .

Fie , texte clare potrivite, , texte cifrate corespunzătoare. Diferența dintre textele clare și textele cifrate este determinată de operația XOR : Pentru a descrie posibilele modificări ale valorii în timpul parcurgerii etapelor DES, se introduce conceptul de caracteristică rotundă , alcătuită din diferențe de text simplu , text cifrat și un set de diferențe rotunde. (diferențe de texte cifrate după fiecare rundă intermediară) . Fiecărei caracteristici i se atribuie probabilitatea ca o pereche aleatorie de texte clare cu o diferență să producă diferențe rotunde și diferențe de text cifrat corespunzătoare caracteristicii după trecerea prin runda de criptare corespunzătoare. O pereche de texte clare a căror trecere printr-o rundă DES este descrisă exact de caracteristică se numește „pereche corectă” ; în caz contrar, se numește „pereche incorectă”. [9] $P$ $P^{'}-$ $C$ $C^{'}-$ $\Delta P=P\oplus P^{'},\Delta C=C\oplus C^{'}.$ $\Delta C$ $\Delta P$ $\Delta C$ $C_{\lambda }=(\lambda _{1},\lambda _{2}...\lambda _{n})$ $\Delta P$

Pentru a determina cheia, se efectuează un atac pe baza textului clar ales. În etapa de colectare a datelor, criptoanalistul trimite spre criptare un număr mare de perechi de texte clare cu anumite diferențe corespunzătoare caracteristicii cu probabilitate (adică între toate perechile de texte clare există perechi corecte). Apoi, în etapa de analiză a datelor , se determină un set de chei rotunde posibile, pentru fiecare cheie posibilă se calculează diferențele textelor cifrate corespunzătoare. În timpul ultimei runde de criptare, are loc o enumerare completă a cheilor posibile. Pentru cheile rotunde incorecte, probabilitatea unei diferențe de texte cifrate corespunzătoare caracteristicii va fi foarte mică, pentru o cheie rotundă corectă, probabilitatea va fi de ordinul mărimii sau mai mare. În acest fel puteți determina cheia de sistem corectă [9] [12] . $p$ $p$ $p$

Trebuie remarcat faptul că metoda criptoanalizei diferențiale este destul de nepractică din cauza cerințelor ridicate de timp și volum de date. De exemplu, cracarea unui DES cu 16 runde necesită texte clare și operații potrivite [9] . $2^{47}$ $2^{55}$

Criptanaliza liniară

În 1993, criptoanalistul japonez Mitsuru Matsui a propus o metodă de criptoanaliza liniară pentru spargerea cifrurilor bloc, cum ar fi DES. Metoda se bazează pe construirea de relații liniare între text simplu, text cifrat și cheie : $P_{i_{1}}\oplus P_{i_{2}}\oplus \dots \oplus P_{i_{a}}\oplus C_{j_{1}}\oplus C_{j_{2}} \oplus \dots \oplus C_{j_{b}}=K_{k_{1}}\oplus K_{k_{2}}\oplus \dots \oplus K_{k_{c}}$

unde sunt cei n -alei biți ai textului, textului cifrat și, respectiv, cheii. Astfel de relații se numesc aproximări liniare. $P_{n},C_{n},K_{n}$

Esența metodei este de a calcula probabilitatea de apariție a aproximărilor liniare. Dacă probabilitatea este diferită de , atunci este posibil să extrageți informații despre cheie folosind perechi text simplu-text cifrat. Inițial, pentru fiecare rundă individuală, se găsește o aproximare liniară cu cea mai mare probabilitate de părtinire. Apoi, aproximațiile rotunde sunt combinate într-o aproximare liniară generală a criptosistemului și, cu ajutorul perechilor text clar-text cifrat, se face o presupunere despre valorile biților cheie [13] . $p$ $1/2$

Inițial, metoda de criptoanaliza liniară a folosit un atac de text simplu cunoscut. De exemplu, a fost nevoie de texte clare cunoscute și 50 de zile pentru a sparge un DES cu 16 runde [13] . În 2000, Lars Knudsen a propus o variantă de criptoanalize liniare bazată pe texte clare alese - a fost nevoie de texte clare alese pentru a deschide 12 biți ai cheii [14] . $2^{43}$ $2^{42}$

Criptosisteme cu cheie publică

Atacul de text clar ales poate fi folosit pentru a sparge criptosisteme asimetrice. În astfel de sisteme, cheia publică este disponibilă oricărui utilizator, ceea ce oferă criptoanalistului control complet asupra algoritmului de criptare. Astfel, este întotdeauna posibil să se organizeze un atac împotriva criptosistemelor cu cheie publică pe baza textului clar ales [15] . De exemplu, dacă un atacator a interceptat un text cifrat , pentru a-l decripta, este suficient să ridicați un alt mesaj și să-l criptați folosind cheia publică . Dacă , se mai face o încercare [16] . $C=E_{k}(P)$ ${\displaystyle P^{'))$ $C^{'}=E_{k}(P^{'})$ $P\neq P^{'}$

Criptare probabilistică

De obicei, criptosistemele asimetrice sunt concepute pentru a rezista atacurilor folosind texte clare alese [15] . De exemplu, apărarea criptosistemului RSA împotriva atacurilor bazate pe text simplu ales se bazează pe dificultatea de a calcula rădăcina textului cifrat printr-un întreg compus modulo [17] . O altă modalitate de a elimina scurgerile de informații din criptosistemele cu chei publice este criptarea probabilistică propusă de Shafi Goldwasser și Silvio Micali . Ideea principală a criptării probabilistice este de a potrivi mai multe texte cifrate selectate aleatoriu cu același text simplu . Astfel, dacă un criptoanalist încearcă să ghicească textul simplu P pentru a decripta , el va obține un text cifrat complet diferit și nu va putea verifica corectitudinea presupunerii sale [18] . $e$ $n$ $P$ $C_{1},C_{2},C_{3},\ldots$ $C=E_{k}(P)$ $C^{'}\neq C$

Atacul asupra criptosistemului RSA

În ciuda securității criptosistemului RSA împotriva atacurilor de text alese, există o serie de vulnerabilități care permit unui criptoanalist să decripteze textul cifrat. Luați în considerare următorul algoritm pentru atacarea unui sistem de semnătură electronică bazat pe RSA, propus de George David în 1982. Atacul se face presupunând că criptoanalistul a interceptat textul cifrat . Scopul criptoanalistului este de a obține un mesaj deschis . Pentru a efectua un atac, un criptoanalist trebuie să fie capabil să semneze orice mesaje pe care le alege [19] [20] . $C=M^{e}\ mod\n$ $M$

În prima etapă a atacului, textul cifrat este descompus în factori (nu neapărat simpli): . Rezultă că mesajul este reprezentabil și ca produs al factorilor , iar egalitățile sunt valabile: , și . $C$ $C=C_{1}C_{2}...C_{t)$ $M$ $t$ $M=M_{1}M_{2}...M_{t)$ $C=C_{1}C_{2}...C_{t}=(M_{1}M_{2}...M_{t})^{e}\ mod\n=M_{1 }^{e}M_{2}^{e}...M_{t}^{e}\ mod\ n$ $M_{i}=C_{i}^{d}\ mod\n$
Criptanalistul selectează un mesaj deschis și îl trimite spre semnare. De asemenea, cere să semneze mesaje . Semnătura se face astfel: , în timp ce . $X$ $XC_{1)$ $XC_{2)$ $...XC_{t}$ $S=X^{d}\mod\n$ $S_{i}=(XC)_{i}^{d}\ mod\n,i=1...t$
Se calculează elementul invers . $S^{-1}=X^{-d}\ mod\n$
Înmulțind expresia rezultată cu se poate obține : . $S_{i)$ $M_{i}$ $S_{i}S^{-1}=(X)^{-d}(XC_{i})^{d}\ mod\n=C_{i}^{d}\ mod\n= M_{i}$
Ca urmare, mesajul original este restaurat: $M=M_{1}M_{2}...M_{t}\ mod\n$

Această metodă nu vă permite să deschideți criptosistemul în sensul tradițional, adică să obțineți o cheie privată, dar criptoanalistul este capabil să decripteze un anumit mesaj. Prin urmare, acest atac este mai slab decât atacul de tip matched-plaintext pentru criptosistemele simetrice, ceea ce vă permite să obțineți toate informațiile despre criptosistem dacă aveți succes [20] .

Note

↑ 1 2 3 Schneier, 2003 , p. douăzeci.
↑ Schneier, 2003 , p. 21.
↑ Gabidulin , p. 25-28.
↑ Schneier, Ferguson, 2002 , p. 48.
↑ Schneier, Ferguson, 2002 , p. 47-49.
↑ Kahn, 2000 , p. 106-109.
↑ Hinsley, 2001 .
↑ Stinson, 2006 , p. 27-29.
↑ 1 2 3 4 Biham, Shamir (DES), 1990 .
↑ Biham, Shamir (FEAL), 1991 .
↑ Biham, Shamir (LOKI), 1991 .
↑ Schneier, 2003 , p. 212-216.
↑ 12 Matsui , 1993 .
↑ Knudsen, 2000 .
↑ 1 2 Schneier, 2003 , p. 342.
↑ Schneier, 2003 , p. 404.
↑ Mao, 2005 , p. 308.
↑ Schneier, 2003 , p. 404-406.
↑ Davida, 1982 .
↑ 12 Denning , 1984 .

Literatură

B. Schneier. Criptografia aplicată. - Triumf, 2003. - 816 p. - ISBN 5-89392-055-4 .
B. Schneier, N. Ferguson. Criptografie practică. - Williams, 2002. - 424 p. — ISBN 5-8459-0733-0 .
E. Gabidulin, A. Kshevetsky, A. Kolybelnikov, S. Vladimirov. Protejarea datelor. Tutorial.
D. Kahn. Spărgătoare de coduri . - Tsentrpoligraf, 2000. - 124 p. — ISBN 5-227-00678-4 .
FH Hinsley, A. Stripp. Codebreakers: The Inside Story of Bletchley Park. - Oxford University Press, 2001. - 360 p. — ISBN 978-0192801326 .
D. Stinson. criptografie. Threory și Practică. - Chapman & Hall / CRC, 2006. - 611 p. - ISBN 978-1-58488-508-5 .
W. Mao. Criptografia modernă. Teorie și practică.- Williams, 2005. - 768 p. — ISBN 5-8459-0847-7 .
E. Biham, A. Shamir. Criptoanaliza diferențială a criptosistemelor asemănătoare DES . - Journal of Criptology, 1990. - V. 4 .
E. Biham, A. Shamir. Criptoanaliza diferențială a Feal și N-Hash . - Progrese în Criptologie - EUROCRYPT '91, 1991. - V. 547 .
E. Biham, A. Shamir. Criptanaliză diferențială a lui Snefru, Khafre, REDOC-II, LOKI și Lucifer . - Progrese în criptologie - CRYPTO' 91, 1991.
M. Matsui. Metoda de criptoanaliza liniară pentru DES Cipher . - Progrese în Criptologie - EUROCRYPT' 93, 1993.
L. Knudsen, J. Mathiassen. Un atac liniar în text simplu asupra DES . - Atelier internațional de criptare rapidă a software-ului, 2000.
D.E. Denning. Semnături digitale cu RSA și alte criptosisteme cu cheie publică . - Comunicările ACM, 1984. - T. 27 .
G. Davida. Criptanaliza aleasă a semnăturii criptosistemului cu chei publice RSA (MIT). — Dept. de Inginerie Electrică și Informatică, Univ. din Wisconsin, 1982.