¿Qué hace que un algoritmo de hash sea "seguro"?

19

Después de leer esta interesante pregunta, sentí que tenía una buena idea de qué algoritmo de hash inseguro usaría si lo necesitara, pero no tengo idea de por qué podría usar un algoritmo seguro.

Entonces, ¿cuál es la distinción? ¿No es la salida solo un número aleatorio que representa la cosa hash? ¿Qué hace que algunos algoritmos de hashing sean seguros?

CodexArcanum
fuente
8
Esta pregunta es más adecuada para el sitio de IT Security SE.
Bernard
@Bernard Si ese es el caso, entonces estoy de acuerdo con eso, pero mi pregunta no era realmente acerca de cómo o cuándo usar un hash seguro, sino qué distingue un algoritmo de hash seguro de uno inseguro. Eso me parece más una pregunta de programación, pero no busco IT Security SE, así que tal vez eso también funcione allí.
CodexArcanum
2
Ya se ha hecho una pregunta muy similar sobre seguridad de TI
ChrisF

Respuestas:

34

Hay tres propiedades que uno quiere de cada función hash criptográfica H:

  • resistencia a la preimagen : dado h, debería ser difícil encontrar algún valor xcon h = H(x).

  • segunda resistencia imagen inversa : Dada x1, debe ser difícil de encontrar x2 != x1con H(x1) = H(x2).

  • resistencia a la colisión : debería ser difícil encontrar dos valores x1 != x2con H(x1) = H(x2).

Con las funciones hash como se usan en los lenguajes de programación comunes para las tablas hash (de cadenas), generalmente no se proporciona ninguna de estas, solo proporcionan:

  • resistencia a la colisión débil : para valores seleccionados al azar (o "típicamente") del dominio, la posibilidad de colisión es pequeña. Esto no dice nada acerca de un atacante que intenta intencionalmente crear colisiones o que trata de encontrar imágenes previas.

Las tres propiedades anteriores son (entre) los objetivos de diseño para cada función hash criptográfica. Para algunas funciones (como MD4, SHA-0, MD5) se sabe que esto falló (al menos parcialmente). Se supone que la generación actual (SHA-2) es segura, y la siguiente ("Algoritmo de hash seguro 3") está actualmente en proceso de estandarización , después de una competencia .

Para algunos usos (como el hash de contraseñas y la derivación de claves de las contraseñas), el dominio de los valores realmente utilizados xes tan pequeño que la fuerza bruta de este espacio se vuelve factible con funciones hash seguras normales (rápidas), y esto es cuando también queremos:

  • ejecución lenta : dado x, se requiere una cantidad mínima (preferiblemente configurable) de recursos para calcular el valor H(x).

Pero para la mayoría de los otros usos, esto no es deseable, uno quiere en su lugar:

  • Ejecución rápida : dado x, calcular el valor de H(x)es lo más rápido posible (mientras sigue siendo seguro).

Hay algunas construcciones (como PBKDF2 y scrypt) para crear una función hash lenta a partir de una rápida al iterarla con frecuencia.

Para obtener más detalles, eche un vistazo a la etiqueta hash en nuestro sitio hermano Cryptography Stack Exchange.

Paŭlo Ebermann
fuente
3

Seguro significa que alguien que quiera inducirlo a cometer un error al usar una colisión (es decir, el hecho de que dos fuentes se combinen con el mismo valor) tendrá dificultades.

Algunas caracteristicas:

  • Conocer el hash, es difícil construir un archivo que tenga ese valor (variante, se proporciona parte del nuevo archivo y el hash deseado)

  • es difícil construir dos archivos diferentes que tengan el mismo valor hash (variante, se proporciona parte de los archivos)

Un programador
fuente
3

La diferencia principal es bastante simple: un hash normal está destinado a minimizar el número de colisiones accidentales, en la medida en que puede sin ralentizar mucho en el proceso.

Un hash seguro destinado a evitar colisiones, incluso cuando alguien está haciendo todo lo posible para causar una. Por lo general, no desea cambiar ninguna posibilidad de colisión para una operación más rápida. De hecho, hacer que la operación sea intencionalmente lenta tiene algunos beneficios de seguridad en sí mismo, incluso si no dificulta la búsqueda de colisiones.

Para un ejemplo de esto último: si calcular un hash tarda 50 ms, no tendrá un efecto material en el inicio de sesión de un usuario normal (es decir, la mayoría de los usuarios no notarán una diferencia de 50 ms cuando inicien sesión). Al mismo tiempo, si un atacante quiere hacer un ataque de diccionario, poder producir solo 20 hashes por segundo es una desventaja grave . En otras palabras, dentro de algún tipo de razón, para un hash seguro, más lento es mejor.

