Satunnaisluvut kryptografiassa

Kryptografiassa satunnaisuus on elintärkeä ominaisuus jota tarvitaan esimerkiksi turvallisten salausavainten luomiseen.

Satunnaisuus: Mitä se tarkoittaa?

Satunnaisuus viittaa siihen, että tapahtuman tai tuloksen ennustettavuus on mahdotonta tai erittäin vaikeaa. Kryptografiassa satunnaiset luvut ovat arvaamattomia ja niiden tulisi olla tasaisesti jakautuneita kaikkien mahdollisten arvojen joukossa.

Miten satunnaisluvun voisi saada? Näppärä mutta turvaton tapa LCG:n (Linear Congruential Generator) avulla

Mikä on LCG?

LCG (Linear Congruential Generator) on yksinkertainen ja tehokas algoritmi satunnaislukujen generointiin. Se perustuu seuraavaan kaavaan:

X_n+1 = (a * X_n + c) mod m

missä:

• X_n on n:nnen satunnaisluvun arvo
• a on vakio, jota kutsutaan "kertoimeksi"
• c on vakio, jota kutsutaan "lisäykseksi"
• m on moduuli, joka rajoittaa tulostettavien lukujen arvoa
• mod on modulo-operaattori, joka palauttaa luvun jakojäännöksen

LCG:n käyttö

• Alusta X_0 alkuarvolla, joka ei ole jaollinen moduulilla m. Tätä alkuarvoa kutsutaan siemeneksi (seed).
• Laske seuraava luku X_n+1 kaavan avulla.
• Toista vaihetta 2 saadaksesi lisää satunnaislukuja.

LCG havainnollistava esimerkki

Tässä on esimerkki LCG:n toiminnasta pienillä arvoilla havainnollistamiseksi:

Parametrit:

• a = 3
• c = 1
• m = 7

Alkuarvo (seed):

• X_0 = 2

Luvujen generointi:

Lasketaan X_1 = (3 * 2 + 1) mod 7 = 7 mod 7 = 0.

Lasketaan X_2 = (3 * 0 + 1) mod 7 = 1 mod 7 = 1.

Lasketaan X_3 = (3 * 1 + 1) mod 7 = 4 mod 7 = 4.

Lasketaan X_4 = (3 * 4 + 1) mod 7 = 13 mod 7 = 6.

Lasketaan X_5 = (3 * 6 + 1) mod 7 = 19 mod 7 = 5.

Lasketaan X_6 = (3 * 5 + 1) mod 7 = 16 mod 7 = 2.

LCG:n ominaisuudet

• Nopea ja tehokas: LCG on erittäin nopea ja tehokas algoritmi satunnaislukujen generointiin.
• Yksinkertainen: LCG:n kaava on yksinkertainen ja helppo ymmärtää.
• Ennustettavuus: LCG on ennustettavissa, jos alkuarvo, kerroin, lisäys ja moduuli tunnetaan.

LCG ei ole kryptografisesti turvallinen

LCG ei ole tarkoitettu olemaan kryptografisesti turvallinen, ja sen erehtyminen käyttämään sellaisena (esimerkiksi salausavainten tai vaikkapa sovelluksen istuntotunnisteiden luomiseen) johtaa vakaviin haavoittuvuuksiin.

LCG:n tapauksessa ainoa "salaisuus" on tyypillisesti seed-arvo, eli siemen jolla LCG on alustettu. Jos hyökkääjä saa sen tietoonsa, hyökkääjän on mahdollista ennustaa sekä kaikki tulevat että kaikki menneet arvot joita on luotu.

Esimerkiksi sovelluksen istuntotunnisteiden osalta tämä tarkoittaisi että hyökkääjä voisi kävellä taaksepäin kaikki käyttäjille annetut istuntotunnisteet ja kirjautua kenenä tahansa käyttäjänä jolla on voimassa oleva istunto, tai odotella että jollekin käyttäjälle annetaan seuraava istuntotunniste ja kaapata sitten se.

