Linked Key Attack

Related- key attack [ 1] on eräänlainen  kryptografinen hyökkäys  , jossa kryptaanalyytikko valitsee suhteen avainparin välillä, mutta itse avaimet jäävät hänelle tuntemattomiksi. Tiedot on salattu molemmilla avaimilla. Tunnetussa selväkieliversiossa kryptanalyytikko tuntee kahdella avaimella salatun tiedon selkeän tekstin ja salatekstin. Hyökkääjän tavoitteena on löytää todelliset salaiset avaimet. Oletetaan, että hyökkääjä tietää tai valitsee jonkin matemaattisen suhteen, joka yhdistää avaimet. Relaatio on muotoa ( ) [2] , jossa  on hyökkääjän valitsema funktio ja  liittyvät avaimet. Jokaiselle salaukselle avainten välinen suhde valitaan erikseen. On monia tapoja löytää tämä suhde oikein [3] . Verrattuna muihin hyökkäyksiin, joissa hyökkääjä voi manipuloida vain selkeää tekstiä ja/tai salatekstiä, salaisten avainten välisen suhteen valitseminen antaa hyökkääjälle lisää vapautta. Tämän vapauden haittapuoli on, että tällaiset hyökkäykset voivat olla käytännössä vaikeampia. Suunnittelijat yrittävät kuitenkin yleensä luoda "ihanteellisia" primitiivejä, joita voidaan käyttää automaattisesti ilman lisäanalyysiä mahdollisimman laajassa protokolla- tai toimintatilassa. Siten tällaisten hyökkäysten vastustaminen on tärkeä lohkosalauksen suunnittelutavoite, ja itse asiassa se oli yksi Rijndael -algoritmin ilmoitetuista suunnittelutavoitteista .

Avaimen laajennus

Useimmat salausalgoritmit muokkaavat alkuperäistä avainta myöhempää käyttöä varten. Tätä muutosta kutsutaan avaimen laajentamiseksi . On esimerkkejä algoritmeista, joissa avaimen laajennusprosessi on äärimmäisen monimutkainen verrattuna varsinaiseen salaukseen, joista mainittakoon HPC- ja FROG -algoritmit . Proseduurin nimen määrää se, että alkuperäisen salausavaimen koko on yleensä huomattavasti pienempi kuin algoritmin kierroksilla käytetty aliavainjoukko, eli laajennettu avain.


Osoittautuu, että salausalgoritmi voidaan loogisesti jakaa kahteen aligoritmiin: varsinaisiin salausmuunnoksiin ja avaimen laajennusmenettelyyn. Avaimen laajennusmenettelyyn liittyy useita vaatimuksia [4] :

Klassinen linkitetty näppäinhyökkäys [1]

Tämäntyyppistä hyökkäystä ehdotti ensimmäisen kerran israelilainen tiedemies Eli Biham vuonna 1992 artikkelissa New Types of Cryptanalytic Attacks Using Related Keys . Hänen kuvaamansa linkkiavaimen hyökkäys muistuttaa leikkaushyökkäystä . Shift attack ( englanniksi  slide attack ) - kryptografinen hyökkäys , joka on yleisesti ottaen valittuun selkeään tekstiin perustuva hyökkäys , joka mahdollistaa usean kierroksen lohkosalausten kryptausanalyysin käytettyjen kierrosten määrästä riippumatta. Alex Biryukovin ja David Wagnerin ehdottama vuonna 1999 [5] . Vaihtohyökkäys käyttää kahta selkeää tekstiä ja täyttää seuraavan suhteen: , missä on  kierrosfunktio ja on 1. kierroksen  aliavain. Aiheeseen liittyvä avainhyökkäys käyttää samanlaista suhdetta avainten välillä. Oletetaan, että haluttu salausavain K sen avaimenlaajennusproseduurilla muokatun jälkeen antaa aliavainsarjan: , jossa  on salausalgoritmin kierrosten lukumäärä. Oletetaan, että on olemassa avain , jonka laajennus antaa seuraavan järjestyksen: , eli avaimen perusteella luotua aliavainsarjaa siirretään syklisesti suhteessa halutun avaimen järjestykseen 1 kierroksen verran [6] .

