Safe primes in Diffie-Hellman

Diffie-Hellman key agreement protocol uses modular exponentiation and calls for use of special prime numbers. If you ever wondered why, I’ll try to explain.

Diffie-Hellman key agreement

The “classical” Diffie-Hellman key exchange also known as Finite Field Diffie-Hellman uses one type of operation — modular exponentiation — and two secrets for two communication peers to arrive at a single shared secret.

The protocol requires a prime number and a number that is a so-called “generator” number to be known to both peers. This is usually achieved by either the server sending those values to the client (e.g. in TLS before v1.3 or in some SSH key exchange types) or by distributing them ahead of time to the peers (e.g. in IPSec and TLS 1.3).

When both peers know which parameters to use, they generate a random number, perform modular exponentiation with this random number, group generator and prime and send the result to the other party as a “key share”. That other party takes this key share and uses it as the generator to perform modular exponentiation again. The result of that second operation is the agreed key share.

If we define $g$ as the generator, $p$ as the prime, $S_r$ as the server selected random, $S_k$ as the server key share, $C_r$ as the client selected random and $C_k$ as the client key share, and $SK$ being the agreed upon secret, the server performs following operations:
$g^{S_r} = S_k \mod p$
$C_k^{S_r} = SK \mod p$

Client performs following operation:
$g^{C_r} = C_k \mod p$
$S_k^{C_r} = SK \mod p$

Because $(g^{C_r})^{S_r} = (g^{S_r})^{C_r} = SK \mod p$ both parties agree on the same $SK$.

Unfortunately both peers need to operate on a value provided by the other party (not necessarily trusted or authenticated) and their secret value at the same time. This calls for the the prime number used to have some special properties.

Modular exponentiation

The basic operation we’ll be dealing with is modular exponentiation. The simple way to explain it is that we take a number, raise it to some power. Then we take that result and divide it by a third number. The remainder of that division is our result.

For `2^10 mod 12`, the calculation will go as follows, first exponentiation:

`2^10 = 1024`

Then division:

`1024 = 85*12 + 4`

So the result is 4.

One of the interesting properties of modular exponentiation, is that it is cyclic. If we take a base number and start raising it to higher and higher powers, we will be getting the same numbers in the same order:

```\$ python powmod.py -g 3 -m 14 -e 28
3^0  mod 14 = 1
3^1  mod 14 = 3
3^2  mod 14 = 9
3^3  mod 14 = 13
3^4  mod 14 = 11
3^5  mod 14 = 5
3^6  mod 14 = 1
3^7  mod 14 = 3
3^8  mod 14 = 9
3^9  mod 14 = 13
3^10 mod 14 = 11
3^11 mod 14 = 5
3^12 mod 14 = 1
3^13 mod 14 = 3
3^14 mod 14 = 9
3^15 mod 14 = 13
3^16 mod 14 = 11
3^17 mod 14 = 5
3^18 mod 14 = 1
3^19 mod 14 = 3
3^20 mod 14 = 9
3^21 mod 14 = 13
3^22 mod 14 = 11
3^23 mod 14 = 5
3^24 mod 14 = 1
3^25 mod 14 = 3
3^26 mod 14 = 9
3^27 mod 14 = 13```

This comes from the fact that in modulo arithmetic, for addition, subtraction, multiplication and exponentiation, the order in which the modulo operations are made does not matter; `a + b mod c` is equal to `(a mod c + b mod c) mod c`. Thus if we try to calculate the example for `3^17 mod 14` we can write it down as `((3^6 mod 14) * (3^6 mod 14) * (3^5 mod 14)) mod 14`. Then the calculation is reduced to `1 * 1 * 3^5 mod 14`.

The inverse of modular exponentiation is discrete logarithm, in which for a given base and modulus, we look for exponent that will result in given number:

`g^x mod m = n`

Where g, m and n are given, we’re looking for x.

Because there are no fast algorithms for calculating discrete logarithm, is one of the reasons we can use modulo exponentiation as the base of Diffie-Hellman algorithm.

Cyclic groups

Let’s see what happens if we start calculating results of modular exponentiation for 14 with different bases:

