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.
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.
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.
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.