Kuinka lineaarinen kyrptanalyysi voi rikkoa DES-salausjärjestelmän?

/ / Julkaistu Kyberturvallisuus, EITC/IS/CCF: n klassisen salauksen perusteet, DES-salaussalaussysteemi, Data Encryption Standard (DES) - Avainaikataulu ja salauksen purku

Lineaarinen kryptoanalyysi on tehokas kryptoanalyyttinen hyökkäysmenetelmä, joka soveltaa lineaarisia approksimaatioita salausalgoritmin toimintaan. Se on erityisen tehokas lohkosalauksia, kuten Data Encryption Standard (DES) -standardia vastaan. Ymmärtääksemme, kuinka lineaarinen kryptoanalyysi voi rikkoa DES-salausjärjestelmän, on tärkeää ottaa huomioon sekä DES:n mekaniikka että lineaarisen kryptoanalyysin periaatteet.

1. Yleiskatsaus DES:stä:

Data Encryption Standard (DES) on symmetrisen avaimen algoritmi digitaalisen tiedon salaukseen. Se toimii 64-bittisillä tietolohkoilla ja käyttää 56-bittistä avainta. DES perustuu Feistel-rakenteeseen, joka jakaa syöttölohkon kahteen puolikkaaseen ja käsittelee ne useiden permutaatio- ja korvauskierrosten kautta. Jokainen kierros sisältää seuraavat vaiheet:
– Laajennus: Lohkon oikea puoli on laajennettu 32 bitistä 48 bittiin.
– Näppäinsekoitus: Laajennettu oikea puoli on XOR-merkitty pyöreällä avaimella, joka on johdettu päänäppäimestä.
– Korvaus: Tulos jaetaan kahdeksaan 6-bittiseen segmenttiin, joista jokainen kulkee vastaavan S-laatikon läpi, jolloin saadaan 4-bittinen tulos.
– Permutaatio: S-laatikoiden 32-bittinen lähtö permutoidaan ennalta määritetyn taulukon mukaan.

Sitten vasen ja oikea puolisko vaihdetaan ja prosessi toistetaan 16 kierrosta. Lopullinen permutaatio tuottaa salatun tulosteen.

2. Lineaarisen kryptaanalyysin periaatteet:

Mitsuru Matsuin 1990-luvun alussa kehittämä lineaarinen kryptausanalyysi pyrkii hyödyntämään suoratekstin, salatekstin ja avainbittien välisiä lineaarisia suhteita. Ydinideana on löytää lineaarisia approksimaatioita, jotka pätevät tietyllä todennäköisyydellä salauksen epälineaarisille komponenteille, kuten S-laatikoille DES:ssä. Lineaarisen kryptaanalyysin vaiheet ovat seuraavat:
– Tunnista lineaariset approksimaatiot: Määritä lineaariset yhtälöt, jotka approksoivat S-ruutujen käyttäytymistä. Nämä likiarvot ovat muotoa P[i] \oplus C[j] \oplus K[k] = 0, Jossa P on selväkielinen bitti, C on salatekstin bitti ja K on avainbitti.
– Laske bias: Mittaa todennäköisyys, että lineaarinen approksimaatio pätee. Bias on poikkeama arvosta 0.5 (todennäköisyys, että satunnainen arvaus on oikea).
– Kerää tietoja: Salaa suuri määrä selkeitä tekstejä kerätäksesi riittävästi tietoa tilastollista analyysiä varten.
– Analysoi tiedot: Käytä kerättyä tietoa todennäköisimpien avainbittien tunnistamiseen havaittujen harhojen perusteella.

3. Lineaarisen krypta-analyysin käyttäminen DES:ssä:

Lineaarisen krypta-analyysin soveltaminen DES:ään käsittää useita vaiheita. Puretaan prosessi:

3.1. Lineaaristen likiarvojen tunnistaminen:

Ensimmäinen askel on tunnistaa lineaariset approksimaatiot DES:ssä käytetyille S-laatikoille. Jokaisessa DES:n S-laatikossa on 6 tulobittiä ja 4 lähtöbittiä. Tavoitteena on löytää lineaariset yhtälöt, jotka approksimoivat S-boxin lähtöjä tietyllä biasilla. Harkitse esimerkiksi S-laatikkoa tulobiteillä x_1, x_2, x_3, x_4, x_5, x_6 ja lähtöbitit y_1, y_2, y_3, y_4. Lineaarinen approksimaatio voi olla muotoa:

    \[ x_1 \oplus x_2 \oplus y_3 = 0 \]

Tämä yhtälö osoittaa, että tulobittien XOR x_1 ja x_2 ja lähtöbitti y_3 on yhtä suuri kuin 0 tietyllä todennäköisyydellä.

