20

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?

  • 1
    I think you're getting downvoted because a simple A vs B google search would give you nice results like ssl.com/article/comparing-ecdsa-vs-rsa – Pablo Recalde Apr 28 at 18:37
  • I don't know how long Tectia has implemented ECC, but it (at least the X9/NIST version) was standardized for SSH in 2009 and has been implemented in OpenSSH since at least 2012. That isn't really 'new', although it is less old than the first implementations of any SSH v2. – dave_thompson_085 Apr 29 at 4:04
  • 2
    Not a security point, and probably not worthy of an answer, but one key advantage that RSA has over ECDSA is that it's more widely and consistently supported. SSH does better than SSL in this regard, but support for ECDSA and for particular curves is not universal, especially if you need to support old or weird implementations. – James_pic Apr 29 at 13:36
  • 4
    For what it's worth, SSH.com is the long-obsolete commercial fork of SSH from decades ago that nobody serious uses anymore. OpenSSH is the modern SSH. – R.. GitHub STOP HELPING ICE Apr 30 at 1:26
  • @James_pic and the number of places that do a regex match to reject anything that's not an RSA key is high. Often some of them if you bypass the clientside regex it continues to work just fine, so hopefully as ECDSA keys become more used they'll become more supported. – Mark Henderson Apr 30 at 21:15
17

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.

| improve this answer | |
  • 1
    Also another improvement is the speed of the operations that is faster on ECC than on RSA. – camp0 Apr 28 at 20:22
  • 5
    It should be mentionned many cryptographers are suspicious that NIST curves used in ECDSA might be designed as backdoors. See git.libssh.org/projects/libssh.git/tree/doc/… for a summary of the concerns. – alci Apr 29 at 9:57
24

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.

| improve this answer | |
5

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

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

| improve this answer | |
  • This table is available inside the first link in my answer. – Z.T. Apr 28 at 20:54
  • 8
    @Z.T. The first link of your answer is a pretty interesting tool for sure, and it contains a comparison between 8 different recommendations including NIST, NSA, BSI, etc, and be sure I checked it before giving my answer. I just find NIST table to be pretty illustrative and after all it would be easier to watch it here without extra-clicks. Cheers! – Alexander Fadeev Apr 28 at 21:22
3

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.

| improve this answer | |
  • How would one know if the random number generator fails? – leeand00 Apr 30 at 2:05
  • 1
    That in general is a very difficult problem. There are loads of ways a random number generator can look good in testing but end up creating duplicate sequences in production. – Peter Green Apr 30 at 2:17
  • and duplicate "random" number sequences can lead to duplicate nonces which are the Achilles heel of basic DSA implementations. – Peter Green Apr 30 at 2:18
  • 2
    so sometimes the first you know about a rng failure is when someone finds singatures with duplicate nonces in the wild and recovers the private key........ – Peter Green Apr 30 at 2:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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