Safe curves for Elliptic Curve Cryptography [pdf](eprint.iacr.org)
eprint.iacr.org
Safe curves for Elliptic Curve Cryptography [pdf]
https://eprint.iacr.org/2024/1265.pdf
75 comments
People migrating to djb's curves, or at least allowing them as a first-class citizen, include
It's only like migrating from C to rust for the person implementing the crypto package and singature verifier. For the average package maintainer, they just have to generate a new key and pass a new command line flag to their sign command.
- SSH (which includes git over SSH - github suggests djb's Curve 25519 as default: https://docs.github.com/en/authentication/connecting-to-github-with-ssh/generating-a-new-ssh-key-and-adding-it-to-the-ssh-agent)
- TLS (recommended in n1.3)
- NIST (allows Curve25519, but isn't the default choice)
- various cryptocurrency crap
It's only like migrating from C to rust for the person implementing the crypto package and singature verifier. For the average package maintainer, they just have to generate a new key and pass a new command line flag to their sign command.
GPG is using ed25519 keys as default since 2.3
https://lists.gnupg.org/pipermail/gnupg-announce/2021q2/0004...
https://lists.gnupg.org/pipermail/gnupg-announce/2021q2/0004...
Yes, but SSH isn't e.g. forbidding you from connecting to servers that use RSA or secp256r1, whereas they want to make apt refuse to access repositories that aren't using djb's curves.
SSH by default isn't, but admins can set up their own list of allowed ciphers in their config file. Github, for example, has banned ssh_dss - I think they still support ECDSA, but they only mention Curve25519 and RSA (with caveats) on their SSH keys page.
> SSH by default isn't
Yes, and that's fine. But if SSH mandated a certain thing and disallowed even admins to change it it would be the equivalent problem.
It's Ubuntu preventing the use of anything but "SafeCurves" that's the problem.
If Ubuntu/Canonical want to use them—fine. (Maybe.†) But don't disable the functionality for admins.
† Some regulated industries need to use certain Approved Algorithms, which may or may not include your favourite ones. Further there may be all sorts of other (workflow) tooling that may not support your favourite ones either, and forcing your favourites on other people (especially taking away other options) is a jerk move.
Yes, and that's fine. But if SSH mandated a certain thing and disallowed even admins to change it it would be the equivalent problem.
It's Ubuntu preventing the use of anything but "SafeCurves" that's the problem.
If Ubuntu/Canonical want to use them—fine. (Maybe.†) But don't disable the functionality for admins.
† Some regulated industries need to use certain Approved Algorithms, which may or may not include your favourite ones. Further there may be all sorts of other (workflow) tooling that may not support your favourite ones either, and forcing your favourites on other people (especially taking away other options) is a jerk move.
So, I'm mostly with you here, but I'd say disallowing e.g. MD5 (horribly broken) or anything involving Dual_EC (horribly suspicious) by force would be reasonable. ECDSA/secp* curves, that's more controversial.
The TLS 1.2 -> 1.3 upgrade also disallowed a lot of previously used things, and this was generally considered to be a great improvement (though of course TLS endpoints can be backwards-compatible).
The TLS 1.2 -> 1.3 upgrade also disallowed a lot of previously used things, and this was generally considered to be a great improvement (though of course TLS endpoints can be backwards-compatible).
[deleted]
Infosec suffers from a huge cargo cult and mindless sticky meme problem because so few people actually understand it.
There are still admins who block all ICMP because of the “ping of death,” a Windows bug from either the late 1990s or 2000s. They don’t know this though. They just heard that ICMP is “dangerous.”
People also don’t use IPv6 because they think NAT is a security feature.
I guess it’s similar to baseless health fears and happens whenever people don’t really understand a domain. You get a proliferation of lore that is just repeated.
There are still admins who block all ICMP because of the “ping of death,” a Windows bug from either the late 1990s or 2000s. They don’t know this though. They just heard that ICMP is “dangerous.”
People also don’t use IPv6 because they think NAT is a security feature.
I guess it’s similar to baseless health fears and happens whenever people don’t really understand a domain. You get a proliferation of lore that is just repeated.
Windows had an ICMP CVE last year and also just released a patch for an IPv6 CVE. OpenSSH on Linux had a CVE recently too. Security in depth is reasonable and not baseless.
In either the case of infosec or health, the idea at work is that you can ensure that something is good simply by identifying and removing all that is bad. ... and everyone feels free to determine for themselves what is bad with no deep understanding of the involved systems.
> People also don’t use IPv6 because they think NAT is a security feature.
Literally had a sales engineer parrot this at me awhile back. I had to point out that the service they were offering was on the open internet. It only got worse from there. Le sigh...
Literally had a sales engineer parrot this at me awhile back. I had to point out that the service they were offering was on the open internet. It only got worse from there. Le sigh...
> unless you think the NSA have an unknown backdoor that nobody was able to find
Your post names sense to me, but I don't think it's too crazy to allow for the possibility that e.g. the NSA has backdoored some of the "recommended" crypto constants in current use.
Your post names sense to me, but I don't think it's too crazy to allow for the possibility that e.g. the NSA has backdoored some of the "recommended" crypto constants in current use.
Snowden said that they were doing this, I think?
The NSA definitely put back doors into cryptographic algorithms by forcing their variant into the NIST standards. E.g.: https://en.wikipedia.org/wiki/Dual_EC_DRBG
Dual EC DRBG is a bad design and so you shouldn't use it. It is reasonable to believe it's backdoored, but only the same way it would be reasonable to believe David Cameron stuck his dick in a dead pig. Some people say he did, he says he didn't, there's no conclusive proof available - and it's worth noting the "source" is a man who has a grudge against Cameron.
My favourite also reasonable explanation for the mysterious Dual EC DBRG constants is that some senior person picked their favourite numbers (birthday of a niece, phone number of a friend, whatever) not realising that these should be Nothing Up My Sleeve Numbers. Later when a subordinate says "For documentation we need to explain these numbers" it was late to change them and so the agency can't do better than insist they were chosen at random.
If this was crucial technology we should do the work to re-make it with Nothing Up My Sleeve Numbers, but it's garbage, indeed that's one reason for the suspicion, this is a very complicated machine, well suited to hiding a backdoor, why do this at all?
My favourite also reasonable explanation for the mysterious Dual EC DBRG constants is that some senior person picked their favourite numbers (birthday of a niece, phone number of a friend, whatever) not realising that these should be Nothing Up My Sleeve Numbers. Later when a subordinate says "For documentation we need to explain these numbers" it was late to change them and so the agency can't do better than insist they were chosen at random.
If this was crucial technology we should do the work to re-make it with Nothing Up My Sleeve Numbers, but it's garbage, indeed that's one reason for the suspicion, this is a very complicated machine, well suited to hiding a backdoor, why do this at all?
As far as I'm aware, the other problem with Dual EC is there's two kinds of componets you can use to build a DRBG: "chaotic" (think hash functions, or components thereof) and "algebraic" (highly structured but guaranteed to have certain properties such as minimum period size).
Cryptographic common sense is that if you use an "algebraic" generator, you feed the output through a "chaotic" one at the end. This can't possibly harm security (as long as the output transformation doesn't depend on secret state) as there's a reduction in which the adversary just does the transformation themselves. This is even more important if the algebraic transformation is efficiently invertible in principle, for example if someone has extra secret knowledge (such as the dlog of the base point in use).
If they'd used Dual-EC followed by SHA1 or something that would have not only been better according to folk wisdom, and demonstrably no worse for security (and costing very little compared to the EC operations) but it would also have shut down a lot of conjectured attacks that one could do with twiddled constants.
Yet for some reason, Dual-EC decided to go with an algebraic approach without a "chaotic" output transformation, which is either extreme incompetence or strong evidence that someone is up to no good.
Cryptographic common sense is that if you use an "algebraic" generator, you feed the output through a "chaotic" one at the end. This can't possibly harm security (as long as the output transformation doesn't depend on secret state) as there's a reduction in which the adversary just does the transformation themselves. This is even more important if the algebraic transformation is efficiently invertible in principle, for example if someone has extra secret knowledge (such as the dlog of the base point in use).
If they'd used Dual-EC followed by SHA1 or something that would have not only been better according to folk wisdom, and demonstrably no worse for security (and costing very little compared to the EC operations) but it would also have shut down a lot of conjectured attacks that one could do with twiddled constants.
Yet for some reason, Dual-EC decided to go with an algebraic approach without a "chaotic" output transformation, which is either extreme incompetence or strong evidence that someone is up to no good.
This is really overthinking it. Dual EC is an asymmetric RNG; it "encrypts" its state to a public key, with an undisclosed private key. To believe it wasn't backdoored (as some people, me included, did --- long story!) you have to take on faith that nobody in the world actually has that private key. We're now fairly sure someone does. That's the whole story.
You're probably right, I'm just saying that if you want to design a RNG that doesn't look extremely suspicious, you do it in such as way that there is no way to have a private key to start with. For example with a hash function somewhere in the loop, since these are (presumably) one-way.
[deleted]
> Dual EC DRBG is a bad design and so you shouldn't use it. It is reasonable to believe it's backdoored, but only the same way it would be reasonable to believe David Cameron stuck his dick in a dead pig. Some people say he did, he says he didn't, there's no conclusive proof available - and it's worth noting the "source" is a man who has a grudge against Cameron.
Hard disagree. Dual_EC_DRBG more-or-less encrypts the next state of the random number generator to a certain elliptic curve public key, cuts off a few bits, and outputs the truncated ciphertext as a "pseudorandom number". Given this framing, the backdoor is obvious: guess the truncated bits, decrypt the ciphertext, and check whether the decrypted next state is consistent with later data that depend on that DRBG.
This is a pretty fucking weird design unless you're intending a backdoor. It's orders of magnitude slower and more complex than just symmetric-key encryption or hashing, which are traditionally used for DRBGs, and elliptic curve ciphertexts aren't uniformly pseudorandom so it's slightly biased as a DRBG as well. The claimed justification is that it's secure based on properties of elliptic curves, but even aside from the backdoor this is false (since it's biased), and anyway you'd be going for provable security here but there isn't any proof (even aside from the bias AND the backdoor... except maybe in the generic group model, which is too strong to be relevant here). Also, the backdoor potentials of Dual_EC_DRBG were discussed both before and after standardization, but it was standardized and used anyway.
It is conceivable that NSA chose this design through a firm but misguided belief that it has superior security properties, and that they don't have the private key corresponding to that public key, and that they paid RSA security $10 million to make it the default DRBG in BSAFE because they were just that proud of their generator, and they didn't notice the backdoor before publication, and they didn't consider the need for nothing-up-my-sleeve numbers because they weren't paying any attention. But IMHO it's much more reasonable to believe that Dual_EC_DRBG's backdoor is intentional, and that NSA does know the private key corresponding to their published recommended public key.
Also note that even if NSA doesn't have the backdoor key, a malicious actor can substitute their own backdoor key and everything just keeps working. With this change of 64 bytes of code, fully permitted by the spec, that actor (and nobody else) now controls the backdoor. This happened to Juniper networks.
--
None of this is apparently the case for the NIST elliptic curves, though. While it is possible that NSA knows a secret weakness in them (or, indeed, in all elliptic curves!), even 25 years later there is no publicly known class of weak curves that could include the NIST curves. Furthermore, the spec does include the values that hash to the curves' coefficients: while this doesn't guarantee that those values were really generated randomly, it significantly constrains how a hypothetical backdoor could work, and what the families of vulnerable curves could look like. If there were a backdoor, it would also in some sense be a less powerful backdoor than in Dual_EC_DRBG: the Dual_EC backdoor is only exploitable to someone who has the private key, but given the constraints on the NIST elliptic curves, it is likely that anyone who figured out the math of a hypothetical backdoor could exploit it.
IMHO it is still reasonable to believe that the NIST curves are backdoored. But IMHO they are very likely not backdoored, and I think my view also matches the consensus of the crypto community.
Hard disagree. Dual_EC_DRBG more-or-less encrypts the next state of the random number generator to a certain elliptic curve public key, cuts off a few bits, and outputs the truncated ciphertext as a "pseudorandom number". Given this framing, the backdoor is obvious: guess the truncated bits, decrypt the ciphertext, and check whether the decrypted next state is consistent with later data that depend on that DRBG.
This is a pretty fucking weird design unless you're intending a backdoor. It's orders of magnitude slower and more complex than just symmetric-key encryption or hashing, which are traditionally used for DRBGs, and elliptic curve ciphertexts aren't uniformly pseudorandom so it's slightly biased as a DRBG as well. The claimed justification is that it's secure based on properties of elliptic curves, but even aside from the backdoor this is false (since it's biased), and anyway you'd be going for provable security here but there isn't any proof (even aside from the bias AND the backdoor... except maybe in the generic group model, which is too strong to be relevant here). Also, the backdoor potentials of Dual_EC_DRBG were discussed both before and after standardization, but it was standardized and used anyway.
It is conceivable that NSA chose this design through a firm but misguided belief that it has superior security properties, and that they don't have the private key corresponding to that public key, and that they paid RSA security $10 million to make it the default DRBG in BSAFE because they were just that proud of their generator, and they didn't notice the backdoor before publication, and they didn't consider the need for nothing-up-my-sleeve numbers because they weren't paying any attention. But IMHO it's much more reasonable to believe that Dual_EC_DRBG's backdoor is intentional, and that NSA does know the private key corresponding to their published recommended public key.
Also note that even if NSA doesn't have the backdoor key, a malicious actor can substitute their own backdoor key and everything just keeps working. With this change of 64 bytes of code, fully permitted by the spec, that actor (and nobody else) now controls the backdoor. This happened to Juniper networks.
--
None of this is apparently the case for the NIST elliptic curves, though. While it is possible that NSA knows a secret weakness in them (or, indeed, in all elliptic curves!), even 25 years later there is no publicly known class of weak curves that could include the NIST curves. Furthermore, the spec does include the values that hash to the curves' coefficients: while this doesn't guarantee that those values were really generated randomly, it significantly constrains how a hypothetical backdoor could work, and what the families of vulnerable curves could look like. If there were a backdoor, it would also in some sense be a less powerful backdoor than in Dual_EC_DRBG: the Dual_EC backdoor is only exploitable to someone who has the private key, but given the constraints on the NIST elliptic curves, it is likely that anyone who figured out the math of a hypothetical backdoor could exploit it.
IMHO it is still reasonable to believe that the NIST curves are backdoored. But IMHO they are very likely not backdoored, and I think my view also matches the consensus of the crypto community.
Bernstein's argument is that, even if the NIST curves are not backdoored mathematically, they're designed in a way to strongly coerce implementors towards a route which leaves side-channels open, such as non-constant-time implementations or sloppy handling of invalid data such as points that do not lie on the curve, or in a small-order subgroup (all of which has been seen in practice).
That was an argument that was more credible before than it is now, right? We have complete addition formulas for the Weierstrass P-curves now.
The complete addition formulas part is indeed solved, and could have been solved much earlier if people had read Lenstra's 1995 work. The complete formulas we have today are based on Renes et al. from Eurocrypt 2016, but that refers back to "We're essentially doing Lenstra". The technical detail here is that it's impossible under certain circumstances to get complete formulas that work over extension fields, but that's not necessary to do it over the NIST curves where you're working over the base field GF(p, 1).
That said, I still think the finite-field inversion in ECDSA signatures (instead of doing vanilla Schnorr) is dumb and risky. (Bernstein's deterministic signature improvement is even better, and would probably have prevented the PS3 hack, but I can't blame NIST for this because it was not known at the time. I think you're allowed to do it with the NIST curves too nowadays.)
FIPS 182 gives a non-constant-time implementation of point multiplication with the note "The algorithm given below is for reference purposes. Other (constant time) algorithms that produce an equivalent result may be used." which should be a MUST not a MAY, and in my opinion the non-constant-time one should never have been in the standard in the first place because that (and the accompanying note's wording) encourages people to go with it.
Checking for invalid curve points is also a solved problem in theory, but as far as I know not always implemented correctly in practice.
That said, I still think the finite-field inversion in ECDSA signatures (instead of doing vanilla Schnorr) is dumb and risky. (Bernstein's deterministic signature improvement is even better, and would probably have prevented the PS3 hack, but I can't blame NIST for this because it was not known at the time. I think you're allowed to do it with the NIST curves too nowadays.)
FIPS 182 gives a non-constant-time implementation of point multiplication with the note "The algorithm given below is for reference purposes. Other (constant time) algorithms that produce an equivalent result may be used." which should be a MUST not a MAY, and in my opinion the non-constant-time one should never have been in the standard in the first place because that (and the accompanying note's wording) encourages people to go with it.
Checking for invalid curve points is also a solved problem in theory, but as far as I know not always implemented correctly in practice.
Yeah, and they're pretty performant too.
I also didn't notice when originally replying, but maybe it's worth tacking on:
> ... even if the NIST curves are not backdoored mathematically, they're designed in a way to strongly coerce implementors towards a route which leaves side-channels open ...
[emphasis mine]
The NIST curves are short Weierstrass curves with a=-3. I believe that before 2007 (Edwards), these were generally considered the best, fastest, easiest-to-implement elliptic curves for general operations. Yes, Montgomery curves are faster and simpler for ECDH, at the cost of having a cofactor, but not for signatures.
So it's worth noting that NIST/NSA/Certicom did not choose this family of curves as a trap for implementers. It was the best choice at the time, but Montgomery or Edwards curves are arguably a better choice now.
I also didn't notice when originally replying, but maybe it's worth tacking on:
> ... even if the NIST curves are not backdoored mathematically, they're designed in a way to strongly coerce implementors towards a route which leaves side-channels open ...
[emphasis mine]
The NIST curves are short Weierstrass curves with a=-3. I believe that before 2007 (Edwards), these were generally considered the best, fastest, easiest-to-implement elliptic curves for general operations. Yes, Montgomery curves are faster and simpler for ECDH, at the cost of having a cofactor, but not for signatures.
So it's worth noting that NIST/NSA/Certicom did not choose this family of curves as a trap for implementers. It was the best choice at the time, but Montgomery or Edwards curves are arguably a better choice now.
Bernstein has multiple arguments. Section 7 is about ways that the NIST curves could hypothetically be backdoored, and about designing curves in a "rigid" way such that they are less likely to be backdoored ... at least assuming that small parameters, or parameters near powers of 2, aren't more likely to be weak.
But yeah, he also argues that Montgomery / Edwards curves are easier to implement securely. IMHO he's right, but he exaggerates the difference. Montgomery and Edwards curves still have plenty of footguns, and some of these are not present in prime-order short Weierstrass curves like the NIST curves. In particular, the fact that Montgomery and Edwards curves must have a cofactor of at least 4 leads to problems: side-channel attacks like "May the 4th be with you", EdDSA signature validity not actually being defined, needing additional complexity (Ristretto/Decaf) to avoid protocol changes, etc.
But yeah, he also argues that Montgomery / Edwards curves are easier to implement securely. IMHO he's right, but he exaggerates the difference. Montgomery and Edwards curves still have plenty of footguns, and some of these are not present in prime-order short Weierstrass curves like the NIST curves. In particular, the fact that Montgomery and Edwards curves must have a cofactor of at least 4 leads to problems: side-channel attacks like "May the 4th be with you", EdDSA signature validity not actually being defined, needing additional complexity (Ristretto/Decaf) to avoid protocol changes, etc.
There’s a strong argument against back doors of this type in ECC.
To back door the NIST curves would require that the NSA knows a secret attack against ECC and used brute force search to find seed hashes to generate the curves to be vulnerable. It would have to be a secret attack since nobody else has found it.
Thing is… if this is true it means there is a secret attack against some elliptic curves.
Using 1990s technology they couldn’t have brute forced all that many curves, meaning some non-trivial percentage of curves must be vulnerable.
How do we know curve25519 isn’t vulnerable to this secret attack? We don’t.
The ultimate conclusion is that if NIST curves are backdoored using secret math we shouldn’t use ECC at all, at least unless NSA discloses the math. But they couldn’t do that without blowing up the Internet since so much uses the NIST curves. It would be an argument to phase out all ECC.
To back door the NIST curves would require that the NSA knows a secret attack against ECC and used brute force search to find seed hashes to generate the curves to be vulnerable. It would have to be a secret attack since nobody else has found it.
Thing is… if this is true it means there is a secret attack against some elliptic curves.
Using 1990s technology they couldn’t have brute forced all that many curves, meaning some non-trivial percentage of curves must be vulnerable.
How do we know curve25519 isn’t vulnerable to this secret attack? We don’t.
The ultimate conclusion is that if NIST curves are backdoored using secret math we shouldn’t use ECC at all, at least unless NSA discloses the math. But they couldn’t do that without blowing up the Internet since so much uses the NIST curves. It would be an argument to phase out all ECC.
The argument for a back door goes like this:
1. The NSA is one of the world's only institutions that has any use for the otherwise irrelevant specialism of designing asymmetrically backdoored cryptography algorithms. They also have (or had) lots of maths PhDs writing internal papers. It's reasonable to assume they know things about kleptography that others don't, as it's not a well funded sub-field of cryptography outside the signals intelligence world. So if there was an attack they'd discovered it wouldn't be surprising if others didn't find it.
2. A good protection against kleptographic attacks is to use "nothing up my sleeve numbers", where the constants that go into an algorithm are derived from some well known source that isn't suspicious.
3. The NIST curves know about this sort of risk and attempt to use NUMS numbers. The constants are derived from the output of SHA1, which at the time was considered secure.
4. But the input to SHA1 is a giant random-looking number, not something obvious and above suspicion. Thus the setup fails to provide the assurance it was supposed to create because the NSA could have searched for a weak curve (if there was such a thing to begin with).
The argument that curve25519 wouldn't be susceptible is simply that curve25519 uses NUMS numbers properly, and so there's no wiggle room where djb or anyone else could have done a secret scan to find curves with certain properties.
As may be clear, how strong you think the above argument / problem is, will depend entirely on your intuition about how well explored kleptography is by non-secret research. Unfortunately as people generally don't publish negative results that's very hard to judge.
1. The NSA is one of the world's only institutions that has any use for the otherwise irrelevant specialism of designing asymmetrically backdoored cryptography algorithms. They also have (or had) lots of maths PhDs writing internal papers. It's reasonable to assume they know things about kleptography that others don't, as it's not a well funded sub-field of cryptography outside the signals intelligence world. So if there was an attack they'd discovered it wouldn't be surprising if others didn't find it.
2. A good protection against kleptographic attacks is to use "nothing up my sleeve numbers", where the constants that go into an algorithm are derived from some well known source that isn't suspicious.
3. The NIST curves know about this sort of risk and attempt to use NUMS numbers. The constants are derived from the output of SHA1, which at the time was considered secure.
4. But the input to SHA1 is a giant random-looking number, not something obvious and above suspicion. Thus the setup fails to provide the assurance it was supposed to create because the NSA could have searched for a weak curve (if there was such a thing to begin with).
The argument that curve25519 wouldn't be susceptible is simply that curve25519 uses NUMS numbers properly, and so there's no wiggle room where djb or anyone else could have done a secret scan to find curves with certain properties.
As may be clear, how strong you think the above argument / problem is, will depend entirely on your intuition about how well explored kleptography is by non-secret research. Unfortunately as people generally don't publish negative results that's very hard to judge.
From memory, so I'm probably wrong, but: I thought the bona fides for Curve25519's design was that it demonstrated clear engineering reasons for all its choices, and Bernstein's issue with other curves was that NUMS constants (like pi, e, etc) were manipulable in the sense that you could take permutations of them --- the (silly) B4D455 paper.
NSA did make a mysterious announcement a few years ago that people should not use ECC and should go back to older public-key methods. Of course, due to their fundamental conflict of interest and reluctance to share their rationale, very few organizations that didn't have to follow that guidance apparently did so.
This is a bit misinformed.
NSA required the use of "Suite B Cryptography" for commercial vendors of government systems, which in its latest revision meant ECC. However, vendors were (and are) slow to adopt ECC from the previously used RSA. If you want public evidence of how slow such transitions can be, check any other commercial crypto like certificate authorities and see which trust chains are entirely elliptic curve. Mostly people are stuck on RSA, even though elliptic curves broadly offer better speed and smaller keys/signatures for the same or better levels of security. There's also still plenty of deployed DES and SHA-1, even though the former is inadvisable and the latter inexcusable. In fact, from what I read in the response to the NSA proposing to drop SHA-3 in favour of SHA-2 in the new PQ standards, vendors were a bit frustrated at the change because of the short timescale involved in the migration. I interpret the demanding schedule for adoption of PQC as a deliberate choice by NSA - a somewhat passive aggressive response to vendors to tell them to get their acts together, based on their experience of trying to roll out ECC.
What NSA said is "if you haven't migrated to elliptic curve cryptography, you should now wait for post quantum and then start on that". You can read that message here: https://web.archive.org/web/20151123081120/https://www.nsa.g... and here is the exact quote:
> For those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition.
I don't think there's much mystery here - basically it amounts to a bunch of procurement rules and guidelines.
NSA required the use of "Suite B Cryptography" for commercial vendors of government systems, which in its latest revision meant ECC. However, vendors were (and are) slow to adopt ECC from the previously used RSA. If you want public evidence of how slow such transitions can be, check any other commercial crypto like certificate authorities and see which trust chains are entirely elliptic curve. Mostly people are stuck on RSA, even though elliptic curves broadly offer better speed and smaller keys/signatures for the same or better levels of security. There's also still plenty of deployed DES and SHA-1, even though the former is inadvisable and the latter inexcusable. In fact, from what I read in the response to the NSA proposing to drop SHA-3 in favour of SHA-2 in the new PQ standards, vendors were a bit frustrated at the change because of the short timescale involved in the migration. I interpret the demanding schedule for adoption of PQC as a deliberate choice by NSA - a somewhat passive aggressive response to vendors to tell them to get their acts together, based on their experience of trying to roll out ECC.
What NSA said is "if you haven't migrated to elliptic curve cryptography, you should now wait for post quantum and then start on that". You can read that message here: https://web.archive.org/web/20151123081120/https://www.nsa.g... and here is the exact quote:
> For those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition.
I don't think there's much mystery here - basically it amounts to a bunch of procurement rules and guidelines.
I wasn't aware of this interpretation. Thanks.
> They're changing apt to refuse to download from repositories signed using NIST curves, for instance.
>
> This doesn't make a whole lot of sense unless you think the NSA have an unknown backdoor...
It's "only" a CSPRNG (Cryptographically INsecure PRNG in this case) but the NIST recommending a backdoored curve in the past is an undisputable fact.
So I don't think it's that non-sensical to go for something simple like 2 exp 255 - 19.
https://en.wikipedia.org/wiki/Dual_EC_DRBG
It's "only" a CSPRNG (Cryptographically INsecure PRNG in this case) but the NIST recommending a backdoored curve in the past is an undisputable fact.
So I don't think it's that non-sensical to go for something simple like 2 exp 255 - 19.
https://en.wikipedia.org/wiki/Dual_EC_DRBG
I don't think you should be using words like "undisputable fact" in this thread, because Dual EC isn't a curve; it's a construction that uses curves.
marcosdumay(2)
It begs the question: what's wrong with RSA??? I've always heard it's because implementation is hard and ECC magically solves most of these problems, but clearly that's not the case...
Everyone else is talking about key lengths here, but the better reason to avoid RSA is that it's full of footguns that ECC hides from you. ECC constructions don't generally expose a direct encrypt-to-the-public-key operation, which is almost never what you want (unless you're doing RSA-KEM, which nobody does) but frequently what you get. The de facto standard RSA padding --- by the way, another parameter ECC doesn't demand you fix for your system --- is PKCS1v15, which is admits a padding oracle attack that TLS has spent 2 decades going through contortions avoiding. Even the process of randomly generating keys --- for Curve25519 this is practically a simple as "fill a buffer with random bytes" --- has been fraught with problems.
The reason not to use RSA is that you're not going to get it right, because it's hard to get right. In cryptography, that makes it intrinsically bad on the merits.
The reason not to use RSA is that you're not going to get it right, because it's hard to get right. In cryptography, that makes it intrinsically bad on the merits.
I mostly agree with this, but you could still have advice of like "use only xxx flavor of RSA-KEM for key establishment and yyy flavor of RSA-FDH-SHAKE for sigs" and things would be fine. Those still aren't exactly easy to implement, but they aren't really any harder than ECC. But they do have bigger keys and are slower, especially for keygen.
They are harder to implement than ECC.
Really? My experience is that RSA in general is harder because it has so many knobs, but if you just lock it to the easiest-to-implement-securely choices then it's not so bad.
However, for DJB's point there is a major advantage for X25519/X448 specifically: it's hard to get a huge speedup by implementing them insecurely, and the same is not true of RSA.
However, for DJB's point there is a major advantage for X25519/X448 specifically: it's hard to get a huge speedup by implementing them insecurely, and the same is not true of RSA.
According to the 2020 NIST recommendations, if I'm reading correctly, to get the equivalent of 256 bits of symmetric security, ECC needs 512 bit keys (the factor 2 seems unavoidable for any public key system, because math), but for both RSA and finite-field crypto, you need 15k bit keys to get the same security level.
This is due to the multiplication group modulo a prime (or a pair of primes in RSA) being vulnerable to "index calculus", a faster-than-brute-force way of attacking things.
As the paper says, the main point of ECC is being impervious to index calculus by design, based on an argument by Victor Miller in 1986 about the structure of "point heights" on elliptic curves.
RSA implementations have also led to vulnerabilities in the past, and one of the big claims of djb (as the paper's first author is called in the crypto scene) is that Curve25519 and friends are designed specifically to select, among many secure choices, one that is particularly easy to implement without falling into any of the usual traps.
This is due to the multiplication group modulo a prime (or a pair of primes in RSA) being vulnerable to "index calculus", a faster-than-brute-force way of attacking things.
As the paper says, the main point of ECC is being impervious to index calculus by design, based on an argument by Victor Miller in 1986 about the structure of "point heights" on elliptic curves.
RSA implementations have also led to vulnerabilities in the past, and one of the big claims of djb (as the paper's first author is called in the crypto scene) is that Curve25519 and friends are designed specifically to select, among many secure choices, one that is particularly easy to implement without falling into any of the usual traps.
Even if many older RSA implementations had serious security bugs, that is not the reason why it is not preferred any more.
For equivalent security with ECC (or with AES) at their typical parameters (i.e. 256 to 512 bit elliptic curves or 128-bit to 256-bit AES keys), RSA must use very long keys, even longer than any RSA keys that are used in practice (which are normally no longer than 4096 bits), which makes the RSA operations slow and adds a large overhead to the communication protocols that must send and receive such long keys.
For equivalent security with ECC (or with AES) at their typical parameters (i.e. 256 to 512 bit elliptic curves or 128-bit to 256-bit AES keys), RSA must use very long keys, even longer than any RSA keys that are used in practice (which are normally no longer than 4096 bits), which makes the RSA operations slow and adds a large overhead to the communication protocols that must send and receive such long keys.
>RSA must use very long keys, ...
But probably no longer than 2048 bits:
https://articles.59.ca/doku.php?id=em:20482030
But probably no longer than 2048 bits:
https://articles.59.ca/doku.php?id=em:20482030
imo this article dramatically understates the likelihood that the NSA has unpublished factoring algorithms. it also shows the CPU performance plateau, but GPUs have mostly followed exponential performance scaling
The bottleneck is with a process that can't be parallelized very well. So GPUs are not useful here.
The NSA might have a computer from a crashed alien spacecraft as well but we have to work with what we know. Of course that alien computer is well known to be helpless against RSA and effective against everything else... :)
The NSA might have a computer from a crashed alien spacecraft as well but we have to work with what we know. Of course that alien computer is well known to be helpless against RSA and effective against everything else... :)
that bottleneck is a bottleneck specific to the GNFS. There are about a dozen pretty different factoring algorithms known to the public (e.g. trial division, Polard, ECM, quadratic sieve, GNFS). I don't think any mathematicians believe that the GNFS is the optimal factoring algorithm out there. GNFS has runtime L(1/3, cbrt(64/9)) if there is a known algorithm of say L(1/3, 1.5) which would be a pretty minor optimization equivalent to making the GNFS as good as the SNFS, or a bigger breakthrough of say, L(1/4, 2.5), 4096 bit keys could easily be necessary. For reference, this amount of improvement is about the same as the difference between the Quadratic sieve and GNFS.
Why yes, if there was an algorithm known good enough to make 4096 bit keys necessary then 4096 bit keys would be necessary. But there isn't and there has been little progress for a long time now.
> But there isn't and there has been little progress for a long time now.
publicly. The algorithm side and the hardware side are really really different because we can be pretty sure that the NSA doesn't have a giant super computer that is either dramatically more efficient than commercially available computers, or that uses more than say 1% of US electricity consumption. On the algorithm side, we know that the NSA employs a decent number of number theory people, and given the way that math research progresses, it's pretty easy to imagine that one of those people has found a slight algorithmic improvement over public state of the art. CFRAC was invented in the 1970s. QS invented in the 1980s. The NFS was the 1990s with some improvements in the 2000s. If we go another 50 years or so with no progress, it maybe starts to be reasonable to believe that there isn't a secret algorithm that's better, but with 5 improvements in the last 50 years, it seems pretty likely that there could be 1 more that has been found but not published.
publicly. The algorithm side and the hardware side are really really different because we can be pretty sure that the NSA doesn't have a giant super computer that is either dramatically more efficient than commercially available computers, or that uses more than say 1% of US electricity consumption. On the algorithm side, we know that the NSA employs a decent number of number theory people, and given the way that math research progresses, it's pretty easy to imagine that one of those people has found a slight algorithmic improvement over public state of the art. CFRAC was invented in the 1970s. QS invented in the 1980s. The NFS was the 1990s with some improvements in the 2000s. If we go another 50 years or so with no progress, it maybe starts to be reasonable to believe that there isn't a secret algorithm that's better, but with 5 improvements in the last 50 years, it seems pretty likely that there could be 1 more that has been found but not published.
It's so full of foot-guns that the implementation you are using almost certainly missed a few;
It has been partially broken so many times that it's expected it will be partially broken again; (That's how foot-guns are born.)
It is slow and expensive, even more because every time it's broken people have to increase their key size, making it slower and more expensive;
It's very flexible, so that people keep using it wrong again and again. Arguably that could be a benefit, but it's hard enough to make people use it right, making them get an innovative usage right is almost impossible.
It has been partially broken so many times that it's expected it will be partially broken again; (That's how foot-guns are born.)
It is slow and expensive, even more because every time it's broken people have to increase their key size, making it slower and more expensive;
It's very flexible, so that people keep using it wrong again and again. Arguably that could be a benefit, but it's hard enough to make people use it right, making them get an innovative usage right is almost impossible.
"Seriously, stop using RSA"
https://news.ycombinator.com/item?id=30879442
https://news.ycombinator.com/item?id=30879442
It's hilarious foil-hat level shit here:
https://blog.trailofbits.com/2019/07/08/fuck-rsa/#comment-91...
He is not wrong on the main claim, which is “All ECC (X25519-P521) will be broken by private sector quantum chips before RSA-2048 due to the physical limitations of stabilizing qubits.”
Shor’s algorithm is polynomial, however the number of qubits required is in order of O(log(n)^2), where n is the length of the key. Because ECC keys are much shorter (e.g., 256 to 521 bits) than RSA (2048 to 4096 bits), a smaller quantum computer would be needed to attack ECC.
Shor’s algorithm is polynomial, however the number of qubits required is in order of O(log(n)^2), where n is the length of the key. Because ECC keys are much shorter (e.g., 256 to 521 bits) than RSA (2048 to 4096 bits), a smaller quantum computer would be needed to attack ECC.
RSA needs 4k (or 16k) keys because, with index calculus, these sizes reduce to a subproblem where you effectively need only 2^128 (or 2^256) time rather than the 2^{4k} for brute-force.
I think, but I may be misremembering, that you could apply Shor's algorithm to speed up index calculus by going for the subproblem directly? In this case RSA would fall too.
I note that the NSA recommendations are "move to post-quantum crypto", not "go back to RSA" so I infer that they think RSA-4096 might still be vulnerable.
I think, but I may be misremembering, that you could apply Shor's algorithm to speed up index calculus by going for the subproblem directly? In this case RSA would fall too.
I note that the NSA recommendations are "move to post-quantum crypto", not "go back to RSA" so I infer that they think RSA-4096 might still be vulnerable.
I am not NSA, but I think their idea is something along the “once Shor’s algorithm is practical for key sizes of hundreds of bits, it’s only a matter of a few years of engineering effort to make it feasible for thousands bits long keys”. In other words, there is no sufficient safety margin for larger keys.
This is the first time in nearly 30 years I've ever heard the claim that you only need 18-20 qubits for something like a 256 bit key.
I've only ever seen the claims of 1:1 key bit to qubits. Aren't there existing claimed quantum computers with 20 qubits? Isn't Canada's machine an order of magnitude more qubits?
I've only ever seen the claims of 1:1 key bit to qubits. Aren't there existing claimed quantum computers with 20 qubits? Isn't Canada's machine an order of magnitude more qubits?
I think it matters not only how many qubits you have, but how they are "connected". As far as I know, it's a far easier problem to put N qubits in a chain with O(N) connections, than it is to have N qubits with O(N^2) connections to form a complete graph. And I believe the second example is what you need to do Shor's algorithm.
I am sorry, I should’ve read it twice before posting. I meant, QC to attack longer keys should be bigger proportionally. Number of operations is logarithmic. Silly me.
I'm not sure this is true anymore. There are recent improvements in quantum factoring algorithms, which significantly reduce the number of qubits required. See eg https://eprint.iacr.org/2024/222
My comments on that article:
https://articles.59.ca/doku.php?id=pgpfan:rsabad
https://articles.59.ca/doku.php?id=pgpfan:rsabad
Tl;dr reason: RSA requires larger key sizes, which makes it slower. ECC makes cryptanalysis more complicated, so the keys can be made smaller, which makes it faster.
Seems to be overloaded, see also the earlier site on this topic from the authors: https://safecurves.cr.yp.to
I would like to see if the authors of this paper have released some kind of benchmark/validation script/tool implementing the maths and checks behind their paper
There's a bunch of validation software at https://safecurves.cr.yp.to/verify.html
[deleted]
“We could prove our innocence by disclosing the details, if only we could remember them”, Jerry Solinas, NSA, page 18.
Apparent backstory:
> Some of the backstory here (it's the funniest fucking backstory ever): it's lately been circulating --- though I think this may have been somewhat common knowledge among practitioners, though definitely not to me --- that the "random" seeds for the NIST P-curves, generated in the 1990s by Jerry Solinas at NSA, were simply SHA1 hashes of some variation of the string "Give Jerry a raise".
> At the time, the "pass a string through SHA1" thing was meant to increase confidence in the curve seeds; the idea was that SHA1 would destroy any possible structure in the seed, so NSA couldn't have selected a deliberately weak seed. Of course, NIST/NSA then set about destroying its reputation in the 2000's, and this explanation wasn't nearly enough to quell conspiracy theories.
> But when Jerry Solinas went back to reconstruct the seeds, so NIST could demonstrate that the seeds really were benign, he found that he'd forgotten the string he used!
* https://news.ycombinator.com/item?id=37784499#unv_37784770
> Some of the backstory here (it's the funniest fucking backstory ever): it's lately been circulating --- though I think this may have been somewhat common knowledge among practitioners, though definitely not to me --- that the "random" seeds for the NIST P-curves, generated in the 1990s by Jerry Solinas at NSA, were simply SHA1 hashes of some variation of the string "Give Jerry a raise".
> At the time, the "pass a string through SHA1" thing was meant to increase confidence in the curve seeds; the idea was that SHA1 would destroy any possible structure in the seed, so NSA couldn't have selected a deliberately weak seed. Of course, NIST/NSA then set about destroying its reputation in the 2000's, and this explanation wasn't nearly enough to quell conspiracy theories.
> But when Jerry Solinas went back to reconstruct the seeds, so NIST could demonstrate that the seeds really were benign, he found that he'd forgotten the string he used!
* https://news.ycombinator.com/item?id=37784499#unv_37784770
[deleted]
This doesn't make a whole lot of sense unless you think the NSA have an unknown backdoor that nobody was able to find. But that isn't their stated justification. Instead they cite djb's website. It's apparently not clear enough that the "SafeCurves" are safe in the sense of being easier for cryptographers to implement without bugs, not in the sense that if you have two correct implementations of a "safe" and "unsafe" curve both are equally cryptographically strong.
Therefore if people want to migrate to the "safe" curves over time, that's fine, but it's more like migrating stuff from C++ to Rust. It doesn't automatically imply the prior codebase was buggy, and if you do know of a specific bug then you need to fix it anyway so such migrations are always about reducing the risk of future problems through better engineering practices. That doesn't justify creating a lot of disruption across a distributed ecosystem.