Wie unterscheiden sich pseudozufällige und wirklich zufällige Zahlen und warum ist das wichtig?

Lassen Sie uns etwas Computer-Poker spielen, nur Sie, mich und einen Server, dem wir beide vertrauen. Der Server verwendet einen Pseudo-Zufallszahlengenerator, der unmittelbar vor dem Spielen mit einem 32-Bit-Startwert initialisiert wird. Es gibt also etwa vier Milliarden mögliche Decks.

Ich habe fünf Karten in der Hand - anscheinend spielen wir nicht Texas Hold 'Em. Angenommen, die Karten werden mir zugeteilt, eine zu Ihnen, eine zu mir, eine zu Ihnen und so weiter. Ich habe also die erste, dritte, fünfte, siebte und neunte Karte im Stapel.

Früher habe ich den Pseudo-Zufallszahlengenerator vier Milliarden Mal einmal mit jedem Samen ausgeführt und die erste Karte, die für jeden erzeugt wurde, in eine Datenbank geschrieben. Angenommen, meine erste Karte ist die Pik-Dame. Dies zeigt nur eine als erste Karte in jedem 52 dieser möglichen Decks. Daher haben wir die möglichen Decks von vier Milliarden auf etwa 80 Millionen reduziert.

Angenommen, meine zweite Karte ist die drei Herzen. Jetzt führe ich meinen RNG noch 80 Millionen Mal aus und benutze die 80 Millionen Samen, die als erste Nummer die Pikdame produzieren. Das dauert ein paar Sekunden. Ich schreibe alle Kartensätze auf, die die drei Herzen als dritte Karte erzeugen - die zweite Karte in meiner Hand. Das sind wiederum nur etwa 2% der Decks, jetzt sind wir nur noch 2 Millionen Decks.

Angenommen, die dritte Karte in meiner Hand ist die 7 der Vereine. Ich habe eine Datenbank mit 2 Millionen Samen, die meine zwei Karten verteilen. Ich führe meine RNG noch 2 Millionen Mal aus, um die 2% der Decks zu finden, die die 7 der Schläger als dritte Karte produzieren, und wir haben nur noch 40.000 Decks.

Sie sehen, wie das geht. Ich renne meine RNG 40000-mal mehr, um alle Samen zu finden, die meine vierte Karte produzieren, und das bringt uns auf 800 Decks, und dann noch 800 Mal, um die ~ 20 Samen zu bekommen, die meine fünfte Karte produzieren, und jetzt habe ich gerade Diese zwanzig Kartenstapel generieren und ich weiß, dass Sie eine von zwanzig möglichen Händen haben. Außerdem habe ich eine sehr gute Vorstellung davon, was ich als nächstes zeichnen werde.

Verstehst du jetzt, warum wahre Zufälligkeit wichtig ist? So wie Sie es beschreiben, denken Sie, dass die Verteilung wichtig ist, aber die Verteilung macht einen Prozess nicht zufällig. Unvorhersehbarkeit macht einen Prozess zufällig.

AKTUALISIEREN

Basierend auf den (jetzt aufgrund ihrer unkonstruktiven Natur gestrichenen) Kommentaren sind mindestens 0,3% der Menschen, die dies gelesen haben, verwirrt, was meinen Standpunkt angeht. Wenn Menschen gegen Punkte argumentieren habe ich nicht gemacht, oder noch schlimmer, argumentiert für Punkte, die ich habe auf der Annahme, dass ich sie nicht gemacht habe, dann weiß ich, dass ich mehr klar und sorgfältig erklären muß.

Es scheint eine besondere Verwirrung in Bezug auf die Wortverteilung zu geben , daher möchte ich die Verwendung sorgfältig nennen.

Die Fragen sind:

• Wie unterscheiden sich Pseudozufallszahlen und echte Zufallszahlen?
• Warum ist der Unterschied wichtig?
• Haben die Unterschiede etwas mit der Verteilung der Ausgabe des PRNG zu tun?

Beginnen wir mit dem perfekten Weg, ein beliebiges Kartenspiel zu generieren, mit dem man Poker spielen kann. Dann werden wir sehen, wie sich andere Techniken zum Erzeugen von Decks unterscheiden, und ob es möglich ist, diesen Unterschied zu nutzen.

