rsa

The cryptopocalipse is near(er)!

That’s at least what NIST, CNSS and NSA think.

The primary reason for deploying cryptographic systems is to protect secrets. When the system carries information with a very long life (like locations of nuclear silos or evidence for marital infidelity) you need to stop using it well before it is broken. That means the usable life of a crypto-system is shorter than the time it remains unbroken.

Suite B is a set of cryptographic algorithms in very specific configurations that was originally published in 2005. Implementations certified by NIST in the FIPS program were allowed for protection of SECRET and TOP SECRET information depending on specific key sizes used. In practice SECRET was equivalent to 128 bit level of security, so SHA-256 signatures, AES-128 and P-256 curve, TOP SECRET required 192 bit level of security with SHA-384 signatures, P-384 curve and AES-256 for encryption.

They now claim that quantum computers are much closer than we think (less than 10 years time frame) and as such the keys used for protection of secure information need to be increased in short term (significantly in case of ECC) and research of quantum resistant algorithms is now a priority.

New recommendations

That means we get a new set of recommendations.

To summarise:

If you’re using TLS or IPsec with Pre-Shared Keys (PSK) with AES-256 encryption, you’ll most likely be fine.

If you were planning deployment of ECC in near future, you should just increase key sizes of existing RSA and DH systems and prepare for deployment of quantum resistant crypto in near future instead.

For RSA and finite-field DH (a new addition to Suite B but very old crypto systems by their own right) the recommended minimum is 3072 bit parameters. That is not particularly surprising, as that is the ENISA as well as NIST recommendation for 128 bit level of security.

What is a bit surprising is that they have changed the minimum hash size from 256 to 384 bit.

For ECC systems the P-256 curve was degraded to be secure enough only to protect unclassified information, so it was put together with 2048 bit RSA or DH. The minimum now is P-384 curve.

So now the table with equivalent systems looks like this:

 LoS RSA key size DH key size ECC key size Hash AES key size
112 bit 2048 bit 2048 bit 256 bit SHA-256 128 bit
128 bit 3072 bit 3072 bit 384 bit SHA-384 256 bit

What does that mean?

Most commercial systems don’t need to perform key rotation and reconfiguration of their systems just yet, as the vast majority of them (nearly 90%) still use just 2048 bit RSA for authentication. What that does mean is that the recent migration to ECC (like ECDHE key exchange and ECDSA certificates) didn’t bring increase in security, just in speed of key exchange. So if you’re an admin, that means you don’t need to do much, at least not until other groups of people don’t do their part.

Software vendors need to make their software actually negotiate the curve used for ECDHE key exchange. Situation in which 86% of servers that can do ECDHE can do it only with P-256 is… unhealthy. The strongest mutually supported algorithms should be negotiated automatically and by default. That means stronger signatures on ECDHE and DHE key exchanges, bigger curves selected for ECDHE and bigger parameters selected for DHE (at least as soon as draft-ietf-tls-negotiated-ff-dhe-10 becomes a standard).

Finally, we need quantum computing resistant cryptography. It would be also quite nice if we didn’t have to wait 15 or even 10 years before it reaches 74% of web servers market because of patent litigation fears.

Advertisements

RSA and ECDSA performance

Update 2017-07-03: nginx does support hybrid configuration with RSA and ECDSA certificates for single virtual host

As servers negotiate TLS connection, few things need to happen. Among them, a master key needs to be  negotiated to secure the connection and the client needs to be able to verify that the server it connected to is the one it intended to connect to. This happens by virtue of key exchange, either RSA, finite field Diffie Hellman (DH) or Elliptic Curve Diffie Hellman (ECDH). The server itself can be identified using either RSA or Elliptic Curve Digital Signature Algorithm (ECDSA) based certificates. All of them have their strong sides and weak sides, so let’s quickly go through them.

RSA key exchange

This way of deriving the key securing the connection is the simplest of the mentioned. It is supported by virtually all the clients and all the servers out there. Its strong point is relative high performance at small key sizes. Unfortunately, it doesn’t provide Forward Secrecy (PFS), which means that in case of private key leak all previous communication will be possible to decrypt.

Side note: while the acronym PFS stands for “Perfect Forward Secrecy”, the term “Perfect” comes from cryptography where it has a slightly different meaning than in vernacular. To limit confusion I’ll be calling it just “Forward Secrecy”.

Finite field Diffie-Hellman key exchange

Forward Secrecy is the prime feature of the ephemeral version of Diffie–Hellman. Its main drawback is high computational cost. Additionally, not all clients support it with RSA authentication, all versions of Internet Explorer being the prime example. While there exist a non ephemeral version of DH, it doesn’t support PFS nor has widespread support so we will ignore it for now.

Elliptic Curve Diffie-Hellman key exchange

ECDH is the new kid on the block, this means that it is supported only by relatively new clients. The strong points are low computational cost and much smaller key sizes for the same security levels. Similarly to DH, there exist ephemeral and non ephemeral version of it, the latter has limited support in clients and does not provide PFS.

RSA authentication

It’s the venerable and widely supported cryptosystem. Supported by virtually anything that has support for TLS or SSL. With us since the SSLv2. Unfortunately it’s starting to show its age, performance at key sizes providing 128 bit level of security is rather low and certificates are starting to get rather large (over 1KiB in size for 3072 bit RSA).

