TTY / Tietoturvallisuuden jatkokurssi / Harjoitustyö 2012 / Luonnosvaihe

Joonas Kangas

Kryptografisten piirien tehoanalyysi

Johdanto

Kryptografiset laitteet ovat osa jokapäiväistä toimintaa sirukorttien ynnä muiden muodossa, ja luotto niiden toiminnan salaisuuteen on korkea. Tehoanalyysihyökkäys on kuitenkin pitkälle kehittynyt ja erittäin tehokas tapa selvittää kryptografisten laitteiden avaimia. Koska tällainen tehoanalyysi saa tarvitsemansa tiedon laitteen toiminnasta sen normaalin toiminnan aikana tuota toimintaa tarkkaillen, on analyysin havaitseminen vaikeaa ja siltä suojautuminen vaatii piirivalmistajilta uusia lähestymistapoja. Tehoanalyysihyökkäyksen uhka on todellinen, sillä hyökkäys on mahdollista suorittaa nopeasti helposti saatavilla olevalla laitteistolla, hinnaltaan vain muutamista sadoista pariin tuhanteen euroon.

Tehoanalyysin perusteet

Kryptografinen laite käyttää salaista avainta sisäänmenevään informaatioon ja tuottaa ulostulevaa informaatiota. Näiden laitteiden protokollat suunnitellaan tyypillisesti sillä oletuksella, että sekä ulos ja sisään tuleva informaatio on kaikkien saatavilla, mutta muu tieto laitteen toiminnasta ja avaimista ei.

1.bmp

Kuva 1:Oletettu kryptografisen piirin toiminnasta saatava tieto [1].

Todellisuudessa laitteista saadaan kuitenkin muutakin informaatiota, esimerkiksi laitteen tehonkulutuksesta.

2.bmp

Kuva 2: Todellinen piirin toiminnasta saatava tieto [1].

Modernit cryptografiset laitteet perustuvat mikropiiriehin, jotka rakentuvat transistoreista, jotka toimivat jänniteohjattuina kytkiminä. Kun transistorin porttiin vaikuttava varaus muuttuu, muuttuu samalla transistorin läpi virtaava sähkövirta. Tämä sähkön virtaus kuluttaa tehoa ja samalla tuottaa sähkömagneettista säteilyä. Piirin tehonkulutuksen selvittämiseksi se kytketään sarjaan pienin resistanssin kanssa, jolloin tuon resistanssin yli olevan jännitteen mukaan voidaan laskea virta.

SPA ja DPA hyökkäykset yleisesti määritellään vaativan vähäisestä kohtalaiseen määrään tietotaitoa hyökkääjältä. Tarvittava laitteisto on tyypillisesti tietokone ohjelmistoineen sekä digitaalinen muistillinen oskilloskooppi. Sopivia oskilloskooppeja on laajasti saatavilla, ja sellaisen voi saada jopa alle 500$ [5] hintaan. Automatisoituna suojaamattomaan laitteeseen SPA hyökkäys voi olla lähes välitön ja DPA hyökkäys viedä muutamasta minuutista pariin tuntiin. Onnistuneella hyökkäyksellä hyökkääjä saa tyypillisesti selville laitteen käyttämät salaiset avaimet, tai voi käyttää DPA:ta patentoitujen kryptosysteemien takaisinmallintamiseen.

Tehoanalyysin menetelmiä

Tehoanalyysi voidaan jaotella eri menetelmiin sen yksinkertaisuuden perusteella. Yksinkertaisin menetelmä, Simple Power Analysis (SPA) perustuu tehonkulutusmittausten suoraan visuaaliseen analysointiin. SPA:lla voidaan saada selville tietoa laitteen toiminnasta sekä avaimesta. Monimutkaisempi menetelmä on Differential Power Analysis (DPA), jossa käytetään tehonkulutustiedon tilastollista analyysiä ja etsitään korrelaatiota tehonkulutuksen ja ennustusmallien välillä. Siinä missä DPA käsittelee yhden tapahtuman tietoja kerrallaan voidaan High-Order DPA:lla (HO-DPA) käyttää monimutkaisempia valintafunktiota datan korreloimiseksi usean eri operaation kesken.

Simple Power Analysis

SPA -hyökkäyksessä hyökkääjä suoraan analysoi järjestelmän tehonkulutusta. Kulutettu teho vaihtelee piirin suorittamien operaatioiden mukaan, ja suuret piirteet kuten DES kierrokset tai RSA operaatiot voidaan tunnistaa koska näiden operaatioiden vaativat toimet vaihtelevat suuresti operaation eri osissa. Tarpeeksi suurennettuna jopa yksittäiset käskyt voidaan erottaa.

