Avain-arvattu hyökkäys

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 21. maaliskuuta 2015 tarkistetusta versiosta . tarkastukset vaativat 24 muokkausta .

Valitun avaimen hyökkäys on yksi kryptanalyyttisen hyökkäyksen menetelmistä , joka valvoo useita salaisia avaimia käyttävän salausalgoritmin toimintaa . Kryptusanalyytikolla on aluksi vain tietoa tietystä matemaattisesta suhteesta, joka yhdistää avaimet toisiinsa.

Kuvaus

Kerckhoffsin periaatteen mukaan kryptanalyytikolla on kaikki tarvittavat tiedot käytetystä salausjärjestelmästä, lukuun ottamatta tiettyä salaisia parametreja, joita kutsutaan avaimeksi. Kryptanalyytikko tietää vain avainparin välisen suhteen. Se käyttää salatekstiä ja annettua suhdetta arvaamaan molemmat avaimet. Valitun avaimen hyökkäystyyppejä tunnetaan kahta tyyppiä: valitun avaimen ja tunnetun selkeän tekstin hyökkäys, jossa kryptanalyytikko määrittelee vain avainparin välisen suhteen, ja valittu avaimen ja selkotekstin hyökkäys, jossa kryptanalyytikko asettaa molemmat suhteet avainpari ja itse selkeä teksti, joka on salattava. [yksi]

