6 ms·

Good article, but there are a lot of claims of '100% certainty' that arn't necessarily true. The author even states that hash functions only guarentee no colli

Good article, but there are a lot of claims of '100% certainty' that arn't necessarily true. The author even states that hash functions only guarentee no collisions to a high probability.

DennisP 9y ago
It looks like there are about as many Earth-like planets in the universe as grains of sand on the Earth. Write your name on a grain of sand on one of those planets. Now have someone else randomly pick a single grain of sand from some planet in the universe. How certain are you that they won't pick yours? The chance of that happening is roughly equal to the chance of a collision randomly occurring somewhere in a few quadrillion SHA256 hashes. https://crypto.stackexchange.com/questions/52261/birthday-attack-against-sha256 https://crypto.stackexchange.com/questions/52261/birthday-at... http://www.npr.org/sections/krulwich/2012/09/17/161096233/which-is-greater-the-number-of-sand-grains-on-earth-or-stars-in-the-sky http://www.npr.org/sections/krulwich/2012/09/17/161096233/wh... https://www.cnet.com/news/the-milky-way-is-flush-with-habitable-planets-study-says/ https://www.cnet.com/news/the-milky-way-is-flush-with-habita...
- CoryG89 9y ago
  So what you're telling me is I have a chance? :P
- dracodoc 9y ago
  It's totally possible the reality is different from the theoretical limit. See collision attacks against MD5, SHA-0 by Wang Xiaoyun. https://en.wikipedia.org/wiki/Wang_Xiaoyun https://en.wikipedia.org/wiki/Wang_Xiaoyun
  - api 9y ago
    Those are directed attacks not random collisions.
    - skate22 9y ago
      The article uses the context of content validation from untrusted sources lol
      - DennisP 9y ago
        As long as the hash function remains unbroken, untrusted sources can't screw with you. Hash functions tend to be broken gradually and publicly, and we migrate to new ones as they start to look shaky. It's theoretically possible for someone to privately break a function that everyone else thinks is secure, but it would be an extremely impressive achievement since lots of full-time cryptographers work on breaking these things and publish every little bit of progress they make.
  - DennisP 9y ago
    Yes, the chance that the hash will be broken is much higher than the chance of collisions occurring randomly. I'm just responding to "hash functions only guarantee no collisions to a high probability." People really underestimate how strong that probabilistic guarantee is.
- ComodoHacker 9y ago
  Let's suppose everyone has moved to content addressing. Considering all the amount of content generated every day, how much time would it take before real hash collisions start to emerge?
  - openasocket 9y ago
    The number of 256-bit hashes you would have to generate in order to have a 50% that there's a duplicate in there is ~4*10^38. If we had a billion machines each generating a billion new hashes a second, it would take over 12 million years to get that many.
    - GordonS 9y ago
      This assumes computing power will remain constant; it won't. Also, it's highly likely that flaws will be found with the hash algorithm long before 12 million years are up.
      - openasocket 9y ago
        I don't assume computing power is constant, just that the rate of content generation is more or less constant (I think a billion devices publishing a billion new pieces of content every second is a pretty reasonable upper bound). OP asked about the odds of collisions occurring by accident due to the sheer volume of content generated and published, not about attacker scenarios. Obviously we wouldn't use the same hash algorithm and setup for 12 million years, but the sheer absurdity of that length of time and that pace of content production shows this method will last, at least until flaws are found in SHA256.
      - jononor 9y ago
        IPFS uses a multihash format, so that new hash functions can be introduced over time.
    - ComodoHacker 9y ago
      >50% that there's a duplicate in ther I think even 0.01% would be enough to harm usability.
Blahah 9y ago
100% certainty is correct to integer rounding. It's correct to many significant figures too.
- skate22 9y ago
  I think '100% certainty' should be reserved for claims that have been proven to always be true. I'm fine with saying 'near 100% certainty'lol

Good article, but there are a lot of claims of '100% certainty' that arn't necessarily true. The author even states that hash functions only guarentee no collisions to a high probability.

DennisP 9y ago

It looks like there are about as many Earth-like planets in the universe as grains of sand on the Earth. Write your name on a grain of sand on one of those planets. Now have someone else randomly pick a single grain of sand from some planet in the universe. How certain are you that they won't pick yours? The chance of that happening is roughly equal to the chance of a collision randomly occurring somewhere in a few quadrillion SHA256 hashes. https://crypto.stackexchange.com/questions/52261/birthday-attack-against-sha256 https://crypto.stackexchange.com/questions/52261/birthday-at... http://www.npr.org/sections/krulwich/2012/09/17/161096233/which-is-greater-the-number-of-sand-grains-on-earth-or-stars-in-the-sky http://www.npr.org/sections/krulwich/2012/09/17/161096233/wh... https://www.cnet.com/news/the-milky-way-is-flush-with-habitable-planets-study-says/ https://www.cnet.com/news/the-milky-way-is-flush-with-habita...

CoryG89 9y ago
So what you're telling me is I have a chance? :P
dracodoc 9y ago
It's totally possible the reality is different from the theoretical limit. See collision attacks against MD5, SHA-0 by Wang Xiaoyun. https://en.wikipedia.org/wiki/Wang_Xiaoyun https://en.wikipedia.org/wiki/Wang_Xiaoyun
- api 9y ago
  Those are directed attacks not random collisions.
  - skate22 9y ago
    The article uses the context of content validation from untrusted sources lol
    - DennisP 9y ago
      As long as the hash function remains unbroken, untrusted sources can't screw with you. Hash functions tend to be broken gradually and publicly, and we migrate to new ones as they start to look shaky. It's theoretically possible for someone to privately break a function that everyone else thinks is secure, but it would be an extremely impressive achievement since lots of full-time cryptographers work on breaking these things and publish every little bit of progress they make.
- DennisP 9y ago
  Yes, the chance that the hash will be broken is much higher than the chance of collisions occurring randomly. I'm just responding to "hash functions only guarantee no collisions to a high probability." People really underestimate how strong that probabilistic guarantee is.
ComodoHacker 9y ago
Let's suppose everyone has moved to content addressing. Considering all the amount of content generated every day, how much time would it take before real hash collisions start to emerge?
- openasocket 9y ago
  The number of 256-bit hashes you would have to generate in order to have a 50% that there's a duplicate in there is ~4*10^38. If we had a billion machines each generating a billion new hashes a second, it would take over 12 million years to get that many.
  - GordonS 9y ago
    This assumes computing power will remain constant; it won't. Also, it's highly likely that flaws will be found with the hash algorithm long before 12 million years are up.
    - openasocket 9y ago
      I don't assume computing power is constant, just that the rate of content generation is more or less constant (I think a billion devices publishing a billion new pieces of content every second is a pretty reasonable upper bound). OP asked about the odds of collisions occurring by accident due to the sheer volume of content generated and published, not about attacker scenarios. Obviously we wouldn't use the same hash algorithm and setup for 12 million years, but the sheer absurdity of that length of time and that pace of content production shows this method will last, at least until flaws are found in SHA256.
    - jononor 9y ago
      IPFS uses a multihash format, so that new hash functions can be introduced over time.
  - ComodoHacker 9y ago
    >50% that there's a duplicate in ther I think even 0.01% would be enough to harm usability.

Blahah 9y ago

100% certainty is correct to integer rounding. It's correct to many significant figures too.

skate22 9y ago
I think '100% certainty' should be reserved for claims that have been proven to always be true. I'm fine with saying 'near 100% certainty'lol