XSL útok

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 12. března 2017; kontroly vyžadují 19 úprav .

XSL útok ( angl. eXtended Sparse Linearization , algebraic attack) je metoda kryptografické analýzy založená na algebraických vlastnostech šifry . Metoda zahrnuje řešení speciální soustavy rovnic .

Tuto metodu navrhli v roce 2001 Nicolas T. Courtois a Josef Pieprzyk.

XSL útoky byly dříve považovány za nemožné, ale 26. května 2006 Courtois demonstroval možnost XSL útoku proti jedinému modelu šifry podobné struktuře jako šifra AES [1] .

Jak řekl jeden z tvůrců Rijndaelovy šifry v soukromé korespondenci: "XSL není útok, je to jen sen." "Tento sen se může změnit v noční můru," odpověděl Nicolas Courtois [2] .

Pokud XSL útoky opravdu fungují, prolomí všechny aktuálně existující šifry. Pouze čistá náhoda může zachránit šifru před prolomením. Na druhou stranu je docela dobře možné (a z našeho pohledu nejspíše), že XSL útoky nejsou v praxi použitelné, nebo jsou aplikovatelné jen na malý počet vysoce strukturovaných šifer.

— Nils Ferguson , Bruce Schneier Practical Cryptography [3]

Historie vytvoření

V roce 2001 Niels Ferguson , Richard Schroeppel a D. Whiting publikovali článek [4] , ve kterém byli schopni znázornit Rijndaelovu šifru jako algebraický vzorec pomocí reprezentací lineárních částí šifry a nelineárních S-boxů v ve formě rovnic vyššího řádu. Došli k závěru, že všechny symetrické blokové šifry lze redukovat na vícerozměrnou rovnici v nějakém konečném poli . Také přemýšleli, zda by znalost algebraické formy pomohla prolomit šifru . Pokud funkce vyjadřující S-boxy nebere v úvahu argumenty s mocninou -1, pak se šifra stane afinní a lze ji snadno prolomit jinými způsoby, které nevyžadují linearizaci . Pokud tyto argumenty přirovnáme k , pak se rovnice ukáže jako polynomiálně složitá. $1/x$ $x^{254}$

V těchto letech se objevilo mnoho útoků na veřejné klíče: útok na systém Matsumoto-Imai [5] , útok na HFE [6] . Tyto útoky skončily úspěchem ihned po zjištění faktu (teoretického či experimentálního) o existenci dalších rovnic mnoha proměnných, které nejsou zřejmé a vývojáři původní šifry je neposkytli [7] .

Adi Shamir v roce 1998 ukázal, že kvadratické rovnice mnoha proměnných (MQ) jsou NP-úplný problém [8] . Jeho složitost výrazně klesá, když jsou rovnice předefinovány [7] . V první studii Nicolas Courtois a Jozef Pepshik ukazují, že výsledné MQ jsou řídké a mají pravidelnou strukturu [7] .

2. prosince 2002 na veletrhu ASIACRYPT-2002 Nicolas Courtois a Jozef Pepshik prezentovali článek „Kryptanalýza blokových šifer s předefinovanými soustavami rovnic“, kde poprvé představili dvě varianty metody útoku XSL [9] . Závěrem této práce je, že bezpečnost AES se opírá pouze o nemožnost v současné době vyřešit soustavu rovnic popisujících algebraickou strukturu šifry.

XSL šifra

Zobecněním třídy SP-šifer, které se skládají z S-boxů a permutačních funkcí bitů, Courtois a Pepchik určili novou třídu SA-šifer, která se skládá z S-boxů a afinních funkcí [10] . Podle studie Adi Shamira a Alexe Biryukova útoky na SA šifry nezávisí na vlastnostech konkrétního S-boxu [11] . Poté byla v článku představena XSL šifra třídy SA, která popisuje strukturu typické blokové šifry, pro kterou lze metodu aplikovat.

Struktura šifrování se skládá z kol: $N$

$X:$ v kole se pomocí klíče relace provede operace s prostým textem $i=1$ $XOR$ ${\displaystyle K_{i-1))$
$S:$ Výsledek je rozdělen do bloků po bitech. Každý takový blok je přiváděn paralelně ke vstupu určitého počtu B bijektivních S-bloků. $s$
$L:$ poté naneste lineární rozptylovou vrstvu.
$X:$ aplikujte operaci na klíč další relace $XOR$ $K_{i}$
pokud přerušíme smyčku, jinak přejdeme k další iteraci a vrátíme se ke kroku . $i=N$ $i$ $S$

Matematické základy

S-boxy šifer Rijndael a Serpent mohou být reprezentovány jako nějaká funkce mnoha vysokostupňových proměnných [12] , Courtoisova metoda snižuje stupeň funkce na nějaké číslo , kde se obvykle volí 2, rozšířením argumentační prostor. Zvláště zajímavý je počet takových funkcí . Jestliže , takové rovnice dostatečně popisují S-blok. Pokud , pak říkáme, že systém je předefinován. $d$ $d$ $r$ $r=s$ $r>>s$

Existují dva typy útoků XSL. První (obecná) pracuje na šifrách XSL, bez ohledu na algoritmus rozvrhu klíčů (viz rozvrh klíčů ). Algoritmus pak vyžaduje tolik šifrových textů, kolik je S-boxů uvnitř šifry. Druhá verze XSL útoku bere v úvahu, že je znám algoritmus pro plánování klíčů, a proto vyžaduje pouze jeden šifrovaný text [13] .

Algoritmus pro první útok XSL

Každé kolo S-bloku je zapsáno jako rovnice:

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

kde jsou vstupní bity -tého S-boxu, jsou výstupní bity -tého S-boxu. $X_{{ij}}$ $i$ $Y_{ik}$ $i$

