Testowanie i walidacja implementacji RNG

Testowanie generatorów liczb losowych wiąże się z fundamentalnym wyzwaniem: prawdziwie losowe ciągi i pseudolosowe ciągi generowane przez dobry PRNG wyglądają identycznie w testach statystycznych. Żaden test dla ciągu o skończonej długości nie może dowieść, że ciąg jest losowy — statystyka może jedynie wykryć nielosowość z pewnym poziomem ufności. Testowanie potwierdza, że RNG nie wykazuje oczywistych obciążeń ani wzorców, ale nie może dowieść bezpieczeństwa kryptograficznego. Testowanie kryptograficznych generatorów RNG ma dwa odrębne cele: (1) jakość statystyczna — sprawdzenie, czy rozkład danych wyjściowych wygląda na jednostajny i niezależny; (2) siła kryptograficzna — sprawdzenie, czy algorytm DRBG został poprawnie zaimplementowany i czy deklaracje dotyczące jego bezpieczeństwa są prawdziwe. Cele te wymagają różnych metod testowania.

NIST SP 800-22 zawiera 15 testów statystycznych do oceny ciągów bitów. Testy obejmują: test częstości (monobit) — proporcja jedynek powinna być zbliżona do 0,5; test częstości bloków — częstość jedynek w każdym bloku m-bitowym; test serii — liczba nieprzerwanych serii identycznych bitów; test najdłuższej serii — długość najdłuższej serii jedynek; test rzędu macierzy binarnych — rząd macierzy binarnych utworzonych z ciągu; test widmowy (DFT) — wykrywanie wzorców okresowych; test dopasowania nakładających się wzorców — zliczanie wystąpień określonych wzorców; uniwersalny test statystyczny Maurera — kompresja ciągu i pomiar stopnia jego skrócenia. Każdy test generuje wartość p; p < 0.01 sugeruje nielosowość. Testy uruchamia się na ciągach od 1 miliona do 1 miliarda bitów.

