“LogJam”, discovered by a group of academic security researchers, is the latest security bug to put Internet users at risk and send developers scrambling to deploy configuration changes and software patches. LogJam allows a sophisticated and well-funded hacker to decrypt encrypted communications sent using a wide range of protocols by exploiting the initial key exchange process called Diffie-Hellman. It is still unclear if state level hackers have taken advantage of LogJam, but the researchers who discovered this problem have done the math and it seems a reasonable possibility given the enormous budgets available to groups such as the NSA.

What is Diffie-Hellman?

If you want to encrypt communications with someone you may have never met before, you first have to choose a mutually agreeable encryption key by which traffic between the two of you can be encrypted and decrypted. Assuming there is always the possibility of an observer reading your traffic, how can you even begin communication and agree on an encryption key to use, without letting the third party know what it is? This is the challenge addressed by the Diffie-Hellman key exchange (D-H), which was invented by cryptographers Whitfield Diffie and Martin Hellman in 1976.

D-H has withstood decades of academic scrutiny[1] without revealing any significant points of weakness. Over the years, D-H has made its way into a wide variety of common cryptographic applications including SSL/TLS, VPNs and secure shell (SSH). There are many key exchange mechanisms, but D-H is in very common use.

A simple analogy explains how D-H works. Alice and Bob want to talk to each other securely and to do this they need a shared secret color that will enable them to create an encryption key known only to each other. To create the shared key, they agree to each secretly mix a bucket of special yellow paint with a secret color of paint that they do not reveal to each other (or anyone else). Once they have each mixed their secret color with the yellow paint, they share their resulting mixture with each other. They then take the other person’s mixed color and secretly mix that with their own secret color (again). It’s easy to see that after they each take this step, they will end up with the exact same color of paint, because after the process is finished, each person’s paint pot has the same mixture of different colors in it. The resulting paint color (e.g. “brown”) is the shared key. To make the analogy work, we assume that “un-mixing” the mixed paint to figure out what colors went into it is a very, very hard problem.

 

How Diffie-Hellman is Exploited by LogJam

Diffie-Hellman

How Diffie-Hellman is Exploited by LogJam

The LogJam problem results from how D-H is used in practice, and is not a general weakness in D-H. The security of D-H results from the immense difficulty involved in un-mixing the paint from our analogy: given the mixed paint pots shared between Alice and Bob, it’s very difficult to figure out the secret colors used by each party. However, in the 1990s, legislation to reduce the potential for foreigners to use powerful encryption resulted in many protocol implementations offering a weakened color palette that makes it relatively easier to un-mix the paint.

Furthermore, for the sake of simplicity, many encryption implementations always use the same initial color (i.e. yellow in our analogy) for mixing the paint. Researchers have discovered that if the initial color is known ahead of time, you can pre-compute a large part of the numerical effort required to un-mix the colors from any D-H exchange using that color initially. Indeed researchers found that 82% of web servers that offer the 1990s low-security color palette also all use exactly the same initial color. By pre-computing the un-mixing process for that initial color, researchers were able to decrypt arbitrary secure web connections to these servers in just minutes.

But the researchers went further than this. They also showed that government agencies such as the NSA probably have the capability to pre-compute for even stronger paint palettes – palettes that were until now considered safe for use. With an investment of several $100M in specialized microprocessors and supercomputers, agencies like the NSA might be able to routinely decrypt encrypted communications that are secured with even strong D-H shared keys.

Should I worry?

By analyzing documents leaked by Edward Snowden, the LogJam researchers deduced that NSA is quite possibly able to determine D-H shared secrets involved in certain IPsec VPN connections. In fact, the researchers found that if the NSA is capable of pre-computing just one of the common “initial colors” used by IKEv1 IPv4 VPN’s, this would enable interception of 66% of such VPN connections worldwide. Results for other protocols were similarly disheartening.

Everyone should be worried about LogJam, and should take the reasonable steps outlined by the researchers to improve the security of D-H. Here are the steps you should take, based on their advice:

  1. Increase the minimum key strength used in D-H groups to 2,048 bits, and configure your software to generate a new unique D-H group. By generating your own “initial color”, you make it nearly impossible for anyone to spend the resources needed to then decrypt session keys efficiently. And by moving to 2,048 bits, the color palette is made so enormous as to make efficient decryption completely infeasible with current technology.
  2. Transition to “elliptic curve” Diffie-Hellman. Most D-H implementations use a prime number based process, which the researchers found to be lacking as described above. Elliptic curve Diffie-Hellman uses a newer cryptographic technique (elliptic curves) that is not known to be vulnerable in the same way.
  3. Don’t allow downgrades to 512-bit D-H groups (i.e. 1990s export crypto).

 

The researchers who discovered LogJam summed it up with a recommendation to the security community:

“A key lesson from this state of affairs is that cryptographers and creators of practical systems need to communicate better. Systems builders should be aware of the difficulty of crypto-graphic attacks and tradeoffs, and cryptographers should be aware of how systems are actually being implemented and used in practice.”

It’s not enough to simply implement great crypto systems. The entire community – from mathematicians to sysadmins – needs to talk more to make sure they’re hearing each other right. As state level hackers build more powerful machines, we have to assume the worst if we want to maintain our privacy and security.

[1] Breaking Diffie-Hellman requires solving the so-called Diffie-Hellman Problem, which is described very well in this Wikipedia article: http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_problem.