83593: Oppikerta 11, 30.3.1999

Oppikerta 11, 30.3.1999

Tämän kerran aiheet: Monen osapuolen laskenta, salaisuuden jakaminen, liikkuvan koodin tietoturva, SSH-demonstraatio.

Monen osapuolen laskenta (secure multiparty computation)

Tilanne: n osapuolta ja n:n muuttujan funktio (esim. n:n bitin konjunktio) Funktion arvo halutaan laskea siten, että jokainen osapuoli antaa arvon "omalle" muuttujalleen, mutta kukaan ei saa tietää muiden arvoista muuta kuin sen, mitä tuloksesta voisi muutenkin päätellä. (Jos esim. konjunktio = 1 silloin kaikkien muuttujien arvo on ollut 1.)

Lisäksi halutaan tietenkin, että funktion arvo on oikein, mutta tämä voi olla suhteessa vain siihen, minkä arvon kukin syöttää. Jos esim. osapuolet haluavat laskea keskimääräisen ikänsä tai palkkansa, mikään ei estä(ne) ketään valehtelemasta.

Funktio toimii vähän niinkuin "automaattinen vaaliuurna": syötteenä ovat vaaliliput, ja uurna laskee vaalituloksen näyttämättä lippuja kenellekään. Tarkoituksena siis on, että laskenta voitaisiin suorittaa ilman luotettua osapuolta. Siis senkään vertaa tietoa muuttujista ei saa paljastua, kuin ääntenlaskija saa tietoa vaalilipuista. (Jos siis esim. konjunktio = 0, tiedetään vain, että ainakin yksi muuttuja on 0, ei sitä, kuinka moni.)

Sovelluksia: (1) Huutokauppa. (2) Salainen äänestys, jossa äänillä voi olla muitakin painokertoimia kuin 1 ja joillakin äänestäjillä eritasoisia veto- ja "vasta"-veto-oikeuksia (siis esim. niin että veto ja vasta-veto kumoavat toisensa). Tällaisessa sovelluksessa ei tarvitse huolestua valehtelemisesta, mutta tuloksen oikeellisuus voi olla hyvinkin kriittinen.

Protokollan täytyy sietää huijareita. Tyypillinen teoreettinen tulos on sellainen, että laskenta voidaan suorittaa turvallisesti, jos enintään kolmasosa "pelaajista on hyökkääjiä" (eli ovat esim. jonkin ulkopuolisen tahon korruptoimia). Yleiset protokollat ovat hyvin mutkikkaita. Seuraavassa on yksi yksinkertainen esimerkki (Yao, vuodelta 1982, [Schn:551]), ja sekin aluksi hieman pelkistettynä.

Oletetaan että A:n syöte on i ja B:n on j, ja kumpikin on väliltä 1..100. Funktiona on vertailu: onko i suurempi kuin j ?

A --> B: E(x,i)
x on satunnaisluku ja E on tietty funktio, joka sisältää salausta B:n julkisella avaimella.
B ei saa selville x:ää eikä i:tä, mutta pystyy valitsemaan alkuluvun p ja muodostamaan lukujonon z₁, ..., z₁₀₀ siten, että z_i on kongruentti x:n kanssa modulo p.
B --> A: z₁,...,z_j, z_j+1+1,..., z₁₀₀+1, p
Harjoitus: Miten A saa selville vertailun tuloksen? Kertooko A sen B:lle?

Vastaus: A tarkistaa onko i:s hänen saamansa luku kongruentti x:n kanssa modulo p: jos näin on, i on enintään j, muuten i on j:tä suurempi.

Tarkennukset:

E := E(x,i) = K_B(x) - i, missä K_B on B:n julkinen avain.
z_u = K_B^-1( E +u) modulo p, u=1,...,100. Tässä p on valittu niin, että se on muutamalla kertaluvulla x:ää pienempi (A on kertonut x:n bittimäärän) ja kaikki z_u:t eroavat toisistaan vähintään kahdella eikä mikään ole 0. (Valitaan uusi p kunnes näin on.)

Salaisuuden jakaminen

