Repository: bitcoin-core/secp256k1
Pull request #710 (2020-01-11 01:07:17)

Eliminate harmless non-constant time operations on secret data.
There were several places where the code was non-constant time
 for invalid secret inputs.  These are harmless under sane use
 but get in the way of automatic const-time validation.

(Nonce overflow in signing is not addressed, nor is s==0 in signing)


gmaxwell: Only the last commit is new, the rest are in other PRs.

This also doesn't touch the privkey tweak functions yet, because I had forgotten about them.

With this PR the valgrind test is totally clean except for overflow and s==0 in signing (and except for whatever functions like the tweak that should be tested but aren't tested yet).

Nonce overflow is a real non-constant timeness but security irrelevant because it never happens.

s==0 test is not actually a branch on secret data, but is instead a false positive owing to the fact that I haven't put in anything yet to tell valgrind that the data is no longer secret at that point-- though that will be easy to do.
gmaxwell: With the latest commit the tests run clean.
gmaxwell: I added a fixups commit which fixes the seckey verify and tweak operations which were previously not tested.

There is a remaining issue that the the scalar code uses "th += (c0 < tl) ? 1 : 0;"  which doesn't always compile to constant time code. E.g. 32-bit scalar on power9 w/ GCC 9.2.1 turns some of the muladds into branches.
gmaxwell: I could use some help figuring out an alternative for that's sort of carry which is equally fast and doesn't sometimes get turned into branches.
gmaxwell: Anyone here?
real-or-random: I'll have a closer look next week.
gmaxwell: Dropped the testing commit, it's now only in #708 which is rebased on top of this branch. I'll keep rebasing 708 based on this one now.
gmaxwell: I think I've lost track of where this is in review. I fixed some things, explained some things, closed some comments,  but feel kind of lost.
real-or-random: > I think I've lost track of where this is in review. I fixed some things, explained some things, closed some comments, but feel kind of lost.

I understand... I always feel lost when looking at this PR because the comments are on many different commits... I pinged you on the two conversations which you haven't addressed. They're both not crucial, it's just my try of making everyone feel less lost and organize the PR.

There's nothing else from my side, I can ACK this after your reply.  
real-or-random: I think you also missed that one:
https://github.com/bitcoin-core/secp256k1/pull/710#discussion_r373744796
gmaxwell: :-/  In fact I didn't miss it, I made the change and then must have lost it in a rebase.  I wonder if I lost any other changes at the same time.

Patch:
diff --git a/.travis.yml b/.travis.yml
index a1f2470..da4254c 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -2,7 +2,9 @@ language: c
 os: linux
 addons:
   apt:
-    packages: libgmp-dev
+    packages:
+      - libgmp-dev
+      - valgrind
 compiler:
   - clang
   - gcc
@@ -60,18 +62,10 @@ matrix:
       env:
         - BIGNUM=no  ENDOMORPHISM=yes  ASM=x86_64 EXPERIMENTAL=yes ECDH=yes  RECOVERY=yes
         - VALGRIND=yes EXTRAFLAGS="--disable-openssl-tests CPPFLAGS=-DVALGRIND" BUILD=
-      addons:
-        apt:
-          packages:
-            - valgrind
     - compiler: gcc
       env: # The same as above but without endomorphism.
         - BIGNUM=no  ENDOMORPHISM=no  ASM=x86_64 EXPERIMENTAL=yes ECDH=yes  RECOVERY=yes
         - VALGRIND=yes EXTRAFLAGS="--disable-openssl-tests CPPFLAGS=-DVALGRIND" BUILD=
-      addons:
-        apt:
-          packages:
-            - valgrind
 
 before_script: ./autogen.sh
 
diff --git a/Makefile.am b/Makefile.am
index de56754..79dcf6e 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -69,6 +69,10 @@ libsecp256k1_la_SOURCES = src/secp256k1.c
 libsecp256k1_la_CPPFLAGS = -DSECP256K1_BUILD -I$(top_srcdir)/include -I$(top_srcdir)/src $(SECP_INCLUDES)
 libsecp256k1_la_LIBADD = $(SECP_LIBS) $(COMMON_LIB)
 
+if VALGRIND_ENABLED
+libsecp256k1_la_CPPFLAGS += -DVALGRIND
+endif
+
 noinst_PROGRAMS =
 if USE_BENCHMARK
 noinst_PROGRAMS += bench_verify bench_sign bench_internal bench_ecmult
diff --git a/configure.ac b/configure.ac
index 5021040..a2023ab 100644
--- a/configure.ac
+++ b/configure.ac
@@ -170,6 +170,9 @@ AC_ARG_WITH([ecmult-gen-precision], [AS_HELP_STRING([--with-ecmult-gen-precision
 
 AC_CHECK_TYPES([__int128])
 
+AC_CHECK_HEADER([valgrind/memcheck.h], [enable_valgrind=yes], [enable_valgrind=no], [])
+AM_CONDITIONAL([VALGRIND_ENABLED],[test "$enable_valgrind" = "yes"])
+
 if test x"$enable_coverage" = x"yes"; then
     AC_DEFINE(COVERAGE, 1, [Define this symbol to compile out all VERIFY code])
     CFLAGS="$CFLAGS -O0 --coverage"
diff --git a/include/secp256k1.h b/include/secp256k1.h
index 36020e5..1678406 100644
--- a/include/secp256k1.h
+++ b/include/secp256k1.h
@@ -162,12 +162,14 @@ typedef int (*secp256k1_nonce_function)(
 /** The higher bits contain the actual data. Do not use directly. */
 #define SECP256K1_FLAGS_BIT_CONTEXT_VERIFY (1 << 8)
 #define SECP256K1_FLAGS_BIT_CONTEXT_SIGN (1 << 9)
+#define SECP256K1_FLAGS_BIT_CONTEXT_DECLASSIFY (1 << 10)
 #define SECP256K1_FLAGS_BIT_COMPRESSION (1 << 8)
 
 /** Flags to pass to secp256k1_context_create, secp256k1_context_preallocated_size, and
  *  secp256k1_context_preallocated_create. */
 #define SECP256K1_CONTEXT_VERIFY (SECP256K1_FLAGS_TYPE_CONTEXT | SECP256K1_FLAGS_BIT_CONTEXT_VERIFY)
 #define SECP256K1_CONTEXT_SIGN (SECP256K1_FLAGS_TYPE_CONTEXT | SECP256K1_FLAGS_BIT_CONTEXT_SIGN)
+#define SECP256K1_CONTEXT_DECLASSIFY (SECP256K1_FLAGS_TYPE_CONTEXT | SECP256K1_FLAGS_BIT_CONTEXT_DECLASSIFY)
 #define SECP256K1_CONTEXT_NONE (SECP256K1_FLAGS_TYPE_CONTEXT)
 
 /** Flag to pass to secp256k1_ec_pubkey_serialize. */
diff --git a/src/ecdsa_impl.h b/src/ecdsa_impl.h
index eb099c8..359c621 100644
--- a/src/ecdsa_impl.h
+++ b/src/ecdsa_impl.h
@@ -280,6 +280,7 @@ static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context *ctx, sec
     secp256k1_ge r;
     secp256k1_scalar n;
     int overflow = 0;
+    int high;
 
     secp256k1_ecmult_gen(ctx, &rp, nonce);
     secp256k1_ge_set_gej(&r, &rp);
@@ -295,7 +296,7 @@ static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context *ctx, sec
         /* The overflow condition is cryptographically unreachable as hitting it requires finding the discrete log
          * of some P where P.x >= order, and only 1 in about 2^127 points meet this criteria.
          */
-        *recid = (overflow ? 2 : 0) | (secp256k1_fe_is_odd(&r.y) ? 1 : 0);
+        *recid = (overflow << 1) | secp256k1_fe_is_odd(&r.y);
     }
     secp256k1_scalar_mul(&n, sigr, seckey);
     secp256k1_scalar_add(&n, &n, message);
@@ -304,16 +305,12 @@ static int secp256k1_ecdsa_sig_sign(const secp256k1_ecmult_gen_context *ctx, sec
     secp256k1_scalar_clear(&n);
     secp256k1_gej_clear(&rp);
     secp256k1_ge_clear(&r);
-    if (secp256k1_scalar_is_zero(sigs)) {
-        return 0;
-    }
-    if (secp256k1_scalar_is_high(sigs)) {
-        secp256k1_scalar_negate(sigs, sigs);
-        if (recid) {
-            *recid ^= 1;
-        }
+    high = secp256k1_scalar_is_high(sigs);
+    secp256k1_scalar_cond_negate(sigs, high);
+    if (recid) {
+            *recid ^= high;
     }
-    return 1;
+    return !secp256k1_scalar_is_zero(sigs);
 }
 
 #endif /* SECP256K1_ECDSA_IMPL_H */
diff --git a/src/eckey_impl.h b/src/eckey_impl.h
index 7c5b789..00e4a86 100644
--- a/src/eckey_impl.h
+++ b/src/eckey_impl.h
@@ -75,12 +75,11 @@ static int secp256k1_eckey_pubkey_tweak_add(const secp256k1_ecmult_context *ctx,
 }
 
 static int secp256k1_eckey_privkey_tweak_mul(secp256k1_scalar *key, const secp256k1_scalar *tweak) {
-    if (secp256k1_scalar_is_zero(tweak)) {
-        return 0;
-    }
+    int ret;
+    ret = !secp256k1_scalar_is_zero(tweak);
 
     secp256k1_scalar_mul(key, key, tweak);
-    return 1;
+    return ret;
 }
 
 static int secp256k1_eckey_pubkey_tweak_mul(const secp256k1_ecmult_context *ctx, secp256k1_ge *key, const secp256k1_scalar *tweak) {
diff --git a/src/ecmult_gen_impl.h b/src/ecmult_gen_impl.h
index a1b9639..30ac165 100644
--- a/src/ecmult_gen_impl.h
+++ b/src/ecmult_gen_impl.h
@@ -163,7 +163,7 @@ static void secp256k1_ecmult_gen_blind(secp256k1_ecmult_gen_context *ctx, const
     secp256k1_fe s;
     unsigned char nonce32[32];
     secp256k1_rfc6979_hmac_sha256 rng;
-    int retry;
+    int overflow;
     unsigned char keydata[64] = {0};
     if (seed32 == NULL) {
         /* When seed is NULL, reset the initial point and blinding value. */
@@ -183,21 +183,18 @@ static void secp256k1_ecmult_gen_blind(secp256k1_ecmult_gen_context *ctx, const
     }
     secp256k1_rfc6979_hmac_sha256_initialize(&rng, keydata, seed32 ? 64 : 32);
     memset(keydata, 0, sizeof(keydata));
-    /* Retry for out of range results to achieve uniformity. */
-    do {
-        secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32);
-        retry = !secp256k1_fe_set_b32(&s, nonce32);
-        retry = retry || secp256k1_fe_is_zero(&s);
-    } while (retry); /* This branch true is cryptographically unreachable. Requires sha256_hmac output > Fp. */
+    /* Accept unobservably small non-uniformity. */
+    secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32);
+    overflow = !secp256k1_fe_set_b32(&s, nonce32);
+    overflow |= secp256k1_fe_is_zero(&s);
+    secp256k1_fe_cmov(&s, &secp256k1_fe_one, overflow);
     /* Randomize the projection to defend against multiplier sidechannels. */
     secp256k1_gej_rescale(&ctx->initial, &s);
     secp256k1_fe_clear(&s);
-    do {
-        secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32);
-        secp256k1_scalar_set_b32(&b, nonce32, &retry);
-        /* A blinding value of 0 works, but would undermine the projection hardening. */
-        retry = retry || secp256k1_scalar_is_zero(&b);
-    } while (retry); /* This branch true is cryptographically unreachable. Requires sha256_hmac output > order. */
+    secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32);
+    secp256k1_scalar_set_b32(&b, nonce32, NULL);
+    /* A blinding value of 0 works, but would undermine the projection hardening. */
+    secp256k1_scalar_cmov(&b, &secp256k1_scalar_one, secp256k1_scalar_is_zero(&b));
     secp256k1_rfc6979_hmac_sha256_finalize(&rng);
     memset(nonce32, 0, 32);
     secp256k1_ecmult_gen(ctx, &gb, &b);
diff --git a/src/field_10x26_impl.h b/src/field_10x26_impl.h
index 4ae4fdc..3930424 100644
--- a/src/field_10x26_impl.h
+++ b/src/field_10x26_impl.h
@@ -320,6 +320,7 @@ static int secp256k1_fe_cmp_var(const secp256k1_fe *a, const secp256k1_fe *b) {
 }
 
 static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a) {
+    int ret;
     r->n[0] = (uint32_t)a[31] | ((uint32_t)a[30] << 8) | ((uint32_t)a[29] << 16) | ((uint32_t)(a[28] & 0x3) << 24);
     r->n[1] = (uint32_t)((a[28] >> 2) & 0x3f) | ((uint32_t)a[27] << 6) | ((uint32_t)a[26] << 14) | ((uint32_t)(a[25] & 0xf) << 22);
     r->n[2] = (uint32_t)((a[25] >> 4) & 0xf) | ((uint32_t)a[24] << 4) | ((uint32_t)a[23] << 12) | ((uint32_t)(a[22] & 0x3f) << 20);
@@ -331,15 +332,17 @@ static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a) {
     r->n[8] = (uint32_t)a[5] | ((uint32_t)a[4] << 8) | ((uint32_t)a[3] << 16) | ((uint32_t)(a[2] & 0x3) << 24);
     r->n[9] = (uint32_t)((a[2] >> 2) & 0x3f) | ((uint32_t)a[1] << 6) | ((uint32_t)a[0] << 14);
 
-    if (r->n[9] == 0x3FFFFFUL && (r->n[8] & r->n[7] & r->n[6] & r->n[5] & r->n[4] & r->n[3] & r->n[2]) == 0x3FFFFFFUL && (r->n[1] + 0x40UL + ((r->n[0] + 0x3D1UL) >> 26)) > 0x3FFFFFFUL) {
-        return 0;
-    }
+    ret = !((r->n[9] == 0x3FFFFFUL) & ((r->n[8] & r->n[7] & r->n[6] & r->n[5] & r->n[4] & r->n[3] & r->n[2]) == 0x3FFFFFFUL) & ((r->n[1] + 0x40UL + ((r->n[0] + 0x3D1UL) >> 26)) > 0x3FFFFFFUL));
 #ifdef VERIFY
     r->magnitude = 1;
-    r->normalized = 1;
-    secp256k1_fe_verify(r);
+    if (ret) {
+        r->normalized = 1;
+        secp256k1_fe_verify(r);
+    } else {
+        r->normalized = 0;
+    }
 #endif
-    return 1;
+    return ret;
 }
 
 /** Convert a field element to a 32-byte big endian value. Requires the input to be normalized */
@@ -1107,10 +1110,10 @@ static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_
     r->n[8] = (r->n[8] & mask0) | (a->n[8] & mask1);
     r->n[9] = (r->n[9] & mask0) | (a->n[9] & mask1);
 #ifdef VERIFY
-    if (a->magnitude > r->magnitude) {
+    if (flag) {
         r->magnitude = a->magnitude;
+        r->normalized = a->normalized;
     }
-    r->normalized &= a->normalized;
 #endif
 }
 
diff --git a/src/field_5x52_impl.h b/src/field_5x52_impl.h
index f426332..71aa550 100644
--- a/src/field_5x52_impl.h
+++ b/src/field_5x52_impl.h
@@ -283,6 +283,7 @@ static int secp256k1_fe_cmp_var(const secp256k1_fe *a, const secp256k1_fe *b) {
 }
 
 static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a) {
+    int ret;
     r->n[0] = (uint64_t)a[31]
             | ((uint64_t)a[30] << 8)
             | ((uint64_t)a[29] << 16)
@@ -317,15 +318,17 @@ static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a) {
             | ((uint64_t)a[2] << 24)
             | ((uint64_t)a[1] << 32)
             | ((uint64_t)a[0] << 40);
-    if (r->n[4] == 0x0FFFFFFFFFFFFULL && (r->n[3] & r->n[2] & r->n[1]) == 0xFFFFFFFFFFFFFULL && r->n[0] >= 0xFFFFEFFFFFC2FULL) {
-        return 0;
-    }
+    ret = !((r->n[4] == 0x0FFFFFFFFFFFFULL) & ((r->n[3] & r->n[2] & r->n[1]) == 0xFFFFFFFFFFFFFULL) & (r->n[0] >= 0xFFFFEFFFFFC2FULL));
 #ifdef VERIFY
     r->magnitude = 1;
-    r->normalized = 1;
-    secp256k1_fe_verify(r);
+    if (ret) {
+        r->normalized = 1;
+        secp256k1_fe_verify(r);
+    } else {
+        r->normalized = 0;
+    }
 #endif
-    return 1;
+    return ret;
 }
 
 /** Convert a field element to a 32-byte big endian value. Requires the input to be normalized */
@@ -454,10 +457,10 @@ static SECP256K1_INLINE void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_
     r->n[3] = (r->n[3] & mask0) | (a->n[3] & mask1);
     r->n[4] = (r->n[4] & mask0) | (a->n[4] & mask1);
 #ifdef VERIFY
-    if (a->magnitude > r->magnitude) {
+    if (flag) {
         r->magnitude = a->magnitude;
+        r->normalized = a->normalized;
     }
-    r->normalized &= a->normalized;
 #endif
 }
 
diff --git a/src/field_impl.h b/src/field_impl.h
index 6070cac..485921a 100644
--- a/src/field_impl.h
+++ b/src/field_impl.h
@@ -315,4 +315,6 @@ static int secp256k1_fe_is_quad_var(const secp256k1_fe *a) {
 #endif
 }
 
+static const secp256k1_fe secp256k1_fe_one = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1);
+
 #endif /* SECP256K1_FIELD_IMPL_H */
diff --git a/src/modules/ecdh/main_impl.h b/src/modules/ecdh/main_impl.h
index 44cb68e..5f36152 100644
--- a/src/modules/ecdh/main_impl.h
+++ b/src/modules/ecdh/main_impl.h
@@ -32,36 +32,40 @@ int secp256k1_ecdh(const secp256k1_context* ctx, unsigned char *output, const se
     secp256k1_gej res;
     secp256k1_ge pt;
     secp256k1_scalar s;
+    unsigned char x[32];
+    unsigned char y[32];
+
     VERIFY_CHECK(ctx != NULL);
     ARG_CHECK(output != NULL);
     ARG_CHECK(point != NULL);
     ARG_CHECK(scalar != NULL);
+
     if (hashfp == NULL) {
         hashfp = secp256k1_ecdh_hash_function_default;
     }
 
     secp256k1_pubkey_load(ctx, &pt, point);
     secp256k1_scalar_set_b32(&s, scalar, &overflow);
-    if (overflow || secp256k1_scalar_is_zero(&s)) {
-        ret = 0;
-    } else {
-        unsigned char x[32];
-        unsigned char y[32];
-
-        secp256k1_ecmult_const(&res, &pt, &s, 256);
-        secp256k1_ge_set_gej(&pt, &res);
-
-        /* Compute a hash of the point */
-        secp256k1_fe_normalize(&pt.x);
-        secp256k1_fe_normalize(&pt.y);
-        secp256k1_fe_get_b32(x, &pt.x);
-        secp256k1_fe_get_b32(y, &pt.y);
-
-        ret = hashfp(output, x, y, data);
-    }
 
+    overflow |= secp256k1_scalar_is_zero(&s);
+    secp256k1_scalar_cmov(&s, &secp256k1_scalar_one, overflow);
+
+    secp256k1_ecmult_const(&res, &pt, &s, 256);
+    secp256k1_ge_set_gej(&pt, &res);
+
+    /* Compute a hash of the point */
+    secp256k1_fe_normalize(&pt.x);
+    secp256k1_fe_normalize(&pt.y);
+    secp256k1_fe_get_b32(x, &pt.x);
+    secp256k1_fe_get_b32(y, &pt.y);
+
+    ret = hashfp(output, x, y, data);
+
+    memset(x, 0, 32);
+    memset(y, 0, 32);
     secp256k1_scalar_clear(&s);
-    return ret;
+
+    return !!ret & !overflow;
 }
 
 #endif /* SECP256K1_MODULE_ECDH_MAIN_H */
diff --git a/src/scalar.h b/src/scalar.h
index 1ee50e1..da71178 100644
--- a/src/scalar.h
+++ b/src/scalar.h
@@ -107,4 +107,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. */
+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 d378335..2d81006 100644
--- a/src/scalar_4x64_impl.h
+++ b/src/scalar_4x64_impl.h
@@ -946,4 +946,14 @@ SECP256K1_INLINE static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r,
     secp256k1_scalar_cadd_bit(r, 0, (l[(shift - 1) >> 6] >> ((shift - 1) & 0x3f)) & 1);
 }
 
+static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) {
+    uint64_t mask0, mask1;
+    mask0 = flag + ~((uint64_t)0);
+    mask1 = ~mask0;
+    r->d[0] = (r->d[0] & mask0) | (a->d[0] & mask1);
+    r->d[1] = (r->d[1] & mask0) | (a->d[1] & mask1);
+    r->d[2] = (r->d[2] & mask0) | (a->d[2] & mask1);
+    r->d[3] = (r->d[3] & mask0) | (a->d[3] & mask1);
+}
+
 #endif /* SECP256K1_SCALAR_REPR_IMPL_H */
