Warum kombinieren wir keine Zufallszahlengeneratoren?

60

Es gibt viele Anwendungen, in denen ein Pseudozufallszahlengenerator verwendet wird. Die Leute implementieren also eine, die sie für großartig halten, und stellen später fest, dass sie fehlerhaft ist. So etwas ist kürzlich mit dem Zufallszahlengenerator von Javascript passiert. RandU auch schon viel früher. Es gibt auch Probleme mit unangemessenem Initial Seeding für so etwas wie den Twister.

Ich kann keine Beispiele finden, bei denen zwei oder mehr Generatorenfamilien mit dem üblichen xor-Operator kombiniert werden. Wenn genügend Computerleistung vorhanden ist, um beispielsweise Java.SecureRandom- oder Twister-Implementierungen auszuführen, warum kombinieren die Benutzer diese nicht? ISAAC xor XORShift xor RandU sollte ein ziemlich gutes Beispiel sein und wo Sie die Schwäche eines einzelnen Generators sehen können, der von den anderen abgeschwächt wird. Es sollte auch bei der Verteilung von Zahlen in höhere Dimensionen helfen, da die intrinsischen Algorithmen völlig unterschiedlich sind. Gibt es ein grundlegendes Prinzip, dass sie nicht kombiniert werden sollten?

Wenn Sie einen echten Zufallszahlengenerator bauen würden, würden die Leute wahrscheinlich raten, dass Sie zwei oder mehr Entropiequellen kombinieren. Ist mein Beispiel anders?

Ich schließe das allgemeine Beispiel mehrerer linearer Rückkopplungsschieberegister aus, die zusammenarbeiten, da sie aus derselben Familie stammen.

Paul Uszak
quelle
Die Antwort kann von der Anwendung abhängen. Wofür möchten Sie die Pseudozufallsfolge verwenden?
Yuval Filmus
1
Haben Sie Fortuna gefunden ( en.wikipedia.org/wiki/Fortuna_%28PRNG%29 ), so scheint es, als ob es in der Nähe dessen liegt, was Sie beschreiben, dass es verschiedene zufällige Quellen zu einer aggregiert.
Kleiner Code
1
@LittleCode Eigentlich klingt es ganz anders. Fortuna gibt Daten von einer einzelnen Hash-Funktion aus. Es wird nur mit vielen schwachen Entropiesammlungsmechanismen herumgespielt, bevor es durch eine einzige Ausgabefunktion (erneut) gehasht wird. Meine Frage bezog sich auf die Ausgabe von mehreren Funktionen (warum nicht 10 von ihnen)? Wenn es sich um ein Füllgerät handelt, ist die Geschwindigkeit ohnehin unerheblich.
Paul Uszak
1
Der verstorbene George Marsaglia, ein bekannter Forscher auf dem Gebiet der PRNGs, der mehrfach neue PRNG-Typen wie Multiplikation mit Übertrag und Xor-Shift erfand, schlug in den 1990er Jahren den KISS-Generator vor, der eine Kombination aus drei PRNGs darstellt von unterschiedlichem Typ. Ich benutze KISS seit zwanzig Jahren erfolgreich, natürlich nicht für die Kryptographie. Eine nützliche sekundäre Quelle in Bezug auf KISS ist dieser Artikel von Greg Rose aus dem Jahr 2011, in dem er auf ein Problem mit einem der konstituierenden PRNGs
hinweist
4
Knuth bezieht das Ergebnis der naiven Kombination von Pseudozufallszahlengeneratoren (unter Verwendung einer Zufallszahl zur Auswahl des zu verwendenden Generators) auf eine Funktion, die gegen einen festen Wert konvergiert! Also warnte er uns in den Tagen vor der Revolution der Mikrocomputer davor, niemals Zufallsgeneratoren zu mischen.
JDługosz

Antworten:

7

