Linjär kryptoanalys

Inom kryptografi är linjär kryptoanalys en metod för kryptoanalys som använder linjära approximationer för att beskriva hur ett chiffer fungerar .

Linjär kryptoanalys uppfanns av den japanske kryptologen Mitsuru Matsui ( Jap. 松井 充 Matsui Mitsuru ). Algoritmen som föreslogs av honom 1993 (vid Eurocrypt '93-konferensen) syftade ursprungligen till att bryta DES och FEAL [1] . Därefter utvidgades linjär kryptoanalys till andra algoritmer. Idag, tillsammans med differentiell kryptoanalys , är det en av de vanligaste metoderna för att bryta blockchiffer [2] . Också användbar för attacker på strömchiffer .

Upptäckten av linjär kryptoanalys var drivkraften för konstruktionen av nya kryptografiska system [3] .

Hur det fungerar

Kryptering sker i två steg. Den första är att bygga relationer mellan klartext , chiffertext och nyckel som är sanna med stor sannolikhet. Den andra är att använda dessa förhållanden, tillsammans med kända klartext-chiffertext-par, för att härleda nyckelbitarna.

Konstruktion av linjära ekvationer

Meningen med algoritmen är att erhålla följande relationer:

var  är de n :te bitarna av texten, chiffertexten respektive nyckeln.

Dessa samband kallas linjära approximationer . Sannolikheten P för giltigheten av en sådan relation för godtyckligt valda bitar av klartext, chiffertext och nyckel är ungefär lika med 1/2. Sådana förhållanden, vars sannolikhet är märkbart annorlunda än 1/2, kan användas för att öppna algoritmen.

Tanken med linjär kryptoanalys är att bestämma uttryck av formen (1) som har en hög eller låg sannolikhet att inträffa. Om krypteringsalgoritmen har en hög frekvens av ekvation (1), eller vice versa, exekveras ekvationen med en låg frekvens, då indikerar detta en dålig förmåga att randomisera chifferen. Om sannolikheten för att uppfylla ekvation (1) är lika med p , är sannolikheten för förskjutning p − 1/2. Ju större sannolikheten för förskjutning är | | p − 1/2|, desto bättre är tillämpligheten av linjär kryptoanalys med färre klartexter som behövs för en attack [1] [4] .

Det finns flera typer av linjära kryptoanalysattacker [5] [6] [7] . Matsui-algoritmen beaktas: initialt, för varje omgång av chifferet, hittas en linjär approximation med den högsta sannolikheten för bias. De resulterande uttrycken kombineras till en linjär approximation som är gemensam för alla omgångar, vars sannolikhet kan skiftas med hjälp av tecknet överskridande lemma .

Därefter överväger vi en algoritm för att hitta den bästa linjära approximationen för en omgång. I blockchiffer koncentreras analysen till övervägande del på S-boxar , eftersom de är den icke-linjära delen av chiffret. Eftersom S-boxen tar m bitar som indata och returnerar n bitar, måste kryptoanalytikern konstruera 2 m + n approximationer. För att hitta sannolikheten för en approximation ges S-boxen alla 2 m möjliga ingångsvärden och räknar hur många gånger denna approximation är sann för ingångs- och utgångsbitarna. Det resulterande antalet matcher divideras med 2 m . I DES-algoritmen har den linjära approximationen för tabell S5 den högsta sannolikheten för bias , där den fjärde av de sex ingångsbitarna XORed över alla fyra utbitarna med en sannolikhet på 12/64 [8] [4] . För en helomgång DES har en relation med en sannolikhet för uppfyllelse på 1/2 + 2 −24 [9] erhållits .

Linjär kryptoanalys har en mycket användbar egenskap: under vissa förhållanden (till exempel när klartexten är känd för att bestå av ASCII-tecken ), kan relation (1) reduceras till en ekvation av formen [10] [11] :

Det finns inga bitar av vanlig text här, det vill säga du kan bygga en attack baserat endast på chiffertexten. En sådan attack kan appliceras på den avlyssnade chiffertexten och är mer praktisk.

Lemma om skyltarnas gång

Även om approximationen med den största avvikelsen från 1/2 inte är svår att hitta för en omgång, finns det ett problem med att beräkna förspänningssannolikheten när man extrapolerar metoden till ett helrundt chiffer. I princip skulle detta kräva att kryptoanalytikern tittar på alla möjliga kombinationer av klartext och nycklar, vilket inte är genomförbart. Lösningen på detta problem är att göra ett antal antaganden och approximera sannolikheten med hjälp av lemmat om intrång av tecken . Låt oss få linjära approximationer för olika omgångar, som är lika med 0 med sannolikhet . Då är sannolikheten att den totala linjära approximationen är noll [1] [4]

Hämta nyckelbitar

När en linjär approximation väl har erhållits kan en direkt algoritm tillämpas och, med hjälp av klartext-chiffertext-par, gissa värdena för nyckelbitarna. I det här fallet är det logiskt att använda det mest effektiva förhållandet, det vill säga ett för vilket avvikelsen av sannolikheten P från 1/2 är maximal.

För varje uppsättning nyckelbitvärden på höger sida av ekvation (1) beräknas antalet klartext-chiffertextpar T för vilka likhet (1) är sann . Den kandidat för vilken avvikelsen T från hälften av antalet klartext-chiffertextpar är störst i absolut värde antas vara den mest sannolika uppsättningen nyckelbitvärden [1] [4] .

Applikation

Linjär krypteringsanalys utvecklades ursprungligen för attacker på blockchiffer, men är även tillämplig på streamchiffer. Dess tillämpning på DES har studerats i detalj av utvecklaren själv.

Ansökan till DES

Mitsuru Matsuis experiment med klartextattacker (beräkningar utfördes på en 66 MHz HP9750) gav följande resultat [12] [13] :

  • En 8-runda DES krävde 221 kända klartexter. Attacken tog 40 sekunder.
  • Den 12-runda DES krävde 233 kända klartexter och 50 timmar.
  • Den 16-runda DES krävde 243 kända klartexter och 50 dagar.

2001 genomförde Pascal Junod ( fr.  Pascal Junod ) en serie experiment för att fastställa attackens komplexitet. Som ett resultat visade det sig att i verkligheten kan attacken på 16-rundans DES framgångsrikt tillämpas i närvaro av 2 39 -2 41 kända texter [13] .

Med ett stort antal omgångar av chiffer, används linjär kryptoanalys vanligtvis i kombination med "brute force"-metoden  - efter att vissa nyckelbitar har hittats med linjär kryptoanalys, utförs en uttömmande sökning på de möjliga värdena av de återstående bitarna. Detta tillvägagångssätt har flera skäl: för det första tillåter de bästa linjära approximationerna oss att hitta värdena för endast några nyckelbitar, och för det andra är antalet nödvändiga klartexter i det här fallet mindre, och uppräkningen av de återstående nyckelbitarna tar mindre tid [5] [13] .

Till skillnad från differentiell kryptoanalys, som kräver utvalda klartexter, nöjer sig metoden med kända klartexter, vilket avsevärt ökar dess omfattning. Men även i linjär kryptoanalys är det ibland användbart att använda utvalda klartexter istället för kända. Till exempel, för DES, finns det en teknik som kraftigt minskar mängden data och beräkningar som krävs genom att använda utvalda klartexter [7] .

Applikation på andra krypteringsmetoder

Förutom DES och FEAL finns det andra algoritmer som är föremål för linjär kryptoanalys, till exempel:

  1. Linjär kryptoanalys agerar mot RC5- algoritmen om den önskade krypteringsnyckeln faller i klassen av svaga nycklar [14] .
  2. Algoritmerna NUSH och NOEKEON bryts också av linjär kryptoanalys [15] [16] [17] .
  3. En förlängning av linjär kryptoanalys baserad på icke-korrelerade linjära approximationer är tillämplig för att bryta 6-runda AES -192 och AES-256, såväl som 13-runda CLEFIA - 256 [6] .

Försvar mot linjär kryptoanalys

För att attackera ett blockchiffer med hjälp av linjär kryptoanalys räcker det, som beskrivits ovan, att erhålla en linjär relation som är signifikant förskjuten i sannolikhet från 1/2. Följaktligen är det första målet med att designa ett attackbeständigt chiffer att minimera sannolikhetsbias, för att säkerställa att ett sådant förhållande inte existerar. Med andra ord är det nödvändigt att se till att blockchifferet uppfyller det strikta lavinkriteriet (SAL). Ett blockchiffer sägs uppfylla SLC:n om, för någon förändring i texten eller nyckeln i den resulterande chiffertexten, exakt hälften av bitarna vänds om, med varje bit som ändras med en sannolikhet på 1/2. Detta uppnås vanligtvis genom att välja mycket icke-linjära S-boxar och förbättra diffusionen .

Detta tillvägagångssätt ger en bra motivering för säkerheten för ett chiffer, men för att rigoröst bevisa säkerheten mot linjär kryptoanalys måste chifferdesigners ta hänsyn till ett mer komplext fenomen, den linjära skroveffekten [ 6] [ 18] . Det bör noteras att chiffer som är optimala mot någon smal klass av attacker vanligtvis är svaga mot andra typer av attacker. Till exempel är arrangemanget av S-boxar i DES känt, vilket avsevärt ökar motståndet mot linjär kryptoanalys, men försämrar motståndet mot differentiell kryptoanalys [19] .  

Användningen av böjda funktioner spelade en betydande roll i konstruktionen av stabila S-boxar . 1982 fann man att sekvenser med maximal längd byggda på basis av böjda funktioner har extremt låga värden på både korskorrelation och autokorrelation [20] [21] . Därefter har ett antal kryptografer arbetat med användningen av böjda funktioner och deras vektoranaloger för den ultimata ökningen av blockchifferens kryptografiska motstånd mot linjär och differentiell analys [22] [23] [24] .

Se även

Anteckningar

  1. ↑ 1 2 3 4 Matsui, 1993 .
  2. ↑ Ferguson, Schneier, 2004 , sid. 82.
  3. ↑ Heys H. M. , Tavares S. E. Substitution-permutationsnätverk som är resistenta mot differentiell och linjär kryptoanalys  // Journal of Cryptology / I. Damgård - Springer Science+Business Media , International Association for Cryptologic Research , 1996. - Vol. 9, Iss. 1. - S. 1-19. — ISSN 0933-2790 ; 1432-1378 - doi:10.1007/BF02254789
  4. ↑ 1 2 3 4 Heys, 2002 .
  5. ↑ 12 Matsui , 1994 .
  6. ↑ 1 2 3 Bogdanov A. , Rijmen V. Linjära skrov med korrelationsnoll och linjär krypteringsanalys av blockchiffer  // Des . Koder Cryptogr. — Springer US , Springer Science+Business Media , 2014. — Vol. 70, Iss. 3. - s. 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, USA, 10–12 april 2000 Proceedings / G. Goos , J. Hartmanis , J.v. Leeuwen , B. Schneier - Berlin : Springer Berlin Heidelberg , 2001. - P. 262-272. - ( Lecture Notes in Computer Science ; Vol. 1978) - ISBN 978-3-540-41728-6 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-44706-7_18
  8. ↑ Matsui, 1993 , sid. 389.
  9. ↑ Matsui, 1993 , sid. 397.
  10. ↑ Matsui, 1993 , sid. 389, 394.
  11. ↑ Kruppa H. , Shah S. U. A. Differentiell och linjär krypteringsanalys vid utvärdering av AES-kandidatalgoritmer  - 1998 .
  12. ↑ Matsui, 1993 , sid. 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, Kanada, 16–17 augusti 2001 Revised Papers / S. Vaudenay , A. M. Youssef - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Berlin Heidelberg , 2001. - P. 199-211. — 364 sid. - ( Lecture Notes in Computer Science ; 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. Linjärt svaga tangenter av 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. Linjär kryptoanalys av NUSH-blockchiffer  // Vetenskap i Kina Series F : Informationsvetenskap - Vetenskap Kina Press , Springer Science+Business Media , 2002. - Vol. 45, Iss. 1. - S. 59-67. — ISSN 1674-733X ; 1869-1919
  16. ↑ Knudsen L. R. , Raddum H. On Noekeon  (engelska) : NES/DOC/UIB/WP3/009/1. Offentlig rapport från NESSIE-projektet - 2001.
  17. ↑ Säkerhetsutvärdering av NESSIE First Phase (D13) (länk ej tillgänglig) . Hämtad 2 december 2015. Arkiverad från originalet 11 augusti 2017. 
  18. ↑ Röck A. , Nyberg K. Exploiting Linear Hull in Matsui's Algorithm  // WCC 2011 : The Seventh International Workshop on Coding and Cryptography, April 11-15, 2011 Paris, France. Förfaranden - 2011.
  19. ↑ Matsui M. Om korrelationen mellan ordningen på S-boxar och styrkan hos DES  // Advances in Cryptology — EUROCRYPT '94 : Workshop on the Theory and Application of Cryptographic Techniques Perugia, Italien, 9–12 maj 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. Theory / 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  // Framsteg inom kryptologi - CRYPTO '88 : Proceedings / S. Goldwasser - NYC : Springer New York , 1990. - P. 450 -468. - ( Lecture Notes in Computer Science ; Vol. 403) - ISBN 978-0-387-97196-4 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/0-387-34799-2
  22. ↑ Nyberg K. Perfekta olinjära S-boxar  // Advances in Cryptology - EUROCRYPT '91 : Workshop on the Theory and Application of Cryptographic Techniques Brighton, Storbritannien, 8–11 april 1991. Proceedings / D. W. Davies - Berlin : Springer Berlin Heidelberg , 1991. - s. 378-386. — ISBN 978-3-540-54620-7 — doi:10.1007/3-540-46416-6_32
  23. ↑ Seberry J. , Zhang X. Mycket icke-linjär 0-1 balanserade booleska funktioner som uppfyller strikt lavinkriterium (utvidgat sammandrag  ) // Framsteg inom kryptologi - AUSCRYPT '92 : Workshop om teorin och tillämpningen av kryptografiska tekniker Gold Coast, Queensland, Australien, 13–16 december 1992 Proceedings / J. Seberry , Y. Zheng - Berlin : Springer Berlin Heidelberg , 1993. - S. 143-155. - ( Lecture Notes in Computer Science ; Vol. 718) - ISBN 978-3-540-57220-6 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-57220-1
  24. ↑ Adams C. M. Konstruera symmetriska chiffer med hjälp av CAST-designproceduren  // Des . Koder Cryptogr. - Springer US , Springer Science + Business Media , 1997. - Vol. 12, Iss. 3. - s. 283-316. — ISSN 0925-1022 ; 1573-7586 - doi:10.1023/A:1008229029587

Litteratur