diff --git a/src/scalar_8x32_impl.h b/src/scalar_8x32_impl.h
index 4f9ed61..f504289 100644
--- a/src/scalar_8x32_impl.h
+++ b/src/scalar_8x32_impl.h
@@ -718,4 +718,18 @@ SECP256K1_INLINE static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r,
     secp256k1_scalar_cadd_bit(r, 0, (l[(shift - 1) >> 5] >> ((shift - 1) & 0x1f)) & 1);
 }
 
+static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) {
+    uint32_t mask0, mask1;
+    mask0 = flag + ~((uint32_t)0);
+    mask1 = ~mask0;
+    r->d[0] = (r->d[0] & mask0) | (a->d[0] & mask1);
+    r->d[1] = (r->d[1] & mask0) | (a->d[1] & mask1);
+    r->d[2] = (r->d[2] & mask0) | (a->d[2] & mask1);
+    r->d[3] = (r->d[3] & mask0) | (a->d[3] & mask1);
+    r->d[4] = (r->d[4] & mask0) | (a->d[4] & mask1);
+    r->d[5] = (r->d[5] & mask0) | (a->d[5] & mask1);
+    r->d[6] = (r->d[6] & mask0) | (a->d[6] & mask1);
+    r->d[7] = (r->d[7] & mask0) | (a->d[7] & mask1);
+}
+
 #endif /* SECP256K1_SCALAR_REPR_IMPL_H */
diff --git a/src/scalar_impl.h b/src/scalar_impl.h
index 6b336d9..c9b38f3 100644
--- a/src/scalar_impl.h
+++ b/src/scalar_impl.h
@@ -24,6 +24,9 @@
 #error "Please select scalar implementation"
 #endif
 
+static const secp256k1_scalar secp256k1_scalar_one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1);
+static const secp256k1_scalar secp256k1_scalar_zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
+
 #ifndef USE_NUM_NONE
 static void secp256k1_scalar_get_num(secp256k1_num *r, const secp256k1_scalar *a) {
     unsigned char c[32];
diff --git a/src/scalar_low.h b/src/scalar_low.h
index 5836feb..2794a7f 100644
--- a/src/scalar_low.h
+++ b/src/scalar_low.h
@@ -12,4 +12,6 @@
 /** A scalar modulo the group order of the secp256k1 curve. */
 typedef uint32_t secp256k1_scalar;
 
+#define SECP256K1_SCALAR_CONST(d7, d6, d5, d4, d3, d2, d1, d0) (d0)
+
 #endif /* SECP256K1_SCALAR_REPR_H */
diff --git a/src/scalar_low_impl.h b/src/scalar_low_impl.h
index 910ce3f..ad81f37 100644
--- a/src/scalar_low_impl.h
+++ b/src/scalar_low_impl.h
@@ -114,4 +114,11 @@ SECP256K1_INLINE static int secp256k1_scalar_eq(const secp256k1_scalar *a, const
     return *a == *b;
 }
 
+static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) {
+    uint32_t mask0, mask1;
+    mask0 = flag + ~((uint32_t)0);
+    mask1 = ~mask0;
+    *r = (*r & mask0) | (*a & mask1);
+}
+
 #endif /* SECP256K1_SCALAR_REPR_IMPL_H */
