2
$\begingroup$

Say some random person manages to, by sheer luck, find 2 messages with the same hash. There is no systematic way of creating more such pairs of messages that produce collisions.

How much would this one pair of collision producing messages affect the security of the hash function?

Improve this question
$\endgroup$
2
  • $\begingroup$ At best it might give insight into what features colliding messages might have for that hash function. The really interesting part is all the evil things you could do with a collision. $\endgroup$
    – user13741
    Commented Sep 3, 2017 at 3:15
  • $\begingroup$ It's difficult. Because all the energy of the sun isn't enough for you to get that lucky, so finding a collision should imply it's insecure. But, what if it simply was just pure luck. I don't even know. I figure the inputs would be analysed for any correlation, and also the inputs should be pretty long too for a lucky argument to be plausible. $\endgroup$
    – Awn
    Commented Sep 3, 2017 at 4:30

1 Answer 1

Reset to default
2
$\begingroup$

In many cases the collision might be exploitable to create many other collisions. In almost all common constructions you could use the collision to build a collision of messages with arbitrary suffix. Building a useable collision for most attacks like colliding pdfs requires something about the prefix. But even without a known attack on the relevant prefix I would be worried a different exploitation scenario exists. Also I would be very worried about such "luck" which may suggest either: a. The chance of collision is much higher than it seems b. There is an efficient way of generating collisions it's simply not public.

Furthermore the structure of the collision may give important cryptographic insights.

So for a random collision I don't know of an exploitable attack. I worry there is such, I worry the collision could be extended, the crypo is weaker than it seems and may have already been broken. I would migrate away.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The Merkle–Damgård construction has this behaviour out of the box BUT sponge constructions like SHA-3 (and other modern hashes) don't do this, you can't just add a suffix. Also, if suffix attacks are a problem for your application you probably wanted a MAC, and a MAC wouldn't be vulnerable to this problem. $\endgroup$
    – tialaramex
    Commented Sep 3, 2017 at 16:32
  • 2
    $\begingroup$ @tialaramex To produce a collision in a sponge construction, at least in the case of sha-3 where the bit length of the rate is greater than the bit length of the capacity. A capacity collision is all that is required to produce a full collision provided you consider the domain extender. So then checking the random rates provided by both messages the attacker must choose an arbitrary value to converge to, and could pick any number of ways to manipulate the rates to produce the output they desire. $\endgroup$
    – Q-Club
    Commented Sep 3, 2017 at 22:19

Your Answer

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

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