9

I am not of the field of IS but I want to secure my humble VPS and I cam across a clashing of opinions between 3 IS guys: 2 say that ed25519 ssh keys are a bit more secure than ssh-rsa of 4096 bytes and one says that in our era, there isn't a significant different at all and either will be just fine for me.

While I don't know who's "right", I went to do some limited reading (limited as I don't have the knowledge to fully understand every passage I read on the subject), and I found out by all that has to do with bytes, public ed25519 keys have much fewer bytes than public ssh-rsa 4096 keys, and hence their private keys are also much shorter.

My question can hence be comprised of the following two questions:

  1. If so, and I'm sorry I think you I need to go and learn 6 months of cryptography --- How are these more secure? I am feeling there is another criterion for their alleged superiority here, and it's not just the amount ob bytes. It's something with formatting.

  2. If it's is only formatting, couldn't we implement this formatting to ssh-rsa 4096 keys? I mean if ed25519 keys contain about 90% less bytes, and we implement their special formatting to ssh-rsa 4096 keys, couldn't we create the most powerful ssh public key ever until now?

  • Dupe http://security.stackexchange.com/questions/101044/is-it-bad-that-my-ed25519-key-is-so-short-compared-to-a-rsa-key and cross http://crypto.stackexchange.com/questions/25577/ecc-vs-rsa-how-to-compare-key-sizes – dave_thompson_085 Nov 20 '16 at 10:30
  • If you are concerned about SSH security, you may find [Secure Secure Shell](https://stribika.github.io/2015/01/04/secure-secure-shell.html) interesting. – Sjoerd Nov 20 '16 at 11:03

2 Answers2

18

Right, welcome to a crypto-nerd battle. Let's try and break this down.

Key length: ed25519 is from a branch of cryptography called "elliptic curve cryptography (ECC)". RSA is based on fairly simple mathematics (multiplication of integers), while ECC is from a much more complicated branch of maths called "group theory". In short: ECC keys can be much shorter and give you the same security level because the mathematical problem they are based on is much more complex. This is far deeper than formatting differences. That's a bit like saying that index cards at the library vs google is a formatting difference.

Security: people tend to like ECC over RSA because the keys are smaller and the computations are faster for the same security level. Below is a table showing the security level comparison of RSA (labeled as Integer Factorization, or IF) vs ECC [source]. You can see that ECC keys really do get the same job done with a smaller key.

enter image description here

So you want to compare RSA-4096 (not in the above table) against ed25519 which has ~ 140 bits of security and is comparable to ~ 3000 bit RSA according to its inventor. Remember that bits is a log scale: 129 bits is twice as secure as 128 bits; 140 bits is 212 = ~4000x as secure as 128, so RSA-4096 might win, but really, anything above 128 bits of security is overkill unless you happen to be a military organisation or a bank.

For putting thumbtacks into your wall, should you use a sledgehammer or a wrecking ball? The correct answer is: whatever.

Mike Ounsworth
  • 57,707
  • 21
  • 150
  • 207
  • Note the actual attack cost (and thus strength) for RSA=IF (and DSA/DH=FF) depends on the attack (factoring) algorithm(s) which have somewhat variable tradeoffs, so the single number used in comparison tables like that is only a rounded-off estimate. But as you say anything over about 128 makes no difference **unless quantum** which is now perceived as a great but unquantifiable risk. – dave_thompson_085 Nov 20 '16 at 10:39
  • Thanks Mike. Can you please elaborate more on "That's a bit like saying that index cards at the library vs google is a formatting difference." ? –  Nov 20 '16 at 12:49
  • @dave_thompson_085 I actually know quite a bit about quantum crypto: once quantum computers become real, ECC reduces to like 2 bits of security, and RSA reduces to like 5 bits of security, almost regardless of key size. The bigger question is "When"? – Mike Ounsworth Nov 20 '16 at 15:37
  • @Benia That comment was a bit of a tongue-in-cheek way of saying that "formatting difference" is an understatement when you have two things that do the same job, but one is a newer, more advanced technology. – Mike Ounsworth Nov 20 '16 at 15:40
  • 1
    @MikeOunsworth I don't believe that's true wrt quantum computers. Both ECC and RSA can be factored in polynomial time if the quantum computer has enough (logical) qubits. If it has 6p qubits (for ECC) or 2p+3 qubits (for RSA), where _p_ is the bit size of the algorithm, it can break it quickly. So 4096-bit RSA requires at least 8195 qubits, whereas 256-bit ECC requires 1536 qubits. – forest Sep 16 '18 at 00:51
  • @forest Well pointed out, but hey, this answer's 2 years old :P – Mike Ounsworth Sep 16 '18 at 01:33
3

You can't directly compare key sizes for RSA and ECC. A 2048 bit RSA key does not give the same security as a 2048 bit ECC key. Here is a table that gives an indication of the security:

table

Sjoerd
  • 28,707
  • 12
  • 74
  • 102