Criptanaliza liniară

În criptografie , criptoanaliza liniară este o metodă de criptoanaliza care utilizează aproximări liniare pentru a descrie funcționarea unui cifr .

Criptanaliza liniară a fost inventată de criptologul japonez Mitsuru Matsui ( Jap. 松井 充 Matsui Mitsuru ). Algoritmul propus de el în 1993 (la conferința Eurocrypt '93) avea ca scop inițial spargerea DES și FEAL [1] . Ulterior, criptoanaliza liniară a fost extinsă la alți algoritmi. Astăzi, împreună cu criptoanaliza diferențială , este una dintre cele mai comune metode de spargere a cifrurilor bloc [2] . De asemenea, util pentru atacuri asupra cifrurilor de flux .

Descoperirea criptoanalizei liniare a fost impulsul pentru construirea de noi scheme criptografice [3] .

Cum funcționează

Criptanaliza are loc în două etape. Primul este de a construi relații între textul simplu , textul cifrat și cheia care sunt adevărate cu mare probabilitate. Al doilea este de a folosi aceste rapoarte, împreună cu perechile cunoscute text simplu-text cifrat, pentru a deriva biții cheie.

Construcția ecuațiilor liniare

Semnificația algoritmului este de a obține următoarele relații:

unde  sunt cei n - lei biți ai textului, textului cifrat și, respectiv, cheii.

Aceste relații se numesc aproximări liniare . Probabilitatea P de valabilitate a unei astfel de relații pentru biții aleși în mod arbitrar ai textului simplu, textului cifrat și cheii este aproximativ egală cu 1/2. Astfel de rapoarte, a căror probabilitate este semnificativ diferită de 1/2, pot fi folosite pentru a deschide algoritmul.

Ideea criptoanalizei liniare este de a determina expresii de forma (1) care au o probabilitate mare sau mică de apariție. Dacă algoritmul de criptare are o frecvență înaltă a ecuației (1), sau invers, ecuația este executată cu o frecvență scăzută, atunci aceasta indică o capacitate slabă de a randomiza cifrul. Dacă probabilitatea de a satisface ecuația (1) este egală cu p , atunci probabilitatea de deplasare este p − 1/2. Cu cât valoarea probabilității deplasării este mai mare | | p − 1/2|, cu atât aplicabilitatea criptoanalizei liniare este mai bună cu mai puține texte clare necesare pentru un atac [1] [4] .

Există mai multe tipuri de atacuri de criptoanaliza liniară [5] [6] [7] . Se ia în considerare algoritmul Matsui: inițial, pentru fiecare rundă a cifrului, se găsește o aproximare liniară cu cea mai mare probabilitate de părtinire. Expresiile rezultate sunt combinate într-o aproximare liniară comună tuturor rundelor, a cărei probabilitate poate fi deplasată folosind lema de depășire a semnului .

În continuare, luăm în considerare un algoritm pentru găsirea celei mai bune aproximări liniare pentru o rundă. În cifrurile bloc, analiza se concentrează predominant pe cutiile S , deoarece acestea sunt partea neliniară a cifrului. Deoarece S-box ia m biți ca intrare și returnează n biți, criptoanalistul trebuie să construiască 2 m + n aproximări. Pentru a găsi probabilitatea pentru o aproximare, caseta S primește toate cele 2 m valori de intrare posibile și numără de câte ori această aproximare este adevărată pentru biții de intrare și de ieșire. Numărul rezultat de potriviri se împarte la 2 m . În algoritmul DES, aproximarea liniară pentru tabelul S 5 are cea mai mare probabilitate de polarizare , în care al patrulea din cei șase biți de intrare este XOR pe toți cei patru biți de ieșire cu o probabilitate de 12/64 [8] [4] . Pentru un DES cu rundă completă, a fost obținută o relație cu o probabilitate de îndeplinire de 1/2 + 2 −24 [9] .

Criptanaliza liniară are o proprietate foarte utilă: în anumite condiții (de exemplu, când textul simplu este cunoscut ca fiind format din caractere ASCII ), relația (1) poate fi redusă la o ecuație de forma [10] [11] :

Nu există fragmente de text simplu aici, adică puteți construi un atac bazat doar pe textul cifrat. Un astfel de atac poate fi aplicat textului cifrat interceptat și este mai practic.

Lema despre mersul semnelor

Deși aproximarea cu cea mai mare abatere de la 1/2 nu este dificil de găsit pentru o rundă, există o problemă cu calcularea probabilității de părtinire atunci când se extrapolează metoda la un cifr cu rotund complet. În principiu, acest lucru ar necesita ca criptoanalistul să analizeze toate combinațiile posibile de texte clare și chei, ceea ce nu este fezabil. Soluția la această problemă este de a face o serie de ipoteze și de a aproxima probabilitatea folosind lema despre incursiunea semnelor . Să obținem aproximări liniare pentru diferite runde, care sunt egale cu 0 cu probabilitate . Atunci probabilitatea ca aproximarea liniară globală să fie zero este [1] [4]

Obținerea biților cheie

Odată obținută o aproximare liniară, se poate aplica un algoritm direct și, folosind perechi text simplu-text cifrat, se ghicesc valorile biților cheie. În acest caz, este logic să se folosească cel mai eficient raport, adică unul pentru care abaterea probabilității P de la 1/2 este maximă.

Pentru fiecare set de valori de biți cheie din partea dreaptă a ecuației (1) , se calculează numărul de perechi text simplu-text cifrat T pentru care egalitatea (1) este adevărată . Candidatul pentru care abaterea T de la jumătate din numărul de perechi text simplu-text cifrat este cea mai mare în valoare absolută se presupune că este cel mai probabil set de valori ale biților cheie [1] [4] .

Aplicație

Criptanaliza liniară a fost dezvoltată inițial pentru atacuri asupra cifrurilor bloc, dar este aplicabilă și cifrurilor în flux. Aplicația sa la DES a fost studiată în detaliu de către dezvoltatorul însuși.

Aplicație la DES

Experimentele lui Mitsuru Matsui cu privire la atacuri cu text clar (calculele au fost efectuate pe un HP9750 de 66 MHz) au dat următoarele rezultate [12] [13] :

  • Un DES cu 8 runde necesita 221 de texte clare cunoscute . Atacul a durat 40 de secunde.
  • DES cu 12 runde a necesitat 233 de texte clare cunoscute și 50 de ore.
  • DES cu 16 runde a necesitat 243 de texte clare cunoscute și 50 de zile.

În 2001, Pascal Junod ( fr.  Pascal Junod ) a efectuat o serie de experimente pentru a determina complexitatea atacului. Ca urmare, s-a dovedit că, în realitate, atacul asupra DES cu 16 runde poate fi aplicat cu succes în prezența a 2 39 -2 41 de texte cunoscute [13] .

Cu un număr mare de runde ale cifrului, criptoanaliza liniară este de obicei utilizată în combinație cu metoda „forței brute”  - după ce anumiți biți cheie sunt găsiți folosind criptoanaliza liniară, se efectuează o căutare exhaustivă asupra valorilor posibile ale biții rămași. Această abordare are mai multe motive: în primul rând, cele mai bune aproximări liniare ne permit să găsim valorile doar ale unor biți cheie și, în al doilea rând, numărul de texte clare necesare în acest caz este mai mic, iar enumerarea biților cheie rămași durează mai puțin. timp [5] [13] .

Spre deosebire de criptoanaliza diferențială, care necesită texte clare alese, metoda se mulțumește cu texte clare cunoscute, ceea ce îi mărește semnificativ domeniul de aplicare. Cu toate acestea, chiar și în criptoanaliza liniară este uneori util să folosiți texte clare alese în loc de cele cunoscute. De exemplu, pentru DES, există o tehnică care reduce foarte mult cantitatea de date și de calcul necesare utilizând texte clare selectate [7] .

Aplicare la alte metode de criptare

Pe lângă DES și FEAL, există și alți algoritmi care sunt supuși criptoanalizei liniare, de exemplu:

  1. Criptanaliza liniară acționează împotriva algoritmului RC5 dacă cheia de criptare dorită se încadrează în clasa cheilor slabe [14] .
  2. Algoritmii NUSH și NOEKEON sunt de asemenea sparți prin criptoanaliza liniară [15] [16] [17] .
  3. O extensie a criptoanalizei liniare bazată pe aproximări liniare necorelate este aplicabilă pentru spargerea AES -192 și AES-256 cu 6 runde, precum și CLEFIA - 256 cu 13 runde [6] .

Apărare împotriva criptoanalizei liniare

Pentru a ataca un cifru bloc folosind criptoanaliza liniară, este suficient, așa cum este descris mai sus, să obțineți o relație liniară care este deplasată semnificativ în probabilitate de la 1/2. În consecință, primul obiectiv în proiectarea unui cifr rezistent la atac este de a minimiza părtinirea probabilistică, pentru a vă asigura că o astfel de relație nu există. Cu alte cuvinte, este necesar să ne asigurăm că cifrul bloc îndeplinește criteriul strict de avalanșă (SAL). Se spune că un cifru bloc satisface SLC dacă, pentru orice modificare a textului sau a cheii în textul cifrat rezultat, exact jumătate dintre biți sunt inversați, fiecare bit schimbându-se cu o probabilitate de 1/2. Acest lucru se realizează de obicei prin selectarea unor cutii S foarte neliniare și prin îmbunătățirea difuziei .

Această abordare oferă o bună justificare pentru securitatea unui cifr, dar pentru a dovedi în mod riguros securitatea împotriva criptoanalizei liniare, proiectanții de cifru trebuie să ia în considerare un fenomen mai complex, efectul liniar hull [ 6] [ 18] . Trebuie remarcat faptul că cifrurile care sunt optime împotriva unor clase restrânse de atacuri sunt de obicei slabe împotriva altor tipuri de atacuri. De exemplu, este cunoscută dispunerea cutiilor S în DES, care crește semnificativ rezistența la criptoanaliza liniară, dar înrăutățește rezistența la criptoanaliza diferențială [19] .  

Utilizarea funcțiilor îndoite a jucat un rol semnificativ în construcția de cutii S stabile . În 1982, s-a constatat că secvențele de lungime maximă construite pe baza funcțiilor îndoite au valori extrem de mici atât ale corelației încrucișate, cât și ale autocorelației [20] [21] . Ulterior, un număr de criptografi au lucrat la utilizarea funcțiilor îndoite și a analogilor lor vectoriali pentru creșterea finală a rezistenței criptografice a cifrurilor bloc la analiza liniară și diferențială [22] [23] [24] .

Vezi și

Note

  1. ↑ 1 2 3 4 Matsui, 1993 .
  2. ↑ Ferguson, Schneier, 2004 , p. 82.
  3. ↑ Heys H. M. , Tavares S. E. Rețele de substituție-permutare rezistente la criptoanaliza diferențială și liniară  // Journal of Cryptology / I. Damgård - Springer Science+Business Media , International Association for Cryptologic Research , 1996. - Vol. 9, Iss. 1. - P. 1-19. — ISSN 0933-2790 ; 1432-1378 - doi:10.1007/BF02254789
  4. ↑ 1 2 3 4 Hei, 2002 .
  5. ↑ 12 Matsui , 1994 .
  6. ↑ 1 2 3 Bogdanov A. , Rijmen V. Linear Hulls with Correlation Zero and Linear Cryptanalysis of Block Ciphers  // Des . Codurile Cryptogr. — Springer US , Springer Science+Business Media , 2014. — Vol. 70, Iss. 3. - P. 369-383. — ISSN 0925-1022 ; 1573-7586 - doi:10.1007/S10623-012-9697-Z
  7. ↑ 1 2 Knudsen L. R. , Mathiassen J. E. A Chosen-Plaintext Linear Attack on DES  // Fast Software Encryption : 7th International Workshop , FSE 2000 New York, NY, SUA, 10–12 aprilie 2000 Proceedings / G. Goos , J. , J. v. Leeuwen , B. Schneier - Berlin : Springer Berlin Heidelberg , 2001. - P. 262-272. - ( Note de curs în Informatică ; Vol. 1978) - ISBN 978-3-540-41728-6 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-44706-7_18
  8. ↑ Matsui, 1993 , p. 389.
  9. ↑ Matsui, 1993 , p. 397.
  10. ↑ Matsui, 1993 , p. 389, 394.
  11. ↑ Kruppa H. , Shah S. U. A. Criptanaliză diferențială și liniară în evaluarea algoritmilor candidați AES  - 1998 .
  12. ↑ Matsui, 1993 , p. 387.
  13. ↑ 1 2 3 Junod P. On the Complexity of Matsui's Attack  // Selected Areas in Cryptography : 8th Annual International Workshop , SAC 2001 Toronto, Ontario, Canada, August 16–17, 2001 Revised Papers / S. Vaudenay , A. M. Youssef - Berlin , Heidelberg , New York, NY , Londra [etc.] : Springer Berlin Heidelberg , 2001. - P. 199-211. — 364 p. - ( Note de curs în Informatică ; Vol. 2259) - ISBN 978-3-540-43066-7 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-45537-X_16
  14. ↑ Heys H. M. Linearly weak keys of RC5  // IEE Electronics Letters - IEEE , 1997. - Vol . 33, Iss. 10. - P. 836-837. — ISSN 0013-5194 ; 1350-911X - doi:10.1049/EL:19970601
  15. ↑ Wu W. , Feng D. Criptanalysis linear al cifrului bloc NUSH  // Science in China Series F : Information Sciences - Science China Press , Springer Science+Business Media , 2002. - Vol. 45, Iss. 1. - P. 59-67. — ISSN 1674-733X ; 1869-1919
  16. ↑ Knudsen L. R. , Raddum H. On Noekeon  (engleză) : NES/DOC/UIB/WP3/009/1. Raport public al proiectului NESSIE - 2001.
  17. ↑ Evaluarea securității pentru prima fază NESSIE (D13) (link nu este disponibil) . Preluat la 2 decembrie 2015. Arhivat din original la 11 august 2017. 
  18. ↑ Röck A. , Nyberg K. Exploiting Linear Hull in Matsui's Algorithm  // WCC 2011 : The Seventh International Workshop on Coding and Cryptography, 11-15 aprilie 2011 Paris, Franța. Proceduri - 2011.
  19. ↑ Matsui M. On corelation between the S-boxes and the strength of DES  // Advances in Cryptology — EUROCRYPT '94 : Workshop on the Theory and Application of Cryptographic Techniques Perugia, Italy, May 9–12, 1994 Proceedings / A. D. Santis - Berlin : Springer Berlin Heidelberg , 1995. - P. 366-375. - ISBN 978-3-540-60176-0 - doi:10.1007/BFB0053451
  20. ↑ Olsen J. D. , Scholtz R. A. , Welch L. R. Bent-function sequences  // IEEE Trans . inf. Teorie / F. Kschischang - IEEE , 1982. - Vol. 28, Iss. 6. - P. 858-864. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1982.1056589
  21. ↑ Forrié R. The Strict Avalanche Criterion: Spectral Properties of Boolean Functions and an Extended Definition  // Advances in Cryptology - CRYPTO '88 : Proceedings / S. Goldwasser - NYC : Springer New York , 1990. - P. 450 -468. - ( Note de curs în Informatică ; Vol. 403) - ISBN 978-0-387-97196-4 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/0-387-34799-2
  22. ↑ Nyberg K. Perfect nonlinear S-boxes  // Advances in Cryptology - EUROCRYPT '91 : Workshop on the Theory and Application of Cryptographic Techniques Brighton, UK, April 8–11, 1991. Proceedings / D. W. Davies - Berlin : Springer Berlin Heidelberg , 1991. - P. 378-386. — ISBN 978-3-540-54620-7 — doi:10.1007/3-540-46416-6_32
  23. ↑ Seberry J. , Zhang X. Funcții booleene echilibrate 0-1 înalt neliniare care satisfac criteriul strict de avalanșă (Rezumat extins  ) // Advances in Cryptology - AUSCRYPT '92 : Workshop on the Theory and Application of Cryptographic Techniques Gold Coast, Queensland, Australia, 13–16 decembrie 1992 Proceedings / J. Seberry , Y. Zheng - Berlin : Springer Berlin Heidelberg , 1993. - P. 143-155. - ( Note de curs în Informatică ; Vol. 718) - ISBN 978-3-540-57220-6 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-57220-1
  24. ↑ Adams C. M. Constructing Symmetric Ciphers Using the CAST Design Procedure  // Des . Codurile Cryptogr. - Springer US , Springer Science + Business Media , 1997. - Vol. 12, Iss. 3. - P. 283-316. — ISSN 0925-1022 ; 1573-7586 - doi:10.1023/A:1008229029587

Literatură