Double-and-add/Montgomery VS blinding

Question

I'm having a hard time understanding why people use constant-time techniques to counter time-attacks, when blinding seems as good and cheaper to implement.

Why do people avoid blinding in ECC?

Answer 1

Good blinding requires good randomness. Randomness is a hard requirement, especially for embedded systems. In a similar vein, the DSA and ECDSA signature algorithms require a strongly random integer (called k) for each signature, and several implementations have failed to use random enough values, with hilarious consequences; the most well-known case is Sony and the signatures protecting the PS3 firmware (they used a fixed k...), but a number of Bitcoin-related "electronic wallet" applications also botched things similarly. This even prompted the specification of deterministic variants of DSA and ECDSA, to avoid the need for randomness. If good randomness cannot always be obtained for (EC)DSA signatures, then one has to assume that good randomness cannot always be obtained either for secure blinding.

Another point is that timing attacks have evolved over time. The "classical" timing attack on RSA, described by Kocher in 1996, only uses a measure of the complete computation time. However, modern, fashionable variants use accesses to cache memory or jump prediction within the CPU to obtain a lot of information from even a single run of the attacked implementation -- especially in contexts where the attacker can run his own code on the same core (hyperthreading) or in a close core (even across virtual machines). It is unclear how well blinding holds against that kind of attack. Common wisdom is that such attacks are very hard to pull off in most cases (and they have not been observed "in the wild" yet), but it is also very hard to ascertain whether they apply, or do not apply, to a particular situation. A general-purpose library has then little choice but to play safe, and go for constant-time code.

Also, in the case of binary curves (curves over a field $GF(2^m)$), Montgomery's ladder (as described by López and Dahab in 1999) can be adapted to binary curve and yields a verify efficient point multiplication algorithm that is both constant-time (provided you use constant-time conditional swaps, which is no hardship) and fast (6 field multiplications per bit). It is not easy to do better than that in all generality, especially on modern x86 hardware with the CLMUL instructions (when field multiplications are slow, point-halving is better, but not when field multiplications are very fast).

Last but not least, many implementers are motivated by the intellectual challenge of coding (especially in open-source projects), and constant-time code is a lot more fun than blinding. Blinding is crude and inelegant. Who wants to spend his weekends implementing blinding ?