Bezpieczny kryptograficznie generator liczb pseudolosowych — Cryptographically-secure pseudorandom number generator

Kryptograficznie bezpieczny generator liczb pseudolosowych ( CSPRNG ) lub numer pseudolosowych generator kryptograficzny ( CPRNG ) jest generator liczb pseudolosowych (PRNG) o właściwościach, które sprawiają, że nadaje się do zastosowania w kryptografii . Jest również powszechnie znany jako kryptograficzny generator liczb losowych ( CRNG ) (patrz Generowanie liczb losowych § „Prawda” a liczby pseudolosowe ).

Większość aplikacji kryptograficznych wymaga liczb losowych , na przykład:

„Jakość” losowości wymaganej dla tych aplikacji jest różna. Na przykład tworzenie nonce w niektórych protokołach wymaga tylko unikalności. Z drugiej strony generowanie klucza głównego wymaga wyższej jakości, takiej jak większa entropia . A w przypadku jednorazowych padów , informacja teoretyczna gwarancja doskonałej tajności obowiązuje tylko wtedy, gdy kluczowy materiał pochodzi z prawdziwie losowego źródła o wysokiej entropii, a zatem jakikolwiek generator liczb pseudolosowych jest niewystarczający.

Idealnie, generowanie liczb losowych w CSPRNG wykorzystuje entropię uzyskaną ze źródła wysokiej jakości, ogólnie z API losowości systemu operacyjnego. Jednak w kilku takich pozornie niezależnych procesach znaleziono nieoczekiwane korelacje. Z punktu widzenia teorii informacji, wielkość losowości, entropia, którą można wygenerować, jest równa entropii dostarczanej przez system. Ale czasami, w praktycznych sytuacjach, potrzeba więcej liczb losowych niż jest dostępna entropia. Ponadto procesy wydobywania losowości z działającego systemu są w praktyce powolne. W takich przypadkach czasami można użyć CSPRNG. CSPRNG może „rozciągnąć” dostępną entropię na więcej bitów.

Wymagania

Wymogi zwykłego PRNG spełnia również bezpieczny kryptograficznie PRNG, ale nie jest to prawdą. Wymagania CSPRNG dzielą się na dwie grupy: po pierwsze, że przechodzą statystyczne testy losowości ; a po drugie, że dobrze wytrzymują poważny atak, nawet jeśli część ich stanu początkowego lub działania stanie się dostępna dla atakującego.

  • Każdy CSPRNG powinien przejść test następnego bitu . Oznacza to, że biorąc pod uwagę pierwsze k bitów losowej sekwencji, nie ma algorytmu wielomianowego , który mógłby przewidzieć ( k +1)-ty bit z prawdopodobieństwem powodzenia znacznie większym niż 50%. Andrew Yao udowodnił w 1982 roku, że generator, który przejdzie test następnego bitu, przejdzie wszystkie inne statystyczne testy losowości w czasie wielomianowym.
  • Każdy CSPRNG powinien wytrzymać „stanowe rozszerzenia kompromisu”. W przypadku ujawnienia (lub poprawnego odgadnięcia) części lub całości jego stanu, odtworzenie strumienia liczb losowych sprzed objawienia powinno być niemożliwe. Dodatkowo, jeśli istnieje wejście entropii podczas działania, nie powinno być możliwe wykorzystanie wiedzy o stanie wejścia do przewidywania przyszłych warunków stanu CSPRNG.
Przykład: Jeśli rozważany CSPRNG generuje dane wyjściowe, obliczając bity π w sekwencji, zaczynając od jakiegoś nieznanego punktu w rozwinięciu binarnym, może on również spełnić test następnego bitu, a zatem być statystycznie losowy, ponieważ π wydaje się być sekwencją losową . (Byłoby to gwarantowane, jeśli na przykład π jest liczbą normalną ). Jednak ten algorytm nie jest kryptograficznie bezpieczny; atakujący, który określi, który bit pi (tzn. stan algorytmu) jest aktualnie używany, będzie mógł również obliczyć wszystkie poprzednie bity.

