8

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$ ?

fgrieu
  • 140,762
  • 12
  • 307
  • 587
Ian MathWiz
  • 505
  • 3
  • 11

1 Answers1

12

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.

fgrieu
  • 140,762
  • 12
  • 307
  • 587
  • 8
    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? – John Coleman Feb 20 '18 at 22:05
  • 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. – Ian MathWiz Feb 20 '18 at 23:57
  • 1
    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. – Luis Casillas Feb 21 '18 at 00:04