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

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?

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.

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)

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.

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.

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 ₂ diferente tal que hash (M ₂ ) == H. (resistencia de colisión débil)
• Dado hash (), produzca M ₁ y M _{2 de} manera que hash (M ₁ ) == hash (M ₂ ). (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 ³⁴ ).

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.

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