Preimage Attack Information

In cryptography, the preimage attack is a classification of attacks on hash functions for finding a message that has a specific hash value.

There are two types of preimage attacks:

• (First-) preimage attack: given a hash h, find a message m (a preimage) such that hash(m) = h.
• Second-preimage attack: given a fixed message m1, find a different message m2 (a second preimage) such that hash(m2) = hash(m1).

These can be compared with a collision attack, which involves finding two arbitrarily different messages m1 and m2 such that hash(m2) = hash(m1).

Applied preimage attacks

For an ideal hash function, the fastest way to compute a first or second preimage is through a brute force attack.^{[citation needed]} For an n-bit hash, this attack has a time complexity 2ⁿ, which is considered too high for a typical output size of n=160 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 in a meaningful amount of time for a meaningful amount of money. 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. In general, a collision attack is easier to mount than a preimage attack.

See also

• Birthday attack
• Cryptographic hash function
• Rainbow table
• Random oracle

References

• IETF RFC 4270: Attacks on Cryptographic Hashes in Internet Protocols

Categories: Cryptographic attacks |

Related 'Preimage Attack' Searches: