¿Cómo será necesario cambiar la seguridad si podemos descifrar los hashes de contraseña en un tiempo casi polinomial?

6

Si suponemos que tenemos acceso a algún tipo de pirateo / descifrado de contraseñas generalizado que puede encontrar una contraseña de n bits en el tiempo O (n ^ (registro n)), ¿hay necesidad de alarma?

Esta pregunta surge de algunas investigaciones que estoy realizando en SAT, el problema de la satisfacibilidad booleana . Puede encontrar otra pregunta de StackExchange que detalla un posible resultado aquí . En resumen, estoy tratando de determinar si es posible resolver el SAT en un tiempo casi polinomial.

Esta pregunta asume ingenuamente que es posible utilizar de alguna manera el SAT, junto con alguna transformación adecuada del problema, para hackear contraseñas en la misma cantidad de tiempo.

Lamentablemente, el límite de tiempo establecido anteriormente puede ser una suposición bastante ingenua del rendimiento real de un algoritmo, que puede ejecutarse mucho más rápido en la práctica. Para llegar a este punto, realmente me pregunto si conocemos algún tipo de umbral (en términos de velocidad) donde el pirateo de contraseñas comienza a ser peligroso.

    
pregunta Matt Groff 23.09.2012 - 20:51
fuente

4 respuestas

9

Creo que la mejor manera de responder a tu pregunta es diciendo: la premisa es altamente inverosímil, por lo que el problema simplemente no surge.

También podría preguntar: si suponemos que descubrimos el viaje en el tiempo, ¿hay algún motivo de alarma sobre la seguridad de la contraseña? Claro, si descubrimos el viaje en el tiempo, alguien podría viajar en el tiempo, aparecer poof justo antes de ingresar mi contraseña, mirar por encima del hombro cuando escribí mi contraseña y poof desaparecer antes de que me diera cuenta.

O, si mi computadora puede viajar en el tiempo a pedido, puedo configurarlo para iterar el siguiente ciclo: elegir una contraseña aleatoria, intente ver si es correcta, si es correcta, imprima la contraseña y deténgala; si es incorrecto, retroceda en el tiempo hasta el comienzo del bucle y comience de nuevo. Si el algoritmo de viaje en el tiempo es posible, este es un algoritmo de O (1) tiempo para descifrar cualquier contraseña, ¡dado su hash de contraseña!

Pero, por supuesto, estas respuestas son tontas, porque en el futuro previsible no existe una posibilidad realista de que alguien descubra cómo viajar en el tiempo. Del mismo modo, para un futuro previsible, no hay una perspectiva realista de que alguien descubra un algoritmo para resolver todas las instancias de SAT de manera eficiente. Claro, si alguien pudiera encontrar un algoritmo de resolución de SAT que pudiera resolver cada instancia de SAT en 15 segundos, podría descifrar cada contraseña (dado su hash de contraseña) en 15 segundos. Pero no creo que sea muy probable que ocurra en mi vida.

P.S. Al hacer clic en su enlace, veo que probablemente preferiría una respuesta más técnica. Mi sugerencia es leer sobre el intercambio de tiempo-espacio de Hellman y sobre las tablas del arco iris; Eso le dará una mejor comprensión de los métodos de vanguardia aplicables al descifrado de contraseñas. También puede leer por qué las tablas de arco iris no son aplicables a las contraseñas con sal; es probable que razones similares se apliquen a tus métodos.

Mirando la complejidad del método en su enlace, veo que su método requiere una precomputación 2 v , donde v es el número de variables en la instancia de SAT. En contraste, las tablas de intercambio y arco iris de tiempo-espacio de Hellman requieren una precomputación 2 n , donde n es el número de bits de la contraseña (el número de bits de entrada a la función hash). En la configuración de la contraseña, n será mucho más pequeño que v , por lo que las tablas de arco iris y la compensación de espacio-tiempo de Hellman parecen que funcionarán mejor que tu método. En otras palabras, no me parece probable que su método, incluso si es válido, supere el estado de la técnica en el descifrado de contraseñas o tenga mucha relevancia en la práctica para descifrar contraseñas. Por supuesto, siempre puede intentarlo en un pequeño experimento y comparar su método con los crackers de contraseñas existentes; Esa sería la verdadera prueba. Pero en este momento, no veo ninguna razón para esperar avances en la resolución del SAT que sean relevantes para el descifrado de contraseñas.

    
respondido por el D.W. 23.09.2012 - 21:58
fuente
0

