Wie sicher ist XOR?

Elderan · Feb 12, 2008

Hallo,

Original von trivilian
Ich hoffe ich verstehe Dich jetzt nicht falsch. Damit wird eigentlich offensichtlich, dass Funktionen wie rand() in herkömmlichen Implementierungen nicht kryptografisch sicher sind.

Ja das stimmt, die Standard-Rand Funktion ist nur selten kryptographisch sicher, allerdings wissen dieses nicht alle und wird dennoch oft für Dinge eingesetzt, für die diese Funktion nicht geeignet ist.
Neben der Erstellung von Session ID's z.B. wird oft auf die normale Rand Methode zurückgegriffen, wenn man ein zufälliges Passwort generieren möchte.

Wer kennt nicht solch ein PHP Code:

PHP:

<?php
$buchstaben = "abcdefghijklmnopqrstuvwxyz0123456789";
$pw = "";

srand((double)microtime()*1000000);
for($i=0;$i<8;$i++)
  $pw .= $buchstaben{rand(0,strlen($buchstaben)-1)};

echo $pw
?>

Das Problem hierdran, es gibt gerade mal 1 Mio. verschiedene Startwert (ggf. um den Faktor 10 oder 100 weniger), die man heutezutage in Bruchteil einer Sekunde überprüfen kann.
Denkt man, man tut was gutes für die Sicherheit und zwingt dem User ggf. ein 'zufälligs' Passwort auf, aber einen Angreifer der die Hashs in die Hand bekommt wird es freuen, er braucht nur 1 Mio. Passwörter probieren.

In der Kryptografie dagegen kommt er nicht zum Einsatz, da man schon aus wenigen Werten der erzeugten Zahlenfolge die Parameter a und b und damit die vollständige Zahlenfolge berechnen kann.

Die Parameter für a, b und m sind ja bekannt, wegen es ausreicht, 1 Zufallswert zu kennen (erraten) um damit die gesamte Kette nachzuvollziehen.

Leider kann ich das selbst mathematisch nicht beweisen, aber auf der Wikipedia wurde es auch angedeutet:

Dies kann man auch ganz leicht grafisch zeigen:

PHP:

<?PHP
//Seed fuer den Zufallsgenerator
$seed = (double)microtime()*1000000;;

mt_srand($seed);
srand($seed);
$badRandomSeed = $seed;

$generator = 3;
function badRandom($max) {
    //Generator in der GNU C Lib mit rand_type == TYPE_0
    global $badRandomSeed, $generator;
    $badRandomSeed = (($badRandomSeed * 1103515245) + 12345) & 0x7fffffff;

    switch($generator) {
        case 1: return rand(0,$max);
        case 2: return mt_rand(0,$max);
        default: return ($badRandomSeed%$max);
    }

}

header ("Content-type: image/gif");
$image = imagecreate(500,500);
$farbe_body=imagecolorallocate($image,255,255,255);

$farbe_b = imagecolorallocate($image,0,0,0);


for($i=0;$i<15000;$i++) {
    $x = badRandom(500);
    $y = badRandom(500);

    imagesetpixel($image,$x  ,$y ,$farbe_b);
}


imagegif($image);
?>

Wobei rand() auch noch vom Betriebssystem/(ggf. vom Compiler) abhängt.

Wenn man wirklich zufällige Daten bekommen würde, dürfte man eigentlich kein Muster erkennen.

Naja Bild 1 ist rand() unter Windows XP (PHP 5.2.1/XAMPP), Bild 2 der Zufallsgeneator aus Glibc mit rand_type == TYPE_0 und das letzte Bild mt_rand.

Aber das ein kryptographisch sicherer Zufallsgenerator muss nicht nur wirklich gute Zufallszahlen (statistisch betrachten) generieren, sondern an diesen werden noch weitere Aspekte gestellt.
z.B. muss es unmöglich, aus bisherigen Zufallszahlen auf zukünftige zu schließen (beim TYPE_0 Generator des Glibc reicht 1 Zufallszahl um alle weiteren zu berechnen) und vieles mehr.
Gute (kryptographisch sichere) Zufallsgeneratoren zu entwickelt ist wirklich schwierig.

Mehr zum Thema hier:
Cryptanalytic Attacks on Pseudorandom Number Generators

trivilian · Feb 13, 2008

Ja das kann ein Indiz sein! ;-)

Für die Alltagstauglichkeit ist dieser Indiz wahrscheinlich schon ausreichend genug. Aber wenn es ernst wird, kann man sich da vielleicht auch nicht verlassen.
Wir haben ja nur ein eingeschränktes Verständnis von Zufall und wenn das Ergebnis wirklich zufällig mal alle Pixel in einer Ecke liefert ( wem das passiert, der darf sich bei mir melden und einmal für mich die Lotto zahlen tippen ^^) würden wir das nicht als zufällig anerkennen.

Ich hab mir einmal erlaubt durch ISAAC 15000 Pixel in eine 500x500 Grafik zu setzen.
Hier wär ja mal ein Vergleich zwischen mt_rand() und ISAAC interessant.
Was würdest Du daraus lesen? Trifft ISAAC öfter die gleichen Pixel oder wird in mt_rand() vermieden die gleichen Werte zu treffen?
Oder sind andere Ergebnisse von mt_rand() auch deart "gelichtet"?

Vielleicht hab ich ISAAC auch falsch implementiert... hab mal den Code in den Anhang gelegt.

Elderan · Feb 13, 2008

Hallo,
das liegt vermutlich daran, dass dir ISAAC auch negative Zahlen zurück gibt.

Habs mal in PHP Implementiert:

PHP:

<?PHP
//Seed fuer den Zufallsgenerator
$seed = (double)microtime()*1000000;;

