Score:2

Understanding Hash collisions - why bad?

cn flag

I read few answers about the question: why are hash collisions so dangerous? But did not get a really satisfying answer. Assume we are the first people who found a SHA256-collision, like

sha256($§"%fa7asd8ft6sds) = sha256(889=?`/&&%"HSF)

(this is not a real equation, but assume it is true).

Why is this dangerous? Why is SHA256 broken now? How do I get more collisions out of this? And maybe more important collisions like sha256(Send me 5€) = sha256(Send me 5000€ &%$"§"%§%...)

knaccc avatar
es flag
If I sign a hash of message A, then the ability to find a hash collision would mean that you could claim that I signed message B instead, because they would share the same hash.
kelalaka avatar
in flag
Does this answer your question? [What are other good attack examples that use the hash collision?](https://crypto.stackexchange.com/questions/87104/what-are-other-good-attack-examples-that-use-the-hash-collision)
Score:4
in flag

First of all, cryptographic hash collisions are not found by searching or by chance. They are computed because - for some reason - the hash algorithm is broken. You'd still have to create about $2^{128}$ hashes to find a collision after all, even if you take the birthday bound in - and remember that you'd have to perform a compare as well, although there are tricks to speed that up.

Instead the team that performs the analysis will find a weak spot and exploit it, sometimes requiring a lot of resources. This also means that if you create a collision that you are likely to be able to create more collisions using the same methodology.

If a relatively small amount of internal states are affected then it may be possible to fix the hash - hardened SHA-1 for instance is protected against the SHAttered attack. Of course, now that SHA-1 is shown to be weak, there is plenty of reason to migrate to e.g. SHA-256 anyway, and I haven't seen an uptake in hardened SHA-1 anywhere.


Even if you have only two inputs generating the same hash value you may be in trouble. Hashes internally operate block-by-block. If it is possible to find a collision then the next blocks will also be vulnerable. In other words, if you find $H'(B_1) = H'(B_2)$ then $H'(B_1 \| E) = H'(B_2 \| E)$ where $\|$ is concatenation. Note that extension $E$ may contain any data. So in that sense: if you find one collision for SHA-256 then you've found many collisions of messages that start with a particular block or blocks of data.

For SHA-3 the situation is a tad more complex (it depends if the internal state - i.e. the capacity of the used sponge - is identical before or after the final operation) but basically you'd still be in trouble.


If these kind of collisions are applicable to your protocol is another question. Schemes such as HMAC that rely on a hash function are not affected at all, as it doesn't require collision resistance from the configured hash function.

poncho avatar
my flag
For SHA-3, the only internal state you need to be identical is the 'capacity bits'; the attacker can set the 'rate bits' on either message to whatever he wants (by selecting the message appropriately).
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.