Oppikerta 4, 2.2.1999

Allekirjoitus

• DA:n pitää riippua allekirjoitettavasta dokumentista sekä jostain tiedosta, joka on ja jonka tiedetään olevan vain allekirjoittajan hallussa.
• DA:n tuottamisen, tallettamisen, tunnistamisen ja tarkastamisen (todentamisen) pitää olla suhteellisen helppoa.
• väärentämisen pitää olla laskennallisesti mahdotonta: ei annettuun DA:een sopivaa uutta dokumenttia eikä annettuun dokumenttiin sopivaa DA:ta.

Harjoitus: 1) Missä määrin symmetrisen avaimen kryptauksella voidaan toteuttaa allekirjoituksen vaatimuksia?

2) RSA:lla on ominaisuus (ns. kommutatiivisuus), että yksityisellä eksponentilla salatun viestin voi purkaa julkisella eksponentilla. Miten tämä soveltuu viestin allekirjoittamiseen?

Ratkaisuna voidaan todeta, että 1) symmetrisyys on ristiriidassa kiistämättömyyden kanssa (Schneier esittää (s. 39) epäkäytännöllisen ratkaisun joka käyttää kolmatta osapuolta), ja 2) RSA on keskeisesti allekirjoitusalgoritmi:

Alkuperäisen RSA-artikkelin nimi (vuodelta 1978) oli "A method for obtaining digital signatures and public key cryptosystems". RSA:ta käytetään allekirjoitukseen siis toisinpäin kuin salaukseen, joka tapahtuu julkisella avaimella ja purku salaisella avaimella. Allekirjoitus muodostetaan salaisella ja se todennetaan julkisella avaimella: Vain se, joka tuntee salaisen eksponentin d, voi tuottaa viestistä m potenssin s=m^d mod n. Kun m ja s lähetetään yhdessä, kuka tahansa joka tuntee vastaavan julkisen avaimen e, voi tarkistaa että m = s^e mod n. Jos siis d on osapuolen A salainen avain, niin A ei voi kiistää allekirjoittaneensa ja lähettäneensä viestiä m - paitsi väittämällä että hänen avaimensa on paljastunut ... (tässä yhteydessä tarvitaan avaintenhallintaa, aiheeseen palataan myöhemmin).

RSA:n eksponenttilasku on hidas operaatio, minkä vuoksi yleensä vain viestin tiivistelmä allekirjoitetaan: lähetys on siis m, (H(m))^d mod n.

Harjoitus: Sovella RSA-allekirjoitusta Diffie-Hellman-avaimen vaihtoon. Oleta, että A ja B ovat kumpikin luoneet oman RSA-systeeminsä julkisilla parametreilla (e_A, n_A) ja (e_B, n_B). Vastaavat salaiset parametrin olkoot d_A ja d_B. Käytä DH-algoritmille aiemmin esitettyjä merkintöjä (n,g,x ja y).

Mahdollinen ratkaisu DH:n autentisointiin allekirjoituksilla: A:n viesti B:lle koostuu kolmesta osasta: nimet A ja B sekä luku (A,B,g^x)^d_A mod n_A. Osapuolen B viesti A:lle vastaava. (Lieneekö näissä jotain tarpeetonta?)

Viestien merkitys selviää, kun katsotaan, miten esim. B ratkaisee yhteisen avaimen g^xy saamastaan viestistä. Hän toteaa väitetyn lähettäjän olevan A ja siis korottaa viestin kolmannen osan potenssiin e_A modulo n_A. Tuloksena on luku, jonka binääriesityksestä B voi lukea (ja tarkistaa) nimet A ja B ja niiden jälkeen on bittijono X (=g^x mod n). Korottamalla X:n potenssiin y modulo n, B saa luvun g^xy mod n, joka on sama kuin se, jonka A saa vastaavalla algoritmilla. Olisiko joku muu voinut lähettää B:lle kyseisen viestin?

Kuten sanottua, vain se joka tuntee d_A:n on voinut alunperin tuottaa kyseisen viestin. Vastustaja C, joka on siepannut A:n lähettämän viestin joskus aiemmin, voi lähettää sen nyt uudestaan. Entäpä sitten: Jos C nyt sieppaa myös B:n viestin, mitä hän saa siitä irti? Ei mitään muuta kuin sen, että B:n tarkoitus on sopia avaimesta A:n kanssa. Tämä ei siis ole huolestuttavaa. Sen sijaan edelleen jää auki, onko B:n saaman viestin takana todella A kuten viesti väittää: Jospa C onkin sijoittanut oman julkisen avaimensa paikkaan josta B hakee A:n julkisen avaimen. Tällöin C voi näytellä A:ta allekirjoittamalla viestejä omalla salaisella avaimellaan. Autenttisuutta ei saavuteta, ellei julkisia avaimia hallinnoida jollain luotettavalla tavalla.

Jotta pääsisimme eteenpäin, meidän täytyy keksiä menetelmä, jolla julkiset avaimet voidaan sitoa omistajiinsa (ilmeisesti siis jonkinlainen allekirjoitus tässäkin). Lisäksi täytyy luoda mekanismi, jolla tällainen sidonta voidaan purkaa. Näitä tehtäviä kutsutaan avaintenhallinnaksi. Ennen kuin voidaan ajatella tiedon sitomista johonkuhun yksilöön, pitäisi oikeastaan pohtia yksilöinnin ongelmaa. Palataan tähän hetken kuluttua.

Otetaan nyt esille yksi monista tunnetuista DH-variaatioista, ns. Station-to-Station-protokolla. Siinä käytetään paitsi allekirjoituksia myös sopimisen kohteena olevaa symmetristä avainta heti kun se on mahdollista. A:n ensimmäinen viesti B:lle on kuten perus-DH:ssa (siis g^x) ja samoin on B:n viesti A:lle alkuosaltaan (siis g^y), mutta sen perään B liittää allekirjoituksen S_B (g^y, g^x) salattuna avaimella k = (g^x)^y. Kolmannessa viestissä A lähettää B:lle vastaavan allekirjoituksen S_A (g^x,g^y), salattuna k:lla.

Tässä S_X on osapuolen X allekirjoitusfunktio. Kumpikin osapuoli soveltaa sitä peräkkäin asetettuihin (katenoituihin) lukuihin. Kunhan kummankin osapuolen julkinen avain (allekirjoituksen todentamiseen) on autenttinen, STS-protokollalla saavutetaan molemminpuolinen yksilöinti ja lisäksi eksplisiittinen avaimen aitous (ts. kumpikin osapuoli tietää että toisella on sama avain k).

Harjoitus: RSA-algoritmin syötteen M pitää olla modulia n pienempi luku. Käänteisoperaatio näet tuottaa luvun M-k*n, missä k on sellainen, että tämä luku on 0:n ja n:n välissä. Mitä ongelmia tämä aiheuttaa tilanteessa, jossa halutaan ensin allekirjoittaa viesti omalla RSA-avaimella ja sitten salata se vastaanottajan avaimella?

Olion autentisointi, tunnistaminen

