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 #767 (comment)

[real-or-random]

This is where we secp256k1_gej_rescale now in secp256k1_ecmult_gen_blind:

secp256k1/src/ecmult_gen_impl.h

Lines 191 to 192 in 98dac87

	/* Randomize the projection to defend against multiplier sidechannels. */
	secp256k1_gej_rescale(&ctx->initial, &s);

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

secp256k1/src/group_impl.h

Lines 184 to 189 in 98dac87

	static void secp256k1_gej_set_infinity(secp256k1_gej *r) {
	r->infinity = 1;
	secp256k1_fe_clear(&r->x);
	secp256k1_fe_clear(&r->y);
	secp256k1_fe_clear(&r->z);
	}

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