Atacul bumerangului

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

Un atac bumerang este un atac criptografic asupra unui cifr bloc bazat pe metode de criptoanaliza diferențială . Algoritmul de atac a fost publicat în 1999 de profesorul de la Universitatea Berkeley, David Wagner, care l-a folosit pentru a sparge codurile COCONUT98 , Khufu și CAST-256 [1] .

Această metodă a făcut posibilă efectuarea de atacuri cu succes asupra multor cifruri recunoscute anterior ca rezistente la criptoanaliza diferențială „clasică”.

Există modificări ale acestei metode de criptoanaliza: atac de bumerang îmbunătățit (atac de bumerang amplificat) și atac dreptunghiular (atac dreptunghiular).

Caracteristici generale

Atacul bumerang se bazează pe principiile criptoanalizei diferenţiale . Metoda bumerangului constă în folosirea unui cvartet de texte clare și a textelor cifrate corespunzătoare, mai degrabă decât a unei perechi, ca în criptoanaliza diferențială.

O altă diferență notabilă între metoda bumerangului și criptoanaliza diferențială clasică, în care modificările textului cifrat cauzate de modificările textului clar acoperă întregul cifru, este că modificările textului clar pot acoperi doar o parte a cifrului.

În unele cazuri, utilizarea acestei metode de atac poate reduce semnificativ cantitatea de date necesare (comparativ cu criptoanaliza diferențială). În plus, atacul este aplicabil algoritmilor cu o structură rotundă eterogenă.

Una dintre cele mai interesante caracteristici ale algoritmului de atac este că funcționează foarte bine cu cifrurile care au funcții rotunde asimetrice. Funcțiile rotunde asimetrice pot fi împărțite în două tipuri: runde de tip A, care au o difuzie mai bună înainte decât înapoi și runde de tip B, care au o difuzie mai bună înapoi. Se remarcă faptul că, dacă prima jumătate a cifrului constă din runde de tip B, iar a doua din runde de tip A, atunci un astfel de cifru va fi cel mai vulnerabil la un atac de bumerang.

Algoritm de atac