Sähköisen käteisen protokollassa asiakkaan tunnistustieto jaettiin kahteen osaan, joiden XORina se saatiin. Kumpikin osa sinänsä oli hyödytön. Ensimmäinen osahan valittiin satunnaisesti ja toinen laskettiin sen ja tunnistustiedon XORina. Kumpikin osa sellaisenaan siis oli täysin satunnainen bittijono. Tässä oli kyseessä salaisuuden halkaiseminen, 'secret splitting', joka voidaan XORin avulla suoraan yleistää ja paloitella salaisuus n osaan. Harjoitus: Miten?

Toisenlainen yleistys on salaisuuden jakaminen n osaan, joista mitkä tahansa k riittävät sen palauttamiseen, mutta mitkään k-1 eivät. Toimituksen nimitys on 'secret sharing' ja sen toteuttavaa protokollaa kutsutaan (k,n)-kynnyskaavioiksi (threshold scheme).

Sovellus: avainten varmuustallennus. Turvallisuus avaimen häviämisen varalta on sitä parempi mitä useammassa (=n) paikassa tietoa avaimesta on. Toisaalta tiedon levittäminen ei (paljonkaan) lisää avaimen paljastumisen todennäköisyyttä (sillä tarvitaan k kpl paljastumisia).

Toisenlaisia sovelluksia: salaisuus voi liittyä allekirjoitukseen, pankkiholvin avaamiseen tai johonkin vastaavaan toimeen, johon tarvitaan useamman tahon yhtäaikainen suostumus, mutta ei kaikkia mahdollisia osapuolia. Lisäksi eri henkilöillä voi "osavaltuutusta" olla eri määrä esim. virka-aseman perusteella. Tällaisissa sovelluksissa ei oikeastaan saisi olla ketään osapuolta, joka tietää koko salaisuuden. Tähänkin on protokollansa, mutta tässä oletamme tahon, jolta salaisuus on lähtöisin.

Yleisesti salaisuuden jakamisella osapuolten P kesken voidaan tavoitella sitä, että tietyt P:n osajoukot saavat sen yhdessä selville mutta tietyt osajoukot eivät. Luonnollista on olettaa että tällainen osajoukkoperhe on monotoninen eli jos joukko A kuuluu siihen, samoin kuuluu jokainen A:n ylijoukko (eli sellainen josta A on osa). Voidaan kuitenkin kehitellä sellaisiakin ratkaisuja, jotka muistuttavat äänestystä: Salaisuus ei aukea jos esim. liian moni vastustaa sitä.

Salaisuuden yhteinen selvittäminen muistuttaa etäisesti myös monen osapuolen laskentaa, poissaolijoiden argumenttien arvoja voitaisiin ajatella vaikka nolliksi. Erona on se, että nyt argumentteja ei tarvitse pitää salassa, kun toimitus suoritetaan, ja funktiolla on vain kaksi arvoa: salaisuus aukeaa tai sitten ei. Kaiken lisäksi salaisuus on alunperin jo ollut jonkin luotetun osapuolen tiedossa. Asiayhteydellä on toinenkin puoli: jaetuilla salaisuuksillakin voidaan nimittäin laskea. Tuloskin on sitten salaisuus, joka on jaettu osapuolten kesken. Kahden (salaisuuksina) jaetun luvun tulon laskemisesta on alle kahden sivun mittainen hyvinkin ymmärrettävissä oleva esitys: [Gennaro & al.: 1998, 22 PS-sivua] sivuilla 5 ja 6. Siinä käytetään seuraavassa harjoituksessa esille tulevaa polynomimenetelmää.

Harjoitus: Keksi kaksi erilaista periaatetta (k,n)-kynnyskaavion toteuttamiseksi lähtien seuraavista tutuista seikoista (kuten ilmeisesti tekivät Blakley ja Shamir vuonna 1979, toisistaan riippumatta):

Kolmiulotteisen avaruuden kaksi tasoa määräävät (yleensä) suoran ja kolme tasoa pisteen.
Jos tiedät toisen asteen polynomin arvon kolmessa pisteessä, voit laskea polynomin kertoimet.