```\$ python groups.py -m 14
Groups modulo 14
g:  0, [1, 0]
g:  1, [1]
g:  2, [1, 2, 4, 8]
g:  3, [1, 3, 9, 13, 11, 5]
g:  4, [1, 4, 2, 8]
g:  5, [1, 5, 11, 13, 9, 3]
g:  6, [1, 6, 8]
g:  7, [1, 7]
g:  8, [1, 8]
g:  9, [1, 9, 11]
g: 10, [1, 10, 2, 6, 4, 12, 8]
g: 11, [1, 11, 9]
g: 12, [1, 12, 4, 6, 2, 10, 8]
g: 13, [1, 13]
```

Neither of the numbers can generate all of the numbers that are smaller than the integer we calculate the modulo operation with. In other words, there is no generator (in number theoretic sense) that generates the whole group.

To find such numbers, we need to start looking at prime numbers.

Cyclic groups modulo prime

Let’s see what happens for 13:

```\$ python groups.py -m 13
Groups modulo 13
g:  0, [1, 0]
g:  1, [1]
g:  2, [1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7]
g:  3, [1, 3, 9]
g:  4, [1, 4, 3, 12, 9, 10]
g:  5, [1, 5, 12, 8]
g:  6, [1, 6, 10, 8, 9, 2, 12, 7, 3, 5, 4, 11]
g:  7, [1, 7, 10, 5, 9, 11, 12, 6, 3, 8, 4, 2]
g:  8, [1, 8, 12, 5]
g:  9, [1, 9, 3]
g: 10, [1, 10, 9, 12, 3, 4]
g: 11, [1, 11, 4, 5, 3, 7, 12, 2, 9, 8, 10, 6]
g: 12, [1, 12]
```

The obvious result is that we now have 4 generators — 2, 6, 7 and 11 generate the whole group.

But there is other result hiding. Let’s see the results for 19, but with sizes of those groups shown:

```\$ python groups-ann.py -m 19
Groups modulo 19
g:   0, len:   2, [1, 0]
g:   1, len:   1, [1]
g:   2, len:  18, [1, 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10]
g:   3, len:  18, [1, 3, 9, 8, 5, 15, 7, 2, 6, 18, 16, 10, 11, 14, 4, 12, 17, 13]
g:   4, len:   9, [1, 4, 16, 7, 9, 17, 11, 6, 5]
g:   5, len:   9, [1, 5, 6, 11, 17, 9, 7, 16, 4]
g:   6, len:   9, [1, 6, 17, 7, 4, 5, 11, 9, 16]
g:   7, len:   3, [1, 7, 11]
g:   8, len:   6, [1, 8, 7, 18, 11, 12]
g:   9, len:   9, [1, 9, 5, 7, 6, 16, 11, 4, 17]
g:  10, len:  18, [1, 10, 5, 12, 6, 3, 11, 15, 17, 18, 9, 14, 7, 13, 16, 8, 4, 2]
g:  11, len:   3, [1, 11, 7]
g:  12, len:   6, [1, 12, 11, 18, 7, 8]
g:  13, len:  18, [1, 13, 17, 12, 4, 14, 11, 10, 16, 18, 6, 2, 7, 15, 5, 8, 9, 3]
g:  14, len:  18, [1, 14, 6, 8, 17, 10, 7, 3, 4, 18, 5, 13, 11, 2, 9, 12, 16, 15]
g:  15, len:  18, [1, 15, 16, 12, 9, 2, 11, 13, 5, 18, 4, 3, 7, 10, 17, 8, 6, 14]
g:  16, len:   9, [1, 16, 9, 11, 5, 4, 7, 17, 6]
g:  17, len:   9, [1, 17, 4, 11, 16, 6, 7, 5, 9]
g:  18, len:   2, [1, 18]
```

Note that all the sizes of those groups are factors of 18 – that is p-1.

The third observation we can draw from those results is that, for any number the size of the group of the generated elements will be at most as large as the size of the base number.

With 19, if we take generator 8, the size of its subgroup is 6. But size of subgroups of 7, 18, 11 and 12 is respectively 3, 2, 3 and 6.

Thus, not only is the subgroup much smaller than the full group, it is also impossible to “escape” from it.

Safe primes

We saw that for primes, some bases are better than others (look into finite fields to learn more).

As we noticed, sizes of all groups are factors of the prime less one (see Fermat’s little theorem for proof of this). Of course, with the exception of 2, all primes are odd numbers, so p-1 will always be divisible by two – it will be a composite number. But `q = (p-1)/2` doesn’t have to be composite. Indeed, we call primes for which q is also prime safe primes.