diff --git a/src/secp256k1.c b/src/secp256k1.c
index a3f446e..c10ac4c 100644
--- a/src/secp256k1.c
+++ b/src/secp256k1.c
@@ -20,6 +20,10 @@
 #include "hash_impl.h"
 #include "scratch_impl.h"
 
+#if defined(VALGRIND)
+# include <valgrind/memcheck.h>
+#endif
+
 #define ARG_CHECK(cond) do { \
     if (EXPECT(!(cond), 0)) { \
         secp256k1_callback_call(&ctx->illegal_callback, #cond); \
@@ -66,13 +70,15 @@ struct secp256k1_context_struct {
     secp256k1_ecmult_gen_context ecmult_gen_ctx;
     secp256k1_callback illegal_callback;
     secp256k1_callback error_callback;
+    int declassify;
 };
 
 static const secp256k1_context secp256k1_context_no_precomp_ = {
     { 0 },
     { 0 },
     { secp256k1_default_illegal_callback_fn, 0 },
-    { secp256k1_default_error_callback_fn, 0 }
+    { secp256k1_default_error_callback_fn, 0 },
+    0
 };
 const secp256k1_context *secp256k1_context_no_precomp = &secp256k1_context_no_precomp_;
 
@@ -132,6 +138,7 @@ secp256k1_context* secp256k1_context_preallocated_create(void* prealloc, unsigne
     if (flags & SECP256K1_FLAGS_BIT_CONTEXT_VERIFY) {
         secp256k1_ecmult_context_build(&ret->ecmult_ctx, &prealloc);
     }
+    ret->declassify = !!(flags & SECP256K1_FLAGS_BIT_CONTEXT_DECLASSIFY);
 
     return (secp256k1_context*) ret;
 }
@@ -215,6 +222,20 @@ void secp256k1_scratch_space_destroy(const secp256k1_context *ctx, secp256k1_scr
     secp256k1_scratch_destroy(&ctx->error_callback, scratch);
 }
 
+/* Mark memory as no-longer-secret for the purpose of analysing constant-time behaviour
+ *  of the software. This is setup for use with valgrind but could be substituted with
+ *  the appropriate instrumentation for other analysis tools.
+ */
+static SECP256K1_INLINE void secp256k1_declassify(const secp256k1_context* ctx, void *p, size_t len) {
+#if defined(VALGRIND)
+    if (EXPECT(ctx->declassify,0)) VALGRIND_MAKE_MEM_DEFINED(p, len);
+#else
+    (void)ctx;
+    (void)p;
+    (void)len;
+#endif
+}
+
 static int secp256k1_pubkey_load(const secp256k1_context* ctx, secp256k1_ge* ge, const secp256k1_pubkey* pubkey) {
     if (sizeof(secp256k1_ge_storage) == 64) {
         /* When the secp256k1_ge_storage type is exactly 64 byte, use its
@@ -451,6 +472,8 @@ int secp256k1_ecdsa_sign(const secp256k1_context* ctx, secp256k1_ecdsa_signature
     secp256k1_scalar sec, non, msg;
     int ret = 0;
     int overflow = 0;
+    unsigned char nonce32[32];
+    unsigned int count = 0;
     VERIFY_CHECK(ctx != NULL);
     ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx));
     ARG_CHECK(msg32 != NULL);
@@ -462,34 +485,37 @@ int secp256k1_ecdsa_sign(const secp256k1_context* ctx, secp256k1_ecdsa_signature
 
     secp256k1_scalar_set_b32(&sec, seckey, &overflow);
     /* Fail if the secret key is invalid. */
-    if (!overflow && !secp256k1_scalar_is_zero(&sec)) {
-        unsigned char nonce32[32];
-        unsigned int count = 0;
-        secp256k1_scalar_set_b32(&msg, msg32, NULL);
-        while (1) {
-            ret = noncefp(nonce32, msg32, seckey, NULL, (void*)noncedata, count);
-            if (!ret) {
+    overflow |= secp256k1_scalar_is_zero(&sec);
+    secp256k1_scalar_cmov(&sec, &secp256k1_scalar_one, overflow);
+    secp256k1_scalar_set_b32(&msg, msg32, NULL);
+    while (1) {
+        int koverflow;
+        ret = noncefp(nonce32, msg32, seckey, NULL, (void*)noncedata, count);
+        if (!ret) {
+            break;
+        }
+        secp256k1_scalar_set_b32(&non, nonce32, &koverflow);
+        koverflow |= secp256k1_scalar_is_zero(&non);
+        /* The nonce is still secret here, but it overflowing or being zero is is less likely than 1:2^255. */
+        secp256k1_declassify(ctx, &koverflow, sizeof(koverflow));
+        if (!koverflow) {
+            ret = secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, NULL);
+            /* The final signature is no longer a secret, nor is the fact that we were successful or not. */
+            secp256k1_declassify(ctx, &ret, sizeof(ret));
+            if (ret) {
                 break;
             }
-            secp256k1_scalar_set_b32(&non, nonce32, &overflow);
-            if (!overflow && !secp256k1_scalar_is_zero(&non)) {
-                if (secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, NULL)) {
-                    break;
-                }
-            }
-            count++;
         }
-        memset(nonce32, 0, 32);
-        secp256k1_scalar_clear(&msg);
-        secp256k1_scalar_clear(&non);
-        secp256k1_scalar_clear(&sec);
-    }
-    if (ret) {
-        secp256k1_ecdsa_signature_save(signature, &r, &s);
-    } else {
-        memset(signature, 0, sizeof(*signature));
+        count++;
     }
-    return ret;
+    memset(nonce32, 0, 32);
+    secp256k1_scalar_clear(&msg);
+    secp256k1_scalar_clear(&non);
+    secp256k1_scalar_clear(&sec);
+    secp256k1_scalar_cmov(&r, &secp256k1_scalar_zero, (!ret) | overflow);
+    secp256k1_scalar_cmov(&s, &secp256k1_scalar_zero, (!ret) | overflow);
+    secp256k1_ecdsa_signature_save(signature, &r, &s);
+    return !!ret & !overflow;
 }
 
 int secp256k1_ec_seckey_verify(const secp256k1_context* ctx, const unsigned char *seckey) {
@@ -500,7 +526,7 @@ int secp256k1_ec_seckey_verify(const secp256k1_context* ctx, const unsigned char
     ARG_CHECK(seckey != NULL);
 
     secp256k1_scalar_set_b32(&sec, seckey, &overflow);
-    ret = !overflow && !secp256k1_scalar_is_zero(&sec);
+    ret = !overflow & !secp256k1_scalar_is_zero(&sec);
     secp256k1_scalar_clear(&sec);
     return ret;
 }
@@ -518,12 +544,14 @@ int secp256k1_ec_pubkey_create(const secp256k1_context* ctx, secp256k1_pubkey *p
     ARG_CHECK(seckey != NULL);
 
     secp256k1_scalar_set_b32(&sec, seckey, &overflow);
-    ret = !overflow && !secp256k1_scalar_is_zero(&sec);
-    if (ret) {
-        secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pj, &sec);
-        secp256k1_ge_set_gej(&p, &pj);
-        secp256k1_pubkey_save(pubkey, &p);
-    }
+    ret = !overflow & !secp256k1_scalar_is_zero(&sec);
+    secp256k1_scalar_cmov(&sec, &secp256k1_scalar_one, !ret);
+
+    secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pj, &sec);
+    secp256k1_ge_set_gej(&p, &pj);
+    secp256k1_pubkey_save(pubkey, &p);
+    memczero(pubkey, sizeof(*pubkey), !ret);
+
     secp256k1_scalar_clear(&sec);
     return ret;
 }
@@ -568,11 +596,9 @@ int secp256k1_ec_privkey_tweak_add(const secp256k1_context* ctx, unsigned char *
     secp256k1_scalar_set_b32(&term, tweak, &overflow);
     secp256k1_scalar_set_b32(&sec, seckey, NULL);
 
-    ret = !overflow && secp256k1_eckey_privkey_tweak_add(&sec, &term);
-    memset(seckey, 0, 32);
-    if (ret) {
-        secp256k1_scalar_get_b32(seckey, &sec);
-    }
+    ret = (!overflow) & secp256k1_eckey_privkey_tweak_add(&sec, &term);
+    secp256k1_scalar_cmov(&sec, &secp256k1_scalar_zero, !ret);
+    secp256k1_scalar_get_b32(seckey, &sec);
 
     secp256k1_scalar_clear(&sec);
     secp256k1_scalar_clear(&term);
@@ -614,11 +640,9 @@ int secp256k1_ec_privkey_tweak_mul(const secp256k1_context* ctx, unsigned char *
 
     secp256k1_scalar_set_b32(&factor, tweak, &overflow);
     secp256k1_scalar_set_b32(&sec, seckey, NULL);
-    ret = !overflow && secp256k1_eckey_privkey_tweak_mul(&sec, &factor);
-    memset(seckey, 0, 32);
-    if (ret) {
-        secp256k1_scalar_get_b32(seckey, &sec);
-    }
+    ret = (!overflow) & secp256k1_eckey_privkey_tweak_mul(&sec, &factor);
+    secp256k1_scalar_cmov(&sec, &secp256k1_scalar_zero, !ret);
+    secp256k1_scalar_get_b32(seckey, &sec);
 
     secp256k1_scalar_clear(&sec);
     secp256k1_scalar_clear(&factor);
diff --git a/src/util.h b/src/util.h
index d5fa39c..2f96e2f 100644
--- a/src/util.h
+++ b/src/util.h
@@ -160,4 +160,16 @@ static SECP256K1_INLINE void *manual_alloc(void** prealloc_ptr, size_t alloc_siz
 SECP256K1_GNUC_EXT typedef unsigned __int128 uint128_t;
 #endif
 
+/* Zero memory if flag == 1. Constant time. */
+static SECP256K1_INLINE void memczero(void *s, size_t len, int flag) {
+    unsigned char *p;
+    unsigned char mask = -(unsigned char)flag;
+    p = (unsigned char *)s;
+    while (len) {
+        *p ^= *p & mask;
+        p++;
+        len--;
+    }
+}
+
 #endif /* SECP256K1_UTIL_H */


Test patch:
diff --git a/src/tests.c b/src/tests.c
index d1cfcb5..7edfa8a 100644
--- a/src/tests.c
+++ b/src/tests.c
@@ -1822,7 +1822,7 @@ void run_field_misc(void) {
         q = x;
         secp256k1_fe_cmov(&x, &z, 0);
 #ifdef VERIFY
-        CHECK(!x.normalized && x.magnitude == z.magnitude);
+        CHECK(x.normalized && x.magnitude == 1);
 #endif
         secp256k1_fe_cmov(&x, &x, 1);
         CHECK(fe_memcmp(&x, &z) != 0);
@@ -1845,7 +1845,7 @@ void run_field_misc(void) {
             secp256k1_fe_normalize_var(&q);
             secp256k1_fe_cmov(&q, &z, (j&1));
 #ifdef VERIFY
-            CHECK(!q.normalized && q.magnitude == (j+2));
+            CHECK((q.normalized != (j&1)) && q.magnitude == ((j&1) ? z.magnitude : 1));
 #endif
         }
         secp256k1_fe_normalize_var(&z);