This should fix #753.
Used @peterdettman’s solution here for the ECMULT_CONST_TABLE_GET_GE #753 (comment)
and in ecdsa_sign I initialize s and r to a zero scalar.
The second commit adds a valgrind check to the cmovs that could’ve caught this (in ecdsa_sign, not in ecmult_const because there’s a scalar clear there under VERIFY_SETUP)
24@@ -25,7 +25,11 @@
25 VERIFY_CHECK((n) <= ((1 << ((w)-1)) - 1)); \
26 VERIFY_SETUP(secp256k1_fe_clear(&(r)->x)); \
27 VERIFY_SETUP(secp256k1_fe_clear(&(r)->y)); \
28- for (m = 0; m < ECMULT_TABLE_SIZE(w); m++) { \
29+ /* Unconditionally ser r->x = (pre)[m].x. r->y = (pre)[m].y. because it's either the correct one \
0 /* Unconditionally set r->x = (pre)[m].x. r->y = (pre)[m].y, because it's either the correct one \
124@@ -125,10 +125,10 @@ static void secp256k1_fe_to_storage(secp256k1_fe_storage *r, const secp256k1_fe
125 /** Convert a field element back from the storage type. */
126 static void secp256k1_fe_from_storage(secp256k1_fe *r, const secp256k1_fe_storage *a);
127
128-/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. */
129+/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. both *r and *a must be initialized.*/
0/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/
same in the other files
124@@ -125,10 +125,10 @@ static void secp256k1_fe_to_storage(secp256k1_fe_storage *r, const secp256k1_fe
125 /** Convert a field element back from the storage type. */
126 static void secp256k1_fe_from_storage(secp256k1_fe *r, const secp256k1_fe_storage *a);
127
128-/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. */
129+/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. both *r and *a must be initialized.*/
130 static void secp256k1_fe_storage_cmov(secp256k1_fe_storage *r, const secp256k1_fe_storage *a, int flag);
131
132-/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. */
133+/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. both *r and *a must be initialized.*/
0/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. Both *r and *a must be initialized.*/
9@@ -10,6 +10,10 @@
10 #include "util.h"
11 #include "field.h"
12
13+#if defined(VALGRIND)
VERIFY here. (Same in the other files)
ACK expect nits.
I think the valgrind checks need some more Concept ACKs because this is “new tooling” in some sense. I think they’re really a good idea here because it’s somewhat unexpected that cmov functions will read their target.
I think the valgrind checks need some more Concept ACKs because this is “new tooling” in some sense. I think they’re really a good idea here because it’s somewhat unexpected that cmov functions will read their target.
Ah yes, it seems that gcc 10 will just warn us here.I get warnings only for the ecdsa_sign function and no for ecmult_const, with ecdh enabled. But since valgrind does not help for ecmult_const, it’s maybe simpler not to include the valgrind checks. I don’t have strong opinions here. Either way is okay with me.
I think this is a grey area in the specification, see https://queue.acm.org/detail.cfm?id=3041020 (in C89 it’s probably even less clear), because uintXX_t cannot have trap representations. The only question is whether just using an unspecified value on itself is UB, which seems up for debate.
Concept ACK on the changes for an abundance of caution.
I’m not convinced about the additional Valgrind check, because this seems to be outside of the scope of what Valgrind is even supposed to check (even without the additional check, it passing means there is no non-constant time behaviour; whether it’s not triggering any other kind of UB beyond that seems more a job for sanitizers, who understand the source code).
Ah yes, it seems that gcc 10 will just warn us here.I get warnings only for the
ecdsa_signfunction and no forecmult_const, with ecdh enabled.
Do you get those warnings consistently? and on what parts of the code? I only got once on the low_impl implementation
I think this is a grey area in the specification, see https://queue.acm.org/detail.cfm?id=3041020 (in C89 it’s probably even less clear), because uintXX_t cannot have trap representations. The only question is whether just using an unspecified value on itself is UB, which seems up for debate.
I must say I wrote down a long post arguing that I do think it’s UB and I think compilers (especially llvm/clang) are really harsh on uninitialized values but then I came across this thread: (after long discussions in the #llvm irc channel) https://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20180528/556592.html So you’re right, this isn’t clear at all.
I’m not convinced about the additional Valgrind check
I’m not either, it was just the only test I could come up with to catch this in the future, but I can drop that commit if there’s no consensus about it.
I’m not convinced about the additional Valgrind check, because this seems to be outside of the scope of what Valgrind is even supposed to check (even without the additional check, it passing means there is no non-constant time behaviour; whether it’s not triggering any other kind of UB beyond that seems more a job for sanitizers, who understand the source code).
I don’t think it’s outside the scope of what valgrind is supposed to check. Valgrind tracks uninitialized memory (on a binary level, not on a C abstract machine level). It does not complain about the existence of uninitialized value, it complains if the externally visible behaviour of your binary depends on uninitialized values (e.g., if a branch depends on it, which valgrind always counts as observable.) This is not the case here as we discussed in #753.
But because valgrind tracks uninitialized memory, you can ask valgrind explicitly to check if a given piece of memory is defined, and that’s what we’re doing here.
So that the check here passed is not related to the code being constant time (because it’s not about a branch).
I’m not either, it was just the only test I could come up with to catch this in the future, but I can drop that commit if there’s no consensus about it.
Yes, shall we get the first commit merged if the second is debatable?
ACK a39c2b09de304b8f24716b59219ae37c2538c242 (the first commit)
I’d be fine with the second commit too. It would have prevented what’s clearly maybe (sic) an issue.
With gcc 10.1.0 I’m only getting warnings (reliably) in scalar_low_impl (called from ecdsa_sign) and therefore no warnings if compiled without exhaustive tests.
r here.
FYI, this new valgrind check won’t even run under the valgrind ctime test because it’s guarded under VERIFY which isn’t set for the ctime test.
It seems rather pointless then?
It seems rather pointless then?
The point is that valgrind ./tests and/or valgrind ./exhuastive_tests will catch this.
Ok, Concept ACK.
I think it’s a bit ugly to have #ifdef VALGRIND all over the place, though.
Perhaps the VG_UNDEF/VG_CHECK macros from tests.c can be moved to util.h, so these checks can be just #ifdef VERIFY. Alternatively, there could be a VG_CHECK_VERIFY that is only defined when VERIFY is set even.