Atacul ghicit

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 21 martie 2015; verificările necesită 24 de modificări .

Atacul cu cheie aleasă este una dintre metodele de atac criptoanalitic , care monitorizează funcționarea unui algoritm de criptare care utilizează mai multe chei secrete . Un criptoanalist are inițial doar informații despre o anumită relație matematică care leagă cheile între ele.

Descriere

Conform principiului Kerckhoffs , criptoanalistul are toate informațiile necesare despre sistemul de criptare utilizat, cu excepția unui anumit set de parametri secreti numit cheie. Un criptoanalist știe doar relația dintre o pereche de chei. Folosește textul cifrat și raportul dat pentru a ghici ambele chei. Sunt cunoscute două tipuri de atacuri ale cheii alese: atacul cheie aleasă și atacul de text simplu cunoscut, în care criptoanalistul specifică doar relația dintre perechea de chei și atacul cheie aleasă și atacul de text simplu, în care criptoanalistul stabilește atât relația dintre perechile de chei. perechea de chei și și textul simplu, care urmează să fie criptat. [unu]

Un atac bazat pe o cheie selectată este efectuat în același mod pe toate criptosistemele, inclusiv așa-numita „cutie neagră”, în care toate proprietățile sunt necunoscute. Această „cutie neagră” folosește funcția de criptare , care este aleasă în același mod pentru permutările aleatorii ale mesajelor. Biții cheii sunt aleși la întâmplare, astfel încât cunoașterea textului cifrat nu ne poate spune nimic despre textul cifrat pentru cheie . $E_{k)$ $k$ $E_{k}(m)$ $E_{h}(m')$ $h\neq k$

Algoritmul de atac bazat pe cheia selectată pe „caseta neagră”, în plus față de operațiunile standard, în orice moment al calculului poate necesita:

criptați sau decriptați folosind cheia secretă și mesajul potrivit și vectorul de inversare , $E_{k\oplus l}(m)$ $E_{k\oplus l}^{-1}(m)$ $k$ $m$ $l$
utilizați „caseta neagră” pentru calcul sau cu ajutorul unei taste (care nu este o funcție ) prin preluarea unui mesaj . $E_{h}(m)$ $E_{h}^{-1}(m)$ $h$ $k$ $m$

De asemenea, algoritmul poate avea acces la un generator de biți aleatori. La sfârșitul calculului, se iese cheia estimată . [2] $k$

Astfel, dacă utilizatorul folosește o cheie secretă și un criptosistem public ( public key cryptosystem ), atunci în orice moment, criptoanalistul poate alege un mesaj și un vector de inversare și poate efectua criptarea sau decriptarea . Aplicația principală a unui atac cu cheie ghicit este verificarea sistemelor, dar în anumite circumstanțe acest atac poate fi aplicat în practică. Dacă se folosește un cifr de flux pentru a transfera o cheie de sesiune de la utilizator la utilizator , iar criptoanalistul câștigă controlul asupra liniei de transmisie, atunci el poate schimba orice biți din cheie după bunul său plac și va primi cheia schimbată în loc de . Apoi, când începe transmiterea cu cheia greșită, va primi un mesaj deranjat și va începe procedura de recuperare. Între timp, criptoanalistul va primi textul criptat cu cheia. (O bună protecție criptografică poate evita astfel de atacuri prin utilizarea unor noi chei de sesiune independente sau prin adăugarea de biți de detectare a erorilor neliniare la cheia de sesiune ori de câte ori este nevoie de o procedură de recuperare. Cu toate acestea, istoricul arată că o bună protecție criptografică nu urmează întotdeauna acest lucru și este este de dorit să existe un sistem care să nu se prăbușească.sub un astfel de atac) [3] . $k$ $E$ $m$ $l$ $E_{{k\oplus l}}$ $E_{{k\oplus l}}^{{-1}}$ $k$ $A$ $B$ $B$ $k\oplus l$ $k$ $B$ $A$ $k\oplus l$

Tipul principal de atac bazat pe o cheie aleasă

În această parte, vom lua în considerare un atac care nu depinde de o slăbiciune specifică a funcției de criptare. Este un atac de tip om-in-the-middle ( MITM ). Acest tip de atac vă permite să reduceți timpul căutării avansate, în funcție de numărul de inversări ale cheilor permise [4] .

Teorema. Fie un cifru bloc cu o cheie de n biți. Să presupunem că criptoanalistul poate efectua inversiuni și are cuvinte de memorie. Apoi va putea sparge cifrul în pași suplimentari [4] . $E$ $2^{p}$ $2^{p}$ $E$ $2^{{np}}$

Dovada:

Analistul înlocuiește ultimii biți din cheie în toate modurile posibile. De exemplu, criptează valorile $p$ $2^{p}$

E_{k}(m),E_{{k\oplus (00\dots 01)}}(m),\dots ,E_{{k\oplus j}}(m),\ldots ,E_{{k\ oplus (00\dots 011\dots 1)}}(m)

unde este cheia privată a utilizatorului și orice mesaj adecvat. Se creează un tabel hash din valorile [4] . $k$ $m$ $2^{p}$ $(E_{{k\oplus j}},j)$

Apoi efectuează criptarea prin schimbarea primilor biți ai cheii și resetarea ultimilor biți: $2^{{np}}$ $np$ $p$

E_{{(00\dots 0)}}(m),E_{{(00\dots 10\dots )}}(m),\dots ,E_{{(11\dots 10\ldots 0)}}( m)

După toate calculele, fiecare valoare este verificată cu tabelul hash [4] .

Dacă cheia originală este spartă prin , unde constă din ultimii biți, atunci intrarea se va potrivi cu rezultatul prin criptare în a doua etapă. Când se găsește o potrivire, aceasta va fi o cheie candidată. Mai multe alarme false sunt posibile dacă mai multe chei se potrivesc cu mesajul , dar, ca în cazul unui atac de text potrivit , unul sau două blocuri suplimentare de text clar cunoscut le vor exclude aproape sigur, cu un impact redus asupra timpului de rulare [4] . $k$ $(a,b)$ $b$ $p$ $(E_{{k\oplus b}},b)$ $a^{{al-lea}}$ $(a,b)$ $m$

Concluzie: Folosind un număr nelimitat de atacuri cu cheie aleasă, orice cifru bloc cu o cheie de n biți poate fi spart folosind nu mai mult decât calcule în memorie [4] . $O(2^{{n/2}})$

Dovada: hai sa alegem . $p=n/2$

Notă: Pentru un număr mare de exemple și o cantitate mare de memorie disponibilă, va fi mult mai eficient să schimbați cele două etape în demonstrarea teoremei. Calculați și stocați criptările în memorie. Pentru fiecare sarcină, efectuați inversări și verificați tabelul pentru conformitate. Astfel, iterațiile vor fi cheltuite pentru fiecare sarcină suplimentară [4] . $2^{{np}}$ $2^{p}$ $2^{p}$

Vulnerabilitatea codului de blocare la atac pe baza cheii alese

Vom demonstra capabilitățile acestui tip de atac asupra unui criptosistem, care s-a dovedit a fi extrem de rezistent împotriva unui atac de text potrivit [3] .

Să fie un cifr bloc secret cu o dimensiune a cheii de biți. Să definim un nou cifru bloc . $E$ $n$ $F$

F_{k}(m)=E_{k}(m)

dacă primul bit este 0

k

F_{k}(m)=E_{{k'}}(m)\oplus k

în alte cazuri, în care rezultatul inversării primului bit este, de exemplu, .

k'

k

k'=k\oplus(1,0,\ldots,0)

F

cifru bloc legitim:

F_{k}^{{-1}}(m)=E_{k}^{{-1}}(m)

dacă primul bit al cheii este 0

k

F_{k}^{{-1}}(m)=E_{{k'}}^{{-1}}(m\oplus k)

, in alte cazuri

Dacă cifrul principal are o protecție bună pe n-biți, atunci spargerea cifrului cu un atac de analiză a textului necesită o căutare avansată în spațiul de biți cheie. Cu alte cuvinte, dacă analistul nu deține informații despre cifrul , atunci poate obține informațiile necesare dacă criptează sau decriptează cu cheile sau [3] . $E$ $F$ $n-1$ $E$ $k$ $k'$

Deși cifrul este greu de spart cu un atac de text ales, este foarte ușor de spart cu un atac de cheie aleasă. Analistul are nevoie de două cifruri: și pentru un mesaj potrivit . Dacă primul bit este zero, atunci $F$ $F_{k}(m)$ $F_{{k'}}(m)$ $m$ $k$

F_{k}(m)\oplus F_{{k'}}(m)=E_{k}(m)\oplus (E_{{k''}}(m)\oplus k')=k'

In alte cazuri,

F_{k}(m)\oplus F_{{k'}}(m)=(E_{{k'}}(m)\oplus k)\oplus (E_{{k'}}(m)=k

[3] .

Astfel, analistul primește imediat toți biții cheii , cu excepția primului, și poate finaliza operația, deoarece cunoaște textul clar [4] . $k$

Exemple de atacuri

Atacul asupra LOKI89

În cifrul LOKI89, fiecare alegere a două subchei , una dintr-un ciclu par și una dintr-un ciclu impar, are o cheie corespunzătoare pe 64 de biți. Deoarece toți algoritmii pentru obținerea a două subchei de la cele două anterioare sunt aceiași, locația ciclurilor în care se află cele două subchei curente nu afectează rezultatul următoarelor subchei. Dacă reparăm două subchei și chei și definim a doua cheie selectând și , atunci valorile subcheilor ale cheii vor fi aceleași cu următoarele subchei ale cheii . În acest caz, . Această relație este păstrată pentru oricare două chei alese în acest fel: dacă informațiile dinaintea celui de-al doilea ciclu de criptare cu cheia sunt aceleași cu informațiile dinaintea primei criptări cu cheia , atunci informațiile și datele de intrare ale funcției sunt aceleași în ambele operaţii deplasate cu un ciclu. În acest caz, dacă textul simplu este criptat cu cheia , atunci textul cifrat înainte de al doilea ciclu va fi . Datele primite sunt aceleași cu cele găsite înainte de primul ciclu de criptare cu cheia , a cărei valoare va fi , și astfel în această pereche $K2$ $K3$ $K$ $K^{*}$ $K1^{*}=K2$ $K2^{*}=K3$ $Ki^{*}$ $K^{*}$ $K(i+1)$ $K$ $K^{*}=(K2,K3)=(K_{R},ROL12(K_{L}))$ $K$ $K^{*}$ $F$ $P$ $K$ ${\ displaystyle (P_{R}\oplus K_{R},P_{L}\oplus K_{L}\oplus F(P_{R}\oplus K_{R},K_{L}))}$ $K^{*}$ $P^{*}\oplus K^{*}=(P_{R}^{*}\oplus K_{L},P_{R}^{*}\oplus ROL12(K_{L}))$

P ∗ = ( P R , P L ⊕ K L ⊕ R O L 12 ( K L ) ⊕ F ( P R ⊕ K R , K L ) ) {\displaystyle P^{*}=(P_{R},P_{L}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{R}\oplus K_{R},K_ {L}))}

P^{*}=(P_{R},P_{L}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{R}\oplus K_{R},K_ {L}))

Puteți vedea că partea dreaptă a expresiei este aceeași cu partea stângă a expresiei , iar raportul celorlalte două părți depinde de cheie. Într-o astfel de pereche, există o relație similară între textele cifrate:

P

P^{{*}}

C ∗ = ( C R ⊕ K L ⊕ R O L 12 ( K L ) ⊕ F ( C L ⊕ K R , K L ) , C L ) . {\displaystyle C^{*}=(C_{R}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(C_{L}\oplus K_{R},K_{L}), C_{L}).}

C^{*}=(C_{R}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(C_{L}\oplus K_{R},K_{L}), C_{L}).

Graficele descriu relația dintre subcheile celor două chei și relația dintre valori în timpul procesului de criptare.

SISTEM

Un atac de text simplu cu potrivire cheie care se bazează pe aceste proprietăți selectează o valoare de 32 de biți , texte clare ale căror părți din dreapta sunt și ale căror jumătăți din stânga de 32 de biți sunt alese aleatoriu și texte clar ale căror părți din stânga sunt , și ale căror părțile din dreapta sunt alese la întâmplare. Două chei asociate necunoscute sunt folosite pentru a cripta datele text simplu de pe sistemul studiat: cheia este folosită pentru a cripta primele texte clare, iar cheia este folosită pentru a cripta textele clare rămase . Pentru fiecare pereche de texte clare și se garantează că , și cu mare probabilitate există două texte clare astfel încât . Pentru o astfel de pereche, datele rămân aceleași dacă ambele execuții sunt deplasate cu un ciclu. O astfel de pereche poate fi selectată cu ușurință, dacă există, prin verificarea egalității.Probabilitatea de a trece la întâmplare acest test este , deci doar câteva perechi îl vor putea trece. $P_{R}$ $2^{16}$ $P_{0},...,P_{65535}$ $P_{R}$ $2^{16}$ $P_{0}^{*},...,P_{65535}^{*}$ $P_{R}$ $K$ $2^{16}$ $K^{*}=(K_{R},ROL12(K_{L}))$ $2^{16}$ $P_{{i}}$ $P_{j}^{*}$ $P_{jL}^{*}=P_{iR}$ $P_{jR}^{*}=P_{iL}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{iR}\oplus K_{R},K_{L} )$ $C_{R}^{*}=C_{L}.$ $2^{-32}$

Perechile care au aceste proprietăți de text simplu și de text cifrat îndeplinesc cerințele cheie (1) și (2). Astfel, pentru această pereche este îndeplinită relația , în care valoarea este singura necunoscută . Dintre toate valorile posibile, doar câteva satisfac ecuația. Folosind tehnici de criptoanaliza și optimizare diferențială, găsirea unei valori se poate face în câteva operațiuni. Odată ce valoarea a fost găsită , este ușor de calculat folosind formulele (1) și (2) pentru a obține și . $F(P_{R}\oplus K_{R},K_{L})\oplus F(C_{L}\oplus K_{R},K_{L})=P_{R}^{*} \oplus P_{L}\oplus C_{L}^{*}\oplus C_{R}$ $K_{L}\oplus K_{R}$ $2^{32}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus ROL12(K_{L})$ $K$ $K^{*}$

Un atac similar ales-cheie-cunoscut-text simplu utilizează texte clare cunoscute criptate cu o cheie necunoscută și texte clare criptate cu o cheie asociată . O pereche cu aceste proprietăți poate fi ușor identificată prin 32 de biți comuni de text simplu și 32 de biți comuni de text cifrat. Această pereche poate fi folosită pentru a căuta chei în același mod ca într-o cheie aleasă și un atac de text clar ales. [unu] $2^{32}$ $P_{{i}}$ $K$ $2^{32}$ $P_{j}^{*}$ $K^{*}=(K_{R},ROL12(K_{L}))$

Comparație cu alte tipuri de atacuri

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

Î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. [unu]

Un atac de cheie potrivită este mai puternic decât un atac de text potrivit. Acesta sparge instantaneu un cifr bloc special conceput, care este sigur împotriva altor atacuri. Pentru orice cifru bloc, un atac de cheie aleasă poate accelera procesul de căutare avansată, în funcție de numărul de inversiuni de cheie permise. Pentru un atac de cheie ghicit nerestricționat, cantitatea de muncă poate fi redusă ca rădăcină pătrată. Aceste rezultate sunt cele mai bune posibile pentru un atac general care nu se bazează pe un anumit cifru bloc.

Note

↑ 1 2 3 Biham, 1993 .
↑ Winternitz & Hellman, 1987 .
↑ 1 2 3 4 Winternitz & Hellman, 1987 , p. 17
↑ 1 2 3 4 5 6 7 8 Winternitz & Hellman, 1987 , p. optsprezece
↑ Schneier, 2003 .

Literatură

Robert Winternitz, Martin Hellman . Atacurile cu cheie aleasă asupra unui cifr de bloc // Cryptologia : journal. - 1987. - Nr. 11:1 . - P. 16-20 . - doi : 10.1080/0161-118791861749 .
Eli Biham. Noi tipuri de atacuri criptoanalitice folosind chei înrudite // Helleseth T. (eds) Advances in Cryptology . — EUROCRYPT '93. EUROCRYPT 1993. Lecture Notes in Computer Science, vol 765. Springer, Berlin, Heidelberg, 1993. doi : 10.1007/3-540-48285-7_34 .
B. Schneier. Criptografia aplicată. - Triumf, 2003. - 816 p. - ISBN 5-89392-055-4 .