Symmetric_6_random+number+generation.pdf

# Belang van willekeurige getallen in cryptografie Willekeurige binaire getallen spelen een fundamentele rol in diverse netwerkbeveiligingsalgoritmen en -protocollen door essentiële functies te ondersteunen zoals sleuteldistributie, authenticatie en de generatie van sessiesleutels [1](#page=1). ### 1.1 Cruciale toepassingen van willekeurige getallen Willekeurige getallen worden gebruikt in de volgende belangrijke cryptografische toepassingen: * **Sleuteldistributie en wederzijdse authenticatie:** Bij protocollen waarbij twee partijen berichten uitwisselen om sleutels te distribueren of elkaar te authenticeren, worden vaak 'nonces' gebruikt. Nonces zijn unieke, eenmalig gebruikte willekeurige getallen die fungeren als 'handshake' om herhalingsaanvallen (replay attacks) te voorkomen. De willekeurigheid van nonces bemoeilijkt het voor een tegenstander om deze te voorspellen of te raden, wat hen zou kunnen helpen bij het herhalen van verouderde transacties [1](#page=1). * **Sessie-sleutelgeneratie:** In veel protocollen wordt voor specifieke transacties of sessies een geheime sleutel voor symmetrische encryptie gegenereerd die slechts voor korte tijd geldig is. Deze sleutel wordt doorgaans een sessiesleutel genoemd [1](#page=1). * **Generatie van RSA-sleutels:** Willekeurige getallen zijn essentieel voor het genereren van de sleutels die gebruikt worden in het RSA publieke-sleutel encryptiealgoritme [1](#page=1). * **Generatie van bitstromen voor streamciphers:** Willekeurige getallen vormen de basis voor het genereren van een bitstroom die gebruikt wordt in symmetrische streamencryptie [1](#page=1). ### 1.2 De aard van willekeurigheid in cryptografie De vraag of iets werkelijk willekeurig is, is complex, vooral in de context van computerbeveiliging waar de betrouwbaarheid van cryptografische sleutels cruciaal is [2](#page=2). #### 1.2.1 Definitie en criteria voor willekeurigheid In de computerbeveiliging is het van groot belang dat de sleutels voor encryptie willekeurig worden gegenereerd, of ten minste willekeurig genoeg om te voorkomen dat een potentiële afluisteraar ze kan raden. Hoewel het strikt genomen onmogelijk is om met absolute zekerheid te bewijzen dat iets willekeurig is zonder aanvullende aannames, worden er wiskundige en statistische benaderingen gebruikt om de vereisten voor willekeurige getallengeneratie te definiëren: willekeurigheid en onvoorspelbaarheid [2](#page=2). Traditioneel lag de nadruk bij het genereren van schijnbaar willekeurige getallenreeksen op statistische willekeurigheid. Twee belangrijke criteria worden gebruikt om de willekeurigheid van een getallenreeks te valideren [2](#page=2): * **Uniforme distributie:** De verdeling van bits in de reeks moet uniform zijn. Dit betekent dat de frequentie van zowel nullen als enen ongeveer gelijk moet zijn [3](#page=3). * **Onafhankelijkheid:** Geen enkele deelreeks mag afleidbaar zijn uit andere delen van de reeks [3](#page=3). #### 1.2.2 Statistische tests en onafhankelijkheid Hoewel er weloverwogen statistische tests bestaan om te controleren of een bitreeks voldoet aan een specifieke distributie (zoals uniformiteit), bestaat er geen test om onafhankelijkheid te "bewijzen". In plaats daarvan wordt een reeks tests toegepast om aan te tonen dat een reeks géén onafhankelijkheid vertoont. De algemene strategie is om zoveel tests uit te voeren totdat het vertrouwen in de onafhankelijkheid van de reeks voldoende sterk is. Als een reeks tests er niet in slaagt om aan te tonen dat de bitreeks *niet* onafhankelijk is, dan kan men met een hoge mate van zekerheid aannemen dat de reeks daadwerkelijk onafhankelijk is [3](#page=3). #### 1.2.3 Statistisch willekeurig versus onvoorspelbaar Voor toepassingen zoals wederzijdse authenticatie, sessie-sleutelgeneratie en streamciphers is de eis niet alleen dat de reeks getallen statistisch willekeurig is, maar vooral dat opeenvolgende elementen van de reeks onvoorspelbaar zijn. "Echte" willekeurige reeksen hebben het kenmerk dat elk getal statistisch onafhankelijk is van de andere getallen in de reeks, en daardoor onvoorspelbaar. Hoewel echte willekeurige getallen in sommige toepassingen worden gebruikt, hebben ze beperkingen zoals inefficiëntie. Daarom worden vaker algoritmen geïmplementeerd die reeksen getallen genereren die *lijken* op willekeurige getallen [3](#page=3). #### 1.2.4 Pseudo-willekeurige getallengeneratoren In gevallen waar algoritmen worden gebruikt om getallenreeksen te genereren die willekeurig *lijken* te zijn (pseudo-willekeurig), is het cruciaal dat een tegenstander niet in staat is om toekomstige elementen van de reeks te voorspellen op basis van eerdere elementen [3](#page=3). > **Tip:** Determinisme in getallengeneratoren kan voordelen hebben. Bijvoorbeeld, om aan derden te kunnen aantonen dat getallen niet handmatig zijn gekozen, of om een test opnieuw te kunnen uitvoeren. Voor streamciphers moet de gegenereerde stroom identiek zijn voor zowel zender als ontvanger. Determinisme betekent echter dat het niet echt willekeurig is, maar pseudo-willekeurig [3](#page=3). > **Voorbeeld:** In Python kan het `random` module twee opeenvolgende uitvoeren identieke resultaten produceren als ze met dezelfde 'seed' (startwaarde) worden geïnitialiseerd. Dit illustreert de deterministische aard van pseudo-willekeurige getallengeneratoren [3](#page=3). > **Waarschuwing:** De `random` bibliotheek van Python wordt over het algemeen niet aanbevolen voor het genereren van cryptografisch veilige willekeurige of pseudo-willekeurige getallen. De `secrets` module wordt als veiliger beschouwd. Het is echter belangrijk op te merken dat zelfs de `secrets` module vaak een combinatie is van aanroepen naar de `random` module. Het belangrijkste advies voor veilig gebruik, ongeacht de module, is het volgen van best practices [3](#page=3). --- # Criteria voor willekeurigheid en onvoorspelbaarheid Dit deel behandelt de essentiële vereisten voor willekeurige getallen, met nadruk op uniforme distributie en onafhankelijkheid, en het cruciale onderscheid tussen statistische willekeurigheid en ware onvoorspelbaarheid. ### 2.1 Criteria voor willekeurigheid Om een reeks getallen als willekeurig te valideren, worden doorgaans twee primaire criteria gehanteerd: uniforme distributie en onafhankelijkheid [3](#page=3). #### 2.1.1 Uniforme distributie De distributie van bits in de reeks moet uniform zijn, wat betekent dat de frequentie van voorkomende en en enen ongeveer gelijk moet zijn. Hoewel er goed gedefinieerde statistische tests bestaan om te bepalen of een bitreeks voldoet aan een specifieke distributie, zoals de uniforme distributie, is er geen soortgelijke test om onafhankelijkheid te "bewijzen" [3](#page=3). #### 2.1.2 Onafhankelijkheid In plaats van een directe test, wordt onafhankelijkheid benaderd door een reeks tests toe te passen om aan te tonen dat een reeks **niet** onafhankelijk is. Als meerdere van dergelijke tests niet kunnen aantonen dat een bitreeks niet onafhankelijk is, kan men met een hoge mate van zekerheid aannemen dat de reeks wel degelijk onafhankelijk is [3](#page=3). > **Tip:** Het belang van onafhankelijkheid is dat geen enkel deel van de reeks kan worden afgeleid uit andere delen [3](#page=3). ### 2.2 Statistische willekeurigheid versus onvoorspelbaarheid Voor specifieke toepassingen, zoals wederzijdse authenticatie, sessiesleutelgeneratie en stroomversleuteling (stream ciphers), 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.2.1 ware willekeurigheid Bij "ware" willekeurige reeksen is elk getal statistisch onafhankelijk van andere getallen in de reeks en daardoor per definitie onvoorspelbaar. Hoewel ware willekeurige getallen in sommige toepassingen essentieel zijn, hebben ze beperkingen, zoals inefficiëntie [3](#page=3). #### 2.2.2 Pseudowillekeurige getallen In de praktijk wordt vaker gebruikgemaakt van algoritmen die reeksen getallen genereren die **lijken** willekeurig te zijn; dit zijn pseudowillekeurige getallen. Bij het implementeren van dergelijke algoritmen is het cruciaal om ervoor te zorgen dat een tegenstander toekomstige elementen van de reeks niet kan voorspellen op basis van eerdere elementen [3](#page=3). > **Tip:** Algoritmen voor pseudowillekeurige getalgeneratie (PRNG's) zijn deterministisch. Dit betekent dat bij gebruik van dezelfde startwaarde (seed) de reeks getallen identiek zal zijn bij herhaalde uitvoeringen. Hoewel dit voordelen heeft voor reproduceerbaarheid en verificatie, impliceert determinisme dat de reeks niet werkelijk willekeurig is, maar pseudowillekeurig [3](#page=3). #### 2.2.3 Voorbeelden van PRNG's en hun beperkingen Een veelgebruikte techniek voor pseudowillekeurige getalgeneratie is de lineaire congruentiële methode, oorspronkelijk voorgesteld door Lehmer. Deze methode werkt met een modulo-operatie [4](#page=4): $$ X_{n+1} = (aX_n) \pmod{m} $$ Een typische keuze voor $m$ is bijna gelijk aan de maximaal representeerbare niet-negatieve gehele waarde voor een gegeven computer, vaak een waarde nabij $2^{31}$ [4](#page=4). > **Voorbeeld:** Een veelgebruikte implementatie is $X_{n+1} = (aX_n) \pmod{(2^{31} - 1)}$ met $a = 16807$. Deze generator is uitgebreid getest en wordt vaak aanbevolen voor statistisch werk en simulaties [4](#page=4). Ondanks de uitgebreide tests, is de reeks getallen die door dit algoritme worden gegenereerd volledig deterministisch zodra de initiële waarde $X_0$ is gekozen. Dit heeft belangrijke implicaties voor cryptanalyse. Daarom zijn lineaire congruentiële methoden niet voldoende veilig voor cryptografische doeleinden en worden ze beschouwd als voorgangers van Lineaire Feedback Shift Registers (LFSR's) die vandaag de dag in veel stroomversleutelingen worden gebruikt [4](#page=4). > **Tip:** De standaard `random` module in Python wordt over het algemeen niet aanbevolen voor het genereren van cryptografisch willekeurige of pseudowillekeurige getallen. De `secrets` module wordt als veiliger beschouwd. Het wordt aangeraden om PRNG's te gebruiken die ondersteund worden door de hardware of het besturingssysteem van het systeem [3](#page=3). #### 2.2.4 Testen van onvoorspelbaarheid Een stroom van pseudowillekeurige getallen moet twee vormen van onvoorspelbaarheid vertonen [5](#page=5): * **Forward unpredictability:** Als de seed onbekend is, moet het volgende uitvoerbit in de reeks onvoorspelbaar zijn, ongeacht enige kennis van eerdere bits in de reeks [5](#page=5). * **Backward unpredictability:** Het mag ook niet mogelijk zijn om de seed te achterhalen op basis van kennis van gegenereerde waarden. Er mag geen correlatie tussen een seed en enige waarde die daaruit is gegenereerd, zichtbaar zijn; elk element van de reeks moet lijken op de uitkomst van een onafhankelijke willekeurige gebeurtenis met een waarschijnlijkheid van 1/2 [5](#page=5). #### 2.2.5 De relatie tussen willekeurigheidstests en onvoorspelbaarheid Dezelfde reeks tests die worden gebruikt om willekeurigheid te evalueren, dienen ook als tests voor onvoorspelbaarheid. Als een gegenereerde bitreeks willekeurig lijkt, is het niet mogelijk om een bepaald bit of een reeks bits 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). ### 2.3 Voorbeelden van willekeurigheidstests Het NIST SP 800-22 document beschrijft 15 afzonderlijke tests voor willekeurigheid. Hieronder worden drie van deze tests genoemd, met hun doelen [4](#page=4): * **Frequency test:** Dit is de meest basale test en essentieel in elke testsuite. Het doel is om te bepalen of het aantal enen en nullen in een reeks ongeveer gelijk is aan wat verwacht zou worden voor een werkelijk willekeurige reeks [4](#page=4). * **Runs test:** Deze test focust op het totale aantal "runs" in de reeks, waarbij een run een ononderbroken reeks identieke bits is, begrensd door een bit van de tegengestelde waarde. Het doel is om te bepalen of het aantal runs van enen en nullen van verschillende lengtes overeenkomt met de verwachtingen voor een willekeurige reeks [4](#page=4) [5](#page=5). * **Maurer's universal statistical test:** Deze test focust 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 gecomprimeerd kan worden zonder informatieverlies. Een significant comprimeerbare reeks wordt als niet-willekeurig beschouwd [5](#page=5). --- # Generatoren voor willekeurige getallen: PRNG's en TRNG's Dit onderwerp vergelijkt Pseudo Random Number Generators (PRNG's) en True Random Number Generators (TRNG's), hun methoden, beperkingen en toepassingen, met name in cryptografie. ### 3.1 Introductie tot willekeurige getallen generatoren Willekeurige getallen generatoren (RNG's) zijn onder te verdelen in twee hoofdtypen: Pseudo Random Number Generators (PRNG's) en True Random Number Generators (TRNG's). De keuze tussen deze twee hangt sterk af van de specifieke toepassing en de vereisten voor de mate van willekeurigheid [8](#page=8) [9](#page=9). ### 3.2 True Random Number Generators (TRNG's) TRNG's genereren willekeurige getallen door gebruik te maken van natuurlijke, niet-deterministische entropiebronnen. Deze bronnen zijn gebaseerd op fysische fenomenen die inherent willekeurig of onvoorspelbaar zijn [8](#page=8) [9](#page=9). #### 3.2.1 Entropiebronnen voor TRNG's Entropie, de maat voor willekeurigheid, wordt geoogst uit diverse natuurlijke bronnen. Voorbeelden van deze bronnen zijn [8](#page=8): * **Thermische ruis:** Gemeten door spanningen over niet-aangedreven weerstanden te amplifieren. Intel heeft hiervoor een commerciële chip ontwikkeld [10](#page=10). * **Licht of elektromagnetische straling:** Zoals zichtbaar spectrum elektromagnetische golven. Een project genaamd LavaRnd gebruikt hiervoor goedkope camera's en code [10](#page=10). * **Fysische processen:** Zoals de ioniserende straling gemeten door pulsdetectoren, gasontladingsbuizen, of lekkende condensatoren [10](#page=10). * **Elektrische activiteit:** Zoals huidgeleiding [10](#page=10). * **Systeemeigen sensoren:** Ingebouwde sensoren in computers die temperatuur, luchtvochtigheid, of licht meten [10](#page=10). * **Computerspecifieke bronnen:** Keystroke timing patronen, schijfactiviteit, muisbewegingen, en de momentane waarde van de systeemtijd [9](#page=9). * **Chaos-gebaseerde systemen:** Structureel vergelijkbare chaotische systemen die tijdreeksen genereren die op ruis lijken [10](#page=10). #### 3.2.2 Werking van TRNG's Het proces van een TRNG omvat het oogsten van entropie uit natuurlijke bronnen om een entropiepool te creëren. Wanneer een willekeurig getal nodig is, worden bits uit deze pool onttrokken. De pool wordt vervolgens opnieuw aangevuld door data van de entropiebron te oogsten [8](#page=8). > **Tip:** Het oogsten van entropie uit natuurlijke bronnen kan traag zijn, waardoor de generatie van grote hoeveelheden willekeurige getallen tijdrovend kan zijn en toepassingen kan blokkeren [9](#page=9). #### 3.2.3 Kwaliteit en schatting van entropie De kwaliteit van een TRNG hangt primair af van de entropiebron. Omdat de exacte hoeveelheid entropie in een bron niet nauwkeurig gemeten kan worden, is het noodzakelijk om deze te schatten. De min-entropie schatting, aanbevolen door NIST, is een veelgebruikte methode om goede entropiebronnen te identificeren [9](#page=9). #### 3.2.4 Verwerking en deskewing van TRNG-output De output van een TRNG kan bevooroordeeld zijn (niet een perfecte 50/50 verdeling van 0s en 1s). Om dit te corrigeren, worden deskewing-algoritmen gebruikt. Een methode hiervoor is het doorlopen van de bitstroom door een hash-functie of een PRNG. RFC 4086 raadt aan om input van meerdere hardwarebronnen te verzamelen en deze te mengen met een hash-functie voor willekeurige output [10](#page=10). #### 3.2.5 Implementatie in besturingssystemen Besturingssystemen bieden vaak ingebouwde mechanismen voor het genereren van willekeurige getallen. Linux gebruikt bijvoorbeeld muis- en toetsenbordactiviteit, schijf I/O operaties en specifieke interrupts als entropiebronnen. Deze bits worden gecombineerd in een buffer en vervolgens door een SHA-1 hash-functie gehaald wanneer willekeurige bits nodig zijn [10](#page=10). #### 3.2.6 Quantum Random Number Generation (QRNG) Voor toepassingen waarbij absolute zekerheid over willekeurigheid essentieel is, wordt quantum random number generation overwogen. Hoewel dit als duur wordt beschouwd, garandeert het ware willekeurigheid. In cryptografische context wordt alles wat een externe "goede" entropiebron gebruikt, als "echt willekeurig" beschouwd [11](#page=11). ### 3.3 Pseudo Random Number Generators (PRNG's) PRNG's genereren reeksen getallen die willekeurig lijken, maar die volledig deterministisch zijn, bepaald door een beginwaarde genaamd de "seed" [12](#page=12). #### 3.3.1 Werking van PRNG's Een PRNG neemt een vaste waarde, de seed, als input en produceert een reeks bits met behulp van een deterministisch algoritme. Vaak worden de resultaten van het algoritme teruggevoerd als input voor de productie van verdere bits (feedback-pad). Het cruciale punt is dat de outputbitstroom volledig wordt bepaald door de inputwaarde(n); een aanvaller die het algoritme en de seed kent, kan de volledige bitstroom reproduceren. De seed wordt vaak gegenereerd door een TRNG [12](#page=12). > **Tip:** Het nut van een PRNG is dat het efficiënt grote hoeveelheden willekeurige getallen kan produceren, wat bij TRNG's minder praktisch is [14](#page=14). #### 3.3.2 Toepassingen van PRNG's Er zijn twee hoofdtypen PRNG's gebaseerd op hun toepassing [13](#page=13): * **Pseudorandom number generator (PRNG):** Wordt gebruikt om een open-ended reeks bits te produceren, vaak als input voor een symmetrische stream cipher [13](#page=13). * **Pseudorandom function (PRF):** Produceert een pseudorandom string van bits met een vaste lengte, zoals symmetrische encryptiesleutels en nonces. Een PRF neemt naast een seed ook contextspecifieke waarden (zoals een gebruikers- of applicatie-ID) als input [13](#page=13). #### 3.3.3 Cryptografische veiligheid van PRNG's Voor cryptografische toepassingen is het essentieel dat een aanvaller die de seed niet kent, de pseudorandom string niet kan bepalen. Als de pseudorandom bitstroom voor een stream cipher wordt gebruikt, kan kennis hiervan de aanvaller helpen de plaintext te herstellen. Bij een PRF kan een zwakke generatie van willekeurige output de mogelijkheden voor brute-force aanvallen verkleinen [13](#page=13). > **Tip:** Hoewel PRNG's periodiek zijn, is de periode van moderne PRNG's zo lang dat deze voor de meeste praktische doeleinden genegeerd kan worden [14](#page=14). #### 3.3.4 Terminologie: DRBG en NDRBG Een TRNG wordt soms een non-deterministic random bit generator (NDRBG) genoemd, terwijl een PRNG een deterministic random bit generator (DRBG) wordt genoemd. De termen DRBG en NDRBG worden voornamelijk gebruikt in overheidscontexten, terwijl PRNG en TRNG vaker buiten deze kringen voorkomen. Soms wordt de afkorting voorafgegaan door 'CS' (Cryptographically Secure), wat resulteert in CSDRBG (Cryptographically Secure Deterministic Random Bit Generator) [13](#page=13). ### 3.4 Vergelijking en relatie tussen PRNG's en TRNG's Hoewel TRNG's ware willekeurigheid bieden, zijn er belangrijke redenen om PRNG's te gebruiken, zelfs wanneer TRNG's beschikbaar zijn [13](#page=13). #### 3.4.1 Waarom PRNG's gebruiken naast TRNG's? * **Efficiëntie voor stream ciphers:** Stream ciphers vereisen een determinische random number generator (PRNG). Het gebruik van een TRNG voor een lange keystream zou praktisch onhaalbaar zijn omdat de hele keystream veilig naar de ontvanger gestuurd moet worden. Met een PRNG hoeft alleen de kortere stream cipher sleutel veilig te worden overgedragen [13](#page=13). * **Bias eliminatie:** Zelfs als een TRNG beschikbaar is, is het wenselijk om deze te gebruiken om de seed voor een PRF te genereren, in plaats van de TRNG direct te gebruiken. Een PRNG kan de output van een TRNG "randomizen" en eventuele bias in de output elimineren [14](#page=14). * **Snelheid en schaalbaarheid:** TRNG's kunnen vaak niet de snelheid bereiken die nodig is voor toepassingen die miljoenen willekeurige bits per seconde vereisen, zoals in bank- of nationale beveiligingssystemen. PRNG's zijn efficiënter en kunnen veel getallen in korte tijd produceren [14](#page=14). * **PRF-toepassingen:** Zelfs wanneer een beperkt aantal bits wordt gegenereerd (zoals bij een PRF), is het gebruik van een TRNG voor de seed en vervolgens een PRF voor de output over het algemeen de voorkeur [14](#page=14). #### 3.4.2 Integratie van PRNG's en TRNG's Een gebruikelijke en robuuste aanpak is het gebruik van een TRNG om de seed voor een PRNG te genereren. Dit combineert de ware willekeurigheid van de TRNG voor de initiële seed met de efficiëntie en outputmogelijkheden van de PRNG voor het genereren van de benodigde reeksen willekeurige getallen [12](#page=12). > **Voorbeeld:** Een typische implementatie in een besturingssysteem combineert entropie van verschillende hardwarebronnen (TRNG-componenten) en verwerkt dit vervolgens met een hash-functie (een vorm van PRNG of deskewing) om een veilige pseudowillekeurige bitstroom te genereren [10](#page=10). ### 3.5 Beperkingen en overwegingen * **Entropie schatting:** De exacte hoeveelheid entropie in een bron is moeilijk te meten [9](#page=9). * **Kwaliteit van de bron:** De kwaliteit van een TRNG wordt direct bepaald door de gekozen entropiebron [9](#page=9). * **Determinisme van PRNG's:** De output van een PRNG is volledig voorspelbaar als het algoritme en de seed bekend zijn [12](#page=12). * **Kosten van QRNG's:** Quantum random number generation is een dure oplossing [11](#page=11). * **Browser fingerprinting:** De uniekheid van een browser fingerprint, die gerelateerd is aan de entropy van de browserconfiguratie, kan kwetsbaarheden creëren [11](#page=11). * **Wachtwoord entropy:** Wachtwoord entropy is gerelateerd aan het aantal pogingen dat nodig is om een wachtwoord te kraken, afhankelijk van lengte en karakterset. Recente richtlijnen leggen meer nadruk op lengte dan op complexiteit [11](#page=11). ### 3.6 Toepassingen in cryptografie Beide typen generatoren spelen een cruciale rol in cryptografie [13](#page=13) [8](#page=8): * **Stream ciphers:** Vereisen een deterministische bron van willekeurige getallen (PRNG) om een keystream te genereren [13](#page=13). * **Sleutelgeneratie:** PRNG's worden gebruikt om cryptografische sleutels te genereren, waarbij de kwaliteit van de sleutel afhangt van de willekeurigheid van de output [13](#page=13). * **Nonces:** Pseudo-random functies (PRF's) worden gebruikt om nonces (getallen die slechts één keer gebruikt worden) te genereren [13](#page=13). * **Beveiliging tegen brute-force aanvallen:** Een sterk gegenereerde sleutel door een PRNG verhoogt de weerstand tegen brute-force aanvallen [13](#page=13). * **Chaos-gebaseerde cryptografie:** Een opkomend onderzoeksveld dat chaotische systemen gebruikt voor het genereren van willekeurige sequenties, met potentieel voor kwantumresistentie [10](#page=10). --- # Specifieke algoritmen voor pseudowillekeurige getalgeneratie Dit onderwerp behandelt specifieke algoritmen voor het genereren van pseudowillekeurige getallen, waaronder de Blum-Blum-Shub (BBS) generator, de ANSI X9.17 PRNG, en methoden gebaseerd op blokcijfers zoals CTR- en OFB-modus [15](#page=15) [17](#page=17) [18](#page=18). ### 4.1 De Blum-Blum-Shub (BBS) generator De Blum-Blum-Shub (BBS) generator is een populaire benadering voor het genereren van cryptografisch veilige pseudowillekeurige getallen (CSPRBG) en staat bekend om zijn sterke theoretische basis voor cryptografische veiligheid [15](#page=15). #### 4.1.1 Principe van de BBS generator Het principe van de BBS generator omvat de volgende stappen [15](#page=15): 1. Kies twee grote priemgetallen, $p$ en $q$, zodanig dat $p \equiv 3 \pmod{4}$ en $q \equiv 3 \pmod{4}$ [15](#page=15). 2. Bereken $n = p \times q$ [15](#page=15). 3. Kies een willekeurig getal (seed) $s$ dat relatief priem is met $n$ (d.w.z. $p$ en $q$ zijn geen factoren van $s$) [15](#page=15). 4. Initialiseer de eerste toestand $X_0$ met de seed $s$: $X_0 = s$ [15](#page=15). 5. Genereer de volgende toestand door te kwadrateren modulo $n$: $X_i = (X_{i-1})^2 \pmod{n}$ [15](#page=15). 6. Output is de minst significante bit van de toestand $X_i$ [15](#page=15). #### 4.1.2 Cryptografische veiligheid Een CSPRBG, zoals de BBS generator, moet de 'next-bit test' doorstaan. Dit betekent dat er geen polynomial-time algoritme mag bestaan dat, gegeven de eerste $k$ bits van de outputsequentie, de $(k+1)$-de bit kan voorspellen met een waarschijnlijkheid significant groter dan 1/2. De veiligheid van BBS is direct gekoppeld aan de moeilijkheid om $n$ te factoriseren in zijn priemfactoren $p$ en $q$ [15](#page=15). #### 4.1.3 Voorbeeld van BBS Een voorbeeld van de BBS generator: met $n = 192649 = 383 \times 503$ en een seed $s = 101355$. De uitvoer wordt gegenereerd door herhaaldelijk de huidige waarde te kwadrateren modulo $n$ en de minst significante bit te extraheren [16](#page=16). > **Tip:** De meeste gangbare PRNG's zijn niet speciaal ontworpen, maar gebaseerd op andere cryptografische primitieven zoals blokcijfers of hashfuncties [16](#page=16). ### 4.2 De ANSI X9.17 PRNG De ANSI X9.17 PRNG was ooit een van de sterkste PRNG's en werd in veel financiële applicaties, PGP en sommige VPN's gebruikt [17](#page=17). #### 4.2.1 Principe en veiligheidsoverwegingen Dit algoritme maakt gebruik van Triple DES als blokcijfer om willekeurige bitpatronen te genereren. Een belangrijk nadeel is het gebruik van twee statische sleutels, $K_1$ en $K_2$, die geheim moeten blijven. Kwetsbaarheden in sommige implementaties, zoals hard-coded sleutels, konden aanvallers in staat stellen de veiligheid van de generator te doorbreken met kennis van de sleutel en een beperkte hoeveelheid output. Hoewel de zwakheden al in 1998 werden beschreven, bleef het systeem lange tijd in gebruik [17](#page=17). ### 4.3 PRNG's gebaseerd op blokcijfers (CTR en OFB modus) Twee veelgebruikte benaderingen om een PRNG te bouwen met behulp van een blokcijfer zijn de CTR (Counter) modus en de OFB (Output Feedback) modus [18](#page=18). #### 4.3.1 CTR modus In de CTR modus wordt een encryptiesleutel $K$ en een tellerwaarde $V$ gebruikt. De waarde $V$ wordt na elke encryptie met 1 verhoogd. De seed voor de generator bestaat uit de encryptiesleutel en de initiële tellerwaarde $V$. NIST SP 800-90, ANSI X9.82 en RFC 4086 bevelen de CTR modus aan [18](#page=18). > **Voorbeeld:** Bij AES-128 bestaat de seed uit een 128-bit sleutel en een 128-bit $V$-waarde [18](#page=18). #### 4.3.2 OFB modus In de OFB modus wordt de tellerwaarde $V$ bij elke outputblokupdate vervangen door de waarde van het voorgaande PRNG-blok. Net als de CTR modus wordt de OFB modus aanbevolen in X9.82 en RFC 4086 [18](#page=18). #### 4.3.3 CTR_DRBG (Deterministic Random Bit Generator) De NIST CTR_DRBG is een gedetailleerd algoritme gebaseerd op de CTR modus [19](#page=19). * **Initialisatie en update functie:** Vereist een encryptiesleutel $K$ en een initiële tellerwaarde $V$. Deze waarden worden vaak gecombineerd tot een 'seed'. Een entropiebron levert $seedlen$ bits die worden gecombineerd met de output van de CTR-encryptie om een nieuwe seed te vormen. De $seedlen$ meest significante bits van deze nieuwe seed vormen de nieuwe sleutel ($K$), en de meest significante $outlen$ bits vormen de nieuwe tellerwaarde ($V$) [19](#page=19) [20](#page=20). * **Generate functie:** Genereert pseudowillekeurige bits blok voor blok met behulp van dezelfde encryptiesleutel $K$ en een oplopende tellerwaarde $V$ [20](#page=20). * **Reseed interval:** Om de veiligheid te verhogen, wordt het aantal gegenereerde bits per cyclus beperkt door een `reseed_interval`. Wanneer dit interval is bereikt, wordt de update functie aangeroepen om de staat ($K$ en $V$) te vernieuwen met behulp van de entropiebron [20](#page=20). > **Tip:** Hardware-implementaties van CTR_DRBG, zoals de Intel DRNG, kunnen hogere snelheden en potentieel meer veiligheid bieden door de eliminatie van I/O-vertragingen en softwarekwetsbaarheden [20](#page=20). #### 4.3.4 Veiligheidsoverwegingen bij CTR_DRBG Ondanks de aanbevelingen zijn er veiligheidskwesties gerelateerd aan CTR_DRBG [21](#page=21): * **State leakage:** Gedeeltelijke uitlekken van de interne staat kan leiden tot onverwachte beveiligingsafbrekingen, zelfs bij aanbevelingen zoals die van NIST [21](#page=21) [22](#page=22). * **Side-channel attacks:** Implementaties die gebruik maken van kwetsbare blokcijfers (zoals T-table AES) of specifieke parameterkeuzes, kunnen vatbaar zijn voor side-channel attacks, zoals cache-aanvallen. Dit kan leiden tot het herstellen van geheime sleutels uit TLS-verbindingen [21](#page=21). * **Forward Security:** Bij het weglaten van optionele inputs kan HMAC_DRBG de eigenschap van forward security niet behalen, ondanks beweringen in de standaard [22](#page=22). #### 4.3.5 Andere NIST DRBG's Naast CTR_DRBG bevat het NIST-document ook hash-gebaseerde PRNG's zoals HASH_DRBG en HMAC_DRBG [22](#page=22). #### 4.3.6 Dual_EC_DRBG De Dual_EC_DRBG, een voorheen door NIST goedgekeurde, maar nu ingetrokken, algoritme, bleek een backdoor te bevatten die door de NSA was ingebouwd [22](#page=22). > **Tip:** Het is essentieel om de werking en potentiële kwetsbaarheden van verschillende DRBG's, inclusief die gebaseerd op hashfuncties en de ingetrokken Dual_EC_DRBG, grondig te bestuderen [22](#page=22). --- # Lineaire Feedback Shift Registers (LFSR's) Lineaire feedback shift registers (LFSR's) zijn fundamentele bouwstenen voor stroomcijfers, bestaande uit een reeks geheugencellen waarvan de inhoud periodiek wordt bijgewerkt via een lineaire feedbackfunctie [23](#page=23). ### 5.1 Werking en notatie van LFSR's Een LFSR is opgebouwd uit een aantal geheugencellen, elk met een bitwaarde, die samen een register vormen. In elke cyclus worden specifieke cellen ‘getapt’ en hun waarden door een feedbackfunctie geleid. Vervolgens wordt het register met één bit verschoven, waarbij de uitvoer de bit is die uit het register wordt geschoven. De gecombineerde waarde van de getapte bits wordt in de lege cel bovenaan het register ingevoerd [23](#page=23). #### 5.1.1 Feedbackfunctie en GF [2](#page=2). De feedbackfunctie is doorgaans een lineaire functie, en bewerkingen vinden plaats in het eindige veld $GF $ (Galoisveld met twee elementen). Dit betekent dat optelling de XOR-operatie is, waarbij $1+1=0$. Een reeks van alleen nullen zal altijd resulteren in nullen [23](#page=23) [2](#page=2). #### 5.1.2 Notatie De definitie van LFSR-transformaties kan op verschillende manieren worden genoteerd. Een veelgebruikte notatie beschrijft de relatie tussen opeenvolgende bitwaarden. Een andere notatie maakt gebruik van polynomen. Hierbij correspondeert de oudste bitwaarde (bijvoorbeeld $s_0$) met de term van de hoogste graad in het polynoom, en elke volgende bitwaarde met een term van lagere graad. Er wordt altijd een constante term van 1 toegevoegd aan het polynoom [23](#page=23) [24](#page=24). * **Lineaire recurrence relatie:** $s_n = s_{n-1} + s_{n-4} + s_{n-5}$ (in $GF $) [23](#page=23) [2](#page=2). * **Polynomale notatie:** * $X^3 + x + 1$ correspondeert met $s_3 = s_2 + s_0$ [24](#page=24). * $X^4 + x^3 + 1$ correspondeert met $s_4 = s_1 + s_0$ [24](#page=24). * $X^{32} + x^3 + 1$ correspondeert met $s_{32} = s_{29} + s_0$ [24](#page=24). ### 5.2 Periode en maximale periodes Een LFSR heeft altijd een periode, waarna de gegenereerde reeks zich gaat herhalen. De maximale periode kan worden berekend op basis van de orde van het register [23](#page=23). #### 5.2.1 Irreducibele en primitieve polynomen Wanneer de "connection polynomial" irreducibel (of priem) en primitief is, bereikt de LFSR zijn maximale periode, die gelijk is aan $2^n - 1$, waarbij $n$ het aantal bits in het register is [24](#page=24). ### 5.3 Beperkingen en het belang van non-lineariteit Ondanks hun snelheid en de goede statistische eigenschappen, met name een hoge periode, zijn LFSR's als zelfstandige keystreamgeneratoren kwetsbaar (#page=23, 25). De lineariteit maakt het mogelijk om de cipher te breken bij kennis van een relatief klein aantal opeenvolgende bits [23](#page=23) [25](#page=25). #### 5.3.1 Methoden om non-lineariteit te introduceren Om de lineariteit van LFSR's te overwinnen en veiligere stroomcijfers te creëren, worden ze vaak gecombineerd binnen complexere systemen. Enkele algemene methoden hiervoor zijn [25](#page=25): * Non-lineaire combinatie generator [25](#page=25). * Non-lineaire filter generator [25](#page=25). * Klok-gecontroleerde generator [25](#page=25). * Dynamische LFSR's [25](#page=25). Daarnaast bestaan er ook zogenaamde Non-Linear Feedback Shift Registers (NLFSR's), die een non-lineaire feedbackfunctie $f$ gebruiken in plaats van een lineaire. S-boxen, bekend uit blokcijfers, zijn een andere techniek die wordt toegepast om non-lineariteit te bereiken in sommige stroomcijferontwerpen. Non-lineariteit wordt bereikt door termen zoals $s_i^2$ of producten zoals $s_i \cdot s_{i-1}$ te gebruiken [25](#page=25). > **Tip:** De eenvoud van LFSR's, hoewel gunstig voor hardware-implementaties, is ook hun grootste zwakte in cryptografische toepassingen. #### 5.3.2 Voorbeelden van zwakke stroomcijfers Slechte voorbeelden van de combinatie van LFSR's met toegevoegde non-lineariteit zijn de algoritmes A5/1 en E0 [25](#page=25). * **A5/1:** Dit is een bekend stroomcijfer dat werd gebruikt in GSM-netwerken. Het maakt gebruik van drie LFSR's met specifieke connection polynomials. De sleutelgrootte van 64 bits wordt als te klein beschouwd en is effectief slechts 61 bits. Het breken van A5/1 vereist slechts enkele minuten computatietijd met korte gespreksfragmenten, zonder significante pre-computatie of opslagcapaciteit [25](#page=25) [26](#page=26). * **E0:** Dit stroomcijfer wordt gebruikt in het Bluetooth-protocol voor draadloze communicatie. E0 biedt slechts een beperkt beveiligingsniveau met een tijdscomplexiteit van $2^{38}$ [26](#page=26). Beide algoritmes, A5/1 en E0, vertonen serieuze zwakheden [26](#page=26). > **Tip:** Hoewel LFSR's zeer nuttig zijn als bouwstenen vanwege hun efficiëntie, is het cruciaal om te begrijpen dat ze nooit op zichzelf gebruikt mogen worden als keystream generator in een beveiligd cryptografisch systeem. Ze vormen de basis voor complexere ontwerpen die non-lineariteit introduceren om de veiligheid te verhogen. --- ## 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 | |------|------------| | Willekeurige binaire getallen | Getallen die gebruikt worden in cryptografische algoritmen en protocollen voor sleuteldistributie, authenticatie en het voorkomen van replay-aanvallen door middel van nonces. | | Nance | Een willekeurig nummer dat slechts één keer wordt gebruikt, voornamelijk tijdens handshake-protocollen om replay-aanvallen te voorkomen. | | Sessiesleutel | Een geheime sleutel voor symmetrische encryptie die wordt gegenereerd voor een specifieke transactie of sessie en slechts voor een korte periode geldig is. | | RSA publieke-sleutel encryptie | Een encryptiealgoritme dat gebruikmaakt van een paar publieke en private sleutels, waarbij de publieke sleutel gebruikt wordt voor encryptie en de private sleutel voor decryptie. | | Symmetrische stroomencryptie | Een encryptiemethode waarbij dezelfde sleutel wordt gebruikt voor zowel encryptie als decryptie, en waarbij een bitstroom wordt gegenereerd om de plaintext te versleutelen. | | Uniforme distributie | Een eigenschap van een reeks getallen waarbij de frequentie van het voorkomen van nullen en enen ongeveer gelijk is, wat kenmerkend is voor echt willekeurige reeksen. | | Onafhankelijkheid | Een eigenschap van een reeks getallen waarbij geen enkel deel van de reeks kan worden afgeleid uit andere delen, wat cruciaal is voor onvoorspelbaarheid in cryptografie. | | Pseudowillekeurige getallen | Getallen die worden gegenereerd door een deterministisch algoritme, maar die statistisch gezien willekeurig lijken en vaak worden gebruikt wanneer echte willekeurige getallen niet praktisch zijn. | | Seed | Een beginwaarde die wordt gebruikt door een pseudowillekeurige getalgenerator (PRNG) om een reeks getallen te produceren. Dezelfde seed zal altijd dezelfde reeks getallen genereren. | | Lineaire congruentiële methode | Een veelgebruikte methode voor het genereren van pseudowillekeurige getallen, gebaseerd op een lineaire recurrente relatie met modulus. | | Lineaire Feedback Shift Registers (LFSR's) | Circuits die bestaan uit geheugencellen en een feedbackfunctie om reeksen bits te genereren. Ze zijn efficiënt in hardware, maar hebben inherente lineariteitsproblemen. | | True Random Number Generators (TRNG's) | Generatoren die gebruikmaken van natuurlijke, entropiebronnen zoals atmosferische ruis of thermische ruis om echt willekeurige getallen te produceren. | | Entropy | Een maat voor de willekeurigheid of onvoorspelbaarheid van informatie. TRNG's oogsten entropy uit fysieke processen. | | Min-entropy schatting | Een methode om de hoeveelheid entropy in een bron te schatten, aanbevolen door NIST, om goede entropybronnen te identificeren voor TRNG's. | | Deskewing algoritmen | Algoritmen die worden gebruikt om de "bias" (onevenwichtigheid) in een reeks bits te verminderen of te elimineren, die afkomstig kan zijn van een entropybron. | | Cryptographically Secure Pseudorandom Bit Generator (CSPRBG) | Een PRNG die voldoet aan specifieke cryptografische veiligheidsnormen, zoals de next-bit test, waardoor de output onvoorspelbaar is voor aanvallers. | | Blum-Blum-Shub (BBS) generator | Een cryptografisch veilige pseudowillekeurige bitgenerator waarvan de beveiliging gebaseerd is op de moeilijkheid van het factoriseren van een groot getal (het product van twee grote priemgetallen). | | ANSI X9.17 PRNG | Een pseudowillekeurige getalgenerator die vroeger als sterk werd beschouwd en gebruikmaakte van triple DES. Zwakheden werden gevonden in de statische sleutels. | | CTR modus | Een modus van blokcijfers (Cipher Block Chaining) die kan worden gebruikt om pseudowillekeurige getallen te genereren. Hierbij wordt een teller ($V$) geïncrementeerd voor elke blok encryptie. | | OFB modus | Een modus van blokcijfers (Output Feedback) die ook wordt gebruikt voor het genereren van pseudowillekeurige getallen. Hierbij wordt de output van de vorige encryptie gebruikt als input voor de volgende. | | NIST CTR_DRBG | Een specifieke implementatie van een Deterministic Random Bit Generator (DRBG) die de CTR-modus gebruikt en door NIST wordt aanbevolen. | | Dual_EC_DRBG | Een door NIST goedgekeurde DRBG die later werd ingetrokken omdat er een backdoor door de NSA was ingebouwd. | | Chaos-gebaseerde cryptografie | Een nieuw onderzoeksgebied dat gebruikmaakt van chaotische systemen om stroomcijfers te genereren, met potentieel voor kwantumresistentie. | | NLFSR (Non-Linear Feedback Shift Register) | Een variatie op LFSR's die een niet-lineaire functie gebruikt in plaats van een lineaire, om de voorspelbaarheid te verhogen. | | S-box | Een tabel die wordt gebruikt in blokcijfers om niet-lineariteit te introduceren, en die ook in sommige stroomcijfers kan worden toegepast. | | A5/1 | Een bekende stroomcijfer, voorheen gebruikt in GSM-netwerken, die drie LFSR's combineert. Het heeft zwakheden vanwege een te kleine sleutel en lineaire eigenschappen. | | E0 | De stroomcijfer die wordt gebruikt voor de vertrouwelijkheid van communicatie in het Bluetooth-protocol, met beperkte beveiliging. |