Po co w ogóle używać klasy C # System.Random zamiast System.Security.Cryptography.RandomNumberGenerator?

Dlaczego ktokolwiek miałby w ogóle używać „standardowego” generatora liczb losowych z System.Random zamiast zawsze używać generatora liczb losowych zabezpieczonego kryptograficznie z System.Security.Cryptography.RandomNumberGenerator (lub jego podklas, ponieważ RandomNumberGenerator jest abstrakcyjny)?

Nate Lawson mówi nam w swojej prezentacji Google Tech Talk „ Crypto Strikes Back ” w minucie 13:11, aby nie używać „standardowych” generatorów liczb losowych z Pythona, Javy i C #, a zamiast tego używać wersji bezpiecznej kryptograficznie.

Znam różnicę między dwiema wersjami generatorów liczb losowych (patrz pytanie 101337 ).

Ale jakie jest uzasadnienie, aby nie zawsze używać bezpiecznego generatora liczb losowych? Dlaczego w ogóle używać System.Random? Może wydajność?

Szybkość i zamiar. Jeśli generujesz liczbę losową i nie potrzebujesz zabezpieczeń, po co używać powolnej funkcji kryptograficznej? Nie potrzebujesz zabezpieczeń, więc po co komuś sądzić, że numer może być użyty do czegoś bezpiecznego, gdy nie będzie?

Oprócz szybkości i bardziej użytecznego interfejsu ( NextDouble()itp.) Możliwe jest również utworzenie powtarzalnej losowej sekwencji przy użyciu stałej wartości ziarna. Przydaje się to między innymi podczas testowania.

Random gen1 = new Random();     // auto seeded by the clock
Random gen2 = new Random(0);    // Next(10) always yields 7,8,7,5,2,....

Przede wszystkim prezentacja, którą łączysz, mówi tylko o liczbach losowych ze względów bezpieczeństwa. Więc nie twierdzi, że Randomjest zły ze względów niezwiązanych z bezpieczeństwem.

Ale twierdzę, że tak. Implementacja .net 4 Randomjest wadliwa z kilku powodów. Zalecam używanie go tylko wtedy, gdy nie dbasz o jakość swoich liczb losowych. Polecam używanie lepszych implementacji innych firm.

Wada 1: Rozstawienie

Domyślny konstruktor nasiona z bieżącym czasem. Tak więc wszystkie instancje Randomutworzone za pomocą domyślnego konstruktora w krótkim czasie (ok. 10 ms) zwracają tę samą sekwencję. Jest to udokumentowane i „zgodne z projektem”. Jest to szczególnie denerwujące, jeśli chcesz wielowątkowość swojego kodu, ponieważ nie możesz po prostu utworzyć wystąpienia Randomna początku wykonywania każdego wątku.

Aby obejść ten problem, należy zachować szczególną ostrożność podczas korzystania z domyślnego konstruktora i ręcznie, gdy jest to konieczne.

Innym problemem jest to, że przestrzeń nasion jest raczej mała (31 bitów). Więc jeśli wygenerujesz 50k instancji Randomz idealnie losowymi nasionami, prawdopodobnie otrzymasz dwukrotnie jedną sekwencję liczb losowych (ze względu na paradoks urodzin ). Tak więc ręczne wysiewanie również nie jest łatwe.

Wada 2: Rozkład liczb losowych zwracanych przez Next(int maxValue)jest obciążony

Istnieją parametry, które Next(int maxValue)wyraźnie nie są jednolite. Na przykład, jeśli obliczysz r.Next(1431655765) % 2, otrzymasz 0około 2/3 próbek. (Przykładowy kod na końcu odpowiedzi.)

Wada 3: NextBytes()Metoda jest nieefektywna.

Koszt za bajt NextBytes()jest mniej więcej tak duży, jak koszt wygenerowania pełnej próbki całkowitej za pomocą Next(). Na tej podstawie podejrzewam, że rzeczywiście tworzą jedną próbkę na bajt.