Hyökkäyksen ydin

  1. Oletetaan, että kryptanalyytikko tuntee selkeiden tekstien parit ja niitä vastaavat salatekstit (salattu avaimella ), jossa  on salatun datan lohkon koko, esitetty bitteinä .
  2. Lisäksi kryptanalyytikko tuntee tekstipareja, jotka on salattu käyttämällä yllä olevaan suhteeseen liittyvää avainta.
  3. Jokaiselle tekstin korrelaatiolle kryptanalyytikon on löydettävä ratkaisut yhtälöjärjestelmään [7] :

Mikä teksteistä vastaa kutakin osoitteesta peräisin olevaa tekstiä, kryptanalyytikko ei tiedä etukäteen. Mutta todennäköisyys, että kaksi satunnaisesti valittua tekstiä täyttää vaaditun suhteen, on . Silloin vaadittu pari on löydettävä analysoimalla enintään tekstiä syntymäpäiväparadoksin mukaisesti . Tekstien ehto ei ole tiukka, se on arvio ja toteutuu vain keskimäärin [8] .

Yllä olevasta järjestelmästä löydetty avain on vaadittu aliavain . Riippuen avaimen luontitoiminnasta, tieto voi antaa kryptanalyytikolle monia mahdollisuuksia luvaton pääsyyn tietoihin. Esimerkiksi LOKI89 -algoritmin avaimen generointi on rakennettu siten, että se on yksinkertaisesti avaimen vasen 32-bittinen osa . Koska tämä algoritmi käyttää 64-bittistä avainta, laskennan jälkeen riittää, että luetellaan vaihtoehdot sen löytämiseksi . [9]

Hyökkäyksen kohteena olevan algoritmin pyöreän funktion on oltava riittävän heikko laskeakseen , mikä on useimpien nykyaikaisten salausalgoritmien tilanne. Lisäksi hyökkäyksen monimutkaisuutta voidaan vähentää merkittävästi edellä kuvattuun tapaukseen verrattuna, kaikki riippuu valitusta selkotekstin salausalgoritmista. Esimerkiksi tasapainotettuun Feistel-verkkoon perustuvien algoritmien laskelmia yksinkertaistetaan .

Hyökkäykset erilaisiin salausalgoritmeihin

Hyökkäys DES:ää vastaan

DES ( datan encryption s tandard  ) on IBM : n kehittämä ja Yhdysvaltain hallituksen vuonna 1977 viralliseksi standardiksi hyväksymä algoritmi symmetriselle salaukselle ( FIPS 46-3). DES:n lohkokoko on 64 bittiä . Algoritmi perustuu Feistel-verkkoon , jossa on 16 sykliä ( kierrosta ) ja 56 - bittinen avain . Algoritmi käyttää yhdistelmää epälineaarisia (S-laatikot) ja lineaarisia (E, IP, IP-1 permutaatioita) muunnoksia.

DES-salausalgoritmi kestää tällaisen hyökkäyksen. Pääsalaustoiminnon salausprosessin aikana on laskettava kuusitoista 48-bittistä avainta, jotka ovat tulosta 56-bittisen alkuperäisen avaimen muuntamisesta ( katso lisätietoja kohdasta Avainten luominen ). Avainlaskenta-algoritmin vuorojen määrä ei täsmää kaikilla kierroksilla. Tyypillisesti avainrekistereitä siirretään kaksi bittiä jokaisen kierroksen jälkeen ja vain yksi bitti ensimmäisen, yhdeksännen ja viidennentoista kierroksen jälkeen. Jos kuitenkin muutat tätä kytkentämallia, asetat muutoksen samaksi kaikilla kierroksilla, tuloksena oleva kryptojärjestelmä tulee alttiiksi linkitetyn avaimen hyökkäykselle. Vähiten suojattu hyökkäämiselle on modifioitu DES, jossa avainta siirretään kahdella bitillä jokaisen vaiheen jälkeen [10] .

