Algorithm and key size to choose for SSL certificates (security and CPU wise) in 2020 (using nginx)

Question

I posted this question already on SO, but as it is not really a programmin question I thought it might be a better place to ask here:

I want to setup a new SSL certificate store for generating SSL certs (server certs (nginx) and client certs (linux/windows devices))

I'm searching already for quite some time and I'm not sure I fully understand. especially as some articles are a few years old.

Many articles just talk about RSA and seem to recommend 2048 or 3072 though mentioning that 2048 is today probably still the best choice ( https://expeditedsecurity.com/blog/measuring-ssl-rsa-keys/ )

I found for example one Article ( https://paragonie.com/blog/2019/03/definitive-2019-guide-cryptographic-key-sizes-and-algorithm-recommendations ) but it seems to talk mostly about key encryption as @dave_thompson_085 pointed out on SO

stating in the section "Asymmetric ("Public Key") Encryption"

Use, in order of preference:
    X25519 (for which the key size never changes) then symmetric encryption.
    ECDH with secp256r1 (for which the key size never changes) then symmetric encryption.
    RSA with 2048-bit keys.

The security of a 256-bit elliptic curve cryptography key is about even with 3072-bit RSA.

Although many organizations are recommending migrating from 2048-bit RSA to 3072-bit RSA (or even 4096-bit RSA) 
in the coming years, don't follow that recommendation. Instead migrate from RSA to elliptic curve cryptography,
and then breathe easy while you keep an eye out for post-quantum cryptography recommendations.

However they don't mention the impact on server CPU usage compared to RSA 2048/3072/4048. I also didn't find many other articles suggesting to switch to Elliptic curve algorithms.

Another article ) https://www.thesslstore.com/blog/you-should-be-using-ecc-for-your-ssl-tls-certificates/ _ tries to promote ECC instead of RSA, but comments on the article state, that ECC is less safe than RSA if quantum computers kick in. And the article cites nowhere numbers for what performance improvement to expect when using ECC.

https://crypto.stackexchange.com/questions/1190/why-is-elliptic-curve-cryptography-not-widely-used-compared-to-rsa mentions potentially legal issues and fear of being sued.

Though CPU usage is not a major issue Id still like to get some idea as I'd like to use the same CA and cert store also on devices like raspberries.

So what is today the best choice for certificate key algorithms and key sizes for server certs (old internet explorer not required but PCs, tablets, mobile phones being used today should be able to connect to the server

and what's the best choice for client certs (will not be used on mobile devices)?

I kind of tend to RSA 2048, but I'm really not that sure I interpret all the articles correctly and don't like to make choices based on feelings.

Answer 1

Benchmarks on a single core in my aging laptop (Skylake, openssl 1.1.1):

$ openssl speed rsa2048 rsa3072 rsa4096
                  sign    verify    sign/s verify/s
rsa 2048 bits 0.000662s 0.000020s   1510.2  49977.8
rsa 3072 bits 0.002078s 0.000040s    481.2  24920.9
rsa 4096 bits 0.004433s 0.000068s    225.6  14614.6

$ openssl speed ecdsap256 ecdsap384 ecdsap521
                              sign    verify    sign/s verify/s
 256 bits ecdsa (nistp256)   0.0000s   0.0001s  37387.6  12823.3
 384 bits ecdsa (nistp384)   0.0012s   0.0009s    855.6   1154.5
 521 bits ecdsa (nistp521)   0.0003s   0.0007s   2881.8   1510.7

$ openssl speed ed25519 ed448
                              sign    verify    sign/s verify/s
 253 bits EdDSA (Ed25519)    0.0000s   0.0001s  21340.9   7981.1
 456 bits EdDSA (Ed448)      0.0004s   0.0006s   2827.1   1599.6

I recommend you run the benchmark on your own hardware and your own version of the TLS library (e.g. SChannel for IIS would have different performance, but openssl adds optimized versions for different microarchitectures as features, so benchmark different openssl versions too).

P-384 is not a great curve, it's slower than P-521 because of the curve parameters, that's not an implementation quirk of openssl. NSA Suite B makes it more popular than it deserves.

In TLS, the server performs "sign" and the client performs "verify", unless client certs are used, then both sides do both (this is rarely used, if you use this you know that you do).

The EdDSA numbers don't matter because although the RFC exists, WebPKI will not use EdDSA, they will upgrade to PQCrypto whenever the HSMs for those standards are out after the standards themselves are out. I suppose for self-signed certs you can use EdDSA (I didn't try that, I don't know what supports this).

You see that the server would prefer to do ECDSA NISP P-256 signatures, because those are fast. The clients would prefer to verify RSA-2048 or bigger RSA and not to verify ECDSA, because that is slow.

The choice between RSA and ECDSA is whether you want to put more load on the server or on the client. Also, some people don't like ECDSA and it's possible some clients are too old to handle ECDSA.

The most popular choice currently is RSA-2048 and it's ok.

Note that if you only allow PFS cipher suites (and you should do that), the key for the certificate becomes useless to the attacker when the certificate expires, so it doesn't need to stay unbroken for decades.

Your ECDH is the part that needs to stay unbroken for a long time to prevent retroactive decryption of recorded traffic.

So if you read that RSA-2048 is no longer considered secure because NSA might soon be able to break it, replace your cert and you're good even for older traffic. But if you read that X25519 or P-256 ECDH is no longer considered secure because NSA might soon be able to break it - too late, they already have records of your TLS traffic protected by those primitives, after you upgrade you only protect future traffic, not older traffic.