Permítame solo citar sus dos preguntas reales y poner las cosas del SAT a un lado ...

  

Si suponemos que tenemos acceso a alguna forma de pirateo / descifrado de contraseñas generalizada que de alguna manera puede encontrar una contraseña de $ n $ -bit en el tiempo $ O (n ^ {\ log n}) $, ¿hay necesidad de alarma? ?

Si asumimos que eso es verdad por el bien de un experimento mental, entonces sí, estamos claramente en problemas, ya que todas las contraseñas en el mundo serán simplemente irrelevantes. En comparación con descifrar un hash de contraseña, es relativamente fácil conseguir sus manos en dicho hash. No es como si todos supieran la contraseña de todos al instante, pero sería malo.

  

Realmente me pregunto si conocemos algún tipo de umbral (en términos de velocidad) donde el pirateo de contraseñas comienza a ser peligroso.

¿Quieres decir que un hacker "moral" (no cracker) debería dejar de hackear en algún momento? Lo contrario es cierto, en lo que a mí respecta. Si las personas dejan de piratear esto porque temen que se acerquen demasiado a una solución, entonces habrá otros crackers menos morales que no se detendrán. Los piratas informáticos "benignos" son los únicos que pueden señalar los peligros potenciales y al menos tratar de obtener cualquier tipo de advertencia por adelantado.

    
respondido por el AnoE 11.03.2016 - 15:48
fuente
-1

Este tiene un voto de pregunta realmente alto.

De todos modos, si es verdadero, que almacenar hashes de contraseña ~ = almacenar contraseñas de texto sin formato. Ahora considere qué demandas de seguridad se implementarán para almacenar contraseñas de texto sin formato.

En caso de que no sea tan obvio, ahora se requiere el uso de contraseñas completamente diferentes para cada sitio, y esto significa usar un administrador de contraseñas o anotar las contraseñas. Y eso supone que el criptográfico subyacente que protege a SSL sobrevive (no debería).

    
respondido por el Joshua 12.01.2015 - 20:53
fuente
-3

Sí, las grietas en el tiempo casi polinomiales o las contraseñas probablemente conducirían a un número mucho mayor de intrusiones de seguridad. El craqueo de contraseñas por fuerza bruta ya está hecho, cuando los hackers están lo suficientemente desesperados como para esperar un algoritmo de tiempo exponencial. Si los piratas informáticos pudieran descifrar contraseñas en un tiempo casi polinomial, descifrarían aún más contraseñas. Por supuesto, necesitan tener acceso al diccionario de contraseñas para que no se cierren por el número de intentos de contraseña. El número de intentos de contraseña permitidos suele ser una constante, por lo que incluso el crackeo casi polinómico se ejecutaría en bloques a menos que los piratas informáticos tuvieran el diccionario.

Perdóneme, ¿no hay reducciones estándar de SAT a aplicaciones de descifrado? Parece una reducción que debería existir en la literatura. Dado que el cifrado en sí mismo se reduce a SAT a través de la NP completa, los algoritmos de craqueo también usan la misma reducción. Consulte su libro de texto de teoría de la CS para conocer las reducciones de tiempo de duración que se utilizan para demostrar la integridad del NP. Una reducción de poli-tiempo puede ciertamente usarse para transformar un algoritmo de tiempo de psuedo-poli en un algoritmo de descifrado de contraseñas para contraseñas encriptadas, ya que el tiempo de poli es más rápido que el tiempo de pseudo-poli.

    
respondido por el Brent Kirkpatrick 12.03.2016 - 01:25
fuente

Lea otras preguntas en las etiquetas