Symmetric_6_random number generation.pdf

# Rol van willekeurige getallen in cryptografie Willekeurige binaire getallen spelen een cruciale rol in diverse netwerkbeveiligingsalgoritmen en protocollen, met name bij het waarborgen van de vertrouwelijkheid en authenticiteit van communicatie. Hun toepassing strekt zich uit tot sleuteldistributie, wederzijdse authenticatie, sessiesleutelgeneratie, en de creatie van bitstreams voor stream-encryptie [1](#page=1). ### 1.1 Toepassingen van willekeurige getallen Willekeurige getallen worden ingezet in verschillende cryptografische processen: #### 1.1.1 Sleuteldistributie en authenticatie Bij sleuteldistributie- en authenticatieschema's werken twee communicerende partijen samen door middel van berichtuitwisseling om sleutels te distribueren en/of elkaar te authenticeren [1](#page=1). #### 1.1.2 Nonces ter preventie van replay-aanvallen In veel van deze schema's worden "nonces" (een willekeurig getal dat slechts één keer wordt gebruikt) ingezet tijdens de handshake-fase om replay-aanvallen te voorkomen. Het gebruik van willekeurige getallen voor nonces bemoeilijkt de pogingen van een tegenstander om de nonce te achterhalen of te raden, wat essentieel is om te voorkomen dat een verouderde transactie wordt herhaald [1](#page=1). > **Tip:** Het willekeurig karakter van nonces is essentieel. Als een nonce voorspelbaar is, kan een aanvaller deze kopiëren en herhalen, wat de beveiliging ondermijnt. #### 1.1.3 Generatie van sessiesleutels Willekeurige getallen zijn van belang bij de generatie van geheime sleutels voor symmetrische encryptie die specifiek voor een bepaalde transactie of sessie worden gebruikt en voor een korte periode geldig zijn. Deze sleutels worden vaak sessiesleutels genoemd [1](#page=1). #### 1.1.4 Generatie van RSA-sleutels Bij de generatie van publieke-sleutelcryptografiesystemen, zoals het RSA-algoritme, worden eveneens willekeurige getallen gebruikt [1](#page=1). #### 1.1.5 Generatie van bitstreams voor stream-encryptie Willekeurige getallen zijn ook cruciaal voor het creëren van een bitstream die gebruikt wordt voor symmetrische stream-encryptie [1](#page=1). ### 1.2 Belang van willekeurigheid Het gebruik van echt willekeurige getallen is fundamenteel voor de beveiliging van deze cryptografische toepassingen. Onvoldoende willekeurigheid kan leiden tot voorspelbaarheid, wat de deur opent voor diverse aanvallen, waaronder replay-aanvallen [1](#page=1). --- # Definitie en criteria voor willekeurigheid Dit deel behandelt de betekenis van willekeurigheid in de context van computerbeveiliging, met specifieke aandacht voor statistische criteria zoals uniforme distributie en onafhankelijkheid, en onderscheidt dit van voorspelbaarheid. ### 2.1 Wat is willekeurigheid? In computerbeveiliging is het van cruciaal belang dat de sleutels die voor encryptie worden gebruikt, willekeurig worden gegenereerd, of op zijn minst zo willekeurig dat een potentiële afluisteraar ze niet kan raden. Strikt genomen is het, zonder aanvullende aannames, nooit mogelijk om met zekerheid te zeggen dat iets willekeurig is. De traditionele benadering om de eis voor willekeurige getalgeneratie te definiëren, richt zich op de statistische willekeurigheid van een reeks getallen [2](#page=2) [3](#page=3). ### 2.2 Criteria voor statistische willekeurigheid Om te valideren dat een reeks getallen willekeurig is, worden doorgaans twee criteria gehanteerd [3](#page=3): #### 2.2.1 Uniforme distributie Dit criterium stelt dat de distributie van bits in de reeks uniform moet zijn. Dit betekent dat de frequentie van het voorkomen van enen en nullen ongeveer gelijk moet zijn [3](#page=3). #### 2.2.2 Onafhankelijkheid Onafhankelijkheid houdt in dat geen enkele subreeks in de reeks kan worden afgeleid uit andere subreeksen. Hoewel er goed gedefinieerde statistische tests bestaan om te controleren of een reeks voldoet aan een bepaalde distributie (zoals de uniforme distributie), bestaat er geen specifieke test om onafhankelijkheid te "bewijzen". In plaats daarvan wordt een reeks tests toegepast om aan te tonen dat de reeks geen onafhankelijkheid vertoont. De algemene strategie is om voldoende tests uit te voeren totdat het vertrouwen in de onafhankelijkheid voldoende sterk is. Als een reeks tests niet aantoont dat een bitreeks niet onafhankelijk is, dan kan men met een hoog niveau van vertrouwen aannemen dat de reeks inderdaad onafhankelijk is [3](#page=3). > **Tip:** Het is belangrijk te beseffen dat, hoewel statistische tests sterk bewijs kunnen leveren voor willekeurigheid, ze geen absolute zekerheid kunnen bieden [2](#page=2). ### 2.3 Willekeurigheid versus voorspelbaarheid In toepassingen zoals wederzijdse authenticatie, generatie van sessiesleutels en streamciphers is het niet alleen vereist dat de reeks getallen statistisch willekeurig is, maar ook dat de opeenvolgende leden van de reeks onvoorspelbaar zijn [3](#page=3). #### 2.3.1 Ware willekeurigheid en pseudo-willekeurigheid Bij "ware" willekeurige reeksen is elk getal statistisch onafhankelijk van andere getallen in de reeks en daardoor onvoorspelbaar. Hoewel ware willekeurige getallen in sommige toepassingen worden gebruikt, hebben ze beperkingen, zoals inefficiëntie. Vaker worden algoritmen geïmplementeerd die reeksen getallen genereren die willekeurig *lijken*. In dit laatste geval is het cruciaal dat een tegenstander toekomstige elementen van de reeks niet kan voorspellen op basis van eerdere elementen [3](#page=3). #### 2.3.2 Determinisme en pseudo-willekeurigheid Determinisme betekent dat iets niet echt willekeurig is, maar waarschijnlijk pseudo-willekeurig. Een voorbeeld hiervan is te zien in de Python `random` module, waar twee opeenvolgende uitvoeren identieke resultaten kunnen produceren als ze worden geïnitialiseerd met dezelfde "seed". Determinisme heeft specifieke voordelen, zoals de mogelijkheid om aan te tonen dat getallen zijn gegenereerd of om tests opnieuw uit te voeren. De willekeurige stroom in een stream cipher moet identiek zijn aan zowel de zender- als de ontvangerszijde [3](#page=3). > **Tip:** De Python `secrets` module wordt over het algemeen als veiliger beschouwd voor cryptografisch willekeurige of pseudo-willekeurige getallen dan de `random` module [3](#page=3). #### 2.3.3 Lineaire congruente methode Een veelgebruikte techniek voor pseudo-willekeurige getalgeneratie is het lineaire congruente methode, oorspronkelijk voorgesteld door Lehmer. Deze methode werkt modulo een waarde $m$, die bij voorkeur erg groot is om een lange reeks onderscheidende willekeurige getallen te produceren. Een veelvoorkomend criterium is dat $m$ bijna gelijk is aan de maximaal representeerbare niet-negatieve gehele waarde voor een gegeven computer, bijvoorbeeld $m \approx 2^{31}$. De formule luidt [4](#page=4): $$X_{n+1} = (aX_n) \pmod{m}$$ [4](#page=4). Een voorbeeld van een multiplier die de meeste tests voor willekeurigheid doorstaat is $a = 16807$, oorspronkelijk geselecteerd voor de IBM 360-familie van computers. Hoewel dit algoritme breed wordt gebruikt en grondig is getest, is er niets willekeurigs aan het algoritme zelf, afgezien van de keuze van de initiële waarde $X_0$. De resterende getallen volgen deterministisch. Lineaire congruente methoden zijn daarom niet voldoende veilig voor cryptografisch gebruik [4](#page=4). ### 2.4 Statistische tests voor willekeurigheid Het NIST SP 800-22 document beschrijft 15 afzonderlijke tests voor willekeurigheid. Enkele voorbeelden van deze tests zijn [4](#page=4): #### 2.4.1 Frequentietest Dit is de meest basale test en moet in elke testsuite worden opgenomen. Het doel is om te bepalen of het aantal enen en nullen in een reeks ongeveer gelijk is aan wat verwacht zou worden van een echt willekeurige reeks [4](#page=4). #### 2.4.2 Runs test Deze test richt zich op het totale aantal "runs" in de reeks, waarbij een run een ononderbroken sequentie van identieke bits is, begrensd door bits van de tegenovergestelde waarde. Het doel is om te bepalen of het aantal runs van enen en nullen van verschillende lengtes overeenkomt met wat verwacht wordt van een willekeurige reeks [5](#page=5). #### 2.4.3 Maurer's universele statistische test Deze test richt zich op het aantal bits tussen overeenkomende patronen, wat gerelateerd is aan de lengte van een gecomprimeerde reeks. Het doel is om te detecteren of de reeks significant kan worden gecomprimeerd zonder informatieverlies; een significant comprimeerbare reeks wordt als niet-willekeurig beschouwd [5](#page=5). ### 2.5 Criteria voor voorspelbaarheid Een reeks pseudo-willekeurige getallen moet twee vormen van onvoorspelbaarheid vertonen [5](#page=5): #### 2.5.1 Voorwaartse onvoorspelbaarheid Als de seed onbekend is, moet het volgende uitvoerbit in de reeks onvoorspelbaar zijn, ondanks enige kennis van eerdere bits in de reeks [5](#page=5). #### 2.5.2 Achterwaartse onvoorspelbaarheid Het moet ook niet haalbaar zijn om de seed te achterhalen op basis van kennis van gegenereerde waarden. Er mag geen correlatie zichtbaar zijn tussen een seed en enige daaruit gegenereerde waarde; elk element van de reeks moet lijken op de uitkomst van een onafhankelijke willekeurige gebeurtenis met een waarschijnlijkheid van 1/2 [5](#page=5). Dezelfde set tests voor willekeurigheid biedt ook een test voor onvoorspelbaarheid. Als de gegenereerde bitstroom willekeurig lijkt, is het niet mogelijk om een bit of bitreeks te voorspellen op basis van kennis van eerdere bits. Evenzo, als de bitreeks willekeurig lijkt, is er geen haalbare manier om de seed af te leiden op basis van de bitreeks; een willekeurige reeks zal geen correlatie vertonen met een vaste waarde (de seed) [5](#page=5). --- # Typen random number generators (RNGs) Random number generators (RNGs) worden gecategoriseerd in twee hoofdcategorieën: Pseudorandom Number Generators (PRNGs) en True Random Number Generators (TRNGs) [8](#page=8). ### 3.1 True Random Number Generators (TRNGs) TRNGs genereren willekeurige getallen door gebruik te maken van natuurlijke, niet-deterministische bronnen van entropie. Deze bronnen zijn vaak fysieke verschijnselen die schijnbaar onvoorspelbare uitkomsten produceren [8](#page=8) [9](#page=9). #### 3.1.1 Entropiebronnen voor TRNGs De kwaliteit van een TRNG is direct afhankelijk van de gebruikte entropiebron. Potentiële entropiebronnen zijn divers en kunnen worden onderverdeeld in interne en externe bronnen [9](#page=9): * **Interne bronnen (omgevingsgerelateerd):** * Timing van toetsaanslagen [9](#page=9). * Elektrische activiteit van schijven [9](#page=9). * Muisbewegingen [9](#page=9). * Instantane waarden van de systeemtijdklok [9](#page=9). * Thermische ruis (bijvoorbeeld van weerstanden) [10](#page=10) [9](#page=9). * Lawaai van een geluidskaart zonder bron [9](#page=9). * Data van een camera met gesloten lens (thermische ruis) [9](#page=9). * Kleine fluctuaties in de rotatiesnelheid van harde schijven [9](#page=9). * Sensoren aan boord van een apparaat, zoals temperatuur-, vochtigheids- of lichtsensoren [10](#page=10). * Huidgeleiding (galvanische huidreactie) [10](#page=10). * **Externe bronnen:** * Atmosferische ruis [10](#page=10). * Zichtbaar spectrum elektromagnetische golven [10](#page=10). * Pulsdetectoren van ioniserende stralingsevents [10](#page=10). * Gasontladingsbuizen [10](#page=10). * Lekkende condensatoren [10](#page=10). > **Tip:** Omdat de exacte hoeveelheid entropie die uit een bron kan worden gehaald niet nauwkeurig meetbaar is, worden schatters gebruikt. De min-entropie schatting wordt door NIST aanbevolen voor het identificeren van goede entropiebronnen [9](#page=9). #### 3.1.2 Werking en Verwerking van TRNGs Het proces begint met het oogsten van entropie uit natuurlijke bronnen, wat kan resulteren in een "entropiepool". Wanneer een willekeurig getal gegenereerd moet worden, worden bits uit deze pool gehaald. Vervolgens wordt de pool weer aangevuld door nieuwe data van de entropiebron te oogsten. Dit oogsten kan traag zijn, wat de bulkgeneratie van willekeurige getallen tijdrovend maakt en toepassingen kan blokkeren [8](#page=8). De entropiebron dient als input voor een algoritme dat een willekeurige binaire output produceert. TRNGs kunnen bestaan uit eenvoudige conversie van een analoge bron naar een binaire output. Vaak is verdere verwerking nodig om eventuele vooringenomenheid (bias) in de bron te corrigeren [10](#page=10). #### 3.1.3 Deskewing Algoritmen Bias kan worden verminderd of geëlimineerd met behulp van deskewing algoritmen. Een methode is om de bitstroom door een hash-functie te leiden. Een hash-functie produceert een output van $n$ bits uit een input van willekeurige lengte. Voor deskewing kunnen blokken van $m$ inputbits, waarbij $m \geq n$, door de hash-functie worden gevoerd. RFC 4086 beveelt aan om input van meerdere hardwarebronnen te verzamelen en deze te mengen met een hash-functie om willekeurige output te produceren [10](#page=10). > **Voorbeeld:** Besturingssystemen zoals Linux gebruiken ingebouwde mechanismen voor het genereren van willekeurige getallen. Linux combineert bits uit muis- en toetsenbordactiviteit, schijf-I/O-operaties en specifieke interrupts. Deze bits worden in een gepoolde buffer verzameld en vervolgens door de SHA-1 hash-functie gehaald wanneer willekeurige bits nodig zijn [10](#page=10). #### 3.1.4 Quantum Random Number Generation Voor toepassingen waar 100% zekerheid van willekeurigheid vereist is, wordt quantum random number generation (QRNG) overwogen. Hoewel QRNGs als "echt willekeurig" worden beschouwd, wordt in de cryptografie elke bron die gebruik maakt van een externe "goede" entropiebron als "echt willekeurig" beschouwd. Sommigen vinden QRNG een kostbare oplossing voor een probleem dat klassiek al adequaat is opgelost [11](#page=11). #### 3.1.5 Gebruik van TRNGs Een TRNG wordt ook wel een non-deterministic random bit generator (NDRBG) genoemd [13](#page=13). ### 3.2 Pseudorandom Number Generators (PRNGs) PRNGs genereren lange sequenties van getallen die willekeurig lijken, gebaseerd op een initiële waarde, de zogenaamde "seed" . Ze maken geen gebruik van een entropiebron (behalve voor de seed), waardoor hun output deterministisch is. Dit maakt PRNGs sneller en geschikt voor bulkgeneratie van willekeurige getallen, maar ze zijn niet geschikt voor toepassingen die ware willekeurigheid vereisen [8](#page=8). #### 3.2.1 Werking van PRNGs Een PRNG neemt een vaste waarde, de seed, als input en produceert een reeks outputbits met een deterministisch algoritme. Vaak wordt een deel van de resultaten van het algoritme teruggevoerd als input voor het genereren van aanvullende outputbits. Belangrijk is dat de output bitstroom volledig wordt bepaald door de inputwaarde(n); een tegenstander die het algoritme en de seed kent, kan de gehele bitstroom reproduceren [12](#page=12). > **Tip:** Vaak wordt de seed voor een PRNG gegenereerd door een TRNG [12](#page=12). #### 3.2.2 Typen PRNGs Er worden twee vormen van PRNGs onderscheiden op basis van hun toepassing [12](#page=12): 1. **Pseudorandom Number Generator (PRNG):** Een algoritme dat wordt gebruikt om een open-ended reeks bits te produceren. Een veelvoorkomende toepassing is als input voor een symmetrische stream cipher [12](#page=12). 2. **Pseudorandom Function (PRF):** Een PRF produceert een pseudorandom string van bits van een bepaalde vaste lengte. Voorbeelden hiervan zijn symmetrische encryptiesleutels en nonces. Een PRF neemt doorgaans een seed plus context-specifieke waarden (zoals een gebruikers-ID of applicatie-ID) als input [13](#page=13). Er is geen significant verschil tussen een PRNG en een PRF, behalve het aantal gegenereerde bits. Dezelfde algoritmen kunnen voor beide toepassingen worden gebruikt, mits ze een seed vereisen en zowel willekeurigheid als onvoorspelbaarheid vertonen [13](#page=13). #### 3.2.3 Cryptografische Vereisten voor PRNGs Wanneer een PRNG of PRF voor cryptografische doeleinden wordt gebruikt, is de basisvereiste dat een tegenstander die de seed niet kent, de pseudorandom string niet kan bepalen. Als de pseudorandom bitstroom bijvoorbeeld in een stream cipher wordt gebruikt, kan kennis hiervan de tegenstander in staat stellen de plaintext uit de ciphertext te herstellen. Voor een PRF is het belangrijk dat de gegenereerde outputwaarden effectief willekeurig zijn om brute-force aanvallen te voorkomen [13](#page=13). > **Voorbeeld:** Een 128-bit seed wordt gebruikt met context-specifieke waarden om een 128-bit geheime sleutel te genereren. Als de PRF geen effectief willekeurige 128-bit outputwaarden produceert, kan een tegenstander de mogelijkheden verkleinen en een succesvolle brute-force aanval uitvoeren [13](#page=13). #### 3.2.4 Terminologie en Vergelijking met TRNGs Een PRNG wordt ook wel een deterministische random bit generator (DRBG) genoemd. Soms worden de termen PRBG / TRBG gebruikt, waarbij 'Bit' en 'Number' synoniemen zijn. De afkorting kan voorafgegaan worden door 'CS' (Cryptographically Secure), zoals CSDRBG. De termen DRBG en NDRBG worden voornamelijk gebruikt in Amerikaanse overheidscontexten [13](#page=13). #### 3.2.5 Noodzaak van PRNGs naast TRNGs Hoewel TRNGs ware willekeurigheid bieden, zijn PRNGs in bepaalde situaties noodzakelijk [13](#page=13): * **Stream Ciphers:** Voor stream ciphers is een deterministische random number generator vereist. Een TRNG is hiervoor niet praktisch, omdat de zender een keystream van dezelfde lengte als de plaintext zou moeten genereren en veilig naar de ontvanger zou moeten verzenden. Met een PRNG hoeft alleen de doorgaans kleinere stream cipher key veilig te worden overgedragen [13](#page=13). * **Seed voor PRFs:** Zelfs voor PRF-toepassingen is het wenselijk om een TRNG te gebruiken voor de seed en de PRF-output te gebruiken in plaats van direct de TRNG-output. Een TRNG kan namelijk een binaire string met enige bias produceren, en de PRF kan deze bias "randomiseren" ] [13](#page=13). * **Efficiëntie en Snelheid:** TRNGs zijn vaak inefficiënter en langzamer in het produceren van getallen dan PRNGs. Cryptografische systemen die miljoenen willekeurige bits per seconde nodig hebben, vereisen de efficiëntie van PRNGs [14](#page=14). * **Periodieke Aard van PRNGs:** PRNGs zijn doorgaans periodiek, wat betekent dat de sequentie zich uiteindelijk herhaalt. Moderne PRNGs hebben echter periodes die zo lang zijn dat dit voor de meeste praktische toepassingen verwaarloosbaar is [14](#page=14). > **Tip:** De website https://coveryourtracks.eff.org helpt bij het berekenen van de entropie van een browser fingerprint. Wachtwoordentropie is equivalent aan het aantal pogingen dat nodig is om een wachtwoord te kraken, bepaald door de lengte en de tekenset. De NIST-richtlijn van 2024 benadrukt lengte boven tekensetgrootte voor wachtwoorden [11](#page=11). --- # Specifieke PRNG-algoritmen en -mechanismen Dit onderdeel onderzoekt specifieke algoritmen en mechanismen voor Pseudorandom Number Generators (PRNG's), waaronder de Blum-Blum Shub (BBS) generator, de ANSI X9.17 PRNG, mechanismen gebaseerd op CTR- en OFB-modi van blokcijfers, en de NIST DRBG-varianten (CTR_DRBG, HASH_DRBG, HMAC_DRBG), evenals de ingetrokken Dual_EC_DRBG [15](#page=15). ### 4.1 De Blum-Blum Shub (BBS) generator De Blum-Blum Shub (BBS) generator is een cryptografisch veilige pseudorandom bit generator (CSPRBG) die bekend staat om zijn sterke cryptografische bewijs [15](#page=15). #### 4.1.1 Algoritme Het algoritme vereist de volgende stappen [15](#page=15): 1. Kies twee grote priemgetallen, $p$ en $q$, zodanig dat $p \pmod{4} = 3$ en $q \pmod{4} = 3$. 2. Bereken $n = p \times q$. 3. Kies een willekeurig getal $s$ (de seed) dat relatief priem is tot $n$ (d.w.z. $p$ en $q$ zijn geen factoren van $s$). 4. Initialiseer $X_0 = s$. 5. Genereer de opeenvolgende waarden met de formule $X_i = (X_{i-1})^2 \pmod{n}$. 6. Output is de minst significante bit van $X_i$. #### 4.1.2 Cryptografische veiligheid Een CSPRBG moet de "next-bit test" doorstaan. Dit betekent dat er geen polynomial-time algoritme mag bestaan dat, gegeven de eerste $k$ bits van een uitvoerreeks, de $(k+1)$-de bit kan voorspellen met een waarschijnlijkheid significant groter dan 1/2. De veiligheid van BBS is gebaseerd op de moeilijkheid van het ontbinden van $n$ in zijn priemfactoren [15](#page=15). > **Tip:** De security van BBS is direct gekoppeld aan de RSA-kwetsbaarheid (integer factorization). #### 4.1.3 Voorbeeld Een voorbeeld van de werking van BBS is gegeven met $n = 192649 = 383 \times 503$ en een seed $s = 101355$ [16](#page=16). ### 4.2 De ANSI X9.17 PRNG De ANSI X9.17 PRNG werd voorheen beschouwd als een van de sterkste PRNG's en werd in diverse financiële toepassingen en beveiligingssoftware gebruikt. Het mechanisme maakt gebruik van triple DES als blokcijfer [17](#page=17). #### 4.2.1 Zwakheden De belangrijkste zwakte van de ANSI X9.17 PRNG ligt niet in triple DES zelf, maar in het gebruik van twee statische sleutels ($K1, K2$) die geheim moeten blijven. Implementaties die deze sleutels hardcodeerden, konden worden gecompromitteerd door de broncode of binaire sleutel te inspecteren. Kennis van de statische sleutel en enige uitvoer van de PRNG waren voldoende om het systeem te breken [17](#page=17). ### 4.3 PRNG-mechanismen gebaseerd op CTR- en OFB-modi van blokcijfers Twee veelgebruikte benaderingen om een PRNG te bouwen met behulp van een blokcijfer zijn de Cipher Block Chaining (CBC) modus en de Output Feedback (OFB) modus. Beide modi worden aanbevolen in standaarden zoals NIST SP 800-90, ANSI X9.82 en RFC 4086 [18](#page=18). #### 4.3.1 Structuur In beide gevallen bestaat de seed uit twee delen: een encryptiesleutel ($K$) en een waarde $V$ die na elke gegenereerde blok pseudowillekeurige getallen wordt bijgewerkt [18](#page=18). * **CTR-modus:** De waarde van $V$ wordt na elke encryptie met 1 verhoogd [18](#page=18). * **OFB-modus:** De waarde van $V$ wordt gelijkgesteld aan de waarde van het voorgaande PRNG-blok [18](#page=18). Pseudowillekeurige bits worden blok per blok geproduceerd, bijvoorbeeld 128 bits tegelijk voor AES [18](#page=18). ### 4.4 NIST DRBG-varianten NIST (National Institute of Standards and Technology) definieert verschillende methoden voor Deterministic Random Bit Generators (DRBG's) in de standaard SP 800-90A [19](#page=19). #### 4.4.1 NIST CTR_DRBG CTR_DRBG is een DRBG-methode gebaseerd op de CTR-modus van een blokcijfer [19](#page=19). ##### 4.4.1.1 Initialisatie en update * **Initialisatie:** Vereist een encryptiesleutel ($K$) en een initiële tellerwaarde ($V$), gezamenlijk de "seed" genoemd. De combinatie van $K$ en $V$ wordt "seed" genoemd. Vaak worden $K=0$ en $V=0$ gebruikt als initiële waarden voor de CTR-modus. Er zijn minimaal `seedlen` bits van een entropiebron nodig [19](#page=19) [20](#page=20). * **Update:** De CTR-modus encryptie wordt geïtereerd met $V$ verhoogd met 1 na elke encryptie, totdat minimaal `seedlen` bits zijn gegenereerd. De linker `seedlen` bits van de output worden ge-XORd met de `seedlen` entropiebits om een nieuwe seed te produceren. De linker `keylen` bits vormen de nieuwe sleutel ($K$) en de rechter `outlen` bits vormen de nieuwe tellerwaarde ($V$) [20](#page=20). ##### 4.4.1.2 Generatie Nadat $K$ en $V$ zijn verkregen, gaat de DRBG naar de generatiefase. De encryptiefunctie wordt herhaald om het gewenste aantal pseudowillekeurige bits te genereren, waarbij dezelfde encryptiesleutel ($K$) wordt gebruikt en de tellerwaarde ($V$) bij elke iteratie met 1 wordt verhoogd [20](#page=20). ##### 4.4.1.3 Reseeding Om de veiligheid te verhogen, wordt het aantal gegenereerde bits gelimiteerd door een `reseed_interval` parameter. Wanneer een reseed-teller het `reseed_interval` bereikt, wordt de update-functie aangeroepen. De laatst gebruikte $K$ en $V$ uit de generatiefase dienen als input voor de update-functie, samen met nieuwe entropiebits [20](#page=20). > **Tip:** Hardwarematige implementaties van CTR_DRBG, zoals die van Intel, kunnen hogere snelheden en verbeterde beveiliging bieden door de eliminatie van I/O-vertragingen en softwarecomponenten [20](#page=20). ##### 4.4.1.4 Kwetsbaarheden Ondanks aanbevelingen, vertoont NIST CTR_DRBG, net als HASH_DRBG en HMAC_DRBG, zwakheden waardoor gedeeltelijke state-lekkage kan leiden tot veiligheidsincidenten (#page=21, page=22). Side-channel aanvallen op implementaties, zoals die gebruik maken van "leaky" T-tables in AES, kunnen leiden tot de recuperatie van geheime sleutels [21](#page=21) [22](#page=22). #### 4.4.2 NIST HASH_DRBG en HMAC_DRBG Deze DRBG-methoden zijn gebaseerd op hash-functies en Hash-based Message Authentication Codes (HMAC), die later in de cursus worden behandeld [22](#page=22). > **Tip:** Bestudeer de werking en mogelijke kwetsbaarheden van HASH_DRBG en HMAC_DRBG zorgvuldig, ondanks dat ze niet direct als 'gebroken' worden beschouwd [22](#page=22). #### 4.4.3 Dual_EC_DRBG Dual_EC_DRBG is een NIST-goedgekeurde, maar nu ingetrokken, PRNG die een achterdeur (backdoor) van de NSA bleek te bevatten [22](#page=22). > **Alert:** Dual_EC_DRBG mag niet meer gebruikt worden vanwege de bewezen backdoor [22](#page=22). ### 4.5 Algemene overwegingen voor DRBG's DRBG's, inclusief de NIST-aanbevolen varianten, kunnen zwakheden vertonen waarbij gedeeltelijke state-lekkage leidt tot onverwachte veiligheidsafbreuk. Het niet gebruiken van optionele inputs, zoals bij HMAC_DRBG, kan zelfs de (zwakkere) forward security eigenschap niet garanderen, in tegenspraak met de standaardclaims [22](#page=22). --- # Lineaire Feedback Shift Registers (LFSRs) Lineaire feedback shift registers (LFSRs) dienen als fundamentele bouwstenen voor streamciphers, waarbij hun constructie, polynomiale representatie en de vereisten voor maximale periodes centraal staan, hoewel hun inherente lineariteit ook beperkingen met zich meebrengt [23](#page=23) [25](#page=25). ### 5.1 Constructie en werking van LFSRs Een LFSR bestaat uit een reeks geheugencellen, elk opslaghoudend voor één bit aan informatie, die gezamenlijk een register vormen. In elke cyclus worden specifieke cellen 'getapt' en hun waarden door een feedbackfunctie geleid. Vervolgens wordt het register met één positie verschoven, waarbij de bit die uit het register schuift, de uitvoerbit is. De uitkomst van de getapte bits wordt ingevoerd in de lege cel aan het begin van het register [23](#page=23). > **Tip:** LFSRs kunnen eenvoudig in hardware worden geïmplementeerd [23](#page=23). Een reeks van uitsluitend nullen als beginwaarde zal altijd resulteren in een reeks van nullen. Dit komt doordat in het eindige veld GF geldt dat $1+1 = 0$. Een LFSR heeft altijd een periode, wat betekent dat de gegenereerde sequenties op den duur herhaald worden [23](#page=23) [2](#page=2). ### 5.2 Polynomiale notatie De transformaties binnen een LFSR worden vaak uitgedrukt met behulp van polynomiale notatie. Hierbij correspondeert de oudste waarde ($s_0$) met de hoogste graad van de polynomiale term, en de andere waarden met lagere graden. Een constante term van 1 wordt altijd meegenomen [24](#page=24). Als voorbeeld, de relatie $s_n = s_{n-1} + s_{n-4} + s_{n-5}$ in GF kan worden uitgedrukt met de polynomiale notatie $X^5 + X^4 + X + 1$. De relatie $s_{32} = s_{29} + s_0$ correspondeert met de polynoom $X^{32} + X^{29} + 1$ [23](#page=23) [24](#page=24) [2](#page=2). ### 5.3 Maximale periodes en irreducibele/primitieve polynomen Om een maximale periode voor een LFSR te garanderen, moet de connectiepolynoom zowel irreducibel (of priem) als primitief zijn. Een irreducibele polynoom kan niet verder worden ontbonden in factoren. De maximale periode van een LFSR is $2^n - 1$, waarbij $n$ het aantal bits in het register is [23](#page=23) [24](#page=24). > **Tip:** Lijsten van irreducibele en primitieve polynomen zijn essentieel voor het ontwerpen van LFSRs met maximale periodes [24](#page=24). ### 5.4 Beperkingen en combinaties met niet-lineaire methoden LFSRs mogen nooit op zichzelf worden gebruikt als keystream generator, omdat de kennis van slechts een beperkt aantal opeenvolgende bits al voldoende is om het cipher te breken door de inherente lineariteit. Desondanks zijn LFSRs snel, kosteneffectief en genereren ze sequenties met goede statistische eigenschappen en een hoge periode, waardoor ze nuttige bouwstenen zijn binnen complexere systemen [25](#page=25). Om de lineariteitsproblemen te overwinnen, worden LFSRs vaak gecombineerd met niet-lineaire componenten. Vier algemene methoden hiervoor zijn [25](#page=25): * Niet-lineaire combinatiegenerator [25](#page=25). * Niet-lineaire filtergenerator [25](#page=25). * Klok-gestuurde generator [25](#page=25). * Dynamische LFSRs [25](#page=25). Daarnaast bestaan er Niet-Lineaire Feedback Shift Registers (NLFSRs) die gebruikmaken van een niet-lineaire functie in plaats van een lineaire. S-boxes, bekend uit blockciphers, worden ook ingezet om niet-lineariteit te realiseren in sommige streamciphers (zoals SOSEMANUK, BEAN, Enocoro, Hummingbird). Niet-lineariteit kan worden bereikt door termen zoals $s_i^2$ of producten zoals $s_i \ast s_{i-1}$ te gebruiken [25](#page=25). > **Voorbeeld:** De streamciphers A5/1 (gebruikt in GSM) en E0 (gebruikt in Bluetooth) zijn voorbeelden van ontwerpen die LFSRs combineren met andere technieken, maar deze bleken ineffectief en hadden ernstige zwakheden. A5/1 heeft bijvoorbeeld een te kleine en niet-geheime 64-bit sleutel, wat resulteert in een effectieve sleutelgrootte van slechts 61 bits. Het breken van A5/1 vereist slechts enkele minuten rekentijd met een korte stukje bekende plaintext. De opvolgers van GPRS (GEA-1 en GEA-2) en E0 hebben ook slechts een beperkt beveiligingsniveau [25](#page=25) [26](#page=26). --- ## Veelgemaakte fouten om te vermijden - Bestudeer alle onderwerpen grondig voor examens - Let op formules en belangrijke definities - Oefen met de voorbeelden in elke sectie - Memoriseer niet zonder de onderliggende concepten te begrijpen

