Bumerangin hyökkäys

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 18. joulukuuta 2014 tarkistetusta versiosta . tarkastukset vaativat 34 muokkausta .

Bumerangihyökkäys on kryptografinen hyökkäys lohkosalaukseen , joka perustuu differentiaalisiin kryptausanalyysimenetelmiin . Hyökkäysalgoritmin julkaisi vuonna 1999 Berkeleyn yliopiston professori David Wagner, joka käytti sitä murtamaan COCONUT98- , Khufu- ja CAST-256- salaukset [1] .

Tämä menetelmä mahdollisti onnistuneiden hyökkäysten suorittamisen moniin salakirjoihin, jotka aiemmin tunnistettiin vastustuskykyisiksi "klassista" differentiaalista kryptoanalyysiä vastaan.

Tästä krypta-analyysimenetelmästä on muunnelmia: tehostettu bumerangihyökkäys (vahvistettu bumerangihyökkäys) ja suorakulmainen hyökkäys (suorakulmiohyökkäys).

Yleiset ominaisuudet

Bumerangihyökkäys perustuu differentiaalisen kryptaanalyysin periaatteisiin . Bumerangimenetelmässä käytetään selkeiden tekstien ja niitä vastaavien salatekstien kvartettia parin sijaan, kuten differentiaalisessa kryptausanalyysissä.

Toinen huomattava ero bumerangimenetelmän ja klassisen differentiaalisen krypta-analyysin välillä, jossa selvän tekstin muutosten aiheuttamat muutokset salatekstiin kattavat koko salauksen, on se, että selvän tekstin muutokset voivat kattaa vain osan salauksesta.

Joissakin tapauksissa tämän hyökkäysmenetelmän käyttö voi merkittävästi vähentää tarvittavan tiedon määrää (verrattuna differentiaaliseen kryptausanalyysiin). Lisäksi hyökkäys soveltuu algoritmeihin, joissa on heterogeeninen pyöreä rakenne.

Yksi hyökkäysalgoritmin mielenkiintoisimmista ominaisuuksista on, että se toimii erittäin hyvin salausten kanssa, joissa on epäsymmetrisiä pyöreitä toimintoja. Epäsymmetriset kierrosfunktiot voidaan jakaa kahteen tyyppiin: A-tyypin kierroksiin, joilla on parempi diffuusio eteenpäin kuin taaksepäin, ja B-tyypin kierroksiin, joilla on parempi diffuusio taaksepäin. On huomattava, että jos salauksen ensimmäinen puolikas koostuu B-tyypin sarjoista ja toinen A-tyypin sarjoista, tällainen salaus on haavoittuvin bumerangihyökkäykselle.

Hyökkäysalgoritmi

