Generate new key - ECC vs RSA

Question

I intend to start using GnuPG again. I haven't used it for the last 2 years and was surprised that there is now the option for RSA and ECC keys.

After reading a bit about ECC, it seems to me there is quite a bit uncertainty about where it is going and what curves should be used. There were for example some discussions about whether or not the NIST curves are compromised or not. GnuPG 2.1.11 and libgcrypt 1.6.5 could only choose between NIST- and Brainpool-Curves (Which ECC to choose with GPG?) and this was only 8 month ago. Now we can choose the 25519-Curve too (GnuPG 2.1.18).

My questions are is it safe start using ECC or should one stick with RSA for at least a few more years? I guess I would use the 25519-Curve. But is this curve compatible to older GnuPG versions and other systems or are there some problems? Will this be something we can use for the next few years or should I expect some constant changing in terms of some curves being standardized and staying for a long time (like RSA) and supported by all systems, but some curves might disappear because they're not trustworthy? I also came across a paper where the NSA recommends keep using RSA and wait for Post-Quantum-Cryptography instead of using ECC.

I'm just an average GnuPG-user but it seems to me there is some sort of uncertainty about the way cryptography will develop within the next few years.

Answer 1

It's fine to stick with RSA. ECC is more space-efficient, but it is not supported everywhere.

My questions are is it safe start using ECC or should one stick with RSA for at least a few more years?

When using curve25519, ECC is considered more secure. It is fast and immune to a variety of side-channel attacks by design. RSA is no less secure though in practical terms, and is also considered unbreakable by modern technology. It is sufficiently fast for use by GnuPG.

But is this Curve compatible to older GnuPG-Version and other systems or are there some problems?

It is incompatible with older systems. It is necessary for all parties to support the same algorithm. You can, however, have multiple subkeys. You can have a single newer subkey with ECC, and an older one with regular RSA which could later be revoked once ECC support is ubiquitous.

Also will this be something we can use for the next few years or should I expect some constant changing in terms of some curves will be standardized and stay for a long time (like RSA) and supported by all systems and some curves might be disappear because they're not trustworthy?

ECC is old. Not as old as RSA, but it is still old and well-studied. It is unlikely that curve25519 will disappear due to trustworthiness as it uses nothing-up-my-sleeve numbers. It is a safe curve. Curve25519 uses modulo p = 2²⁵⁵ - 19 and y² = x³ + 486662x² + x. Compare this with a standard NIST curve like P-256 where these values are... unexplained at best, leading people to speculate that they were designed intentionally to weaken them to classes of attacks known only to the NSA (NOBUS). The only reason it would fall out of favor is if a major attack on this class of curves is found.

I also came across a paper where the NSA recommends keep using RSA and wait for Post-Quantum-Cryptography instead of using ECC.

This is in part because ECC requires a smaller key size. For classical security, this is absolutely fine, and a 256-bit ECC key can be stronger than a 2048-bit classical key. Both of these types of keys can be broken by functioning cryptanalytic quantum computers. For a quantum computer to function, it needs a number of qubits (the quantum equivalent of transistors). It is very difficult to get a large amount of qubits to work together due to a phenomenon known as quantum decoherence, so the number of qubits may be limited for some time. It is possible that a cryptanalytic quantum computer will have enough qubits to break a 256-bit ECC key, but not a 2048-bit RSA key. It may be better to wait for post-quantum cryptography like SIDH, NTRU, or NewHope which resist all these attacks.

I'm just an average GnuPG-user but it seems to me there is some sort of uncertainty about the way cryptography develops within the next few years.

It is perfectly acceptable to keep using RSA. Once ECC is better supported, you can migrate to it in the form of a new subkey. ECC keys and signatures are much smaller, so if this is a priority for you, you may want to start using ECC. RSA keys and signatures are large and can be quite unwieldy.

Answer 2

The advantage of elliptic curves is that they allow much smaller keys for a given level of presumed-security*.

However to the best of my knowledge.

1. Some popular curves were created by the US government with no indication given as to why the parameters were chosen. There is concern among the more paranoid types that the US government may have "backdoored" the curve by choosing the parameters in a way that helps them crack cryptography based on the curve.
2. There exist "nothing up my sleeve" curves which are newer but then software support becomes more of an issue.
3. Traditional ECDSA (like DSA but unlike RSA) is critically reliant on the random number generator on systems used for signing. EdDSA fixes this but it's a pretty new option (read: may not be supported in environments using older but still supported software) and only appears to be supported with curve 25519.
4. Curve 25519 is a "nothing up my sleeve" curve from a respected non-government cryptographer but it's "only" aimed at the 128 bit security level.
5. ECC in general is fairly new as far as I can tell it is not supported at all by GnuPG 1.x. Some still supported distro releases are still on 1.x as their main GnuPG implementation.
6. While quantum computing is a threat to all classical cryptography, it seems that it is more of a threat to ECC than RSA (given current practice key lengths for both).

Given all of the above, I'm sticking with 4096 bit RSA.

* That is the time to crack the key given the best currently known attacks.