1 a). Miten menee perusversio anonyymista bittikäteisestä, kun osapuolina ovat C(lient), M(erchant) ja B(ank) ja bittisetelin sarjanumerona on u? Mihin tarvittiinkaan u:n satunnaisuutta ja toisaalta siihen liitettävää redundanssia?
b) Mitä hyötyä voisi olla seuraavasta ja miten se toteutettaisiin? Client generoikin vain satunnaisluvun u’ ja laskee sarjanumeroksi luvun u=H(u’), jolloin u:ssa ei voi havaita mitään redundanssia. Vastaus löytyy, kun muistaa, että tällaisella u’:lla voi myöhemmin kertaalleen autentikoitua samaksi, joka on joskus aiemmin lähettänyt u:n. Redundanssi pitää tietysti myös lisätä.
2. Muunnetaan protokollaa (1a) siten, että M maksaakin C:lle ja edelleen nimenomaan C säilyy anonyymina -- ts. jäljittymättömänä. (Kohdassa 4b tätä tarvitaan vaihtorahan vastaanotossa, mutta voitaisiin ajatella myös, että M on taho, joka maksaa C:lle sosiaaliavustusta -- tai lahjuksia.)
3. Protokollat (1) ja (2) voidaan yhdistää käyttämällä B:tä tai jotain muuta kolmatta osapuolta siten, että C ja M pysyvät molemmat anonyymeina. Sama tulos saadaan muuntamalla (1a) siten että M luo setelin, sokaisee sen ja C tekee siihen vielä oman sokaisunsa ennenkuin hakee sille allekirjoituksen B:ltä. Siis miten tämä menee? (Huomaa samankaltaisuus protokollaan (2) jossa C:n ja M:n roolit on vaihdettu. Mitä B näissä kaikissa lopulta saa ja mitä se voi päätellä?)
4. Vaihtoraha.
a) Kuten ennenkin on todettu, pankilla voi olla eri allekirjoituksia eri arvoisille seteleille. Näissä voidaan käyttää samaa RSA-moduulia n = p·q. Muodostetaan ensin sellainen systeemi, jossa julkisesta eksponentista e näkee suoraan, minkä arvoisen allekirjoituksen sillä voi todentaa. Vastaava allekirjoitusavainhan on sitten d = e-1 mod (p-1)·(q-1).
Bittijonon b = b1 b2 b3 b4 ... bk numeroarvo b määrittelee setelin arvon jossain kiinteässä yksikössä (olkoon tässä €) ja sitä vastaava todennuseksponentti on e = 3-b1 ·5-b2 ·7-b3 ·11-b4 ·...· (k:s pariton alkuluku) -bk .
Olkoon k=4, jolloin käytössä on setelit 1€ .. 15€. Niitä vastaavat e:t ovat siis 11, 7, 77, 5, 55, 35, 385, ..., 105, 1155.
Tällaisessa systeemissä bittisetelin ostaja voi itse muuttaa sen arvoa, mutta vain pienempään päin. Millä tavoin? (Vastaus paljastuu viimeistään seuraavassa kohdassa.)
b) Vaihtorahasysteemin voi toteuttaa joustavamminkin, mutta tarkastellaan tässä sellaista mallia, jossa
Olkoon maksettavana 10 €:n arvoinen ostos. Käytössä on siis 15 €:n arvoinen seteli, joka todentuu eksponentilla 1155 = 3·5·7·11. Muunnetaan sitä niin, että se todentuu eksponentilla 3·7=21, joka vastaa arvoa 10 €. Tämä toteutuu korottamalla seteli potenssiin 1155 / 21 = 55. Todennuksen tekee ensin M, jolle C on maksamassa, ja sitten B joka hyvittää M:n tiliä 10 €:lla ja allekirjoittaa 5 €:a vastaavalla avaimellaan viestin mukana olevan C:ltä peräisin olevan sokaistun vaihtorahasetelin.
Kun C purkaa vaihtorahaviestistä sokaisun hän saa kohdan (4a) mukaisen setelin, jonka hän voi tallettaa linkittymättä kauppiaaseen M. Tässä käytetään oleellisesti protokollaa (2). Kohdan (4a) arvosysteemi ei ole rajoittunut binäärijonoihin b = b1 b2 b3 b4. Esimerkiksi jono 2061 määräisi arvon 2 · 8€ + 0 · 4€ + 6 · 2€ + 1 · 1€ = 29 €. Jos C luottaa kauppiaisiin näin paljon, hän on voinut sokaista saman vaihtorahasetelin yhä uudestaan ja hankkia siihen lisää allekirjoitusta eli vaihtorahaa. Jos hän sitten lopulta lähettää B:lle viestin, joka todentuu eksponentilla 32 ·50 ·76 ·111, hän saa tililleen 29 €.
Vaihtorahasetelin redundanssirakenteen täytyy olla erilainen kuin maksuun käytettävien setelien tai allekirjoituksen täytyy perustua eri moduuliin, jotta erityyppisiä seteleitä ei voisi sekoittaa. Muutenhan yhden euron vaihtorahalla maksaminen toisi 14 € vaihtorahaa.
Miten 10 €:n arvoinen ostos siis tapahtuu?
”Osittaista kokonaiskuvaa” varten tarkastellaan kirjan sisällysluetteloa: Mostafa Hashem Sherif: Protocols for Secure Electronic Commerce (CRC Press, 2nd ed. 2004). Edellä käsitellyt bittikäteisen muodot ovat muuten oleellisesti kirjan luvusta Digital Money. (Viimeisessä eli vaihtoraha-aiheessa ainakin kirjan 1. laitos vuodelta 2000 sisälsi useita kirjoitusvirheitä. Vaihtoraha-aiheen jälkeen, luvussa 11.1.5. kirja esittää anonyymille jäljittyvälle bittikäteiselle toisenlaisen toteutuksen kuin jatkokurssilla esillä ollut.)
Maksamisen protokollien kannalta melko laaja-alaista pohdintaa löytyy artikkelista Electronic Payments: Where Do We Go From Here? (Jakobsson & al, 1999, LNCS 1740, 46-33). Siinä esitetään mm. protokollien kirjoa jäsentämään tarkoitettu luokittelu muutaman ulottuvuuden suhteen:
Artikkeli esittelee lyhyesti kaksi vanhaa mekanismia ja niiden ongelmia, joiden ratkaisuksi sitten tarjotaan kolmea uutta protokollaa lukuisten variaatioiden kera. Uudet ovat nekin variaatioita vanhoista, jotka ovat PayWord ja ”RA”.
PayWord: asiakas allekirjoittaa hash-iteraation viimeisen arvon (”juuren”) ja lähettää edeltäjiä sitä mukaa kuin maksettavaa kertyy. Pankki laskuttaa allekirjoituksen ja viimeisen perusteella ketjun pituuden mukaan. Ongelma: Kauppias ei voi kerätä yhteen eri asiakkaiden ketjuja.
”RA”: Rivestin arpajaissysteemi: Asiakas sitoutuu tavalla tai toisella (esim. allekirjoituksella kuten jatkossa tai PayWordin tapaan) jokaiseen mikroyksikköön. Niistä kauppiaan kanssa käytävä protokolla määrittää ennakoimattomalla tavalla keskimäärin joka 1000:nnen maksuunpantavaksi, mutta maksu onkin sitten aina 1000-kertainen -- eli sen kokoinen, että kulut eivät muodostu raskaiksi. Ongelmat: maksuunpanoprotokollan interaktiivisuus ja käyttäjän riski, joka ei ole psykologisesti hyväksyttävissä.
Uudet protokollat ovat MR1, MR2 ja MR3 tekijöiden nimien, Micali ja Rivest, mukaan.
MR1 poistaa interaktion tarpeen RA:sta: Asiakas allekirjoittaa jokaisen maksusitoumuksen ja kauppias puolestaan allekirjoittaa ne ja laskee tuloksesta muunnoksen lukuvälille 0..1. Jos muunnos tuottaa pienemmän luvun kuin 1/1000, sitoumus pannaan maksuun 1000-kertaisena. Pankki voi tarkistaa molemmat allekirjoitukset sekä muunnoksen.
Tämän protokollan esittelyssä kirjoittajat esittävät sellaisen variantin jonka he voivat todistaa turvalliseksi. Tässä yhteydessä tulee esille tärkeä teoreettinen käsite: Random Oracle -malli. Se tarkoittaa ajatusta, jossa yleensä hash-funktion ajatellaan olevan ns. satunnaisoraakkeli ja siitä saadaan lähtökohta teoreettiselle turvatodistukselle, jonka sanotaan sitten perustuvan Random Oracle -malliin. Se, että funktio on satunnaisoraakkeli, tarkoittaa, että sen tulosta ei voida erottaa satunnaisluvusta, mutta se antaa kuitenkin joka kerta samasta syötteestä saman tuloksen.
Protokollalle MR1 esitellään useita variaatioita, jotka käyvät myös MR2:een ja MR3:een. Nämä ovat mainioita esimerkkejä protokollien suunnittelussa tarvittavasta luovuudesta.
MR2 on kuten MR1, mutta poistaa asiakkaalta huolen, että tämä joutuisi koskaan maksamaan enemmästä kuin on ostanut. Pankki kantaa tähän liittyen itselleen pienen riskin, sillä kauppiaalle hyvitetään silti kulloisenkin maksusitoumuksen koko summa. Asiakas liittää maksusitoumukseensa juoksevan sarjanumeron. Jos sitoumus tulee pannuksi maksuun (MR1:n mekanismilla), pankki veloittaa asiakkaalta nykyisen ja edellisen maksuunpannun sarjanumeron erotuksen.
Tähän protokollaan samoin kuin MR3:een liittyy riskinhallintaa myös siten, että pankki voi sanoa sopimuksen irti huonosti käyttäytyviltä asiakkailta ja/tai kauppiailta. Asiakkaan huono käytös olisi sitä, että hän ei kasvatakaan sarjanumeroa. Kauppias taas voi tehdä yhteistyötä asiakkaan kanssa siten, että maksumääräykset tulevat aina maksettaviksi. Asiakkaalta menee esim. sentti joka kerta mutta kauppias saa kympin (jonka jakaa asiakkaan kanssa).
MR3 käyttää MR2:n tapaan sarjanumeroita, mutta siirtää pankille laskennan, jonka mukaan maksuunpanopäätös tapahtuu. Tätä varten M kerää asiakkaidensa maksusitoumuksia tietyn omassa vallassaan olevan ajan. Tilitystarpeen koittaessa M lähettää pankille allekirjoittamansa listan, jossa on n kappaletta hash-arvoja. Ne on laskettu asiakkaiden maksumääräyksistä, jotka M on valitsemallaan tavalla jakanut n:ään luetteloon. Allekirjoituksessa on mukana myös maksumääräysten kokonaissumma. Pankki valitsee satunnaiset k indeksiä ja pyytää M:ltä niitä vastaavat maksumääräysten luettelot. Pankki voi nyt tarkistaa, että niistä tulee oikeat hash-arvot. Jos näin käy, pankki hyvittää M:lle kokonaissumman ja laskuttaa saamiensa maksumääräysten mukaan asiakkaita MR2-systeemin mukaisesti.
(Vastausta: Vaikka tässä onkin enempi kyse datan eikä olion autentikoinnista, olion kannalta menettelyillä on juuri nämä kaksi merkitystä: ostaja päätyy vastuuseen ja menettää sen mukaisesti tililtään rahaa; kauppias puolestaan autentikoi itselleen hyvityksen. Kumpikin joutuu vastuulliseksi siten, että voi myöhemmin saada rangaistuksen väärinkäytöksestä.)
Mikromaksamisen artikkeli esittää MR3-järjestelmän muunnokseksi autentikointipuun käyttämistä autentikointilistan sijasta. Yleisesti autentikointipuussa puun kukin solmu sisältää sen lapsisolmuista lasketun hash-arvon. Puun lehtisolmut ovat datasta laskettuja tiivisteitä, ja uutta dataa voi olla mukana myös välisolmujen hash-syötteessä. Tällaisen puun juuren allekirjoittaminen vastaa sitä, mitä edellä teki autentikointilistan juuren eli hash-iteraation viimeisen arvon allekirjoitus. Puun tapauksessa jonkin tietyn solmun tietojen autentikointiin tarvitaan keskimäärin paljon vähemmän vaivaa kuin autentikointilistassa. Tutkittavasta solmusta tarvitaan data ja siitä juureen johtavan polun solmuista tarvitaan niiden (mahdollisen datan lisäksi) lapsisolmujen sisältämät hash-arvot. Polkuun kuulumattomista lapsisolmuista autentikaation tarkastaja ei siis näe mitään muuta.
Autentikointipuun kehitteli Ralph Merkle jo 1979 digitaalisen allekirjoituksen tarpeisiin: Puun solmuihin talletetetaan kertakäyttöisiä julkisia avaimia, eikä niiden kaikkien autenttisuudesta tarvitse vakuuttua erikseen, kunhan vain on varma juuresta ja saa allekirjoitusten mukana tarvittavat alipuiden hash-arvot tarkistusta varten. Avaintenhallinnan tehostusta tarvitsevia kertakäyttöisiä allekirjoitusavaimia (itse asiassa todennusavaimia) on muissakin systeemeissä, mutta autentikointipuun kehittely liittyi Lamportin algoritmiin, joka on itsekin hash-pohjainen: yksityisenä avaimena on satunnaislukuparien (xi, yi) jono, julkisena on näistä laskettujen hash-parien jono (h(xi), h(yi)), ja bittijonon allekirjoitus muodostetaan paljastamalla kutakin bittiä kohti yksityisen avaimen vastaavasta parista ensimmäinen tai toinen jäsen. Jos siis pitäisi allekirjoittaa bittijono 110... (joka sekin on tietysti tiiviste), kerrottaisiin siis x1, x2, y3, ... .
Kun tehokkaampia allekirjoitusalgoritmeja tuli käyttöön, puurakenne menetti tämän tarpeensa, mutta säilytti autentikaatioon sopivan merkityksensä (Merkle 1987). Sittemmin järjestelmä on tullut yleiseen käyttöön esim. joissain P2P-järjestelmissä palasista koostuvan tiedoston eheyden toteamiseen. Juonena on tarjota kunkin palasen datan mukana muiden palasten edustaman alipuun hash-arvo, jolloin eheys voidaan todeta, vaikka kaikkea dataa ei ole vastaanotettu. Tätä ideaa voidaan käyttää myös stream-sovelluksissa, joissa osa datasta voi lopulta jäädä saamatta. Näitä rakenteita on tarkasteltu esim. artikkelissa Digital Signatures for Flows and Multicasts (Wong, Lam, 1999)
Myös TTJ:ssä mainittiin puujärjestelmän käyttökelpoisuus PKI-sulkulistan yhteydessä [id=335]. Sulkulistahan (CRL) täytyy autentikoida varmentaja (CA) allekirjoituksella, ja jos ei käytetä OCSP-protokollaa ja siihen liittyviä palvelimia, CA lähettää koko CRL:n vastauksena, kun siltä kysytään jotain varmennetta. Jos käytetään peruutuspuuta eli sijoitetaan peruutetut varmenteet autentikointipuuhun, voidaan säästää lähettämällä ”avattuna” vain kysyttyä varmennetta koskeva kohta puusta. Tätä varten tarvitaan tietysti sovelias sarjanumerointi, ja uusien peruutusten sijoittelua puuhun voidaan optimoida tasapainottamalla puuta sopivasti. Tällainen rakenne on esitetty esim. artikkelissa Performance Evaluation of Public-key Certificate Revocation System with Balanced Hash Tree (Kikuchi, Abe, Nakanishi, 1999)
Autentikointipuu ja tehostuksia siihen esitellään RSA-laboratorion sivulla ja yleinen katsaus löytyy wikipediastakin. Autentikointipuuta on sovellettu esim. sensoriverkkojen autentikoinnin tehostamisessa: Seys, Preneel, 2005 (ks. artikkelin luku 3).