SSH Key: Ed25519 vs RSA

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

    The introduction page of Ed25519 ( 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?

    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 while i was reading your comment i felt a few cells on my brain explode :-D

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

    last §: good to remind the lowest point of the wall :).

    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 for references on half a dozen papers on the subject.

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

    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 That's not how it works. You encrypt the document *today*, and in 5 years, re-encrypt it with a key that is of appropriate length for that time. Do it again every 5 years. In 50 years, your document is still secure, and it is encrypted with of-the-day standards.

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

  • 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 protected]om"

    ED25519 already encrypts keys to the more secure OpenSSH format.

    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.

License under CC-BY-SA with attribution

Content dated before 7/24/2021 11:53 AM