Taulukossa kuvataan vuorojen lukumäärä ennen kutakin avaimen luontikierrosta ja muokattu vuoronumeromuunnos, joka on alttiina linkitetylle avainhyökkäykselle. Sellaisen algoritmin muunnelman murtamiseksi kryptanalyytikko tarvitsisi vain 2 17 valittua selkeää tekstiä valituille avaimille tai 2 33 tunnettua selkeää tekstiä valituille avaimille. Modifioidun DES:n katkaisemiseksi on suoritettava 1,43*2 53 operaatiota, mikä on pieni voitto verrattuna tyhjentävään hakuun, jossa operaatioita on 2 56 [11] . Vuonna 1998 DES murrettiin alle kolmessa päivässä käyttämällä 250 000 dollarin EFF DES -supertietokonetta [12] . EFF DES -krakkeri käytti raa'an voiman hakua [13] krakkaukseen . Valtavat aika- ja datamäärävaatimukset eivät salli hyökkäyksen toteuttamista kytkettyjä avaimia vastaan ​​ilman kalliiden laitteiden apua. Hyökkäys on kuitenkin mielenkiintoinen kahdesta syystä:

Attack on AES

Advanced Encryption Standard ( AES ), joka tunnetaan myös nimellä Rijndael (lausutaan [rɛindaːl] (Randal [14] )) on symmetrinen lohkosalausalgoritmi (lohkokoko 128 bittiä, avain 128/192/256 bittiä), jonka salausstandardi on ottanut käyttöön. Yhdysvaltain hallitus AES-kilpailun tulosten mukaan . Tämä algoritmi on analysoitu hyvin, ja sitä käytetään nyt laajalti, kuten sen edeltäjän DES :n tapauksessa . AES on saatavilla kolmessa eri versiossa, joista jokainen tarjoaa eri suojaustasoa salaisen avaimen pituudesta riippuen. Avain voi olla 128, 192 ja 256 bittiä pitkä. Vuodesta 2001 lähtien, sen jälkeen, kun AES valittiin salausstandardiksi, sen kryptausanalyysi on edistynyt erittäin vähän [15] . Parhaat tulokset saatiin vuonna 2009 liittyvissä avaimissa tehdyissä hyökkäyksissä. Alex Biryukov yhdessä Dmitri Khovratovitšin kanssa toimitti ensimmäisen linkitetyn avaimen kryptanalyyttisen hyökkäyksen täyden kierroksen AES-192:ta ja AES-256:ta vastaan, kehitetty menetelmä on nopeampi kuin raaka voima.

Kehitetty hyökkäys AES-256:ta vastaan ​​soveltuu kaikentyyppisille avaimille ja sen monimutkaisuus on noin 2 96. Esitettiin myös hyökkäys AES-192:ta vastaan. Molemmat hyökkäykset minimoivat avainten luontialgoritmin aktiivisten S-laatikoiden määrän. Tätä toimintoa käytetään bumerangihyökkäyksellä . Bumerangin differentiaaliominaisuudet määritettiin etsimällä paikallisia törmäyksiä salakirjoituksesta [16] . AES-256:n pääominaisuus, joka on ratkaiseva tarkasteltavien hyökkäysten kannalta, on, että salausalgoritmissa on 14 kierrosta ja 256-bittinen avain, joka kaksinkertaistuu sisäisessä tilassa. Tästä syystä avainten luontialgoritmi koostuu vain 7 kierroksesta, ja jokaisella kierroksella on puolestaan ​​8 S-laatikkoa. Samoin AES-192:ssa, koska avaimesta tulee puolitoista kertaa suurempi sisäisessä tilassa, avaimen generointialgoritmi koostuu vain 8, ei 12 kierrosta. Jokaisella kierroksella on vain 4 S-lohkoa.

Hyökkäys AES-256:ta vastaan

Seuraavat vaiheet on suoritettava 2 25,5 kertaa [17] :

  1. Valmistele selkeiden tekstien rakenne alla kuvatulla tavalla.
  2. Salaa se avaimilla ja ja tallenna tuloksena saadut joukot ja .
  3. Toiminto on suoritettava kaikille salakirjoituksille ja purettava muunnettujen salatekstien salaus avaimella .  - uusi joukko avoimia tekstejä.
  4. Vastaavasti ja avain .  - uusi joukko avoimia tekstejä.
  5. Kaikkien selkeiden tekstien parien vertailu 56 bitin pituudesta.
  6. Tarkista kaikkien muiden osalta ero todennäköisyysarvon välillä . Jos se on yhtä suuri 16-bittisen suodattimen molemmilla puolilla, niin avainpareja tai muuten niitä kutsutaan kvarteiksi ja , at , on myös yhtä suuri molemmilla puolilla sivut.
  7. On tarpeen valita kvartetteja, joiden eroihin eivät voi vaikuttaa aktiiviset S-laatikot ensimmäisellä kierroksella ja aktiiviset S-laatikot avaimen generointialgoritmissa.
  8. Suodattamalla pois vääriä kvartetteja, palautamme osittain avaimen arvon.