TestU01 (L'Ecuyer i Simard, 2007) to kompleksowy zestaw testów statystycznych, szeroko stosowany w społeczności zajmującej się RNG. SmallCrush: 10 testów, około 35 sekund, odpowiedni do szybkich kontroli. Crush: 144 testy, około 2 godzin. BigCrush: 160 testów, około 24 godzin. Testy BigCrush wykrywają subtelne korelacje, których nie wykrywa NIST SP 800-22. Dobrze zaprojektowane kryptograficzne DRBG (HMAC_DRBG, CTR_DRBG) bez problemu przechodzą BigCrush — ich dane wyjściowe są obliczeniowo nieodróżnialne od losowych dla algorytmów działających w czasie wielomianowym. Niekryptograficzne PRNG (Mersenne Twister, generatory liniowe kongruencyjne) nie przechodzą niektórych testów BigCrush. Niepowodzenie testu BigCrush jest silnym sygnałem, że danego RNG nie należy używać do celów kryptograficznych.

SP 800-90B i 90A określają testy poprawności działania, które DRBG muszą wykonywać nieprzerwanie podczas pracy. Ciągły test RNG (CRNGT): każdy wygenerowany blok jest porównywany z poprzednim — jeśli bloki są równe (zablokowany RNG), DRBG musi przejść w stan błędu i zatrzymać generowanie. Test liczby powtórzeń: jeśli kolejne próbki mają tę samą wartość powtórzoną więcej razy, niż można oczekiwać statystycznie na podstawie oszacowania entropii, test należy uznać za nieudany. Adaptacyjny test proporcji: jeśli najczęściej występująca wartość pojawi się w oknie więcej razy niż wynosi ustalony próg, test należy uznać za nieudany. Testy te wykrywają awarie źródeł entropii (zablokowany czujnik, usterka sprzętowego HWRNG), zanim po cichu doprowadzą do naruszenia generowania kluczy kryptograficznych.

PractRand to nowoczesne narzędzie do testowania RNG, zaprojektowane do oceny online (strumieniowej). Analizuje ciąg w miarę jego generowania, zamiast wymagać z góry ustalonej długości. Stosuje między innymi testy odstępów, testy rozkładu bitów i testy widmowe z adaptacyjną precyzją. PractRand szczególnie dobrze wykrywa generatory RNG, które tworzą dobre krótkie ciągi, ale ujawniają wzorce po wygenerowaniu miliardów bitów. Kryptograficzne DRBG generują dane wyjściowe, których PractRand nie potrafi odróżnić od losowych niezależnie od długości — jest to operacyjna definicja obliczeniowej nieodróżnialności. PractRand służy również do oceny źródeł entropii (testowania danych wyjściowych /dev/urandom i RDRAND) w celu wykrywania awarii sprzętu lub systematycznych obciążeń.

Cryptographic Algorithm Validation Program (CAVP) udostępnia oficjalne wektory testowe dla DRBG z SP 800-90A. Testowanie CAVP polega na przekazaniu implementacji do automatycznego systemu testowego NIST wraz z wektorami testów znanej odpowiedzi (KAT): dla określonych danych wejściowych entropii, nonce, ciągu personalizacji i additional_input implementacja musi wygenerować dokładnie oczekiwane bity danych wyjściowych. CAVP nie bada właściwości statystycznych — sprawdza poprawność algorytmiczną. Certyfikacja FIPS 140-3 wymaga walidacji CAVP dla wszystkich algorytmów kryptograficznych używanych w granicach modułu. Wektory testowe CAVP są publicznie dostępne na serwerze ACVP (Automated Crypto Validation Protocol) firmy NIST i są zintegrowane z zestawami testów OpenSSL, mbedTLS i BoringSSL.

Zanim DRBG będzie można bezpiecznie zainicjalizować, jego źródło entropii musi zostać zwalidowane. SP 800-90B definiuje: (1) oszacowanie entropii — pomiar rzeczywistej entropii na bit za pomocą testów statystycznych (oszacowanie min-entropii); (2) testy uruchomieniowe — sprawdzenie, czy źródło entropii generuje prawidłowe dane wyjściowe przed pierwszym użyciem; (3) testy na żądanie — opcjonalne testy uruchamiane przez aplikację; (4) testy poprawności źródła szumu — wykrywanie degradacji sprzętu. Typowe źródła entropii i ich szacowana entropia na bit: CPU RDRAND/RDSEED (~1 bit/bit, certyfikowane sprzętowo); /dev/urandom (łączy wiele źródeł, oszacowanie entropii jest zachowawcze); TRNG z oscylatorem pierścieniowym (0,5–0,9 bitu/bit zależnie od projektu); szum ADC (0,1–0,5 bitu/bit). Walidacja zgodnie z SP 800-90B wymaga badań laboratoryjnych z użyciem specjalistycznego sprzętu.

Środowiska wirtualne stwarzają specyficzne wyzwania związane z testowaniem RNG. Maszyny wirtualne mogą przy uruchamianiu mieć dostęp do niewielkiej ilości entropii (brak zdarzeń sprzętowych) lub po przywróceniu migawki (zresetowany stan). Kontenery Docker współdzielą RNG jądra hosta — kontener nie może bezpośrednio przetestować jakości źródłowej entropii. Testy dla wdrożeń na maszynach wirtualnych: (1) Należy zmierzyć czas do zakończenia odczytu z /dev/random — długie oczekiwanie wskazuje na niewystarczającą entropię. (2) Należy sprawdzić, czy identyfikatory UUID lub klucze generowane równolegle w instancjach maszyn wirtualnych nie są zduplikowane (jest to rzeczywisty tryb awarii udokumentowany we wdrożeniach chmurowych). (3) Należy sprawdzić, czy w maszynach wirtualnych załadowano VIRTIO-RNG (virtio_rng.ko) — zapewnia on wstrzykiwanie entropii z hosta do gościa. (4) Należy przeprowadzić audyt sekwencji uruchamiania aplikacji: czy generowanie kluczy odbywa się przed uzyskaniem wystarczającej entropii?

Testowanie bezpieczeństwa RNG względem forkowania zapobiega subtelnemu zagrożeniu: gdy proces wykonuje fork, proces nadrzędny i potomny współdzielą ten sam stan DRBG, przez co generują identyczne sekwencje. Wykrywanie: należy uruchomić N procesów potomnych, wygenerować w każdym identyfikator UUID i sprawdzić, czy wszystkie identyfikatory UUID są unikatowe. Jeśli dowolne dwa są takie same, RNG nie jest odporny na forkowanie. OpenSSL naprawił błąd związany z bezpieczeństwem względem forkowania w 2020 roku (CVE-2020-1971 nie dotyczył bezpośrednio DRBG, ale schemat był podobny). Obecny OpenSSL używa aktualizacji ziarna opartej na PID: jeśli PID zmienił się od ostatniego wywołania (co wskazuje na fork), DRBG automatycznie otrzymuje nowe ziarno. Testowanie tego mechanizmu polega na uruchomieniu testu przed i po wykonaniu fork oraz potwierdzeniu, że nastąpiło ponowne wygenerowanie ziarna przez sprawdzenie, czy wyniki są różne.

Praktyczna lista kontrolna audytu implementacji RNG: (1) Czy RNG jest inicjalizowany przez system operacyjny (getrandom, BCryptGenRandom), a nie za pomocą ziaren opartych na czasie? (2) Czy typ DRBG jest mechanizmem zatwierdzonym przez NIST SP 800-90A (Hash, HMAC, CTR)? (3) Czy długość ziarna jest wystarczająca dla deklarowanego poziomu bezpieczeństwa? (4) Czy ponowne generowanie ziarna jest uruchamiane okresowo lub po ustalonej liczbie wywołań generate? (5) Czy implementacja obsługuje bezpieczeństwo względem forkowania (ponowne generowanie ziarna po fork)? (6) Czy testy kondycji są włączone i czy w razie niepowodzenia zatrzymują system? (7) Czy stan jest zerowany podczas zamykania? (8) Czy wektory testowe CAVP są uruchamiane w CI/CD? (9) Czy oszacowania entropii są udokumentowane i zweryfikowane? (10) W przypadku wymagań FIPS: czy moduł ma certyfikat FIPS 140-3?

Historyczne awarie RNG pokazują, jak poważne mogą być ich konsekwencje. Debian OpenSSL (2006–2008): poprawka przypadkowo usunęła dwie linie kodu zbierającego entropię, ograniczając pulę ziaren do 15-bitowej przestrzeni PID — dla całej bazy użytkowników Debiana wygenerowano zaledwie 32 767 możliwych kluczy SSH. Wszystkie wygenerowane przez Debiana klucze hostów SSH i klucze użytkowników wymagały wymiany. Portfele Bitcoin na Androidzie (2013): SecureRandom systemu Android używał inicjalizacji na poziomie Javy, która na niektórych urządzeniach kończyła się niepowodzeniem, powodując duplikowanie wartości k w podpisach ECDSA — co bezpośrednio ujawniało klucze prywatne. Sony PS3 (2010): w oprogramowaniu układowym użyto stałej wartości nonce do podpisywania ECDSA, co umożliwiało wyodrębnienie klucza prywatnego na podstawie dwóch podpisów (ta sama wartość k dla różnych komunikatów ujawnia klucz za pomocą prostych przekształceń algebraicznych).

Który z poniższych testów wykrywa, że DRBG może generować zablokowane wyjście (wielokrotnie tę samą wartość)?

Testy statystyczne (NIST SP 800-22, TestU01 BigCrush, PractRand) weryfikują jakość wyników, ale nie mogą dowieść bezpieczeństwa kryptograficznego. Testy ze znaną odpowiedzią CAVP weryfikują poprawność algorytmiczną implementacji SP 800-90A. Testy źródeł entropii SP 800-90B (szacowanie min-entropii, testy kondycji) sprawdzają dane wejściowe ziarna. Ciągły test RNG (CRNGT) wykrywa zablokowanie wyjścia w czasie rzeczywistym. Wdrożenia na maszynach wirtualnych i w kontenerach wymagają wstrzykiwania entropii (VIRTIO-RNG) oraz kontroli entropii podczas uruchamiania. Testowanie bezpieczeństwa względem forkowania pozwala sprawdzić, czy procesy potomne nie dziedziczą stanu DRBG procesu nadrzędnego. Awarie z rzeczywistych wdrożeń (Debian, Android) pokazują, że błędy RNG prowadzą bezpośrednio do przejęcia kluczy kryptograficznych. Listy kontrolne audytu formalizują te kontrole na potrzeby wdrożeń produkcyjnych.