Warum sollte die C # -Klasse System.Random überhaupt anstelle von System.Security.Cryptography.RandomNumberGenerator verwendet werden?

Warum sollte jemand den "Standard" -Zufallszahlengenerator von System.Random verwenden, anstatt immer den kryptografisch sicheren Zufallszahlengenerator von System.Security.Cryptography.RandomNumberGenerator (oder dessen Unterklassen, da RandomNumberGenerator abstrakt ist) zu verwenden?

Nate Lawson sagt uns in seiner Google Tech Talk-Präsentation " Crypto Strikes Back " in Minute 13:11, dass wir nicht die "Standard" -Zufallszahlengeneratoren aus Python, Java und C # verwenden und stattdessen die kryptografisch sichere Version verwenden sollen.

Ich kenne den Unterschied zwischen den beiden Versionen von Zufallszahlengeneratoren (siehe Frage 101337 ).

Aber welche Gründe gibt es, um nicht immer den sicheren Zufallszahlengenerator zu verwenden? Warum überhaupt System.Random verwenden? Leistung vielleicht?

Geschwindigkeit und Absicht. Wenn Sie eine Zufallszahl generieren und keine Sicherheit benötigen, warum sollten Sie eine langsame Kryptofunktion verwenden? Sie brauchen keine Sicherheit. Warum sollte jemand anderes denken, dass die Nummer für etwas Sicheres verwendet werden kann, wenn dies nicht der Fall ist?

Neben der Geschwindigkeit und der nützlicheren Schnittstelle ( NextDouble()usw.) ist es auch möglich, eine wiederholbare Zufallssequenz unter Verwendung eines festen Startwerts zu erstellen . Das ist unter anderem beim Testen sehr nützlich.

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

Zunächst geht es in der von Ihnen verlinkten Präsentation aus Sicherheitsgründen nur um Zufallszahlen. Es wird also nicht behauptet, dass Randomes aus Sicherheitsgründen schlecht ist.

Aber ich behaupte es ist. Die .net 4-Implementierung von Randomist in mehrfacher Hinsicht fehlerhaft. Ich empfehle, es nur zu verwenden, wenn Sie sich nicht für die Qualität Ihrer Zufallszahlen interessieren. Ich empfehle die Verwendung besserer Implementierungen von Drittanbietern.

Fehler 1: Die Aussaat

Der Standardkonstruktor legt die aktuelle Zeit fest. Somit geben alle Instanzen, Randomdie mit dem Standardkonstruktor innerhalb eines kurzen Zeitrahmens (ca. 10 ms) erstellt wurden, dieselbe Sequenz zurück. Dies ist dokumentiert und "by-design". Dies ist besonders ärgerlich, wenn Sie Ihren Code mit mehreren Threads versehen möchten, da Sie nicht einfach Randomzu Beginn der Ausführung jedes Threads eine Instanz von erstellen können .

Die Problemumgehung ist besonders vorsichtig, wenn Sie den Standardkonstruktor verwenden und bei Bedarf manuell festlegen.

Ein weiteres Problem hierbei ist, dass der Startraum eher klein ist (31 Bit). Wenn Sie also 50.000 Instanzen Randommit perfekt zufälligen Samen generieren, erhalten Sie wahrscheinlich zweimal eine Folge von Zufallszahlen (aufgrund des Geburtstagsparadoxons ). Manuelles Seeding ist also auch nicht einfach richtig zu machen.

Fehler 2: Die Verteilung der von zurückgegebenen Zufallszahlen Next(int maxValue)ist voreingenommen

Es gibt Parameter, für die Next(int maxValue)eindeutig keine Einheitlichkeit besteht. Wenn Sie zum Beispiel rechnen, erhalten r.Next(1431655765) % 2Sie 0ungefähr 2/3 der Stichproben. (Beispielcode am Ende der Antwort.)

Fehler 3: Die NextBytes()Methode ist ineffizient.

Die Kosten pro Byte von NextBytes()sind ungefähr so ​​hoch wie die Kosten für die Erzeugung einer vollständigen Ganzzahl-Stichprobe mit Next(). Daraus vermute ich, dass sie tatsächlich ein Sample pro Byte erstellen.

