2
$\begingroup$

According to ssh_config(5), HostKeyAlgorithms “specifies the host key algorithms that the client wants to use in order of preference ... The default for this is:

ecdsa-sha2-nistp256-cert-v01@openssh.com,
ecdsa-sha2-nistp384-cert-v01@openssh.com,
ecdsa-sha2-nistp521-cert-v01@openssh.com,
ssh-ed25519-cert-v01@openssh.com,
rsa-sha2-512-cert-v01@openssh.com,rsa-sha2-256-cert-v01@openssh.com,
ssh-rsa-cert-v01@openssh.com,
ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,
ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa

This lists ECDSA keys before Ed25519 key, and also prefers ECDSA keys with curves nistp256 over nistp384 and that over nistp521.

I was under impression that Ed25519 is generally superior to ECDSA keys, and that keys with higher n curves, at least of these three, are more secure.

So why OpenSSH lists the algorithms in this order?

Also, I'm developing an Android application that uses SSH as a transport. It also needs a list of preferred host key algorithms. Would it be a good idea to replicate OpenSSH's list in the app? Or should I prefer ed25519 over ecdsa with nistp521 over -384 over -256 over rsa keys?

$\endgroup$
2
  • $\begingroup$ Interesting question. I hope someone can give an answer that is not opinion based. $\endgroup$
    – kelalaka
    Sep 30 '20 at 18:50
  • 2
    $\begingroup$ @kelalaka I would say my answer is only partially opinion based, since I used my judgement in parsing the changelog notes $\endgroup$ Oct 1 '20 at 0:11
6
$\begingroup$

If I remember correctly, it is simply an issue of performance. Remember, HostKeyAlgorithms determines the method used to authenticate the server to the client, it does not generate session keys.

The ECDSA algorithm is faster than RSA, and small key sizes are faster than large key sizes, when the default was changed in 5.7, the changelog specially referenced performance reasons, See the first feature item.

NIST keys are probably preferred over ED25519 for compatibility reasons, I have had to generate NIST keys after Curve25519 based keys after finding the server did not support them, so that makes total sense. Curve25519 based keys are probably more secure, unless you are asking NIST, then they say the are equally secure.

Since these are just default options, you are of course free to change them or force a specific algorithm, I have forced 3072-bit RSA for my default host key method. Remember, this is a selection option, if a key type on the list does not exist, it will not be used. If you only have RSA keys in your configuration, all the EC options will be skipped, you can delete them at will.

If you are using SSH for transport and you have control over the app and server, you can just generate the 1 host key you want and be done with it, and ignore the configuration options, since they will not matter.

$\endgroup$
8
  • $\begingroup$ Interesting and let's hope that the simple metric of performance is not going to be a problem in the future. $\endgroup$
    – kelalaka
    Oct 1 '20 at 6:07
  • $\begingroup$ @kelalaka it should not be, using a smaller key size for authentication should only require you to refresh the key more regularly, but on a server were hundreds or even thousands of SSH connections may be simultaneously active, that performance benefit can be huge $\endgroup$ Oct 1 '20 at 20:46
  • $\begingroup$ @RichieFrame What do you mean “after finding the server did not support them”? Unless you are reusing keys of a different server, which is highly not recommended, I don't see why this would be an issue. During connection, the host key algorithm is primarily chosen by client preference, so unless you only offer Ed25519 keys, a client that doesn't support them would still be able to connect. Said that, it appears that Ed25519 is slightly slower than ECDSA nistp256 (see my answer), so maybe it makes sense to have that first. I'm still not sure why -386 and -521 are preferred over 25519, though. $\endgroup$
    – squirrel
    Oct 2 '20 at 18:05
  • $\begingroup$ @squirrel I mean the version of OpenSSH did not support ED25519 or Curve25519, because it was old, and on the client side I had only generated a Curve25519 key pair and nothing else $\endgroup$ Oct 2 '20 at 20:13
  • $\begingroup$ @RichieFrame but host key verification is used to verify the server, not the client. i don't suppose you made keys for the server on the client machine? $\endgroup$
    – squirrel
    Oct 2 '20 at 20:37
4
$\begingroup$

So I got curious as to how fast things actually are. Apparently you can use $ openssl speed to see how fast certain operations are. I am not sure, however, as to how this translates to actual performance issues when connecting to an SSH server.

As a part of the Diffie-Hellman key exchange, the SSH server computes a certain hash and then signs it with its private host key. The client then computes the same hash and verifies the server signature. So it's useful to look at how slow both of these operations are. The signing operation is perhaps more important as servers tend to have much more SSH connections than clients.

The signing/verifying operation will typically involve another hashing operation; it is going to be a part of the host key verification algorithm. E.g. ssh-rsa is going to use sha1 and ecdsa-sha2-nistp521 is going to use sha512. I am not sure if the numbers below include hashing times. In either case, it seems that for data > 16 bytes sha256 and sha512 perform comparably.

