DOI: http://dx.doi.org/10.1145/2810103.2813707.
groups, which are widely used in practice and still considered
ACM 978-1-4503-3832-5/15/10.
plications of precomputation attacks for 768- and 1024-bit
CCS’15, October 12–16, 2015, Denver, Colorado, USA.
Risks from common 1024-bit groups.      We explore the im-
owner/author(s).
honored.  For all other uses, contact the Owner/Author(s).  Copyright is held by the
attacks too and discover several vulnerable implementations.
tion on the first page.   Copyrights for third-party components of this work must be
has no provision to communicate.  We implement these
for profit or commercial advantage and that copies bear this notice and the full cita-
classroom use is granted without fee provided that copies are not made or distributed
parameters without knowing the subgroup order, which TLS
Permission to make digital or hard copies of part or all of this work for personal or                   and the inability of clients to properly validate Diffie-Hellman
vulnerable to a known attack of van Oorschot and Wiener [51],
subgroups in combination with short exponents, which is
configuration mistakes. These include use of composite-order
critically, the common practice of using standardized, hard-
other servers because of design and implementation flaws and
support for obsolete 1990s-era export-grade crypto. More
We were also able to compromise Diffie-Hellman for many
of servers use weak Diffie-Hellman parameters or maintain
vulnerabilities in real-world systems.
There are two reasons for this. First, a surprising number
is the first time they have been exploited to expose concrete
it frequently offers less security than widely believed.
been computed before [8], but, as far as we are aware, this
and deployed with these protocols and find that, in practice,
Million HTTPS sites. Discrete logs over larger groups have
We examine how Diffie-Hellman is commonly implemented
log oracle, we can compromise connections to over 7% of Top
mechanism in SSH and IPsec and a popular option in TLS.
individual discrete logs in about a minute. Using our discrete
session keys in Internet protocols. It is the main key exchange
92% of the vulnerable servers. This allows us to compute
Diffie-Hellman key exchange is widely used to establish
for two 512-bit Diffie-Hellman groups used by more than
1.    INTRODUCTION
sieve discrete log algorithm and carried out precomputation
To exploit this attack, we implemented the number field
methods should be a priority for the Internet community.    of all HTTPS servers that have browser-trusted certificates.
a break. We conclude that moving to stronger key exchange applies to 8.4% of Alexa Top Million HTTPS sites and 3.4%
attacks on VPNs are consistent with having achieved such   ability. We present measurements that show that this attack
close reading of published NSA leaks shows that the agency’s is a TLS protocol flaw rather than an implementation vulner-
of traffic to 66% of IPsec VPNs and 26% of SSH servers. A but applies to the ephemeral Diffie-Hellman ciphersuites and
HTTPS sites, and a second group would allow decryption    tography. This attack is reminiscent of the FREAK attack [7]
group would allow passive eavesdropping on 18% of popular  attacker can downgrade a connection to export-grade cryp-
of servers; performing precomputation for a single 1024-bit   Logjam, a new attack on TLS by which a man-in-the-middle
number of fixed or standardized groups are used by millions Active attacks on export ciphers in TLS.        We introduce
putations are plausible given nation-state resources. A small
to obtain the following results:
groups. We estimate that even in the 1024-bit case, the com-
among practitioners deploying cryptosystems. We exploit it
We go on to consider Diffie-Hellman with 768- and 1024-bit
mathematical cryptographers, it seems to have been lost
browsers are being changed to reject short groups.
this parameter. Although this fact is well known among
to 7% of Alexa Top Million HTTPS sites. In response, major
in that group, amortizing the cost over all targets that share
a single 512-bit group, allowing us to compromise connections
for a primep can then quickly calculate arbitrary discrete logs
in about a minute. We find that 82% of vulnerable servers use
However, an adversary who performs a large precomputation
group, we can compute arbitrary discrete logs in that group
difficult than factoring an RSA modulus of the same size.
After a week-long precomputation for a specified 512-bit
field sieve algorithms, computing a single discrete log is more
we implement the number field sieve discrete log algorithm.
value (ga mod p, gb mod p). With state-of-the-art number
to “export-grade” Diffie-Hellman. To carry out this attack,
by computing the discrete log of the corresponding public
in TLS that lets a man-in-the-middle downgrade connections
relies on compromising one of the private exponents (a, b)
than widely believed. First, we present Logjam, a novel flaw
The current best technique for attacking Diffie-Hellman
used in popular Internet protocols and find it to be less secure
bringing some within range of feasibility today.
We investigate the security of Diffie-Hellman key exchange as
effect of dramatically reducing the cost of large-scale attacks,
coded, or widely shared Diffie-Hellman parameters has the
ABSTRACT
For additional materials and contact information, visit WeakDH.org.
kMicrosoft Research    ‡ University of Pennsylvania    § Johns Hopkins    ¶ University of Michigan
∗ INRIA Paris-Rocquencourt    † INRIA Nancy-Grand Est, CNRS, and Université de Lorraine
¶           ¶                     k              †
Benjamin VanderSloot  Eric Wustrow  Santiago Zanella-Béguelin  Paul Zimmermann
¶             ‡            ¶               †           ‡
J. Alex Halderman   Nadia Heninger  Drew Springall  Emmanuel Thomé  Luke Valenta
¶                   ∗             ¶             †             §
David Adrian  Karthikeyan Bhargavan  Zakir Durumeric  Pierrick Gaudry  Matthew Green
How Diffie-Hellman Fails in Practice
Imperfect Forward Secrecy:
----------------Page (0) Break----------------
2
(NFS) [21,24,43]. 1 There is a closely related number field    apply to the prime fields used in practice.
characteristic fields [3], but these advances are not known to
most efficient discrete log algorithm is the number field sieve
have resulted in a quasi-polynomial algorithm for small-
with prime fields and large group orders. In this case, the
1Recent spectacular advances in discrete log algorithms
The typical case Diffie-Hellman is typically implemented
Diffie-Hellman exchanges made with that prime.
compute the discrete logs of many targets.
precomputation on p can be used to efficiently break all
linear algebra can be done once for a primep and reused to
discrete log. In fact, as illustrated in Figure 1, a single large
that involvesy (or g), so polynomial selection, sieving, and
parameters to minimize overall time to compute a single
the log database. Crucially, descent is the only NFS stage
about the computational tradeoffs, for example by balancing
and a final phase that actually reconstructs the target using
Textbook descriptions of discrete log can be misleading
be represented by elements in the database of known logs,
log x from y = gx mod p can easily find the shared secret.
these medium-sized primes are further sieved until they can
cryptanalytic attack. An attacker who can find the discrete
in terms of medium-sized primes, a middle phase, in which
33,34]), but computing discrete logs remains the best known
phases: an initialization phase, which tries to write the target
lent to the discrete log problem (except in certain groups [13,
precomputed database. This step is accomplished in three
The security of Diffie-Hellman is not known to be equiva-
that allow us to write the log ofy in terms of the logs in the
over elliptic curve groups, we address only the “modp” case.
of the targety. We re-sieve until we can find a set of relations
gab mod p. While there is also a Diffie-Hellman exchange
The final stage,descent, actually deduces the discrete log
Bob sends gb mod p, and each computes a shared secret
size and can be parallelized in a limited fashion.
multiplicative subgroup modulo p. Alice sends ga mod p,
to the final stage. The difficulty depends onq and the matrix
Alice and Bob agree on a primep and a generator g of a
many small elements. This database of logs serves as input
key algorithm [14].  In the simple case of prime groups,
matrix modulo the orderq of the group will give us logs of
Diffie-Hellman key exchange was the first published public-
factorizations we have found. A nonzero kernel vector of the
2.    DIFFIE-HELLMAN CRYPTANALYSIS
sparse matrix consisting of the coefficient vectors of prime
In the third stage, linear algebra , we construct a large,
Diffie-Hellman groups, such as those based on elliptic curves.
to consider before having enough relations.
longer term, we advocate that protocols migrate to stronger
search; it also depends onI and on the number of specialq
carefully vet the Diffie-Hellman groups they use.  In the
the probability of encounteringB-smooth numbers in this
that TLS servers disable export-grade cryptography and
The time for this step depends on heuristic estimates of
Diffie-Hellman groups they accept. We further recommend
must search through and attempt to factor many elements.
are implementing a more restrictive policy on the size of
of the others, but is computationally expensive, because we
in response to the Logjam attack, all mainstream browsers
parallelizes well since each specialq is handled independently
Mitigations and lessons.    As a short-term countermeasure
region of 22I   candidates, where I is a parameter. Sieving
16% of SMTP servers, and 24% of popular HTTPS sites.    lattice sieving, which for each specialq explores a sieving
crypt traffic to about 66% of IKE VPNs, 26% of SSH servers,B (called B-smooth). Modern implementations usespecial-q
precomputations for ten 1024-bit groups could passively de-  elements, all of whose prime factors are less than some bound
popular protocols, finding that an attacker who could performand number field elements in batches to find many relations of
ments to understand the implications of such an attack for    In the second stage,sieving, one factors ranges of integers
Diffie-Hellman to decrypt VPN traffic. We perform measure- parallelizes well and is only a small portion of the runtime.
ments that suggests NSA may already be exploiting 1024-bit tion. (For our cases,f (z) typically has degree 5 or 6.) This
We then examine evidence from published Snowden docu-  mial f (z) defining a number fieldQ(z)/f  (z) for the computa-
can be quickly computed after the initial precomputation.      First is polynomial selection , in which one finds a polyno-
range of state-level attackers. In both cases, individual logs   on the primep and comprise most of the computation.
demic teams, and 1024-bit groups may plausibly be within   tational properties. The first three steps are only dependent
sizes, concluding that 768-bit groups are within range of aca- called index calculus and has four stages with different compu-
sources necessary to compute discrete logs in groups of these the implementations can be shared. The general technique is
secure. We provide new estimates for the computational re-  sieve algorithm for factoring [12,31], and in fact many parts of
any Diffie-Hellman instances that use a particularp.
the primep and a descent stage that computes individual logs. With sufficient precomputation, an attacker can quickly break
Figure 1: The number field sieve algorithm for discrete logconsists of a precomputation stage that depends only on
precomputation                                                                       individual log
log  db
p                                                                                                                                                     x
selection                                                        algebra
y, g
descen  t
sieving
polynomial                                                        linear
----------------Page (1) Break----------------
3
well within reach of NFS-based cryptanalysis. Furthermore,   we focus exclusively on the traditional prime field variety.
curve Diffie-Hellman (ECDHE) are gaining in popularity, but
“export-grade” Diffie-Hellman using 512-bit primes that are
contained in its certificate. New ciphersuites that use elliptic
However, a smaller number of servers also support legacy
format, where the server’s key exchange value is fixed and
HTTPS sites allow it, most commonly using 1024-bit primes.
2TLS also supports a rarely used “static” Diffie-Hellman
key exchange methods, and about two-thirds of popular
TLS supports Diffie-Hellman as one of several possible     tography, SSL 3.0 and TLS 1.0 supported reduced-strength
To comply with 1990s-era U.S. export restrictions on cryp-
3.    ATTACKING TLS
keys also derived fromgab.
data, protected by an authenticated encryption scheme with
log precomputation among vast numbers of potential targets.
Thereafter, client and server start exchanging application
since it allows the attacker to amortize the cost of discrete
in a pair ofFinished messages and verified by the recipients.
limits of an adversary’s capabilities into devastating breaks,
of the handshake transcript. These MACs are exchanged
of Diffie-Hellman groups can convert attacks that are at the
TLS master secret fromgab and calculates a MAC of its view
no disadvantage to reusing them. However, widespread reuse
prevent downgrade attacks [52], each party computes the
When primes are of sufficient strength, there seems to be
To ensure agreement on the negotiation messages, and to
since, including IKE, SSH, Tor, and OTR.
with a ClientKeyExchange message containingga.
published in 1998 and have been used for many applications
its certificate. The client verifies the signature and responds
Group 2), and 1536 (Oakley Group 5). These groups were
tuple (cr, sr, p, g, g     b) using the long-term signing key from
“safe” primes of length 768 (Oakley Group 1), 1024 (Oakley
a ServerKeyExchange message containing a signature over the
A prominent example is the Oakley groups [40], which give
parameters. It chooses a group(p, g ), computes gb, and sends
tations use fixed or standardized Diffie-Hellman parameters.  DHE
, the server is responsible for selecting the Diffie-Hellman
ties can be computationally burdensome, so many implemen-
is identified by ciphersuites that begin withTLS_DHE_*.2 In
Standard primes  Generating primes with special proper-                                              DHE
strength is called “ephemeral” Diffie-Hellman, or , and
baby-step giant-step or Pollard rho.                        Diffie-Hellman. Textbook Diffie-Hellman with unrestricted
i
i     i
Pohlig-Hellman algorithm [41], which costs   e   q  using       TLS specifies ciphersuites supporting multiple varieties of
√
P
cover x using the Chinese remainder theorem. This is the    a ServerHello message (containing a random noncesr).
i
i
log in each subgroup of orderq    dividing q, and then re-    a ciphersuite from the client’s list and signals its selection in
e
use any of the above algorithms to compute the discrete     exchange algorithm and other primitives. The server selects
factorization of the subgroup order q is known, one can     the ClientHello message, where each ciphersuite specifies a key
putation can speed up individual log calculations. If the     list of supported ciphersuites (and a random noncecr) within
x < t   in time  t. These parallelize well [50], and precom-    the crypto algorithms used for the session. The client sends a
√
(sub)group of order q, while Pollard lambda [42] can find      The TLS handshake begins with a negotiation to determine
rithms both take  q time to compute a discrete log in any
√
3.1    TLS and Diffie-Hellman
The baby-step giant-step [45] and Pollard rho [42] algo-
practice and susceptible to attack.                          7.8% of HTTPS servers among Alexa Top Million domains.
§3.5, improperly generated groups are sometimes used in      this attack with our precomputations can compromise about
subgroups have order 2,  q, or 2q. However, as we show in    strength and then recovering the session key. We find that
that p − 1 = 2 q for some primeq, so that the only possible    TLS protocol flaw to downgrade the connection to export-
implementations use “safe” primes, which have the property    server that allows export-grade Diffie-Hellman, by using a
small or has many small prime factors. To avoid this, most  can attack connections between popular browsers and any
are practical even for large primes when the group order is  of them. Next, we show how a man-in-the-middle, so armed,
algorithms runs in time exponential in group order, and they the discrete log for any key-exchange message that uses one
Improperly generated groups  A different family of     512-bit primes on the web, so that we can quickly compute
we perform NFS precomputations for the two most popular
to perform an effective man-in-the-middle attack on TLS.
attack against TLS, which we call the Logjam attack. First,
allows us to quickly compute 512-bit discrete logs in order
In this section, we exploit these facts to construct a novel
step easier. In §3.3, we show how exploiting these tradeoffs
majority of servers use a handful of common groups.
more work in the precomputation makes the final descent
for both normal and export-grade Diffie-Hellman, the vast
a smaller matrix, making linear algebra cheaper, and doing
expense of others. For example, sieving more will result in
flexibility to reduce time on some computational steps at the
92.3% use one of the two most popular primes, shown here.
The numerous parameters of the algorithm allow some
Top 1M HTTPS domains allow DHE_EXPORT, of which
the precomputation in practice.
p
Table 1:Top 512-bit DH primes for TLS.8.4% of Alexa
and later toL (1/ 3, 1. 232) [2], which is much cheaper than
p
improved the complexity of descent toL (1/ 3, 1. 442) [10],
(others )    8%        (463 distinct primes)
mance of the NFS for discrete logs. More recent analyses have
48976f76795094e71e7903529f5a824b
this may have contributed to misconceptions about the perfor-
d6b5145b9f241e5acc31ff090a4bc711
plexity of this step would equal that of the precomputation;
c8157f62d8f33633ee5772f11f05ab22
technical difficulties with descent and reported that the com-  mod_ssl   10%        d4bcd52406f69b35994b88de5db89682
smoothness bound B. Early articles (e.g. [21]) encountered
80a3030c6e4c3757d08f70e6aa871033
sieving region parameter  I, and, most importantly, the                           71fd19d8d8f37c39bf863fd60e3e3006
by tuning many parameters, including the degree off , the                          274cdf1a9f588218fb435316a16e3741
Apache    82%        9fdb8b8a004544f0045f1737d0ba2e0b
exp (1.923 +   o(1))(log p) 1/3  (log log p) 2/3   . This is obtained
                  
p
The running time of this algorithm isL (1/ 3, (64/ 9)1/3  ) =       Source    Popularity   Prime
----------------Page (2) Break----------------
4
Alexa Top 1M HTTPS sites, but modern browsers never     both strong and weak ciphersuites.
efficiently breakDHE_EXPORThandshakes for about 8% of    party uses only strong cryptography but the other supports
the ability to compute discrete logs in 512-bit groups could  preted as a backwards compatibility attack [23] where one
Given the widespread use of these primes, an attacker withthis protocol flaw. More generally, Logjam can also be inter-
ServerKeyExchange message. We expect that TLS 1.3 will fix
3.2    Active Downgrade to Export-Grade DHE
be prevented by additionally signing the ciphersuite in the
about 89,000 servers with browser-trusted certificates.        fused with DHE handshakes [35]. All these attacks could
introduced in version 2.3.0 in 1999. We found it in use by   showed how explicit-curve ECDHE handshakes could be con-
default used forDHE_EXPORTwhen using mod_ssl. It was     called key exchange rollback  [52]. Mavrogiannopoulos et al.
certificates. The second most popular 512-bit prime is the    Schneier and Wagner noted a related vulnerability that they
found it in use by about 564,000 servers with browser-trustedcross-protocol attacks discovered in TLS. As early as SSL 3.0,
was used until 2.4.7, which disabled export ciphersuites. We    Logjam and FREAK both follow the same pattern as other
sions of Apache. Introduced in 2005 with Apache 2.1.5, it    each individual discrete log only takes about a minute.
most popular 512-bit prime was hard-coded into many ver-  indefinitely against all servers that use that group, and since
DHEfollows a similar distribution with longer primes.) The   since the precomputation for each 512-bit group can be used
trusted certificates that supportDHE_EXPORT. (Non-export                 shall see, the cost per compromised connection is far lower,
support DHE_EXPORT, and 92.5% of all servers with browser-             bits.) Logjam affects fewer servers than FREAK, but, as we
bit primes account for 92.3% of Alexa Top 1M domains that to this work, most popular browsers acceptedp of size≥ 512
DHE
one of a handful of primes. As shown in Table 1, just two 512-defense is to reject small primes in   handshakes. (Prior
Diffie-Hellman parameters, the overwhelming majority use    an implementation bug. From a client perspective, the only
While the TLS protocol allows servers to generate their own In contrast, Logjam is due to a protocol flaw in TLS, not
certificates, 23.9% supportedDHEand 4.9% DHE_EXPORT.                 a fresh ephemeral RSA key (typically when it restarts).
Of 14.3 million IPv4 HTTPS servers with browser-trusted    commodity hardware and is usable until the server generates
68.3% supported DHEand 8.4% supported DHE_EXPORT.                 use the same key. The cryptanalysis takes several hours on
539,000 HTTPS sites among Top 1M domains, we found thatfactors the ephemeral key to hijack future connections that
Top 1M domains. The scans took place in March 2015. Of   in several TLS client implementations. The attacker then
both the full public IPv4 address space and the Alexa       export-grade 512-bit ephemeral RSA keys, relying on a bug
and DHE_EXPORTciphersuites and scanned TCP/443 on     downgrades a regular RSA key exchange to one that uses
Hellman, we modified the ZMap [15] toolchain to offerDHEniscent of the recent FREAK [7] attack, in which an attacker
To understand how HTTPS servers in the wild use Diffie- Comparison with previous attacks  Logjam is remi-
DHE_EXPORTciphersuites.
had time to finish. We address these in the next subsections.
safe because most modern TLS clients do not offer or accept
handshake completion until the discrete log computation has
group for legacy DHE_EXPORT. This has been considered
discrete logs in close to real time, and the second is to delay
1024-bit group for regularDHEkey exchanges and a 512-bit
active downgrade attack. The first is to compute individual
TLS servers are still configured with two groups: a strong
There are two remaining challenges in implementing this
servers maintain support for backwards compatibility. Many
read and write application data pretending to be the server.
restrictions are no longer in effect, but many libraries and
to complete the handshake with the client, and then freely
protocol messages are identical toDHE. The relevant export
time can then derive the master secret and connection keys
longer than 512 bits. In all other respects, DHE_EXPORT
stage, but an attacker who can computeb in close to real
DHE_EXPORTciphersuites that were restricted to primes no
client and server have different handshake transcripts at this
sen by the server and proceed with the handshake. The
512
export-grade tuple(p    , g, g   b) as validDHEparameters cho-
the server’s Finished message.
message to the client as is. The client will interpret the
application data that some TLS clients send before receiving
non-export ciphersuite and forwards theServerKeyExchange
read or modify the contents.Datafs refers to False Start [30]
replace the chosenDHE_EXPORTciphersuite with a matching
crete log, the attacker can learn the session key and arbitrarily
instead. The attacker rewrites the ServerHello  response to
that allowsDHE_EXPORT. Then, by finding the 512-bit dis-
the server and remove other ciphersuites that could be chosen
force TLS clients to use export-strength DH with any server
offer a correspondingDHE_EXPORTciphersuite accepted by
Figure 2: The Logjam attack.A man-in-the-middle can
DHE, an active attacker can rewrite the client’s ClientHello to
suite that the server has chosen. Provided that a client offers
message fails to include any indication of the specific cipher-
ciphersuites. Critically, the signed portion of the server’s
message is identical to the message sent during standardDHE
512
message containing a 512-bitp    , but the structure of this
handshake, it proceeds by issuing a signedServerKeyExchange
DHE_EXPORT. When a server selects             DHE_EXPORTfor a
and relies on a flaw in the way TLS composes DHEand
The attack, which we call Logjam, is depicted in Figure 2
confidentiality and integrity of application data.
to use aDHE_EXPORTgroup, and thereby break both the
logs in real time  can downgrade a regularDHEconnection
show how an attacker who can compute 512-bit discrete
negotiate export-grade ciphersuites. To circumvent this, we
----------------Page (3) Break----------------
5
of Amazon EC2c4.8xlarge instances.                       Microsoft IIS does not support 512-bit export ciphersuites.
descent, and about three hours parallelized across 1,800 cores ever, forDHE_EXPORT, only 0.1% reused            gb, likely because
eight days of wall-clock time on the computer used for the  of 20 handshakes, and that 15% only used one value. How-
ization using the CADO-NFS implementation takes about    we found that 17% reusedgb at least once over the course
For purposes of comparison, a single 512-bit RSA factor-   hosts serving browser-trusted certificates that supportDHE,
sieving—should bring the median time well below a minute.    to do the computation online. By randomly sampling IPv4
effective parallelization on the middle phase or additional    tion and use it to attack later handshakes, avoiding the need
on the middle phase. Further optimizations—such as more     attacker can compute the discrete log ofgb from one connec-
about 20 seconds for descent initialization and the remainder two hours—this setting is hard-coded. For these servers, an
from 34 to 206 seconds (see Fig. 3). This is divided between DH” option is checked [53]. Microsoft Schannel cachesgb for
individual logs took about 70 seconds, but the time varied   and hardware TLS frontends will reusegb unless the “Single
E5-2699 CPUs and 128 GB of RAM. On average, computing such as stud [48], do not. The F5 BIG-IP load balancers
We ran the server on a machine with two 18-core Intel XeonNginx internally apply this option, certain load balancers,
sieving in C, and the final discrete log is deduced in Python.for the lifetime of a TLS context. While both Apache and
and C. The first and second stages are parallelized and run  the SSL_OP_SINGLE_DH_USE option, OpenSSL will reuse gb
We implemented the descent calculation in a mix of Pythononce and reuse it for multiple negotiations. Without enabling
in RAM and returns logs for values passed to it by clients.  fresh value b for each connection, but instead computegb
saging library. The server maintains the precomputed data   Ephemeral key caching.    Many TLS servers do not use a
mented a client-server architecture using the ZeroMQ mes-
background resource that does not delay rendering the page.
In order to save time on individual computations, we imple-
the attacker might choose to compromise a request for a
crete logs in about a minute for targets in each of these groups.
the victim connection still takes much longer than usual,
able to run the final descent step to compute individual dis-
we tested close the connection after a minute.) Although
Descent  Once this precomputation was finished, we were
Firefox’s TLS connections alive indefinitely. (Other browsers
reset the handshake timer. For example, this allows us to keep
logs for the descent occupies about 2.5 GB in ASCII format.
TLS warning alerts, which are ignored by the browser but
slightly over one week. Each resulting database of known
timeouts, but we can keep their connections alive by sending
In total, the wall-clock time for each precomputation was
TLS warning alerts.    Web browsers tend to have shorter
at least a factor of three.
We expect that optimizations could bring this cost down by
we can hijack their connections without difficulty.
finished in 120 hours, corresponding to 60,000 core-hours.
often run unattended, so they have long or no timeouts, and
NFS [1] for linear algebra over GF(p), the computation
connection.  Command-line clients such as curl and git
n = 6. Using the unoptimized implementation from CADO-
time limits for the handshake, after which they kill the
Wiedemann algorithm [11,49] with parametersm = 18 and
Non-browser clients.  Different TLS clients impose different
per node, connected with Infiniband FDR. We used the block
are several ways an attacker can work around this delay:
a 36-node cluster with two 8-core Intel Xeon E5-2650 CPUs
the computation takes an average of 70 seconds, but there
row on average. We solved the corresponding linear system on
message from the server. With our descent implementation,
2,157,378 rows and columns, with 113 nonzero coefficients per
before the handshake completes in order to forge aFinished
From this data set, we obtained a square matrix with
The main challenge is to compute the shared secretgab
of at most 27 bits (hence boundB from §2 is 227).
connection towards the client by impersonating the server.
which 28,372,442 were unique, involving 15,207,865 primes
the server, computes the session keys, and takes over the
core-hours. This sufficed to collect 40,003,519 relations of
sequence in Figure 2: it downgrades the connection towards
hours. Sieving ran for 15 hours, corresponding to 21,400
bit Apache group. Our implementation follows the message
for about 3 hours, which in total corresponds to 7,600 core-
that supportsDHE_EXPORTand uses the most common 512-
CPUs were Intel Sandy Bridge. Polynomial selection ran
that sits between a TLS client (web browser) and any server
idle time on 2000–3000 CPU cores in parallel, of which most
We implemented a man-in-the-middle network attacker
For the polynomial selection and sieving steps, we used
sieving is much easier to parallelize than linear algebra.
3.4    Active Attack Implementation
yield a smaller linear algebra step, which is desirable because
makes the descent faster. Second, more sieving relations also
we eventually obtain a larger database of known logs, which computing 3,500 individual logs; the median is 70 seconds.
mizations: first, with more relations obtained from sieving,   any key exchange that uses them. Here we show times for
sieved more than strictly necessary. This enabled two opti-   export-grade primes (see Table 1), we can quickly break
linear algebra steps. For this precomputation, we deliberately After a week-long precomputation for each of the two top
putation phase includes the polynomial selection, sieving, and         Individual discrete log time for 512-bit DH.
Figure 3:
Precomputation  As illustrated in Figure 1, the precom-
Seconds
below. The times were about the same for each prime.
30       60       90      120      150
onds. We list the runtime for each stage of the computation
CDF
after which computing individual logs took a median of 70 sec-     0
shown in Table 1. Precomputation took 7 days for each prime,
of keys
512-bit primes, including the top twoDHE_EXPORTprimes
0.5
sieve discrete log algorithm from §2 and applied it to three
We modified CADO-NFS [1] to implement the number field
1
3.3    512-bit Discrete Log Computations
----------------Page (4) Break----------------
6
as hypothetical by van Oorschot and Wiener [51].           a generator leaks 290 bits of information about exponents at
to recoverx in time   x/z  . This attack was first described    For Java’ssun.security.provider 512-bit prime, usingq as
p                      generated according to [38],(p − 1)/q   is a random integer.
recover x. If not, Pollard lambda can use this information
i
i     i
to have many small prime factors in its order, since forp
recover x  mod z in time   e   q . If x ≤ z, this suffices to
1      k                 i  i√
P                    In a DSA group, the subgroup generated by q is likely
1       k                    i
factors {q     . . . q       } with    q    = z, Pohlig-Hellman cane
e                    e
Q                   these formats led to a simple programming error.
to recover information about exponents. From a subset of
PKIX) is(p, q, g   ); we conjecture that the confusion between
subgroup generated byg has small factors, they can be used
quence (p, g ), while that of DSA parameters (coming from
be the Pollard lambda algorithm. But if the order of the
key exchange parameters (coming from PKCS#3) is a se-
known to decrease security, as the most efficient attack will
lem: the canonical ASN.1 representation of Diffie-Hellman
2048-bit group. For safe p, such exponent lengths are not
This substitution ofq for g is likely due to a usability prob-
bits, intended to match the estimated strength of a 1024- or
this way.
x; commonly suggested sizes forx are as small as 160 or 224
place of the generatorg. We found 5,741 hosts misconfigured
implementations use ephemeral keysgx with a short exponent
primes asp but mistakenly used the DSA group orderq in the
primes can lead to an attack. For efficiency reasons, some
servers. However, some servers in our scans used Java’s DSA
In some real-life configurations, however, choosing such
package and are used by default in many Java-based TLS
the Pohlig-Hellman algorithm as an attack.
groups are hard-coded in Java’s  sun.security.provider
with at least one sufficiently large subgroup order to rule out
secure for use in Diffie-Hellman key exchanges. Notably, DSA
are not necessarily vulnerable, as long asg generates a group
using properly generated DSA parameters, these groups are
(Incidentally, we also found 9 compositep.) These groups
factor q and g generates only a subgroup of orderq. When
4,800 were not safe, meaning that(p − 1)/ 2 was composite.
(DSA) [38] uses primesp such that p − 1 has a large prime
primes seen across both export and non-export TLS scans,
Misconfigured groups  The Digital Signature Algorithm
uses “safe” primes. Out of approximately 70,000 distinct
can result in devastating attacks.  Not every TLS server
with a delay hardly noticeable for browser users.
generate Diffie-Hellman primes according to best practices
to an attack using NFS, we could compute the discrete log
Attacks on composite-order subgroups   Failure to
vulnerable server and capture user credentials. Compared
our man-in-the-middle attacker of §3.3 to impersonate a
computation. The website no longer supportsDHE.
FTP servers (6 hosts). As a proof-of-concept, we modified
was the third group for which we performed the NFS pre-
software (21 hosts), web conferencing servers (27 hosts), and
used the default 512-bit DH group from OpenSSL, which
web interfaces for VPN devices (48 hosts), communications
test connections to www.fbi.gov. Until April 2015, this server
nections to a variety of vulnerable TLS servers, including
dropper for regularDHEconnections and used it to decrypt
Our computations would have allowed us to hijack con-
As a proof-of-concept, we implemented a passive eaves-
calculations used interval width varying from 40 to 70 bits.
choose a vulnerableDHEciphersuite.
50 and 176 hours) implementation.  The Pollard lambda
downgrade attack, an active attacker can force the server to
(which finishes in seconds) to 81 bits (which took between
server not selectingDHE. In this case, as in the DHE_EXPORT
The order of the largest-order subgroup ranged from 46 bits
when the client’s ordering of ciphersuites would result in the
of them used 160-bit exponents and the rest used 128 bits.
for the connection. An active attack may still be necessary
cases, the vulnerable hosts used 512-bit prime moduli; three
compute the discrete log and obtain the TLS session keys
authenticated with valid browser-trusted certificates. In all
with one of these servers, apassive eavesdropper can later
the whole exponent used by 159 different hosts, 53 of which
be unnecessary. If a browser negotiates aDHEciphersuite
exponent used in 460 exchanges and were able to recover
non-export DHE.  In these instances, active attacks may
We computed partial information about the server secret
Top 1M domains) that used 512-bit or weaker primes for
precomputing a table of distinguished points.
servers with browser-trusted certificates (and 118 in the
advance, this implementation can be arbitrarily sped up by
512-bit primes in non-export DHEWe found 2,631
points method for collision detection; for a prime known in
issues in the DHE configurations used by TLS servers.
wrote in C using the GMP library. We used the distinguished
In our scans, we found several other exploitable security
Sage [47] using a parallel Pollard rho implementation that we
We implemented the van Oorschot and Wiener algorithm in
3.5    Other Weak and Misconfigured Groups
connections across all of our scans.
information, such as passwords and cookies.                 the subgroup generated byg; these had been used for 40,903
sent by a browser often contains sensitive user authenticationbits. There were 753(p, g ) pairs where we knew factors of
False Start payload at leisure. We note that this initial data a target private exponentx of length ranging from64 to 256
man-in-the-middle can record the handshake and decrypt the required using Pohlig-Hellman and Pollard lambda to recover
dows 10) send False Start data withDHE. In these cases, a        of the order ofg, and ordered them by the estimated work
versions. Firefox 35, Chrome 41, and Internet Explorer (Win- if the prime factorization ofp − 1 had revealed prime factors
Start, but their policies on when to enable it vary between  We classified a tuple(p, g, y   ) sent by a server as interesting
of Chrome, Internet Explorer, and Firefox implement False     We then examined the generatorsg used with each primep.
for the server’s Finished  message to arrive. Recent versions    across 28 cores and discovered 36,447 prime factors.
application data (such as an HTTP request) without waiting and the ECM factoring methods [54] for 5 days parallelized
reduces connection latency by having the client send early   GMP-ECM implementations of the Pollardp − 1 algorithm
supports the TLS False Start extension [30]. This extension  p − 1 using Bernstein’s batch method [5]. We then ran the
still break the confidentiality of user requests if the client    For each non-safe prime p, we opportunistically factored
outs and servers do not reuse values forb, the attacker can    attack, we tested various non-safe primes found in our scans.
TLS False Start.    Even when clients enforce shorter time-      To see if TLS servers in the wild were vulnerable to this
----------------Page (5) Break----------------
7
our own experiments, but further work is needed for greater parameters in [29].
We would lower the smoothness bounds compared to the
1024-bit discrete log based on the existing literature and     3
asymptotic complexity.) We attempt estimates for 768- and
formula is inherently imprecise, since theo(1) in the expo-
many published estimates are crude extrapolations of the
discrete log, and k is an algorithm-specific constant. This
gone to understanding 1024-bit factorization, but, even there,
where N is the integer to factor or the prime modulus for
computational characteristics. (Much more attention has
the complexity is exp (k + o(1))(log N )1/3  (log log N )2/3   ,
sieving and linear algebra steps, which have very different
                 

ing from asymptotic complexity. For the number field sieve,
complexity of parameter tuning and to tradeoffs between the
Without better parameter choices, we resort to extrapolat-
key sizes is far from straightforward, due in part to the
relevant parameter choices.
Estimating the cost for discrete log cryptanalysis at longer
experimentally update the estimates of this paper with more
4.1    Scaling NFS to 768- and 1024-bit DH
with values of I larger than those proposed, we could not
task. Since no publicly available software can currently deal
access to VPN, SSH, and TLS traffic.
too small, giving too few smooth results per sieving sub-
on unanswered questions about how NSA may be gaining
proposed value of the sieving region parameterI is clearly
or AES. We believe that this analysis may help shed light
thin: [28] proposes smoothness bounds of 42 bits, but the
other proposed explanations, such as novel breaks on RC4
proposing parameters for factoring a 1024-bit RSA key is
indeed, matches the known capabilities more closely than
algorithm and their relative parallelism.  The prior work
the intelligence community’s cryptanalytic capabilities, and,
case is difficult due to the tradeoffs between the steps of the
this hypothesis is consistent with the published details of
perimentally extrapolating sieving parameters to the 1024-bit
has already implemented such a capability. We show that
DH-1024: Plausible with state-level resources  Ex-
to evaluate the hypothesis that the National Security Agency
cently published documents leaked by Edward Snowden [46]  and is easily parallelizable.
Finally, we apply this new understanding to a set of re-   single 768-bit discrete log computation is around 2 core-days
have long been embedded in standards and implementations. 1 core-day. In total, after precomputation, the cost of a
to sunset the use of fixed 1024-bit Diffie-Hellman groups thatexperiments, the rest of the descent should take at most
our measurements also indicate that it may be very difficult sieving much as in the precomputation; extrapolating from
the most common Diffie-Hellman parameters. Unfortunately,  an average of around 1 core-day. The remaining phase uses
used to attack millions of hosts, due to widespread reuse of  in [6]. Using these techniques, the initial descent phase took
of equal size, we observe that a one-time investment could bewith GMP-ECM based on the early-abort strategy described
1024-bit group is several times higher than for an RSA key  mented with both CADO-NFS and a new implementation
ful attackers. Although the cost of the precomputation for a   The descent step takes relatively little time. We experi-
the vulnerability of their key exchanges to attacks by resource-reach by computing power available to academics.
net security protocols—IKE, SSH, and TLS—to determine        core-years, for a total of 36,500 core-years. This is within
In light of these results, we examine several standard Inter-existing software that this linear algebra would take 28,500
close to real time.                                         around 150M rows. We extrapolate from experiments with
would be fast enough to break individual key exchanges in   much sieving as the RSA case would reduce the matrix to
any specific discrete log instance within a common group—      For a 768-bit discrete log, we can expect that ten times as
in the 1024-bit case, the descent time—necessary to solve      RSA-768 integer would take 900 core-years in total.
known in the academic literature. We further show that evenoptimizing for the total time,we estimate that factoring an
3
require any major algorithmic improvements beyond what is  ing algorithmic improvements since 2009 into account and
would likely require special-purpose hardware, but would not As a result, the linear algebra took 150 core-years, but tak-
the resources of state-level attackers. The precomputation    the matrix that was produced had 200M rows and columns.
for a small number of 1024-bit groups is plausibly within    step. The cost of sieving was around 1500 core-years, and
computational resources, and performing precomputations     time on sieving in order to save time on the linear algebra
relatively widespread use, are now within reach for academic   Similarly, the 768-bit RSA factoring record spent more
groups. As we argue below, 768-bit groups, which are still in our 512-bit experiments in §3.3.
number field sieve for discrete log scales to 768- and 1024-bitcalculation to 80 core-years. We used this same strategy in
To answer this question we must first examine how the   50 core-years on sieving. This reduced their linear algebra
and when applied with stronger groups?                    discrete log effort tuned parameters such that they spent
as used in other protocols that do not suffer from downgrade,of it spent on sieving. In comparison, the record 596-bit
question: how secure is Diffie-Hellman in broader practice,     A 596-bit factorization takes about 5 core-years, most
of unsafe parameters. In this section we address the followingalgebra, this tradeoff is desirable for large inputs.
downgrade connections to export-grade crypto or on the use  algebra step. Since sieving parallelizes better than linear
used by TLS. However, these attacks rely on the ability to  more, thus generating a smaller input matrix to the linear
cal attacks against Diffie-Hellman key exchange as currently  no longer Boolean. We can reduce overall time by sieving
The previous sections demonstrate the existence of practi-  stage is many times more difficult, as the matrix entries are
and discrete log are similar, the discrete log linear algebra
4.    STATE-LEVEL THREATS TO DH
768 bits from 2009 [29]. While the algorithms for factorization
record at 596 bits [8] and the integer factorization record of
and serves as a cautionary tale for programmers.
bit case, we base our estimates on the recent discrete log
misconfiguration bug results in a significant loss of security
DH-768: Feasible with academic power For the 768-
this does not suffice to recover a full exponent. Still, this
generates exponents of length max(n/ 2, 384) for n-bit p,     all the costs, measured or estimated, in Table 2.
a cost of roughly240 operations. Luckily, since the provider    confidence, particularly for the 1024-bit case. We summarize
----------------Page (6) Break----------------
8
the dies from the 130 nm technology node used in the paper to4The National Science Foundation’s budget was $7 billion.
mate of 3M chips to complete sieving in one year. Shrinking
encryption for widely used VPN protocols?
sieve more and save on linear algebra as above, giving an esti-
by the Edward Snowden leaks: How is NSA defeating the
discrete log. We increase their chip count by a factor of ten to
would answer one of the major cryptographic questions raised
estimates for modern techniques and adjust parameters for
made with those groups in close to real time. If true, this
mann and Steinwandt [18]. In the following, we update their
groups. This would allow them to break any key exchanges
implementation of 1024-bit sieving is the 2007 work of Geisel-
tions for at least a small number of 1024-bit Diffie-Hellman
To our knowledge, the best prior description of an ASIC
resources to have performed number field sieve precomputa-
Sieving is a natural target for hardware implementation.
Our calculations suggest that it is plausibly within NSA’s
could be realized by developing application-specific hardware.
nation state. Moreover, at this scale, significant cost savings
4.2    Is NSA Breaking 1024-bit DH?
computational effort, it is not necessarily out of reach for a
Costs in hardware  Although 45M core-years is a huge    cryptanalytic capability for the nation” [63].
art for high performance computing to maintain pre-eminent
again easily parallelizable.                                  to invest in the industrial base and drive the state of the
that a 1024-bit descent would take about 30 core-days, once leaked strategic plan for the period called for it to “continue
proper sieving software were available. Thus we estimate     ysis and exploitation services program C” (to $360M). NSA’s
down to the smoothness bound in a few more core-days if   IT services” (to $247M), and a cryptically named “cryptanal-
certain to have bootstrapped the descent, and could continue notable $100M increases in two programs [57]: “cryptanalytic
we reached primes of about 110 bits. At this point, we were versarial cryptography and exploit internet traffic,” included
most 130 bits to be descended further. In twice this time,   in “groundbreaking cryptanalytic capabilities to defeat ad-
initialization took 22 core-days, yielding a few primes of at   classified 2013 budget request, which prioritized investment
log computation. For a random target in Oakley Group 2,   includes the NSA) was $10.5 billion4 [57].  The agency’s
initialization, which should dominate the individual discrete  get for the U.S. Consolidated Cryptologic Program (which
abort implementation to inform our estimates for descent      To put this dollar figure in context, the FY2012 bud-
For 1024-bit descent, we experimented with our early-     plausibly on the order of hundreds of millions of dollars.
compared to the other steps.                               to perform the linear algebra for DH-1024 in one year is
step has been far less studied both in theory and in practice reduction can be achieved for discrete log, the hardware cost
in practice; we attribute that to the fact that the descent   factor of 80 [17]. If we optimistically assume that a similar
This last number does not correspond to what we observed  CPUs to ASICs has been estimated to reduce costs by a
log after the precomputation should be multiplied by 95.     of factorization, moving linear algebra from general purpose
45M core-years. The time complexity for each individual     in supercomputers to finish this step in a year. In the context
DH-1024, we get a total cost for the precomputation of aboutwas constructed in 2012 for $94M, suggesting a cost of $11B
since they have the same asymptotic behavior. Hence, for    117 years to complete the 1024-bit linear algebra stage. Titan
35. These are valid for both factorization and discrete log,   the most powerful supercomputer in the U.S.—would take
of 1220, while space complexity will increase by a factor of  Titan supercomputer [39]—at 300,000 CPU cores, currently
tation, the total time complexity will increase by a factor    hardware and the core-year estimate from Table 2.  The
increase from the 768- to the 1024-bit case. For precompu-  To derive a rough estimate, we can begin with general purpose
estimated multiplicative factors by which time and space will that are suitable for the larger fields involved in discrete log.
Evaluating the formula for 768- and 1024-bitN gives us     difficult, since there has been little work on designing chips
strategy similar to the one in [6] mentioned above.            Estimating the financial cost for the linear algebra is more
well; [2, Chapter 4] gives k = 1 . 232, using an early-abort        likely be reused to speed calculations of individual logs.
Discrete log descent has a complexity of the same form as   Since a step of descent uses sieving, the same hardware could
of this function, i.e., the same function, takingk = 0 . 9615.     to complete the DH-1024 sieving precomputation in one year.
plexity (the size of the matrix in memory) is the square root suggests that an $8M investment would buy enough ASICs
and linear algebra in the precomputation. The space com-   ter fixed design and tape-out costs of roughly $2M [32]. This
log and factorization, which are both dominated by sieving   lization, this would cost about $2 per chip to manufacture, af-
with k = 1 . 923, describes the overall time for both discrete      at newer technologies. With standard transistor costs and uti-
nent can hide polynomial factors. This complexity formula,   a more modern size reduces costs, as transistors are cheaper
DSA primes withq of 160 bits, this should be divided by 6.4 for 1024 bits, 4.8 for 768 bits, and 3.2 for 512 bits.
bits of the smoothness boundB and the sieving region parameterI. For linear algebra, all costs for DH are for safe primes; for
Table 2:Estimating costs for factoring and discrete log. For sieving, we give two important parameters: the number of
DH-1024   19      40   10,000,000   5.2B   35,000,000    30days    Est. based on complexity formula and our experiments.
RSA-1024   18      42    1,000,000   8.7B     120,000               Est. based on complexity formula.
DH-768   17      35       8,000   150M      28,500     2days    Est. based on [8,29] and our own experiments.
RSA-768   16      37         800   250M         100             Est. based on [29] with less sieving.
DH-512   15      27         2.5   2.1M         7.7    10mins     For the computations in this paper; may be suboptimal.
RSA-512   14      29         0.5   4.3M        0.33               Timings with default CADO-NFS parameters.
2
I   log B     core-years   rows   core-years   core-time
Sieving            Linear Algebra     Descent
----------------Page (7) Break----------------
9
scale, with a target of 100,000 per hour [64].                ware “implants” on VPN devices, indicating that the use of
documents indicate that NSA is recovering ESP keys at largemeans.  Certain published NSA documents refer to soft-
passed to other systems for storage and analysis [69]. The   bility remains that NSA could defeat IPsec using alternative
is reinjected into TURMOIL processing infrastructure and      Of course, this explanation is not dispositive. The possi-
in software [68,69]. From this point, decrypted VPN traffic  “[r]un attacks to recover PSK” [60].
ESP traffic is decrypted via hardware accelerators [59] or    administrator “chatter” [70]. Additionally, NSA is willing to
were generated correctly. Once keys have been returned, the PSKs [60], previously decrypted SSH traffic [60], or system
until CES can respond with the recovered ESP keys if they  figurations [70,71], the CORALREEF database of known
The ESP traffic itself is buffered for up to 15 minutes [64],to locate a PSK, including using a database of router con-
resulting “recovered” ESP session keys [60,61,67].              PSK. Several documents describe techniques for analysts
tographic values, including a set of known PSKs and the      The attack system also seems to require knowledge of the
also maintains a database, CORALREEF, that stores cryp-  traverses multiple network paths [55,56,58,66].
required to generate the ESP session key [61,62,67]. VAO    must be reassembled (“paired”) whenever the interaction
Ridge National Laboratory, which perform the computation   complexity of the attack execution, since IKE transcripts
located at NSA Headquarters and in a data center at Oak   indicate that this requirement substantially increases the
a collection of high-performance grid computing resources    two-sided IKE transcript [60]. The published documents
specialized VPN Attack Orchestrator (VAO) system manages requirement of the VAO is the need to obtain thecomplete
Services (CES) [56,65] via a secure tunnel. Within CES, a   NSA’s VPN attack system. As Figure 4 illustrates, a hard
of ESP ciphertext to NSA’s Cryptanalysis and Exploitation     Both of the above requirements are also present in the
complete IKE handshake and may transmit a small amount  used in derivingSKEYID.
any tasked selector [65]. If so, TURMOIL transmits the      both sides of the connection, and(2) in IKEv1 only, the PSK
ESP payloads and determining whether the traffic matches   ga and gb as well as the nonces and cookies transmitted by
The initial phases of the attack involve collecting IKE and IKE transcript, including the Diffie-Hellman ephemeral keys
of information through the TURMOIL system               attacker can obtain the following:(1) a complete two-sided
excerpt from one of the documents [67], illustrates the flow  problem, attacks on IKE are possible provided that the
man-in-the-middle attacks on IPsec or IKE. Figure 4, an       Given an efficient oracle for solving the discrete logarithm
eavesdropping and does not require message injection or     group, Oakley Group 2, even when offered stronger groups.
indicates that this decryption is performed using passive     majority of IKE systems select one particular 1024-bit DH
that is used to collect and decrypt VPN traffic. The evidencegroups, our Internet-wide scans (§4.3) show that the vast
lished by Der Spiegel describe a system named TURMOIL     While IKE is designed to support a range of Diffie-Hellman
NSA’s VPN exploitation process The documents pub-   passively observing an IKE handshake.
the attacker to recover a Diffie-Hellman shared secret after
the optional Phase 2 Diffie-Hellman exchange.
derivation function or transport encryption, this requires
derived from SKEYID, additional nonces, and the result of
by the Phase 1 exchange. Absent a vulnerability in the key
additional round of Diffie-Hellman. Ultimately,KEYMATis
attacker must at minimum recover theSKEYIDgenerated
(AH) [26]. In some circumstances, this phase includes an
recover the session keys for the ESP or AH protocols, the
lating Security Payload (ESP) [27] or Authenticated Header
rations under passive eavesdropping attacks. In order to
protocol used to protect subsequent traffic, such as Encapsu-
and is not believed to be exploitable in standard configu-
and key material, KEYMAT, for a cryptographic transport
The IKE protocol has been extensively analyzed [9,36],
a Phase 2 handshake. Phase 2 establishes the parameters
VAO’s operation that support this hypothesis.
The resultingSKEYIDis used to encrypt and authenticate
of Diffie-Hellman, there are several features of IKE and the
the derivation ofSKEYID.
to decrypt VPN traffic does not by itself indicate a defeat
authenticated with a PSK, this value is incorporated into
Evidence for a discrete log attack While the ability
including symmetric pre-shared keys (PSK); when IKEv1 is
SKEYID. IKE provides several authentication mechanisms,
side, such as nonces and cookies, to derive a value called
consistent with an efficient break for 1024-bit Diffie-Hellman.
is combined with other cleartext values transmitted by each
keys for ESP session traffic. The details of this attack are
key exchange to establish a shared secret. The shared secret
performance computing system, which returns the symmetric
from a small set of standardized parameters and perform a
captured IKE handshake messages being passed to a high-
which the client and server select a Diffie-Hellman group
classified illustration published by Der Spiegel [67] shows
Each IKE session begins with a Phase 1 handshake, in
Figure 4:NSA’s VPN decryption infrastructure.This
brevity, we will use IKEv1 terminology.
sage structure but are conceptually similar. For the sake of
versions, IKEv1 [22] and IKEv2 [25], which differ in mes-
tablishment protocol used for IPsec VPNs. There are two
IKE  Internet Key Exchange (IKE) is the main key es-
precomputation to calculate discrete logs at scale.
tion to evaluate the hypothesis that the NSA is leveraging
key establishment works, we will use the published informa-
the attack system architecture. After reviewing how IPsec
analytic techniques used, but they do provide an overview of
significant scale. The documents do not describe the crypt-
cate that NSA is passively decrypting IPsec connections at
Classified documents published by Der Spiegel [46] indi-
----------------Page (8) Break----------------
10
preferred the 1024-bit Oakley Group 2. For IKEv2, 5.8%     primes; 17.9% of connections with Top 1M sites could be
reach today for moderately resourced attackers—and 66.1%     will negotiateDHEwith one of the ten most popular 1024-bit
the 768-bit Oakley Group 1—which is within cryptanalytic     enabled Top 1M sites (and 10% with browser-trusted sites)
sample of IKEv1 servers, 2.6% of profiled servers preferred     Approximately 24.0% of browser connections with HTTPS-
respectively supported Oakley Group 2 (1024-bit). In our     negligible differences in whetherDHEis chosen.
support Oakley Group 1 (768-bit) while 86.1% and 91.0%    differ slightly between browsers, this turns out to result in
We found that 31.8% of IKEv1 and 19.7% of IKEv2 serversas Chrome, Firefox, and Safari. While the offered ciphers
omit them from the results here.                           which this will occur by offering the same sets of ciphersuites
our source address. We consider these hosts “unprofiled” and   use Diffie-Hellman. We can estimate the number of sites for
posal. Many of these may be site-to-site VPNs that reject   per can only decrypt connections that organically agree to
with a NO-PROPOSAL-CHOSEN message regardless of our pro-      Despite widespread support forDHE, a passive eavesdrop-
one scan. The majority of the remaining hosts responded     of these using one of five groups.
44.2% were willing to accept an offered proposal from at leastsupport DHE, 84% use a 1024-bit or smaller group, with 94%
Of the 80K hosts that responded with a valid IKE packet, with browser-trusted certificates. Of the Top 1M sites that
prefer Oakley Groups 1 and 2.                             of Alexa Top 1M sites supportDHE, as do 23.9% of sites
and IKEv2 are a lower bound for the number of servers thatHTTPS  DHEis commonly deployed on web servers. 68.3%
scans. Because of this, the percentages we present for IKEv1
to 3.6M (25.7%) publicly accessible SSH servers.
commonly supported symmetric cipher in our single group
almost two decades) could passively eavesdrop on connections
we scanned with the 3DES symmetric cipher—the most
1024-bit Oakley Group 2 (which has been in standards for
Oakley Groups 1 and 2. When measuring server preference,
level attacker who performed NFS precomputations for the
variety of DH groups, with the lowest priority groups being
Combining these equivalent choices, we find that a state-
question. To detect default behavior, we offered servers a
all provided Oakley Group 2 rather than a custom group.
for individual groups, we offered only the single group in
the server-defined groups were 1024-bit, but, of those, near
groups) and which group servers prefer. To test support
Group 2, and 37.4% preferred a server-defined group. 10% of
Groups 1 and 2 (two popular 768- and 1024-bit, built-in
In this scan, 21.8% of servers preferred the 1024-bit Oakley
the ZMap UDP probe module to measure support for Oakley
offered by OpenSSH 6.6.1p1, the latest version of OpenSSH.
initiate an IPsec VPN connection) in May 2015. We used
we performed a scan in which we mimicked the algorithms
address space for IKEv1 and IKEv2 (the protocols used to
rithm servers will prefer in practice. In order to estimate this,
practice by scanning a 1% random sample of the public IPv4
algorithm. Therefore, we cannot directly measure what algo-
IKE  We measured how IPsec VPNs use Diffie-Hellman in
client’s highest priority mutually supported key exchange
for a small number of common 1024-bit groups.               During the SSH handshake, the client and server select the
attacker who had the resources to invest in precomputation  Oakley Group 14, and 68.7% support DH-GEX.
would be subject to widespread compromise by a state-level  the 1024-bit Oakley Group 2, 77.6% support the 2048-bit
indicate that these protocols, as they are commonly used,    in April 2015. We find that 98.9% of SSH servers support
lar protocols: IKE, SSH, and HTTPS. Our measurements    scanned 1% random samples of the public IPv4 address space
the impact of a hypothetical DH-1024 break on three popu-  implemented the SSH protocol in the ZMap toolchain and
In this section, we use Internet-wide scanning to assess      In order to measure how SSH uses DH in practice, we
Group Exchange (DH-GEX) handshake [16].
4.3    Effects of a 1024-bit Break
which can be negotiated through an auxiliary Diffie-Hellman
Group 14 (2048-bit) but also allows a server-defined group,
non-compromised devices.
defines support for Oakley Group 2 (1024-bit) and Oakley
approach, which appears to succeed across a broad swath of
part of the SSH key exchange. The SSH protocol explicitly
a pure cryptographic attack is the generality of the VAO
Diffie-Hellman or elliptic curve Diffie-Hellman exchange as
attack described above. The most compelling argument for
SSH  All SSH handshakes complete either a finite field
thus appears to be an alternative mechanism to the VAO
the resulting trafficdoes not require IKE handshakes, and     that most VPN clients only offer Oakley Group 2 by default.
however, the same documents also note that decryption of   Oakley Group 2. This coincides with our anecdotal findings
targeted malware is a piece of the collection strategy [60];   of profiled servers chose Oakley Group 1, and 63.9% chose
For HTTPS, we provide figures with and without downgrade attacks on the chosen ciphersuite. All others are passive attacks.
world servers for which typical connections could be compromised by attackers with various levels of computational resources.
Table 3: Estimated impact of Diffie-Hellman attacks.We use Internet-wide scanning to estimate the number of real-
SSH IPv4                                             –                  –   3,600,000 (25.7%)    3,600,000 (25.7%)
IKEv2 IPv4                                           –      66,000 (5.8%)     726,000 (63.9%)      726,000 (63.9%)
IKEv1 IPv4                                           –      64,700 (2.6%)   1,690,000 (66.1%)    1,690,000 (66.1%)
HTTPS Trusted                             1,000 (0.0%)      46,700 (0.3%)     939,000 (6.56%)    1,430,000 (10.0%)
HTTPS Trusted w/ active downgrade         489,000 (3.4%)     556,000 (3.9%)   1,840,000 (12.8%)    3,410,000 (23.8%)
HTTPS Top 1M                               118 (0.0%)        407 (0.1%)      98,500 (17.9%)      132,000 (24.0%)
HTTPS Top 1M w/ active downgrade        45,100 (8.4%)      45,100 (8.4%)     205,000 (37.1%)      309,000 (56.1%)
all 512-bit groups   all 768-bit groups   one 1024-bit group   ten 1024-bit groups
Vulnerable servers, if the attacker can precompute for ...
----------------Page (9) Break----------------
11
sources.                                                  known to cryptographers, it apparently has not been widely
sidered secure, even against an attacker with moderate re-   that group has a far lower cost. Although this fact is well
groups. Primes of less than 1024 bits should not be con-     only on the group, after which computing individual logs in
tacks when communicating with servers that still use smaller attacker to perform a single precomputation that depends
groups to at least 1024 bits in order to avoid downgrade at- the fact that the number field sieve for discrete log allows an
should raise the minimum accepted size for Diffie-Hellman    less secure than widely believed. The problems stem from
to use primes of 2048 bits or larger. Browsers and clients    cryptography, but we find that, as used in practice, it is often
should disableDHE_EXPORTand configureDHEciphersuites       Diffie-Hellman key exchange is a cornerstone of applied
Increase minimum key strengths.  Server operators
7.    CONCLUSION
vulnerabilities described in this paper.
possible; this is the most effective long-term solution to the
2048-bits and higher and to gracefully reject weak ones [19].
cols. We recommend transitioning to elliptic curves where
clients and servers to negotiate a few well-known groups of
being standardized by the IRTF for use in Internet proto-
TLS developers plan to support a new extension that allows
going scrutiny, and new curves, such as Curve25519, are
mai has removed all support for export ciphersuites. Many
known or suspected weaknesses. These curves are under-
Oracle, IBM, Cisco, and various hosting providers. Aka-
suspicion due to NSA influence on their design, despite no
pected to follow suit. On the server side, we notified Apache,
parameters, those specified by NIST, are now viewed with
they accept to 1024 bits, and OpenSSL and Safari are ex-
are faster. Unfortunately, the most widely supported ECDH                                            DHE
Chrome are transitioning the minimum size of thegroups
in “mod p” Diffie-Hellman, and shared-secret computations
result of our disclosures, Internet Explorer [37], Firefox, and
precomputation. In addition, ECDH keys are shorter than
whereas Safari allowed groups as small as 16 bits.  As a
strong curves do not gain as much of an advantage from
Chrome, Firefox, and Opera all accepted 512-bit primes,
attacks. Current elliptic curve discrete log algorithms for
our findings public. Prior to our work, Internet Explorer,
priate parameters avoids all known feasible cryptanalytic
the vulnerabilities discussed in this paper before we made
tic curve Diffie-Hellman (ECDH) key exchange with appro-
We notified major client and server developers about
Transition to elliptic curves.  Transitioning to ellip-
6.    DISCLOSURE AND RESPONSE
mainstream Internet protocols.
cover the expected security of Diffie-Hellman as it is used in
deliberately weakening cryptography.
In this section, we present concrete recommendations to re-
our attacks warn of the long-term debilitating effects of
suites—may have actually reduced security for many hosts.
implementations vulnerable for decades. Like FREAK [7],
offering “perfect forward secrecy” over RSA-based cipher-
technical debt induced by the additional complexity has left
surveillance—promotion of DHE-based TLS ciphersuites
quent attempts to remove support for DHE_EXPORT, the
tions from security experts in response to the threat of mass
eventual relaxation of crypto export restrictions and subse-
Our findings indicate that one of the key recommenda-
lowered the bar to attacks on such key sizes. Despite the
rithmic and computational improvements have significantly
5.    RECOMMENDATIONS
intended to be tractable only to NSA, two decades of algo-
though the key sizes originally used inDHE_EXPORTwere
IMAPS, and 454K POP3S servers.
illustrates the fragility of cryptographic “front doors”. Al-
can hijack connections to approximately 1.6M SMTP, 429K
attack on export-grade 512-bit Diffie-Hellman groups in TLS
downgrade attack of §3.3, an attacker with modest resources
Don’t deliberately weaken crypto.   Our downgrade
SMTP, 276K IMAPS, and 245K POP3S servers. Using our
were compromised, this would affect approximately 1.7M     the risk of trapdoors.
If each of the top ten 1024-bit primes used by each protocolparameters in TLS should be standardized so as to thwart
1024-bit primes accounting for only 4.8% of servers.         186 [38]. Ideally, the process for generating and validating
and 74.9% supportingDHE, but with the ten most common       verifiable generation process, such as that proposed in FIPS
is similar, with 8.9% of servers supporting DHE_EXPORTshould check that servers’ parameters use safe primes or a
primes account for only 5.4% of servers. POP3S deployment are computationally difficult to detect. At minimum, clients
75% supportedDHE. However, the ten most common 1024-bit     that it is possible to create trapdoored primes [20,44] that
For IMAPS, 8.4% of servers supportedDHE_EXPORTand     putation for very common fixed groups. However, we note
1024-bit groups.                                           mitigate some of the damage caused by NFS-style precom-
15.5% of SMTP servers used one of the ten most common   for compatibility reasons, generating fresh groups may help
ported DHE, and 14.8% supported     DHE_EXPORTciphers.     tions that must continue to use or support 1024-bit groups
50.7% of SMTP servers supported STARTTLS, 41.4% sup-     Avoid fixed-prime 1024-bit groups. For implementa-
for IMAPS, POP3S, and SMTP+StartTLS. We found that
algorithmic improvement.
We studied 1% samples of the public IPv4 address space
so 2048-bit Diffie-Hellman will remain secure barring a major
to fetch received mail, wrap the entire connection in TLS.
group is around109 times harder than for a 1024-bit group,
STARTTLS command. POP3S and IMAPS, used by end users
transition. Precomputation for a 2048-bit non-trapdoored
allows a connection to be upgraded to TLS by issuing the
tors should move to 2048-bit or larger groups to facilitate this
the protocol used to relay messages between mail servers,
2048 bits as soon as server configurations allow. Server opera-
Mail  TLS is also used to secure email transport. SMTP,
recommend that clients raise the minimumDHEgroup size to
primes is sohu.com (ranked 31st globally).                  NIST has recommended such a transition since 2010 [4]. We
DHEciphersuite using one of the two most common 1024-bit (and 1024-bit RSA) must be phased out in the near term.
1024-bit prime. The most popular site that negotiates a      within reach for state-level actors. As such, 1024-bitDHE
passively eavesdropped given the precomputation for a single   Our analysis suggests that 1024-bit discrete log may be
----------------Page (10) Break----------------
12
PKC, 2006.                                                    Schannel could allow information disclosure, May 2015.
discrete logarithm problem with the number field sieve. In    [37] Microsoft Security Bulletin MS15-055. Vulnerability in
[10] A. Commeine and I. Semaev. An algorithm to solve the
Security and Privacy, 1999.
signature-based key-exchange protocol. InCrypto, 2002.                   using the NRL protocol analyzer. InIEEE Symposium on
[9] R. Canetti and H. Krawczyk. Security analysis of IKE’s       [36] C. Meadows. Analysis of the Internet key exchange protocol
180 decimal digits, 2014. http://caramel.loria.fr/p180.txt.          ACM CCS, pages 62–72, 2012.
New record for discrete logarithm in a prime finite field of        B. Preneel. A cross-protocol attack on the TLS protocol. In
[8] C. Bouvier, P. Gaudry, L. Imbert, H. Jeljeli, and E. Thomé.  [35] N. Mavrogiannopoulos, F. Vercauteren, V. Velichkov, and
Security and Privacy, 2015.
1996.
composite state machines of TLS. InIEEE Symposium on
[34] U. M. Maurer and S. Wolf. Diffie-Hellman oracles. InCrypto,
Zinzindohoue. A messy state of the union: Taming the
In Crypto, 1994.
C. Fournet, M. Kohlweiss, A. Pironti, P.-Y. Strub, and J. K.
Diffie-Hellman protocol and computing discrete logarithms.
[7] B. Beurdouche, K. Bhargavan, A. Delignat-Lavaud,
[33] U. M. Maurer. Towards the equivalence of breaking the
in Cryptography, 2014.
industry shift. Technical report, Jefferies, 2012.
[6] D. J. Bernstein and T. Lange. Batch NFS. InSelected Areas
[32] M. Lipacis. Semiconductors: Moore stress = structural
http://cr.yp.to/factorization/smoothparts-20040510.pdf.
Development of the Number Field Sieve. Springer, 1993.
[5] D. J. Bernstein. How to find smooth parts of integers, 2004.
[31] A. K. Lenstra and H. W. Lenstra, Jr., editors.The
Management, 2007.
security (TLS) false start. IETF Internet Draft, 2010.
NIST Special Publication 800-57: Recommendation for Key
[30] A. Langley, N. Modadugu, and B. Moeller. Transport layer
[4] E. Barker, W. Barker, W. Burr, W. Polk, and M. Smid.
Factorization of a 768-bit RSA modulus. InCrypto, 2010.
in finite fields of small characteristic. InEurocrypt, 2014.
Osvik, H. te Riele, A. Timofeev, and P. Zimmermann.
heuristic quasi-polynomial algorithm for discrete logarithm
J. W. Bos, P. Gaudry, A. Kruppa, P. L. Montgomery, D. A.
[3] R. Barbulescu, P. Gaudry, A. Joux, and E. Thomé. A
[29] T. Kleinjung, K. Aoki, J. Franke, A. K. Lenstra, E. Thomé,
corps finis. PhD thesis, Université de Lorraine, France, 2013.
SHARCS/talks06/thorsten.pdf.
[2] R. Barbulescu.Algorithmes de logarithmes discrets dans les
bit integers, 2006. http://www.hyperelliptic.org/tanja/
algorithm, 2014. Release 2.1.1.
sieve and an estimate for the sieving step for factoring 1024
cado-nfs, an implementation of the number field sieve
[28] T. Kleinjung. Cofactorisation strategies for the number field
A. Kruppa, F. Morain, E. Thomé, and P. Zimmermann.
RFC 4303, Dec. 2005.
[1] S. Bai, C. Bouvier, A. Filbois, P. Gaudry, L. Imbert,
[27] S. Kent. IP encapsulating security payload (ESP).
[26] S. Kent. IP authentication header. RFC 4302, Dec. 2005.
8.    REFERENCES
RFC 7296, Oct. 2014.
Internet key exchange protocol version 2 (IKEv2).
experiments used UCS hardware donated by Cisco.
[25] C. Kaufman, P. Hoffman, Y. Nir, P. Eronen, and T. Kivinen.
and several other universities and organizations; additional
Comp., 72(242):953–967, 2003.
testbed, which is supported by INRIA, CNRS, RENATER,      comparison with the Gaussian integer method.Math.
ship. Some experiments were conducted using the Grid’5000      number field sieve for discrete logarithms in prime fields. A
[24] A. Joux and R. Lercier. Improvements to the general
ship, and by an Alfred P. Sloan Foundation Research Fellow-
cryptography. InNDSS, 2013.
Morris Wellman Faculty Development Assistant Professor-
apple: Backwards compatibility attacks on state-of-the-art
the Google Ph.D. Fellowship in Computer Security, by the
[23] T. Jager, K. G. Paterson, and J. Somorovsky. One bad
by the Mozilla Foundation, by a gift from Supermicro, by
RFC 2409, Nov. 1998.
Research Fellowship Program under grant DGE-1256260,
[22] D. Harkins and D. Carrel. The Internet key exchange (IKE).
search grant ANR-12-BS02-001-01, by the NSF Graduate
number field sieve.SIAM J. Discrete Math., 6(1), 1993.
Starting Grant 259639 (CRYSP), by the French ANR re-
[21] D. M. Gordon. Discrete logarithms inGF(p)     using the
Research under contract N00014-11-1-0470, by the ERC          discrete log cryptosystems. InCrypto, 1992.
CNS-1518741, and EFRI-1441209, by the Office of Naval     [20] D. M. Gordon. Designing and detecting trapdoors for
Foundation under contracts CNS-1345254, CNS-1409505,         parameters for TLS. IETF Internet Draft, May 2015.
[19] D. Gillmor. Negotiated finite field Diffie-Hellman ephemeral
in part upon work supported by the U.S. National Science
1024-bit. In Eurocrypt, 2007.
Martin Thomson, and Eric Rescorla. This material is based
hardware for the NFS: Another attempt to cope with
Andrei Popov, Ivan Ristic, Edward Snowden, Brian Smith,
[18] W. Geiselmann and R. Steinwandt. Non-wafer-scale sieving
Ron Dreslinski, Tanja Lange, Adam Langley, Kenny Paterson,
2005.
The authors wish to thank Michael Bailey, Daniel Bernstein,
sieve. InInformation Technology: Coding and Computing,
Improved routing-based linear algebra for the number field
Acknowledgments
[17] W. Geiselmann, H. Kopfer, R. Steinwandt, and E. Tromer.
RFC 4419, Mar. 2006.
for keeping future systems secure.
exchange for the secure shell (SSH) transport layer protocol.
ilous gap that separates these communities will be essential  [16] M. Friedl, N. Provos, and W. Simpson. Diffie-Hellman group
with standards efforts and software review. Bridging the per-    Usenix Security, 2013.
Fast Internet-wide scanning and its security applications. In
crypto is actually being applied, such as through engagement
[15] Z. Durumeric, E. Wustrow, and J. A. Halderman. ZMap:
tographers, for their part, should involve themselves in how
1976.
for being aware of applicable cryptanalytic attacks. Cryp-
cryptography. IEEE Trans. Inform. Theory, 22(6):644–654,
more effectively. System builders should take responsibility
[14] W. Diffie and M. E. Hellman. New directions in
phers and creators of practical systems need to work together
certain primes. InCrypto, 1988.
A key lesson from this state of affairs is that cryptogra-
[13] B. den Boer. Diffie-Hellman is as strong as discrete log for
exchanges that use a few small, widely shared groups.
Computational Perspective. Springer, 2001.
of Internet communication depends on Diffie-Hellman key    [12] R. Crandall and C. B. Pomerance.Prime Numbers: A
phers did not appreciate that the security of a large fraction     block Wiedemann algorithm.Math. Comp., 62(205), 1994.
understood by system builders. Likewise, many cryptogra-    [11] D. Coppersmith. Solving linear equations overGF(2) via
----------------Page (11) Break----------------
13
devcentral.f5.com/articles/ssl-profiles-part-5-ssl-options.             Media leak. http://www.spiegel.de/media/media-35551.pdf.
[53] J. Wagnon. SSL profiles part 5: SSL options, 2013. https://   [71] What your mother never told you about SIGDEV analysis.
In 2nd Usenix Workshop on Electronic Commerce, 1996.            http://www.spiegel.de/media/media-35520.pdf.
[52] D. Wagner and B. Schneier. Analysis of the SSL 3.0 protocol. [70] VPN SigDev basics. Media leak.
key agreement with short exponents. InEurocrypt, 1996.                     http://www.spiegel.de/media/media-35527.pdf.
[51] P. C. Van Oorschot and M. J. Wiener. On Diffie-Hellman    [69] VALIANTSURF – WikiInfo. Media leak.
logarithms. In ACM CCS, 1994.
http://www.spiegel.de/media/media-35517.pdf.
search with application to hash functions and discrete
[68] VALIANTSURF (VS): Capability levels. Media leak.
[50] P. C. Van Oorschot and M. J. Wiener. Parallel collision
http://www.spiegel.de/media/media-35526.pdf.
algorithm. J. Symbolic Comput., 33(5):757–775, 2002.
[67] TURMOIL VPN processing. Media leak, Oct. 2009.
polynomials and improvement of the block Wiedemann
http://www.spiegel.de/media/media-35528.pdf.
[49] E. Thomé. Subquadratic computation of vector generating
[66] TURMOIL IPsec VPN sessionization. Media leak, Aug. 2009.
19a7f19686bcdbd689c6fbea31f68a276e62d886/stud.c#L593.
Media leak. http://www.spiegel.de/media/media-35513.pdf.
https://github.com/bumptech/stud/blob/
[65] TURMOIL/APEX/APEX high level description document.
[48] stud: The scalable TLS unwrapping daemon, 2012.
http://www.spiegel.de/media/media-35522.pdf.
http://www.sagemath.org.
[64] SPIN 15 VPN story. Media leak.
The Sage Development Team, 2015.
politics/23nsa-sigint-strategy-document.html.
[47] W. Stein et al.Sage Mathematics Software (Version 6.5).
http://www.nytimes.com/interactive/2013/11/23/us/
inside-the-nsa-s-war-on-internet-security-a-1010361.html.
[63] SIGINT strategy. Media leak.
http://www.spiegel.de/international/germany/
http://www.spiegel.de/media/media-35519.pdf.
security. Der Spiegel, Dec 2014.
[62] POISONNUT – WikiInfo. Media leak.
[46] Spiegel Staff. Prying eyes: Inside the NSA’s war on Internet
http://www.spiegel.de/media/media-35533.pdf.
genera. In Proc. Sympos. Pure Math., volume 20. 1971.
[61] LONGHAUL – WikiInfo. Media leak.
[45] D. Shanks. Class number, a theory of factorization, and
2010. http://www.spiegel.de/media/media-35515.pdf.
finite prime fields.Math. Comp., 71(237):363–377, 2002.
[60] Intro to the VPN exploitation process. Media leak, Sept.
[44] I. A. Semaev. Special prime numbers and discrete logs in
http://www.spiegel.de/media/media-35509.pdf.
57(2):140–147, 2005.
[59] Innov8 experiment profile. Media leak.
[43] O. Schirokauer. Virtual logarithms.J. Algorithms,
http://www.spiegel.de/media/media-35514.pdf.
Numerical Mathematics, 15(3):331–334, 1975.
[58] GALLANTWAVE@scale. Media leak.
[42] J. M. Pollard. A Monte Carlo method for factorization.BIT
significance (corresp.).Trans. Inform. Theory, 24(1), 1978.          http://cryptome.org/2013/08/spy-budget-fy13.pdf.
[57] FY 2013 congressional budget justification. Media leak.
computing logarithms overGF(p)     and its cryptographic
[41] S. C. Pohlig and M. E. Hellman. An improved algorithm for      Media leak. http://www.spiegel.de/media/media-35529.pdf.
RFC 2412, Nov. 1998.                                      [56] Fielded capability: End-to-end VPN SPIN 9 design review.
[40] H. Orman. The Oakley key determination protocol.               http://www.spiegel.de/media/media-35671.pdf.
https://www.olcf.ornl.gov/titan.                             [55] APEX active/passive exfiltration. Media leak, Aug. 2009.
[39] Oak Ridge National Laboratory. Introducing Titan, 2012.          https://gforge.inria.fr/projects/ecm.
[38] NIST. FIPS PUB 186-4: Digital signature standard, 2013.     [54] P. Zimmermann et al. GMP-ECM, 2012.
----------------Page (12) Break----------------