En criptografía , un ataque de preimagen a las funciones hash criptográficas intenta encontrar un mensaje que tenga un valor hash específico. Una función hash criptográfica debe resistir los ataques a su preimagen (conjunto de posibles entradas).
En el contexto del ataque, hay dos tipos de resistencia a la preimagen:
- resistencia a la preimagen : para esencialmente todas las salidas preespecificadas, es computacionalmente inviable encontrar cualquier entrada que tenga un valor hash en esa salida; es decir, dado y , es difícil encontrar una x tal que h ( x ) = y . [1]
- resistencia de la segunda preimagen : es computacionalmente inviable encontrar una segunda entrada que tenga la misma salida que la de una entrada especificada; es decir, dado x , es difícil encontrar una segunda preimagen x ′ ≠ x tal que h ( x ) = h ( x ′) . [1]
Éstos se pueden comparar con una resistencia a la colisión , en la que no es factible computacionalmente encontrar dos entradas distintas x , x ′ que apunten a la misma salida; es decir, tal que h ( x ) = h ( x ′) . [1]
La resistencia a colisiones implica resistencia a la segunda preimagen, [1] pero no garantiza la resistencia a la preimagen. [1] Por el contrario, un ataque de segunda preimagen implica un ataque de colisión (trivialmente, ya que, además de x ′, x ya se conoce desde el principio).
Ataques de preimagen aplicados
Por definición, una función hash ideal es tal que la forma más rápida de calcular una primera o segunda preimagen es mediante un ataque de fuerza bruta . Para un n bits de hash, este ataque tiene un tiempo de complejidad 2 n , que se considera demasiado alto para un tamaño de salida típica de n = 128 bits. Si tal complejidad es la mejor que puede lograr un adversario, entonces la función hash se considera resistente a las preimágenes. Sin embargo, hay un resultado general de que las computadoras cuánticas realizan un ataque de preimagen estructurado en √ 2 n = 2 n / 2 , lo que también implica una segunda preimagen [2] y, por lo tanto, un ataque de colisión.
Se pueden encontrar ataques de preimagen más rápidos mediante el criptoanálisis de ciertas funciones hash, y son específicos de esa función. Ya se han descubierto algunos ataques de preimagen importantes, pero aún no son prácticos. Si se descubre un ataque de preimagen práctico, afectaría drásticamente a muchos protocolos de Internet. En este caso, "práctico" significa que podría ser ejecutado por un atacante con una cantidad razonable de recursos. Por ejemplo, un ataque de preimagen que cuesta billones de dólares y lleva décadas preimagen un valor hash deseado o un mensaje no es práctico; uno que cuesta unos pocos miles de dólares y toma algunas semanas puede ser muy práctico.
Todos los ataques prácticos o casi prácticos actualmente conocidos [3] [4] [5] en MD5 y SHA-1 son ataques de colisión [ cita requerida ] . En general, un ataque de colisión es más fácil de montar que un ataque de preimagen, ya que no está restringido por ningún valor establecido (se pueden usar dos valores cualesquiera para colisionar). La complejidad temporal de un ataque de colisión de fuerza bruta, en contraste con el ataque de preimagen, es de solo 2 n / 2 .
Ataques restringidos al espacio de preimagen
La inviabilidad computacional de un primer ataque de preimagen en una función hash ideal supone que el conjunto de posibles entradas hash es demasiado grande para una búsqueda de fuerza bruta. Sin embargo, si se sabe que un valor hash dado se ha producido a partir de un conjunto de entradas que es relativamente pequeño o está ordenado por probabilidad de alguna manera, entonces una búsqueda de fuerza bruta puede ser efectiva. La practicidad depende del tamaño del conjunto de entrada y la velocidad o el costo de calcular la función hash.
Un ejemplo común es el uso de hash para almacenar datos de validación de contraseñas para la autenticación. En lugar de almacenar el texto sin formato de las contraseñas de los usuarios, un sistema de control de acceso almacena un hash de la contraseña. Cuando un usuario solicita acceso, la contraseña que envía se codifica y se compara con el valor almacenado. Si se roban los datos de validación almacenados, el ladrón solo tendrá los valores hash, no las contraseñas. Sin embargo, la mayoría de los usuarios eligen contraseñas de formas predecibles y muchas son lo suficientemente cortas como para que se puedan probar todas las combinaciones posibles si se utilizan hash rápidos, incluso si el hash está clasificado como seguro contra ataques de preimagen. [6] Se han creado hashes especiales llamados funciones de derivación de claves para ralentizar las búsquedas. Consulte Descifrado de contraseñas .
Ver también
- Ataque de cumpleaños
- Función hash criptográfica
- Resumen de seguridad de la función hash
- Mesa arcoiris
- Oráculo aleatorio
- RFC 4270 : Ataques a hashes criptográficos en protocolos de Internet
Referencias
- ^ a b c d e Rogaway, P .; Shrimpton, T. (2004). "Conceptos básicos de la función hash criptográfica: definiciones, implicaciones y separaciones para la resistencia a la preimagen, la resistencia a la segunda preimagen y la resistencia a colisiones" (PDF) . Cifrado de software rápido . Springer-Verlag . Consultado el 17 de noviembre de 2012 .
- ^ Daniel J. Bernstein (12 de noviembre de 2010). "Ataques cuánticos contra Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD y Skein" (PDF) . Universidad de Illinois en Chicago . Consultado el 29 de marzo de 2020 .
- ^ Bruce Morton, Clayton Smith (30 de enero de 2014). "Por qué necesitamos mudarnos a SHA-2" . Consejo de Seguridad de la Autoridad de Certificación .Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ "MD5 y perspectivas" . 2009-01-01.
- ^ "Blog de seguridad en línea de Google: anunciando la primera colisión SHA1" . Consultado el 23 de febrero de 2017 .
- ^ Goodin, Dan (10 de diciembre de 2012). "El clúster de 25 GPU descifra todas las contraseñas estándar de Windows en <6 horas" . Ars Technica . Consultado el 23 de noviembre de 2020 .