RNG-implementaties testen en valideren

Het testen van generatoren voor willekeurige getallen kent een fundamentele uitdaging: echt willekeurige reeksen en pseudowillekeurige reeksen van een goede PRNG zien er voor statistische toetsen identiek uit. Geen enkele toets van eindige lengte kan bewijzen dat een reeks willekeurig is — statistiek kan alleen met een bepaalde mate van zekerheid niet-willekeurigheid detecteren. Toetsen controleren of een RNG geen duidelijke vertekeningen of patronen heeft, maar kunnen cryptografische veiligheid niet bewijzen. Het toetsen van cryptografische RNG's heeft twee verschillende doelen: (1) statistische kwaliteit — controleren of de verdeling van de uitvoer uniform en onafhankelijk lijkt; (2) cryptografische sterkte — controleren of het DRBG-algoritme correct is geïmplementeerd en of de beveiligingsclaims standhouden. Hiervoor zijn verschillende toetsbenaderingen nodig.

NIST SP 800-22 biedt 15 statistische toetsen voor het beoordelen van bitreeksen. De toetsen omvatten: de frequentietoets (monobit-toets) — de verhouding enen moet dicht bij 0,5 liggen; de blokfrequentietoets — de frequentie van enen in elk blok van m bits; de reeksen-toets — het aantal ononderbroken reeksen van identieke bits; de toets voor de langste reeks — de lengte van de langste reeks enen; de rangtoets voor binaire matrices — de rang van binaire matrices die uit de reeks zijn gevormd; de spectraaltoets (DFT) — het detecteren van periodieke patronen; overlappende patroonherkenning — het tellen van voorkomens van specifieke patronen; de universele statistische toets van Maurer — de reeks comprimeren en meten hoeveel korter deze wordt. Elke toets levert een p-waarde op; p < 0,01 wijst op niet-willekeurigheid. De toetsen worden uitgevoerd op 1 miljoen tot 1 miljard bits.

