Maszyna, która nie umie zgadywać
Komputer jest z natury przewidywalny. Ten sam program z tymi samymi danymi zawsze da ten sam wynik. Żeby cokolwiek wylosować, komputer potrzebuje czegoś z zewnątrz: zjawisk fizycznych, których nie da się przewidzieć.
Tę nieprzewidywalność nazywamy entropią i mierzymy w bitach. Uczciwy rzut monetą to 1 bit, bo ma dwa równie prawdopodobne wyniki. Każdy kolejny bit podwaja liczbę możliwości. Weźmy klucz kryptograficzny, czyli tajny ciąg bitów używany na przykład do szyfrowania. Jeśli ma 256 bitów, może przyjąć 2²⁵⁶ równie prawdopodobnych wartości. W zwykłym zapisie ta liczba ma 78 cyfr.
Skąd komputer bierze entropię? Źródłem są między innymi dokładne czasy przerwań sprzętowych, czyli sygnałów, którymi urządzenia dają znać procesorowi o nowym zdarzeniu. Do tego dochodzą szum urządzeń, sprzętowe generatory losowości wbudowane w procesory i ruchy użytkownika. System operacyjny zbiera te okruchy w jednym miejscu, nazywanym pulą. Potem miesza je funkcjami kryptograficznymi i przekazuje generatorowi, z którego korzystają programy, także przeglądarka. Cała droga wygląda tak:
- Źródła entropiiCzasy zdarzeń, szum sprzętu, generator w procesorze, ruchy myszy
- PulaSystem zbiera surowe, nierówne bity
- MieszanieFunkcje kryptograficzne wygładzają je w ziarno
- CSPRNGGenerator rozciąga ziarno na dowolnie wiele bitów
- Twoje losowaniecrypto.getRandomValues w przeglądarce
Entropia z Twoich ruchów
Jedno z tych źródeł możesz obejrzeć z bliska, bo jest nim Twoja ręka. Ruchu ręki nie da się powtórzyć co do piksela i milisekundy. Wykorzystuje to generator haseł w naszym serwisie. Przy każdym ruchu myszy program odczytuje, o ile przesunął się kursor w poziomie i w pionie oraz ile czasu minęło od poprzedniego ruchu. Z każdej z tych trzech liczb bierze dwa najniższe bity, czyli dwie ostatnie cyfry w zapisie dwójkowym. Te końcówki zależą od drobnych drgnięć, nad którymi nikt nie panuje.
Daje to sześć bitów na ruch, ale ile jest w nich prawdziwej nieprzewidywalności, to tylko szacunek, a nie pomiar. Dlatego generator nie polega na samych ruchach. Łączy zebrane z nich dane z liczbami z generatora przeglądarki i z rundą drand, czyli losową wartością, którą publiczna sieć drand ogłasza co kilka sekund.
W surowych bitach zera i jedynki układają się też nierówno: ruch po prostej daje inne wzory niż kreślenie kółek. Dlatego program przepuszcza zebraną pulę przez funkcję skrótu SHA-256. Taka funkcja przerabia dowolne dane na krótki ciąg, który wygląda na losowy, więc nierówności znikają. Więcej o niej piszemy w artykule o funkcji skrótu i efekcie lawiny. Poruszaj myszą albo palcem nad polem poniżej i zobacz to sam:
Złap trochę entropii
Poruszaj tu myszą albo palcem
Surowe bity z ruchu
Jedynki: –
Po SHA-256
Jedynki: –
Generatory pseudolosowe: wzór udający przypadek
Entropii jest jednak mało i gromadzi się ją powoli, a programy potrzebują milionów losowych liczb. Dlatego używa się generatorów pseudolosowych (w skrócie PRNG). To algorytmy, które z krótkiej wartości startowej, nazywanej ziarnem, wyliczają długi ciąg liczb wyglądających na losowe. Z tego samego ziarna zawsze wychodzi ten sam ciąg. W symulacjach i grach to zaleta, bo wynik da się powtórzyć. Bywa to jednak także słabością.
Najstarszy i najprostszy jest generator liniowy kongruencyjny (LCG). Każdą kolejną liczbę wylicza z poprzedniej, oznaczonej x. Mnoży ją przez stałą a, dodaje stałą c i zostawia resztę z dzielenia przez stałą m: (a · x + c) mod m. Jego wady widać gołym okiem:
- Najniższe bity się powtarzają. Gdy m jest potęgą dwójki, najniższy bit na zmianę wynosi 0 i 1. Dwa najniższe bity powtarzają się co 4 liczby i tak dalej. Dlatego funkcja
rand(), którą norma języka C podaje jako przykład, zwraca tylko wyższe bity wyliczonej liczby, a dolne 16 odrzuca. - Kolejne liczby leżą na prostych. Jeśli zaznaczyć na wykresie pary kolejnych wyników, ułożą się na kilku równoległych liniach. Gdy zamiast par weźmiemy trójki kolejnych wyników i zaznaczymy je w przestrzeni, punkty ułożą się na płaszczyznach. George Marsaglia opisał to w 1968 roku w pracy o wymownym tytule „Random numbers fall mainly in the planes”, czyli „Liczby losowe padają głównie na płaszczyzny”.
Porównaj na obrazku liczby z takiego generatora z liczbami z generatora kryptograficznego:
Generator pod lupą
Bity 0–1 kolejnych liczb. Powtarzają się co 4 liczby, stąd pasy.
Te same bity z crypto.getRandomValues: bez wzoru.
Które bity pokazać0–1
Współczesne generatory, takie jak te stojące za Math.random() w przeglądarkach, są statystycznie dużo lepsze. Na takich obrazkach nie pokazałyby wzoru. Nadal jednak nie są bezpieczne w sensie kryptograficznym. Kto zna kilka kolejnych wyników, może odtworzyć stan generatora, czyli liczby, które generator trzyma w pamięci, i przewidzieć następne wyniki. W grze to bez znaczenia. Przy haśle albo losowaniu nagród taki generator się nie nadaje.
Stary generator potrafi też zostawić bardzo wyraźne ślady. Pokazuje to historia krzywych eliptycznych NIST, czyli wzorów używanych w kryptografii, które zatwierdził amerykański instytut normalizacyjny NIST. Ich parametry wyliczono z ziaren. Badacze rozpoznali w tych ziarnach charakterystyczny ślad generatora lrand48. Potem odtworzyli je, uruchamiając ten generator z datą z 1997 roku. Całą historię opisujemy w artykule o zagadce krzywych NIST.
CSPRNG: generator, którego nie da się przewidzieć
Na szczęście istnieją generatory, których nie da się w ten sposób przewidzieć. Kryptograficznie bezpieczny generator pseudolosowy, w skrócie CSPRNG, też rozciąga ziarno na długi ciąg. Daje jednak gwarancję, której zwykłe PRNG nie dają. Nawet ktoś, kto zna dowolnie wiele wcześniejszych wyników, nie przewidzi następnego lepiej, niż gdyby zgadywał. Do tego system regularnie zasila taki generator świeżą entropią.
W przeglądarce taki generator jest dostępny przez funkcję crypto.getRandomValues. Korzystają z niej wszystkie narzędzia losowaliczba.pl, od generatora liczb po generator haseł. W narzędziach z trybem weryfikowalnym możesz też losować z publicznej losowości sieci drand, którą każdy może sprawdzić.
Losowe hasło z generatora to jedno, a hasła wymyślane przez ludzi pod dyktando reguł to drugie. Dlaczego NIST zakazuje wymogu znaku specjalnego i okresowej zmiany hasła, pokazujemy w artykule o polityce haseł według NIST.