JANUARY 2019 | VOL. 62 | NO. 1 | COMMUNICATIONS OF THE ACM 113
for its Suite B cryptographic algorithms and would replace
them with algorithms resistant to quantum computers. 16
However, since no fully vetted and standardized quantum-resistant algorithms exist currently, elliptic curves remain
the most secure choice for public key operations.
Increase minimum key strengths
To protect against the Logjam attack, server operators should
disable DHE_EXPORT and configure DHE ciphersuites to use
primes of 2048 bits or larger. Browsers and clients should
raise the minimum accepted size for Diffie-Hellman groups
to at least 1024 bits in order to avoid downgrade attacks.
Don’t deliberately weaken cryptography
The Logjam attack illustrates the fragility of cryptographic
“front doors.” Although the key sizes originally used in
DHE_EXPORT were intended to be tractable only to NSA, two
decades of algorithmic and computational improvements
have significantly lowered the bar to attacks on such key
sizes. Despite the eventual relaxation of cryptography export
restrictions and subsequent attempts to remove support for
DHE_EXPORT, the technical debt induced by the additional
complexity has left implementations vulnerable for decades.
Like FREAK, 1 our results warn of the long-term debilitating
effects of deliberately weakening cryptography.
We find that Diffie-Hellman key exchange, as used in practice, is often less secure than widely believed. The problems
stem from the fact that the number field sieve for discrete
logarithms allows an attacker to perform a single precomputation that depends only on the group, after which computing individual logarithms in that group has a far lower cost.
Although this is well known to cryptographers, it apparently
has not been widely understood by system builders. Likewise,
many cryptographers did not appreciate that a large fraction
of Internet communication depends on a few small, widely
A key lesson is that cryptographers and creators of practical
systems need to work together more effectively. System builders should take responsibility for being aware of applicable
cryptanalytic attacks. Cryptographers should involve themselves in how cryptography is actually being applied, such
as through engagement with standards efforts and software
review. Bridging the perilous gap that separates these communities will be essential for keeping future systems secure.
The authors thank Michael Bailey, Daniel Bernstein, Ron
Dreslinski, Tanja Lange, Adam Langley, Kenny Paterson,
Andrei Popov, Ivan Ristic, Edward Snowden, Brian Smith,
Martin Thomson, and Eric Rescorla. This work was supported by the U.S. National Science Foundation, the Office
of Naval Research, the European Research Council, and the
French National Research Agency, with additional support
from the Mozilla Foundation, Supermicro, Google, Cisco,
the Morris Wellman Professorship, and the Alfred P. Sloan
Foundation. Some experiments used the Grid’5000 testbed,
supported by INRIA, CNRS, RENATER, and others.
the 768-bit Oakley Group 1 and 66.1% preferred the 1024-bit
Oakley Group 2. For IKEv2, 5.8% of profiled servers chose
Oakley Group 1, and 63.9% chose Oakley Group 2.
SSH. All SSH handshakes complete either a finite field or
elliptic curve Diffie-Hellman exchange. The protocol explicitly defines support for Oakley Group 2 (1024-bit) and Oakley
Group 14 (2048-bit) but also allows a server-defined group to
be negotiated. We scanned 1% random samples of the public IPv4 address space in April 2015. We found that 98.9% of
SSH servers supported the 1024-bit Oakley Group 2, 77.6%
supported the 2048-bit Oakley Group 14, and 68.7% supported a server-defined group.
During the SSH handshake, the server selects the client’s highest priority mutually supported key exchange
algorithm. To estimate what servers will prefer in practice,
we performed a scan in which we mimicked the algorithms
offered by OpenSSH 6. 6.1p1, the latest version of OpenSSH.
In this scan, 21.8% of servers preferred the 1024-bit Oakley
Group 2, and 37.4% preferred a server-defined group. 10% of
the server-defined groups were 1024-bit, but, of those, nearly
all provided Oakley Group 2 rather than a custom group.
Combining these equivalent choices, we find that a
nation-state adversary who performed NFS precomputations for the 1024-bit Oakley Group 2 could passively eavesdrop on connections to 3.6mn ( 25.7%) publicly accessible
HTTPS. Our 2015 scans found that DHE was commonly
deployed on web servers. 68.3% of Alexa Top Million sites
supported DHE, as did 23.9% of sites with browser-trusted
certificates. Of the Top Million sites that supported DHE,
84% used a 1024-bit or smaller group, with 94% of these
using one of five groups.
Despite widespread support for DHE, a passive eavesdropper can only decrypt connections that organically agree to
use Diffie-Hellman. We estimated the number of sites for
which this would occur by offering the same sets of ciphersuites as Chrome, Firefox, and Safari. We found that browser
connections to approximately 24% of browser connections
with HTTPS-enabled Top Million sites (and 10% of all sites
with browser-trusted sites certificates) would negotiate DHE
using one of the ten most popular 1024-bit primes. After
completing the NFS precomputation for only the most popular 1024-bit prime, an adversary could passive eavesdrop
on browser connections to 17.9% of Top Million sites.
In this section, we present concrete recommendations to
recover the expected security of Diffie-Hellman.
Transition to elliptic curves
Transitioning to Elliptic Curve Diffie-Hellman (ECDH) key
exchange avoids all known feasible cryptanalytic attacks.
Current elliptic curve discrete logarithm algorithms do not
gain as much of an advantage from precomputation. In addition, ECDH keys are shorter and computations are faster.
We recommend transitioning to elliptic curves; this is the
most effective solution to the vulnerabilities in this paper.
We note that in August 2015, NSA announced that it was
planning to transition away from elliptic curve cryptography