mt_srand($seed);
srand($seed);
$badRandomSeed = $seed;

$isaac = file_get_contents("isaac.txt");

//Code saeubern
$isaac = str_replace(array(" ","\n","\r"), "", $isaac);
$generator = 3;
function badRandom($max) {
   global $badRandomSeed, $generator;
	$badRandomSeed = (($badRandomSeed * 1103515245) + 12345) & 0x7fffffff;

	switch($generator) {
    case 1: return rand(0,$max);
	 case 2: return mt_rand(0,$max);
	 case 3: return (isaac()%$max );
	 default: return ($badRandomSeed%$max);
	}
}


$isaac_pointer = 0;
function isaac() {
 global $isaac, $isaac_pointer;


 //3 Hex = 12 Bit  aus ISAAC auslesen
 $str = substr($isaac, $isaac_pointer, 3);
 $isaac_pointer += 3;


 return (hexdec($str));
}


header ("Content-type: image/gif");
$image = imagecreate(500,500);
$farbe_body=imagecolorallocate($image,255,255,255);

$farbe_b = imagecolorallocate($image,0,0,0);


for($i=0;$i<15000;$i++) {
	$x = badRandom(500);
	$y = badRandom(500);
  imagesetpixel($image,$x  ,$y ,$farbe_b);
}


imagegif($image);
?>

Die isaac.txt wurde gefüttert durch die randtest.c, nur dass dort i bis 60 läuft (um genügend Werte zu haben).

Dabei entstand dann auch ein zufällig aussehendes Bild.

Was würdest Du daraus lesen? Trifft ISAAC öfter die gleichen Pixel oder wird in mt_rand() vermieden die gleichen Werte zu treffen?

Weder die eine Möglichkeit noch die andere wäre würde man dann noch als zufällig bezeichnen.
Wenn ich vermeide doppelte Zufallswerte zu bekommen, wäre diese nicht mehr wirklich Zufällig.
Wie gesagt, hängt bei dir vermutlich an negativen Zufallszahlen.

Asonsten gibt es auch eine FIPS-Testprozedur um zu überprüfen, ob 'zufällige' Daten auch wirklich zufällig sind, also statistisch betrachten.
Diese ist auch in CrypTool, und sowohl mt_rand als auch ISAAC erfüllen natürlich diese FIPS-Testbatterie.
Wenn nicht, hätte man einen wirklich schlechten Zufallsgenerator.

weltio · Feb 13, 2008

Dies ist so nicht richtig, nicht alles basiert auf dem Aktion-Reaktion. Da ich keine Lust habe dir einen Exkurs in Quantenmechnik zu geben verweise ich mal auf Google, Wikipedia und co.

Google, Wikipedia und Co irren sich des Öfteren. Nur weil man heute vielleicht nicht alle Zusammenhänge kennt, heisst das nicht, dass heutige Ergebnisse der Forschung endgültig sind.
Früher dachte man höchstwahrscheinlich auch, Frauen würden "zufällig" ein Kind bekommen. Später kam man dann dahinter, dass man dafür schon ein Bisschen Sperma benötigt,,,
Früher dachte man auch, Donner und Blitz erschienen "zufällig" (oder meinetwegen auch aufgrund irgendwelcher Launen Thors oder wem auch immer). Heute ist man da hoffentlich schon weiter.

oO, an Zufall in der Natur nicht glauben aber mal flux ne Zeitmaschine bauen.

Steht sich das etwa diametral gegenüber?

Das ist so nicht richtig.
Mal angenommen, du kannst so eine Zeitmaschine bauen wie wir sie aus 'Zurück in die Zukunft' kennen, dann beobachtest du ja einen Prozess der bereits stattgefunden hat und dessen Ausgang bereits feststeht.

Ja und dieser Ausgang steht auch schon fest, bevor man in die Vergangenheit reist. Ganz einfach weil die Faktoren dieselben sind.

Der Münzwurf ist in der Tat nur von Faktoren abhänig, allerdings macht dies ihn noch lange nicht berechenbar.

Doch! Man muss nur alle Faktoren kennen.
Ich weiss, dass das Ergebnis von f(19) = 23 ist. Ich weiss ohne den Algorithmus aber nicht, was dabei rauskommt. Also benötige ich diesen, um vorher zu wissen, dass f(19)=23 ist. In unserem Beispiel gibt es natürlich unendlich Möglichkeiten. Angenommen wir nehmen die womöglich einfachste: f(x)=x+4. Dann wissen wir, egal was wir für Ausgangswerte haben, was das Ergebnis sein wird, bevor wir den Versuch gestartet haben. (Da das hier einfache Mathematik ist, und das Ergebnis nur durch Berechnung (jaja, ich weiss, Parabelrechner, etc.) hervorkommen kann, muss man sich hier einfach mal ein Experiment vorstellen ^^). Ob f(x) nun nur von einer Variable oder von 1000000000^99999999999, ist vollkommen egal. Das tut der Rechnung nicht weh. (Beansprucht nur mehr Zeit). Würde man alle Variablen kennen, könnte man die Chaostheorie auch verifizieren (oder besser nicht-falsifizieren -> Karl Popper hieß der Mensch wohl).

Das ist aber nicht richtig.
Da du ja anwesend bist beim Wurf, aber nur zuguckst, kann diese minimale Änderung im System schon dazu führen, dass du ein anderes Ergebnis beim Münzwurf erhälst.
[...]

^^ Ein interessanter Aspekt. Dann fahr halt nicht selbst in die Vergangenheit, sondern lass dir diese Simulieren ^^ Das Ding ist, dass auch die Algorithmen der Natur vollkommen gleich sind. Man muss nur die Variablen kennen und kann das Ergebnis berechnen, vorhersehen, zeigen...
Eine Münze kann nicht anders fallen, wenn wirklich exakt alle Variablen die gleichen sind.
Das ist doch doof für die Natur

