Hardening Encrypted Communications Against Diffie-Hellman Precomputation Attacks

Introduction

A few weeks ago, a group of researchers published a paper detailing weakness in the Diffie-Hellman key exchange protocol and summarized it in a blog post in which they posited that anyone with sufficient funds would be able to crack one of the commonly used primes for Diffie-Hellman key exchange. They estimated that a system costing nine figures would be able to crack one prime per year, effectively trivializing the effort in listening in on any connection using that prime during the key exchange. The targets are those with 768 or 1024-bit primes. Larger standard primes are listed in RFC 3526. A 2048-bit prime requires approximately 100 million times more effort than a 1024-bit prime, so those should be safe for the time being, but we still recommend using a non-standard prime set.

Wealthy nation states would consider this to be an acceptable expenditure, and as we’ve all learned, criminal organizations have no problem commandeering large numbers of computers on the Internet for computationally heavy tasks. As you can imagine, the ability for a criminal organization to listen to encrypted communications, including credit card payments and authentication credentials, would likely pay off in a big way. One could imagine such an organization taking the time to write a system that processed the work in a distributed manner, perhaps using the GPU units on video cards as we’ve seen done with Bitcoin mining for years.

An important distinction to make is that this isn’t just about protecting credit cards over HTTPS. It also affects VPNs and SSH as well. This could allow breaches of corporate systems as authentication credentials are stolen, or email snooping, or even spearphishing attacks by making your target believe that the links are coming from inside your own company. A compromise of encryption is one of the most critical points to focus on resolving.

Diffie-Hellman Fundamentals

What does this mean for you? What does the Diffie-Hellman key exchange do? How does it work? Where is it used? What does the prime matter? So many questions! Cryptography can be pretty complicated, but the short version is this: when two computers decide they want to talk to each other in secret, they have to agree on a means to communicate, like two people finding a common language. This is what is known as a handshake or key exchange. One of the most secure methods is the Diffie-Hellman key exchange.

The way that it works is that the systems agree to use a prime number and a primitive root modulo coprime, and then performs a handshake using a known mathematical function, in which they are able to derive a common number which is used as the key for the symmetric encryption that actually carries the data later. There is a good example using basic numbers in the link earlier in this paragraph. However, you need to use really large prime and coprime numbers or it’s really easy to guess all the possible shared secret numbers. In fact, that’s basically what the precomputation attack is: figuring out all possible shared encryption keys, and then you just apply each of them until you can listen in on the traffic. On small primes and small numbers, you can do it with pencil and paper. A bit bigger and you’d use a calculator, or phone, or computer, or cluster, or supercomputer depending on the size of the prime. The idea here is to pick a number so large that it takes anyone trying to listen in at least a few months to generate all the possible shared secret keys so that they can listen in to any substantial amount of your traffic. And you want to make sure you’re probably not using the same primes as anyone else, because then they may already have the work done.

Elliptic Curve Diffie-Hellman uses the same idea as above, but instead of using primes, the systems use elliptic curve discrete logarithms, which are, by a large degree, significantly more difficult and time consuming to solve. A 256-bit elliptical curve provides an approximately equivalent challenge to a 3072-bit prime, without significantly raising the processing cost for normal use. The result is more security per unit of processing time. These asymmetric encryption key exchanges happen almost everywhere. Anywhere that TLS is used, like websites, email, chat, server-to-server communications, remote control protocols, and much more.

So how do we fix it?

The current recommendation is to switch to Elliptical Curve Diffie-Hellman (ECDH) for the key exchange, and then follow with an elliptical curve signature like Elliptic Curve Digital Signature Algorithm (ECDSA) or ed25519. At the moment, elliptical curves are not known to have a similar vulnerability, however the selection of the named curve could be important to limit any potential vulnerabilities. It’s also critical to note that there is current ongoing research exploring methods to attack elliptical curve encryptions, and more efficient and practical ways to attack other forms (the adage “if it’s important enough to encrypt, it’s important enough that someone wants it” applies). ECDSA is based on the elliptical curve P-256 that was mapped by NIST, and there is one suggested weakness that would allow for reduced solution time. The other option on the table is the less commonly implemented Curve25519, which was generated to specifically provide another option to the NIST provided P-256 after the aforementioned potential weakness. As a result, Farsight recommends using Curve25519 wherever possible. Unfortunately, Curve25519 isn’t currently available on all platforms and packages, most notably anything backed by OpenSSL, so we’ll fall back to P-256 where we can still use elliptical curves. Also worth noting is that CNSS requires that you use the NIST curves for any work done for the National Security Systems, so if that fits you, you should use P-256 or P-384 instead of Curve25519.

It’s important to note that Diffie-Hellman itself is still a great choice for key exchange, when used with strong, non-standard primes, and so we will be generating 2048 bit and larger non-standard primes, and setting those for use when elliptical curve is unavailable. We recommend not going below 2048 bit to avoid the LogJam attack, we recommend not using the same non-standard prime on multiple machines to limit the scope of compromise should your prime be targeted for a precomputation or brute force attack, and we recommend rotating the prime every 2-4 months (which significantly reduces the time that a compromised prime attack would bear fruit).

