Modulo-reduce msg32 inside RFC6979 nonce fn to match spec. Fixes #1063 #1064

pull paulmillr wants to merge 1 commits into bitcoin-core:master from paulmillr:master changing 1 files +6 −2
  1. paulmillr commented at 1:00 am on January 15, 2022: contributor
  2. real-or-random commented at 12:18 pm on January 15, 2022: contributor

    I think it’s good to adhere to the spec.

    If we want to change this, the right way will be to change it in nonce_function_rfc6979 because the change you propose here will also affect callers who provide their custom nonce function. But that means we’ll need to do another reduction in nonce_function_rfc6979, change the nonce function API, or introduce strange special casing. Hm, I don’t know, not sure if it’s worth the hassle.

    Anyway, I think what we should do is to overhaul the ECDSA API (https://github.com/bitcoin-core/secp256k1/issues/974), and then we could provide a nice simple ECDSA function that uses a much faster nonce function than RFC6979.

  3. paulmillr commented at 3:00 pm on January 15, 2022: contributor

    Is it okay to cut a new release with the change (or an alternative similar change in nonce function)?

    Before the refactoring, which could take a long time.

    I develop secp256k1 in js and it seems like there are some assumptions in libraries that test against particular vectors e.g message > curve order. Releasing a new libsecp version would allow to have some “real” vectors to test against, since it’s considered a reference implementation.

  4. real-or-random commented at 3:13 pm on January 15, 2022: contributor

    Is it okay to cut a new release with the change (or an alternative similar change in nonce function)?

    I’d be totally fine with adding a reduction to nonce_function_rfc6979. That’s simple and the solution with the cleanest code (right now) and while it makes signing slightly slowing, you anyway can’t expect optimal performance from RFC6979 signing. How does that sound to others?

    Well, releases are a separate issue… So far we never had a release (https://github.com/bitcoin-core/secp256k1/issues/286) but there’s good progress recently (https://github.com/bitcoin-core/secp256k1/pull/1055).

  5. sipa commented at 4:43 pm on January 15, 2022: contributor

    I think we should:

    • Make nonce_function_rfc6979 do the modulo reduction, to comply with the spec.
    • We could make nonce_function_rfc6979 also reduce the output, so that it doesn’t cause a second RNG invocation if the result exceed the order. This isn’t an observable difference however, if RFC6979 is a PRF.
    • Add a new fast, sane, nonce function with the simplest possible semantics around edge cases (something based on the BIP340 nonce function, I imagine).
    • Optionally, make this new nonce function the default, but leave the rfc6979 one in place.
  6. real-or-random commented at 9:25 am on January 16, 2022: contributor

    Add a new fast, sane, nonce function with the simplest possible semantics around edge cases (something based on the BIP340 nonce function, I imagine).

    There’s some discussion around this here: #757 (comment)

  7. in src/secp256k1.c:431 in 3c5c4950e0 outdated 
    422@@ -423,6 +423,10 @@ static int nonce_function_rfc6979(unsigned char *nonce32, const unsigned char *m
423    unsigned int offset = 0;
424    secp256k1_rfc6979_hmac_sha256 rng;
425    unsigned int i;
426+   secp256k1_scalar msg;
427+   unsigned char msgmod32[32];
428+   secp256k1_scalar_set_b32(&msg, msg32, NULL);
429+   secp256k1_scalar_get_b32(msgmod32, &msg);
430    /* We feed a byte array to the PRNG as input, consisting of:
431     * - the private key (32 bytes) and message (32 bytes), see RFC 6979 3.2d.
    real-or-random commented at 9:29 am on January 16, 2022: 
    0    * - the private key (32 bytes) and reduced message (32 bytes), see RFC 6979 3.2d.
  8. real-or-random commented at 9:29 am on January 16, 2022: contributor
    Looks good, can you squash?
  9. Modulo-reduce msg32 inside RFC6979 nonce fn to match spec. Fixes #1063. 45f37b6506
  10. paulmillr commented at 2:08 am on January 17, 2022: contributor
    @real-or-random done
  11. paulmillr renamed this:
    Modulo-reduce msg32 in sign() to match RFC6979. Fixes #1063.
    Modulo-reduce msg32 inside RFC6979 nonce fn to match spec. Fixes #1063
    on Jan 17, 2022
  12. real-or-random approved
  13. real-or-random commented at 9:23 am on January 17, 2022: contributor
    ACK 45f37b650635e46865104f37baed26ef8d2cfb97
  14. siv2r commented at 6:54 pm on January 20, 2022: contributor

    ACK 45f37b6. The diff looks good. It reduces msg32 to modulo curve order for rfc6979 nonce generation. All tests passed on my machine with make check.

     0make  check-am
 1make[1]: Entering directory '/home/siv2r/Projects/secp256k1'
 2make  check-TESTS
 3make[2]: Entering directory '/home/siv2r/Projects/secp256k1'
 4make[3]: Entering directory '/home/siv2r/Projects/secp256k1'
 5PASS: tests
 6PASS: exhaustive_tests
 7============================================================================
 8Testsuite summary for libsecp256k1 0.1.0-pre
 9============================================================================
10# TOTAL: 2
11# PASS:  2
12# SKIP:  0
13# XFAIL: 0
14# FAIL:  0
15# XPASS: 0
16# ERROR: 0
17============================================================================
18make[3]: Leaving directory '/home/siv2r/Projects/secp256k1'
19make[2]: Leaving directory '/home/siv2r/Projects/secp256k1'
20make[1]: Leaving directory '/home/siv2r/Projects/secp256k1'
  15. sipa commented at 11:37 pm on January 22, 2022: contributor
    utACK 45f37b650635e46865104f37baed26ef8d2cfb97
  16. sipa merged this on Jan 22, 2022
  17. sipa closed this on Jan 22, 2022
  18. sipa commented at 5:29 pm on January 24, 2022: contributor

    Apparently this was detected to cause a divergence with the trezor firmware: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=43997

    I haven’t verified myself, but I assume it’s because they use the unreduced msghash as well.

  19. guidovranken cross-referenced this on Jan 25, 2022 from issue Trezor's RFC6979 operation diverges from that of Bitcoin core by guidovranken
  20. prusnak commented at 10:59 pm on January 25, 2022: none

    I haven’t verified myself, but I assume it’s because they use the unreduced msghash as well.

    We will address this in the upcoming PR (issue https://github.com/trezor/trezor-firmware/issues/2085)

  21. dhruv referenced this in commit 6f7e395acc on Jan 26, 2022
  22. hebasto referenced this in commit 065b6dbf9d on Jan 30, 2022
  23. dhruv referenced this in commit 139d4b881e on Feb 1, 2022
  24. fanquake referenced this in commit 8f8631d826 on Mar 17, 2022
  25. fanquake referenced this in commit 4bb1d7e62a on Mar 17, 2022
  26. fanquake referenced this in commit 465d05253a on Mar 30, 2022
  27. jonasnick cross-referenced this on Mar 30, 2022 from issue Upstream PRs 1064, 1049, 899, 1068, 1072, 1069, 1074, 1026, 1033, 748, 1079, 1088, 1090, 731, 1089, 995, 1094, 1093 by jonasnick
  28. real-or-random referenced this in commit 6c0aecf72b on Apr 1, 2022
  29. stratospher referenced this in commit 4d5afc9767 on Apr 3, 2022
  30. stratospher referenced this in commit 5b18493cfa on Apr 3, 2022
  31. fanquake referenced this in commit afb7a6fe06 on Apr 6, 2022
  32. gwillen referenced this in commit 35d6112a72 on May 25, 2022
  33. patricklodder referenced this in commit 21badcf9d2 on Jul 25, 2022
  34. patricklodder referenced this in commit 03002a9013 on Jul 28, 2022
  35. janus referenced this in commit 3a0652a777 on Aug 4, 2022
  36. str4d referenced this in commit 522190d5c3 on Apr 21, 2023
  37. vmta referenced this in commit e1120c94a1 on Jun 4, 2023
  38. vmta referenced this in commit 8f03457eed on Jul 1, 2023


paulmillr real-or-random sipa siv2r prusnak

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-22 10:15 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me