Furtka NSA w generatorze pseudolosowym

Jedną z najszerzej komentowanych informacji pochodzących od Edwarda Snowdena jest ta o manipulowaniu przez NSA standardami NIST dotyczącymi generatorów pseudolosowych. Choć dokumenty ujawnione przez Snowdena nie podają o który generator dokładnie chodzi, to przypuszcza się, że jest to generator Dual_EC_DRBG, który od początku przyjmowany był przez kryptologów ze sporym sceptycyzmem. 

Sceptycyzm ten wynikał z kilku powodów. Przede wszystkim, generator ten jest o kilka rzędów wielkości wolniejszy od innych generatorów, co jest konsekwencją faktu, że jego działanie oparte jest na krzywych eliptycznych. Taka niska wydajność niekoniecznie dyskwalifikuje algorytm. Czasami użytkownicy są gotowi pogodzić się z wolniejszym działaniem systemu, o ile zwiększa to jego bezpieczeństwo. Tak jest np. w przypadku kiedy bezpieczeństwo to może być formalnie dowiedzione w oparciu o jakieś wiarygodne założenia dotyczące trudności konkretnych problemów algorytmicznych. O dziwo generator Dual_EC_DRBG nie został poparty żadnym takim dowodem, co od razu powinno wydawać się podejrzane. Początkowo cześć inżynierów uważała jednak te wątpliwości za kaprysy teoretyków. Portal Ars Technica cytuje (anonimowo) jednego z nich:

Wyobrażałem sobie matematyka zirytowanego brakiem teoretycznych podstaw generatora pseuodolosowego marudzącego na temat standardów NIST.

Tymczasem dość szybko wyszło na jaw, że Dual_EC_DRBG ma wady, które powinny zainteresować nie tylko teoretyków ale i praktyków. Po pierwsze, okazało się, że z prawdopodobieństwem około 0.1% lepszym od 0.5 da się przewidzieć kolejny bit wygenerowany przez Dual_EC_DRBG na podstawie bitów poprzednich (0.1% to zdecydowanie za dużo w kryptografii). Po drugie, Dual_EC_DRBG zawiera arbitralnie ustalone, wpisane stałe do standardu, parametry.  Jeśli parametry te zostały wybrane losowo, to generator wydaje się w miarę bezpieczny (poza problemem opisanym powyżej). Kryptologom udało się jednak pokazać, że twórcy generatora są w stanie wybrać te parametry w taki sposób by wyglądały one na losowe, a jednak dawały tym twórcom możliwość całkowitego złamania bezpieczeństwa generatora -- krótko mówiąc w generatorze tym można zamontować tzw. furtkę (ang. backdoor)! Wzbudziło to oczywiście podejrzenia, że NSA manipulowało tymi parametrami, a rewelacje Snowdena tylko te podejrzenia potwierdziły. Więcej na temat szczegółów technicznych ataków na Dual_EC_DRBG można poczytać w artykule Matthew Greena.

Warto dodać, że Dual_EC_DRBG jest używany w szeregu produktów kryptograficznych. Podkreślmy też, że dobra losowość jest bardzo ważna w kryptografii -- jest chociażby potrzebna do generacji kluczy, oraz niezbędna jest w wielu algorytmach szyfrujących (np. popularny szyfr ElGamala jest zupełnie złamany jeśli przeciwnik może przewidzieć losowość użytą w procesie szyfrowania).

NIST oczywiście zaprzecza, że w Dual_EC_DRBG zainstalowano furkę. Mało kto jednak w te zapewnienia wierzy. O tym jak poważna jest sytuacji świadczy fakt, że firma RSA Security wydała właśnie zalecenie dla swoich klientów aby jak najszybciej zaprzestali używania Dual_EC_DRBG. 

---

Aktualizacja z 25.09.2013:
W magazynie "Wired" ukazał się właśnie bardzo dobry artykuł na powyższy temat.