3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ @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) $\endgroup$ – ispiro Jul 18 '17 at 19:34
  • $\begingroup$ @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. $\endgroup$ – ispiro Jul 18 '17 at 19:34
5
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.