(ist ja auch bei Schrödigners Katze so, nur wenn man die Kiste aufmacht muss die Katze sich nun entscheiden, ob sie tot oder lebendig ist )

Wieso? Wenn ich weiss, dass der Geigerzähler ausgeschlagen hat, weiss ich, dass die Katze tot ist. (Ich glaube aber dass ich das nicht richtig verstanden habe. Es ist doch so, dass die Katze sterben muss, wenn der Geigerzähler auslöst, da dieser einen Pistolenschuss o.ä. zur Folge hätte)

Auch wenn du beim 'zweiten' Wurf, also nachdem du in die Vergangenheit gereist bist, ein anderes Ergebnis erhalten würdest, könntest du nicht feststellen, dass du ein anderes Ergebnis erhalten hast.
[...]
Jetzt, in der Vergangenheit, wirfst du die Münze und es kommt 'Kopf', du schaust auf deinen Zettel und dort wird 'Kopf' stehen, denn dein Ich in der Vergangenheit hat beim Münzwurf 'Kopf' gesehen und dieses auf den Zettel geschrieben.

Das muss man sich auch merken

Sicherlich kannst du sagen, dass sich die Synapsen anders gebildet hätten, etc. aber das ist ja auch das dumme an einer Reise in die Vergangenheit

(auch bezüglich des Großvaterparadoxons)

Wie du siehst, eignet sich Zeitreisen sehr schlecht um gegen Zufall zu argumentieren.

Dann stell dir einfach vor, du würdest alle Variablen kennen. Dann könntest du ganz einfach alles vorhersagen

Also, wie bereits mehrfach erwähnt, kann man fertigen Programmcode disassemblen und somit an deinen 'geheimen' Algorithmus gelangen. Deswegen sollte man auch stets darauf achten, dass man dem Kerckhoffs? Prinzip 'treu' bleibt.

Ja das habe ich schon verstanden ^^

Dann solltest du ihn aufbessern

Deshalb antworte ich ja auch immer so fleißig

Wie gesagt, den Algo. geheim zu halten funktioniert nicht.

Ja so weit waren wir schon - dachte ich jedenfalls.
Wenn der Algorithmus von einer zufälligen (hier das erwähnte semantische Problem - Nehmen wir an, Zufall heisst "nicht so leicht reproduzierbar und vorhersehbar") abhängig ist, dann ist es doch egal, ob der Algortihmus geheim oder offen ist.

Ich seh in deinem Modell oben nicht, wo nun der Schlüssel zum Einsatz kommt.
Wie sieht die Verknüpfung von Schlüssel und '46465189,55454866' aus? Wie generierst du überhaupt diese komische Zahl?

Soweit ich mich entsinne, war es Dein Modell

Die wurde folgendermaßen generiert: einfach auf dem Nummernblock rumtippen!
Nochmal: Man nehme einen Text von vier Buchstaben.
Jedes Bit wird mit einer Zufallszahl (gemäß obiger Definition) verXORt.
Ohne die Zahlen kann ich den Text nicht wieder zurückholen. Korrekt?
Der Text kann auch "eeee" lauten. Das ist egal, da ja jedes Bit mit einer anderen Zahl (sind Werte- und Definitionsmenge bei XOR beschränkt?) verXORt wird. Dadurch kann meines Erachtens kein Muster entstehen.

Also deine gesamte Methode ist extrem konfus, ein kleiner Pseudo-Code (verschlüsselung und entschlüsselung) würde helfen, so dass man dir die Schwächen deiner Methode dir aufzeigen kann.

Meinetwegen:

Code:

int i = Math.random.nextInt*Math.random.nextInt //Zufallszahlen multiplizieren (natürlich nur als Beispiel die Math.Zufallszahlen)
String c = "Hallo"
chars ausC[] = c.toCharArray;
for(int a=0; a<ausC.length;a++)
{
 ausC[a]=ausC[a] XOR i //pseudocode
}

Wenn du sagst, dass IPSec potenziell unsicher ist, könnte man darüber getrost lächeln.

Falsch. Wenn ich sowas sage, dann muss ich es beweisen. Die Tatsache ändert sich nicht durch den Autor.
Die Glaubwürdigkeit hängt von den Beweisen ab

Bei allen gängigen Runtime Librarys, die ich kenne (VB, Delphi, C,...) ist das nicht so wie du sagst.

Da greife ich dann zumindest meist auf Hardwarerauschen zurück, dass sich unter Linux ganz einfach aus /dev/random lesen lässt.

Ich weiss allerdings nicht, ob Windoof eine ähnliche Funktion bestitzt.

trivilian · Feb 13, 2008

@Elderan: yepp! Die negativen Werte habe ich vergessen!

edit:
Um nochmal zum Ursprung der Diskussion zurückzukommen:
XOR ist wahrscheinlich selbst in Verwendung mit One-Time-Pads kaum praxistauglich. Schließlich müsste man die Schlüssel austauschen und das benötigt wiederum kryptographische Austauschverfahren ( sofern man das nicht offline machen will).
Und selbst wenn die Lister sicher übergeben wird, so wäre die Schlüsselliste immer ein Angriffspunkt.

Alles in allem finde ich XOR daher eher... naja suboptimal ^^

Elderan · Feb 13, 2008

Hallo,

Original von weltio
Doch! Man muss nur alle Faktoren kennen.

Und auch noch alle exat bestimmen können

Es gibt Funktionen, bei denen ist:
f(-0.00001) = 5166214
f(0) = 1
f(0.00001) = 2/3
f(0.00002) = -992354314