IIRC (und das ist aus dem Gedächtnis), der 1955er Rand-Bestseller A Million Random Digits, hat so etwas gemacht. Bevor Computer billig waren, wählten die Leute Zufallszahlen aus diesem Buch.

Die Autoren erzeugten zufällige Bits mit elektronischem Rauschen, aber das stellte sich als vorgespannt heraus (es ist schwierig, ein Flip-Flop genau gleich oft für Flip und Flop zu verwenden). Das Kombinieren von Bits machte die Verteilung jedoch viel gleichmäßiger.

Amateur
quelle
45

Natürlich können Sie PRNGs wie diese kombinieren, wenn Sie möchten, vorausgesetzt, sie werden unabhängig voneinander gesetzt. Es wird jedoch langsamer und wird wahrscheinlich nicht die dringendsten Probleme lösen, die Menschen haben.

In der Praxis verwenden Sie, wenn Sie ein PRNG mit sehr hoher Qualität benötigen, ein PRNG mit guter kryptografischer Stärke und setzen es mit echter Entropie ein. Wenn Sie dies tun, ist der wahrscheinlichste Fehlermodus kein Problem mit dem PRNG-Algorithmus selbst. Der wahrscheinlichste Fehlermodus ist ein Mangel an angemessener Entropie (oder möglicherweise Implementierungsfehler). Das X-Oder mehrerer PRNGs hilft bei diesem Fehlermodus nicht. Wenn Sie also ein PRNG mit sehr hoher Qualität wünschen, ist es wahrscheinlich wenig sinnvoll, sie zu xen.

Wenn Sie einen statistischen PRNG wünschen, der für Simulationszwecke gut genug ist, geht es in der Regel um Geschwindigkeit (Generieren von Pseudozufallszahlen sehr schnell) oder Einfachheit (Sie möchten nicht viel Entwicklungszeit für die Erforschung oder Implementierung dieses PRNGs aufwenden). Xor-ing verlangsamt das PRNG und macht es komplexer, sodass es auch in diesem Kontext nicht die primären Anforderungen erfüllt.

Solange Sie angemessene Sorgfalt und Kompetenz zeigen, sind Standard-PRNGs mehr als gut genug. Es gibt also keinen Grund, warum wir etwas schickeres brauchen (keine Notwendigkeit für Xor-ing). Wenn Sie nicht einmal ein Mindestmaß an Sorgfalt oder Kompetenz haben, werden Sie sich wahrscheinlich nicht für etwas Komplexes wie Xor-ing entscheiden. Der beste Weg, die Dinge zu verbessern, besteht darin, sich bei der Auswahl des PRNG auf mehr Sorgfalt und Kompetenz zu konzentrieren eher als auf xor-ing.

Fazit : Grundsätzlich löst der xor-Trick nicht die Probleme, die Menschen normalerweise bei der Verwendung von PRNGs haben.