Większość PRNG nie nadaje się do użycia jako CSPRNG i zawiedzie w obu przypadkach. Po pierwsze, podczas gdy większość wyników PRNG wydaje się losowa w różnych testach statystycznych, nie są one odporne na zdeterminowaną inżynierię odwrotną. Specjalistyczne testy statystyczne można znaleźć specjalnie dostrojone do takiego PRNG, które pokazuje, że liczby losowe nie są naprawdę losowe. Po drugie, w przypadku większości PRNG, gdy ich stan zostanie ujawniony, wszystkie przeszłe liczby losowe mogą zostać zaktualizowane, umożliwiając atakującemu odczytanie wszystkich przeszłych wiadomości, a także przyszłych.

CSPRNG zostały zaprojektowane w taki sposób, aby opierały się tego typu kryptoanalizie .

Definicje

W ustawieniu asymptotycznym rodzina deterministycznych funkcji obliczalnych w czasie wielomianu dla pewnego wielomianu p jest generatorem liczb pseudolosowych ( PRNG lub PRG w niektórych odniesieniach ), jeśli rozciąga długość swojego wejścia ( dla dowolnego k ) i jeśli jego wyjście jest obliczeniowo nie do odróżnienia od prawdziwej losowości, tj. dla dowolnego algorytmu probabilistycznego czasu wielomianowego A , który wyprowadza 1 lub 0 jako rozróżnienie,

dla jakiejś nieistotnej funkcji . (Zapis oznacza, że x jest wybierane jednolicie losowo ze zbioru X .)

Jest odpowiednikiem Charakterystyka: Dla każdej rodziny funkcji , G jest PRNG wtedy i tylko wtedy, gdy następny bit wyjściowy G nie można przewidzieć za pomocą algorytmu czasie wielomianowym.

Naprzód-Secure PRNG z długością bloku jest PRNG , gdzie ciąg wejściowy o długości k jest obecny stan w okresie I i wyjście ( , ) składa się z następnego stanu i blokiem wyjściowym pseudolosowych okresu í , że wytrzymuje stan kompromisowe rozszerzenia w następującym sensie. Jeżeli stan początkowy jest wybierany jednostajnie losowo z , to dla dowolnego i , ciąg musi być obliczeniowo nie do odróżnienia od , w którym są wybierane jednostajnie losowo z .

Każdy PRNG można przekształcić w bezpieczny PRNG do przodu o długości bloku , dzieląc jego wyjście na następny stan i rzeczywiste wyjście. Odbywa się to poprzez ustawienie , w którym i ; wtedy G jest bezpiecznym PRNG do przodu z następnym stanem i pseudolosowym blokiem wyjściowym bieżącego okresu.

Ekstrakcja entropii

Santha i Vazirani udowodnili, że kilka strumieni bitów o słabej losowości można połączyć w celu uzyskania quasi-losowego strumienia bitów o wyższej jakości. Jeszcze wcześniej John von Neumann udowodnił, że prosty algorytm może usunąć znaczną część odchylenia w dowolnym strumieniu bitów, który należy zastosować do każdego strumienia bitów przed użyciem jakiejkolwiek odmiany projektu Santha-Vazirani.

Projekty

W poniższej dyskusji projekty CSPRNG dzielą się na trzy klasy:

  1. te oparte na prymitywach kryptograficznych, takich jak szyfry i skróty kryptograficzne ,
  2. te oparte na problemach matematycznych uważanych za trudne, oraz
  3. projekty specjalnego przeznaczenia.

Ta ostatnia często wprowadza dodatkową entropię, gdy jest dostępna i, ściśle mówiąc, nie jest „czystym” generatorem liczb pseudolosowych, ponieważ ich wyjście nie jest całkowicie określone przez ich stan początkowy. Ten dodatek może zapobiec atakom, nawet jeśli stan początkowy zostanie naruszony.

