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.

YESSSSSS killing it. Digital cash here we comeâŚ

MACKER

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.

Circular definitionsâŚ

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.

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.

Thanks for sharing this.

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

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

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] https://en.wikipedia.org/wiki/Schnorr_signature

[2] https://eprint.iacr.org/2012/029.pdf

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.

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

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.

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.

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.

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

This is not really stated clearly *anywhere*, let alone wikipedia.

Thanks for laying this out explicitly here like this.

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.

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.

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.