Vastaus on ilmeinen (eikä sitä kannata kirjoittaa tähän senkään takia, että se löytyy tiiviisti esitettynä Berliinistäkin). Käytännön toteutukset täytyy vain muodostaa diskreettiin avaruuteen eli käyttää modulaarista aritmetiikkaa. Keskeinen ero näissä kahdessa periaatteessa on se, että ensimmäisessä epätietoisuus salaisuudesta vähenee sitä mukaa kun uusia osatietoja tuodaan laskentaan; tasohan kertoo pisteestä enemmän kuin koko avaruus, kahden tason leikkaussuora vielä enemmän. Jos jälkimmäisesssä menettelyssä joku saa haltuunsa enintään k-1 osatietoa, tilanne on informaatioteoreettisessa mielessä yhtäpitävä sen kanssa, ettei hänellä olisi osatietoja lainkaan.

Yksi polynomimenetelmän hyvistä ominaisuuksista on se, että n:ää voi kasvattaa myös jälkikäteen (k on kiinnitetty).

Liikkuvat agentit, mobiili koodi

Agentilla tarkoitetaan suhteellisen itsenäisesti toimivaa koodia, mutta tarkempi tulkinta vaihtelee näkökulmasta riippuen. Tekoälyn yhteydessä agenttien odotetaan suoriutuvan mutkikkaista tietoa tai tekoälykkäitä algoritmeja edellyttävistä toimista, kuten automaattisesta osakekaupasta. Käyttöliittymäagentit edustavat älykkyyttä, jonka on määrä tottua käyttäjän taipumuksiin ja siten esim. välttää häiritseviä kyselyjä; myös jatkuvatoiminen oikolukija on agentti tässä mielessä. Hajautettujen järjestelmien agentit taas ovat verkossa vaeltavia agentteja, jotka isäntäkoneesta toiseen siirtyessään keräävät ja suodattavat niistä saamaansa tietoa.

Agentti on siis ohjelma, joka toimittaa asioita ihmisen puolesta. Olionäkökulmasta agentti on olio, jolla on yksityinen toteutussäie. Liikkuva agentti siirtää itsensä (oikeastaan agenttisysteemin avustuksella) host-koneeseen, joka sisältää olion, jonka kanssa agentti haluaa vuorovaikuttaa. Tällaisten agenttien käyttö vähentää verkon kuormaa ja toisaalta verkon aiheuttaman viipeen vaikutusta tehtävän suorittamiseen. Agentit myös kapseloivat protokollia.

Liikuvien agenttien ominaisuuksia: autonomisuus (säieohjelmointia, lisäksi asynkronisuus), tavoitehakuisuus (ehtolausekkeiden pohjalta), reaktiivisuus (olioita metodeineen), sosiaalisuus (olioiden vuorovaikutus), mukautuvuus (poikkeusten käsittely, ympäristön muutoksiin sopeutuminen, "vankkatekoisuus"), liikkuvuus (sekä monistuvuus ja pysyvyys, joiden ansiota on vikasietoisuus), luontainen verkkolaskentaan sopiva heterogeenisuus.

Liikkuvaa koodia kirjoitetaan tyypillisesti tulkattavalla kielellä, jolloin saavutetaan parempi riippumattomuus alustasta. Java on suosituin kieli tähän tarkoitukseen ja sen arkkitehtuurin ansiosta tuntemattoman agentin isännöinti on "suhteellisen" turvallista. Ongelmia: isäntäkone ei voi rajoittaa oliolle tai säikeelle tarjottavia prosessori- ja muistiresursseja. Java-objektin julkiset metodit ovat kenen tahansa saatavissa osoitteen perusteella. Agentilla ei ole suoraa keinoa valvoa, mitkä muut agentit käyttävät sen metodeja. Olion täydellistä suoritustilaa ei saa nykyisellään selville ja esim. pinokehys ja ohjelmalaskuri pysyvät kiellettynä tietona.

Muita kieliä on esim. Tcl (Tool Control Language, 1988-, Python ja Tk ovat Tcl:n jälkeläisiä).

