# Is it theoretically possible to construct a string that contain its own hash value?

After saw the xkcd comic self-description, I wonder is it 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
...

-
Are you asking about whether for any such string, there exists one (or more) possible "hash values" satisfying this condition, or whether for an arbitrary "hash value" you can find a string of a given length satisfying the condition? Or both? –  Thomas Aug 22 '13 at 5:52
@Thomas I think I meant both. One way I think of it is by adding characters to that string, the hash value of the string is equal to the arbitrary value. –  Mys_721tx Aug 22 '13 at 6:11
I don't think this could be done even with a broken cryptographic hash function such as MD5. –  Maarten Bodewes Aug 22 '13 at 11:16
–  Gilles Oct 11 '13 at 19:24

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} &= \exp(2^n \log(1 - 1/2^k)) \\ &\lesssim \exp(-2^n/2^k) \\ &\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.

-
At the end of your corollary paragraph, what's relevant is a randomly chosen function, $\hspace{1.21 in}$ although the limit for permutations happens to be the same. $\:$ –  Ricky Demer Aug 22 '13 at 19:08
@RickyDemer: Thanks, fixed. –  Ilmari Karonen Aug 22 '13 at 19:10
In that case, for a broken hash function (e.g. MD4), do we have a better chance to find such input? –  Mys_721tx Aug 23 '13 at 0:10
@Mys_721tx: If you have a practical chosen-prefix preimage attack on the hash, then you can use it to find such a string: just choose a prefix equal to the desired hash value. I'm not familiar with the attacks on MD4, but most attacks on Merkle-Damgård style hashes do tend to allow chosen prefixes. That said, AFAIK the best known preimage attacks on MD4 aren't really that practical yet: the Laurent attack still needs about $2^{102}$ compression function computations to find a full preimage. –  Ilmari Karonen Aug 23 '13 at 0:18
@Alex: With respect to what parameter? With respect to the hash output length $k$, it's clearly in NP($k$), assuming that computing the hash of a given string is in P($k$). By the argument given above, if the hash is secure in the sense described, finding such a string cannot be in P($k$). (Yes, the existence of secure hash functions implies that P ≠ NP.) With respect to the input string length, finding such a string (if there is one to be found) takes on average a constant number of hash evaluations, and is thus in ZPP. –  Ilmari Karonen Nov 30 '13 at 14:33

For any function $H$ with an $N$-bit output, take a string $S$ consisting of the concatenation of all possible $2^N$-bit strings (in any order).¹ This string contains all $N$-bit strings — including its own image by $H$. I'll call such strings $N$-bit-universal strings. The string is $N \cdot 2^N$ bits long, so it cannot be practically computed unless there is a mathematical way to find the hash value without processing the string bit by bit. The minimum length of an $N$-bit-universal string is $2^N + N - 1$.

A string $S$ of length $2^N$ or more also has the property that two of its prefixes have the same image (by the pigeonhole principle: there are $2^N$ distinct image values and $2^N+1$ or more prefixes). This means that any hash function that can work in streaming mode (read the input bits one by one with $O(1)$ work for each bit, and produce the hash in $O(1)$ work at the end of the input) is intrinsically broken for such input lengths — it is possible to exhibit a collision in $O(|S|)$ work. In fact, such collisions begin to be likely for strings that are around $2^{N/2}$ bits long, by the birthday paradox.

Typical cryptographic hash functions are limited to input that are $2^{N/2}$ bits long or less. For example, MD5, SHA-1 and SHA-256 are limited to 64-bit input and SHA-512 to 128-bit input. With this limitation, the easy example of a string containing its own hash value doesn't work.

