Is the last step of an iterated cryptographic hash still as resistant to preimage attacks as the original hash?

Question

Considering a cryptographic hash, such as MD5 or SHA2, denoted by the function $H(m)$ where $m$ is an arbitrary binary string, there is a lot of material available that deals with potential weakness to preimage attack. I am interested in resistance to preimage attack where the cryptographic hash is applied recursively a number of times.

A classical first-preimage attack asks to determine a message $m$ for a given hash $h$ such that $h=H(m)$.

A related question considers a known value for $H(H(m))$ and asks if $H(m)$ can be determined more easily than $m$ from $H(m)$. The extension asks if $H^{(n+1)}(m)$ is more vulnerable to preimage attacks to determine $H^n(m)$ than it is to first preimage attacks... and, if resistance deteriorates as $n$ increases, how many times can $H(·)$ be applied while it is safe to remain confident the last application of $H(·)$ remains non-invertible - i.e. how many times is it safe to chain this non-invertible function without significantly weakening its resistance to inversion?

I'm also interested to establish if different hashes have different strengths relative to this scenario of repeated application.

Answer 1

If the hash function is any good, then it should behave as a "random function" (i.e. a function chosen randomly and uniformly among all possible functions). For a random function with output size $n$ bits, it is expected that nested application will follow a "rho" pattern: the sequence of successive values ultimately enters a cycle with an expected size of $2^{n/2}$; and the length of the "queue" (the values before entering the cycle) should also be close to $2^{n/2}$.

So, theoretically, recursive application weakens the function with regards to preimage resistance, but the weakening is low-bounded by $2^{n/2}$, a boundary which requires an awfully big number of invocations to be reached.

Moreover, when we select a hash function, we want to have decent resistance to collisions, and collisions can be found with effort $2^{n/2}$. So we already choose hash functions such that $2^{n/2}$ is unreachable (e.g. we use SHA-256, because $2^{128}$ is far beyond what can be realistically achieved with Earth-bound technology; see this answer for a discussion on the subject). In short words, the weakening through recursive application has no practical consequence (while the time taken to compute all the hashes improves things greatly with regards to dictionary attacks).