Score:7

Crypto

Why are NIST curves still used?

miraunpajaro

12/11/22, 3:04 PM

I'm relatively new to the world of crypto (But as far as the math goes, I am familiar with the inner workings. I used to rarely use it for privacy, but now I use it for many things).

Anyway, I was taking a look at this URL, and of course I noticed that NIST curves seem to have a lot of weaknesses. More than other curves, such as E-521, which, as I understand, has been mathematically proven to be secure to most known attacks.

From this I have a couple of questions that I was hoping someone could explain to me:

Why does GPG offer NIST encryption if it's less safe than others? Why don't they offer the safest options?
My GPG keys are all of the NIST category, should I change them? (Incidentally, my signing subkey is different, but still of a vulnerable kind.)

2689

1 + 4

elliptic-curves

public-key

pgp

nist

miraunpajaro

12/11/22, 3:27 PM

@Patriot Thanks! You're right, I changed it, I think now is more correct. On your first comment, does this mean that it's a common complaint? Shouldn't this be a priority issue for, let's gnupg?

poncho

12/11/22, 5:11 PM

The best known attack against Curve25519 is four times easier than the best known attack against P256. How then is P256 a 'less secure' option?

dave_thompson_085

12/11/22, 10:33 PM

Mostly dupe https://crypto.stackexchange.com/questions/52983/why-is-there-the-option-to-use-nist-p-256-in-gnupg https://crypto.stackexchange.com/questions/52859/why-is-c25519-in-the-gpg-expert-options https://security.stackexchange.com/questions/160311/which-ecc-to-choose-with-gpg

Lery

12/12/22, 2:24 PM

Also related: https://crypto.stackexchange.com/q/44397/29574

Score:17

Crypto

Lery

12/11/22, 4:25 PM

This is a though question that is surfing at the limits of meta/political wars within the cryptography community.

SafeCurves is a good resource, but it's very opinionated about what "safe" means. As an example secp256k1, the curve used by Bitcoin and Ethereum to guarantee their security is deemed "unsafe" by the SafeCurves team, while it currently has over a 1000+ B$ "bug bounty" in the form of BTC and ETH that could be hacked if you could break it...

So, no, it's not because SafeCurves says something is not "safe" that it means it's "broken". NIST curves could be better, sure, but they still work and do their job and (as far as we are aware of) there are no effective, practical attacks against them that would threaten systems that are currently using them, as long as they are "properly" implemented... Which means they aren't broken, and I wouldn't personally say they aren't "safe" for usage in 2021. But if I'm designing a new system where I can choose whatever key agreement mechanism or signature algorithm, they also aren't my first choice.

A huge problem when you're working in software (and hardware) development is "compliance", and the NIST are the ones issuing the "standards" that are considered as the holy grail in the compliance world, I'm afraid.
So, while they are currently working on new drafts (e.g. the draft for FIPS 186-5 is currently including Ed25519 as a signature algorithm) containing more "modern" curves, they still haven't yet updated their recommendations and standards and as such many entities are mandated to rely on their good old recommendations such as the P-256 curve.

Compatibility is also a big issue. For example, the NIST P-256 curve is supported by Web Crypto API, which should be constant-time and "secure" (in the sense "we don't know effective, practical attacks against it"). Meanwhile the more modern Curve25519 is considered to be safer and less prone to implementation errors than P-256, but it isn't supported by Web Crypto API yet. So, to do JavaScript stuff using ECC, you're better off using P-256 than Curve25519 for now. (Or WASM, but that's another topic.)

Also, it's important to notice that GnuPG is following the OpenPGP specifications and is trying to be a widely interoperable, inter-compatible tool. As such it supports a LOT of different schemes, amongst which some are older than other, some are more or less used. There is a draft including Ed25519 and X25519 support in PGP that is currently open and has been actively worked on for the past few years:

https://datatracker.ietf.org/doc/draft-ietf-openpgp-crypto-refresh/03/

The same compatibility issues also arise with PGP: if you want to be able to easily communicate with others using it, it's best to use something others are also using/supporting.

So, PGP will get there at some point, but it's a slow process and as long as these old curves and standards aren't practically (or at risk of being) broken, this slow process likely won't accelerate.

Now, should you change your PGP keys if you're using P-256 or another curve whose "cost for rho" is above 2^100 in that list: https://safecurves.cr.yp.to/rho.html ? I would say "No". You don't need to worry for now, at least for the next 5 years, possibly more. But Quantum Computers might change this story in a few more years shall they be as effective as we expect them to be at breaking the discrete logarithm problem in practice.

0 + 11

poncho

12/11/22, 5:47 PM

One "real" Quantum Computers exist (where "real" means 'large and reliable enough to run Shor's algorithm on the size of curves we use), all elliptic curves become insecure (exception: supersingular isogeny-based methods, which works completely differently)

Lery

12/11/22, 5:49 PM

Yup, that's the expectation I was mentioning. But I have doubts we'll be able to have "stable" enough QC to achieve this ^^'

miraunpajaro

12/11/22, 6:39 PM

Very nice! One question about quantum computers. AFAI, there are lower bounds on how much energy it would take to brute force some ecc algos. Do these bounds apply to quantum computing? My guess is no, but idk.

Lery

12/11/22, 6:45 PM

No, any ECC algo (that isn't isogney-based) is broken by a quantum computer. Also, you are probably mixing up with the [famous bound](https://crypto.stackexchange.com/a/1160/29574) on the energy it would take to bruteforce a 256 bits key, but that's for symmetric algorithms, not ECC.

Mark

12/11/22, 7:16 PM

@Lery the important point is actually that it is for brute forcing, while a functioning QC allows one to do much better than brute force against ECC.

miraunpajaro

12/11/22, 7:17 PM

Aahh I see. And symmetric crypto is quantum resistent, I see.

miraunpajaro

12/11/22, 7:18 PM

@Mark Could you elaborate? How exactly?

Mark

12/11/22, 7:21 PM

@miraunpajaro if one were brute forcing ECC, it would take $\Theta(2^\lambda)$ time (essentially by definition). Generic techniques in quantum computing (Grover's algorithm) often let you bring this down to $\Theta(2^{\lambda/2})$ - you can stop this via doubling key sizes though. The issue with ECC is that Schor's algorithm exists, which brings the complexity of DLOG (over a group of size $O(2^\lambda)$) down to (quantum) polynomial time, e.g. $\lambda^{O(1)}$.

Mark

12/11/22, 7:25 PM

The energy expenditure bound itself essentially says "you pay a minimum amount of energy for each bit of energy that is erased". This probably means that there isn't a quantum analog (quantum computing is, up until you measure, "reversible"), but you could bound the amount of energy to solve DLOG over a generic group (which has a lower bound of $\Omega(2^{\lambda/2})$ in the classical setting --- the bound itself isn't specific to symmetric crypto.

poncho

12/12/22, 2:14 AM

@Mark: actually, there are generic techniques in classical computing that break ECC in time $\Theta(2^{\lambda/2})$ - these attacks rely on the group structure of ECC

Mark

12/12/22, 5:17 AM

@poncho Yes, that is why I wrote $\Omega(2^{\lambda/2})$ and not $\omega(2^{\lambda/2})$. I wrote $\Omega(\cdot)$ instead of $\Theta(\cdot)$ to highlight that the argument cares about the *lower bound* specifically (and the fact that a matching upper bound exists doesn't matter), perhaps this was somewhat pedantic.