6 ms·

Is there an MD5 hash string that hashes to itself?

by zeven7 4y ago

AustinDev 4y ago
Probably not but, would love to be proven wrong. To get this stuff to work you have to add a ton of garbage data to the end of the file from what I understand which you can't really do with a string.
- rileymat2 4y ago
  It is interesting that the OP used “hash string” instead of MD5 value. I’d wager that if you dove into string encodings that you would find some.
  - kadoban 4y ago
    There's not _that_ many encodings that feel natural enough. Maybe: bytes, ascii/utf-8/latin1/etc. (all equiv.), utf-16, utf-32, maybe ebcdic. I guess it should be pretty likely to exist if you try them all, but the search is likely very computationally difficult unless I'm forgetting some particular weakness in md5 (quite possible).
    - Retr0id 4y ago
      There are more options if you consider whitespace. You can separate the digit pairs with single or double spaces (or in groups of 4, etc. etc.), and end the line with nothing, or \n, or \r\n
      - kadoban 4y ago
        Good call, \n and \r\n feel like good ideas. Separating digits feels like it'd look a little cheap to me, but I'd still be impressed.
    - rileymat2 4y ago
      True, but you are mapping X items onto X space. The odds of a hit, if the algorithm allows it is already reasonably high, add four more encodings and I'd put money on one hitting.
      - kadoban 4y ago
        Yeah I think it's essentially independent dice rolls, that's gotta put it well into the 90%s
manimino 4y ago
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

Is there an MD5 hash string that hashes to itself?

by zeven7 4y ago

Is there an MD5 hash string that hashes to itself?

Probably not but, would love to be proven wrong. To get this stuff to work you have to add a ton of garbage data to the end of the file from what I understand which you can't really do with a string.

rileymat2 4y ago
It is interesting that the OP used “hash string” instead of MD5 value. I’d wager that if you dove into string encodings that you would find some.
- kadoban 4y ago
  There's not _that_ many encodings that feel natural enough. Maybe: bytes, ascii/utf-8/latin1/etc. (all equiv.), utf-16, utf-32, maybe ebcdic. I guess it should be pretty likely to exist if you try them all, but the search is likely very computationally difficult unless I'm forgetting some particular weakness in md5 (quite possible).
  - Retr0id 4y ago
    There are more options if you consider whitespace. You can separate the digit pairs with single or double spaces (or in groups of 4, etc. etc.), and end the line with nothing, or \n, or \r\n
    - kadoban 4y ago
      Good call, \n and \r\n feel like good ideas. Separating digits feels like it'd look a little cheap to me, but I'd still be impressed.
  - rileymat2 4y ago
    True, but you are mapping X items onto X space. The odds of a hit, if the algorithm allows it is already reasonably high, add four more encodings and I'd put money on one hitting.
    - kadoban 4y ago
      Yeah I think it's essentially independent dice rolls, that's gotta put it well into the 90%s

manimino 4y ago

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