Let’s see what happens if we calculate groups of such a prime:

```\$ python groups-ann.py -m 23
Group sizes modulo 23
g:   0, len:   2, [1, 0]
g:   1, len:   1, [1]
g:   2, len:  11, [1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12]
g:   3, len:  11, [1, 3, 9, 4, 12, 13, 16, 2, 6, 18, 8]
g:   4, len:  11, [1, 4, 16, 18, 3, 12, 2, 8, 9, 13, 6]
g:   5, len:  22, [1, 5, 2, 10, 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, 3, 15, 6, 7, 12, 14]
g:   6, len:  11, [1, 6, 13, 9, 8, 2, 12, 3, 18, 16, 4]
g:   7, len:  22, [1, 7, 3, 21, 9, 17, 4, 5, 12, 15, 13, 22, 16, 20, 2, 14, 6, 19, 18, 11, 8, 10]
g:   8, len:  11, [1, 8, 18, 6, 2, 16, 13, 12, 4, 9, 3]
g:   9, len:  11, [1, 9, 12, 16, 6, 8, 3, 4, 13, 2, 18]
g:  10, len:  22, [1, 10, 8, 11, 18, 19, 6, 14, 2, 20, 16, 22, 13, 15, 12, 5, 4, 17, 9, 21, 3, 7]
g:  11, len:  22, [1, 11, 6, 20, 13, 5, 9, 7, 8, 19, 2, 22, 12, 17, 3, 10, 18, 14, 16, 15, 4, 21]
g:  12, len:  11, [1, 12, 6, 3, 13, 18, 9, 16, 8, 4, 2]
g:  13, len:  11, [1, 13, 8, 12, 18, 4, 6, 9, 2, 3, 16]
g:  14, len:  22, [1, 14, 12, 7, 6, 15, 3, 19, 13, 21, 18, 22, 9, 11, 16, 17, 8, 20, 4, 10, 2, 5]
g:  15, len:  22, [1, 15, 18, 17, 2, 7, 13, 11, 4, 14, 3, 22, 8, 5, 6, 21, 16, 10, 12, 19, 9, 20]
g:  16, len:  11, [1, 16, 3, 2, 9, 6, 4, 18, 12, 8, 13]
g:  17, len:  22, [1, 17, 13, 14, 8, 21, 12, 20, 18, 7, 4, 22, 6, 10, 9, 15, 2, 11, 3, 5, 16, 19]
g:  18, len:  11, [1, 18, 2, 13, 4, 3, 8, 6, 16, 12, 9]
g:  19, len:  22, [1, 19, 16, 5, 3, 11, 2, 15, 9, 10, 6, 22, 4, 7, 18, 20, 12, 21, 8, 14, 13, 17]
g:  20, len:  22, [1, 20, 9, 19, 12, 10, 16, 21, 6, 5, 8, 22, 3, 14, 4, 11, 13, 7, 2, 17, 18, 15]
g:  21, len:  22, [1, 21, 4, 15, 16, 14, 18, 10, 3, 17, 12, 22, 2, 19, 8, 7, 9, 5, 13, 20, 6, 11]
g:  22, len:   2, [1, 22]
```

The groups look very different to the ones we saw previously, with the exception of bases 0, 1 and p-1, all groups are relatively large – 11 or 22 elements.

One interesting observation we can make about bases that have group order of 2q, is that even exponents will remain in a group of size 2q while odd will move to a group with order of q. Thus we can say that use of generator that is part of group order of 2q will leak the least significant bit of the exponent.

That’s why protecting against small subgroup attacks with safe primes is so easy, it requires comparing the peer’s key share against just 3 numbers. It’s also the reason why it’s impossible to “backdoor” the parameters (prime and generator), as every generator is a good generator.

Testing for SLOTH

Researchers at INRIA have published a new attack against TLS they called SLOTH. More details about it can be found at http://sloth-attack.org.

The problematic part, is that many frameworks (that is GnuTLS, OpenSSL, NSS) even if they don’t advertise support for MD5 hashes, would in fact accept messages signed with this obsolete and insecure hash.

Thus, to test properly if a server is vulnerable against this attack, we need a client that is misbehaving.

For easy writing of such test cases I have been working on the tlsfuzzer. Just released version of it was extended to be able test servers for vulnerability against the SLOTH attack (to be more precise, just the client impersonation attack – the most severe of the described ones).

Client impersonation attack

To test vulnerability of server to client impersonation attack, you will need the TLS server, set of a client certificate and key trusted by server and Python (any version since 2.6 or 3.2 will do). The full procedure for testing a server is as follows.

Certificates:

For testing we will need a set of certificates trusted by the server, in this case we will cheat a little and tell the server to trust a certificate directly.

Client certificate:

```openssl req -x509 -newkey rsa -keyout localuser.key \
-out localuser.crt -nodes -batch -subj /CN=Local\ User
```

Server certificate:

```openssl req -x509 -newkey rsa -keyout localhost.key -out localhost.crt -nodes -batch -subj /CN=localhost
```

Server setup

The test client expects an HTTP server on localhost, on port 4433 that requests client certificates:

`openssl s_server -key localhost.key -cert localhost.crt -verify 1 -www -tls1_2 -CAfile localuser.crt`

Reproducer setup

The reproducer has a bit of dependencies on the system.

First thing, you will need python pip command. In case your distribution doesn’t provide it, download it from https://bootstrap.pypa.io/get-pip.py and run using python:

```python get-pip.py
```

After that, install dependencies of tlsfuzzer:

```pip install --pre tlslite-ng
```

Note: Installation may print an error: “error: invalid command ‘bdist_wheel'”, it can be ignored, it doesn’t break installation of package. In case you want to fix it anyway, upgrade setuptools package installed on your system by running:

```pip install --upgrade setuptools
```

```git clone https://github.com/tomato42/tlsfuzzer.git
```

Running reproducer

Once we have all pieces in place, we can run the reproducer as follows:

```cd tlsfuzzer
PYTHONPATH=. python scripts/test-certificate-verify.py -k /tmp/localuser.key -c /tmp/localuser.crt
```

(if you generated user certificates in /tmp directory)

Results

If the execution finished with

```MD5 CertificateVerify test version 4
MD5 forced...
OK
Sanity check...
OK
Test end
successful: 2
failed: 0
```

That means that the server is not vulnerable.

In case the “MD5 forced” failed, but “Sanity check” resulted in “OK”, it means that the server is vulnerable.

Example failure may look like this:

```MD5 CertificateVerify (CVE-2015-7575 aka SLOTH) test version 4
MD5 forced...
Error encountered while processing node <tlsfuzzer.expect.ExpectClose object at 0xe3a410> with last message being: <tlslite.messages.Message object at 0xe3a8d0>
Error while processing
Traceback (most recent call last):
File "scripts/test-certificate-verify.py", line 140, in main
runner.run()
File "/root/tlsfuzzer/tlsfuzzer/runner.py", line 139, in run
msg.write()))
AssertionError: Unexpected message from peer: ChangeCipherSpec()

Sanity check...
OK
Test end
successful: 1
failed: 1
```

(if the error was caused by Unexpected message from peer: ChangeCipherSpec, as shown above, it means that the server is definitely vulnerable)

In case the Sanity check failed, that may mean one of few things:

• the server is not listening on localhost on port 4433
• the server does not support TLS v1.2 protocol, in that case it is not vulnerable (note: this is NOT a good workaround)
• the server does not support TLS_RSA_WITH_AES_128_CBC_SHA cipher (AES128-SHA in OpenSSL naming system)
• the server did not ask for certificate on first connection attempt

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.

More nails to RC4 coffin

Last week Christina Garman, Kenneth G. Paterson and Thyla van der Merwe have published a new attacks on RC4 in a paper titled Attacks Only Get Better: Password Recovery Attacks Against RC4 in TLS. In it they outline an attack which recovers user passwords in IMAP and HTTP Basic authentication using 226 ciphertexts. Previous attacks required about 234 ciphertexts.

The other attack, published yesterday at the BlackHat conference, is the Bar-mitzvah attack which requires about 229 ciphertexts.

While connections to relatively few servers (~6% of Alexa top 1 million TLS enabled sites) will end up with RC4 cipher, the 75% market share of RC4 in general is not reassuring.

RC4 prohibited

After nearly half a year of work, the Internet Engineering Task Force (IETF) Request for Comments (RFC) 7465 is published.

What it does in a nutshell is disallows use of any kind of RC4 ciphersuites. In effect making all servers or clients that use it non standard compliant.

Halloween special

Since the Haloween is the time of scary stories, let me share with you some preliminary results of the new cipherscan results.

