Fortuna (PRNG) - Fortuna (PRNG)

Fortuna to kryptograficznie bezpieczny generator liczb pseudolosowych (PRNG) opracowany przez Bruce'a Schneiera i Nielsa Fergusona i opublikowany w 2003 roku. Jego nazwa pochodzi od Fortuny , rzymskiej bogini przypadku. FreeBSD używa Fortuny dla /dev/random, a /dev/urandom jest z nim symbolicznie powiązany od czasu FreeBSD 11. Systemy Apple OS przeszły na Fortunę od pierwszego kwartału 2020 roku.

Projekt

Fortuna to rodzina bezpiecznych PRNG; jego konstrukcja pozostawia pewien wybór podmiotom wdrażającym. Składa się z następujących utworów:

  • Sam generator, który raz zaszczepi , wyprodukuje nieskończoną ilość danych pseudolosowych.
  • Entropia akumulator, który zbiera prawdziwie losowych danych z różnych źródeł i wykorzystuje ją do reseedować generator gdy wystarczająco nowy losowość przyjechał.
  • Plik źródłowy, który przechowuje wystarczająco dużo stanu, aby komputer mógł rozpocząć generowanie liczb losowych zaraz po uruchomieniu.

Generator

Generator bazuje na dowolnym dobrym szyfrze blokowym . Kryptografia praktyczna sugeruje AES , Serpent lub Twofish . Podstawową ideą jest uruchomienie szyfru w trybie licznika , szyfrowanie kolejnych wartości licznika narastającego.

W przypadku 128-bitowego szyfru blokowego dałoby to statystycznie identyfikowalne odchylenia od losowości; na przykład, wygenerowanie 264 prawdziwie losowych 128-bitowych bloków dałoby średnio około jednej pary identycznych bloków, ale nie ma w ogóle powtarzających się bloków wśród pierwszych 2 128 generowanych przez 128-bitowy szyfr w trybie licznika. Dlatego klucz jest zmieniany okresowo: nie więcej niż 1 MiB danych (2 16 128-bitowych bloków) jest generowany bez zmiany klucza. Książka zwraca uwagę, że szyfry blokowe o rozmiarze bloku 256-bitowego (lub większym), które nie cieszyły się wówczas dużą popularnością, nie mają tego statystycznego problemu.

Klucz jest również zmieniany po każdym żądaniu danych (niezależnie od tego, jak mały), tak aby przyszłe złamanie klucza nie zagrażało poprzednim wyjściom generatora. Ta właściwość jest czasami określana jako „Szybkie usuwanie klucza” lub utajnienie przekazywania .

Akumulator entropii

Akumulator entropii został zaprojektowany tak, aby był odporny na ataki „wstrzykiwania”, bez konieczności stosowania wyrafinowanych (i nieuchronnie zawodnych) estymatorów entropii. Istnieje kilka „kałuż” entropii; każde źródło entropii rozprowadza swoją rzekomą entropię równomiernie w pulach; i (tutaj jest kluczowa idea) przy n- tym ponownym zasianiu generatora, pula k jest używana tylko wtedy, gdy n jest wielokrotnością 2 k . Tak więc k- ta pula jest używana tylko w 1/2 tys . Innymi słowy, pule o wyższych numerach (1) rzadziej przyczyniają się do ponownego wysiewu, ale (2) gromadzą większą ilość entropii między kolejnymi wysiewami. Ponowne rozmieszczanie odbywa się poprzez mieszanie określonych pul entropii do klucza szyfru blokowego przy użyciu dwóch iteracji SHA-256 .

Wysiew

O ile atakujący nie jest w stanie kontrolować wszystkich źródeł domniemanej entropii napływającej do systemu (w takim przypadku żaden algorytm nie jest w stanie uchronić go przed skompromitowaniem), będzie pewna liczba k, dla której k- ta pula zgromadzi wystarczającą ilość entropii między ponownymi zasiewami, aby ta pula zapewnia bezpieczeństwo. I ta pula będzie używana w odstępach proporcjonalnych do wielkości danej entropii. Dlatego system zawsze odzyska sprawność po ataku polegającym na wstrzykiwaniu, a czas potrzebny na to jest co najwyżej współczynnikiem stałym większym niż teoretyczny czas, jaki mógłby zająć, gdybyśmy byli w stanie zidentyfikować, które źródła entropii zostały uszkodzone, a które nie.

Ten wniosek zależy od wystarczającej liczby pul. Fortuna korzysta z 32 puli i ogranicza ponowne wysiewanie maksymalnie 10 razy na sekundę. Wyczerpanie się basenów zajęłoby wtedy około 13 lat, co Ferguson i Schneier uważają za wystarczająco długo ze względów praktycznych. Bardziej paranoidalni implementatorzy lub ci, którzy wymagają generowania losowych danych w kolosalnym tempie i odpowiednio częstego ponownego umieszczania, mogliby użyć większej liczby pul.

Alternatywy

Fortuna różni się od wcześniejszej rodziny algorytmów Yarrow Schneiera, Kelseya i Fergusona głównie w sposobie obsługi akumulatora entropijnego. Yarrow wymagał, aby każdemu źródłu entropii towarzyszył mechanizm szacowania rzeczywistej dostarczonej entropii i używał tylko dwóch pul; a jego sugerowana postać (zwana Yarrow-160 ) wykorzystywała SHA-1 zamiast iterowanego SHA-256 .

Analiza

Analiza i propozycja ulepszenia Fortuny została wykonana w 2014 roku.

Zobacz też

Bibliografia

Ogólny

  • Niels Ferguson i Bruce Schneier, „ Praktyczna kryptografia” , opublikowana przez Wiley w 2003 r. ISBN  0-471-22357-3 .
  • John Viega, „Praktyczne generowanie liczb losowych w oprogramowaniu”, acsac, s. 129, 19. doroczna konferencja na temat zastosowań zabezpieczeń komputerowych (ACSAC '03), 2003

Zewnętrzne linki