Eine bessere Implementierung mit 3 Bytes aus jedem Sample würde NextBytes()sich um fast den Faktor 3 beschleunigen .

Dank dieses Fehlers Random.NextBytes()ist nur etwa 25% schneller als System.Security.Cryptography.RNGCryptoServiceProvider.GetBytesauf meinem Computer (Win7, Core i3 2600MHz).

Ich bin sicher, wenn jemand den Quell- / dekompilierten Bytecode inspiziert, findet er noch mehr Fehler als bei meiner Black-Box-Analyse.

Codebeispiele

r.Next(0x55555555) % 2 ist stark voreingenommen:

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]);

Performance:

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 ist viel leistungsfähiger, da es keine kryptografisch sicheren Zufallszahlen generiert.

Ein einfacher Test auf meinem Computer, der 1.000.000 Mal einen Puffer von 4 Bytes mit zufälligen Daten füllt, dauert für Random 49 ms, für RNGCryptoServiceProvider 2845 ms. Beachten Sie, dass sich der Unterschied verringert, wenn Sie den Puffer, den Sie füllen, vergrößern, da der Overhead für RNGCryptoServiceProvider weniger relevant ist.

Die offensichtlichsten Gründe wurden bereits erwähnt, daher hier ein dunklerer: Kryptografische PRNGs müssen normalerweise kontinuierlich mit "echter" Entropie neu besät werden. Wenn Sie ein CPRNG zu oft verwenden, können Sie den Entropiepool des Systems erschöpfen, wodurch es (abhängig von der Implementierung des CPRNG) entweder geschwächt wird (wodurch ein Angreifer es vorhersagen kann) oder es blockiert, während es versucht, sich zu füllen seinen Entropiepool (wird so zu einem Angriffsvektor für einen DoS-Angriff).

In beiden Fällen ist Ihre Anwendung jetzt zu einem Angriffsvektor für andere, völlig unabhängige Anwendungen geworden, die - anders als Ihre - tatsächlich entscheidend von den kryptografischen Eigenschaften des CPRNG abhängen.

Dies ist ein echtes Problem, übrigens, das auf Headless-Servern (die natürlich eher kleine Entropiepools haben, weil ihnen Entropiequellen wie Maus- und Tastatureingaben fehlen) unter Linux beobachtet wurde, wo Anwendungen den /dev/randomKernel CPRNG für alle Arten falsch verwenden von Zufallszahlen, während das richtige Verhalten darin besteht, einen kleinen Startwert daraus zu lesen /dev/urandomund diesen zu verwenden, um ihr eigenes PRNG zu setzen.

Wenn Sie ein Online-Kartenspiel oder einen Lotter programmieren, sollten Sie sicherstellen, dass die Reihenfolge so gut wie unmöglich zu erraten ist. Wenn Sie Benutzern jedoch beispielsweise ein Zitat des Tages anzeigen, ist die Leistung wichtiger als die Sicherheit.

Beachten Sie, dass die System.Random-Klasse in C # falsch codiert ist und daher vermieden werden sollte.

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

Dies wurde ausführlich erörtert, aber letztendlich spielt das Thema Leistung bei der Auswahl eines RNG eine untergeordnete Rolle. Es gibt eine Vielzahl von RNGs, und das Lehmer-LCG in Dosen, aus dem die meisten System-RNGs bestehen, ist weder das beste noch notwendigerweise das schnellste. Auf alten, langsamen Systemen war es ein ausgezeichneter Kompromiss. Dieser Kompromiss ist heutzutage selten wirklich relevant. Das Ding bleibt in heutigen Systemen bestehen, vor allem, weil A) das Ding bereits gebaut ist und es in diesem Fall keinen wirklichen Grund gibt, das Rad neu zu erfinden, und B) für das, wofür die große Masse der Leute es verwenden wird, es ist 'gut genug'.

