Teljes kétoldalú gráf támadása

A teljes bipartit gráf támadása ( angol. Biclique attack ) a "meeting in the middle" támadás egyik változata [1] . Ez a támadás teljes kétoldalú gráfstruktúrát használ, hogy növelje a középső támadási kísérletek számát . Mivel ez a támadás a „man-in-the-middle” támadáson alapul, a blokkrejtjelekre és a kriptográfiai hash-függvényekre egyaránt alkalmazható . Ez a támadás az AES [2] és az IDEA [3] titkosítások feltöréséről ismert , bár csak valamivel gyorsabb, mint a nyers erő . A támadás számítási összetettsége , illetve az AES128, AES192 és AES256 esetében. Mivel a számítási összetettség elméleti érték, ez azt jelenti, hogy az AES-t nem törték fel, és használata viszonylag biztonságos. Ezenkívül ez a támadás megkérdőjelezte az AES-ben használt töltények számának elegendőségét. $2^{126.1}$ $2^{189.7}$ $2^{254.4}$

Történelem

A középső támadást először Diffie és Hellman javasolta 1977-ben, miközben a DES algoritmus tulajdonságait tárgyalták . [4] Azt feltételezték, hogy a kulcs mérete túl kicsi, és a DES különböző kulcsokkal történő újrafelhasználása megoldást jelenthet a problémára. Azt javasolták azonban, hogy ne használjunk „kettős DES”-t, hanem azonnal használjunk legalább háromszoros DES -t az ember a középső támadás természete miatt. Amióta Diffie és Hellman javasolta az ember a középső támadást, számos változat létezik, amelyek használhatók, ha a klasszikus MITM nem alkalmazható. A teljes kétoldalú gráftámadás ötletét először Horatovich, Rekhberger és Savelyeva javasolta egy hash függvényeket használó változathoz. [5] Ezt követően Bogdanov, Horatovich és Rechberger közzétett egy támadást az AES ellen, amely megmutatta, hogyan alkalmazható a teljes kétoldalú gráf koncepciója egy blokkrejtjelet tartalmazó titkos kulcsra [6] .

A teljes kétrészes gráf

Man-in-the-middle támadásnál az első és második helyettesítő titkosításnak megfelelő kulcsbiteknek függetlennek kell lenniük egymástól, különben a nyílt szöveg és a titkosított szöveg egyező köztes értékei nem számíthatók ki egymástól függetlenül a man- középső támadás. Ezt a tulajdonságot gyakran nehéz kihasználni nagy számú körön keresztül, a megtámadott titkosítás terjedése miatt. $K_1$ $K_{2}$

Egyszerűen fogalmazva, minél több iterációt használnak a támadásban, annál nagyobb lesz a helyettesítő titkosítás „kimenete”, ami viszont a helyettesítő rejtjelek közötti független kulcsbitek számának csökkenéséhez vezet, amelyeket kimerítő kereséssel kell feltörni.

Ebben az esetben egy komplett bipartit gráf segít a probléma megoldásában. Például, ha 7 kört futtatunk egy proxytámadást AES-en, majd egy 3-as hosszúságú (a titkosítás 3 iterációját lefedő) teljes bipartit gráfot használunk, akkor lehetséges lesz a 7. iteráció elején lévő köztes állapot egyeztetése. az utolsó iteráció köztes állapotával (10-től, AES128 esetén) . Így a titkosítás minden köre ellen támadást érünk el, bár egy klasszikus „man-in-the-middle” támadásban ez nem biztos, hogy lehetséges.

A full bipartite graph támadás lényege egy hatékony teljes kétrészes gráf felépítése, amely a kulcsbitek függvényében illesztheti az aktuális köztes értéket a megfelelő rejtjelezett szöveggel. $K_1$ $K_{2}$

Teljes kétoldalú gráf felépítése

Ezt a módszert Bogdanov, Khovratovich és Rehberger javasolta a Biclique Cryptanalysis of the Full AES című művében.

Nem szabad elfelejteni , hogy a teljes kétrészes gráf fő funkciója az állapotok ) úgy, hogy) és a kulcsot (), a titkosított szöveget (Válasszon ki egy állapotot (Első lépés:Felépítés:: kulcsok segítségévelés rejtjelezett szövegek $S$ $C$ $K[i,j]$
$S_{0}$ $C_{0}$ $K[0,0]$ $S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}$ $f$

Második lépés: Két kulcskészlet van kiválasztva, mindegyik mérete , így: ${\2. megjelenítési stílus^{d))$

Az első billentyűkészlet azok a billentyűk, amelyek az alapvető számítások alapján kielégítik a függvény differenciálkövetelményeit : $f$ $0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}$
A második billentyűkészlet azok a billentyűk, amelyek az alapul szolgáló számítások alapján kielégítik a függvény differenciális követelményeit : $f$ $\nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K))}0$

