What is a pre-image attack on digital signatures, and what is its computational complexity?

A pre-image attack forges a second document that has the same hash as the original — it attacks weak collision resistance and requires approximately $2^n$ operations.

* Only the forgery is altered; it must hit the original's fixed hash — realistic but costs ~2ⁿ tries. *

Scenario: Alice signs a check for $100. Eve wants to create a forged check for $100,000 with the same hash value, so Alice's signature remains valid.

How it works:

• Eve takes the target hash from the original document
• She must find a different document that produces the same hash
• Only the forged document is modified — the original stays untouched

Complexity: On average $2^n$ attempts for an n-bit hash (brute force over the entire hash space).

This attack is considered realistic (someone might actually try it) but difficult because $2^n$ is enormous for modern hash sizes. For SHA2-256, that's $2^{256}$ operations — utterly infeasible.

Note on naming: In the signature setting this is called a pre-image attack, but technically it targets second-preimage resistance — you are given one document and must find a different one with the same hash, not invert the hash from nothing.

Go deeper:

• Preimage attack (Wikipedia) — first vs second preimage, and the current best-known attacks on real hashes.