image

NIST verwijdert verdacht NSA-algoritme van advieslijst

woensdag 23 april 2014, 12:42 door Redactie, 5 reacties

Het Amerikaanse National Institute of Standards and Technology (NIST) heeft een door de NSA ontworpen encryptiealgoritme van de advieslijst verwijderd. Reden zijn langlopende verdenkingen dat het algoritme door de inlichtingendienst van een backdoor is voorzien.

Vorig jaar september werd via klokkenluider Edward Snowden bekend dat de NSA opzettelijk backdoors aan encryptiestandaarden zou hebben toegevoegd. Het zou in ieder geval om de Dual Elliptic Curve Deterministic Random Bit Generator (Dual_EC_DRBG) gaan, waarmee willekeurige getallen worden gegenereerd. Door de backdoor zouden de gegenereerde getallen helemaal niet willekeurig zijn en zou het mogelijk om versleutelde informatie te ontsleutelen.

Volgens documenten van Snowden zou de NSA erin zijn geslaagd om het algoritme door het NIST goedgekeurd te krijgen en werd in de Special Publication 800-90A en draft Special Publications 800-90B en 800-90C opgenomen, die aanbevelingen bevatten voor het genereren van willekeurige getallen middels DRBG. Na de onthullingen in september besloot het NIST het algoritme te onderzoeken en gaf dezelfde maand nog een waarschuwing af om het algoritme gedurende het onderzoek niet te gebruiken.

Het onderzoek is nu afgelopen en het adviesorgaan heeft aan de hand hiervan en het verdwenen vertrouwen bij gebruikers besloten om het algoritme uit de Special Publication 800-90A publicatie te verwijderen. Leveranciers die het algoritme toch nog gebruiken en zich aan Amerikaanse Federale richtlijnen willen houden krijgen het advies om op een ander algoritme uit de advieslijst over te stappen.

Reacties (5)
23-04-2014, 14:01 door Anoniem
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.
23-04-2014, 15:09 door Anoniem
Waarom zou iemand NIST ooit nog geloven ? Of Diginotar ?
23-04-2014, 15:49 door Anoniem
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`.
23-04-2014, 16:28 door Anoniem
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.
24-04-2014, 10:35 door Anoniem
Door Anoniem: 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.
Reageren

Deze posting is gelocked. Reageren is niet meer mogelijk.