Eliminating finalize step

So, sharing the nonce is not a problem, but it turns out, the scheme where we no longer commit to pub excess in the challenge string actually is vulnerable to Wagner’s attack after all. A huge thanks to Beam’s Vlad Gelfer for working this out. I’ll describe the attack now.

The proposed (insecure) signature scheme:
k = nonce, k*G = pub nonce
r = excess, r*G = pub excess
M = message
e = Hash(M | k*G)
s = k + e*r
Signature = (k*G, s)

The attack:
Rather than using k*G as the pubnonce, the attacker generates another random number, x, and uses k*G + x*H as the pub nonce. Then, he can calculate a pub excess after performing the challenge as:
pub excess = r*G - x*(e^-1)*H. He now just built a valid signature which, in addition to the excess (r), also has a value x*(e^-1).

This is still not trivial to perform in mimblewimble, since in order to build outputs with the value of x*(e^-1), the value has to fit in 64-ish bits to build a bulletproof (actually, closer to 70, because you could build say 1,000 outputs). But as it turns out, you can sum multiple kernels together so that the sum of their x*(e^-1) only has to total 70-ish bits, which Wagner’s attack tells us is much easier. Performing this attack results in undetected inflation :cry:

Solution:
Left as an exercise for the reader.

2 Likes