Use bit ops instead of int mult for constant-time logic in gej_add_ge #882

pull real-or-random wants to merge 1 commits into bitcoin-core:master from real-or-random:202101-bitops-gej-add changing 1 files +1 −1

real-or-random commented at 4:03 PM on January 28, 2021: contributor

Nothing is wrong with the current implementation. But it looks out of place because we generally prefer bit operations because they're faster and are more likely constant-time.
Use bit ops instead of int mult for constant-time logic in gej_add_ge e491d06b98
real-or-random force-pushed on Jan 30, 2021
sipa commented at 8:42 PM on January 30, 2021: contributor

utACK e491d06b98c9caa5eab74e38ba8419b9fb3b5015. Seems obviously better.

in src/group_impl.h:594 in e491d06b98

 590 | @@ -591,7 +591,7 @@ static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const
 591 |      secp256k1_fe_cmov(&n, &m, degenerate);              /* n = M^3 * Malt (2) */
 592 |      secp256k1_fe_sqr(&t, &rr_alt);                      /* t = Ralt^2 (1) */
 593 |      secp256k1_fe_mul(&r->z, &a->z, &m_alt);             /* r->z = Malt*Z (1) */
 594 | -    infinity = secp256k1_fe_normalizes_to_zero(&r->z) * (1 - a->infinity);
 595 | +    infinity = secp256k1_fe_normalizes_to_zero(&r->z) & ~a->infinity;

elichai commented at 11:07 PM on January 30, 2021:

Isn't & !a->infinity clearer?

real-or-random commented at 12:45 PM on January 31, 2021:

I can't show you any evidence right but from my experience ! is much more likely to make compilers introduce branches.

elichai commented at 5:49 PM on January 31, 2021:

We already assume it is constant time in a few places:

$ rg "&= !"
src/modules/schnorrsig/main_impl.h
159:    ret &= !!noncefp(buf, msg32, seckey, pk_buf, bip340_algo16, ndata);
161:    ret &= !secp256k1_scalar_is_zero(&k);

src/secp256k1.c
370:    ret &= !overflow;
372:    ret &= !overflow;

src/tests_exhaustive.c
281:                    should_verify &= !secp256k1_scalar_is_high(&s_s);

src/modules/recovery/main_impl.h
49:    ret &= !overflow;
51:    ret &= !overflow;

src/modules/recovery/tests_exhaustive_impl.h
124:                    should_verify &= !secp256k1_scalar_is_high(&s_s);

sipa commented at 2:21 AM on February 1, 2021:

@elichai Compilers don't translate every C operator the same way. We know the current code works (valgrind ctime test) with common compilers on common platforms, but that's no guarantee for the future, or a guarantee that a ~ is never compiled into a branch in other contexts.

There is no downside to using ~, right?

elichai commented at 8:01 AM on February 1, 2021:

I guess you're right. And I believe @real-or-random when he says that ! is more likely to introduce branches :)

real-or-random commented at 9:48 AM on February 1, 2021:

Good remark that we use ! other places, I wasn't really aware of this anymore. But ok, I'd say let's keep it then.

elichai commented at 8:01 AM on February 1, 2021: contributor

ACK e491d06b98c9caa5eab74e38ba8419b9fb3b5015
jonasnick commented at 10:22 AM on February 1, 2021: contributor

ACK e491d06b98c9caa5eab74e38ba8419b9fb3b5015
jonasnick merged this on Feb 1, 2021
jonasnick closed this on Feb 1, 2021
Fabcien referenced this in commit cda247c5f7 on Apr 8, 2021
deadalnix referenced this in commit d0f691d45d on Apr 9, 2021

Contributors