XSL támadás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2017. március 12-én felülvizsgált verziótól ; az ellenőrzések 19 szerkesztést igényelnek .

Az XSL-támadás ( eng. eXtended Sparse Linearization , algebraic attack) a titkosítás algebrai tulajdonságain alapuló kriptográfiai elemzési módszer . A módszer egy speciális egyenletrendszer megoldását foglalja magában .

Ezt a módszert 2001-ben Nicolas T. Courtois és Josef Pieprzyk javasolta.

Az XSL-támadásokat korábban lehetetlennek tartották, de 2006. május 26-án Courtois bemutatta az XSL-támadás lehetőségét egyetlen, az AES -rejtjelhez hasonló szerkezetű titkosítási modell ellen [1] .

Ahogy a Rijndael titkosítás egyik megalkotója magánlevelezésben mondta: "Az XSL nem támadás, csak álom." "Ez az álom rémálommá változhat" - válaszolta Nicolas Courtois [2] .

Ha az XSL támadások valóban működnek, feltörik az összes jelenleg létező titkosítást. Csak a puszta véletlen mentheti meg a rejtjelet a feltöréstől. Másrészt nagyon is lehetséges (és a mi szempontunkból a legvalószínűbb), hogy az XSL támadások nem alkalmazhatók a gyakorlatban, vagy csak kis számú erősen strukturált titkosításra alkalmazhatók.

– Nils Ferguson , Bruce Schneier gyakorlati kriptográfia [3]

Létrehozási előzmények

2001-ben Niels Ferguson , Richard Schroeppel és D. Whiting publikált egy cikket [4] , amelyben a Rijndael-rejtjelet algebrai képletként tudták ábrázolni a rejtjel lineáris részeinek és a nemlineáris S-dobozoknak a reprezentációival. magasabb rendű egyenletek formájában. Arra a következtetésre jutottak, hogy minden szimmetrikus blokk-rejtjel többdimenziós egyenletté redukálható valamilyen véges mezőn . Arra is gondoltak, hogy az algebrai forma ismerete segít-e feltörni a titkosítást . Ha az S-boxokat kifejező függvény nem veszi figyelembe az argumentumokat -1 erejéig, akkor a titkosítás affinná válik , és könnyen feltörhető más, linearizálást nem igénylő módon . Ha ezeket az argumentumokat egyenlővé tesszük a -val , akkor az egyenlet polinomiálisan összetettnek bizonyul. $1/x$ $x^{254}$

Ezekben az években számos nyilvános kulcs elleni támadás jelent meg: támadás a Matsumoto-Imai rendszer ellen [5] , támadás a HFE ellen [6] . Ezek a támadások azonnal sikerrel zárultak, miután felfedezték a tényt (elméleti vagy kísérleti) a számos változóból álló további egyenlet létezésének tényéről, amelyek nem nyilvánvalóak, és amelyeket az eredeti titkosítás fejlesztői nem biztosítottak [7] .

Adi Shamir 1998-ban kimutatta, hogy a sok változó másodfokú egyenlete (MQ) NP-teljes probléma [8] . Komplexitása jelentősen csökken az egyenletek újradefiniálásakor [7] . Az első tanulmányban Nicolas Courtois és Jozef Pepshik kimutatták, hogy a kapott MQ-k ritkák és szabályos szerkezetűek [7] .

2002. december 2-án az ASIACRYPT-2002 kiállításon Nicolas Courtois és Jozef Pepshik bemutatták a "Túldefiniált egyenletrendszerű blokkrejtjelek kriptanalízise" című cikket, ahol először mutatták be az XSL támadási módszer két változatát [9] . A munka következtetése az, hogy az AES biztonsága csak azon múlik, hogy pillanatnyilag lehetetlen megoldani a rejtjel algebrai szerkezetét leíró egyenletrendszert.

XSL titkosítás

Az S-boxokból és a bitfüggvények permutációjából álló SP-rejtjelek osztályát általánosítva Courtois és Pepchik az SA-rejtjelek új osztályát jelölte ki, amely S-boxokból és affin függvényekből áll [10] . Adi Shamir és Alex Biryukov tanulmánya szerint az SA-rejtjelek elleni támadások nem egy adott S-box tulajdonságaitól függenek [11] . Ezt követően a cikkben bemutatásra került az SA osztály XSL titkosítása, amely egy tipikus blokk titkosítás felépítését írja le, amelyre a metódus alkalmazható.

