10
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ Related: Associative hash mixing $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 28, 2011 at 1:56
  • 2
    $\begingroup$ Are you interested in this property holding for all input text or for one input text? If you want it to hold for all input text then constructing collisions is trivial by design so I don't think it can be considered a good hash function. $\endgroup$
    – Peter Taylor
    Commented Jan 28, 2011 at 8:20
  • $\begingroup$ Somebody wants to hash files that contain their own hashes! ;) $\endgroup$
    – Raphael
    Commented Jan 28, 2011 at 9:05
  • $\begingroup$ @Peter Taylor - I am looking for a function which works as described for arbitrary input text. Each different input produces a hash which in general has high mutual entropy to every other possible input. Much as a good irreversible hash function works. However, the hash function I am looking for does not need to have the property of irreversibility. High entropy is sufficient. $\endgroup$
    – user3494
    Commented Jan 28, 2011 at 19:29
  • $\begingroup$ @Raphael - Yep, that's a succinct way of putting it. $\endgroup$
    – user3494
    Commented Jan 28, 2011 at 19:30

1 Answer 1

Reset to default
9
$\begingroup$

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:

  1. If $|x| \le k$, then $H(x) \overset{\text{def}}{=} G(x)$.
  2. If $|x| > 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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I am not very sure-footed in the realms of encodings, but does $H$ still have high entropy? By construction, it certainly has the same hash for double as many strings as before. And they come in pairs that are very close to each other. (Oh, it should be $|R|=k$ in the second line of 2.) $\endgroup$
    – Raphael
    Commented Jan 29, 2011 at 17:16
  • $\begingroup$ @Raphael: Thanks for pointing out the typo (corrected). H has the same entropy as G, unless in the condition where R=G(L). By requirement, in this condition, H(x) should equal R. We can't do anything here to increase the entropy; since the "reflexivity" requirement prevents us from altering the output. $\endgroup$
    – Sadeq Dousti
    Commented Jan 29, 2011 at 18:50
  • $\begingroup$ @Sadeq: Is it required that the hash function to be computed recursively? I the algorithm benefiting from this fact in any way? $\endgroup$
    – Yasser Sobhdel
    Commented Jan 30, 2011 at 18:42
  • $\begingroup$ @Yasser: If you take a look at the history of the question, you'll notice that my first reply didn't require the recursion. However, the former answer was not correct for the case of computing something like: $H(M+H(M)+H(M)+\ldots+H(M))$ which should be $H(M)$ by definition. $\endgroup$
    – Sadeq Dousti
    Commented Jan 30, 2011 at 20:08
  • $\begingroup$ Sadeq, thank you. I believe this may answer my question, as it was asked. You have couched the answer in a suitable caveat. From a pragmatic point of view, I like the fact that it's an overlay for any well-known algorithm such as SHA-1. If I have understood correctly, your algorithm will continue to compute hashes recursively until it hits the required collision and then it stops. In which case perhaps we can dub this the naive solution. My concern is there seems to be an implicit assumption that the embedded algorithm (SHA-1 say) will eventually hit the required collision hash, given an $\endgroup$
    – user3535
    Commented Feb 15, 2011 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.