Informatyka i programowanieKryptografia i bezpieczeństwo komputerowe

Mersenne Twister ma olbrzymi okres i świetne statystyki — a do kryptografii się nie nadaje

Generator Mersenne Twister jest ceniony w symulacjach: jest szybki, dobrze przebadany i ma astronomicznie długi okres 2^19937−1. Dokumentacja Pythona jednocześnie ostrzega wprost, że jest całkowicie nieodpowiedni do celów kryptograficznych. Nie ma tu sprzeczności. Testy statystyczne i długi okres odpowiadają na pytanie, czy sekwencja dobrze zachowuje się jako dane pseudolosowe do obliczeń. Bezpieczeństwo wymaga czegoś więcej: obserwowane wyjścia nie powinny pozwalać przewidzieć kolejnych ani odzyskać stanu. Generator deterministyczny może wyglądać „bardzo losowo”, a jednocześnie być przewidywalny dla przeciwnika znającego jego konstrukcję.

Długi okres nie jest tym samym co nieprzewidywalność

Okres mówi, po ilu krokach generator może zacząć powtarzać cały cykl. W Mersenne Twisterze liczba ta jest niewyobrażalnie duża, więc w normalnej symulacji nie grozi nam przejście całej sekwencji. Napastnik nie musi jednak czekać na powtórzenie. Interesuje go stan wewnętrzny. Jeśli struktura generatora umożliwia odtworzenie tego stanu z wystarczającej liczby obserwacji, kolejne wyniki stają się obliczalne mimo gigantycznego okresu.

Symulacja i bezpieczeństwo mają inne kryteria jakości

W Monte Carlo chcemy m.in. dobrego rozkładu, braku prostych korelacji i szybkości. Jeśli ktoś zna seed eksperymentu, może nawet pożądać dokładnej powtarzalności wyników. W kryptografii odtwarzalność przez osobę trzecią jest katastrofą: token resetu hasła, klucz sesyjny czy identyfikator uwierzytelniający nie może być przewidywalny na podstawie wcześniejszych wartości. Ten sam generator może więc być znakomitym narzędziem naukowym i fatalnym narzędziem bezpieczeństwa.

Dokumentacja Pythona rozdziela oba zastosowania

Moduł random używa Mersenne Twistera i opisuje go jako jeden z najdokładniej testowanych generatorów. W tym samym miejscu dokumentacja zaznacza, że z powodu deterministycznego charakteru nie nadaje się do wszystkich zastosowań i jest całkowicie nieodpowiedni kryptograficznie. Python dostarcza osobny moduł secrets oraz SystemRandom wykorzystujący źródła systemowe przeznaczone do zastosowań wymagających silniejszej nieprzewidywalności.

To błąd klasy „narzędzie działa dokładnie zgodnie ze specyfikacją”

Jeśli programista użyje zwykłego generatora do stworzenia np. tokenu bezpieczeństwa, kod może przejść wszystkie proste testy. Wartości będą się zmieniały, wyglądały chaotycznie i nie będą się często powtarzały. Błąd ujawnia się dopiero w modelu przeciwnika: ktoś może obserwować wyniki, znać algorytm, zgadywać seed albo odtwarzać stan. To szczególnie zdradliwa klasa problemów, bo nie powoduje awarii funkcjonalnej — system działa, tylko sekret przestaje być sekretem.

„Losowe” ma co najmniej dwa różne znaczenia

Dane mogą być statystycznie podobne do losowych, a jednak przewidywalne dla kogoś znającego stan. Kryptografia wymaga computational unpredictability, nie tylko ładnego histogramu. Dlatego ocena generatora bezpieczeństwa nie może kończyć się na testach rozkładu i długości okresu. Potrzebna jest konstrukcja zaprojektowana przeciw przeciwnikowi, odpowiednia entropia wejściowa i właściwe zarządzanie stanem. Mersenne Twister jest świetnym przykładem, bo właśnie jego wysoka jakość w jednej dziedzinie może uśpić czujność w drugiej.

Przewidywalność to zupełnie inny test niż „czy histogram wygląda losowo”

Generator do symulacji może przejść wymagające testy statystyczne i mieć olbrzymi okres, a mimo to po obserwacji wystarczającej części wyjścia ujawniać stan pozwalający przewidywać kolejne wartości. Dla Monte Carlo taka właściwość bywa nieistotna, a deterministyczność wręcz ułatwia reprodukcję eksperymentu. Dla tokenu resetowania hasła, klucza sesyjnego czy sekretnego nonce'a jest niedopuszczalna, bo przeciwnik aktywnie próbuje przewidzieć następny wynik. Dokumentacja Pythona dlatego bardzo wyraźnie oddziela moduł `random`, oparty na Mersenne Twisterze, od modułu `secrets`, który korzysta ze źródeł odpowiednich do kryptografii. Nie chodzi o to, że Mersenne Twister produkuje „mało losowe” liczby — produkuje liczby nieprzeznaczone do środowiska z przeciwnikiem.

Reprodukowalność, która jest zaletą w nauce, staje się wadą przy sekretach

W symulacji badacz często chce uruchomić dokładnie ten sam eksperyment po raz drugi. Jawny seed Mersenne Twistera pozwala otrzymać tę samą sekwencję i znaleźć błąd albo porównać wyniki algorytmów. Token bezpieczeństwa ma odwrotne wymaganie: nawet jeśli przeciwnik zna kod, widział wcześniejsze wartości i potrafi wywoływać generator, kolejne wyniki powinny pozostać nieprzewidywalne. Dlatego jedno API `random` nie powinno być automatycznie używane do obu zadań. Python rozdziela te zastosowania także na poziomie bibliotek: `random` służy modelowaniu i symulacji, a `secrets` dobiera źródło odpowiednie do generowania haseł, tokenów i innych sekretów. To przykład, jak ta sama techniczna cecha może być atutem albo luką zależnie od modelu zagrożeń.

#CSPRNG#losowość#Mersenne Twister#PRNG#Python
Źródła i weryfikacja
Otrzymuj codzienne losowe ciekawostki