Lineáris kriptanalízis

A lineáris kriptanalízis egy olyan technika, amelyet Mitsuru Matsui , a Mitsubishi Electric kutatója talált ki . 1993- ból származik, és eredetileg a DES szimmetrikus titkosítási algoritmus törésére fejlesztették ki . Ez a fajta kriptanalízis egy Matsui felfedezését megelőző koncepción alapszik: lineáris valószínűségi kifejezések. Ezeket Henri Gilbert és Anne Tardy-Corfdir tanulmányozta a FEAL elleni támadás összefüggésében .

A lineáris kriptanalízis hatékonyabb, mint a differenciális kriptanalízis , de kevésbé praktikus abból az egyszerű okból, hogy feltételezzük, hogy a támadónak nincs a titkosítási algoritmust szimbolizáló fekete doboza, és hogy nincs. A DES esetében ehhez a támadáshoz eredetileg olyan párokra volt szükség (mind ugyanazzal a kulccsal titkosítva), amelyeket a támadó képes volt helyreállítani egyik vagy másik eszközzel. Ezt követően Matsui 1994-ben fejlesztette algoritmusát, és megoldást javasolt párokkal. A bonyolultság jó megvalósítás mellett azonban alacsonyabb és a DES műveletek sorrendjében van . $2 ^ {{47}}$ $2 ^ {{43}}$ $2 ^ {39}$

A lineáris kriptanalízis abból áll, hogy a titkosítási algoritmust lineáris közelítéssel végezzük annak egyszerűsítésével. A rendelkezésre álló párok számának növelésével javul a közelítés pontossága és kihúzható a kulcs. Minden új titkosítási algoritmusnak ügyelnie kell arra, hogy ellenálljon az ilyen típusú támadásoknak. A DES-t nem azért tervezték, hogy megakadályozza ezt a fajta módszert, a helyettesítési táblázatok ( S-Boxok ) valóban bizonyos lineáris tulajdonságokat mutatnak, miközben pontosan a nem-linearitást kívánták a DES-hez hozzáadni.

Ezt követően sikeresen alkalmazták több algoritmusra, például a LOKI , a FEAL vagy a Kígyó egyszerűsített verziójára . Az olyan újabb algoritmusok, mint az AES (Rijndael), az IDEA és még sok más, immunisak a lineáris támadásokkal szemben. A támadás bonyolultsága ezekben az esetekben sokkal nagyobb, mint a kimerítő keresésé .

Lineáris egyenletek és helyettesítések

Legyen például egy 8 elemű helyettesítő táblázat , az S függvény a függvény helyettesítése . S ( X ) végrehajtása, Y első helyettesítésének végrehajtása . A visszafejtés során a fordított műveletet alkalmazzuk, azaz S⁻1 (Y) = S⁻¹ (S ( X )) = X.

x	Y
000	010
001	100
010	000
011	111.
100	001
101	110
110	101
111.	011

Egy ilyen táblázat nem lineáris, de több helyettesítés és művelet kombinációja részben megszüntetheti a nem-linearitást; ez a lineáris kriptanalízis által keresett hiba. A lineáris kifejezés valójában a következő forma kifejezésére utal ( bináris XOR művelettel ): $\ oplus$ $X_ {1} \ oplus X_ {2} \ oplus X_ {3} \ oplus \ ldots \ oplus X_ {N} = Y_ {1} \ oplus Y_ {2} \ oplus Y_ {3} \ oplus \ ldots \ oplus Y_ {NEM}$ .

Az X vektor annak a függvénynek a bemenete, Y pedig a kimenete, amelyet ezzel a Boole-egyenlettel próbálunk közelíteni. A változó megfelel az X. i- edik bit értékének. $X_ {i}$

Ez a kifejezés ekvivalens: $X_ {1} \ oplus X_ {2} \ oplus X_ {3} \ oplus \ ldots \ oplus X_ {N} \ oplus Y_ {1} \ oplus Y_ {2} \ oplus Y_ {3} \ oplus \ ldots \ oplus Y_ {N} = 0$ .

Példa egyenletekre

A lineáris kriptanalízis célja a valószínűségeket hozzárendelni a lehetséges egyenletekhez. Vegyük például a következő két egyenletet:

$X_ {1} \ oplus X_ {2} \ oplus X_ {3} = Y_ {1} \ oplus Y_ {2}$
$X_ {2} \ oplus X_ {3} = Y_ {3}$

Most ezeket az egyenleteket alkalmazzuk az előző szakasz helyettesítési táblázataira.

