JANUARY 2019 | VOL. 62 | NO. 1 | COMMUNICATIONS OF THE ACM 107
logarithm. In fact, as illustrated in Figure 1, a single large
precomputation on p can be used to efficiently break all
Diffie-Hellman exchanges made with that prime.
Diffie-Hellman is typically implemented with prime fields
and large group orders. In this case, the most efficient known
algorithm for computing discrete logarithms is the Number
Field Sieve (NFS). 9, 11, 18 The algorithm has four stages with
different computational properties. The first three steps are
only dependent on the prime p and comprise most of the
First is polynomial selection, in which one finds a polynomial f (z) defining a number field Q[z]/f (z) for the computation. This parallelizes well and is only a small portion of the
In the second stage, sieving, one factors ranges of integers
and number field elements in batches to find many relations of elements, all of whose prime factors are less than
some bound B (called B-smooth). Sieving parallelizes well,
but is computationally expensive, because we must search
through and attempt to factor many elements.
In the third stage, linear algebra, we construct a large,
sparse matrix consisting of the coefficient vectors of prime
factorizations we have found. This stage can be parallelized
in a limited fashion, and produces a database of logarithms
which are used as input to the final stage.
The final stage, descent, actually deduces the discrete logarithm of the target y. We re-sieve until we find a set of relations
that allow us to write the logarithm of y in terms of the logarithms in the precomputed database. Crucially, descent is the
only NFS stage that involves y (or g), so polynomial selection,
sieving, and linear algebra can be done once for a prime p and
reused to compute the discrete logarithms of many targets.
The numerous parameters of the algorithm allow some flexibility to reduce time on some computational steps at the expense
of others. For example, sieving more will result in a smaller
matrix, making linear algebra cheaper, and doing more work in
the precomputation makes the final descent step easier.
Generating safe primesb can be computationally bur-
densome, so many implementations use standardized
and still considered secure. We estimate the computational
resources necessary to compute discrete logarithms in groups
of these sizes, concluding that 768-bit groups are within
range of academic teams, and 1024-bit groups may plausibly
be within range of nation-state adversaries. In both cases,
individual logarithms can be quickly computed after the ini-
We then examine evidence from published Snowden documents that suggests that the National Security Agency (NSA)
may already be exploiting 1024-bit Diffie-Hellman to decrypt
Virtual Private Network (VPN) traffic. We perform measurements to understand the implications of such an attack for
popular protocols, finding that an attacker who could perform precomputations for ten 1024-bit groups could passively
decrypt traffic to about 66% of Internet Key Exchange (IKE)
VPNs, 26% of SSH servers, and 24% of popular HT TPS sites.
Mitigations and lessons
In response to the Logjam attack, mainstream browsers
have implemented a more restrictive policy on the size of
Diffie-Hellman groups they accept, and Google Chrome has
discontinued support for finite field key exchanges. We further recommend that TLS servers disable export-grade cryptography and carefully vet the Diffie-Hellman groups they
use. In the longer term, we advocate that protocols migrate
to elliptic curve Diffie-Hellman.
2. DIFFIE-HELLMAN CRYPTANALYSIS
Diffie-Hellman key exchange was the first published public-key algorithm. 5 In the simple case of prime groups, Alice and
Bob agree on a prime p and a generator g of a multiplicative
subgroup modulo p. Then each generates a random private
exponent, a and b. Alice sends ga mod p, Bob sends gb mod
p, and each computes a shared secret gab mod p. While there
is also a Diffie-Hellman exchange over elliptic curve groups,
we address only the “mod p” case.
The security of Diffie-Hellman is not known to be equivalent to the discrete logarithm problem, but computing
discrete logarithms remains the best known cryptanalytic
attack. An attacker who can find the discrete logarithm x
from y = gx mod p can easily find the shared secret.
Textbook descriptions of discrete logarithm algorithms
can be misleading about the computational tradeoffs, for
example by optimizing for computing a single discrete
y, g Descent
Figure 1. Number field sieve for discrete logarithms. This algorithm consists of a precomputation stage that depends only on the prime p
and a descent stage that computes individual logarithms. With sufficient precomputation, an attacker can quickly break any Diffie-Hellman
instances that use a particular p.
b An odd prime p is safe when (p − 1)/2 is prime.