Difficulty of collision vs preimage vs second-preimage attacks

Question

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?

Answer 1

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.

The simplest such method is Floyd's cycle finding, which uses negligible memory, at the expense of like tripling the expected number of hashes. Better methods exist that achieve a lower increase of the expected number of hashes, or/and allow a near arbitrary number of independent search engines to cooperate with modest data exchange. The reference article is Paul C. van Oorschot, Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology (1999).