Ein Beispiel ist das Dreikörperproblem.
Hat man 2 Sonnen und 1 Planeten der um diese kreist, kann man natürlich die Umlaufbahn von dem Planeten mehr oder weniger berechnen/simulieren, wenn dies ein abgeschlossenes System ist.
Ändert man die Startposition des Planeten aber nur um 1 mm, kann es sein, dass der Planet nicht mehr irgendwann mit Sonne A kollidiert sondern mit Sonne B oder ggf. auch in eine stabile Umlaufbahn gelangt.

Und 1 mm bei zig Milliarden Kilometern abstand ist nicht viel.

Ähnlich beim Münzswurf, du hast immer irgendwelche Messungenauigkeiten die das Ergebnis fundamental beeinflussen können, selbst wenn diese im Milliardstel Bereich sind. Genau Messen können wir nie, damit auch nie genau berechnen.

^^ Ein interessanter Aspekt. Dann fahr halt nicht selbst in die Vergangenheit, sondern lass dir diese Simulieren ^^ Das Ding ist, dass auch die Algorithmen der Natur vollkommen gleich sind. Man muss nur die Variablen kennen und kann das Ergebnis berechnen, vorhersehen, zeigen...
Eine Münze kann nicht anders fallen, wenn wirklich exakt alle Variablen die gleichen sind.

Durch deine Reise in die Vergangenheit sind aber z.B. nicht mehr alle Variablen gleich. Denn dann gibt es z.B. bereits 1 Menschen und 1 Zeitmaschine mehr auf der Erde, als wenn du nicht zurück gereist wärst.
Dies ändert bereits etwas an der Masse der Erde (die Gesamtmasse, also mit Menschen etc.) und noch viele andere Werte.

Wieso? Wenn ich weiss, dass der Geigerzähler ausgeschlagen hat, weiss ich, dass die Katze tot ist. (Ich glaube aber dass ich das nicht richtig verstanden habe. Es ist doch so, dass die Katze sterben muss, wenn der Geigerzähler auslöst, da dieser einen Pistolenschuss o.ä. zur Folge hätte)

Du weist aber eben nicht, ob der Geigerzähler ausgeschlagen hat oder nicht, da die Kiste absolut 'Dicht' ist, heißt es gelangt auch kein Ton, also allgemein keine Information, nach draußen.
Und keine Angst, Schrödingers Katze kann man logisch nicht verstehen, man muss es hinnehmen und akzeptieren dass es solch unmöglichen Dinger (bzw. sich gegenseitig ausschließenden Dinger) in der Quantenmechanik gibt.

Dann stell dir einfach vor, du würdest alle Variablen kennen. Dann könntest du ganz einfach alles vorhersagen

Nicht in der Quantenmechanik.
Du kannst nicht berechnen, ob dieses instabile Atom nach der Halbwertzeit zerfallen ist oder nicht.
Genauso wenn du mit einzelnen Photonen auf einen Strahlenteilerwürfel 'schießt'. Du kannst nicht berechnen, ob das Atom nun weiter fliegt oder ob es 'abbiegt'.

Nochmal: Man nehme einen Text von vier Buchstaben.
Jedes Bit wird mit einer Zufallszahl (gemäß obiger Definition) verXORt.
Ohne die Zahlen kann ich den Text nicht wieder zurückholen. Korrekt?
Der Text kann auch "eeee" lauten. Das ist egal, da ja jedes Bit mit einer anderen Zahl (sind Werte- und Definitionsmenge bei XOR beschränkt?) verXORt wird. Dadurch kann meines Erachtens kein Muster entstehen.

Soweit korrekt.

Das Problem ist jetzt:
Wie kommt diese Zufallszahl zum Empfänger?
Wenn diese auf sicheren Wege zu ihm gelangt hast du ein One Time Pad

Wird diese mit dem Geheimtext versendet, dann hast du nicht viel an Sicherheit gewonnen.
Bzw. da verlagert man dann das Problem darauf, wie verschlüssel ich die Zufallszahl?

PS:

Wenn du sagst, dass IPSec potenziell unsicher ist, könnte man darüber getrost lächeln.

Zum Vergrößern anklicken....

Falsch. Wenn ich sowas sage, dann muss ich es beweisen. Die Tatsache ändert sich nicht durch den Autor.
Die Glaubwürdigkeit hängt von den Beweisen ab Augenzwinkern

In der Mathematik ist dieses wohl war, nur lassen sich viele Aussagen aus dem Alltag nicht wirklich beweisen.
Wenn Bruce Schneier und Niels Ferguson sagen, IPSec ist potenziell unsicher, da dieses Protokoll zu komplex ist, kann man daran natürlich zweifel und es als schwachsinn abtun, allerdings tut man gut daran ihnen zu glauben.

Wenn irgendwer anderes, unbekanntes, gesagt hätte, IPSec wäre potenziell unsicher, da zu komplex, hätte man diese Person bischen belächelt und sich im Stillen gedacht, dass diese Person einfach nicht ausreichend Expertise besitzt und seine Aussage einfach ignoriert.
Wenn aber zwei krypto-Gurus sagen, dass IPSec einfach zu komplex ist, dann nimmt man sich das doch zu herzen.

Ähnlich ist es in vielen Lebenssituationen, was das Leben auch sehr angenehm macht, bzw. was überhaupt fortschritt ermöglicht.
Jeder weiß aus der Schule, dass aus 0*x = 0 ist bzw. aus x*y = 0 folgt dass x=0 oder y=0 sein muss. Dieses oder andere ähnliche Banalitäten zu beweisen ist so auf anhieb gar nicht so leicht, dennoch werden solche Rechenregeln überall verwendet ohne jemals einen mathematischen Beweis dazu gesehen zu haben. Wir verlassen uns einfach auf Sachen, wo andere Experte sagen dass sie stimmen.
Würde man wirklich alles hinterfragen, müsste man bevor man VWL oder was auch immer studieren will, zuerst ein Mathestudium absolvieren, damit man beweisen kann, dass 0*x = 0 ist. Fortschritt wäre so nicht möglich.

