Cleaner infinity handling in group law and ecmult_const. #791

pull gmaxwell wants to merge 5 commits into bitcoin-core:master from gmaxwell:202008_clearinfinity changing 9 files +113 −18
  1. gmaxwell commented at 3:59 am on August 8, 2020: contributor

    Clean up infinity handling, make x/y/z always initialized for infinity.

    Make secp256k1_ecmult_const handle infinity.

    Infinity isn’t currently needed here, but correctly handling it is a little more safe against future changes.

    Update docs for it to make it clear that it is not constant time in Q. It never was constant time in Q (and would be a little complicated to make constant time in Q: needs a constant time addition function that tracks RZR). It isn’t typical for ECDH to be constant time in terms of the pubkey.

    If it was later made constant time in Q infinity support would be easy to preserve, e.g. by running it on a dummy value and cmoving infinity into the output.

  2. gmaxwell commented at 3:59 am on August 8, 2020: contributor
    The second commit is an alternative to #789.
  3. elichai commented at 11:32 am on August 8, 2020: contributor

    Verified that indeed it isn’t constant time on the point:

     0==2047291== Memcheck, a memory error detector
 1==2047291== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
 2==2047291== Using Valgrind-3.16.1 and LibVEX; rerun with -h for copyright info
 3==2047291== Command: /home/elichai2/gits/secp256k12/.libs/lt-valgrind_ctime_test
 4==2047291== 
 5==2047291== Conditional jump or move depends on uninitialised value(s)
 6==2047291==    at 0x484E271: secp256k1_pubkey_load (secp256k1.c:254)
 7==2047291==    by 0x4856353: secp256k1_ecdh (main_impl.h:47)
 8==2047291==    by 0x1096B7: main (valgrind_ctime_test.c:74)
 9==2047291== 
10==2047291== Conditional jump or move depends on uninitialised value(s)
11==2047291==    at 0x4849B69: secp256k1_fe_normalizes_to_zero_var (field_5x52_impl.h:206)
12==2047291==    by 0x4851F1B: secp256k1_gej_add_ge_var (group_impl.h:445)
13==2047291==    by 0x4852541: secp256k1_ecmult_odd_multiples_table.constprop.0 (ecmult_impl.h:122)
14==2047291==    by 0x4856721: secp256k1_ecmult_odd_multiples_table_globalz_windowa (ecmult_impl.h:152)
15==2047291==    by 0x4856721: secp256k1_ecmult_const (ecmult_const_impl.h:178)
16==2047291==    by 0x4856721: secp256k1_ecdh (main_impl.h:53)
17==2047291==    by 0x1096B7: main (valgrind_ctime_test.c:74)
18==2047291== 
19==2047291== Conditional jump or move depends on uninitialised value(s)
20==2047291==    at 0x4849B7B: secp256k1_fe_normalizes_to_zero_var (field_5x52_impl.h:206)
21==2047291==    by 0x4851F1B: secp256k1_gej_add_ge_var (group_impl.h:445)
22==2047291==    by 0x4852541: secp256k1_ecmult_odd_multiples_table.constprop.0 (ecmult_impl.h:122)
23==2047291==    by 0x4856721: secp256k1_ecmult_odd_multiples_table_globalz_windowa (ecmult_impl.h:152)
24==2047291==    by 0x4856721: secp256k1_ecmult_const (ecmult_const_impl.h:178)
25==2047291==    by 0x4856721: secp256k1_ecdh (main_impl.h:53)
26==2047291==    by 0x1096B7: main (valgrind_ctime_test.c:74)
27==2047291== 
28==2047291== 
29==2047291== HEAP SUMMARY:
30==2047291==     in use at exit: 0 bytes in 0 blocks
31==2047291==   total heap usage: 1 allocs, 1 frees, 224 bytes allocated
32==2047291== 
33==2047291== All heap blocks were freed -- no leaks are possible
34==2047291== 
35==2047291== Use --track-origins=yes to see where uninitialised values come from
36==2047291== For lists of detected and suppressed errors, rerun with: -s
37==2047291== ERROR SUMMARY: 15 errors from 3 contexts (suppressed: 0 from 0)
  4. LLFourn cross-referenced this on Aug 8, 2020 from issue ecmult implementation is not constant time on the point by LLFourn
  5. gmaxwell commented at 11:33 pm on August 8, 2020: contributor
    Can someone with access please kick travis to clear the spurious failure?
  6. sipa commented at 11:47 pm on August 8, 2020: contributor

    Can someone with access please kick travis to clear the spurious failure?

    Done.

  7. sipa commented at 11:32 pm on August 9, 2020: contributor
    It seems s390x doesn’t really work; I think we need to disable it again unfortunately. See #794.
  8. gmaxwell commented at 2:36 am on August 10, 2020: contributor
    I’ll rebase when 794 is merged.
  9. sipa commented at 10:33 pm on August 10, 2020: contributor

    utACK 6e712dcdc71f08672d8f243174051a000c85268f

    Seems s390x is green again; let’s hope it stays that way.

  10. gmaxwell commented at 2:57 am on August 11, 2020: contributor

    Okay, then this doesn’t need to be rebased.

    Unsurprisingly, no gross performance loss, FWIW:

    Before: ecdsa_verify: min 54.9us / avg 54.9us / max 54.9us ecdh: min 65.6us / avg 65.7us / max 65.8us After: ecdsa_verify: min 54.9us / avg 55.0us / max 55.1us ecdh: min 65.6us / avg 65.7us / max 65.8us

    I think that tiny difference is real but it might be compiler alignment noise.

  11. real-or-random commented at 9:17 am on August 11, 2020: contributor
    In the first commit, both modified functions currently have VERIFY_CHECK(!a->infinity); lines.
  12. gmaxwell commented at 11:14 am on August 11, 2020: contributor
    Yep. I didn’t intend to change their infinity-handling-ness beyond making them less wrong. (for the second function too, making those handle infinities would be non-trivial)
  13. in src/ecmult_const_impl.h:156 in 6e712dcdc7 outdated 
    151@@ -152,6 +152,10 @@ static void secp256k1_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, cons
