Dual EC DRBG is een "cryptographically secure pseudorandom number generator", een ding dat een stroom bitjes genereert die "niet te onderscheiden is van werkelijk willekeurig". Op zichzelf dus geen encryptiealgoritme, maar het hoort wel thuis in de gereedschapskist van de cryptograaf. Nouja, dit specifieke algoritme hoort in quarantaine, het is schadelijker dan waardeloos.

En toch heeft bijvoorbeeld RSA Security (het bedrijf*) Dual EC DRBG standaard aangezet, terwijl er betere keuzes voorhanden waren. En ook terwijl er toch al een tijd vragen over gesteld werden. Heel toevallig.


* Dus niet te verwarren met het algoritme genaamd RSA, waar voor zover bekend niets mis mee is.

Waarom zou iemand NIST ooit nog geloven ? Of Diginotar ?

Er hoeft geen backdoor in de pseudo-random generator te zitten om de gegenereerde getallen door een Universal Turing Machine (UTM) te kunnen voorspellen.

Je kunt op qrng.physik.hu-berlin.de lezen dat er meer dan 1000 gebruikers zijn van de true quantum randomness server
en er sinds de start meer dan 1 PetaByte aan data geleverd.

Daar is een goede reden voor.

Pseudo-randomness faalt voor specifieke statistische testen zoals de LIL-test, zie bijvoorbeeld
wuala.com/FreemoveQuantumExchange/Aspects/Randomness/Theory/LIL

Wat ernstiger is dat pseudo-random generatoren te analyseren zijn en de output na een bepaalde hoeveelheid bits volledig te voorspellen is.

Wil je dit zelf eens proberen, dan kun je het LCPT_gcc.cc programma uit de directory wuala.com/FreemoveQuantumExchange/Aspects/Randomness/Theory/Berlekamp-Massey downloaden met de
files s01.dat en s02.dat. Dit zijn pseudo-random files welke gegeneerd zijn met een Mersenne-Twister PRNG. Alleen de laatste byte van elk output word is opgeslagen in deze files. Je kunt dit doen omdat in een PRNG alle bits met elkaar gecorreleerd zijn. Wil je zelf pseudo-random data genereren met de Mersenne-Twister dan kan dit ook. De source code van de Mersenne Twister is ook te downloaden uit de bovenstaande directory.

Het hierboven genoemde LCPT_gcc.cc is een O(n^2) Berlekamp-Massey algoritme. In de source wordt alleen
de least significant bit van elk byte van de inputfile gesampled. Ook dit is weer mogelijk omdat in een PRNG alle
output bits gecorreleerd zijn.

Wanneer je met het LCPT_gcc.cc programma de files s01.dat en s02.dat test dan zul je zien dat de
complexity op 19937 blijft steken, wat de complexity van een Mersenne-Twister is. Wanneer je met de Mersenne
Twister welke je kunt vinden in bovenstaande directory pseudo-random files genereerd en test, dan zult je zien
dat de complexity 4*19937 is. Dit komt omdat er per output word (van 32bits) 4 bits gesampled worden. Ook kun je op
vergelijkbare wijze de output van de Microsoft PRNG testen, zie de directory. Je zult dan vergelijkbare resultaten vinden.

Bovenstaande PRNGs zijn als voorbeeld bedoeld. Je kunt deze procedure voor elke universele Turing-machine (UTM) uitvoeren. wanneer je alle output bits sampeld.

Je kunt de lengte van de output file van een willekeurige UTM welke je nodig hebt om deze te analyseren uitrekenen
met het Excel spreadsheet in de directory. Met het abc tool kun je de complexiteit van het algoritme schatten.
Het abc tool dat je in de directory kunt vinden is gecompileerd voor Mac OS-X.

Voor de meeste UTM`s is de benodigde filelengte te lang om het met een O(n^2) algoritme te kunnen analyseren. Dit
kan echter wel met een O(n) Berlekamp-Massey algoritme.

Hier zijn meerdere implementaties van zoals de Blackburn implementatie, zie het paper in de directory.

In de subdirectories Chapter2 en Chapter3 kun je de sources vinden van een andere O(n) implementatie.
Een beschrijving van deze implementatie kun je vinden in het document `Linear Feedback Shift Registers`.

Een beetje vreemd dat een veiligheidsorganisatie de digitale veiligheid van haar eigen burgers probeert te ondermijnen met dit soort onzin. Als de NSA kennis heeft van een backdoor dan hebben anderen dat ongetwijfelt ook.

Je kunt backdoors creëren waar je alleen wat mee kunt indien je een geheime sleutel hebt.
Min of meer vergelijkbaar met public key encryptie, waar je iets met een sleutel kunt encrypten, maar alleen de eigenaar van de bijbehorende geheime sleutel het weer kan decrypten.