Első egyenlet

$x$	$Y$	$X_ {1} \ oplus X_ {2} \ oplus X_ {3}$	$Y_ {1} \ oplus Y_ {2}$
000	010	0	1
001	100	1	1
010	000	1	0
011	111.	0	0
100	001	1	0
101	110	0	0
110	101	0	1
111.	011	1	1

Második egyenlet

$x$	$Y$	$X_ {2} \ oplus X_ {3}$	$Y_ {3} ~$
000	010	0	0
001	100	1	0
010	000	1	0
011	111.	0	1
100	001	0	1
101	110	1	0
110	101	1	1
111.	011	0	1

Látjuk, hogy az első egyenlet 8-ból 4-szer teljesül, míg a (2) egyenlet csak a 8-ból 2-es teljesül. Az (1) egyenlet tehát a becslés jobb közelítése, de nem feltétlenül a legjobb, a az összes lehetséges egyenlet lehetővé teszi a kérdés megválaszolását.

Ez a fajta becslés megismétlődik a titkosítási algoritmus különböző részein, ez a lépés az architektúrájától függően változik. Ezeknek a közelítéseknek köszönhetően megpróbáljuk megtalálni a köztes kulcsok részeit (az alkulcsokat ).

Példa

Vegyünk egy nagyon egyszerű titkosítási algoritmust, amely 3 bitet vesz bemenetként, és 3 titkosított bitet ad kimenetként.

Értékelés

Azaz 3 bites adatok nélkül. Vagyis a végeredmény és 3 bit által titkosítva. Vagyis négy köztes kulcs , amelyet a fő kulcsból veszünk, és használunk a három közbenső szakaszhoz és az utolsó XOR-hoz. Vagyis a "helyettesítés" függvény az i . Számú helyettesítési táblázattal . Legyen az i kulcs j bitjének jelölése . A három táblázat hasonló a fent leírtakhoz. $P ~$ $C ~$ $K_ {1}, K_ {2}, K_ {3}, K_ {4} ~$ $S_ {i} (x) ~$ $K _ {{i, j}} ~$

Titkosítás

A titkosítási eljárást a következőképpen hajtják végre:

$A_ {1} = K_ {1} \ oplus P$
$B_ {1} = S_ {1} (A_ {1}) ~$
$A_ {2} = K_ {2} \ oplus B_ {1}$
$B_ {2} = S_ {2} (A_ {2}) ~$
$A_ {3} = K_ {3} \ oplus B_ {2}$
$B_ {3} = S_ {3} (A_ {3}) ~$
$C = K_ {4} \ oplus B_ {3}$

Összefoglalva: egy XOR-ot alkalmazunk egy köztes kulccsal, minden alkalommal más táblával helyettesítjük, és újra kezdjük.

A lineáris közelítés létrehozása

Most két következő lineáris közelítést veszünk figyelembe az első két helyettesítési táblázatnál. :

$S_ {1}: X_ {1} \ oplus X_ {2} \ oplus X_ {3} = Y_ {2}$
$S_ {2}: X_ {2} = Y_ {1} \ oplus Y_ {3}$

Ebben a példában egyetértünk abban, hogy az első táblázat valószínűsége 3/4, a második valószínűsége 2/7. Ezek a lineáris egyenletek már beépíthetők a titkosítási eljárásba.

A titkosítás első lépése

Eredetileg mi $B_ {1} = S_ {1} (A_ {1}) ~$ .

Az S 1 első helyettesítés közelítésével írhatunk $B _ {{1,2}} = A _ {{1,1}} \ oplus A _ {{1,2}} \ oplus A _ {{1,3}}$ .

Vagy azzal egyenértékű , ezért kicseréljük : $A_ {1} ~$ $K_ {1} \ oplus P$ $A_ {1} ~$ ${\ displaystyle B_ {1,2} = (K_ {1,1} \ oplus P_ {1}) \ oplus (K_ {1,2} \ oplus P_ {2}) \ oplus (K_ {1,3} \ oplus P_ {3})}$ .

A titkosítás második lépése

A következő lépés a titkosítás az, hogy nem egy XOR között B 1 és a K kulcs 2 . Ezt az eredményt közvetlenül integráljuk az előző lépésben kapott utolsó egyenlettel: $A _ {{2,2}} = B _ {{1,2}} \ oplus K _ {{2,2}}$ van ${\ displaystyle A_ {2,2} = {\ Nagy (} (K_ {1,1} \ oplus P_ {1}) \ oplus (K_ {1,2} \ oplus P_ {2}) \ oplus (K_ { 1,3} \ oplus P_ {3}) {\ Nagy)} \ oplus K_ {2,2}}$ .