Ajatusleikki: LCG ja lottonumerot

Oletetaan, että lottoarvonnassa käytettäisiin LCG:tä satunnaislukujen generointiin. Jaska kekkaa tämän ja tekee rikastumissuunnitelman. Oletetaan yksinkertaistuksen nimissä että Jaskalla on tiedossa kerroin (a) ja lisäys (c) ja modulo (m). Nämä ovat harvoin salaisuuksia.

• Ensin Jaska lataa listan vanhoja lottorivejä tietokoneelleen.
• Sitten jaska yhdistää lottorivien numerot yhdeksi rimpsuksi jossa on vaikkapa 100 viimeisintä arvonnan ennustamaa numeroa.
• Seuraavaksi Jaska alkaa brute force -tekniikalla kokeilemaan yhtä siemenarvoa toisen jälkeen. 1... 2... 3.. 4.... Jaksa käyttää hurjasti laskentatehoa ja kokeilee valtavan määrän eri siemenarvoja sekunnissa.
• Lopulta Jaska löytää yhden simenarvon: 3827182, joka johtaisi juuri näihin 100 numeroon mitä lottoarvonnassa on viimeksi ennustettu.
• Jaska tarkistaa vielä että siemen oli tosiaan oikea ja kokeilee mennä LCG:llä taaksepäin ja varmistaa että numerot ovat samoja kuin vielä aiemmat lottonumerot. Ne ovat.
• Nyt Jaska on varma onnistumisestaan. Jaska menee LCG:llä eteenpäin 7 numeroa. 4, 8, 15, 16, 23, 42, 43. Jaskalla on nyt tiedossa seuraavan viikon voittavat lottonumerot.
• Jaska laittaa lottokupongin menemään.

Koodiesimerkki: java.util.Random

Tässä on Java-koodia jossa on kriittinen haavoittuvuus. Miksi? Koska java.util.Random käyttää LCG:tä. Sitä ei ole tarkoitettu kryptografiseen käyttöön, mutta tässä sovellus kuitenkin käyttää sitä istuntotunnisteiden luomiseen.

import java.util.Random;

public class SessionIDGenerator {
    private Random rng;

    public SessionIDGenerator() {
        // Alustetaan Random-olio ilman eksplisiittistä siemenarvoa, jolloin nykyiseen kellonaikaan perustuvaa arvoa käytetään oletuksena
        this.rng = new Random();
    }

    public long generateSessionID() {
        // Generoidaan ja palautetaan uusi istuntotunnus
        return Math.abs(rng.nextLong());
    }
}

Haavoittuvuuden voisi korjata näin. Esona on, että nyt käytetään java.security.SecureRandom luokkaa. Erona on että tämä luokka käyttää taustalla kryptografisesti turvallista PRNG:tä (eli CSPRNG).

import java.security.SecureRandom;

public class SecureSessionIDGenerator {
    private SecureRandom secureRng;

    public SecureSessionIDGenerator() {
        // Alustetaan SecureRandom-olio
        this.secureRng = new SecureRandom();
    }

    public long generateSecureSessionID() {
        // Generoidaan ja palautetaan turvallinen istuntotunnus
        return Math.abs(secureRng.nextLong());
    }

}

Tämä on hyvä pitää mielessä jos joskus teet esimerkiksi tietoturvatarkastusta sovellukselle. Katso sovelluksen koodista että luodaanko siellä satunnaislukuja ja mihin niitä käytetään. Jos niitä käytetään kryptografisiin tarkoituksiin, varmista että käytetty PRNG on kryptografisesti turvallinen!

PRNG: Pseudo satunnaisten lukujen generaattori

LCG kuuluu nk. pseudo-satunnaisien lukujen generaattoreihin (PRNG, pseudo-random number ghenerator).

PRNG on algoritmi, joka tuottaa numerosarjoja, jotka näyttävät satunnaisilta, mutta eivät ole todellisuudessa satunnaisia. Kuten näit, nämä algoritmit perustuvat matemaattisiin kaavoihin ja alkuarvoihin, joita kutsutaan siemeniksi. Sama siemen johtaa aina samaan numerosarjaan.

