j08ny

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

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.

We are working on lowering that number :)

It is quite a conservative estimate, we didn't want to claim something our PoC couldn't deliver. Also, it is with minimal attack runtime, as in, after you have those signatures and timings it takes a few minutes to get the private key. There is a trade-off where you can get around some of the noise and thus need less signatures if you just throw more computation resources at it.

If my two cents count, I would say that if you were to implement EdDSA from the paper, you would have a good chance of creating a secure implementation w.r.t. to this kind of leakage.

However, if you were starting with some Short-Weierstrass EC code in your library, then you might be inclined to skip all the scalar multiplication specific stuff in the Ed25519 paper, just take some (incomplete) Edwards formulas, take some general scalar multiplication algo (or even reuse the one you have for Short-Weierstrass, like libgcrypt) and end up with a vulnerable EdDSA (if your ECDSA was).

The short-circuiting in the addition formulas is necessary if incomplete formulas are used. Either that is done, or the scalar multiplication algorithm has to explicitly find out the bit-length and start so that the point at infinity is not input into them ever.

Thanks, a paper is being prepared with the full details and an improved method. The sensitivity of the method to noise (one bad inequality in the lattice can make it not find the key) is really worth looking at, as that would improve the number of signatures necessary for the attack severely.

We considered listing implementations we tested and deemed secure, however this is really hard to do in practice. See also the answer in the second question in the Q&A.

Most libraries have several implementations of the scalar multiplication algorithm, which they choose from dynamically, based on build options, the chosen curve, the platform, the cryptosystem/operation being performed, the current phase of the moon, etc..

We tested the libraries listed here:

https://github.com/crocs-muni/ECTester/blob/master/docs/LIBS...

as we had those implemented and so testing meant just running our tools and analyzing the results. However, even this could have missed stuff, as at first we did miss the Java vulnerability, as we focused on prime field curves and did not test binary field ones. We then analyzed most other cryptographic libraries with ECC support one could think of, but only via source code analysis.

Regarding the stars, we put those in to give some context of why we listed those particular vulnerable implementations on GitHub. We searched through GitHub repositories mentioning ECDSA, ordered by their stars as a measure of popularity and analyzed the source code of their scalar multiplication for the vulnerability. One could choose just random hobby ECDSA implementations and list them as likely vulnerable, these are just a few that are worthy of listing because of their popularity.

Edit: We have added the list of tested implementations deemed secure https://minerva.crocs.fi.muni.cz/#secure-impl.

It's not practical for most cases, but the few very very high-security ones. The pads are distributed beforehand, stored securely and used when a message encrypted to them comes in. So it's just that the message can have OTP security while not taking the time of a courier trip and can be just sent on other somewhat insecure channel.