W jaki sposób system operacyjny tworzy entropię dla losowych nasion?

W systemie Linux pliki /dev/randomi/dev/urandom pliki są (odpowiednio) blokującymi i nieblokującymi źródłami pseudolosowych bajtów.

Można je odczytać jako normalne pliki:

$ hexdump /dev/random
0000000 28eb d9e7 44bb 1ac9 d06f b943 f904 8ffa
0000010 5652 1f08 ccb8 9ee2 d85c 7c6b ddb2 bcbe
0000020 f841 bd90 9e7c 5be2 eecc e395 5971 ab7f
0000030 864f d402 74dd 1aa8 925d 8a80 de75 a0e3
0000040 cb64 4422 02f7 0c50 6174 f725 0653 2444
...

Wiele innych wariantów uniksowych zapewnia /dev/randomi /dev/urandomrównież bez rozróżnienia blokującego / nieblokującego.

Odpowiednikiem systemu Windows jest CryptGenRandom()funkcja .

W jaki sposób system operacyjny generuje pseudolosowość?

Tytuł i ciało swoje pytanie zadać dwa różne pytania: w jaki sposób system operacyjny tworzy entropia (powinno to być naprawdę uzyskiwanych przez entropia), i jak to generuje pseudo-losowość z tego entropii. Zacznę od wyjaśnienia różnicy.

Skąd pochodzi losowość?

Generatory liczb losowych (RNG) występują w dwóch typach:

• Generatory liczb pseudolosowych (PRNG), zwane także deterministycznymi generatorami losowych bitów (DRBG) lub ich kombinacje, są algorytmami deterministycznymi, które utrzymują stan wewnętrzny zmiennej zmiennej wielkości i obliczają swoje wyjście z tego stanu.
• Sprzętowy generator liczb losowych (HRNG), zwany także „prawdziwymi” generatorami liczb losowych, oparty jest na zjawiskach fizycznych. „Prawda” jest trochę mylącym, ponieważ nie ma źródeł informacji, które są naprawdę przypadkowe , tylko źródła informacji, o których nie wiadomo, że są przewidywalne.

Niektóre zastosowania, takie jak symulacje zjawisk fizycznych, mogą być zadowolone z liczb losowych, które przejdą testy statystyczne. Inne aplikacje, takie jak generowanie kluczy kryptograficznych, wymagają silniejszej właściwości: nieprzewidywalności . Nieprzewidywalność to właściwość bezpieczeństwa, a nie (tylko) właściwość statystyczna: oznacza to, że przeciwnik nie może odgadnąć wyniku generatora liczb losowych. (Dokładniej, możesz zmierzyć jakość RNG, mierząc prawdopodobieństwo, że przeciwnik zgadnie każdy bit wyniku RNG. Jeśli prawdopodobieństwo jest mierzalnie różne od 1/2, RNG jest złe.)

Istnieją zjawiska fizyczne, które generują losowe dane o dobrych właściwościach statystycznych - na przykład rozpad radioaktywny lub niektóre astronomiczne obserwacje hałasu w tle lub wahania na giełdzie. Takie pomiary fizyczne wymagają warunkowania ( wybielania ), aby przekształcić tendencyjne rozkłady prawdopodobieństwa w jednolity rozkład prawdopodobieństwa. Fizyczny pomiar, który jest znany wszystkim, nie jest dobry dla kryptografii: wahania na giełdzie mogą być dobre dla geohashingu , ale nie można ich używać do generowania tajnych kluczy .

Kryptografia wymaga zachowania tajemnicy : przeciwnik nie może być w stanie znaleźć danych, które uległy uwarunkowaniu. Istnieją kryptograficznie bezpieczne generatory liczb pseudolosowych (CSPRNG): algorytmy PRNG, których dane wyjściowe nadają się do zastosowania w aplikacjach kryptograficznych, oprócz dobrych właściwości statystycznych . Jedną z właściwości, które sprawiają, że CSPRNG jest kryptograficznie bezpieczny, jest to, że jego dane wyjściowe nie pozwalają przeciwnikowi zrekonstruować stanu wewnętrznego (znajomość wszystkich bitów, ale jedna wygenerowana przez CSPRNG, nie pomaga znaleźć brakującego bitu). Nie będę się zastanawiać, jak zrobić CSPRNG, ponieważ to jest łatwe - możesz postępować zgodnie z przepisami podanymi przez profesjonalnych kryptografów (użyj standardowegoalgorytm, taki jak Hash_DRBG, HMAC_DRBG lub CTR_DRBG z NIST SP 800-90A ) lub ANSI X9.31 PRNG . CSPRNG wymaga dwóch właściwości swojego stanu w celu zapewnienia bezpieczeństwa:

• Stan musi być utrzymywany w tajemnicy od samego początku i przez cały czas (chociaż ujawnienie stanu nie ujawni wyników z przeszłości).
• Stan musi być liniowy: RNG nigdy nie może zostać uruchomiony dwukrotnie z tego samego stanu.

Architektura generatora liczb losowych

W praktyce prawie wszystkie dobre generatory liczb losowych łączą CSPRNG z co najmniej jednym źródłem entropii . Mówiąc krótko, entropia jest miarą nieprzewidywalności źródła danych. Oparcie generatora liczb losowych wyłącznie na sprzętowym RNG jest trudne:

• Surowe dane fizyczne i tak prawdopodobnie będą wymagać warunkowania, aby przekształcić dane probabilistyczne w jednolity rozkład.
• Dane wyjściowe ze źródła losowości muszą być utrzymywane w tajemnicy.
• Źródła entropii są często powolne w porównaniu z zapotrzebowaniem.

Dlatego RNG w systemie operacyjnym prawie zawsze działa w następujący sposób :

1. Zbierz wystarczającą entropię, aby zbudować nieprzewidywalny stan wewnętrzny.
2. Uruchom CSPRNG , używając nagromadzonej entropii jako materiału siewnego, tj. Jako początkowej wartości stanu wewnętrznego.
3. Opcjonalnie okresowo mieszaj dodatkową entropię ze stanem wewnętrznym. (Nie jest to absolutnie konieczne, ponieważ entropia nie jest „zużywana” w żadnym mierzalnym tempie . Pomaga w zwalczaniu niektórych zagrożeń, które przeciekają stan RNG bez narażania całego systemu).

Usługa generowania liczb losowych jest częścią zadania systemu operacyjnego, ponieważ gromadzenie entropii wymaga dostępu do sprzętu, a źródła entropii stanowią współdzielony zasób: system operacyjny musi je gromadzić i uzyskiwać z nich dane wyjściowe odpowiednie dla aplikacji. W systemie operacyjnym wymagane jest pseudolosowe warunkowanie źródeł entropii; równie dobrze może być kryptograficznie bezpieczny, ponieważ nie jest to zasadniczo trudniejsze (i jest wymagane w systemach operacyjnych, w których aplikacje nie ufają sobie nawzajem; w systemach w pełni współpracujących każda aplikacja musiałaby uruchomić wewnętrznie własny CSPRNG, jeśli system operacyjny i tak nie podał).

Większość systemów z trwałym magazynem ładuje ziarno RNG z dysku (użyję „dysku” jako skrótu dla dowolnego rodzaju trwałego magazynu) podczas uruchamiania i zastępują ziarno niektórymi świeżymi pseudolosowymi danymi wygenerowanymi z tego ziarna, lub jeśli są dostępne z losowymi danymi wygenerowanymi z tego ziarna plus inne źródło entropii. W ten sposób, nawet jeśli entropia nie jest dostępna po ponownym uruchomieniu, entropia z poprzedniej sesji jest ponownie używana.

Należy zachować ostrożność w przypadku zapisanego stanu. Pamiętasz, jak powiedziałem, że stan musi być liniowy? Jeśli uruchomisz dwa razy z tego samego stanu dysku, otrzymasz te same wyjścia RNG. Jeśli jest to możliwe w twoim środowisku, potrzebujesz innego źródła entropii. Zachowaj ostrożność podczas przywracania kopii zapasowych lub klonowania maszyny wirtualnej . Jedną z technik klonowania jest mieszanie przechowywanej entropii z pewnymi danymi środowiskowymi, które są przewidywalne, ale unikalne (np. Czas i adres MAC); Uwaga: jeśli dane środowiskowe są przewidywalne, każdy, kto posiada zapisany stan maszyny wirtualnej, może zrekonstruować ziarno rozwidlonej instancji maszyny wirtualnej.

Źródła Entropii

Znalezienie (i prawidłowe użycie) źródeł entropii jest najtrudniejszą częścią generowania liczb losowych w systemie operacyjnym. Dostępne źródła entropii będą koniecznie zależeć od sprzętu i środowiska, w którym działa.

Jeśli masz szczęście, twój sprzęt zapewnia urządzenie peryferyjne, które może być użyte jako źródło entropii: sprzętowy generator liczb losowych , dedykowany lub poboczny. Na przykład:

• hałas termiczny
• hałas lawinowy z szumu lawinowego
• różne typy (kombinacje) oscylatorów , takie jak oscylatory pierścieniowe
• rozpad radioaktywny
• różne zjawiska kwantowe , których nie potrafiłem wyjaśnić
• hałas akustyczny
• szum aparatu

NIST SP800-90B zawiera wytyczne dotyczące projektowania sprzętowego RNG. Ocena sprzętowego RNG jest trudna . Sprzętowe RNG to zazwyczaj delikatne bestie, które należy stosować ostrożnie: wiele typów wymaga pewnego czasu po rozruchu i pewnego czasu między odczytami w celu destabilizacji, często są wrażliwe na warunki otoczenia, takie jak temperatura itp.

Procesory Intel x86-64 oparte na architekturze Ivy Bridge dostarczają RdRandinstrukcję, która dostarcza dane wyjściowe z CSPRNG zaszczepionego przez szum termiczny . Większość procesorów do smartfonów zawiera sprzętowe źródło entropii, chociaż Android nie zawsze go używa.

Systemy, które nie mają silnego źródła entropii, muszą zadowolić się łączeniem słabych źródeł entropii i mieć nadzieję ( upewniając się, że byłoby to zbyt mocne słowo), że będą wystarczające. Losowe ruchy myszą są popularne na komputerach klienckich, a niektóre programy kryptograficzne, które proszą o poruszenie myszą , mogły zobaczyć program bezpieczeństwa (nawet jeśli w dowolnym systemie operacyjnym na komputery PC w XXI wieku system operacyjny zgromadził entropię bez konieczności zawracania głowy aplikacją ).

Jeśli chcesz spojrzeć na przykład, możesz spojrzeć na Linuksa, choć strzeż się, że nie jest idealny . W szczególności /dev/randomzbyt często blokuje (ponieważ blokuje, dopóki dostępna jest wystarczająca ilość entropii, z nadmiernie konserwatywnym pojęciem entropii), podczas gdy /dev/urandomprawie zawsze jest dobra, z wyjątkiem pierwszego rozruchu, ale nie daje żadnych wskazówek, gdy nie ma wystarczającej entropii. Linux ma sterowniki dla wielu urządzeń HRNG i akumuluje entropię z różnych urządzeń (w tym urządzeń wejściowych ) i taktowania dysku .

Jeśli masz (poufne) trwałe miejsce do przechowywania, możesz go użyć do zapisania entropii od jednego rozruchu do drugiego, jak wskazano powyżej. Pierwszym rozruchu jest delikatna czas: system może być w stanie dość przewidywalny w tym momencie, zwłaszcza w urządzeniach produkowanych seryjnie, które zasadniczo działają z fabryki w taki sam sposób. Niektóre urządzenia wbudowane, które mają trwałą pamięć masową, są fabrycznie zaopatrywane w początkowy seed (produkowany przez RNG działający na komputerze w fabryce). W zwirtualizowanych środowiskach serwerowych początkową entropię można zapewnić podczas tworzenia maszyny wirtualnej z hosta lub z serwera entropii.

Źle rozstawione urządzenia są powszechnym problemem w praktyce - badanie publicznych kluczy RSA wykazało, że wiele serwerów i urządzeń miało klucze wygenerowane przy złym RNG, najprawdopodobniej dobrym PRNG, który nie był wystarczająco rozstawiony. Jako projektant systemu operacyjnego nie możesz rozwiązać tego problemu na własną rękę: zadaniem jednostki kontrolującej łańcuch wdrażania jest zapewnienie, że RNG zostanie poprawnie zaszczepiony przy pierwszym uruchomieniu. Twoim zadaniem jako projektanta systemu operacyjnego jest zapewnienie właściwego RNG, w tym interfejsu zapewniającego ten pierwszy seed, oraz zapewnienie właściwej sygnalizacji błędu, jeśli RNG zostanie użyty przed jego prawidłowym uruchomieniem.

Oprócz odpowiedzi Gillesa, można również użyć przerwań do ustanowienia entropii. Na przykład w Linuksie, dodając moduł obsługi przerwań, można określić, czy wystąpienie tego przerwania powinno być wykorzystane jako wkład do puli entropii jądra.

Oczywiście nigdy nie powinno tak być w przypadku przerwań, które atakujący mógłby określić. Na przykład na pierwszy rzut oka ruch sieciowy (tj. Wynikające z niego przerwania) wydaje się dobrym źródłem losowości. Jednak osoba atakująca może być w stanie manipulować ruchem w taki sposób, aby mógł przewidzieć losowość potrzebną do wykonania operacji.