Frage:
Is a concatenation of random numbers better than a single random number?
topher
2016-05-23 21:24:06 UTC
view on stackexchange narkive permalink

Wir generieren Zufallszahlen mit einer Länge von 16 Stellen. Eine Option, die vorgeschlagen wurde, bestand darin, vier Zufallszahlen mit jeweils 4 Ziffern zu generieren und diese zu verketten, anstatt nur eine einzelne 16-stellige Zufallszahl zu generieren. Der Grund für den Vorschlag war, dass es schwieriger ist, die nächste Zahl vorherzusagen, falls ein Problem mit dem Zufallszahlengenerator auftritt.

Ist die verkettete Zufallszahl also besser als eine einzelne Zufallszahl?

Abhängig davon, wie Ihr Pseudozufallszahlengenerator implementiert ist, erhalten Sie möglicherweise mit beiden Methoden dieselbe Nummer.
Wenn nur eine "einfache Verkettung" vorgenommen wird, kann dies sogar noch schwächer sein als die Verwendung von 16 Ziffern.Wenn Sie jedoch die nächsten 4 Ziffern als Teil eines Seeds oder als Teil der Verschlüsselungsmethode verwenden, erhöht dies die Entropie und Sicherheit.
@nwildner Ich bin gespannt, wie könnte es das RNG noch schwächer machen?Ich verstehe, dass die Zufälligkeit nicht zunehmen konnte, aber ich sehe nicht, wie sie abnehmen könnte.
@nwildner Könnten Sie das "wird die Entropie und Sicherheit weiter erhöhen" weiter erklären?
Weil 4 Zahlen mit 4 Ziffern (dezimal) "10 ^ n + 10 ^ n + 10 ^ n + 10 ^ n = 10 ^ n + 1 + 10 ^ n + 1 = 10 ^ n + 2 = 10 ^ 6" sindzu praktisch Bruteforce, während 16-stellig "10 ^ 16" sein wird - http://crypto.stackexchange.com/questions/18591/entropy-of-two-concatenated-random-values
@nwildner Ihre Mathematik ist falsch: `10 ^ n + 10 ^ n + 10 ^ n + 10 ^ n = 4 (10 ^ n)`.Auch alle 3 Antworten in dieser Frage besagen, dass die Behauptung des Autors falsch ist.
@nwildner Die am häufigsten gewählte Antwort auf die von Ihnen erwähnte Frage lautet eindeutig: "Die Verkettung unabhängiger Zeichenfolgen mit der Entropie n, m ergibt eine Zeichenfolge mit der Entropie n + m, Punkt."
Dann bin ich einfach falsch.Es tut uns leid.
Interessieren Sie sich für * statistische Zufälligkeit *?Was Sie beschreiben, ähnelt dem Erzeugen von Punkten in einem 4D-Raum (eine Zahl pro Koordinate).Während ein ** PRNG ** gleichmäßig verteilt sein kann, wenn seine Ausgabe als 1D betrachtet wird, muss es ** nicht ** gleichmäßig verteilt sein, wenn Sie das tun, was Sie beschreiben, dh die 4D-Punkte können Cluster bilden oder in jedem Fall nicht gleichmäßig verteilt sein, wenngesehen als Punkte in diesem 4D Raum.
[Dieses Video analysiert, wie der Zufallszahlengenerator in Super Mario 64 funktioniert.] (Https://youtu.be/MiuLeTE2MeQ?t=11m47s) Es ist nicht das ernsteste Video, aber an einem Punkt macht der Ersteller des Videos eine interessante Beobachtung: Das speziell verwendete RNG erzeugt ungefähr 65000 verschiedene Zufallszahlen, erzeugt sie jedoch konsistent in derselben Reihenfolge.Wenn "n" -Nummern nacheinander ausgewählt werden, gibt es daher * keine * 65000 ^ n "möglichen Ergebnisse - es gibt nur" 65000 "mögliche Ergebnisse, unabhängig von" n "!Ob Ihr RNG das gleiche Problem hat oder nicht, hängt von Ihrer Implementierung ab.
@nwildner Es sieht so aus, als würden Sie Addition mit Multiplikation verwechseln."10 * 10 ^ n = 10 ^ 1 * 10 ^ n = 10 ^ (1 + n)".Exponenten addieren sich, wenn Sie mit Zahlen mit derselben Basis multiplizieren.(Das heißt, "x ^ n * x ^ m = x ^ (n + m)" für jedes echte "x", "n", "m".)
Mein Bauchgefühl besagt, dass wenn ich drei Zufallsgeneratoren habe, von denen nur einer kryptografisch sicher ist, die XOR-Verknüpfung aller Werte immer noch eine gute Zufallszahl ergeben sollte, da wir nur dann einen schlechten erhalten könnten, wenn der Zustand des guten RNGwar mit den anderen verbunden.
@Kevin die meisten PRNG arbeiten so.Sie haben eine Sequenz, und der Startwert bestimmt, wo in der Sequenz Sie beginnen.
Drei antworten:
Steffen Ullrich
2016-05-23 21:39:40 UTC
view on stackexchange narkive permalink

Ist die verkettete Zufallszahl also besser als eine einzelne Zufallszahl?

Wenn der Zufallsgenerator wirklich zufällige Daten erzeugt, spielt dies keine Rolle.

... es wäre schwieriger, die nächste Zahl vorherzusagen, falls es ein Problem mit dem Zufallszahlengenerator gibt.

Wenn das Problem darin besteht, dass der Zufallsgenerator dies nicht ist überhaupt zufällig, dann könnte es für einen Angreifer sogar besser sein, so viele letzte Ausgaben wie möglich zu erhalten, da dann das Verhalten besser vorherzusagen sein könnte. Natürlich hängt diese Annahme stark von den Interna des Zufallsgenerators ab, daher ist keine allgemeine Antwort möglich.

Aber im Allgemeinen: Wenn Sie wirklich gute Zufallsdaten benötigen, sollten Sie einen geeigneten Zufallsgenerator verwenden. Ihre Methode verbessert die Qualität der Ausgabe nicht, wenn der Zufallsgenerator schlecht ist, d. H. Vorhersehbar bleibt. Wenn Sie tatsächlich keine echten Zufallsdaten benötigen, sondern nur sicherstellen möchten, dass Sie etwas zufällige Daten ohne Verzerrung erhalten, sollten Sie vorsichtig sein, da Ihre Methode abhängig davon, wie genau Sie dies tun, der Ausgabe möglicherweise eine Verzerrung hinzufügt. P. >

Ich verstehe nicht, wie es nicht sicherer ist.Der Angreifer würde nicht wissen, dass Sie mehrere verkettete Zahlen zusammenfügen, oder?Sie würden nur das Ergebnis sehen.
@TankorSmash: Es gibt keinen Unterschied zwischen dem Angreifer, der eine Zahl mit 16 Ziffern oder 4 Zahlen mit jeweils 4 Ziffern erraten muss.Die Anzahl der möglichen Kombinationen ist genau gleich.
Aber Sie sagten, es würde sich darauf auswirken. "Es könnte sogar besser für einen Angreifer sein, so viele letzte Ausgaben wie möglich zu erzielen."Ich verstehe, dass es dieselbe Nummer ist, aber der Angreifer würde nur eine Ausgangsnummer sehen, ohne zu bemerken, dass es tatsächlich 4 war, also sehe ich nicht, wie es es verletzen könnte.Ich denke, es ist schwer, auf die eine oder andere Weise ohne ein Beispiel sicher zu sagen.
@TankorSmash: Wenn der Zufallsgenerator wirklich schlecht ist, erhalten Sie möglicherweise mehr Informationen über seinen internen Zustand, wenn Sie 4 aufeinanderfolgende Zufallszahlen haben, als wenn Sie nur eine einzige Zahl haben.Und diese Informationen könnten dann verwendet werden, um zukünftiges Verhalten vorherzusagen.All dies hängt jedoch wirklich von den Besonderheiten des verwendeten Zufallsgenerators ab.
Ich stimme zu, wenn sie wüssten, dass es 4 Zufallszahlen sind, aber sie würden es zu diesem Zeitpunkt nicht tun, sie würden nur 16 Ziffern sehen und nichts anderes wissen.Wenn sie das wüssten, würden sie wissen, wie das RNG funktioniert, würde man meinen.
Ramón García
2016-05-23 23:18:48 UTC
view on stackexchange narkive permalink

Diese Präsentation über das Konzept eines unvorhersehbaren Pseudostreams kann zur Verdeutlichung der Ideen beitragen: https://class.coursera.org/crypto-preview/lecture/5 Präsentation in PDF http://spark-university.s3.amazonaws.com/stanford-crypto/slides/02.2-stream-annotated.pdf

Ein pseudozufälliger Dampf ist nicht vorhersehbar, wenn kein Angreifer richtig raten kann Der nächste Inhalt des Streams, der den vorherigen Inhalt kennt, mit einer Wahrscheinlichkeit, die größer ist als die zufällige Auswahl (1/2 ^ (Anzahl der Bits)) und der angemessenen Zeit.

Wenn Sie daher einen sicheren Pseudozufalls-Stream verwenden, wie Chacha20 (der Pseudozufallsstrom ist der Strom, der in dieser Verschlüsselung zum XOR der Daten verwendet wird), dann sind die Bytes per Definition unvorhersehbar. Andernfalls wäre dies eine erhebliche Sicherheitsverletzung in diesen Stream-Chiffren.

Warren Dew
2016-05-24 03:27:21 UTC
view on stackexchange narkive permalink

In der Regel ist die Kombination aufeinanderfolgender Ergebnisse desselben Pseudozufallszahlengenerators der Verwendung eines einzelnen Ergebnisses unterlegen. Stellen Sie sich das so vor: Der Zufallszahlengenerator generiert eine bestimmte Anzahl von Ergebnissen, bevor er zur ersten angegebenen Zahl zurückkehrt. Wenn Sie vier Ergebnisse gleichzeitig verbrauchen, können Sie nur ein Viertel so viele Ergebnisse erzielen - vorausgesetzt, die mögliche Anzahl der Ergebnisse ist ein Vielfaches von vier, was auf einer Binärmaschine wahrscheinlich ist -, was bei einem Brute-Force-Angriff der Fall wäre Es dauert nur ein Viertel so lange, bis Ihre Daten beschädigt sind.

Darüber hinaus kann das Verhalten der Daten selbst problematisch sein, wenn Sie aufeinanderfolgende Ergebnisse kombinieren. Beispielsweise stellen viele Zufallszahlengeneratoren einzelne Zahlen mit guten statistischen Verteilungen bereit, dies gilt jedoch nicht unbedingt für Kombinationen aufeinanderfolgender Zahlen, bei denen der Zufallszahlengenerator mehr oder weniger wahrscheinlich Läufe mit ähnlichen Ergebnissen erzeugt als dies tatsächlich der Fall wäre zufällige Quelle. Zum Beispiel habe ich einmal einen Zufallszahlengenerator verwendet, um Würfe eines sechsseitigen Würfels zu simulieren, und als ich drei aufeinanderfolgende Ergebnisse summierte, war das Verhalten aufeinanderfolgender Ergebnisse so, dass ich bei vielen tausend Versuchen nie eine Summe von 18 erhielt.

Ich diskutiere aufeinanderfolgende Ergebnisse, aber diese Argumente gelten auch für die Verwendung nicht aufeinanderfolgender Ergebnisse, wenn sie systematisch ausgewählt werden. Am besten wählen Sie einfach einen besseren Zufallsgenerator aus und verwenden die Ergebnisse nacheinander. Das einzige Mal, wenn Sie mehrere Ergebnisse kombinieren müssen, ist, wenn ein einzelnes Ergebnis nicht über genügend Bits verfügt, um Ihre Anforderungen zu erfüllen - selten bei handelsüblichen Pseudozufallszahlengeneratoren.

Aber woher weiß ein Angreifer, dass es sich nicht nur um eine zufällige 16-stellige Zahl handelt?
@TheGreatDuck: [Kerckhoffs Prinzip] (http://en.wikipedia.org/wiki/Kerckhoffs%27s_principle), auch bekannt als Shannons Maxime: ["Der Feind kennt das System"] (http://security.stackexchange.com/search?q =% 22 kennt + das + System% 22).Es ist sicher, dass der Angreifer wahrscheinlich keine echten Zufallszahlen errät (die als Ausgangsbasis für den Pseudozufallszahlengenerator verwendet werden).Angenommen, der Angreifer weiß nicht, wie das System funktioniert, ist Wunschdenken.
Das mag wahr sein, aber ist das Generieren einer 16-stelligen Zahl nicht dasselbe wie das Generieren von 16 Ziffern und das Anhängen dieser?Vielleicht verstehe ich den Prozess nicht.


Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 3.0-Lizenz, unter der er vertrieben wird.
Loading...