Harmadik lépés: Vegye figyelembe, hogy , Könnyen belátható, hogy a sor is kielégíti mindkét különbséget. Bármelyik definícióba behelyettesítve megkapjuk a , hol és . Ez azt jelenti, hogy az alapul szolgáló számításokból kapott tuple XOR-ezhető is:
$0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K))}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K)) }\Delta _{i}$
$(S_{0},C_{0},K[0,0])$ $S_{0},C_{0}$ $K[0,0]$ $0{\xrightarrow[{f}]{0}}0$ $\Delta _{0}=0,\nabla _{0}=0$ $\Delta _{0}^{K}=0$
$S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j} ^{K}}}C_{0}\oplus \Delta _{i}$

Negyedik lépés: Könnyen belátható, hogy: Így van: Ami megegyezik a teljes kétrészes gráffüggvény fentebb bemutatott definíciójával:
${\displaystyle S_{j}=S_{0}\oplus \nabla _{j))$
${\displaystyle K[i,j]=K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K))$
${\displaystyle C_{i}=C_{0}\oplus \Delta _{i))$

$S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}$

$\forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}$

Így létre lehet hozni egy teljes kétrészes méretű gráfot ( , mivel az első halmaz kulcsait össze kell kapcsolni a második halmaz kulcsaival). Ez azt jelenti, hogy differenciálszámítások és és függvények segítségével méretgráfot lehet létrehozni . Ha a , akkor minden kulcs különbözik a teljes grafikonon. ${\displaystyle 2^{2d))$ ${\displaystyle 2^{2d))$ ${\2. megjelenítési stílus^{d))$ ${\2. megjelenítési stílus^{d))$ ${\displaystyle 2^{2d))$ ${\displaystyle 2*2^{d))$ $\Delta _{i}$ $\nabla _{j}$ $f$ ${\displaystyle \Delta _{i}\neq \nabla _{j))$ $i+j>0$ $K[i,j]$

Kriptográfiai támadáselemzés

1. A kriptoanalitikus az összes lehetséges kulcsot méretű kulcsok részhalmazaiba gyűjti , ahol valamilyen szám. A csoport kulcsát úgy jelöljük, mint a méretmátrixban . Ezután a kriptoanalizátor felosztja a rejtjelet két helyettesítő rejtjelre, és (olyan, hogy ), csakúgy, mint az ember a középső támadásnál. Az egyes helyettesítő rejtjelekhez tartozó kulcskészletek számossággal rendelkeznek , és jelölésük van . A két helyettesítési rejtjel kulcsának egyesítését a fenti mátrixban fejezzük ki . ${\displaystyle 2^{2d))$ $d$ $K[i,j]$ ${\displaystyle 2^{d}\times 2^{d))$ $f$ $g$ $E=f\circ g$ ${\2. megjelenítési stílus^{d))$ $K[i,0]$ $K[0,j]$ $K[i,j]$

2. A kriptoanalizátor minden kulcscsoporthoz komplett kétoldalú gráfot készít . A gráf dimenzióval rendelkezik , mivel a belső állapotokat, , titkosított szövegekre képezi le kulcsok segítségével. Ebben az esetben egy teljes kétrészes gráfot építünk fel a két kulcskészlet közötti különbségek alapján, és . ${\displaystyle 2^{2d))$ $d$ ${\2. megjelenítési stílus^{d))$ $S_j$ ${\2. megjelenítési stílus^{d))$ $C_{i}$ ${\displaystyle 2^{2d))$ $K[i,0]$ $K[0,j]$

3. A rejtjelelemző kiválasztja a lehetséges titkosított szövegeket, és lekéri a megfelelő nyílt szövegeket, . ${\2. megjelenítési stílus^{d))$ $C_{i}$ $P_{i}$

4. A támadó kiválaszt egy belső állapotot és a hozzá tartozó nyílt szöveget ( ) , és a és a segítségével végrehajt egy klasszikus man-in-the-middle támadást . $S_j$ $P_{i}$ $f$ $g$

5. Ha talál egy kulcsot, amely megegyezik a -val , akkor azt egy másik „belső állapot-titkosszöveg” párral szemben teszteljük. Ha a kulcs ezen a páron működik, akkor nagy valószínűséggel ez a helyes kulcs. $S_j$ $P_{i}$

Példa egy támadásra

Az alábbiakban egy példa látható az AES128 elleni támadásra. A támadás egy 7 fordulós mediátor támadásból áll, az utolsó 3 iterációban a teljes bipartit gráfot használják.

Kulcsmegosztás

