Atac cu chei legate

Atacul cu chei înrudite [ 1] este un tip de atac criptografic în care un criptoanalist alege o relație între o pereche de chei, dar cheile în sine rămân necunoscute pentru el. Datele sunt criptate cu ambele chei. În varianta de text simplu cunoscută, criptoanalistul cunoaște textul simplu și textul cifrat al datelor criptate cu două chei. Scopul atacatorului este să găsească cheile secrete reale. Se presupune că atacatorul știe sau alege o relație matematică care leagă cheile între ele. Relația are forma ( ) [2] , unde este funcția aleasă de atacator și sunt cheile asociate. Pentru fiecare criptare, raportul dintre chei este selectat individual. Există multe modalități de a găsi corect acest raport [3] . În comparație cu alte atacuri în care atacatorul poate manipula doar textul simplu și/sau textul cifrat, alegerea relației dintre cheile secrete oferă un grad suplimentar de libertate atacatorului. Dezavantajul acestei libertăți este că astfel de atacuri pot fi mai dificile în practică. Cu toate acestea, designerii încearcă de obicei să creeze primitive „ideale” care să poată fi utilizate automat fără analize suplimentare în cel mai larg set posibil de protocoale sau moduri de operare. Astfel, rezistența unor astfel de atacuri este un obiectiv important de proiectare al cifrurilor bloc și, de fapt, a fost unul dintre obiectivele de proiectare declarate ale algoritmului Rijndael . $K$ $B$ $=$ $F$ $K$ $A$ $F$ $K$ $A$ $K$ $B$

Extensie cheie

Majoritatea algoritmilor de criptare modifică cheia originală pentru o utilizare ulterioară. Această modificare se numește extindere cheie . Există exemple de algoritmi în care procedura de extindere a cheilor este extrem de complexă în comparație cu criptarea propriu-zisă, printre care merită amintiți algoritmii HPC și FROG . Numele procedurii este determinat de faptul că cheia de criptare inițială are de obicei o dimensiune semnificativ mai mică decât setul de subchei utilizate în rundele algoritmului, adică cheia extinsă.

Se pare că algoritmul de criptare poate fi împărțit logic în doi subalgoritmi: transformările efective de criptare și procedura de extindere a cheii. Există o serie de cerințe pentru procedura de extindere a cheii [4] :

Este necesar ca procedura de extindere a cheilor să calculeze cheile în paralel cu transformările de criptare: acest lucru va permite atât paralelizarea calculelor în sistemele multiprocesor, cât și să nu irosească memorie pentru a stoca întreaga cheie extinsă atunci când se criptează în condiții limitate de resurse.
În multe aplicații ale algoritmilor de criptare simetrică, este adesea necesară schimbarea cheilor din criptor. În consecință, o procedură de extindere a cheii foarte complexă nu va permite utilizarea unui algoritm de criptare în aceste cazuri.
Măsura în care un algoritm este susceptibil la atacuri asupra cheilor asociate este, de asemenea, foarte dependentă de procedura de extindere a cheilor.

Atac clasic cu chei legate [1]

Acest tip de atac a fost propus pentru prima dată de omul de știință israelian Eli Biham în 1992 în articolul New Types of Cryptanalytic Attacks Using Related Keys . Atacul cu cheie conectată descris de el seamănă cu un atac de forfecare . Shift attack ( English slide attack ) - atac criptografic , care este, în cazul general, un atac bazat pe text clar selectat , care permite criptoanaliza cifrurilor cu mai multe runde bloc, indiferent de numărul de runde utilizate. Propus de Alex Biryukov și David Wagner în 1999 [5] . Atacul shift folosește două texte clare și satisface următoarea relație: , unde este funcția rotundă și este subcheia primei runde. Un atac asociat cheii folosește o relație similară între chei. Să presupunem că cheia de criptare dorită K după modificarea ei prin procedura de extindere a cheilor oferă o secvență de subchei: , unde este numărul de runde ale algoritmului de criptare. Să presupunem că există o cheie a cărei extindere dă următoarea secvență: , adică secvența de subchei creată pe baza cheii este deplasată ciclic față de secvența cheii dorite cu 1 rundă [6] . $P$ $P'$ $P'=F(P,k_{1})$ $F()$ $k_{1}$ $Ex(K)$ $Ex(K)=\left\{{k_{1},k_{2},\ldots,k_{r-1},k_{r}}\right\}$ $r$ $K'$ $Ex(K')=\left\{{k_{2},k_{3},\ldots,k_{r},k_{1}}\right\}$ $K'$ $K$