DW
quelle
3
"Mangel an adäquater Entropie ... Das Xoring mehrerer PRNGs hilft hier nicht weiter" - in der Tat kann es hinderlich sein, da Sie die Menge an Entropie erhöhen, die für die Aussaat Ihrer PRNGs erforderlich ist. Das ist der Grund, warum Sie es nicht zur Routine machen wollen, gut überprüfte PRNGs zu kombinieren, obwohl es Sie tatsächlich vor einem dieser gut überprüften PRNGs schützt, die sich als kompletter Müll herausstellen (in der Implementierung, die Sie verwenden). .
Steve Jessop
Ein weiterer Grund ist, dass Implementierungsfehler weitaus häufiger auftreten als grundlegende Probleme mit Algorithmen. Je einfacher, desto besser. Ein Standardalgorithmus kann zumindest gegen eine andere Implementierung oder Referenzwerte getestet werden, ein maßgeschneiderter xoder nicht.
Gilles 'SO- hör auf böse zu sein'
1
@DW Warum "unabhängig ausgesät"? Da sich meine Frage auf Kombinationen verschiedener Generatorenfamilien bezieht, sollte jede Familie eine eindeutige Ausgabesequenz aus identischen Samen erzeugen. Zum Beispiel könnten java.SecureRandom und RC4 leicht vom selben Schlüssel ausgesät und dann kombiniert werden.
Paul Uszak
1
@DW Die große Annahme, die Sie angeben, lautet "Verwenden Sie ein PRNG mit guter Verschlüsselungsstärke". In der Realität ist dies praktisch unmöglich festzustellen, wie bei den meisten kryptografischen Chiffren, Hashes usw. - Schwachstellen treten im Laufe der Zeit auf. Sie waren für das Wissen von gestern oder gestern "gut geprüft".
Shiv
1
@PaulUszak, ich glaube nicht, dass ich jemals argumentiert habe, dass das Xen von zwei Generatoren die Fehleranfälligkeit erhöht. Ich sage, wenn Sie einen guten PRNG (nur einen) auswählen, ist einer der wahrscheinlichsten Fehlermodi ein Fehler beim Seeding oder ein Implementierungsfehler, und das Xor-ing von zwei Generatoren hilft auch nicht. (Wenn das einzelne PRNG nicht ausfällt, ist es natürlich auch nicht sinnvoll, zwei Generatoren zu xen.) Im Grunde genommen geht es also um das falsche Problem. Mit anderen Worten, XORING-Generatoren erhöhen die Sicherheit nicht wesentlich, da sie nicht die wichtigsten Ursachen für Unsicherheit ansprechen.
DW
19

Tatsächlich wurde gerade ein Durchbruch angekündigt, indem genau dies getan wurde.

David Zuckerman, Informatikprofessor an der Universität von Texas, und Eshan Chattopadhyay, Doktorand, stellten fest, dass eine Zufallszahl mit "hoher Qualität" durch Kombinieren von zwei Zufallsquellen mit "niedriger Qualität" erzeugt werden kann.

Hier ist ihr Artikel: Explizite Zwei-Quellen-Extraktoren und ausfallsichere Funktionen

NietzscheanAI
quelle
8
Dies ist eine rein theoretische Abhandlung zu einem anderen Thema, die trotz der PR-Bemühungen von UT keinerlei praktische Relevanz hat.
Yuval Filmus
4
@Yuval Filmus - Würden Sie diesen Kommentar gerne erweitern?
NietzscheanAI
8
Es gibt eine große Kluft zwischen Theorie und Praxis. Normalerweise interessieren sich Praktiker nicht für Theorie und umgekehrt. In diesem Fall entschied sich die PR-Abteilung von UT für ein ausgezeichnetes theoretisches Paper, das als praktisch relevant bezeichnet wurde, was es nicht ist. Die in der Veröffentlichung behandelten Probleme sind aus praktischer Sicht nicht so interessant und es gibt einfache Lösungen, die gut genug funktionieren, obwohl es unmöglich ist, zu beweisen, dass sie dies tun.
Yuval Filmus
2
Darüber hinaus ist dieses Papier nur eine Arbeit im theoretischen Bereich der Extraktoren. Sie können jedes andere Papier in der Region auf die gleiche Weise in Rechnung stellen. Es geht darum, schwache Quellen zu einer starken Quelle zu kombinieren. Der Unterschied liegt nur in den Parametern.
Yuval Filmus
3
Schließlich ist die Konstruktion in der Zeitung höchstwahrscheinlich ein Overkill, nicht etwas, das Sie jemals implementieren möchten. Konkrete Parameter für diese Art der Konstruktion sind schwer zu bestimmen und in der Regel extrem schlecht, da sich die Arbeiten immer auf das asymptotische Regime konzentrieren und Konstanten ignorieren.
Yuval Filmus
9

