Oppikerta 2, 19.1.1999
Kertausta: Käsitekaavio tietoturvan koko kentästä ja kurssin aihepiirin rajaus. (Vastaava kaavio Esa Kerttulan uudesta kirjasta: Tietoverkkojen tietoturva.)

Kryptoprimitiivit

Tietoturvaa luodaan kryptografialla eli matemaattisilla algoritmeilla: salauksella, yksisuuntaisilla tiivistefunktioilla (=hash), satunnaisluvuilla, erityisillä laskuoperaatioilla (esim. allekirjoitukseen tarkoitetuilla). Näihin liittyy salaisina pidettäviä parametreja (salaus- ja/tai purkuavaimia).

Piirretään luokittelukaavio kryptoprimitiiveistä [HAC:5]:

Tekemättä aivan yhtä tarkkaa jaottelua käsittelemme seuraavat "alkeisprimitiivit": Viestin salaaminen/purkaminen (symmetrinen ja epäsymmetrinen) ja (yksisuuntainen) tiivistäminen sekä ennustamattomien satunnaislukujen generointi. Tässä vaiheessa ei ehditä kovin paljon viitata primitiivien käyttöön (esim. allekirjoitukseen tai autentisointiin) vaan ne "säästetään" osittain jopa itse keksittäviksi seuraavien oppituntien aikana (ja luettavaksi tämän ja ensi kerran artikkelista).

Saavutettavaa turvallisuutta voidaan luokitella ensinnäkin seuraavasti:

Informaatioteoreettinen näkökulma on mukana murtamiseen tarvittavien syötetietojen määrän arvioinnissa, mutta käytännössä on tyytyminen sellaiseen laskennalliseen turvallisuuteen, jossa vastustajan ratkaistavaksi tulevaa probleemaa on runsaasti tutkittu ja paraskin tunnettu algoritmi on laskennallisesti mahdoton. (Mikä kulloinkin on tarpeeksi vaikeaa ollakseen mahdotonta, on tulkintakysymys ja voi myös riippua vastustajan laskentatehosta tehdyistä oletuksista). Systeemin sanotaan olevan todistettavasti turvallinen (provably secure), mikäli on voitu todistaa, että kyky murtaa systeemi tuottaisi ratkaisun myös mainittuun "mahdottomaan" probleemaan. (Näistä käsitteistä löytyy varsin tiivis esittely Zürichistä.)

Toiseksi algoritmeja luokitellaan sen mukaan, millaisin oletuksin ne tarjoavat laskennallista turvallisuutta, eli kuinka voimakkaan vastustajan ne kestävät. Tässä ajatellaan selvätekstiä (cleartext, plaintext) ja sen salakirjoitettua versiota eli salatekstiä (cryptotext, ciphertext): Lähtökohtana on, että vastustaja tuntee algoritmin ja hänellä on salatekstiä, jonka hän haluaisi purkaa. Vastustajan voimakkuutta kuvaa se, mitä muuta hän tietää:

  1. vain salateksti
  2. tunnettu selväteksi: edellisen lisäksi vastustajalla on selväteksti-salateksti pareja (samalla avaimella salattuja kuin purettavakin teksti).
  3. valittu selväteksti: vastustaja saa haltuunsa em. pareja joissa hän on voinut valita selvätekstin: hän on siis jotenkin pystynyt syöttämään salausalgoritmin läpi haluamiaan selvätekstejä vaikka ei tunnekaan avainta. Voimakkaammassa (ns. adaptiivisessa) versiossa hän pystyy aiempien tulosten perusteella valitsemaan uusia selvätekstejä.
  4. valittu salateksti: kuten kohdassa 2, mutta vastustaja voikin valita salatekstin. Tehtäväksi tyypillisesti muodostuukin avaimen ratkaiseminen. Tilanne liittyy lähinnä julkisen avaimen systeemeihin.
  5. valittu teksti: edelliset kohdat yhdessä.