Ähnlich wenn du zum Arzt gehst, da vertraust du auch auf sein Expertenwissen und zweifelst nicht an seiner Diagnose, auch wenn er diese nicht wirklich bewiesen hat.
Naja, wir kommen vom Thema ab

weltio · Feb 14, 2008

Hallo,
leider verspätet sich meine Antwort doch um einen Tag, da sich meine gestrige Antwort kurz vor dem Erstellen in Wohlgefallen aufgelöst hat.

Nun denn:

Und auch noch alle exat bestimmen können

Es gibt Funktionen, bei denen ist:
f(-0.00001) = 5166214
f(0) = 1
f(0.00001) = 2/3
f(0.00002) = -992354314

Ein Beispiel ist das Dreikörperproblem.
[...]

Sicherlich hast du recht. Aber da du deine Antwort jetzt schon auf die Realität beziehst - ich streite im übrigen keineswegs ab, dass "die Zukunft vorhersehen, berechnen, etc." heutzutage (und auch die nächsten 100 Jahre) vollkommen unmöglich ist - lässt sich erkennen, dass du faktisch (also gesetzt den Fall, man kenne alle Variablen) keine Einwände hast.

Ähnlich beim Münzswurf, du hast immer irgendwelche Messungenauigkeiten die das Ergebnis fundamental beeinflussen können, selbst wenn diese im Milliardstel Bereich sind. Genau Messen können wir nie, damit auch nie genau berechnen.

Nun, sage niemals nie. Der Mensch ist theoretisch ein geniales Wesen. Theoretisch kann der Mensch auch das schaffen. Es scheint nur natürlich, dass er dieses können wird.
Dennoch reicht es ja, die Variablen zu kennen

Durch deine Reise in die Vergangenheit sind aber z.B. nicht mehr alle Variablen gleich. Denn dann gibt es z.B. bereits 1 Menschen und 1 Zeitmaschine mehr auf der Erde, als wenn du nicht zurück gereist wärst.
Dies ändert bereits etwas an der Masse der Erde (die Gesamtmasse, also mit Menschen etc.) und noch viele andere Werte.

Angenommen wir lassen uns die Vergangenheit simulieren, so ändert sich keineswegs die Masse in der Vergangenheit. Das wäre wirklich nur bei einer Zeitreise der Fall. Aber da es sich hier nur um ein Gedankenexperiment handelt, lässt man, wie in allen anderen Gedankenexperimenten, diese, faktisch natürlich vollkommen richtigen, Tatsachen aussen vor.
Theoretisch könnte man auch diese Veränderungen wieder zurückrechnen um auf das Vergangenheitsergebnis zu kommen

Du weist aber eben nicht, ob der Geigerzähler ausgeschlagen hat oder nicht, da die Kiste absolut 'Dicht' ist, heißt es gelangt auch kein Ton, also allgemein keine Information, nach draußen.
Und keine Angst, Schrödingers Katze kann man logisch nicht verstehen, man muss es hinnehmen und akzeptieren dass es solch unmöglichen Dinger (bzw. sich gegenseitig ausschließenden Dinger) in der Quantenmechanik gibt.

Nunja, ich verstehe das anscheinend immernoch nicht. Angenommen ich weiss, dass ein Atom in zwei Sekunden zerfällt und die Katze dadurch stirbt. Wieso sollte ich dann nicht wissen, dass die Katze nach zwei Sekunden tot ist? Ich meine, ich stelle mir das im Moment wie eine Zeitbombe vor. Die Explodiert auch nach zwei Sekunden, wenn ich so einstelle.

Nicht in der Quantenmechanik.
Du kannst nicht berechnen, ob dieses instabile Atom nach der Halbwertzeit zerfallen ist oder nicht.
Genauso wenn du mit einzelnen Photonen auf einen Strahlenteilerwürfel 'schießt'. Du kannst nicht berechnen, ob das Atom nun weiter fliegt oder ob es 'abbiegt'.

Wieso nicht? Wenn ich genaue Daten habe, kann ich das.
Auch bei deiner Funktion oben. Ich benötige doch nur X (und natürlich den Algorithmus) um auf Y zu kommen.

Das Problem ist jetzt:
Wie kommt diese Zufallszahl zum Empfänger?
Wenn diese auf sicheren Wege zu ihm gelangt hast du ein One Time Pad
Wird diese mit dem Geheimtext versendet, dann hast du nicht viel an Sicherheit gewonnen.
Bzw. da verlagert man dann das Problem darauf, wie verschlüssel ich die Zufallszahl?

Irgendwie muss man da irgendetwas machen ^^ Ich habe schon daran gedacht, eine Art der Steganographie dafür zu verwenden. Ich weiss ja nicht, was sicher ist

Also um meine Eingangsfrage zu beantworten: XOR ist sicher, solange man die Zahl (also den Schlüssel) geheim hält. Korrekt?
Ich meine, es kann ja sein, dass irgendeine Art von Algorithmus XOR-Verknüpfungen entdecken und rückgängig machen könnte... ^^

In der Mathematik ist dieses wohl war, nur lassen sich viele Aussagen aus dem Alltag nicht wirklich beweisen.
Wenn Bruce Schneier und Niels Ferguson sagen, IPSec ist potenziell unsicher, da dieses Protokoll zu komplex ist, kann man daran natürlich zweifel und es als schwachsinn abtun, allerdings tut man gut daran ihnen zu glauben.