Angenommen, ist eine pseudozufällige Binärsequenz. Das heißt, jedes X i ist eine Zufallsvariable, die von { 0 , 1 } unterstützt wird , und die Variablen X 1 , , X n sind nicht unbedingt unabhängig. Wir können uns vorstellen, dass diese Sequenz folgendermaßen generiert wird: Zuerst wird ein gleichmäßig zufälliger Schlüssel K abgetastet und dann wird mit einer Funktion f ( K ) die Pseudozufallssequenz generiert.X1,,XnXi{0,1}X1,,XnKf(K)

Wie messen wir, wie gut die Pseudozufallsfolge ist? Während es möglich ist zu messen, wie gut eine bestimmte Realisierung ist (zB mit Kolmogorov-Komplexität), werde ich mich hier auf Maßnahmen konzentrieren, die von der gesamten Verteilung der Zufallsvariablen ( X 1 , , X n ) abhängen . Ein solches Beispiel ist Entropie, aber wir werden nur zwei Eigenschaften unseres Maßes L benötigen : (Ein größeres L ( ) bedeutet eine zufälligere Folge)X1,,Xn(X1,,Xn)LL()

  • Wenn eine deterministische Folge (dh eine feste Folge) ist, dann ist L ( X 1y 1 , ... , X ny n ) = L ( X 1 , ... , X n ) .y1,,ynL(X1y1,,Xnyn)=L(X1,,Xn)

  • Wenn zwei unabhängige Pseudozufallsfolgen sind, T { 0 , 1 } ein unabhängiges Zufallsbit ist und Z = X T , dann ist L ( Z ) min ( X 0 , X 1 ) .X0,X1T{0,1}Z=XTL(Z)Mindest(X0,X1)

Die erste Eigenschaft bedeutet, dass die Kennzahl beim Umkehren des ten Bits invariant ist . Die zweite Eigenschaft bedeutet, dass wenn wir zwei Verteilungen X , Y mischen , das Ergebnis mindestens so gut ist wie das schlechtere.ichX,Y.

Jedes vernünftige Zufallsmaß erfüllt die erste Eigenschaft. Die zweite Eigenschaft wird durch die gängigsten Maße wie Entropie und Min-Entropie H erfüllt .HH

Wir können nun einen Satz aufstellen und beweisen, der zeigt, dass die XOR-Verknüpfung von zwei Pseudozufallssequenzen immer eine gute Idee ist.

Satz. Sei zwei unabhängige Pseudozufallsfolgen gleicher Länge und sei L ein zulässiges Zufallsmaß (eine, die die beiden obigen Bedingungen erfüllt). Dann ist L ( XY ) max ( L ( X ) , L ( Y ) ) .X,Y.L

L(XY.)max(L(X),L(Y.)).

L(X)L(Y.)XY.XyY.L(Xy)=L(X)L(XY.)L(X) 

Was dieses Theorem bedeutet, ist, dass, wenn Sie zwei Pseudozufallssequenzen, die mit zwei unabhängigen Schlüsseln erzeugt wurden, XOR- verknüpfen, das Ergebnis in Bezug auf jedes zulässige Zufallsmaß immer mindestens so gut wie die bessere Sequenz ist, die XOR-verknüpft ist.

In der Praxis erweitern wir, um zwei unabhängige Schlüssel zu verwenden, wahrscheinlich einen Schlüssel auf pseudozufällige Weise auf zwei Schlüssel. Die beiden Schlüssel sind dann nicht unabhängig. Wenn wir jedoch einen "teuren" Weg verwenden, um den einen Schlüssel in zwei Schlüssel zu erweitern, erwarten wir, dass die resultierenden zwei Schlüssel unabhängig "aussehen" und dass der Satz "moralisch" gilt. In der theoretischen Kryptographie gibt es Möglichkeiten, diese Aussage zu präzisieren.


TTT1T2T1+T2=tT1,T2(t/2,t/2)(t,0)(0,t)

Der beste Rat ist, sich an ein beliebtes PRNG zu halten, das als stark gilt. Wenn Sie mehr Zeit für die Erstellung Ihrer Sequenz haben, können Sie mehrere Kopien mit unabhängigen Schlüsseln (oder Schlüsseln, die durch Erweitern eines einzelnen Schlüssels mit einem teuren PRNG generiert werden) XOR.

