4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\;$ $\endgroup$ – user991 Apr 22 '15 at 20:38
  • 1
    $\begingroup$ 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. $\endgroup$ – poncho Apr 23 '15 at 15:41
4
$\begingroup$

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 ?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.