9
$\begingroup$

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.)

Improve this question
$\endgroup$
4

1 Answer 1

Reset to default
20
$\begingroup$

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:

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.

Improve this answer
$\endgroup$
11
  • 4
    $\begingroup$ 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) $\endgroup$
    – poncho
    Commented Aug 11, 2021 at 17:47
  • $\begingroup$ Yup, that's the expectation I was mentioning. But I have doubts we'll be able to have "stable" enough QC to achieve this ^^' $\endgroup$
    – Lery
    Commented Aug 11, 2021 at 17:49
  • $\begingroup$ 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. $\endgroup$
    – miraunpajaro
    Commented Aug 11, 2021 at 18:39
  • 1
    $\begingroup$ 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 on the energy it would take to bruteforce a 256 bits key, but that's for symmetric algorithms, not ECC. $\endgroup$
    – Lery
    Commented Aug 11, 2021 at 18:45
  • 1
    $\begingroup$ @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)}$. $\endgroup$
    – Mark Schultz-Wu ♦
    Commented Aug 11, 2021 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.