A titkosítás harmadik lépése

Ezen a ponton a következő lineáris egyenlet áll rendelkezésünkre: ${\ displaystyle A_ {2,2} = {\ Nagy (} (K_ {1,1} \ oplus P_ {1}) \ oplus (K_ {1,2} \ oplus P_ {2}) \ oplus (K_ { 1,3} \ oplus P_ {3}) {\ Nagy)} \ oplus K_ {2,2}}$ .

Most alkalmazzuk a 2 e helyettesítést : $S_ {2}: X_ {2} = Y_ {1} \ oplus Y_ {3}$ $A _ {{2,2}} = B _ {{2,1}} \ oplus B _ {{2,3}}$ .

Helyettesítésével: ${\ displaystyle {\ Big (} (K_ {1,1} \ oplus P_ {1}) \ oplus (K_ {1,2} \ oplus P_ {2}) \ oplus (K_ {1,3} \ oplus P_ {3}) {\ Nagy)} \ oplus K_ {2,2} = B_ {2,1} \ oplus B_ {2,3}}$ .

Negyedik lépés

A kimenet az előző lépésben most titkosított kulccsal , így , ez azt jelenti, ez az egyenlet: $K_ {3} ~$ $A_ {3} = B_ {2} \ oplus K_ {3}$ ${\ displaystyle B_ {2} = A_ {3} \ oplus K_ {3}}$

Ez végül: ${\ displaystyle {\ Big (} (K_ {1,1} \ oplus P_ {1}) \ oplus (K_ {1,2} \ oplus P_ {2}) \ oplus (K_ {1,3} \ oplus P_ {3}) {\ Nagy)} \ oplus K_ {2,2} = (A_ {3,1} \ oplus K_ {3,1}) \ oplus (A_ {3,3} \ oplus K_ {3,3 })}$ .

Ezt az egyenletet úgy rendezzük, hogy csoportosítsuk a kifejezéseket: ${\ displaystyle (K_ {1,1} \ oplus K_ {1,2} \ oplus K_ {1,3} \ oplus K_ {2,2} \ oplus K_ {3,1} \ oplus K_ {3,3} ) \ oplus (P_ {1} \ oplus P_ {2} \ oplus P_ {3}) \ oplus (A_ {3,1} \ oplus A_ {3,3}) = 0}$ .

Sűrűbben: ${\ displaystyle \ Sigma K \ oplus (P_ {1} \ oplus P_ {2} \ oplus P_ {3}) \ oplus (A_ {3,1} \ oplus A_ {3,3}) = 0}$ a . $\ Sigma K = (K _ {{1,1}} \ oplus K _ {{1,2}} \ oplus K _ {{1,3}} \ oplus K _ {{2,2}} \ oplus K _ {{3, 1}} \ oplus K _ {{3,3}})$

Van egy lineáris közelítésünk, amely a következőktől függ:

a három köztes kulcs része
egyszerű szöveg
az utolsó helyettesítési táblázat bejegyzésének része

Alkalmazásával Matsui a Cölöp-Up lemma és a beállítás, hogy 0 vagy 1, akkor megtudja a valószínűsége annak, hogy ez az egyenlet érvényes. Két közelítésünk van, amelyeknek ismerjük a valószínűségeket (a helyettesítő dobozok elemzésének köszönhetően). Két közelítéssel, n = 2: $\ Sigma K$ $1/2 + 2 ^ {{n-1}} (1 / 2-3 / 4) (1 / 2-2 / 7) \ kb. 0,607$ .

Közelítésünknek körülbelül 3 az 5-ben esélye van érvényesnek lenni. Ennek a valószínűségnek a javításával megpróbáljuk finomítani a lineáris közelítést, és egyre több információt kapunk az algoritmusról. Ehhez számos titkosítatlan üzenetre és titkosított megfelelőjükre van szükség. Mivel a helyettesítő dobozok kombinált hatásait nehéz megbecsülni, fontos adatok javíthatják a modellt.

A lineáris kriptanalízis döntő lépése az utolsó kulcs helyreállítása, az a kulcs, amely a titkosítást egy utolsó helyettesítés után hurkolja.

Kulcs helyreállítása