Letztendlich hängt die Auswahl eines RNG vom Risiko / Ertrags-Verhältnis ab. In einigen Anwendungen, beispielsweise einem Videospiel, besteht keinerlei Risiko. Ein Lehmer RNG ist mehr als ausreichend und klein, prägnant, schnell, gut verstanden und "in the box".

Wenn es sich bei der Anwendung beispielsweise um ein Online-Pokerspiel oder eine Lotterie handelt, bei der es um tatsächliche Preise geht und an einem bestimmten Punkt der Gleichung echtes Geld ins Spiel kommt, ist der Lehmer „in the Box“ nicht mehr ausreichend. In einer 32-Bit-Version hat es nur 2 ^ 32 mögliche gültige Zustände, bevor es bestenfalls mit dem Zyklus beginnt . Heutzutage ist das eine offene Tür für einen Brute-Force-Angriff. In einem solchen Fall möchte der Entwickler zu einem RNG für sehr lange Zeiträume einiger Arten gehen und es wahrscheinlich von einem kryptografisch starken Anbieter aussäen. Dies bietet einen guten Kompromiss zwischen Geschwindigkeit und Sicherheit. In einem solchen Fall sucht die Person nach etwas wie dem Mersenne Twister oder einem multiplen rekursiven Generator .

Wenn es sich bei der Anwendung um die Kommunikation großer Mengen von Finanzinformationen über ein Netzwerk handelt, besteht jetzt ein großes Risiko, und jede mögliche Belohnung wird stark überwogen. Es gibt immer noch gepanzerte Autos, weil manchmal schwer bewaffnete Männer die einzige Sicherheit sind, die ausreicht, und vertrauen Sie mir, wenn eine Brigade von Spezialeinheiten mit Panzern, Kämpfern und Hubschraubern finanziell machbar wäre, wäre dies die Methode der Wahl. In einem solchen Fall ist die Verwendung eines kryptografisch starken RNG sinnvoll, da die Sicherheitsstufe, die Sie erhalten können, nicht so hoch ist, wie Sie möchten. Sie werden also so viel nehmen, wie Sie finden können, und die Kosten sind ein sehr, sehr entferntes Problem des zweiten Platzes, entweder in Bezug auf Zeit oder Geld. Und wenn dies bedeutet, dass jede zufällige Sequenz 3 Sekunden benötigt, um auf einem sehr leistungsstarken Computer generiert zu werden, warten Sie die 3 Sekunden.

Nicht jeder benötigt kryptografisch sichere Zufallszahlen, und sie profitieren möglicherweise mehr von einem schnelleren einfachen Prng. Vielleicht noch wichtiger ist, dass Sie die Reihenfolge für System.Random-Nummern steuern können.

In einer Simulation mit Zufallszahlen, die Sie möglicherweise neu erstellen möchten, führen Sie die Simulation mit demselben Startwert erneut aus. Dies kann nützlich sein, um Fehler zu verfolgen, wenn Sie auch ein bestimmtes fehlerhaftes Szenario neu generieren möchten - indem Sie Ihr Programm mit genau der gleichen Folge von Zufallszahlen ausführen, mit denen das Programm abgestürzt ist.

Wenn ich die Sicherheit nicht benötige, dh nur einen relativ unbestimmten Wert möchte, der nicht kryptografisch stark ist, hat Random eine viel einfachere Benutzeroberfläche.

Unterschiedliche Anforderungen erfordern unterschiedliche RNGs. Für Krypto möchten Sie, dass Ihre Zufallszahlen so zufällig wie möglich sind. Für Monte-Carlo-Simulationen möchten Sie, dass sie den Raum gleichmäßig ausfüllen und das RNG von einem bekannten Zustand aus starten können.

Random ist kein Zufallszahlengenerator, sondern ein deterministischer Pseudozufallssequenzgenerator, der aus historischen Gründen seinen Namen hat.

Der Grund zu verwenden System.Random ist, wenn Sie diese Eigenschaften wünschen, nämlich eine deterministische Sequenz, die garantiert dieselbe Ergebnissequenz erzeugt, wenn sie mit demselben Startwert initialisiert wird.