Să presupunem mai întâi că algoritmul de criptare poate fi împărțit în două părți consecutive, aproximativ egale ca complexitate și , și , unde este un text simplu. De exemplu, un algoritm DES cu 16 runde cu runde de structură similară poate fi împărțit în două părți a câte 8 runde $E$ $E_{0}$ $E_1$ $E(M)=E_{1}(E_{0}(M))$ $M$
Să alegem o pereche de texte deschise și cu diferență . Ca urmare a procesării acestor texte de către funcție, obținem diferența $P$ $P^{'}$ $\Delta =P\oplus P'$ $E_{0}$ $\Delta ^{*}=E_{0}(P)\oplus E_{0}(P^{'})$
Continuăm să criptăm textele simple și să funcționăm și obținem două texte cifrate și $P$ $P'$ $E_1$ $C=E_{1}(E_{0}(P))$ $C^{'}=E_{1}(E_{0}(P^{'}))$
Folosim și pentru a obține alte două texte cifrate și asociate cu diferența anterioară $C$ $C^{'}$ $D$ $D^{'}$ $\nabla =C\oplus D=C^{'}\oplus D'$
Mai departe, formarea cvartetului continuă în direcția opusă: funcțiile de „semi-decriptare” sunt aplicate la și și pentru a obține diferența $D$ $D^{'}$ $E_{{1}}^{{-1}}$ $E_{{0}}^{{-1}}$ $\nabla ^{*}=E_{{1}}^{{-1}}(D)\oplus E_{{0}}(P)=E_{{1}}^{{-1}}(D ^{'})\oplus E_{{0}}(P^{'})$
Decriptarea suplimentară a textelor cifrate și oferă două texte clare și $D$ $D^{'}$ $Q=E_{{0}}^{{-1}}(E_{{1}}^{{-1}}(D))$ $Q^{'}=E_{{0}}^{{-1}}(E_{{1}}^{{-1}}(D^{'}))$

Mai mult, în lucrarea sa [1] , Wagner demonstrează că diferența dintre textele clare astfel obținute și este egală cu diferența dintre textele clare originale și și este egală cu . $Q$ $Q^{'}$ $P$ $P^{'}$ $\Delta$

Analizând un set de cvartete de texte cu o anumită diferență, se poate selecta o anumită cheie (sau fragmentul acesteia), care este cheia dorită fie fără ambiguitate, fie cu cea mai mare probabilitate (în comparație cu alte chei).

Atacul de bumerang îmbunătățit [2]

Atacul cu bumerang îmbunătățit este un atac cu text clar , în timp ce atacul cu bumerang clasic este un atac cu text clar ales adaptiv .

Când comparăm acești doi algoritmi, celelalte lucruri fiind egale, atacul clasic de bumerang necesită mult mai puține date decât cel îmbunătățit. La prima vedere, o astfel de schimbare a algoritmului nu aduce beneficii. Cu toate acestea, există trei puncte care îl deosebesc de atacul clasic, ceea ce face ca în unele cazuri să merite folosirea unui atac îmbunătățit:

Într-un atac de text simplu, este posibil să ghiciți cheia la sfârșitul cifrului fără a fi nevoie să creșteți numărul de texte clare alese.
Este posibil să aplicați un atac bumerang îmbunătățit nu numai perechilor, ci și K-seturi de texte.
Se poate folosi un atac boost pentru a obține o pereche (sau K) de texte pentru o parte a cifrului și apoi se poate folosi alți algoritmi pentru rundele rămase ale cifrului. Astfel, se poate folosi criptoanaliza diferențială trunchiată , care definește doar o mică parte a blocului și nu poate fi utilizată cu un atac bumerang standard.

Algoritmi de criptare vulnerabili la atacurile bumerang

Descris în articolul original [1]

COCONUT98 crapă cu texte clare și texte cifrate alese adaptiv . $2^{16}$
Khufu cu 16 runde este spart cu texte clare și texte cifrate alese adaptiv. $2^{18}$
16 fisuri rotunde CAST-256 cu texte cunoscute. $2^{{49.3}}$

Descris în alte surse

KASUMI cu 6 runde este spart cu texte clare și texte cifrate alese adaptiv [3] . $2^{13}$
Fisuri MARS cu 11 runde cu texte cunoscute [2] . $2^{{65}}$
Șarpele crapă în 8 runde cu versuri celebre [2] . $2^{{114}}$
fisuri AES cu 5 runde cu texte cunoscute [4] . $2^{{39}}$
fisuri AES cu 6 runde cu texte cunoscute [4] . $2^{{71}}$

Aplicație la AES complet [5]

Principiile atacului bumerang și atacului bumerang îmbunătățit au fost aplicate pentru a efectua un atac cu cheie conectată asupra cifrurilor AES -192 și AES-256. Această metodă se bazează pe detectarea coliziunilor locale în cifrurile bloc și pe utilizarea comutatoarelor bumerang.

În mod implicit, cifrul este împărțit în runde, dar această diviziune nu este întotdeauna cea mai bună pentru un atac cu bumerang. S-a propus împărțirea rundelor în operații simple și folosirea paralelismului existent în aceste operații. De exemplu, unii octeți pot fi procesați independent. Într-un astfel de caz, un octet poate fi procesat mai întâi înainte de conversie de către algoritmul de criptare, după care trece la procesarea unui alt octet după conversie. Există întrerupătoare pe scară, întrerupătoare Feistel și întrerupătoare cu S-box.

Această metodă de atac este mai eficientă decât atacul cu forță brută . Dar, în același timp, se observă că metoda are în principal valoare teoretică pentru specialiști și nu va reprezenta o amenințare pentru implementările practice ale AES în viitorul apropiat, din cauza cerințelor ridicate pentru timpul de procesare și puterea de calcul. Pe de altă parte, această tehnică poate fi aplicată destul de eficient atacurilor cu funcția hash criptografică .

Aplicație pentru funcții hash

Deoarece multe funcții hash se bazează pe cifruri bloc , este firesc să încerci atacuri bumerang asupra lor, dar există mai multe obstacole. În special, decriptarea, care este o parte integrantă a unui atac bumerang, poate să nu fie disponibilă în contextul funcțiilor hash.

Cu toate acestea, s-a demonstrat [6] că un atac bumerang, și anume o variantă a acestuia, un atac de bumerang îmbunătățit bazat pe text clar, poate fi folosit pentru a sparge o funcție hash. Acest tip de atac oferă o îmbunătățire față de atacurile diferențiale utilizate anterior .

Ideea principală a adaptării la atac este de a folosi, pe lângă calea diferențială globală atent aleasă, utilizată în atacurile diferențiale clasice, mai multe căi diferențiale suplimentare care sunt foarte bune la un număr limitat de etape, dar nu acoperă întreaga funcție. . Pentru a combina aceste căi diferențiale împreună, este utilizată o schemă de bază de atac cu cifru bloc folosind metoda bumerangului.

Acest atac a fost aplicat cu succes algoritmului SHA-1 .

Dezavantajele algoritmului

Un atac bumerang este o alegere adaptativă a atacului text simplu și text cifrat. Acesta este unul dintre cele mai dificile tipuri de atacuri criptografice de implementat în practică.

În ceea ce privește metoda criptoanalizei diferențiale, aplicarea practică a atacului bumerang este limitată de cerințe ridicate pentru timpul de procesare și volumul de date.

În practică, atacul bumerang a fost aplicat în principal cifrurilor cu un număr redus de runde.

În acest sens, algoritmul este mai mult o realizare teoretică.

Note

↑ 1 2 3 David Wagner. Atacul bumerangului .
↑ 1 2 3 John Kelsey , Tadayoshi Kohno, Bruce Schneier . Atacuri cu bumerang amplificat împotriva lui MARS și a șarpelui cu rotund redus .
↑ Eli Biham , Orr Dunkelman, Nathan Keller. Un atac cu cheie în dreptunghi înrudit asupra întregului KASUMI .
↑ 12 Alex Biriukov . Atacul Boomerang pe AES redus în 5 și 6 runde .
↑ Alex Biriukov, Dmitri Hovratovici. Criptanaliză cu chei înrudite pentru AES-192 și AES-256 complet .
↑ Antoine Joux, Thomas Peyrin. Funcțiile Hash și atacul bumerang (amplificat) .

Literatură

Panasenko S. P. Algoritmi de criptare. Carte de referință specială - Sankt Petersburg. : BHV-SPb , 2009. - 576 p. — ISBN 978-5-9775-0319-8