Žodis angliškai:

Timming analysis attack

Santrumpa:

Žodis lietuviškai:

Laiko analizės ataka

Apibrėžimas:

Laiko analizės ataka - tai ataka vykdoma matuojant bendrą kriptografinių operacijų laiką, tarp šifro patekimo puolamai sistemai ir jos atsakymo. Žinant naudojamą kodavimo algoritmą ir atakuojamos mašinos veikimo greitį, dėl algoritmo įgyvendinime panaudotų šakojimosi ir peršokimo operacijų galima atsekti kokios naudojamos rakto reikšmės.

Paaiškinimas:

1996 metais Paul C. Kocher pristatė kaip gali būti nustatomi šifravimo raktai analizuojant mažus laiko reikalingo kriptografiniams skaičiavimams atlikti pakitimus. Ši ataka apima hipotezių formavimą apie galimas slaptas reikšmes ir statistinius metodus hipotezių tyrimui stebint įrenginio elgsenos koreliaciją hipotezės atžvilgiu. Šis atakos tipas nereikalauja daug skaičiavimo resursų, tačiau reikalauja žinomo pradinio šifruojamo teksto. Tarp pažeidžiamų sistemų yra kriptografinės žymos (angl. token), tinko kriptosistemos ir kitokios sistemos kur atakuojantis gali tiksliai išmatuoti laiką.

Kriptosistemos dažniausiai užtrunka nevienodą laiką apdorojant skirtingą informaciją. Laiko skirtumai atsiranda dėl:

kodo optimizacijos praleidžiant nereikalingas kodo dalis,
šakojimosi ir sąlygos operacijų sakinių,
nepataikymų į greitinančią atmintį,
kintamos trukmės dalybos/daugybos operacijų,
dėl kitų priežasčių.

Dažniausiai šifravimo našumas priklauso nuo šifruojamo teksto ir nuo rakto, atitinkamai keičiasi ir šifravimo laikas. Suprantama, kad tokiu atveju nedidelė dalis informacijos laiko trukmių pavidalų apie šifruojamus duomenis ir raktą nuteka. Tačiau įmanomos atakos kai pagal laiko trukmes atkuriamas visas slaptas raktas.

Defio-Helmano ir RSA privataus rakto operacijos susideda iš R = y^x mod n skaičiavimo, kur n yra viešas ir y gali būti rastas stebint taikinį. Įsibrovėlio tikslas nustatyti slaptą raktą x. Kad ataka pavyktų, auka turi paskaičiuoti y^x mod n kelioms y reikšmėms, kur y, n ir skaičiavimo laikas yra žinomi atakuojančiam. Ataka nepavyks jei kiekvieną kartą naudojamas kitokia eksponentė x. Reikiama informacija gali būti nustatyta pasyviai pasiklausant interaktyvaus protokolo, kadangi atakuojantis gali įrašyti taikinio gaunamas žinutes ir laiką reikalingą atsakyti į kiekvieną y. Taip pat tariama, kad atakuojantis žino taikinio sistemos architektūrą, praktiškai tai gali būti nustatoma pagal laiką per kurį atliekami veiksmai. Ataka gali būti pritaikyta beveik bet kuriam algoritmui, kuris veikia ne fiksuotu laiku. Panagrinėkime supaprastintą atakos modelį, kai naudojamas paprastas moduliarus laipsnio rodiklio algoritmas R = y^x mod n skaičiavimui atlikti, kur x yra w ilgio:

Let s..0.. = 1. For k = 0 upto w - 1: If (bit k of x) is 1 then Let R..k.. = (s..k.. ∙ y) mod n. Else Let R..k.. = s..k... Let s..k..+1 = R..k..^2 mod n.
EndFor. Return (R..w..-1).

Ataka leidžia, kažkam žinančiam laipsnio rodiklio bitus 0..(b-1) rasti bitą b. Tam, kad rasti visą laipsnio rodiklį, reikia pradėti nuo b lygaus 0 ir kartoti ataką kol visas rodiklis taps žinomas.

Kai pirmieji b laipsnio rodiklio bitai žinomi, atakuojantis gali apskaičiuoti s_b reikšmę. Sekanti iteracija reikalauja pirmojo nežinomo laipsnio rodiklio bito. Jei šis bitas nustatytas bus skaičiuojama R_b = (s_b ∙ y) mod n, jei ne operacija bus praleidžiama.

Tarkime, kad R_b = (sb ∙ y) mod n operacija yra itin lėta, tokiu atveju kai laipsnio rodiklio bitas lygus 0 lėta operacija nenulems lėto normaliojo moduliariojo kėlimo laipsniu vykdymą. Tačiau kai rodiklio b bitas bus lygus 1, tai nulems lėtą moduliariojo kėlimo laipsniu vykdymą. Iš vykdymo galima bus nustatyti kokia buvo rodiklio bito reikšmė.

