Hacker News Reader

Comment by gtrubetskoy | Hacker News Reader

My first thought is how does it handle SHA hash collisions? Googling for it took me back to HN: https://news.ycombinator.com/item?id=9322489 AFAICT it's not yet resolved.

View on HN

256 bit hash collisions have so low probability that you don't need to prepare for them. If one happens, its cause for celebration.

You can cover earth surface with 8.5×10^36 oxygen atoms. Imagine that every one of them is IPFS file with 256 bit hash. Probability of collision is still less than 0.1%.

ipfs currently uses what we call a 'multihash' where every hash value is tagged with the hash function used to generate it. As of now, the default hash function is sha256, and if I recall correctly, the chances of a world ending asteroid hitting earth and wiping out the planet is far more likely to occur than a collision. If sha256 is shown to be broken, we can change our default hash function to something like sha512 without breaking any existing data.

Well.... while an asteroid annihilating life on the planet isn't likely, the size of the web isn't a joke either, so such a collision is more probable than in other cases...

I suppose this could be made a problem for the user, i.e. if you want to make sure that your page isn't colliding with any other, then simply check first. (Of course there is still a race condition possibility of two colliding addresses being created at around the same time...)

Heres the article i normally link to when this comes up: http://stackoverflow.com/questions/4014090/is-it-safe-to-ign...

Its generally considered safe to ignore, there are no known sha256 collisions, and most people are fairly confident they wont see one for quite some time.

the caveat of course being that SHA256 may be _broken_. That's when we'd have to upgrade to another hash function.

(We may improve how this upgrade will work down the road by allowing links to link with multiple hashes at the same time, but at this time this has not proved to be necessary, and can be added later)

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.

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.

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.

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

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.

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

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?

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