Testning och validering av RNG-implementationer

Testning av slumptalsgeneratorer står inför en grundläggande utmaning: verkligt slumpmässiga sekvenser och pseudoslumpmässiga sekvenser från en bra PRNG ser identiska ut för statistiska tester. Inget test av en ändlig sekvenslängd kan bevisa att en sekvens är slumpmässig — statistik kan bara upptäcka icke-slumpmässighet med en viss grad av säkerhet. Testning verifierar att en RNG inte har uppenbara skevheter eller mönster, men kan inte bevisa kryptografisk säkerhet. Testning av kryptografiska RNG:er har två skilda mål: (1) statistisk kvalitet — att verifiera att utdatas fördelning ser likformig och oberoende ut; (2) kryptografisk styrka — att verifiera att DRBG-algoritmen är korrekt implementerad och att säkerhetsanspråken håller. Dessa mål kräver olika testmetoder.

NIST SP 800-22 innehåller 15 statistiska test för utvärdering av bitsekvenser. Testerna omfattar: frekvenstest (monobit-test) — andelen ettor bör ligga nära 0,5. Blockfrekvenstest — frekvensen av ettor i varje block om m bitar. Runs-test — antalet sammanhängande sekvenser av identiska bitar. Test av längsta sekvens — längden på den längsta sekvensen av ettor. Rangtest av binär matris — rangen hos binära matriser som bildats från sekvensen. Spektraltest (DFT) — upptäcker periodiska mönster. Test av överlappande mallar — räknar förekomsten av specifika mönster. Maurers universella statistiska test — komprimerar sekvensen och mäter hur mycket kortare den blir. Varje test ger ett p-värde; p < 0.01 tyder på icke-slumpmässighet. Testerna körs på sekvenser med 1 miljon till 1 miljard bitar.