Harjoitus: Ajattele koodia, joka tulee jostain ajettavaksi koneessasi ja lähtee sitten edelleen jonnekin. Intressinäsi on tarjota koneesi palvelua, mutta miten varmistut, ettei mitään asiatonta tapahdu? Katso samaa asiaa toisinpäin: kirjoitat koodia, jonka haluat kiertelevän ajautumassa muissa koneissa ja palaavan kiinnostavia tuloksia mukanaan. Mitä voit tehdä että tosiaan saat tuloksia ja voit myös luottaa niihin? Vastauksia tämän kerran artikkelin pohjalta: Ensinnä turvatekniikoita, joilla agenteilta suojaudutaan:

Aitoustodistukset: koodin laatijan ja lähettäjän sekä koodin eheyden todentaminen.
Koodin todentaminen: "ennakkosensuuri" (hidas prosessi eikä aukoton).
Pääsyn tarkkailu ja rajoittaminen, monitorin toimesta. Yhtenä erityisongelmana piilokanavat ('covert' eli 'subliminal channels'), jotka ovat yleisempi ilmiö: tietoa välitetään (mahdollisesti siis luvatta) redundanssin tai jonkin oheisilmiön kautta, niin ettei sitä voi asiasta tietämätön havaita selkokielestäkään.
Aikarajoitukset: elinaika (ennen tuhoamista tai palauttamista lähettäjälle)
Vaikutusalueen rajoitukset: monessako paikassa agentti saa käydä
Monistuksen rajoitukset: yläraja sille montako kopiota agentista saa kaikkiaan muodostua
Tapahtumakirjanpito (audit log)

Nämä perustuvat informaatiolinnakkeen nimellä kulkevaan tietoturvamalliin, jonka tavoitteena on sulkea turvattava systeemi tarkoin määriteltyjen liittymien taakse. Tätä tavoittelevat toimintaperiaatteet ('policy') perustuvat eheyden ja salaisuuden ylläpitämiseen, mutta näiden toteutuminen on kiistanalaista nykyisessä tietojenkäsittelyssä!

Agenttien suojeleminen pahantahtoisilta isänniltä on paljon vaikeampi ongelma. Suojattavaksi tulevat agentin koodi, tila (= työ, jonka agentti on tehnyt), ja koodin kulloinenkin suoritus. Isännän lisäksi koodi ja tila pitää tietysti suojata tietoliikennekanavissa kuten mikä tahansa viesti.

Turvatekniikoita, joilla agentteja suojellaan

Monistautuminen ja äänestys: eheyden tarkistus esim. useassa osassa useaa reittiä kulkeneen agentin osien kesken jaetun salaisuuden perusteella.
Liukuva salaus: kerätyn datan salaus.
Jälkien häivyttäminen: siten ettei agenttia pysty jäljittämään tunnistamalla se samaksi eri paikoissa.
Koodin hämäännyttäminen (obfuscation): jopa niin, että koodia ajetaan kryptattuna (teoriassa).
Datan käsittely salattuna: (eri asia, mutta mieti mitä oikeastaan tapahtui sokeassa allekirjoituksessa)
Tilan arviointi (state appraisal): tarkistus, ettei agentin tila ole muuttunut sellaiseksi, joka tekee agentista vihamielisen.
Pysyvyys: suhteessa koneen kaatumiseen; siis tallettaminen levylle suorituksen ajaksi.
Uudelleensuuntaaminen ohi "tiesulkujen".

Luennon kannalta hyvin ajankohtainen uutinen oli Melissa-viruksen ja sen seuraajan löytyminen. Viruksethan ovat mobiileja agentteja jos mitkä. Joitakin linkkejä näiden uusimpien virusten suhteen on seuraavassa:

SSH-demonstraatio, HC414 klo 11:15-12

Tausta ja motivointi vastaavin askelin kuin kurssin alkupuolellakin tehtiin: Muodostettaessa pääteyhteys turvattoman kanavan yli pitää viesti salata (käyttäjältä merkki kerrallaan!) --- avainkin olisi vaihdettava --- yksilöinti puolin ja toisin --- avainten hallinta.