Jerry Coffin
fuente
3
En el dominio de las funciones hash criptográficas, hay dos subgrupos importantes: los rápidos (utilizados para la autenticación de mensajes, firma y similares), y los lentos, utilizados para la derivación de claves y el hash de contraseñas. No mezcle estos, hay aplicaciones para ambos.
Paŭlo Ebermann
En realidad, también hay funciones hash que están diseñadas para maximizar las colisiones: Soundex es un ejemplo. Obviamente, esto lo convierte en una función hash segura muy mala.
Jörg W Mittag
@ JörgWMittag: no solo es malo como un hash seguro, sino que también sería bastante pobre para usar con una tabla hash. Por otra parte, aunque ciertamente es algo similar a un hash, dudaría en llamar a Soundex una función hash, simplemente porque su intención y uso son muy diferentes de las funciones hash normales.
Jerry Coffin
@JerryCoffin: Supongo que depende de la definición. Por ejemplo, la página de Wikipedia en inglés simplemente dice que una función hash es cualquier algoritmo o subrutina que mapea un conjunto más grande (potencialmente infinito) de valores arbitrarios en un conjunto finito más pequeño de valores (típicamente escalares). Mientras que la página de Wikipedia en alemán dice que el "hashing" (alemán: "zerhacken") es una parte integral, es decir, que la prevención de colisiones y la distribución de los valores mapeados es clave. Soundex cumple mucho la primera definición pero no la segunda.
Jörg W Mittag
3

Lea esto http://www.codinghorror.com/blog/2012/04/speed-hashing.html , explicará todo mucho mejor de lo que podría explicarlo. Estos son los dos encabezados más importantes del artículo que abordan directamente su pregunta:

  • Los hashes seguros están diseñados para ser a prueba de manipulaciones
    • cambia su salida radicalmente con pequeños cambios de un solo bit en los datos de entrada
  • Los hashes seguros están diseñados para ser lentos

Su sección TL; DR al final:

Si eres usuario:

Asegúrese de que todas sus contraseñas tengan 12 caracteres o más, idealmente mucho más. Recomiendo adoptar frases de contraseña, que no solo son mucho más fáciles de recordar que las contraseñas (si no las escribe), sino que también son ridículamente seguras contra la fuerza bruta debido a su longitud.

Si eres desarrollador:

Use bcrypt o PBKDF2 exclusivamente para trocear todo lo que necesite para estar seguro. Estos nuevos hashes fueron diseñados específicamente para ser difíciles de implementar en las GPU. No use ninguna otra forma de hash. Casi todos los demás esquemas de hash populares son vulnerables a la fuerza bruta por conjuntos de GPU de productos básicos, que solo se vuelven más rápidos y paralelos y más fáciles de programar para cada año.

Nate
fuente
44
Jeff se equivoca aquí en el segundo punto ... mientras que para algunos usos (como hashing de contraseña y derivación de clave de una contraseña) desea ser lento, para otros usos (como autenticación de mensajes, firmas, etc.) rápido (seguro) las funciones hash son buenas.
Paŭlo Ebermann
Tienes razón Paŭlo. El rendimiento del hash depende de la aplicación del hash. Sin embargo, los hash lentos siempre son más seguros que los rápidos. La razón por la que usaría un hash rápido es si está bien sacrificando la seguridad por el rendimiento.
Nate
2
@Nate "Más seguro" siempre es ambiguo, pero incluso bajo la aplicación más caritativa, "los hash lentos siempre son más seguros que los rápidos" es definitivamente incorrecto. Hay muchas aplicaciones donde la velocidad de un hash es irrelevante.
Gilles 'SO- deja de ser malvado'
@Gilles, ¿puedes dar un ejemplo? En realidad, eso me parece cierto, pero sería más útil contar con más detalles.
Nate
2
@Nate La aplicación más obvia de los hashes es verificar la integridad de un dato: transmita el hash a través de un canal seguro pero posiblemente de bajo ancho de banda, transmita la carga útil posiblemente grande a través de un canal inseguro, luego verifique que la carga recibida tenga el esperado picadillo. Los hashes también ocupan un lugar destacado en los métodos de firma (donde no solo verifica la integridad, sino también quién le envió los datos). Hashing contraseñas es más bien la excepción.
Gilles 'SO- deja de ser malvado'
2

