Eliminate harmless non-constant time operations on secret data.

gmaxwell commented at 1:07 am on January 11, 2020: contributor

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 commented at 1:10 am on January 11, 2020: contributor

Only the “Eliminate harmless” “declassify” commits are 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.

This was made somewhat more complicated by preserving the output-zeroization on failure.

gmaxwell commented at 1:38 pm on January 11, 2020: contributor

With the latest commit the tests run clean.

gmaxwell cross-referenced this on Jan 15, 2020 from issue Constant-time behaviour test using valgrind memtest. by gmaxwell

gmaxwell renamed this:
~~[WIP] Eliminate harmless non-constant time operations on secret data.~~
Eliminate harmless non-constant time operations on secret data.
on Jan 15, 2020

gmaxwell commented at 6:33 pm on January 15, 2020: contributor

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 (e.g. src/scalar_8x32_impl.h:444).

gmaxwell commented at 6:54 pm on January 15, 2020: contributor

I could use some help figuring out an alternative for that sort of carry which is equally fast and doesn’t sometimes get turned into branches.

Similarly, testing this with different compilers/build-options/arches would be useful to learn if there are any other missed cases.

I think this is probably enough progress to merge– it does at least make the tests clean on my desktop–, if people would like I can drop off the tester commit and I could work towards merging this much even though there are a few platform/compiler specific issues remaining.

gmaxwell commented at 8:16 pm on January 25, 2020: contributor

Anyone here?

in src/ecmult_gen_impl.h:190 in 82989f565c outdated

191-    } while (retry); /* This branch true is cryptographically unreachable. Requires sha256_hmac output > Fp. */
192+    /* Accept unobservably small non-uniformity. */
193+    secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32);
194+    range = !secp256k1_fe_set_b32(&s, nonce32);
195+    range |= secp256k1_fe_is_zero(&s);
196+    secp256k1_fe_cmov(&s, &secp256k1_fe_one, range);

elichai commented at 10:01 am on January 26, 2020:

why set to one instead of just letting it overflow?

sipa commented at 0:24 am on February 1, 2020:

@elichai s remains uninitialized if secp256k1_fe_set_b32 fails; doing anything on it can cause failure (and it actually can in practice in debug mode, because the magnitude/normalized flags will be garbage). @gmaxwell I think you also can’t call secp256k1_fe_is_zero in case secp256k1_fe_set_b32 above fails. Perhaps it’s easiest to call secp256k1_fe_clear on s before the set_b32?

gmaxwell commented at 6:34 am on February 3, 2020:

@sipa so I took another approach: I made the cmovs propagate the actual magnitude rather than the worst case. This reduces test sensitivity a little but I think it’s cleaner. Your thoughts?

gmaxwell commented at 6:35 am on February 3, 2020:

See the fixups commit.

real-or-random commented at 6:44 pm on February 3, 2020:

I think either way is fine but why do you think it’s cleaner?

gmaxwell commented at 3:52 am on February 8, 2020:

Because it makes the cmov behave how I thought it behaved, also less code.

in src/ecmult_gen_impl.h:197 in 82989f565c outdated

204-        retry = retry || secp256k1_scalar_is_zero(&b);
205-    } while (retry); /* This branch true is cryptographically unreachable. Requires sha256_hmac output > order. */
206+    secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32);
207+    secp256k1_scalar_set_b32(&b, nonce32, NULL);
208+    /* A blinding value of 0 works, but would undermine the projection hardening. */
209+    secp256k1_scalar_cmov(&b, &secp256k1_scalar_one, secp256k1_scalar_is_zero(&b));

elichai commented at 10:06 am on January 26, 2020:

same

in src/field_10x26_impl.h:335 in 82989f565c outdated

331@@ -331,15 +332,15 @@ static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a) {
332     r->n[8] = (uint32_t)a[5] | ((uint32_t)a[4] << 8) | ((uint32_t)a[3] << 16) | ((uint32_t)(a[2] & 0x3) << 24);
333     r->n[9] = (uint32_t)((a[2] >> 2) & 0x3f) | ((uint32_t)a[1] << 6) | ((uint32_t)a[0] << 14);
334 
335-    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) {
336-        return 0;
337-    }
338+    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));