Oletetaan ensin, että salausalgoritmi voidaan jakaa kahteen peräkkäiseen osaan, joiden monimutkaisuus on suunnilleen yhtä suuri , ja , ja , jossa on jotain selvää tekstiä. Esimerkiksi 16 kierroksen DES-algoritmi , jolla on samankaltainen rakenne, voidaan jakaa kahteen 8 kierroksen osaan. $E$ $E_{0}$ $E_1$ $E(M)=E_{1}(E_{0}(M))$ $M$
Valitaan pari avointa tekstiä ja erolla . Käsittelemällä näitä tekstejä funktiolla saamme eron $P$ $P^{'}$ $\Delta =P\oplus P'$ $E_{0}$ $\Delta ^{*}=E_{0}(P)\oplus E_{0}(P^{'})$
Jatkamme selkeiden tekstien ja toimintojen salaamista ja saamme kaksi salatekstiä ja $P$ $P'$ $E_1$ $C=E_{1}(E_{0}(P))$ $C^{'}=E_{1}(E_{0}(P^{'}))$
Käytämme ja saadaksemme kaksi muuta salatekstiä , jotka liittyvät edelliseen eroon $C$ $C^{'}$ $D$ $D^{'}$ $\nabla =C\oplus D=C^{'}\oplus D'$
Lisäksi kvartetin muodostuminen jatkuu päinvastaiseen suuntaan: "puolipurku" -funktioita sovelletaan eron saamiseksi ja ja $D$ $D^{'}$ $E_{{1}}^{{-1}}$ $E_{{0}}^{{-1}}$ $\nabla ^{*}=E_{{1}}^{{-1}}(D)\oplus E_{{0}}(P)=E_{{1}}^{{-1}}(D ^{'})\oplus E_{{0}}(P^{'})$
Salatekstien edelleen purkaminen ja antaa kaksi selkeää tekstiä ja $D$ $D^{'}$ $Q=E_{{0}}^{{-1}}(E_{{1}}^{{-1}}(D))$ $Q^{'}=E_{{0}}^{{-1}}(E_{{1}}^{{-1}}(D^{'}))$

Lisäksi Wagner todistaa työssään [1] , että ero näin saatujen selkeiden tekstien ja välillä on yhtä suuri kuin ero alkuperäisten selkeiden tekstien ja ja on yhtä suuri kuin . $K$ $Q^{'}$ $P$ $P^{'}$ $\Delta$

Analysoimalla kvartettijoukkoa tekstiä, joilla on tietty ero, voidaan valita tietty sävel (tai sen fragmentti), joka on haluttu sävel joko yksiselitteisesti tai suurimmalla (muihin avaimiin verrattuna) todennäköisyydellä.

Tehostettu bumerangihyökkäys [2]

Tehostettu bumerangihyökkäys on selkokielinen hyökkäys , kun taas klassinen bumerangihyökkäys on mukautuvasti valittu selväkielihyökkäys .

Kun näitä kahta algoritmia verrataan, muiden asioiden ollessa samat, klassinen bumerangihyökkäys vaatii paljon vähemmän dataa kuin tehostettu. Ensi silmäyksellä tällainen algoritmin muutos ei tuota etuja. On kuitenkin kolme seikkaa, jotka erottavat sen klassisesta hyökkäyksestä, minkä vuoksi tehostetun hyökkäyksen käyttö kannattaa joissakin tapauksissa:

Selkeätekstihyökkäyksessä on mahdollista arvata salauksen lopussa oleva avain ilman, että valittujen selkeiden tekstien määrää tarvitsee lisätä.
Tehostettua bumerangihyökkäystä voidaan soveltaa paitsi pareihin, myös K-teksteihin.
Voidaan käyttää tehostushyökkäystä saadakseen pari (tai K) tekstiä jollekin salauksen osalle ja käyttää sitten muita algoritmeja salauksen jäljellä oleville kierroksille. Siten voidaan käyttää katkaistua differentiaalista kryptausanalyysiä , joka määrittää vain pienen osan lohkosta, eikä sitä voida käyttää tavallisen bumerangihyökkäyksen kanssa.

Salausalgoritmit ovat alttiina bumerangihyökkäyksille

Kuvattu alkuperäisessä artikkelissa [1]

COCONUT98 halkeaa mukautuvasti valituilla selkoteksteillä ja salateksteillä. $2^{16}$
16-kierroksen Khufu on murrettu mukautuvasti valituilla selkoteksteillä ja salateksteillä. $2^{18}$
16 pyöreää CAST-256 halkeamaa tunnetuilla teksteillä. $2^{{49.3}}$

Kuvattu muissa lähteissä

6-kierroksen KASUMI on murrettu mukautuvasti valituilla selkoteksteillä ja salateksteillä [3] . $2^{13}$
11 kierrosta MARS - halkeamia tunnetuilla teksteillä [2] . $2^{{65}}$
8-kierrosta Serpent cracks kuuluisilla sanoilla [2] . $2^{{114}}$
5-kierroksen AES - halkeamat tunnetuilla teksteillä [4] . $2^{{39}}$
6-kierroksen AES-halkeamat tunnetuilla teksteillä [4] . $2^{{71}}$

Sovellus täysimittaiseen AES:ään [5]

Bumerangihyökkäyksen ja parannetun bumerangihyökkäyksen periaatteita sovellettiin linkitetyn avaimen hyökkäyksen suorittamiseen AES -192 ja AES - 256 täyden kierroksen salakirjoituksiin . Tämä menetelmä perustuu paikallisten törmäysten havaitsemiseen lohkosalauksissa ja bumerangikytkimien käyttöön.

Oletuksena salaus on jaettu kierroksiin, mutta tämä jako ei ole aina paras bumerangihyökkäykselle. Kierrokset ehdotettiin jakavaksi yksinkertaisiin operaatioihin ja hyödyntäen näissä operaatioissa olemassa olevaa rinnakkaisuutta. Esimerkiksi joitain tavuja voidaan käsitellä itsenäisesti. Tällöin yksi tavu voidaan käsitellä ensin ennen muuntamista salausalgoritmilla, minkä jälkeen se siirtyy muuntamisen jälkeen toisen tavun käsittelyyn. On tikkaat kytkimet, Feistel kytkimet ja s-box kytkimet.

Tämä hyökkäysmenetelmä on tehokkaampi kuin raakavoimahyökkäys . Mutta samalla todetaan, että menetelmällä on pääasiassa teoreettista arvoa asiantuntijoille, eikä se aiheuta uhkaa AES:n käytännön toteutuksille lähitulevaisuudessa korkeiden käsittelyaika- ja laskentatehovaatimusten vuoksi. Toisaalta tätä tekniikkaa voidaan soveltaa varsin tehokkaasti kryptografisten hajautustoimintojen hyökkäyksiin .

Sovellus hash-funktioihin

Koska monet hash-funktiot perustuvat lohkosalauksiin , on luonnollista kokeilla bumerangihyökkäyksiä niitä vastaan, mutta esteitä on useita. Erityisesti salauksen purku, joka on olennainen osa bumerangihyökkäystä, ei välttämättä ole käytettävissä hash-toimintojen yhteydessä.

On kuitenkin osoitettu [6] , että bumerangihyökkäystä, nimittäin sen muunnelmaa, tehostettua selkotekstipohjaista bumerangihyökkäystä, voidaan käyttää hash-funktion murtamiseen. Tämäntyyppinen hyökkäys tarjoaa parannusta aiemmin käytettyihin erohyökkäyksiin verrattuna .

Hyökkäyssopeutuksen pääideana on käyttää klassisissa differentiaalihyökkäyksissä käytetyn huolella valitun globaalin differentiaalipolun lisäksi useita muita differentiaalipolkuja, jotka ovat erittäin hyviä rajoitetussa määrässä vaiheita, mutta eivät kata koko toimintoa kokonaan. . Näiden differentiaalipolkujen yhdistämiseksi yhteen käytetään peruslohkosalauksen hyökkäysmenetelmää, jossa käytetään bumerangimenetelmää.

Tämä hyökkäys on onnistuneesti sovellettu SHA-1- algoritmiin .

Algoritmin haitat

Bumerangihyökkäys on mukautuva valinta selkeän tekstin ja salatekstin hyökkäyksestä. Tämä on yksi vaikeimmista käytännössä toteutettavista kryptografisista hyökkäyksistä.

Mitä tulee differentiaalisen krypta-analyysin menetelmään, bumerangihyökkäyksen käytännön soveltamista rajoittavat korkeat käsittelyajan ja datamäärän vaatimukset.

Käytännössä bumerangihyökkäystä sovellettiin pääasiassa salakirjoihin, joilla oli pienempi määrä kierroksia.

Tässä suhteessa algoritmi on enemmänkin teoreettinen saavutus.

Muistiinpanot

↑ 1 2 3 David Wagner. Bumerangin hyökkäys .
↑ 1 2 3 John Kelsey , Tadayoshi Kohno, Bruce Schneier . Vahvistettu bumerangi hyökkää lyhennettyä MARSia ja käärmettä vastaan .
↑ Eli Biham, Orr Dunkelman, Nathan Keller. Aiheeseen liittyvä suorakulmiohyökkäys koko KASUMIin .
↑ 12 Alex Biryukov . Boomerang Attack 5- ja 6-kierroksen alennettuun AES:iin .
↑ Alex Biryukov , Dmitri Khovratovich. Täydellisen AES-192:n ja AES-256:n vastaava salausanalyysi .
↑ Antoine Joux, Thomas Peyrin. Hash-funktiot ja (vahvistettu) bumerangihyökkäys .

Kirjallisuus

Panasenko S. P. Salausalgoritmit. Erityinen hakuteos - Pietari. : BHV-SPb , 2009. - 576 s. — ISBN 978-5-9775-0319-8