XSL-hyökkäys

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 12. maaliskuuta 2017 tarkistetusta versiosta . tarkastukset vaativat 19 muokkausta .

XSL-hyökkäys ( eng. eXtended Sparse Linearization , algebraic attack) on salausanalyysimenetelmä , joka perustuu salauksen algebrallisiin ominaisuuksiin . Menetelmä sisältää erityisen yhtälöjärjestelmän ratkaisemisen .

Tätä menetelmää ehdottivat vuonna 2001 Nicolas T. Courtois ja Josef Pieprzyk.

XSL-hyökkäyksiä pidettiin aiemmin mahdottomina, mutta 26. toukokuuta 2006 Courtois osoitti XSL-hyökkäyksen mahdollisuuden yhtä salausmallia vastaan, joka on rakenteeltaan samanlainen kuin AES -salauksen [1] .

Kuten yksi Rijndael -salauksen luojista sanoi yksityisessä kirjeenvaihdossa: "XSL ei ole hyökkäys, se on vain unta." "Tämä unelma voi muuttua painajaiseksi", vastasi Nicolas Courtois [2] .

Jos XSL-hyökkäykset todella toimivat, ne rikkovat kaikki nykyiset salaukset. Vain puhdas sattuma voi pelastaa salauksen rikkoutumasta. Toisaalta on täysin mahdollista (ja meidän näkökulmastamme todennäköisimmin), että XSL-hyökkäykset eivät sovellu käytännössä tai ne ovat sovellettavissa vain pieneen määrään erittäin jäsenneltyjä salauksia.

— Nils Ferguson , Bruce Schneier käytännön kryptografia [3]

Luontihistoria

Vuonna 2001 Niels Ferguson , Richard Schroeppel ja D. Whiting julkaisivat artikkelin [4] , jossa he pystyivät esittämään Rijndaelin salauksen algebrallisena kaavana käyttämällä salauksen lineaaristen osien ja epälineaaristen S-laatikoiden esityksiä . korkeamman asteen yhtälöiden muodossa. He päättelivät, että kaikki symmetriset lohkosalaukset voidaan pelkistää moniulotteiseksi yhtälöksi jonkin äärellisen kentän yli . He myös ihmettelivät, auttaisiko algebrallisen muodon tunteminen murtamaan salauksen . Jos S-laatikoita ilmaiseva funktio ei ota huomioon argumentteja -1:n potenssiin asti, salauksesta tulee affiine ja se särkyy helposti muilla tavoilla, jotka eivät vaadi linearisointia . Jos rinnastamme nämä argumentit :een , yhtälö osoittautuu polynomiaalisesti monimutkaiseksi. $1/x$ $x^{254}$

Noina vuosina ilmestyi monia hyökkäyksiä julkisiin avaimiin: hyökkäys Matsumoto-Imai-järjestelmää vastaan [5] , hyökkäys HFE :tä vastaan [6] . Nämä hyökkäykset päättyivät menestykseen heti sen jälkeen, kun havaittiin tosiasia (teoreettinen tai kokeellinen) monien muuttujien lisäyhtälöiden olemassaolosta, jotka eivät ole ilmeisiä ja joita alkuperäisen salauksen kehittäjät eivät toimittaneet [7] .

Adi Shamir vuonna 1998 osoitti, että monien muuttujien toisen asteen yhtälöt (MQ) ovat NP-täydellinen ongelma [8] . Sen monimutkaisuus pienenee huomattavasti, kun yhtälöt määritellään uudelleen [7] . Ensimmäisessä tutkimuksessa Nicolas Courtois ja Jozef Pepshik osoittavat, että tuloksena saadut MQ:t ovat harvassa ja niillä on säännöllinen rakenne [7] .

Joulukuun 2. päivänä 2002 ASIACRYPT-2002:ssa Nicolas Courtois ja Jozef Pepshik esittelivät artikkelin "Cryptanalysis of block crypts with overdefined systems of equication", jossa he esittelivät ensimmäisen kerran kaksi muunnelmaa XSL-hyökkäysmenetelmästä [9] . Tämän työn johtopäätös on, että AES:n turvallisuus perustuu vain siihen, että salauksen algebrallista rakennetta kuvaavaa yhtälöjärjestelmää ei tällä hetkellä ole mahdollista ratkaista.

XSL-salaus

Yleistäen SP-salausten luokan, joka koostuu S-laatikoista ja bittifunktioiden permutaatiosta, Courtois ja Pepchik määrittelivät uuden SA-salauksen luokan, joka koostuu S-laatikoista ja affiinisista funktioista [10] . Adi Shamirin ja Alex Biryukovin tutkimuksen mukaan SA-salauksiin kohdistuvat hyökkäykset eivät riipu tietyn S-boxin ominaisuuksista [11] . Tämän jälkeen artikkelissa esiteltiin luokan SA XSL-salaus, joka kuvaa tyypillisen lohkosalauksen rakennetta, johon menetelmää voidaan soveltaa.