elichai commented at 10:07 am on January 26, 2020:

Isn’t .. > 0x3FFFFFFUL still a branch?

gmaxwell commented at 8:55 pm on January 26, 2020:

Not on any compilers, platforms I tested it on. AFAICT. If it is, a LOT of the code is screwed.

in src/field_5x52_impl.h:321 in 82989f565c outdated

317@@ -317,15 +318,15 @@ static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a) {
318             | ((uint64_t)a[2] << 24)
319             | ((uint64_t)a[1] << 32)
320             | ((uint64_t)a[0] << 40);
321-    if (r->n[4] == 0x0FFFFFFFFFFFFULL && (r->n[3] & r->n[2] & r->n[1]) == 0xFFFFFFFFFFFFFULL && r->n[0] >= 0xFFFFEFFFFFC2FULL) {
322-        return 0;
323-    }
324+    ret = !((r->n[4] == 0x0FFFFFFFFFFFFULL) & ((r->n[3] & r->n[2] & r->n[1]) == 0xFFFFFFFFFFFFFULL) & (r->n[0] >= 0xFFFFEFFFFFC2FULL));

elichai commented at 10:08 am on January 26, 2020:

Same for >= 0xFFFFEFFFFFC2FULL

in src/modules/ecdh/main_impl.h:68 in 82989f565c outdated

81+    memset(x, 0, 32);
82+    memset(y, 0, 32);
83     secp256k1_scalar_clear(&s);
84-    return ret;
85+
86+    return !!ret & !overflow;

elichai commented at 10:15 am on January 26, 2020:

FYI this is a change in behavior. before that we returned ret as is, here we check if ret>1 or not. i.e. if someone passes hashfp that returned 5 this function will now return 1 instead of 5 (we use this behavior in rust-secp https://github.com/rust-bitcoin/rust-secp256k1/blob/master/src/ecdh.rs#L162 @apoelstra)

gmaxwell commented at 9:01 pm on January 26, 2020:

You are relying on behavior that directly contradicts the documentation and isn’t tested.

Returns: 1: exponentiation was successful

      0: scalar was invalid (zero or overflow)

Nonce functions have an opaque data, so they can return information in other ways…

In either case the interface should be tested. I knew I was tightening up the behavior to better match the public interface but didn’t consider the existence of bespoke nonce functions that would return something else only that further changes might accidentally return non-0/1 values.

Thanks for noticing this! I consider the return values not agreeing with the docs to be a pretty serious bug, and it’s unfortunate that there aren’t tests for cases where the nonce function induces it. That said, the noncefp docs specify that the return is 0 or 1 too: " * Returns: 1 if a nonce was successfully generated. 0 will cause signing to fail."

sipa commented at 0:52 am on February 1, 2020:

~~Opened an issue here: #710~~

EDIT: I mean here: https://github.com/rust-bitcoin/rust-secp256k1/issues/196

real-or-random commented at 2:51 pm on February 1, 2020:

Opened an issue here: #710

This is a link to this PR here and also I don’t see any other new issue.

apoelstra commented at 5:05 pm on February 1, 2020:

Nice catch. I don’t think I ever considered that a nonce function might return a non-0/1 value. This certainly wasn’t deliberate behaviour in rust-secp, at least on my part.

elichai commented at 5:11 pm on February 1, 2020:

Honestly I thought it was intentional, but I was wrong. Should’ve read the docs more carefully

sipa commented at 7:48 pm on February 1, 2020:

@real-or-random Fixed, it’s https://github.com/rust-bitcoin/rust-secp256k1/issues/196

in src/scalar_8x32_impl.h:721 in 82989f565c outdated

717@@ -718,4 +718,18 @@ SECP256K1_INLINE static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r,
718     secp256k1_scalar_cadd_bit(r, 0, (l[(shift - 1) >> 5] >> ((shift - 1) & 0x1f)) & 1);
719 }
720 
721+static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) {

elichai commented at 10:40 am on January 26, 2020:

~~icc 19.0.1 produces branching in this function https://godbolt.org/z/882jPA~~ (seems to be a check for overlaps and then it either uses vector ops or “regular” ops) and gcc(trunk) with -O3 -march=native uses vmovdqu which might be variable time on AMD Bolldozer according to https://www.agner.org/optimize/instruction_tables.pdf

gmaxwell commented at 9:11 pm on January 26, 2020:

Many of the vector/memory load store instructions can be variable time based on alignment, which wouldn’t be a problem for us. In any case, that code emits vmovdqu32 which is an avx512 instruction, it doesn’t exist on bulldozer.

in src/scalar_4x64_impl.h:949 in 82989f565c outdated

945@@ -946,4 +946,14 @@ SECP256K1_INLINE static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r,
946     secp256k1_scalar_cadd_bit(r, 0, (l[(shift - 1) >> 6] >> ((shift - 1) & 0x3f)) & 1);
947 }
948 
949+static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) {

elichai commented at 10:47 am on January 26, 2020:

Same as below. gcc(trunk) with -O3 -march=native uses vmovdqu64 which might be variable time on AMD bolldozer

gmaxwell commented at 9:12 pm on January 26, 2020:

Again. That is an AVX512 instruction, it doesn’t exist on bulldozer.

in src/secp256k1.c:501 in 82989f565c outdated

503+        }
504+        secp256k1_scalar_set_b32(&non, nonce32, &koverflow);
505+        koverflow |= secp256k1_scalar_is_zero(&non);
506+        /* The nonce is still secret here, but it overflowing or being zero is is less likely than 1:2^255. */
507+        declassify(ctx, &koverflow, sizeof(koverflow));
508+        if (!koverflow) {

elichai commented at 10:53 am on January 26, 2020:

why not cmov on this too? (or just let it overflow? altough that will be a behavior change) if koverflow put 1 into the k and sign, but then clear and return 0

gmaxwell commented at 9:19 pm on January 26, 2020:

Letting it overflow would bias the nonce, which is extremely bad for security. The order of secp256k1 is fortunately such that the bias would not actually be a problem, though this isn’t the case for many other curves. Personally, if I were auditing an someone elses crypto code and saw it producing biased nonces like that I would instant fail the audit and not bother looking at anything else because the software was clearly written people by people who didn’t notice or didn’t heed the pile of dead bodies of their forebearers that thought leaving nonces a little biased was okay.

There isn’t much point in cmoving there because the loop must run again that case, making the function take a non-constant time. So the cmov would just be constant time theatre with no improvement. It would still have to be declassified too, since constant time analysis would notice the loop being conditioned on it– so the cmov would be just pure theater, not actually improve the constant timeness and just adding code.

real-or-random commented at 3:22 pm on February 1, 2020:

Personally, if I were auditing an someone elses crypto code and saw it producing biased nonces like that I would instant fail the audit and not bother looking at anything else because the software was clearly written people by people who didn’t notice or didn’t heed the pile of dead bodies of their forebearers that thought leaving nonces a little biased was okay.

We ignore the overflow in the BIP 340 draft by the way. :X

sipa commented at 7:54 pm on February 1, 2020:

@real-or-random I think the situation is a little different in BIP340, because it’s not using a generic retrying PRG-based approach, but a specified scheme (and curve) specific algorithm, with a rationale explaining that this approach is only safe because the order is so close to 2^256.

If we’d decide that’s worrisome because it may end up being reused for another curve, I’d prefer the EdDSA approach (hash to twice the width, and then modulo reduce it) over an iterative approach.

real-or-random commented at 5:07 pm on February 3, 2020:

Well I personally think it’s okay to assume in the context of a specific curve in the end. I’m just not sure if there’s a real difference to BIP340 because here also assume a specific curve.

real-or-random commented at 6:48 pm on February 3, 2020:

I’d also be fine with the more radical approach of eliminating the loop. This does not need to be done by ignoring the overflow, we could alternatively simply fail.

jonasnick commented at 2:19 pm on February 7, 2020:

The schnorrsig implementation matches the BIP and does not fail nor retry on overflow (but on 0). That means as is, we wouldn’t necessarily need to declassify in schnorrsig_sign and could instead continue with the 0 nonce and memczero the signature before returning 0.

in src/util.h:164 in 82989f565c outdated

159@@ -160,4 +160,16 @@ static SECP256K1_INLINE void *manual_alloc(void** prealloc_ptr, size_t alloc_siz
160 SECP256K1_GNUC_EXT typedef unsigned __int128 uint128_t;
161 #endif
162 
163+/* Zero memory if flag == 1. Constant time. */
164+static SECP256K1_INLINE void memczero(void *s, size_t len, int flag) {

elichai commented at 10:56 am on January 26, 2020:

why not just unsigned char flag? why int and then case?

elichai commented at 10:56 am on January 26, 2020:

And I like the idea here :)

gmaxwell commented at 9:21 pm on January 26, 2020:

int is more efficient on many platforms than char (which would require masking), and this is a consistent interface with cmov.

in src/secp256k1.c:518 in 82989f565c outdated

536+    secp256k1_scalar_clear(&msg);
537+    secp256k1_scalar_clear(&non);
538+    secp256k1_scalar_clear(&sec);
539+    secp256k1_ecdsa_signature_save(signature, &r, &s);
540+    memczero(signature, sizeof(*signature), (!ret) | overflow);
541+    return !!ret & !overflow;

elichai commented at 10:57 am on January 26, 2020:

Same behavior change on ret

gmaxwell commented at 9:25 pm on January 26, 2020:

Returns: 1: signature created

      0: the nonce generation function failed, or the private key was invalid.

Fixes a bug. Like above behavior should get a test.

gmaxwell commented at 1:14 am on February 11, 2020:

I opened an issue.

elichai commented at 11:02 am on January 26, 2020: contributor

I reviewed all the cmov implementations in godbolt with latest 3 versions of gcc,clang,icc and WINE MSVC 2017 x64

Personally I’d prefer to split between the changes and the valgrind addition./

I like that the valgrind call is wrapped in #if defined(VALGRIND) but Idk about the addition of int to the context just for this, but I don’t feel knowledgeable enough to comment on this seriously.

sipa cross-referenced this on Feb 1, 2020 from issue secp256k1_ecdh_hash_function must return 0 or 1 by sipa

in src/secp256k1.c:503 in 7c28ecc152 outdated

500+        koverflow |= secp256k1_scalar_is_zero(&non);
501+        /* The nonce is still secret here, but it overflowing or being zero is is less likely than 1:2^255. */
502+        declassify(ctx, &koverflow, sizeof(koverflow));
503+        if (!koverflow) {
504+            int success = secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, NULL);
505+            /* The final signature is no longer a secret. */

sipa commented at 1:07 am on February 1, 2020:

Nit: while true, it’s not the signature that’s being declassified here, but whether or not one was produced.

sipa commented at 1:08 am on February 1, 2020: contributor

Concept ACK, nothing seems painfully invasive here or detrimental to performance.

real-or-random commented at 3:22 pm on February 1, 2020: contributor

I’ll have a closer look next week.

in src/eckey_impl.h:82 in bf40d0f1b6 outdated

81+    int ret;
82+    ret = !secp256k1_scalar_is_zero(tweak);
83 
84     secp256k1_scalar_mul(key, key, tweak);
85-    return 1;
86+    return ret;

real-or-random commented at 3:28 pm on February 3, 2020:

note: This is superficially related to #701 because now this does the tweaking even if the tweak is zero, which funnily zeroizes the key then (even if we will decide that the public wrapper function won’t.)

in src/ecdsa_impl.h:311 in bf40d0f1b6 outdated

314-            *recid ^= 1;
315-        }
316+    high = secp256k1_scalar_is_high(sigs);
317+    secp256k1_scalar_cond_negate(sigs, high);
318+    if (recid) {
319+            *recid ^= high;

real-or-random commented at 3:32 pm on February 3, 2020:

This is another instance where we assume that a function (secp256k1_scalar_is_high) returns only 0/1. In general, it would be good to document this and have simple explicit tests for this.

real-or-random commented at 4:27 pm on February 3, 2020:

Actually, is this a general convention for every “boolean” function in the codebase?

gmaxwell commented at 7:21 am on February 4, 2020:

Yes. And the tests do check that:

    /* Check that comparison with the half order is equal to testing for high scalar. */
    CHECK(secp256k1_scalar_is_high(&s) == (secp256k1_num_cmp(&snum, &half_order) > 0));
    /* Check that comparison with the half order is equal to testing for high scalar after negation. */
    CHECK(secp256k1_scalar_is_high(&neg) == (secp256k1_num_cmp(&negnum, &half_order) > 0));

For an “is” function is there any other logical return that might show up?

real-or-random commented at 3:41 pm on February 6, 2020:

For an “is” function is there any other logical return that might show up? I think a lot of C code doesn’t bother to return exactly 1 and will be fine with every non-zero value instead, which is not an unreasonable choice.

General convention: Okay, then we should double-check this and document it… (another PR of course).

Tests: Yes, I’ve seen those. My feeling was that it’s not very explicit but yes, it’s there.

in src/scalar_impl.h:28 in 2a81949b9e outdated

23@@ -24,6 +24,9 @@
24 #error "Please select scalar implementation"
25 #endif
26 
27+static const secp256k1_scalar secp256k1_scalar_one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1);
28+static const secp256k1_scalar secp256k1_scalar_zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);

