My thought: assume there a black box, that given a cryptographic hash function $h$, finds some $x$ and $r$ in polynomial time, such
that applying $h()$, $r$ times gives $x$: $$ h(h(h\ldots(h(x))) = x $$
I thought about this, and I found that the answer is yes. The oracle can be used to find preimages and collisions in an arbitrary function $$h : \{0,1\}^n \longrightarrow \{0,1\}^k.$$
Finding collisions
To find a collision in $h$, define function $h'$ from $h$ as
$$h'(x) =
\begin{cases}
x+1 \bmod 2^k& \quad \text{if } h(x) = x,\\
x & \quad \text{else if } h(h(x)) = h(x),\\
x+1 \bmod 2^k& \quad \text{otherwise}.
\end{cases}
$$
Querying the oracle with $h'$, it will return a cycle of length $1$ if $h$ has a collision and that it has a fixed point. If $h$ does not have a fixed point, then the oracle will return a cycle with all elements of length $2^k$. If so, the cycle structure can be re-randomized via a (efficiently computable) random permutation $\pi$ as $\pi \circ h$. Eventually, it will have a fixed point.
The oracle will (eventually) return a $1$-cycle in $h'$. From construction, we know that $h(y) \neq y$ (if so, it would not be a fixed point in $h'$). But we also know that $h(h(y)) = h(y)$. This gives collision $(h(y), y)$.
A bit more complex, but requiring no fixed points in $h$:
$$f(x\|y) =
\begin{cases}
x\|y+1 \bmod 2^k & \quad \text{if } x = y,\\
x\|y & \quad \text{else if } h(x) = h(y),\\
x\|y+1 \bmod 2^k& \quad \text{otherwise}.
\end{cases}
$$
This immediately gives collision $(x,y)$, since fixed points must have the property $x\neq y$ and $h(x) = h(y)$.
Finding preimages
In order to find a preimage $h^{-1}(A)$, we proceed in the same manner as before and create an auxilliary function as follows
$$g_A(x) =
\begin{cases}
x & \quad \text{if } h(x) = A,\\
x+1 \bmod 2^k& \quad \text{otherwise}.
\end{cases}
$$
So, when calling the oracle with $g_A$, it will return two possible results
- a cycle of length $1$, i.e., $g_A(x) = x \iff h(x) = A$,
- a cycle of length $2^k$, if $h(x) \neq A$ for all $x$.
The first one means there exists a non-empty preimage for $A$, while the second means it does not.
Decision version
If we have an oracle that we can ask if there exists a cycle of length $r$, then we can transform this to the search version. Define
$$u_{A,B}(x) =
\begin{cases}
h(x) & \quad \text{if } A \leq x \leq B,\\
x+1 \bmod 2^k& \quad \text{otherwise}.
\end{cases}
$$
Assume that we want to find a cycle of length 1. We call $\textsf{Oracle}(u_{A,B}, 1)$, with $A = 0, B = 2^k-1$. If it returns no, then there are no such cycles. Otherwise, we can conduct binary search on $A$ and $B$ to find the fixed point.
To conclude, this oracle is very strong and capable of solving any problem in NP. For instance, any 3SAT can be encoded as $h$ which returns a $1$-cycle whenever the formula is satisfied. For instance, any 3SAT can be encoded as function $h$ which returns a $1$-cycle whenever a formula $\varphi$ (in $k$ variables) is satisfied:
$$v_{\varphi}(x) =
\begin{cases}
x & \quad \text{if } \varphi(x_0,x_1,...,x_k) = 1\\
x+1 \bmod 2^k& \quad \text{otherwise}.
\end{cases}
$$
If a $1$-cycle is returned, then $x$ encodes this (possibly one out of many) solution, while if a $2^k$-cycle is returned then $\varphi$ has no satisfying solution. So, finding a cycle in an arbitrary hash function $h$ is at least as hard as 3SAT.