Bonehin ja Franklinin IBE-systeemissä käytetään elliptisiä käyriä, ja niissä määriteltyjä kahden muuttujan kuvauksia, jotka ovat bilineaarisia eli molempien muuttujien suhteen lineaarisia. Jos ajatellaan tavallisia lukuavaruuksia, bilineaarinen kuvaus f toteuttaisi siis tällaiset yhtälöt: f(x+y,z)=f(x,z)+f(y,z) ja f(x,y+z)= f(x,y)+f(x,z). Lisäksi olisi f(a·x,b·y)=a·b·f(x,y).
IBE-systeemin käyttämä kuvaus on nimeltään Weil-pairing. Siinä kuvauksen tulos on luku, jolla lasketaankin multiplikatiivisesti eli eo. tulokset olisivatkin f(x,z)·f(y,z), f(x,y)·f(x,z) ja f(x,y)a·b. Kumpikin muuttuja puolestaan on käyrän piste, mikä tarkoittaa siis lukuparia. Niillä lasketaan additiivisesti eli x+y ja a·x kuten eo. kaavoissa.
Kuten edellä sanotusta voi jo päätellä, elliptiset käyrät ovat tuttuihin modulaarisiin kokonaislukuihin verrattavissa olevia algebrallisia struktuureja. Ne koostuvat siis joukosta alkioita ja niiden välille määritellystä laskutoimituksesta, joka on yhteenlasku. Vastaavasti modulaaristen kokonaislukujen eli lukujoukkojen Zp*={1,...,p-1} operaatio on kertolasku. Sitä on kurssilla totuttu käyttämään potenssilaskuissa, jonka kautta on generoitu koko Zp* tai sen jokin kertolaskun suhteen suljettu osajoukko (aliryhmä), jossa on q alkiota. Tällöin q on p-1:n (iso) alkutekijä, kuten DSA-systeemissä ja viimeksi esillä olleessa Schnorr-allekirjoituksessa. Elliptisillä käyrillä on vastaavasti aliryhmiä, jonka kaikki alkiot saadaan jonkin sopivan generaattorin monikertoina. Elliptisten käyrien protokollia voi tätä kautta yrittää ymmärtää, kun vain muuntaa mielessään kertolaskut yhteenlaskuiksi ja potenssilaskut kertolaskuiksi. Tässä esitellään Boneh-Franklin -systeemiä niin ylimalkaisesti, että käytetään vain tuttuja (multiplikatiivisia) termejä.
Edellä sanotun kuvauksen lisäksi tarvitaan hash-funktioita H1, H2, H3 ja H4, joiden arvot ovat sopivista alkiojoukoista (mm. mainituilta käyriltä), jotta niillä voidaan laskea.
Avaintenjakokeskus KDC luo ElGamalin tapaisen globaalin julkisen avaimen (p, g, y), missä y = gx mod p ja x on yksityinen avain (master secret). Jokaisella asiakkaalla on julkisena avaimena jokin identiteettimerkkijono ID. Sitä käytetään protokollissa hash-funktiolla muunnettuna eli muodossa h=H1(ID), jolla siis voidaan laskea. Erityisesti KDC luo siitä jokaiselle yksityisen avaimen hx mod p. Julkisen avaimen h omistaja voi saada h:lla salattuja viestejä jo ennen kuin tietää omaa yksityistä avaintaan. Purkamista varten täytyy vain kysyä KDC:ltä hx.
Esitetään viestin salaus ja purku ensin yksinkertaistetussa muodossa, jossa ei käytetä muita hash-funktiota kuin H1:ä, jolla jo äsken laskettiin julkinen avain h. Tämä yksinkertaistus ei ole turvassa valitun kryptotekstin hyökkäykseltä, mutta havainnollistaa hyvin bilineaarikuvauksen merkitystä. Kyseinen Weil-paring -kuvaus jätetään tässä varsin epämääräiseksi, mutta täydennetään edellä olevaa esitystä nyt sen verran, että kuvaukselle pätee bilineaarinen Diffie-Hellmanin hypoteesi. Edellä sovituin merkinnöin ja merkitsemällä kuvausta itseään e:llä tämä tarkoittaa, että on vaikeaa laskea e(g,g)xyz, vaikka tiedettäisiin g, gx, gy ja gz. Näistähän saataisiin bilineaarisuuden ansiosta jo esim. e(gx, gy) = e(g,g,)xy mutta ei päästäisi pidemmälle.
Yksinkertaistetusti siis, viestin m lähettäjä arpoo satunnaisen r:n, piilottaa sen hiukan ElGamalin tapaan laskemalla gr, missä g oli KDC:n julkinen parametri (käyrällä), ja jatkaa niin ikään ElGamalin tapaisesti salaamalla viestin tuloksi m · e(h, y)r, missä y oli KDC:n julkinen avain. Vastaanottaja saa arvot gr ja m · e(h, y)r ja hän pystyy laskemaan istuntoavaimena toimivan e-lausekkeen e(h, y)r arvon tietämiensä tietojen perusteella, sillä se on sama kuin e( hx, gr). Ulkopuoliset eivät tähän pysty sillä heillä ei ole yksityistä avainta hx.
Varsinaisessa IBE-systeemissä käytetään lisää hash-funktioita. Salauksen aloittava satunnaisluku r lasketaankin H3:n avulla näin: Valitaan satunnainen s ja lasketaan siitä ja viestistä r = H3(s, m). Kryptotekstinä on kolmikko (u,v,w), jossa u:lla ja w:llä on edelleen vähän ElGamal-kryptotekstin tapainen sisältö mutta ei enää yhtä selvästi kuin edellä:
Tuollaisia laskuja voi tietysti keksiä kuka vain. Hieman haastavampaa on kaivaa m esille kolmikosta (u,v,w) ja varsinainen idea on tietysti siinä, että esiinkaivuu onnistuu vain, jos tietää ID:hen liittyvän yksityisen avaimen. Purkaminen lähtee liikkeelle kuvauksesta e, jota sovelletaan yksityiseen avaimeen hx ja kolmikon ensimmäiseen komponenttiin u=gr. Kuvauksen e bilineaarisuus merkitsee sitä, että näiden eksponentit voisivat yhtä hyvin olla e:n "ulkopuolella" ja sieltä päin katsottuna ne voisivat yhtä hyvin olla "sisäpuolella" mutta vaihdettuina keskenään. Jättämällä tässä tarkastelussa kuitenkin r ulkopuolelle huomataan, että sisäpuolella on tarkalleen sama kuin siellä oli kryptausvaiheessa, apumuuttujassa J. Ja se on nyt korotettuna potenssiin r, mikä antaa saman syötteen H2-hashille kuin kryptauksessa. Siitä päästään taaksepäin jakolaskuilla: ensin saadaan v:stä ja sitten w:stä m.
Tämän tarkemmin ei järjestelmää tällä kursilla kannata kuvata. Jos identiteettipohjaista järjestelmää haluaisi soveltaa laajalti, täytyisi kuitenkin kehittää jokin oma järjestelmä ja julkaista se avoimen koodin lisenssillä (ks. Boneh-Franklin -systeemin patenttihakemusta nro 20030081785, 13.8.2002.)
Lukuisia kehitelmiä tietysti on jo olemassa (riippumatta patentin sitovuudesta). Boneh-Franklin -systeemiä on esimerkiksi sovellettu identity based signcrypt -järjestelmäksi (Boyen 2003), joka yhdistää tehokkaasti sinänsä peräkkäiset allekirjoituksen ja salauksen. Edellinen tietysti tehdään lähettäjän ja jälkimmäinen vastaanottajan identiteettipohjaisella avaimella.
Joka tapauksessa IBE:n leviämisen esteenä on KDC:n tarve, johon tarvitaan luja luottamus. Sillähän on tiedossa jokaisen yksityinen avain! Itse asiassa KDC on PKG, private key generator. On vaikea kuvitella, miten tällaiselta escrow-tilanteelta voisi välttyä niin kauan kuin julkinen salausavain tosiaan perustuu vain identiteettiin, joka on muidenkin tiedossa. Joitakin yrityksiä on tehty heikentämällä tätä ominaisuutta. Yksi mahdollisuus on hajauttaa luottamusta (Horwitz, Lynn: Toward Hierarchical Identity-Based Encryption , 2002). Identiteettipohjainen allekirjoitus, eli IBS, on nähtävästi saatu aikaan ilman PKG:tä (Chen, Zhang, Kim: A New ID-based Group Signature Scheme from Bilinear Pairings, 2003). Tämä ei ole kovin yllättävää, sillä tavanomaisen allekirjoituksen oheen liitetty sertifikaatti perustuu allekirjoittajan identiteettiin ja sitä voi pitää IBS-systeeminä! (Tämän "folkloren" toteavat mm. Paterson ja Schuldt: Efficient Identity-based Signatures Secure in the Standard Model 2006).
Lisätietoja IBE:stä saa esim. yleistajuisilta Stanfordin yliopiston sivuilta IBE Secure E-mail ja kaupalliselta sivustolta www.voltage.com. Tarjolla on mm. IBE-pohjaista sähköpostia ja ohjelmistoja on osittain saatavana lähdekoodisinakin. Tieteellistä lisätietoa julkaistaan kaiken aikaa. Yleiskatsauskin jo löytyy: M.C.Gorantla, R.Gangishetti, A.Saxena: A Survey on ID-Based Cryptographic Primitives (2005).
Alussa mainittu Güntherin identiteettipohjaisen DH-vaihdon kulku on esitetty luennolla ja tässä on "valkotaulukaappaus". Artikkeliin verrattuna joitakin merkintöjä on muokattu: kantaluvun alfa tilalla on tavanomaiseen tapaan g, ja osapuolen B muuttujissa on merkkinä piste heittomerkin sijasta. Tämän protokollan ideana on suorittaa DH-vaihto sellaisilla arvoilla, jotka luotettu KDC (artikkelissa KAC) on sitonut osapuolten identiteettiin. Ne ovat ElGamal-allekirjoituksia identiteetistä, muodoltaan (r,s). Tässä r ottaa DH-kantaluvun ja s osapuolen salaisen eksponentin roolin. Apumuuttujat t ja u (ja vastaavat pisteelliset) tarvitaan siksi, että tarjolla olevien DH-puolikkaiden kantaluvut eivät täsmää. Kaaviossa punaisella merkityt lisä-DH-puolikkaat (ilmeiset g^a ja g^b, joita ei ole viety tarkistuslaskuun mukana) puolestaan tekevät vaihdosta sellaisen, että A ja B saavat siihen eri kerroilla vaihtuvaa tietoa. Tämä tuottaa PFS-ominaisuuden (perfect forward secrecy).
Anonymiteetin määrittelyjä ja yleisiä menettelyjä oli esillä TTJ-kurssissa (id=288 ja id=289). Matkaviestinnän anonymisointi tarkoittaa tässä sitä, että keskuksetkaan eivät tiedä, kuka puhelinverkon asiakkaista eli tilaajista sitä käyttää. Perusidea on tilaajan suorittama ennakkomaksu ja sen perusteella saatu sokeasti allekirjoitettu lippu, jolla hän myöhemmin voi autentikoitua viestintäpalveluun ilman, että häntä pystytään tunnistamaan. Laskutus tapahtuu siten, että lippu toimii indeksinä nimettömään tiliin, jolle ensimmäisellä palvelun käyttökerralla talletetaan tunnetun ennakkomaksun verran rahaa, jota sitten vähennetään käytön mukaan.
Ensinnäkin osapuolet ovat
S = subscriber, tilaaja
H = HSD, home service domain, palvelu jonne S on rekisteröitynyt
V = VSD, visiting service domain, vieras palvelu, jonka alueella S haluaa
käyttää matkaviestintään.
Autentikoinnin tarkoituksena on luoda S:n ja V:n välille istuntoavain Ki (vastaten i:nnettä puhelua). Avaimen Ki voi laskea S:n keksimästä satunnaisluvusta ri sekä S:n ja H:n yhteisestä salaisuudesta Ksh. Sen S on ostanut H:lta eikä se identifioi S:ää. Se on itse asiassa sama kuin lippu H:n allekirjoittamana.
Avaimen Ki saattaminen S:n ja V:n väliseen käyttöön on H:n toimintaa. Sen tekee mahdolliseksi yhtäältä se, että H:lla on käytössään Rabinin julkisen avaimen kryptosysteemi eli oleellisesti moduuli m, joka on kahden suuren tietynlaisen alkuluvun tulo. Rabin-salaus on neliöön korottamista modulo m ja merkitään jatkossa {..}2m. (Artikkelissa m:n tilalla on er ja sen tekijätkin on mainittu, eli salaiset alkuluvut pr ja qr, mutta niitä ei tarvita tässä).
Toisaalta H:lla ja V:llä on yhteinen avain Kvh. Viestit H:lta V:lle salataan tällä avaimella niin tässä kuin muissakin protokollissa. Toisinpäin eli V:ltä H:lle näin ei tehdä, sillä kyseessä on vain S:ltä tulleiden viestien forwardointi, minkä lisäksi V vain liittää mukaansa keksimänsä nonce-luvun. Tässä protokollassa kyseinen luku sattuu olemaan numeroltaan 4.
Tilaaja S aloittaa i:nnen puhelun keksimällä satunnaisluvun ri. Siitä ja osapuolten S ja H välisestä S:n suhteen anonyymista salaisuudesta Ksh lasketaan istuntoavain kaavalla Ki = h(Ksh, ri). Tässä h on julkinen tiivistefunktio, ja sen käyttö on siis samantapainen kuin A8:lla GSM:ssä.
Luku ri on samalla eräänlainen haaste, joka esiintyy kaikissa seuraavissakin viesteissä. Salaisuutta Ksh kutsutaan myös lipuksi ja se on H:n sokeasti allekirjoittama.
Saatuaan lipun Ksh, H tarkistaa, että se on oikeanlainen (allekirj. todennus ja voimassaolo) ja ettei haastetta ri ole käytetty aiemmin. Jos sitten lippua Ksh ei ole käytetty aiemmin (eli i=1), H perustaa sitä vastaavan näennäistilin PA (pseudo account), jolle asetetaan summa, jonka H tietää aiemmin saaneensa (joltain) S:ltä. Jos lippua on jo käytetty, haetaan sitä vastaavan PA:n saldo.
| 1 | S | --> | V | : | "H", N3, { Ksh, ri }2m | ||
| 2 | V | --> | H | : | { Ksh, ri }2m, N4 | ||
| 3 | V | <-- | H | : | ( Ki, ri, PA-tietoja, N4 )Kvh | ||
| 4 | S | <-- | V | : | N3, ( Ii, ri )Ki |
Viestin 3 saatuaan V tarkastaa, että N4 täsmää. Viestissä on mukana V:n myöhempää H:lta tekemää laskutusta varten PA:n tunniste, saldo ja voimassaolon alkuaika (myös ri tarvitaan laskutukseen). Nyt V luo S:lle näennäistunnuksen Ii tätä istuntoa varten.
Kuten jo tiedämme, myös S on voinut laskea istuntoavaimen Ki ja saa siis esille Ii:n ja ri:n. Jälkimmäisen perusteella ilmenee viestin 4 tuoreus. Viesti 4 on lähetetty broadcast-tyyppisesti ja S tunnistaa omansa luvun N3 perusteella. Tämä nonce kulki molempiin suuntiin selväkielisenä, joten sillä ei voi olla merkitystä autenttisuuden kannalta.
Nyt puhelu pääsee normaaliin käyntiin istuntoavaimen Ki ja keinotunnuksen Ii avulla, ja voi jatkua kunnes PA tyhjentyy (V:n mielestä).
Lipun sokeaan allekirjoitukseen käytetään RSA:ta. Sitä varten H tarvitsee avaimet n, e ja d, joista n on moduuli, e on julkinen ja d yksityinen eksponentti (artikkelissa nh, eh ja dh).
Kun S on alunperin rekisteröitynyt H:lle, S on saanut julkisen tunnisteen Key ja siitä vain H:n tiedossa olevalla yksisuuntaisella funktiolla f lasketun avaimen f(Key). Jatkossa tarvitaan vain tätä avainta, joten merkitään sitä F:llä (artikkelissa siis f(Keyi)). Avainta F käytetään symmetriseen kryptaukseen, mutta tarkoituksena on autentikointi, eräänlainen sertifikaatin muodostaminen lipun myöntöprotokollassa (siksi merkintä Certi, jota ei tässä esiinny vaan se on kirjoitettu auki).
Symmetrinen salaus merkitään sulkeilla (..)k. Näissä protokollissa avaimena k on joko F, Kvh tai h(Ksh) ja toisena osapuolena aina H.
Seuraavassa apumuuttujat X, Y ja C määritellään ohjelmointityyliin "lennossa", eikä niitä käytetä yhtä tekstikappaletta kauempana protokollan ulkopuolella. Näistä X ja Y ovat artikkelin Psi ja Gamma.
| 1 | S | --> | V | : |
"H", N1, C={ "S", X=(re L) mod n, (T1,R)F, T1 }2m | T1 on aikaleima, sat.luku R vähentää sen arvattavuutta. | ||
| 2 | V | --> | H | : | C, N2 | V lähettää äskeisen C:n eteenpäin ja lisää mukaan oman nonce-luvun. | ||
| 3 | V | <-- | H | : | ( Y=Xd mod n, N2 )Kvh | H voi luottaa nimeen "S", jos F:llä salattu T1 on sama kuin salaamaton T1, eikä T1 ole esiintynyt aiemmin. H allekirjoittaa. | ||
| 4 | S | <-- | V | : | N1, Y | Ennen lähetystä V tarkistaa N2:n. Lähetys broadcast-tyyppisesti, S tunnistaa omansa N1:n perusteella. |
Koska S saa viimeisessä viestissä luvun Y = (re L)d = rLd mod n, hän saa r:llä jakamalla haltuunsa allekirjoitetun lipun Ksh = Ld mod n ja voi tietenkin itsekin todentaa siinä olevan H:n allekirjoituksen. Tämän ja satunnaistekijän vuoksi viimeisessä viestissä ei tarvitse kryptata Y:tä (ei olisi kyllä yhteistä avaintakaan). Oleellista on, että lippu kelpaa H:lle ja ettei kukaan muu kuin S tiedä, että se on S:n hallussa. Tietenkään Ksh:ta ei pidä näyttää kenellekään muulle kuin H:lle. Sehän salattiin V:ltä autentikointiprotokollassa ja samoin tehdään kohta lippua uudistettaessa.
Kun H allekirjoitti lipun, se ei nähnyt L:ää eli lipun sisältöä. Miten se voi jatkossa todentaa, että sille lähetetystä luvusta e:nteen korottamalla (mod n) esiin tuleva L on jotakin kelpoisaa?
Lippu L sisältää oleellisesti voimassaolon alkuajan ja lipun ajallinen kelpoisuus määräytyy sitten allekirjoitusavaimeen kiinnitetyn keston (esim. vuosi) perusteella. Kryptografista kelpoisuutta varten alkuajan oheen on liitetty sekä redundanssia että satunnaisuutta. Edellinen tarvitaan, jotta H tietäisi, että allekirjoitus tosiaan on hänen. (Aikaleimassa ei ehkä ole riittävästi redundanssia.)
Satunnaisuutta tarvitaan artikkelin mukaan samasta syystä kuin viestin 1 F:llä kryptatussa osiossa, nimittäin arvaushyökkäyksen torjumiseksi. Tätä hyökkäystä ei eritellä tarkemmin, mutta jos joku pystyy arvaamaan kumman vain kyseisistä kryptaustuloksista, niiden hyötykäyttöä varten ei tarvitse arvata enempää. Nehän lähtevät H:lle tämän julkisella avaimella salattuina. Satunnaisuuden ansiosta joka tapauksessa kahdelle eri tilaajalle S ei todennäköisesti satu samaa Ksh-arvoa.
Artikkeli ehdottaa 512-bittisen RSA-avaimen tapauksessa redundanssiksi 256:n mittaista nollista koostuvaa bittijonoa ja satunnaisten bittien määräksi 244:ää. Tällöin loput 32 bittiä ilmaisisivat voimassaolon alkuajan.
Uudistusprotokollassa ei tarvita mitään uutta sokeaa allekirjoitusta, vaan anonyymiuden ansiosta S vain lähettää lipun L' sellaisenaan ja saa sen d:nteen korotettuna takaisin, nimellä K'sh. Mennessä se on Rabin-salattu kuten ennenkin ja tullessa symmetrisesti salattu. Tähän tarkoitukseen käytetään samaa tiivistefunktiota h kuin istuntoavaimen Ki muodostamiseen, nyt tosin ilman muita argumentteja kuin vanha lippu Ksh.
| 1 | S | --> | V | : | "H", N5, D={ Ksh, L' }2m | ||
| 2 | V | --> | H | : | D, N6 | ||
| 3 | V | <-- | H | : | ( ( K'sh )h(Ksh), N6 )Kvh | ||
| 4 | S | <-- | V | : | N5, ( K'sh )h(Ksh) |
Aluksi S autentikoituu H:lle ja hankkii tältä itselleen anonymisoivan lipun (esitellään jäljempänä käyttöyhteydessään). Autentikoinnin perusteena on, että S on laskenut viestiin A3-tiivisteen aikaleimasta T ja identiteetistään käyttäen S:n ja H:n yhteistä symmetristä avainta Ki, samaa johon normaalikin GSM-autentikointi perustuu. Autentikointiviesti S:ltä kulkee V:n kautta H:lle H:n julkisella avaimella salattuna. Protokolla ei käytä julkisen avaimen operaatioita muuhun kuin tähän.
Kun H on todennut S:n viestin autenttiseksi, H lähettää V:lle viestin
N1, Auth_VLRh, T, TKi, Texpire
Tästä V lähettää edelleen S:lle muut paitsi TKi:n. Tämä tapahtuu
yleislähetyksenä, jossa nonce-luvun N1 merkitys on sama kuin eo.
JLC-protokollassa. Luku N1 on siis S:n keksimä ja se oli mukana S:n
ensimmäisessä viestissä. Mikään muukaan em. viestissä ei ole S:lle uutta. Hän
oli lähettänyt alkuperäisessä viestissään jo nämä:
N1 = nonce-luku
T = aikaleima
Texpire = viimeinen voimassaoloaika
ja pystyy laskemaan nämä
Auth_VLRh = A3( Ki, T)
TKi = A3( Ki, Texpire) = tilapäisavain
Termin Auth_VLRh merkitys on autentikoida V S:lle. Perusteena tälle on se, että
H:n viesti V:lle tuli autentikoitua kanavaa pitkin. Artikkeli kutsuu lipuksi
kolmikkoa (Auth_VLRh, TKi, Texpire). Näistä TKi on S:n ja V:n yhteinen
salaisuus, jolla ne voivat jatkossa autentikoitua toisilleen. Auth_VLRh ja
Texpire eivät ole yleislähetyksen jälkeen enää salaisia, joten niiden
merkityksenä on vain indeksoida V:n tietokantaa.
Puhelupalvelun käyttövaiheessa S:n ja V:n viestintä näyttää tältä:
1. S --> V: Auth_VLRh, Texpire, A
Voidaan havaita, että protokolla toteuttaa alussa mainitut neljä ominaisuutta. Verkon autentikoituminen tuli jo esille ja H:n vähäisempi viestintä ja laskenta käyvät ilmi. Se, että V:n tarvitsee tallettaa vähemmän ilmenee siinä, että alkuperäisessä GSM-protokollassa H toimittaa sille kerralla useita (RAND, SRES, Kc)-kolmikoita tietyn S:n kanssa kommunikointia varten (Kc on istuntoavain).
Kotitehtävä ensi kerraksi: Miten protokolla toteuttaa S:n anonymiteetin V:tä vastaan ja miten H:ta vastaan? Vertaile myös eo. JLC-protokollaan.
Edellistä tuoreemmalla päiväyksellä mutta aika paljon sekavammin kirjoitettu anonymisointiehdotus löytyy artikkelista: C.C. Yang, Y.L. Tang, R.C. Wang, H.W. Yang: A secure and efficient authentication protocol for anonymous channel in wireless communications (Applied Mathematics and Computation, Vol.169:2, Oct 2005, 1431-1439).
Anonymiteettiaiheen tutkimukseen saa sekä historiallisen näkemyksen että tuoreen linkkilistan sivustolta Anonymity Bibliography.
