Kryptograficzny generator losowy może być deterministyczny
Słowo „deterministyczny” brzmi jak przeciwieństwo bezpiecznej losowości, a jednak współczesne systemy kryptograficzne powszechnie używają DRBG — deterministic random bit generators. Taki generator po zainicjalizowaniu stanem zawierającym odpowiednią entropię rozwija go algorytmicznie w długi strumień pseudolosowych bitów. Jeśli algorytm jest dobrze zaprojektowany, stan pozostaje tajny, a ziarno miało wystarczającą entropię, wynik ma być nieprzewidywalny dla napastnika mimo całkowicie deterministycznych reguł generacji. NIST standaryzuje właśnie takie konstrukcje. Krytyczne pytanie nie brzmi więc „czy komputer wykonuje deterministyczny algorytm?”, lecz „skąd wziął nieprzewidywalny stan i czy przeciwnik może go odtworzyć?”.
Komputer może generować „losowość” przez dokładnie określony algorytm
NIST SP 800-90A opisuje mechanizmy DRBG oparte m.in. na funkcjach skrótu i szyfrach blokowych. Po inicjalizacji generator ma wewnętrzny stan, a kolejne wywołania przekształcają go według deterministycznych reguł. Gdyby znać pełny stan i algorytm, wyniki można byłoby odtworzyć. Bezpieczeństwo pochodzi z faktu, że stan jest zasilony entropią niedostępną przeciwnikowi, a konstrukcja kryptograficzna ma uniemożliwiać wywnioskowanie stanu z obserwowanych wyjść.
Entropia i generator pełnią inne role
Źródło entropii ma dostarczyć nieprzewidywalności pochodzącej z procesów, których napastnik nie zna dostatecznie dobrze. DRBG ma z tej ograniczonej porcji entropii wydajnie produkować wiele bitów nadających się do kluczy, nonce’ów i innych zastosowań. NIST rozdziela te zagadnienia w rodzinie SP 800-90: część A opisuje deterministyczne mechanizmy, część B źródła entropii, a część C sposoby łączenia ich w kompletne generatory. To rozdzielenie pokazuje, że „losowość systemu” jest architekturą, a nie pojedynczą funkcją.
Dobre ziarno jest ważniejsze niż niezwykle długi okres generatora
Generator może mieć astronomicznie długi okres, ale jeśli został uruchomiony z jednym z kilku łatwych do odgadnięcia seedów, jego przyszłe wyniki również pochodzą z małego zbioru możliwości. Dlatego inicjalizacja czasu systemowego, identyfikatora procesu czy kilku przewidywalnych parametrów może być fatalna dla kryptografii, nawet jeśli sam generator ma świetne statystyki. Bezpieczeństwo mierzy się nie liczbą możliwych stanów na papierze, lecz tym, ile nieprzewidywalności przeciwnik realnie musi pokonać.
DRBG może być okresowo ponownie zasilany
Standardowe konstrukcje przewidują reseeding — wprowadzenie świeżej entropii do stanu. Może to ograniczać skutki części kompromitacji i odświeżać bezpieczeństwo po wygenerowaniu dużej ilości danych. W zależności od projektu generator może również zapewniać własności takie jak odporność na odtworzenie dawnych wyjść po późniejszym poznaniu stanu. To kolejny powód, dla którego kryptograficzny RNG jest czymś więcej niż funkcją typu „daj mi następną liczbę”. Zarządza cyklem życia tajnego stanu.
To zmienia potoczną definicję „prawdziwie losowego” komputera
Nie trzeba wymagać, aby każdy bit klucza pochodził bezpośrednio z osobnego zjawiska fizycznego. W praktyce system zbiera ograniczoną ilość entropii, a następnie używa kryptograficznego generatora do jej bezpiecznego rozwinięcia. Determinizm nie jest więc automatycznie wadą. Wadą jest przewidywalność z perspektywy przeciwnika. Ta różnica tłumaczy, dlaczego zwykłe generatory do symulacji mogą być nieodpowiednie mimo dobrych testów statystycznych, a dobrze zaprojektowany DRBG może bezpiecznie produkować ogromne ilości pseudolosowych danych z krótkiego tajnego stanu.
Bezpieczeństwo DRBG obejmuje również pytanie, co stanie się po ujawnieniu jego stanu
NIST opisuje generatory deterministyczne nie tylko przez jakość statystyczną bitów, lecz także przez pojęcia związane z odpornością na kompromitację. Jeżeli przeciwnik pozna wewnętrzny stan generatora, ważne staje się, czy potrafi odtworzyć wcześniejsze wyjścia oraz jak szybko nowe, niezależne źródło entropii pozwoli odzyskać nieprzewidywalność przyszłych wyjść. Stąd mechanizmy reseeding i rozdzielenie procesu zbierania entropii od samego rozwijania jej w długi strumień. To pokazuje, że kryptograficzna losowość jest systemem, nie jedną funkcją `random()`: trzeba bezpiecznie pozyskać początkową entropię, przechowywać stan, kontrolować jego użycie i w odpowiednich momentach go odświeżać. Determinizm algorytmu nie przeszkadza, dopóki stan pozostaje poza zasięgiem przeciwnika.
Ten sam generator może być bezpieczny kryptograficznie i nadal całkowicie reprodukowalny w laboratorium
Deterministyczność sama w sobie oznacza tylko, że ten sam stan wejściowy prowadzi do tego samego wyjścia. W testach oprogramowania jest to zaleta: można zapisać seed i odtworzyć przebieg. W bezpieczeństwie różnica polega na tym, że seed oraz stan generatora muszą być pozyskane i chronione tak, aby przeciwnik ich nie znał ani nie mógł przewidzieć. Standardy NIST traktują DRBG jako komponent większej konstrukcji obejmującej źródła entropii i procedury inicjalizacji. Potoczna opozycja „pseudolosowe = złe, prawdziwie losowe = dobre” pomija więc sedno. Dobrze zaprojektowany system używa niewielkiej ilości nieprzewidywalnej entropii do zainicjowania deterministycznego mechanizmu, który następnie może szybko dostarczać ogromne ilości kryptograficznie nieprzewidywalnych bitów.