Sopivilla ja riittävän turvallisilla kryptograafisilla algoritmeilla ja protokollilla voidaan luoda pohja useimpien tietoturvatavoitteiden toteuttamiselle, kunhan rakennetaan turvallinen implementaatio ja sille puolestaan turvallinen installaatio. Tällä kurssilla keskitytään kuitenkin algoritmeihin ja protokolliin.
Symmetrinen kryptosysteemi
Perinteinen idea: viesti "lukkoon" avaimella ja auki toisaalla samalla avaimella. Algoritmia ei voi olettaa salaiseksi. Turvallisuus on avaimessa.

Yleinen informaatioteoreettinen tavoite: "diffusion and confusion". Näillä tarkoitetaan keinoja, joilla selvätekstin redundanssia kätketään, kun se muunnetaan salatekstiksi. Konfuusio hämärtää selvä- ja salatekstin välistä yhteyttä suorittamalla korvauksia (yksinkertaisimmillaan). Diffuusiossa puolestaan hajotetaan selvätekstin jakaumia koko kryptotekstiin permutaatioiden avulla (taaskin yksinkertaisimmillaan).

Ainoa täysin turvallinen: "one-time pad". Avain on satunnainen ja sen pituus on suurempi kuin viestin. Kryptoteksti = viesti XOR avain. (Toki tästä voi laatia muunnoksia, jotka ovat yhtä turvallisia. Yhtä epäkäytännöllisiä ne ovat silti.)

Blokkikryptaus
Algoritmia sovelletaan kiinteään määrään viestibittejä kerrallaan: Tyypillinen blokkikoko on 64 tai 128.

Useimmat algoritmit pohjautuvat Feistel-periaatteeseen: On jokin kiinteä funktio f, jota sovelletaan avaimeen (tai siitä laskettuun lukuun) ja viestin loppupuolikkaaseen. Tulos XOR-summataan viestin alkupuolikkaan kanssa. Seuraavaa kierrosta varten puolikkaat vaihdetaan, eli loppuun tulee äskeinen summa ja alkuun äskeinen loppupuolikas sellaisenaan. Kierroksia tehdään tietty määrä. Joka kierroksella käytetään avaimesta eri tavalla muodostettua osa-avainta. Salauksen purku ei edellytä funktion f kääntämistä vaan XOR-operaation ominaisuuden ansiosta riittää toistaa samat kierrokset, kunhan avainsekvenssi käydään lopusta alkuun. Harjoitus: Piirrä kaavio ja tutki dekryptauksen onnistumista.

Valitsemalla erilaisia funktioita f, ja erilaisia avainsekvenssejä saadaan erilaisia algoritmeja. On myös useita läheisiä muunnoksia Feistel-periaatteesta.

DES on vuonna 1977 standardoitu algoritmi, joka muodostuu 16 Feistel-kierroksesta. Avain on 56-bittinen. Joka 8:nneksi lisätään pariteettibitti, joten avain näyttää 64-bittiseltä. Blokkikoko on 64. Yksi tapa parantaa DES:n turvallisuutta on käyttää sitä kolminkerroin kahdella avaimella k1 ja k2. Merkitään: Ei = kryptaus ja Di = dekryptaus avaimella ki. Viestin M triple-DES-kryptaus on E1( D2 ( E1( M))). (Kolmeakin avainta voi tietysti käyttää, mutta em. tekniikka on standardoitu.)

DES oli alunperin IBM:n ehdotus standardiksi vuodelta 1974. DES:n seuraajaksi tarkoitetun AES:n (Advanced Encryption Standard) luominen alkoi vuoden 1997 alussa. Virallinen kutsu ehdotuksille oli syyskuussa 1997. Elokuussa 1998 ensimmäisen AES-konferenssin yhteydessä NIST (National Institute of Standards and Technology) julisti 15 virallista ehdokasta julkisesti tutkittaviksi. Toinen konferenssi pidetään maaliskuussa 1999. Ensimmäisen kierroksen julkinen kommentointiaika päättyy 15.4.1999. [AES-tilanteesta raportoiva NIST:n sivu]

