¿Por qué la gente piensa que esta es una mala forma de hash de contraseñas?

39

Bueno, por favor, dime, ¿qué hay de malo con este código?

$password = "hello";
$password = md5($password);
for($i=1;$i<20;$i++){
    $password = md5($password);
}

Es exactamente el mismo que este:

md5(md5(md5(md5(md5(md5(md5(mD5(md5(md5(md5(md5(md5(md5(md5(md5(mD5(md5(md5(md5(‌​md5($password))))))))))))))))))));

y no creo que un atacante con mi base de datos pueda descifrar cualquier contraseña con longitud > 2.

El atacante tendría que descifrar esta lista de hash md5 para poder obtener la contraseña de texto sin formato:

69a329523ce1ec88bf63061863d9cb14
0dcd649d4ef5f787e39ddf48d8e625a5
5d6aaee903365197ede6f325eb3716c5
cbe8d0c48ab0ed8d23eacb1621f6c5c3
8fa852c5f5b1d0d6b1cb0fad32596c71
91a84cf929b73800d2ff81da28834c64
45b7d5e4d3fca6a4868d46a941076b72
e5b7d9d10fef132829731255ef644319
b3af6ff5f5c7ae757ca816a6cb62f092
150f3682b2e58d1d0e1f789f9ba06982
3f76626950bf31dbc815c667ca4b2b43
44f4c75517671e12946aab3c8c293f98
442256b098b2d88e93428b08b5155308
7fd8ebc5bdff94f24a10decaa1ab64e8
d04bbc863839b720d932a697f0bf443b
de737c934db23c2d1d1026863e7583a8
d745f6394700c4ab1e9ded0924ea35d2
ce9428b51d3a63431c57a435423877b6
7017f40bdb4f1be1f5fae7dd0fc7b907

y con fuerza bruta, debe probar 36 combinaciones 32 (* 19), que es bastante imposible de conseguir; o me equivoco? ¿No es eso cierto?

    
pregunta genesis 24.07.2011 - 16:27
fuente

15 respuestas

34

Otros han descrito las limitaciones de este método hash; Me gustaría señalar un error conceptual en la pregunta:

  

No creo que el atacante con mi base de datos pueda descifrar ninguna contraseña con longitud > 2

     

El atacante tendría que descifrar esta lista de hash md5 para poder obtener una contraseña simple:

     

[lista de resultados intermedios]

El error aquí es pensar que la complejidad de los resultados intermedios proporciona protección contra un ataque de diccionario de fuerza bruta. Creo que el que pregunta está pensando que el ataque debe funcionar hacia atrás, a partir del hash almacenado, y fuerza bruta a su vez cada resultado intermedio.

Esto no es verdad en absoluto; Los ataques de diccionario razonables comenzarán con las contraseñas posibles y atacarán a la pila completa de 20 hash a la vez. Aquí está el bosquejo del algoritmo:

for each candidate password:
    hash 20 times
    compare with stored hash

El uso de esto para verificar todas las posibles contraseñas de 3 caracteres (suponiendo que se imprima ASCII) requeriría solo 20 * 95 ^ 3 = 17147500 hashes, lo que es básicamente trivial. Usar SHA-512 en lugar de MD5, a pesar de tener valores intermedios mucho más grandes, sería más seguro solo porque cada hash tarda un poco más en calcularse.

tl; dr, una función hash compleja no puede salvarte si la contraseña en sí no tiene suficiente entropía.

    
respondido por el Gordon Davisson 27.07.2011 - 03:25
fuente
76

Las cosas incorrectas en tu método son:

  • Usas muy pocas iteraciones (20 es demasiado bajo, debería ser de 20000 o más): el procesamiento de la contraseña sigue siendo demasiado rápido, un atacante con una PC básica todavía podrá "probar" docenas de millones de contraseñas por segundo.
  • No hay sal: un atacante puede atacar varias contraseñas con un costo por contraseña muy bajo, por ejemplo. con tablas precomputadas de contraseñas con hash (en particular tablas de arco iris ).
  • Estás en el proceso de inventar tu propia criptografía. No hay nada de malo en ser inquisitivo y tratar de entender las cosas, pero como no hay una prueba segura para saber si un algoritmo dado es seguro o no, inventar su propia criptografía es a menudo una receta para el desastre. No lo hagas.

Lo que debes hacer es usar bcrypt ; hay una implementación de PHP en el marco de hashing de contraseña de PHP portátil .

    
respondido por el Thomas Pornin 24.07.2011 - 17:00
fuente
17

20x MD5 es un algoritmo de hash rápido, lo que significa que puede generar contraseñas a una velocidad sorprendente.

Deje de usar algoritmos de hash rápidos para almacenar contraseñas. Incluso con sales individuales; Si alguien tiene acceso directo (lectura: fuera de línea) a su base de datos, se puede calcular muy fácilmente.

Este artículo explica por qué es mucho mejor que yo:

enlace

El artículo menciona en gran medida BCrypt (con un enlace a una biblioteca de PHP), pero tenga en cuenta que hay otros algoritmos de hashing lento que pueden serle de utilidad.

    
respondido por el oliland 24.07.2011 - 17:43
fuente
11

El problema es que este es un "algoritmo" bastante obvio y bastante rápido de iniciar.
Es muy probable que haya una tabla de arco iris precomputada disponible para este "algoritmo", e incluso si no la hay, md5 es lo suficientemente rápido como para poder precomputar una en una cantidad de tiempo realista.

Debería siempre usar un salt individual para cada contraseña para evitar este tipo de ataque.

    
respondido por el deceze 24.07.2011 - 16:33
fuente
10

Aparte de lo que ya se ha señalado en las otras respuestas hasta ahora, me parece que tiene un malentendido fundamental en su pregunta. El espacio de salida de una función hash de 128 bits como MD5 no es 36 ^ 32 (aproximadamente 6.3e49), sino 2 ^ 128 (aproximadamente 3.4e38). ¡Eso es 11 órdenes de magnitud!

La criptografía es difícil. Si no sabe exactamente lo que está haciendo (y en muchos casos, incluso si lo sabe), es mucho mejor, mucho no tratar de diseñar algo por sí mismo, sino más bien usar un Solución probada y verdadera. Para ver un ejemplo de la vida real de cómo pueden ir las cosas terriblemente mal cuando no sabe exactamente lo que está haciendo, busque la debacle de la clave OpenSSL de Debian . La versión anterior Netscape PRNG es otro ejemplo. Estoy seguro de que también hay muchos otros, más o menos publicitados.

    
respondido por el a CVn 25.07.2011 - 14:30
fuente
9

Hay cuatro problemas con solo iterar md5 una y otra vez, sin importar cuántas veces lo hagas.

Potencia de cálculo en el tiempo

El primer gran problema aquí es que, tal como está escrito, no se escala con el tiempo para mantenerse seguro a medida que las computadoras se vuelven más rápidas. Lo que es seguro hoy se romperá en momentos en las computadoras del mañana.

Los algoritmos modernos y seguros, como bcrypt y scrypt, se han incorporado en el ajuste para que el algoritmo pueda ajustarse automáticamente para ser más lento a medida que las computadoras atacantes se vuelven más rápidas. Dado que bcrypt también es gratuito y aún es una simple función para ti, no hay ninguna buena razón para no usarlo.

Ahora, tienes el inicio de una estructura de escala integrada en tu código. Sería fácil refactorizar que ejecutar el hash md5 un número arbitrario de veces, de modo que pueda ajustarlo para que sea más lento con el tiempo. Pero eso no es suficiente.

Diseñado para el fracaso

El segundo problema es que md5 es una opción fundamentalmente mala para un hash criptográfico porque fue diseñado específicamente para ser rápido . El propósito de md5 es verificar o comparar rápidamente archivos grandes. Para lograr esto, el hash necesita poder ser computado de manera rápida y eficiente. Esto significa que los objetivos de implementación y diseño del algoritmo están completamente en desacuerdo con el almacenamiento de contraseñas. Las posibilidades de que en algún momento encontremos una manera de calcular un hash md5 que sea órdenes de magnitud más rápido de lo que podemos hacer actualmente son órdenes de magnitud más altas de lo que podremos hacer lo mismo para sha1 o bcrypt.

Degeneración

El tercer problema es que los algoritmos de hash en general tienden a degenerate a medida que los iteras. Para entender esto, tome el texto original suministrado por el usuario. El tamaño conceptual de este texto es ilimitado . Aquí hay un número infinito de valores posibles. Una vez que hemos procesado el texto una vez con md5, hemos bajado a 2 128 número de valores posibles ... aún muy grandes, pero ya no están sin límites. Pero vamos a completar esto otra vez. md5 es bueno, pero no es perfecto . Esos 340 undecillion entradas potenciales tendrán algunas colisiones y producirán una cantidad de resultados que están cerca, pero todavía algo menos que, 2 128 . A medida que continúe iterando, encontrará más colisiones, hasta que finalmente termine con un número que, aunque aún es grande, es significativamente menor que el espacio conceptual con el que pensaba que estaba trabajando.

Ciclos

Finalmente, el cuarto problema es que algunas de sus entradas potenciales originales darán como resultado ciclos : el número de valor 12345 hashes a 98743, que hashes a 67321, que vuelve a 12345, y así sucesivamente. En otras palabras, algunas entradas se desplazarán por el mismo conjunto pequeño de valores hash, y si los vuelve a hacer no será de utilidad . De hecho, cuantas más veces ejecute el hash, mayor será la probabilidad de que una entrada original determinada termine en un ciclo.

Esto se remonta al diseño de md5. Un hash criptográfico podría diseñarse para minimizar (no eliminar completamente, pero al menos minimizar) la degeneración y los fenómenos del ciclo, pero no fue una preocupación en absoluto para md5.

Conclusión

Cualquiera de estas razones es suficiente para no usar md5. Hay otras opciones perfectamente buenas disponibles, y generalmente usan la misma interfaz, por lo que elegir una diferente no es difícil. En algunas plataformas, es tan fácil como cambiar un valor de enumeración que se pasa a la función "createhash". Ponga las tres razones juntas, y continuar usando md5 es una locura.

    
respondido por el Joel Coehoorn 24.07.2011 - 20:51
fuente
7

Tiene una función de hashing unidireccional simple para contraseñas, parece seguro, ¿verdad? Tendrías que hacer muchas suposiciones para forzar la fuerza bruta de un sistema así. Sin embargo, considere un caso malo (ni siquiera el peor de los casos). Utiliza este nivel de seguridad con un sitio de gran importancia, o incluso un sitio con muchos usuarios.

Luego, un día hay un pequeño error de seguridad o su sitio tiene una vulnerabilidad previamente desconocida que se explota y todos los datos de su cuenta de usuario, incluidas las contraseñas con hash, ahora están en manos de "los malos". Los malos van a su PC de bajo costo con una GPU decente en ella y modifican un programa que ya existía para generar hashes para que haga 19 niveles de hashing md5. Luego lo alimentan con un diccionario bien afilado de contraseñas comunes y probables, así como cadenas alfanuméricas aleatorias de longitud creciente. Con el tiempo, la GPU comienza a generar hashes creando una tabla de consulta. En cualquier momento dado, los malos pueden verificar su tabla de búsqueda de hash generada en la lista de contraseñas de hash y, debido a que no usó un salt por contraseña, puede encontrar coincidencias fácilmente. Con el tiempo, a medida que la GPU continúa trabajando, se revelan más y más contraseñas, hasta que solo quedan las contraseñas de mayor fortaleza.

    
respondido por el Wedge 25.07.2011 - 04:56
fuente
6

MD5 no es el mejor hash que se usa hoy en día para la seguridad en la actualidad; Los hashes pueden calcularse demasiado rápido (aunque el mayor defecto de md5 es la facilidad para generar colisiones). Sus solo 128 bits (16 ^ 32 = 2 ^ 128 ~ 10 ^ 38); intente sha-256 (2 ^ 256 ~ 10 ^ 77; es 2 ^ 128 veces más teclas) o sha-512. El fortalecimiento de claves es una buena práctica (por ejemplo, se tarda 20 veces más en generar una tabla de arco iris); pero aún así, 20 veces más, no es tan largo (por ejemplo, usa 20 máquinas y toma el mismo tiempo), pero se hace mejor con una sal aleatoria. Sería mucho mejor fortalecer las teclas, por ejemplo, 100.000 veces.

$password = "hello";
$salt = random_str(); // generate some relatively short random str
$password = sha256($password);
for($i=1;$i<100000;$i++){
    $password = sha256($salt + $password);
}
$sep = "|";
$password_scheme = "SHA256x100k";
$password = $salt + $sep + $password_scheme + $sep + $password;

Usando un lenguaje de pseudocódigo donde + concatena cadenas y random_str () es una función que genera una cadena aleatoria corta. El propósito de la sal aleatoria es que si un atacante ve su código fuente, ve sus hashes de contraseña, debe generar una tabla de arco iris separada para cada sal diferente (o una para cada contraseña). Así que ahora, en lugar de tener que generar una tabla de arco iris para obtener todas las contraseñas de los usuarios, tienen que generar una tabla de arco iris para obtener una sola contraseña. También es una buena idea documentar el esquema de contraseñas en el hash, por lo que puede actualizarlo según sea necesario, por ejemplo, migrar de SHA256x100k a SHA256x1k si necesita utilizar menos la CPU o decide cambiar a un hash diferente más adelante.

Por supuesto, no es la mejor idea crear tu propio método criptográfico personalizado si no eres un experto en criptografía. Definitivamente, usted deja la oportunidad para los agujeros de seguridad sutiles como ataques de tiempo incluso con algoritmos aparentemente seguros. bcrypt es probablemente tu mejor apuesta.

Nota: MD5 es particularmente vulnerable a los ataques de colisión, pero realmente no tienes que preocuparte por las colisiones en los ataques de preimagen (que es el método de ataque contra los hashes de contraseña). Un atacante obtuvo una lista de hashes de contraseña (h) de alguna manera, y aprendió la rutina de hash (md5 x 20 o sha256 salada x 100k), y está tratando de obtener cualquier mensaje m, tal que hash_routine (m) = h, para permitirles en su sistema.

La vulnerabilidad de colisión hace que te preocupes es que si tienes un hash (m1) = hash (m2) cuando m1! = m2; así que si descarga algo en el que la gente haya comprobado que el archivo m1 es seguro y quiere asegurarse de que realmente descargó m1, comparará el hash (m1) con el hash público md5. Si hay una versión maliciosa de m2 con el mismo hash md5, entonces no puede estar seguro de que m1 esté seguro al verificar su suma de md5.

    
respondido por el dr jimbob 25.07.2011 - 20:03
fuente
5

Las tablas de arco iris funcionan porque varios sistemas usan esquemas similares para manejar datos. Si bien está bien considerado que agregar una sal debe ser una característica universal del hash de contraseñas, agregar una serie de rondas también ayuda a derrotar las tablas de arco iris. A saber: una tabla de arco iris para cualquier subconjunto de caracteres en MD5 no puede dar lugar a una coincidencia para ninguna contraseña en su sistema, excepto por colisión accidental. La función de reducción de la tabla del arco iris convertirá cada hash generado en una cadena que coincida con la letra, el número y el patrón de símbolos para el que está diseñada la tabla. En el momento en que un método hash genere un hash que incluya un símbolo fuera de ese rango (una certeza virtual como entrada a su función hash es la salida de un hash), evitará que la tabla funcione.

El hecho de que su sistema sea simple o incluso conocido públicamente no importa tanto como para vencer a una tabla de arco iris solo requiere que sus hashes no puedan haber sido creados en gran número por el método utilizado para generar esa tabla.

Wikipedia ha considerado el problema de la fuerza del hash a lo largo del tiempo, ya que su base de datos de usuarios es muy conocida y muy antigua, y utilizó varios métodos de hashing que ahora son inseguros. La solución discutida fue clave en los diferentes métodos. Para calcular una contraseña allí, se busca la versión del método hash y la contraseña se calcula de acuerdo con eso. Al iniciar sesión con un hash de versión anterior, se actualizaría a la versión más reciente.

Thomas mencionó que debes usar más rondas para tu hash. Lo que no se ha hablado es cómo determinas cuántas rondas usar. La respuesta a esto es confusa, pero básicamente se reduce a "¿Cuántas iteraciones puedo realizar para la carga de inicio de sesión en mi sistema?" Si tiene 10,000 usuarios que inician sesión cada minuto, podría estar dispuesto a dedicar una carga de CPU del 25% a eso. Para eso, elige una serie de iteraciones que te permitan hacer aproximadamente 700 cálculos por segundo.

    
respondido por el Jeff Ferland 24.07.2011 - 17:56
fuente
4

No, estás equivocado. El problema con los hashes md5 es que hay una probabilidad relativamente grande de colisiones: hay muchas cadenas que generan el mismo hash. Y como creo que solo hay 36 ^ 32 posibilidades, todas las cuales se pueden probar en aproximadamente 35 horas (y obtendrán un resultado mucho antes porque hay una gran posibilidad de colisiones), ya no se considera un buen hash. Sin mencionar que probablemente exista una tabla de arco iris para 20 md5 hashes. Además, hay personas que dicen que md5 es realmente reversible, pero no estoy seguro de eso.

Hay dos formas de hacer que las contraseñas sean más difíciles de hackear:

  1. Usa una sal estática. Básicamente, esto hace que las tablas arco iris sean ineficaces, porque el pirata informático ya no puede usar solo palabras en inglés, ya que su sal (que el pirata informático ojalá no sabe) está constituyendo una gran parte de la cadena. Pruebe las sales largas que consisten en muchos caracteres especiales;
  2. Utilice un algoritmo de hashing mejor y más largo como whirlpool o sha512. Esto obviamente aumenta enormemente la cantidad de posibilidades;
  3. hash su cadena varias veces (x). Esta es una de las cosas que has hecho bien: si el pirata informático conoce tu sal y la cantidad de veces que hash (así que básicamente tiene acceso a tu código fuente y a tu base de datos), esto asegura que te lleve más tiempo obtener resultados. ;
  4. Crea una sal dependiente de la cadena. Esta es una sal que se genera aleatoriamente para cada cadena que guarda en la base de datos y se almacena junto con ella. Esto asegura que el pirata informático tenga que hacer un bucle con todas las posibilidades del hash para cada contraseña, en lugar de poder hacerlo una vez por cada contraseña que haya almacenado. Si tiene 500 contraseñas almacenadas en la base de datos, de esta manera el pirata informático tarda 500 veces más en piratear todas las contraseñas.

Espero que esto haya ayudado. :)

    
respondido por el Frog 24.07.2011 - 16:47
fuente
2

En general, no hay nada de malo en hacer hashing de un valor varias veces para hacerlo más robusto contra los ataques de fuerza bruta. De hecho, esta es una técnica ya aplicada conocida como estiramiento de la tecla .

Las únicas objeciones a tu ejemplo es que deberías usar un algoritmo criptográfico de hashing fuerte , así como un esquema de hashing eso incluye una salt para obtener más entropía y resistencia a ataques de tabla de arco iris . En el mejor de los casos, un esquema de almacenamiento de contraseñas ya comprobado como crypt que fue diseñado específicamente para contraseñas.

    
respondido por el Gumbo 24.07.2011 - 16:53
fuente
2
  

No creo que el atacante ... pueda

Supones que sabes cómo funcionan los atacantes.

Supones que sabes todos los trucos que usan los atacantes y que has defendido con éxito contra todos y cada uno de ellos.

Está asumiendo que no hay nada en la investigación publicada, el conocimiento está disponible para cualquier persona que quiera aprender, que podría ayudar incluso a un atacante moderadamente experto a romper su seguridad.

Está asumiendo que el atacante no está dispuesto ni siquiera a realizar un ataque de fuerza bruta con cómputo robado. (¿Ha considerado el escenario en el que un atacante es paciente y ejecuta un trabajo en segundo plano en el servidor de otra persona, un servidor en el que el atacante violó y no está pagando, con el fin de descifrar su archivo de contraseña durante un período de un mes? ?)