Now that we’ve selected the curve that we’re going to use to implement the signatures, and a key exchange method, we need to implement it. We will cover OpenSSH, Nginx and Apache here. For your own software, there are several libraries that carry support for Curve25519, including libSSH, NaCl, GnuTLS, and the embedded SSL library wolfSSL.

Some general tips for increasing the security and compatibility of the changes:

Update your crypto engine (probably OpenSSL) to the latest version offered by your distribution, or if you prefer, build the latest from source.
Update your applications to the latest versions offered by your distribution, or build the latest from source.
Ensure you’re using the latest crypto library (which you installed in above), and not configured to use an earlier version.

Adding ED25519 Support to OpenSSH

The potential impact of switching to elliptical curve encryption in SSH is minimal if your users update their SSH installs. There exists a possibility that some older systems will not support them, but if you’re unable to patch the software it’s likely already insecure. Directions will vary slightly based on the Linux distribution, but should be recognizable. These directions were written specifically with Debian in mind. Please note that for ed25519 you will need an SSH version above 6.5, which for many older distributions means using a backported or compiled-from-source version.

Update your SSH daemons and clients. Until you’re running the latest, there are possible conflicts, and also possible vulnerabilities in the daemon itself.
Check to see if you already have the keys. On the server side, look in the SSH daemon config (/etc/ssh/sshd_config) to see if you have a line accepting the ed25519 host key. It would look something like HostKey /etc/ssh/ssh_host_ed25519_key. If it’s there, you’re already configured on the server side and can skip the next few commands. If not, run ssh-keygen -t ed25519 -f /etc/ssh/ssh_host_ed25519_key and follow the prompts. Note: if you enter a passphrase, SSH will need it to start, so you probably shouldn’t do that for a remote server unless you like your iKVM.
Edit /etc/ssh/sshd_config to add the line HostKey /etc/ssh/ssh_host_ed25519_key near the other HostKey lines.
Restart the SSH daemon.

This enables clients to begin connecting with the new signature keys and still enable them to use their old keys. You’ll probably want to have a transition period where your users change their keys over before you move on to the removal stage, and possibly stand up a test machine with the final changes made so users can confirm they will have access after the cut-over.

Clients should run ssh-keygen -t ed25519 -a 100 and then change the key they use (with the -i option) to the new key. Farsight Security strongly recommends passphrases on the client side so that if the key is somehow stolen, people can’t easily access your infrastructure. The -a 100 option only works if a passphrase is used, and it is the number of iterations that bcrypt is called on the private key with the passphrase. The more iterations, the more secure as it increases significantly the amount of time required to bruteforce the key. However, as with all things, there is a cost and the more iterations, the longer it takes for either a successful connection or a failure, so we suggest that people use the highest number that they can tolerate the time-cost of a typo.

If you’re unable to ensure that all clients will be using the latest version of SSH, you don’t want to only use ed25518, so you’ll want to leave the options they are using in place. Modify the following as needed.

Cutting over to ed25519:

Remove all lines starting with HostKey except the HostKey /etc/ssh/ssh_host_ed25519_key line.
Change (or add) your KexAlgorithms line to KexAlgorithms [email protected].
Change (or add) your Ciphers line to Ciphers [email protected],aes256-ctr.
Restart the SSH daemon

If you need to keep non-elliptical curve handshakes around, you’ll want to generate a non-standard prime moduli and replace the default set that came with SSH to use it:

Remove all unused host keys.
Change (or add) your KexAlgorithms line to KexAlgorithms [email protected],diffie-hellman-group-exchange-sha256
Change (or add) your Ciphers line to Ciphers [email protected],aes256-ctr.

Generate the new moduli with the following commands:

ssh-keygen -G moduli-2048.candidates -b 2048
ssh-keygen -T moduli-2048 -f moduli-2048.candidates
mv /etc/ssh/moduli /etc/ssh/moduli.old
cp moduli-2048 /etc/ssh/moduli

Restart the SSH daemon

The KexAlgorithms handles the key exchange, and the cipher handles the actual encryption of the data.

Do not put in place a cipher you feel does not provide an adequate level of protection, since they client can prefer any cipher on the list and use it and the LogJam attack utilizes this to lower bit rates. At the time of the writing, Farsight was unable to locate vulnerabilities in the ciphers listed above. Additionally, we excluded potentially weak ciphers with known vulnerabilities, including lower bit rate AES.

While you’re at it, do yourself a favor and please disable password authentication if you haven’t already. All SSH logins should be done by key. Ensure the following entries are in the SSH daemon config and then restart the daemon:

    PubKeyAuthentication yes
    ChallengeResponseAuthentication no
    PasswordAuthentication no
    PermitEmptyPasswords no

This will restrict people to using key-based authentication only.

Adding Elliptical Curve Support to Nginx and Apache

