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

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.

-

## 1 Answer

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).

-
Thanks for the answer... though there are a couple of things I'd like clarified. Do you have a reference regarding the "rho pattern"? – aSteve Sep 25 '11 at 17:11
The other issue is whether or not the real hash function "is good"... If there is any narrowing of the state space, it strikes me that there must be a finite limit to the number of times the hash function can be recursively applied before there's insufficient entropy to assure security. It also strikes me as unlikely that all (any?) hash functions are entropy preserving when applied to values of the same length as the hash. In order to establish the limit, I'd need to estimate information loss on each application... but I don't know how to go about that. – aSteve Sep 25 '11 at 17:25
– Thomas Pornin Sep 25 '11 at 23:15

1
@aSteve: the point of the rho pattern is that the "narrowing" is limited to the size of the cycle -- you cannot narrow down any further because that's a cycle. And the size of the cycle is about $2^{n/2}$. – Thomas Pornin Sep 25 '11 at 23:17

1
@aSteve: it is proven that the probability of not having a very small cycle with a random function is vanishingly small. The risks involved in that probability are negligible with regards to other unlucky events such as, e.g., getting hit by an old satellite reentering the atmosphere. The "real" issue is rather on whether a given hash function behaves like a random function. – Thomas Pornin Sep 26 '11 at 14:02
show 4 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 22, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9223375916481018, "perplexity_flag": "middle"}