search

kmackay / micro-ecc

ECDH and ECDSA for 8-bit, 32-bit, and 64-bit processors.
BSD 2-Clause "Simplified" License
1.26k stars 461 forks source link

Generation of ECDSA random k #6

Closed jlogue closed 10 years ago

jlogue commented 10 years ago

Hi Ken,

I was looking over the implementation of ecdsa_sign() and was wondering about of the generation of the k value. The algorithm effectively performs a simple modulo of the supplied random value against the configured curve's order (n). This would appear to bias the generation of k towards lower values.

Now as I understand it (and I readily admit I may have it wrong), this sort of bias can lead to a leak of the private key provided an attacker can gather enough sample signatures. To this end, SEC1 and NIST SP800-90 specify a variety of algorithms to convert random bit strings into numbers while maintaining a uniform distribution. The ecc_make_key() function also uses a similar modulo approach to generating a private key, however the issue may not be as concerning in this situation as it is for ECDSA.

So my 'issue' is twofold: 1) Do I correctly understand the effect of the code in ecdsa_sign(); and 2) Was there a reason you didn't go with one of the algorithms from SEC1/SP800-90?

BTW, thanks for making this code available. It's great to have a simple yet compact implementation of ECC code that's open source.

Jay

kmackay commented 10 years ago

Your interpretation of the ecdsa_sign() is correct. As for why it is that way… I had thought that the bias attacks on ECDSA were only effective on binary fields, but after further research that was not correct (eg http://eprint.iacr.org/2013/346.pdf). So I will change it to fail on k >= n. It doesn't seem to be a significant issue for ECDH but it is reasonable to do the same thing there.

It turns out that there is another more serious issue, which is that the Montgomery ladder implementation of point multiplication gives timing information about the number of bits in the scalar. This leads to a simple timing attack on the ECDSA code to get "small" values of k, which (with enough samples) can then be used to extract the private key. This should be possible to fix using the countermeasure described in http://eprint.iacr.org/2011/232.pdf

(Note that the Montgomery ladder point multiplication is preferred for ECDH because it doesn't leak any timing information about the values of the scalar bits).

kmackay commented 10 years ago

Thanks for letting me know about this issue.