Export page to Open Document format View page as slide show

Tietoturva

Yksisuuntaiset tiivistefunktiot (hash funktiot)

  • one-way hash, message digest, tiivistefunktio, sormenjäljet, kryptografinen tarkistesumma, MIC
  • Luodaan määrittämättömän kokoisesta viestistä M, määrätyn kokoinen tiivistearvo h.
    • h=h(M)
  • Algoritmit ovat julkisia, ei avaimia
    • SHA-1, RIPEMD-160, MD5, whirlpool
  • Hash on yksisuuntainen funktio
    • tiivistearvo on helppo ja nopea laskea
    • Viestiä M ei pysty selvittämään tiivistearvosta.
    • Lautasten rikkominen
  • Funktioiden tulee olla törmäysvapaita (collision free)
    • On vaikea löytää arvo M' siten että H(M)=H(M')
      • hash on
    • On vaikea löytää arvoja M and M' siten että H(M)=H(M')
    • Syntymäpäivä paradoksi
      • 50% mahdollisuus että 23 ihmisen joukossa kahdella on sama syntymäpäivä

Hashin käyttö

  • Hashin avulla voidaan varmistaa viestin muuttumattomuus
  1. Haetaan koodinpätkä suomesta ja hash arvo tekijän kotisivulta
  2. Lasketaan koodinpätkästä hash
  3. Verrataan hasheja, jos ovat samat, koodi on alkuperäinen, jos erit, koodi on muuttunut
  • Salasanojen tallennus
    • Tallennetaan salasanasta hash, itse salasanan sijaan → salasanoja ei pysty selvittämään tiedostosta
  • Hasheja käytetään yhtenä osana erilaisissa tietoturvaprotokollissa.
    • Esimerkiksi osana digitaalista allekirjoitusta.

Hash turvallisuus

  • Hasheja murrettu viimevuosina
    • MD5 osoitettu oletettua heikommaksi crypto-2004 konferenssissa (samalla meni mm. RIPEMD)
    • SHA-1 osoitettu oletettua heikommaksi vuonna 2006
    • Avoin kilpailu käynnissä uudesta hash standardista
  • Syntymäpäivähyökkäys
    • Monta opiskelijaa tarvitaan luokkahuoneeseen, jotta on yli 50% mahdollisuus että jollain on sama syntympäivä kuin luennoitsijalla? 253
      • (355/356)^253 < 0.5
    • Entä jotta kahdella opiskelijalla olisi sama syntymäpäivä? 23 (muodostavat 253 erilaista paria)
    • Tarvitaan keskimäärin 2^{n/2} viestin generointia, jotta löydetään kaksi erilaista viestiä jotka tuottavat saman hashin.
      • Tietokone joka laskee miljoona tiivistearvoa sekunnissa pystyy toteuttamaan tämän tunnissa 64-bittiselle tiivistearvolle.
      • Tapauksissa joissa syntymäpäivä hyäkkäys on potentiaalinen uhka, tarvitaan kaksi kertaa pitempi hash kuin muuten. (Mieti tilanne jossa näin ei ole?)

Esimerkki hyökkäys

  1. A luo kaksi sopimusta. Toisessa sovitaa että B saa rahaa toisessa että B maksaa rahaa.
  2. A tekee pieniä muutoksia molempiin dokumentteihin (lisää välilyöntejä, tyhjiä rivejä jne.) ja luo näin suuren määrän variaatioita sopimuksista.
  3. A laskee tiivistearvot sopimuksista kunnes löytää kaksi eri sopimusta jotka tuottavat saman tiivisteen.
  4. A tallentaa löydetyt dokumenti
  1. A lähettää B:lle allekirjoitettavaksi sopimuksen jossa B saa rahaa. (protokolla jossa allekirjoitus toteutetaan tiivisteelle) )
  2. Allekirjotuksen saatuaan A vaihtaa sopimukseksi version jossa B on maksaja.
  3. Later A switches the documents and claims in court that B signed the document, which drives B to bankrupt.
    • Attack can be prevented by making small change (e.g. adding space) in the document before calculating hash and signing it.

Yleinen malli tiivisteen laskuun

  • Jaetaan viesti lohkoihin
  • Syötetään lohko tiivistefunktiolle edellisen lohkon tiivisteen kanssa
    h_{i}=f(M_{i},h_{i-1})
  • Tulos viimeisen lohkon jälkeen on koko viestin tiiviste.
  • Jos tiiviste on liian lyhyt sitä voidaan pidentää
  1. Luo tiiviste tiivistefunktiolla
  2. Yhdistä laskettu tiiviste viestin alkuun.
  3. Laske uusi tiiviste yhidstetystä viestistä
  4. Yhdistä tiiviste arvot
  5. Toista kunnes saat halutun kokoisen tiivisteen.