Blokkialgoritmien moodit
Jos algoritmia käytetään kryptaamaan jokainen blokki erikseen, sanotaan että kyseessä on elektroninen koodisanakirja ECB (electronic code book mode). Siinä sama blokki tuottaa aina saman kryptotekstin, mikä ei ole hyvä ominaisuus, jos teksti on pitkä. Algoritmi on kuitenkin nopea, koska se on mahdollista rinnakkaistaa.

Useimmiten on syytä käyttää jotain seuraavista ketjuttavista moodeista, joissa seuraavan blokin kryptaus riippuu aiemmista. Kaikissa niistä tarvitaan yhden blokin mittainen alustusvektori (IV) eli bittijono, joka toimii blokkialgoritmin ensimmäisenä syötteenä. Sen ei tarvitse olla salainen.

Harjoitus: Täydennä salausmoodeista piirrettävät kaaviot kuvaamaan myös, miten salauksen purku tapahtuu. Oletetaan, että kryptotekstissä tapahtuu bittivirhe. Mikä vaikutus sillä on purettavaan selvätekstiin eri moodeissa? Miten purku saadaan synkronoiduksi virheen jälkeen?
Vuokryptaus (stream ciphers)
Blokkialgoritmi käytettynä OFB-moodissa tuottaa avaimesta ja alustusvektorista oleellisesti avainvirran (key stream), joka XOR-summataan selvätekstin kanssa. Virta on riippumaton selvätekstistä ja voidaan vaikkapa laskea etukäteen. Tällaista vuokryptausta sanotaan synkroniseksi, koska vastaanottajan avainvirran täytyy olla samassa vaiheessa lähettäjän virran kanssa. Voidaan myös muodostaa ns. itsesynkronoivia systeemejä, jotka siis toipuvat automaattisesti. Perusidea on se, että avainvirta riippuu vain tietystä määrästä aiempia kryptotekstibittejä (näin on vaikka selvätekstibiteistä kaikki aiemmat vaikuttavat kryptotekstiin). Tavallisin tällainen systeemi on blokkialgoritmin CFB-moodi, jossa r=1.

Yleensä vuokryptaus toteutetaan lineearisilla takaisinkytketyillä siirtorekistereillä (linear feedback shift registers, LFSR) Sellainen koostuu n:stä yhden bitin rekisteristä R0, R1, ..., R(n-1). Kellon antaessa sykäyksen bitit siirtyvät yhtä pienempään rekisteriin siten, että R0:sta muodostuu rekisterin ulostulo. Tämä bitti syötetään samalla toiseen päähän eli rekisteriin R(n-1), kuitenkin siten että siihen on XOR-summattu joidenkin muiden rekisterien sisältö.

Kun siirtorekisterillä on jokin alkutila, se tulostaa bittijonon, joka toteuttaa tietyn lineaarisen rekursioyhtälön ja on jaksollinen. Jakson pituus on korkeintaan 2n-1. Tämä maksimaalinen jakso saavutetaan (kaikilla ei-nollilla alkutiloilla), mikäli takaisinkytkettävät rekisterit valitaan jonkin ns. primitiivisen polynomin kertoimien mukaisesti.

Täksi kerraksi luettavassa artikkelissa on esimerkki neljäbittisestä siirtorekisteristä (sama kuin [HAC:196]). Sen polynomi on 1+x+x4 ja rekursioyhtälö si = si-1 + si-4 modulo 2. Tämä tarkoittaa, että ulostulo on si, kun i=0,1,2,... . Rekisterin Ri alkutilaksi oletetaan si (i=0,1,2,3).

LFSR:n lineaarisuutta häivytetään vuokryptausalgoritmeissa jollain seuraavista tavoista.

