Ataque de preimagen

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 de preimagen:

• Resistencia de preimagen : para esencialmente todas las salidas preespecificadas, es computacionalmente inviable encontrar cualquier entrada que genere esa salida; es decir, dado y , es difícil encontrar una x tal que h ( x ) = y . ^[1]
• Resistencia de segunda preimagen : para una entrada específica, es computacionalmente inviable encontrar otra entrada que produzca la misma salida; es decir, dado x , es difícil encontrar una segunda entrada x ′ ≠ x tal que h ( x ) = h ( x ′) . ^[1]

Estos pueden compararse con una resistencia de colisión , en la que es computacionalmente inviable encontrar dos entradas distintas x , x ′ que tengan la misma salida; es decir, tales que h ( x ) = h ( x ′) . ^[1]

La resistencia a colisiones implica resistencia a segundas preimagen. La resistencia a segundas preimagen implica resistencia a preimagen solo 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 a segundas preimagen implica un ataque de colisión (trivial, ya que, además de x ′ , x ya se conoce desde el principio).

Por definición, una función hash ideal es aquella en la que la forma más rápida de calcular una primera o una segunda preimagen es mediante un ataque de fuerza bruta . Para un hash de n bits, este ataque tiene una complejidad temporal de 2 ⁿ , 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 las preimágenes. 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.${\displaystyle {\sqrt {2^{n}}}=2^{\frac {n}{2}}}$

Los ataques de preimagen más rápidos se pueden detectar 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 tarda décadas en preimagenar un valor hash deseado o un mensaje no es práctico; uno que cuesta unos pocos miles de dólares y tarda unas pocas semanas podría ser muy práctico.

Todos los ataques prácticos o casi prácticos conocidos actualmente ^{[3] [4]} sobre MD5 y SHA-1 son ataques de colisión . ^[5] 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 solo .${\displaystyle 2^{\frac {n}{2}}}$

La inviabilidad computacional de un primer ataque de preimagen sobre una función hash ideal supone que el conjunto de posibles entradas hash es demasiado grande para una búsqueda por fuerza bruta. Sin embargo, si se sabe que un valor hash determinado 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 por fuerza bruta puede ser efectiva. La viabilidad depende del tamaño del conjunto de entradas y de la velocidad o el 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 simple 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 convierte en hash 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 las contraseñas de forma 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 de preimagen. ^[6] Se han creado hashes especiales llamados funciones de derivación de claves para ralentizar las búsquedas. Véase Descifrado de contraseñas . Para conocer un método para evitar la prueba de contraseñas cortas, véase salt (criptografía) .

• Ataque de cumpleaños
• Función hash criptográfica
• Resumen de seguridad de la función hash
• Amabilidad con los rompecabezas
• Mesa arcoiris
• Oráculo aleatorio
• RFC  4270: Ataques a hashes criptográficos en protocolos de Internet