Yuval Filmus
quelle
Kommentare sind nicht für längere Diskussionen gedacht. Diese Unterhaltung wurde in den Chat verschoben . Wenn Sie zu einem konstruktiven Ende gekommen sind, bearbeiten Sie bitte die Antwort, um die Ergebnisse Ihrer Diskussion einzubeziehen.
Raphael
4

Ich werde es versuchen, da ich von den Ratschlägen in einigen anderen Antworten ausreichend beunruhigt bin.

X,Y.XY.XY.XY.

  • (0) Die Wahrscheinlichkeit der wahren Zufälligkeit der Sequenz nimmt zu oder ab
  • (1) Die Wahrscheinlichkeit einer beobachtbaren Nicht-Zufälligkeit nimmt zu oder ab (in Bezug auf einen Beobachter, der eine bestimmte Menge an Kontrolle anwendet, vermutlich)
  • (2) Der Schweregrad / die Offensichtlichkeit der beobachtbaren Nicht-Zufälligkeit nimmt zu oder ab.

X,Y.εX,εY.XY.εXεY.<michn{εX,εY.}εX,εY.X,Y.

Pr(XY. nOt truly reinndOm)Mindest{Pr(X nOt truly reinndOm),Pr(Y. nOt truly reinndOm),Pr(X,Y. dependent)}.

(0) ist jedoch für PRNGs nicht interessant, da im Fall von PRNGs keine der fraglichen Sequenzen eine Chance hat, wirklich zufällig zu sein.

Daher müssen wir für diese Frage, die sich in Wirklichkeit um PRNGs handelt, über etwas wie (1) oder (2) sprechen. Da es sich um Eigenschaften und Größen wie "beobachtbar", "schwerwiegend", "offensichtlich", "offensichtlich" handelt, sprechen wir jetzt über die Komplexität von Kolmogorov, und ich werde nicht versuchen, dies genau zu machen. Aber ich werde so weit gehen, die hoffentlich unumstrittene Behauptung aufzustellen, dass durch ein solches Maß "01100110 ..." (Periode = 4) schlechter ist als "01010101 ..." (Periode = 2), was schlechter ist als " 00000000 ... "(konstant).

XY.XY.X=Y.X=nOt(Y.)XY.XY.XY.XY.

Eine solche Überraschungsabhängigkeit stellt sich als ein wirklich großes Problem heraus.


Ein Beispiel dafür, was schief geht

In der Frage heißt es: "Ich schließe das übliche Beispiel mehrerer linearer Rückkopplungsschieberegister aus, die zusammenarbeiten, da sie aus derselben Familie stammen." Aber ich werde diesen Ausschluss vorerst ausschließen, um ein sehr einfaches, klares Beispiel für die Art der Dinge zu geben, die mit XORing schief gehen können.

Mein Beispiel wird eine alte Implementierung von rand () sein, die sich in einer Unix-Version von 1983 befand. IIRC, diese Implementierung der rand () -Funktion hatte die folgenden Eigenschaften:

  • Der Wert jedes Aufrufs von rand () betrug 15 pseudozufällige Bits, dh eine ganze Zahl im Bereich von [0, 32767].
  • aufeinanderfolgende Rückgabewerte wechselten gerade-ungerade-gerade-ungerade; das niedrigstwertige Bit hat 0-1-0-1 abgewechselt ...
  • 2fünfzehn
  • 2fünfzehn

Ich konnte den ursprünglichen Quellcode nicht finden, aber ich vermute, dass ich einige Beiträge aus https://groups.google.com/forum/#!topic/comp.os.vms/9k4W6KrRV3A zusammengesetzt habe es tat genau das Folgende (C-Code), was mit meiner Erinnerung an die obigen Eigenschaften übereinstimmt:

#define RAND_MAX 32767
static unsigned int next = 1;
int rand(void)
{
    next = next * 1103515245 + 12345;
    return (next & RAND_MAX);
}
void srand(seed)
unsigned int seed;
{
    next = seed;
}

Wie man sich vorstellen kann, führte der Versuch, diesen rand () auf verschiedene Arten zu verwenden, zu einer Reihe von Enttäuschungen.

An einem Punkt habe ich zum Beispiel versucht, eine Folge zufälliger Münzwürfe zu simulieren, indem ich wiederholt Folgendes genommen habe:

rand() & 1

ichich-1 ist hier nicht nützlich "; alles, was wir wirklich sagen können, ist, dass die nummerierten Bitpositionen einen unterschiedlichen Grad an Nützlichkeit / Nutzlosigkeit aufwiesen.

Ich habe auch versucht, die Ergebnisse weiter zu verschlüsseln oder Werte, die von mehreren Aufrufen an rand () zurückgegeben wurden, durch XOR zu verknüpfen. Das XORen von Paaren aufeinanderfolgender rand () - Werte war natürlich eine Katastrophe - es ergab alle ungeraden Zahlen! Für meine Zwecke (nämlich das Erzeugen einer "scheinbar zufälligen" Folge von Münzwürfen) war das Ergebnis der Konstantparität des XOR noch schlimmer als das abwechselnde gerade-ungerade Verhalten des Originals.

XsXY.sY.XY.

Mit anderen Worten, dies ist ein Beispiel, in dem XOR die Dinge im Sinne von (1) und (2) durch eine vernünftige Interpretation verschlimmert hat. Es ist auch auf verschiedene andere Arten schlimmer:

  • (3) Das XOR-Bit mit der niedrigsten Signifikanz ist offensichtlich vorgespannt, dh es hat ungleiche Frequenzen von Nullen und Einsen, im Gegensatz zu jeder nummerierten Bitposition in einem der Eingänge, die alle unverzerrt sind.
  • (4) Tatsächlich gibt es für jede Bitposition Paare von Startwerten, für die diese Bitposition im XOR-Ergebnis vorgespannt ist, und für jedes Paar von Startwerten gibt es (mindestens 5) Bitpositionen, die im XOR vorgespannt sind Ergebnis.
  • 2142fünfzehn

Keiner von (3), (4), (5) ist offensichtlich, aber sie sind alle leicht überprüfbar.


Lassen Sie uns abschließend überlegen, das Verbot von PRNGs aus derselben Familie wieder einzuführen. Ich denke, das Problem dabei ist, dass es nie wirklich klar ist, ob zwei PRNGs "aus derselben Familie" stammen, bis / es sei denn, jemand beginnt, die XOR-Funktion zu verwenden und bemerkt (oder ein Angreifer bemerkt), dass sich die Situation im Sinne von (1) verschlechtert hat. und (2) dh bis nicht zufällige Muster in der Ausgabe die Schwelle von nicht bemerkt zu bemerkt / peinlich / katastrophal überschreiten und zu diesem Zeitpunkt ist es zu spät.

Ich bin alarmiert über andere Antworten, die einen uneingeschränkten Ratschlag geben: "XOR kann nicht schaden" auf der Grundlage theoretischer Maßnahmen, die meiner Ansicht nach schlecht darin sind, das zu modellieren, was die meisten Leute als "gut" und "schlecht" betrachten PRNGs im wirklichen Leben. Diesem Ratschlag wird durch klare und offensichtliche Beispiele widersprochen, in denen XOR die Situation verschlimmert, wie das oben angegebene rand () - Beispiel. Während es denkbar ist, dass relativ "starke" PRNGs konsistent das entgegengesetzte Verhalten zeigen könnten, wenn sie mit der XOR-Funktion des Spielzeug-PRNGs rand () verknüpft werden, wodurch XOR für sie eine gute Idee ist, habe ich weder theoretisch noch theoretisch Beweise dafür gesehen empirisch, daher erscheint es mir unvernünftig anzunehmen, dass dies geschieht.