Esto generalmente es una suposición muy mala .

    
respondido por el yfeldblum 28.09.2011 - 03:38
fuente
1

Enlaces relacionados:

respondido por el random65537 31.10.2011 - 16:58
fuente
0

Entiendo que esta pregunta ya estuvo aquí por un tiempo y tiene algunas respuestas excelentes. Sin embargo, creo que hay un problema que no se ha abordado. Usar un algoritmo fuerte (de una biblioteca) es el camino a seguir, ya que esos métodos han sido probados. Pero esto es lo que veo:

  

No creo que el atacante con mi DB pueda descifrar ningún   contraseña con longitud > 2

El problema no es crear el algoritmo más imposible de descifrar. El problema es asegurar su base de datos. Por ejemplo, si el atacante tiene una retención de su base de datos, no creo que se preocupe mucho por las contraseñas que contiene.

    
respondido por el Ibu 28.09.2011 - 01:36
fuente
-5

El problema con su método es que con cada llamada en md5 está ampliando el espacio de colisión de sus contraseñas ( no hay pruebas matemáticas al respecto, solo un entendimiento ingenuo ). Por genial que parezca, no intente hacer que su seguridad sea más complicada de lo que necesita. El algoritmo de hashing es tan sólido como usar múltiples pseudoaleatorios para intentar generar un aleatorio seguro. Podría obtener una seguridad simple que sea lo suficientemente segura si aplica la práctica del sentido común.

De todos modos, se da el consejo habitual, use sal use un hashing algo que tenga un espacio de colisión suficientemente grande. Si desea más seguridad, debe considerarlos en otros niveles, como la seguridad del servidor, la administración de la seguridad del personal.

De todos modos, si desea aplicar otros consejos de uso de bcrypt ( que es tan malo como se requiere para obtener la clave para descifrar la lista completa de contraseñas [ O (n) una vez que obtenga la contraseña], para no mirar una tabla de arco iris contra cada entrada [ O (n * m) ]), le recomendaría al menos que use una clave de clave pública ya que la clave para descifrar sus datos no será necesaria en su verificación de entrada (use la clave para cifrar de la misma forma en que hash sus datos).

    
respondido por el dvhh 25.07.2011 - 04:42
fuente

Lea otras preguntas en las etiquetas