Meine Frage ist ein bisschen allgemein gehalten, deshalb denke ich mir eine schöne Geschichte aus, um sie zu rechtfertigen. Trage es mit mir, wenn es nicht realistisch ist ;-)
Geschichte
Herr X, der Leiter der Computersicherheitsabteilung eines großen Unternehmens, ist etwas paranoid: Er verlangt, dass alle Mitarbeiter ihre Passwörter einmal im Monat ändern, um das Risiko von Identitäts- oder Informationsdiebstahl zu minimieren. Darüber hinaus vertraut er den Mitarbeitern nicht, dass sie sichere Passwörter erstellen können.
Daher generiert er jeden Monat neue Passwörter mit einer von ihm geschriebenen Software und gibt sie den Mitarbeitern, damit sie sich erneut anmelden können. Herr X ist nicht nur paranoid, sondern auch ein bisschen faul: Die von ihm generierten Passwörter folgen einem bestimmten Muster, und der Algorithmus, mit dem sich Benutzer anmelden können, überprüft nur, ob das Passwort gemäß dieser Regel "in Ordnung" aussieht und ob es ist nicht in der "abgelaufenen Liste".
Leider hat sein anmaßendes Verhalten viele Menschen bitter gemacht, und einer von ihnen, Herr Y, beschließt, ihm zu beweisen, dass er seine Passwörter knacken kann. Eines Nachts sammelt er einige davon und versucht, einen Lernalgorithmus zum Generieren gültiger Passwörter zu entwerfen, der mithilfe seines PCs überprüft wird.
Frage
Das von Herrn Y verwendete Orakel ist insofern etwas seltsam, als es ihm "die Wahrheit, aber nicht die ganze Wahrheit" sagt (daher das Adjektiv "stillschweigend"). Genauer gesagt: Herr Y weiß, dass ein Passwort gültig ist, wenn sein Computer es akzeptiert, aber wenn ein Passwort abgelehnt wird, weiß Herr Y nicht, ob es gültig sein könnte oder nicht : Das Passwort kann abgelehnt werden, weil es nicht gültig ist entsprechen einem bestimmten Muster, können aber auch abgelehnt werden, da es früher gültig war, aber nicht mehr gültig ist, gemäß der Regel "einmal im Monat ändern" von Herrn X.
Wird Mr. Y jemals in der Lage sein, sich in dieser Umgebung etwas auszudenken? Oder können wir behaupten / beweisen, dass die Passwörter von Herrn X von Natur aus unvorhersehbar sind (wie in der PAC-Lerneinstellung definiert, aber möglicherweise existiert dieses Konzept in anderen Frameworks)?
quelle
Die Schwierigkeit des Reverse Engineering des Algorithmus scheint davon abzuhängen, wie viel des Schlüsselraums bereits abgelaufen ist.
Angenommen, der Algorithmus von Mr. X ist sehr eingeschränkt, sodass es (sagen wir) nur 10.000 potenziell gültige Schlüssel gibt. Wenn Herr X diese Firma erst vor kurzem gegründet hat, so dass es nur sehr wenige abgelaufene Schlüssel gibt - und daher nur wenige "falsche Negative" -, kann das Reverse Engineering des Algorithmus relativ einfach sein. Wenn Herr X bereits 9.000 der potenziell gültigen Schlüssel abgelaufen ist und wir 9 von 10 "falschen Negativen" haben, scheint das Reverse Engineering des Algorithmus viel schwieriger zu sein. Und wenn Herr X bereits alle potenziell gültigen Schlüssel abgelaufen ist, mit Ausnahme derjenigen, die Herr Y und seine Mitarbeiter bereits kennen, gibt ihm das "stillschweigende Orakel" keine neuen Informationen.
quelle
Es scheint, dass tatsächlich nur endlich viele gültige Passwörter verwendet werden können. Wenn die Passwortsprache endlich ist, gibt es keine Hoffnung (wie in diesem Fall können alle gültigen Passwörter verwendet werden. In diesem Fall gibt das Orakel immer FALSE zurück).
quelle