[Schnorr API BREAK] Improve Schnorr multisigning API + fix vulnerability #322

pull sipa wants to merge 2 commits into bitcoin-core:master from sipa:schnorrstages2 changing 6 files +598 −242

sipa commented at 7:43 PM on September 28, 2015: contributor
This reworks the Schnorr multisigning API to 4 self-contained functions:
- secp256k1_multischnorr_stage1 computes public nonces
- secp256k1_multischnorr_stage2 computes partial signatures using those public nonces
- secp256k1_multischnorr_combine_sigs combines stage2 sigs into a full signature
- secp256k1_multischnorr_combine_keys combines signers' public keys into a combined public key.
This changes the combined public key to be A*H(A) + B*H(B) + C*H(C) + ..., in an attempt to prevent a pubkey cancellation vulnerability.

The documentation is also moved out to a separate schnorr.md document.
sipa cross-referenced this on Sep 28, 2015 from issue [Schnorr API BREAK] Improve Schnorr multisigning API + refactoring by sipa
sipa force-pushed on Oct 25, 2015
sipa force-pushed on Oct 25, 2015
sipa force-pushed on Oct 30, 2015
sipa force-pushed on Oct 31, 2015
sipa force-pushed on Nov 1, 2015
sipa commented at 10:27 PM on November 1, 2015: contributor

Rebased, and added several guarantee-zeroed-output cases. Ping @gmaxwell
sipa force-pushed on Nov 25, 2015
sipa cross-referenced this on Nov 25, 2015 from issue [SCHNORR BREAK] Use quadratic-residue-y as symmetry breaker by sipa

in include/secp256k1_schnorr.h:None in 7fd00c237c outdated

 191 | - *  function take their arguments in any order, and it is possible to
 192 | - *  pre-combine several inputs already with one call, and add more inputs later
 193 | - *  by calling the function again (they are commutative and associative).
 194 | + *  All cosigners must use the same msg32, and the same as in stage1. You must
 195 | + *  also use the same noncefp/ndata for your own stage1 and stage2. Other
 196 | + *  participants may use different nonce generation, though.

apoelstra commented at 11:32 PM on November 28, 2015:

I think you should be more explicit: "Different participants may use different nonce generating functions and data, as long as they are each consistent between stage 1 and stage 2."

Up to you.

Edit Oh, you say this in the first sentence. So I think replace "You" with "Each participant" and "Other" with "Different" then.

sipa commented at 8:40 PM on December 12, 2015:

Fixed. Used your language.

in src/modules/schnorr/schnorr_impl.h:None in 7fd00c237c outdated
```
  73 | +        return 0;
  74 | +    }
  75 | +    return secp256k1_ge_set_xo_var(p, &x, 0);
  76 | +}
  77 | +
  78 | +/** Computes {priv = +/- (scalar)b32; pub = priv * G } with pub.y even. */
```
apoelstra commented at 11:40 PM on November 28, 2015:

pub = priv * G + pubothers

sipa commented at 8:40 PM on December 12, 2015:

It's more complicated even. Fixed.
in src/modules/schnorr/schnorr_impl.h:None in 7fd00c237c outdated
```
  86 | +        secp256k1_scalar_clear(priv);
  87 | +        return 0;
  88 | +    }
  89 | +    secp256k1_ecmult_gen(ctx, &gej, priv);
  90 | +    if (secp256k1_gej_is_infinity(&gej)) {
  91 | +        return 0;
```
apoelstra commented at 11:43 PM on November 28, 2015:

Can this branch be hit? If priv is zero the above check gets it; if priv is n (or higher) then overflow should be set and the above check gets it.

sipa commented at 8:40 PM on December 12, 2015:

Replaced with VERIFY_CHECK.
sipa force-pushed on Dec 12, 2015
sipa commented at 8:41 PM on December 12, 2015: contributor