Beginnen wir mit der Annahme, dass wir eine magische Box haben TRNG. Als Eingabe geben wir ihm eine ganze Zahl n, die größer oder gleich eins ist, und gibt als Ausgabe eine wirklich zufällige Zahl zwischen eins und n einschließlich an. Die Ausgabe der Box ist völlig unvorhersehbar (wenn eine andere Zahl als eine gegeben wird) und jede Zahl zwischen eins und n ist so wahrscheinlich wie eine andere; das heißt, die Verteilung ist einheitlich . (Es gibt andere fortgeschrittene statistische Überprüfungen der Zufälligkeit, die wir durchführen könnten; ich ignoriere diesen Punkt, da dies für meine Argumentation nicht von Belang ist.

Wir beginnen mit einem ungemischten Kartenspiel. Wir bitten die Box um eine Zahl zwischen eins und 52 - das heißt TRNG(52). Welche Zahl auch immer zurückgegeben wird, wir zählen so viele Karten aus unserem sortierten Stapel ab und entfernen diese Karte. Es wird die erste Karte im gemischten Deck. Dann fragen wir nach TRNG(51)und tun das Gleiche, um die zweite Karte auszuwählen und so weiter.

Ein anderer Blickwinkel ist: Es gibt 52! = 52 x 51 x 50 ... x 2 x 1 mögliche Decks, was ungefähr 2 ^{226 entspricht} . Wir haben einen von ihnen zufällig ausgewählt.

Jetzt geben wir die Karten aus. Wenn ich mir meine Karten anschaue, habe ich keine Ahnung, welche Karten Sie haben. (Abgesehen von der offensichtlichen Tatsache, dass Sie keine der Karten haben, die ich besitze.) Dies könnten beliebige Karten sein, mit gleicher Wahrscheinlichkeit.

Lassen Sie mich also sicherstellen, dass ich das klar erkläre. Wir haben eine gleichmäßige Verteilung jedes einzelnen Outputs von TRNG(n); Jeder wählt mit der Wahrscheinlichkeit 1 / n eine Zahl zwischen 1 und n aus. Das Ergebnis dieses Prozesses ist, dass wir eine von 52 ausgewählt haben! möglich Decks mit einer Wahrscheinlichkeit von 1/52 !, so die Verteilung über die Menge der möglichen Decks sind auch einheitlich.

Gut.

Nehmen wir an, wir haben eine weniger magische Box, die mit einem Label versehen ist PRNG. Bevor Sie es verwenden können, müssen sie werden ausgesät mit einem 32 - Bit - Zahl ohne Vorzeichen.

ASIDE: Warum 32 ? Könnte es nicht mit einer 64-, 256- oder 10000-Bit-Zahl gesetzt werden? Sicher. Aber (1) in der Praxis werden die meisten handelsüblichen PRNGs mit einer 32-Bit-Zahl ausgesät, und (2) wenn Sie 10000 zufällige Bits haben, um den Samen zu erstellen, warum verwenden Sie dann überhaupt einen PRNG? Sie haben bereits eine Zufallsquelle von 10000 Bits!

Wie auch immer, zurück zur Funktionsweise des PRNG: Nachdem es ausgesät wurde, können Sie es auf dieselbe Weise verwenden, wie Sie es verwenden TRNG. Das heißt, Sie übergeben eine Zahl n, und Sie erhalten eine Zahl zwischen 1 und n einschließlich. Darüber hinaus ist die Verteilung dieser Leistung mehr oder weniger einheitlich . Das heißt, wenn wir PRNGnach einer Zahl zwischen 1 und 6 fragen, erhalten wir 1, 2, 3, 4, 5 oder 6 in etwa einem Sechstel der Zeit, unabhängig davon, was der Samen war.

Ich möchte diesen Punkt mehrmals betonen, weil es scheint, dass einige Kommentatoren verwirrt werden. Die Verteilung des PRNG ist auf mindestens zwei Arten einheitlich. Angenommen, wir wählen einen bestimmten Samen aus. Wir würden erwarten, dass die Sequenz PRNG(6), PRNG(6), PRNG(6)...eine Million Mal zu einer einheitlichen Verteilung der Zahlen zwischen 1 und 6 führen würde. Und zweitens würden wir, wenn wir eine Million verschiedene Samen auswählen und PRNG(6) einmal für jeden Samen aufrufen, eine gleichmäßige Verteilung der Zahlen von 1 bis 6 erwarten 6. Die Einheitlichkeit des PRNG über eine dieser Operationen ist für den von mir beschriebenen Angriff nicht relevant .

Es wird gesagt, dass dieser Prozess pseudo-zufällig ist, da das Verhalten der Box tatsächlich vollständig deterministisch ist. Es wählt aus 2 ³² möglichen Verhaltensweisen, die auf dem Samen basieren. Das heißt, sobald es ausgesät wurde, PRNG(6), PRNG(6), PRNG(6), ... wird eine Folge von Zahlen mit einer gleichmäßigen Verteilung erzeugt, die jedoch vollständig vom Samen bestimmt wird. Für eine bestimmte Folge von Anrufen, beispielsweise PRNG (52), PRNG (51) ... und so weiter, gibt es nur 2 ³² mögliche Folgen. Der Samen wählt im Wesentlichen den, den wir bekommen.

Um ein Deck zu generieren, generiert der Server jetzt einen Startwert. (Wie? Wir kommen zu diesem Punkt zurück.) Dann rufen sie PRNG(52)an PRNG(51)und so weiter, um das Deck zu generieren, ähnlich wie zuvor.

Dieses System ist anfällig für den von mir beschriebenen Angriff. Um den Server anzugreifen, säen wir vorab unsere eigene Kopie der Box mit 0 und bitten PRNG(52)und notieren diese. Dann keimen wir wieder mit 1, fragen nach PRNG(52)und schreiben das auf bis zu 2 ³² -1.

Nun muss der Pokerserver, der PRNG zum Generieren von Decks verwendet, irgendwie einen Samen generieren. Es ist egal, wie sie das tun. Sie könnten anrufen TRNG(2^32), um einen wirklich zufälligen Samen zu erhalten. Oder sie könnten die gegenwärtige Zeit als Samen nehmen, was kaum zufällig ist; Ich weiß wie viel Uhr es ist. Der Punkt meines Angriffs ist, dass es keine Rolle spielt, weil ich meine Datenbank habe . Wenn ich meine erste Karte sehe, kann ich 98% der möglichen Samen entfernen. Wenn ich meine zweite Karte sehe, kann ich 98% mehr eliminieren und so weiter, bis ich schließlich eine Handvoll möglicher Samen finden kann und mit hoher Wahrscheinlichkeit weiß, was in Ihrer Hand liegt.

Nun möchte ich noch einmal betonen, dass hier davon ausgegangen wird, dass wirPRNG(6), wenn wir eine Million Mal anrufen würden, jede Zahl ungefähr ein Sechstel der Zeit erhalten würden . Diese Verteilung ist (mehr oder weniger) einheitlich, und wenn Sie sich nur für die Einheitlichkeit dieser Verteilung interessieren, ist das in Ordnung. Die Frage der Frage war, ob es andere Dinge gibt, die sich um die Verteilung von PRNG(6)uns kümmern. und die Antwort lautet ja . Wir kümmern uns auch um Unvorhersehbarkeit .

Eine andere Möglichkeit, das Problem zu betrachten, besteht darin, dass die Verteilung von einer Million Anrufen zwar in PRNG(6)Ordnung sein kann, da der PRNG jedoch nur 2 ³² mögliche Verhaltensweisen auswählt, nicht jedes mögliche Deck erzeugen kann. Es kann nur 2 ³² der 2 ²²⁶ möglichen Decks erzeugen ; ein winziger Bruchteil. Die Verteilung über alle Decks hinweg ist also sehr schlecht. Der fundamentale Angriff basiert jedoch darauf, dass wir das vergangene und zukünftige Verhalten von einer kleinen Stichprobe seiner Leistung erfolgreich vorhersagen könnenPRNG .

Lassen Sie mich dies ein drittes oder vier Mal sagen, um sicherzustellen, dass dies einbricht. Hier gibt es drei Distributionen. Zunächst die Verteilung des Prozesses, der den zufälligen 32-Bit-Startwert erzeugt. Das kann völlig zufällig, unvorhersehbar und einheitlich sein und der Angriff wird trotzdem funktionieren . Zweitens, die Verteilung von einer Million Anrufe nach PRNG(6). Das kann vollkommen gleichförmig sein und der Angriff wird noch funktionieren. Drittens die Verteilung der Decks, die durch den Pseudozufallsprozess ausgewählt wurde, den ich beschrieben habe. Diese Verteilung ist extrem schlecht; Möglicherweise kann nur ein winziger Bruchteil der möglichen IRL-Decks ausgewählt werden. Der Angriff hängt von der Vorhersagbarkeit des Verhaltens des PRNG ab, basierend auf der teilweisen Kenntnis seiner Ausgabe .

ASIDE: Dieser Angriff setzt voraus, dass der Angreifer den genauen Algorithmus des PRNG kennt oder erraten kann. Ob das realistisch ist oder nicht, ist eine offene Frage. Allerdings, wenn ein Sicherheitssystem entwerfen Sie entwerfen müssen sie sicher vor Angriffen sein, auch wenn der Angreifer alle Algorithmen im Programm kennt . Anders ausgedrückt: Der Teil eines Sicherheitssystems, der für die Sicherheit des Systems geheim bleiben muss, wird als "Schlüssel" bezeichnet. Wenn Ihr System für die Sicherheit von den verwendeten Algorithmen als geheim abhängt, enthält Ihr Schlüssel diese Algorithmen . Das ist eine extrem schwache Position!

Weitermachen

Nehmen wir an, wir haben eine dritte beschriftete Box CPRNG. Es ist eine Krypto-Version von PRNG. Es ist ein 256-Bit-Startwert und kein 32-Bit-Startwert erforderlich. Es teilt mit PRNGder Eigenschaft, die das Saatgut aus 2 ²⁵⁶ möglichen Verhaltensweisen auswählt . Und wie unsere anderen Maschinen hat es die Eigenschaft, dass eine große Anzahl von Aufrufen CPRNG(n)eine einheitliche Ergebnisverteilung zwischen 1 und n erzeugt: Jede 1 / n der Zeit passiert. Können wir unseren Angriff dagegen ausführen?

Unser ursprünglicher Angriff erfordert, dass wir 2 ³² Zuordnungen von Samen zu speichern PRNG(52). Aber 2 ²⁵⁶ ist eine viel größere Zahl. Es ist völlig unmöglich CPRNG(52), so viele Male auszuführen und die Ergebnisse zu speichern.

Aber nehmen wir an, es gibt einen anderen Weg, um den Wert von CPRNG(52)Saatgut zu ermitteln und daraus eine Tatsache abzuleiten. Wir waren bisher ziemlich dumm und haben alle möglichen Kombinationen brutal erzwungen. Können wir in die magische Box hineinschauen, herausfinden, wie es funktioniert, und anhand der Ausgabe Fakten über den Samen ableiten?

Nein . Die Details sind zu kompliziert zu erklären, aber CPRNGs sind geschickt so konstruiert, dass es unmöglich ist, abzuleiten, jede nützliche Tatsache über die Samen aus dem ersten Ausgang CPRNG(52)oder von jeder Teilmenge des Ausgangs, egal wie groß .

OK, also nehmen wir an, der Server verwendet CPRNG, um Decks zu generieren. Es braucht einen 256-Bit-Startwert. Wie wählt es diesen Samen? Wenn ein Wert ausgewählt wird, den ein Angreifer vorhersagen kann, wird der Angriff plötzlich wieder funktionsfähig . Wenn wir feststellen können, dass von den 2 ²⁵⁶ möglichen Startwerten wahrscheinlich nur vier Milliarden vom Server ausgewählt werden, sind wir wieder im Geschäft . Wir können diesen Angriff erneut durchführen, wobei wir nur auf die geringe Anzahl von Samen achten, die möglich ist.

Der Server sollte daher dafür sorgen, dass die 256-Bit-Zahl gleichmäßig verteilt ist, dh jeder mögliche Startwert wird mit einer Wahrscheinlichkeit von 1/2 ^{256 gewählt} . Grundsätzlich sollte der Server anrufen TRNG(2^256)-1, um den Seed für zu erzeugen CPRNG.

Was ist, wenn ich den Server hacken und hineinschauen kann, um zu sehen, welcher Samen ausgewählt wurde? In diesem Fall kennt der Angreifer die vollständige Vergangenheit und Zukunft des CPRNG . Der Autor des Servers muss sich vor diesem Angriff schützen! (Natürlich, wenn ich diesen Angriff erfolgreich bestreiten kann, kann ich das Geld wahrscheinlich auch direkt auf mein Bankkonto überweisen, daher ist das vielleicht nicht so interessant.) Punkt ist: Der Samen muss ein schwer zu erratendes Geheimnis sein, und ein wirklich zufällige 256-Bit-Zahl ist ziemlich schwer zu erraten.)

