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 theyposited that anyone with sufficient funds would be able to crack one of thecommonly used primes for Diffie-Hellman key exchange. They estimated that asystem costing nine figures would be able to crack one prime per year,effectively trivializing the effort in listening in on any connection usingthat prime during the key exchange. The targets are those with 768 or 1024-bitprimes. Larger standard primes are listed inRFC 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 anon-standard prime set.

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

An important distinction to make is that this isn’t just about protectingcredit cards over HTTPS. It also affects VPNs and SSH as well. This couldallow breaches of corporate systems as authentication credentials are stolen,or email snooping, or even spearphishing attacks by making your target believethat the links are coming from inside your own company. A compromise ofencryption 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 manyquestions! Cryptography can be pretty complicated, but the short version isthis: 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 commonlanguage. This is what is known as a handshake or key exchange. One of themost 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 thenperforms a handshake using a known mathematical function, in which they areable to derive a common number which is used as the key for the symmetricencryption that actually carries the data later. There is a good exampleusing basic numbers in the link earlier in this paragraph. However, you needto use really large prime and coprime numbers or it’s really easy to guess allthe possible shared secret numbers. In fact, that’s basically what theprecomputation attack is: figuring out all possible shared encryption keys, andthen you just apply each of them until you can listen in on the traffic. Onsmall primes and small numbers, you can do it with pencil and paper. A bitbigger 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 picka number so large that it takes anyone trying to listen in at least a fewmonths to generate all the possible shared secret keys so that they can listenin to any substantial amount of your traffic. And you want to make sure you’reprobably not using the same primes as anyone else, because then they mayalready have the work done.

Elliptic Curve Diffie-Hellman uses the same idea as above, but instead ofusing 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 a3072-bit prime, without significantly raising the processing cost for normaluse. The result is more security per unit of processing time. These asymmetricencryption key exchanges happen almost everywhere. Anywhere that TLS is used,like websites, email, chat, server-to-server communications, remote controlprotocols, and much more.

So how do we fix it?

The current recommendation is to switch to Elliptical Curve Diffie-Hellman (ECDH) for thekey exchange, and then follow with an elliptical curve signature likeElliptic Curve Digital Signature Algorithm (ECDSA) or ed25519. At the moment, elliptical curves are not known to have a similarvulnerability, however the selection of the named curve could be important tolimit any potential vulnerabilities. It’s also critical to note that there iscurrent ongoing research exploring methods to attack elliptical curveencryptions, and more efficient and practical ways to attack other forms (theadage “if it’s important enough to encrypt, it’s important enough that someonewants it” applies). ECDSA is based on the elliptical curveP-256that was mapped by NIST, and there is one suggested weakness that would allow for reduced solution time. The other optionon the table is the less commonly implemented Curve25519, which was generated to specifically provide anotheroption 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 andpackages, most notably anything backed by OpenSSL, so we’ll fall back to P-256where we can still use elliptical curves. Also worth noting is thatCNSS requires that you use the NIST curvesfor any work done for the National Security Systems, so if that fits you, youshould use P-256 or P-384 instead of Curve25519.

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

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

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

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

Adding ED25519 Support to OpenSSH

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

1. Update your SSH daemons and clients. Until you’re running the latest,there are possible conflicts, and also possible vulnerabilities in thedaemon itself.
2. Check to see if you already have the keys. On the server side, look in theSSH daemon config (/etc/ssh/sshd_config) to see if you have a lineaccepting the

ed25519

HostKey /etc/ssh/ssh_host_ed25519_key

1. . If it’s there, you’re alreadyconfigured 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

1. and follow theprompts. Note: if you enter a passphrase, SSH will need it to start, soyou probably shouldn’t do that for a remote server unless you like youriKVM.
2. Edit /etc/ssh/sshd_config to add the line

HostKey /etc/ssh/ssh_host_ed25519_key

1. near the other

HostKey

1. lines.
2. Restart the SSH daemon.