152 
153     /* build wnaf representation for q. */
154     int rsize = size;
155+    if (secp256k1_ge_is_infinity(a)) {
156+      secp256k1_gej_set_infinity(r);
157+      return;
158+    }
    LLFourn commented at 2:50 am on August 13, 2020:
    I think this fix can also be applied to ecmult for the a argument. Just replacing it with an ecmult_gen in the case that a is infinity. Otherwise the check here fails: https://github.com/bitcoin-core/secp256k1/blob/master/src/ecmult_impl.h#L102
    gmaxwell commented at 4:09 am on August 13, 2020:

    ecmult_gen isn’t necessarily available to ecmult, as it requires a signing context and also would be a non-trivial code-size increase for something that was validation only.

    0        if (secp256k1_scalar_is_zero(&na[np]) || secp256k1_gej_is_infinity(&a[np])) {
1            continue;
2        }

    should be skipping the input if its an infinity.

    LLFourn commented at 5:41 am on August 13, 2020:
    Ah sorry I missed that. I was mistakenly projecting what happens in the rust parity code base onto this.
    real-or-random commented at 2:18 pm on September 9, 2020:
    nit: Indentation
  14. LLFourn cross-referenced this on Aug 13, 2020 from issue Test Check multiplying by infinity returns infinity by LLFourn
  15. real-or-random commented at 11:12 am on August 13, 2020: contributor

    Yep. I didn’t intend to change their infinity-handling-ness beyond making them less wrong. (for the second function too, making those handle infinities would be non-trivial)

    Yeah okay, I suspect that the fix is not that easy but I didn’t bother to understand the code when I wrote the comment.

    But then, this seems to me like a little code smell to do VERIFY_CHECK(!a->infinity); but then use that value.

    Okay, so… It anyway does not make a lot to for this functions to support infinity but maybe it’s a good idea to add an additional comment to the doc header that a must not be infinity.

  16. jonasnick commented at 9:23 am on August 23, 2020: contributor

    make x/y/z always initialized for infinity.

    That z implies this is for gej only?

  17. gmaxwell commented at 9:03 pm on August 29, 2020: contributor
    @jonasnick What non-gej-outputting function are you thinking of?
  18. gmaxwell commented at 9:21 pm on August 29, 2020: contributor
    Rebased and added a comment that secp256k1_ecmult_odd_multiples_table’s a argument cannot be infinity.
  19. sipa commented at 1:19 am on September 2, 2020: contributor
    As it seems this should be adding a strict invariant that ge/gej objects always have sane coordinates, I added checks for that in VERIFY mode: https://github.com/sipa/secp256k1/commits/202009_pr791. There was one place where this is violated (secp256k1_ge_set_gej_var with infinity input didn’t initialize the output ge coordinates), which I added a fix for. Feel free to cherry-pick the commits, or I can do it afterwards in another PR.
  20. gmaxwell commented at 3:39 am on September 2, 2020: contributor

    Your branch needs a patch along the lines of

     0diff --git a/src/group_impl.h b/src/group_impl.h
 1index 950b51d..b8ed209 100644
 2--- a/src/group_impl.h
 3+++ b/src/group_impl.h
 4@@ -197,6 +197,8 @@ static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a
 5         r[i].infinity = a[i].infinity;
 6         if (!a[i].infinity) {
 7             secp256k1_ge_set_gej_zinv(&r[i], &a[i], &r[i].x);
 8+        } else {
 9+            secp256k1_ge_set_infinity(&r[i]);
10         }
11         secp256k1_ge_verify(&r[i]);
12     }

    or the tests call ge_verify on incompletely initialized elements.

  21. sipa commented at 3:51 am on September 2, 2020: contributor

    Fixed. The

    0r[i].infinity = a[i].infinity;

    line above can be removed now.

  22. real-or-random commented at 10:11 am on September 2, 2020: contributor
    If we want to initialize the coords here in the set functions, then we also want them in the add functions, see #699.
  23. sipa cross-referenced this on Sep 2, 2020 from issue Initialize field elements when resulting in infinity by elichai
  24. sipa commented at 6:04 pm on September 2, 2020: contributor

    @real-or-random Good to point that out, the changes here not enough to guarantee that field elements in ge/gej are always initialized, and I wonder why the tests don’t catch that.

    If we’re going in the direction of actually enforcing that invariant, we should make both changes.

  25. jonasnick commented at 8:04 pm on September 2, 2020: contributor

    @jonasnick What non-gej-outputting function are you thinking of?

    Was thinking of ge_set_gej_var but looks like that’s fixed now. Ideally we’d clarify the commit message Clean up infinity handling, make x/y/z always initialized for infinity. because without the follow up commits this does not seem to be true.

  26. sipa commented at 3:41 am on September 9, 2020: contributor

    ACK 49a59a115be3cfa9666c6575b52455754e69cc4b (+ my own commits, up to 95d8d92f5d576f2e36d01148bf9d61e37976e969).

    Should be combined with #699 to deal with the exceptional branches in add functions (which can still leave output coordinates uninitialized otherwise). It can be cleanly merged with this.

  27. in src/group_impl.h:243 in 95d8d92f5d outdated 
    249 static void secp256k1_gej_clear(secp256k1_gej *r) {
250     r->infinity = 0;
251     secp256k1_fe_clear(&r->x);
252     secp256k1_fe_clear(&r->y);
253     secp256k1_fe_clear(&r->z);
254+    secp256k1_gej_verify(r);
    real-or-random commented at 2:16 pm on September 9, 2020:
    nit: I believe this is conceptually wrong. The purpose of the clear function is nuke the contents of the element, so those functions are not supposed to uphold any invariants. But it doesn’t matter for this PR, I can clean this up in #636 .
    sipa commented at 4:51 pm on September 9, 2020:
    Agree.
    sipa commented at 3:24 am on October 27, 2020:
    This got lost in rebase as well.
  28. real-or-random approved
  29. real-or-random commented at 2:21 pm on September 9, 2020: contributor

    ACK https://github.com/bitcoin-core/secp256k1/pull/791/commits/95d8d92f5d576f2e36d01148bf9d61e37976e969 diff looks good, tests pass

    Let’s address these nits somewhere else.

  30. real-or-random commented at 9:38 am on September 13, 2020: contributor
    I think after this PR (and #814) we initialize group elements fully everywhere, and we could introduce VG_CHECKs for this.
  31. sipa commented at 7:06 pm on September 13, 2020: contributor
    Yeah, there could be VG_CHECKs in secp256k1_{fe,ge,gej}_verify after this and #814.
  32. elichai commented at 9:12 am on September 14, 2020: contributor
    ACK 95d8d92f5d576f2e36d01148bf9d61e37976e969 the diff looks correct and reasonable idk how I feel about moving the VERIFY ifdef from the secp256k1_*_verify functions to their content, but I guess it makes the code smaller and cleaner (less ifdefs all over), and the comment clearly says it’s a no-op on non VERIFY builds.
  33. sipa commented at 10:09 pm on October 5, 2020: contributor
    A rebased version of this PR, with @real-or-random’s nit above addressed is here: https://github.com/sipa/secp256k1/commits/202009_pr791
  34. gmaxwell commented at 3:28 am on October 6, 2020: contributor
    I switched this to sipa’s rebase.
  35. sipa cross-referenced this on Oct 10, 2020 from issue Rip out non-endomorphism code by sipa
  36. jonasnick commented at 9:16 am on October 23, 2020: contributor
    This seems to be ready for merge but needs rebase.
  37. real-or-random commented at 10:22 am on October 23, 2020: contributor

    This seems to be ready for merge but needs rebase.

    Oh sorry, we should just have merged this earlier, I think we had the ACKs. :/

  38. Clean up infinity handling, make x/y/z always initialized for infinity. 18644909c9
  39. Make secp256k1_ecmult_const handle infinity. 
    Infinity isn't currently needed here, but correctly handling it is a
 little more safe against future changes.

Update docs for it to make it clear that it is not constant time in Q.
 It never was constant time in Q (and would be a little complicated
 to make constant time in Q).

If it was later made constant time in Q infinity support would be easy
 to preserve, e.g. by running it on a dummy value and cmoving infinity
 into the output.
    020094ec1e
  40. Expose secp256k1_fe_verify to other modules 
    Also define it even when VERIFY is not set (as a no-op), to avoid
conditions when calling it.
    c8739ee12a
  41. Always initialize output coordinates in ge_set_[all_]gej_var e5f1b88a4e
  42. Add invariant checking to group elements 666d210542
  43. in src/ecmult_const_impl.h:154 in 666d210542 
    149@@ -150,6 +150,10 @@ static void secp256k1_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, cons
150 
151     /* build wnaf representation for q. */
152     int rsize = size;
153+    if (secp256k1_ge_is_infinity(a)) {
154+      secp256k1_gej_set_infinity(r);
    sipa commented at 3:23 am on October 27, 2020:
    I believe this got lost in rebase: wrong indentation
  44. in src/group_impl.h:250 in 666d210542 
    245 
246 static void secp256k1_ge_clear(secp256k1_ge *r) {
247     r->infinity = 0;
248     secp256k1_fe_clear(&r->x);
249     secp256k1_fe_clear(&r->y);
250+    secp256k1_ge_verify(r);
    sipa commented at 3:24 am on October 27, 2020:
    This too.
  45. sipa commented at 3:25 am on October 27, 2020: contributor
    re-ACK by verifying against rebasing myself, but a few small improvements got lost.
  46. real-or-random commented at 11:39 am on June 10, 2021: contributor
    needs rebase
  47. real-or-random cross-referenced this on Jun 10, 2021 from issue Valgrind errors with struct assignment on ARM and PPC64LE by gmaxwell
  48. sipa cross-referenced this on May 9, 2023 from issue Infinity handling: ecmult_const(infinity) works, and group verification by sipa
  49. sipa commented at 4:51 pm on May 9, 2023: contributor
    Rebased as #1299.
  50. sipa closed this on May 9, 2023
  51. real-or-random referenced this in commit 341cc19726 on May 10, 2023


gmaxwell elichai sipa real-or-random LLFourn jonasnick

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