MD5

  • Ron Rivest kehitti vuonna 1992
    • perustuu MD4:n.
  • RFC 1321
  • Tuottaa 128-bittisen tiivisteen viestistä.
  • Viesti jaetaan 512-bitin lohkoihin jotka ajetaan vuorotellen tiivistefunktion läpi.
    • Viesti täydennetään niin että sen pituus n on n\: mod\:512=448
      • Täydennys tehdään lisäämällä 1 ja sen perään tarvittava määrä nollia.
    • Loppuun lisätään 64 bittinen arvo joka ilmoittaa viestin mitan. (448+64 = 512)
      • Tiivistettävä arvo on siis k*512 bittiä.
  • Alustus
    • Alustetaan neljä 32-bittistä ketjutusmuuttujaa (chaining variable, CV) (CV) A,B,C,D

      A=0x01234567

      B=0x89ABCDEF

      C=0xFEDCBA98

      D=0x76543210
  • MD5 operaatio
    • Tiivistys funktoi (512 bittiä sisään, 128 bittiä ulos)
      • A,B,C,D Kopioidaan muuttujiin a,b,c,d
      • 512-bitin lohko jaetaan 16 32 bitin alilohkoon.
      • Pääsilmukka koostuu neljästä kierroksesta(F,G,H,I).
  • Joka kierroksella seuraava funktio ajetaan 16 kertaa
    a\leftarrow b+((a+g(b,c,d)+M_{i}+T_{i})<<<s
  • a,b,c,d ovat aiemmin mainitut muuttujat a,b,c,d , jotka vaihtavat paikkoja joka kierroksella (4 arvoa, 16 eri kombinaatiota, 16 kierrosta)
  • i on nykyinen kierros
  • T_{i} on kokonaisluku osa funktiosta 2^{32}*abs(\sin(i)) , jossa i on radiaaneina
  • M_{i} on i:s 32-bitin alilohko
  • s ilmoittaa shiftausten määrän, joka riippuu kierroksesta (1-16) ja pääsilmukan kierroksesta (1-4)

    s[0..15]=[7,12,17,22,7,12,17,22,7,12,17,22,7,12,17,22]

    s[16..31]=[5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20]

    s[32..47]=[4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23]

    s[48..63]=[6,10,15,21,6,10,15,21,6,10,15,21,6,10,15,21]
  • Funktio g riippuu kierroksesta.
    F(X,Y,Z)=(X\wedge Y)\vee((\neg X)\wedge Z)

    G(X,Y,Z)=(X\wedge Z)\vee(Y\wedge(\neg Z))

    H(X,Y,Z)=X\oplus Y\oplus Z

    I(X,Y,Z)=Y\oplus(X\vee(\neg Z))
  • Analyysi funktioista F,G and H:
    • F on if funktio (if b, then c else d) (b?c:d)
    • G on myös if funktio (d?b:c)
    • H tuottaa pariteetti bitin
  • 4 kierroksen jälkeen muuttujat a,b,c,d lasketaan yhteen ketjutusmuuttujien A,B,C,D kanssa yksitellen ja tuloksista otetaan modulus 2^{32}
    • A=(A+a)\: mod\:2^{32} , B=(B+b)\: mod\:2^{32} , C=(C+c)\: mod\:2^{32} , D=(D+d)\: mod\:2^{32}
  • Tämän jälkeen otetaan seuraav 512-bitin lohko käsittelyyn.
    • Lopullinen tiiviste on A,B,C,D toisiinsa liitetynä (4*32bit = 128-bit hash)

MD5 Ominaisuuksia

  • Jokaisella kierroksella on omat vakiot
  • Jokainen askel vaikuttaa seuraavaan askeleeseen →lumivyöryefekti
    • yhden bitin muutos alkuperäisessä tekstissä vaikuttaa koko tiivisteeseen, ei vain yhteen bittiin.
  • Perusoperaatioiden usean läpikäynnin johdosta on epätodennäköistä että kaksi satunnaista viestiä tuottaa saman tiiviste arvon.
  • Usean eri perusoperaation käyttämisen johdosta on epätodennäköistä että kaksi satunnaista viestiä tuottaa saman tiiviste arvon.
  • MD5:den tiivistysalgoritmista on löydetty heikkouksia jotka voivat aiheuttaa törmäyksiä.
  • crypto 2004 konferenssissa julkistettiin tutkimustulos joka osoitti heikkouksia MD5:ssä (http://www.schneier.com/essay-074.html)
    • Sama ongelma koskee myös vastaavia SHA-0 ja RIPEMD160 algoritmeja

SHA-1

  • SHA-1 is and algorithm developed by NSA for DSS (Digital Signature Standard) and is thus the algorithm of SHS (Secure Hash Standard)
  • SHA-1 is based on MD4 algorithm (as was MD5) developed by Ron Rivest at 1990.
  • Maximum message length for SHA-1 is 2^{64} bits from where SHA-1 provides 160-bit hash value
  • SHA-1 vs MD5
    • SHA-1 uses five vectors where MD5 used 4 (128+32 = 160)
    • SHA-1 has 4*20= 80 rounds while MD5 had 4*16=64 rounds
    • SHA-1 bit functions are slightly different

Security of SHA-1

  • Compared to MD5
    • The hash size of SHA-1 is 32 bits longer and is thus more resistant for brute-force attacks
      • SHA-1 is slightly slower and requires bit more memory(more rounds, longer vectors to get 160 bit hash)
    • SHA-1 uses input bits more often in during the hash function than MD5
  • On February 15th, 2005 Bruce Schneier stated on his blog:
    “SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing. The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper announcing their results:
    • collisions in the the full SHA-1 in 2^{69} hash operations, much less than the brute-force attack of 2^{80} operations based on the hash length.
    • collisions in SHA-0 in 2^{39} operations.
    • collisions in 58-round SHA-1 in 2^33 operations.”

Whirlpool

  • Lohkosalaimeen perustuva tiivistefunktio (http://www.larc.usp.br/~pbarreto/WhirlpoolPage.html)
    • Käyttää W lohkosalainta joka perustuu AES:ään.
      • W on erityisesti suunniteltu tiivistefunktioissa käytettäväksi
  • Noudattaa Miyaguchi-Preneel:in yksisuuntaisten tiivistefunktioiden periaatetta.
    • Seuraava lohko salataan hyödyntämällä edellisen lohkon salauksentulosta avaimena sekä XOR:lla se salattavan lohkon kanssa.
      H_{i}=E_{H_{i-1}}(m_{i})\oplus H_{i-1}\oplus m_{i}
  • Tuottaa 512-bittisen tiivistearvon
    • Lohkon koko W:ssä on 512-bittiä
  • On osoitettu turvalliseksi tunnetuja lohkosalaimiin perustuvien tiivisteiden uhkia vastaan.
    • Lohkosalaimet eivät tuota kunnollista satunnaisuutta (ne on suunniteltu niin että salaustulos voidaan palauttaa), joka voi luoda heikkouksia
    • Lohko salaimet ovat hitaita tiivisteisiin verrattuna.
      • W on suunniteltu normaaleja lohkosalaimia nopeammaksi
    • Lohkosalaimissa on pienehköt lohkot jonka johdosta hash on lyhyt
      • Normaali lohkon koko lohkosalaimessa on 64 tai 128 bittiä, W.ssä 512
  • NESSIE (New European Schemes for Signatures, Integrity and Encryption) tukee
    • Osana ISO 10118-3 standardia
  • Vuonna 2009, esiteltiin hyökkäys jolla saadaan aiheutettua törmäyksiä rajoitetuilla kierroksilla.
    • W algoritmissa normaalisti 10 kierrosta (vrt. DES 16)

Tiivistefunktioiden nykytila

  • Kaikki MD5 tyyppisten tiivistefunktioiden turvallisuus on kyseenalainen.
    • Täyttä murtoa ei le tehty, mutta vahvuus ei vastaa suoraan hashin kokoa eli on olemassa raakaa voimaa nopeampi keinoja hyökätä hashia vastaan.
  • NIST avasi kilpailun uudesta standardista (sha-3) marraskuussa 2007
  • Keccak valittiin SHA-3 algoritmiksi 2.10.2012
    • Kehittäjät Guido Bertoni, Joan Daemen (joka oli mukana kehittämässä myös AES (Rijndael) algoritmia), Michaël Peeters and Gilles Van Assche.

Viestin autenttisuuskoodi (MAC)

  • Avaimellinen tiivistearvo
    • Message authentication code (MAC)
  • Annetaan funktiolle syötteeksi koko viesti ja avain, tuloksena MAC
    • MAC=f_{K}(M)
  • MAC avaimen paljastuttua MAC vastaa hash tiivistettä.
  • MAC ei salaa itse viestiä, vaan sen voi lukea kuka vain.
    • Avainta ei tarvitse jakaa kaikille, joilla on tarve päästä tietoon käsiksi.
  • Hyvä kesto raa'an voiman hyökkäyksiä vastaan.

MAC käyttö

  • MACin avulla voidaan varmistaa vaihdetun viestin eheys ja autenttisuus
    • Viestin saavuttua, lasketaan siitä itse MAC salaisella avaimella ja verrataan viestin mukana tulleeseen MAC:iin
    • MACia ei voi luoda kuin avaimen tunteva henkilö
  • MACin avulla voidaan varmistaa talletetun tiedon muuttumattomuus
    • Talletetaan tieto ja siitä laskettu MAC tietokantaan
    • Haettaessa tieto lasketaan MAC ja verrataan sitä kannassa olevaan MAC:iin
    • MACia ei voi muuttaa tietämättä avainta
  • MAC ei toimi allekirjoituksena
    • kuka tahansa avaimen tuntija voi laskea MAC:n
    • MAC:n tarkistamista varten on avain luovutettava

CBC-MAC

  • Helpoin tapa tuottaa MAC on salata hash arvo symmetrisellä salaimella E_{k}(H(M))
  • Toinen helppo tapa on käyttää lohkosalainta CBC-moodissa
    • Viestin viimeisen lohkon salauksen tulos on MAC-arvo.
  • Algoritmia voi vahvistaa salaamalla viimeisen arvon vielä toisella avaimella.
  • CBC-moodin käytön johdosta viestin jokainen bitti vaikuttaa lopulliseen tiivistearvoon.
    • Yhden bitin muutos viestissä muuttaa koko tuloksen

HMAC

  • Luodaan MAC lisäämällä kryptografinen ominaisuus hash-funktioon
    • Hash-funktiot ovat nopeampi kuin lohko-salaimet
  • Suunnittelu perusteet.
    • Käyttää olemassaolevia hash-funktioita
    • hash-funktio tulee olla helppo vaihtaa tarvittaessa.
    • hash funktion suorituskyky pitää säilyä
    • helppo käyttää ja yksinkertainen avaimen käsittely
    • Todistettava turvallisuus.
  • HMAC(K,m) = H((K \oplus opad) || H((K \oplus ipad) || m))

HMAC Algoritmi

  1. Avain K laajennetaan lisäämällä nollia vasemmalle niin että uuden avaimen K^{+} koko on b bittiä.
    • b on hashin lohkon koko.
  2. XOR K^{+} ipad:in kanssa (ipad on 00110110 toistettuna b/8 kertaa). tuloksena siis b bittiä pitkä lohko S_{i}
  3. Yhdistä M ja S_{i}> (S_{i} viestin alkuun)
  4. Aja tulos hash funktion H läpi.
  5. XOR K^{+} opadin kanssa (opad on 01011010 toistettuna b/8 kertaa). Tulos on b-bittiä pitkä S_{o}
  6. Yhdistä kohdan 4 tulos (täydennä tarvittaessa b bittiin) S_{o}:n kanssa (S_{o} liitetään alkuun)
  7. Aja tulos kohdasta 6 hash funktion läpi saadaksesi MAC arvon
  • Ipad:n ja opad:n käyttö luo kaksi erilaista avainta alkuperäisestä avaimesta K.
  • hash-funktion käytöstä johtuen molemmat avaimet vaikuttavat satunnaisesti lopputulokseen.
    • ipad ja opad kumpikin vaihtavat puolet alkuperäisen avaimen biteistä, joten tehdyt avaimet ovat pseudosatunnaisia.
  • Pitkillä viesteillä algoritmi on vain hieman tavallista hashia hitaampi
    • With long messages the algorithm is just slightly slower than the used hash function
    • Kolme ylimääräistä hash funktion ajoa (S_{i} askeleessa 4, S_{o} askeleella 7 sekä itse hash askeleessa 7)

Nopeampi HMAC

  • S_{i} ja S_{o} on laskettu etukäteen ja ajetaan tiiviste funktion läpi.
  • tiivistettyä S_{i} käytetään IV:n hash funktiossa.
  • Hash tulos täydennetään b bittiin ja ajetaan tiviistefunktion läpi käyttäen tiivistettyä S_{o} IV:nä
  • Ainoastaan yksi tiivistys kierros enemmän verrattuna normaali tiivisteeseen.
    • S_{i} ja S_{o}tiivistys tarvii toteuttaa vain kun avain vaihdetaan.
  • Voidaan todistaa että turvallisuus on suoraan riippuvainen hash-funktiosta.
Last modified: 2013/07/01 14:42