I’ve extended the tool to check different grades of TLS ClientHello intolerance, like TLS version, size of client hello and the results are scary indeed.

Over 3% of servers just in Alexa top 2000 sites are not RFC compliant (can’t process big ClientHello, ClientHello with extensions they don’t understand, ClientHello with high protocol version, like for TLSv1.2 or with cipher suites they don’t know).

Two servers in this set are strictly TLSv1.2 intolerant, that means they use TLS implementations that can’t handle new protocol version 6 years after its release!

Those are the servers which force web browsers to use the fallback mechanism or limit their cipher suite set.

47% have SSLv3 still enabled, making them possibly vulnerable to POODLE (if they support ciphers besides RC4 in SSLv3).

Statistics

The new section added to statistics is “Required fallbacks”. It reports what kind of client connection attempts are problematic to servers the scan was still able to connect to.

The set of “big” hellos (big-SSLv3, big-TLSv1.0, big-TLSv1.1, big-TLSv1.2) are “Christmas tree packet” like connection attempts – where every option, extension and cipher suite supported by the OpenSSL tool was enabled.

In case the big-TLSv1.2 test was unsuccessful, the tool runs additional tests: “no-npn-alpn-status” where it queries the server again with a TLSv1.2 packet, but drops the NPN, ALPN and certificate status request (OCSP staple) extensions. “small-TLSv1.2” and “small-TLSv1.0” are reduced size packets, that still include SNI, elliptic curves (albeit limited to the P-256, P-384 and P-521 curves) and signature algorithms, but offer only limited set of ciphers, modelled after Firefox ClientHello. All those are from connections that were tolerant to at least one of the “big-” hello’s.

Then there are “inconclusive ” results, which show servers which the tool was able to connect to only using at least one of the “no-” or “small-” fallbacks but not using the “big-“. Such servers are not included in the general stats, but they do exclude servers which didn’t provide valid certificates.

```SSL/TLS survey of 1693 websites from Alexa's top 2 thousand
Stats only from connections that did provide valid certificates
(or anonymous DH from servers that do also have valid certificate installed)

Supported Protocols       Count     Percent
-------------------------+---------+-------
SSL2                      44        2.5989
SSL2 Only                 4         0.2363
SSL3                      801       47.3125
SSL3 Only                 26        1.5357
SSL3 or TLS1 Only         295       17.4247
TLS1                      1663      98.228
TLS1 Only                 74        4.3709
TLS1.1                    1265      74.7194
TLS1.2                    1325      78.2634
TLS1.2, 1.0 but not 1.1   89        5.2569

Required fallbacks                       Count     Percent
----------------------------------------+---------+-------
big-SSLv3 Only tolerant                  22        1.2995
big-SSLv3 intolerant                     892       52.6875
big-SSLv3 tolerant                       801       47.3125
big-TLSv1.0 intolerant                   26        1.5357
big-TLSv1.0 or big-SSLv3 Only tolerant   2         0.1181
big-TLSv1.0 tolerant                     1667      98.4643
big-TLSv1.1 intolerant                   29        1.7129
big-TLSv1.1 tolerant                     1664      98.2871
big-TLSv1.2 intolerant                   49        2.8943
big-TLSv1.2 tolerant                     1644      97.1057
inconclusive small-TLSv1.0               7         0.4135
inconclusive small-TLSv1.2               7         0.4135
no-npn-alpn-status intolerant            49        2.8943
small-TLSv1.0 tolerant                   49        2.8943
small-TLSv1.2 intolerant                 2         0.1181
small-TLSv1.2 tolerant                   47        2.7761
```

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.

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

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.

TLS landscape

Transport Layer Security (TLS) or, as it was known in the beginnings of the Internet, Secure Sockets Layer (SSL) is the technology responsible for securing communications between different devices. It is used everyday by nearly everyone using the globe-spanning network.

Let’s take a closer look at how TLS is used by servers that underpin the World Wide Web and how the promise of security is actually executed.

Hyper Text Transfer Protocol (HTTP) in versions 1.1 and older make encryption (thus use of TLS) optional. Given that the upcoming HTTP 2.0 will require use of TLS and that Google now uses the HTTPS in its ranking algorithm, it is expected that many sites will become TLS-enabled.

Surveying the Alexa top 1 million sites, most domains still don’t provide secure communication channel for their users.