Salausrakenne koostuu kierroksista: $N$

$X:$ kierroksella , selkätekstitoiminto suoritetaan istuntoavaimella $i=1$ $XOR$ ${\displaystyle K_{i-1))$
$S:$ Tulos jaetaan lohkoihin bittien mukaan. Jokainen tällainen lohko syötetään rinnakkain bijektiivisten S-lohkojen B-luvun tulon kanssa. $s$
${\näyttötyyli L:}$ levitä sitten lineaarinen sirontakerros .
$X:$ Käytä toimintoa seuraavaan istuntoavaimeen $XOR$ $K_{i}$
jos katkaisemme silmukan, muussa tapauksessa siirrymme seuraavaan iteraatioon ja palaamme vaiheeseen . $i=N$ $i$ $S$

Matemaattiset perusteet

Rijndael- ja Serpent -salauksen S-laatikot voidaan esittää useiden korkean asteen muuttujien funktiona [12] , Courtois'n menetelmä alentaa funktion astetta johonkin numeroon , missä se yleensä valitaan 2:ksi laajentamalla argumentti tilaa. Erityisen kiinnostavaa on tällaisten toimintojen määrä . Jos , sellaiset yhtälöt kuvaavat riittävästi S-lohkoa. Jos , niin sanomme, että järjestelmä on määritelty uudelleen. $d$ $d$ $r$ $r=s$ $r>>s$

XSL-hyökkäyksiä on kahdenlaisia. Ensimmäinen (yleinen) toimii XSL-salauksilla riippumatta avainaikataulun algoritmista (katso avainaikataulu ). Tällöin algoritmi vaatii niin monta salatekstiä kuin on S-laatikoita salauksen sisällä. XSL-hyökkäyksen toinen versio ottaa huomioon, että avaimen ajoitusalgoritmi tunnetaan ja vaatii siksi vain yhden salatekstin [13] .

Ensimmäisen XSL-hyökkäyksen algoritmi

Jokainen S-lohkon kierros kirjoitetaan yhtälöksi:

${\displaystyle \sum _{i,j}\alpha _{ijk}*X_{ij}*Y_{jk}+\sum _{i,j}\beta _{ij}*X_{ij} +\summa _{i,j}\gamma _{ij}*Y_{ij}+\delta =0}$

missä ovat -: nnen S-laatikon tulobitit, ovat -: nnen S-laatikon lähtöbitit . $X_{{ij}}$ $i$ $Y_{ik}$ $i$

Seuraavaksi valitaan kriittinen hyökkäysparametri . Hyökkäyksen aikana kunkin S-laatikon yhtälö kerrotaan jäljellä olevien S-laatikoiden osajoukon kaikilla mahdollisilla monomiaaleilla. Lisäksi salauksen kierrosten lukumäärää muutettaessa parametrin ei pitäisi kasvaa paljon, kuten Courtois'n ja Pepshikin kokeet osoittivat [14] . $P\in \mathbb {N}$ ${\näyttötyyli (P-1)}$ $P$

Seuraavaksi järjestelmän löytämiseksi, jolle on ainutlaatuinen ratkaisu, kirjoitetaan uusi yhtälö:

$X_{i,j}\bigoplus \sum \alpha _{j}Y_{i-1,j}=X'_{i,j}\bigoplus \sum \alpha _{j}Y'{i -1,j}=X''_{i,j}\sum \alpha _{j}Y''_{i-1,j}=...$

Kaikkien näiden muunnosten tarkoituksena on saattaa yhtälöjärjestelmä lineaariseen ylimäärättyyn järjestelmään, jossa ei ole ilmeisiä lineaarisesti riippuvia yhtälöitä.

Tiedeyhteisön mielipide

Algebrallisten hyökkäysten menetelmä vaikutti lupaavalta kryptausanalyysille, koska se ei teoriassa vaatinut suurta määrää salatekstejä ja tarjosi eniten käytetyn salausstandardin (AES) rikkomisen. Viimeisten viiden vuoden aikana on julkaistu paljon tutkimuksia XSL-hyökkäysten suorituskyvystä.

Joten Carlos Cidin (Carlos Cid) ja G. Laurenin (Ga¨etan Leurent) työssä analysoitiin XSL-hyökkäyksen toinen versio alkuperäisestä artikkelista - kompakti XSL - AES-128:lla [15] . Artikkelissa analysoitiin esimerkkejä, joissa tämä algoritmi romahtaa ns. T-lohkossa, jota käytetään laajentamaan muuttujien tilaa. Tutkijat päättelivät kuitenkin, että XSL-lähestymistapa on ensimmäinen yritys löytää haavoittuvuus AES-salauksen rakenteellisessa osassa.

