Eliminating finalize step

There is a sneaky sneaky attack i just see in the scheme with sender-generated receiver’s nonce, and receiver-generated receiver’s partial excess. I have not seen yet an instance of the attack where it is possible to steal money, so the post can be seen as a bit of zoology on potential subtilities arising from these new schemes removing the need of a final 3rd step to build transactions. Edit: it is actually possible to steal money using the attack. Left as an exercise : )

The attack:

If an attacker could send to the same receiving party two different transactions with the same excess signature’s message:

In that case we get the following two equations:
s_1 = x_1 + b + Hash(m).sk_1
s_2 = x_2 + b + Hash(m).sk_2
Subtracting the last equation from the first one:
s_1 - s_2 - (x_1 - x_2) = Hash(m).(sk_1 - sk_2).
It means that sk_1 - sk_2 = (s_1 - s_2 - (x_1 - x_2)).Hash(m)^(-1).
So, it simply says the sender can learn the value of sk_1 - sk_2.

While knowing the value of Hash(m_1).sk_1 - Hash(m_2).sk_2 is not a problem and does not lead to an attack, learning the value of sk_1 - sk_2 can be a problem in Mimblewimble.

Why does this lead to a problem?

sk_1 + receiver_offset_1 = sum(r_1), where sum(r_1) is the sum of the blinding factors of the receiver’s outputs in first transaction. Similarly sk_2 + receiver_offset_2 = sum(r_2), where sum(r_2) is the sum of the blinding factors of the receiver’s outputs in second transaction.

so we have that sk_1 + receiver_offset_1 - (sk_2 + receiver_offset_2) = sum(r_1) - sum(r_2). Other way to put it, denoting z = sk_1 - sk_2, known by the sender as we mentioned earlier, we have:
z + receiver_offset_1 - receiver_offset_2 = sum(r_1) - sum(r_2).
But receiver_offset_1 and receiver_offset_2 can be learnt by the sender when the two transactions are broadcasted. It means that the receiver can learn sum(r_1) - sum(r_2), and yes, this is dangerous.

Indeed, it means that the attacker could basically use the tx outputs of the second transaction as transacttion’s inputs of a malicious tx he would do, and use the tx outputs of the first transaction as the transaction outputs of this malicious transaction (he can copy paste the bulletproofs), because he can recreate a valid mimblewimble balance equation, without the will of the owner of these outputs. He could do this malicious transaction without the need to use a previous kernel or kernel excess. He could just build a brand new kernel for the malicious transaction, with the knowledge of z = sk_1 - sk_2.

What can be done to prevent this?

The source of this attack arises from the fact that the two excesses of the two txs have a same signature’s message.

Two same signature’s messages means in particular that R = R_a + R_b is the same in both transactions. Denote the nonce appearing in the second transaction: R' = R'_a + R'_b.

R = R' means:
R_a + x.G + B = R'_a + x'.G + B. Which implies (the B cancelling out) r_a + x = r'_a + x'.
Unfortunately, this does not imply that x = x' since the sender could create x' first, with x' != x, and then compute r'_a so that r_a + x = r'_a + x'. This is something we want to fix, because we want a way so that the receiver can notice when the sender is trying the attack, a.k.a, using the same R in the two txs, and thus we want that the attacker must use x' = x in order to have R' = R. And then, the receiver can notice through examining the pre-image of x and comparing with what he got before to check if he is being attacked or not.

In my post earlier, I proposed x = Hash(c||B||tx_amount||timestamp). This needs to be modified to commit to the sender’s public nonce as well; we rather define x with the following formula:

x = Hash(c||B||R_a||tx_amount||timestamp).

Now, it means that the sender has to choose his private partial nonce first; before actually creating the x. if r'_a != r_a is fixed, finding x' such as r_a + x = r'_a + x' now reduces to finding a hash collision, which is considered impossible with Sha256.

It means that with that new definition of x (committing to R_a), the sender will have no choice but to choose r'_a = r_a (i.e, R'_a = R_a) in order to get R' = R. He must also choose x' = x, which implies R_b = R'_b = x.G + B, and in turn, R' = R (because R'_a = R_a).

With that new definition of x, we have just provided a way to ensure that R' = R implies x = x', which is striclty equivalent to: "x != x' implies R != R'".

Then, it suffices that the receiver verifies that he always receives different timestamp in each of his transactions to be sure that none of excess’s signatures messages provided by the sender are a duplicate.

To sum up, we recommand to rather define x as:
x = Hash(c||B||R_a||tx_amount||timestamp),
and to require checking timestamp uniqueness when receiving transactions. Those two things prevent the attack.

3 Likes