A titkosítási struktúra körökből áll: $N$

$X:$ fordulóban egy egyszerű szöveges műveletet hajtanak végre a session kulccsal $i=1$ $XOR$ ${\displaystyle K_{i-1))$
$S:$ Az eredményt bitekkel blokkokra osztjuk . Minden ilyen blokk párhuzamosan van táplálva néhány B számú bijektív S-blokk bemenetével. $s$
$L:$ majd alkalmazzunk egy lineáris szóróréteget .
$X:$ alkalmazza a műveletet a következő szekciókulcsra $XOR$ $K_{i}$
ha megszakítjuk a hurkot, ellenkező esetben a következő iterációra lépünk, és visszatérünk a lépéshez . $i=N$ $én$ $S$

Matematikai alapok

A Rijndael és a Serpent titkosítások S-dobozai számos nagyfokú változó valamilyen függvényeként ábrázolhatók [12] , Courtois módszere a függvény mértékét valamilyen számra csökkenti , ahol általában 2-nek választják, a érvtér. Különösen érdekes az ilyen funkciók száma . Ha , az ilyen egyenletek kellően leírják az S-blokkot. Ha , akkor azt mondjuk, hogy a rendszer újradefiniált. $d$ $d$ $r$ $r=s$ $r>>s$

Kétféle XSL-támadás létezik. Az első (általános) XSL titkosításokon működik, függetlenül a kulcsütemezési algoritmustól (lásd a kulcsütemezést ). Ekkor az algoritmusnak annyi rejtjelezett szövegre van szüksége, ahány S-doboz van a rejtjelen belül. Az XSL támadás második verziója figyelembe veszi, hogy a kulcsütemezési algoritmus ismert, ezért csak egy rejtjelezett szöveget igényel [13] .

Algoritmus az első XSL-támadáshoz

Az S-blokk minden köre egyenletként van felírva:

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

ahol a -edik S-box bemeneti bitjei, a -edik S-box kimeneti bitjei . $X_{{ij}}$ $én$ $Y_{ik}$ $én$

Ezután a kritikus támadási paraméter kerül kiválasztásra . A támadás során az egyes S-boxok egyenlete megszorozódik a fennmaradó S-dobozok részhalmazának összes lehetséges monomijával. Ráadásul a rejtjelezési körök számának megváltoztatásakor a paraméternek nem szabad sokat növekednie, amint azt Courtois és Pepshik kísérletei mutatták [14] . $P\in \mathbb {N}$ $(P-1)$ $P$

Ezután egy olyan rendszer megtalálásához, amelyre egyedi megoldás van, egy új egyenletet írunk fel:

$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}=...$

Mindezen transzformációk célja, hogy az egyenletrendszert olyan lineárisan túldefiniált rendszerré hozzuk, amelyben nincsenek nyilvánvaló lineárisan függő egyenletek.

A tudományos közösség véleménye

Az algebrai támadások módszere ígéretesnek tűnt a kriptoanalízis számára, mivel elméletileg nem igényelt nagyszámú rejtjelezett szöveget , és a leggyakrabban használt titkosítási szabvány (AES) feltörését kínálta. Az elmúlt öt évben sok kutatás jelent meg az XSL-támadások teljesítményéről.

Tehát Carlos Cid (Carlos Cid) és G. Lauren (Ga¨etan Leurent) munkájában az XSL támadás második változatát elemezték az eredeti cikkből - a kompakt XSL - az AES-128-on [15] . A cikk olyan példákat elemzett, amelyekben ez az algoritmus összeomlik az úgynevezett T-blokkban, amely a változók terének bővítésére szolgál. A tudósok azonban arra a következtetésre jutottak, hogy az XSL-megközelítés az első kísérlet az AES-rejtjel szerkezeti részének sebezhetőségére.

Például Chu-Wee Lim és Khoongming Khoo [16] munkája a BES (Big Encryption System) alkalmazás AES -re törésére irányuló kísérletet vizsgál . Ez a kiterjesztés az összes számítást a mezőbe fordítja , ami ennek megfelelően csökkenti a műveletek számát. Az elméleti számítások azonban azt mutatták, hogy a BES-rejtjel algoritmusának bonyolultsága növekszik. A BES-változatok nehézségei: ${GF_{256}}$

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

