20
$\begingroup$

I was wondering if there's any string that has a hash equal to itself, so that – when using any (none specific) hash function – the hash would be equal to that string?

so that:

hash(x) = x

Note that this is not an assignment or anything. I’m just curious and couldn't find any specific answer or reference. And I’m not sure how to go and prove/disprove that to myself!

$\endgroup$

migrated from stackoverflow.com Oct 6 '14 at 12:44

This question came from our site for professional and enthusiast programmers.

22
$\begingroup$

I restrict to hash functions $H$ with an output of some fixed size $n\ge1$ bit(s), accepting as input some strings, including all $n$-bit strings; MD5 (resp. SHA-1, SHA-256) is an example of such function for $n=128$ (resp. $n=160$, $n=256$).

Whether there exists a solution to $H(x)=x$ depends on the particular hash function. If $H$ is a random function (as MD5, SHA-1, and SHA-256 aim to be), the answer is YES with odds next to $63.2\%$ for practical values of $n$.

More precisely: $H(x)=x$ can hold only if $x$ has exactly $n$ bits. There are $2^n$ values of $x$ that satisfy the later condition, and restricting $H$ to such $x$ there are $(2^n)^{(2^n)}$ different $H$ functions, of which $(2^n-1)^{(2^n)}$ such that $H(x)=x$ has no solution. Therefore, if we choose one $H$ uniformly randomly, odds are exactly $1-{(2^n-1)^{(2^n)}\over(2^n)^{(2^n)}}=1-(1-2^{-n})^{(2^n)}$ that we picked $H$ such that $H(x)=x$ has a solution. As $n$ increases, this converges very fast to $1-1/e\approx0.632$ (where $e\approx2.718$ is the base of the natural logarithm).

This does not tell if MD5 has the property that there exists a solution to $\operatorname{MD5}(x)=x$ (which would be a 128-bit bitstring $x$). The best we can say is that it likely holds, with odds about to 63%, but determining if the assertion is true or false is beyond our current computing power (the best method we have is exhaustive search, and if the answer is no it would require $2^{128}$ hashes; otherwise it is still likely to require over $2^{126}$ hashes, which is beyond reach).

PHP specific: if md5($string) === $string had some solution, that would be a 32-character string of hexadecimal lowercase characters; we are not hashing the same $2^{128}$ candidates as above so the question is not equivalent, but the reasoning can be adapted, and again the best we can say is that it is likely there's a solution, with odds about 63%.
The question originally asked if there is a string such that md5($string) == $string; to answer this, we must take into account how the == operator works due to type juggling (it holds that "0042" == "42", and "20e2" == " +002000"). It is overwhelmingly likely that there is a solution (just consider that among the $2^{200}$ strings consisting of 200 space or tab and an additional final 0, we expect about $31\cdot2^{72}$ hash to one of "00000000000000000000000000000000", "000000000000000000000000000000e0" .. "0e000000000000000000000000000000"); however we can't exhibit one.


It is easy to define a hash function $H$ such that $H(x)=x$ has no solution: for example, define $$H(x)=\begin{cases}x\oplus1&\text{if }\operatorname{MD5}(x)=x\\\operatorname{MD5}(x)&\text{otherwise}\end{cases}$$


It is also easy to define a hash function $H$ such that $H(x)=x$ has at least one solution: for example, choose some arbitrary 128-bit constant like $k=\text{af5d2bc6c9181f76f3161f43f41f6aeb}$, and define $$H(x)=\begin{cases}k&\text{if }x=k\\\operatorname{MD5}(x)&\text{otherwise}\end{cases}$$


There can be no $x$ such that for all possible hash functions $H$, $H(x)=x$.

Proof by contraposition: assume there is such $x$, a function $H$ with $x$ having that property, and consider the function $\tilde H$ defined by $\tilde H(x)=H(x)\oplus1$.

$\endgroup$
-2
$\begingroup$

This won’t be possible, because the MD5 algorithm has left bit rotation by $s$ places, where $s$ varies for each operation. So, the MD5 of a string can never be the same string.

Refer the Algorithm section of Wikipedia’s MD5 article.

Every hashing algorithm has its basis in block ciphers and there is byte-shifting involved as a core part. So, it won’t be possible that a plaintext $m$ is equal to ciphertext $c$.

$\endgroup$
  • $\begingroup$ Sure, what about any other algorithms ? $\endgroup$ – Mostafa Torbjørn Berg Sep 12 '14 at 10:24
  • 3
    $\begingroup$ The use of bit rotation doesn't guarantee this property. For example, if an algorithm used only bit rotation, even by a varying number of bits, a string of all zeros or all ones would hash to itself. There's something missing in this answer. $\endgroup$ – guest Sep 15 '14 at 19:44
  • 1
    $\begingroup$ I think that the argument about left bit rotation making a solution impossible for MD5 is plain wrong. $\endgroup$ – fgrieu Oct 6 '14 at 14:17
  • 2
    $\begingroup$ Keeping it short: rotation itself does not guarantee anything! Most of the time, it merely helps hashing functions to gain and/or enhance their avalanche effect. But in the unlikely case you’re aware of any papers which provide proof that MD5 and/or the SHA families use bitwise rotations to specifically prevent something like that from happening, I would surely be interested in getting a heads-up… because it would be the first time I would see a security proof that’s based on “bitwise rotations” only. $\endgroup$ – e-sushi Oct 6 '14 at 16:39
  • 3
    $\begingroup$ A rotation itself doesn't prevent things mapping to itself, e.g. (on a byte-level) rotating 11111111 by any amount still gives 11111111. $\endgroup$ – Paŭlo Ebermann Oct 6 '14 at 20:13
-2
$\begingroup$

With any hash function as you ask:

No.

If you write a Hash-function wich calculates the Hash-value in some way, and then append a t to the result (because you like the letter), then no matter what your input string is, the hash result will be different from your input.

For specific hash functions:

Sure, it could be; especially with a "bad" hash-function like "first 3 letters of the String".


Since a clarification (see comment) pointed out that the question only targets mature hash functions, please refer to user2351586's answer for MD5 specifics.

$\endgroup$
  • $\begingroup$ I'm not sure I'm following what you mean by As your hash-function can really be ANY, so you could just append a "t" at the end of your result because you like that letter. If you append a t, the string will have changed.. Hash functions do not modify the input string. yeah i know a bad implementation would do that, but what I had in mind is mature ones that we use daily $\endgroup$ – Mostafa Torbjørn Berg Sep 12 '14 at 9:31
  • $\begingroup$ I edited my answer due to the question. Thanks for clarifying the question! $\endgroup$ – Layna Sep 12 '14 at 9:41
  • 4
    $\begingroup$ Appending a "t" to the end of the result of any function doesn't guarantee this property. For a trivial function that always returns "a" for the hash of any input, the hash of "at" would be "at" for this hash algorithm. $\endgroup$ – guest Sep 15 '14 at 19:46

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.