• se on jotain: eli ominaisuus on fyysinen kuten sormenjälki (biometriikasta voidaan kyllä keskustella, mutta se ei kuulu kurssiin).
• sillä on jotain fyysistä omistuksessaan, esim. toimikortti.
• se tietää jotain (esim. salasanan). Tällaisen tiedon pitäisi mieluimmin tietysti olla sellaista, ettei sitä tarvitse paljastaa ja silti voidaan vakuuttua sen olemassaolosta. Yksilöinnin keskeinen ominaisuus (ja vaatimus) on ajankohtaisuus: olio jota varten yksilöinti tapahtuu (eli verifioija) vakuuttuu myös siitä, että tunnistettava yksilö on aktiivinen samanaikaisesti. Yksilöinnin tärkeimpiä sovelluksia on pääsyn valvonta. Sisäänpääsy tuo sitten tyypillisesti mukanaan oikeutuksen käyttää resursseja sen mukaan, millainen autorisointi yksilölle on erikseen määritelty. Oikeuksien määrittely on keskeinen tietoturvallisuuteen vaikuttava tekijä, mutta se ei varsinaisesti enää kuulu protokollien yhteyteen, joten aihetta ei käsitellä tällä kurssilla.

  Salasanapohjainen autentisointi

  Kiinteät salasanat. Niiden (login-tyypistä) käyttöä kutsutaan myös heikoksi autentisoinniksi, mikä muistuttaa turvallisuuden tasosta. PIN kuuluu tähän kategoriaan, vaikka se useimmiten liittyykin johonkin omistettuun. Kiinteät salasanat eivät kuulu tämän kurssin aihepiiriin, vaikka niiden yhteydessä käytetäänkin yksisuuntaista funktiota (lasketaan salasanasta ja verrataan talletettuun arvoon, esim Unixin /etc/passwd-tiedostossa.)

  Kertakäyttöiset salasanat: esimerkkinä avainlukulistat pankkien puhelin- ja weppipalveluissa: palvelin kertoo monesko luku käyttäjän pitää kulloinkin tietää. Oleellinen ominaisuus on, että ulkopuolinen ei pysty ennustamaan seuraavaa lukua. Harjoitus: Listan sijasta voitaisiin käyttää yksisuuntaista funktiota f, jota käytetään "takaperoisesti". Oletetaan että käyttäjä on soveltanut f:ää n kertaa johonkin generoimaansa satunnaislukuun ja on ilmoittanut tuloksen palvelimelle jollain autentisoidulla tavalla. Miten hän voi tämän jälkeen osoittaa henkilöllisyytensä n kertaa? [DH-artikkeli, s 651; HAC, s 396; vrt. myös SKEY Schneier s. 53]

  Haaste-vaste-menetelmä (vahva autentisointi)

  Idea: Vieraalla on tiedossaan jokin salaisuus, jonka tietää myös isäntä (eli he ovat toisilleen tuttuja jotka ovat joskus sopineet salaisuudesta). Isäntä vakuuttuu tästä kysymällä epäsuoria kysymyksiä (haasteita), joihin vieras voi vastata paljastamatta salaisuutta. Toisaalta oikeita vastauksia ei voi tuottaa ilman salaisuutta. Kysymysten pitää olla sellaisia, ettei ulkopuolinen pysty useastakaan vastauksesta päättelemään salaisuutta.

  Harjoitus: Oletetaan, että titeläisillä olisi vaikkapa taskulaskimessaan salauskone, jolla he voisivat salata lyhyitä viestejä käyttäen esim. nykyistä unix-salasanaansa avaimena. Miten tämän avulla voitaisiin hoitaa sisäänkirjoittautuminen ilman, että (kerran saatua) salasanaa tarvitsee koskaan kirjoittaa päätteelle? Jos login-ohjelmaa muuttaa tämän verran, pitäisi toki tehdä lisämuutoksia: miten ylläpitäjältä saadun (tai muuten vanhentuneen) salasanan voisi vaihtaa uudeksi ilman, että tätä uuttakaan tarvitsee sellaisenaan kirjoittaa päätteelle? Edelleen: miten käyttäjä sisäänkirjoittautumisen jälkeen voisi varmistua siitä, että hän on siinä koneessa, jossa pitääkin? (Oletetaan, että käyttäjä ei olekaan titeläinen, jolla on hakemistonsa yms., vaan joku joka käyttää konetta vain surffailuun ja vaikkapa pankkitilinsä käsittelyyn.)

  Mahdollinen ratkaisu edellyttää, että salasana on selväkielisenä myös isäntäkoneen hallussa!

  Yleistys: edes isäntä ei tiedä salaisuutta, mutta voi silti vakuuttua, että vieras tietää! Tällaista sanotaan nollatietotodistukseksi, esimerkkinä katsotaan Feige-Fiat-Shamir-protokollaa [Schn:503-, HAC:408]. Merkitään:
  Y = vieras joka pitää Yksilöidä
  T = isäntä, joka haluaa Todentaa Y:n henkilöllisyyden

  Esitetään protokolla ensin yksinkertaisessa muodossa ja sitten harjoituksena "moninkertaistetaan" eli tietyllä tavalla rinnakkaistetaan. Aivan aluksi esitellään protokollan idea olettaen vain jokin yksisuuntainen funktio f, jolle pätee ns. morfismiominaisuus f(x*y)=f(x)*f(y).

  Protokollan tavoitteena on vakuuttaa T siitä, että Y tietää salaisen lukunsa s, jonka Y on valinnut ja laskenut siitä julkisen avaimensa v = f(s). Jotta T (eikä salakuuntelija) ei saisi tietää s:ää, Y ei koskaan lähetä hänelle itse s:ää vaan tulon u=r*s, missä r on satunnaisluku, josta Y on protokollan alussa kertonut T:lle arvon f(r). Jotta Y ei kuitenkaan voisi lähettää mitä tahansa, T pyytää Y:ltä satunnaisesti joko r:n tai s*r:n.

  Harjoitus: Miten T tarkastaa nämä vastaukset ja mikä on todennäköisyys että Y, joka ei tunne s:ää, läpäisee tarkastuksen?

  Vastaus: T käyttää vastaanottamaansa lukua u ja julkista avainta v. Tapaus "u=r": T laskee f:n arvolla r ja vertaa. Tapaus "u=s*r": T tarkistaa, onko f(u)= f(r)*v. Todennäköisyys on enintään 1/2. Ainoa, mitä Y voi tehdä, on yrittää ennakoida jompaakumpaa pyyntöä ensimmäisessä viestissään: miten Y voisi vastata "oikein", jos hän tietäisi että r*s:ää kysytään? Vastaus: Y valitsee jonkin z:n, lähettää aluksi arvon "f(r)" = f(z)/v ja vastaukseksi arvon "r*s" = z.

  Yksisuuntainen funktio, jolla on tarvittava (morfismi-)ominaisuus on neliöinti modulo n, missä n=p*q ja osapuolet Y ja T eivät tunne (suuria alkuluku)tekijöitä p ja q. (Vrt. Rabin; Y saisi tuntea ne, jos n olisi Y:n oma.) Tarvitaan luotettu välittäjä, joka valitsee luvut p ja q ja julkaisee niiden tulon n. Osapuoli Y valitsee satunaisluvun s ja rekisteröi julkiseksi avaimekseen luvun v=s² mod n.

  Itse protokollassa toistetaan seuraava m kertaa, kunnes 1/2^m on riittävän pieni vakuuttamaan T:n siitä että Y tietää s:n:

  1. Y valitsee satunnaisluvun r (<n) ja laskee luvun x = r² mod n ja lähettää x:n T:lle.
  2. T lähettää Y:lle satunnaisen bitin b.
  3. Jos b = 0, Y lähettää T:lle luvun r. Jos b = 1, Y lähettää T:lle luvun u = r*s mod n.
  4. Jos b = 0, T todentaa että x=r². Jos b = 1, T todentaa, että u² = x*v mod n.
  Tästä protokollasta voidaan todistaa, että T ei saa sen kautta mitään sellaista tietoa, mitä sillä ei ole ennestään (esim. käytännössä laskettavissa v:n ja n:n perusteella).

  Harjoitus Jos samalla kerralla liikkuisikin yhden sijasta k bittiä tarvittaisiin vain m/k kierrosta. Seuraava olisi suora yleistys edellisestä:

  1. Y muodostaa k:sta satunnaisluvusta koostuvan vektorin R ja lähettää T:lle lukujen neliöistä koostuvan vektorin.
  2. T lähettää haasteeksi k:sta bitistä koostuvan vektorin B.
  3. Y vastaa vektorilla U, jossa i:s komponentti on Ri*s^Bi mod n (eli em. protokollan mukainen).
  Todellinen Feige-Fiat-Shamir on kuitenkin toisenlainen yleistys. Siinä Y:n julkinen avain koostuu k:sta luvusta (v1,...,vk) ja salainen avain on vastaavasti (s1,...,sk). Jokainen pari (vi,si) on periaatteessa kuten edellä (tarkemmin kylläkin kukin vi on plus tai miinus 1/si² mod n, mutta unohdetaan tämä nyt). Osapuolen Y ensimmäinen viesti on kuten ennenkin, eli r² mod n. Haaste on k:sta bitistä muodostuva vektori ja Y:n vastaus siihen on yksi luku. Millainen mahtaisi toimia?

  Vastaus on, että vastaus on u = r*s1^B1*...*sk^Bk ja todennettava yhtälö on u² = x*v1^B1*...*vk^Bk.

  Avaintenhallinta

  Tämä aihepiiri päättää protokolliin tutustumisen ensimmäisen kierroksen ja aloittaa samalla seuraavan: Jatkossa siis käydään tarkemmin läpi useita muita perusprotokollia, mutta avaintenhallinnan kokonaisuuteen palataan tämän jälkeen vasta (käytännön) sovelluksissa, kuten erilaisissa julkisen avaimen infrastruktuurihankkeissa.

  Julkisen avaimen aitous

  Olemme jo nähneet, että keskeinen kysymys on julkisen avaimen saatavilla olo luotettavalla tavalla. Julkisten avainten jakeluun on periaatteessa seuraavanlaiset keinot (jotka tunnettiin jo 70-luvun lopulla, [Stal:182, vrt. myös HAC:555-556]:
  • Avaimen julkaiseminen lähettämällä se viestin mukana, www-sivulla tai uutisryhmässä jne.: ei mitään takeita aitoudesta. Harjoitus: Miten voisit puhelimen välityksellä varmistua jonkun tuntemasi henkilön avaimesta (1000-bittistä numeroa hänen ei kannata sanella)? Entäpä, jos et tunne häntä?
  • Julkisesti nähtävillä oleva avainhakemisto: luotettu osapuoli (T) ylläpitää, hakemistoon rekisteröidytään autentisoidulla tavalla (esim. paikan päällä), avainta voi vaihtaa, tietokanta tai sen muutokset julkaistaan ajoittain, avaimen haku kannasta autentisoidaan, esim. seuraavasti:
    T:llä on oma julkinen avain, jonka jokainen asiakas tuntee luotettavasti. Asiakas A, joka aikoo kommunikoida B:n kanssa, pyytää B:n julkista avainta hakemistosta ja saa sen viestissä, jonka T on kryptannut salaisella avaimellaan (yleisemmin: allekirjoittanut). Sitten A lähettää viestin B:lle, joka pyytää A:n julkisen avaimen ja saa sen T:ltä vastaavasti kuin A. Tämän jälkeen molemmilla on toisen osapuolen aito julkinen avain ja ne voivat suorittaa esim. symmetrisen avaimen vaihdon autentikoidusti.
  • Avainten sertifiointi: Jokainen asiakas luo oman julkisen avaimensa ja hakee sille (yksilöidysti) sertifikaatin varmenneviranomaiselta T, johon kaikki osapuolet luottavat. Varmenne koostuu asiakkaan nimestä ja julkisesta avaimesta, jotka T on allekirjoittanut.
  Julkisen hakemiston ongelmana on sen turvaaminen hyökkäyksiltä, sillä sen takana on kaikki. Lisäksi hakemisto on pullonkaula, vaikka asiakkaat säilyttäisivätkin toistensa julkisia avaimia jonkin aikaa. Varmenteet ratkaisevat jälkimmäisen ongelman, mutta T:n allekirjoitusavain on nytkin pidettävä täydellisessä turvassa. Ratkaistessaan yhden ongelman varmenteet tuovat toisen tilalle: vanhentuneet, ehkä jo paljastuneet avaimet pitää jollain tavoin peruuttaa. Voidaan esim. ylläpitää listoja käytöstä poistetuista avaimista, mutta näistä voi tulla uusia pullonkauloja, jos sertifikaatin voimassaolo halutaan aina tarkistaa!

  [Jatkuu...]

  ---

  Ensi kerralla pohditaan avaintenhallinnan jälkeen yleisesti autentisointia. Kertaa aiemmista artikkeleista (Margrave ja Diffie-Hellman), millaista autentisointia tarvitaan ja miten sitä toteutetaan.

  Pääaihe ensi kerralla on (autentisointi)protokollien suunnitteluperiaatteet. Aihetta käsitellään seuraavan artikkelin pohjalta: M. Abadi, R.Needham: Prudent Engineering Practice for Cryptographic Protocols, IEEE Trans. on Software Eng., Vol 22, No 1, Jan 1996, 6-15. (alunperin vuodelta 1994)