2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – Maarten Bodewes
    Aug 8, 2023 at 17:08

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.