[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
  1. 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.

  2. sipa cross-referenced this on Sep 28, 2015 from issue [Schnorr API BREAK] Improve Schnorr multisigning API + refactoring by sipa
  3. sipa force-pushed on Oct 25, 2015
  4. sipa force-pushed on Oct 25, 2015
  5. sipa force-pushed on Oct 30, 2015
  6. sipa force-pushed on Oct 31, 2015
  7. sipa force-pushed on Nov 1, 2015
  8. sipa commented at 10:27 pm on November 1, 2015: contributor
    Rebased, and added several guarantee-zeroed-output cases. Ping @gmaxwell
  9. sipa force-pushed on Nov 25, 2015
  10. sipa cross-referenced this on Nov 25, 2015 from issue [SCHNORR BREAK] Use quadratic-residue-y as symmetry breaker by sipa
  11. in include/secp256k1_schnorr.h: 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.
  12. in src/modules/schnorr/schnorr_impl.h: 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.
  13. in src/modules/schnorr/schnorr_impl.h: 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.
  14. sipa force-pushed on Dec 12, 2015
  15. sipa commented at 8:41 pm on December 12, 2015: contributor
    Addressed nits.
  16. sipa force-pushed on Dec 13, 2015
  17. [Schnorr API change] Schnorr multisigning API overhaul 33f1913ab2
  18. Move schnorr documentation to markdown document 968e2f415a
  19. sipa force-pushed on Dec 15, 2015
  20. 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.
  21. sipa cross-referenced this on Feb 2, 2016 from issue Key tree signatures by sipa
  22. sipa commented at 7:58 pm on February 16, 2016: contributor
    @apoelstra Subtle ping
  23. fanatid commented at 2:50 pm on April 20, 2016: contributor

    @sipa can you explain Verification (method 1)?

     0x - private key, k - private nonce
 1m - 32 byte message, Q - public key, signature pair - (R.x, s)
 2
 3signing:
 4R = G^k
 5e = SHA256(R.x || m)
 6s = k - e * x
 7signature is (R.x, s)
 8
 9verify:
10e = SHA256(R.x || m)
11R' = 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:

    0R' = G^(x * e) * G^(k - e * x) = G^(x * e + k - e * x) = G^k
  24. 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

  25. fanatid commented at 3:30 pm on April 20, 2016: contributor
    @sipa thank you! I really forgot that EC multiplication is repeated addition.
  26. in src/modules/schnorr/schnorr.md: 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) ?
  27. in src/modules/schnorr/schnorr.md: 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) ?
  28. sipa commented at 1:56 pm on June 29, 2016: contributor
    Going to do this differently.
  29. sipa closed this on Jun 29, 2016
  30. 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:

  31. 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.
  33. businessintegrator commented at 6:28 pm on January 23, 2018: none
    What about collision period of the H function?


sipa apoelstra fanatid prusnak ysangkok businessintegrator

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin-core/secp256k1. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-12-23 03:15 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me