Aikahyökkäys

Salauksessa ajoitushyökkäys on sivukanavahyökkäys , jossa hyökkääjä yrittää vaarantaa kryptojärjestelmän analysoimalla salausalgoritmien suorittamiseen kuluvaa aikaa . Jokaisen loogisen toimenpiteen suorittaminen tietokoneessa vie aikaa, ja tämä aika voi vaihdella syötetietojen mukaan. Tarkoilla aikamittauksilla eri toimintoja varten hyökkääjä voi palauttaa syötetiedot.

Salausjärjestelmät käyttävät usein hieman eri aikaa eri syötteiden käsittelyyn. Syynä tähän voivat olla suorituskyvyn optimoinnit, jotka ohittavat tarpeettomia operaatioita, haaroitus , tietojen lukeminen välimuistista , prosessorin käskyt (kuten kerto- ja jakolasku), jotka suoritetaan epädeterministisessä ajassa ja muut. Suorituskykyominaisuudet riippuvat yleensä sekä salausavaimesta että syöttötiedoista. Samanaikaisesti tiettyjen pyyntöjen suorittamiseen käytetty aika voi muodostua tietovuodosta järjestelmästä. Se, kuinka paljon tällaiset tiedot voivat auttaa hyökkääjää, riippuu monista parametreistä, kuten: salausjärjestelmän suunnittelusta, järjestelmää palvelevasta prosessorista , käytetyistä algoritmeista, oleellisista toteutusyksityiskohdista, ajoitushyökkäystä vastaan toteutetuista vastatoimista, viiveen tarkkuudesta. otettuja mittauksia.

Hyökkäys nopeaa eksponentioalgoritmia vastaan

Diffie-Hellman- ja RSA - algoritmien käyttämä nopea eksponentioalgoritmi suorittaa seuraavan toiminnon salaiselle avaimelle , jossa n on osa julkista avainta (RSA) tai vakio (Diffie-Hellman) ja y voidaan kuulla. Hyökkääjän tavoitteena on saada salainen avain x . Uhri laskee useita y - arvoja . w on avaimen x bitin pituus . $R=y^{x}{\bmod {n))$ $y^{x}{\bmod {n))$

Let~s_{{0}}~=~1

~k=0~~w-1:lle:

Jos~(bitt~k~of~x)~on~1~niin

LetR_{k}=(s_{k}\cdot y){\bmod {n))

muu

Olkoon~R_{{k}}~=~s_{{k}}

Let~s_{k+1}=R_{k}^{2}{\bmod {n))

EndFor

Paluu~(R_{{w-1}})

Hyökkäys sallii bittien 0..(b-1) tiedossa löytää bitin b . Koko eksponentin saamiseksi voidaan aloittaa arvolla b=0 ja jatkaa, kunnes koko eksponentti tunnetaan.

Tietäen x : n ensimmäiset b bitit , hyökkääjä voi laskea silmukan ensimmäiset b iteraatiot ja löytää arvon . Seuraava iteraatio käyttää x:n ensimmäistä tuntematonta bittiä . Jos se on yhtä suuri kuin 1, laskenta suoritetaan , jos se on 0, toiminto ohitetaan. $varten$ $s_{{b}}$ $R_{b}=(s_{b}\cdot y){\bmod {n))$

Kiinan jäännöslauseen käyttäminen

Salaisen avaimen toimintojen optimoimiseksi RSA :ssa käytetään usein kiinalaista jäännöslausetta . Ensin lasketaan ja , jossa y on viesti. Yksinkertaisin hyökkäys on valita y lähellä p tai q . Jos y on pienempi kuin p , se ei tee mitään, ja jos , sen on vähennettävä p arvosta y vähintään kerran. Lisäksi, jos y on hieman suurempi kuin p , sen merkittävimmät bitit ovat yhtä kuin nolla, mikä voi lyhentää ensimmäisen kertolaskuaikaa. Tarkka ajoitus riippuu toteutuksesta. $y{\bmod {p}}$ $y{\bmod {q}}$ $y{\bmod {p}}$ $y>p$ $y{\bmod {p}}$

Esimerkkejä hyökkäyksistä RSA:ta vastaan: RSA: n ajoitushyökkäykset ja RSA :n ajoitushyökkäykset

Temporal cryptanalysis DSS