Wenn Sie die "Zufälligkeit" verbessern möchten, ohne die Schnittstelle zu beeinträchtigen, können Sie das System.RandomÜberschreiben mehrerer Methoden erben .

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

Warum sollten Sie eine deterministische Sequenz wollen?

Ein Grund für eine deterministische Sequenz anstelle einer echten Zufälligkeit ist, dass sie wiederholbar ist.

Wenn Sie beispielsweise eine numerische Simulation ausführen, können Sie die Sequenz mit einer (wahren) Zufallszahl initialisieren und aufzeichnen, welche Zahl verwendet wurde .

Wenn Sie dann genau dieselbe Simulation wiederholen möchten , z. B. zu Debugging-Zwecken, können Sie dies tun, indem Sie stattdessen die Sequenz mit dem aufgezeichneten Wert initialisieren .

Warum sollten Sie diese bestimmte, nicht sehr gute Sequenz wollen?

Der einzige Grund, den ich mir vorstellen kann, ist die Abwärtskompatibilität mit vorhandenem Code, der diese Klasse verwendet.

Kurz gesagt, wenn Sie die Reihenfolge verbessern möchten, ohne den Rest Ihres Codes zu ändern, fahren Sie fort.

Ich habe ein Spiel geschrieben (Crystal Sliders auf dem iPhone: Hier ), das eine "zufällige" Reihe von Edelsteinen (Bildern) auf der Karte platziert und Sie die Karte nach Ihren Wünschen drehen und auswählen und sie verschwinden lassen. - Ähnlich wie Bejeweled. Ich habe Random () verwendet und es wurde mit der Anzahl von 100 ns Ticks seit dem Start des Telefons gesät, ein ziemlich zufälliger Startwert.

Ich fand es erstaunlich, dass es Spiele erzeugen würde, die fast identisch miteinander waren - von den ungefähr 90 Edelsteinen in zwei Farben würde ich zwei genau gleich bekommen, außer 1 bis 3 Edelsteinen! Wenn Sie 90 Münzen werfen und das gleiche Muster mit Ausnahme von 1-3 Würfen erhalten, ist dies SEHR unwahrscheinlich! Ich habe mehrere Screenshots, die sie gleich zeigen. Ich war schockiert, wie schlecht System.Random () war! Ich nahm an, dass ich etwas schrecklich Falsches in meinen Code geschrieben haben MUSS und es falsch verwendete. Ich habe mich geirrt, es war der Generator.

Als Experiment - und als endgültige Lösung - ging ich zurück zu dem Zufallszahlengenerator, den ich seit ungefähr 1985 verwende - was VIEL besser ist. Es ist schneller und hat eine Periode von 1,3 * 10 ^ 154 (2 ^ 521), bevor es sich wiederholt. Der ursprüngliche Algorithmus wurde mit einer 16-Bit-Nummer geimpft, aber ich habe diese in eine 32-Bit-Nummer geändert und das anfängliche Seeding verbessert.

Das Original ist hier:

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

Im Laufe der Jahre habe ich jeden erdenklichen Zufallszahlentest durchgeführt, und zwar an allen vorbei. Ich erwarte nicht, dass es einen kryptografischen Wert hat, aber es gibt eine Zahl zurück, die so schnell ist wie "return * p ++;" bis die 521 Bits ausgehen, und dann wird ein schneller Prozess über die Bits ausgeführt, um neue zufällige zu erstellen.

Ich habe einen C # -Wrapper erstellt - JPLRandom () genannt - die gleiche Schnittstelle wie Random () implementiert und alle Stellen geändert, an denen ich ihn im Code aufgerufen habe.

Der Unterschied war VIEL besser - OMG, ich war erstaunt - es sollte unmöglich sein, nur die Bildschirme von ungefähr 90 Edelsteinen in einem Muster zu betrachten, aber ich habe danach eine Notveröffentlichung meines Spiels durchgeführt.

Und ich würde System.Random () nie wieder für irgendetwas verwenden. Ich bin schockiert, dass ihre Version von etwas umgehauen wird, das jetzt 30 Jahre alt ist!

-Traderhut-Spiele