![]() |
Noise XOR Signal = Noise?
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? |
AW: Noise XOR Signal = Noise?
Zitat:
![]() Du kannst dir mal einfach einen Entscheidungsbaum für ein einzelnes Bit aufzeichnen, da kann man sich das gut überlegen. Zitat:
|
AW: Noise XOR Signal = Noise?
Zitat:
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. |
AW: Noise XOR Signal = Noise?
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. |
AW: Noise XOR Signal = Noise?
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 :wink: 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. |
AW: Noise XOR Signal = Noise?
Ich denke das Hauptproblem ist hier auch, dass man
Delphi-Quellcode:
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.
Byte XOR Byte
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. |
AW: Noise XOR Signal = Noise?
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 :duck: |
AW: Noise XOR Signal = Noise?
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 :tongue: |
AW: Noise XOR Signal = Noise?
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.
|
AW: Noise XOR Signal = Noise?
Ich kann mich intuitiv an
![]() 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. |
AW: Noise XOR Signal = Noise?
Selbst bei Phoenix' Methode (welche ich auch für die einzig denkbare mit (vielen) weltlichen Mitteln halte), ist nochmals zu betonen, dass man auch damit nicht dazu kommt, das Signal zu rekonstruieren. Es geht dabei nur darum, ob ein Signal auf das Rauschen ge-xor-t ist oder nicht. Null Aussage darüber, wie dieses Signal wohl aussehen mag.
|
AW: Noise XOR Signal = Noise?
Zitat:
Zitat:
Ein trivialer Lösungsansatz wäre, das Signal aus dem Zufallsgenerator zu nehmen und mit diesem per XOR zu verwursten. Dann ist das Ausgangssignal immer $00 wenn das Signal an ist. Der Umkehrschluß (wenn $00 ankommt ist das Signal an) gilt aber auch da nicht. Eine Folge von Nullen wäre dann auch erst ab einer gewissen Länge mit hoher Wahrscheinlichkeit ein Indiz für ein eingeschaltetes Signal. |
AW: Noise XOR Signal = Noise?
Zitat:
Für ein einzelnes Bit zwar schon, aber mit einem einzigen Bit kann man deine Gerade (oder irgendwas „komplexeres“) auch gar nicht erst bilden. |
AW: Noise XOR Signal = Noise?
Ich würde mich sogar aus dem Fenster lehnen und behaupten, das die Addition modulo 256 genau so effektiv ist, wenn man gleich-verteilten Noise mit Elementen 0..255 aufaddiert. Mit den gleichen Argumenten wie zuvor. Oder vielleicht sogar für alle
![]() Klar kann man ein Muster (die Gerade) erkennen, wenn man keine inversen Elemente auswählen kann. @Namenloser: Mit etwas Augen zudrücken kann man eine 1-Bit "Gerade" haben; es gibt dann sogar 4 verschiedene :mrgreen:
Code:
Modulo 2 entspricht die Addition dem XOR und die Multiplikation dem AND.
y = 0*x + 0 (mod 2) => 0
y = 0*x + 1 (mod 2) => 1 y = 1*x + 0 (mod 2) => Identität y = 1*x + 1 (mod 2) => Not |
AW: Noise XOR Signal = Noise?
Zitat:
|
AW: Noise XOR Signal = Noise?
Hab zwar keine Ahnung, aber meine Vermutung, wenn ich davon ausgeh, daß es sich um echten Zufall handelt und nicht um einen Zufall aus soeinem 32-Bit-Gernerator, wie im Delphi:
Dann ist die Anzahl der Werte unendlich. Und betrachten kann man nur einen kleinen Bereich davon. Also ist es doch unmöglich rauszubekommen, ob in dem betrachteten Bereich etwas Anderes eingerechnet wurde, denn irgendwo in allen Werten des Zufallsgenerators steckt ganz bestimmt der betrachtete Bereich, egal ob da was eingerechnet wurde oder nicht und wenn man nicht weiß welchen Bereich des Zufalls man betrachtet, dann kann man doch auch nichts wissen oder sonstwie irgendein Muster erkennen? |
AW: Noise XOR Signal = Noise?
Zitat:
Die andere Meinung ist, dass das nicht passiert, wenn die Bits aus dem Generator echter Zufall und gleich-verteilt sind. |
AW: Noise XOR Signal = Noise?
Zitat:
Wenn ich einen gleichverteilt zufälligen Bitstrom (Input) habe und verändere jedes Bit per XOR mit einem vom [u]Input unabhängigen Bitstrom (mein Nutzsignal)[/b], wie kann das Ausgangssignal dann nicht zufällig sein? Wie kann ich die Wahrscheinlichkeit einer '1' erhöhen, wenn ich gar nicht weiß, wann eine '1' ankommt? In dem Augenblick, wo ich die Gleichverteilung meines Inputs verändere, also z.B. etwas mehr Einsen als Nullen produziere, werde ich sehr wohl erkennen, ob das Signal verändert wurde, weil dieses Ungleichgewicht durch das Nutzsignal verändert wird. Gleiches gilt für bestimmte Sequenzen. Der Eingangstrom '01010101' ist auch gleichverteilt, seine Entropie wird aber verändert, sobald ich ihn manipuliere. Zitat:
|
AW: Noise XOR Signal = Noise?
Zitat:
|
AW: Noise XOR Signal = Noise?
Zitat:
|
AW: Noise XOR Signal = Noise?
Ich schließe mich der Aussage von Dejan Vu an.
Angenommen ich mische einem zufälligen Bitstrom per Xor ein stetiges Signal zu, bei dem alle Bits 1 sind. Solange im Ausgangssignal genausoviele 0 wie 1-Bit vorkommen, wird auch das Ergebnis dieser Bedingung entsprechen. Angenommen ich mische einem zufälligen Bitstrom per Xor ein Signal zu, bei dem die Bits 1 und 0 jedesmal wechseln (10101010...). Im Ausgangssignal folgt auf eine 0 genauso häufig eine 1 wie erneut eine 0. Das Ergebnis entspricht auch dieser Regel. |
AW: Noise XOR Signal = Noise?
Das gilt aber genau nur solange, wie das Signal entweder absolut gleichförmig (den Zufall also immer gleich verändert) oder aber selber auch absolut zufällig ist (und damit keine Information beinhaltet).
Sobald der Signalstrom ein Muster enthält, schlägt sich dieses im erzeugten Datenstrom zwangsläufig wieder. Und dieses Muster kann, bei ausreichend intensiver Analyse des Bereiches der das Muster enthält gegenüber anderen Bereichen die nicht manipuliert wurden, mit einer gewissen Wahrscheinlichkeit erkannt werden. Das hat grundsätzlich nichts mit der Sicherheit von OTP's zu tun, denn ohne den originalen, nicht veränderten Zufallsstrom als Schlüssel ist eine Rekonstruktion der Information nicht möglich (da gibts genug mathematische Beweise für ;-) ). Nichts desto trotz ist es aber so, dass der erzeugte Datenstrom durch das eingeflochtene Muster den sonst reinen Zufall an den modifizierten Stellen mit der Ungleichverteilung des Input-Signals verzerrt, und diese Verzerrung ist bei globaler Betrachtung sehr wahrscheinlich irgendwann erkennbar. |
AW: Noise XOR Signal = Noise?
Unter den Annahme:
1. wir reden hier von "echtem Zufall" 2. das Dignal wird ohne Kenntnis des Zufalls generiert schlage ich mich mal auf die Seite von Noise XOR Signal = Noise. Zitat:
![]() ![]() Oder Mathematisch formuliert: Das Zufallsbit kann 0 oder 1 sein, je mit Wahrscheinlichkeit 50%. D.h. eine 1 Im Signal wird zu 50% eine 1 bleiben, oder zu 50% geflippt. Es ist (auch bei geschickter, trickreicher Wahl des Signals) unmöglich, aus dem Ergebnis Rückschlüsse auf das Signal zu erlangen. Oder als Herausforderung: Zitat:
|
AW: Noise XOR Signal = Noise?
Zitat:
Du könntest ja über An- und Ausschalten des Signals sogar jede beliebige Information (Nachrichten, Dateien, ...) binär kodiert übertragen. Was du schreibst ist also ein ganz klarer Widerspruch zur Sicherheit des One-Time-Pad. |
AW: Noise XOR Signal = Noise?
Zitat:
Das One-Time-Pad wird nicht als permanenter Zufallsstrom verwendet, in dem ab und zu eine Nachricht eingeflochten wird. Das One-Time-Pad ist eine doppelt gespeicherte (endliche) folge von Zufall, aus dem pro Nachricht immer genau so viel als Schlüssel verwendet wird, um die Nachricht vollständig zu verschlüsseln. Andersrum: Habe ich eine 100 Byte lange Nachricht, nehme ich die nächsten 100 Byte aus dem OTP als Schlüssel. Da die gesamte(!) Nachricht aus Noise XOR Signal besteht, ist eine statistische Analyse wo denn jetzt Signal anfängt oder aufhört weder Sinnvoll (es steckt eh immer Signal drin), und vor allem wäre es auch aussichtslos, da nie genug Daten für eine Analyse vorlägen. Aber mal ganz praktisch: Noise XOR Noise = 0. Alle Bits sind null. Eine Glatte Nulllinie. Das heisst: lege ich perfekten Zufall über perfekten Zufall, und analysiere diesen Zufall statistisch in seiner Gesamtheit, so werde ich absolut keinerlei Auffälligkeiten finden. Noise XOR Noise ist also 0, und nicht Signal. Daher kann Noise XOR Signal nicht Noise sein, denn Noise XOR Noise ist wieder Null und das Signal wäre flöten. Daher ist Noise XOR Signal maximal Noise2. Nur dann können wir aus Noise2 XOR Noise wieder das Signal erhalten. Dort, wo das Signal anliegt, unterscheiden sich Noise und Noise2. An den Stellen, an denen das Signal nicht anliegt, ist Noise2 wieder mit Noise1 identisch. An den Stellen, an denen Noise2 nun von Noise unterschiedlich ist, wird ein XOR mit Noise nicht mehr zu glatten Nullen führen, sondern zu anderen Werten - nämlich dem Signal. Perfekter Zufall beinhaltet auch Muster, und diese wiederholen sich zufällig. Die Wiederholung jedes einzelnen Patterns in einem Zufallsstrom ist wieder rein zufällig und daher auch normalverteilt. Was heisst das nun aber, wenn wir uns Noise2 an den Stellen angucken, an denen das Signal anlag? Richtig: Noise2 unterscheidet sich von Noise. Das heisst, es findet sich dort eine andere Bitfolge - ein anderes Muster - das bei perfektem Zufall eben nicht genau dort wäre. Dieses Muster wird sich in im normalen Zufallsstrom auch - mehrmals - wiederfinden, aber an anderer Stelle. Das Muster, das in Noise an dieser Stelle war, ist entsprechend auch nicht mehr an dieser Stelle vorhanden. Schaue ich mir nun Noise2 in einer ausreichend großen Menge an, so wird mir auffallen, das zwei bestimmte Muster auffallen. Eines kommt statistisch gesehen zu wenig vor (nämlich das, was in Noise1 an dieser Stelle war), und ein anderes Muster tritt zu oft auf (nämlich das, das durch das Signal erzeugt wurde). Wenn man sich nun die zufällig auch normalverteilten Abstände zwischen den Mustern anschaut, dann wird man, wieder bei ausreichender Datenmenge, auch erkennen können, dass der Abstand zwischen zwei bestimmten Mustern deutlich größer ist als normal und interessanterweise genau an dieser Stelle auch das andere auffällige Muster, mit einem sehr wahrscheinlich auffallend engen Abstand zu anderen seines gleichen vorkommt. Voilá, ich habe mit einer leicht erhöhten Wahrscheinlichkeit feststellen können, das vermutlich an dieser Stelle der echte Zufall modifiziert wurde. Zitat:
Nehme eine beliebige Zahl und XORe sie mit Zufall. XORe den gleichen Zufall erneut, und die Original-Information ist weiterhin vorhanden. Wenn die Information nicht im Ergebnisstrom wäre, dann wäre das ja keine umkehrbare Verschlüsselung, sondern z.B. ein Hash-Algorithmus, bei dem die Original-Information verloren geht und nur ein (reproduzierbares) Abbild der Information übrig bleibt. |
AW: Noise XOR Signal = Noise?
Natürlich gehen wir davon aus, dass Signal und Noise stochastisch unabhängig voneinander sind, wie es bei echtem Zufall sein sollte.
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 23:58 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz