Infinity handling: ecmult_const(infinity) works, and group verification #1299

1. 
   sipa commented at 4:51 pm on May 9, 2023: contributor

   Rebase of #791.

   • 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.
   • Add group verification (secp256k1_ge_verify and secp256k1_gej_verify, mimicking secp256k1_fe_verify).
   • Make the secp256k1_{fe,ge,gej}_verify functions also defined (as no-ops) in non-VERIFY mode.
2. sipa marked this as ready for review on May 9, 2023
3. sipa cross-referenced this on May 9, 2023 from issue Cleaner infinity handling in group law and ecmult_const. by gmaxwell
4. sipa force-pushed on May 9, 2023
5. sipa force-pushed on May 9, 2023
6. real-or-random approved
7. 
   real-or-random commented at 5:28 pm on May 9, 2023: contributor

   ACK 2d3b35077f98bea0a136b7cabd7592dd3b246827
8. in src/group_impl.h:220 in 2d3b35077f outdated

   215@@ -166,7 +216,10 @@ static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a
   216     for (i = 0; i < len; i++) {
   217         if (!a[i].infinity) {
   218             secp256k1_ge_set_gej_zinv(&r[i], &a[i], &r[i].x);
   219+        } else {
   220+            secp256k1_ge_set_infinity(&r[i]);
   

   ---

   ---

   

   jonasnick commented at 8:34 am on May 10, 2023:

   Isn’t that redundant with secp256k1_ge_set_infinity(&r[i]); at the start of the function?

   ---

   

   sipa commented at 1:25 pm on May 10, 2023:

   It is. Dropped the change.
9. in src/group_impl.h:259 in 148197cb75 outdated

   254                 secp256k1_fe_mul(&zs, &zs, &zr[i]);
   255             }
   256             i--;
   257+#ifdef VERIFY
   258+            secp256k1_ge_verify(&a[i]);
   259+#endif
   

   ---

   ---

   

   jonasnick commented at 8:37 am on May 10, 2023:

   didn’t we already verify zr and a at the start of the function?

   ---

   

   sipa commented at 1:09 pm on May 10, 2023:

   Only zr[len - 1] and a[len - 1] are verified at the start; the others are verified here.

   ---

   

   sipa commented at 1:25 pm on May 10, 2023:

   Simplified a bit, and added more comments.
10. 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 A
    (the input point). It never was constant time in Q (and would be a little
    complicated to make constant time in A).
    
    If it was later made constant time in A, infinity support would be easy
    to preserve, e.g. by running it on a dummy value and cmoving infinity into
    the output.

    a0e696fd4d
11. Expose secp256k1_fe_verify to other modules 3086cb90ac
12. Always initialize output coordinates in secp256k1_ge_set_gej a18821d5b1
13. Add invariant checking to group elements f20266722a
14. Make secp256k1_{fe,ge,gej}_verify work as no-op if non-VERIFY 0a2e0b2ae4
15. Avoid secp256k1_ge_set_gej_zinv with uninitialized z bbc834467c
16. sipa force-pushed on May 10, 2023
17. 
    jonasnick commented at 4:34 pm on May 10, 2023: contributor

    ACK bbc834467c5d14e3e53744211e7c4fa9d8fabe41
18. real-or-random approved
19. 
    real-or-random commented at 4:43 pm on May 10, 2023: contributor

    ACK bbc834467c5d14e3e53744211e7c4fa9d8fabe41
20. real-or-random merged this on May 10, 2023
21. real-or-random closed this on May 10, 2023

    ---

22. sipa cross-referenced this on May 10, 2023 from issue WIP Group verification by peterdettman
23. sipa cross-referenced this on May 11, 2023 from issue Abstract out and merge all the magnitude/normalized logic by sipa
24. sipa referenced this in commit b4eb644b6c on May 12, 2023
25. hebasto referenced this in commit 49c52ea2b1 on May 13, 2023
26. vmta referenced this in commit e1120c94a1 on Jun 4, 2023
27. theStack referenced this in commit 78ef599ff0 on Jun 15, 2023
28. theStack cross-referenced this on Jun 15, 2023 from issue tighten group magnitude limits, save normalize_weak calls in group add methods (revival of #1032) by theStack
29. sipa referenced this in commit 901336eee7 on Jun 21, 2023
30. theStack referenced this in commit a55902c091 on Jun 27, 2023
31. vmta referenced this in commit 8f03457eed on Jul 1, 2023
32. theStack referenced this in commit 672b1016ff on Jul 10, 2023
33. theStack referenced this in commit 0ce5892cac on Jul 14, 2023
34. theStack referenced this in commit 9b8aa9804d on Jul 14, 2023
35. theStack referenced this in commit 72aa104f28 on Jul 15, 2023
36. theStack referenced this in commit 690b0fc05a on Jul 22, 2023
37. jonasnick cross-referenced this on Jul 24, 2023 from issue Upstream PRs 1268, 1276, 1267, 1265, 1230, 1279, 1273, 1263, 1231, 1285, 1283, 1205, 1286, 1275, 1234, 1239, 1240, 1284, 1277, 1289, 1270, 1296, 1301, 1299, 1066, 1300, 1292, 1305, 1303, 1133, 1306, 1207, 1304, 1307, 1311, 1309, 1312 by jonasnick

Contributors
sipa real-or-random jonasnick