Prawdziwa losowość a pseudolosowość

Bezpieczeństwo kryptograficzne zależy przede wszystkim od nieprzewidywalności. Jeśli atakujący może przewidzieć Twój klucz, IV lub nonce — nawet częściowo — cały system kryptograficzny może się załamać. Słaba losowość doprowadziła do katastrofalnych przełamań zabezpieczeń w rzeczywistych systemach.

TRNG czerpią entropię fizyczną: szum termiczny w rezystorach, szum śrutowy w diodach spolaryzowanych zaporowo, rozpad promieniotwórczy, ruchy myszy, czasy naciskania klawiszy i opóźnienia wyszukiwania dysku. Są to rzeczywiście nieprzewidywalne zjawiska fizyczne.

System operacyjny utrzymuje pulę entropii — zbiór próbek fizycznego szumu, które są łączone operacją XOR i haszowane. Linux: /dev/random i /dev/urandom pobierają dane z tej puli. Pula jest stale uzupełniana podczas działania systemu.

PRNG (nazywany również deterministycznym generatorem liczb losowych / DRNG) rozwija krótkie ziarno do długiego strumienia pseudolosowych bajtów za pomocą deterministycznego algorytmu. Dla tego samego ziarna generuje ten sam wynik. Nie nadaje się do kryptografii, chyba że został zainicjalizowany prawdziwą entropią.

PRNG może wykazywać wykrywalne obciążenie statystyczne lub być przewidywalny na podstawie zaobserwowanych danych wyjściowych. Kryptograficznie bezpieczny PRNG (CSPRNG) zapewnia dodatkowo: (1) bezpieczeństwo w przód (nie można przewidzieć wcześniejszych danych wyjściowych na podstawie bieżącego stanu) oraz (2) odporność na odtwarzanie wstecz (nie można przewidzieć przyszłych danych wyjściowych na podstawie wcześniejszych).

PRNG jest kryptograficznie bezpieczny, jeśli żaden algorytm działający w czasie wielomianowym nie potrafi odróżnić jego wyników od prawdziwie losowej sekwencji z prawdopodobieństwem istotnie większym niż 1/2. Jest to kryterium nieprzewidywalności następnego bitu.

Linux: /dev/urandom (nieblokujący po początkowym zainicjalizowaniu), wywołanie systemowe getrandom(). Windows: CryptGenRandom(), BCryptGenRandom(). macOS/iOS: SecRandomCopyBytes(). Przeglądarka: window.crypto.getRandomValues(). Wszystkie zasilają pulę entropii systemu operacyjnego.

NIST SP 800-22 udostępnia 15 testów statystycznych losowości: częstości, częstości bloków, serii, uniwersalny Maurera, złożoności liniowej itd. Przejście testów statystycznych nie dowodzi bezpieczeństwa kryptograficznego — wskazuje jedynie na brak oczywistego obciążenia.

CSPRNG zainicjalizowany słabą entropią (np. bieżącym czasem w sekundach) jest przewidywalny. Atakujący, który zna ziarno, może odtworzyć cały wynik. Zawsze inicjalizuj generator na podstawie entropii systemu operacyjnego: os.urandom(32) w Pythonie, a nie time.time() ani random.random().

Intel RDRAND (instrukcja x86) zwraca wygenerowane sprzętowo losowe bajty z TRNG znajdującego się w układzie. Odpowiedni sprzęt istnieje również dla AMD i ARM. Linux łączy dane RDRAND z /dev/urandom. Jest używany jako dodatkowe źródło entropii, a nie jedyne źródło (ze względu na kwestie zaufania).

QRNG wykorzystują zjawiska mechaniki kwantowej (czasy nadejścia fotonów, fluktuacje próżni) do generowania wyników o dowiedzionej losowości. Komercyjne QRNG (ID Quantique, Quantis) są używane w zastosowaniach o wysokich wymaganiach bezpieczeństwa. Ich koszt uniemożliwia powszechne zastosowanie.

Jaka właściwość odróżnia CSPRNG od zwykłego PRNG?

TRNG czerpią entropię fizyczną, PRNG deterministycznie rozwijają ziarno, a CSPRNG są nierozróżnialne od prawdziwej losowości. Pule entropii systemu operacyjnego łączą oba źródła. Dalej: konkretne konstrukcje CSPRNG stosowane w praktyce.