Um zu meinem früheren Punkt über Tiefenverteidigung zurückzukommen: Der 256-Bit-Startwert ist der Schlüssel zu diesem Sicherheitssystem. Die Idee eines CPRNG ist, dass das System sicher ist, solange der Schlüssel sicher ist . Selbst wenn jede andere Tatsache über den Algorithmus bekannt ist, sind die Karten des Gegners nicht vorhersagbar, solange Sie den Schlüssel geheim halten können.

Okay, der Samen sollte sowohl geheim als auch gleichmäßig verteilt sein, denn wenn dies nicht der Fall ist, können wir einen Angriff starten. Wir gehen davon aus, dass die Verteilung der Outputs von CPRNG(n)einheitlich ist. Wie sieht es mit der Verteilung aller möglichen Decks aus?

Man könnte sagen: Es gibt 2 ²⁵⁶ mögliche Sequenzen, die vom CPRNG ausgegeben werden, aber es gibt nur 2 ²²⁶ mögliche Decks. Daher gibt es mehr mögliche Sequenzen als Decks, also geht es uns gut. Jedes mögliche-IRL-Deck ist jetzt (mit hoher Wahrscheinlichkeit) in diesem System möglich. Und das ist ein gutes Argument außer ...

2 ²²⁶ ist nur eine Annäherung von 52 !. Teilen Sie es aus. 2 ^256/52 ! kann unmöglich eine ganze Zahl sein, weil zum einen 52! ist durch 3 teilbar aber keine Zweierpotenz ist! Da dies jetzt keine ganze Zahl ist, haben wir die Situation, dass alle Decks möglich sind, aber einige Decks sind wahrscheinlicher als andere .

