XSL-attack

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 12 mars 2017; kontroller kräver 19 redigeringar .

XSL-attack ( eng.  eXtended Sparse Linearization , algebraisk attack) är en kryptografisk analysmetod baserad på chifferets algebraiska egenskaper . Metoden går ut på att lösa ett speciellt ekvationssystem .

Denna metod föreslogs 2001 av Nicolas T. Courtois och Josef Pieprzyk.

XSL-attacker ansågs tidigare omöjliga, men den 26 maj 2006 visade Courtois möjligheten av en XSL-attack mot en enda chiffermodell som liknar AES- chifferets struktur [1] .

Som en av skaparna av Rijndael- chifferet sa i privat korrespondens: "XSL är inte en attack, det är bara en dröm." "Den här drömmen kan förvandlas till en mardröm", svarade Nicolas Courtois [2] .

Om XSL-attacker verkligen fungerar kommer de att bryta alla befintliga chiffer. Endast en ren slump kan rädda chiffret från att gå sönder. Å andra sidan är det fullt möjligt (och ur vår synvinkel, mest troligt) att XSL-attacker inte är tillämpliga i praktiken, eller bara är tillämpliga på ett litet antal högstrukturerade chiffer.

— Nils Ferguson , Bruce Schneier Praktisk kryptografi [3]


Skapande historia

År 2001 publicerade Niels Ferguson , Richard Schroeppel och D. Whiting en artikel [4] där de kunde representera Rijndael-chifferet som en algebraisk formel med hjälp av representationerna av chifferets linjära delar och icke-linjära S-boxar i i form av ekvationer av högre ordning. De drog slutsatsen att alla symmetriska blockchiffer kan reduceras till en flerdimensionell ekvation över något ändligt fält . De undrade också om att veta om den algebraiska formen skulle hjälpa till att bryta chifferet . Om funktionen som uttrycker S-boxar inte tar hänsyn till argument i styrkan av -1, så blir chiffern affin och bryts lätt på andra sätt som inte kräver linjärisering . Om vi ​​likställer dessa argument med , så visar sig ekvationen vara polynomiellt komplex.

Under de åren dök många attacker mot offentliga nycklar upp: en attack mot Matsumoto-Imai-systemet [5] , en attack mot HFE [6] . Dessa attacker slutade med framgång omedelbart efter upptäckten av faktumet (teoretiskt eller experimentellt) av existensen av ytterligare ekvationer av många variabler, som inte är uppenbara och inte tillhandahålls av utvecklarna av det ursprungliga chiffer [7] .

Adi Shamir 1998 visade att andragradsekvationer av många variabler (MQ) är ett NP-komplett problem [8] . Dess komplexitet minskar markant när ekvationerna omdefinieras [7] . I den första studien visar Nicolas Courtois och Jozef Pepshik att de resulterande MQ:erna är glesa och har en regelbunden struktur [7] .

Den 2 december 2002 vid ASIACRYPT-2002 presenterade Nicolas Courtois och Jozef Pepshik artikeln "Cryptanalysis of block ciphers with overdefined systems of equations", där de först presenterade två varianter av XSL-attackmetoden [9] . Slutsatsen från detta arbete är att säkerheten för AES endast bygger på omöjligheten för tillfället att lösa ekvationssystemet som beskriver chifferets algebraiska struktur.

XSL-chiffer

Genom att generalisera klassen av SP-chiffer, som består av S-boxar och permutation av bitfunktioner, utsåg Courtois och Pepchik en ny klass av SA-chiffer, som består av S-boxar och affina funktioner [10] . Enligt en studie av Adi Shamir och Alex Biryukov beror attacker på SA-chiffer inte på egenskaperna hos en viss S-box [11] . Därefter introducerades XSL-chifferet för klassen SA i artikeln, som beskriver strukturen för ett typiskt blockchiffer för vilket metoden kan tillämpas.

Krypteringsstrukturen består av rundor:

  1. i omgången utförs en klartextoperation med sessionsnyckeln
  2. Resultatet är uppdelat i block för bitar. Varje sådant block matas parallellt med ingången av ett antal B av bijektiva S-block.
  3. applicera sedan ett linjärt spridningsskikt .
  4. tillämpa operationen på nästa sessionsnyckel
  5. om vi bryter slingan, annars går vi till nästa iteration genom och återgår till steg .

Matematiska grunder

S-rutorna i Rijndael- och Serpent -chiffrorna kan representeras som en funktion av många höggradsvariabler [12] , Courtois metod sänker graden av funktionen till något tal , där den vanligtvis väljs till 2, genom att expandera argumentutrymme. Av särskilt intresse är antalet sådana funktioner . Om , sådana ekvationer beskriver S-blocket tillräckligt. Om , då säger vi att systemet är omdefinierat.

Det finns två typer av XSL-attacker. Den första (allmänna) fungerar på XSL-chiffer, oavsett nyckelschemaalgoritm (se nyckelschema ). Då kräver algoritmen lika många chiffertexter som det finns S-rutor inuti chifferet. Den andra versionen av XSL-attacken tar hänsyn till att nyckelschemaläggningsalgoritmen är känd och kräver därför endast en chiffertext [13] .