Just under 40% of HTTP servers support TLS or SSL and present valid certificates.

Additionally, if we look at the version of the protocol supported by the servers most don’t support the newest (and most secure) version of the protocol TLSv1.2. Of more concern is the number of sites that support the completely insecure SSLv2 protocol.

Only half of HTTPS servers support TLS 1.2

(There are no results for SSLv2 for first 3 months because of error in software that was collecting data.)

One of the newest and most secure ciphers available in TLS is Advanced Encryption Standard (AES) in Galois/Counter Mode (AES-GCM). Those ciphers provide good security, resiliency against known attacks (BEAST and Lucky13), and very good performance for machines with hardware accelerators for them (modern Intel and AMD CPUs, upcoming ARM).

Unfortunately, it is growing a bit slower than TLS adoption in general, which means that some of the newly deployed servers aren’t using new cryptographic libraries or are configured to not use all of their functions.

Only 40% of TLS web servers support AES-GCM ciphersuites.

A few years back, a weakness in TLS 1.0 and SSL 3 was shown to be exploitable in the BEAST attack. The recommended workaround for it was to use RC4-based ciphers. Unfortunately, we later learned that the RC4 cipher is much weaker than it was previously estimated. As the vulnerability that allowed BEAST was fixed in TLSv1.1, using RC4 ciphers with new protocol versions was always unnecessary. Additionally, now all major clients have implemented workarounds for this attack, which currently makes using RC4 a bad idea.

Unfortunately, many servers prefer RC4 and some (~1%) actually support only RC4. This makes it impossible to disable this weak cipher on client side to force the rest of servers (nearly 19%) to use different cipher suite.

RC4 is still used with more than 18% of HTTPS servers.

The other common issue, is that many certificates are still signed using the obsolete SHA-1. This is mostly caused by backwards compatibility with clients like Windows XP pre SP2 and old phones.

SHA-256 certificates only recently started growing in numbers

The sudden increase in the SHA-256 between April and May was caused by re-issuance of certificates in the wake of Heartbleed.

Many servers also support insecure cipher suites. In the latest scan over 3.5% of servers support some cipher suites that uses AECDH key exchange, which is completely insecure against man in the middle attacks. Many servers also support single DES (around 15%) and export grade cipher suites (around 15%). In total, around 20% of servers support some kind of broken cipher suite.

While correctly implemented SSLv3 and later shouldn’t allow negotiation of those weak ciphers if stronger ones are supported by both client and server, at least one commonly used implementation had a vulnerability that did allow for changing the cipher suite to arbitrary one commonly supported by both client and server. That’s why it is important to occasionally clean up list of supported ciphers, both on server and client side.

Forward secrecy

Forward secrecy, also known as perfect forward secrecy (PFS), is a property of a cipher suite that makes it impossible to decrypt communication between client and server when the attacker knows the server’s private key. It also protects old communication in case the private key is leaked or stolen. That’s why it is such a desirable property.

The good news is that most servers (over 60%) not only support, but will actually negotiate cipher suites that provide forward secrecy with clients that support it. The used types are split essentially between 1024 bit DHE and 256 bit ECDHE, scoring respectively 29% and 33% of all servers in latest scan. The amount of servers that do negotiate PFS enabled cipher suites is also steadily growing.

PFS support among TLS-enabled HTTP servers

Summary

Most Internet facing servers are badly configured, sometimes it is caused by lack of functionality in software, like in case of old Apache 2.2.x releases that don’t support ECDHE key exchange, and sometimes because of side effects of using new software with old configuration (many configuration tutorials suggested using !ADH in cipher string to disable anonymous cipher suites, that unfortunately doesn’t disable anonymous Elliptic Curve version of DH – AECDH, for that, use of !aNULL is necessary).

Thankfully, the situation seems to be improving, unfortunately rather slowly.

If you’re an administrator of a server, consider enabling TLS. Performance issues when encryption was slow and taxing on servers are long gone. If you already use TLS, double check your configuration preferably using the Mozilla guide to server configuration as it is regularly updated. Make sure you enable PFS cipher suites and put them above non-PFS ciphers and that you as well as the Certificate Authority you’ve chosen, use modern crypto (SHA-2) and large key sizes (at least 2048 bit RSA).

If you’re a user of a server and you’ve noticed that the server doesn’t use correct configuration, try contacting the administrator – he may have just forgotten about it.