| Term | Definition | |------|------------| | Niet-deterministische random bit generator (NDRBG) | Een type random number generator dat gebruikmaakt van natuurlijke, onvoorspelbare bronnen van entropie om willekeurige bits te produceren. | | Deterministiche random bit generator (DRBG) | Een type random number generator dat algoritmes gebruikt om schijnbaar willekeurige getallenreeksen te genereren, gebaseerd op een initiële 'seed'. De output is volledig bepaald door de seed en het algoritme. | | Entropie | De mate van willekeurigheid of onvoorspelbaarheid in een gegevensbron. Ware random number generators (TRNGs) oogsten entropie uit natuurlijke bronnen. | | Sessiesleutel | Een geheime encryptiesleutel die voor een specifieke transactie of sessie wordt gegenereerd en slechts voor een korte periode geldig is. Wordt vaak gegenereerd met behulp van willekeurige getallen. | | Nonce | Een willekeurig getal dat slechts één keer wordt gebruikt, vaak tijdens handshake-protocollen in cryptografie om replay-aanvallen te voorkomen. | | Uniforme distributie | Een statistisch criterium voor willekeurige getallenreeksen, waarbij de frequentie van voorkomen van enen en nullen (of andere waarden) ongeveer gelijk is. | | Onafhankelijkheid (in willekeurigheid) | Een statistisch criterium waarbij geen enkele subreeks van de getallenreeks kan worden afgeleid uit andere delen van de reeks. Dit betekent dat opeenvolgende getallen niet van elkaar afhankelijk zijn. | | Pseudowillekeurig getal | Een getal dat door een algoritme wordt gegenereerd en eigenschappen vertoont van een willekeurig getal, maar dat feitelijk deterministisch is en kan worden gereproduceerd als de initiële 'seed' bekend is. | | Lineaire Congruentiële Methode | Een veelgebruikte methode voor pseudowillekeurige getalgeneratie, die de formule $X_{n+1} = (aX_n) \pmod{m}$ gebruikt. | | Frequentietest | Een basale statistische test om te bepalen of het aantal enen en nullen in een binaire reeks ongeveer gelijk is, zoals verwacht mag worden van een werkelijk willekeurige reeks. | | Runs test | Een statistische test die zich richt op het aantal ononderbroken sequenties van identieke bits (runs) in een reeks, om te bepalen of dit aantal overeenkomt met wat verwacht wordt van een willekeurige reeks. | | Maurer's Universele Statistische Test | Een statistische test die de lengte van de compressie van een binaire reeks analyseert om te detecteren of de reeks significant kan worden gecomprimeerd zonder verlies van informatie; een sterk comprimeerbare reeks wordt als niet-willekeurig beschouwd. | | Voorwaartse voorspelbaarheid | Het concept dat, gegeven de reeds gegenereerde bits van een reeks, de volgende bit niet voorspelbaar mag zijn, zelfs niet met kennis van de voorgaande bits en zonder kennis van de initiële seed. | | Achterwaartse voorspelbaarheid | Het concept dat het niet haalbaar mag zijn om de initiële 'seed' te bepalen op basis van de kennis van de gegenereerde waarden uit de reeks. | | Blum-Blum Shub (BBS) generator | Een cryptografisch veilige pseudowillekeurige bit generator (CSPRBG) waarvan de beveiliging gebaseerd is op de moeilijkheid van het factoriseren van grote getallen. De generator gebruikt de formule $X_i = (X_{i-1})^2 \pmod{n}$ en output de minst significante bit. | | Cryptografisch Veilige Pseudowillekeurige Bit Generator (CSPRBG) | Een pseudowillekeurige bit generator die de 'next-bit test' doorstaat, wat betekent dat er geen efficiënt algoritme bestaat dat de volgende bit kan voorspellen met een waarschijnlijkheid die significant groter is dan 1/2. | | ANSI X9.17 PRNG | Een pseudowillekeurige getalgenerator die voorheen als sterk werd beschouwd en triple DES gebruikte als blokcijfer. Kwetsbaarheden konden ontstaan door statische sleutels. | | CTR-modus (Counter Mode) | Een modus voor blokcijfers, ook gebruikt in PRNGs, waarbij de teller $V$ na elke encryptie wordt geïncrementeerd om pseudowillekeurige bits te genereren. | | OFB-modus (Output Feedback Mode) | Een modus voor blokcijfers, ook gebruikt in PRNGs, waarbij de output van de encryptie wordt teruggekoppeld en gebruikt wordt als input voor de volgende encryptie om pseudowillekeurige bits te genereren. | | NIST CTR_DRBG | Een cryptografische standaard voor een deterministische random bit generator die gebruikmaakt van de CTR-modus van een blokcijfer om pseudowillekeurige bits te genereren, vaak met een hardwarematige entropiebron. | | Lineair Feedback Shift Register (LFSR) | Een type digitaal circuit dat bestaat uit een reeks geheugencellen, waarbij een lineaire terugkoppelingsfunctie wordt gebruikt om nieuwe bits te genereren. Vaak gebruikt als bouwsteen in streamciphers. | | GF(2) | Het eindige lichaam (veld) met twee elementen, {0, 1}, waarin optelling en vermenigvuldiging modulo 2 plaatsvinden. Wordt gebruikt in de definitie van LFSR's. | | Irreducibel polynoom | Een polynoom dat niet verder kan worden ontbonden in factoren (behalve triviale factoren zoals 1 en zichzelf). In de context van LFSRs, draagt een irreducibel en primitief terugkoppelingspolynoom bij aan een maximale periode. | | Stream cipher | Een symmetrisch encryptiealgoritme dat een continue stroom van bits genereert (de keystream) en deze vervolgens XORt met de platte tekst om de cijfertekst te produceren. | | Niet-lineaire Feedback Shift Registers (NLFSR) | Een uitbreiding van LFSRs waarbij een niet-lineaire functie wordt gebruikt in plaats van een lineaire functie, om de veiligheid te verhogen en de lineariteitskwetsbaarheden te omzeilen. | | A5/1 | Een stream cipher die werd gebruikt in GSM-netwerken. Het maakt gebruik van drie LFSRs en heeft beperkte beveiliging. | | E0 | Een stream cipher die werd gebruikt voor de vertrouwelijkheid van communicatie in het Bluetooth-protocol. Het heeft ook significante beveiligingszwakheden. |