Eyyy, it’s our favorite fluffy blue thing here once again to talk about applied math and memes!
This is a really good rundown. There’s just enough history and theory to tell us what these things are and why they exist. Then summaries to separate all the voodoo, interesting-but-impractical, and the-government-says-thou-must from the actually useful things? As someone with enough interest in cryptography to care, but not enough to make it an actual topic of study… thank you!
I’m a dummy, what library will force me to use the right curve & other parameters and provides a high quality constant-time implementation of whatever tool I need?
I really like libsodium, but I don’t think I could have understood the bits of their docs where they justify their algorithm choices without your blog (the nice thing about libsodium is that I don’t need to understand those bits of the docs, of course, but that doesn’t mean that I don’t want to).
Agreed. I generally recommend the original upstream NaCl, libsodium, or Monocypher depedning on your circumstances. All three are fantastic libraries with minimal footguns.
I was researching this exact question recently and wish I had this article on hand. One additional property of ECDSA I stumbled across was the ability to reconstruct the public key from a message+signature for the cost of a single extra bit, which I thought was pretty neat if I don’t want to spend extra bytes explaining who it was that signed the thing.
Also my research turned up considerably more discussion about the perceived trustworthiness of the NIST curves than in OP. Presumably opinions vary as to whether it’s a serious concern. :)
The common sense argument, of course, is that you don’t sh*t where you eat. In other words, the NSA wouldn’t deliberately choose weak elliptic curves given that they planned to use them for encrypting Secret and Top Secret data for the next 20 years.
By calculating the number of possible curve families, Koblitz and Menezes show that a vast proportion of curves (for P-256, around 2^{209} out of 2^{257}) would have to be weak in order for the NSA to succeed in this attack. The implications of such a large class of vulnerable curves is very bad for the field of ECC. It dwarfs every previous known weak curve class and would call into question the decision to use ECC at all.
In other words, Koblitz and Menezes are saying that if you accept the weak curve hypothesis into your heart, the solution is not to replace the NIST elliptic curves with anything at all, but rather, to leave the building as rapidly as possible and perhaps not shut the door on the way out. No joke.
With that in mind, even though I vehemently distrust the NSA, I still don’t buy the “NIST curves are backdoored” argument at all. Some of this discourse might be due to confusion about the Dual_EC_DRBG backdoor (which used “elliptic curves”, so it may be viewed as a “proven elliptic curve backdoor”).
(Meanwhile, Ed25519 is designed to be side-channel and misuse-resistant, partly due to its Schnorr construction and constant-time ladder for scalar multiplication, so any library that implements Ed25519 is overwhelmingly likely to be constant-time.)
Is an interesting observation - I wouldn’t mind reading a blogpost about how a cryptographer might build this kind of side-channel-resistance into a cryptographic protocol.
Eyyy, it’s our favorite fluffy blue thing here once again to talk about applied math and memes!
This is a really good rundown. There’s just enough history and theory to tell us what these things are and why they exist. Then summaries to separate all the voodoo, interesting-but-impractical, and the-government-says-thou-must from the actually useful things? As someone with enough interest in cryptography to care, but not enough to make it an actual topic of study… thank you!
I’m a dummy, what library will force me to use the right curve & other parameters and provides a high quality constant-time implementation of whatever tool I need?
You want libsodium.
I really like libsodium, but I don’t think I could have understood the bits of their docs where they justify their algorithm choices without your blog (the nice thing about libsodium is that I don’t need to understand those bits of the docs, of course, but that doesn’t mean that I don’t want to).
Yeah, we’re tackling opposite sides of the problem.
“I don’t know what I’m doing, please save me from making a bad decision” -> libsodium
“I want to know what I’m doing” -> blogs from cryptography nerds
They’re complementary features :)
Monocypher is also a good choice IMHO — smaller and simpler.
Agreed. I generally recommend the original upstream NaCl, libsodium, or Monocypher depedning on your circumstances. All three are fantastic libraries with minimal footguns.
Great to know this is still the right choice! Thanks.
It really is too bad that SafeCurves is a static site and not a living application like the L-functions and modular forms database.
I was researching this exact question recently and wish I had this article on hand. One additional property of ECDSA I stumbled across was the ability to reconstruct the public key from a message+signature for the cost of a single extra bit, which I thought was pretty neat if I don’t want to spend extra bytes explaining who it was that signed the thing.
Also my research turned up considerably more discussion about the perceived trustworthiness of the NIST curves than in OP. Presumably opinions vary as to whether it’s a serious concern. :)
I’m definitely skeptical of the NSA, and therefore NIST by extension, but Koblitz and Menezes tackles the NIST curve backdoor arguments pretty well. Matt Green has a good write-up about that subject.
With that in mind, even though I vehemently distrust the NSA, I still don’t buy the “NIST curves are backdoored” argument at all. Some of this discourse might be due to confusion about the Dual_EC_DRBG backdoor (which used “elliptic curves”, so it may be viewed as a “proven elliptic curve backdoor”).
Is there any reason other than the author’s ideological problem with cryptocurrency to think that Secp256k1 is a bad curve to use for any purpose?
https://soatok.blog/2022/05/19/guidance-for-choosing-an-elliptic-curve-signature-algorithm-in-2022/#secp256k1-beyond-cybercash
Added a section for you.
Thanks for the additional information here.
Is an interesting observation - I wouldn’t mind reading a blogpost about how a cryptographer might build this kind of side-channel-resistance into a cryptographic protocol.
You’re in luck
I wrote a guide to side-channel attacks in 2020. A lot of the lessons here go into writing constant-time cryptography (especially the bignum stuff).