Van kéznél egy titkosítási algoritmusunk első 3 körének közelítése, de esetünkben az utolsó kör kulcsa hiányzik . Itt érkeznek a rendelkezésünkre álló titkosított üzenetek. Veszünk egy üzenetet, és megpróbáljuk visszafejteni az összes lehetséges kulcs tesztelésével . Különösen a titkosítás végén lévő eredmények érdekelnek minket. Pontosabban, veszünk egy titkosított üzenet és végre egy XOR az utolsó kulcs : . Ez megfelel az utolsó helyettesítési táblázat kimenetének. Most végre az ellenkező másodlagosan a táblázat ismert: . $K_ {4} ~$ $K_ {4} ~$ $C ~$ $K_ {4} ~$ $C \ oplus K_ {4}$ $S_ {3} ^ {{- 1}} (C \ oplus K_ {4})$

Ez az érték azonban valójában megfelel lineáris egyenletünk bal oldalának. Van: . Tehát megbecsülhetjük a tesztelt kulcsok érvényességét, ha összehasonlítjuk a fordított helyettesítés által visszaadott pontos értéket és a bitek egészére vagy egy részére vonatkozó lineáris közelítésünket. Nagyszámú üzenetpárral a becslések pontosabbá tehetők. A többi köztes kulcs felfedezéséhez megtámadjuk az algoritmust úgy, hogy fokozatosan haladunk felfelé a tornyokban, amíg az első kulcshoz nem érünk. $S_ {3} ^ {{- 1}} (C \ oplus K_ {4}) = A_ {3}$

Az olyan összetettebb rejtjeleken, mint a DES, a támadások összetettségének csökkentése érdekében csak az alkulcsok egy része érdekel minket. A további tanulmányok lehetővé teszik annak meghatározását, hogy az utolsó alkulcs mely bitjei befolyásolják valóban a lineáris közelítést. 8 fordulatú DES-példájával Matsui jelzi, hogy az utolsó (48 bites) kulcs jelenléte ellenére az egyenletben ennek az utolsó kulcsnak csak 6 bitje befolyásolja azt a kifejezést, amelyben megjelenik.

Számos egyéb technikát fejlesztettek ki a kriptanalízis teljesítményének javítására.

Megjegyzések és hivatkozások

Függelékek

Bibliográfia

[Baignères, Junod és Vaudenay 2004] (en) Thomas Baignères, Pascal Junod és Serge Vaudenay: „ Meddig mehetünk túl a lineáris kriptanalízison? » , A kriptológia fejlődése -ASIACRYPT 2004 , Springer, előadás Notes in Computer Science, vol. 3329,2004, P. 432–450 ( ISBN 978-3-540-23975-8 , ISSN 0302-9743 , DOI 10.1007 / 978-3-540-30539-2_31 , online olvasás [PDF] ).
[Biham 1995] (en) Eli Biham, „ A Matsui lineáris kriptanalíziséről ” , Advances in Cryptology - EUROCRYPT'94 , Springer, előadás Notes in Computer Science, vol. 950,1995, P. 341–355 ( ISBN 978-3-540-60176-0 , ISSN 0302-9743 , DOI 10.1007 / BFb0053449 , online olvasás [PDF] ).
[Collard, Standaert and Quisquater 2007] (en) Baudoin Collard, FX Standaert és Jean-Jacques Quisquater, „ Matsui lineáris kriptanalízisének időbeli komplexitásának javítása ” , információbiztonság és kriptológia - ICISC 2007 , Springer, előadás jegyzetek a számítástechnikában, vol. . 4817,2007, P. 77–88 ( ISBN 978-3-540-76787-9 , ISSN 0302-9743 , DOI 10.1007 / 978-3-540-76788-6_7 ).

[Matsui 1993] (en) Mitsuru Matsui, „ Linear cryptanalysis method for DES cipher ” , Proc. Eurocrypt '93 , Springer, előadás Notes in Computer Science, vol. 765,1993, P. 386–397 ( ISBN 978-3-540-57600-6 , ISSN 0302-9743 , DOI 10.1007 / 3-540-48285-7_33 , online olvasás [PDF] ).

Kapcsolódó cikkek

Külső linkek

[Ritter 1997] ( fr ) Terry Ritter, „ Lineáris kriptanalízis: irodalmi felmérés ” , a lineáris kriptanalízishez kapcsolódó irodalomjegyzék,1997. szeptember 25(megtekintve : 2016. október 27. ) .
[Junod 2000] (en) Pascal Junod, „ A DES lineáris kriptanalízise ” [PDF] ,2000(megtekintve : 2016. október 27. ) .