Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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 http://stackoverflow.com/questions/4823680/reflexive-hash

share|improve this question
    
Related: Associative hash mixing –  Tsuyoshi Ito Jan 28 '11 at 1:56
2  
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. –  Peter Taylor Jan 28 '11 at 8:20
    
Somebody wants to hash files that contain their own hashes! ;) –  Raphael Jan 28 '11 at 9:05
    
@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. –  user3494 Jan 28 '11 at 19:29
    
@Raphael - Yep, that's a succinct way of putting it. –  user3494 Jan 28 '11 at 19:30
show 1 more comment

1 Answer

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.

share|improve this answer
    
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.) –  Raphael Jan 29 '11 at 17:16
    
@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. –  Sadeq Dousti Jan 29 '11 at 18:50
    
@Sadeq: Is it required that the hash function to be computed recursively? I the algorithm benefiting from this fact in any way? –  Yasser Sobhdel Jan 30 '11 at 18:42
    
@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. –  Sadeq Dousti Jan 30 '11 at 20:08
    
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 –  user3535 Feb 15 '11 at 17:16
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.