6
$\begingroup$

For example, if $H$ is a secure cryptographic hash function, is it infeasible to find $x$ such that $H(x)=x$ or such that $H(H(x))=x$ ?

What about finding $x, y$, and $z$ such that $H(y||H(z||x))=x$ ?

$\endgroup$
11
$\begingroup$

No, preimage-resistance or/and collision-resistance do not imply the infeasibility of finding fixed points in hash functions.

For example, define $H(x)=\begin{cases}0^{256}&\text{if }x=0^{256}\\\operatorname{SHA-256}(x)&\text{otherwise.}\end{cases}$

This function is just as preimage-resistant and collision-resistant as SHA-256 is, yet it holds that $H(x)=x$ and $H(H(x))=x$ for $x=0^{256}$.

Exhibiting a preimage-resistant and collision-resistant $H$, and matching $(x,y,z)$ such that $H(y\|H(z\|x))=x$, is almost as easy and is left as an exercise to the reader.


Per comment: a good general purpose cryptographic hash function is essentially a random function, and wide, with no special case like in the above counterexamples. We have no efficient algorithm to exhibit a fixed point (if there is one, which has probability $1-1/e\approx63\%$) for such functions. Essentially, we must compute the function at $O(2^k)$ points where $k$ is the width. Therefore, there can't be a good general purpose cryptographic hash with a known fixed point. And that extends to all general purpose cryptographic hashes that I know, including those which collision-resistance or preimage-resistance is seriously broken.

$\endgroup$
  • 7
    $\begingroup$ This nicely answers the question (+1) but in some ways isn't the most satisfying of examples. Is there an example of a secure hash function which wasn't designed with having a stipulated fixed point in mind which nevertheless has a fixed point which can be feasibly found? Looked at another way, if someone were to come up with a fixed point for SHA-256 itself, would that cause you to question its security? $\endgroup$ – John Coleman Feb 20 '18 at 22:05
  • $\begingroup$ Interesting. So it seems that it's not collision or preimage resistance that makes finding fixed points infeasible, but the random oracle nature of a hash function. $\endgroup$ – Ian MathWiz Feb 20 '18 at 23:57
  • 1
    $\begingroup$ Regarding the edit prompted by @JohnColeman's comment: we know of ways in which standard hash function constructions depart from random functions, and yet we do not consider these breaks. For example, length extensions with Merkle-Damgård, and inner collisions in sponges (although the latter are at least generically hard). Perhaps one way to reformulate John's question is whether a hash function construction with efficiently computable fixpoints would be practically worse than one vulnerable to extensions like M-D. $\endgroup$ – Luis Casillas Feb 21 '18 at 0:04

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.