Minerva: Practically exploitable side-channel leakage in ECDSA implementations
minerva.crocs.fi.muni.cz> 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_...
Use Ed25519 for your SSH keys, then. (For the unfamiliar: it's not a NIST-chosen curve.)
'tptacek would write that no reputable cryptographer believes the NIST curves themselves are backdoored.
Is this a joke? Doesn't everybody believe they're backdoored?
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.
Oh, just that once.
We don't actually know for sure that Dual EC is backdoored, we have unexplained constants plus subsequently a way to pick constants that backdoor the algorithm have been discovered. The constants could have been chosen randomly or based on something that would be embarrassing to reveal, e.g. the project leader picked their children's birthdays. Since this algorithm is worse in other ways there is no reason to use it and it's reasonable to treat things that pick Dual EC as problematic because they had no good reason to do that once it became controversial. But we shouldn't forget that it's not actually proven to be backdoored, we have only reasonable suspicions.
Reading this [1] and then saying that maybe it's not a backdoor, maybe it's the NSA cryptographer's kids' birthdays is completely nuts.
Some people put their faith in the strangest places.
We also know that the NSA secretly paid RSA-the-company $10 million to use dual ec as the default.
We also know that Juniper not only used Dual-EC for their VPNs, but that someone at some point got access to their source tree and rekeyed the backdoor to a new secret. It's obviously a backdoor.
We do know a lot more than that now. It was in the Snowden leaks.
We have a lot of competent people at the NSA.
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.
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), 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.
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.
^ primary contact author of the paper in question
Thank you for the explanation!
In 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?
Right, there are many ways to do it correctly. In general, you need complete addition formulas (those that can take the point at infinity and produce a correct result in a side-channel indistinguishable way), if you have those, almost any scalar multiplication algo can be made constant time with regards to the scalar bit-length (you would just start at some fixed point past the end of the scalar in case of a left-to-right algo, with the point at infinity intialized).
One of the main points in the root causes discussion is that without complete formulas you are almost always going to leak the bit-length, so the only way to not be vulnerable in that case is to fix the bit-length to a constant value. This cannot be done naively by simply setting the high bit, because this would introduce bias in the nonces which would be exploitable even without measuring the duration, a much worse attack! However it can be done via the method suggested by Brumley & Tuveri in https://eprint.iacr.org/2011/232 where you add a multiple of the curve order to the scalar to fix its bit-length. This means the distribution of the nonce modulo the order remains the same (uniform, no bias) yet the bit-length used in scalarmult as a loop bound is constant.
Thanks, a paper is being prepared with the full details and an improved method. The sensitivity of the method to noise (one bad inequality in the lattice can make it not find the key) is really worth looking at, as that would improve the number of signatures necessary for the attack severely.
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)
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.
Athena’s IDProtect Smart Card and Middleware Approved for US Government PIV/HSPD-12 Deployment
https://www.securetechalliance.org/athenas-idprotect-smart-c...
There’s no reason I’m aware of to use ECDSA over other available crypto. Don’t use ECDSA.
1. They show libgcrypt managed to have the bug in EdDSA (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/00087...).
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.
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.
Can downvoters explain why I'm wrong?
There's no reason I'm aware of to use libgcrypt over other available crypto. Don't use libgcrypt.
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.
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.
What is the latest "most secure" crypto I should be using?
In new designs or like, SSH keys?
For new designs: basically just use libsodium.
For SSH: Ed25519 or 2048 bit RSA.
We can get into the weeds about which specific cryptographic primitives are fine in isolation, but that misses the point — the ones that were fine 5-10 years ago are still more or less fine — the problems for developers and end-users generally stem from accidental misuse of cryptographic primitives in designing systems incorporating cryptographic primitives as a component. Sure, don't use DES, DSA, or MD5/SHA1; strong primitives are only necessary, not sufficient.
>For new designs: basically just use libsodium.
Check out libhydrogen from the same author. The API contains less footguns (like nonces).
The appeal of libsodium is that it is (or was) mostly an easy to consume NaCl. Correct me if I'm wrong, but I don't think libhydrogen is related to NaCl or the NaCl authors.
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/b...
Now that's a deep cut even for a Dan Harmon fan.
For anyone else wondering what the Dan Harmon reference was:
What's wrong with using AES in CBC mode?
See my original comment about attack surface. Given the correct set of circumstances, transmitting the IV in the clear with CBC could possibly open you up to chosen ciphertext/plaintext attacks. And you better be doing encrypt-then-prepend-IV-then-MAC with CBC. Just a lot of gotchas that may or may not be relevant, depending on your environment.
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.
I don't think curve25519 is used in any ECDSA implementations. ed25519 is part of EdDSA.
You're correct. ed25519 is a separate scheme.
Start from cryptographic right answers:
https://latacora.singles/2018/04/03/cryptographic-right-answ...
On a glance none of those recommendations have become invalid in the passing 18 months or so.
previously: https://news.ycombinator.com/item?id=21136946