Recovery signing: add to constant time test, and eliminate non ct operators #755

elichai commented at 8:08 AM on May 27, 2020: contributor

Hi, The recovery module was overlooked in #708 and #710, so this adds it to the valgrind_ctime_test and replaces the secret dependent branching with the cmovs, I created a new function secp256k1_ecdsa_sign_inner (feel free to bikeshed) which does the logic both for ecdsa_sign and for ecdsa_sign_recoverable, such that next time when things get changed/improved in ecdsa it will affect the recoverable signing too.

elichai renamed this:
~~Recovery sign, add to constant time test, and eliminate non ct operators.~~
Recovery signning: add to constant time test, and eliminate non ct operators.
on May 27, 2020

in src/util.h:178 in 8ebf3d120a outdated

 174 | @@ -175,4 +175,12 @@ static SECP256K1_INLINE void memczero(void *s, size_t len, int flag) {
 175 |      }
 176 |  }
 177 |  
 178 | +/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. */

real-or-random commented at 1:54 PM on May 27, 2020:

nit: comment should also cover requirement to be defined, similar as in #754

elichai commented at 4:05 PM on May 27, 2020:

You're right :D fixed.

real-or-random commented at 1:55 PM on May 27, 2020: contributor

ACK except nit

elichai force-pushed on May 27, 2020

in src/util.h:181 in 59709b7268 outdated

 174 | @@ -175,4 +175,12 @@ static SECP256K1_INLINE void memczero(void *s, size_t len, int flag) {
 175 |      }
 176 |  }
 177 |  
 178 | +/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time.  Both *r and *a must be initialized.*/
 179 | +static SECP256K1_INLINE void secp256k1_int_cmov(int *r, const int *a, int flag) {
 180 | +    uint32_t mask0, mask1;
 181 | +    mask0 = flag + ~((uint32_t)0);

real-or-random commented at 9:17 AM on May 28, 2020:

    unsigned int mask0, mask1;
    mask0 = flag + ~((unsigned int)0);

or shorter

    unsigned int mask0, mask1;
    mask0 = flag + ~0u;

is probably cleaner to review and more portable because unsigned int is guaranteed to have the same bitlength as int.

elichai commented at 5:05 PM on May 28, 2020:

I wonder now if I'm sure this function is 100% safe for signed integers (I'll need to look again at the integer promotion rules etc) I think it is safe though? (flag will probably be promoted to unsigned, and then the overflow will be safe and I think all AND operations on ints are safe )

real-or-random commented at 5:12 PM on May 28, 2020:

I thought about this too.

(flag will probably be promoted to unsigned, and then the overflow will be safe and I think all AND operations on ints are safe )

Indeed, this was my understanding, too! (flag will not be "promoted" it will be "converted" to unsigned but this is just wording). The same is true in (*r & mask0) where *r will be converted to unsigned, and the same for (*a & mask1), so everything on the right-hand side of the final assignment is unsigned arithmetic.

jonasnick commented at 9:09 PM on May 29, 2020:

Would it make sense to test this function with a equal INT_MIN and INT_MAX?

real-or-random commented at 10:46 AM on May 30, 2020:

I guess it can't hurt and it's cheap to do.

elichai commented at 10:06 AM on May 31, 2020:

I'll add a test, FYI passing some flags to clang shows us exactly how the conversions happen here: https://godbolt.org/z/t9GHKK

Though I wouldn't mind changing it to something like this: https://godbolt.org/z/BKQqxf

jonasnick commented at 4:06 PM on May 31, 2020:

Yeah explicit conversions would be nice. PR looks good. Thanks for the tests.

elichai commented at 2:18 PM on June 1, 2020:

argh, this cmov is implementation defined for any negative value :/ See http://port70.net/~nsz/c/c89/c89-draft.html#3.2.1.2

an unsigned integer is converted to its corresponding signed integer, if the value cannot be represented the result is implementation-defined.

So even (int)(unsigned int)(-1) is implementation defined behavior.

real-or-random commented at 3:38 PM on June 2, 2020:

Yeah, even though all non-obscure C implementations will do the most efficient thing possible, i.e., make the cast a noop on the bit level, which implies that casting back and forth is fine. So it will probably never be a problem for us. But it's cleaner not to rely on it. I suggest we simply VERIFY that inputs are nonnegative and a comment why this VERIFY makes sense?

elichai commented at 3:40 PM on June 2, 2020:

Yeah, people on ##C in freenode told me I'm being overly paranoid lol, VERIFY is more than enough

elichai force-pushed on May 31, 2020

in src/util.h:209 in 009a515800 outdated

 179 | +static SECP256K1_INLINE void secp256k1_int_cmov(int *r, const int *a, int flag) {
 180 | +    unsigned int mask0, mask1;
 181 | +    mask0 = flag + ~0u;
 182 | +    mask1 = ~mask0;
 183 | +    *r = (*r & mask0) | (*a & mask1);
 184 | +}

real-or-random commented at 3:53 PM on June 2, 2020:

