En criptografía , un ataque de preimagen a funciones hash criptográficas intenta encontrar un mensaje que tenga un valor hash específico. Una función hash criptográfica debería resistir ataques a su preimagen (conjunto de posibles entradas).
En el contexto del ataque, existen dos tipos de resistencia previa a la imagen:
Estos se pueden comparar con una resistencia a la colisión , en la que es computacionalmente inviable encontrar dos entradas distintas x , x ′ que generen la misma salida; es decir, tal que h ( x ) = h ( x ′ ) . [1]
La resistencia a la colisión implica una resistencia a la segunda preimagen. La resistencia a la segunda preimagen implica resistencia a la preimagen sólo si el tamaño de las entradas de la función hash puede ser sustancialmente (por ejemplo, factor 2) mayor que el tamaño de las salidas de la función hash. [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).
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 hash de n bits, este ataque tiene una complejidad temporal de 2 n , que se considera demasiado alta para un tamaño de salida típico de n = 128 bits. Si dicha complejidad es la mejor que puede lograr un adversario, entonces la función hash se considera resistente a la preimagen. Sin embargo, existe un resultado general de que las computadoras cuánticas realizan un ataque de preimagen estructurado en , 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 práctico de preimagen, 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 preimaginar un valor hash deseado o un mensaje no es práctico; uno que cueste unos cuantos miles de dólares y demore algunas semanas puede resultar muy práctico.
Todos los ataques prácticos o casi prácticos conocidos actualmente [3] [4] [5] contra MD5 y SHA-1 son ataques de colisión . [ cita necesaria ] 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, a diferencia del ataque previo a la imagen, es de sólo .
La inviabilidad computacional de un primer ataque de preimagen a 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 determinado se produjo 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 de la velocidad o costo de calcular la función hash.
Un ejemplo común es el uso de hashes 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 manera predecible y muchas contraseñas son lo suficientemente cortas como para que se puedan probar todas las combinaciones posibles si se utilizan hashes rápidos, incluso si el hash está clasificado como seguro contra ataques previos a la imagen. [6] Se han creado hashes especiales llamados funciones de derivación de claves para ralentizar las búsquedas. Consulte Descifrar contraseñas . Para conocer un método para evitar la prueba de contraseñas cortas, consulte salt (criptografía) .
