Timing attack on MAC verification

Žodis angliškai

Žodis Lietuviškai

Laiko ataka MAC patvirtinime

Paaiškinimai

Teorija:

Hash funkcija

Tai algoritmas kuris iš kintamo ilgio duomenų bloko įėjime gauna pastovaus dydžio bitų eilutę išėjime. Pagrindinė „Hash“ funkcijos savybė yra, didelė tikimybė, kad pakeitus duomenis, pasikeis pati „Hash eilutė.

„Hash“ funkcija pasižymi šiomis savybėmis:

· Ją galima lengvai suskaičiuoti bet kokiam duotam duomenų blokui

· Neįmanoma atkurti duomenų bloko žinant tik „hash“ eilutę.

· Neįmanoma modifikuoti duomenų nemodifikuojant „hash“ eilutės.

· Labai maža tikimybė, kad du duomenų blokai turės tą pačią „hash“ eilutę.

MAC (Message Authentication Codes) - pranešimo autentifikavimo kodas

Tai trumpas informacijos kiekis skirtas autentifikuoti pranešimą ir užtikrinti jam vientisumą bei tikrumą. Vientisumo užtikrinimas aptinka atsitiktinius ir tikslinius pranešimo pakitimus, o tikrumo užtikrinimas patvirtina pranešimo kilmę. Iš esmės MAC yra mažo pastovaus dydžio duomenų blokas kuris gaunamas iš kintamo ilgio pranešimo bei rakto. Jei pranešimą žymėsime „P“, o raktą „R“ tai MAC galime apibrėžti kaip „P“ ir „R“ kriptografine kontroline suma: MAC = K(R, P).

Jei vartotojas A nori siųsti pranešimą „P“ vartotojui B ir apsaugoti jį MAC, visų pirma jie turi pasidalinti slaptu raktu „R“. Tada A suskaičiuoja MAC kaip „P“ ir „R“ funkcija ir siunčia pranešimą bei suskaičiuota MAC vartotojui B. B taipogi atlieka skaičiavimus pasinaudojąs slaptuoju raktu „R“ ir gautuoju pranešimu „P“ ir gauna savo MAC‘. Jeigu gautas MAC ir suskaičiuotas MAC‘ sutampa, galima daryti prielaidą, kad pranešimas autentiškas.

HMAC – MAC sudarytas iš „hash“ funkcijos ir kriptografinio rakto.

Ataka:

Atibūdinti ataka galima pavyzdžiu. Tinkamas pavyzdys būtų „Keyczar“ kriptografijos biblioketa parašyto „Python“ kalba. Supaprastinta kodo ištrauka:

def Verify (key, msg, sig_bytes):

return HMAC(key, msg) == sig_bytes

(sig_bytes – (signature bytes/tag bytes)

Veikimo principas, gavus pranešimą yra suskaičiuojamas HMAC pasinaudojant „key“ ir „msg“ vertėmis ir palyginama su sig_bytes reikšme, Abiejų kintamųjų dydis 16 baitų. Tačiau atkreipus dėmėsį į kodą galima pamatyti kaip yra atliekamas palyginimas: „==“. „Python“ interpretatorius tokį palyginimą atliekamas ciklu, kuris vykdomas lyginant kintamuosius pabaičiui. Taigi kai tik kompiliatorius randą pirmąjį neteisingą baitą, procesas panaikinamas. O tai leidžia pritaikyti laiko ataką.

Taigi turim serveri kuris turi raktą „R“ ir piktavalį, kuris siunčia pranešimą „P“ su tam tikru sugalvotu HMAC‘o „tag“.

Taigi piktavalis savo ruoštu siunčia sukurtąjį pranešima „P“ kartu su „tag“, o serveris patikrina ar atsiųstas „tag“ yra teisingas ir jei ne siunčia klaidos pranešimą. Taigi piktavalis pastoviai siunčia užklausas į serveri naudodamas tą patį pranešimą „P“, tačiau kaskart keisdamas „tag“ reikšmę. Taigi pirmiausia piktavalis nusiunčia atsitiktinę užklausą ir matuoja kiek laiko serveris užtrunka pateikti atsakymą. Toliau jis siunčia „tag“ kurio pirmas baitas vis kitoks ir žiūri kada serveris užtruks truputi ilgiau prieš atsiųsdamas atsakymą. Taip jis sužino kada pirmas bitas yra teisingas. Toliau procesas kartojamas, tik jau su antruoju baitų. Taip pabaičiui piktavalis gali sužinoti visą „tag“, ir serveris priims piktavalio pranešimą.

Žinoma tokiai atakai yra sukurti veiksmingi gynybos budai:

Vienas iš jų – tikrinti ar atsiųstas „tag“ yra tinkamo ilgio, bet naudoti palyginimo funkcija kuri duomenis lygina blokais (pvz. po 16 baitų. ) Kitas – nuslėpti kurie baitai yra lyginami, tai galima padaryti naudojant dviguba HMAC funkcija.

Literatūra

1. http://en.wikipedia.org/wiki/Cryptographic_hash_function

2. http://en.wikipedia.org/wiki/Message_authentication_code

3. Stanford University online Cryptography course