9 ms·

Minerva: Practically exploitable side-channel leakage in ECDSA implementations

85 points by j08ny 7y ago

xnyan 7y ago
There’s no reason I’m aware of to use ECDSA over other available crypto. Don’t use ECDSA.
- tptacek 7y ago
  This impacts EdDSA as well, the Edwards-curve Schnorr-based system that is a gold standard for signing crypto. While I agree that you should avoid ECDSA, implementation errors can happen to anything.
- wolf550e 7y ago
  1. They show libgcrypt managed to have the bug in EdDSA (https://git.gnupg.org/cgi-bin/gitweb.cgi?p=libgcrypt.git;a=commit;h=b9577f7c89b4327edc09f2231bc8b31521102c79 https://git.gnupg.org/cgi-bin/gitweb.cgi?p=libgcrypt.git;a=c...). 2. People need to use ECDSA for same reason they need to use RSA: compatibility. In particular, EdDSA webpki certificates will likely never happen (https://cabforum.org/pipermail/servercert-wg/2019-June/000875.html https://cabforum.org/pipermail/servercert-wg/2019-June/00087...).
  - loeg 7y ago
    There's no reason I'm aware of to use libgcrypt over other available crypto. Don't use libgcrypt.
  - tptacek 7y ago
    But, if you fear and loathe ECDSA (and I do as well), it's probably a good idea to get in early against protocols that seek to deploy more of it. For instance, DNSSEC, which is barely deployed anywhere on the Internet, is just now (as in, resolvers couldn't reliably verify ECC records until recently) introducing ECC support --- with ECDSA.
    - wolf550e 7y ago
      I think EdDSA desperately needs to be allowed in FIPS certified hardware, so that secure hardware will have support for EdDSA so that people who have to store keys in secure hardware will be able to use it. I mean HSMs, smart cards, secure enclaves, TPMs, things with a ATECC508A, etc.
      - wolf550e 7y ago
        Can downvoters explain why I'm wrong?
wolf550e 7y ago
previously: https://news.ycombinator.com/item?id=21136946 https://news.ycombinator.com/item?id=21136946
tptacek 7y ago
This looks like a really phenomenal writeup, with worked examples. The underlying math and algorithm stuff here is applicable to other attacks; it looks like this is worth a close read.
- wolf550e 7y ago
  Can you say whether libgcrypt did something especially stupid? [1] I understand that most people just take the ref10 code from supercop, but if I were to try to implement ed25519 from the paper (https://ed25519.cr.yp.to/papers.html https://ed25519.cr.yp.to/papers.html), what is the chance I would do something like what libgcrypt did, or equally bad? Basically, is ed25519 secure because everyone uses a known secure implementation or because it is engineered to be genuinely hard to implement incorrectly from the paper? (I know it's both, but is it mostly one or the other?) 1 - They special cased the point at infinity and this short-circuit allowed to count leading zeros.
  - j08ny 7y ago
    If my two cents count, I would say that if you were to implement EdDSA from the paper, you would have a good chance of creating a secure implementation w.r.t. to this kind of leakage. However, if you were starting with some Short-Weierstrass EC code in your library, then you might be inclined to skip all the scalar multiplication specific stuff in the Ed25519 paper, just take some (incomplete) Edwards formulas, take some general scalar multiplication algo (or even reuse the one you have for Short-Weierstrass, like libgcrypt) and end up with a vulnerable EdDSA (if your ECDSA was). The short-circuiting in the addition formulas is necessary if incomplete formulas are used. Either that is done, or the scalar multiplication algorithm has to explicitly find out the bit-length and start so that the point at infinity is not input into them ever.
    - wolf550e 7y ago
      ^ primary contact author of the paper in question Thank you for the explanation! In https://minerva.crocs.fi.muni.cz/#details-reasons https://minerva.crocs.fi.muni.cz/#details-reasons and in your comment you're describing two bad ways to do scalarmult, but you do not show side-by-side the correct way (e.g. what ref10 does). Can you describe it in a sentence or two?
svnpenn 7y ago
> the trustworthiness of NIST-produced curves being questioned after revelations that the NSA willingly inserts backdoors into software, hardware components and published standards were made; well-known cryptographers have expressed doubts about how the NIST curves were designed, and voluntary tainting has already been proved in the past. https://wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Concerns https://wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_...
- loeg 7y ago
  Use Ed25519 for your SSH keys, then. (For the unfamiliar: it's not a NIST-chosen curve.)
- wolf550e 7y ago
  'tptacek would write that no reputable cryptographer believes the NIST curves themselves are backdoored.
  - deleted 7y ago
    [deleted]
  - 1000units 7y ago
    Is this a joke? Doesn't everybody believe they're backdoored?
    - hannob 7y ago
      There's two stories that often get mixed together. One is an elliptic curve based random number generator (Dual EC DRBG), and yes, everyone who knows the facts believes it's backdoored. Then there's some much more general concerns about the NIST curves themselve. These concerns come down to that a) we don't really know how they were generated (there are some numbers in the paper that just "appear out of nowhere") and b) that they've been created by the NSA. But there's no concrete proof of any backdooring and it seems relatively implausible, as no method is known that would explain how that backdooring would work. I guess most people familiar with the facts don't believe they are backdoored.
exabrial 7y ago
Great writeup. Once again, physical access owns. This line stuck out: > The attack required 11000 signatures For a smartcard, this seems rather impractical in the real world. My Nitrokey has 1938 total signs after a month of usage, signing every git commit to our company repository and using it to authenticate over ssh (gpg-agent)
- j08ny 7y ago
  We are working on lowering that number :) It is quite a conservative estimate, we didn't want to claim something our PoC couldn't deliver. Also, it is with minimal attack runtime, as in, after you have those signatures and timings it takes a few minutes to get the private key. There is a trade-off where you can get around some of the noise and thus need less signatures if you just throw more computation resources at it.