ECDSA authentication

Elliptic Curve Digital Signature Algorithm, just like ECDH is a new cryptosystem. This causes it to suffer from same problem: no support for it in old clients. It does use much smaller key sizes for the same security margins and is less computationally intensive than RSA.

Benchmarking

While the key exchanges and authentication mechanisms are relatively separate, in TLS the ciphersuites limit the available options. In fact, for the ECDSA ciphers, only ECDH key exchange is available. Or to spell it out, I could test only following configurations:

RSA key exchange - RSA authentication
DHE key exchange - RSA authentication
ECDHE key exchange - RSA authentication
ECDHE key exchagne - ECDSA authentication

The tested key sizes were: 1024 bit RSA as the recently obsoleted commonly used size, 2048 bit RSA as the current standard key size, 3072 bit as the recommended key size for systems that have to remain secure for foreseeable future, 4096 bit as the minimal size that matches the existing CA key sizes and is secure for foreseeable future (as there are virtually no commercial CAs that have 3072 bit key sizes) and finally 256 bit ECDSA as the recommended key size for secure systems for foreseeable future.

The tests were done on Atom D525 @ 1.8GHz with 4GiB of RAM (as an example of lowest performance on a relatively modern hardware) and used httpd-2.4.10-1.fc20.x86_64, mod_ssl-2.4.10-1.fc20.x86_64 with openssl-1.0.1e-39.fc20.x86_64. Interestingly, while this CPU has SSSE3, it doesn’t have AES-NI or SSE4.1, this makes AES-128-GCM faster than AES-128-CBC (50.7MiB/s vs 27.8MiB/s). Every query from client has downloaded 4KiB of data. The graphs show the maximum performance while serving concurrent users (usually around 8-10 at the same time).

So, lets compare RSA authenticated ciphers performance.

rsa-performance

Performance of different RSA key sizes

We can clearly see that that using non PFS enabled key exchanges brings huge performance improvements for legacy key sizes. RSA key exchange at 1024 bit is actually over 3.4 times faster than DHE key exchange. At this small sizes, using 256 bit ECDHE also doesn’t show much performance advantage over DHE, it is just 11% faster (note though that it is also comparable to 3072 bit DHE in security level).

Going to 2048 bit RSA, the performance advantage of not using PFS ciphers quickly shrinks. Here using RSA key exchange over 1024 bit DHE gives about 78% more performance. This configuration, while common because of lack of support of higher DHE parameter sizes in older Apache servers, doesn’t really provide higher security against targeted attack than use of 1024 bit RSA. Use of ECDHE is also looking much more interesting, at only 40% penalty compared to RSA key exchange. Using DHE key exchange with matching parameter sizes give performance that is nearly 7 times slower than pure RSA.

ECDHE shows its real potential at the 3072 bit RSA key size where while providing PFS with matching level of security it requires just 26% more computing power, again outperforming 1024 bit DHE. The ephemeral DH with matching key size gives a truly abysmal 800% drop in performance.

At the 4096 bit level, where the 256 bit ECDHE is the weaker link, pure RSA key exchange is just 18% more power hungry.

So, how does it compare to ECDSA key exchange?

ECDSA vs RSA authenticated connections

ECDSA vs RSA authenticated connections

If we use the currently acceptable 2048 bit RSA key exchange, it will turn out that the RSA is about 3% faster than the combination of ECDHE key exchange and ECDSA authentication (both using 256 bit curve). But if the required security level reaches 128 bits or PFS is required ECDSA with ECDHE is much faster.

ECDHE and  ECDSA with 256 bit curves is 2.7 times faster than 2048 bit RSA with 256 bit ECDHE and 3.4 times faster than 3072 bit RSA alone!

Apache

In other words, if you’re running Apache web servers you should consider using two certificates for the same site. This will allow to negotiate RSA cipher suites with the legacy clients while it will provide lessened load on the server with modern clients.

The configuration is also relatively simple, you just need to specify certificate and key file twice:

SSLCertificateFile /etc/pki/tls/certs/example.com-RSA.crt
SSLCertificateKeyFile /etc/pki/tls/private/example.com-RSA.key
SSLCertificateFile /etc/pki/tls/certs/example.com-ECDSA.crt
SSLCertificateKeyFile /etc/pki/tls/private/example.com-ECDSA.key

and make sure that your SSLCipherSuite doesn’t disable ECDSA authenticated ciphersuites (just check if this command outputs anything: openssl ciphers -v <cipher string from apache> | grep ECDHE-ECDSA).

nginx

For nginx, the configuration is very similar, you will need to run the relatively new 1.11.0 version, or later (see CHANGES) though.

ssl_certificate /etc/pki/tls/certs/example.com-RSA.crt
ssl_certificate_key /etc/pki/tls/private/example.com-RSA.key
ssl_certificate /etc/pki/tls/certs/example.com-ECDSA.crt
ssl_certificate_key /etc/pki/tls/private/example.com-ECDSA.key

Similarly, you need to make sure that the cipher string used doesn’t disable ECDSA authenticated ciphersuites.