Digital Signature Standard -algoritmi laskee , jossa p ja q ovat hyökkääjän tiedossa ja lasketaan etukäteen, H(m) on viestin hash, x on salainen avain. Käytännössä se ensin lasketaan ja kerrotaan sitten . Hyökkääjä voi laskea H(m) :n ja korjata sen. Koska H(m) on suunnilleen samankokoinen kuin q , summalla on vain vähän vaikutusta pelkistysoperaatioon Montgomeryn eksponentiomenetelmässä ( en ). Korkeimmat bitit ovat merkittävimpiä . R :n arvo tunnetaan. X :n korkeiden bittien ja Montgomeryn vähennysoperaation suoritusajan välillä on suhde . Ennakkoon laskettuna viestin allekirjoitus vaatii vain kaksi modulokertoa, joten lisätyn kohinan määrä jää suhteellisen pieneksi. $s=(k^{-1}(H(m)+x\cdot r)){\bmod {q))$ $k^{{-1}}$ ${\näyttötyyli (H(m)+x\cdot r){\bmod {q))}$ $k^{-1}{\bmod {q))$ $x\cdot r$ $k^{{-1}}$

Ajoituksen maskaus

Ilmeisin tapa estää ajoitushyökkäykset on varmistaa, että kaikki toiminnot vievät yhtä paljon aikaa. Tällaista ratkaisua, varsinkin alustasta riippumatonta, on kuitenkin vaikea toteuttaa, koska kääntäjän suorittamat optimoinnit, välimuistin käyttö, käskyjen ajoitukset ja muut tekijät voivat aiheuttaa odottamattomia ajoituspoikkeamia. Jos ajastinta käytetään viivästyttämään tuloksen antamista, järjestelmän vaste pysyy havaittavissa. Jotkin käyttöjärjestelmät ilmoittavat myös prosessorin kuormituksen ja virrankulutuksen.

Toinen tapa on tehdä aikamittauksista niin epätarkkoja, että hyökkäys muuttuu sietämättömäksi. Suoritusaikaan lisätään satunnaisia viiveitä, mikä lisää hyökkääjän tarvitsemien salatekstien määrää.

Attack Prevention

Sokean allekirjoituksen luomiseen käytettyjä tekniikoita (katso myös Blinding ) voidaan mukauttaa estämään hyökkääjää altistamasta syötettä modulo eksponentiotoiminnolle. Ennen kuin laskemme modulaarisen eksponentin, valitsemme satunnaisen parin siten, että . Diffie-Hellmanille on helpompi valita ensin satunnainen ja sitten laskea . RSA: ssa on nopeampaa valita satunnainen koprima n :llä ja sitten laskea , jossa e on osa julkista avainta. Ennen eksponentiomoduulin suorittamista syöttöviesti on kerrottava luvulla , jonka jälkeen tulos on korjattava kertomalla . Järjestelmän tulee hylätä viestit, jotka ovat yhtä suuria kuin . $(v_{{i}},v_{{f}})$ $v_{f}^{-1}=v_{i}^{x}{\bmod {n))$ $v_{{i}}$ $v_{f}={(v_{i}^{-1})^{x}}{\bmod {n}}$ $v_{{f}}$ $v_{i}={(v_{f}^{-1})}^{e}{\bmod {n))$ $v_{i}{\pmod {n))$ $v_{f}{\pmod {n))$ $0{\pmod {n}}$

Käänteismoduulin laskemista pidetään hitaana operaationa, joten on usein epäkäytännöllistä luoda uutta paria jokaiselle eksponentiooperaatiolle. Niitä ei kuitenkaan voi käyttää uudelleen, koska aika voi hyökätä niihin itsessään. On olemassa ratkaisu: päivitä ja ennen jokaista eksponentiotoimintoa laskemalla ja . $(v_{{i}},v_{{f}})$ $v_{{i}}$ $v_{{f}}$ $v_{{i}}^{{'}}=v_{{i}}^{{2}}$ $v_{{f}}^{{'}}=v_{{f}}^{{2}}$

Linkit

Paul C. Kocher. Ajoitushyökkäykset Diffie-Hellmanin, RSA:n, DSS:n ja muiden järjestelmien toteutuksiin . CRYPTO 1996: 104-113.
David Brumley, Dan Boneh. Etäajoitushyökkäykset ovat käytännöllisiä . USENIX Security Symposium, elokuu 2003.