6 ms·

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 th

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

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