¿Cómo será necesario cambiar la seguridad si P = NP?

Question

¿Cómo será necesario cambiar la seguridad si P = NP?

#1 de D.W. (23 votos)

19

Si suponemos que se encuentra que P = NP, ¿cómo deberán cambiarse las medidas de seguridad?

Me gustaría saber las principales medidas de seguridad que se ven afectadas y cómo deberían cambiarse. Podemos suponer que las contraseñas pueden ser hackeadas en el tiempo O (n ^ 4), por el bien del argumento.

Como ejemplo de lo que estoy buscando en parte, es posible que tengamos una respuesta, ya que las contraseñas RSA de 1.024 bits deberían extenderse a 5 millones de bits, o SSH se volvería insegura. Supongo que estoy intentando obtener una medida científica de los cambios que deberían tener lugar sin entrar en el ámbito de la especulación. Así que probablemente tendríamos que determinar primero qué nivel de seguridad es adecuado y luego comparar los cambios necesarios. Por lo tanto, para tener este nivel como parte de la pregunta, podemos usar prácticas de seguridad comunes vigentes hoy.

Soy un tanto novato en el ámbito de la seguridad de TI, así que espero que alguien pueda ayudarnos a señalar lo que es importante saber en este escenario.

passwords authentication cryptography exploit

pregunta Matt Groff 16.03.2012 - 17:17

fuente

1 respuesta

Lea otras preguntas en las etiquetas passwords authentication cryptography exploit

ESET advierte: Skype intenta comunicarse con una computadora remota desconocida ¿Cuáles son las diferencias entre los estándares de autenticación U2F y UAF FIDO?

score 23 · Answer 1

La respuesta es: depende.

Supongamos que encontramos un algoritmo de tiempo O (n ^ 4) para un problema NP-completo como SAT, donde la constante oculta por la notación big-O no es demasiado grande. Eso mataría a casi toda la criptografía moderna, incluida la criptografía de clave simétrica y la criptografía de clave pública. Lo único que quedaría de pie serían los criptosistemas teóricamente seguros como el pad de una sola vez y la autenticación de mensajes al estilo de Carter-Wegman.

En ese caso, uno podría ser capaz de responder mediante el diseño de sistemas criptográficos con una clave de 10 millones de bits o algo así, pero, vaya, la vida apestaría. Sería bastante difícil transferir claves tan grandes. Y sería muy difícil confiar en el sistema de cifrado resultante para cualquier tipo de seguridad duradera. Si hoy a alguien se le ocurre un algoritmo O (n ^ 4) para SAT, debe asumir que quizás el próximo año alguien descubra cómo mejorar eso a O (n ^ 3 log n) o algo así. Entonces, en la práctica, si alguien encuentra un algoritmo práctico de tiempo O (n ^ 4) para SAT, una gran cantidad de criptografía se basa en una base de arena, y tendríamos que volver a pensar todo.
Alternativamente, suponga que alguien encontró un algoritmo de tiempo O (n ^ 100) para un problema de NP-completo como SAT. En términos de impacto inmediato, tal algoritmo sería totalmente inútil para el craqueo de la criptografía. Sin embargo, de muchas maneras estaríamos en la situación del último párrafo: todos se preguntarán si el próximo año algún genio mejorará esto a O (n ^ 10), y luego el año después de eso O (n ^ 4), y pronto. Esto podría fácilmente ser un golpe para la confianza de la gente en la seguridad de la criptografía moderna. Por lo tanto, esto también sería un descubrimiento bastante impresionante, incluso si no tiene un impacto directo e inmediato.
O, suponga que alguien encuentra una prueba no constructiva de que existe un algoritmo de tiempo polinomial para algún problema de NP-completo, pero sin indicación de cómo convertir esto en un algoritmo real y no hay evidencia de que el resultado sea El algoritmo será eficiente en la práctica. Entonces estaríamos en un estado de confusión. Nadie sabría si tal vez estamos en el mundo de la bala 1 anterior, o el mundo de la bala 2, o algo completamente distinto.

Dicho todo esto, no creo que ninguno de estos escenarios sea muy probable en el futuro previsible. De hecho, me atrevería a suponer que son muy poco probables. Podríamos hablar del efecto que tendría en la criptografía si un asteroide masivo golpeara la Tierra el año que viene. Bueno, el impacto sería bastante devastador, pero la probabilidad es bastante pequeña. Creo que hay cosas mucho más relevantes y probables de las que preocuparse.

Entonces, si te estás preguntando si deberías tomar algunas medidas para protegerte contra la posibilidad de que alguien demuestre que P = NP: no te preocupes. Eso es una pérdida de tiempo. Gasta tu energía en amenazas más realistas.