Use blinded instead of constant time inverse in secret gej->ge? #694

1. 
   gmaxwell commented at 2:20 am on November 14, 2019: contributor

   Currently the conversion from projective to affine in pubkey creation, signing, and ECDH use a constant time ladder inverse because the z value conceivably leaks information. This applies even in the pubkey and signing case where the resulting point is made public.

   The constant time inverse is much slower than the best variable time inverse.

   If the point is rescaled with a uniformly random value via secp256k1_gej_rescale (at the cost of four multiplies and a square) then z becomes uniformly random and thus inverting it cannot leak any information at all. Blinding in this way is arguably more secure against EMI/DPA sidechannels because the slow ladder inverse does a lot of operations and has more potential to leak than a couple used for blinding.

   Benchmarking schnorr signing using this and the GMP inverse gives me a speedup of 1.15x, though that isn’t including the time to come up with a random value.

2. 
   apoelstra commented at 3:32 pm on November 22, 2019: contributor

   concept ACK. An open question is where to source randomness from.
3. 
   elichai commented at 6:20 pm on November 22, 2019: contributor

   What do you think about making this optional iff the user used context randomization? That way we have a seed to use (can apply chacha or some other PRF on the seed)
4. 
   gmaxwell commented at 4:33 am on November 23, 2019: contributor

   Well we always have randomness in these cases– because we have a secret. :) But just running an extra sha2 compression function run would be pretty bad for performance.
5. bitcoin-core deleted a comment on Jun 16, 2020
6. bitcoin-core deleted a comment on Jun 16, 2020
7. 
   real-or-random commented at 1:46 pm on January 27, 2021: contributor

   I think we should revisit this issue once #831 has been merged, see also the discussion in #767 (comment)
8. 
   sipa commented at 6:38 pm on January 27, 2021: contributor

   With #831 + the hddivsteps improvement, I think the difference between vartime and consttime inverses is much smaller (around 1.8 us vs 1.2 us on my Zen+ CPU, where signing overall is around 30 us). Not sure it’s worth dropping consttime just for performance reasons. It may still be worth doing this for extra blinding, though.
9. 
   gmaxwell commented at 7:17 pm on January 27, 2021: contributor

   That’s my thought, I think there isn’t a reason to drop the constant time anymore, but it would perhaps still be good to add more blinding.

Contributors
gmaxwell apoelstra elichai real-or-random sipa