Repository: bitcoin-core/secp256k1 (c)

Issue:
Instances of operations on uninitialized values
Hi,
Currently we have 2 instances of operations on uninitialized values, in the cmov implementation.
all the `_cmov` implementations read from the resulting variable(ie `r->n[0] & mask0`) so if `r` points to uninitialized values this is undefined behavior [1] [2]
Unlike the `memcpy` debate, actual user operations and conditions on uninit values are assumed to not happen in the compiler and are used for optimizations (especially in clang)

**Instance 1:**
In ecdsa_sign, if `noncefp` returns 0 then we get to:
https://github.com/bitcoin-core/secp256k1/blob/41fc78560223aa035d9fe2cbeedb3ee632c740e2/src/secp256k1.c#L517-L518
with both `r` and `s` being unitialized. 
**Instance 2:**
In ecdh, we pass `&tmpa`  here: https://github.com/bitcoin-core/secp256k1/blob/41fc78560223aa035d9fe2cbeedb3ee632c740e2/src/ecmult_const_impl.h#L186 to the `ECMULT_CONST_TABLE_GET_GE` in an uninit state, which become the `r` value in the macro. 
Then in:
https://github.com/bitcoin-core/secp256k1/blob/41fc78560223aa035d9fe2cbeedb3ee632c740e2/src/ecmult_const_impl.h#L31-L32
 we cmov into `&(r)->x` which will perform operations on uninit values.
notice that under `VERIFY` we actually do clear those before:
https://github.com/bitcoin-core/secp256k1/blob/41fc78560223aa035d9fe2cbeedb3ee632c740e2/src/ecmult_const_impl.h#L26-L27

Possible solutions:
The only solution I can currently think of is default initializing those arguments.

Mitigations:
We could add `VALGRIND_CHECK_MEM_IS_DEFINED(r, sizeof(*r));` to all the cmovs but we only enable valgrind(`-DVALGRIND`) under tests, which use the VERIFY macro too, so that will not catch the second case.

[1] http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_451.htm
[2] https://markshroyer.com/2012/06/c-both-true-and-false/