Azt találták, hogy az XSL-támadás nem hatékony a BES-rejtjelekkel szemben.

Jegyzetek

↑ Algebraic Cryptanalysis of the Data Encryption Standard, 2007 , pp. 152-169.
↑ Vincent Rijman. Rijndael és más blokk titkosítások . NESSIE fórum (12-18-02 18:51). (határozatlan)
↑ Nils Ferguson , Bruce Schneier . Gyakorlati kriptográfia = Gyakorlati kriptográfia: Biztonságos kriptográfiai rendszerek tervezése és megvalósítása. - M . : Dialektika, 2004. - 432 p. - 3000 példányban. — ISBN 5-8459-0733-0 , ISBN 0-4712-2357-3 .
↑ A Simple Algebraic Representation of Rijndael, 2001 , pp. 1-9.
↑ Jacques Patarin. Az Eurocrypt'88 Matsumoto és Imai nyilvános kulcsú sémájának kriptoanalízise // Advances in Cryptology - CRYPT0' 95. - Berlin, Heidelberg: Springer Berlin Heidelberg, 1995. - 248–261 . — ISBN 9783540602217 , 9783540447504 .
↑ Cryptographers' Track az RSA konferencián (2001: San Francisco, Kalifornia). Kriptológiai témák, CT-RSA 2001: a kriptográfusok pályája az RSA konferencián 2001, San Francisco, CA, USA, 2001. április: kiadványok . - ISBN 3540418989 , 9783540418986, 2001020877.
↑ 1 2 3 Túldefiniált egyenletrendszerű blokkrejtjelek kriptoanalízise, 2002 , pp. 2.
↑ Aviad Kipnis, Adi Shamir. A HFE nyilvános kulcsú kriptorendszerének kriptoanalízise újralinearizálással // Advances in Cryptology - CRYPTO' 99. - Berlin, Heidelberg: Springer Berlin Heidelberg, 1999. - 19–30 . - ISBN 9783540663478 , 9783540484059 .
↑ Túldefiniált egyenletrendszerű blokkrejtjelek kriptanalízise, 2002 , pp. 1-35.
↑ Túldefiniált egyenletrendszerű blokkrejtjelek kriptanalízise, 2002 , pp. 3.
↑ Alex Biryukov, Adi Shamir. A SASAS szerkezeti kriptanalízise // Journal of Cryptology. — 2010-06-08. - T. 23 , sz. 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.
↑ Túldefiniált egyenletrendszerű blokkrejtjelek kriptanalízise, 2002 , pp. 6-8.
↑ Túldefiniált egyenletrendszerű blokkrejtjelek kriptanalízise, 2002 , pp. 12.
↑ Nemzetközi konferencia a kriptológia és információbiztonság elméletéről és alkalmazásáról (11.: 2005: Madras, India). Fejlődés a kriptológiában: ASIACRYPT 2005, 11. nemzetközi konferencia a kriptológia és információbiztonság elméletéről és alkalmazásáról, Chennai, India, 2005. december 4-8.: kiadványok . - Springer, 2005. - ISBN 9783540322672
↑ An Analysis of XSL Applied to BES, 2007 , pp. 7-13.

Irodalom

Nicolas T. Courtois, Gregory V. Bard. Az adattitkosítási szabvány algebrai kriptoanalízise // Kriptográfia és kódolás. - Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. - ISBN 9783540772712 .
Ferguson N., Schneier B. Gyakorlati titkosítás. - 2005. - 424 p.
Nicolas T. Courtois és Josef Pieprzyk. Túldefiniált egyenletrendszerű blokkrejtjelek kriptoanalízise . - Berlin, Heidelberg: Springer Berlin, 2002. - S. 1-35 .
Chu-Wee Lim, Khoongming Khoo. A BES-re alkalmazott XSL elemzése // Gyors szoftveres titkosítás. - 2007. - S. 13 . Az eredetiből archiválva: 2016. március 3.
Niels Ferguson, Richard Schroeppel, Doug Whiting. Rijndael egyszerű algebrai ábrázolása // Selected Areas in Cryptography. – Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. – 103–111 . - ISBN 9783540430667 , 9783540455370 .