Kuvassa 3 on tyypillisen sirukortin tehonkulutusmittaus kun se suorittaa DES operaatiota. DES:in 16 kierrosta ovat selkeästi nähtävissä.

3_1.bmp

Kuva 3: SPA-jälki kokonaisesta DES-operaatiosta [2].

Kuvassa 4 on suurennettuna tuon saman operaation toinen ja kolmas kierros. Tästä kuvasta on nähtävissä monia DES operaation yksityiskohtia, kuten esimerkiksi 28-bittiset avainrekisterit kierretään kerran toisella kierroksella (vasen nuoli) ja kahdesti kolmannella kierroksella (oikeat nuolet). Myös muita eroja kierrosten välillä on havaittavissa. Monet erotettavista yksityiskohdista ovat avaimeen ja laskennallisiin välittäjiin perustuvia, ehdollisista hypyistä johtuvia SPA-heikkouksia.

4_1.bmp

Kuva 4: DES-operaation kierrokset 2 ja 3 [2].

Kuvassa 5 on kaksi vielä suuremman resoluution mittausta, molemmissa 7 kellojaksoa 3.5714 Mhz taajuudella. Näistä ylemmässä tapauksessa suoritetaaan hyppykäsky kun taas alemmassa ei. Tästä aiheutuva ero on selkeästi nähtävilä 6. kellojakson kohdalla. Koska SPA voi paljastaa käytetyn käskyjonon, sitä voidaan käyttää rikkomaan kryptografisia toteutuksia, joissa käskyjono riippuu käsiteltävästä datasta.Kuvassa 5 on kaksi vielä suuremman resoluution mittausta, molemmissa 7 kellojaksoa 3.5714 Mhz taajuudella. Näistä ylemmässä tapauksessa suoritetaaan hyppykäsky kun taas alemmassa ei. Tästä aiheutuva ero on selkeästi nähtävilä 6. kellojakson kohdalla.

5.bmp

Kuva 5: Suuren resoluution SPA-jälki [2].

Koska SPA voi paljastaa käytetyn käskyjonon, sitä voidaan käyttää murtamaan kryptografisia toteutuksia, joissa käskyjono riippuu käsiteltävästä datasta, esimerkiksi

  • DES avaintaulu(key schedule): DES:issä lasketaan aina seuraavan kierroksen avaimet kiertämällä 28-bittisiä avainrekistereitä. Yleensä käytetään ehdollista hyppyä tarkistamaan kierretty bitti, jotta 1-bitit voidaan tunnistaa. Tästä seuraantuva tehonkulutusjälki on erilainen 1- ja 0-biteille, jos käskyjono on niille erilainen.

  • DES permutaatiot.

  • Vertailut.: Erojen löytyessä suoritetaan yleensä ehdollinen hyppy, josta aiheuu selkeä SPA-ominaisuus.

  • Kertojat.: Modulaarisia kertolaskuja suorittavat piirit vuotavat usein paljon tietoa prosessoitavasta datasta. Vuoto riippuu kertojan suunnittelusta, mutta korreloi usein muuttujien arvoihin tai Hamming painoihin

  • Potenssiinkorotukset.: Yksinkertainen modulaarinen potenssinkorotusfunktio kartoittaa koko exponentin suorittaen neliöönkorotuksen joka kierroksella, sekä ylimääräisen kertolaskun jokaisella exponentin ykkösbitillä. Tästä voidaan exponentti saada selville, jos neliöönkorotus- sekä kertolaskuoperaatiot käyttävät tehoa eri tavalla, kestävät eriävän ajan tai ovat koodilla erotettu.

Differential Power Analysis

DPA -hyökkäyksessä käytetään tilastollista analyysiä sekä virheenkorjaustekniikoita avainten selvittämiseksi. Periaate DPA:n takana on se, että tilastollinen korrelaatio tehonkulutusdatan sekä ennustemallien välillä antaa analysoijalle tietoa avaimesta. DPA on tehokas, koska sillä voidaan hyökätä tutkien avainta osa kerrallaan, ja siten pienentää etsintäalaa suuresti, esimerkiksi 2^128:sta 16*2^8:aan.

Teoria DPA:n takaa

