Integroitu kryptausanalyysi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 15. kesäkuuta 2014 tarkistetusta versiosta . tarkastukset vaativat 14 muokkausta .

Integral cryptanalysis on kryptoanalyysimenetelmä , joka yhdistää useita hyökkäyksiä symmetrisiin lohkosalausalgoritmeihin . Toisin kuin differentiaalinen kryptausanalyysi , jossa tarkastellaan algoritmin vaikutusta selkeiden tekstien pariin, integraalinen kryptausanalyysi käsittää selkeiden tekstien joukon yhdistämisen salatekstiksi . Lars Knudsen on käyttänyt ensimmäisen kerran vuonna 1997 .

Historia

Tieteellisissä artikkeleissa termiä " integral cryptanalysis " ehdotettiin vuonna 1999 julkaisussa Integral cryptanalysis of SAFER + (englanniksi) . Itse käsitteen esitti ensimmäisenä Lars Knudsen analysoidessaan neliösalausta vuonna 1997. Tästä syystä termiä "neliön kaltaiset hyökkäykset" tai yksinkertaisesti "neliöhyökkäys" käytetään usein kirjallisuudessa. Vuonna 2011 ei ole tapahtunut vallankumouksellista edistystä Square-hyökkäyksen suhteen integroidun krypta-analyysin alalla.

Menetelmän teoreettinen perusta

Olkoon rajallinen Abelin ryhmä . Sitten ottamalla 1. lohkon mahdollisten salatekstien joukoksi (yleensä se määräytyy valitun aakkoston ja lohkokoon mukaan), voidaan tarkastella seuraavan muotoista ryhmää, jolla on sama ryhmäoperaatio: . Näin muodostettu n-ulotteisen avaruuden joukko on kaikkien mahdollisten salatekstien joukko. Vastaavasti tilaelementti on tietty salateksti, tämän vektorin komponentit ovat salatekstilohkojen arvot. Oletetaan, että vektorien summa on vektori, jonka komponentit ovat yhtä suuret kuin termien vastaavien komponenttien summat. Joukkointegraali on kaikkien vektoreiden summa : . ${\näyttötyyli (G,+)}$ $G$ $G$ $G^{n}=G\times ...\times G$ $v=(v_{1},...,v_{n}),v\in G$ $S\subseteq G$ $S$ $\int S=\sum _{v\in S}v$

Onnistuneen integraalisen kryptauksen pitäisi vähentää avainten arvausiteraatioiden määrää . Tätä varten yritämme ryhmitellä selkotekstivektorit niin, että ryhmittelyn perusteella mahdolliset kuviot löytyvät. On kätevää tutkia algoritmeja , jotka perustuvat seuraavaan osioon:

$v_{i}=c,\forall v\in S$
$\{v_{i}:v\in S\}=G$
$\sum _{v\in S}=c'$ ,

missä on kiinteä luku, (vektori) $i$ $c,c'=const\in G$

Seuraavalla lauseella [1] on keskeinen rooli :

Olkoon rajallinen Abelin ryhmä . Merkitse , ja g:n järjestys on 1 tai 2. Määritä . Sitten . Lisäksi, ${\näyttötyyli (G,+)}$ $H=\{g\in G:g+g=0\}$ $s(G)=\sum _{g\in G}g$ $s(G)=\sum _{t\in H}h$ $s(G)+s(G)=0$