Valittuun avaimeen perustuva hyökkäys suoritetaan samalla tavalla kaikkiin salausjärjestelmiin, mukaan lukien niin sanottu "musta laatikko", jonka kaikkia ominaisuuksia ei tunneta. Tämä "musta laatikko" käyttää salaustoimintoa , joka valitaan samalla tavalla viestien satunnaisiin permutaatioihin. Avaimen bitit valitaan sattumanvaraisesti siten, että salatekstin tuntemus ei voi kertoa meille mitään avaimen salatekstistä . ${\displaystyle E_{k))$ $k$ $E_{k}(m)$ $E_{h}(m')$ $h\neq k$

Hyökkäysalgoritmi, joka perustuu valittuun avaimeen "mustassa laatikossa", standarditoimintojen lisäksi, voi milloin tahansa laskennan aikana vaatia:

salata tai purkaa salaus käyttämällä salaista avainta ja vastaavaa viesti- ja inversiovektoria , $E_{k\oplus l}(m)$ $E_{k\oplus l}^{-1}(m)$ $k$ $m$ $l$
käytä "mustaa laatikkoa" laskemiseen tai näppäimen (joka ei ole funktio ) avulla poimimalla viesti . $E_{h}(m)$ $E_{h}^{-1}(m)$ $h$ $k$ $m$

Algoritmilla voi myös olla pääsy satunnaisbittigeneraattoriin. Laskennan lopussa arvioitu avain tulostetaan . [2] $k$

Näin ollen, jos käyttäjä käyttää salaista avainta ja julkista salausjärjestelmää ( julkisen avaimen salausjärjestelmä ), kryptoanalyytikko voi milloin tahansa valita viestin ja inversiovektorin ja suorittaa salauksen tai salauksen purkamisen . Arvatun avaimen hyökkäyksen pääasiallinen sovellus on järjestelmien varmentaminen , mutta tietyissä olosuhteissa tätä hyökkäystä voidaan soveltaa käytännössä. Jos stream-salausta käytetään istuntoavaimen siirtämiseen käyttäjältä käyttäjälle ja kryptanalyytikko saa siirtolinjan hallinnan, hän voi muuttaa mitä tahansa avaimen bittejä mielensä mukaan ja vastaanottaa muutetun avaimen sijaan . Sitten kun se aloittaa lähetyksen väärällä avaimella, se vastaanottaa sotkuisen viestin ja aloittaa palautusprosessin. Sillä välin kryptanalyytikko vastaanottaa avaimella salatun tekstin. (Hyvä salaussuojaus voi torjua tällaisia hyökkäyksiä käyttämällä uusia itsenäisiä istuntoavaimia tai lisäämällä epälineaarisia virheentunnistusbittejä istuntoavaimeen aina, kun tarvitaan palautusmenettelyä. Historia kuitenkin osoittaa, että hyvä kryptosuojaus ei aina noudata tätä ja se on toivottavaa, että järjestelmä ei kaatuisi. tällaisen hyökkäyksen alla) [3] . $k$ $E$ $m$ $l$ $E_{{k\oplus l}}$ $E_{{k\oplus l}}^{{-1}}$ $k$ $A$ $B$ $B$ $k\oplus l$ $k$ $B$ $A$ $k\oplus l$

Pääasiallinen hyökkäystyyppi valittuun avaimeen

Tässä osassa tarkastelemme hyökkäystä, joka ei riipu tietystä salaustoiminnon heikkoudesta. Se on mies-in-the-middle ( MITM ) -hyökkäys. Tämän tyyppisen hyökkäyksen avulla voit lyhentää tarkennetun haun aikaa riippuen sallittujen avaimen käännösten määrästä [4] .

Lause. Olkoon lohkosalaus n-bittisellä avaimella. Oletetaan, että kryptanalyytikko voi suorittaa inversioita ja että hänellä on muistisanoja. Sitten hän pystyy murtamaan salauksen lisävaiheissa [ 4 ] . $E$ $2^{p}$ $2^{p}$ $E$ $2^{{np}}$

Todiste:

Analyytikko korvaa avaimen viimeiset bitit kaikin mahdollisin tavoin. Se esimerkiksi salaa arvot $s$ $2^{p}$

E_{k}(m),E_{{k\oplus (00\pisteet 01)}}(m),\pisteet ,E_{{k\oplus j}}(m),\ldots ,E_{{k\ oplus (00\pisteet 011\pisteet 1)}}(m)

missä on käyttäjän yksityinen avain ja mikä tahansa sopiva viesti. Se luo arvoista hash - taulukon [4] . $k$ $m$ $2^{p}$ $(E_{{k\oplus j}},j)$

Sitten se suorittaa salauksen muuttamalla avaimen ensimmäiset bitit ja nollaamalla viimeiset bitit: $2^{{np}}$ $np$ $s$

E_{{(00\pisteet 0)}}(m),E_{{(00\pisteet 10\pisteet )}}(m),\pisteet ,E_{{(11\pisteet 10\lpisteet 0)}}( m)

Kaikkien laskelmien jälkeen jokainen arvo tarkistetaan hash-taulukosta [4] .

Jos alkuperäinen avain murretaan kautta , jossa on viimeiset bitit, merkintä vastaa tulosta salauksen kautta toisessa vaiheessa. Kun vastaavuus löytyy, se on ehdokasavain. Useat vääriä hälytyksiä ovat mahdollisia, jos viestiä vastaavat useat avaimet , mutta kuten sovitetun tekstin hyökkäyksessä , yksi tai kaksi lisälohkoa tunnettua selkeää tekstiä sulkee ne lähes varmasti pois, sillä on vain vähän vaikutusta ajoaikaan [4] . $k$ $(a, b)$ $b$ $s$ $(E_{{k\oplus b}},b)$ $a^{{th}}$ $(a, b)$ $m$

Johtopäätös: Käyttämällä rajoittamatonta määrää valitun avaimen hyökkäyksiä mikä tahansa lohkosalaus n-bittisellä avaimella voidaan murtaa käyttämällä vain muistin sisäisiä laskelmia [4] . $O(2^{{n/2}})$

Todiste: valitaan . $p = n/2$

Huomautus: Jos esimerkkejä on paljon ja käytettävissä on paljon muistia, on paljon tehokkaampaa vaihtaa kaksi vaihetta lauseen todistuksessa. Laske ja tallenna salaukset muistiin. Suorita jokaiselle tehtävälle käännökset ja tarkista taulukon vaatimustenmukaisuus. Siten jokaiseen lisätehtävään kuluu iteraatioita [4] . $2^{{np}}$ $2^{p}$ $2^{p}$

Estokoodin haavoittuvuus hyökkäykselle valitun avaimen perusteella

Esittelemme tämän tyyppisen hyökkäyksen ominaisuudet salausjärjestelmää vastaan, joka on osoittanut olevansa erittäin vastustuskykyinen vastaavaa tekstihyökkäystä vastaan [3] .

Antaa olla salainen lohkosalaus , jonka avaimen koko on bittiä. Määritetään uusi lohkosalaus . $E$ $n$ $F$

F_{k}(m)=E_{k}(m)

jos ensimmäinen bitti on 0

k

F_{k}(m)=E_{{k'}}(m)\oplus k

muissa tapauksissa, joissa ensimmäisen bitin inversion tulos on esimerkiksi .

k'

k

k'=k\oplus(1,0,\ldots ,0)

F

laillinen lohkosalaus:

F_{k}^{{-1}}(m)=E_{k}^{{-1}}(m)

jos avaimen ensimmäinen bitti on 0

k

F_{k}^{{-1}}(m)=E_{{k'}}^{{-1}}(m\plus k)

, muissa tapauksissa

Jos pääsalauksella on hyvä n-bittinen suojaus, niin salauksen murtaminen tekstianalyysihyökkäyksellä vaatii tarkennetun haun avainbittitilassa. Toisin sanoen, jos analyytikolla ei ole tietoa salauksesta , hän voi saada tarvittavat tiedot, jos hän salaa tai purkaa salauksen avaimilla tai [3] . $E$ $F$ $n-1$ $E$ $k$ $k'$

Vaikka salausta on vaikea murtaa valitulla tekstihyökkäyksellä, se on erittäin helppo murtaa valitulla avainhyökkäyksellä. Analyytikko tarvitsee kaksi salausta: ja sopivaa viestiä varten . Jos ensimmäinen bitti on nolla, niin $F$ $F_{k}(m)$ $F_{{k'}}(m)$ $m$ $k$

F_{k}(m)\oplus F_{{k'}}(m)=E_{k}(m)\oplus (E_{{k''}}(m)\oplus k')=k'

Muissa tapauksissa

F_{k}(m)\oplus F_{{k'}}(m)=(E_{{k'}}(m)\oplus k)\oplus (E_{{k'}}(m)=k

[3] .

Siten analyytikko vastaanottaa välittömästi kaikki avaimen bitit ensimmäistä lukuun ottamatta ja voi suorittaa toiminnon loppuun, koska hän tietää selkeän tekstin [4] . $k$

Esimerkkejä hyökkäyksistä

Hyökkäys LOKI89 :ää vastaan

LOKI89-salauksessa jokaisella valinnalla kahdesta aliavaimesta , joista toinen on parillinen ja toinen parittomasta jaksosta, on vastaava 64-bittinen avain. Koska kaikki algoritmit kahden aliavaimen hankkimiseksi kahdesta edellisestä on samat, niiden syklien sijainti, joissa kaksi nykyistä aliavainta sijaitsevat, ei vaikuta seuraavien aliavaimien tulostukseen. Jos korjaamme kaksi aliavainta ja avainta ja määritämme toisen avaimen valitsemalla ja , avaimen aliavaimien arvot ovat samat kuin seuraavat avaimen aliavaimia . Siinä tapauksessa ,. Tämä suhde säilyy kahdelle tällä tavalla valitulle avaimelle: jos tiedot ennen toista salausjaksoa avaimella ovat samat kuin tiedot ennen ensimmäistä salausta avaimella , niin funktion tiedot ja syöttötiedot ovat samat . molemmissa toiminnoissa siirretty yhdellä jaksolla. Tässä tapauksessa, jos selkeä teksti on salattu avaimella , salateksti ennen toista jaksoa on . Vastaanotettu data on sama kuin se, joka löydettiin ennen ensimmäistä salausjaksoa avaimella , jonka arvo on , ja siten tässä parissa $K2$ $K3$ $K$ $K^{*}$ $K1^{*}=K2$ $K2^{*}=K3$ $Ki^{*}$ $K^{*}$ $K(i+1)$ $K$ $K^{*}=(K2,K3)=(K_{R},ROL12(K_{L}))$ $K$ $K^{*}$ $F$ $P$ $K$ $(P_{R}\oplus K_{R},P_{L}\oplus K_{L}\oplus F(P_{R}\oplus K_{R},K_{L}))$ $K^{*}$ $P^{*}\oplus K^{*}=(P_{R}^{*}\oplus K_{L},P_{R}^{*}\oplus ROL12(K_{L}))$

P ∗ = ( P R , P L ⊕ K L ⊕ R O L 12 ( K L ) ⊕ F ( P R ⊕ K R , K L ) ) {\displaystyle P^{*}=(P_{R},P_{L}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{R}\oplus K_{R},K_ {L}))}

P^{*}=(P_{R},P_{L}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{R}\oplus K_{R},K_ {L}))

Voit nähdä, että lausekkeen oikea puoli on sama kuin lausekkeen vasen puoli , ja kahden muun osan suhde riippuu avaimesta. Tällaisessa parissa on samanlainen suhde salatekstien välillä:

P

P^{{*}}

C ∗ = ( C R ⊕ K L ⊕ R O L 12 ( K L ) ⊕ F ( C L ⊕ K R , K L ) , C L ) . {\displaystyle C^{*}=(C_{R}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(C_{L}\oplus K_{R},K_{L}), C_{L}).}

C^{*}=(C_{R}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(C_{L}\oplus K_{R},K_{L}), C_{L}).

Kaaviot kuvaavat kahden avaimen aliavaimien välistä suhdetta ja arvojen välistä suhdetta salausprosessin aikana.

JÄRJESTELMÄ

Näihin ominaisuuksiin perustuva avainsovitus-plaintext-hyökkäys valitsee 32-bittisen arvon , selkotekstit , joiden oikeat puolet ovat , ja joiden 32-bittiset vasen puoliskot valitaan satunnaisesti, ja selkotekstit , joiden vasen puoli on , ja joiden oikeat puolet valitaan sattumanvaraisesti. Kahta tuntematonta liittyvää avainta käytetään salaamaan tutkittavan järjestelmän selkokieliset tiedot: avaimella salataan ensimmäiset selkeät tekstit ja avaimella loput selkeät tekstit. Jokaiselle selkeiden tekstien parille ja on taattu , että ja suurella todennäköisyydellä on kaksi selkeitä tekstiä siten, että . Tällaisen parin tiedot pysyvät samoina, jos molempia suorituksia siirretään yhdellä jaksolla. Sellainen pari voidaan helposti valita, jos sellainen on olemassa, tarkistamalla yhtäläisyys Todennäköisyys läpäistä tämä testi satunnaisesti on , joten vain harvat parit voivat läpäistä sen. $P_{R}$ $2^{16}$ $P_{0},...,P_{65535}$ $P_{R}$ $2^{16}$ $P_{0}^{*},...,P_{65535}^{*}$ $P_{R}$ $K$ $2^{16}$ $K^{*}=(K_{R},ROL12(K_{L}))$ $2^{16}$ $P_{{i}}$ $P_{j}^{*}$ ${\displaystyle P_{jL}^{*}=P_{iR))$ $P_{jR}^{*}=P_{iL}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{iR}\oplus K_{R},K_{L} )$ $C_{R}^{*}=C_{L}.$ $2^{-32}$

Parit, joilla on nämä selkeän tekstin ja salatekstin ominaisuudet, täyttävät avainvaatimukset (1) ja (2). Näin ollen tälle parille täyttyy relaatio , jossa arvo on ainoa tuntematon . Kaikista mahdollisista arvoista vain harvat täyttävät yhtälön. Differentiaalisen krypta -analyysin ja optimointitekniikoiden avulla arvon löytäminen voidaan tehdä muutamalla operaatiolla. Kun arvo on löydetty , on helppo laskea kaavojen (1) ja (2) avulla saada ja . $F(P_{R}\oplus K_{R},K_{L})\oplus F(C_{L}\oplus K_{R},K_{L})=P_{R}^{*} \oplus P_{L}\oplus C_{L}^{*}\oplus C_{R}$ $K_{L}\oplus K_{R}$ $2^{32}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus ROL12(K_{L})$ $K$ $K^{*}$

Samanlainen valittu avain-tunnettu-plaintext -hyökkäys käyttää tunnettuja selkeitä tekstejä, jotka on salattu tuntemattomalla avaimella, ja selkeitä tekstejä, jotka on salattu vastaavalla avaimella . Pari, jolla on nämä ominaisuudet, voidaan helposti tunnistaa 32 yleisestä selkeän tekstin bitistä ja 32 yhteisestä salatekstibitistä. Tätä paria voidaan käyttää avaimien etsimiseen samalla tavalla kuin valitussa avaimessa ja valitussa selkotekstihyökkäyksessä. [yksi] $2^{32}$ $P_{{i}}$ $K$ $2^{32}$ $P_{j}^{*}$ $K^{*}=(K_{R},ROL12(K_{L}))$

Vertailu muuntyyppisiin hyökkäyksiin

Bruce Schneierin mukaan kryptanalyyttiselle hyökkäykselle on 7 päätapaa [5] :

Salatekstipohjaisen hyökkäyksen tapauksessa kryptanalyytikolla on pääsy vain salatekstiin. Tämä on vaikein hyökkäystyyppi saatavilla olevan tiedon pienen määrän vuoksi.

Tunnetun selkotekstin hyökkäyksessä kryptanalyytikko tietää sekä selkeän tekstin että salatekstin. Tämäntyyppinen hyökkäys on tehokkaampi kuin salatekstipohjainen hyökkäys, koska kryptojärjestelmästä on enemmän tunnettua tietoa.

Valittu selväkielihyökkäys on tehokkaampi hyökkäystyyppi kuin tunnettu selväkielihyökkäys. Mahdollisuus esivalita selkeitä tekstejä tarjoaa enemmän vaihtoehtoja järjestelmäavaimen purkamiseen. On myös totta, että jos kryptojärjestelmä on alttiina tunnetun selkotekstin hyökkäykselle, se on myös alttiina valitulle selväkieliselle hyökkäykselle. [yksi]

Vastaava avainhyökkäys on vahvempi kuin vastaava tekstihyökkäys. Se murtaa välittömästi erityisesti muodostetun lohkosalauksen, joka on suojattu muita hyökkäyksiä vastaan. Minkä tahansa lohkosalauksen kohdalla valittu avainhyökkäys voi nopeuttaa tarkennettua hakuprosessia riippuen avainten käännösten määrästä. Rajoittamattomassa arvausnäppäinhyökkäyksessä työn määrää voidaan vähentää neliöjuurena. Nämä tulokset ovat parhaat mahdolliset yleiselle hyökkäykselle, joka ei perustu mihinkään tiettyyn lohkosalaukseen.

Muistiinpanot

↑ 1 2 3 Biham, 1993 .
↑ Winternitz & Hellman, 1987 .
↑ 1 2 3 4 Winternitz & Hellman, 1987 , s. 17
↑ 1 2 3 4 5 6 7 8 Winternitz & Hellman, 1987 , s. kahdeksantoista
↑ Schneier, 2003 .

Kirjallisuus

Robert Winternitz, Martin Hellman . Valitun avaimen hyökkäykset lohkosalaukseen // Cryptologia : Journal. - 1987. - Ei. 11:1 . - s. 16-20 . - doi : 10.1080/0161-118791861749 .
Eli Biham. Uudet kryptanalyyttisten hyökkäysten tyypit vastaavia avaimia käyttämällä // Helleseth T. (toim.) Advances in Cryptology . — EUROKRYPT '93. EUROCRYPT 1993. Lecture Notes in Computer Science, voi 765. Springer, Berlin, Heidelberg, 1993. doi : 10.1007/3-540-48285-7_34 .
B. Schneier. Sovellettu kryptografia. - Triumph, 2003. - 816 s. - ISBN 5-89392-055-4 .