This enables clients to begin connecting with the new signature keys and stillenable them to use their old keys. You’ll probably want to have a transitionperiod where your users change their keys over before you move on to theremoval stage, and possibly stand up a test machine with the final changesmade 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 theyuse (with the

-i

option) to the new key. Farsight Security stronglyrecommends passphrases on the client side so that if the key is somehowstolen, people can’t easily access your infrastructure. The

-a 100

optiononly 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 moreiterations, the more secure as it increases significantly the amount of timerequired to bruteforce the key. However, as with all things, there is a costand the more iterations, the longer it takes for either a successfulconnection or a failure, so we suggest that people use the highest number thatthey can tolerate the time-cost of a typo.

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

Cutting over to ed25519:

1. Remove all lines starting with HostKey except the

HostKey /etc/ssh/ssh_host_ed25519_key

1. line.
2. Change (or add) your KexAlgorithms line to

KexAlgorithms [email protected]

1. .
2. Change (or add) your Ciphers line to

Ciphers [email protected],aes256-ctr

1. .
2. Restart the SSH daemon

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

1. Remove all unused host keys.
2. Change (or add) your

KexAlgorithms

1. line to

KexAlgorithms [email protected],diffie-hellman-group-exchange-sha256

1. Change (or add) your

Ciphers

1. line to

Ciphers [email protected],aes256-ctr

1. .
2. 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


1. Restart the SSH daemon

The

KexAlgorithms

handles the key exchange, and the cipher handles the actualencryption 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 andthe 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 passwordauthentication 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 thedaemon:

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). Thatleaves us with the only option being to use the NIST provided P-256 curveimplementations, and later return to switch to another curve.

Before you begin you should realize that the potential impact of locking downyour web engine can come with an unintended side effect: you will leave behindvisitors using older browsers and operating systems. Clients will need to berunning 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 useFirefox, which does not use the native encryption libraries and should be ableto handle the encryption. This is from the smaller, but necessary, step ofdisabling SSLv2 and SSLv3. There is another camp that strongly suggestsdisabling everything except TLSv1.2. As with all things, there are pros andcons to each decision. Disabling everything other than TLS v1.2 has a muchgreater 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 beable to see the hosted web pages. That is a relatively small slice of themarket, and serious thought and consideration should be made before thedecision is made. However, it’s possible that within the same organizationthere will be pages and servers that fall on each side of that line, and so youshould use what makes sense for them:

• Internal servers where the hardware is company controlled, displaying andtransferring 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 secureenvironment 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 youuse strong, non-standard primes, you’re probably going to be secure, especiallyif you replace them every few months. If you intend to use them to reach abroader audience, or even to give your web engine more flexibility, you’ll wantto generate a nonstandard prime. You’ll want to use different primes for eachtask.

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

Nginx

1. Run

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

1. Edit

/etc/nginx/nginx.conf

1. 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;


1. Restart Nginx.

Apache

1. Run

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

1. Edit

/etc/apache2/apache.conf

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


1. 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 Standardwith Galois/Counter Mode”, “Advanced Encryption Standard 256-bit with EphemeralElliptical Curve Diffie-Hellman” and then moving down to the options not using elliptical curve. This also disables SSLv2 and SSLv3, leaving only TLS. Thenext line of configuration is to tell the system to prefer the strongerencryption first, and the last line disables the storage and reuse of an sslsession. You can add back other ciphers to suit your needs with your clientsas needed.

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

There are a lot of other things you can do to secure your traffic againstinterception, and this is by no means a comprehensive guide, so please tune theencryption 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 acritical part of everyone’s day-to-day lives. It protects finances, privatecommunications, access credentials, companies, and in some nations, it protectslives. It’s important enough that we need to make sure we’re doing everythingwe can to protect our users, our employers and ourselves. Switching toelliptical curves where possible, using non-standard primes where we can’t,and ensuring we’re using the strongest ciphers possible helps to carry thatout.

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