real-or-random commented at 4:51 pm on February 3, 2020:

Is the zero used anywhere?

gmaxwell commented at 7:21 am on February 4, 2020:

src/secp256k1.c: secp256k1_scalar_cmov(&sec, &secp256k1_scalar_zero, !ret); src/secp256k1.c: secp256k1_scalar_cmov(&sec, &secp256k1_scalar_zero, !ret);

in src/secp256k1.c:141 in 2a81949b9e outdated

137@@ -132,6 +138,7 @@ secp256k1_context* secp256k1_context_preallocated_create(void* prealloc, unsigne
138     if (flags & SECP256K1_FLAGS_BIT_CONTEXT_VERIFY) {
139         secp256k1_ecmult_context_build(&ret->ecmult_ctx, &prealloc);
140     }
141+    ret->declassify = !!(flags & SECP256K1_FLAGS_BIT_CONTEXT_DECLASSIFY);

real-or-random commented at 6:47 pm on February 3, 2020:

nit: you don’t need the !! here

real-or-random commented at 11:11 am on February 11, 2020:

@gmaxwell Can you reply to this one? Ignoring it by clicking “resolve conversation” counts as a reply. :)

gmaxwell commented at 12:29 pm on February 11, 2020:

lol Github was helpfully hiding this one from me, I only found it because you said two… :)