On syytä huomata eräs tärkeä lauseen tulos: jos ), niin , koska ${\displaystyle G=GF(2^{s))$ $s(G)=0$ $H=\{0\}$

Panemme merkille useita merkintöjä, joita käytetään usein integraaliin kryptausanalyysiin perustuvia hyökkäyksiä koskevissa julkaisuissa:

Jos integraalin i :s komponentti on merkitty , tämä tarkoittaa, että integraalisumman kaikissa ehdoissa i - komponentti on sama ${\mathcal {C}}$
Samoin se osoittaa, että vastaava komponentti eroaa kaikissa termeissä. $\mathcal{A}$
$\mathcal{S}$ osoittaa, että integraalin annettu komponentti voidaan ennustaa.
? osoittaa, että on mahdotonta ennustaa integraalin komponenttia.

Yleinen periaate haavoittuvuuksien etsimisestä Feistel-verkon esimerkissä

Harkitse kuinka integraalit yli S muuttuvat , jos kaikki tämän joukon elementit syötetään Feistelin verkon tuloon. Olkoon S joukko salatekstejä, joissa kaikki vastaavat lohkot yhtä lukuun ottamatta ovat samoja (ne voivat poiketa toisistaan). Esimerkissä salateksti on 16 lohkoa, jotka on järjestetty 2 riville. Salauksille, kuten AES , on myös tärkeää ottaa huomioon, että salateksti annetaan matriisin avulla, koska ne käyttävät erilaisia toimintoja riveille ja sarakkeille. Harkitse Feistelin solujen vaikutusta vaiheittain:

Olettaen, että Feistel-solut tuottavat bijektiivisiä kuvauksia , on selvää, että samat lohkot salatekstien välillä menevät samoihin lohkoihin muunnettujen salatekstien välillä (on kuitenkin lähes varmaa, että vanhat ja uudet arvot eroavat toisistaan). Siten voidaan kirjoittaa, että 1. solu kuvasi joukon joukkojen luokasta, jonka komponentit ovat identtisiä joukossa, samaan luokkaan.
Koska kaikkien Feistel-solun lähdössä olevien lohkojen arvo riippuu kunkin lohkon arvosta sisääntulossa, yhden lohkon vaikutus muuttaa jokaista salatekstin lohkoa lähdössä. Siten integraalin komponenttien arvoista ei tule enempää kuin ennustettavissa [2] . $\mathcal{A}$
Koska jokaisen syötesalaustekstiin kuuluvan lohkon sisääntulossa arvojoukko ei ole sama kuin mahdollisten lohkoarvojen joukko, niiden summa ei välttämättä säily bijektiivisen muunnoksen aikana, joten ulostulossa voidaan saada mitä tahansa solu.

Jopa kuvattuun esimerkkiin sovellettaessa on mahdollista merkittävästi vähentää valinnan iteraatioiden määrää tai tarjota lisätietoa erityyppisiin kryptausanalyysiin.

Vertailu differentiaaliseen kryptausanalyysiin

Kuten differentiaalisen kryptauksen yhteydessä, integraalipohjaiset hyökkäykset voidaan luokitella hyökkäystyypeiksi, jotka perustuvat mukautuvasti valittuun selkeään tekstiin .

Lars Knudsen totesi myös samankaltaisuuden katkaistun differentiaalihyökkäyksen kanssa , jonka ideana on ottaa huomioon ei koko eron käyttäytyminen, kuten differentiaaliskriptianalyysissä, vaan sen osia. Lisäksi integraalisella kryptausanalyysillä on ylivoimainen kyky ottaa huomioon tuloksen kolmas tila - , kun taas katkaistujen differentiaalien hyökkäys erottaa vain kaksi. $\mathcal{S}$

Voit hyökätä korkean kertaluvun differentiaaleihin , voit nähdä, että Galois-kentässä s :nnen kertaluvun differentiaalin lauseke on samanlainen kuin integraali [3] . Siten voidaan yrittää yleistää joitakin differentiaalisen kryptaanalyysin menetelmiä integraalisiksi. $GF(2^{s})$

On huomionarvoista, että myös Lars Knudsen julkaisi ensimmäisen kerran katkaistujen differentiaalien ja korkean asteen differentiaalien hyökkäykset vuonna 1994, myös FSE:n konferenssissa [4]

Merkittäviä hyökkäyksiä

Hyökkäykset AES :n kaltaisiin salakirjoihin ( Rijndael , SQUARE , CRYPTON ) voidaan yleistää ensimmäisellä askeleella - integraalien huomioon ottaminen kolmannen salauskierroksen jälkeen. Seuraavat askeleet ovat yrityksiä parantaa hyökkäystä lisäämällä kierrosten määrää käyttämällä erilaisia oletuksia, jotka väistämättä lisää haun iteraatioiden määrää ja siten myös katkaisun monimutkaisuutta.

AES

Hyökkäys 4-kierroksen salausta vastaan

Tavumatriisin salauksen avainkohdat ovat epälineaarinen muunnos, rivinsiirto, sarakemuunnos, tekstin lisääminen (välitavumatriisi) pyöreällä avainmatriisilla.

Harkitse kuusitoistatavuista selkeää tekstiä . Olkoon kryptanalyytikolla käytössään 256 salatekstiä, joilla on seuraava ominaisuus: ne saadaan tavumatriiseista, joissa kaikki tavut yhtä lukuun ottamatta ovat samoja näiden salatekstien joukossa. Niiden lukumäärän vuoksi voimme sanoa, että "epätasainen" tavu ottaa kaikki mahdolliset arvot tietyssä joukossa. Siten voimme siirtyä yllä olevaan merkintään:

Alkutila:

$\mathcal{A}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$

Harkitse tekstin tilaa jokaisen kierroksen jälkeen:

Bijektiivisyydestä johtuva epälineaarinen muunnos ei muuta tavutyyppiä, vain yksittäisten tekstien arvoja.
Rivien siirto ei vaikuta 1. riviin, loput siirretään integraalia muuttamatta.
Sarakemuunnos tekee jokaisen tuloksena olevan tavun riippuvaiseksi alkuperäisen sarakkeen kaikista 4 tavusta, mutta jälleen kerran toiminnan bijektiivisyyden vuoksi saamme, että sarakkeen jokainen tavu ottaa jokaisen arvonsa vain kerran.
Lisäys avaimella ei muuta tavutyyppejä.

Eli ensimmäisen kierroksen jälkeen:

1. kierroksen jälkeen:

$\mathcal{A}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
$\mathcal{A}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
$\mathcal{A}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$
$\mathcal{A}$	${\mathcal {C}}$	${\mathcal {C}}$	${\mathcal {C}}$

Rivisiirto jakaa 1 tavun jokaiseen sarakkeeseen, jonka tyyppi on . $\mathcal{A}$
Kuten kierroksella 1, jos sarakkeessa on yksi tavu ja loput ovat , kaikki sarakkeen tavut muunnetaan . Kaikki 4 saraketta muunnetaan tällä tavalla. $\mathcal{A}$ ${\mathcal {C}}$ $\mathcal{A}$

Toisen kierroksen jälkeen:

2. kierroksen jälkeen:

$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$
$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$
$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$
$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$

Käyttämällä teoriaosassa kuvatun lauseen tulosta, saamme jokaisen tavun integraalien arvot ${\mathcal {S}}=0$

3. kierroksen jälkeen :

{\mathcal {S}}=0

$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$
$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$
$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$
$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$

Koska viimeisellä kierroksella ei ole sarakemuunnoksia (AES-spesifikaation mukaan) ja loput muunnokset muunnetaan muotoon , niin nelikierroksisessa järjestelmässä integraalin arvo ei muutu viimeisen kierroksen seurauksena binäärilisäysvaiheeseen asti pyöreällä avaimella. Tässä tapauksessa ei jää muuta kuin kunkin tavun olettaa kierrosavaimen vastaavan tavun arvo, saada 3. kierroksen arvioitu teksti ja tarkistaa, onko vastaavan lohkon integraali nolla. Jos yhtä suuri, pyöreä avaintavu voidaan katsoa löytyneeksi. $\mathcal{A}$ $\mathcal{A}$

Laajennukset kierrosten lukumäärän mukaan

Menetelmää voidaan laajentaa seitsemän kierroksen malliksi ottamalla huomioon, mitä integraalin muunnos riippuu tietystä tavusta. Kuitenkin jopa 7 kierroksen tapauksessa vaadittujen iteraatioiden määrä on suuri, tässä tapauksessa kierrosnäppäinten välisiä linkkejä etsitään analysoimalla koodinmuodostusmallia. [5]

Cryptographer Resource Improvements

Vähennä merkittävästi avainten etsimiseen kuluvaa aikaa, koska hakuehtojen erityisjärjestelystä johtuen kolmitavuisia vektoreita käyttämällä voidaan ottaa käyttöön niin sanottu osasumma. Tällainen kuuden kierroksen salauksen muunnos pienentää numeroinnin tehoa arvosta . Toinen lähestymistapa on käyttää sitä tosiasiaa, että integraali ylisarjoja erilaisten kanssa myös katoaa halutun kolmannen kierroksen jälkeen. Tämä menetelmä vaatii valtavan määrän muistiresursseja ja erittäin suuren perustekstipohjan - salakirjoituksen - hallussa. [6] $2^{{72}}$ $2^{{44}}$ ${\mathcal {C}}$

Osittaisia summia käyttämällä on mahdollista toteuttaa kahdeksan kierroksen järjestelmän hakkerointi, mutta tämän hakkeroinnin monimutkaisuus on vielä suurempi kuin tyhjentävä luettelointi .

Neliö

Perushyökkäys Square-salausta vastaan on käytännössä sama kuin neljän kierroksen hyökkäys AES:ää vastaan, sen avulla voit myös laajentaa kierrosten määrää. Ehkä ainoa merkittävä ero on ensimmäisen salauskierroksen olemassaolo ja sen seurauksena kaksi laajennusmenetelmää (toinen kohti viimeistä kierrosta, toinen kohti ensimmäistä). Salauksen kehittäjät pystyivät sitä tutkiessaan rakentamaan hyökkäyksen kuuden kierroksen salaukselle .

Seuraavat tulokset on julkaistu [7] :

Hyökkäykset Squarella:

Hyökkäys	Avointen tekstien määrä	Aika	Muistin hinta
4 kierrokselle	$2^{{9}}$	$2^{{9}}$	Harva
5 kierrosta 1. tavalla	$2^{11}$	$2^{40}$	muutama
5 kierrosta toisella tavalla	$2^{32}$	$2^{40}$	$2^{32}$
6 kierrokselle	$2^{32}$	$2^{{72}}$	$2^{32}$

Muistiinpanot

↑ Herstein, Algebran aiheet, 2. painos, 1975, sivu 116
↑ Dolgov, Golovashich, Ruzhentsev. "Tornado-salauksen kryptografisen vahvuuden analyysi" (2003), s. 7
↑ Lars Knudsen (2001). "Integraal Cryptanalysis (Extended Abstract), s. 118"
↑ Lars Knudsen (1994). "Katkaistu ja korkeamman asteen erotus"
↑ Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner ja Doug Whiting. "Parannettu Rijndaelin kryptaanalyysi" (2001), s. 2-3
↑ Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner ja Doug Whiting. "Parannettu Rijndaelin kryptaanalyysi" (2001), s. 4-7
↑ Joan Daemen, Lars Knudsen, Vincent Rijmen. "The Block Cipher Square" (1997), s. 15

Linkit

Lars Knudsen ja David Wagner. Integral Cryptanalysis (Extended Abstract) (neopr.) . – 2003.
Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner ja Doug Whiting. Parannettu Rijndaelin krypta- analyysi (neopr.) . - 2001. Arkistoitu 8. tammikuuta 2009. Arkistoitu 8. tammikuuta 2009 Wayback Machinessa
Joan Daemen, Lars Knudsen, Vincent Rijmen (tammikuu 1997). The Block Cipher Square (PDF) . 4th International Workshop on Fast Software Encryption (FSE '97), Volume 1267 of Lecture Notes in Computer Science. Haifa: Springer-Verlag. s. 149-165.