Is it theoretically possible to construct a string that contains its own hash value? After saw the xkcd comic Self-Description, I wonder if it is theoretically possible to construct a self-descriptive string that contains its own hash value?

Let's say the string's MD5 value is 663ef7d3f38cf900574cd4d9f83eb1b7, the string would be something like:

...
The md5sum value of this file is 663ef7d3f38cf900574cd4d9f83eb1b7
...
Yes, for any secure cryptographic hash function, it is overwhelmingly likely that there exists a string which contains, or even begins with, its own hash value (in any given encoding, even).  However, if the hash function is indeed secure, it is also exceeding unlikely that we could ever find such a string.



First, let's look on the positive side.  A good cryptographic hash is, a priori, supposed to be indistinguishable from a random function from the set of all bitstrings (or byte strings) to bitstring of a given fixed length $k$.  For such a random function, the probability that a randomly chosen $n$-bit string (where $n \ge k$) maps to its own $k$-bit prefix is $1/2^k$.  Since there are $2^n$ distinct $n$-bit strings, the probability that none of them maps to its own $k$-bit prefix is:

$$\begin{aligned}
(1 - 1/2^k)^{2^n}
&amp;= \exp(2^n \log(1 - 1/2^k)) \\
&amp;\lesssim \exp(-2^n/2^k) \\
&amp;\to 0 \quad \text{as } n \to \infty
\end{aligned}$$

Thus, the probability that there is at least one $n$-bit string that maps to its own $k$-bit prefix tends to $1$ as $n$ increases.  Indeed, the convergence is extremely rapid, being given by the exponential of an exponential.  For example, for a 256-bit hash, the probability that there exists some 260-bit input string that hashes to its own 256-bit prefix is about $1 - \exp(-2^{260}/2^{256}) =$ $1 - \exp(-2^4) \approx$ $1 - 10^{-7}$.  For 261-bit inputs, it's $1 - \exp(-2^5) \approx$ $1 - 10^{-14}$, and so on.

Obviously, the probability that there is an input string that hashes to some substring of itself must be at least as high as the probability that there is one that hashes to its prefix.

In particular, a curious corollary of this result is that, for any secure hash function, the probability that there exists an input string that hashes exactly to itself is very close to $1 - \exp(-1) =$ $1 - 1/\mathrm e \approx$ $0.63$.  (This approximation is good as long as the output bit length $k$ is greater than about 4 or so.  For, say, a 256-bit hash function, it's as close to exact as makes no difference.)  This is a general mathematical result: for any sufficiently large set $S$, a randomly chosen function $f: S \to S$ has a fixed point with probability close to $1 - 1/\mathrm e$.



Now for the bad news: to find such a string by brute force, the expected number of trials we'd need is $2^k$.  For, say, $k=256$, such a search is way beyond not just currently available computing power, but any conceivable computing power achievable in the universe using known physics.

Now, of course, real hash functions are not actually random functions, and it's possible that there might be some way to find such strings more efficiently than by brute force.  However, if such a method were found, it would arguably be good evidence that the hash function in question was not secure, and that its use should be discontinued.

In particular, the ability to efficiently find an input string that hashes to a given value would be a clear break of first preimage resistance, and any hash function allowing it would be considered completely broken.  Technically, just having the ability to efficiently find strings that hash to a substring of themselves, without being able to control what the actual hash value is, would not violate any of the three standard security properties required of a hash function (first and second preimage resistance and collision resistance).  However, it would allow the hash function to be distinguished from a random function, and in practice, any plausible attack that would allow such input to be found would almost certainly compromise other security properties of the hash as well.