Hacker News Reader

Comment by hardwaresofton | Hacker News Reader

In the (relatively rare) case of a SHA hash collision, couldn't you try and resolve a collision by using (the results) of other hashing functions?

While two things may produce the same SHA hash, they may differ with other hashing functions.

View on HN

All you're doing then is fiddling with probabilities. You can do that just as well by changing the length of the sha unless you have a reason to think sha is broken.

However, the probability of a hash collision is already incredibly low. As a demonstration of this, here's a list of a tiny subset of bitcoin private keys: http://directory.io/

The human mind just isn't capable of understanding how large of a number the number of sha hashes is.

But the probability that sha256 is broken is much much higher than a collision, and definitely within the realm of human understanding.

this is why we use multihash -- https://github.com/jbenet/multihash

Right, but fiddling with probabilities is exactly what you want to do in that case right? I don't know if a hashing algorithm that has no collisions exists (I suspect the answer is no, maybe other than the identity function). If collisions start to become a problem, you can move that problem further out (much much farther out) by mixing more hashing functions in, which was my point.

It's well documented (of course also by the link you posted), the super low likelihood of hash collisions, but I think (hope) the original poster knew that -- was trying to answer assuming that extraordinary case actually happened.

> I don't know if a hashing algorithm that has no collisions exists (I suspect the answer is no, maybe other than the identity function).

There is no hash function without collisions. The set of inputs is infinite but the set of outputs is finite. (The identity function isn't a hash function--its output isn't a fixed length.)

Thanks for the correction! Somehow forgot the fixed length output requirement of hashing functions.

It will reduce the probability of a collision at the expense of the address being longer - because now you need to carry around hash1 + hash2. But still it doesn't eliminate the possibility, only makes it less likely.

Exactly, what I noted was the most likely temporary/possibly long-term solution to the problem.

What about hashing an object that contains the hashes generated by x hashing algorithms? an extra step of resolution, sure, but some way to easily demarcate that some file experienced a collision with another file, and had to have the number of hashes increased to stave off further collisions?

There's no hashing construction that will "completely eliminate the possibility" (see https://en.wikipedia.org/wiki/Pigeonhole_principle), so I'm not sure what answer you're looking for. It's computationally infeasible to generate collisions (accidental or malicious) if SHA-2 is not broken. If you're interested in reading about how combining multiple hashes affects security, see this paper: https://www.iacr.org/cryptodb/archive/2004/CRYPTO/1472/1472....

instead of calculating multiple hashes every time, might as well use a better hash?

We're way past my personal knowledge, but what I was thinking was that the probablistic combinations of two algorithms outweigh (in terms of probability of a collision) the likely hood of a single algo.

IE if you have some hashing function with a 1/2^5 chance of a collisions, using that in conjuntion with another hashing function with say 1/2^3 requires that both unlikely probabilities occur, resulting in 1/2^8, where a "stronger" hashing function might only have 1/2^6 (technically stronger than either one of them, but still not as strong as both)

I'd really love some correction on the logic above though, I am by no means well studied in probability or hashing functions, despite some effort, and would really appreciate any corrections.

Reply on news.ycombinator.com