Mi pregunta es un poco genérica, así que estoy inventando una buena historia para justificarla. Ten paciencia conmigo si no es realista ;-)
Historia
El Sr. X, jefe del departamento de seguridad informática de una gran empresa, es un poco paranoico: exige que todos los empleados cambien sus contraseñas una vez al mes, para minimizar los riesgos de identidad o robo de información. Además, no confía en que los empleados puedan encontrar contraseñas seguras.
Por lo tanto, cada mes, genera nuevas contraseñas utilizando un software que escribió y se las entrega a los empleados para que puedan iniciar sesión nuevamente. Pero además de ser paranoico, el Sr. X también es un poco vago: las contraseñas que genera siguen algún patrón, y el algoritmo utilizado para permitir que las personas inicien sesión solo comprueba que la contraseña "se ve bien" de acuerdo con esa regla, y que no está en la "lista caducada".
Desafortunadamente, su comportamiento pretencioso hizo amargar a mucha gente, y uno de ellos, el Sr. Y, decide demostrarle que puede descifrar sus contraseñas. Entonces, una noche, recoge algunas de ellas y comienza a tratar de diseñar un algoritmo de aprendizaje para generar contraseñas válidas, utilizando su computadora personal para verificarlas.
Pregunta
El oráculo utilizado por el Sr. Y es un poco extraño, ya que le dice "la verdad, pero no toda la verdad" (de ahí el adjetivo "taciturno"). Más precisamente: el Sr. Y sabrá que una contraseña es válida cuando su computadora la acepte, pero cuando se rechaza una contraseña, el Sr. Y no sabrá si podría haber sido válida o no : la contraseña puede ser rechazada porque no corresponde a algún patrón, pero también puede ser rechazado porque solía ser válido pero ya no lo es, según la regla de "cambio una vez al mes" del Sr. X.
Entonces, ¿podrá el Sr. Y llegar a algo en ese entorno? ¿O podemos afirmar / probar que las contraseñas del Sr. X son inherentemente impredecibles (como se define en el entorno de aprendizaje PAC, pero tal vez este concepto existe en otros marcos)?
fuente
La dificultad de aplicar ingeniería inversa al algoritmo parece depender de la cantidad de espacio de teclas que ya ha expirado.
Digamos que el algoritmo del Sr. X es muy restringido, por lo que hay (digamos) solo 10,000 claves potencialmente válidas. Si el Sr. X comenzó recientemente esta compañía, entonces hay muy pocas claves caducadas, y por lo tanto pocos "falsos negativos", entonces la ingeniería inversa del algoritmo puede ser relativamente fácil. Si el Sr. X ya expiró 9,000 de las claves potencialmente válidas, y entonces tenemos 9 de 10 "falsos negativos", entonces la ingeniería inversa del algoritmo parece ser mucho más difícil. Y, por supuesto, si el Sr. X ya expiró todas las claves potencialmente válidas, excepto las que el Sr. Y y sus colaboradores ya conocen, entonces el "oráculo taciturno" le dará cero información nueva.
fuente
Parece que, de hecho, solo se pueden utilizar muchas contraseñas válidas. Si el idioma de la contraseña es finito, entonces no hay esperanza (como en este caso, se pueden usar todas las contraseñas válidas, en cuyo caso el oráculo siempre devuelve FALSO).
fuente