Asennetaan TTKK:n lisenssoima F-Secure SSH paikalliselta web-sivulta käsin. Asennusohjelman saatua työnsä valmiiksi se käynnistää avaimen generointiohjelman, joka kysyy
-- avaimeen liitettävää kommenttia: kenen avain (esim. sähköpostiosoite)
-- loitsun, jolla RSA-avain salataan
-- avaimen pituuden eli RSA-modulin bittien määrän (minimi 512, oletus 1024)

Satunnaislukugeneraattorin siemenluku syötetään hiiren liikuttelulla (unixissa näppäimistöltä).

Generoidaan RSA-moduli ja avainpari, jotka jäävät asiakasohjelman tulevaan käyttöön tiedostoon IDENTITY (oletusnimi), jossa ne ovat salattuna. IDENTITY.PUB sisältää tekstimuodossa julkisen avaimen eli modulin ja salauseksponentin.

Yhteydenotto: SSH:lla otetaan yhteys ssh-demoniin, joka unix-koneessa on nimeltään sshd. Se kuuntelee TCP-porttia 22.

Jos kohdekoneen julkista avainta ei ole tuotu mikrolle etukäteen, ensimmäisellä kerralla ei voi vielä käyttää RSA-pohjaista autentikointia.

Oletetaan aluksi, että

kohdekoneen julkinen avain on tuotu mikrolle etukäteen esim. korpulla tai se on luettu webistä ja todennettu esim. tiivisteen ja puhelimen avulla (SSH ei tosin tue tätä todentamista).
mikron (käyttäjäkohtainen) julkinen avain on tallennettu käyttäjän henkilökohtaiseen hakemistoon kohdekoneella.

Yhteyden luontia varten annetaan (paikallisesti): host, käyttäjätunnus sekä loitsu, jolla mikrolla olevan RSA-avaimen (salaisen osan) salaus puretaan. Tämän jälkeen tapahtuu istuntoavaimen vaihto siten että autentikointi perustuu kummankin osapuolen toisesta tietämään julkiseen avaimeen --- salasanaa ei käytetä. Tämän jälkeen kommunikointi on kolmois-DESin salaamaa (CBC-moodissa).

Mikäli kohdekoneen julkista avainta ei ole mikrolla, SSH kysyy sen kohdekoneelta ja käyttäjällä ei ole oikeastaan muuta vaihtoehtoa kuin hyväksyä se ainakin siksi kerraksi.

Jos mikron julkista avainta ei ole kohdekoneessa (käyttäjän omalla alueella), tai sitä ei haluta käyttää, yhteyden aloittamiseksi tarvitaan käyttäjän salasana kohdekoneessa ja kohdekoneen julkinen avain. Tässä tapauksessa protokolla istuntoavaimen K muodostamiseksi C:n ja S:n (Client ja Server) välillä eteni (aiemmissa versioissa) likimain näin:

C --> S : nc
S --> C: ns, K1, K2
C vakuuttuu RSA-avaimen K1 aitoudesta (K2 vaihtuu tunneittain)
C --> S : { {K} _K1}_K2
missä K riippuu tiivistefunktion kautta ns:stä ja C:n valitsemasta satunnaisluvusta
S --> C : {"OK"} _K

Tämän jälkeen C autentikoituu S:lle salasanansa avulla. Uudemmassa versiossa K syntyy Diffie-Hellman-avaimenvaihdolla, jonka S autentisoi allekirjoituksellaan.

Sshd sekä SSH (siis client) kykenevät tarvittaessa salaamaan minkä tahansa TCP/IP-yhteyden. Tästä käytetään usein nimitystä tunnelointi tai TCP/IP portti-forwardointi. Tällöin sshd tai ssh-asiakasohjelma asetetaan kuuntelemaan jotakin muuta(-kin) porttia kuin 22. Tähän porttiin (esimerkiksi HTTP-protokollan käyttämä 80) tuleva liikenne kuljetetaan sitten salatun yhteyden läpi kohdekoneen vastaavaan porttiin.

Ilman eri asetuksia SSH tunneloi X.11 ikkunoinnin liikenteen automaattisesti. SSH toimii siis kätevästi proxynä.

Luettavaksi: A.D.Rubin, D.E. Geer Jr.: A Survey of WebSecurity, IEEE Computer Sep 1998, 34-41.