Ataque da preimagem

Em criptografia, um ataque da preimagem em uma função de hash criptográfica tenta achar uma mensagem que seja um específico valor de hash. Uma função de hash criptográfica deve ser resistente sob este tipo de ataque.

No contexto do ataque, há dois tipos de resistência a preimagem:

• resistência à preimagem: para essencialmente todas as saídas preespecificadas, é ser computacionalmente inviável achar qualquer entrada que seu valor de hash seja o da saída, exemplo: é difícil achar qualquer preimagem x dado um "y" que h(x) = y.^[1]
• resistência segunda à preimagem: é computacionalmente inviável achar qualquer segunda entrada que tenha a mesma saída que uma entrada específica, exemplo: dado um x, é difícil achar uma segunda preimagem x' ≠ x tal que h(x)=h(x').^[1]

Isto pode ser comparado com a resistência a colisão, em que é computacionalmente inviável achar duas entradas distintas x, x', cujos valores da aplicação de hash sejam os mesmos, ou seja, tal que h(x)=h(x').^[1]

A resistência à colisão implica resistência à segunda preimagem, mas não garante a resistência à preimagem.^[1]

Ataques de preimagem aplicados

Por definição, uma função de hash ideal é tal que a maneira mais rápida de computar a primeira ou segunda preimagem seja através do ataque de força bruta. Para um n-bit hash, este ataque tem a complexidade de tempo igual a ${\displaystyle 2^{n}}$, o que é considerado muito alto para uma saída com tamanho típico de 128 bits. Se esta for a melhor complexidade alcançada pelo adversário, então a função de hash é considerada resistente a preimagem.

Ataques de preimagem mais rápidos podem ser encontrados através da criptoanálise de certas funções de hash, e são específicas para estas funções. Alguns ataques de preimagem significativos já foram descobertos, mas eles ainda não são práticos. Se um ataque de preimagem prático é descoberto, isto afetaria drasticamente muitos protocolos da internet. Neste caso, "prático" significa que ele pode ser executado por um atacante com uma quantidade razoável de recursos. Por exemplo, um ataque de preimagem que custa trilhões de dólares e leva décadas achar a preimagem de um desejado valor de hash ou uma mensagem não é prático, mas um que custa alguns milhares de dólares e leva algumas semanas pode se tornar muito prático.

Todos os ataques práticos ou quase-práticos atualmente conhecidos sobre MD5 ou SHA-1 são ataques de colisão.^[2][3] Em geral, um ataque de colisão é mais fácil de executar do que um ataque de preimagem, uma vez que ele não é limitado por qualquer valor definido (quaisquer dois valores podem ser usados para colidir). A complexidade de tempo do ataque de colisão é, em contraste, ${\displaystyle 2^{n/2}}$ .

Ver também

• Ataque do aniversário
• Função hash criptográfica
• Rainbow table
• Oráculo randômico

Referências

1. http://www.cs.ucdavis.edu/~rogaway/papers/relates.pdf
2. «Why We Need to Move to SHA-2». CA Security Council. Consultado em 10 de agosto de 2015
3. «MD5 and Perspectives». www.cs.cmu.edu. Consultado em 10 de agosto de 2015