TestU01 (L'Ecuyer en Simard, 2007) is een uitgebreide verzameling statistische toetsen die veel wordt gebruikt binnen de RNG-gemeenschap. SmallCrush: 10 toetsen, ongeveer 35 seconden, geschikt voor snelle controles. Crush: 144 toetsen, ongeveer 2 uur. BigCrush: 160 toetsen, ongeveer 24 uur. BigCrush-toetsen detecteren subtiele correlaties die NIST SP 800-22 mist. Goed ontworpen cryptografische DRBG's (HMAC_DRBG, CTR_DRBG) doorstaan BigCrush zonder problemen — hun uitvoer is voor algoritmen met polynomiale looptijd computationeel niet te onderscheiden van willekeurige uitvoer. Niet-cryptografische PRNG's (Mersenne Twister, lineaire congruentiegeneratoren) falen voor sommige BigCrush-toetsen. Falen voor BigCrush is een sterke aanwijzing dat de RNG niet voor cryptografische doeleinden mag worden gebruikt.

SP 800-90B en 90A schrijven voor dat DRBG's tijdens het gebruik voortdurend controles op hun goede werking uitvoeren. Doorlopende RNG-toets (CRNGT): elk gegenereerd blok wordt vergeleken met het vorige blok — als ze gelijk zijn (een vastgelopen RNG), moet de DRBG een fouttoestand binnengaan en stoppen met genereren. Toets voor herhalingsaantallen: als opeenvolgende steekproeven dezelfde waarde vaker herhalen dan op basis van de entropieschatting statistisch wordt verwacht, moet de toets falen. Adaptieve proportietoets: als de meest voorkomende waarde in een venster vaker voorkomt dan een bepaald drempelaantal, moet de toets falen. Deze controles op de goede werking detecteren storingen in entropiebronnen (een vastgelopen sensor, een hardwarestoring in een HWRNG) voordat ze ongemerkt het genereren van cryptografische sleutels in gevaar brengen.

PractRand is een modern hulpmiddel voor het toetsen van RNG's, ontworpen voor online evaluatie waarbij de reeks wordt geanalyseerd terwijl deze wordt gegenereerd, in plaats van dat een vooraf bepaalde lengte vereist is. Het past onder andere gatentoetsen, toetsen voor bitverdelingen en spectraaltoetsen toe, met adaptieve nauwkeurigheid. PractRand is bijzonder effectief in het detecteren van RNG's die korte reeksen goed produceren, maar na miljarden bits patronen onthullen. Cryptografische DRBG's produceren uitvoer die PractRand, ongeacht de lengte, niet van willekeurige uitvoer kan onderscheiden — dit is de operationele definitie van computationele ononderscheidbaarheid. PractRand wordt ook gebruikt om entropiebronnen te beoordelen, bijvoorbeeld door uitvoer van /dev/urandom en RDRAND te toetsen op hardwarestoringen of systematische vertekeningen.

Het Cryptographic Algorithm Validation Program (CAVP) biedt officiële testvectoren voor DRBG's uit SP 800-90A. CAVP-toetsing houdt in dat je een implementatie met known-answer-toetsvectoren (KAT-vectoren) indient bij het geautomatiseerde testsysteem van NIST: bij een specifieke entropie-invoer, nonce, personalisatiestring en additional_input moet de implementatie exact de verwachte uitvoerbits produceren. CAVP toetst geen statistische eigenschappen — het toetst de algoritmische juistheid. Voor FIPS 140-3-certificering is CAVP-validatie vereist voor alle cryptografische algoritmen die binnen de modulegrens worden gebruikt. CAVP-testvectoren zijn openbaar beschikbaar via de ACVP-server van NIST (Automated Crypto Validation Protocol) en zijn geïntegreerd in de toetsverzamelingen van OpenSSL, mbedTLS en BoringSSL.

Voordat een DRBG veilig kan worden geïnitialiseerd, moet zijn entropiebron worden gevalideerd. SP 800-90B definieert: (1) entropieschatting — meet de werkelijke entropie per bit met statistische toetsen (schatting van minimale entropie); (2) opstarttoetsen — verifieer dat de entropiebron vóór het eerste gebruik geldige uitvoer produceert; (3) toetsen op aanvraag — optionele toetsen die door de toepassing worden gestart; (4) controles op de goede werking van ruisbronnen — detecteer achteruitgang van de hardware. Veelgebruikte entropiebronnen en hun geschatte entropie per bit: CPU RDRAND/RDSEED (ongeveer 1 bit/bit, hardwaregecertificeerd); /dev/urandom (combineert meerdere bronnen, de entropieschatting is conservatief); TRNG met ringoscillator (0,5-0,9 bit/bit, afhankelijk van het ontwerp); ADC-ruis (0,1-0,5 bit/bit). Validatie volgens SP 800-90B vereist laboratoriumonderzoek met gespecialiseerde apparatuur.

Virtuele omgevingen brengen specifieke uitdagingen voor het testen van RNG's met zich mee. VM's kunnen bij het opstarten te weinig entropie hebben (geen hardwaregebeurtenissen) of na het herstellen van een momentopname (toestand teruggezet). Docker-containers delen de RNG van de hostkernel — een container kan de onderliggende entropiekwaliteit niet rechtstreeks testen. Toetsen voor VM-implementaties: (1) Meet hoelang het duurt voordat een lezing uit /dev/random is voltooid — lange wachttijden wijzen op onvoldoende entropie. (2) Controleer op dubbele UUID's of sleutels die parallelle VM-instanties genereren (een echte foutmodus die in cloudimplementaties is gedocumenteerd). (3) Controleer of VIRTIO-RNG (virtio_rng.ko) in VM's is geladen — dit levert entropie-injectie van host naar gast. (4) Controleer de opstartvolgorde van de toepassing: vindt het genereren van sleutels plaats voordat er voldoende entropie beschikbaar is?

Het testen van forkveiligheid voorkomt een subtiele kwetsbaarheid: wanneer een proces wordt geforkt, delen het ouder- en het kindproces dezelfde DRBG-toestand, waardoor ze identieke reeksen genereren. Detectie: start N dochterprocessen, genereer in elk proces een UUID en controleer of alle UUID's uniek zijn. Als twee ervan overeenkomen, is de RNG niet forkveilig. OpenSSL herstelde in 2020 een fout in de forkveiligheid (CVE-2020-1971 had niet rechtstreeks betrekking op DRBG, maar het patroon is vergelijkbaar). De huidige versie van OpenSSL gebruikt een op PID gebaseerde zaadbijwerking: als de PID sinds de vorige aanroep is veranderd (wat op een fork wijst), wordt de DRBG automatisch opnieuw van een zaadwaarde voorzien. Test dit door de toets voor en na een fork uit te voeren en te bevestigen dat de herzaaiing heeft plaatsgevonden door verschillende uitvoer te controleren.

Praktische controlelijst voor RNG-implementaties: (1) Wordt de RNG geïnitialiseerd vanuit het besturingssysteem (getrandom, BCryptGenRandom) in plaats van met tijdgebaseerde zaadwaarden? (2) Is het DRBG-type een door NIST SP 800-90A goedgekeurd mechanisme (Hash, HMAC, CTR)? (3) Is de zaadlengte voldoende voor de geclaimde beveiligingssterkte? (4) Wordt periodiek of na een vast aantal aanroepen voor generate opnieuw van een zaadwaarde voorzien? (5) Verwerkt de implementatie forkveiligheid (opnieuw van een zaadwaarde voorzien na fork)? (6) Zijn gezondheidstoetsen ingeschakeld en stoppen ze het systeem bij een fout? (7) Wordt de toestand bij afsluiten op nul gezet? (8) Worden CAVP-toetsvectoren uitgevoerd in CI/CD? (9) Zijn entropieschattingen gedocumenteerd en gevalideerd? (10) Voor FIPS-vereisten: is de module FIPS 140-3-gecertificeerd?

Historische RNG-fouten laten zien wat er op het spel staat. Debian OpenSSL (2006-2008): een patch verwijderde per ongeluk twee regels code voor het verzamelen van entropie, waardoor de zaadpool werd teruggebracht tot een PID-ruimte van 15 bits — voor de volledige Debian-gebruikersbasis werden slechts 32.767 mogelijke SSH-sleutels gegenereerd. Alle door Debian gegenereerde SSH-hostsleutels en gebruikerssleutels moesten worden vervangen. Bitcoin-portefeuilles op Android (2013): SecureRandom van Android gebruikte een zaadinitialisatie op Java-niveau die op sommige apparaten mislukte, waardoor dubbele k-waarden in ECDSA-handtekeningen ontstonden — hierdoor werden privésleutels rechtstreeks onthuld. Sony PS3 (2010): gebruikte een constante nonce bij het ondertekenen van ECDSA-firmware, waardoor privésleutels konden worden geëxtraheerd uit twee handtekeningen (dezelfde k voor verschillende berichten onthult de sleutel via eenvoudige algebra).

Statistische toetsen (NIST SP 800-22, TestU01 BigCrush, PractRand) controleren de uitvoerkwaliteit, maar kunnen cryptografische beveiliging niet bewijzen. Bekende-antwoordtoetsen van CAVP controleren de algoritmische correctheid van SP 800-90A-implementaties. Toetsen voor entropiebronnen volgens SP 800-90B (schatting van de min-entropie, gezondheidstoetsen) valideren de zaadinvoer. De Continue RNG-toets (CRNGT) detecteert vastgelopen uitvoer in realtime. VM- en containerimplementaties vereisen entropie-injectie (VIRTIO-RNG) en controles van entropie bij het opstarten. Toetsen op forkveiligheid controleren of kindprocessen de DRBG-toestand van het ouderproces niet overnemen. Fouten uit de praktijk (Debian, Android) laten zien dat RNG-fouten rechtstreeks tot het uitlekken van cryptografische sleutels leiden. Controlelijsten formaliseren deze controles voor productie-implementaties.