Jei laipsnio rodiklio bitas spėjamas neteisingai apskaičiuotos R_k≥b bu neteisingos ir atakos požiūriu atsitiktiniai. Laikas reikalingas daugybai po klaidos neatitiks bendro kėlimo laipsniu laiko. Taigi ši ataka turi klaidos aptikimo savybė. Po neteisingo spėjimo nebegaunama prasmingų koreliacijų. Ši savybė gali būti panaudojama klaidos taisymui. Tam turi būti vienu metu sekamos kelios galimos reikšmės. Aptikus, neteisingą reikšmę jos reitingas vienetu sumažinamas, o teisingų reikšmių padidinamas. Kadangi vienu metu sekamos kelios galimos reikšmės ataka reikalauja daugiau atminties ir skaičiavimo pajėgumų, bet gali akivaizdžiai sumažinti reikalingų atskaitų skaičių, ypač nesėkmės atveju.

Pats akivaizdžiausias šios atakos prevencijos būdas padaryti, kad visos operacijos užimtų vienodą laiko tarpą. Tačiau dažniausiai tai sudėtinga. Sukurti programą veikiančia fiksuotu laiku nepriklausomai nuo platformos yra sunku, dėl kompiliatoriaus optimizacijų, nepataikymų į greitinančiąją atmintį, instrukcijų vykdymo trukmės ir kitų faktorių nulemiančių laiko skirtumus. Net jei taimeris yra naudojamas, tam kad sulaikyti rezultatų pateikimą iki numatyto laiko, tokie faktoriai kaip sistemos atsako laikas ir galios sąnaudos gali pastebimai keistis, kai operacija pabaigiama, be to dažnai operacinė sistema praneša procesoriaus apkrovos lygį. Be to toks sulyginimas nulemia, kad visų operacijų vykdymo laikas bus lygus lėčiausios operacijos vykdymo laikui. Be to net jei visada bus atliekama R_i = (s_i ∙ y) mod n, tai vis tiek laiko charakteristikos gali būti atsektos iš kėlimo kvadratu operacijos, nes pakitus skaičiui jos vydimo laikas taip pat pakis.

Kitas kelias yra padaryti laiko matavimus tokiais netiksliais, kad ataka taptų neįmanoma. Atsitiktiniai vėlinimai pridėti prie skaičiavimo laiko gali padidinti atskaitų kiekį reikalingą sėkmingai atakai. Jų kiekis didėja apytiksliai laiko triukšmo kvadratu. Pavyzdžiui, jei standartinis moduliarinio kėlimo nuokrypis siekia 10 ms, tai pakanka 1000 matavimų, o pridėjus atsitiktinius normaliniu pasiskirstymu išsidėsčiusius nuokrypius su 1 sekundės standartiniu nuokrypiu jau reikės apytiksliai ((1000 ms)/(10 ms))^{2 (1000)= 10}7 atskaitų. 107 gali būti daugiau nei galės gauti įsibrovėlis, tačiau tai laikoma nepakankama patikimai saugumui užtikrinti.

Norint patikimiau apsisaugoti reikia naudoti technikas taikomas parašų paslėpimui (angl. blinding). Prieš duomenis paduodant į moduliariąją kėlimo laipsnių operaciją pasirenkama atsitiktinė pora (vi, vf) taip, kad v_f^(-1)=v_ix mod n. Prieš atliekant operaciją pirminiai duomenys padauginami iš vi (mod n), ir po operacijos rezultatas pataisomas padauginant iš v_f (mod n). Šis metodas veiksmingas tik kai neįmanoma atsekti minėtų operacijų pagal vykdymo laiką. Be to nors inversinio mod n operacija lėta, patartina generuoti kiekvieną kartą naują reikšmę, tik taip galima patikimai išvengti atakos galimybės. Efektyvus problemos sprendimo būdas vieną kartą pasirinkus porą sekantį kartą poros reikšmes kelti kvadratu ir naudoti gautas naujas reikšmes. Jei pirminė pora išlieka slapta atakuojantis negauna naudingos informacijos apie pradinius duomenis. Tačiau blogai įgyvendintas kėlimo laipsniu algoritmas teoriškai gali turėti pikus pasiskirstyme atitinkančius laipsnio rodiklio bitus, todėl net paslepiant pradinius duomenis tikimybė rasti raktą išlieka.

Naudota literatūra:

Paul Kocher ir kiti. Security As a New Dimension in Embedded System Design. DAC 2004, June 7–11, 2004, San Diego, California, USA. [Žiurėta 2013-03-25]. Prieiga per internetą: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.58.3009&rep=rep1&type=pdf

CategoryŽodis