Algoritm för den första XSL-attacken

Varje omgång av S-blocket skrivs som en ekvation:

där är ingångsbitarna för den -: e S-boxen, är utmatningsbitarna för den -: e S-rutan.

Därefter väljs den kritiska attackparametern . Under attacken kommer ekvationen för varje S-box att multipliceras med alla möjliga monomialer av delmängden av de återstående S-boxarna. Dessutom, när man ändrar antalet rundor av chiffer, bör parametern inte öka mycket, som experimenten från Courtois och Pepshik visade [14] .

Därefter, för att hitta ett system för vilket det finns en unik lösning, skrivs en ny ekvation:

Syftet med alla dessa transformationer är att föra ekvationssystemet till ett linjärt överbestämt system där det inte finns några uppenbara linjärt beroende ekvationer.

Yttrande från det vetenskapliga samfundet

Metoden med algebraiska attacker verkade lovande för kryptoanalys, eftersom den inte krävde ett stort antal chiffertexter i teorin och erbjöd brytningen av den mest använda krypteringsstandarden (AES). Under de senaste fem åren har mycket forskning publicerats om prestandan för XSL-attacker.

Så i arbetet av Carlos Cid (Carlos Cid) och G. Lauren (Ga¨etan Leurent) analyserades den andra versionen av XSL-attacken från den ursprungliga artikeln - kompakt XSL - på AES-128 [15] . Artikeln analyserade exempel där denna algoritm kollapsar i det så kallade T-blocket, som används för att utöka utrymmet för variabler. Forskare drog dock slutsatsen att XSL-metoden är det första försöket att hitta en sårbarhet i den strukturella delen av AES-chifferet.

Till exempel undersöker arbetet av Chu-Wee Lim och Khoongming Khoo [16] ett försök att bryta BES (Big Encryption System)-applikationen till AES. Denna förlängning översätter alla beräkningar till fältet , vilket följaktligen bör minska antalet operationer. Teoretiska beräkningar har dock visat att komplexiteten i algoritmen för BES-chifferet ökar. Svårighet för BES-varianter:

Det har visat sig att XSL-attacken inte är effektiv mot BES-chiffer.

Anteckningar

  1. ↑ Algebraic Cryptanalysis of the Data Encryption Standard, 2007 , s. 152-169.
  2. ↑ Vincent Rijman. Rijndael och andra blockchiffer . NESSIE forum (12-18-02 18:51).
  3. ↑ Nils Ferguson , Bruce Schneier . Praktisk kryptografi = Praktisk kryptografi: Designa och implementera säkra kryptografiska system. - M .  : Dialektik, 2004. - 432 sid. - 3000 exemplar.  — ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .
  4. ↑ En enkel algebraisk representation av Rijndael, 2001 , s. 1-9.
  5. ↑ Jacques Patarin. Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt'88  // Advances in Cryptology - CRYPT0' 95. - Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. - s. 248–261 . — ISBN 9783540602217 , 9783540447504 .
  6. ↑ Cryptographers' Track på RSA Conference (2001: San Francisco, Kalifornien). Ämnen inom kryptologi, CT-RSA 2001: Kryptografernas spår vid RSA-konferensen 2001, San Francisco, CA, USA, april 2001: förfaranden . - ISBN 3540418989 , 9783540418986, 2001020877.
  7. ↑ 1 2 3 Kryptanalys av blockchiffer med överdefinierade ekvationssystem, 2002 , pp. 2.
  8. ↑ Aviad Kipnis, Adi Shamir. Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization  // Advances in Cryptology - CRYPTO' 99. - Berlin, Heidelberg: Springer Berlin Heidelberg, 1999. - s. 19–30 . - ISBN 9783540663478 , 9783540484059 .
  9. ↑ Kryptanalys av blockchiffer med överdefinierade ekvationssystem, 2002 , s. 1-35.
  10. ↑ Kryptanalys av blockchiffer med överdefinierade ekvationssystem, 2002 , s. 3.
  11. ↑ Alex Biryukov, Adi Shamir. Strukturell krypteringsanalys av SASAS  // Journal of Cryptology. — 2010-06-08. - T. 23 , nej. 4 . — S. 505–518 . - ISSN 1432-1378 0933-2790, 1432-1378 . - doi : 10.1007/s00145-010-9062-1 .
  12. ↑ En enkel algebraisk representation av Rijndael, 2001 , s. 1-4.
  13. ↑ Kryptanalys av blockchiffer med överdefinierade ekvationssystem, 2002 , s. 6-8.
  14. ↑ Kryptanalys av blockchiffer med överdefinierade ekvationssystem, 2002 , s. 12.
  15. ↑ Internationell konferens om teorin och tillämpningen av kryptologi och informationssäkerhet (11:e: 2005: Madras, Indien). Framsteg inom kryptologi: ASIACRYPT 2005, 11:e internationella konferensen om teorin och tillämpningen av kryptologi och informationssäkerhet, Chennai, Indien, 4-8 december 2005: förfaranden . - Springer, 2005. - ISBN 9783540322672
  16. ↑ An Analysis of XSL Applied to BES, 2007 , pp. 7-13.

Litteratur