Logjam: the latest security flaw threatening communication protocols

This new encryption attack compromises 8.4% of Alexa Top Million HTTPS sites, putting secure data at risk.

The official discovery of the logjam vulnerability, made few days ago by security researchers, affects the “Diffie-Hellman” key exchange algorithm which grants protocols such as SSH, HTTP and TLS to pass encryption keys over an insecure channel. The basis of the algorithm is for two users to agree on a key for encryption such that no third party can listen in, ensuring a secure transfer of information. This is done by using large prime values and computing (g^a mod p, g^b mod p) where p a prime number, g is a generator of a multiplicative group modulo p, and a, b are random secret values, one for each communicating party. The security of the scheme relies on the fact that it is easy to compute g^x mod p, but difficult to invert the computation to recover x given only g and p (the discrete logarithm problem).

The Logjam vulnerability involves two distinct weaknesses: one in the TLS protocol and one in the way that Diffie-Hellman key exchange is implemented. Due to a flaw in the TLS protocol, a man-in-the-middle attack could be implemented, which would downgrade a Diffie-Hellman key exchange to a less-secure 512-bit export grade version. Many TLS servers are configured to accept DHE_EXPORT primes (which are 512 bits long), allowing an attacker to recover the shared secret.

The TLS protocol weakness in Logjam is similar to the FREAK attack that occurred back in March, except that it involves a Diffie-Hellman key exchange rather than an RSA key exchange (another public key cryptosystem). The implementation weakness of Logjam is made possible by the following observations:

a) For key exchanges involving the same prime p, the discrete logarithm computation can be split into two parts, the first of which takes a lot of computing effort but can be precomputed ahead of time, and a second part which has to be repeated for each individual key exchange, but can be done near-real time.

b) Since generating prime numbers with the special properties required for Diffie-Hellman is not trivial, a lot of implementations reuse the same small set of prime numbers that are known to be safe from number-theoretic shortcuts.

It took researchers a week to precompute the first part for a 512-bit prime (used by 82% of vulnerable HTTPS servers) and they were then able to leverage the result to crack DH key exchanges using this prime within 90 seconds on average. Precomputation attacks for 768 and 1024 bit groups, which are extensively used in practice, were also explored. Results showed that precomputations for the 768-bit groups were within reach of academic teams, while 1024-bit groups were a distinct possibility for nation-state attackers.

The researchers recommend disabling all support for export grade RSA (512-bit primes) and configure DH groups of at least 1024 bits or, better yet, 2048 bits. This will prevent downgrade attacks during communication with servers that still support DHE_EXPORT. A long term recommendation involves transitioning to elliptic curve Diffie-Hellman key exchange, as it is not affected by the precomputation attack described above.

Source: https://weakdh.org/imperfect-forward-secrecy.pdf

Akash Malhotra is a Technical Writer at eSentire.