Lineaarinen kryptausanalyysi

Krypografiassa lineaarinen kryptausanalyysi on kryptausanalyysimenetelmä , joka käyttää lineaarisia approksimaatioita kuvaamaan salauksen toimintaa .

Lineaarisen kryptoanalyysin keksi japanilainen kryptologi Mitsuru Matsui ( Jap. 松井 充 Matsui Mitsuru ). Hänen vuonna 1993 (Eurocrypt '93 -konferenssissa) ehdottaman algoritmin tarkoituksena oli alun perin murtaa DES ja FEAL [1] . Myöhemmin lineaarinen kryptausanalyysi laajennettiin muihin algoritmeihin. Nykyään se on differentiaalisen krypta -analyysin ohella yksi yleisimmistä menetelmistä lohkosalausten murtamiseen [2] . Hyödyllinen myös tietovirtasalauksia vastaan .

Lineaarisen kryptoanalyysin löytäminen oli sysäys uusien salausmenetelmien rakentamiseen [3] .

Kuinka se toimii

Kryptaanalyysi tapahtuu kahdessa vaiheessa. Ensimmäinen on luoda suhteita selkeän tekstin , salatekstin ja avaimen välille , jotka ovat totta suurella todennäköisyydellä. Toinen on käyttää näitä suhteita yhdessä tunnettujen selväteksti-salateksti-parien kanssa avainbittien johtamiseen.

Lineaaristen yhtälöiden rakentaminen

Algoritmin tarkoitus on saada seuraavat suhteet:

missä  ovat tekstin, salatekstin ja avaimen n :s bitti.

Näitä suhteita kutsutaan lineaarisiksi approksimaatioiksi . Tällaisen suhteen kelpoisuuden todennäköisyys P mielivaltaisesti valituille selkeän tekstin, salatekstin ja avaimen biteille on suunnilleen yhtä suuri kuin 1/2. Sellaisia ​​suhteita, joiden todennäköisyys eroaa huomattavasti 1/2:sta, voidaan käyttää algoritmin avaamiseen.

Lineaarisen kryptaanalyysin ideana on määrittää muotoa (1) olevat lausekkeet, joilla on suuri tai pieni esiintymistodennäköisyys. Jos salausalgoritmilla on yhtälön (1) korkea taajuus tai päinvastoin, yhtälö suoritetaan alhaisella taajuudella, tämä osoittaa huonoa kykyä satunnaistaa salaus. Jos yhtälön (1) toteutumisen todennäköisyys on yhtä suuri kuin p , niin siirtymän todennäköisyys on p − 1/2. Mitä suurempi siirtymän todennäköisyys on | | p − 1/2|, sitä parempi on lineaarisen kryptaanalyysin sovellettavuus vähemmällä hyökkäykseen tarvittavalla selkeällä tekstillä [1] [4] .

Lineaarisia kryptausanalyysihyökkäyksiä on useita tyyppejä [5] [6] [7] . Matsui-algoritmia tarkastellaan: aluksi jokaiselle salauskierrokselle löydetään lineaarinen approksimaatio, jolla on suurin harhan todennäköisyys. Tuloksena saadut lausekkeet yhdistetään kaikille kierroksille yhteiseksi lineaariseksi approksimaatioksi, jonka todennäköisyyttä voidaan siirtää etumerkin ylityslemman avulla .

Seuraavaksi tarkastellaan algoritmia parhaan lineaarisen approksimation löytämiseksi yhdelle kierrokselle. Lohkosalauksissa analyysi keskittyy pääasiassa S-laatikoihin , koska ne ovat salauksen epälineaarinen osa. Koska S-laatikko ottaa m bittiä syötteenä ja palauttaa n bittiä, kryptanalyytikon on muodostettava 2 m + n approksimaatiota. Yhden approksimoinnin todennäköisyyden löytämiseksi S-laatikolle annetaan kaikki 2 m :n mahdolliset tuloarvot ja lasketaan kuinka monta kertaa tämä approksimaatio on totta tulo- ja lähtöbiteille. Tuloksena saatu otteluiden määrä jaetaan 2 metrillä . DES-algoritmissa taulukon S5 lineaarisella approksimaatiolla on suurin biasin todennäköisyys , jossa neljäs kuudesta tulobitistä on XOR-korjattu kaikkien neljän lähtöbitin yli todennäköisyydellä 12/64 [8] [ 4] . Täyden kierroksen DES:lle on saatu relaatio, jonka täyttymistodennäköisyys on 1/2 + 2 −24 [9] .

Lineaarisella kryptausanalyysillä on yksi erittäin hyödyllinen ominaisuus: tietyissä olosuhteissa (esimerkiksi kun selkeän tekstin tiedetään koostuvan ASCII-merkeistä ) relaatio (1) voidaan pelkistää yhtälöksi, jonka muoto on [10] [11] :

Tässä ei ole pelkkää tekstiä, eli voit rakentaa hyökkäyksen pelkän salatekstin perusteella. Tällainen hyökkäys voidaan soveltaa siepattu salateksti ja on käytännöllisempi.

Lemma merkkien juoksemisesta

Vaikka likimäärää, jolla on suurin poikkeama 1/2:sta, ei ole vaikea löytää yhdelle kierrokselle, bias-todennäköisyyden laskemisessa on ongelma, kun menetelmä ekstrapoloidaan koko kierroksen salaukseen. Periaatteessa tämä vaatisi kryptanalyytikon tarkastelevan kaikkia mahdollisia selkeiden tekstien ja avainten yhdistelmiä, mikä ei ole mahdollista. Ratkaisu tähän ongelmaan on tehdä useita oletuksia ja arvioida todennäköisyys merkkien tunkeutumisen lemman avulla . Otetaan eri kierroksille lineaariset approksimaatiot, jotka ovat yhtä kuin 0 todennäköisyydellä . Tällöin todennäköisyys, että lineaarinen kokonaisapproksimaatio on nolla, on [1] [4]

Haetaan avainbittejä

Kun lineaarinen approksimaatio on saatu, voidaan käyttää suoraa algoritmia ja arvata avainbittien arvot pelkkäteksti-salateksti-parien avulla. Tässä tapauksessa on loogista käyttää tehokkainta suhdetta, eli sellaista, jolla todennäköisyyden P poikkeama 1/2:sta on suurin.

Jokaiselle avainbittiarvojoukolle yhtälön (1) oikealla puolella lasketaan selkoteksti-salateksti-parien määrä T , joille yhtälö ( 1) on tosi . Ehdokas, jonka poikkeama T puolella selväteksti-salateksti-parien lukumäärästä on absoluuttisesti suurin, oletetaan olevan todennäköisin avainbittiarvojen joukko [1] [4] .

Sovellus

Lineaarinen kryptausanalyysi kehitettiin alun perin lohkosalauksiin kohdistuviin hyökkäyksiin, mutta sitä voidaan soveltaa myös suorasalauksiin. Kehittäjä itse on tutkinut yksityiskohtaisesti sen soveltamista DES:ään.

Sovellus DES:ään

Mitsuru Matsuin kokeet selkokielisillä hyökkäyksillä (laskelmat suoritettiin 66 MHz HP9750:lla) antoivat seuraavat tulokset [12] [13] :

  • 8-kierroksen DES vaati 221 tunnettua selkeää tekstiä. Hyökkäys kesti 40 sekuntia.
  • 12-kierroksen DES vaati 233 tunnettua selkeää tekstiä ja 50 tuntia.
  • 16 kierroksen DES vaati 243 tunnettua selkeää tekstiä ja 50 päivää.

Vuonna 2001 Pascal Junod ( fr.  Pascal Junod ) suoritti sarjan kokeita selvittääkseen hyökkäyksen monimutkaisuuden. Tuloksena kävi ilmi, että todellisuudessa hyökkäys 16 kierroksen DES:ää vastaan ​​voidaan toteuttaa onnistuneesti 2 39 - 2 41 tunnetun tekstin läsnä ollessa [13] .

Useilla salauskierroksilla lineaarista kryptausanalyysiä käytetään yleensä "raaka voima" -menetelmän yhteydessä  - sen jälkeen, kun tietyt avainbitit on löydetty lineaarisella kryptausanalyysillä, suoritetaan tyhjentävä haku mahdollisista arvoista. loput bitit. Tällä lähestymistavalla on useita syitä: Ensinnäkin parhaat lineaariset approksimaatiot antavat meille mahdollisuuden löytää vain joidenkin avainbittien arvot, ja toiseksi vaadittujen selkotekstien määrä on tässä tapauksessa pienempi ja jäljellä olevien avainbittien luettelointi kestää vähemmän. aika [5] [13] .

Toisin kuin differentiaalinen kryptausanalyysi, joka vaatii valittuja selkeitä tekstejä, menetelmä tyytyy tunnettuihin selkeisiin teksteihin, mikä lisää merkittävästi sen laajuutta. Kuitenkin myös lineaarisessa kryptausanalyysissä on joskus hyödyllistä käyttää valittuja selkotekstejä tunnettujen tekstien sijaan. Esimerkiksi DES:lle on olemassa tekniikka, joka vähentää huomattavasti datan määrää ja laskentaa, jota tarvitaan käyttämällä valittuja selkeitä tekstejä [7] .

Sovellus muihin salausmenetelmiin

DES:n ja FEALin lisäksi on muitakin algoritmeja, jotka ovat lineaarisen kryptaanalyysin alaisia, esimerkiksi:

  1. Lineaarinen kryptausanalyysi toimii RC5 -algoritmia vastaan, jos haluttu salausavain kuuluu heikkojen avainten luokkaan [14] .
  2. NUSH- ja NOEKEON - algoritmit rikotaan myös lineaarisella kryptausanalyysillä [15] [16] [17] .
  3. Korreloimattomiin lineaarisiin approksimaatioihin perustuva lineaarisen krypta-analyysin laajennus soveltuu 6-kierroksen AES -192:n ja AES-256:n sekä 13-kierroksen CLEFIA - 256 :n katkaisemiseen [6] .

Suojaus lineaarista kryptausanalyysiä vastaan

Lohkosalauksen hyökkäämiseksi lineaarisella kryptausanalyysillä riittää, kuten edellä on kuvattu, että saadaan lineaarinen suhde, jonka todennäköisyys on siirtynyt merkittävästi 1/2:sta. Vastaavasti ensimmäinen tavoite hyökkäyskestävän salauksen suunnittelussa on minimoida todennäköisyysbias, jotta voidaan varmistaa, ettei tällaista suhdetta ole olemassa. Toisin sanoen on varmistettava, että lohkosalaus täyttää tiukan avalanche-kriteerin (SAL). Lohkosalauksen sanotaan tyydyttävän SLC:n, jos tuloksena olevan salatekstin tekstin tai avaimen muutoksen yhteydessä täsmälleen puolet biteistä käännetään, ja jokainen bitti muuttuu todennäköisyydellä 1/2. Tämä saavutetaan yleensä valitsemalla erittäin epälineaarisia S-laatikoita ja tehostamalla diffuusiota .

Tämä lähestymistapa antaa hyvän perustelun salauksen turvallisuudelle, mutta varmistaakseen tiukasti suojan lineaarista kryptausanalyysiä vastaan, salauksen suunnittelijoiden on otettava huomioon monimutkaisempi ilmiö, lineaarinen runkoilmiö [ 6 ] [ 18] . On huomattava, että salaukset, jotka ovat optimaalisia tiettyä kapeaa hyökkäysluokkaa vastaan, ovat yleensä heikkoja muuntyyppisiä hyökkäyksiä vastaan. Esimerkiksi DES:ssä tunnetaan S-laatikoiden järjestely, joka lisää merkittävästi lineaarisen kryptaanalyysin vastustuskykyä, mutta huonontaa vastustuskykyä differentiaalista kryptausanalyysiä kohtaan [19] .  

Taivutettujen toimintojen käytöllä oli merkittävä rooli vakaiden S-laatikoiden rakentamisessa . Vuonna 1982 havaittiin, että taivutettujen funktioiden perusteella rakennetuilla maksimipituisilla sekvensseillä on erittäin alhaiset sekä ristikorrelaation että autokorrelaation arvot [20] [21] . Myöhemmin useat kryptografit ovat työskennelleet taivutettujen funktioiden ja niiden vektorianalogien käytön parissa lohkosalausten salausresistanssin lopullisen lisäämiseksi lineaarista ja differentiaalista analyysiä kohtaan [22] [23] [24] .

Katso myös

Muistiinpanot

  1. ↑ 1 2 3 4 Matsui, 1993 .
  2. ↑ Ferguson, Schneier, 2004 , s. 82.
  3. ↑ Heys H. M. , Tavares S. E. Substituutio-permutaatioverkot, jotka vastustavat differentiaalista ja lineaarista kryptausanalyysiä  // Journal of Cryptology / I. Damgård - Springer Science+Business Media , International Association for Cryptologic Research , 1996. - Voi. 9, Iss. 1. - s. 1-19. — ISSN 0933-2790 ; 1432-1378 - doi:10.1007/BF02254789
  4. ↑ 1 2 3 4 Hei, 2002 .
  5. ↑ 12 Matsui , 1994 .
  6. ↑ 1 2 3 . _ _ _ _  _ _ Koodit Cryptogr. — Springer US , Springer Science+Business Media , 2014. — Voi. 70, Iss. 3. - s. 369-383. — ISSN 0925-1022 ; 1573-7586 - doi:10.1007/S10623-012-9697-Z
  7. ↑ 1 2 Knudsen L. R. , Mathiassen J. E. Valittu selväkielinen lineaarinen hyökkäys DES :ään  // Fast Software Encryption : 7th International Workshop , FSE 2000 New York, NY, USA, 10.–12 . huhtikuuta 2000 Proceedings , J. Hartmanis , J. v. Leeuwen , B. Schneier - Berliini : Springer Berlin Heidelberg , 2001. - P. 262-272. - ( Lecture Notes in Computer Science ; Vol. 1978) - ISBN 978-3-540-41728-6 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-44706-7_18
  8. ↑ Matsui, 1993 , s. 389.
  9. ↑ Matsui, 1993 , s. 397.
  10. ↑ Matsui, 1993 , s. 389, 394.
  11. ↑ Kruppa H. , Shah S. U. A. Differentiaalinen ja lineaarinen kryptaanalyysi AES-ehdokasalgoritmien arvioinnissa  - 1998 .
  12. ↑ Matsui, 1993 , s. 387.
  13. ↑ 1 2 3 Junod P. Matsuin hyökkäyksen monimutkaisuudesta  // Selected Areas in Cryptography : 8th Annual International Workshop , SAC 2001 Toronto, Ontario, Kanada, 16.–17. elokuuta 2001 Revised Papers / S. Vaudenay Yousse , A - M. Berlin . , Heidelberg , New York, NY , Lontoo [jne.] : Springer Berlin Heidelberg , 2001. - P. 199-211. — 364 s. - ( Lecture Notes in Computer Science ; Voi. 2259) - ISBN 978-3-540-43066-7 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-45537-X_16
  14. ↑ Heys H. M. RC5:n lineaarisesti heikot näppäimet  // IEE Electronics Letters - IEEE , 1997. - Voi . 33, Iss. 10. - P. 836-837. — ISSN 0013-5194 ; 1350-911X - doi:10.1049/EL:19970601
  15. ↑ Wu W. , Feng D. NUSH-lohkosalauksen lineaarinen kryptausanalyysi  // Science in China Series F : Information Sciences - Science China Press , Springer Science+Business Media , 2002. - Voi. 45, Iss. 1. - s. 59-67. — ISSN 1674-733X ; 1869-1919
  16. ↑ Knudsen L. R. , Raddum H. Noekeonissa  (englanniksi) : NES/DOC/UIB/WP3/009/1. NESSIE-projektin julkinen raportti - 2001.
  17. ↑ NESSIE First Phase (D13) -turvallisuusarviointi (linkki ei saatavilla) . Haettu 2. joulukuuta 2015. Arkistoitu alkuperäisestä 11. elokuuta 2017. 
  18. ↑ Röck A. , Nyberg K. Lineaarisen rungon hyödyntäminen Matsuin algoritmissa  // WCC 2011 : Seitsemäs kansainvälinen koodauksen ja kryptografian työpaja, 11.-15. huhtikuuta 2011 Pariisi, Ranska. Käsittely - 2011.
  19. ↑ Matsui M. Korrelaatiosta S-laatikoiden järjestyksen ja DES:n vahvuuden välillä  // Advances in Cryptology — EUROCRYPT '94 : Workshop on the Theory and Application of Cryptographic Techniques Perugia, Italia, 9.–12.5.1994 Proceedings / A. D. Santis - Berlin : Springer Berlin Heidelberg , 1995. - P. 366-375. - ISBN 978-3-540-60176-0 - doi:10.1007/BFB0053451
  20. ↑ Olsen J. D. , Scholtz R. A. , Welch L. R. Taivutetut funktiosekvenssit  // IEEE Trans . inf. Teoria / F. Kschischang - IEEE , 1982. - Voi. 28, Iss. 6. - P. 858-864. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1982.1056589
  21. ↑ Forrié R. Tiukka lumivyörykriteeri: Boolen funktioiden spektriominaisuudet ja laajennettu määritelmä  // Advances in Cryptology - CRYPTO '88 : Proceedings / S. Goldwasser - NYC : Springer New York , 1990. - P. 468450. - ( Lecture Notes in Computer Science ; Vol. 403) - ISBN 978-0-387-97196-4 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/0-387-34799-2
  22. ↑ Nyberg K. Täydelliset epälineaariset S-laatikot  // Advances in Cryptology - EUROCRYPT '91 : Workshop on the Theory and Application of Cryptographic Techniques Brighton, UK, 8.–11. huhtikuuta 1991. Proceedings / D. W. Davies - Berlin : Springer Berlin Heidelberg 1991. - s. 378-386. — ISBN 978-3-540-54620-7 — doi:10.1007/3-540-46416-6_32
  23. ↑ Seberry J. , Zhang X. Erittäin epälineaariset 0-1 tasapainoiset Boolen funktiot, jotka täyttävät tiukat lumivyörykriteerit (laajennettu tiivistelmä  ) // Advances in Cryptology - AUSCRYPT '92 : Workshop on theory and Application of Cryptographic Techniques, Australia, Queens Coast, Queens Coast 13.– 16. joulukuuta 1992 Proceedings / J. Seberry , Y. Zheng - Berlin : Springer Berlin Heidelberg , 1993. - P. 143-155. - ( Lecture Notes in Computer Science ; Vol. 718) - ISBN 978-3-540-57220-6 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-57220-1
  24. ↑ Adams C. M. Symmetrinen salakirjoituksen rakentaminen CAST-suunnitteluproseduurilla  // Des . Koodit Cryptogr. - Springer US , Springer Science + Business Media , 1997. - Voi. 12, Iss. 3. - s. 283-316. — ISSN 0925-1022 ; 1573-7586 - doi:10.1023/A:1008229029587

Kirjallisuus