Diffie-Hellman Primes and Keys

Millions of HTTPS, SSH, and VPN servers that use the Diffie-Hellman key exchange protocol, when a client attempts to create a secure connection to a server, do so in a poorly configured way and may be susceptible to passive eavesdropping, depending on server configuration and key strength, as demonstrated by the Logjam attack [CVE-2015-4000].

We assess a server’s Diffie-Hellman configuration if it exists, in order to help evaluate configurations and conditions that are below current security standards, including a server’s vulnerability to the Logjam attack.

Frequently Asked Questions

What is a Diffie-Hellman key exchange?

It is a specific method of publicly exchanging cryptographic keys and allows two parties to create a shared secret over insecure channels to establish encrypted communication. It is mathematically easy to generate a shared secret, but quite difficult for third parties to reverse.

A significant component of the key exchange is a static prime number stored on the server for use in generating the public keys during key exchanges, called a “Diffie-Hellman prime.”

Why are Diffie-Hellman primes evaluated?

The most efficient mathematical algorithm for breaking a Diffie-Hellman connection is dependent only on this prime. After this first step, an attacker can quickly break individual connections for any server using this prime.

An attacker needs to spend a significant amount of time and effort to calculate all the values required to break a set of session keys, but those values only need to be calculated once per prime. This means there are advantages to going after common primes, as there is a much bigger ROI (return on investment).

How are Diffie-Hellman primes assessed?

We evaluate Diffie-Hellman primes based on if servers on a company’s infrastructure use the Diffie-Hellman key exchange protocol, the size of the primes, and if those primes are commonly used by other servers.

How is information on Diffie-Hellman primes collected?

Primes (prime groups) are sent publicly to clients by servers as part of the Diffie-Hellman key exchange process. We check the prime being sent against lists of known common primes.

What is a common Diffie-Hellman prime?

A common Diffie-Hellman prime is a published value, sourced from software libraries or other publications, used during key exchange.

Common Diffie-Hellman primes are considered a security hazard because of the return on investment on time spent by adversaries on breaking a common prime: Once the prime is broken by an adversary, it is easier for them to passively eavesdrop on encrypted communications from other servers that use the same common primes.

What is a common Diffie-Hellman key?

A common Diffie-Hellman key is seen on more than one server and is created using the configured Diffie-Hellman prime. Multiple servers that use the same public key (a commonly-seen key) for calculating the “master secret” for encrypting an upcoming session indicates a poorly configured server.

Why are Diffie-Hellman primes less than or equal to 512 bits considered bad?

Primes less than 1024 bits are estimated to be breakable by groups with resources ranging from consumer-level hardware to those of an academic institution.

How is a Diffie-Hellman prime graded?

Strength: We currently grade primes less than or equal to 512 bits as BAD, and less than 2048 bits as WARN. If a server uses a Diffie-Hellman prime greater than or equal to 2048 bits, it is graded as GOOD.

Commonality: Any prime less than or equal to 512 bits that appears on more than 1,000 IP addresses are considered broken, so these findings are graded as BAD. The 2048-bit common primes sub-groups can be vulnerable to small subgroup key recovery attacks. We recommend not using a common subgroup form and generating your own DH/ECDH keys^[4].

Since the 2048-bit common primes subgroups are vulnerable to small subgroup key recovery attacks, they are considered to be risky. This is based on research done by the University of Pennsylvania, the University of Michigan, and Adobe, which states the following:

We performed a best-effort attempt to factor p − 1 for all non-safe primes that we found in the wild, using ~100,000 core-hours of computation. Group 23 from RFC 5114, a 2048-bit prime, is particularly vulnerable to small subgroup key recovery attacks; for TLS a full key recovery requires 2^33 online work and 2^47 offline work to recover a 224-bit exponent.