Hacker News new | ask | show | jobs
by ForkMeOnTinder 894 days ago
How is it impossible? I would think an MD5 quine exists with probability approaching 1 as the size of the document grows to infinity. Think about the reduced problem:

1. a document containing "1", whose hash begins with "1"

2. a document containing "12", whose hash begins with "12"

3. a document containing "123", whose hash begins with "123"

#1 is certain to exist. #2 exists, but would take 16x as long to brute force. #3 would take 16x longer again. If this pattern doesn't continue until 2^128, where would it stop, and why?

All hashes can be brute forced this way, even secure ones SHA-2. Its security relies on the fact that the earth doesn't contain enough computing power to execute a brute force attack within the universe's lifetime.
2 comments
userbinator 894 days ago
as the size of the document grows to infinity.

Therein lies the problem.

Also the fact that it would need to be constrained to 7-bit ASCII only, and on top of that be "valid" in its natural language. It's a neat trick to make two documents look completely different with the same hash, but looking at the techniques which are required, they all rely on a binary file format and copious amounts of data which are effectively "hidden" --- all of which do not apply to a text file.

link
Jenda_ 893 days ago
Maybe try to have a look at it as permutations: the mapping "hex of the hash" → "its actual hash" is a (presumably random) permutation. And it's quite probable that such permutation has a fixed point: http://laurentmazare.github.io/2014/09/27/fixed-points-of-ra...

The problem is that we currently don't know how find it more efficiently than with exhaustive search, AFAIK.

Edit: previously on HN: https://news.ycombinator.com/item?id=614079

link