Testing og validering av RNG-implementasjoner

Testing av tilfeldige tallgeneratorer står overfor en grunnleggende utfordring: Sekvenser som er virkelig tilfeldige, og pseudotilfeldige sekvenser fra en god PRNG, ser identiske ut for statistiske tester. Ingen test av endelig lengde kan bevise at en sekvens er tilfeldig — statistiske metoder kan bare avdekke ikke-tilfeldighet med en viss sikkerhet. Testing bekrefter at en RNG ikke har åpenbare skjevheter eller mønstre, men kan ikke bevise kryptografisk sikkerhet. Testing av kryptografiske RNG-er har to forskjellige mål: (1) statistisk kvalitet — å kontrollere at utdatafordelingen ser uniform og uavhengig ut; (2) kryptografisk styrke — å kontrollere at DRBG-algoritmen er riktig implementert, og at sikkerhetspåstandene holder. Disse målene krever ulike testmetoder.

NIST SP 800-22 inneholder 15 statistiske tester for evaluering av bitsekvenser. Testene omfatter: Frekvenstest (monobit-test) — andelen 1-biter bør ligge nær 0,5. Blokkfrekvenstest — frekvensen av 1-biter i hver blokk på m biter. Runs-test — antallet sammenhengende serier med identiske biter. Test av lengste serie — lengden på den lengste serien med 1-biter. Rangtest for binærmatriser — rangen til binærmatriser som dannes fra sekvensen. Spektraltest (DFT) — avdekker periodiske mønstre. Overlappende malgjenkjenning — teller forekomster av bestemte mønstre. Maurers universelle statistiske test — komprimerer sekvensen og måler hvor mye kortere den blir. Hver test produserer en p-verdi; p < 0.01 tyder på ikke-tilfeldighet. Testene kjøres på fra 1 million til 1 milliard biter.