I tested this on three devices:

  • Thinkpad X220, Intel Core i5-2520M

                                  sign      verify      sign/s verify/s
      rsa 2048 bits               0.001350s 0.000048s    740.8  20913.2
      rsa 3072 bits               0.006107s 0.000094s    163.7  10639.3
      rsa 4096 bits               0.010134s 0.000158s     98.7   6316.4
      rsa 7680 bits               0.089906s 0.000525s     11.1   1903.0
      rsa 15360 bits              0.468636s 0.002004s      2.1    499.0
      dsa 2048 bits               0.000600s 0.000519s   1667.5   1927.0
      256 bits ecdsa (nistp256)   0.0000s   0.0001s    23594.7   7348.1
      384 bits ecdsa (nistp384)   0.0016s   0.0011s      620.4    890.8
      521 bits ecdsa (nistp521)   0.0005s   0.0009s     1866.4   1080.1
      253 bits EdDSA (Ed25519)    0.0001s   0.0002s    15737.2   6078.1
    
  • Xiaomi Mi A2, Qualcomm SDM660 Snapdragon 660

                                  sign      verify      sign/s verify/s
      rsa 2048 bits               0.004257s 0.000111s    234.9   9030.1
      rsa 3072 bits               0.012975s 0.000243s     77.1   4116.7
      rsa 4096 bits               0.029138s 0.000425s     34.3   2353.9
      rsa 7680 bits               0.220952s 0.001460s      4.5    684.9
      rsa 15360 bits              1.362500s 0.005801s      0.7    172.4
      dsa 2048 bits               0.001530s 0.001434s    653.8    697.3
      256 bits ecdsa (nistp256)   0.0001s   0.0003s    12472.4   3907.9
      384 bits ecdsa (nistp384)   0.0032s   0.0025s      311.4    396.6
      521 bits ecdsa (nistp521)   0.0081s   0.0062s      123.1    161.9
      253 bits EdDSA (Ed25519)    0.0002s   0.0004s     6284.5   2412.9
    
  • Raspberry Pi 3 Model B Rev 1.2, Cortex-A53

                                  sign      verify      sign/s verify/s
      rsa 2048 bits               0.011919s 0.000268s     83.9   3735.0
      rsa 3072 bits               0.032787s 0.000550s     30.5   1819.5
      rsa 4096 bits               0.069583s 0.000934s     14.4   1070.1
      rsa 7680 bits               0.381111s 0.003097s      2.6    322.9
      rsa 15360 bits              2.725000s 0.012002s      0.4     83.3
      dsa 2048 bits               0.003586s 0.003021s    278.9    331.0
      256 bits ecdsa (nistp256)   0.0004s   0.0013s     2249.3    743.5
      384 bits ecdsa (nistp384)   0.0181s   0.0127s       55.1     78.5
      521 bits ecdsa (nistp521)   0.0421s   0.0287s       23.7     34.8
      253 bits EdDSA (Ed25519)    0.0005s   0.0012s     2156.7    800.2
    

Here are the charts, linear and logarithmic. Y axis is sign/s (solid, circles) and verify/s (dotted, triangles). Blue is the X220, Orange is Xiaomi, and Red is Raspberry Pi.

linear plot logarithmic plot

My take away here is that ECDSA nistp256 is much faster at signing than other ECDSA keys. On Raspberry pi, using nistp384 and 521 leads to a maximum of 55.1 or 23.7 signing operations per second—these look like bad defaults to me.

Ed25519 is somewhat slower than ECDSA, especially at signing, but not by much.

Also, surprisingly, nistp521 performs better than nistp384 on Intel CPU.

$\endgroup$
5
  • $\begingroup$ Could you give the command lines exactly? So that others can use to test and verify the results. Also, you might go deeper about the nistp521 and nistp384 difference. $\endgroup$
    – kelalaka
    Oct 3 '20 at 17:52
  • $\begingroup$ the command is literally $ openssl speed, i just made the graphs of the subset of results. i have no idea why nistp521 performs better, it's just something that i found unusual $\endgroup$
    – squirrel
    Oct 3 '20 at 20:39
  • $\begingroup$ I know it is OpenSSL speed. I mean like writing openssl speed rsa. The difference might interesting related to CPU instruction usage. here the +1. $\endgroup$
    – kelalaka
    Oct 3 '20 at 20:49
  • $\begingroup$ i just did openssl speed without any parameters, didn't realize you could run it only for rsa haha. i tried openssl speed rsa just now and got the very same results $\endgroup$
    – squirrel
    Oct 3 '20 at 20:55
  • $\begingroup$ It should be the same since it makes averages, but the total time in your command, man. Don't let others to this trap! $\endgroup$
    – kelalaka
    Oct 3 '20 at 20:57

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.