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

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.

• I've upvoted the question, but I don't see what the increase of hash iterations has to do with the problem of breaking a hash instruction regarding the internal rounds. As best, the amount of iterations will make it harder to let an adversary enter a specific input to the (second & later) hash operations to perform an attack. And if the input of the iterated hash is a secret (HMAC, HKDF or PBKDF) then the attack becomes much harder as you'd need a pre-image rather than collision attack (which you've asked for). Aug 8 at 17:08

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