5
$\begingroup$

I was thinking about the old question regarding the existence of fixed points in hash functions (for instance, if we restrict the domain of MD5 to $S = \{0, 1\}^{128}$, making it a mapping $S \to S$, then is there an element $s \in S.~MD5(s) = s$?). Of course, a simple probabilistic argument indicates that the existence of such an element is likely, but as far as I know, there is no clear proof of the existence of such a fixed point.

Then I recalled Poincare's recurrence theorem in ergodic theory, which basically states that iterations of a well-behaving transformation brings almost every point in the space to near where it started, given sufficient time. So I'm just wondering whether there has ever been some connections between results along that branch of math and the study of hash functions? For instance, something saying that "a certain hash function, given enough time, will always bring any $s$ to $\{s': d(s, s') < \delta\}$ where $d$ is some metric on the value space"? Of course, Poincare's theorem would probably not directly apply here, but some weaker version, with additional simplifications on the hash functions, may bring about something interesting?

Additional thoughts on this and/or reference to related literature would be much appreciated. Thanks.

$\endgroup$
  • 1
    $\begingroup$ Interesting question! On top of my mind, if a (cryptographic) hash function maps a point of domain to a point in its range within distance $\delta$, it can be easily inverted: Given $y$ in the range, exhaustively search for all $x$'s in the domain, such that $d(x,y)<\delta$. This idea works fine as long as $\delta$ is sufficiently small. Therefore, I believe that for a (cryptographic) hash function, even a weak version of Poincare's recurrence theorem (as stated above) should hold at most for a negligible fraction of the domain $S$. $\endgroup$ – M.S. Dousti May 18 '13 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.