Wenn dies nicht klar ist, betrachten Sie die Situation mit kleineren Zahlen. Nehmen wir an, wir haben drei Karten, A, B und C. Nehmen wir an, wir verwenden ein PRNG mit einem 8-Bit-Samen, also gibt es 256 mögliche Samen. Es gibt 256 mögliche Ausgaben von PRNG(3)je nach Seed; Es gibt keine Möglichkeit, dass ein Drittel von ihnen A ist, ein Drittel von ihnen B und ein Drittel von ihnen C, weil 256 nicht gleichmäßig durch 3 teilbar ist.

Ebenso teilt sich 52 nicht gleichmäßig in 2 ^{256 auf}, so dass bei der ersten gewählten Karte einige Karten und bei anderen Karten eine Abweichung vorhanden sein muss.

In unserem ursprünglichen System mit einem 32-Bit-Saatgut gab es eine massive Neigung, und die große Mehrheit der möglichen Decks wurde nie produziert. In diesem System können alle Decks hergestellt werden, die Verteilung der Decks ist jedoch immer noch fehlerhaft . Einige Decks sind etwas wahrscheinlicher als andere.

Jetzt ist die Frage: Haben wir einen Angriff, der auf diesem Fehler basiert? und die Antwort ist in der Praxis wahrscheinlich nicht . CPRNGs sind so konzipiert, dass, wenn der Samen wirklich zufällig ist, es rechnerisch unmöglich ist, den Unterschied zwischen CPRNGund zu erkennen TRNG.