It is possible to construct a function $H$ with $N$-bit output such that no string of length $2^N + N - 2$ or less hashes to an image that is a substring of the input. Write $S_0 \sqsubset T$ for “$S$ is a substring of $T$”. Take any function $G$ with $N$-bit output, and define $H(S) = G(S)$, except that if $G(S) \sqsubset S$, then take the next value in lexicographic order, and so on until a value that is not a substring of $S$ is found. It is likely that $H$ would make a worse hash function than $G$, because the way $H$ is constructed introduces a bias. To take an extreme example, if you take an $N$-bit-universal string of length $2^N+N-1$ and remove its last bit, then $H$ has only one possible value. A hash function should “look random” — an ideal hash function should be a random oracle (except that random oracles don't exist, so we make do with hash functions that are merely close enough to a random oracle for our purposes). That $H(S)$ is less likely (indeed, forbidden) to have a value that is a substring of $H$ shows that $H$ isn't a random oracle right there, which casts doubts as to its suitability as a cryptographic hash function. This is intrinsic in any function with the property that $H(S)$ is never a substring of $S$.

If $H$ is close enough to a random oracle, then probabilistically speaking, the events $H(X) = Y$ and $Y \subseteq X$ are independent. Since Ilmari Karonen has already written a very good analysis, I won't repeat it here: there's a very good chance that there is a string of length only little more than $N$ that contains its hash as a substring. For a string of length $N$, the probability is already about $1-e^{-1} \approx 0.63$. However — and again I refer you tu Ilmari Karonen's excellent answer — precisely because a good hash function is close to a random oracle, there is no way to find such a string short of enumerating all possibilities.

-

The input space is "infinite" and thus it has an infinite amount of values that will collide into a single hash. This means that you can take any hash and concatenate it (with pre, post or pre and post values) with an infinite amount of different values, of any size, that will end up matching said hash. So, infinite amount of collisions means that out of an infinitely large input there will be a way in which the pattern of the hash will appear.

The thing is that when it comes to hashes, values like 2^256 (for a SHA-256 implementation) are already enormous and there is simply no current realistic way of coming with collisions, particularly under predefined limiting conditions.

So, yes, it is theoretically possible that string can contain its own hash, but it does not seem probable that you will find one.

-
Although this answer seems basically correct (+1), a more formal answer would be preferable. –  Maarten Bodewes Aug 22 '13 at 11:13
Technically, the input space for the SHA-1 and SHA-2 hash functions is not "infinite"; SHA-1 and SHA-256 inputs are limited to $2^{64}-1$ bits; SHA-512 is limited to $2^{128}-1$ bits. –  poncho Aug 22 '13 at 14:22
There's an incorrect or at least incomplete step in your reasoning: even with an infinite amount of values leading to the same hash, it could happen that none have that hash as a substring. It works if you tackle the problem the other way round: consider the concatenation of all possible $N$-bit strings; for any hash function with $N$-bit output, its hash must appear in it. This however assumes that the function is defined over strings of length at least $2^N+N-1$ (for shorter strings, you can build a hash function that avoids all substrings, but it won't be a good cryptographic hash). –  Gilles Aug 22 '13 at 18:23
@poncho I used "infinite" because, indeed, it isn't infinite. However, an string that is 2^128 bits long is so long that for practical purposes I commented it as infinite. –  Mamsaac Aug 22 '13 at 23:44
@Gilles that's an interesting approach to it. Ilmari Karonen's answer, which is excellent, still shows how overwhelmingly likely it is for there to exist the case. –  Mamsaac Aug 22 '13 at 23:46

Yes, in fact there are infinitely many strings which contain their own hash value. This is because the domain of a hash function is bit strings of any length, and by a simple counting argument you can show that some strings of the form $h_1 || b_0 || b_1 || ... || b_n$ have hash value $h_1$.

-
That only works for hash functions whose domain is actually bit strings of any length, something that is not satisfied by, for example, SHA-1, SHA-256, SHA-384, SHA-512. $\:$ –  Ricky Demer Aug 22 '13 at 6:20
I'm confused, why can't SHA-1 take a bit string of any length? –  pg1989 Aug 22 '13 at 6:59
Because the padding would become ambiguous. $\:$ –  Ricky Demer Aug 22 '13 at 7:02
Oh I forgot about that, dag. You're right. –  pg1989 Aug 22 '13 at 7:32

For MD5 You can use HashClash to find "Chosen-prefix Collision".

-
But a chosen-prefix collision won't help here: the hash value is not predictable. Read the other answers for a more in-depth explanation. –  Gilles Aug 22 '13 at 16:25