Cleaner infinity handling in group law and ecmult_const.

[gmaxwell]

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.

[gmaxwell]

The second commit is an alternative to #789.

[elichai]

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

==2047291== Memcheck, a memory error detector
==2047291== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2047291== Using Valgrind-3.16.1 and LibVEX; rerun with -h for copyright info
==2047291== Command: /home/elichai2/gits/secp256k12/.libs/lt-valgrind_ctime_test
==2047291== 
==2047291== Conditional jump or move depends on uninitialised value(s)
==2047291==    at 0x484E271: secp256k1_pubkey_load (secp256k1.c:254)
==2047291==    by 0x4856353: secp256k1_ecdh (main_impl.h:47)
==2047291==    by 0x1096B7: main (valgrind_ctime_test.c:74)
==2047291== 
==2047291== Conditional jump or move depends on uninitialised value(s)
==2047291==    at 0x4849B69: secp256k1_fe_normalizes_to_zero_var (field_5x52_impl.h:206)
==2047291==    by 0x4851F1B: secp256k1_gej_add_ge_var (group_impl.h:445)
==2047291==    by 0x4852541: secp256k1_ecmult_odd_multiples_table.constprop.0 (ecmult_impl.h:122)
==2047291==    by 0x4856721: secp256k1_ecmult_odd_multiples_table_globalz_windowa (ecmult_impl.h:152)
==2047291==    by 0x4856721: secp256k1_ecmult_const (ecmult_const_impl.h:178)
==2047291==    by 0x4856721: secp256k1_ecdh (main_impl.h:53)
==2047291==    by 0x1096B7: main (valgrind_ctime_test.c:74)
==2047291== 
==2047291== Conditional jump or move depends on uninitialised value(s)
==2047291==    at 0x4849B7B: secp256k1_fe_normalizes_to_zero_var (field_5x52_impl.h:206)
==2047291==    by 0x4851F1B: secp256k1_gej_add_ge_var (group_impl.h:445)
==2047291==    by 0x4852541: secp256k1_ecmult_odd_multiples_table.constprop.0 (ecmult_impl.h:122)
==2047291==    by 0x4856721: secp256k1_ecmult_odd_multiples_table_globalz_windowa (ecmult_impl.h:152)
==2047291==    by 0x4856721: secp256k1_ecmult_const (ecmult_const_impl.h:178)
==2047291==    by 0x4856721: secp256k1_ecdh (main_impl.h:53)
==2047291==    by 0x1096B7: main (valgrind_ctime_test.c:74)
==2047291== 
==2047291== 
==2047291== HEAP SUMMARY:
==2047291==     in use at exit: 0 bytes in 0 blocks
==2047291==   total heap usage: 1 allocs, 1 frees, 224 bytes allocated
==2047291== 
==2047291== All heap blocks were freed -- no leaks are possible
==2047291== 
==2047291== Use --track-origins=yes to see where uninitialised values come from
==2047291== For lists of detected and suppressed errors, rerun with: -s
==2047291== ERROR SUMMARY: 15 errors from 3 contexts (suppressed: 0 from 0)

[gmaxwell]

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

[sipa]

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

Done.

[sipa]

It seems s390x doesn't really work; I think we need to disable it again unfortunately. See #794.

[gmaxwell]

I'll rebase when 794 is merged.

[sipa]

utACK 6e712dcdc71f08672d8f243174051a000c85268f

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

[gmaxwell]

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.

[real-or-random]

In the first commit, both modified functions currently have VERIFY_CHECK(!a->infinity); lines.

[gmaxwell]

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)

[real-or-random]

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.

[gmaxwell]

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

[gmaxwell]

Rebased and added a comment that secp256k1_ecmult_odd_multiples_table's a argument cannot be infinity.

[sipa]

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.

[gmaxwell]

Your branch needs a patch along the lines of

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

or the tests call ge_verify on incompletely initialized elements.

[sipa]

Fixed. The

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

line above can be removed now.

[real-or-random]

If we want to initialize the coords here in the set functions, then we also want them in the add functions, see #699.

[sipa]

@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.

[jonasnick]

@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.

[sipa]

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.

[real-or-random]

I think after this PR (and #814) we initialize group elements fully everywhere, and we could introduce VG_CHECKs for this.

[sipa]

Yeah, there could be VG_CHECKs in secp256k1_{fe,ge,gej}_verify after this and #814.

[elichai]

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.

[sipa]

A rebased version of this PR, with @real-or-random's nit above addressed is here: https://github.com/sipa/secp256k1/commits/202009_pr791

[gmaxwell]

I switched this to sipa's rebase.

[jonasnick]

This seems to be ready for merge but needs rebase.

[real-or-random]

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. :/

[real-or-random]

needs rebase