Unfortunately, both Nginx and Apache base their SSL support on OpenSSL, which does not yet support Curve 25519 (though they’re currently working on it). That leaves us with the only option being to use the NIST provided P-256 curve implementations, and later return to switch to another curve.

Before you begin you should realize that the potential impact of locking down your web engine can come with an unintended side effect: you will leave behind visitors using older browsers and operating systems. Clients will need to be running Microsoft Windows Vista or newer, Apple OS X 10.6 or newer, Google Android 4 or newer. On Microsoft Windows XP, users may be able to use Firefox, which does not use the native encryption libraries and should be able to handle the encryption. This is from the smaller, but necessary, step of disabling SSLv2 and SSLv3. There is another camp that strongly suggests disabling everything except TLSv1.2. As with all things, there are pros and cons to each decision. Disabling everything other than TLS v1.2 has a much greater impact, meaning that users would need Microsoft Windows 7 or newer, Google Android 5 or newer, Apple OSX 10.9 or later, or iOS 5 or newer to be able to see the hosted web pages. That is a relatively small slice of the market, and serious thought and consideration should be made before the decision is made. However, it’s possible that within the same organization there will be pages and servers that fall on each side of that line, and so you should use what makes sense for them:

Internal servers where the hardware is company controlled, displaying and transferring trade secrets? TLS v1.2 only!
Company’s front web page displaying the same content to every visitor? TLS v1.0 is probably OK.

As always, make the right decisions for your organization. A secure environment isn’t useful if no one can actually access it.

Now, Diffie-Hellman isn’t a bad key exchange algorithm, far from it; so if you use strong, non-standard primes, you’re probably going to be secure, especially if you replace them every few months. If you intend to use them to reach a broader audience, or even to give your web engine more flexibility, you’ll want to generate a nonstandard prime. You’ll want to use different primes for each task.

Let’s begin with using Elliptical Curve Diffie-Hellman with the NIST P-256 curve and Diffie-Hellman with a non-standard prime.

Nginx

Run openssl dhparam -out /etc/nginx/dhparams.pem 2048

Edit /etc/nginx/nginx.conf and add

ssl_ciphers EECDH+AESGCM:AES256+EECDH:AESGCM:AES256:AES256+EDH:!aNULL:!eNULL:!LOW:!3DES:!MD5:!EXP:!PSK:!DSS:!RC4:!SEED; 
ssl_protocols TLSv1 TLSv1.1 TLSv1.2; 
ssl_dhparam /etc/nginx/dhparams.pem;
ssl_prefer_server_ciphers on; 
ssl_session_tickets off;

Restart Nginx.

Apache

Run openssl dhparam -out /etc/apache2/dhparams.pem 2048

Edit /etc/apache2/apache.conf

SSLCipherSuite EECDH+AESGCM:AES256+EECDH
SSLProtocol All -SSLv2 -SSLv3
SSLOpenSSLConfCmd DHParameters "/etc/apache2/dhparams.pem"
SSLHonorCipherOrder On
SSLSessionTickets Off

Restart Apache.

To be clear, what you’re doing in the above Apache and Nginx configuration is: “Ephemeral Elliptical Curve Diffie-Hellman with Advanced Encryption Standard with Galois/Counter Mode”, “Advanced Encryption Standard 256-bit with Ephemeral Elliptical Curve Diffie-Hellman” and then moving down to the options not using elliptical curve. This also disables SSLv2 and SSLv3, leaving only TLS. The next line of configuration is to tell the system to prefer the stronger encryption first, and the last line disables the storage and reuse of an ssl session. You can add back other ciphers to suit your needs with your clients as needed.

You’ll want to re-run the first line every few months and restart the web engine to pull in the new primes. As mentioned above, this will help to raise the bar of a targeted attack against your specific prime so that it does not yield results for long.

There are a lot of other things you can do to secure your traffic against interception, and this is by no means a comprehensive guide, so please tune the encryption ciphers and handshakes to meet your needs.

Conclusion

Encryption was made for two main purposes: to keep communications confidential, and to ensure the information has not been altered in transit. It’s truly a critical part of everyone’s day-to-day lives. It protects finances, private communications, access credentials, companies, and in some nations, it protects lives. It’s important enough that we need to make sure we’re doing everything we can to protect our users, our employers and ourselves. Switching to elliptical curves where possible, using non-standard primes where we can’t, and ensuring we’re using the strongest ciphers possible helps to carry that out.

Travis Hall is a Systems Administrator for Farsight Security, Inc.

Hardening Encrypted Communications Against Diffie-Hellman Precomputation Attacks

Share this entry

Introduction

Diffie-Hellman Fundamentals

So how do we fix it?

Adding ED25519 Support to OpenSSH

Cutting over to ed25519:

Adding Elliptical Curve Support to Nginx and Apache

Nginx

Apache

Conclusion

Sign up for our newsletter

Related Content

7 Most Popular Blogs of Q1 2024

The DomainTools Report, Spring 2024

Five Ways to Give Bad Actors a Taste of Their Own Medicine