Jokaisessa rakenteessa on kaikenlaisia ​​vaihtoehtoja sarakkeen nollalle, riville nollalle ja vakioarvolle muissa tavuissa. Jokaisen rakenteen 272 tekstistä voidaan verrata 2144 paria. Näistä pareista 2 (144−8*9) = 2 72 läpäisee ensimmäisen kierroksen. Näin saadaan 1 vaadittu kvartetti 2 (96-72) = 2 24 rakennetta ja 3 vaadittua kvartettia 2 25,5 rakenteesta. Laskemme viimeisten 6 askeleen kvartettojen lukumäärän, niitä on noin 2 (144-56-16) = 2 72 paria. Seuraava askel on käyttää 16-bittistä suodatinta, jolloin saadaan mahdollisten kvartettojen kokonaismäärä 2 (72+25.5−6) = 2 91.5 [18] .

Hyökkäys AES-192:ta vastaan

Avainten luontialgoritmilla on tässä tapauksessa paras diffuusio. Siksi bumerangihyökkäys käyttää kahta 6 kierroksen alaraitaa. Analysoidaan 2 73 rakennetta 2 48 tekstillä seuraavan kaavion mukaisesti [19] :

  1. Vertaa kaikkia mahdollisten selkeiden tekstien pareja avainpareille ja .
  2. Vertaa ja tallenna kaikkia salatekstikvartetteja.
  3. Jokaiselle odotetulle avaintavulle : , ja in ; ja : _
    1. laske näiden tavujen arvot kaikissa avaimissa deltajäljestä. Hanki tärkeimmät erot ja ;
    2. valitse kvartettit, jotka ovat ristiriidassa ;
    3. valmistele laskurit laskemattomille avaintavuille, jotka vastaavat aktiivisia S-ruutuja kahdessa ensimmäisessä ja viimeisessä: , , ,  — avaimissa ja , , , ,  — avaimissa ja , yhteensä 16 tavua;
    4. aseta kullekin kvartetille mahdolliset arvot niiden tuntemattomille tavuille ja lisää laskureita;
    5. luo 16 avaintavun ryhmä enimmäismäärällä;
    6. kokeile avaimen vielä tuntemattomien 9 tavun mahdollisia arvoja ja tarkista, että avain on oikea. Jos skenaario epäonnistuu, siirry ensimmäiseen vaiheeseen [19] .

Molemmat esitetyt hyökkäykset ovat lähinnä teoreettisia eivätkä käytännössä aiheuta todellista uhkaa AES:ää käyttäville sovelluksille.

Käytännön sovellus

