¿Puede alguna contraseña hash estar segura?

Primero, MD5 tiene otros problemas además de las rápidas velocidades de hash, incluyendo vulnerabilidades de colisión .

  

Una vez que las computadoras se vuelvan más rápidas, estas no serán mejores que md5.   Así que me pregunto si es posible tener una función hash que sea   ¿Seguro, independientemente del tiempo que lleve ejecutarse?

No, una función hash en sí misma siempre podría ser dañada usando una computadora suficientemente rápida (lo suficientemente rápida como la ambigua bala de plata). Sin embargo, las implementaciones de algoritmos de hash pueden solucionar esto .

Como ejemplo, bcrypt proporciona mecanismos para abordar el aumento de la velocidad de cálculo.

bcrypt usa el concepto de rondas para calcular hashes. Por ejemplo, bcrypt hash su contraseña con un salt y varias rondas:

bcrypt("password","salt",10000)

  

Nota: Como señalado por    darkhogg , el parámetro de rondas no se envía realmente a bcrypt. En su lugar se envía un factor de trabajo. La diferencia es que lo que se envía es en realidad un número N, que es el exponente utilizado para calcular las rondas. Entonces, aunque 10,000 se utilizan aquí como un ejemplo para el número de rondas, la unidad de trabajo real que necesitaría suministrar para obtener 10,000 rondas sería mucho más pequeña.

hash la sal y la contraseña combinadas 10.000 veces antes de almacenar el hash, la sal y el número de rondas. Entonces, supongamos que en el momento inicial de la implementación, 10,000 rondas de hashing toman .02 segundos. Un año después de la implementación inicial, se da cuenta de que 10,000 rondas solo toman .01 segundos, o la mitad del tiempo. Puedes cambiar las rondas a 20,000. La próxima vez que un usuario inicie sesión, su hash se computará con 10,000 rondas para autenticar, pero el hash se almacenará con 20,000 rondas, para una futura autenticación.

  

Así que me pregunto, ¿es posible tener una función hash que sea segura, independientemente del tiempo que demore la ejecución?

No, por supuesto que no. Piense en una función de hash como algo que toma cualquier cadena y genera una huella digital corta de esa cadena. Si tengo una computadora lo suficientemente rápida para enumerar todas las cadenas posibles y calcular sus huellas dactilares (también conocidos como valores hash), entonces puedo crear una tabla de búsqueda que asigne cada valor hash a la cadena que lo produce. Con una computadora infinitamente rápida con memoria infinitamente grande puedo construir una tabla de búsqueda que rompe cualquier función de hash, incluso las teóricas. Periodo.

Para una función hash real como SHA2 que tiene una salida de 256 bits, suponga que recibió la tabla de búsqueda para las 2 posibles salidas ²⁵⁶ , y suponga que le llevará 25 ms realice cada hash, le tomaría 6.7x10 ⁵⁷ x edad del universo solo para verificar que la tabla de búsqueda sea correcta. Ahora, si en lugar de entregarte la tabla de búsqueda, tuvieras que calcularla tú mismo a través de prueba y error, ese número sería aún mayor. Entonces, sí, todas las funciones de hash pueden romperse con una "computadora muy rápida", pero como realmente realmente , como las edades del universo más rápido que cualquier otra computadora que tenemos hoy. [Como lo señaló @ BlueRaja-DannyPflughoeft en los comentarios, obtener suficiente electricidad para hacer este cálculo requeriría consumir varias estrellas, por lo que no es físicamente posible para una sociedad pre-interestelar]

La razón por la que los ataques son manejables en las funciones hash modernas, lo que nos obliga a hacer trucos como salt & iterat para hacerlos más lentos, es que para cosas como las contraseñas no es necesario verificar las 2 ²⁵⁶ posibles pre-imágenes. Si todo el mundo usara generadores de contraseñas aleatorios, esto sería cierto, pero la gente no ... de hecho, el 1.5% de nosotros (1 de cada 68 personas) usa la contraseña "123456" (source) . Por lo tanto, solo necesita comprobar las cosas que la gente usa comúnmente como contraseñas. Una lista de las 100k contraseñas más comunes le proporcionará a casi todos los usuarios en Internet, que una computadora modesta puede verificar en unos pocos minutos si solo se las revisa una vez. Compensamos las contraseñas débiles de las personas haciendo que cada cálculo de hash tarde más tiempo. Si están salados y picados 10.000 veces, entonces, en unos pocos minutos con un hardware modesto, se pueden acumular meses en una plataforma GPU personalizada.

En resumen; Muchos de los problemas que tenemos con los hashes no son porque los hashes en sí mismos son débiles, sino porque les pedimos que protejan los datos, lo que es fácil de adivinar.

Como han dicho Mike Ounsworth, amccormack y Romain Clair en sus respuestas, si tiene poderes de computación ilimitados, podrá romper cualquier algoritmo de hash simplemente (pre) calculando cada entrada posible.

Su pregunta real es probablemente: ¿Para qué necesito el hash y por cuánto tiempo lo guardaré? Entonces, si usa hashes para almacenar contraseñas, recomiendo este enlace: ¿Cómo hash seguro las contraseñas?

Pero si solo lo necesita porque desea calcular de forma única un identificador temporal para alguna entrada, entonces md5 podría ser suficiente para usted.

La seguridad de todo está siempre en un estado de cambio. Hace 40 años, el algoritmo DES también era considerado como seguro, pero una mayor velocidad de cómputo lo ha hecho crackeable con una cantidad bastante modesta de hardware dedicado.

Hace 30 años, se consideraba que el algoritmo de cifrado de Unix (también basado en DES) era lo suficientemente lento para generar contraseñas con hash como para ser seguro. Ahora está obsoleto.

Los algoritmos de hash de contraseñas más modernos, como bcrypt, están diseñados para tener una dificultad variable para explicar el aumento de la velocidad de computación. Así que a medida que aumenta la potencia de cálculo, la dificultad del algoritmo se puede aumentar para mantenerse al día. Es poco probable que el simple aumento del poder de computación en bruto que hemos visto en los últimos 40 años haga que bcrypt quede obsoleto.

La seguridad existe dentro de un contexto, y el contexto siempre está cambiando. Aún así, solo podemos dar cuenta del cambio que podemos predecir. Los aumentos en la potencia de cálculo son cambios predecibles. Sin embargo, no podemos planear una ruptura desconocida del algoritmo (como sucedió con MD5).

El punto es que cualquier seguridad podría romperse en cualquier momento. La seguridad nunca está garantizada.

La respuesta corta es no.

La mayoría de los sistemas criptográficos que se usan en la actualidad, incluidas las funciones hash, solo son seguros contra un atacante que tiene una capacidad de cálculo limitada. Todos pueden ser derrotados usando la fuerza bruta, pero llevará mucho tiempo alcanzarla.

¿Pero es realmente útil intentar romper una clave si le lleva más de 100 años de cálculos intensos y extensos?

  

Una vez que las computadoras se vuelvan más rápidas, estas no serán mejores que md5.

Seguirán siendo mejores, pero quizás no lo suficiente.

Básicamente, un atacante agrieta los hashes de las contraseñas (correctamente salados) tomando las contraseñas posibles y ejecutándolas a través de la función de comprobación de contraseñas. Entonces

Tiempo para descifrar la contraseña hash = (tiempo para verificar una contraseña contra un hash) * (número de contraseñas que el atacante debe probar)

  

Así que me pregunto, ¿es posible tener una función hash que sea segura, independientemente del tiempo que demore la ejecución?

No.