Lepsza implementacja wykorzystująca 3 bajty z każdej próbki przyspieszyłaby NextBytes()prawie 3-krotnie.

Dzięki temu wada Random.NextBytes()jest tylko o około 25% szybsza niż System.Security.Cryptography.RNGCryptoServiceProvider.GetBytesna moim komputerze (Win7, Core i3 2600MHz).

Jestem pewien, że gdyby ktoś sprawdził źródłowy / zdekompilowany kod bajtowy, znalazłby jeszcze więcej błędów niż ja podczas analizy czarnej skrzynki.

Próbki kodu

r.Next(0x55555555) % 2 jest mocno stronniczy:

Random r = new Random();
const int mod = 2;
int[] hist = new int[mod];
for(int i = 0; i < 10000000; i++)
{
    int num = r.Next(0x55555555);
    int num2 = num % 2;
    hist[num2]++;
}
for(int i=0;i<mod;i++)
    Console.WriteLine(hist[i]);

Występ:

byte[] bytes=new byte[8*1024];
var cr=new System.Security.Cryptography.RNGCryptoServiceProvider();
Random r=new Random();

// Random.NextBytes
for(int i=0;i<100000;i++)
{
    r.NextBytes(bytes);
}

//One sample per byte
for(int i=0;i<100000;i++)
{   
    for(int j=0;j<bytes.Length;j++)
      bytes[j]=(byte)r.Next();
}

//One sample per 3 bytes
for(int i=0;i<100000;i++)
{
    for(int j=0;j+2<bytes.Length;j+=3)
    {
        int num=r.Next();
        bytes[j+2]=(byte)(num>>16);   
        bytes[j+1]=(byte)(num>>8);
        bytes[j]=(byte)num;
    }
    //Yes I know I'm not handling the last few bytes, but that won't have a noticeable impact on performance
}

//Crypto
for(int i=0;i<100000;i++)
{
    cr.GetBytes(bytes);
}

System.Random jest znacznie wydajniejszy, ponieważ nie generuje liczb losowych zabezpieczonych kryptograficznie.

Prosty test na mojej maszynie wypełniający bufor 4 bajtów losowymi danymi 1000000 razy zajmuje 49 ms dla Random, ale 2845 ms dla RNGCryptoServiceProvider. Zwróć uwagę, że jeśli zwiększysz rozmiar wypełnianego buforu, różnica zmniejszy się, ponieważ narzut dla RNGCryptoServiceProvider jest mniej istotny.

Najbardziej oczywiste powody zostały już wymienione, więc oto jeden z nich bardziej niejasny: kryptograficzne PRNG zazwyczaj muszą być nieustannie uzupełniane „prawdziwą” entropią. Tak więc, jeśli używasz CPRNG zbyt często, możesz wyczerpać pulę entropii systemu, która (w zależności od implementacji CPRNG) albo ją osłabi (umożliwiając napastnikowi to przewidzenie), albo zablokuje się podczas próby wypełnienia jego pulę entropii (stając się tym samym wektorem ataku dla ataku DoS).

Tak czy inaczej, Twoja aplikacja stała się teraz wektorem ataku dla innych, zupełnie niezwiązanych ze sobą aplikacji, które - w przeciwieństwie do twojej - w rzeczywistości są niezwykle zależne od właściwości kryptograficznych CPRNG.

Przy okazji, jest to rzeczywisty problem świata rzeczywistego, który zaobserwowano na serwerach bezgłowych (które naturalnie mają raczej małe pule entropii, ponieważ brakuje im źródeł entropii, takich jak wejście myszy i klawiatury) z Linuksem, gdzie aplikacje nieprawidłowo używają /dev/randomCPRNG jądra dla wszystkich rodzajów liczb losowych, podczas gdy poprawnym zachowaniem byłoby odczytanie małej wartości początkowej z /dev/urandomi użycie jej do zapoczątkowania własnego PRNG.

Jeśli programujesz grę karcianą lub loterię online, chciałbyś upewnić się, że sekwencja jest prawie niemożliwa do odgadnięcia. Jeśli jednak pokazujesz użytkownikom, powiedzmy, cytat z dnia, wydajność jest ważniejsza niż bezpieczeństwo.

Omówiono to obszernie, ale ostatecznie kwestia wydajności jest kwestią drugorzędną przy wyborze RPG. Istnieje szeroki wachlarz RNG, a konserwowany Lehmer LCG, z którego składa się większość systemowych RNG, nie jest najlepszy, ani nawet koniecznie najszybszy. Na starych, powolnych systemach był to doskonały kompromis. W dzisiejszych czasach ten kompromis rzadko jest naprawdę istotny. Ta rzecz utrzymuje się w dzisiejszych systemach głównie dlatego, że A) rzecz jest już zbudowana i nie ma prawdziwego powodu, aby `` odkrywać koło na nowo '' w tym przypadku, oraz B) ponieważ ogromna większość ludzi będzie jej używać 'wystarczająco dobry'.

Ostatecznie wybór RNG sprowadza się do stosunku ryzyka do korzyści. W niektórych aplikacjach, na przykład w grach wideo, nie ma żadnego ryzyka. Lehmer RNG jest więcej niż wystarczający i jest mały, zwięzły, szybki, dobrze zrozumiany i „w pudełku”.

Jeśli aplikacja jest na przykład grą w pokera online lub loterią, w której w pewnym momencie pojawiają się rzeczywiste nagrody, a do gry wchodzą prawdziwe pieniądze, „w pudełku” Lehmer nie jest już wystarczający. W wersji 32-bitowej ma tylko 2 ^ 32 możliwe prawidłowe stany, zanim zacznie w najlepszym przypadku cykliczne . W dzisiejszych czasach to otwarte drzwi do brutalnego ataku. W takim przypadku deweloper będzie chciał przejść do czegoś w rodzaju bardzo długiego okresu RNG niektórych gatunków i prawdopodobnie wysiać go od dostawcy o silnej kryptografii. Daje to dobry kompromis między szybkością a bezpieczeństwem. W takim przypadku osoba będzie szukała czegoś takiego jak Mersenne Twister lub pewnego rodzaju Multiple Recursive Generator .

Jeśli aplikacja jest czymś w rodzaju przekazywania dużych ilości informacji finansowych przez sieć, teraz istnieje ogromne ryzyko i znacznie przewyższa każdą możliwą nagrodę. Wciąż są samochody opancerzone, ponieważ czasami ciężko uzbrojeni ludzie są jedynym wystarczającym zabezpieczeniem, i uwierzcie mi, gdyby brygada ludzi do zadań specjalnych z czołgami, myśliwcami i helikopterami była finansowo opłacalna, byłaby to metoda z wyboru. W takim przypadku użycie silnego kryptograficznie RNG ma sens, ponieważ bez względu na poziom bezpieczeństwa, jaki możesz uzyskać, nie jest tak duży, jak chcesz. Więc weźmiesz tyle, ile możesz znaleźć, a koszt jest bardzo, bardzo odległym problemem na drugim miejscu, zarówno pod względem czasu, jak i pieniędzy. A jeśli to oznacza, że ​​wygenerowanie każdej losowej sekwencji na bardzo wydajnym komputerze zajmuje 3 sekundy, poczekasz 3 sekundy,

Należy zauważyć, że klasa System.Random w języku C # jest kodowana nieprawidłowo, dlatego należy jej unikać.

https://connect.microsoft.com/VisualStudio/feedback/details/634761/system-random-serious-bug#tabs

Nie każdy potrzebuje zabezpieczonych kryptograficznie liczb losowych, a szybszy zwykły sposób może przynieść większe korzyści. Być może ważniejsze jest to, że możesz kontrolować sekwencję liczb System.Random.