TestU01 (L'Ecuyer og Simard, 2007) er en omfattende samling statistiske tester som er mye brukt i RNG-miljøet. SmallCrush: 10 tester, omtrent 35 sekunder, egnet for raske kontroller. Crush: 144 tester, omtrent 2 timer. BigCrush: 160 tester, omtrent 24 timer. BigCrush avdekker subtile korrelasjoner som NIST SP 800-22 ikke fanger opp. Godt utformede kryptografiske DRBG-er (HMAC_DRBG, CTR_DRBG) består BigCrush uten problemer — utdataene deres er beregningsmessig umulige å skille fra tilfeldige data for algoritmer med polynomisk kjøretid. Ikke-kryptografiske PRNG-er (Mersenne Twister, lineære kongruensgeneratorer) feiler i enkelte BigCrush-tester. At BigCrush feiler, er en sterk indikasjon på at RNG-en ikke bør brukes til kryptografiske formål.

SP 800-90B og 90A angir helsetester som DRBG-er må utføre kontinuerlig under drift. Continuous RNG Test (CRNGT): Hver genererte blokk sammenlignes med den forrige blokken — hvis de er like (en fastlåst RNG), må DRBG-en gå inn i en feiltilstand og slutte å generere. Repetition Count Test: Hvis påfølgende prøver har samme verdi gjentatt flere ganger enn det som er statistisk forventet ut fra entropiestimatet, skal testen feile. Adaptive Proportion Test: Hvis den hyppigst forekommende verdien forekommer flere ganger enn en angitt terskel i et vindu, skal testen feile. Disse helsetestene oppdager feil i entropikilden (en fastlåst sensor eller en maskinvarefeil i HWRNG) før de i det stille svekker genereringen av kryptografiske nøkler.

PractRand er et moderne verktøy for RNG-testing, utviklet for løpende (strømmende) evaluering. Det analyserer sekvensen etter hvert som den genereres, i stedet for å kreve en forhåndsbestemt lengde. Verktøyet bruker blant annet avstandstester, tester av bitfordeling og spektraltester med adaptiv presisjon. PractRand er spesielt effektivt til å oppdage RNG-er som produserer gode korte sekvenser, men avslører mønstre over milliarder av biter. Kryptografiske DRBG-er produserer utdata som PractRand ikke kan skille fra tilfeldige data, uansett lengde — dette er den operative definisjonen av beregningsmessig umulighet av å skille dataene fra tilfeldige data. PractRand brukes også til å evaluere entropikilder (ved å teste utdata fra /dev/urandom og RDRAND) for å oppdage maskinvarefeil eller systematiske skjevheter.

Cryptographic Algorithm Validation Program (CAVP) tilbyr offisielle testvektorer for DRBG-er i SP 800-90A. CAVP-testing innebærer at en implementasjon sendes inn til NISTs automatiserte testsystem med KAT-vektorer (known-answer test): Gitt et bestemt entropiinndata, en nonce, en personaliseringsstreng og additional_input, må implementasjonen produsere nøyaktig de forventede utdata-bitene. CAVP tester ikke statistiske egenskaper — det tester algoritmisk korrekthet. FIPS 140-3-sertifisering krever CAVP-validering for alle kryptografiske algoritmer som brukes innenfor modulgrensen. CAVP-testvektorene er offentlig tilgjengelige fra NISTs ACVP-server (Automated Crypto Validation Protocol) og er integrert i testpakkene til OpenSSL, mbedTLS og BoringSSL.

Før en DRBG kan initialiseres på en sikker måte, må entropikilden valideres. SP 800-90B definerer: (1) Entropiestimat — mål den faktiske entropien per bit ved hjelp av statistiske tester (estimering av min-entropi). (2) Oppstartstester — kontroller at entropikilden produserer gyldige data før første bruk. (3) Tester ved behov — valgfrie tester som utløses av applikasjonen. (4) Helsetester for støykilden — oppdag maskinvareforringelse. Vanlige entropikilder og estimert entropi per bit: CPU RDRAND/RDSEED (omtrent 1 bit/bit, maskinvaresertifisert); /dev/urandom (blander flere kilder, entropiestimatet er konservativt); ringoscillator-TRNG (0,5–0,9 bit/bit, avhengig av designet); ADC-støy (0,1–0,5 bit/bit). Validering i henhold til SP 800-90B krever laboratorietesting med spesialisert utstyr.

Virtuelle miljøer medfører særskilte utfordringer ved testing av RNG-er. VM-er kan ha forhold med lav entropi ved oppstart (ingen maskinvarehendelser) eller etter gjenoppretting av et øyeblikksbilde (tilstanden er tilbakestilt). Docker-containere deler vertskjernens RNG — en container kan ikke teste kvaliteten på den underliggende entropien direkte. Tester for VM-distribusjoner: (1) Mål tiden det tar før lesing fra /dev/random fullføres — lange ventetider indikerer utilstrekkelig entropi. (2) Test om UUID-er eller nøkler som genereres parallelt i VM-instanser, blir duplikater (en reell feilmodus som er dokumentert i skybaserte distribusjoner). (3) Bekreft at VIRTIO-RNG (virtio_rng.ko) er lastet inn i VM-ene — dette tilfører entropi fra verten til gjesten. (4) Kontroller programmets oppstartssekvens: skjer nøkkelgenereringen før tilstrekkelig entropi er tilgjengelig?

Testing av RNG-ens fork-sikkerhet forhindrer en subtil sårbarhet: når en prosess kaller fork, deler foreldreprosessen og barneprosessen den samme DRBG-tilstanden, slik at de genererer identiske sekvenser. Slik oppdages dette: Opprett N underordnede prosesser, generer en UUID i hver av dem, og bekreft at alle UUID-ene er unike. Hvis to av dem er like, er RNG-en ikke fork-sikker. OpenSSL rettet en fork-sikkerhetsfeil i 2020 (CVE-2020-1971 gjaldt ikke DRBG direkte, men mønsteret er tilsvarende). Dagens OpenSSL bruker en PID-basert seed-oppdatering: Hvis PID-en er endret siden forrige kall (noe som indikerer en fork), seedes DRBG-en automatisk på nytt. Slik testes dette: Kjør testen før og etter en fork, og bekreft at ny seeding fant sted ved å kontrollere at resultatene er forskjellige.

En praktisk sjekkliste for revisjon av RNG-implementasjoner: (1) Initialiseres RNG-en fra operativsystemet (getrandom, BCryptGenRandom) i stedet for med tidsbaserte seed-verdier? (2) Er DRBG-typen en godkjent mekanisme i NIST SP 800-90A (Hash, HMAC, CTR)? (3) Er seed-lengden tilstrekkelig for den oppgitte sikkerhetsstyrken? (4) Utløses reseeding med jevne mellomrom eller etter et fast antall genereringskall? (5) Håndterer implementasjonen fork-sikkerhet (reseeding etter fork)? (6) Er helsetester aktivert, og stanser de systemet ved feil? (7) Nullstilles tilstanden ved avslutning? (8) Kjøres CAVP-testvektorer i CI/CD? (9) Er entropiestimater dokumentert og validert? (10) For FIPS-krav: er modulen FIPS 140-3-sertifisert?

Historiske RNG-svikt viser hvor alvorlige konsekvensene kan være. Debian OpenSSL (2006–2008): En patch fjernet ved en feil to linjer med kode for innsamling av entropi, noe som reduserte seed-poolen til et 15-biters PID-område — bare 32 767 mulige SSH-nøkler ble generert for hele Debian-brukerbasen. Alle Debian-genererte SSH-vertsnøkler og brukernøkler måtte erstattes. Android Bitcoin-lommebøker (2013): Androids SecureRandom brukte seeding på Java-nivå som sviktet på enkelte enheter, noe som førte til dupliserte k-verdier i ECDSA-signaturer — dette avslørte de private nøklene direkte. Sony PS3 (2010): brukte en konstant nonce i ECDSA-fastvaresigneringen, noe som gjorde det mulig å hente ut den private nøkkelen fra to signaturer (samme k i forskjellige meldinger avslører nøkkelen ved enkel algebra).

Statistiske tester (NIST SP 800-22, TestU01 BigCrush, PractRand) bekrefter kvaliteten på resultatene, men kan ikke bevise kryptografisk sikkerhet. CAVP-tester med kjente svar bekrefter algoritmisk korrekthet for implementasjoner av SP 800-90A. Tester av entropikilder i SP 800-90B (estimering av min-entropi og helsetester) validerer seed-inndataene. Continuous RNG Test (CRNGT) oppdager fastlåste resultater i sanntid. VM- og containerdistribusjoner krever entropitilførsel (VIRTIO-RNG) og kontroller av entropi ved oppstart. Fork-sikkerhetstesting bekrefter at underordnede prosesser ikke arver foreldreprosessens DRBG-tilstand. Reelle svikt (Debian, Android) viser at RNG-feil kan føre direkte til kompromittering av kryptografiske nøkler. Sjekklister for revisjon formaliserer disse kontrollene for produksjonsdistribusjoner.