OK, also zusammenfassend.

Wie unterscheiden sich Pseudozufallszahlen und echte Zufallszahlen?

Sie unterscheiden sich in der Vorhersagbarkeit.

• Wirklich zufällige Zahlen sind nicht vorhersehbar.
• Alle Pseudozufallszahlen sind vorhersagbar, wenn der Samen bestimmt oder erraten werden kann.

Warum ist der Unterschied wichtig?

Denn es gibt Anwendungen, bei denen die Sicherheit des Systems von Unvorhersehbarkeit abhängt .

• Wenn ein TRNG zur Auswahl jeder Karte verwendet wird, ist das System nicht verfügbar.
• Wenn eine CPRNG zur Auswahl jeder Karte verwendet wird, ist das System sicher, wenn der Startwert sowohl unvorhersehbar als auch unbekannt ist.
• Wenn ein gewöhnlicher PRNG mit einem kleinen Saatplatz verwendet wird, ist das System nicht sicher, unabhängig davon, ob der Saatgut unvorhersehbar oder unbekannt ist. ein ausreichend kleiner Saatraum ist anfällig für brutale Angriffe der von mir beschriebenen Art.

Hat der Unterschied etwas mit der Verteilung der Ausgabe des PRNG zu tun?

Die Gleichmäßigkeit der Verteilung oder deren Fehlen für einzelne Anrufe zu RNG(n)ist nicht relevant für die Angriffe ich beschrieben habe.

Wie wir gesehen haben, erzeugen sowohl a PRNGals CPRNGauch arme Distibutionen der Wahrscheinlichkeit, ein einzelnes Deck aller möglichen Decks zu wählen. Das PRNGist wesentlich schlechter, aber beide haben Probleme.

Noch eine Frage:

Wenn TRNG so viel besser ist als CPRNG, was wiederum viel besser als PRNG ist, warum werden dann CPRNG oder PRNG verwendet?

Zwei Gründe.

Erstens: Aufwand. TRNG ist teuer . Es ist schwierig, wirklich zufällige Zahlen zu erzeugen. CPRNGs liefern gute Ergebnisse für beliebig viele Anrufe mit nur einem Aufruf von TRNG für den Seed. Der Nachteil ist natürlich, dass Sie diesen Samen geheim halten müssen .

Zweitens: Manchmal wollen wir Vorhersehbarkeit und alles, was uns wichtig ist, ist eine gute Verteilung. Wenn Sie "zufällige" Daten als Programmeingaben für eine Testsuite generieren und ein Fehler angezeigt wird, wäre es schön, wenn Sie die Testsuite erneut ausführen, um den Fehler erneut zu erzeugen.

Ich hoffe das ist jetzt viel klarer.

Wenn Ihnen dies gefallen hat, können Sie sich über das Thema Zufälligkeit und Permutationen informieren.

• Angenommen, ich habe Zufallsdaten gleichmäßig verteilt. Wie kann ich es in eine bestimmte ungleichmäßige Verteilung umwandeln?
• Warum werden einige GUIDs zufällig generiert? Sind alle ihre Bits zufällig? (Nein.) Kann ich mich auf eine GUID als Quelle wahrer Zufälligkeit verlassen? (Nein!)
• Wie kann ich mithilfe der faktoradischen Notation große Zufallszahlen generieren?
  • Wie kann ich daraus eine zufällige Permutation machen?
• Wie können wir den hier beschriebenen Angriff gegen die zufällige Permutation durchführen?
• Wie viel Voreingenommenheit wird durch die Implementierung der Resttechnik eingeführt RNG(n)?

Wie Eric Lippert sagt, ist es nicht nur der Vertrieb. Es gibt andere Möglichkeiten, die Zufälligkeit zu messen.

Einer der frühen Zufallszahlengeneratoren hat eine Sequenz im niedrigstwertigen Bit - er hat 0 und 1 abgewechselt. Daher war das LSB zu 100% vorhersehbar. Aber Sie müssen sich um mehr Sorgen machen. Jedes Bit muss unvorhersehbar sein.

Hier ist ein guter Weg, um über das Problem nachzudenken. Nehmen wir an, Sie erzeugen 64 Bit Zufälligkeit. Nimm für jedes Ergebnis die ersten 32 Bits (A) und die letzten 32 Bits (B) und mache einen Index in ein Array x [A, B]. Führen Sie den Test nun eine Million Mal durch, und erhöhen Sie für jedes Ergebnis das Array um diese Nummer, dh X [A, B] ++;

