Is hash function cryptanalysis the same or more difficult for iterated hashing, as H(H(H(H(H))))?

Question

The effectiveness of hash function attacks is typically measured in $x$ broken rounds of $N$ total designed rounds. And some constructs containing iterated hash functions include proof of work schemes, blockchains and key derivation functions. Constructs like $H^i(...)$.

What is the predicted effect on $x$ as $i$ increases? Or simply, can we still break $x$ rounds of $H$ no matter how many times it's iterated within one construct?

In terms of "the problem of breaking a hash instruction regarding the internal rounds", I see the iteration as a chain. And we know that a chain's strength lies within it's weakest link, not the number of links. Is the whole chain then only $x \text{ of } N$ strong as each link is, or does each link (iteration) reinforce each other and strengthen the whole chain?

I've seen Does the double-hash H(H(x)) have greater collision probability than H(x)?, but I'm not quite sure it fits this question accurately.

Answer 1

Or simply, can we still break $x$ rounds of $H$ no matter how many times it's iterated within one construct?

Largely, yes; let's go through the various security assumptions:

• If we are breaking collision resistance, then yes, it is the same level of effort.

What we do is simply find a collision $H(a) = H(b)$. We then have $H^i(a) = H^i(b)$

And, conversely, if we have a method for finding collisions in $H^i$, we can easily use that to find collisions in $H$, so those two problems have the same complexity.

• If we are breaking second preimage resistance, then yes, it is (at most) the same level of effort (with some probability of failure).

If we are looking for a second preimage of $H^i(a)$, what we can do is look for a second preimage of $H(a)$ (given the preimage $a$). If we find $H(a) = H(b)$, then we also have $H^i(a) = H^i(b)$, hence solving the problem. The probability of failure: $H(a)$ might not have a second preimage.

• If we are breaking preimage resistance, then it is (with some handwaving) circa $i$ times harder (which isn't that much).

We can try the obvious, given the image $a$, we first look for an $H$ preimage $H(b_1) = a$; once we find that, we then look for a preimage of that $H(b_2) = b_1$ (which implies $H^2(b_2) = a$. We iterate that $i$ times, obtaining $H^i(b_i) = a$, which is our preimage.

The fly in the ointment? Like the previous case, we might end up trying to find a preimage that doesn't exist; if that's the case, we would need to back up and search for a second preimage - I'm not sure how to model that (and that doesn't even address the case that there isn't a preimage of $a$ to the function $H^i$...