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$ ?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Closely related: If you hashed a hash an infinite number of times would you end up with a unique hash? $\endgroup$– Gilles 'SO- stop being evil'Commented Aug 9, 2019 at 16:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
8$\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$ Commented Feb 20, 2018 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$ Commented Feb 20, 2018 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$ Commented Feb 21, 2018 at 0:04