Noise XOR Signal = Noise?

[sx2008]

Ich habe mal eine eher theoretische Frage.
Angenommen man hat einen guten Zufallsgenerator der einen Strom von zufälligen Bytes liefert.
Dann hat man einen Signalgenerator der eine frei wählbare Bytefolge liefert.
Die beiden Bytefolgen werden mit XOR verknüpft und das Ergebnis wird analysiert.
Man kann den Signalgenerator auch abschalten; dann wird immer Noise XOR $00 berechnet was natürlich genau
dem Ausgang des Zufallsgenerators entspricht.

Kann man an dem Ergebnis irgendwie erkennen, ob gerade der Signalgenerator an oder aus ist?
Oder anderst gefragt: kann man ein Signal erzeugen, dass sich messbar gegen das Rauschen des Zufallsgenerator absetzen kann?

[BUG]

Zitat von sx2008:

Kann man an dem Ergebnis irgendwie erkennen, ob gerade der Signalgenerator an oder aus ist?

Bei einer 50% Chance für das Zufallsbit sollte man das nicht erkennen können. Stromverschlüsselungen basieren darauf.
Du kannst dir mal einfach einen Entscheidungsbaum für ein einzelnes Bit aufzeichnen, da kann man sich das gut überlegen.

Zitat von sx2008:

Oder anderst gefragt: kann man ein Signal erzeugen, dass sich messbar gegen das Rauschen des Zufallsgenerator absetzen kann?

Was hast du vor?

[Phoenix]

Zitat von sx2008:

Kann man an dem Ergebnis irgendwie erkennen, ob gerade der Signalgenerator an oder aus ist?
Oder anderst gefragt: kann man ein Signal erzeugen, dass sich messbar gegen das Rauschen des Zufallsgenerator absetzen kann?

1. Ja.
2. Nein.
3. Das ist nicht Praxisrelevant.

Du kannst den reinen Zufall statistisch analysieren, und erkennen, dass es echter Zufall ist.
Du kannst den Strom des Signalgenerators statistisch analysieren und erkennen, das es kein Zufall ist.

Der Signalstrom 'verzerrt' beim XORen den Zufall, denn er wird ohne Informationsverlust in den Zufall hineingewoben. Dadurch, das der Signalstrom nicht zufällig ist, wird er zwangsläufig *irgendwann* zu messbaren Patterns im modifizierten Zufallsstrom führen.

Die Unterschiede sind allerdings sehr gering. Du wirst nur über einen *längeren* Zeitraum durch sehr aufwändige Analysen des gesamten Datenstroms herausbekommen, ob in einem Teilstrom nun ein Signal eingewoben ist oder nicht.

Da wir hier auch nur über statistische Auffälligkeiten reden wirst Du auch den Beginn oder das Ende des Einwebens nie genau ermitteln können, sondern nur auf einem definierten Teilstrom mit einer gewissen Wahrscheinlichkeit sagen können: Hier war er an, und hier nicht.


Es ist also keineswegs so, dass Du den Strom mithörst und sagen kannst: 'Jetzt ist das Signal da, und jetzt nicht mehr', sondern Du kannst im Nachhinein nach der Analyse der Aufzeichnung vielleicht mal einigermassen sicher sagen: Damals, da in dem Teilbereich, ist es wahrscheinlich dass das Signal da war.

Wir reden hier aber über Datenmengen, die in der Praxis nicht zu bewältigen sind (ausser, Du bist die NSA oder hast unbegrenzte finanzielle Mittel um den nötigen Storage und die Rechenkapazität aufzubringen). Deswegen habe ich oben das 'nicht Praxisrelevant' dazugeschrieben.

[Dejan Vu]

Klingt logisch, ist aber trotzdem (in meinen Augen) nicht richtig. Ich glaube eher, das ein Signalstrom etwaige Schwächen des Zufallsgenerators aufdecken würde, mehr nicht. Ein 'perfekter' bzw. hinreichend guter Zufallsstrom wird dir nicht den Gefallen tun. Voraussetzung ist natürlich, das die Wertebereiche beider Signale (Rauschen und Muster) identisch sind.

Deiner Ansicht nach gilt: Zufall xor Muster = Kein Zufall (vereinfacht). Das stimmt aber meiner Meinung nach nicht.
Ein Gedankenexperiment soll das belegen.
Du hast ein Gefäß mit zwei Bällen (schwarz und weiß). Du greifst blind in das Gefäß, nimmst einen Ball und schreibst die Farbe auf (Zufallsstrom). Nun kommt das Signal (111100001111000). Bei einer '1' schreibst Du die Farbe des gezogenen Balles auf, bei einer '0' die andere.
Preisfrage: Wird sich die Sequenz bzw. der Informationsgehalt dadurch in irgend einer Weise verändern? Selbst wenn Du das Ausgangssignal 1000 Jahre analysierst, wirst Du nicht merken, ob die Sequenz durch das blinde Ziehen oder erzeugt wurde, oder eine Regel zur Veränderung angewandt wurde.

