15
$\begingroup$

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
...
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Thomas
    Aug 22 '13 at 5:52
  • $\begingroup$ @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. $\endgroup$
    – Mys_721tx
    Aug 22 '13 at 6:11
  • $\begingroup$ I don't think this could be done even with a broken cryptographic hash function such as MD5. $\endgroup$
    – Maarten Bodewes
    Aug 22 '13 at 11:16
  • 1
    $\begingroup$ See also Is SHA-512 bijective when hashing a single 512-bit block? $\endgroup$ Oct 11 '13 at 19:24
  • 2
    $\begingroup$ There's a GIF displaying it's own MD5 hash shells.aachen.ccc.de/~spq/md5.gif $\endgroup$
    – Fractalice
    Mar 28 at 7:12
27
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\:$ $\endgroup$
    – user991
    Aug 22 '13 at 19:08
  • $\begingroup$ In that case, for a broken hash function (e.g. MD4), do we have a better chance to find such input? $\endgroup$
    – Mys_721tx
    Aug 23 '13 at 0:10
  • 2
    $\begingroup$ @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. $\endgroup$ Aug 23 '13 at 0:18
  • $\begingroup$ To find this string that contain its own hash value is $NP$ or $P$ problem ? $\endgroup$
    – T.B
    Nov 30 '13 at 9:02
  • 2
    $\begingroup$ @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. $\endgroup$ Nov 30 '13 at 14:33
6
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Although this answer seems basically correct (+1), a more formal answer would be preferable. $\endgroup$
    – Maarten Bodewes
    Aug 22 '13 at 11:13
  • 1
    $\begingroup$ 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. $\endgroup$
    – poncho
    Aug 22 '13 at 14:22
  • 1
    $\begingroup$ 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). $\endgroup$ Aug 22 '13 at 18:23
  • $\begingroup$ @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. $\endgroup$
    – Mamsaac
    Aug 22 '13 at 23:44
  • $\begingroup$ @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. $\endgroup$
    – Mamsaac
    Aug 22 '13 at 23:46
6
$\begingroup$

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 $2^{64}$-bit input and SHA-512 to $2^{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.

$\endgroup$
3
  • $\begingroup$ In the first paragraph, I don't understand the use of $2^N$-bit instead of $N$-bit in the phrase, "concatenation of all possible $2^𝑁$-bit strings". It seems to me that if the output of $H$ is $N$ bits long, the concatenation of all possible outputs will be the concatenation of all $2^N$ possible $N$-bit strings, rather than what was written. $\endgroup$ Mar 27 at 22:48
  • $\begingroup$ In the phrase, "MD5, SHA-1 and SHA-256 are limited to 64-bit input and SHA-512 to 128-bit input", should there be exponentiation there? I mean, 64-bit input is 8 bytes, and I'm pretty sure that I've applied SHA-256 to inputs that are longer than 8 bytes. Maybe this should read, "$2^64$-bit input" and "$2^128$-bit input" respectively? Also, this phrase implies that MD5, SHA-1 and SHA-256 all have the same size output, when in fact they have 128-bit, 160-bit, and 256-bit outputs respectively, per crypto.stackexchange.com/a/2148/18426 . $\endgroup$ Mar 27 at 23:00
  • $\begingroup$ @JimDeLaHunt I wrote those numbers with the habit of writing the limit on the input length, but didn't notice when I was writing the sentence that I was making calculations on the input length rather than the length of the input length. I've fixed that sentence, thanks. I assume that the reader is already familiar with the output lengths as they are very well known. $\endgroup$ Mar 27 at 23:14
1
$\begingroup$

The other answers have already pointed out that a secure hash function almost certainly has input-output pairs of this kind. What the answers so far have not pointed out is that it is trivial to construct a hash function that fulfills all standard hash function security criteria and for which a fixed point is known.

For instance, set $H(x) = SHA256(x) \oplus C_0$, where $C_0 := SHA256(0)$. Then clearly, $H$ is as collision-resistant, second-preimage resistant and first preimage resistant as $SHA256$, but on the other hand $H(0) = 0$ by construction.

Note that if we are not told how $C_0$ was constructed, we have no known better way of finding preimages (or, indeed, fixed points) of $H$ than brute force (of course if $C_0$ is chosen such as in the example, i.e. if $H$ has a fixed point that one might reasonably find in a small dictionary, then that fixed point can efficiently be found, but this is generically and trivially true anyway).

$\endgroup$
0
$\begingroup$

An example of such a file for MD5 is PoC||GTFO 0x14. This of course is only possible because MD5 is not a secure hash function. Sections 9-12 of that document explain how it can be done for various file formats (Postscript, PDF, GIF, and the iNES ROM format).

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\:$ $\endgroup$
    – user991
    Aug 22 '13 at 6:20
  • $\begingroup$ I'm confused, why can't SHA-1 take a bit string of any length? $\endgroup$
    – pg1989
    Aug 22 '13 at 6:59
  • $\begingroup$ Because the padding would become ambiguous. $\:$ $\endgroup$
    – user991
    Aug 22 '13 at 7:02
  • $\begingroup$ Oh I forgot about that, dag. You're right. $\endgroup$
    – pg1989
    Aug 22 '13 at 7:32
-2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Aug 22 '13 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.