Po tym jak NIST opublikował nowe cztery standardy generatorów liczb losowych (NIST SP 800-90) część kryptologów zwraca uwagę na anomalie w jednym z nich mogące być potencjalnym backdoorem. Zaprezentowane w dokumencie generatory są oparte o podstawowe algorytmy kryptograficzne (chciałoby się skalkować z angielskiego “o prymitywy”, ale źle się kojarzy), każdy o inny. Jeden jest oparty o funkcję skrótu, jeden o HMAC (funkcja skrótu z kluczem), jeden o szyfr blokowy a jeden o krzywe eliptyczne.
Ostatni z nich (Dual_EC_DRBG) jest właśnie przedmiotem krytyki. Nie tylko ze względu na powolność działania, ale głównie na podejrzane własności algorytmu. Otóż w prezentacji na konferencji Crypto’2007 panowie Dan Shumow i Niels Fergusson zaprezentowali ciekawą rzecz - otóż generator jest oparty o zbiór stałych - są to wartoście arbitralnie ustalone przez NIST (NSA) i wymienione w standardzie bez uzasadnienia dlaczego wybrano akurat te a nie inne liczby (podobnie jak z S-Boksami w DES). Shumow i Fergusson wykazali, że liczby te są związane z innym, nieznanym zbiorem liczb - jak rozumiem w sposób podobny jak klucz prywatny z publicznym.
Co jest najbardziej istotne, znajomość tego drugiego zestawu umożliwia ustalenie stanu generatora - i w konsekwencji przewidywanie kolejnych wartości - już po przeanalizowaniu 32 bajtów wyjścia z generatora.
Bruce Schneier stawia sprawę jasno - nie wiadomo czy NSA posiada ten drugi zestaw i czy w ogóle posiada go ktokolwiek. Dziwi go jednak fakt arbitralnego wskazania tego zestawu wartości jako standardowego w generatorze Dual_EC_DRBG. Przyznaje jednak równocześnie, że standard rekomenduje jako opcję wygenerowanie własnego zestawu wartości, co skutecznie zamyka “backdoor”.
Sami autorzy użyli w prezentacji następującego sformułowania:
WHAT WE ARE NOT SAYING: NIST intentionally put a back door in this PRNG WHAT WE ARE SAYING: The prediction resistance of this PRNG (as presented in NIST SP800-90) is dependent on solving one instance of the elliptic curve discrete log problem. (And we do not know if the algorithm designer knew this before hand.)
- "Did NSA Put a Secret Backdoor in New Encryption Standard?", Bruce Schneier, Wired
- "On the Possibility of a Back Door in the NIST SP800-90 Dual EcPrng", Niels Fergusson, Dan Shumow (Microsoft) (tak, to nie pomyłka :)
- "Recommendation for Random Number Generation Using Deterministic Random Bit Generators", NIST SP 800-90
- SecurityStandard.pl "Backdoor w standardzie kryptograficznym?"