Ataque de preimage

En el campo de la criptografía, un ataque de preimage hacia una función hash criptográfica es aquel ataque que intenta encontrar un mensaje con un hash específico. Una función hash criptográfica debe de poder resistir ataques a su preimage (el conjunto de todas las entradas posibles).

En el contexto de un ataque, existen dos tipos de resistencia del preimage:

resistencia del preimage: para prácticamente todos los valores preestablecidos, es computacionalmente inviable encontrar alguna entrada que dé como salida dicho valor; es decir, dado $y$ , es difícil encontrar una $x$ tal que $h (x) = y$ .^[1]
resistencia del segundo preimage: para un mensaje de entrada predefinido, es computacionalmente inviable encontrar otro mensaje que genere el mismo hash (el mensaje de salida); dicho de otra manera, dada una $x$ , es difícil encontrar otro mensaje $x' \neq x$ tal que $h (x) = h (x')$ .^[1]

Estos pueden ser comparados a la resistencia contra colisiones, en la cual resulta inmanejable encontrar mediante una computadora dos mensajes distintos $x$ y $x'$ tal que tengan el mismo hash; es decir, tal que $h (x) = h (x')$ .^[1]

El que una función resista ataques de colisión implica que resiste ataques al segundo preimage. La resistencia del segundo preimage implica la resistencia del preimage solamente si la cantidad de entradas posibles de la función hash puede ser considerablemente más grande (por ejemplo, dos veces más) que la cantidad de salidas posibles de la función.^[1] En cambio, un ataque al segundo preimge implica un ataque de colisión (trivialmente, ya que, además de $x'$ , $x$ se conoce desde el inicio).

Ataques de preimage aplicados

Por definición, una función hash ideal es aquella que tiene la característica de que la manera más rápida de calcular un preimage o un preimage segundo es mediante un ataque de fuerza bruta. Para un hash de $n$ bits, este tipo de ataque tiene una complejidad de tiempo de $2 n$ , lo cual se considera demasiado alto para un tamaño de salida usual ( $n$ = 128 bits). Si dicha complejidad es la más óptima que puede alcanzar un adversario, se dice que la función hash es resistente a un preimage. Sin embargo, hay un resultaldo matemático generalizado que establece que una computadora cuántica puede efectuar un ataque preimage estructurado en ${\sqrt {2^{n}}}=2^{\frac {n}{2}}$ , lo cual a su vez implica que se puede efectuar un preimage segundo^[2], y, por lo tanto, un ataque de colisión.

Es posible encontrar ataques de preimage más rápidos si se aplica el criptoanálisis a ciertas funciones hash, pero estos ataques solamente aplican a dichas funciones. Algunos ataques notables han sido descubiertos, pero todavía no son prácticos. De ser descubierto, un ataque preimage práctico afectaría en gran manera los protocolos utilizados en internet. En este contexto «práctico» significa que el ataque puede ser ejecutado por un adversario que posea una cantidad razonable de recursos.

Todos los ataques prácticos o casi prácticos conocidos contra^[3]^[4] MD5 y SHA-1 son ataques de colisión.^[5] En general, un ataque de colisión es más sencillo de realizar que un ataque al preimage, ya que no contiene la restricción de algún valor fijo (se pueden utilizar dos valores cualesquiera para generar la colisión). La complejidad de tiempo de un ataque de colisión mediante fuerza bruta, a diferencia del ataque de preimage, es solamente $2^{\frac {n}{2}}$ .

Ataques con espacio de preimage reducido

La inviabilidad de un ataque al primer preimage de una función hash ideal asume que el conjunto de todos los mensajes de entrada posibles es demasiado grande para una búsqueda por fuerza bruta. No obstante, si se sabe que un valor hash determinado fue producido por un conjunto de entradas que es relativamente pequeño o que está ordenado por probabilidad en alguna manera, entonces puede ser efectivo un ataque de fuerza bruta. El que sea o no práctico depende de la cantidad de entradas posibles y el costo o velocidad de computar la función hash.

Un ejemplo común es el uso de valores hash para almacenar datos para validar contraseñas, esto para la autenticación de usuarios. En lugar de almacenar las contraseñas en forma directa, un sistema de control de acceso almacena los valores hash de las contraseñas. Cuando el usuario o usuaria solicita acceso, la contraseña que ingresan pasa por la función hash y es comparada con el valor almacenado. Si los datos de validación son robados, el atacante únicamente podrá acceder a los valores hash y no a las contraseñas. Sin embargo, gran parte de los usuarios eligen contraseña de forma predecible, y además muchas contraseñas son lo suficientemente cortas que es posible revisar todas las combinaciones posibles si se usan hashes rápidos, incluso si el hash resiste ataques a su preimage.^[6] Se han creado funciones hash especiales, llamadas funciones de derivación de claves, que buscan ralentizar las búsquedas.