Nunja, das ist auch kein richtiger Beweis. Das ist eine subjektive Empfindung. So kann jemand vielleicht gerade aufgrunddessen davon ausgehen, dass es sicher ist oder jemand, der "alles durchschaut" weiss es besser o.ä.

Wenn irgendwer anderes, unbekanntes, gesagt hätte, IPSec wäre potenziell unsicher, da zu komplex, hätte man diese Person bischen belächelt und sich im Stillen gedacht, dass diese Person einfach nicht ausreichend Expertise besitzt und seine Aussage einfach ignoriert.
Wenn aber zwei krypto-Gurus sagen, dass IPSec einfach zu komplex ist, dann nimmt man sich das doch zu herzen.

Das würde aber im Umkehrschluss heissen, dass man nur etwas zu sagen hat, wenn man berühmt wird. Es gibt aber Leute, die gerade aufgrund solcher Geschichten berühmt werden.
Wie gesagt ist Komplexität kein guter Beweis. Ein guter Beweis wäre ein richtiger Beweis, der so aussähe, dass ich (oder der Kryptoguru) die Verschlüsselung einfach knackt. Dabei kommt es natürlich auch nicht auf den Namen an

Dieses oder andere ähnliche Banalitäten zu beweisen ist so auf anhieb gar nicht so leicht, dennoch werden solche Rechenregeln überall verwendet ohne jemals einen mathematischen Beweis dazu gesehen zu haben. Wir verlassen uns einfach auf Sachen, wo andere Experte sagen dass sie stimmen.
Würde man wirklich alles hinterfragen, müsste man bevor man VWL oder was auch immer studieren will, zuerst ein Mathestudium absolvieren, damit man beweisen kann, dass 0*x = 0 ist. Fortschritt wäre so nicht möglich.

Naja natürlich. Aber du gehst im Moment davon aus, dass jeder alles Beweisen müsse. Ich redete aber davon, dass jeder alles beweisen kann

Naja, wir kommen vom Thema ab

Solange es interessant bleibt. So sind halt Diskussionen. Sie verlaufen einmal so, einmal so. Dafür gibt es im Moment auch noch keine Gesetzmäßigkeit, da sie ganz einfach von vielen unbekannten Variablen (z.B. deinem/meinem Temprament, Charakter, meinem Wissensstand, etc.) abhängig ist.

Trotzdem danke für die Teilnahme

trivilian · Feb 14, 2008

Irgendwie muss man da irgendetwas machen ^^ Ich habe schon daran gedacht, eine Art der Steganographie dafür zu verwenden. Ich weiss ja nicht, was sicher ist großes Grinsen
Also um meine Eingangsfrage zu beantworten: XOR ist sicher, solange man die Zahl (also den Schlüssel) geheim hält. Korrekt?

Ja und Nein! Wichtig dabei ist, dass der Schlüssel wie schon erwähnt ein One-Time-Pad ist!
Der Schlüssel muss also mindestens genausolang sein, wie der zu verschlüssende Inhalt und absolut zufällig, sonst ist XOR keineswegs sicher.

Der Grund dafür liegt dann nicht in XOR, sondern darin, dass man per Brute Force keine Chance hat, die wahre Nachricht zu ermitteln.
Ein kleines Beispiel:

Nehmen wir an, Du willst jemandem für eine Geheime Aktion ein Schlüsselwortübertragen und per One-Time-Pad verschlüsseln. Die Nachricht beim Empfänger heißt "LOS", wenn die Aktion stattfinden soll und "BYE", wenn die Aktion abgebrochen wird.

Nehmen wir an, Du verschlüsselst das Wort "LOS", dann kann jemand alle möglichen Schlüssel ausprobieren.
Er wird dabei unter anderem die Nachrichten LOS und BYE entschlüsseln, allerdings auch CYA, CIA, FBI, BRD, DDR, W32, 123 ... also alles was "Sinn" macht und 3 Buchstaben lang ist ( wobei es dabei also egal war, ob XOR zum verschlüsseln benutzt wurde).
Er weiß also niemals, welche dieser Worte Du wirklich hättest meinen können.

Ich meine, es kann ja sein, dass irgendeine Art von Algorithmus XOR-Verknüpfungen entdecken und rückgängig machen könnte... ^^

Man kann das also ohne den echten Schlüssel nicht rückgängig machen ( wie gesagt, es geht im Endeffekt weniger um XOR).

So! Und jetzt der Knackpunkt: wenn Du den Schlüssel online sicher übertragen willst, fängst Du wieder von vorne an. Du musst ihn verschlüsseln. Da beißt sich der Hund in den Schwanz ...
Du kannst also praktisch gleich ein anderes Verfahren benutzen oder offline handeln.
Von Verschleierung halte ich nicht viel.
Würde ich versuchen ein One-Time-Pad zu lesen, würde ich mich zuerst fragen, welchen weg der Schlüssel genommen hat. Steganografie steht da bei mir ganz oben auf der Liste. Da der Empfänger wahrscheinlich bekannt ist, sollte die Auswertung des Verkehrs durchaus Ergebnisse bringen!

XOR pur würde keine Sicherheit bieten, egal welche anderen Schlüssel ( sofern kein One-Time-Pad) man nutzt.
Werft vielleicht einmal einen Blick auf kryptographiespielplatz.de
Das ist eine ganz nette Seite für den Einstieg. Gerade, wenn man auch einmal ein wenig Interesse an der Entschlüsselung so einfacher Verfahren wie "XOR" ^^ hat...

Elderan · Feb 14, 2008

Hallo,

Angenommen ich weiss, dass ein Atom in zwei Sekunden zerfällt und die Katze dadurch stirbt. Wieso sollte ich dann nicht wissen, dass die Katze nach zwei Sekunden tot ist? Ich meine, ich stelle mir das im Moment wie eine Zeitbombe vor. Die Explodiert auch nach zwei Sekunden, wenn ich so einstelle.