Projekty oparte na prymitywach kryptograficznych

  • Bezpieczny szyfr blokowy można przekształcić w CSPRNG, uruchamiając go w trybie licznika . Odbywa się to poprzez wybranie losowego klucza i zaszyfrowanie 0, następnie zaszyfrowanie 1, następnie zaszyfrowanie 2 itd. Licznik można również uruchomić od dowolnej liczby innej niż zero. Zakładając n- bitowy szyfr blokowy, wyjście można odróżnić od losowych danych po około 2 n /2 bloków, ponieważ po problemie z urodzinami , w tym momencie powinno dojść do kolizji bloków, podczas gdy szyfr blokowy w trybie CTR nigdy nie wypisze identycznych bloków . W przypadku 64-bitowych szyfrów blokowych ogranicza to bezpieczny rozmiar wyjścia do kilku gigabajtów, przy blokach 128-bitowych ograniczenie jest na tyle duże, że nie wpływa na typowe aplikacje. Jednakże, gdy jest używany samodzielnie, nie spełnia wszystkich kryteriów CSPRNG (jak wspomniano powyżej), ponieważ nie jest silny przeciwko „rozszerzeniom kompromisu stanu”: ze znajomością stanu (w tym przypadku licznika i klucza) możesz przewidzieć wszystkie przeszłe dane wyjściowe.
  • W niektórych przypadkach kryptograficznie bezpieczny skrót licznika może również działać jako dobry CSPRNG. W tym przypadku konieczne jest również, aby początkowa wartość tego licznika była losowa i tajna. Jednak niewiele jest badań nad tymi algorytmami do wykorzystania w ten sposób i przynajmniej niektórzy autorzy ostrzegają przed takim użyciem.
  • Większość szyfrów strumieniowych działa poprzez generowanie pseudolosowego strumienia bitów, które są łączone (prawie zawsze XORed ) z tekstem jawnym ; uruchomienie szyfru na liczniku zwróci nowy strumień pseudolosowy, prawdopodobnie z dłuższym okresem. Szyfr może być bezpieczny tylko wtedy, gdy oryginalny strumień jest dobrym CSPRNG, chociaż niekoniecznie tak jest (zobacz szyfr RC4 ). Ponownie, stan początkowy musi być utrzymywany w tajemnicy.

Projekty z teorii liczb

  • Blum Blum Shub algorytm ma dowodu bezpieczeństwa opartego na trudności kwadratowego problemu residuosity . Ponieważ jedynym znanym sposobem rozwiązania tego problemu jest faktoryzacja modułu, powszechnie uważa się, że trudność faktoryzacji liczb całkowitych zapewnia warunkowy dowód bezpieczeństwa dla algorytmu Blum Blum Shub. Jednak algorytm jest bardzo nieefektywny i dlatego niepraktyczny, chyba że potrzebne jest ekstremalne bezpieczeństwo.
  • Algorytm Blum-Micali ma dowodu bezpieczeństwa opartego na trudności dyskretnego problemu logarytmu , ale jest również bardzo nieefektywne.
  • Daniel Brown z firmy Certicom napisał w 2006 r. dowód bezpieczeństwa dla Dual_EC_DRBG , oparty na założonej twardości założenia decyzyjnego Diffie-Hellmana , problemie x-logarytmu i problemie z obciętymi punktami . Dowód z 2006 r. wprost zakłada niższy outlen niż w standardzie Dual_EC_DRBG, a P i Q w standardzie Dual_EC_DRBG (które w 2013 r. ujawniono jako prawdopodobnie backdoored przez NSA) zostały zastąpione wartościami bez backdoora.

Projekty specjalne

Istnieje wiele praktycznych PRNG, które zostały zaprojektowane tak, aby były bezpieczne kryptograficznie, w tym

Oczywiście technikę tę można łatwo uogólnić na dowolny szyfr blokowy; Zasugerowano AES .

Normy

Kilka CSPRNG zostało znormalizowanych. Na przykład,

