Eliminating finalize step

[Kurt]

Of course, I am certain it is impossible that a wallet prevents from re-signing 32,000 times a same key and then send the 32,000 nonces to the other co-signers.

[Macker]

@Kurt

by adding a third round to prevent the Wagner’s attack and relief a (uniqueness) check burdon from the user is that solution 1. makes striclty no sense at all .

YESSSSSS killing it. Digital cash here we come…

MACKER

[Macker]

[Kurt]

I want to describe another attack on the scheme, which is fixable with a slight modification of the protocol.

EDIT: As tromp points out below, I did a mistake in this attack and the below is not correct.

The attack:

Party A does a first legit transaction to party B. s_A: partial signature of the sender, s_B: partial signature of the receiver.
s_B = x + b + Hash(m).x_B.
with x = Hash(R_a, B, amount, timestamp).
Total nonce R is R = R_a + B + x.G.
Then, s = s_A + s_B is a valid signature on total excess X for total nonce R. Up to here, everything is fine.

But later Party A can replay the transaction without the participation of party B with using a different x (call it x’) on a different partial nonce R’_a:
R’_a = R_a - x’.G + x.G.
x’ = Hash(R’_a, B, amount’, timestamp’),

s = s_A + s_B is in fact a valid signature on excess X for total nonce R’ = R’_a + (B + x’.G).
But one can notice that R’ = R, which means the message of the first signature can be replayed with using R’_a as sender’s address and x’ as the “payment proof part” of the receiver’s nonce.

Use amount’ = $1,000,000 in x’ and party A is able to prove that he paid $1,000,000 to party B without party B participating.

In initial proposal, we had:
R_b = x.G + B.

Fix: replace by
R_b = x.G + x.B.

That way, party A would have to use an adjusted nonce R’_a for the second transaction equal to:
R’_a = R_a - x’.G + x.G - x’.b + x.b
But he would not know the private key of this R’_a because he does not the value of b.

Hence party A will not be able to provide correct payment proof for the second transaction as a correct payment proof requires a proof of knowledge of the private key to sender’s nonce.

Of course the fix is only necessary if solution 1. (put burden on user and wallet devs) is chosen. If nonce uniqueness at consensus level is chosen one can keep R_b = x.G + B since the attack relies on using the same total nonce.

[tromp]

@Kurt

R’_a = R_a - x’.G + x.G.
x’ = Hash(R’_a, B, amount’, timestamp’),

Circular definitions…

[Kurt]

You’re right, indeed.

I guess that’s why I notified the importance of committing to R_a in x in an earlier post in this thread.

[david]

@antioch

tl;dr Sharing the public nonce prior to committing to the message to be signed may be a bad idea.

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

Solution:
Left as an exercise for the reader.

[lehnberg]

Thanks for sharing this.

An uninformed question: Would this apply to the scheme proposed here as well? Integrated Payment Proofs and Round Minimization

[tromp]

@david

and uses k*G + x*H as the pub nonce.

As Kurt explained, they also use a new e = Hash(M | k*G+ x*H) then.

[Kurt]

@david

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

Yeah, I am either missing something big, but this seems to work, and this would just be a plain attack against the Schnorr scheme without committing to the public key, which is weird because the scheme is documented everywhere [1] and proven secure [2].

General case: You choose R = kG + A where A is some curve point.
You compute e = Hash(R,m)
You choose X = xG - e^(-1)A.
You give (s,R) as your signature where s = k + e.x and X as the public key.

R + e.X = kG + A + e.(xG - e^(-1)A) = kG + e.x.G = (k + e.x).G = s.G.

Verification: We indeed have s.G = R + e.X.

I have also tried with the alternative version of Schnorr signature, where, instead of providing (s,R) as the signature, the signer instead provides (s,e). (And then the verifier computes R' = sG - e.X and verifies that e' = Hash(R',m) = e). The attack seems to also work.

Probably something I am missing, I don’t know : )

[1] Schnorr signature - Wikipedia
[2] https://eprint.iacr.org/2012/029.pdf

[tromp]

I think the references assume a known public key X that can sign different messages, not an ephemeral X that is dependent on the nonce in a single signature.

The problem is that Grin public excesses are rather ephemeral…

Wikipedia is also a little sloppy in not explaining what exactly should be included in the hash of the Fiat-Shamir transform. It should be the history of all messages exchanged up to that point in the protocol. Which for Schnorr signatures ought to include the public key X.

[valdo]

Yes, exactly! This is the difference.
This seems really confusing at first. But this is the difference.

“Traditionally” when you sign a message - it is assumed that the verifier already knows you by your pubkey, and you only approve the message.

In MW, however, the pubkey is random, and you must prove both: the message, AND the fact that your pubkey is indeed of the form sk*H

[Kurt]

Yes, indeed maybe.

I always assumed this scheme without committing to the public key was valid under the “Plain public key model”, which is a model where you don’t need to assume that X is of the form x.G, for some x. I guess this variation indeed just does not apply in the “plain public key model”.

Fortunately, the variation that we currently use in Grin (where e also commits to the public key X) is secure under this model, and this attack does not apply.

But yeah, unfortunately, it seems clear that we cannot apply the variation e=Hash(R,m) blindly.
Maybe there is a fix (for eliminating last step) to this by committing to the sender’s partial public key, but it would require to have the two partial public keys in the kernel, adding 33 byttes to each kernel.
I don’t even know if it would work, will try to think more about it.

[valdo]

If you re-read the security proof of the Schnorr’s signature (the ‘extractor’ technique, what-if you answer on different challenges), you can see that it assumes the the pubkey must be constant.

So it’s either known in advance, or included in the message.

[tromp]

Yes, it applies to that scheme, which assumes that not committing to the public key only suffers from malleability. Now we see it suffers much worse. I added an UPDATE message in that post to reflect the new insight.

[antioch]

The further we go down this path the less and less these actually look and behave like signatures (known public key signing multiple messages etc.)

[antioch]

@tromp

Wikipedia is also a little sloppy in not explaining what exactly should be included in the hash of the Fiat-Shamir transform. It should be the history of all messages exchanged up to that point in the protocol.

This is not really stated clearly anywhere, let alone wikipedia.
Thanks for laying this out explicitly here like this.

[Kurt]

@Kurt

by committing to the sender’s partial public key

This would not work, since there is enough freedom to do the same attack using the non-committed public key. Rather:

• 1 signature on the sender’s partial nonce
• 1 signature on the receiver’s partial nonce

would prevent this attack. But around + 5 x 32 bytes of data per kernel.

Let’s try to remain optimist, we’ll maybe find a scalable fix if we continue to search.

Actually, it would be likely more secure to do these two signatures on each of the partial excesses since both of them are generated randomly, unlike the receiver’s partial nonce which has to be deterministically generated. You also gain excess’s non-malleability.

[Kurt]

I think I found a potential solution to the attack with adding only 33 bytes (one curve point) to the kernels. It will be a long post to explain and justify, and i know everyone would love including me that we keep our kernels the same size, so let me know if it worth I take the time to describe and explain in details the proposal in a thread tomorrow.

[david]

Verification requirements are a bigger deal than 33 bytes in the kernel. Does this scheme just require an extra point addition? If so, I’m personally on board, but that doesn’t mean much.