Ataque de preimagen

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 ataques a su preimagen (conjunto de posibles entradas).

En el contexto de un ataque, existen dos tipos de resistencia a la preimagen:

• Resistencia a la preimagen : para prácticamente todas las salidas preespecificadas, es computacionalmente inviable encontrar cualquier entrada que genere esa salida mediante hash; es decir, dado y , es difícil encontrar un x tal que h ( x ) = y . ^{[ 1 ]}
• Resistencia a la segunda preimagen : para una entrada especificada, 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 se pueden comparar con una resistencia a colisiones , en la que es computacionalmente inviable encontrar dos entradas distintas x , x ′ que produzcan la misma salida; es decir, tales 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 ]} Sin embargo, bajo ciertas suposiciones del rango de la función hash, la resistencia a colisiones sí implica resistencia a la preimagen (por una implicación provisional) ^{[ 1 ]} . A la inversa, un ataque a la segunda preimagen implica un ataque a colisiones (trivialmente, ya que, además de x ′ , x ya se conoce desde el principio). Mediante la implicación provisional, un ataque a la preimagen también implicará un ataque a la segunda preimagen, que luego también se extiende a un ataque a colisiones.

Por definición, una función hash ideal es aquella en la 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 ⁿ , 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 que indica que las computadoras cuánticas realizan un ataque de preimagen estructurado en${\displaystyle {\sqrt {2^{n}}}=2^{\frac {n}{2}}}$, lo que también implica una segunda preimagen ^{[ 2 ]} y, por lo tanto, un ataque de colisión.

Mediante el criptoanálisis de ciertas funciones hash, se pueden encontrar ataques de preimagen más rápidos , específicos de cada función. Ya se han descubierto algunos ataques de preimagen importantes, pero aún no son prácticos. Si se descubriera un ataque de preimagen práctico, afectaría drásticamente a muchos protocolos de Internet. En este caso, "práctico" significa que un atacante con recursos suficientes podría ejecutarlo. Por ejemplo, un ataque de preimagen que cuesta billones de dólares y tarda décadas en generar la preimagen de un valor hash 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 realizar que un ataque de preimagen, ya que no está restringido por ningún valor fijo (cualquier par de valores pueden usarse para colisionar). La complejidad temporal de un ataque de colisión por fuerza bruta, en contraste con el ataque de preimagen, es solo${\displaystyle 2^{\frac {n}{2}}}$.

• ataque de cumpleaños
• Función hash criptográfica
• Resumen de seguridad de la función hash
• Amabilidad con los rompecabezas
• Mesa arcoíris
• oráculo aleatorio
• RFC 4270 : Ataques a funciones hash criptográficas en protocolos de Internet