Das weißt du ja eben nicht.

Bei instablen Atomen gibt man immer eine Halbwertzeit an, diese besagt, nach abblauf dieser hast du eine 50% Chance dass das Atom bereits zerfallen ist.
D.h. ab, theoretisch kann ein Atom, welches eine Halbwertzeit von 2 Sekunden hat, auch in 1 Billionen Jahre nicht zerfallen sein oder schon nach 1 Nanosekunde zerfallen, beides aber eben entsprechend unwahrscheinlich.
Statistisch ist diese Ungenauigkeit nicht weiter schlimm, hast du 1 kg radioaktives Material hast du nach 2 Sekunden eben nur noch 0,5 kg usw.

Für die Katze heißt das, nach Ablauf der Halbwertzeit, also nach 2 Sekunden, hat die Katze eine 50% Chance noch zu leben, bzw. bezogen auf die Quantenmechanik, ist die Katze sowohl tot als auch lebendig und erst wenn man die Kiste öffnet, wird die Katze gewzungen tot oder lebendig zu sein.
Irgendwie logisch verstehen kann man das nicht, stellt aber die 'Paradoxien' da, mit der man es in der Quantenmechanik zu tun hat.

Noch nen paar Zitate:

"Es gab eine Zeit, als Zeitungen sagten, nur zwölf Menschen verständen die Relativitätstheorie. Ich glaube nicht, dass es jemals eine solche Zeit gab. Auf der anderen Seite denke ich, es ist sicher zu sagen, niemand versteht Quantenmechanik." - Richard Feynman, The Character of Physical Law, 1967

"Wer glaubt, die Quantentheorie verstanden zu haben, hat sie nicht verstanden." - Richard Feynman

Wieso nicht? Wenn ich genaue Daten habe, kann ich das.
Auch bei deiner Funktion oben. Ich benötige doch nur X (und natürlich den Algorithmus) um auf Y zu kommen.

Den gibt es aber nicht, da der zerfall des Atomkerns zufällig geschieht.

Aber zurück zum Thema:

Also um meine Eingangsfrage zu beantworten: XOR ist sicher, solange man die Zahl (also den Schlüssel) geheim hält. Korrekt?

Solange die Zahl wirklich zufällig, nur einmal verwendet und >= dem Plaintext ist, ja.

Aber wie gesagt, wenn dein Schlüssel min. genauso lang ist wie der Plaintext, verlagert man nur das Problem dahin, dass man den Schlüssel sicher übertragen muss.
Und dies nur selten möglich und praktikabel.

weltio · Feb 14, 2008

Bei instablen Atomen gibt man immer eine Halbwertzeit an, diese besagt, nach abblauf dieser hast du eine 50% Chance dass das Atom bereits zerfallen ist.

Gibt die nicht an, dass nach dieser Zeit bereit 50% der Masse an radioaktivem Material zerfallen ist? So hatte ich das mal in der Schule gelernt. Aber das mag ja heutzutage nichts heißen :-O

Für die Katze heißt das, nach Ablauf der Halbwertzeit, also nach 2 Sekunden, hat die Katze eine 50% Chance noch zu leben, bzw. bezogen auf die Quantenmechanik, ist die Katze sowohl tot als auch lebendig und erst wenn man die Kiste öffnet, wird die Katze gewzungen tot oder lebendig zu sein.

Mmmh naja, ich kann das nicht so recht verstehen - kann ja sein, dass mir das zu unlogisch ist

Aber wenn ich nicht weiss, ob ein Mensch in Afrika stirbt, heisst das ja nicht, dass er nicht stirbt (bzw. nicht (nicht) mehr lebt) ^^.
Nur weil ich etwas nicht weiss, heisst das nicht, dass der Zustand nicht schon eingetreten ist.

Den gibt es aber nicht, da der zerfall des Atomkerns zufällig geschieht.

Prinzipiell kannst du das genauso wenig beweisen, wie ich beweisen kann, dass es nicht so ist

Aber nach Karl Popper kann man generell nicht verfizieren, sondern nur falsifizieren.
Wenn man drüber nachdenkt, ist das eine sehr kluge Aussage.

Solange die Zahl wirklich zufällig, nur einmal verwendet und >= dem Plaintext ist, ja.

Was heisst die Zahl muss >= dem Plaintext sein? Oder meinst du jetzt die Anzahl der Ziffern in der Zahlenfolge? Habe ich etwas das Prinzip von XOR nicht verstanden?
Ich dachte:
H XOR 5 = X
X XOR 5 = H
X XOR 1698413598463 = Z
Z XOR 1698413598463 = X
Oder gibt es da Definitions- bzw. Wertemengen?
H,X,Z sind Variablen ^^

Aber wie gesagt, wenn dein Schlüssel min. genauso lang ist wie der Plaintext, verlagert man nur das Problem dahin, dass man den Schlüssel sicher übertragen muss.
Und dies nur selten möglich und praktikabel.

Ist es nicht eigentlich unauffälliger, verschlüsselte Nachricht und Schlüssel in einer Datei zu verstecken?
Wie man damit Sicherheit gewährleistet lässt sich auch noch überlegen. Vielleicht sollte es zu Abwechslung etwas sein, was ein Computer unmöglich erfassen kann.
Bsplw. bei einem Bild ein Schlüsselwort (z.B. Hotel, wenn ein Hotel zu sehen/lesen ist)

Elderan · Feb 14, 2008

Hallo,

Original von weltio

Bei instablen Atomen gibt man immer eine Halbwertzeit an, diese besagt, nach abblauf dieser hast du eine 50% Chance dass das Atom bereits zerfallen ist.

Zum Vergrößern anklicken....

Gibt die nicht an, dass nach dieser Zeit bereit 50% der Masse an radioaktivem Material zerfallen ist? So hatte ich das mal in der Schule gelernt. Aber das mag ja heutzutage nichts heißen :-O

Wenn ein Atom nach der Halbwertzeit mit 50% Wahrscheinlichkeit zerfällt, heißt dies für sehr sehr viele Atom, dass nach der Halbwertzeit eben die Hälfte zerfallen ist.

Deine Aussage ist so nicht ganz richtig, dass nach der Halbwertzeit die Hälfte der Masse zerfallen ist.
Was ist wenn die Masse nur 1 Atom ist? Ist dieser Atom dann nach der Halbwertzeit zur Hälfte zerfallen?

Für die Katze heißt das, nach Ablauf der Halbwertzeit, also nach 2 Sekunden, hat die Katze eine 50% Chance noch zu leben, bzw. bezogen auf die Quantenmechanik, ist die Katze sowohl tot als auch lebendig und erst wenn man die Kiste öffnet, wird die Katze gewzungen tot oder lebendig zu sein.

Zum Vergrößern anklicken....

Mmmh naja, ich kann das nicht so recht verstehen - kann ja sein, dass mir das zu unlogisch ist
Aber wenn ich nicht weiss, ob ein Mensch in Afrika stirbt, heisst das ja nicht, dass er nicht stirbt (bzw. nicht (nicht) mehr lebt) ^^.
Nur weil ich etwas nicht weiss, heisst das nicht, dass der Zustand nicht schon eingetreten ist.

Da bist du nicht alleine, der die Quantenmechanik nicht logisch versteht, siehe Zitat von Richard Feynman.

Diese quantenmechanischen Effekte sind allerdings recht praktisch, z.B. lässt sich damit Teleportieren (also Informationen z.B.), Quantencomputer konstruieren die sehr schnell große Zahlen faktorisieren können (RSA wäre dann nicht mehr sicher) oder eben eine absolut sichere Kryptographie erstellen (Quantenkryptographie).

Prinzipiell kannst du das genauso wenig beweisen, wie ich beweisen kann, dass es nicht so ist

Ich kanns nicht beweisen, kluge Physiker aber schon, bzw. ist dies die gängige Meinung unter den Physikern.
Ob man es beweisen kann, weiß ich nicht, Google könnte evt. helfen

Aber nach Karl Popper kann man generell nicht verfizieren, sondern nur falsifizieren.
Wenn man drüber nachdenkt, ist das eine sehr kluge Aussage.

Naja diese Aussage stimmt so auch nicht.
Ich kann durchaus mathematische Aussage wunderbar verfizieren, z.B. dass in den reellen Zahlen aus x*y = 0 eben x=0 oder y=0 folgen muss.
Auch die Relativitätstheorie lässt sich beweisen, genauso die ähnlich bei der Quantenmechanik.
Die Quantenmechanik gehört zu den am meisten überprüften Theorie die es in der Physikwelt so gibt.

Wobei, die heisenbergsche Unschärferelation sagt ja vorallem aus:
"dass jeweils zwei Messgrößen eines Teilchens (etwa sein Ort und Impuls) nicht gleichzeitig beliebig genau bestimmt sind"
Kommen wir zu deinem Algorithmus zurück, bei dem man nur alle Variablen kennen muss.
Nach der (bewiesenen) Unschräferelation lassen sich nicht alle Messgrößen beliebig genau bestimmen, d.h. man kann nicht alle Variablen beliebig genau bestimmen und nach der Chaos-Theorie folgt, dass diese minimalen Ungenauigkeiten zu einem ganz anderem Ergebnis führen können.
Außerdem, wie man beim Welle-Teilchen-Dualismus eindrucksvoll sieht, verändert eine Messung den Zustand des System.
D.h., wenn ich die Werte für alle Variablen messen würde, ändere ich durch die Messung eben diese Werte und nach der Messung hätten sie genau durch diese einen ganz anderen Wert, soll heißen, ich würde nur veraltetet/ungenaue Messwerte haben und könnte den Ausgang nicht berechnen (wenn noch die Chaos Theorie zum Einsatz kommt).
Deswegen sind bestimmte Dinge nicht berechenbar, auch wenn sie nicht eigentlich nur von Faktoren abhängen. Die Welt der Atome/Quanten ist eben sehr ungenau und viele Eigenschaften lassen sich nicht präzise bestimmen, oder die Messung verändert den Wert.

Was heisst die Zahl muss >= dem Plaintext sein?

Die Zufallszahl muss mindestens solang sein wie der Plaintext, dann hast du das besprochene One Time Pad.
Ansonsten, wenn man die Zufallszahl wiederhohlt, hat man eine polyalphabetische Substitution, welche sehr leicht zu knacken ist.

Ich dachte:
H XOR 5 = X
X XOR 5 = H
X XOR 1698413598463 = Z
Z XOR 1698413598463 = X

Z XOR 1698413598463 macht keinen Sinn, nimmt man an Z ist mit 1 Byte repräsentiert ginge maximal Z XOR 255

Aber wie gesagt, wenn dein Schlüssel min. genauso lang ist wie der Plaintext, verlagert man nur das Problem dahin, dass man den Schlüssel sicher übertragen muss.
Und dies nur selten möglich und praktikabel.

Zum Vergrößern anklicken....

Ist es nicht eigentlich unauffälliger, verschlüsselte Nachricht und Schlüssel in einer Datei zu verstecken?

Wenn du Kerckhoffs? Prinzip missachten willst ja, aber dann hängt die Sicherheit nur von der Geheimhaltung des Algos ab, was nicht funktioniert.
Besser wäre dann ein hardcoded Passwort in dem Programm