Imperfect Forward Secrecy:
How Diffie-Hellman Fails in Practice
David Adrian
¶
Karthikeyan Bhargavan
∗
Zakir Durumeric
¶
Pierrick Gaudry
†
Matthew Green
§
J. Alex Halderman
¶
Nadia Heninger
‡
Drew Springall
¶
Emmanuel Thomé
†
Luke Valenta
‡
Benjamin VanderSloot
¶
Eric Wustrow
¶
Santiago Zanella-Béguelin
k
Paul Zimmermann
†
∗
INRIA Paris-Rocquencourt
†
INRIA Nancy-Grand Est, CNRS, and Université de Lorraine
k
Microsoft Research
‡
University of Pennsylvania
§
Johns Hopkins
¶
University of Michigan
For additional materials and contact information, visit WeakDH.org.
ABSTRACT
We investigate the security of Diffie-Hellman key exchange as
used in popular Internet protocols and find it to be less secure
than widely believed. First, we present Logjam, a novel flaw
in TLS that lets a man-in-the-middle downgrade connections
to “export-grade” Diffie-Hellman. To carry out this attack,
we implement the number field sieve discrete log algorithm.
After a week-long precomputation for a specified 512-bit
group, we can compute arbitrary discrete logs in that group
in about a minute. We find that 82% of vulnerable servers use
a single 512-bit group, allowing us to compromise connections
to 7% of Alexa Top Million HTTPS sites. In response, major
browsers are being changed to reject short groups.
We go on to consider Diffie-Hellman with 768- and 1024-bit
groups. We estimate that even in the 1024-bit case, the com-
putations are plausible given nation-state resources. A small
number of fixed or standardized groups are used by millions
of servers; performing precomputation for a single 1024-bit
group would allow passive eavesdropping on 18% of popular
HTTPS sites, and a second group would allow decryption
of traffic to 66% of IPsec VPNs and 26% of SSH servers. A
close reading of published NSA leaks shows that the agency’s
attacks on VPNs are consistent with having achieved such
a break. We conclude that moving to stronger key exchange
methods should be a priority for the Internet community.
1. INTRODUCTION
Diffie-Hellman key exchange is widely used to establish
session keys in Internet protocols. It is the main key exchange
mechanism in SSH and IPsec and a popular option in TLS.
We examine how Diffie-Hellman is commonly implemented
and deployed with these protocols and find that, in practice,
it frequently offers less security than widely believed.
There are two reasons for this. First, a surprising number
of servers use weak Diffie-Hellman parameters or maintain
support for obsolete 1990s-era export-grade crypto. More
critically, the common practice of using standardized, hard-
Permission to make digital or hard copies of part or all of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full cita-
tion on the first page. Copyrights for third-party components of this work must be
honored. For all other uses, contact the Owner/Author(s). Copyright is held by the
owner/author(s).
CCS’15, October 12–16, 2015, Denver, Colorado, USA.
ACM 978-1-4503-3832-5/15/10.
DOI: http://dx.doi.org/10.1145/2810103.2813707.
coded, or widely shared Diffie-Hellman parameters has the
effect of dramatically reducing the cost of large-scale attacks,
bringing some within range of feasibility today.
The current best technique for attacking Diffie-Hellman
relies on compromising one of the private exponents (
a
,
b
)
by computing the discrete log of the corresponding public
value (
g
a
mod p
,
g
b
mod p
). With state-of-the-art number
field sieve algorithms, computing a single discrete log is more
difficult than factoring an RSA modulus of the same size.
However, an adversary who performs a large precomputation
for a prime
p
can then quickly calculate arbitrary discrete logs
in that group, amortizing the cost over all targets that share
this parameter. Although this fact is well known among
mathematical cryptographers, it seems to have been lost
among practitioners deploying cryptosystems. We exploit it
to obtain the following results:
Active attacks on export ciphers in TLS. We introduce
Logjam, a new attack on TLS by which a man-in-the-middle
attacker can downgrade a connection to export-grade cryp-
tography. This attack is reminiscent of the FREAK attack [7]
but applies to the ephemeral Diffie-Hellman ciphersuites and
is a TLS protocol flaw rather than an implementation vulner-
ability. We present measurements that show that this attack
applies to 8.4% of Alexa Top Million HTTPS sites and 3.4%
of all HTTPS servers that have browser-trusted certificates.
To exploit this attack, we implemented the number field
sieve discrete log algorithm and carried out precomputation
for two 512-bit Diffie-Hellman groups used by more than
92% of the vulnerable servers. This allows us to compute
individual discrete logs in about a minute. Using our discrete
log oracle, we can compromise connections to over 7% of Top
Million HTTPS sites. Discrete logs over larger groups have
been computed before [8], but, as far as we are aware, this
is the first time they have been exploited to expose concrete
vulnerabilities in real-world systems.
We were also able to compromise Diffie-Hellman for many
other servers because of design and implementation flaws and
configuration mistakes. These include use of composite-order
subgroups in combination with short exponents, which is
vulnerable to a known attack of van Oorschot and Wiener [51],
and the inability of clients to properly validate Diffie-Hellman
parameters without knowing the subgroup order, which TLS
has no provision to communicate. We implement these
attacks too and discover several vulnerable implementations.
Risks from common 1024-bit groups. We explore the im-
plications of precomputation attacks for 768- and 1024-bit
groups, which are widely used in practice and still considered
评论1