Persönlich, nachdem ich in meiner Jugend von XORing rand () s und unzähligen anderen Überraschungskorrelationen überrascht worden bin, habe ich wenig Grund zu der Annahme, dass das Ergebnis anders ausfallen wird, wenn ich es erneut mit ähnlichen Taktiken versuche. Aus diesem Grund würde ich es persönlich sehr ablehnen, mehrere PRNGs zusammen zu XORen, es sei denn, es wurden sehr umfangreiche Analysen und Überprüfungen durchgeführt, um mir die Gewissheit zu geben, dass dies für die jeweiligen RNGs sicher sein könnte. Als potenzielle Heilung für den Fall, dass ich einem oder mehreren der einzelnen PRNGs nicht vertraue, ist es unwahrscheinlich, dass das XOR-Verfahren mein Vertrauen erhöht. Daher werde ich es wahrscheinlich nicht für einen solchen Zweck verwenden. Ich stelle mir vor, die Antwort auf Ihre Frage ist, dass dies ein weit verbreitetes Gefühl ist.

Don Hatch
quelle
Wie erklären Sie die Nutzung von A5 / 1 durch buchstäblich Milliarden von Menschen?
Paul Uszak
@PaulUszak Ich habe keine Ahnung. Widerspricht A5 / 1, das von Milliarden von Menschen verwendet wird, etwas, das ich gesagt habe?
Don Hatch
Es sind drei Prngs (die eigentlich aus derselben Familie stammen), die zusammengefügt wurden, um ein besseres zu bilden, das Sie stört und alarmiert ...
Paul Uszak
Was mich beunruhigt und beunruhigt, ist der uneingeschränkte Rat: "Wenn Sie sich nicht sicher sind, können Sie eine Reihe von RNGs miteinander verknüpfen. Das kann die Situation nicht verschlimmern." Ich wollte nicht sagen oder andeuten, dass XOR in allen Fällen schlecht ist, und ich habe überhaupt keine Meinung zu A5 / 1 oder der Verwendung von XOR darin. Wäre es hilfreich, wenn ich meine abschließende Zusammenfassung ändern würde, um dies klarer zu machen?
Don Hatch
1
Ich habe die simplen "Sag einfach nein zu XORing-RNGs" am Ende durch etwas Realeres und hoffentlich weniger Irreführendes ersetzt.
Don Hatch
0

HAFTUNGSAUSSCHLUSS: Diese Antwort bezieht sich ausschließlich auf "Wir tun es nicht" und nicht auf "Hier ist ein mathematischer Beweis, warum es funktionieren kann oder nicht." Ich behaupte nicht, dass XOR kryptografische Schwachstellen einführt (oder nicht). Mein Punkt ist nur, dass uns die Erfahrung zeigt, dass selbst einfachste Systeme fast immer unvorhergesehene Folgen haben - und deshalb vermeiden wir sie.

"Randomness" ist nur eine Spitze des Eisbergs, wenn es um RNGs und PRNGs geht. Es gibt andere wichtige Eigenschaften, z. B. die Gleichmäßigkeit.

Stellen Sie sich einen gewöhnlichen Würfel vor, der für sich genommen ein ziemlich gutes RNG ist. Angenommen, Sie benötigen einen Bereich von 1 bis 5 anstelle von 1 bis 6. Das erste, was mir in den Sinn kommt, ist, einfach die 6 zu löschen und durch eine zusätzliche 1 zu ersetzen. Die "Zufälligkeit" bleibt bestehen (die Ergebnisse sind immer noch wirklich zufällig), die Gleichmäßigkeit leidet jedoch stark: Jetzt ist 1 doppelt so wahrscheinlich wie andere Ergebnisse.

