# Preimage attack

In cryptography, a preimage attack is a classification of attacks on cryptographic hash functions for finding a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage (message).

In the context of attack, there are two types of preimage resistance:

• preimage resistance: for essentially all pre-specified outputs, it is computationally infeasible to find any input which hashes to that output, i.e., to find any preimage x′ such that h(x′) = y when given any y for which a corresponding input is not known.[1]
• second-preimage resistance: it is computationally infeasible to find any second input which has the same output as any specified input, i.e., given x, to find a 2nd-preimage x' != x such that h(x) = h(x′).[1]

These can be compared with a collision resistance, in which it is computationally infeasible to find any two distinct inputs x, x′ which hash to the same output, i.e., such that h(x) = h(x′).[1]

Collision resistance implies 2nd-preimage resistance of hash functions;[1] and collision resistance does not guarantee preimage resistance.[1]

## Applied preimage attacks

By definition, an ideal hash function is such that the fastest way to compute a first or second preimage is through a brute force attack. For an n-bit hash, this attack has a time complexity $2^{n}$, which is considered too high for a typical output size of n=64 bits. If such complexity is the best that can be achieved by an adversary, then the hash function is considered preimage resistant.

Faster preimage attacks can be found by cryptanalysing certain hash functions, and are specific to that function. Some significant preimage attacks have already been discovered, but they are not yet practical. If a practical preimage attack is discovered, it would drastically affect many Internet protocols. In this case, "practical" means that it could be executed by an attacker with a reasonable amount of resources. For example, a preimaging attack that costs trillions of dollars and takes decades to preimage one desired hash value or one message is not practical; one that costs a few thousand dollars and takes a few weeks might be very practical.

All currently known practical or almost-practical attacks on MD5 and SHA-1 are collision attacks.[citation needed] In general, a collision attack is easier to mount than a preimage attack, as it is not restricted by any set value (any two values can be used to collide). The time complexity of the collision attack, in contrast, is $2^{\frac{n}{2}}$