3.2. Biasin laskenta:

Kun lineaariset approksimaatiot on tunnistettu, seuraava vaihe on laskea harha jokaiselle approksimaatiolle. Bias on ero todennäköisyyden, että approksimaatio pätee, ja 0.5:n välillä. Esimerkiksi jos approksimaatio x_1 \oplus x_2 \oplus y_3 = 0 pätee todennäköisyydellä 0.75, harha on:

    \[ \epsilon = 0.75 - 0.5 = 0.25 \]

3.3. Tietojen kerääminen:

Lineaarisen krypta-analyysin suorittamiseen DES:ssä tarvitaan suuri määrä selväteksti-salateksti-pareja. Tarvittavien parien määrä riippuu lineaarisen approksimoinnin biasista. Yleensä mitä enemmän pareja kerätään, sitä suurempi on analyysin tarkkuus. DES:lle saattaa tarvita useita tuhansia tai jopa miljoonia pareja.

3.4. Datan analysointi:

Kerätyllä tiedolla seuraava vaihe on analysoida selväteksti-salateksti-parit todennäköisimpien avainbittien määrittämiseksi. Tämä sisältää seuraavat alavaiheet:
– Laske kullekin selväkieli-salateksti-parille lineaaristen approksimaatioiden arvot.
– Laske, kuinka monta kertaa kukin approksimaatio pätee.
– Käytä laskelmia todennäköisyyksien arvioimiseen ja vertaa niitä odotettuihin todennäköisyyksiin harhojen perusteella.

4. Esimerkki lineaarisesta kryptaanalyysistä DES:ssä:

Tarkastellaan yksinkertaistettua esimerkkiä, jossa olemme tunnistaneet lineaarisen approksimaation DES:n ensimmäiselle S-laatikolle. Oletetaan, että likiarvo on:

    \[ P[1] \oplus C[3] \oplus K[5] = 0 \]

Täällä P[1] on selvän tekstin ensimmäinen osa, C[3] on salatekstin kolmas bitti ja K[5] on avaimen viides bitti. Vaiheet DES:n katkaisemiseksi käyttämällä tätä likiarvoa ovat seuraavat:

4.1. Tiedonkeruu:

Salaa suuri määrä selkeitä tekstejä DES:n avulla ja kerää vastaavat salatekstit. Yksinkertaisuuden vuoksi oletetaan, että olemme keränneet 1,000,000 XNUMX XNUMX selväteksti-salateksti-paria.

4.2. Datan analysointi:

Laske jokaiselle selväteksti-salateksti-parille arvo P[1] \oplus C[3]. Jos tulos on 0, lisää laskuria; muussa tapauksessa vähennä laskuria. Laskurin arvo ilmaisee likiarvon biasin.

4.3. Avainbittien arviointi:

Arvioi laskurin arvon perusteella todennäköisyys, että approksimaatio pätee. Vertaa tätä todennäköisyyttä odotettuun harhaan perustuvaan todennäköisyyteen. Jos havaittu todennäköisyys on merkittävästi suurempi tai pienempi kuin 0.5, se viittaa siihen, että avainbitti K[5] on todennäköisesti 0 tai 1, vastaavasti.

5. Käytännön huomioita:

Vaikka yllä oleva esimerkki on yksinkertaistettu, käytännöllinen lineaarinen kryptausanalyysi DES:ssä sisältää monimutkaisempia approksimaatioita ja useita S-laatikoita. Lisäksi hyökkäys vaatii merkittäviä laskentaresursseja tietojen keräämiseen ja analysointiin. Riittävällä datalla ja laskentateholla lineaarinen kryptausanalyysi voi kuitenkin vähentää tehokkaasti avaintilaa ja mahdollistaa avaimen palauttamisen.

6. Vastatoimenpiteet:

Lineaarisen kryptoanalyysin riskin vähentämiseksi nykyaikaiset salausalgoritmit on suunniteltu kestämään tällaisia ​​hyökkäyksiä. Tekniikat, kuten kierrosten määrän lisääminen, suurempien avainkokojen käyttö ja monimutkaisempien S-laatikoiden sisällyttäminen, voivat parantaa lohkosalausten turvallisuutta. DES:lle Triple DES:n (3DES) käyttöönotto tarjoaa korkeamman turvallisuustason soveltamalla DES-algoritmia kolme kertaa eri avaimilla.

Muita viimeaikaisia ​​kysymyksiä ja vastauksia liittyen Data Encryption Standard (DES) - Avainaikataulu ja salauksen purku:

Katso lisää kysymyksiä ja vastauksia kohdassa Data Encryption Standard (DES) - Avainaikataulu ja salauksen purku

Lisää kysymyksiä ja vastauksia:

Tagged alla: , , , , ,