Why is a hash of blocks - with index - weaker than hashing the entire thing?

Question

Let's say we want to sign message $M$ with RSA using a safe hash function. However, instead of signing $\operatorname{hash}(M)$, We split the message into 64-bit blocks (|| is concatenation):

$$M = {m_0}||{m_1}||{m_2}||{m_3}\,...$$

For each block we calculate:

$${h_i} = \operatorname{hash}({m_i}||i)$$

and then we calculate the total hash:

$$h = {h_1} \oplus {h_2} \oplus {h_3}\,...$$

and sign $h$ with RSA instead of $\operatorname{hash}(M)$.

Why is it weaker than signing $\operatorname{hash}(M)$?

I know that the order of the blocks cannot be modified because of the concatenation of $i$, and that I cannot add the same block twice because of that too.

I think the answer involves collision, birthday or brute-force attack which may be faster than performing those attacks against $\operatorname{hash}(M)$ but couldn't show that. Any ideas?

P.S: Homework question - hint is enough :)

Answer 1

Ok, here's a hint as to why this construct has essentially no cryptographical strength.

By using Gaussian Elimination, we can solve the below problem in $O(n^3)$ time (that is, very fast):

• Given a target value $T$ and $n$ values $v_1, v_2, ..., v_n$ what bit vector $b_1, b_2, ..., b_n$ makes this happen:

$$\bigoplus_{i=1}^n b_i \cdot v_i = T$$

where $\cdot$ is multiplication (so $0 \cdot v_i = $ and $1 \cdot v_i = v_i$), and $\bigoplus$ is the exclusive-or.

If we were given a value $S$, how can the above observation be used to craft a message, that, when hashed by the method in question, generates the value $S$?

Further hint: suppose we were to arbitrarily select $n$ pairs of messages blocks $(m_1, m'_1)$, $(m_2, m'_2)$..., $(m_n, m'_n)$, and we set:

$u_i = Hash(m_i||i)$

$v_i = Hash(m_i||i) \oplus Hash(m'_i||i)$

$T = S \oplus \bigoplus_{i=1}^n u_i$

And we use Gaussian Elimination to find the bit vector $b_1, ... b_n$ with:

$$\bigoplus_{i=1}^n b_i \cdot v_i = T$$

How can we use the $v_i$ values to directly deduce the message that hashes to $S$?

(Practical note: often, there will be no such bit vector that satisfies the equation; this can be handled by including a few extra message block pairs (and hence $v_i$ values).

Answer 2

One simple reason that immediately springs to my mind is the following:

If an attacker wants to find a collision of your hash function and you have hashed the entire message $M$, the attacker needs to find another message $M'$ such that $hash(M) = hash(M')$. so, roughly speaking, we can say the attacker has only one possibility, in the sense that he can only find a collision on the string $hash(M)$

Now, if instead you use the "blocks technique", say you divide the message $M$ in $k$ blocks, so $M = m_1||m_2||...||m_k$, you hash block by block, and define $h = hash(m_1) \oplus hash(m_2)\oplus ...\oplus hash(m_k)$. An attacker has now $k$ possibilities of finding a collision, because it is sufficient for him to find a collision for one of the $k$ strings $hash(h_i)$: let's say he finds a collision for the string $hash(m_2)$, i.e. he finds a message $y$ such that $hash(m_2)=hash(y)$. He can than create $M' = m_1||y||m_3||...||m_k$ which would have the same "block-hash" of $M$.