3 ms·

Neat question. The best answer seems to be an HN thread from 13 years ago (!) which posits that the chance of one existing is ~63%: https://news.ycombinator.co

Neat question. The best answer seems to be an HN thread from 13 years ago (!) which posits that the chance of one existing is ~63%: https://news.ycombinator.com/item?id=614079 https://news.ycombinator.com/item?id=614079 However, it appears no one has actually discovered it yet, if it exists. A more tractable question might be to find a cycle in the MD5 hash space, like a->b->c->d->a. So one might ask, what is the shortest MD5 cycle found so far?

Retr0id 4y ago
Funny timing, I was joking about this percentage mere days ago - https://retr0.id/notice/ANnYouw6w2di8XvcNE https://retr0.id/notice/ANnYouw6w2di8XvcNE
- papandada 4y ago
  Are there any other examples of this?
  - amelius 4y ago
    I think it's mostly a joke because the negation of a predicate is a predicate too, and they can't both have the same probability unless it's 50%.
manimino 4y ago
Follow-up -- If you repeatedly do MD5(MD5(MD5(something))), how long will it take to find a repeat value? Assuming MD5 is random, this is the birthday problem. Since MD5 is 128 bits, you need about 10^19 hashes to get a repeat. [1] The MD5 hashrate on an RTX 3090 is about 65 billion hashes per second. [2] Dividing that out, about 4 GPU-years would be needed to find a repeat in this brute-force way. [1] https://en.wikipedia.org/wiki/Birthday_attack#Mathematics https://en.wikipedia.org/wiki/Birthday_attack#Mathematics [2] https://gist.github.com/Chick3nman/e4fcee00cb6d82874dace72106d73fef https://gist.github.com/Chick3nman/e4fcee00cb6d82874dace7210...
- userbinator 4y ago
  Isn't the GPU doing that in parallel? If you want to feed the output of the hash into itself, I think it'll be much slower.
  - manimino 4y ago
    You'd need to run many parallel processes like MD5(MD5(MD5(thing1))), MD5(MD5(MD5(thing2)))... I think the math still works if you do that. But the cycle would have to be contained entirely within one of the individual runs. So that could potentially take longer. The tricky part would be combing through the 160 exabytes of output to find the cycle.
    - fsckboy 4y ago
      > The tricky part would be combing through the 160 exabytes of output to find the cycle I don't think you get to leave that out of the O(?) of this problem
      - Retr0id 4y ago
        You can, since there are cycle detection algorithms that do not increase the big-O complexity at all (constant factor).
    - hinkley 4y ago
      So I’m getting much bigger than 160 exabytes. Can you show your math? MD5 is 128 bits so that’s 2^128 keys. And it’s 32 bytes for the output, so that’s really 2^133 bytes. Which is 10^38 which we don’t even have a unit for yet. Apparently it’s 100 million queccabytes. You can get that down to two million queccabytes if you use a Bloom filter.
      - manimino 4y ago
        You don't have to generate every possible md5. Just ~10^19 keys is enough to probably have a cycle.

Retr0id 4y ago

Funny timing, I was joking about this percentage mere days ago - https://retr0.id/notice/ANnYouw6w2di8XvcNE https://retr0.id/notice/ANnYouw6w2di8XvcNE

papandada 4y ago
Are there any other examples of this?
- amelius 4y ago
  I think it's mostly a joke because the negation of a predicate is a predicate too, and they can't both have the same probability unless it's 50%.

manimino 4y ago

Follow-up -- If you repeatedly do MD5(MD5(MD5(something))), how long will it take to find a repeat value? Assuming MD5 is random, this is the birthday problem. Since MD5 is 128 bits, you need about 10^19 hashes to get a repeat. [1] The MD5 hashrate on an RTX 3090 is about 65 billion hashes per second. [2] Dividing that out, about 4 GPU-years would be needed to find a repeat in this brute-force way. [1] https://en.wikipedia.org/wiki/Birthday_attack#Mathematics https://en.wikipedia.org/wiki/Birthday_attack#Mathematics [2] https://gist.github.com/Chick3nman/e4fcee00cb6d82874dace72106d73fef https://gist.github.com/Chick3nman/e4fcee00cb6d82874dace7210...

userbinator 4y ago
Isn't the GPU doing that in parallel? If you want to feed the output of the hash into itself, I think it'll be much slower.
- manimino 4y ago
  You'd need to run many parallel processes like MD5(MD5(MD5(thing1))), MD5(MD5(MD5(thing2)))... I think the math still works if you do that. But the cycle would have to be contained entirely within one of the individual runs. So that could potentially take longer. The tricky part would be combing through the 160 exabytes of output to find the cycle.
  - fsckboy 4y ago
    > The tricky part would be combing through the 160 exabytes of output to find the cycle I don't think you get to leave that out of the O(?) of this problem
    - Retr0id 4y ago
      You can, since there are cycle detection algorithms that do not increase the big-O complexity at all (constant factor).
  - hinkley 4y ago
    So I’m getting much bigger than 160 exabytes. Can you show your math? MD5 is 128 bits so that’s 2^128 keys. And it’s 32 bytes for the output, so that’s really 2^133 bytes. Which is 10^38 which we don’t even have a unit for yet. Apparently it’s 100 million queccabytes. You can get that down to two million queccabytes if you use a Bloom filter.
    - manimino 4y ago
      You don't have to generate every possible md5. Just ~10^19 keys is enough to probably have a cycle.