RNG-toteutusten testaaminen ja validointi

Satunnaislukugeneraattorien testaamiseen liittyy perustavanlaatuinen haaste: aidosti satunnaiset jonot ja hyvän PRNG:n tuottamat pseudorandom-jonot näyttävät tilastollisissa testeissä samanlaisilta. Mikään äärellisen pituinen testi ei voi todistaa jonoa satunnaiseksi — tilastollisin menetelmin voidaan vain havaita ei-satunnaisuutta tietyllä varmuudella. Testaamisella voidaan varmistaa, ettei RNG:ssä ole ilmeisiä vinoumia tai kuvioita, mutta kryptografista turvallisuutta ei voida todistaa. Kryptografisella RNG-testauksella on kaksi erillistä tavoitetta: (1) tilastollinen laatu — varmistetaan, että tulosteen jakauma näyttää tasaiselta ja riippumattomalta; (2) kryptografinen vahvuus — varmistetaan, että DRBG-algoritmi on toteutettu oikein ja että turvallisuutta koskevat väitteet pitävät paikkansa. Näihin tarvitaan erilaisia testausmenetelmiä.

NIST SP 800-22 sisältää 15 tilastollista testiä bittijonojen arviointiin. Testeihin kuuluvat seuraavat: Frequency-testi (monobit-testi) — ykkösten osuuden pitäisi olla lähellä arvoa 0.5. Block frequency -testi — ykkösten esiintymistiheys jokaisessa m-bittisessä lohkossa. Runs-testi — samanlaisista biteistä muodostuvien katkeamattomien jaksojen määrä. Longest run -testi — pisimmän ykkösjakson pituus. Binary matrix rank -testi — jonosta muodostettujen binäärimatriisien rangi. Spectral-testi (DFT) — jaksottaisten kuvioiden havaitseminen. Overlapping template matching -testi — tiettyjen kuvioiden esiintymien laskeminen. Maurerin universal statistical test — jono pakataan ja mitataan, kuinka paljon se lyhenee. Jokainen testi tuottaa p-arvon; p < 0.01 viittaa ei-satunnaisuuteen. Testit suoritetaan 1 miljoonalle–1 miljardille bitille.