Vuoalgoritmit ovat kovototeutuksina tyypillisesti nopeampia kuin blokkialgoritmit. Pienten puskureiden tai tiukkojen reaaliaikavaatimusten yhteydessä, esim. telekommunikaatiossa ne ovat usein välttämättömiä. Esimerkkinä A5-algoritmi, jota käytetään GSM:ssä: ks. news-artikkeli vuodelta 1994 tai sama artikkeli ja lisää asiayhteyttä.

Satunnaisluvut
Satunnaisluku valitaan annetusta lukujoukosta siten, että jokaisella luvulla on sama todennäköisyys tulla valituksi. Satunnaislukuja tarvitaan avainten generoinnissa (sekä symmetrinen että julkinen), autentisointihaasteissa ja viestin tuoreuden osoitukseen (viimeksi vastaanotetun satunnaisluvun, ns. 'nonce'n palauttaminen kryptattuna).

Satunnaislukuja tuotetaan generaattoreilla, jollaiseksi riittää satunnaisbittijonon tuottava algoritmi tai laite. Yleisiä vaatimuksia tuotetulle bittijonolle: bitit ovat toisistaan riippumattomia ja jakauma on tasainen. Käytännössä tämä todetaan tilastollisilla testeillä, jotka jättävät aina tietyn epävarmuuden asiasta. Tuotetusta bittijonosta lasketaan tunnuslukuja, joita verrataan teoreettisesti johdettuihin täysin satunnaiseen bittijonon vastaaviin lukuihin (Khin neliön testillä). Vertailut koskevat esim. erilaisten k bitin osajonojen frekvenssejä, erimittaisten juoksujen (runs) eli maksimaalisten peräkkäisistä ykkösistä (tai nollista) koostuvien osajonojen frekvenssejä ja autokorrelaatiota (tietyllä bittimäärällä siirretyn jonon samanlaisuutta alkuperäisen kanssa).

Yleisesti käytetty ja sopivilla parametreilla (a, b ja m) tilastollisesti hyvä menetelmä satunnaislukujen generointiin on modulaarinen iteraatio: x(n+1) = a*x(n) + b modulo m, missä x(0)=siemenluku (satunnainen). Esimerkiksi m=231-1, a = 75 ja b=0. Ongelmana kryptografian kannalta on se, että muutamasta luvusta voidaan päätellä koko jono.

Kryptograafisessa käytössä satunnaisluvuilta vaaditaan lisäksi ennustamattomuutta. Satunnaisten bittien generaattorit (BG) jaotellaan seuraavasti;

Esimerkki "CSPRBG":stä on BBS-generaattori (keksijöinä Blum, Blum ja Shub). Oletuksena turvallisuudelle on tekijöihinjakoprobleeman vaikeus.
  1. generoi kaksi suurta alkulukua p ja q ja laske n=p*q.
  2. valitse satunnaisesti sellainen luku s väliltä [1,n-1], ettei sillä ole yhteisiä tekijöitä n:n kanssa. Laske x0 = s2 mod n.
  3. toista kun i=1,...,m:
    xi = xi-12 mod n.
    tulosta xi:n vähiten merkitsevä bitti.
Algoritmia voidaan tehostaa tulostamalla useampia bittejä kerralla, mutta on selvittämättä, montako voidaan ottaa niin, että seuraavan bitin testi vielä läpäistään.

Käytännössä tyydytään vähempään kuin todistettuun turvallisuuteen. Esim. muutamat standardit käyttävät avainten generointiin algoritmeja, joiden on vain "todettu" toimivan turvallisesti. Erityisesti satunnaisbittien generointiin käytetään muita kryptograafisia primitiivejä, kuten salausalgoritmeja sekä (yksisuuntaisia) tiivistealgoritmeja.

Luettavaksi julkisen avaimen systeemien "klassikko", joka esittelee myös perinteisten kryptosysteemien periaatteita: W. Diffie, M.E.Hellman: New directions in cryptography. IEEE Trans. on Inf. Theory, 22, 1976, 644-655.