Should I be using ECDSA keys instead of RSA?

Question

I read on ssh.com that there are new ECDSA ssh keys that one should be using to create the public / private key pair; and that's it's a US Government Standard based on elliptical curves (probably something mathy). I also noticed that they use fewer bits, so I'm unsure how it is supposed to be more secure. Have you heard anything about this, and if it uses fewer bits how on earth could it be more secure?

Answer 1

For "bits of security", see something like this comparison.

For why ECC over Prime Field gives you security equivalent to half the bit size, while RSA and FFDHE give much less security per-bit, it's because the strength of RSA against the best known attack is calculated like this while the strength of ECC against best known attack is calculated like this.

The NIST P-256/384/521 curves are safe, and ECDH over them and the ECDSA algorithm are safe, but they are a previous generation of curves and algorithms. The advancement since then has been in three areas:

1. Choosing a curve in a non-arbitrary way so that it is much more "nothing up my sleeve", to ensure the curve isn't one in which the NSA have a way to break crypto faster than brute force, which people worry about. You shouldn't worry IMO, for these reasons, but some people consider it a reason to upgrade from NIST curves.
2. Ease of implementation, or equivalently, chance of a random implementation turning out to be secure.
3. Performance.

The state of the art currently and the ECC systems recommended by everyone is X25519 ECDH (Curve25519 ECDH) and Ed25519 Digital Signatures / long term keys. Basically everyone agrees they are better than NIST P-256 ECDH and ECDSA. A drawback is that they are not supported in HSMs and hardware tokens like Yubikeys.

If you can use software SSH host keys, you should use Ed25519 host keys.

If you can use software SSH user keys, you should use Ed25519 user keys.

If you can use curve25519 key exchange, you should use it.

The fallback for 25519 is NISP P-256. The fallback for P-256 is RSA and FFDHE, with at least 2048 bits (up to 4096 bits), both with SHA2 and not with SHA1. RSA with SHA1 and FFDHE with SHA1 are not allowed anymore.

Note that all of these systems will fall if and when someone builds a big enough quantum computer. To solve this problem, people are working on "post quantum" replacements that will be secure even if the adversary has a quantum computer. NIST is waiting for PQ Crypto competition to end, issue recommendations and standards, hardware crypto device vendors to start selling PQ devices, and everyone will upgrade to the PQ algos.

Because this upgrade is imminent (in NIST time frames), they have decided to not urge everyone to upgrade from P-256 to Curve25519, or even from RSA to ECC. NSA basically said to save your budget for the PQ upgrade.

People using SSH keys not stored in hardware devices have upgraded though, and everyone has upgraded ECDH because ephemeral keys don't need hardware secure storage.

Even the ossified TLS ecosystem (not SSH) has upgraded to X25519 ECDH, though they can't upgrade to Ed25519 because there are no HSMs available and they basically decided to wait for PQ crypto standards and HSMs. The standards / RFCs are available, it's just nobody uses them.

Answer 2

ECC keys can be much shorter than RSA keys, and still provide the same amount of security, in terms of the amount of brute force that an attacker would need to crack these keys. For example, a 224-bit ECC key would require about the same amount of brute force to crack as a 2048-bit RSA key. See https://wiki.openssl.org/index.php/Elliptic_Curve_Cryptography for more info.

Answer 3

To be complementary to other answers, just let me share a nice table taken from NIST SP 800-57:

Basically, what you can see here is that you would need RSA 3072 bit vs ECDSA 256-383 bit to achieve the same level of security strength (128-bit).

Answer 4

There are pros and cons.

We rate the security strength of algorithms by asking "using the best known attack how long would it take to break this". There is a known attack on RSA and traditional prime based DSA that is considerably better than the best known approaches for ECDSA. Therefore a much longer key length is needed to get an equivilent security level with RSA or prime-based DSA than with ECDSA.

However this is taken account of in the key lengths that are practically used, there is no reason to believe that a 4096 bit RSA key will be broken any time soon, even 2048 bit is probably fine for a while.

Unfortunately there are a couple of potential caveats with the basic ecdsa standards.

• There are some suspicions among the more paraniod in the crypto community that the widely used nist curves may have been backdoored such that the US government has shortcuts to cracking the crypto.
• Basic implementations of DSA and ECDSA are highly sensitive to random number generator failure. Making signatures with a bad random number generator can lead to compromise of the key (even if the key was generated with a good random number generator).

ed25519 fixes these issues by using a "nothing up my sleeve" curve and by using a deterministic variant of the signature algorithm but the curve chosen "only" gives about 128 bits of security (which by most comparisons makes it stronger than RSA2048 but weaker than RSA4096). It's been supported by openssh since 2014 so it's probably not a bad choice if you are happy with the 128 bit security level and you don't need to log into legacy systems.

ed448 uses the same algorithm as ed25519 with a curve that gives 224 bits of security making it more secure than RSA4096. Unfortunately while there is a standard for ed448 in ssh the dominant implementation openssh does not seem to support it.