UI_at_80x24 7y ago
What is the latest "most secure" crypto I should be using?
- exabrial 7y ago
  At minimum, for asymmetric, at the time of the writing: * ECDSA with secp-256 or ed25519 curves * RSA >= 2048 bits. Performance takes a steep dive at 4096bits unfortunately What people don't understand is that your implementation needs to be selected against your attack surface. If your attack surface includes hardening against side channels, your implementation selection needs to take that into account.
  - regecks 7y ago
    I don't think curve25519 is used in any ECDSA implementations. ed25519 is part of EdDSA.
    - exabrial 7y ago
      You're correct. ed25519 is a separate scheme.
- exabrial 7y ago
  Finally, read this: "If You’re Typing the Letters A-E-S Into Your Code You’re Doing It Wrong" https://www.nccgroup.trust/us/about-us/newsroom-and-events/blog/2009/july/if-youre-typing-the-letters-a-e-s-into-your-code-youre-doing-it-wrong/ https://www.nccgroup.trust/us/about-us/newsroom-and-events/b...
  - pilsetnieks 7y ago
    Now that's a deep cut even for a Dan Harmon fan.
    - aidenn0 7y ago
      For anyone else wondering what the Dan Harmon reference was: https://en.wikipedia.org/wiki/Heat_Vision_and_Jack https://en.wikipedia.org/wiki/Heat_Vision_and_Jack
exabrial 7y ago
Athena’s IDProtect Smart Card and Middleware Approved for US Government PIV/HSPD-12 Deployment https://www.securetechalliance.org/athenas-idprotect-smart-card-and-middleware-approved-for-us-government-pivhspd-12-deployment/ https://www.securetechalliance.org/athenas-idprotect-smart-c...
garganzol 7y ago
I like the presentation format of this work. Not only it plays well as a paper, it also contains elements of interactivity to make things more concise and clear. Definitely a thing from the future.

85 points by j08ny 7y ago

xnyan 7y ago

There’s no reason I’m aware of to use ECDSA over other available crypto. Don’t use ECDSA.

tptacek 7y ago
This impacts EdDSA as well, the Edwards-curve Schnorr-based system that is a gold standard for signing crypto. While I agree that you should avoid ECDSA, implementation errors can happen to anything.
wolf550e 7y ago
1. They show libgcrypt managed to have the bug in EdDSA (https://git.gnupg.org/cgi-bin/gitweb.cgi?p=libgcrypt.git;a=commit;h=b9577f7c89b4327edc09f2231bc8b31521102c79 https://git.gnupg.org/cgi-bin/gitweb.cgi?p=libgcrypt.git;a=c...). 2. People need to use ECDSA for same reason they need to use RSA: compatibility. In particular, EdDSA webpki certificates will likely never happen (https://cabforum.org/pipermail/servercert-wg/2019-June/000875.html https://cabforum.org/pipermail/servercert-wg/2019-June/00087...).
- loeg 7y ago
  There's no reason I'm aware of to use libgcrypt over other available crypto. Don't use libgcrypt.
- tptacek 7y ago
  But, if you fear and loathe ECDSA (and I do as well), it's probably a good idea to get in early against protocols that seek to deploy more of it. For instance, DNSSEC, which is barely deployed anywhere on the Internet, is just now (as in, resolvers couldn't reliably verify ECC records until recently) introducing ECC support --- with ECDSA.
  - wolf550e 7y ago
    I think EdDSA desperately needs to be allowed in FIPS certified hardware, so that secure hardware will have support for EdDSA so that people who have to store keys in secure hardware will be able to use it. I mean HSMs, smart cards, secure enclaves, TPMs, things with a ATECC508A, etc.
    - wolf550e 7y ago
      Can downvoters explain why I'm wrong?

wolf550e 7y ago

previously: https://news.ycombinator.com/item?id=21136946 https://news.ycombinator.com/item?id=21136946

tptacek 7y ago

This looks like a really phenomenal writeup, with worked examples. The underlying math and algorithm stuff here is applicable to other attacks; it looks like this is worth a close read.

