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

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

• Hint: The xor can be described as system of linear equations modulo 2. – CodesInChaos Jun 4 '17 at 15:48
• Related: Forgery attack on OCB – CodesInChaos Jun 4 '17 at 15:52
• One thing that jumps out at me is that Wagner's algorithm can be used to find collisions, but this doesn't feel like the sort of answer that a homework assignment would have. – Andrew Poelstra Jun 4 '17 at 16:13
• About: 'Forgery attack on OCB' the xor is after hashing, not before. So i think it isn't similar.. Wagner's algorithm is certainly too much :) – dujil Jun 4 '17 at 16:26
• @CodesInChaos: you want to give an answer? I would, except you beat me to it... To dujil; you can find preimages in $O(n^3)$ time, where $n$ is the size of the hash in bits, if you approach the problem the right way... – poncho Jun 4 '17 at 17:36

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

• i'm not sure why the first equation will ever have solution. If I got it right, the vector b baisicly choose what vectors to include in the xor operation (put the vectors as cols in a matrix A, and solve Ab=T (mod 2) ). It's definitely an overkill answer for this question, but looks interesting to know why it works :) – dujil Jun 5 '17 at 8:31

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

• I actually thought about that, but the concatenated i actually complicate that complexity of finding a collision. That because attacker actually need to find a collision that satisfy a condition: the message must end with the number i (we know what it is at the time of the attack - we choose what block to collide with) – dujil Jun 4 '17 at 17:11
• I'm not sure of what you mean. I think my answer shows that if an attacker has a way of finding collisions (either by brute force, or with a smarter algorithm), it is easier to find a collision if you use the "block-hash", as he can attack k messages instead of only one. – richard Jun 4 '17 at 18:08
• richard: let's say we have two blocks m_0, m_1 , so we need to find m' such that hash(m' || 0) == hash(m_0 || 0) OR hash(m' || 1) == hash(m_1 || 1) . the concatenation complicates things, and as far as I can tell the complexity to find collision as above may be even bigger than finding a collision wihout concatenation (hash(m_1) vs hash(m_1 || 1)). Am I missing something? – dujil Jun 4 '17 at 18:15
• @dujil : I'm sorry I thought the definition of the h_i was h_i = hash(m_i) I missed the "||i". – richard Jun 4 '17 at 22:31
• it's ok. actually without the i, we can do worse things like adding any we want block twice... – dujil Jun 5 '17 at 8:31