Esimerkiksi Chu-Wee Limin ja Khoongming Khoo [16] työ tutkii yritystä murtaa BES (Big Encryption System) -sovellus AES:ään. Tämä laajennus kääntää kaikki laskelmat kenttään , jonka pitäisi vastaavasti vähentää toimintojen määrää. Teoreettiset laskelmat ovat kuitenkin osoittaneet, että BES-salauksen algoritmin monimutkaisuus kasvaa. Vaikeus BES-versioille: ${GF_{256}}$

BES-128: $\noin 2^{401}$
BES-192: $\noin 2^{622}$
BES-256: $\noin 2^{691}$

On havaittu, että XSL-hyökkäys ei ole tehokas BES-salauksia vastaan.

Muistiinpanot

↑ Algebraic Cryptanalysis of the Data Encryption Standard, 2007 , pp. 152-169.
↑ Vincent Rijman. Rijndael ja muut lohkosalaukset . NESSIE-foorumi (12.18.2002 18:51). (määrätön)
↑ Nils Ferguson , Bruce Schneier . Käytännön kryptografia = Käytännön kryptografia: Turvallisten kryptografisten järjestelmien suunnittelu ja toteutus. - M . : Dialektiikka, 2004. - 432 s. - 3000 kappaletta. — ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .
↑ A Simple Algebraic Representation of Rijndael, 2001 , pp. 1-9.
↑ Jacques Patarin. Eurocrypt'88:n Matsumoton ja Imai julkisen avaimen kaavion krypta-analyysi // Advances in Cryptology - CRYPT0' 95. - Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. - s. 248–261 . — ISBN 9783540602217 , 9783540447504 .
↑ Cryptographers' Track RSA-konferenssissa (2001: San Francisco, Kalifornia). Kryptologian aiheet, CT-RSA 2001: Cryptographers' Track at RSA Conference 2001, San Francisco, CA, USA, huhtikuu 2001: julkaisut . - ISBN 3540418989 , 9783540418986, 2001020877.
↑ 1 2 3 Lohkosalausten kryptaanalyysi ylimääritellyillä yhtälöjärjestelmillä, 2002 , s. 2.
↑ Aviad Kipnis, Adi Shamir. HFE:n julkisen avaimen kryptosysteemin kryptoanalyysi uudelleenlinearisoinnilla // Advances in Cryptology - CRYPTO' 99. - Berlin, Heidelberg: Springer Berlin Heidelberg, 1999. - s. 19–30 . - ISBN 9783540663478 , 9783540484059 .
↑ Lohkosalausten kryptaanalyysi ylimääritellyillä yhtälöjärjestelmillä, 2002 , pp. 1-35.
↑ Lohkosalausten kryptaanalyysi ylimääritellyillä yhtälöjärjestelmillä, 2002 , pp. 3.
↑ Alex Biryukov, Adi Shamir. SASASin rakenteellinen kryptaanalyysi // Journal of Cryptology. - 08-06-2010. - T. 23 , no. 4 . — S. 505–518 . - ISSN 1432-1378 0933-2790, 1432-1378 . - doi : 10.1007/s00145-010-9062-1 .
↑ A Simple Algebraic Representation of Rijndael, 2001 , pp. 1-4.
↑ Lohkosalausten kryptaanalyysi ylimääritellyillä yhtälöjärjestelmillä, 2002 , pp. 6-8.
↑ Lohkosalausten kryptaanalyysi ylimääritellyillä yhtälöjärjestelmillä, 2002 , pp. 12.
↑ Kansainvälinen konferenssi kryptologian ja tietoturvan teoriasta ja soveltamisesta (11.: 2005: Madras, Intia). Kryptologian edistysaskel: ASIACRYPT 2005, 11. kansainvälinen kryptologian ja tietoturvan teoria- ja soveltamiskonferenssi, Chennai, Intia, 4.-8. joulukuuta 2005: julkaisut . - Springer, 2005. - ISBN 9783540322672
↑ An Analysis of XSL Applied to BES, 2007 , pp. 7-13.

Kirjallisuus

Nicolas T. Courtois, Gregory V. Bard. Tietojen salausstandardin algebrallinen kryptaanalyysi // Salaus ja koodaus. - Berliini, Heidelberg: Springer Berlin Heidelberg, 2007. - ISBN 9783540772712 .
Ferguson N., Schneier B. Käytännön kryptografia. - 2005. - 424 s.
Nicolas T. Courtois ja Josef Pieprzyk. Lohkosalausten krypta-analyysi ylimääritellyillä yhtälöjärjestelmillä . - Berliini, Heidelberg: Springer Berlin, 2002. - S. 1-35 .
Chu-Wee Lim, Khoongming Khoo. BES:ään sovelletun XSL:n analyysi // Fast Software Encryption. - 2007. - S. 13 . Arkistoitu alkuperäisestä 3. maaliskuuta 2016.
Niels Ferguson, Richard Schroeppel, Doug Whiting. Rijndaelin yksinkertainen algebrallinen esitys // Valitut alueet kryptografiassa. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. — s. 103–111 . - ISBN 9783540430667 , 9783540455370 .