Un hash "seguro" es un hash que se cree que es difícil de "falsificar" de una manera formulable y reproducible sin conocimiento previo del mensaje utilizado para crear el hash. Como esa información es generalmente secreta, de ahí la necesidad de un hash, esta es una buena propiedad de una función de hash destinada a usarse en la autenticación.

Un hash generalmente se considera "seguro" si, dado un mensaje M, una función hash hash () y un valor hash H producido por hash (M) con una longitud en bits L, ninguno de los siguientes puede realizarse en menos de O (2 L ) tiempo:

  • Dado hash () y H, produce M. (resistencia previa a la imagen)
  • Dados hash () y M, producen un M 2 diferente tal que hash (M 2 ) == H. (resistencia de colisión débil)
  • Dado hash (), produzca M 1 y M 2 de manera que hash (M 1 ) == hash (M 2 ). (fuerte resistencia a la colisión)

Además, un hash "seguro" debe tener una longitud de hash L tal que 2 LNo es un número factible de pasos para que una computadora realice el hardware actual dado. Un hash de entero de 32 bits solo puede tener 2,1 mil millones de valores; Si bien un ataque de preimagen (encontrar un mensaje que produce un hash H específico) tomaría un tiempo, no es inviable para muchas computadoras, especialmente aquellas en manos de agencias gubernamentales autorizadas para descifrar códigos. Además, un algoritmo que crea y almacena mensajes aleatorios y sus valores hash, según la probabilidad, tendría un 50% de posibilidades de encontrar un hash duplicado con cada nuevo mensaje después de intentar solo 77,000 mensajes, y tendría un 75% de posibilidades de acertar duplicado después de solo 110,000. Incluso los hashes de 64 bits todavía tienen un 50% de posibilidades de colisionar después de probar solo unos 5 mil millones de valores. Tal es el poder del ataque de cumpleaños en pequeños hashes. Por el contrario,decillion números (1.5 * 10 34 ).

La mayoría de los ataques demostrados en hashes criptográficos han sido ataques de colisión, y han demostrado la capacidad de generar mensajes colisionantes en menos de 2 L (la mayoría todavía han sido de tiempo exponencial, pero reducir el exponente a la mitad es una reducción significativa en la complejidad, ya que hace que un hash de 256 bits tan fácil de resolver como un de 128 bits, un 128 bits tan fácil de resolver como un de 64 bits, etc.

Además del tamaño de hash pequeño, otros factores que pueden hacer que un hash sea demostrablemente inseguro son:

Bajo trabajo: un hash diseñado para ser utilizado por una tabla hash o para otros fines de tipo "suma de verificación" generalmente está diseñado para ser computacionalmente económico. Eso hace que un ataque de fuerza bruta sea mucho más fácil.

"Estado fijo": la función de hash es propensa a patrones de entrada donde el valor de hash actual de todas las entradas hasta el momento no cambia cuando se le da un byte de entrada adicional en particular. Tener "estado fijo" hace que las colisiones sean fáciles de encontrar, porque una vez que identifica un mensaje que produce un hash de "estado fijo", es trivial generar otros mensajes que tengan el mismo hash agregando bytes de entrada que mantienen el hash en su "estado fijo" ".

Difusión: cada byte de entrada del mensaje debe distribuirse entre los bytes del valor hash de una manera igualmente compleja. Ciertas funciones hash crean cambios predecibles a ciertos bits en el hash. De nuevo, esto hace que la creación de colisiones sea trivial; dado un mensaje que produce un hash, las colisiones se pueden crear fácilmente al introducir nuevos valores en el mensaje que solo afectan los bits que cambian de manera predecible.

KeithS
fuente
0

Use el algoritmo correcto para la tarea en cuestión.

Los CRC se utilizan para la detección / corrección de errores.

Los resúmenes de mensajes criptográficos, como SHA2, se utilizan como un bloque de construcción para construcciones criptográficas (firmas digitales, MAC, funciones de derivación de claves / hashing de contraseña) y protocolos de seguridad.

En tablas / diccionarios / mapas hash, use SipHash .

Lo que llama algoritmos hash inseguros no debe usarse en tablas hash , como lo demuestran las siguientes entradas CVE: CVE-2003-0364, CVE-2011-4461, CVE-2011-4838, CVE-2011-4885, CVE-2011- 4462, CVE-2011-4815, CVE-2012-0840, CVE-2012-5371 , CVE-2012-5374, CVE-2012-5375

Erwan Legrand
fuente