# Difficulty of collision vs preimage vs second-preimage attacks

It seems at first glance that brute-forcing a collision would be exactly as difficult for all of them. They all (I would expect) work like this: select a hash value, and then try messages to get an equal hash.

The difference between them is just how that first hash is selected:

• Collision: random message.
• Preimage: the supplied hash.
• Second-preimage: the hash of the supplied message.

So why are they different in difficulty? (~$2^{n}$ vs ~$2^{n/2}$) Yes. Obviously I'm wrong about some point (probably that collision resistance has some shortcut). I'm asking what is my error.

EDIT

It seems that the simple answer to my question is that collision resistance is weaker because every hash one is testing can be paired with every hash tested up to that point, and not only with one specific hash.

If this is not correct - please correct me. If it is, however:

In practice, somewhere around $2^{40}$ (-Terabyte) - the IO time for storing and testing would probably be greater than hashing a message (which can be in excess of $10^{8}$ hashes/s). and over $2^{60}$ would probably be practically impossible. So the difficulty levels are more theoretical than practical for high values such as in the case of SHA-256. Is this correct?

• @fgrieu a) I admit I'm in over my head in this so I might be making some stupid mistake here. b) It seems that collision resistance is weaker because every hash one is testing can be paired with every hash tested up to that point, and not only to the original hash. This sounds logical at first, but in practice ... (1/2) Jul 18, 2017 at 19:34
• @fgrieu (2/2) ... for anything over 2^40 (-Terabyte) - the IO time for storing and testing would probably be much greater than hashing a message (which can be in excess of 10^8 hashes/s). and over 2^60 would probably be practically impossible. Yet you mention this in your answer to my previous question dealing with $2^{256}$ (and therefore $2^{128}$). As I said - I might be talking complete nonsense here so please correct me if I'm wrong. Jul 18, 2017 at 19:34

For a $n$-bit ideal hash:
• Finding a collision is expected to require a little above $2^{n/2}$ hashes, in short because after having computed $m$ hashes, there are $m(m-1)/2$ opportunities of collisions. For details, see Birthday problem for cryptographic hashing, 101.
• Finding a preimage (first or second) is expected to require about $2^n$ hashes, in short because the best known method is to try until hitting the hash thought, and each try has odds $2^{-n}$ to succeed.
The naive algorithm to find collisions with about $2^{n/2}$ hashes requires to store the previous hashes and search among these, thus requires in the order of $2^{n/2}n$ bits of memory, which is totally impractical for cryptographic hashes. However, with better methods, memory becomes essentially a non-issue.