Niedobór entropii i błędy związane ze słabymi kluczami

Niedobór entropii występuje, gdy system nie ma wystarczającej ilości nieprzewidywalnych danych wejściowych do zainicjalizowania CSPRNG. Dzieje się tak w przypadku świeżo uruchomionych urządzeń wbudowanych, zwirtualizowanych serwerów lub systemów pozbawionych danych wprowadzanych przez użytkownika. Dane wyjściowe RNG stają się przewidywalne.

W 2006 roku programista Debiana usunął wiersz wskazany przez Valgrind: MD_Update(&m, buf, j). Wiersz ten był źródłem entropii. W rezultacie OpenSSL w Debianie inicjalizował się wyłącznie na podstawie PID (maksymalnie 32 768 wartości). Wszystkie klucze wygenerowane w latach 2006–2008 należą do zbioru obejmującego 32 768 możliwości.

Klucze RSA, DSA i ECDSA, klucze hostów SSH, certyfikaty TLS oraz klucze SSL VPN wygenerowane w systemach Debian/Ubuntu w latach 2006–2008 zostały zaatakowane. Dotyczyło to systemów Debian Etch, Debian Lenny oraz Ubuntu 7.04–8.04. Opublikowano czarne listy i unieważniono certyfikaty.

Maszyny wirtualne można klonować wraz z identycznym stanem dysku. Jeśli obie maszyny wygenerują klucze z tego samego stanu CSPRNG, utworzą identyczne klucze. Obecnie hipernadzorcy wstrzykują entropię za pomocą VirtIO RNG lub tabel ACPI, ale nieprawidłowo skonfigurowane maszyny wirtualne nadal są narażone na to ryzyko podczas uruchamiania.

Urządzenia IoT (routery, kamery) często generują klucze SSH/TLS przy pierwszym uruchomieniu, zanim zgromadzą wystarczającą entropię. Badania wykazały, że miliony urządzeń współdzieliły kilka tysięcy par kluczy RSA, ponieważ wszystkie inicjalizowały się na podstawie tego samego stanu uruchamiania o niskiej entropii.

Lenstra i in. (2012) zebrali 11,7 miliona certyfikatów TLS i obliczyli parami wartości GCD. Znaleziono 12 720 kluczy RSA współdzielących czynnik pierwszy — oznaczało to, że oba klucze można było w pełni rozłożyć na czynniki. Złamano 0,2% wszystkich kluczy publicznych. Przyczyną była niewystarczająca entropia podczas uruchamiania.

ECDSA wymaga unikatowego losowego nonce k dla każdego podpisu. Jeśli k zostanie użyte ponownie (lub będzie słabe), klucz prywatny można natychmiast odzyskać: d = (s1-s2)^{-1} * (z1-z2) * k / (r1-r2) mod n. W konsoli Sony PS3 używano k=constant — wszystkie gry można było podpisywać za pomocą odzyskanego klucza.

Java SecureRandom w systemie Android 4.x był w określonych warunkach inicjalizowany na podstawie czasu systemowego. Wiele aplikacji portfeli Bitcoin generowało podpisy z tym samym nonce k, ujawniając klucze prywatne. Skradziono miliony dolarów. Firma Google poprawiła implementację SecureRandom.

Narzędzia: ssh-vulnkey (sprawdza klucze względem czarnej listy słabych kluczy Debiana), badkeys (sprawdza certyfikaty TLS pod kątem znanych słabych liczb pierwszych), algorytm GCD-batch do masowego audytowania kluczy RSA. Dzienniki Certificate Transparency umożliwiają analizę na dużą skalę.

Przy pierwszym generowaniu klucza należy użyć getrandom(GRND_RANDOM). Po odczekaniu na początkową inicjalizację należy odczytywać dane z /dev/urandom (sprawdzając, czy /proc/sys/kernel/random/entropy_avail > 128). Należy używać sprzętowego RNG (RDRAND) jako dodatkowego źródła entropii. Nigdy nie należy generować kluczy przy pierwszym uruchomieniu bez opóźnienia.

Należy zachowywać stan CSPRNG między ponownymi uruchomieniami: podczas zamykania zapisać 32 bajty z /dev/urandom do pliku z ziarnem, a podczas uruchamiania odczytać je i ponownie przekazać do generatora. Zapewnia to ciągłość entropii między zimnymi uruchomieniami. Linux robi to automatycznie, ale systemy wbudowane często tego nie robią.

Jaka była główna przyczyna błędu entropii OpenSSL w Debianie?

Niedobór entropii powoduje powstawanie przewidywalnych kluczy. Rzeczywiste przełamania zabezpieczeń obejmowały: OpenSSL w Debianie (ziarno oparte wyłącznie na PID), ataki GCD na urządzenia IoT, ponowne użycie nonce w ECDSA na PS3 oraz portfele Bitcoin na Androidzie. Zawsze należy inicjalizować generator na podstawie entropii systemowej, a generowanie kluczy w systemach wbudowanych dokładnie audytować. Dalej: bezpieczne generowanie kluczy, nonce i IV.