W symulacji wykorzystującej liczby losowe, które możesz chcieć odtworzyć, ponownie uruchamiasz symulację z tym samym ziarnem. Może to być przydatne do śledzenia błędów, gdy chcesz również zregenerować dany błędny scenariusz - uruchamianie programu z dokładnie tą samą sekwencją liczb losowych, które spowodowały awarię programu.

Jeśli nie potrzebuję zabezpieczeń, tj. Chcę tylko względnie nieokreślonej wartości, a nie takiej, która jest silna kryptograficznie, Random ma znacznie łatwiejszy w użyciu interfejs.

Różne potrzeby wymagają różnych RNG. W przypadku kryptowalut chcesz, aby Twoje liczby losowe były jak najbardziej losowe. W przypadku symulacji Monte Carlo chcesz, aby równomiernie wypełniły przestrzeń i mogły rozpocząć RNG ze znanego stanu.

Random nie jest generatorem liczb losowych, jest deterministycznym generatorem sekwencji pseudolosowych, który bierze swoją nazwę ze względów historycznych.

Powodem jest użycie System.Randomtych właściwości, a mianowicie deterministycznej sekwencji, która gwarantuje uzyskanie tej samej sekwencji wyników po zainicjowaniu tego samego materiału siewnego.

Jeśli chcesz poprawić „losowość” bez poświęcania interfejsu, możesz odziedziczyć z System.Randomzastąpienia kilku metod.

• https://msdn.microsoft.com/en-us/library/system.random.sample(v=vs.110).aspx

Dlaczego miałbyś chcieć deterministycznej sekwencji

Jednym z powodów, dla których warto mieć raczej deterministyczną sekwencję niż prawdziwą losowość, jest to, że jest ona powtarzalna.

Na przykład, jeśli przeprowadzasz symulację numeryczną, możesz zainicjować sekwencję (prawdziwą) liczbą losową i zapisać, jaka liczba została użyta .

Następnie, jeśli chcesz powtórzyć dokładnie tę samą symulację, np. W celu debugowania, możesz to zrobić, zamiast tego inicjalizując sekwencję zapisaną wartością.

Dlaczego miałbyś chcieć tej konkretnej, niezbyt dobrej sekwencji

Jedynym powodem, jaki przychodzi mi do głowy, byłaby wsteczna kompatybilność z istniejącym kodem, który używa tej klasy.

Krótko mówiąc, jeśli chcesz poprawić sekwencję bez zmiany reszty kodu, śmiało.

Napisałem grę (Crystal Sliders on the iPhone: Here ), która wyświetlałaby „losową” serię klejnotów (obrazów) na mapie, a ty obracałeś mapę tak, jak chcesz, wybierałeś je i znikały. - Podobny do Bejeweled. Używałem Random () i został on obsadzony liczbą 100ns ticków od momentu uruchomienia telefonu, całkiem losowe ziarno.

Wydało mi się to niesamowite , że generował gry, które były prawie identyczne - z około 90 klejnotów, w 2 kolorach, dostałbym dwa DOKŁADNIE takie same, z wyjątkiem 1 do 3 klejnotów! Jeśli przerzucisz 90 monet i uzyskasz ten sam wzór z wyjątkiem 1-3 rzutów, jest to BARDZO mało prawdopodobne! Mam kilka zrzutów ekranu, które pokazują im to samo. Byłem zszokowany, jak zły był System.Random ()! Założyłem, że MUSZĘ napisać w swoim kodzie coś strasznie złego i źle go używać. Myliłem się jednak, to był generator.

Jako eksperyment - i ostateczne rozwiązanie, wróciłem do generatora liczb losowych, którego używam mniej więcej od 1985 roku - który jest OSTATECZNIE lepszy. Jest szybszy, ma okres 1,3 * 10 ^ 154 (2 ^ 521), zanim się powtórzy. Oryginalny algorytm został zapoczątkowany liczbą 16-bitową, ale zmieniłem ją na liczbę 32-bitową i poprawiłem początkowe wysiewanie.

Oryginał jest tutaj:

