5 ms·

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 https://news.ycombi

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 https://news.ycombinator.com/item?id=9322489 AFAICT it's not yet resolved.

hardwaresofton 11y ago
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.
- gtrubetskoy 11y ago
  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.
  - hardwaresofton 11y ago
    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?
  - dchest 11y ago
    There's no hashing construction that will "completely eliminate the possibility" (see https://en.wikipedia.org/wiki/Pigeonhole_principle 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.pdf https://www.iacr.org/cryptodb/archive/2004/CRYPTO/1472/1472....
- titfn 11y ago
  instead of calculating multiple hashes every time, might as well use a better hash?
  - hardwaresofton 11y ago
    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.
- TheDong 11y ago
  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/ http://directory.io/ The human mind just isn't capable of understanding how large of a number the number of sha hashes is.
  - colordrops 11y ago
    But the probability that sha256 is broken is much much higher than a collision, and definitely within the realm of human understanding.
    - _prometheus 11y ago
      this is why we use multihash -- https://github.com/jbenet/multihash https://github.com/jbenet/multihash
  - hardwaresofton 11y ago
    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.
    - walrus 11y ago
      > 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.)
whyrusleeping 11y ago
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.
- gtrubetskoy 11y ago
  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...)
  - whyrusleeping 11y ago
    Heres the article i normally link to when this comes up: http://stackoverflow.com/questions/4014090/is-it-safe-to-ignore-the-possibility-of-sha-collisions-in-practice 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.
    - _prometheus 11y ago
      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)
nabla9 11y ago
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%.

hardwaresofton 11y ago

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.

gtrubetskoy 11y ago
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.
- hardwaresofton 11y ago
  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?
- dchest 11y ago
  There's no hashing construction that will "completely eliminate the possibility" (see https://en.wikipedia.org/wiki/Pigeonhole_principle 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.pdf https://www.iacr.org/cryptodb/archive/2004/CRYPTO/1472/1472....
titfn 11y ago
instead of calculating multiple hashes every time, might as well use a better hash?
- hardwaresofton 11y ago
  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.
TheDong 11y ago
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/ http://directory.io/ The human mind just isn't capable of understanding how large of a number the number of sha hashes is.
- colordrops 11y ago
  But the probability that sha256 is broken is much much higher than a collision, and definitely within the realm of human understanding.
  - _prometheus 11y ago
    this is why we use multihash -- https://github.com/jbenet/multihash https://github.com/jbenet/multihash
- hardwaresofton 11y ago
  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.
  - walrus 11y ago
    > 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.)

whyrusleeping 11y ago

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.

gtrubetskoy 11y ago
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...)
- whyrusleeping 11y ago
  Heres the article i normally link to when this comes up: http://stackoverflow.com/questions/4014090/is-it-safe-to-ignore-the-possibility-of-sha-collisions-in-practice 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.
  - _prometheus 11y ago
    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)

nabla9 11y ago

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