Zeichnen Sie nun ein 2D-Diagramm. Je größer die Zahl, desto heller ist das Pixel an dieser Stelle.

Wenn es wirklich zufällig ist, sollte die Farbe ein einheitliches Grau sein. Aber du könntest Muster bekommen. Nehmen Sie zum Beispiel dieses Diagramm der "Zufälligkeit" in der TCP-Sequenznummer des Windows NT-Systems:

oder auch dieses von Windows 98:

Und hier ist die Zufälligkeit der Implementierung des Cisco-Routers (IOS).

Diese Diagramme stammen von Michał Zalewskis Zeitung . Wenn man in diesem speziellen Fall vorhersagen kann, welche TCP-Sequenznummer ein System sein wird, kann man sich beim Herstellen einer Verbindung zu einem anderen System als das ausgeben, was das Hijacking von Verbindungen, das Abfangen der Kommunikation usw. ermöglichen würde. Und selbst wenn Die nächste Zahl kann nicht zu 100% vorhergesagt werden. Wenn wir unter unserer Kontrolle eine neue Verbindung herstellen können, können wir die Erfolgschancen erhöhen. Und wenn Computer in wenigen Sekunden 100.000 Verbindungen herstellen können, steigt die Wahrscheinlichkeit eines erfolgreichen Angriffs von astronomisch bis möglich oder sogar wahrscheinlich.

Während Pseudo- Zufallszahlen, die von Computern generiert werden, für die meisten Anwendungsfälle von Computerbenutzern akzeptabel sind, gibt es Szenarien, in denen völlig unvorhersehbare Zufallszahlen erforderlich sind.

In sicherheitsrelevanten Anwendungen wie Verschlüsselung kann ein Pseudozufallszahlengenerator (PRNG) Werte erzeugen, die, obwohl sie zufällig erscheinen, tatsächlich von einem Angreifer vorhersagbar sind. Jemand, der versucht, ein Verschlüsselungssystem zu knacken, kann möglicherweise die Verschlüsselungsschlüssel erraten, wenn ein PRNG verwendet wurde und der Angreifer Informationen zum Status des PRNG hat. Für solche Anwendungen ist daher ein Zufallszahlengenerator erforderlich, der wirklich nicht ermittelbare Werte erzeugt. Beachten Sie, dass einige PRNGs kryptografisch sicher sind und für solche sicherheitsrelevanten Anwendungen verwendet werden können.

Weitere Informationen zu RNG-Angriffen finden Sie in diesem Wikipedia-Artikel .

Ich habe es in Python ausprobiert: Hier ist das Ergebnis von 60 Millionen Rollen. Die höchste Abweichung liegt bei 0,15. Ist das nicht so zufällig wie es wird?

Eigentlich ist es so "gut", es ist schlecht ... Alle vorliegenden Antworten konzentrieren sich auf die Vorhersagbarkeit bei einer kleinen Folge von Anfangswerten. Ich möchte ein anderes Problem ansprechen:

    Ihre Distribution hat eine viel kleinere Standardabweichung als zufällige Rollen

Echte Zufälligkeit kommt nur nicht ganz, dass die Nähe „fast genau 1 über wie immer viele Zahlen sie können wählen, von“ zu durchschnittlich, dass man als Hinweis auf der Qualität verwenden.

Wenn Sie sich diese Stack Exchange-Frage zu Wahrscheinlichkeitsverteilungen für mehrere Würfel ansehen, wird eine Formel für die Standardabweichung von N Würfeln angezeigt (unter der Annahme, dass zufällige Ergebnisse erzielt werden):

 sqrt(N * 35.0 / 12.0). 

Mit dieser Formel wird die Standardabweichung für:

• 1 Million Rollen ist 1708
• 60 Millionen Rollen sind 13229

Wenn wir uns Ihre Ergebnisse ansehen:

• 1 Million Rollen: stddev (1000066, 999666, 1001523, 999452, 999294, 999999) ist 804
• 60 Millionen Rollen: stddev (9997653, 9997789, 9996853, 10006533, 10002774, 9998398) ist 3827

Man kann nicht erwarten, dass die Standardabweichung eines endlichen Musters genau der Formel entspricht, aber sie sollte ziemlich nahe kommen. Bei 1 Million Würfeln haben Sie jedoch weniger als die Hälfte des richtigen Stddev und bei 60 Millionen liegen Sie unter einem Drittel - es wird schlimmer und das ist kein Zufall.