Pull request description:
Fix uninit values passed into cmov
This should fix #753.
Used @peterdettman's solution here for the `ECMULT_CONST_TABLE_GET_GE` https://github.com/bitcoin-core/secp256k1/issues/753#issuecomment-631316091
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`)


Patch:
diff --git a/configure.ac b/configure.ac
index 6021b76..7f762fa 100644
--- a/configure.ac
+++ b/configure.ac
@@ -210,7 +210,7 @@ if test x"$use_ecmult_static_precomputation" != x"no"; then
   AC_RUN_IFELSE(
     [AC_LANG_PROGRAM([], [])],
     [working_native_cc=yes],
-    [working_native_cc=no],[:])
+    [working_native_cc=no],[dnl])
 
   CFLAGS_FOR_BUILD="$CFLAGS"
 
diff --git a/src/ecmult_const_impl.h b/src/ecmult_const_impl.h
index 011ccf0..6d6d354 100644
--- a/src/ecmult_const_impl.h
+++ b/src/ecmult_const_impl.h
@@ -14,7 +14,7 @@
 
 /* This is like `ECMULT_TABLE_GET_GE` but is constant time */
 #define ECMULT_CONST_TABLE_GET_GE(r,pre,n,w) do { \
-    int m; \
+    int m = 0; \
     /* Extract the sign-bit for a constant time absolute-value. */ \
     int mask = (n) >> (sizeof(n) * CHAR_BIT - 1); \
     int abs_n = ((n) + mask) ^ mask; \
@@ -25,7 +25,11 @@
     VERIFY_CHECK((n) <=  ((1 << ((w)-1)) - 1)); \
     VERIFY_SETUP(secp256k1_fe_clear(&(r)->x)); \
     VERIFY_SETUP(secp256k1_fe_clear(&(r)->y)); \
-    for (m = 0; m < ECMULT_TABLE_SIZE(w); m++) { \
+    /* Unconditionally set r->x = (pre)[m].x. r->y = (pre)[m].y. because it's either the correct one \
+     * or will get replaced in the later iterations, this is needed to make sure `r` is initialized. */ \
+    (r)->x = (pre)[m].x; \
+    (r)->y = (pre)[m].y; \
+    for (m = 1; m < ECMULT_TABLE_SIZE(w); m++) { \
         /* This loop is used to avoid secret data in array indices. See
          * the comment in ecmult_gen_impl.h for rationale. */ \
         secp256k1_fe_cmov(&(r)->x, &(pre)[m].x, m == idx_n); \
diff --git a/src/field.h b/src/field.h
index 8283e4b..7993a1f 100644
--- a/src/field.h
+++ b/src/field.h
@@ -125,10 +125,10 @@ static void secp256k1_fe_to_storage(secp256k1_fe_storage *r, const secp256k1_fe
 /** Convert a field element back from the storage type. */
 static void secp256k1_fe_from_storage(secp256k1_fe *r, const secp256k1_fe_storage *a);
 
-/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. */
+/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time.  Both *r and *a must be initialized.*/
 static void secp256k1_fe_storage_cmov(secp256k1_fe_storage *r, const secp256k1_fe_storage *a, int flag);
 
-/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. */
+/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time.  Both *r and *a must be initialized.*/
 static void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag);
 
 #endif /* SECP256K1_FIELD_H */
diff --git a/src/field_10x26_impl.h b/src/field_10x26_impl.h
index 3930424..651500e 100644
--- a/src/field_10x26_impl.h
+++ b/src/field_10x26_impl.h
@@ -1097,6 +1097,7 @@ static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a) {
 
 static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag) {
     uint32_t mask0, mask1;
+    VG_CHECK_VERIFY(r->n, sizeof(r->n));
     mask0 = flag + ~((uint32_t)0);
     mask1 = ~mask0;
     r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
@@ -1119,6 +1120,7 @@ static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_
 
 static SECP256K1_INLINE void secp256k1_fe_storage_cmov(secp256k1_fe_storage *r, const secp256k1_fe_storage *a, int flag) {
     uint32_t mask0, mask1;
+    VG_CHECK_VERIFY(r->n, sizeof(r->n));
     mask0 = flag + ~((uint32_t)0);
     mask1 = ~mask0;
     r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
diff --git a/src/field_5x52_impl.h b/src/field_5x52_impl.h
index 71aa550..71a38f9 100644
--- a/src/field_5x52_impl.h
+++ b/src/field_5x52_impl.h
@@ -449,6 +449,7 @@ static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a) {
 
 static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag) {
     uint64_t mask0, mask1;
+    VG_CHECK_VERIFY(r->n, sizeof(r->n));
     mask0 = flag + ~((uint64_t)0);
     mask1 = ~mask0;
     r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
@@ -466,6 +467,7 @@ static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_
 
 static SECP256K1_INLINE void secp256k1_fe_storage_cmov(secp256k1_fe_storage *r, const secp256k1_fe_storage *a, int flag) {
     uint64_t mask0, mask1;
+    VG_CHECK_VERIFY(r->n, sizeof(r->n));
     mask0 = flag + ~((uint64_t)0);
     mask1 = ~mask0;
     r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
diff --git a/src/group.h b/src/group.h
index ded4e1d..863644f 100644
--- a/src/group.h
+++ b/src/group.h
@@ -132,7 +132,7 @@ static void secp256k1_ge_to_storage(secp256k1_ge_storage *r, const secp256k1_ge
 /** Convert a group element back from the storage type. */
 static void secp256k1_ge_from_storage(secp256k1_ge *r, const secp256k1_ge_storage *a);
 
-/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. */
+/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time.  Both *r and *a must be initialized.*/
 static void secp256k1_ge_storage_cmov(secp256k1_ge_storage *r, const secp256k1_ge_storage *a, int flag);
 
 /** Rescale a jacobian point by b which must be non-zero. Constant-time. */
diff --git a/src/scalar.h b/src/scalar.h
index 6dc7574..2a74703 100644
--- a/src/scalar.h
+++ b/src/scalar.h
@@ -111,7 +111,7 @@ static void secp256k1_scalar_split_lambda(secp256k1_scalar *r1, secp256k1_scalar
 /** Multiply a and b (without taking the modulus!), divide by 2**shift, and round to the nearest integer. Shift must be at least 256. */
 static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b, unsigned int shift);
 
-/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. */
+/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time.  Both *r and *a must be initialized.*/
 static void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag);
 
 #endif /* SECP256K1_SCALAR_H */
diff --git a/src/scalar_4x64_impl.h b/src/scalar_4x64_impl.h
index 2d81006..8f539c4 100644
--- a/src/scalar_4x64_impl.h
+++ b/src/scalar_4x64_impl.h
@@ -948,6 +948,7 @@ SECP256K1_INLINE static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r,
 
 static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) {
     uint64_t mask0, mask1;
+    VG_CHECK_VERIFY(r->d, sizeof(r->d));
     mask0 = flag + ~((uint64_t)0);
     mask1 = ~mask0;
     r->d[0] = (r->d[0] & mask0) | (a->d[0] & mask1);
diff --git a/src/scalar_8x32_impl.h b/src/scalar_8x32_impl.h
index f504289..3c372f3 100644
--- a/src/scalar_8x32_impl.h
+++ b/src/scalar_8x32_impl.h
@@ -720,6 +720,7 @@ SECP256K1_INLINE static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r,
 
 static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) {
     uint32_t mask0, mask1;
+    VG_CHECK_VERIFY(r->d, sizeof(r->d));
     mask0 = flag + ~((uint32_t)0);
     mask1 = ~mask0;
     r->d[0] = (r->d[0] & mask0) | (a->d[0] & mask1);
diff --git a/src/scalar_low_impl.h b/src/scalar_low_impl.h
index ad81f37..b79cf1f 100644
--- a/src/scalar_low_impl.h
+++ b/src/scalar_low_impl.h
@@ -116,6 +116,7 @@ SECP256K1_INLINE static int secp256k1_scalar_eq(const secp256k1_scalar *a, const
 
 static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) {
     uint32_t mask0, mask1;
+    VG_CHECK_VERIFY(r, sizeof(*r));
     mask0 = flag + ~((uint32_t)0);
     mask1 = ~mask0;
     *r = (*r & mask0) | (*a & mask1);
diff --git a/src/secp256k1.c b/src/secp256k1.c
index de66be5..2b2238b 100644
--- a/src/secp256k1.c
+++ b/src/secp256k1.c
@@ -468,7 +468,8 @@ const secp256k1_nonce_function secp256k1_nonce_function_rfc6979 = nonce_function
 const secp256k1_nonce_function secp256k1_nonce_function_default = nonce_function_rfc6979;
 
 int secp256k1_ecdsa_sign(const secp256k1_context* ctx, secp256k1_ecdsa_signature *signature, const unsigned char *msg32, const unsigned char *seckey, secp256k1_nonce_function noncefp, const void* noncedata) {
-    secp256k1_scalar r, s;
+    /* Default initialization here is important so we won't pass uninit values to the cmov in the end */
+    secp256k1_scalar r = secp256k1_scalar_zero, s = secp256k1_scalar_zero;
     secp256k1_scalar sec, non, msg;
     int ret = 0;
     int is_sec_valid;
diff --git a/src/util.h b/src/util.h
index 9a86e78..a93ffb1 100644
--- a/src/util.h
+++ b/src/util.h
@@ -69,6 +69,25 @@ static SECP256K1_INLINE void secp256k1_callback_call(const secp256k1_callback *
 #define VERIFY_SETUP(stmt)
 #endif
 
+/* Define `VG_UNDEF` and `VG_CHECK` when VALGRIND is defined  */
+#if !defined(VG_CHECK)
+# if defined(VALGRIND)
+#  include <valgrind/memcheck.h>
+#  define VG_UNDEF(x,y) VALGRIND_MAKE_MEM_UNDEFINED((x),(y))
+#  define VG_CHECK(x,y) VALGRIND_CHECK_MEM_IS_DEFINED((x),(y))
+# else
+#  define VG_UNDEF(x,y)
+#  define VG_CHECK(x,y)
+# endif
+#endif
+
+/* Like `VG_CHECK` but on VERIFY only */
+#if defined(VERIFY)
+#define VG_CHECK_VERIFY(x,y) VG_CHECK((x), (y))
+#else
+#define VG_CHECK_VERIFY(x,y)
+#endif
+
 static SECP256K1_INLINE void *checked_malloc(const secp256k1_callback* cb, size_t size) {
     void *ret = malloc(size);
     if (ret == NULL) {


Test patch:
diff --git a/src/tests.c b/src/tests.c
index 324b60c..2c1306c 100644
--- a/src/tests.c
+++ b/src/tests.c
@@ -32,17 +32,6 @@ void ECDSA_SIG_get0(const ECDSA_SIG *sig, const BIGNUM **pr, const BIGNUM **ps)
 #include "contrib/lax_der_parsing.c"
 #include "contrib/lax_der_privatekey_parsing.c"
 
-#if !defined(VG_CHECK)
-# if defined(VALGRIND)
-#  include <valgrind/memcheck.h>
-#  define VG_UNDEF(x,y) VALGRIND_MAKE_MEM_UNDEFINED((x),(y))
-#  define VG_CHECK(x,y) VALGRIND_CHECK_MEM_IS_DEFINED((x),(y))
-# else
-#  define VG_UNDEF(x,y)
-#  define VG_CHECK(x,y)
-# endif
-#endif
-
 static int count = 64;
 static secp256k1_context *ctx = NULL;