I don’t like having an apparently boolean variable have its truth value be other than one. It would totally be fine to not !! here with the current code, but then later we go and refactor something and the boolean test gets turned into an ==1 or used in an arithmetic expression and it works incorrectly.

So in general, I usually tend to boolenize a boolean variable unless its never used outside of a single scope, or in some performance critical inner loop where the single test opcode might actually matter. Though for flags the more ordinary way to booleanize is (flags & flag) == flag.

real-or-random commented at 12:31 pm on February 11, 2020:

Nevermind, I got the semantics wrong here.

in src/secp256k1.c:229 in 2a81949b9e outdated

221@@ -215,6 +222,20 @@ void secp256k1_scratch_space_destroy(const secp256k1_context *ctx, secp256k1_scr
222     secp256k1_scratch_destroy(&ctx->error_callback, scratch);
223 }
224 
225+/* Mark memory as no-longer-secret for the purpose of analysing constant-time behaviour
226+ *  of the software. This is setup for use with valgrind but could be substituted with
227+ *  the appropriate instrumentation for other analysis tools.
228+ */
229+static SECP256K1_INLINE void declassify(const secp256k1_context* ctx, void *p, size_t len) {

real-or-random commented at 6:48 pm on February 3, 2020:

I think this should be called secp256k1_declassify. Or maybe not? We also don’t have the prefix in util.h, hm.

gmaxwell commented at 7:23 am on February 4, 2020:

It’s static inline, so it shouldn’t matter. I don’t care one way or another, utility functions don’t seem to be.

real-or-random commented at 9:28 am on February 8, 2020:

I suggest moving this to util.h then.

gmaxwell commented at 1:01 am on February 11, 2020:

okay.

gmaxwell commented at 1:10 pm on February 11, 2020:

un-okay: I changed this and blew CI up… ctx is an opaque type in util.h when util.h is being used in benchmarks and such, causing them to fail to compile. I didn’t like hoisting out the ctx-> dereference because I want that compiled out when not compiled with DVALGRIND, and changing things so util.h could see the non-opaque type made a mess when I briefly attempted it. When I said okay, I didn’t really care either way. I found reasons to care.

in src/secp256k1.c:490 in 2a81949b9e outdated

506+        /* The nonce is still secret here, but it overflowing or being zero is is less likely than 1:2^255. */
507+        declassify(ctx, &koverflow, sizeof(koverflow));
508+        if (!koverflow) {
509+            int success = secp256k1_ecdsa_sig_sign(&ctx->ecmult_gen_ctx, &r, &s, &sec, &msg, &non, NULL);
510+            /* The final signature is no longer a secret. */
511+            declassify(ctx, &success, sizeof(success));

real-or-random commented at 6:58 pm on February 3, 2020:

Here we have success == ret. So we could simply get rid of success (or alternatively VERIFY that success == ret). I think this matters here for the reader because we also “declassify” ret in a sense but that’s not obvious.

real-or-random commented at 11:10 am on February 11, 2020:

@gmaxwell Can you reply to this one?

gmaxwell commented at 12:44 pm on February 11, 2020:

okay, I didn’t understand your comment at first because I was (and am) completely unable to get github to display any context for it. I understand it now, reasonable enough.

in src/secp256k1.c:516 in 2a81949b9e outdated

535+    memset(nonce32, 0, 32);
536+    secp256k1_scalar_clear(&msg);
537+    secp256k1_scalar_clear(&non);
538+    secp256k1_scalar_clear(&sec);
539+    secp256k1_ecdsa_signature_save(signature, &r, &s);
540+    memczero(signature, sizeof(*signature), (!ret) | overflow);

real-or-random commented at 7:01 pm on February 3, 2020:

If we declassify !ret | overflow here, then we can get rid of the call to memczero, which is probably not for free. Is there a reason why you preferred the call? It’s easy to see that the declassification is not an issue. ret is already declassified (see my comment above) and overflow will anyway be zero.

gmaxwell commented at 7:30 am on February 4, 2020:

It would then be replaced with a regular memset which I doubt would be significantly slower. My preference was to make it actually constant time unless it had a non-trivial cost.

I can give a contrived attack against secret overflow: If I can give you a tweak that you apply to you secret key with naive addition, and I can query you log(n) times, I can use the time signing takes to read off your secret key. It’s contrived not only because of the bad tweak function, but also because it assumes I can’t distinguish your failures by some way other than time.

real-or-random commented at 9:32 am on February 8, 2020:

It would then be replaced with a regular memset which I doubt would be significantly slower. My preference was to make it actually constant time unless it had a non-trivial cost.

Makes sense to me.

in src/valgrind_ctime_test.c:34 in 2a81949b9e outdated

29+        fprintf(stderr, "This test can only usefully be run inside valgrind.\n");
30+        fprintf(stderr, "Usage: libtool --mode=execute valgrind ./valgrind_ctime_test\n");
31+        exit(1);
32+    }
33+
34+    /** In theory, testing with a single secret input should be sufficient:

real-or-random commented at 7:09 pm on February 3, 2020:

True but here you set the message, which is not a secret input.

gmaxwell commented at 7:32 am on February 4, 2020:

Other PR. :)

real-or-random commented at 7:09 pm on February 3, 2020: contributor

Let me repeat that this great stuff and very helpful.

jonasnick commented at 10:11 pm on February 10, 2020: contributor

Needs rebase, but otherwise looks good to me.

gmaxwell commented at 1:20 am on February 11, 2020: contributor

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 commented at 5:38 am on February 11, 2020: contributor

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 commented at 11:15 am on February 11, 2020: contributor

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 commented at 12:38 pm on February 11, 2020: contributor

I think you also missed that one: #710 (review)

gmaxwell commented at 12:46 pm on February 11, 2020: contributor

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

jonasnick approved

jonasnick commented at 1:42 pm on February 11, 2020: contributor

ACK 3eb69f6d1a917079131b415c4e92ea45259ec641

in src/secp256k1.c:517 in 3eb69f6d1a outdated

534-    return ret;
535+    memset(nonce32, 0, 32);
536+    secp256k1_scalar_clear(&msg);
537+    secp256k1_scalar_clear(&non);
538+    secp256k1_scalar_clear(&sec);
539+    secp256k1_ecdsa_signature_save(signature, &r, &s);

real-or-random commented at 12:52 pm on February 12, 2020:

This reads uninitialized memory if the nonce function returned 0.

We could now start a long discussion if this yields UB (see in #699 (comment)). But I think it’s preferable to just avoid the situation entirely by cmoving zero scalars into r and s before calling secp256k1_ecdsa_signature_save instead of cmoving zero bytes afterwards.

gmaxwell commented at 5:34 pm on February 20, 2020:

It would be a bad use of the internal api to send it uninitialized data regardless. Thanks for noticing this, fixed.

in src/ecmult_gen_impl.h:188 in 3eb69f6d1a outdated

189-        retry = !secp256k1_fe_set_b32(&s, nonce32);
190-        retry = retry || secp256k1_fe_is_zero(&s);
191-    } while (retry); /* This branch true is cryptographically unreachable. Requires sha256_hmac output > Fp. */
192+    /* Accept unobservably small non-uniformity. */
193+    secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32);
194+    range = !secp256k1_fe_set_b32(&s, nonce32);

