One of the main points in the root causes discussion is that without complete formulas you are almost always going to leak the bit-length, so the only way to not be vulnerable in that case is to fix the bit-length to a constant value. This cannot be done naively by simply setting the high bit, because this would introduce bias in the nonces which would be exploitable even without measuring the duration, a much worse attack! However it can be done via the method suggested by Brumley & Tuveri in https://eprint.iacr.org/2011/232 where you add a multiple of the curve order to the scalar to fix its bit-length. This means the distribution of the nonce modulo the order remains the same (uniform, no bias) yet the bit-length used in scalarmult as a loop bound is constant.
Re:Minerva: Practically exploitable side-channel leakage in ...
by j08ny on Thursday October 03, 2019 @03:42PM
(#21151230)
Right, there are many ways to do it correctly. In general, you need complete addition formulas (those that can take the point at infinity and produce a correct result in a side-channel indistinguishable way), if you have those, almost any scalar multiplication algo can be made constant time with regards to the scalar bit-length (you would just start at some fixed point past the end of the scalar in case of a left-to-right algo, with the point at infinity intialized).
Thank you for the explanation!
In https://minerva.crocs.fi.muni.cz/#details-reasons and in your comment you're describing two bad ways to do scalarmult, but you do not show side-by-side the correct way (e.g. what ref10 does). Can you describe it in a sentence or two?