90

A lot of people recommend using Ed25519 instead of RSA keys for SSH.

The introduction page of Ed25519 (http://ed25519.cr.yp.to/) says:
[..] breaking it has similar difficulty to breaking [..] RSA with ~3000-bit keys [..]

So speaking only of security (not speed!), why should one not prefer RSA 4096 over Ed25519?
If Ed25519 only provides ~3000 bit key strength, RSA with 4096 bit should be much more secure?

2
  • It's helpful to mind the power of… well, powers, the exponentials. The difference between 3000 and 2592 (citing the Tom Leek's answer) is still a few puny times greater than 10^120, an unimaginably large number, exceeding the total count of particles in this Universe by an unimaginably large factor. If you'd somehow be able to compute something of the O(2^2592) time complexity, that would still be nearly infinitely far away from O(2^3000). To be fair, the complexity of factorization might not grow linearly with the number length--and, of course, P-vs-NP is still a $1M open question… :)
    – kkm
    Feb 15 '20 at 11:45
  • @kkm while i was reading your comment i felt a few cells on my brain explode :-D
    – giomanda
    Oct 28 '20 at 0:12
88

Key strengths, and their equivalences, become meaningless when they reach the zone of "cannot be broken with existing and foreseeable technology", because there is no such thing as more secure than that. It is a common reflex to try to think of key sizes as providing some sort of security margin, but this kind of reasoning fails beyond some point.

Basically, the best known algorithms for breaking RSA, and for breaking elliptic curves, were already known 25 years ago. Since then, breaking efficiency has improved because of faster computers, at a rate which was correctly predicted. It is a tribute to researchers that they could, through a lot of fine tuning, keep up with that rate, as shown on this graph:

Factorization records over time

(extracted from this answer).

The bottom-line is that while a larger key offers longer predictable resistance, this kind of prediction works only as long as technology improvements can be, indeed, predicted, and anybody who claims that he knows what computers will be able to do more than 50 years from now is either a prophet, a madman, a liar, or all of these together.

50 years from now, the optimistic formula given in the answer quoted above ((year - 2000) * 32 + 512) means that, at best, RSA records could contemplate approaching 2592 bits.

The conclusion is that there is no meaningful way in which 3000-bit and 4000-bit RSA keys could be compared with each other, from a security point of view. They both are "unbreakable in the foreseeable future". A key cannot be less broken than not broken.

An additional and important point is that "permanent" keys in SSH (the keys that you generate and store in files) are used only for signatures. Breaking such a key would allow an attacker to impersonate the server or the client, but not to decrypt a past recorded session (the actual encryption key is derived from an ephemeral Diffie-Hellman key exchange, or an elliptic curve variant thereof). Thus, whether your key could be broken, or not, in the next century has no importance whatsoever. To achieve "ultimate" security (at least, within the context of the computer world), all you need for your SSH key is a key that cannot be broken now, with science and technology as they are known now.

Another point of view on the same thing is that your connections can only be as secure as the two endpoints. Nothing constraints your enemies, be they wicked criminals, spies or anything else, to try to defeat you by playing "fair" and trying to break your crypto upfront. Hiring thousands upon thousands of informants to spy on everybody (and on each other) is very expensive, but it has been done, which is a lot more than can be said about breaking a single RSA key of 2048 bits.

7
  • 2
    last §: good to remind the lowest point of the wall :).
    – dan
    May 26 '15 at 0:29
  • 3
    The logic is flawed. We don't know what kind of advances will happen in the future, so don't pick really large key sizes today? How does that even make sense? There are many meaningful ways that key sizes can be compared across different crypto systems. It is, in fact, the subject of much research. See keylength.com/en for references on half a dozen papers on the subject. Dec 8 '18 at 4:40
  • 3
    @KurtFitzner The logic is not flawed, when security reaches certain threshold then anything else becomes irrelevant and unnecessary. The purpose of these keys is to provide authentication now, not "whenever is possible to break it", duh. No one is gonna be using the same key 50 years from now, not even 10 years... For the same reason you should change passwords, you also change the keys you use to authenticate. Therefore more key length becomes completely irrelevant.
    – Chazy Chaz
    Jan 5 '19 at 21:31
  • 4
    There are lots of 50 year-old documents that are still secret today. We can assume that some documents created this year will need to be secret (according to somebody) in 50 years. If that document is to be transported via SSH today, then @KurtFitzner's concern is valid.
    – daveloyall
    Apr 17 '19 at 20:35
  • 2
    @WedTM That assumes that nobody gets a copy of the encrypted document tomorrow. Re-encrypting my copy of a document in five years wouldn't affect their copy.
    – daveloyall
    Feb 19 '20 at 19:41
7

According to gitlab

The book Practical Cryptography With Go suggests that ED25519 keys are more secure and performant than RSA keys.

and recommends

If you use RSA keys for SSH ... that you use a key size of at least 2048 bits.

the ED25519 key is better

ssh-keygen -t ed25519 -C "<comment>"

If rsa is used, the minimum size is 2048 But it is better to use size 4096:

ssh-keygen -o -t rsa -b 4096 -C "email@example.com"

ED25519 already encrypts keys to the more secure OpenSSH format.

3
  • As that gitlab page correctly says (except for 'inclusive' where it should be 'left-inclusive') -o is not needed in OpenSSH 7.8 (2018-08) up because new format is now the default. Sep 14 '20 at 0:11
  • 3
    FYI, the main factor that caused the author of Practical Cryptography WIth Go to declare that ED25519 is more secure than RSA is that ED25519 is more robust against PRNG (Pseudo-Random Number Generator) failures.
    – cowlinator
    Jun 17 '21 at 0:37
  • 1
    Not only is ed25519 provably better, but if for no other reason, having a shorter key is a nice bonus too.
    – DeeJayh
    Sep 10 '21 at 10:02

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.