Addressed nits.
sipa force-pushed on Dec 13, 2015
[Schnorr API change] Schnorr multisigning API overhaul 33f1913ab2
Move schnorr documentation to markdown document 968e2f415a
sipa force-pushed on Dec 15, 2015
apoelstra commented at 7:24 PM on January 14, 2016: contributor

Hi, sorry for the delays, this fell off my radar. Will review today while in flight.
sipa cross-referenced this on Feb 2, 2016 from issue Key tree signatures by sipa
sipa commented at 7:58 PM on February 16, 2016: contributor

@apoelstra Subtle ping

fanatid commented at 2:50 PM on April 20, 2016: contributor

@sipa can you explain Verification (method 1)?

x - private key, k - private nonce
m - 32 byte message, Q - public key, signature pair - (R.x, s)

signing:
R = G^k
e = SHA256(R.x || m)
s = k - e * x
signature is (R.x, s)

verify:
e = SHA256(R.x || m)
R' = Q^e + G^s = G^(x * e) + G^(k - e * x) = ???

How G^(x * e) + G^(k - e * x) can be equal to R = G^k? if instead + will be * all be ok:

R' = G^(x * e) * G^(k - e * x) = G^(x * e + k - e * x) = G^k

sipa commented at 3:17 PM on April 20, 2016: contributor

@fanatid I think you're confusing additive notation with multiplicative notation.

We call the EC group operation +, and its repeated application a number of times *, so when a + b = c, then c*G = (a+b)*G = a*G + b*G
fanatid commented at 3:30 PM on April 20, 2016: contributor

@sipa thank you! I really forgot that EC multiplication is repeated addition.

in src/modules/schnorr/schnorr.md:None in 968e2f415a

 122 | +
 123 | +Steps:
 124 | +* Check whether all `R_all(j).x` values in each of the stage 2 signature are
 125 | +  identical. If not, fail.
 126 | +* Compute the sum `s_all` of all `s(j)` values.
 127 | +* The full combined signature is `(R_all.x, s(i))`.

fanatid commented at 3:52 PM on April 20, 2016:

(R_all.x, s_all) ?

in src/modules/schnorr/schnorr.md:None in 968e2f415a

 109 | +* Compute the sum `R_all(i)` of all the `R(j)` points, including your own
 110 | +  `R(i)`.
 111 | +* If `R_all.y` is odd, negate `k(i)` and `R_all(i)`.
 112 | +* Compute scalar `e = SHA256(R_all(i).x || m)`. If `e == 0` or `e >= order`,
 113 | +  fail.
 114 | +* Compute scalar `s(i) = k(i) - e * x`.

fanatid commented at 3:52 PM on April 20, 2016:

s(i) = k(i) - e * x(i) ?

sipa commented at 1:56 PM on June 29, 2016: contributor

Going to do this differently.
sipa closed this on Jun 29, 2016
prusnak commented at 2:40 PM on March 23, 2017: none
Going to do this differently.

Is there a source where I can learn how this is being done today?

Also not sure if helpful, but I found a working two-stage cosigning implementation for ed25519 in Go:
- https://godoc.org/github.com/bford/golang-x-crypto/ed25519/cosi
- https://github.com/bford/golang-x-crypto/tree/master/ed25519/cosi
sipa commented at 9:18 PM on March 23, 2017: contributor

@prusnak In review we discovered the AH(A) + BH(B) + ... scheme was vulnerable to a generalized birthday attack. We have a new scheme, but no strong proof for security yet. I didn't know about CoSi - I'll have a look at it.
ysangkok commented at 2:26 PM on January 5, 2018: none

@prusnak more details here: https://github.com/kanzure/diyhpluswiki/blob/master/transcripts/bitcoin-core-dev-tech/2017-09-06-signature-aggregation.mdwn
businessintegrator commented at 6:28 PM on January 23, 2018: none

What about collision period of the H function?

Contributors

Linked (view graph)

#318 [Schnorr API BREAK] Improve Schnorr multisigning API + refactoring #359 [SCHNORR BREAK] Use quadratic-residue-y as symmetry breaker