[BUG]

Angenommen man hat einen Generator für echten Zufall (z.B. radioaktiver Zerfall, thermisches Rauschen, usw.), dann entspräche das in Grunde einem One-Time-Pad.
Die Argumentation ist natürlich verkehrt herum, weil das OTP gerade sicher ist, weil dort diese Eigenschaften ausgenutzt werden; aber wenn Phoenix recht hätte wäre das OTP nicht sicher

Auch die Theorie mit dem Informationsverlust hat einen Haken: Die Information ist steckt eben nicht in dem Endresultat, sondern nur in der Kombination aus Schlüssel und dem Resultat ... also exakt so viele Bits wie vorher.

[nuclearping]

Ich denke das Hauptproblem ist hier auch, dass man Byte XOR Byte macht. Also beide Positionen haben einen Wertbereich von 0-255. Daran direkt zu erkennen, ob ein zusätzlicher Prozess das Signal beeinflusst oder nicht, schließt sich wohl damit auch aus.

Ich denke auch, dass der Ansatz von Phoenix, über eine indirekte Analyse, hier eher zum Ergebnis führen würde, vorrausgesetzt es handelt sich um einen "echten" Zufall.

[Namenloser]

Es kommt wohl darauf an, um was für eine Art Zufall es sich handelt, bzw. wie der Zufall verteilt ist.

Wenn man gleichverteilete Zufallswerte von 0..255 generiert und diese Byte-weise mit dem Signal XORt, dann kann man unter Umständen eine Analyse durchführen, denn durch das XOR mit dem Signal ändert sich die Verteilung (beispielsweise ist der Mittelwert dann u.U. nicht mehr 127).

Hantiert man dagegen mit zufälligen Bits, wobei jedes Bit eine 50%ige Chance hat, 1 oder 0 zu sein, dann sollte es unmöglich sein, das Signal zu rekonstruieren. Das ist ja gerade das Prinzip des One-Time-Pad.

Edit:
Schwachsinn, bei gleichverteilten Bytes ist jedes Bit auch wieder gleichverteilt.

Also man kann das Signal so oder so nicht rekonstruieren.

Bei Stochastik verknoten sich mir immer die Hirnwindungen

[BUG]

Bist du sicher das gleich-verteilte Bytes nicht gleich-verteilte Bits implizieren?

Ich würde mir das so überlegen: Angenommen man hat ein Byte aus einer gleich-verteilten Quelle. Nun wähle man ein beliebiges Bit in diesem Byte. Für jeden Wert dieses Bits gibt es gleich viele Byte-Werte, bei dem dieses Bit gesetzt bzw. nicht gesetzt ist. Jeder dieser Byte-Werte ist gleich wahrscheinlich. Daraus folgt, dass das einzelne Bit auch eine 50% Chance hat, gesetzt zu sein.

Beispiel: das höchstwertige Bit
Gesetzt für 0..127, also 128 Werte
Nicht gesetzt für 128..255, also 128 Werte
Die Wahrscheinlichkeit für beide Mengen von Werten ist jeweils (1/256)*128 = 1/2.

@rote Box: Ich poste es jetzt trotzdem

[Dejan Vu]

Ich will nur daran erinnern, das es hier nicht um Ver/Entchlüsselung geht, sondern *ob* man erkennt, ob eine Signalveränderung durch XOR stattgefunden hat, oder nicht.

[Aphton]

Ich kann mich intuitiv an Phonix #3 anschließen..

Als ein einfaches Beispiel habe ich mir ein Geradensegment vorgestellt, das beliebig durch den Raum verläuft, wo man aber mit dem freien Auge bereits ein Muster erkennt.
Wenn man nun die Operation "Xor" in diesem Fall durch "Addition" substituiert und dem Geradensegment ein Noise "draufaddiert", kann man folglich Änderungen am Muster warnehmen. Komplizierter wirds dann natürlich, wenn die Muster komplexer werden. Hängt m.M.n also von der Mustererkennung ab.

Ob die Änderung der Operation ohne Weiteres möglich ist und die Schlussfolgerung dadurch nicht beeinträchtigt wird, ist mir moment nicht bewusst.