PRNG:t ovat yleisiä ja tehokkaita, mutta niillä on omat rajoituksensa. Koska ne perustuvat kaavoihin, on mahdollista ennustaa tulevia lukuja tai löytää heikkouksia algoritmista, jotka heikentävät satunnaisuutta.

PRNG:t eivät siis ole oikeasti satunnaisia vaan äärimmäisen deterministisiä. TRNG:t taas ovat toista maata.

TRNG: Todellisten satunnaisten lukujen generaattori

TRNG hyödyntää fyysisiä ilmiöitä, kuten lämpökohinaa tai radioaktiivista hajoamista, satunnaisten lukujen tuottamiseen. Nämä prosessit ovat luonnostaan arvaamattomia ja tuottavat aidosti satunnaisia lukuja.

TRNG:t ovat kalliimpia ja hitaampia kuin PRNG:t, mutta ne tarjoavat korkeamman turvallisuustason. Satunnaisuutta ei voida ennustaa tai manipuloida, mikä tekee niistä erinomaisen vaihtoehdon kryptografisiin sovelluksiin, joissa turvallisuus on kriittinen.

Entropia

Entropia, tietotekniikan ja kryptografian kontekstissa, viittaa arvaamattomuuteen tai satunnaisuuteen, jota käytetään tietoturvasovelluksissa, kuten salausavainten luomisessa. Se on tärkeä käsite, sillä korkea entropiataso tarkoittaa suurempaa arvaamattomuutta, mikä tekee järjestelmän turvallisemmaksi hyökkäyksiltä. Entropiaa voidaan kerätä erilaisista lähteistä, joita yleisesti pidetään arvaamattomina, kuten käyttäjän syötteiden ajoituksesta (esim. näppäimistön painallukset, hiiren liikkeet), laitteiston toiminnasta (esim. levyaseman pyörimisnopeus, verkkojen latenssi), tai jopa ympäristön fyysisistä ilmiöistä (esim. lämpötilan vaihtelut).

Entropian kerääminen ja sen käyttäminen pseudosatunnaislukugeneraattoreissa (PRNG) tai kryptografisesti turvallisissa pseudosatunnaislukugeneraattoreissa (CSPRNG) on kriittistä, jotta voidaan varmistaa, että tuotetut satunnaisluvut ovat riittävän arvaamattomia ja turvallisia. Esimerkiksi Fortuna-algoritmissa (johon mennään kohta) entropian kerääminen ja hallinta on keskeisessä osassa sen suunnittelua, ja se mahdollistaa algoritmin tuottaa korkealaatuista satunnaisuutta, mikä on erityisen tärkeää turvallisuuskriittisissä sovelluksissa.

Miten kryptografisesti turvallisen satunnasluvun voisi saada? Parempi esimerkki Fortunan avulla

Fortuna on kryptografisesti turvallinen pseudosatunnaislukugeneraattori (CSPRNG), jonka ovat suunnitelleet Bruce Schneier ja Niels Ferguson. Fortuna on suunniteltu vastustamaan erilaisia hyökkäystapoja ja tarjoamaan korkean turvallisuustason. Se koostuu useista osista, kuten useista erillisistä lähteistä tulevan entropian keräämisestä, entropian akkumulaattorista, ja useista pseudosatunnaislukugeneraattoreista (PRNG), jotka tuottavat lopullisen satunnaisluvun. Fortuna pystyy vastaanottamaan entropiaa jatkuvasti ja on suunniteltu siten, että se ei kärsi tietyistä matemaattisista ongelmista, jotka voivat heikentää muiden PRNG:ien turvallisuutta.

Summa summarum

Satunnaisuutta on erilaista eri käyttötarkoituksiin. Kun sitä tarvitaan kryptografisiin käyttötarkoituksiin, on elintärkeää valita siihen tarkoitukseen soveltuva satunnaislukugeneraattori!