Partial-Message Collisions on Iterated Hash Functions

Question

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?

Answer 1

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