TestU01 (L'Ecuyer ja Simard, 2007) on kattava tilastollisten testien kokonaisuus, jota käytetään laajalti RNG-yhteisössä. SmallCrush: 10 testiä, noin 35 sekuntia, sopii nopeisiin tarkistuksiin. Crush: 144 testiä, noin 2 tuntia. BigCrush: 160 testiä, noin 24 tuntia. BigCrushin testit havaitsevat hienovaraisia korrelaatioita, joita NIST SP 800-22 ei havaitse. Hyvin suunnitellut kryptografiset DRBG:t (HMAC_DRBG, CTR_DRBG) läpäisevät BigCrushin ongelmitta — niiden tulostetta ei voi polynomiaikaisilla algoritmeilla erottaa laskennallisesti satunnaisesta. Ei-kryptografiset PRNG:t (Mersenne Twister, lineaariset kongruenssigeneraattorit) epäonnistuvat joissakin BigCrushin testeissä. BigCrush-testin epäonnistuminen on vahva osoitus siitä, ettei RNG:tä pitäisi käyttää kryptografisiin tarkoituksiin.

SP 800-90B ja 90A määrittelevät kuntotestit, jotka DRBG:iden on suoritettava jatkuvasti käytön aikana. Continuous RNG Test (CRNGT): jokaista tuotettua lohkoa verrataan edelliseen lohkoon — jos ne ovat yhtä suuret (RNG on jumiutunut), DRBG:n on siirryttävä virhetilaan ja lopetettava tuottaminen. Repetition Count Test: jos peräkkäisissä näytteissä sama arvo toistuu useammin kuin entropia-arvion perusteella tilastollisesti pitäisi odottaa, testi epäonnistuu. Adaptive Proportion Test: jos yleisin arvo esiintyy ikkunassa kynnysarvoa useammin, testi epäonnistuu. Näillä kuntotesteillä havaitaan entropialähteen vikoja (jumiutunut anturi, HWRNG-laitteistovika) ennen kuin ne vaarantavat kryptografisten avainten luonnin huomaamatta.

PractRand on nykyaikainen RNG-testaustyökalu, joka on suunniteltu verkossa tapahtuvaan eli suoratoistona tehtävään arviointiin. Se analysoi jonoa sen muodostamisen aikana eikä edellytä ennalta määrättyä pituutta. Se käyttää muun muassa aukkotestejä, bittijakaumatestejä ja spektritestejä mukautuvalla tarkkuudella. PractRand havaitsee erityisen tehokkaasti RNG:t, jotka tuottavat hyviä lyhyitä jonoja mutta paljastavat kuvioita miljardien bittien aikana. Kryptografiset DRBG:t tuottavat tulostetta, jota PractRand ei pysty erottamaan satunnaisesta pituudesta riippumatta — tämä on laskennallisen erottamattomuuden käytännön määritelmä. PractRandia käytetään myös entropialähteiden arviointiin (testaamalla /dev/urandomin ja RDRANDin tulostetta), jotta laitteistoviat tai systemaattiset vinoumat voidaan havaita.

Cryptographic Algorithm Validation Program (CAVP) tarjoaa viralliset testivektorit SP 800-90A:n DRBG:ille. CAVP-testauksessa toteutus toimitetaan NIST:n automaattiseen testijärjestelmään, jossa käytetään tunnetun vastauksen testivektoreita (KAT): tietyn entropiasyötteen, noncen, personalization stringin ja additional_inputin perusteella toteutuksen on tuotettava täsmälleen odotetut tulostebitit. CAVP ei testaa tilastollisia ominaisuuksia, vaan algoritmista oikeellisuutta. FIPS 140-3 -sertifiointi edellyttää CAVP-validointia kaikille moduulin rajojen sisällä käytettäville kryptografisille algoritmeille. CAVP-testivektorit ovat julkisesti saatavilla NIST:n ACVP-palvelimella (Automated Crypto Validation Protocol), ja ne on integroitu OpenSSL:n, mbedTLS:n ja BoringSSL:n testisarjoihin.

Ennen kuin DRBG voidaan alustaa turvallisesti, sen entropialähde on validoitava. SP 800-90B määrittelee seuraavat asiat: (1) Entropia-arvio — todellinen entropia bittiä kohden mitataan tilastollisin testein (minimientropian arviointi). (2) Käynnistystestit — varmistetaan, että entropialähde tuottaa kelvollista tulostetta ennen ensimmäistä käyttökertaa. (3) Tarvittaessa suoritettavat testit — sovellus voi käynnistää ne. (4) Kohinalähteen kuntotestit — havaitaan laitteiston heikkeneminen. Yleisiä entropialähteitä ja niiden arvioitu entropia bittiä kohden ovat seuraavat: suorittimen RDRAND/RDSEED (noin 1 bitti/bitti, laitteistovarmennettu); /dev/urandom (yhdistää useita lähteitä, entropia-arvio on varovainen); rengasoskillaattoriin perustuva TRNG (0,5–0,9 bittiä/bitti mallista riippuen); ADC-kohina (0,1–0,5 bittiä/bitti). SP 800-90B:n validointi edellyttää laboratoriotestausta erikoislaitteistolla.

Virtuaaliympäristöt tuovat mukanaan erityisiä RNG:n testaushaasteita. Virtuaalikoneissa voi käynnistyksen aikana olla vähän entropiaa (laitteistotapahtumia ei ole) tai entropia voi puuttua tilannevedoksen palauttamisen jälkeen (tila nollautuu). Docker-kontit käyttävät isäntäkoneen ytimen RNG:tä — kontti ei voi testata suoraan taustalla olevan entropian laatua. Virtuaalikoneympäristöjen testit: (1) Mitatkaa, kuinka kauan /dev/random-lukuoperaation valmistuminen kestää — pitkät odotusajat viittaavat riittämättömään entropiaan. (2) Testatkaa, syntyykö rinnakkain suoritetuissa virtuaalikoneinstansseissa päällekkäisiä UUID-tunnisteita tai avaimia (tämä on pilviympäristöissä dokumentoitu todellinen vikatilanne). (3) Varmistakaa, että VIRTIO-RNG (virtio_rng.ko) on ladattu virtuaalikoneisiin — se syöttää entropiaa isäntäkoneelta vieraskäyttöjärjestelmään. (4) Auditoikaa sovelluksen käynnistysjärjestys: tapahtuuko avainten luonti ennen kuin entropiaa on saatavilla riittävästi?

RNG:n fork-turvallisuuden testaaminen ehkäisee hienovaraista haavoittuvuutta: kun prosessi forkataan, sekä isäntä- että lapsiprosessi käyttävät samaa DRBG-tilaa, minkä vuoksi ne tuottavat identtisiä jonoja. Havaitseminen: luokaa N lapsiprosessia, muodostakaa kussakin UUID ja varmistakaa, että kaikki UUID:t ovat yksilöllisiä. Jos mitkä tahansa kaksi täsmäävät, RNG ei ole fork-turvallinen. OpenSSL korjasi fork-turvallisuuteen liittyvän virheen vuonna 2020 (CVE-2020-1971 ei liittynyt suoraan DRBG:hen, mutta toimintamalli on samankaltainen). Nykyinen OpenSSL käyttää PID-pohjaista siemenarvon päivitystä: jos PID on muuttunut edellisen kutsun jälkeen (mikä osoittaa fork-operaation tapahtuneen), DRBG saa automaattisesti uuden siemenarvon. Testatkaa tämä suorittamalla testi ennen fork-operaatiota ja sen jälkeen sekä varmistamalla, että uudelleensiemennys tapahtui tarkistamalla tulosten olevan erilaisia.

Käytännöllinen RNG-toteutusten auditointilista: (1) Alustetaanko RNG käyttöjärjestelmästä (getrandom, BCryptGenRandom) aikaperusteisten siemenarvojen sijaan? (2) Onko DRBG-tyyppi NIST SP 800-90A:n hyväksymä mekanismi (Hash, HMAC, CTR)? (3) Onko siemenarvo riittävän pitkä ilmoitettuun turvallisuusvahvuuteen nähden? (4) Käynnistetäänkö uudelleensiemennys säännöllisesti tai tietyn generate-kutsujen määrän jälkeen? (5) Käsitteleekö toteutus fork-turvallisuuden (uudelleensiemennys forkin jälkeen)? (6) Ovatko terveystestit käytössä, ja pysäyttävätkö ne järjestelmän vikatilanteessa? (7) Nollataanko tila sammutuksen yhteydessä? (8) Suoritetaanko CAVP-testivektorit CI/CD:ssä? (9) Ovatko entropia-arviot dokumentoitu ja validoitu? (10) FIPS-vaatimusten osalta: onko moduuli FIPS 140-3 -sertifioitu?

Historialliset RNG-virheet osoittavat, kuinka paljon on pelissä. Debian OpenSSL (2006–2008): korjaustiedosto poisti vahingossa kaksi entropian keräämiseen käytetyn koodin riviä, jolloin siemenpooli pieneni 15-bittiseksi PID-avaruudeksi — koko Debian-käyttäjäkunnalle tuotettiin vain 32 767 mahdollista SSH-avainta. Kaikki Debianilla luodut SSH-palvelinavaimet ja käyttäjäavaimet oli vaihdettava. Androidin Bitcoin-lompakot (2013): Androidin SecureRandom käytti Java-tason siemenarvon alustusta, joka epäonnistui joissakin laitteissa, minkä seurauksena ECDSA-allekirjoitusten k-arvot toistuivat — tämä paljasti yksityiset avaimet suoraan. Sony PS3 (2010): käytti ECDSA-laiteohjelmiston allekirjoituksessa vakioarvoista noncea, mikä mahdollisti yksityisen avaimen selvittämisen kahdesta allekirjoituksesta (sama k eri viesteillä paljastaa avaimen yksinkertaisella algebralla).

Tilastolliset testit (NIST SP 800-22, TestU01 BigCrush, PractRand) tarkistavat tulosteen laadun, mutta eivät voi todistaa salausteknistä turvallisuutta. CAVP:n tunnetun vastauksen testit varmistavat SP 800-90A -toteutusten algoritmisen oikeellisuuden. SP 800-90B:n entropialähdetestit (min-entropian arviointi ja terveystestit) validoivat siemenarvon syötteen. Continuous RNG Test (CRNGT) havaitsee jumiutuneen tulosteen reaaliajassa. Virtuaalikone- ja konttikäyttöönotot edellyttävät entropian syöttämistä (VIRTIO-RNG) ja käynnistyksen aikaisia entropiatarkistuksia. Fork-turvallisuuden testaus varmistaa, etteivät lapsiprosessit peri isäntäprosessin DRBG-tilaa. Todelliset vikatapaukset (Debian, Android) osoittavat, että RNG-virheet johtavat suoraan kryptografisten avainten vaarantumiseen. Auditointilistat muodostavat näistä tarkistuksista muodollisen käytännön tuotantokäyttöönottoja varten.