Dále je vybrán parametr kritického útoku . Během útoku bude rovnice každého S-boxu vynásobena všemi možnými monomiály podmnožiny zbývajících S-boxů. Navíc při změně počtu kol šifry by se parametr neměl příliš zvyšovat, jak ukázaly experimenty Courtoise a Pepshika [14] . $P\in \mathbb {N}$ $(P-1)$ $P$

Dále, abychom našli systém, pro který existuje jedinečné řešení, je napsána nová rovnice:

$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}\součet \alpha _{j}Y''_{i-1,j}=...$

Účelem všech těchto transformací je přivést soustavu rovnic k lineárnímu předurčenému systému, ve kterém nejsou žádné zjevné lineárně závislé rovnice.

Názor vědecké komunity

Metoda algebraických útoků se jevila jako slibná pro kryptoanalýzu, protože teoreticky nevyžadovala velké množství šifrových textů a nabízela prolomení nejpoužívanějšího šifrovacího standardu (AES). Za posledních pět let bylo publikováno mnoho výzkumů o výkonu XSL útoků.

Takže v práci Carlose Cida (Carlos Cid) a G. Laurena (Ga¨etan Leurent) byla analyzována druhá verze XSL útoku z původního článku - kompaktní XSL - na AES-128 [15] . Článek analyzoval příklady, kdy tento algoritmus kolabuje v tzv. T-bloku, který se používá k rozšíření prostoru proměnných. Vědci však dospěli k závěru, že přístup XSL je prvním pokusem najít zranitelnost ve strukturální části šifry AES.

Například práce Chu-Wee Lim a Khoongming Khoo [16] zkoumá pokus prolomit aplikaci BES (Big Encryption System) na AES. Toto rozšíření převádí všechny výpočty do pole , což by mělo snížit počet operací. Teoretické výpočty však ukázaly, že se zvyšuje složitost algoritmu pro šifru BES. Obtížnost pro varianty BES: ${GF_{256}}$

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

Bylo zjištěno, že útok XSL není účinný proti šifrám BES.

Poznámky

↑ Algebraická kryptoanalýza standardu pro šifrování dat, 2007 , s. 152-169.
↑ Vincent Rijman. Rijndael a další blokové šifry . Fórum NESSIE (18. 12. 2002 18:51). (neurčitý)
↑ Nils Ferguson , Bruce Schneier . Praktická kryptografie = Praktická kryptografie: Navrhování a implementace bezpečných kryptografických systémů. - M . : Dialektika, 2004. - 432 s. - 3000 výtisků. — ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .
↑ Jednoduchá algebraická reprezentace Rijndaela, 2001 , pp. 1-9.
↑ 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 .
↑ Cryptografers' Track na konferenci RSA (2001: San Francisco, Kalifornie). Témata kryptologie, CT-RSA 2001: The Cryptographers' Track at RSA Conference 2001, San Francisco, CA, USA, duben 2001: sborník . - ISBN 3540418989 , 9783540418986, 2001020877.
↑ 1 2 3 Kryptoanalýza blokových šifer s předefinovanými soustavami rovnic, 2002 , str. 2.
↑ Aviad Kipnis, Adi Shamir. Kryptoanalýza kryptosystému HFE veřejného klíče pomocí relinearizace // Pokroky v kryptologii - CRYPTO' 99. - Berlin, Heidelberg: Springer Berlin Heidelberg, 1999. - s. 19–30 . - ISBN 9783540663478 , 9783540484059 .
↑ Kryptoanalýza blokových šifer s předefinovanými soustavami rovnic, 2002 , str. 1-35.
↑ Kryptoanalýza blokových šifer s předefinovanými soustavami rovnic, 2002 , str. 3.
↑ Alex Biryukov, Adi Shamir. Strukturální kryptoanalýza SASAS // Journal of Cryptology. — 2010-06-08. - T. 23 , č.p. 4 . — S. 505–518 . - ISSN 1432-1378 0933-2790, 1432-1378 . - doi : 10.1007/s00145-010-9062-1 .
↑ Jednoduchá algebraická reprezentace Rijndaela, 2001 , pp. 1-4.
↑ Kryptoanalýza blokových šifer s předefinovanými soustavami rovnic, 2002 , str. 6-8.
↑ Kryptoanalýza blokových šifer s předefinovanými soustavami rovnic, 2002 , str. 12.
↑ Mezinárodní konference o teorii a aplikaci kryptologie a informační bezpečnosti (11.: 2005: Madras, Indie). Pokroky v kryptologii : ASIACRYPT 2005, 11. mezinárodní konference o teorii a aplikaci kryptologie a informační bezpečnosti, Chennai, Indie, 4.–8. prosince 2005: sborník . - Springer, 2005. - ISBN 9783540322672
↑ An Analysis of XSL Applied to BES, 2007 , pp. 7-13.

Literatura

Nicolas T. Courtois, Gregory V. Bard. Algebraická kryptoanalýza standardu šifrování dat // Kryptografie a kódování. - Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. - ISBN 9783540772712 .
Ferguson N., Schneier B. Praktická kryptografie. - 2005. - 424 s.
Nicolas T. Courtois a Josef Pieprzyk. Kryptoanalýza blokových šifer s předefinovanými soustavami rovnic . - Berlín, Heidelberg: Springer Berlin, 2002. - S. 1-35 .
Chu-Wee Lim, Khoongming Khoo. Analýza XSL aplikovaná na BES // Rychlé softwarové šifrování. - 2007. - S. 13 . Archivováno z originálu 3. března 2016.
Niels Ferguson, Richard Schroeppel, Doug Whiting. Jednoduchá algebraická reprezentace Rijndaela // Vybrané oblasti v kryptografii. — Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. — s. 103–111 . - ISBN 9783540430667 , 9783540455370 .