Rescale initial point before every ecmult_gen

[real-or-random]

[...] 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 https://github.com/bitcoin-core/secp256k1/pull/767#issuecomment-679110697

[real-or-random]

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]

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]

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]

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

[real-or-random]

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]

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]

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).