Rescale initial point before every ecmult

real-or-random commented at 9:36 am on January 28, 2021: contributor

[…] right now the ecmult_gen uses a random projection for the initial point (secp256k1_gej_rescale). ([…] the rescale currently only happens on randomize– but that is already something that should get fixed independent of anything being done with the inversion).

Originally posted by @gmaxwell in #767 (comment)

real-or-random renamed this:
~~Rescale initinal point before every ecmult_gen~~
Rescale initial point before every ecmult_gen
on Jan 28, 2021

real-or-random commented at 10:08 am on January 28, 2021: contributor

This is where we secp256k1_gej_rescale now in secp256k1_ecmult_gen_blind: https://github.com/bitcoin-core/secp256k1/blob/98dac87839838b86094f1bccc71cc20e67b146cc/src/ecmult_gen_impl.h#L191-L192 This is only called when contexts are created (or at build time for static precomp) and secp256k1_context_randomize.

So this is blinding but the blinding value is fixed across all multiplications. In particular, the z-coordinate will always be the same for the first step of the scalar multiplication, which processes the MSBs of the scalar. (The more steps we do, the more z-coord of the accumulator point will randomized, even though this is not easy to reason about due to our addition formula.)

The proposal is to call secp256k1_gej_rescale(&ctx->initial, ...) at the beginning of every ecmult_gen multiplication. The randomness can derived from the secrets available in the current high-level operation, i.e., the seckey during pubkey generation, and seckey||message during signing.

sipa commented at 10:57 pm on January 28, 2021: contributor

If it’s derived from the seckey and/or message (and not from a counter or other mutable data), there is no need to modify the actual in-context initial point though. The rescaling could be done on a local copy instead.

real-or-random commented at 8:58 am on January 29, 2021: contributor

If it’s derived from the seckey and/or message (and not from a counter or other mutable data), there is no need to modify the actual in-context initial point though. The rescaling could be done on a local copy instead.

In fact that’s what I have in mind. (I admit it’s not what I wrote when I wrote secp256k1_gej_rescale(&ctx->initial, ...). So the idea is to rescale the initial accumulator in secp256k1_ecmult_gen() after initializing it as a copy of ctx->initial.

Ok, I think I could open a PR then.

sipa commented at 9:14 am on January 29, 2021: contributor

Perhaps after #693? The ecmult_gen code gets changed a lot.

real-or-random commented at 9:30 am on January 29, 2021: contributor

Oh yes. That’s again what I had in mind yesterday. But apparently I can’t even remember things for 24h anymore when I don’t write them down.

real-or-random commented at 8:08 pm on January 29, 2021: contributor

maybe also look into making it so that the constant time ge_add preserves z when landing on infinity?

Good point. And I think that’s fine. From looking at the code, it seems we don’t have any invariant that imposes requirements on the coordinates when the infinity flag is set. (But then I wonder why we clear the coordinates here:) https://github.com/bitcoin-core/secp256k1/blob/98dac87839838b86094f1bccc71cc20e67b146cc/src/group_impl.h#L184-L189

gmaxwell commented at 0:54 am on January 30, 2021: contributor

So that they don’t end up floating around uninitialized and mixing uninitialized stuff in places (harmlessly and even without causing valgrind to complain, but it’s a pita to reason about).

real-or-random cross-referenced this on Dec 26, 2021 from issue Random isomorphism blinding for ecmult_gen by peterdettman

apoelstra cross-referenced this on Jan 27, 2022 from issue Context randomization tracking issue by apoelstra

Rescale initial point before every ecmult_gen #881