wolf550e 7y ago
Can you say whether libgcrypt did something especially stupid? [1] I understand that most people just take the ref10 code from supercop, but if I were to try to implement ed25519 from the paper (https://ed25519.cr.yp.to/papers.html https://ed25519.cr.yp.to/papers.html), what is the chance I would do something like what libgcrypt did, or equally bad? Basically, is ed25519 secure because everyone uses a known secure implementation or because it is engineered to be genuinely hard to implement incorrectly from the paper? (I know it's both, but is it mostly one or the other?) 1 - They special cased the point at infinity and this short-circuit allowed to count leading zeros.
- j08ny 7y ago
  If my two cents count, I would say that if you were to implement EdDSA from the paper, you would have a good chance of creating a secure implementation w.r.t. to this kind of leakage. However, if you were starting with some Short-Weierstrass EC code in your library, then you might be inclined to skip all the scalar multiplication specific stuff in the Ed25519 paper, just take some (incomplete) Edwards formulas, take some general scalar multiplication algo (or even reuse the one you have for Short-Weierstrass, like libgcrypt) and end up with a vulnerable EdDSA (if your ECDSA was). The short-circuiting in the addition formulas is necessary if incomplete formulas are used. Either that is done, or the scalar multiplication algorithm has to explicitly find out the bit-length and start so that the point at infinity is not input into them ever.
  - wolf550e 7y ago
    ^ primary contact author of the paper in question Thank you for the explanation! In https://minerva.crocs.fi.muni.cz/#details-reasons https://minerva.crocs.fi.muni.cz/#details-reasons and in your comment you're describing two bad ways to do scalarmult, but you do not show side-by-side the correct way (e.g. what ref10 does). Can you describe it in a sentence or two?

svnpenn 7y ago

> the trustworthiness of NIST-produced curves being questioned after revelations that the NSA willingly inserts backdoors into software, hardware components and published standards were made; well-known cryptographers have expressed doubts about how the NIST curves were designed, and voluntary tainting has already been proved in the past. https://wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#Concerns https://wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_...

loeg 7y ago
Use Ed25519 for your SSH keys, then. (For the unfamiliar: it's not a NIST-chosen curve.)
wolf550e 7y ago
'tptacek would write that no reputable cryptographer believes the NIST curves themselves are backdoored.
- deleted 7y ago
  [deleted]
- 1000units 7y ago
  Is this a joke? Doesn't everybody believe they're backdoored?
  - hannob 7y ago
    There's two stories that often get mixed together. One is an elliptic curve based random number generator (Dual EC DRBG), and yes, everyone who knows the facts believes it's backdoored. Then there's some much more general concerns about the NIST curves themselve. These concerns come down to that a) we don't really know how they were generated (there are some numbers in the paper that just "appear out of nowhere") and b) that they've been created by the NSA. But there's no concrete proof of any backdooring and it seems relatively implausible, as no method is known that would explain how that backdooring would work. I guess most people familiar with the facts don't believe they are backdoored.

exabrial 7y ago

Great writeup. Once again, physical access owns. This line stuck out: > The attack required 11000 signatures For a smartcard, this seems rather impractical in the real world. My Nitrokey has 1938 total signs after a month of usage, signing every git commit to our company repository and using it to authenticate over ssh (gpg-agent)

j08ny 7y ago
We are working on lowering that number :) It is quite a conservative estimate, we didn't want to claim something our PoC couldn't deliver. Also, it is with minimal attack runtime, as in, after you have those signatures and timings it takes a few minutes to get the private key. There is a trade-off where you can get around some of the noise and thus need less signatures if you just throw more computation resources at it.

UI_at_80x24 7y ago

What is the latest "most secure" crypto I should be using?

exabrial 7y ago
At minimum, for asymmetric, at the time of the writing: * ECDSA with secp-256 or ed25519 curves * RSA >= 2048 bits. Performance takes a steep dive at 4096bits unfortunately What people don't understand is that your implementation needs to be selected against your attack surface. If your attack surface includes hardening against side channels, your implementation selection needs to take that into account.
- regecks 7y ago
  I don't think curve25519 is used in any ECDSA implementations. ed25519 is part of EdDSA.
  - exabrial 7y ago
    You're correct. ed25519 is a separate scheme.
exabrial 7y ago
Finally, read this: "If You’re Typing the Letters A-E-S Into Your Code You’re Doing It Wrong" https://www.nccgroup.trust/us/about-us/newsroom-and-events/blog/2009/july/if-youre-typing-the-letters-a-e-s-into-your-code-youre-doing-it-wrong/ https://www.nccgroup.trust/us/about-us/newsroom-and-events/b...
- pilsetnieks 7y ago
  Now that's a deep cut even for a Dan Harmon fan.
  - aidenn0 7y ago
    For anyone else wondering what the Dan Harmon reference was: https://en.wikipedia.org/wiki/Heat_Vision_and_Jack https://en.wikipedia.org/wiki/Heat_Vision_and_Jack

exabrial 7y ago

Athena’s IDProtect Smart Card and Middleware Approved for US Government PIV/HSPD-12 Deployment https://www.securetechalliance.org/athenas-idprotect-smart-card-and-middleware-approved-for-us-government-pivhspd-12-deployment/ https://www.securetechalliance.org/athenas-idprotect-smart-c...

garganzol 7y ago

I like the presentation format of this work. Not only it plays well as a paper, it also contains elements of interactivity to make things more concise and clear. Definitely a thing from the future.