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.
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. */
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);
0 unsigned int mask0, mask1;
1 mask0 = flag + ~((unsigned int)0);
or shorter
0 unsigned int mask0, mask1;
1 mask0 = flag + ~0u;
is probably cleaner to review and more portable because unsigned int is guaranteed to have the same bitlength as int.
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.
a equal INT_MIN and INT_MAX?
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
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.
VERIFY that inputs are nonnegative and a comment why this VERIFY makes sense?
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+}
I’m sure people won’t like this but this is perfectly well-defined. :p
0static SECP256K1_INLINE void secp256k1_int_cmov(int *r, const int *a, int flag) {
1 int mask0, mask1;
2 mask0 = 1 - flag;
3 mask1 = flag;
4 *r = (*r * mask0) + (*a * mask1);
5}
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. ;)
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
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;
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);
recid being secret, it’s ret being secret.
(ret includes the validity of seckey so we don’t want to branch over it)
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
@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.