Atac preimatge

A la criptografia, un atac de preimatge a les funcions hash criptogràfiques intenta trobar un missatge que tingui un valor hash específic. Una funció hash criptogràfica hauria de resistir els atacs a la seva preimatge (conjunt de possibles entrades).

En el context de l'atac, hi ha dos tipus de resistència a la preimatge:

• resistència a la preimatge : per a essencialment totes les sortides especificades prèviament, és computacionalment inviable trobar qualsevol entrada que s'hagi a aquesta sortida; és a dir, donada y, és difícil trobar una x tal que h(x) = y.
• resistència a la segona preimatge : per a una entrada especificada, és computacionalment inviable trobar una altra entrada que produeixi la mateixa sortida; és a dir, donat x, és difícil trobar una segona entrada x′ ≠ x tal que h(x) = h(x′).

Aquests es poden comparar amb una resistència de col·lisió, en la qual és computacionalment inviable trobar dues entrades diferents x, x′ que hash a la mateixa sortida; és a dir, tal que h(x) = h(x′).

La resistència a la col·lisió implica una resistència a la segona preimatge. La resistència a la segona preimatge implica resistència a la preimatge només si la mida de les entrades de la funció hash pot ser substancialment (per exemple, el factor 2) més gran que la mida de les sortides de la funció hash. Per contra, un atac de segona preimatge implica un atac de col·lisió (trivialment, ja que, a més de x′, x ja es coneix des del principi).

Atacs de preimatge aplicats

Per definició, una funció hash ideal és tal que la manera més ràpida de calcular una primera o segona preimatge és mitjançant un atac de força bruta. Per a un hash de n bits, aquest atac té una complexitat temporal 2ⁿ, que es considera massa alta per a una mida de sortida típica de n = 128 bits. Si aquesta complexitat és la millor que pot aconseguir un adversari, la funció hash es considera resistent a la preimatge. Tanmateix, hi ha un resultat general que els ordinadors quàntics realitzen un atac de preimatge estructurat ${\sqrt {2^{n}}}=2^{\frac {n}{2}}$, que també implica una segona preimatge i, per tant, un atac de col·lisió.

Es poden trobar atacs de preimatge més ràpids mitjançant la criptoanàlisi de determinades funcions hash, i són específics d'aquesta funció. Ja s'han descobert alguns atacs importants de preimatge, però encara no són pràctics. Si es descobreix un atac de preimatge pràctic, afectaria dràsticament molts protocols d'Internet. En aquest cas, "pràctic" vol dir que podria ser executat per un atacant amb una quantitat raonable de recursos. Per exemple, un atac de preimatge que costa bilions de dòlars i triga dècades a preimatge d'un valor hash desitjat o d'un missatge no és pràctic; un que costa uns quants milers de dòlars i triga unes quantes setmanes pot ser molt pràctic.

Tots els atacs pràctics o gairebé pràctics coneguts actualment a MD5 i SHA-1 són atacs de col·lisió. En general, un atac de col·lisió és més fàcil de muntar que un atac de preimatge, ja que no està restringit per cap valor establert (es poden utilitzar dos valors qualsevol per xocar). La complexitat temporal d'un atac de col·lisió de força bruta, en contrast amb l'atac preimatge, és només $2^{\frac {n}{2}}$.