Nikos Mavrogiannopoulos n.mavrogiannopoulos@gmail.com writes:
My comments were not for ECDSA specifically. ECDSA is pretty fragile.
For me, ECDSA is the primary application of elliptic curves. So then it seems important to use a point multiplication k * G which has a running time independent of the bits in k. That's why I find the method used in gnutls a bit worrying.
Could be. Unfortunately unlike RSA there is not much on timing attacks on (EC)DSA or preventions (or at least known to me).
Maybe one could get some insights from Bleichenbacher's paper. I have not read up on the details, but as far as I understand, the point was that k in the range 1 <= k < 2^bit_size - q were generated with a higher probability density than numbers in the range 2^bit_size - q < k < q.
And for a wnaf timing attack, one idea would be to divide signatures into two classes, those generated with a k expanding to n wnaf digits, and those generated with a k expanding to n+1 digits. Each class corresponds to a different set of possible k, and if the classification is not perfect, you still have a bias in each guessed class.
And I don't think prevention is too difficult. Just write the algorithm to not include any branches depending on bits in k, and preferably (for side-channels related to caches) also with all memory accesses idnependent of the k bits. There's going to be some performance penalty, of course.
Regards, /Niels