real-or-random commented at 1:04 pm on February 12, 2020:

nit: range is typically called overflow in other code here. range is a somewhat ambiguous identifier because it’s not clear whether it means “in range” or “out of range”.

gmaxwell commented at 5:34 pm on February 20, 2020:

Fair enough.

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)

34a67c773b

Adds a declassify operation to aid constant-time analysis.

ECDSA signing has a retry loop for the exceptionally unlikely case
 that S==0.  S is not a secret at this point and this case is so
 rare that it will never be observed but branching on it will trip
 up tools analysing if the code is constant time with respect to
 secrets.

Derandomized ECDSA can also loop on k being zero or overflowing,
 and while k is a secret these cases are too rare (1:2^255) to
 ever observe and are also of no concern.

This adds a function for marking memory as no-longer-secret and
 sets it up for use with the valgrind memcheck constant-time
 test.

7b50483ad7

jonasnick approved

jonasnick commented at 9:56 am on February 21, 2020: contributor

reACK 7b50483ad789081ba158799e5b94330f62932607

sipa commented at 4:34 am on February 22, 2020: contributor

utACK 7b50483ad789081ba158799e5b94330f62932607

real-or-random commented at 1:01 pm on February 24, 2020: contributor

ACK 7b50483ad789081ba158799e5b94330f62932607 I read the code carefully and tested it