Pseudo-RNGs neigen dazu, sich durch eine Reihe unterschiedlicher Zahlen zu bewegen, angefangen mit dem Startwert und nicht für einen bestimmten Zeitraum. Zum Beispiel haben Implementierungen der alten C-Bibliotheksfunktion rand()üblicherweise eine Periode von 2 ^ 32, und sie werden jede Zahl zwischen 0 und 2 ^ 32-1 genau einmal besuchen, bevor sie den Seed wiederholen. Wenn Sie also 2 ^ 32 Würfel simulieren, wird der Vormodul (%) Die Ergebnisse würden jede Zahl von 0 bis 2 ^ 32 einschließen, die Zählungen für jedes 1-6 Ergebnis wären 715827883 oder 715827882 (2 ^ 32 ist kein Vielfaches von 6) und die Standardabweichung ist daher nur trivial über 0. Verwendung von In der obigen Formel lautet die korrekte Standardabweichung für 2 ^ 32-Rollen 111924. Wenn sich jedoch die Anzahl der Pseudo-Zufallsrollen erhöht, konvergieren Sie gegen 0 Standardabweichung. Es kann erwartet werden, dass das Problem signifikant ist, wenn die Anzahl der Walzen einen signifikanten Bruchteil der Periode ausmacht. Einige Pseudo-RNGs können jedoch schlechtere Probleme oder sogar Probleme mit weniger Proben aufweisen als andere.

Selbst wenn Sie sich nicht für kryptografische Schwachstellen interessieren, können Sie sich in einigen Anwendungen darum kümmern, Distributionen zu haben, die keine übermäßigen, künstlich sogar Ergebnisse haben. Einige Simulationstypen versuchen ganz konkret, die Konsequenzen der ungleichmäßigen Ergebnisse zu ermitteln, die bei großen Stichproben von zufällig ausgewählten Ergebnissen natürlich auftreten, aber in einigen pRNG-Ergebnissen sind sie unterrepräsentiert. Wenn Sie versuchen zu simulieren, wie eine riesige Bevölkerung auf ein Ereignis reagiert, könnte dieses Problem Ihre Ergebnisse radikal verändern und zu ungenauen Schlussfolgerungen führen.

Um ein konkretes Beispiel zu geben: Ein Mathematiker sagt einem Poker-Automaten-Programmierer, dass nach 60 Millionen simulierten Würfeln hunderte von kleinen "Lichtern" über den Bildschirm flackerten, falls es 10.013.229 oder mehr Sixes gab, was der Mathematiker erwartet 1 stddev von Mean, sollte es eine kleine Auszahlung geben. Per der 68-95-99.7 Regel (Wikipedia) soll etwa geschehen 16% der Zeit (~ 68% fällt in einer Standardabweichung / nur die Hälfte außerhalb ist oben). Bei Ihrem Zufallszahlengenerator liegt dieser ab ca. 3,5 Standardabweichungen über dem Mittelwert: Unter 0,025% Chance - fast kein Kunde bekommt diesen Vorteil. Siehe die Tabelle "Höhere Abweichungen" auf der gerade genannten Seite.

| Range | In range | Outside range | Approx. freq. for daily event | | µ ± 1σ | 0.68268... | 1 in 3 | Twice a week | | µ ± 3.5σ | 0.99953... | 1 in 2149 | Every six years | 

Ich habe gerade diesen Zufallszahlengenerator geschrieben, um Würfelrollen zu erzeugen

def get_generator(): next = 1 def generator(): next += 1 if next > 6: next = 1 return next return generator 

Du verwendest es so

>> generator = get_generator() >> generator() 1 >> generator() 2 >> generator() 3 >> generator() 4 >> generator() 5 >> generator() 6 >> generator() 1 

usw. usw. Würden Sie diesen Generator gerne für ein Programm verwenden, das ein Würfelspiel lief? Denken Sie daran, dass die Verteilung genau das ist, was Sie von einem "wirklich zufälligen" Generator erwarten würden!

Pseudo-Zufallszahlengeneratoren machen im Wesentlichen dasselbe - sie erzeugen vorhersagbare Zahlen mit der richtigen Verteilung. Sie sind aus dem gleichen Grund schlecht, aus dem der obige einfache Zufallszahlengenerator schlecht ist - sie sind nicht für Situationen geeignet, in denen Sie echte Unvorhersehbarkeit benötigen, nicht nur die korrekte Verteilung.

Die Zufallszahlengenerierung, die Ihr Computer ausführen kann, ist für die meisten Anforderungen geeignet, und Sie werden wahrscheinlich nicht auf eine Zeit stoßen, in der Sie eine wirklich zufällige Zahl benötigen.

Echte Zufallszahlengenerierung hat jedoch ihre Zwecke. In der Computersicherheit, beim Glücksspiel, bei großen statistischen Stichproben usw.

Wenn Sie sich für die Anwendung von Zufallszahlen interessieren, lesen Sie den Wikipedia-Artikel .

Die von typischen Funktionen in den meisten Programmiersprachen erzeugten Zufallszahlen sind keine reinen Zufallszahlen. Sie sind Pseudo-Zufallszahlen. Da es sich nicht nur um Zufallszahlen handelt, können sie mit ausreichenden Informationen zu zuvor erzeugten Zahlen erraten werden. Dies ist also eine Katastrophe für die Sicherheit in der Kryptographie .

Für ein Beispiel erzeugt die folgende Zufallszahlengeneratorfunktion glibckeine rein zufällige Zahl. Die dadurch generierte Pseudo-Zufallszahl kann erraten werden. Es ist ein Fehler in Sicherheitsfragen. Es gibt eine Geschichte, in der dies katastrophal wird. Dies sollte nicht in der Kryptographie verwendet werden.