Esența atacului

Să presupunem că criptoanalistul cunoaște perechi de texte clare și textele cifrate corespunzătoare acestora (criptate cu cheia ), unde este dimensiunea blocului de date criptate, reprezentată în biți . $2^{\frac {n}{2}}$ $\left({P,C}\right)$ $K$ $n$
În plus, criptoanalistul cunoaște perechi de texte criptate folosind cheia asociată raportului de mai sus. $2^{\frac {n}{2}}$ $\left({P',C'}\right)$ $K'$ $K$
Pentru fiecare corelație de texte , criptoanalistul trebuie să găsească soluții la sistemul de ecuații [7] : $\left({P,C}\right)$ $\left({P',C'}\right)$

${\begin{cases}F(P,k^{*})=P'\\F(C,k^{*})=C'\end{cases))$

Care dintre texte corespunde fiecărui text din , criptoanalistul nu știe dinainte. Dar, probabilitatea ca două texte alese aleatoriu să satisfacă raportul necesar este .Atunci perechea necesară trebuie găsită după analizarea nu mai mult de texte, în conformitate cu paradoxul zilei de naștere . Condiția textelor nu este strictă, este o estimare și va fi îndeplinită doar în medie [8] . $2^{\frac {n}{2}}$ $P$ $P$ ${\frac {1}{2^{n}})$ $\left({P,P'}\right)$ $2^{{\frac {n}{2}}+1}$ $2^{{\frac {n}{2}}+1}$

Cheia găsită din sistemul de mai sus este subcheia necesară . În funcție de operațiunea de generare a cheilor, cunoștințele pot oferi criptoanalistului multe oportunități de acces neautorizat la informații. De exemplu, generarea cheii a algoritmului LOKI89 este construită în așa fel încât să fie pur și simplu partea stângă de 32 de biți a cheii . Deoarece acest algoritm folosește o cheie de 64 de biți, după calcul, este suficient doar să enumerați opțiunile pentru a o găsi . [9] $k^{*}$ $k_{1}$ $k_{1}$ $k_{1}$ $K$ $k_{1}$ $K$ $2^{32}$

Funcția rotundă a algoritmului atacat trebuie să fie suficient de slabă pentru a calcula , ceea ce este cazul majorității algoritmilor de criptare moderni. În plus, complexitatea atacului poate fi redusă semnificativ în raport cu cazul descris mai sus, totul depinde de algoritmul de criptare a textului simplu ales. De exemplu, calculele sunt simplificate pentru algoritmii bazați pe o rețea Feistel echilibrată . $F()$ $k^{*}$

Atacuri la diverși algoritmi de criptare

Atacul asupra DES

DES ( data encryption s tandard ) este un algoritm de criptare simetrică dezvoltat de IBM și aprobat de guvernul SUA în 1977 ca standard oficial ( FIPS 46-3). Dimensiunea blocului pentru DES este de 64 de biți . Algoritmul se bazează pe o rețea Feistel cu 16 cicluri ( runde ) și o cheie de 56 de biți . Algoritmul folosește o combinație de transformări neliniare (S-box) și liniare (permutări E, IP, IP-1).

Algoritmul de criptare DES este rezistent la un astfel de atac. În timpul procesului de criptare pentru funcția principală de criptare , este necesar să se calculeze șaisprezece chei de 48 de biți, care sunt rezultatul conversiei cheii originale de 56 de biți ( pentru mai multe detalii, consultați secțiunea „Generare chei” ). $k_i$ Numărul de schimburi din algoritmul de calcul cheie nu se potrivește în toate rundele. În mod obișnuit, registrele cheie sunt deplasate cu doi biți după fiecare rundă și doar un bit după prima, a noua și a cincisprezecea rundă. Cu toate acestea, dacă schimbați această schemă de comutare, setați schimbarea să fie aceeași în toate rundele, atunci criptosistemul rezultat devine vulnerabil la un atac cu cheie conectată. Cel mai puțin sigur la atac este DES modificat, în care cheia este deplasată cu doi biți după fiecare etapă [10] . $k_i$

Tabelul descrie numărul de schimburi înainte de fiecare rundă de generare a cheilor și varianta modificată a numărului de schimburi, care este vulnerabilă la un atac legat de chei. Pentru a sparge o astfel de variantă a algoritmului, criptoanalistul ar avea nevoie doar de 2 17 texte clare alese pentru cheile alese sau 2 33 de texte clare cunoscute pentru cheile alese. Pentru a sparge DES modificat, este necesar să se efectueze 1,43*2 53 operații, ceea ce reprezintă un mic câștig față de căutarea exhaustivă, unde numărul de operații este de 2 56 [11] . În 1998, folosind un supercomputer de cracker DES de 250.000 USD , DES a fost spart în mai puțin de trei zile [12] . EFF DES cracker a folosit o căutare cu forță brută [13] pentru cracare . Cerințele uriașe de timp și volum de date nu permit implementarea unui atac asupra cheilor conectate fără ajutorul unor echipamente scumpe. Dar, cu toate acestea, atacul este interesant din două motive:

Aceasta este prima încercare de atac criptoanalitic asupra algoritmului de generare a subcheilor DES.
Complexitatea nu depinde de numărul de etape ale algoritmului criptografic, este la fel de eficient împotriva DES cu 16, 32 sau 1000 de etape.

Atacul asupra AES

Advanced Encryption Standard ( AES ), cunoscut și sub numele de Rijndael (pronunțat [rɛindaːl] (Randal [14] )) este un algoritm de criptare bloc simetric (dimensiunea blocului 128 biți, cheie 128/192/256 biți) adoptat ca standard de criptare de către Guvernul SUA în conformitate cu rezultatele competiţiei AES . Acest algoritm a fost bine analizat și este acum utilizat pe scară largă, așa cum a fost cazul predecesorului său DES . AES vine în trei variante, fiecare oferind un nivel diferit de securitate, în funcție de lungimea cheii secrete. Cheia poate avea o lungime de 128, 192 și 256 de biți. Din 2001, după alegerea AES ca standard criptografic, progresul în criptoanaliza sa a fost extrem de scăzut [15] . Cele mai bune rezultate au fost obținute în cursul atacurilor bazate pe chei aferente în 2009. Alex Biryukov , împreună cu Dmitri Khovratovich, au furnizat primul atac criptoanalitic cu cheie conectată asupra AES-192 și AES-256, metoda dezvoltată este mai rapidă decât forța brută.

Atacul dezvoltat asupra AES-256 este potrivit pentru toate tipurile de chei și are o complexitate de aproximativ 2 96. A fost prezentat și un atac asupra AES-192. Ambele atacuri minimizează numărul de casete S active ale algoritmului de generare a cheilor. Această operațiune se aplică folosind un atac bumerang . Caracteristicile diferențiale pentru bumerang au fost stabilite prin căutarea coliziunilor locale în cifr [16] . Caracteristica principală a AES-256, care este decisivă pentru atacurile luate în considerare, este că algoritmul de criptare are 14 runde și o cheie de 256 de biți care se dublează în starea internă. Prin urmare, algoritmul de generare a cheilor este format din doar 7 runde, iar fiecare rundă are la rândul său 8 S-box. În mod similar pentru AES-192, datorită faptului că cheia devine de o dată și jumătate mai mare în starea internă, algoritmul de generare a cheii este format din doar 8, nu 12 runde. Fiecare rundă are doar 4 blocuri S.

Atacul asupra AES-256

Este necesar să efectuați următorii pași de 2 25,5 ori [17] :

Pregătiți structura textelor clare așa cum este indicat mai jos.
Criptați-l cu chei și și salvați seturile rezultate și . $K_{A}$ $K_{B}$ $S_{A}$ $S_{B}$
Este necesar să efectuați operația pentru toate textele cifrate și să decriptați textele cifrate modificate cu cheia . - un nou set de texte deschise. $xor~\Delta _{C}$ $S_{A}$ $K_C$ $S_{C}$
În mod similar pentru și cheie . - un nou set de texte deschise. $S_{B}$ $K_{D}$ $S_{D}$
Comparație a tuturor perechilor de texte clare de la și cu o lungime de 56 de biți. $S_{C}$ $S_{D}$
Pentru restul, verificați dacă există o diferență în valoarea probabilității la . Dacă este egală de ambele părți ale filtrului de 16 biți, atunci pentru perechile de chei sau altfel se numesc cvartet și , la , va fi, de asemenea, egală pe ambele laturi. $p_{i,0}$ $i>1$ $\left({K_{A},K_{B}}\right)$ $\left({K_{C},K_{D))\right)$ $\nabla k_{i,7}^{0}=0$ $\Delta k_{i,0}^{0)$
Este necesar să selectați cvartete ale căror diferențe nu pot fi afectate de casetele S active în prima rundă și de casetele S active în algoritmul de generare a cheilor.
Filtrarea cvartetelor incorecte, restabilim parțial valoarea cheii.

Fiecare structură are tot felul de opțiuni pentru coloana zero, rândul zero și o valoare constantă în alți octeți. Din cele 272 de texte din fiecare structură, se pot compara 2144 de perechi. Dintre aceste perechi, 2 (144−8*9) = 2 72 vor trece de prima rundă. Astfel, obținem 1 cvartet necesar de 2 (96-72) = 2 24 structuri și 3 cvartete necesare de 2 25,5 structuri. Calculăm numărul de cvartete din ultimii 6 pași, vor fi aproximativ 2 (144-56-16) = 2 72 de perechi. Următorul pas este aplicarea unui filtru de 16 biți, astfel încât obținem numărul total de cvartete posibile 2 (72+25,5−6) = 2 91,5 [18] .

Atacul asupra AES-192

Algoritmul de generare a cheilor în acest caz are cea mai bună difuzie. Prin urmare, atacul bumerang folosește două subtrack a câte 6 runde fiecare. Să analizăm 2 73 de structuri cu 2 48 de texte conform următoarei scheme [19] :

Comparați toate perechile de texte clare posibile pentru perechile de chei și . $\left({K_{A},K_{B}}\right)$ $\left({K_{C},K_{D))\right)$
Comparați și stocați toate cvartetele de text cifrat.
Pentru fiecare octet cheie așteptat : și în ; în și : $k^{0,3}$ $k^{2,3}$ $k^{0,5}$ $K_{A}$ $k^{0,5}$ $K_{A}$ $K_{B}$
1. calculați valorile pentru acești octeți în toate cheile din urma delta. Obțineți diferențe cheie în și ; $\Delta K^{0)$ $\nabla K^{8}$
2. alege cvartete care contrazic ; $\nabla K^{8}$
3. pregătiți contoare pentru octeții de cheie necalculați care corespund cutiilor S active în primii doi și ultimii: , , , — în chei și , , , , — în chei și , 16 octeți în total; $K^{0,0}$ $k^{0,1}$ $k^{1,2}$ $k^{3,0}$ $K_{A}$ $K_C$ $k^{0,0}$ $k^{0,1}$ $k^{0,2}$ $k^{0,3}$ $K_{A}$ $K_{B}$
4. pentru fiecare cvartet, setați valorile posibile pentru octeții lor necunoscuți și creșteți contoarele;
5. creați un grup de 16 octeți cheie cu numere maxime;
6. încercați toate valorile posibile ale cheii de 9 octeți încă necunoscute și verificați dacă cheia este corectă. Dacă scenariul eșuează, treceți la primul pas [19] . $K^{0}$

Ambele atacuri prezentate sunt în principal de interes teoretic și în practică nu reprezintă o amenințare reală pentru aplicațiile care utilizează AES.

Aplicație practică

Atacurile descrise folosind chei aferente nu par practice. În multe evoluții, acestea nu beneficiază prea mult în comparație cu căutarea exhaustivă, în plus, necesită un număr mare de ipoteze. Acest atac a fost mult timp considerat destul de puternic, dar pur teoretic [20] . Cu toate acestea, experți precum John Kelsey și Bruce Schneier [20] cred acum că atacurile cu chei legate pot avea aplicații practice. Unele implementări de algoritmi criptografici sau protocoale de rețea (de exemplu, protocoale de autentificare sau de schimb de chei) pot fi deja susceptibile la un atac de chei legate [20] . O aplicație potențială este analiza funcției hash . Teoretic, atacurile cu chei legate pot fi periculoase dacă algoritmii de criptare simetrici sunt utilizați pentru a construi funcții hash. În prezent, nu se cunoaște nicio aplicație specifică pentru funcțiile hash, dar designerii de funcții hash ar trebui să ia în considerare atunci când proiectează că există o astfel de slăbiciune. În orice caz, se recomandă cu tărie să se țină cont de criptoanaliza pe cheile asociate atunci când se dezvoltă algoritmi de criptare și implementarea acestora [21] . Se notează în [20] că condiția principală pentru atac pare destul de ciudată: criptoanalistul poate scrie cheia, adică poate modifica cheia necunoscută dorită în modul cerut, dar nu o poate citi. Cu toate acestea, unele implementări ale algoritmilor criptografici sau protocoalelor de rețea pot fi atacate folosind chei asociate. În orice caz, se recomandă cu tărie să se țină cont de criptoanaliza pe cheile legate [20] atunci când se dezvoltă algoritmi de criptare și implementarea acestora. De asemenea, se remarcă faptul că atacurile asupra cheilor asociate pot fi foarte periculoase dacă algoritmii de criptare simetrici sunt utilizați pentru a construi funcții hash.

Există și alte vulnerabilități potențiale introduse în algoritmul de criptare printr-o procedură de extindere a cheii prost concepută, în special [22] :

vulnerabilitate la atacurile din clasa „meeting in the middle”, deoarece aceste atacuri exploatează faptul că prima parte a transformărilor de criptare ale algoritmului atacat utilizează un set diferit de biți de cheie. decât partea a doua.
Cheile slabe sunt chei care sunt echivalente cu descifrarea sau au alte caracteristici care fac mai ușor de spart.
chei echivalente - chei diferite, dar care oferă același rezultat de criptare pe un anumit subset de texte clare.
clase de chei - apar atunci când un criptoanalist poate determina relativ ușor subsetul setului de chei căruia îi aparține cheia necesară și, în consecință, poate reduce zona de enumerare completă a cheii.

Vezi și

Atacul ghicit

Note

↑ 1 2 Panasenko S., 2009 , p. 54.
↑ Biryukov și Hovratovici, 2009 , p. opt.
↑ Bellare, 2003 , p. 491.
↑ Panasenko S., 2009 , p. 53.
↑ Biryukov, Wagner, 1999 , p. 245-259.
↑ Biryukov și Hovratovici, 2009 , p. 7.
↑ Biham, 1994 , p. 16.
↑ Panasenko S., 2009 , p. 55.
↑ Panasenko S., 2009 , p. 56.
↑ Biham, 1994 , p. cincisprezece.
↑ Biham, 1994 , p. 17.
↑ Computerworld, 1998 .
↑ DES Cracker Project (link în jos) . Eff. — „Miercuri, 17 iulie 1998, EFF DES Cracker, care a fost construit pentru mai puțin de 250.000 USD, a câștigat cu ușurință concursul „DES Challenge II” al Laboratorului RSA și un premiu în bani de 10.000 USD.” Consultat la 8 iulie 2007. Arhivat din original la 7 mai 2017. (nedefinit)
↑ „... În conformitate cu regulile flamande, numele se citește ca „Randal” - „Computerra”, decembrie 1999, nr. 49
↑ Biryukov și Hovratovici, 2009 , p. unu.
↑ Biryukov și Hovratovici, 2009 , p. 2.
↑ Biryukov și Hovratovici, 2009 , p. 9.
↑ Biryukov și Hovratovici, 2009 , p. zece.
↑ 1 2 Biriukov și Hovratovici, 2009 , p. 12.
↑ 1 2 3 4 5 John Kelsey, 1996 .
↑ Biham, 1994 , p. 2.
↑ Panasenko S., 2009 , p. 59.

Literatură

Shnaer B. Criptografia aplicată. Protocoale, algoritmi, texte sursă în limbaj C. - Triumf, 2002. - 816 p. - ISBN 5-89392-055-4 , 0-471-11709-9.
Eli Biham . Noi tipuri de atacuri criptoanalitice folosind chei înrudite // Springer-Verlag: Journal. - 1994. - Nr. 4 . - P. 229-246 . — ISSN 1432-1378 . - doi : 10.1007/BF00203965 .
Alex Biryukov , Dmitri Hovratovici. Criptanaliza cheie aferentă AES-192 și AES-256 complet // Springer Berlin Heidelberg: Journal. - 2009. - P. 1-18 . — ISSN 978-3-642-10366-7 . - doi : 10.1007/978-3-642-10366-7_1 .
Alex Biryukov, David Wagner. Slide Attacks // Criptare rapidă a software-ului. 6th International Workshop, FSE'99 Roma, Italia, 24–26 martie, 1999 Proceedings. - Springer Berlin Heidelberg, 1999. - ISBN 978-3-540-66226-6 . (link indisponibil)
Panasenko S. Criptanalitice atacuri asupra cheilor legate // CIO-World : jurnal. — 2007.
Panasenko S. Algoritmi de criptare. Manual special . - BHV-Petersburg. - 2009. - S. 53-59.
Alexandru Tyrenko. Algoritmul DES a spart în trei zile // Computerworld Rusia: revistă. - 1998. - Nr. 28-29 .
John Kelsey, Bruce Schneier, David Wagner. Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER și Triple-DES // Advances in Cryptology - CRYPTO '96, 16th Annual International Cryptology Conference, Santa Barbara, California, SUA, 18-22 august 1996, Proceedings : revista. — 1996.
Mihir Bellare și Tadayoshi Kohno. Un tratament teoretic al atacurilor cheie conexe: RKA-PRP, RKA-PRF și aplicații . — EUROCRIPTĂ. - 2003. - S. 491-506.