ftp://ftp.grnet.gr/pub/lang/algorithms/c/jpl-c/random.c

Przez lata rzuciłem każdy test liczb losowych, o którym mogłem pomyśleć, i przeszedł przez wszystkie. Nie spodziewam się, że ma jakąkolwiek wartość jako kryptograficzną, ale zwraca liczbę tak szybko, jak „return * p ++;” aż skończy się 521 bitów, a następnie wykonuje szybki proces na bitach, aby utworzyć nowe losowe.

Stworzyłem wrapper C # - nazwałam go JPLRandom () zaimplementowałem ten sam interfejs co Random () i zmieniłem wszystkie miejsca, w których wywołałem go w kodzie.

Różnica była OSTATECZNIE lepsza - OMG, byłem zdumiony - nie powinno być sposobu, bym mógł stwierdzić, patrząc tylko na ekrany z około 90 klejnotami w układzie, ale po tym wydałem awaryjną wersję mojej gry.

I nigdy więcej nie użyłbym System.Random () do niczego. Jestem W SZOKU, że ich wersja jest zdmuchnięta przez coś, co ma teraz 30 lat!

-Traderhut Games

Ponieważ System.Random jest tu atakowany za jego "niepoprawność" i stronniczość, sprawdziłem się.

dystrybucja

Ten kod f # pokazuje, że zachowuje się naprawdę ładnie - na moim przeciętnym komputerze:

let r = System.Random()
Seq.init 1000000 (fun _ -> r.Next(0,10))
|> Seq.toList
|> Seq.groupBy id
|> Seq.map (fun (v,ls) -> v, ls |> Seq.length)
|> Seq.sortBy fst
|> Seq.iter (printfn "%A")

(0, 100208)
(1, 99744)
(2, 99929)
(3, 99827)
(4, 100273)
(5, 100280)
(6, 100041)
(7, 100001)
(8, 100175)
(9, 99522)    

Wersje frameworka, maszyna, system operacyjny - wszystko to może mieć znaczenie. Wprowadź kod w interaktywnym języku F # na swoim komputerze i spróbuj sam. Czytałem dla Cyrptography

let arr = [| 0uy |]
let rr = System. Security.Cryptography.RandomNumberGenerator.Create()
Seq.init 1000000 (fun _ -> rr.GetBytes(arr); arr.[0])
|> Seq.toList
|> Seq.groupBy id
|> Seq.map (fun (v,ls) -> v, ls |> Seq.length)
|> Seq.sortBy fst
|> Seq.take 10 // show first 10 bytes
|> Seq.iter (printfn "%A")

// distribution of first 10 bytes
(0uy, 3862)
(1uy, 3888)
(2uy, 3921)
(3uy, 3926)
(4uy, 3948)
(5uy, 3889)
(6uy, 3922)
(7uy, 3797)
(8uy, 3861)
(9uy, 3874)

występ

#time

let arr = [| 0uy |]

let r = System.Random()
Seq.init 1000000 (fun _ -> r.NextBytes(arr); arr.[0] |> int64) |> Seq.sum

Real: 00:00:00.204, CPU: 00:00:00.203, GC gen0: 45, gen1: 1, gen2: 1
val it : int64 = 127503467L

let rr = System. Security.Cryptography.RandomNumberGenerator.Create()
Seq.init 1000000 (fun _ -> rr.GetBytes(arr); arr.[0] |> int64) |> Seq.sum

Real: 00:00:00.365, CPU: 00:00:00.359, GC gen0: 44, gen1: 0, gen2: 0
val it : int64 = 127460809L

co sugeruje relację 1: 2 i nieco lepsze zachowanie pamięci w wersji kryptograficznej.

wniosek

Głównie ze względu na znacznie ładniejsze API, nieco za wydajność i całkiem dobrą dystrybucję preferowany jest System.Random. System.Random może również zmniejszyć zależności bibliotek, a jeśli framework zostanie przeniesiony, System.Random będzie prawdopodobnie dostępny przed wariantem Crypto.