glibc random(): r[i] ← ( r[i-3] + r[i-31] ) % (2^32) output r[i] >> 1 

Diese Art von Pseudo-Zufallszahlengenerator sollte niemals an sicherheitsrelevanten Orten verwendet werden, auch wenn diese statistisch weitreichend sind.

Einer der berühmten Angriffe auf Pseudo-Zufallsschlüssel ist der Angriff auf 802.11b WEP . WEP hat einen 104-Bit-Langzeitschlüssel, der mit 24-Bit-IV (Zähler) verkettet ist, um einen 128-Bit-Schlüssel zu erstellen, der wiederum auf den RC4-Algorithmus angewendet wird, um einen Pseudozufallsschlüssel zu erzeugen.

( RC4( IV + Key ) ) XOR (message) 

Die Schlüssel waren eng miteinander verbunden. Hier nahm nur IV in jedem Schritt um 1 zu und alle anderen blieben gleich. Da dies nicht rein zufällig war, war es verheerend und konnte leicht abgebaut werden. Der Schlüssel könnte durch die Analyse von etwa 40000 Frames wiederhergestellt werden, was die Angelegenheit von Minuten ist. Wenn das WEP rein zufällige 24-Bit-IV-Werte verwendet, könnte es bis ungefähr 2 ^ 24 (fast 16,8 Millionen) Frames sicher sein.

Daher sollte man, wenn möglich, mit reinem Zufallszahlengenerator in sicherheitsrelevanten Themen arbeiten.

Der Unterschied besteht darin, dass pseudozufällige Zahlen nach einiger Zeit vorhersagbar sind (sich wiederholen), während echte Zufallszahlen keine sind. Die Wiederholungsdauer hängt von der Länge des Saatguts ab, das für seine Erzeugung verwendet wird.

Hier ist ein ziemlich schönes Video zu diesem Thema: http://www.youtube.com/watch?v=itaMNuWLzJo

Angenommen, eine Pseudo-Zufallszahl kann von jedem erraten werden, bevor sie generiert wird.

Für triviale Anwendungen ist eine Pseudo-Zufälligkeit in Ordnung, wie in Ihrem Beispiel erhalten Sie ungefähr den richtigen Prozentsatz (ungefähr 1/6 des Gesamtergebnisses) mit geringfügigen Abweichungen (was Sie sehen würden, wenn Sie einen Würfel mit 600k würfeln würden) mal);

Wenn es jedoch um Dinge wie Computersicherheit geht; Wahre Zufälligkeit ist erforderlich.

Beispielsweise beginnt der RSA-Algorithmus damit, dass der Computer zwei Zufallszahlen (P und Q) auswählt und dann mehrere Schritte zu diesen Nummern ausführt, um die speziellen Nummern zu generieren, die als öffentliche und private Schlüssel bezeichnet werden. (Der wichtige Teil eines privaten Schlüssels ist, dass er privat ist und niemand anders es weiß!)

Wenn ein Angreifer wissen kann, welche zwei "zufälligen" Zahlen Ihr Computer auswählen wird, können Sie dieselben Schritte ausführen, um Ihren privaten Schlüssel zu berechnen (den, den niemand sonst wissen sollte!)

Mit Ihrem privaten Schlüssel kann ein Angreifer Folgendes tun: a) Sprechen Sie mit Ihrer Bank und geben Sie so aus, als seien Sie Sie. B) Hören Sie Ihren sicheren Internetverkehr und können Sie ihn entschlüsseln.

Das ist, wo echte Zufälligkeit (dh nicht erraten werden kann) erforderlich ist.

Die erste Zufallszahl, die ich je verwendete, hatte die ausgezeichnete Eigenschaft, dass von zwei aufeinanderfolgenden Zufallszahlen die zweite mit einer Wahrscheinlichkeit von 0,6 größer war. Nicht 0,5. Und der dritte war mit der Wahrscheinlichkeit 0,6 größer als der zweite und so weiter. Sie können sich vorstellen, wie das mit einer Simulation Chaos spielt.

Einige Leute würden mir nicht glauben, dass dies sogar möglich war, wenn die Zufallszahlen gleich verteilt waren, aber es ist offensichtlich möglich, wenn Sie die Reihenfolge betrachten (1, 3, 5, 2, 4, 1, 3, 5, 2, 4, ...) wobei die zweite von zwei Zahlen mit Wahrscheinlichkeit 0,6 größer ist.

Auf der anderen Seite kann es für Simulationen wichtig sein, Zufallszahlen reproduzieren zu können. Nehmen wir an, Sie führen eine Verkehrssimulation durch und möchten herausfinden, wie einige Aktionen den Verkehr verbessern können. In diesem Fall möchten Sie in der Lage sein, dieselben Verkehrsdaten (z. B. Leute, die versuchen, eine Stadt zu betreten) mit verschiedenen Aktionen, die Sie zur Verbesserung des Verkehrs verwendet haben, neu zu erstellen.