DPA-hyökkääjä käyttää hypoteettista mallia kohdelaitteesta. Tämän mallin laatu perustuu hyökkääjän tietoihin. Mallia käytetään ennustamaan laitteesta käytettäviä sivukanavaulostuloja. Näitä ennustuksia vertaillaan tilastollisesti laitteen mitattuihin sivukanavaulostuloihin. Menetelmiä tähän tilastolliseen vertailuun ovat muiden muassadistance-of-mean testi ja korrelaatioanalyysi.

Korrelaatioanalyysissä mallilla ennustetaan suorituksen tietynhetkinen sivukanavavuoto, ja näitä ennustuksia korreloidaan todelliseen sivukanavavuotoon. Merkitköön t(i) i:ttä mittausdataa ja T mittausjoukkoa, p(i) ennustetta i:delle mittausdatalle sekä P ennustejoukkoa. Tästä saadaan

6_1.bmp

jossa E(T) on joukun T odotusarvo ja Var(T) varianssi. Jos tämä korrelaatio on korkea, voidaan olettaa ennustemallin, ja siten avainhypoteesin, olevan oikea.

Ennen tehoanalyysihyökkäyksen tekoa käytännössä, täytyy hoitaa muutama tekninen hankaluus. Yksi tärkeimmistä on mahdollisimman häiriöttömän mittausdatan hankinta. Mitä enemmän datassa on häiriöitä, sitä vaikeampaa tilastollinen analyysi sekä sitä enemmän dataa tarvitaan. Toisen käytännön haasteen muodostaa itse mittauslaitteiston hankinta. Tämä laitteisto koostuu tyypillisesti hyökättävästä laittteesta, jonkinlaisesta mittaustyökalusta, sekä työkaluista hyökättävän laitteen operointiin, kuten sirukortin lukijasta. Näiden lisäksi tarvitaan välineet laitteiden väliseen kommunikointiin. Koska tätä laitteistoa on kuitenkin jonkinlainen määrä, pitää ensin varmistaa että jos mittaus epäonnistuu, se ei johdu bugeista käytettävissä ohjelmissa tai laitteissa, vaan siitä että sivukanavavuoto ei ole tarpeeksi mittavaa. Siksi laitteiden testaus yleensä aloitetaan hyökkäyssimulaatiolla, jolla voidaan arvioida oikean hyökkäyksen vaativuutta.

Yksityiskohtainen selostus DPA hyökkäyksestä on liian laaja alue tähän tutkielmaan sisällytettäväksi, mutta kiinnostuneelle lukijalle on lähteissä [2] ja [7] laaja selitys ja todellinen hyökkäys DES sekä AES järjestelmiä vastaan.

Tehoanalyysiltä suojautuminen

SPA ja DPA hyökkäykset yleisesti kohdistuvat kryptografisiin tuotteisin laitteistolla tai sulautetuissa järjestelmissä, vaikkakin samantyyliset hyökkäykset sähkömagneettista säteilyä hyväksikäyttäen voidaan kohdistaa jopa ohjelmistoihin tietokoneissa. Järjestelmissä, joissa kryptogragfinen käsittely on vain pienessä osassa yleiseen tehonkulutukseen tarvitaan yleensä DPA:ta.

Kaikki kryptografiset algoritmit ovat alttiita SPA ja DPA hyökkäyksille. Tehoanalyysiä on onnistuneesti käytetty DESiä, AESia, SHAta, Diffie-Hellmania ja RSAta sekä monia muita algoritmeja vastaan.

SPA ja DPA hyökkäyksiä vastaan suojautuminen on kuitenkin hyvin mahdollista. SPA:lta suojautuminen on melko yksinkertaista. Salaisia välittäjiä tai avaimia ehdolliseen haarautumiseen käyttävien toimenpiteiden välttäminen piilottaa monia SPA ominaisuuksia. Joissain tilanteissa kuten haarautumista vaativissa algoritmeissa tämä voi vaatia luovuutta ja suorituskyvyn pudotusta.

SPA ja DPA hyökkäysmenetelmät löytänyt yritys Cryptography Research Inc on patentoinut joukon vastatoimia.

  • Vuotojen vähentäminen: Menetelmä saattaa operaatiojono avaimesta riippumattomaksi sekä laitteisto- ja ohjelmistotekniikoita vaihtelun vähentämiseksi tehonkulutuksessa vaihtelevaa dataa prosessoitaessa

  • Äänen lisääminen: Menetelmä monen tyyppisen äänen lisäämiseksi hyökkääjälle saatavissa olevaan tehonkulutusdataan

  • Tarkoituksen piilottaminen: Pitämällä algoritmin salassa hyökkääjä joutuu takaisinmallintamaan laitteen tehoanalyysin rinnalla

  • Satunnaisuuden lisääminen: Menetelmä laitteen käsittelemän datan sattunnaistamiseksi siten että silti saavutetaan oikea tulos, esimerkiksi peittämällä dataa tai käyttämällä satunnaisia viiveitä datapolulla.

  • Protokollatason vastatoimet: Protokollia muokataan siten, että salaisuuksia päivitetään jatkuvasti laitteen elinjakson aikana, suojellen niitä vuotamiselta.

