# Double-and-add/Montgomery VS blinding

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?

• I suspect that's because blinding is not as good and makes the runtime generally longer, $\hspace{1.04 in}$ even if it seems as good and is cheaper to implement. $\;$ – user991 Apr 22 '15 at 20:38
• Actually, it's not at all true that blinding is slower; at least in the case of multiplication of the generator. If we assume 256-bit EC, then computing xG by double-and-add takes 256 doubles and 256 adds; in contrast (if we precompute the tables) a multiply by the generator might take 64 adds and no doubles (say, by radix-16; actually, there are smarter ways to do it). Even if we compute rG + (x-r)G, that brings us to 129 adds, which is still more than twice as fast as the double-and-add method. – poncho Apr 23 '15 at 15:41

## 1 Answer

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 ?

• Thanks for the answer Thomas! Why are you talking about Montgomery's ladder specifically for binary curves. That algorithm can be adapted to any kind of curves. Also spend weekends implementing blinding? It usually takes two more lines of code to implement, that's the first time I hear someone saying blinding is inelegant and hard to implement oO I think it's good to add the recent research on time padding as a "new" countermeasure (at least it becomes practical) arxiv.org/pdf/1506.00189.pdf – David 天宇 Wong Jun 20 '15 at 20:12
• – David 天宇 Wong Jul 27 '15 at 22:52