Side channel attacks against ECDSA/EdDSA signature generation in smart cards(minerva.crocs.fi.muni.cz)
minerva.crocs.fi.muni.cz
Side channel attacks against ECDSA/EdDSA signature generation in smart cards
https://minerva.crocs.fi.muni.cz/
3 comments
We considered listing implementations we tested and deemed secure, however this is really hard to do in practice. See also the answer in the second question in the Q&A.
Most libraries have several implementations of the scalar multiplication algorithm, which they choose from dynamically, based on build options, the chosen curve, the platform, the cryptosystem/operation being performed, the current phase of the moon, etc..
We tested the libraries listed here:
https://github.com/crocs-muni/ECTester/blob/master/docs/LIBS...
as we had those implemented and so testing meant just running our tools and analyzing the results. However, even this could have missed stuff, as at first we did miss the Java vulnerability, as we focused on prime field curves and did not test binary field ones. We then analyzed most other cryptographic libraries with ECC support one could think of, but only via source code analysis.
Regarding the stars, we put those in to give some context of why we listed those particular vulnerable implementations on GitHub. We searched through GitHub repositories mentioning ECDSA, ordered by their stars as a measure of popularity and analyzed the source code of their scalar multiplication for the vulnerability. One could choose just random hobby ECDSA implementations and list them as likely vulnerable, these are just a few that are worthy of listing because of their popularity.
Edit: We have added the list of tested implementations deemed secure https://minerva.crocs.fi.muni.cz/#secure-impl.
Most libraries have several implementations of the scalar multiplication algorithm, which they choose from dynamically, based on build options, the chosen curve, the platform, the cryptosystem/operation being performed, the current phase of the moon, etc..
We tested the libraries listed here:
https://github.com/crocs-muni/ECTester/blob/master/docs/LIBS...
as we had those implemented and so testing meant just running our tools and analyzing the results. However, even this could have missed stuff, as at first we did miss the Java vulnerability, as we focused on prime field curves and did not test binary field ones. We then analyzed most other cryptographic libraries with ECC support one could think of, but only via source code analysis.
Regarding the stars, we put those in to give some context of why we listed those particular vulnerable implementations on GitHub. We searched through GitHub repositories mentioning ECDSA, ordered by their stars as a measure of popularity and analyzed the source code of their scalar multiplication for the vulnerability. One could choose just random hobby ECDSA implementations and list them as likely vulnerable, these are just a few that are worthy of listing because of their popularity.
Edit: We have added the list of tested implementations deemed secure https://minerva.crocs.fi.muni.cz/#secure-impl.
Thanks for the clarification!
Even a "we tested this specific function, and didn't find an issue" would usually be helpful.
The situation I've faced as an implementer is that people show up asking about a paper (e.g. https://github.com/bitcoin-core/secp256k1/issues/238 ) I read the paper, it discusses a risk vector we were aware of and believe we avoided and I find myself somewhat surprised at the list of vulnerable implementations. This makes me worry that I didn't actually understand the issue-- maybe the countermeasures we had weren't really good enough-- and uncomfortable giving the really strong "not vulnerable" that the requester was looking for.
This is especially the case because the results in papers like yours aren't against toy implementations, but in implementations that I know are written by extremely competent persons.
The end result is usually that I go and read the changes that fix the vulnerability, if possible-- sometimes they're made somewhat surreptitiously and hard to disentangle from the other changes--; and convince myself that it really was the issue I understood it to be... and rest back on my prior constant time testing results and our design countermeasures to be confident that no similar issue exists.
> One could choose just random hobby ECDSA implementations and list them as likely vulnerable, these are just a few that are worthy of listing because of their popularity.
Fair enough. I think actually searching to see how many other projects have copied the vulnerable code might be a better proxy than stars, since there is no particular reason to click the star button if you're using a piece of code. Often end users will pick up vulnerable code via a popular program that links or embed it, and the bulk of users never directly see the repo for the crypto library.
For years searching for "python eddsa" yielded an extremely vulnerable first result (including setting K to H(private key), using double and add, non-constant time infinity handling, etc.) that by all appearances was some random hobby project but because it was the first google hit, it actually got used in a fair number of places.
Even a "we tested this specific function, and didn't find an issue" would usually be helpful.
The situation I've faced as an implementer is that people show up asking about a paper (e.g. https://github.com/bitcoin-core/secp256k1/issues/238 ) I read the paper, it discusses a risk vector we were aware of and believe we avoided and I find myself somewhat surprised at the list of vulnerable implementations. This makes me worry that I didn't actually understand the issue-- maybe the countermeasures we had weren't really good enough-- and uncomfortable giving the really strong "not vulnerable" that the requester was looking for.
This is especially the case because the results in papers like yours aren't against toy implementations, but in implementations that I know are written by extremely competent persons.
The end result is usually that I go and read the changes that fix the vulnerability, if possible-- sometimes they're made somewhat surreptitiously and hard to disentangle from the other changes--; and convince myself that it really was the issue I understood it to be... and rest back on my prior constant time testing results and our design countermeasures to be confident that no similar issue exists.
> One could choose just random hobby ECDSA implementations and list them as likely vulnerable, these are just a few that are worthy of listing because of their popularity.
Fair enough. I think actually searching to see how many other projects have copied the vulnerable code might be a better proxy than stars, since there is no particular reason to click the star button if you're using a piece of code. Often end users will pick up vulnerable code via a popular program that links or embed it, and the bulk of users never directly see the repo for the crypto library.
For years searching for "python eddsa" yielded an extremely vulnerable first result (including setting K to H(private key), using double and add, non-constant time infinity handling, etc.) that by all appearances was some random hobby project but because it was the first google hit, it actually got used in a fair number of places.
In this case, they do show openssl-- but it's burred under a generic titled click through. I would guess they also found other apparently secure implementations, but none are listed.
Providing this information would have several benefits:
(1) People could look and the correct implementations and learn what choices they made which helped them avoid the issue.
(2) The incentive for making secure implementations would be increased.
(3) Effort could be conserved in identifying already correct implementations. In particular, correct implementations get asked over and over again if they're vulnerable ... and it can be a bit exposed-feeling to give an emphatic 'no' without the benefit of the assistance of the researchers and their test setup.
Also, if an error was made in identifying a correct implementation, then someone writing another paper refuting the that sub-result would likely have an easier time getting published than someone who just did the same attack against more implementations-- increasing the incentive to continue this line of research.
Anyone know why they bother listing github "stars" on the vulnerable software list?