4 ms·

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.

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
You could use a cycle-detection algorithm like the tortoise and hare, to avoid needing to keep a list of previous results etc. https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoi...
hinkley 4y ago
Not even that many. With MD5 and at least through SHA-2 you can build the search tree based on a branching structure, where you clone the in-process hash as you go, so that for instance all of the hashes that differ only by the last byte share one partial hash and then feed in the last digit. As long as you can keep 31 partial hashes in memory at a time, which is trivial, you don't have to rerun the work so far to increment the last digit by 1. I think I may have written the code for this at one point. I'll have to look around and see if I can find it.
- Retr0id 4y ago
  That doesn't apply to this situation.
  - hinkley 4y ago
    > Is there an MD5 hash string that hashes to itself? That’s calculable in cpu hours, not GPU years. If the answer is one then you’re done. If it’s not then you test N=2 in 4 GPU years, rather than 8. As N increases the answer becomes less interesting, and the cost goes quadratic.
    - Retr0id 4y ago
      I'm not following. Let's assume N=1, what's the pseudocode to find it in cpu-hours?
Too 4y ago
Sounds a bit like proving there are no cycles in the 3n+1 equation. https://en.m.wikipedia.org/wiki/Collatz_conjecture https://en.m.wikipedia.org/wiki/Collatz_conjecture. Veritasium has a good video about it.

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

You could use a cycle-detection algorithm like the tortoise and hare, to avoid needing to keep a list of previous results etc. https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoi...

hinkley 4y ago

Not even that many. With MD5 and at least through SHA-2 you can build the search tree based on a branching structure, where you clone the in-process hash as you go, so that for instance all of the hashes that differ only by the last byte share one partial hash and then feed in the last digit. As long as you can keep 31 partial hashes in memory at a time, which is trivial, you don't have to rerun the work so far to increment the last digit by 1. I think I may have written the code for this at one point. I'll have to look around and see if I can find it.

Retr0id 4y ago
That doesn't apply to this situation.
- hinkley 4y ago
  > Is there an MD5 hash string that hashes to itself? That’s calculable in cpu hours, not GPU years. If the answer is one then you’re done. If it’s not then you test N=2 in 4 GPU years, rather than 8. As N increases the answer becomes less interesting, and the cost goes quadratic.
  - Retr0id 4y ago
    I'm not following. Let's assume N=1, what's the pseudocode to find it in cpu-hours?

Too 4y ago

Sounds a bit like proving there are no cycles in the 3n+1 equation. https://en.m.wikipedia.org/wiki/Collatz_conjecture https://en.m.wikipedia.org/wiki/Collatz_conjecture. Veritasium has a good video about it.