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).
Estos se pueden comparar con una resistencia a la colisión , en la que no es factible computacionalmente encontrar dos entradas distintas x , x ′ que tengan la misma salida; es decir, tal que h ( x ) = h ( x ′) . [1]
La resistencia a colisiones implica resistencia a la segunda preimagen, 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).
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 la preimagen. 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 tarda algunas semanas puede resultar 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 de tiempo de un ataque de colisión de fuerza bruta, en contraste con el ataque de preimagen, es solo 2 n / 2 .