2
$\begingroup$

Weak collision resistance (CR), or second-preimage resistance, is the property that given $x$ and $h(x)$ ($h$ a hash function) it's difficult to find $x' \neq x$ such that $h(x') = h(x)$. Strong CR, or just collision resistance, is the property that it's difficult to find any two $x,x'$ with the same hash value.

The latter is easier than the former; the former is the "hash function analogue" of "same birthday as me" and the latter the analogue of "any two persons sharing a birthday".

Now then, what would a collision attack look like? I don't understand when it would be of relevance that it's relatively easy to find a pair $x,x'$ with the same hash value; isn't an adversary typically confronted with a given hash value that he has to "work with"? I.e., $x$ and $h(x)$ are given, if he can find a collision pair $(y,y')$, well, what does that help him?

Also, how does one actually find "any two" inputs with the same hash value? Seems to me that you must always first choose one input $x$, and then compare against that, at which point we're back to finding second preimages, right?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
0
$\begingroup$

CR doesn't lead to a direct attack, it's a weakness indicator. For CR you keep a hashed/sorted list of input/output pairs thus if you have $t$ samples you are checking $\binom{t}{2}$ possible collisions so you are not back to 2nd preimage.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks, that really clears it up. Is it really feasible to create such a list? If one's hash rate per sec is $2^{20}$ it would take quite some time to generate a list of, say, $2^{80}$ pairs. $\endgroup$
    – Erik Vesterlund
    Mar 11, 2016 at 21:55
  • $\begingroup$ It would take $2^{40.5}$ hashes, so $2^{20.5}\approx 1,483,000$ seconds or about 17.2 days, under the random hash function model. Actual 2nd preimage attacks on real world hashes have also been demonstrated, e.g., On MD5. These use the structure of the function. $\endgroup$
    – kodlu
    Mar 12, 2016 at 0:11
  • $\begingroup$ Hm, where does $2^{40.5}$ come from? $\endgroup$
    – Erik Vesterlund
    Mar 12, 2016 at 0:38
  • $\begingroup$ It is The approximate value of $t$ required to generate $2^{80}$ pairs via the binomial coefficient in the answer. $\endgroup$
    – kodlu
    Mar 12, 2016 at 0:41
  • $\begingroup$ @kodlu Sorry, but I completely disagree. I am writing my answer as well, so you can see why. $\endgroup$
    – Yehuda Lindell
    Mar 12, 2016 at 18:26
4
$\begingroup$

There are many situations where collision resistance is exactly the property that you need. For example, assume that I want to get a certificate from a CA with the URL www.google.com so that I can play a fishing attack against Google. Assume that I manage to find two certificates with the same hash; one has URL that is www.google.com and the other has something else (e.g., www.yehudalindell.com). Then, the CA will happily sign on the certificate for the latter URL, and due to the collision I will now have a valid certificate for google. Another example is code signing: if I can construct two pieces of code where one is malicious and the other is perfectly valid but both have the same hash, then I can get my valid code accepted to Apple Store or something like that, but then get people to download my malicious code.

It is really important to understand that birthday attacks on hash functions are just the generic way of finding collisions when nothing better is known. However, advanced cryptanalysis can do amazing things and find really valid collisions. For example, using advanced techniques and MD5 collisions, a rogue certificate signing certificate was obtained. The Flame virus also propagated by using an MD5 collision. So, this is not there, but reality!

Weak collision resistance, or more exactly, target resistance or 2nd-preimage resistance is important when a collision must be found with a given hash. But this is often not the case.

Improve this answer
$\endgroup$
5
  • $\begingroup$ "Another example is code signing": how would that work in practice? If you have malicious code $C_1$ and "good" code $C_2$, the objective seems to be to adapt say $C_1$ to $C'_1$ so that $h(C'_1) = h(C_2)$, i.e. given $C_2$ and $h(C_2)$ find a second preimage? $\endgroup$
    – Erik Vesterlund
    Mar 12, 2016 at 19:26
  • 2
    $\begingroup$ @ErikVesterlund In practice, you often create some "good" piece of code that contains a block of data that can be changed without changing the "goodness" of the code, e.g. a block of text in a comment, and a "bad" piece of code that also contains such a block of data. I can now freely manipulate the two blocks of data until I find a pair such that the hashes of the overall programs (including the two blocks of data) are the same. This is not exactly the same as a collision attack, but tends to be about as easy $\endgroup$
    – raptortech97
    Mar 12, 2016 at 19:39
  • $\begingroup$ Fair enough but in your first example you "happen" to find two certs that collide which have the URL you want, this is no longer a collision of any two inputs but collision of two desired inputs (google and Yehuda Lindell) so it is no longer a collision resistance attack but a preimage attack. $\endgroup$
    – kodlu
    Mar 12, 2016 at 23:35
  • $\begingroup$ @kodlu : ​ en.wikipedia.org/wiki/Non_sequitur_(logic) ​ ​ ​ ​ $\endgroup$
    – user991
    Mar 13, 2016 at 3:45
  • 2
    $\begingroup$ @kodlu I do not happen to find two certs that collide with the URL I want. I do it on purpose. It is not a preimage attack since I do not find one and then afterwards find the other. Rather the attack finds them at the same time, and utilizes the flexibility that I have in order to do it. You are possibly confused because you can't see how this is possible to do. However, it is, and I encourage you to look at all the work on "smart" MD5 collisions in order to see how. Of course, that is just an example and different methods may also exist (that we don't know of yet). $\endgroup$
    – Yehuda Lindell
    Mar 13, 2016 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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