Yhteenveto

Tehoanalyysihyökkäys on kryptografian saralla uusi keksintö. Hyökkääjältä vähän ammattitaitoa vaativana ja kryptografisten laitteiden jatkuvasti yleistyessä on sen merkitys kuitenkin korostunut nopeasti. Vaikka nopeaa SPA:ta vastaan puolustautuminen on helppoa ja yksinkertaisesti toteutettavissa, korkeamman asteen differentiaaliselta analyysiltä suojautuminen vaatii hankalia ja kalliita keinoja ja jopa uutta lähestymistapaa laitteiden sekä algoritmien suunnitteluun, millä otetaan huomioon kaikki laitteiden mahdollisesti vuotavat tiedot salausmateriaalsita sähkömagneettiseen säteilyyn. Uudet suojautumiskeinot ovat jatkuvan kehityksen aiheena yritettäessä pitää suorituskyky korkeana ja kustannukset hallittavissa rajoissa.

Lähteet

[1] Paul Kocher, Joshua Jaffe, Benjamin Jun: Introduction to Differential Power Analysis and Related Attacks [viitattu 28.11.2012]. Saatavissa http://www.cryptography.com/public/pdf/DPATechInfo.pdf

[2] Paul Kocher, Joshua Jaffe, Benjamin Jun: Differential Power Analysis [viitattu 29.11.2012]. Saatavissa http://www.cryptography.com/public/pdf/DPA.pdf

[3] Licensed Countermeasures [viitattu 29.11.2012] http://www.cryptography.com/technology/dpa/licensed-countermeasures.html

[4] Matthew Pierson, Bryan Brady: Low cost differential power analysis resistant crypto-chips [viitattu 29.11.2012]. Saatavissa http://www.eecs.berkeley.edu/~bbrady/documents/eecs244-presentation.pdf

[5] Christopher Kevorkian, Jacob Tanenbaum: Advanced Cryptographic Power Analysis [viitattu 28.11.2012] http://www.wpi.edu/Pubs/E-project/Available/E-project-122211-215512/unrestricted/Power_analysis.pdf

[6] DPA Countermeasures FAQ [vitattu 29.11.2012] Saatavissa http://www.cryptography.com/technology/dpa/dpa-qa.html

[7] Sidikka Berna Örs, Frank Gürkaynak, Elisabeth Oswald, Bart Preneel: Power analysis attack on an ASIC AES implementation [viitattu 29.11.2012]. Saatavissa web.itu.edu.tr/~orssi/papers/SBO-0306.pdf.gz

SivuTiedotLaajennettu edit

Vaativuus Jatko
Valmius Valmisteilla
Tyyppi Ydin
Luokitus Uhkat
Mitä Luottamuksellisuus
Miltä Tahallinen uhka
Missä Useita
Kuka Titu-ammattilainen
Milloin Ennakolta
Miksi Hyvä tapa
Topic attachments
I Attachment Action Size Date Who Comment
1.bmpbmp 1.bmp manage 272.7 K 01 Nov 2012 - 05:14 UnknownUser Crypto assumption
2.bmpbmp 2.bmp manage 397.7 K 29 Nov 2012 - 07:04 UnknownUser Crypto actual
3_1.bmpbmp 3_1.bmp manage 607.1 K 29 Nov 2012 - 07:29 UnknownUser SPA Des operation full
4_1.bmpbmp 4_1.bmp manage 627.3 K 29 Nov 2012 - 07:29 UnknownUser SPA DES round 2-3
5.bmpbmp 5.bmp manage 1097.3 K 29 Nov 2012 - 07:48 UnknownUser High resolution SPA trace with jump and no-jump
6_1.bmpbmp 6_1.bmp manage 38.1 K 29 Nov 2012 - 18:23 UnknownUser Correlation
Print version |  PDF  | History: r10 < r9 < r8 < r7 | 
Topic revision: r10 - 07 Dec 2012 - 10:30:57 - JoonasKangas?
 

TUTWiki

Copyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TUTWiki? Send feedback