I'm sure people won't like this but this is perfectly well-defined. :p

static SECP256K1_INLINE void secp256k1_int_cmov(int *r, const int *a, int flag) {
    int mask0, mask1;
    mask0 = 1 - flag;
    mask1 = flag;
    *r = (*r * mask0) + (*a * mask1);
}

elichai commented at 4:02 PM on June 2, 2020:

Nice! Interesting to think of a cmov using arithmetic and not bitwise masking. Why won't people like it?

real-or-random commented at 4:09 PM on June 2, 2020:

Interesting to think of a cmov using arithmetic and not bitwise masking.

You see that often in pseudocode.

Why won't people like it?

Integer multiplication is slower than &. But psst, let's not start the discussion and go with the VERIFY. ;)

real-or-random commented at 4:09 PM on June 2, 2020: contributor

need rebase

elichai force-pushed on Jun 2, 2020

elichai commented at 4:18 PM on June 2, 2020: contributor

I first fixed the comments from #755 (review) so it will be easy to see the diff(https://github.com/bitcoin-core/secp256k1/compare/009a515800ddcb76230a5fd49a78c4ce22fae23b..dcc80cf985dfed5659699eca2f830857b5a42497)

Now I'll rebase

elichai force-pushed on Jun 2, 2020

real-or-random approved

real-or-random commented at 5:56 PM on June 2, 2020: contributor

ACK 9e6287ffbd3598451b6689c51b876fb41134ad75 I inspected the diff and tested it

in src/secp256k1.c:528 in 9e6287ffbd outdated

 525 | +    return ret;
 526 | +}
 527 | +
 528 | +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) {
 529 | +    /* Default initialization here is important so we won't pass uninit values to the cmov in the end */
 530 | +    secp256k1_scalar r = secp256k1_scalar_zero, s = secp256k1_scalar_zero;

jonasnick commented at 9:45 AM on June 3, 2020:

Is initializing twice intentional? Looks more like this crept in during the rebase.

elichai commented at 10:18 AM on June 3, 2020:

Yep, crept in when rebased. Thanks

Split ecdsa_sign logic into a new function and use it from ecdsa_sign and recovery 2876af4f8d

Add ecdsa_sign_recoverable to the ctime tests 73596a85a2

Add tests for the cmov implementations 28609507e7

elichai force-pushed on Jun 3, 2020

jonasnick approved

jonasnick commented at 8:05 PM on June 3, 2020: contributor

ACK 28609507e70a172dd8f39de4aa55f851452fc0b4

sipa renamed this:
~~Recovery signning: add to constant time test, and eliminate non ct operators.~~
Recovery signing: add to constant time test, and eliminate non ct operators
on Jun 5, 2020

in src/secp256k1.c:521 in 2876af4f8d outdated

 518 | -    secp256k1_scalar_cmov(&s, &secp256k1_scalar_zero, !ret);
 519 | +    secp256k1_scalar_cmov(r, &secp256k1_scalar_zero, !ret);
 520 | +    secp256k1_scalar_cmov(s, &secp256k1_scalar_zero, !ret);
 521 | +    if (recid) {
 522 | +        const int zero = 0;
 523 | +        secp256k1_int_cmov(recid, &zero, !ret);

sipa commented at 9:38 PM on June 5, 2020:

Why? recid is not secret.

elichai commented at 9:49 PM on June 5, 2020:

The problem isn't recid being secret, it's ret being secret. (ret includes the validity of seckey so we don't want to branch over it)

sipa commented at 10:53 PM on June 5, 2020:

I don't think there is much of an issue with declassifying ret. If the API is used correctly, ret is always 1 anyway.

elichai commented at 10:57 PM on June 5, 2020:

If we assume a user won't call sign_* without verifying the secret key first then yeah we can declassify is_sec_valid (which is what contaminates ret) https://github.com/bitcoin-core/secp256k1/blob/a39c2b09de304b8f24716b59219ae37c2538c242/src/secp256k1.c#L510-L513

real-or-random commented at 8:38 AM on June 6, 2020:

@sipa This is not the scope of this PR. If we want to change this, I think that's a different discussion.

The current signing code on master is overly cautious and assumes is_sec_valid to be a secret. That's exactly the reason why we cmov r and s (introduced by #710), see also the corresponding code comment and the exact reasoning in the PR.

sipa commented at 3:47 AM on June 8, 2020:

@real-or-random Thanks for the references, that makes sense. My point was mostly that at some point, the complexity of removing decreasingly relevant forms of non-ctness aren't worth it, but this isn't too bad yet.

real-or-random approved

real-or-random commented at 5:49 PM on June 6, 2020: contributor

ACK 28609507e70a172dd8f39de4aa55f851452fc0b4 read the diff, tested with valgrind including ctime tests

real-or-random merged this on Jun 8, 2020

real-or-random closed this on Jun 8, 2020

elichai deleted the branch 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

jasonbcox referenced this in commit 760e829200 on Sep 27, 2020

deadalnix referenced this in commit 360fbf6112 on Sep 28, 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