TestU01 (L'Ecuyer och Simard, 2007) är en omfattande uppsättning statistiska test som används brett inom RNG-communityn. SmallCrush: 10 test, cirka 35 sekunder, lämpligt för snabba kontroller. Crush: 144 test, cirka 2 timmar. BigCrush: 160 test, cirka 24 timmar. BigCrush upptäcker subtila korrelationer som NIST SP 800-22 missar. Välkonstruerade kryptografiska DRBG:er (HMAC_DRBG, CTR_DRBG) klarar BigCrush utan problem — deras utdata kan beräkningsmässigt inte skiljas från slumpmässig utdata av algoritmer med polynomisk körtid. Icke-kryptografiska PRNG:er (Mersenne Twister, linjära kongruensgeneratorer) misslyckas med vissa BigCrush-test. Ett BigCrush-fel är en stark indikation på att RNG:n inte bör användas för kryptografiska ändamål.

SP 800-90B och 90A specificerar hälsotester som DRBG:er måste utföra kontinuerligt under drift. Continuous RNG Test (CRNGT): varje genererat block jämförs med föregående block — om de är identiska (slumptalsgeneratorn har hängt sig) måste DRBG:n gå in i ett feltillstånd och sluta generera. Repetition Count Test: om konsekutiva sampel har samma värde upprepat fler gånger än vad som är statistiskt förväntat med hänsyn till entropiskattningen ska testet underkännas. Adaptive Proportion Test: om det mest frekventa värdet förekommer fler gånger i ett fönster än tröskelvärdet ska testet underkännas. Dessa hälsotester upptäcker fel i entropikällan (en sensor som hängt sig, ett hårdvarufel i HWRNG) innan de i tysthet äventyrar genereringen av kryptografiska nycklar.

PractRand är ett modernt verktyg för testning av slumptalsgeneratorer, utformat för onlineutvärdering (strömmande utvärdering). Det analyserar sekvensen allt eftersom den genereras i stället för att kräva en förutbestämd längd. Verktyget tillämpar bland annat lucktester, bitfördelningstester och spektraltester med adaptiv precision. PractRand är särskilt effektivt för att upptäcka slumptalsgeneratorer som producerar bra korta sekvenser men avslöjar mönster över miljarder bitar. Kryptografiska DRBG:er producerar utdata som PractRand inte kan skilja från slumpmässig utdata, oavsett sekvensens längd — detta är den praktiska definitionen av beräkningsmässig omöjlighet att skilja från slump. PractRand används också för att utvärdera entropikällor (genom att testa utdata från /dev/urandom och RDRAND) och upptäcka hårdvarufel eller systematiska skevheter.

Cryptographic Algorithm Validation Program (CAVP) tillhandahåller officiella testvektorer för SP 800-90A DRBG:er. CAVP-testning innebär att en implementation skickas in till NIST:s automatiserade testsystem med known-answer-testvektorer (KAT): givet en specifik entropiindata, nonce, personaliseringssträng och additional_input måste implementationen producera exakt de förväntade utdatasbitarna. CAVP testar inte statistiska egenskaper — det testar algoritmisk korrekthet. FIPS 140-3-certifiering kräver CAVP-validering för alla kryptografiska algoritmer som används inom modulgränsen. CAVP-testvektorer är offentligt tillgängliga från NIST:s ACVP-server (Automated Crypto Validation Protocol) och integreras i testsviterna för OpenSSL, mbedTLS och BoringSSL.

Innan en DRBG kan initieras på ett säkert sätt måste dess entropikälla valideras. SP 800-90B definierar: (1) Entropiskattning — mät den faktiska entropin per bit med statistiska test (minentropiskattning). (2) Starttester — verifiera att entropikällan producerar giltig utdata före den första användningen. (3) Tester på begäran — valfria tester som utlöses av applikationen. (4) Hälsotester för bruskälla — upptäck försämring av hårdvaran. Vanliga entropikällor och deras uppskattade entropi per bit: CPU RDRAND/RDSEED (~1 bit/bit, hårdvarucertifierad); /dev/urandom (blandar flera källor, entropiskattningen är konservativ); TRNG baserad på ringoscillator (0,5–0,9 bitar/bit beroende på konstruktion); ADC-brus (0,1–0,5 bitar/bit). Validering enligt SP 800-90B kräver laboratorietester med specialiserad utrustning.

Virtuella miljöer medför särskilda utmaningar vid testning av RNG:er. VM:er kan ha låg entropi vid uppstart (inga hårdvaruhändelser) eller efter återställning av en ögonblicksbild (tillståndet återställs). Docker-containrar delar värdkärnans RNG – en container kan inte direkt testa den underliggande entropikvaliteten. Tester av VM-driftsättningar: (1) Mät tiden tills läsningen från /dev/random är klar – långa väntetider tyder på otillräcklig entropi. (2) Testa om UUID:er eller nycklar som genereras parallellt i VM-instanser blir identiska (ett verkligt felscenario som har dokumenterats i molndriftsättningar). (3) Kontrollera att VIRTIO-RNG (virtio_rng.ko) är laddad i VM:er – detta tillför entropi från värden till gästen. (4) Granska programmets uppstartssekvens: sker nyckelgenereringen innan tillräcklig entropi är tillgänglig?

Testning av fork-säkerhet förhindrar en subtil sårbarhet: när en process gör en fork delar både föräldraprocessen och barnprocessen samma DRBG-tillstånd, vilket får dem att generera identiska sekvenser. Upptäckt: skapa N barnprocesser, generera en UUID i var och en och verifiera att alla UUID:er är unika. Om två matchar är RNG:n inte fork-säker. OpenSSL åtgärdade en bugg i fork-säkerheten 2020 (CVE-2020-1971 gällde inte DRBG direkt, men mönstret är liknande). Aktuella versioner av OpenSSL använder en PID-baserad seeduppdatering: om PID har ändrats sedan det senaste anropet (vilket visar att en fork har skett) seedas DRBG automatiskt om. Så testar du detta: kör testet före och efter en fork och bekräfta att omseedningen ägde rum genom att verifiera att utdata skiljer sig åt.

En praktisk checklista för granskning av RNG-implementationer: (1) Initieras RNG:n från operativsystemet (getrandom, BCryptGenRandom) i stället för med tidsbaserade seedvärden? (2) Är DRBG-typen en NIST SP 800-90A-godkänd mekanism (Hash, HMAC, CTR)? (3) Är seedlängden tillräcklig för den angivna säkerhetsstyrkan? (4) Utlöses omseedning periodiskt eller efter ett fast antal genereringsanrop? (5) Hanterar implementationen fork-säkerhet (omseedning efter fork)? (6) Är hälsotester aktiverade, och stoppar de systemet vid fel? (7) Nollställs tillståndet vid avstängning? (8) Körs CAVP-testvektorer i CI/CD? (9) Är entropiskattningarna dokumenterade och validerade? (10) För FIPS-krav: är modulen FIPS 140-3-certifierad?

Historiska RNG-fel visar hur allvarliga konsekvenserna kan bli. Debian OpenSSL (2006–2008): en patch tog av misstag bort två rader kod för entropiinsamling, vilket minskade seedpoolen till ett 15-bitars PID-utrymme – endast 32 767 möjliga SSH-nycklar genererades för hela Debian-användarbasen. Alla Debian-genererade SSH-värdnycklar och användarnycklar behövde ersättas. Android Bitcoin-plånböcker (2013): Androids SecureRandom använde en seedning på Java-nivå som misslyckades på vissa enheter, vilket ledde till duplicerade k-värden i ECDSA-signaturer – detta avslöjade privata nycklar direkt. Sony PS3 (2010): använde en konstant nonce i sin ECDSA-signering av firmware, vilket gjorde det möjligt att extrahera privata nycklar från två signaturer (samma k i olika meddelanden avslöjar nyckeln genom enkel algebra).

Statistiska tester (NIST SP 800-22, TestU01 BigCrush, PractRand) verifierar kvaliteten på utdata men kan inte bevisa kryptografisk säkerhet. CAVP:s known-answer-tester verifierar algoritmisk korrekthet hos implementationer av SP 800-90A. SP 800-90B-tester av entropikällor (skattning av min-entropi, hälsotester) validerar seed-indata. Continuous RNG Test (CRNGT) upptäcker fastnad utdata i realtid. Driftsättning i VM:er och containrar kräver entropitillförsel (VIRTIO-RNG) och kontroller av entropi vid uppstart. Fork-säkerhetstestning verifierar att barnprocesser inte ärver förälderns DRBG-tillstånd. Verkliga fel (Debian, Android) visar att RNG-buggar direkt leder till att kryptografiska nycklar komprometteras. Checklistor för granskning formaliserar dessa kontroller för produktionsdriftsättningar.