Kuvatut hyökkäykset toisiinsa liittyvillä avaimilla eivät vaikuta käytännöllisiltä. Monessa kehityksessä niistä ei ole paljon hyötyä tyhjentävään etsintään verrattuna, lisäksi ne vaativat paljon oletuksia. Tätä hyökkäystä on pitkään pidetty melko voimakkaana, mutta puhtaasti teoreettisena [20] . Asiantuntijat, kuten John Kelsey ja Bruce Schneier [20] uskovat kuitenkin nyt, että linkitettyjen avainten hyökkäyksillä voi olla käytännön sovelluksia. Jotkut salausalgoritmien tai verkkoprotokollien toteutukset (esimerkiksi todennus- tai avaimenvaihtoprotokollat) voivat jo olla alttiita linkitetylle avaimelle [20] . Yksi mahdollinen sovellus on hash - funktioanalyysi . Teoriassa linkitetyn avaimen hyökkäykset voivat olla vaarallisia, jos symmetrisiä salausalgoritmeja käytetään hajautusfunktioiden rakentamiseen. Tällä hetkellä hajautusfunktioille ei tunneta erityistä sovellusta, mutta hash-funktioiden suunnittelijoiden tulee ottaa suunnittelussaan huomioon, että tällainen heikkous on olemassa. Joka tapauksessa on erittäin suositeltavaa ottaa asiaan liittyvien avainten kryptausanalyysi huomioon salausalgoritmeja ja niiden toteuttamista kehitettäessä [21] . [20] : ssa todetaan, että hyökkäyksen pääehto näyttää melko oudolta: kryptanalyytikko voi kirjoittaa avaimen, eli muokata haluttua tuntematonta avainta vaaditulla tavalla, mutta ei voi lukea sitä. Joihinkin salausalgoritmien tai verkkoprotokollien toteutuksiin voidaan kuitenkin hyökätä käyttämällä niihin liittyviä avaimia. Joka tapauksessa on erittäin suositeltavaa ottaa linkitettyjen avainten kryptausanalyysi [20] huomioon salausalgoritmeja ja niiden toteutusta kehitettäessä. On myös huomattava, että hyökkäykset toisiinsa liittyviin avaimiin voivat olla erittäin vaarallisia, jos symmetrisiä salausalgoritmeja käytetään hajautusfunktioiden rakentamiseen.

Huonosti suunnitellulla avaimenlaajennusmenettelyllä salausalgoritmiin on lisätty muita mahdollisia haavoittuvuuksia, erityisesti [22] :

  • haavoittuvuus "meeting in the middle" -luokan hyökkäyksille, koska nämä hyökkäykset hyödyntävät sitä tosiasiaa, että hyökätyn algoritmin salausmuunnosten ensimmäinen osa käyttää erilaista avainbittijoukkoa. kuin toinen osa.
  • Heikot avaimet  ovat avaimia, jotka vastaavat purkamista tai joilla on muita ominaisuuksia, jotka helpottavat murtamista.
  • vastaavat avaimet  - eri avaimet, mutta jotka antavat saman salaustuloksen tietylle selkotekstien alajoukolle.
  • avainluokat  - syntyvät, kun kryptanalyytikko voi suhteellisen helposti määrittää avainjoukon osajoukon, johon vaadittu avain kuuluu, ja vastaavasti vähentää avaimen täydellisen luettelon aluetta.

Katso myös

Muistiinpanot

  1. 1 2 Panasenko S., 2009 , s. 54.
  2. Biryukov ja Khovratovich, 2009 , s. kahdeksan.
  3. Bellare, 2003 , s. 491.
  4. Panasenko S., 2009 , s. 53.
  5. Biryukov, Wagner, 1999 , s. 245-259.
  6. Biryukov ja Khovratovich, 2009 , s. 7.
  7. Biham, 1994 , s. 16.
  8. Panasenko S., 2009 , s. 55.
  9. Panasenko S., 2009 , s. 56.
  10. Biham, 1994 , s. viisitoista.
  11. Biham, 1994 , s. 17.
  12. Computerworld, 1998 .
  13. DES Cracker Project (downlink) . Eff. - "Keskiviikkona 17. heinäkuuta 1998 EFF DES Cracker, joka rakennettiin alle 250 000 dollarilla, voitti helposti RSA Laboratoryn "DES Challenge II" -kilpailun ja 10 000 dollarin rahapalkinnon." Haettu 8. heinäkuuta 2007. Arkistoitu alkuperäisestä 7. toukokuuta 2017. 
  14. "... Flanderin sääntöjen mukaisesti nimi luetaan "Randal" - "Computerra", joulukuu 1999, nro 49
  15. Biryukov ja Khovratovich, 2009 , s. yksi.
  16. Biryukov ja Khovratovich, 2009 , s. 2.
  17. Biryukov ja Khovratovich, 2009 , s. 9.
  18. Biryukov ja Khovratovich, 2009 , s. kymmenen.
  19. 1 2 Biryukov ja Khovratovich, 2009 , s. 12.
  20. 1 2 3 4 5 John Kelsey, 1996 .
  21. Biham, 1994 , s. 2.
  22. Panasenko S., 2009 , s. 59.

Kirjallisuus