real-or-random approved

real-or-random merged this on Feb 24, 2020

real-or-random closed this on Feb 24, 2020

real-or-random cross-referenced this on Mar 4, 2020 from issue Erroneous comment and VERIFY_CHECK in ecdsa_sig_sign by LLFourn

jonasnick cross-referenced this on Mar 7, 2020 from issue Make ec_ arithmetic more consistent and add documentation by jonasnick

benma cross-referenced this on Apr 21, 2020 from issue rebase on bitcoin-core/secp256k1 by benma

elichai cross-referenced this on May 3, 2020 from issue Add macOS to the CI by elichai

elichai cross-referenced this on May 11, 2020 from issue Constant-time tests for libsecp256k1 by unseddd

elichai cross-referenced this on May 13, 2020 from issue Bump libsecp256k1 by elichai

elichai cross-referenced this on May 27, 2020 from issue Recovery signing: add to constant time test, and eliminate non ct operators by elichai

real-or-random referenced this in commit 2ed54da18a on Jun 8, 2020

sipa cross-referenced this on Jun 9, 2020 from issue Update libsecp256k1 subtree by sipa

fanquake referenced this in commit 8c97780db8 on Jun 13, 2020

sidhujag referenced this in commit 8a3a072968 on Jun 13, 2020

ComputerCraftr referenced this in commit b98f1c6e6c on Jun 16, 2020

UdjinM6 referenced this in commit 9d36ba6570 on Aug 10, 2021

5tefan referenced this in commit 8ded2caa74 on Aug 12, 2021

gades referenced this in commit d855cc511d on May 8, 2022

theStack cross-referenced this on May 29, 2023 from issue refactor: take use of `secp256k1_scalar_{zero,one}` constants by theStack

real-or-random referenced this in commit debf3e5c08 on May 31, 2023

Eliminate harmless non-constant time operations on secret data. #710