A billentyűk csoportokra vannak osztva , mindegyik csoport kulcsokból áll. Minden csoport rendelkezik egy egyedi alapkulccsal , amelyet a számításhoz használnak. Ez a kulcs így néz ki: $2^{112}$ $2^{16}$ $K[0,0]$

{\begin{bmatrix}-&-&-&0\\0&-&-&-\\-&-&-&-\\-&-&-&-\end{bmátrix))

A fennmaradó 14 bájt (112 bit) szekvenciálisan kitöltésre kerül. Így egyedi alapkulcsokat kapunk; minden kulcscsoporthoz egyet. Általában az egyes csoportok kulcsait a csoport alapkulcsának megfelelően választják ki. Az alábbi 4 bájt közül csak 2 bájttal különböznek (akár -tól, akár -tól ): $2^{112}$
$2^{16}$ $én$ $j$

{\begin{bmatrix}-&-&i&i\\j&-&j&-\\-&-&-&-\\-&-&-&-\end{bmátrix))

Így kiderül és , ami összességében különböző kulcsokat ad, . $2^{8}K[i,0]$ $2^{8}K[0,j]$ $2^{16}$ $K[i,j]$

Grafikon felépítése

Egy komplett kétrészes gráf méretét a „Teljes kétrészes gráf készítése” részben leírtak szerint állítjuk össze. $2^{112}$

Brókertámadás

A grafikon felépítése után kezdődhet az ember a közepén támadás. A támadás megkezdése előtt a nyílt szövegből származó állapotok : , állapotok a rejtjelezett szövegből: , és a megfelelő állapotok és kulcskészletek vagy már ki vannak számítva. ${\2. megjelenítési stílus^{d))$
$P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}$
${\2. megjelenítési stílus^{d))$
${\xleftarrow[{v_{j}}]{}}{\xleftarrow[{}]{K[0,j]}}S_{j}$
$K[i,0]$ $K[0,j]$

Most elkezdheti támadni a közvetítőt. A kulcs ellenőrzéséhez csak újra kell számítani a titkosítás azon részeit, amelyek az értékek és az értékek között lesznek . A k -val végzett inverz számításokhoz csak 4 S-dobozt kell újraszámolni. További számításokhoz k -vel összesen 3 S-doboz. $K[i,j]$ $P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}$ $P_{i}{\xrightarrow[{}]{K[i,j]}}{\xrightarrow[{v_{i}}]{}}$ $S_j$ ${\xleftarrow[{v_{j}}]{}}$ $P_{i}$ ${\xrightarrow[{v_{i}}]{}}$

Ha az állapotok egyeznek, a rendszer talál egy kulcsjelölt kulcsot , amely től ig értékeket vesz fel . Ezután ezt a kulcsot egy másik nyilvános-/titkosszöveg páron tesztelik. $K[i,j]$ $P_{i}$ $S_j$

Eredmények

Ez a támadás az AES128 feltörésének számítási bonyolultságát -ra csökkenti , ami viszont 3-5-ször gyorsabb, mint a brute force módszer. $2^{126.18}$

Jegyzetek

↑ Ernest Foo, Douglas Stebila. Az AES Biclique kriptoanalízisének javítása // Információbiztonság és adatvédelem: 20. ausztrál konferencia, ACISP 2015, Brisbane, QLD, Ausztrália, 2015. június 29. – július 1., Proceedings . - Springer, 2015. - 39. o.
↑ Andrej Bogdanov, Dmitrij Khovratovics, Christian Rechberger. A teljes AES Biclique kriptoanalízise . Archivált másolat (nem elérhető link) . Letöltve: 2015. november 14. Az eredetiből archiválva : 2016. március 6.. (határozatlan)
↑ Narrow-Bicliques: A teljes ÖTLET kriptanalízise .
↑ Whitfield Diffie, Martin E. Hellman. Az NBS adattitkosítási szabvány kimerítő kriptoanalízise .
↑ Dmitrij Khovratovics, Christian Rechberger, Alexandra Savelieva. Bicliques for Preimages: A Skein-512 és az SHA-2 család elleni támadások .
↑ Andrej Bogdanov, Dmitrij Khovratovics, Christian Rechberger. Biclique Cryptanalysis of the Full AES (angol) // Advances in Cryptology - ASIACRYPT 2011 / Dong Hoon Lee, Xiaoyun Wang. - Berlin, Heidelberg: Springer, 2011. - P. 344–371 . - ISBN 978-3-642-25385-0 . - doi : 10.1007/978-3-642-25385-0_19 . Archiválva az eredetiből: 2020. augusztus 20.

Irodalom

Andrej Bogdanov, Dmitrij Khovratovics és Christian Rechberger. A teljes AES Biclique kriptoanalízise . — P. 1-33 . Az eredetiből archiválva: 2016. március 6.