4
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Hint: The xor can be described as system of linear equations modulo 2. $\endgroup$ – CodesInChaos Jun 4 '17 at 15:48
  • $\begingroup$ Related: Forgery attack on OCB $\endgroup$ – CodesInChaos Jun 4 '17 at 15:52
  • $\begingroup$ 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. $\endgroup$ – Andrew Poelstra Jun 4 '17 at 16:13
  • $\begingroup$ 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 :) $\endgroup$ – dujil Jun 4 '17 at 16:26
  • $\begingroup$ @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... $\endgroup$ – poncho Jun 4 '17 at 17:36
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 :) $\endgroup$ – dujil Jun 5 '17 at 8:31
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – dujil Jun 4 '17 at 17:11
  • $\begingroup$ 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. $\endgroup$ – richard Jun 4 '17 at 18:08
  • $\begingroup$ 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? $\endgroup$ – dujil Jun 4 '17 at 18:15
  • $\begingroup$ @dujil : I'm sorry I thought the definition of the h_i was h_i = hash(m_i) I missed the "||i". $\endgroup$ – richard Jun 4 '17 at 22:31
  • 1
    $\begingroup$ it's ok. actually without the i, we can do worse things like adding any we want block twice... $\endgroup$ – dujil Jun 5 '17 at 8:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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