1
$\begingroup$

In Cryptography Engineering by Ferguson et al it says the following is a problem with iterated hash functions:

Because hashing $m$ and $m'$ leads to the same value, $h(m||X) = h(m'||X)$... for all values for $X$.

I don't see at all how this follows from $h$ being iterated? If some general input $x$ is preprocessed into $x_1...x_t$ then $h(x) = H_t = f(H_{t-1},x_t)$ where $f$ is the compression function. Now, if $m,m'$ both have lengths that are multiples of the block size then the assertion certainly is true, as follows:

Suppose $m = m_1...m_s$, $m' = m'_1...m'_t$ and $h(m)=h(m')$, i.e. $$H_s = f(H_{s-1},m_s) = f(H'_{t-1},m'_t) = H'_t$$ Assuming for simplicity that $X$ is preprocessed into a single block (also denoted by $X$), we get $$h(m||X) = f(H_s,X) = f(H'_t,X) = h(m'||X)$$ All in good order. But suppose now that $h(m)=h(m')$ but $m||X$ and $m'$ are preprocessed into single blocks $M$ and $m'$ resp, so that $m'||X$ is preprocessed into two blocks (denote the preprocssed $X$ by $X$ yet again). We then get $$h(m||X) = f(H_0,M)$$ $$h(m'||X) = f(H_1,X) = f(f(H_0,m'))$$

How does it follow simply from $h$ being iterated that the two are equal?

$\endgroup$

1 Answer 1

1
$\begingroup$

If you go through what Ferguson said, I'm sure he'll include a condition that $m$ and $m'$ are the same length, which is also a multiple of the hash block size. In this case, $m||X$ and $m'||X$ will not be preprocessed into single blocks; instead, they'll be processed as (at least) two blocks; one being $m$ (or $m'$), and the rest consisting only of $X$.

What's crucial is that the state of the hash function after processing $m$ and $m'$ are the same. Because the state is the only way the hash function 'remembers' what came before, it'll do the same thing in both cases when processing $X$; hence $h(m || X) = h(m' || X)$

$\endgroup$
1
  • $\begingroup$ No, that would be the preceding section on length extension attacks, this is something else. It might be as you say but then my golly are the writers sloppy. $\endgroup$ Apr 1, 2016 at 21:23

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.