Das Kombinieren von Ergebnissen aus mehreren RNGs führt zu einer ähnlich rutschigen Steigung. Z.B. Durch einfaches Hinzufügen von 2 Würfeln wird die Gleichmäßigkeit vollständig beseitigt, da "7" jetzt 6-mal wahrscheinlicher ist als "2" oder "12". Ich stimme zu, dass XOR auf den ersten Blick besser aussieht als Addition, aber in PRNGs stellt sich nichts so heraus, wie es auf den ersten Blick aussieht.

Aus diesem Grund bleiben wir in der Regel bei bekannten Implementierungen - weil jemand viel Zeit und Geld in deren Erforschung investiert hat und alle Mängel bekannt sind, verstanden wurden und umgangen werden können. Wenn Sie Ihre eigenen erstellen, können Sie potenziell Sicherheitslücken schaffen, und Sie sollten ähnliche Anstrengungen unternehmen, um dies zu beweisen. Wie das Beispiel für das Hinzufügen von Würfeln zeigt, kann das Kombinieren nicht viel anders sein als das Erstellen eines neuen von Grund auf neu.

Sicherheit ist eine Kette, so stark wie die schwächste Komponente. Eine Faustregel für die Sicherheit: Wenn Sie zwei Dinge kombinieren, erhalten Sie normalerweise eine Summe von Fehlern und keine Summe von Stärken.

Agent_L
quelle
7
Entschieden widersprechen. Wenn Sie eine wirklich zufällige Sequenz mit einer beliebigen Sequenz XOR-verknüpfen, erhalten Sie dennoch eine wirklich zufällige Sequenz. Wenn Sie zwei unabhängige Pseudozufallssequenzen XOR- verknüpft (dh mit unterschiedlichen Schlüsseln generiert), erhalten Sie in ähnlicher Weise etwas, das mindestens so stark ist wie jedes einzelne.
Yuval Filmus
3
Das scheint mir falsch. Der übliche Fall ist, dass ich denke, ich habe zwei sehr hochwertige RNGs, die im Wesentlichen wirklich zufällige Bits produzieren, aber es besteht eine winzige Chance, dass ich mich (vielleicht grob) über einen (oder viel weniger wahrscheinlich über beide) irre. Wenn ich sie zusammenstelle, ist das Ergebnis wirklich zufällig und ich bin gut, solange ich bei mindestens einem davon Recht habe. Durch die Kombination habe ich meine Chance auf ein schlechtes RNG von ungefähr epsilon / 2 auf extrem winziges epsilon ^ 2 reduziert, was definitiv ein Gewinn ist. Ich vermute, dass eine ähnliche Dynamik auch in weniger schwierigen Fällen gegeben ist.
Don Hatch
2
Ich bin immer noch nicht überzeugt. Als ich "wirklich zufällig" schrieb, meinte ich "gleichmäßig zufällig". Wenn Sie eine gleichmäßig zufällige Sequenz mit einer beliebigen Sequenz XOR-verknüpfen, erhalten Sie eine gleichmäßig zufällige Sequenz.
Yuval Filmus
2
Pr[Xich+100=Xich]=(1+ϵ)/2Zich=XichY.ichPr[Zich+100=Zich]=(1+ϵ2)/2ϵ2|ϵ|
3
@YuvalFilmus Sie haben wahrscheinlich Recht, dass die Korrelation zwischen Punkt i und Punkt i + 100 stark reduziert wurde, aber das ist nicht der Punkt. Für ein sehr spezifisches und reales Beispiel: Ich erinnere mich, dass die alte crappy rand () -Implementierung unter Unix ein periodisches Verhalten im niederwertigsten Bit jeder zurückgegebenen 31-Bit-Ganzzahl aufwies, was die meisten Leute nicht bemerkten. Bei dieser Folge von Ints mit einer verschobenen Kopie von sich selbst (die Sie erhalten, wenn Sie einen anderen Startwert verwenden) mit einer unglücklichen Schichtgröße erhalten Sie alle geraden Zahlen. Das ist für die meisten Zwecke viel schlimmer als das Problem in der ursprünglichen Sequenz.
Don Hatch