Ten wycofany standard ma cztery PRNG. Dwa z nich są niekontrowersyjne i sprawdzone: CSPRNG o nazwach Hash_DRBG i HMAC_DRBG.
Trzeci PRNG w tym standardzie, CTR DRBG , opiera się na szyfrze blokowym działającym w trybie licznika . Ma niekontrowersyjną konstrukcję, ale okazał się słabszy pod względem rozróżniania ataku, niż poziom bezpieczeństwa bazowego szyfru blokowego, gdy liczba bitów wyjściowych z tego PRNG jest większa niż dwa do potęgi rozmiaru bloku bazowego szyfru blokowego w bitach.
Gdy maksymalna liczba bitów wyjściowych z tego PRNG jest równa 2 rozmiarom bloku , wynikowe dane wyjściowe zapewniają matematycznie oczekiwany poziom bezpieczeństwa, który powinien wygenerować rozmiar klucza, ale wynik nie jest nie do odróżnienia od prawdziwej liczby losowej generator. Gdy maksymalna liczba bitów wyprowadzanych z tego PRNG jest mniejsza, dostarczany jest oczekiwany poziom bezpieczeństwa, a dane wyjściowe wydają się nie do odróżnienia od prawdziwego generatora liczb losowych.
W następnej wersji zauważono, że deklarowana siła bezpieczeństwa dla CTR_DRBG zależy od ograniczenia całkowitej liczby żądań generowania i bitów dostarczanych na żądanie generowania.
Czwarty i ostatni PRNG w tym standardzie nosi nazwę Dual_EC_DRBG . Wykazano, że nie jest bezpieczny kryptograficznie i uważa się, że ma kleptograficzny backdoor NSA.
  • NIST SP 800-90A Rev.1: Zasadniczo jest to NIST SP 800-90A z usuniętym Dual_EC_DRBG i jest zamiennikiem wycofanego standardu.
  • ANSI X9.17-1985 Dodatek C
  • ANSI X9.31-1998 Dodatek A.2.4
  • ANSI X9.62-1998 Załącznik A.4, przestarzały przez ANSI X9.62-2005, Załącznik D (HMAC_DRBG)

Dobre odniesienie jest utrzymywane przez NIST .

Istnieją również standardy testowania statystycznego nowych projektów CSPRNG:

Backdoor kleptograficzny NSA w Dual_EC_DRBG PRNG

The Guardian i The New York Times poinformowały w 2013 r., że Agencja Bezpieczeństwa Narodowego (NSA) wstawiła tylne drzwi do generatora liczb pseudolosowych (PRNG) NIST SP 800-90A, co pozwala NSA na łatwe odszyfrowanie materiału zaszyfrowanego za pomocą tej pomocy z Dual_EC_DRBG . Oba artykuły donoszą, że jak od dawna podejrzewali niezależni eksperci ds. bezpieczeństwa, NSA wprowadzała słabości do standardu CSPRNG 800-90; po raz pierwszy zostało to potwierdzone przez jeden z ściśle tajnych dokumentów, który Edward Snowden przeciekł do Guardiana. NSA potajemnie pracowała nad uzyskaniem własnej wersji projektu standardu bezpieczeństwa NIST zatwierdzonej do użytku na całym świecie w 2006 roku. Dokument, który wyciekł, stwierdza, że ​​„w końcu NSA została jedynym redaktorem”. Pomimo znanego potencjałubackdoora kleptograficznego i innych znanych znaczących niedociągnięć związanych z Dual_EC_DRBG, kilka firm, takich jak RSA Security, nadal korzystało z Dual_EC_DRBG, dopóki backdoor nie został potwierdzony w 2013 r. RSA Security otrzymała w tym celu 10 milionów dolarów od NSA.

Luki bezpieczeństwa

Atak DUHK

23 października 2017 r. Shaanan Cohney , Matthew Green i Nadia Heninger , kryptolodzy z University of Pennsylvania i Johns Hopkins University, ujawnili szczegóły ataku DUHK (Don't Use Hard-coded Keys) na WPA2, w którym producenci sprzętu używają klucz źródłowy dla algorytmu ANSI X9.31 RNG, stwierdzający, że „atakujący może wymusić zaszyfrowane dane metodą brute-force, aby odkryć pozostałe parametry szyfrowania i wywnioskować główny klucz szyfrowania używany do szyfrowania sesji internetowych lub połączeń wirtualnej sieci prywatnej (VPN).

Japońska maszyna szyfrująca FIOLETOWA

Podczas II wojny światowej Japonia używała maszyny szyfrującej do komunikacji dyplomatycznej; Stany Zjednoczone były w stanie go złamać i przeczytać jego wiadomości , głównie dlatego, że użyte „kluczowe wartości” były niewystarczająco przypadkowe.

Bibliografia

Zewnętrzne linki