Do 'reflexive' hash algorithms exist? Is there a class of hash algorithms, whether theoretical or practical, such that an algorithm in the class might be considered 'reflexive' according a definition given below:


hash1 = algo1 ( "input text 1" )
hash1 = algo1 ( "input text 1" + hash1 )


The + operator might be concatenation or any other specified operation to combine the output (hash1) back into the input ("input text 1") so that the algorithm (algo1) will produce exactly the same result. i.e. collision on input and input+output. The + operator must combine the entirety of both inputs and the algo may not discard part of the input.

The algorithm must produce high entropy in the output. It may, but need not, be cryptographically hard to reverse the output back to one or both possible inputs.

I am not a mathematician, but a good answer might include a proof of why such a class of algorithms cannot exist. This is not an abstract question, however. I am genuinely interested in using such an algorithm in my system, if one does exist.

This is a duplicate of a question that was first posted at https://stackoverflow.com/questions/4823680/reflexive-hash
I give a trivial construction which satisfies the requirement. I provide it to merely answer the existence of "reflexive" hash function.

Let $G$ be any hash function producing high entropy in the output. Assume that $G$ hashes arbitrary-length binary strings to $k$-bit binary strings, where $k$ is any positive integer. Let $+$ denote the concatenation operator, and let $|x|$ denote the length of the binary string $x$.

Define the hash function $H$ on input $x$ as follows:


If $|x| \le k$, then $H(x) \overset{\text{def}}{=} G(x)$.
If $|x| &gt; k$, let $L$ and $R$ be the $(|x|-k)$-bit prefix and $k$-bit suffix of $x$, respectively. That is, $x = L + R$ and $|R|=k$. If $R = H(L)$ (where $H(L)$ is computed recursively), then $H(x) \overset{\text{def}}{=} R$; otherwise, $H(x) \overset{\text{def}}{=} G(x)$.


As I said, this is a trivial construction. It can be applied to any hash function, practical (such as MD5, SHA-1, ...) or theoretical.