27
$\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$
30
$\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%.
Further, the original question asked if there is a string such that md5($string) == $string. To answer this, we must take into account how the == operator works in PHP 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$.

| improve this answer | |
$\endgroup$
9
$\begingroup$

Yes, you can create many such functions.

For instance, lets build such a function based on SHA512. Generate some random value $m_0$ and generate a hash of it. It is important, because there is no guarantee that every 512-bit number has a pre-image.

So, let $h_0 = \operatorname{SHA512}(m_0)$. After hash generated, throw $m_0$ away. Technically you can do that as follows. Create a program that generates $m_0$ as a stream. It should generate a 64-byte block of random values, proceed with hashing, override these 64-bytes with a new block, proceed with hashing, etc. Thus, the program will at no time have the full value of $m_0$.

Now calculate its hash: $h_1 = \operatorname{SHA512}(h_0)$. With very high probability $h_1$ will differ from $h_0$.

Now define a new hash function as follows: \begin{align} \operatorname{hash}(x) &= (\operatorname{SHA512}(x) + h_0 - h_1 + 2^{512}) \bmod 2^{512}\end{align}

Calculate this hash function for $h_0$:

\begin{align} \operatorname{hash}(h_0) &= (\operatorname{SHA512}(h_0) + h_0 - h_1 + 2^{512}) \bmod 2^{512} \\ &= (h_1 + h_0 - h_1 + 2^{512}) \bmod 2^{512} \\ &= (h_0 + 2^{512}) \bmod 2^{512} \\ &= h_0 \end{align}

Thus \begin{align} \operatorname{hash}(h_0) = h_0 \end{align}

Our transformation is actually a rotation of a 512-bit number. This operation does not change the cryptographic properties. This means that cryptographic properties of our hash function are the same as of SHA512:

  • Pre-image resistance: Except of a single value $h_0$ that is a pre-image of itself, for any other value finding a pre-image is as hard as for SHA512
  • 2nd pre-image resistance: For any input and hash the complexity of finding of another input that gives the same hash is as hard as for SHA512. This holds also for $h_0$, because we don't know what was $m_0$.
  • Collision resistance: For any other hashes the complexity of finding collisions is the same as complexity for SHA512. This holds also for $h_0$, because we don't know what was $m_0$.

In this manner you can create other hash functions with other fixed points.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ I think this is actually much simpler. You don't need $h_0$ to have a preimage. You don't need the $m_0$ or the stream. Just start with any 512-bit number $h_0$. Let's say you wish for it to be a fixed-point of SHA512. But maybe it isn't, you have $h_1 = \mathrm{SHA512}(h_0)$. Too bad, it's just off by $h_0 - h_1$. So as you do you define a function $f(x) = \mathrm{SHA512}(x) + h_0 - h_1$. All computation is mod $2^{512}$ of course. Now $f(h_0) = h_0$, and $f$ being just a rotation of SHA512 has the same cryptographic properties. $\endgroup$ – Prateek Jun 22 at 13:29
  • $\begingroup$ I would not call these as a cryptographyic hash function since one cannot explain the final constant modulo addition to the community. $\endgroup$ – kelalaka Jun 22 at 14:01
  • $\begingroup$ The pre-image definition is not correct. In pre-image attack, given a hash value $h$, the attacker tries to find a pre-image $x$ such that $\operatorname{Hash}(x)=h$. The $x$ can be the original input value or not. $\endgroup$ – kelalaka Jun 22 at 15:59
  • $\begingroup$ @kelalaka: "I would not call these as a cryptographyic hash function since one cannot explain the final constant modulo addition to the community" - I thought the definition of "cryptographical hash function" was that it satisfied a series of security properties, not that it had the approval of any specific group of people... $\endgroup$ – poncho Jun 22 at 17:14
  • $\begingroup$ Well, practically, yes so that one can design one with the required property. Let's publish a hash function $h=SHA512(x\mathbin\|0xF7\ldots 9A$. The first question will be why does one add $0xF7\ldots 9A$, and the answer is... Also, none of the MD and Sponge algorithms are proven to be satisfied with these. The reverse is true since MD5 and SHA-1 collisions attacks. $\endgroup$ – kelalaka Jun 22 at 17:38
-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$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Sure, what about any other algorithms ? $\endgroup$ – Mostafa Torbjørn Berg Sep 12 '14 at 10:24
  • 7
    $\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
  • 3
    $\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
  • 3
    $\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.

| improve this answer | |
$\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.