2
apply to the prime fields used in practice.
characteristic fields [3], but these advances are not known to
algorithm for small-
have resulted in a quasi-polynomial
in discrete log algorithms
advances
spectacular
Recent
1
compute the discrete logs of many targets.
and reused to
p
linear algebra can be done once for a prime
), so polynomial selection, sieving, and
g
(or
y
that involves
Crucially, descent is the only NFS stage
the log database.
and a final phase that actually reconstructs the target using
be represented by elements in the database of known logs,
these medium-sized primes are further sieved until they can
in terms of medium-sized primes, a middle phase, in which
an initialization phase, which tries to write the target
6
a generator leaks 290 bits of information about exponents at
phases:
as
This step is accomplished in three
q
precomputed database.
512-bit prime, using
in terms of the logs in the
sun.security.provider
y
For Java’s
that allow us to write the log of
is a random integer.
We re-sieve until we can find a set of relations
3
we focus exclusively on the traditional prime field variety.
.
/q
) are gaining in popularity, but
y
1)
ECDHE
of the target
p −
curve Diffie-Hellman (
The final stage, descent, actually deduces the discrete log
generated according to [38], (
size and can be parallelized in a limited fashion.
New ciphersuites that use elliptic
p
since for
contained in its certificate.
and the matrix
q
prime factors in its order,
format, where the server’s key exchange value is fixed and
to have many small
TLS also supports a rarely used “static” Diffie-Hellman
The difficulty depends on
2
to the final stage.
is likely
tography, SSL 3.0 and TLS 1.0 supported reduced-strength
This database of logs serves as input
q
many small elements.
the subgroup generated by
of the group will give us logs of
To comply with 1990s-era U.S. export restrictions on cryp-
In a DSA group,
these formats led to a simple programming error.
.
q
); we conjecture that the confusion between
ab
matrix modulo the order
p, q, g
keys also derived from g
A nonzero kernel vector of the
data, protected by an authenticated encryption scheme with
PKIX) is (
factorizations we have found.
client and server start exchanging application
), while that of DSA parameters (coming from
sparse matrix consisting of the coefficient vectors of prime
Thereafter,
p, g
we construct a large,
Finished messages and verified by the recipients.
quence (
linear algebra,
in a pair of
key exchange parameters (coming from PKCS#3) is a se-
In the third stage,
These MACs are exchanged
the canonical ASN.1 representation of Diffie-Hellman
to consider before having enough relations.
of the handshake transcript.
q
lem:
and on the number of special
and calculates a MAC of its view
is likely due to a usability prob-
I
ab
g
search; it also depends on
g
for
TLS master secret from
q
-smooth numbers in this
each party computes the
B
This substitution of
prevent downgrade attacks [52],
the probability of encountering
this way.
The time for this step depends on heuristic estimates of
We found 5,741 hosts misconfigured
To ensure agreement on the negotiation messages, and to
must search through and attempt to factor many elements.
.
.
of the others, but is computationally expensive, because we
a
g
with a ClientKeyExchange message containing g
is handled independently
place of the generator
q
The client verifies the signature and responds
in the
parallelizes well since each special
q
its certificate.
Sieving
but mistakenly used the DSA group order
) using the long-term signing key from
is a parameter.
b
p
I
primes as
cr, sr, p, g, g
However, some servers in our scans used Java’s DSA
tuple (
where
a ServerKeyExchange message containing a signature over the
candidates,
servers.
, and sends
package and are used by default in many Java-based TLS
2I
sun.security.provider
b
region of 2
explores a sieving
groups are hard-coded in Java’s
g
Notably, DSA
q
), computes
which for each special
secure for use in Diffie-Hellman key exchanges.
p, g
using properly generated DSA parameters, these groups are
It chooses a group (
lattice sieving,
When
parameters.
q
Modern implementations use special-
.
, the server is responsible for selecting the Diffie-Hellman
q
-smooth).
DHE
B
generates only a subgroup of order
In
(called
g
2
B
and
.
TLS_DHE_*
q
elements, all of whose prime factors are less than some bound
is identified by ciphersuites that begin with
and number field elements in batches to find many relations of
factor
In the second stage, sieving, one factors ranges of integers
, and
1 has a large prime
parallelizes well and is only a small portion of the runtime.
DHE
p −
such that
) typically has degree 5 or 6.) This
strength is called “ephemeral” Diffie-Hellman, or
Textbook Diffie-Hellman with unrestricted
z
p
(DSA) [38] uses primes
Diffie-Hellman.
(
f
The Digital Signature Algorithm
TLS specifies ciphersuites supporting multiple varieties of
Misconfigured groups
a ServerHello message (containing a random nonce sr).
(For our cases,
tion.
a ciphersuite from the client’s list and signals its selection in
with a delay hardly noticeable for browser users.
The server selects
to an attack using NFS, we could compute the discrete log
) for the computa-
Compared
exchange algorithm and other primitives.
z
(
vulnerable server and capture user credentials.
the ClientHello message, where each ciphersuite specifies a key
§3.3 to impersonate a
/f
) within
cr
)
our man-in-the-middle attacker of
list of supported ciphersuites (and a random nonce
z
As a proof-of-concept, we modified
The client sends a
(
FTP servers (6 hosts).
the crypto algorithms used for the session.
software (21 hosts), web conferencing servers (27 hosts), and
Q
The TLS handshake begins with a negotiation to determine
web interfaces for VPN devices (48 hosts), communications
) defining a number field
including
z
TLS and Diffie-Hellman
5
(
nections to a variety of vulnerable TLS servers,
Microsoft IIS does not support 512-bit export ciphersuites.
3.1
f
Our computations would have allowed us to hijack con-
7.8% of HTTPS servers among Alexa Top Million domains.
, likely because
calculations used interval width varying from 40 to 70 bits.
b
this attack with our precomputations can compromise about
mial
selection, in which one finds a polyno-
7
g
The Pollard lambda
We find that
8
First is polynomial
The National Science Foundation’s budget was $7 billion.
parameters in [29].
, only 0.1% reused
50 and 176 hours) implementation.
strength and then recovering the session key.
4
We would lower the smoothness bounds compared to the
DHE_EXPORT
(which finishes in seconds) to 81 bits (which took between
TLS protocol flaw to downgrade the connection to export-
on the prime p and comprise most of the computation.
3
The order of the largest-order subgroup ranged from 46 bits
The first three steps are only dependent
encryption for widely used VPN protocols?
ever, for
server that allows export-grade Diffie-Hellman, by using a
can attack connections between popular browsers and any
11
How-
tational properties.
of them used 160-bit exponents and the rest used 128 bits.
(1) in the expo-
known to cryptographers, it apparently has not been widely
cases, the vulnerable hosts used 512-bit prime moduli; three
of 20 handshakes, and that 15% only used one value.
Next, we show how a man-in-the-middle, so armed,
How is NSA defeating the
called index calculus and has four stages with different compu-
4
In all
at least once over the course
o
of them.
by the Edward Snowden leaks:
The general technique is
both strong and weak ciphersuites.
Although this fact is well
formula is inherently imprecise, since the
party uses only strong cryptography but the other supports
authenticated with valid browser-trusted certificates.
b
the implementations can be shared.
the discrete log for any key-exchange message that uses one
that group has a far lower cost.
would answer one of the major cryptographic questions raised
512-bit primes on the web, so that we can quickly compute
If true, this
sieve algorithm for factoring [12,31], and in fact many parts of
This
g
the whole exponent used by 159 different hosts, 53 of which
preted as a backwards compatibility attack [23] where one
only on the group, after which computing individual logs in
made with those groups in close to real time.
is an algorithm-specific constant.
we found that 17% reused
exponent used in 460 exchanges and were able to recover
More generally, Logjam can also be inter-
we perform NFS precomputations for the two most popular
There is a closely related number field
attacker to perform a single precomputation that depends
First,
k
1
We computed partial information about the server secret
This would allow them to break any key exchanges
,
the fact that the number field sieve for discrete log allows an
this protocol flaw.
attack against TLS, which we call the Logjam attack.
groups.
The problems stem from
We expect that TLS 1.3 will fix
DHE
precomputing a table of distinguished points.
(NFS) [21, 24, 43].
and
ServerKeyExchange message.
tions for at least a small number of 1024-bit Diffie-Hellman
In this section, we exploit these facts to construct a novel
hosts serving browser-trusted certificates that support
advance, this implementation can be arbitrarily sped up by
most efficient discrete log algorithm is the number field sieve
less secure than widely believed.
discrete log,
resources to have performed number field sieve precomputa-
cryptography, but we find that, as used in practice, it is often
is the integer to factor or the prime modulus for
majority of servers use a handful of common groups.
be prevented by additionally signing the ciphersuite in the
In this case, the
points method for collision detection; for a prime known in
By randomly sampling IPv4
with prime fields and large group orders.
these attacks could
We used the distinguished
Our calculations suggest that it is plausibly within NSA’s
for both normal and export-grade Diffie-Hellman, the vast
Diffie-Hellman key exchange is a cornerstone of applied
to do the computation online.
N
92.3% use one of the two most popular primes, shown here.
wrote in C using the GMP library.
Is NSA Breaking 1024-bit DH?
CONCLUSION
All
tion and use it to attack later handshakes, avoiding the need
where
Diffie-Hellman is typically implemented
from one connec-
fused with DHE handshakes [35].
which
The typical case
7.
Sage [47] using a parallel Pollard rho implementation that we
4.2
,
of
b
Diffie-Hellman exchanges made with that prime.
showed how explicit-curve ECDHE handshakes could be con-
We implemented the van Oorschot and Wiener algorithm in
2048-bits and higher and to gracefully reject weak ones [19].
cryptanalytic capability for the nation” [63].
connections across all of our scans.
Mavrogiannopoulos et al.
clients and servers to negotiate a few well-known groups of
,
2/3
g
art for high performance computing to maintain pre-eminent
can be used to efficiently break all
TLS developers plan to support a new extension that allows
attacker can compute the discrete log of
p
DHE_EXPORT
; these had been used for 40,903
)
called key exchange rollback [52].
base and drive the state of the
For these servers, an
to invest in the industrial
Schneier and Wagner noted a related vulnerability that they
Top 1M HTTPS domains allow
log log N
Many
g
precomputation on
8.4% of Alexa
(
the subgroup generated by
As early as SSL 3.0,
leaked strategic plan for the period called for it to “continue
mai has removed all support for export ciphersuites.
two hours — this setting is hard-coded.
In fact, as illustrated in Figure 1, a single large
discrete log.
Aka-
Top 512-bit DH primes for TLS.
) pairs where we knew factors of
1/3
for
ysis and exploitation services program C” (to $360M). NSA’s
cross-protocol attacks discovered in TLS.
and various hosting providers.
time to compute a single
IT services” (to $247M), and a cryptically named “cryptanal-
)
Logjam and FREAK both follow the same pattern as other
b
p, g
Table 1:
g
(463 distinct primes)
Cisco,
There were 753 (
parameters to minimize overall
each individual discrete log only takes about a minute.
“cryptanalytic
log N
bits.
about the computational tradeoffs, for example by balancing
notable $100M increases in two programs [57]:
Microsoft Schannel caches
indefinitely against all servers that use that group, and since
(1))(
IBM,
Oracle,
DH” option is checked [53].
versarial cryptography and exploit internet traffic,” included
Textbook descriptions of discrete log can be misleading
of length ranging from 64 to 256
o
8%
since the precomputation for each 512-bit group can be used
+
in “groundbreaking cryptanalytic capabilities to defeat ad-
shall see, the cost per compromised connection is far lower,
x
mod p can easily find the shared secret.
(others)
On the server side, we notified Apache,
unless the “Single
b
k
x
a target private exponent
classified 2013 budget request, which prioritized investment
48976f76795094e71e7903529f5a824b
pected to follow suit.
bits.) Logjam affects fewer servers than FREAK, but, as we
g
(
The agency’s
are ex-
d6b5145b9f241e5acc31ff090a4bc711
log x from y = g
required using Pohlig-Hellman and Pollard lambda to recover
512
and OpenSSL and Safari
≥
An attacker who can find the discrete
exp
[57].
c8157f62d8f33633ee5772f11f05ab22
, and ordered them by the estimated work
and hardware TLS frontends will reuse
the complexity is
The F5 BIG-IP load balancers
10
d4bcd52406f69b35994b88de5db89682
4
cryptanalytic attack.
they accept to 1024 bits,
of size
g
of the order of
17.9% of connections with Top 1M sites could be
10%
For the number field sieve,
33, 34]), but computing discrete logs remains the best known
includes the NSA) was $10.5 billion
p
groups
do not.
lent to the discrete log problem (except in certain groups [13,
such as stud [48],
ing from asymptotic complexity.
to this work, most popular browsers accepted
mod_ssl
primes;
DHE
1 had revealed prime factors
get for the U.S. Consolidated Cryptologic Program (which
(Prior
with one of the ten most popular 1024-bit
The security of Diffie-Hellman is not known to be equiva-
80a3030c6e4c3757d08f70e6aa871033
9
Chrome are transitioning the minimum size of the
the FY 2012 bud-
certain load balancers,
Without better parameter choices, we resort to extrapolat-
12
p −
” case.
Schannel could allow information disclosure, May 2015.
if the prime factorization of
71fd19d8d8f37c39bf863fd60e3e3006
ware “implants” on VPN devices, indicating that the use of
To put this dollar figure in context,
Nginx internally apply this option,
DHE
handshakes.
result of our disclosures, Internet Explorer [37], Firefox, and
relevant parameter choices.
plausibly on the order of hundreds of millions of dollars.
experimentally update the estimates of this paper with more
While both Apache and
) sent by a server as interesting
DHE
274cdf1a9f588218fb435316a16e3741
p
As a
will negotiate
Microsoft Security Bulletin MS15-055. Vulnerability in
Certain published NSA documents refer to soft-
p, g, y
defense is to reject small primes in
enabled Top 1M sites (and 10% with browser-trusted sites)
[37]
over elliptic curve groups, we address only the “mod
to perform the linear algebra for DH-1024 in one year is
for the lifetime of a TLS context.
we could not
means.
9fdb8b8a004544f0045f1737d0ba2e0b
as 16 bits.
reduction can be achieved for discrete log, the hardware cost
We classified a tuple (
From a client perspective, the only
82%
larger than those proposed,
While there is also a Diffie-Hellman exchange
Security and Privacy, 1999.
Approximately 24.0% of browser connections with HTTPS-
allowed groups as small
bility remains that NSA could defeat IPsec using alternative
b
I
.
g
The possi-
.
Apache
using the NRL protocol analyzer. In IEEE Symposium on
an implementation bug.
whereas Safari
If we optimistically assume that a similar
is chosen.
Prime
mod p
Of course, this explanation is not dispositive.
C. Meadows. Analysis of the Internet key exchange protocol
reuse
factor of 80 [17].
accepted 512-bit primes,
p
In contrast, Logjam is due to a protocol flaw in TLS, not
DHE
with values of
Since no publicly available software can currently deal
and Opera all
negligible differences in whether
OpenSSL will
CPUs to ASICs has been estimated to reduce costs by a
ab
a fresh ephemeral RSA key (typically when it restarts).
used with each prime
[36]
“[r]un attacks to recover PSK” [60].
Firefox,
g
Popularity
commodity hardware and is usable until the server generates
differ slightly between browsers, this turns out to result in
task.
ACM CCS, pages 62–72, 2012.
option,
of factorization, moving linear algebra from general purpose
g
Additionally, NSA is willing to
The cryptanalysis takes several hours on
Source
In the context
SSL_OP_SINGLE_DH_USE
B. Preneel. A cross-protocol attack on the TLS protocol. In
giving too few smooth results per sieving sub-
administrator “chatter” [70].
Chrome,
and each computes a shared secret
While the offered ciphers
We then examined the generators
Furthermore,
PSKs [60], previously decrypted SSH traffic [60], or system
in supercomputers to finish this step in a year.
N. Mavrogiannopoulos, F. Vercauteren, V. Velichkov, and
and Safari.
across 28 cores and discovered 36,447 prime factors.
use the same key.
Internet Explorer,
,
too small,
the
was constructed in 2012 for $94M, suggesting a cost of $11B
Prior to our work,
[35]
mod p
is clearly
the CORALREEF database of known
Without enabling
and the ECM factoring methods [54] for 5 days parallelized
factors the ephemeral key to hijack future connections that
Firefox,
well within reach of NFS-based cryptanalysis.
as Chrome,
figurations [70, 71],
Titan
our findings public.
1996.
I
1 algorithm
b
once and reuse it for multiple negotiations.
The attacker then
the vulnerabilities discussed in this paper before we made
g
117 years to complete the 1024-bit linear algebra stage.
to locate a PSK, including using a database of router con-
b
groups, which are widely used in practice and still considered
TLS client implementations.
U. M. Maurer and S. Wolf. Diffie-Hellman oracles. In Crypto,
proposed value of the sieving region parameter
“export-grade” Diffie-Hellman using 512-bit primes that are
which this will occur by offering the same sets of ciphersuites
p −
We can estimate the number of sites for
documents describe techniques for analysts
plications of precomputation attacks for 768- and 1024-bit
[34]
a smaller number of servers also support legacy
GMP-ECM implementations of the Pollard
in several
Bob sends
g
about
the most powerful supercomputer in the U.S. — would take
but the
However,
export-grade 512-bit ephemeral RSA keys, relying on a bug
developers
Several
,
use Diffie-Hellman.
We explore the im-
In Crypto, 1994.
proposes smoothness bounds of 42 bits,
We then ran the
Titan supercomputer [39] — at 300,000 CPU cores, currently
but instead compute
PSK.
per can only decrypt connections that organically agree to
Risks from common 1024-bit groups.
Diffie-Hellman protocol and computing discrete logarithms.
[28]
downgrades a regular RSA key exchange to one that uses
HTTPS sites allow it, most commonly using 1024-bit primes.
for each connection,
mod p
The
1 using Bernstein’s batch method [5].
and server
The attack system also seems to require knowledge of the
hardware and the core-year estimate from Table 2.
p −
niscent of the recent FREAK [7] attack, in which an attacker
U. M. Maurer. Towards the equivalence of breaking the
thin:
popular
, a passive eavesdrop-
a
attacks too and discover several vulnerable implementations.
b
client
[33]
DHE
We implement these
g
proposing parameters for factoring a 1024-bit RSA key is
Logjam is remi-
traverses multiple network paths [55, 56, 58, 66].
To derive a rough estimate, we can begin with general purpose
we opportunistically factored
fresh value
We notified major
and about two-thirds of
Many TLS servers do not use a
has no provision to communicate.
Alice sends
that are suitable for the larger fields involved in discrete log.
key exchange methods,
must be reassembled (“paired”) whenever the interaction
Comparison with previous attacks
industry shift. Technical report, Jefferies, 2012.
,
The prior work
DISCLOSURE AND RESPONSE
Despite widespread support for
We address these in the next subsections.
since IKE transcripts
parameters without knowing the subgroup order, which TLS
6.
p
Moore stress = structural
difficult, since there has been little work on designing chips
key caching.
algorithm and their relative parallelism.
of these using one of five groups.
possible
.
, 84% use a 1024-bit or smaller group, with 94%
and the inability of clients to properly validate Diffie-Hellman
Estimating the financial cost for the linear algebra is more
M. Lipacis. Semiconductors:
had time to finish.
For each non-safe prime
case is difficult due to the tradeoffs between the steps of the
Ephemeral
several
complexity of the attack execution,
deliberately weakening cryptography.
p
perimentally extrapolating sieving parameters to the 1024-bit
the long-term debilitating effects of
attack, we tested various non-safe primes found in our scans.
[32]
TLS supports Diffie-Hellman as one of
DHE
background resource that does not delay rendering the page.
indicate that this requirement substantially increases the
likely be reused to speed calculations of individual logs.
vulnerable to a known attack of van Oorschot and Wiener [51],
handshake completion until the discrete log computation has
multiplicative subgroup modulo
our attacks warn of
ATTACKING TLS
the attacker might choose to compromise a request for a
Ex-
The published documents
discrete logs in close to real time, and the second is to delay
Since a step of descent uses sieving, the same hardware could
To see if TLS servers in the wild were vulnerable to this
Development of the Number Field Sieve. Springer, 1993.
support
of a
which is
Of the Top 1M sites that
as hypothetical by van Oorschot and Wiener [51].
3.
The first is to compute individual
subgroups in combination with short exponents,
resources
Like FREAK [7],
takes much longer than usual,
two-sided IKE transcript [60].
to complete the DH-1024 sieving precomputation in one year.
A. K. Lenstra and H. W. Lenstra, Jr., editors. The
g
These include use of composite-order
the victim connection still
active downgrade attack.
requirement of the VAO is the need to obtain the complete
suggests that an $8M investment would buy enough ASICs
and a generator
[31]
with browser-trusted certificates.
Plausible with state-level
log precomputation among vast numbers of potential targets.
This attack was first described
implementations vulnerable for decades.
security (TLS) false start. IETF Internet Draft, 2010.
p
configuration mistakes.
DH-1024:
This
since it allows the attacker to amortize the cost of discrete
as do 23.9% of sites
There are two remaining challenges in implementing this
technical debt induced by the additional complexity has left
Although
As Figure 4 illustrates, a hard
.
ter fixed design and tape-out costs of roughly $2M [32].
NSA’s VPN attack system.
Alice and Bob agree on a prime
read and write application data pretending to be the server.
A. Langley, N. Modadugu, and B. Moeller. Transport layer
other servers because of design and implementation flaws and
the
we tested close the connection after a minute.)
x/z
and is easily parallelizable.
limits of an adversary’s capabilities into devastating breaks,
,
prime groups,
lization, this would cost about $2 per chip to manufacture, af-
(Other browsers
of Diffie-Hellman groups can convert attacks that are at the
the above requirements are also present in the
DHE
[30]
single 768-bit discrete log computation is around 2 core-days
We were also able to compromise Diffie-Hellman for many
p
,
to complete the handshake with the client, and then freely
Factorization of a 768-bit RSA modulus. In Crypto, 2010.
However, widespread reuse
a
Both of
of Alexa Top 1M sites support
DHE_EXPORT
Firefox’s TLS connections alive indefinitely.
In the simple case of
With standard transistor costs and uti-
vulnerabilities in real-world systems.
time can then derive the master secret and connection keys
no disadvantage to reusing them.
68.3%
For example, this allows us to keep
the cost of
in time
quent attempts to remove support for
is the first time they have been exploited to expose concrete
in close to real
Osvik, H. te Riele, A. Timofeev, and P. Zimmermann.
key algorithm [14].
at newer technologies.
.
been computed before [8], but, as far as we are aware, this
a more modern size reduces costs, as transistors are cheaper
eventual relaxation of crypto export restrictions and subse-
x
after precomputation,
When primes are of sufficient strength, there seems to be
is commonly deployed on web servers.
J. W. Bos, P. Gaudry, A. Kruppa, P. L. Montgomery, D. A.
reset the handshake timer.
b
SKEYID
Diffie-Hellman key exchange was the first published public-
Despite the
to recover
Discrete logs over larger groups have
T. Kleinjung, K. Aoki, J. Franke, A. K. Lenstra, E. Thomé,
the dies from the 130 nm technology node used in the paper to
DIFFIE-HELLMAN CRYPTANALYSIS
TLS warning alerts, which are ignored by the browser but
In total,
DHE
used in deriving
but an attacker who can compute
since, including IKE, SSH, Tor, and OTR.
2.
Million HTTPS sites.
HTTPS
Shrinking
1 core-day.
published in 1998 and have been used for many applications
[29]
lowered the bar to attacks on such key sizes.
timeouts, but we can keep their connections alive by sending
both sides of the connection, and (2) in IKEv1 only, the PSK
stage,
If not, Pollard lambda can use this information
Web browsers tend to have shorter
the descent should take at most
SHARCS/talks06/thorsten.pdf.
.
Diffie-Hellman groups, such as those based on elliptic curves.
mate of 3M chips to complete sieving in one year.
as well as the nonces and cookies transmitted by
log oracle, we can compromise connections to over 7% of Top
These groups were
rithmic and computational improvements have significantly
to 3.6M (25.7%) publicly accessible SSH servers.
client and server have different handshake transcripts at this
longer term, we advocate that protocols migrate to stronger
Group 2), and 1536 (Oakley Group 5).
x
TLS warning alerts.
bit integers, 2006. http://www.hyperelliptic.org/tanja/
almost two decades) could passively eavesdrop on connections
b
the rest of
intended to be tractable only to NSA, two decades of algo-
Using our discrete
The
sieve more and save on linear algebra as above, giving an esti-
sieve and an estimate for the sieving step for factoring 1024
recover
were
We increase their chip count by a factor of ten to
1024-bit Oakley Group 2 (which has been in standards for
individual discrete logs in about a minute.
we can hijack their connections without difficulty.
“safe” primes of length 768 (Oakley Group 1), 1024 (Oakley
In the
g
experiments,
sen by the server and proceed with the handshake.
often run unattended, so they have long or no timeouts, and
level attacker who performed NFS precomputations for the
, this suffices to
A prominent example is the Oakley groups [40], which give
carefully vet the Diffie-Hellman groups they use.
DHE_EXPORT
and
sieving much as in the precomputation; extrapolating from
This allows us to compute
T. Kleinjung. Cofactorisation strategies for the number field
parameters cho-
discrete log.
that TLS servers disable export-grade cryptography and
git
DHE
Combining these equivalent choices, we find that a state-
estimates for modern techniques and adjust parameters for
though the key sizes originally used in
The remaining phase uses
tations use fixed or standardized Diffie-Hellman parameters.
[28]
a
92% of the vulnerable servers.
x ≤ z
If
ties can be computationally burdensome, so many implemen-
) as valid
and
RFC 4303, Dec. 2005.
all provided Oakley Group 2 rather than a custom group.
In the following, we update their
Al-
g
an average of around 1 core-day.
We further recommend
for two 512-bit Diffie-Hellman groups used by more than
illustrates the fragility of cryptographic “front doors”.
b
.
sieve discrete log algorithm and carried out precomputation
curl
the server-defined groups were 1024-bit, but, of those, near
IKE transcript, including the Diffie-Hellman ephemeral keys
Diffie-Hellman groups they accept.
Using these techniques, the initial descent phase took
mann and Steinwandt [18].
S. Kent. IP encapsulating security payload (ESP).
Generating primes with special proper-
To exploit this attack, we implemented the number field
i
[27]
Standard primes
are implementing a more restrictive policy on the size of
attack on export-grade 512-bit Diffie-Hellman groups in TLS
implementation of 1024-bit sieving is the 2007 work of Geisel-
(1) a complete two-sided
in [6].
, g, g
Command-line clients such as
10% of
an ASIC
in response to the Logjam attack, all mainstream browsers
512
attacker can obtain the following:
Group 2, and 37.4% preferred a server-defined group.
connection.
of all HTTPS servers that have browser-trusted certificates.
baby-step giant-step or Pollard rho.
q
with GMP-ECM based on the early-abort strategy described
Our downgrade
S. Kent. IP authentication header. RFC 4302, Dec. 2005.
p
applies to 8.4% of Alexa Top Million HTTPS sites and 3.4%
[26]
Don’t deliberately weaken crypto.
the
mented with both CADO-NFS and a new implementation
√
As a short-term countermeasure
using
attacks on IKE are possible provided that the
the best prior description of
In this scan, 21.8% of servers preferred the 1024-bit Oakley
RFC 7296, Oct. 2014.
export-grade tuple (
after which they kill
offered by OpenSSH 6.6.1p1, the latest version of OpenSSH.
Mitigations and lessons.
i
We experi-
To our knowledge,
We present measurements that show that this attack
problem,
the risk of trapdoors.
Sieving is a natural target for hardware implementation.
q
time limits for the handshake,
Given an efficient oracle for solving the discrete logarithm
we performed a scan in which we mimicked the algorithms
16% of SMTP servers, and 24% of popular HTTPS sites.
interpret the
i
The descent step takes relatively little time.
Internet key exchange protocol version 2 (IKEv2).
ability.
parameters in TLS should be standardized so as to thwart
Ideally, the process for generating and validating
crypt traffic to about 66% of IKE VPNs, 26% of SSH servers,
could be realized by developing application-specific hardware.
C. Kaufman, P. Hoffman, Y. Nir, P. Eronen, and T. Kivinen.
√
is a TLS protocol flaw rather than an implementation vulner-
Different TLS clients impose different
group, Oakley Group 2, even when offered stronger groups.
The client will
reach by computing power available to academics.
e
In order to estimate this,
i
message to the client as is.
Moreover, at this scale, significant cost savings
precomputations for ten 1024-bit groups could passively de-
186 [38].
[25]
rithm servers will prefer in practice.
majority of IKE systems select one particular 1024-bit DH
but applies to the ephemeral Diffie-Hellman ciphersuites and
This is within
Non-browser clients.
Comp., 72(242):953–967, 2003.
Therefore, we cannot directly measure what algo-
i
of 36,500 core-years.
This attack is reminiscent of the FREAK attack [7]
popular protocols, finding that an attacker who could perform
are several ways an attacker can work around this delay:
our Internet-wide scans (§4.3) show that the vast
non-export ciphersuite and forwards the ServerKeyExchange
verifiable generation process, such as that proposed in FIPS
nation state.
P
groups,
ciphersuite with a matching
should check that servers’ parameters use safe primes or a
comparison with the Gaussian integer method. Math.
ments to understand the implications of such an attack for
for a total
in time
computational effort, it is not necessarily out of reach for a
e
algorithm.
the computation takes an average of 70 seconds, but there
tography.
core-years,
We perform measure-
At minimum, clients
number field sieve for discrete logarithms in prime fields. A
Although 45M core-years is a huge
DHE_EXPORT
i
While IKE is designed to support a range of Diffie-Hellman
attacker can downgrade a connection to export-grade cryp-
client’s highest priority mutually supported key exchange
With our descent implementation,
x mod z
During the SSH handshake, the client and server select the
message from the server.
P
Costs in hardware
recover
are computationally difficult to detect.
existing software that this linear algebra would take 28,500
A. Joux and R. Lercier. Improvements to the general
Diffie-Hellman to decrypt VPN traffic.
passively observing an IKE handshake.
replace the chosen
Logjam, a new attack on TLS by which a man-in-the-middle
[24]
before the handshake completes in order to forge a Finished
Pohlig-Hellman algorithm [41], which costs
Pohlig-Hellman can
We extrapolate from experiments with
again easily parallelizable.
We introduce
ments that suggests NSA may already be exploiting 1024-bit
The attacker rewrites the ServerHello response to
the attacker to recover a Diffie-Hellman shared secret after
Oakley Group 14, and 68.7% support DH-GEX.
that it is possible to create trapdoored primes [20, 44] that
around 150M rows.
However, we note
that a 1024-bit descent would take about 30 core-days, once
This is the
,
instead.
Active attacks on export ciphers in TLS.
this requires
cryptography. In NDSS, 2013.
We then examine evidence from published Snowden docu-
77.6% support the 2048-bit
ab
the server and remove other ciphersuites that could be chosen
derivation function or transport encryption,
z
using the Chinese remainder theorem.
Thus we estimate
can be quickly computed after the initial precomputation.
putation for very common fixed groups.
g
to obtain the following results:
much sieving as the RSA case would reduce the matrix to
the 1024-bit Oakley Group 2,
Backwards compatibility attacks on state-of-the-art
We find that 98.9% of SSH servers support
For a 768-bit discrete log, we can expect that ten times as
Absent a vulnerability in the key
x
In both cases, individual logs
apple:
ciphersuite accepted by
We exploit it
The main challenge is to compute the shared secret
mitigate some of the damage caused by NFS-style precom-
=
proper sieving software were available.
i
down to the smoothness bound in a few more core-days if
cover
DHE_EXPORT
range of state-level attackers.
by the Phase 1 exchange.
among practitioners deploying cryptosystems.
RSA-768 integer would take 900 core-years in total.
T. Jager, K. G. Paterson, and J. Somorovsky. One bad
connection towards the client by impersonating the server.
in April 2015.
for compatibility reasons, generating fresh groups may help
demic teams, and 1024-bit groups may plausibly be within
certain to have bootstrapped the descent, and could continue
and takes over the
we estimate that factoring an
i
[23]
and then re-
offer a corresponding
it seems to have been lost
generated
tions that must continue to use or support 1024-bit groups
scanned 1% random samples of the public IPv4 address space
cryptographers,
sizes, concluding that 768-bit groups are within range of aca-
, an active attacker can rewrite the client’s ClientHello to
implemented the SSH protocol in the ZMap toolchain and
3
e
For implementa-
At this point, we were
RFC 2409, Nov. 1998.
,
SKEYID
computes the session keys,
DHE
q
mathematical
we
optimizing for the total time,
q
the server,
Avoid fixed-prime 1024-bit groups.
attacker must at minimum recover the
sources necessary to compute discrete logs in groups of these
we reached primes of about 110 bits.
D. Harkins and D. Carrel. The Internet key exchange (IKE).
the
Provided that a client offers
known among
i
it downgrades the connection towards
dividing
[22]
In order to measure how SSH uses DH in practice,
In twice this time,
ing algorithmic improvements since 2009 into account and
algorithmic improvement.
We provide new estimates for the computational re-
Group Exchange (DH-GEX) handshake [16].
suite that the server has chosen.
so 2048-bit Diffie-Hellman will remain secure barring a major
Q
recover the session keys for the ESP or AH protocols,
sequence in Figure 2:
i
As a result, the linear algebra took 150 core-years, but tak-
secure.
most 130 bits to be descended further.
number field sieve. SIAM J. Discrete Math., 6(1), 1993.
Although this fact is well
In order to
any Diffie-Hellman instances that use a particular p.
Our implementation follows the message
the matrix that was produced had 200M rows and columns.
which can be negotiated through an auxiliary Diffie-Hellman
with
message fails to include any indication of the specific cipher-
i
times harder than for a 1024-bit group,
D. M. Gordon. Discrete logarithms in GF(p) using the
initialization took 22 core-days, yielding a few primes of at
this parameter.
[21]
the signed portion of the server’s
The cost of sieving was around 1500 core-years, and
bit Apache group.
in that group, amortizing the cost over all targets that share
For a random target in Oakley Group 2,
With sufficient precomputation, an attacker can quickly break
e
9
rations under passive eavesdropping attacks.
Group 14 (2048-bit) but also allows a server-defined group,
}
log computation.
and a descent stage that computes individual logs.
can then quickly calculate arbitrary discrete logs
discrete log cryptosystems. In Crypto, 1992.
step.
q
Critically,
and is not believed to be exploitable in standard configu-
k
and uses the most common 512-
defines support for Oakley Group 2 (1024-bit) and Oakley
group is around 10
D. M. Gordon. Designing and detecting trapdoors for
log in each subgroup of order
p
initialization, which should dominate the individual discrete
has been extensively analyzed [9, 36],
p
k
The SSH protocol explicitly
time on sieving in order to save time on the linear algebra
Precomputation for a 2048-bit non-trapdoored
ciphersuites.
DHE_EXPORT
the prime
DHE
e
that supports
abort implementation to inform our estimates for descent
The IKE protocol
[20]
part of the SSH key exchange.
for a prime
transition.
the above algorithms to compute the discrete
the 768-bit RSA factoring record spent more
VAO’s operation that support this hypothesis.
. . . q
that sits between a TLS client (web browser) and any server
use any of
Similarly,
parameters for TLS. IETF Internet Draft, May 2015.
However, an adversary who performs a large precomputation
message is identical to the message sent during standard
we experimented with our early-
Diffie-Hellman or elliptic curve Diffie-Hellman exchange as
tors should move to 2048-bit or larger groups to facilitate this
consists of a precomputation stage that depends only on
D. Gillmor. Negotiated finite field Diffie-Hellman ephemeral
The number field sieve algorithm for discrete log
one can
difficult than factoring an RSA modulus of the same size.
Server opera-
, but the structure of this
We implemented a man-in-the-middle network attacker
SSH handshakes complete either a finite field
For 1024-bit descent,
of Diffie-Hellman, there are several features of IKE and the
1
our 512-bit experiments in §3.3.
Active Attack Implementation
to decrypt VPN traffic does not by itself indicate a defeat
is known,
compared to the other steps.
All
field sieve algorithms, computing a single discrete log is more
512
2048 bits as soon as server configurations allow.
[19]
1
Figure 1:
We used this same strategy in
SSH
q
individual log
p
step has been far less studied both in theory and in practice
1024-bit. In Eurocrypt, 2007.
With state-of-the-art number
calculation to 80 core-years.
3.4
While the ability
group size to
e
message containing a 512-bit
hardware for the NFS: Another attempt to cope with
that most VPN clients only offer Oakley Group 2 by default.
x
{q
DHE
we attribute that to the fact that the descent
the subgroup order
).
computing 3,500 individual logs; the median is 70 seconds.
This reduced their linear algebra
Evidence for a discrete log attack
factors
recommend that clients raise the minimum
consistent with an efficient break for 1024-bit Diffie-Hellman.
handshake, it proceeds by issuing a signed ServerKeyExchange
mod p
factorization of
Here we show times for
W. Geiselmann and R. Steinwandt. Non-wafer-scale sieving
in practice;
50 core-years on sieving.
This coincides with our anecdotal findings
We
for a
the
This last number does not correspond to what we observed
The details of this attack are
discrete log effort tuned parameters such that they spent
b
any key exchange that uses them.
[18]
Oakley Group 2.
From a subset of
of profiled servers chose Oakley Group 1, and 63.9% chose
log after the precomputation should be multiplied by 95.
DHE_EXPORT
NIST has recommended such a transition since 2010 [4].
to recover information about exponents.
g
descent
keys for ESP session traffic.
we can quickly break
If
2005.
the record 596-bit
When a server selects
has small factors, they can be used
In comparison,
5.8%
,
export-grade primes (see Table 1),
performance computing system, which returns the symmetric
(and 1024-bit RSA) must be phased out in the near term.
log calculations.
The time complexity for each individual
Coding and Computing,
mod p
g
For IKEv2,
putation can speed up individual
it spent on sieving.
sieve. In Information Technology:
DHE
After a week-long precomputation for each of the two top
.
45M core-years.
captured IKE handshake messages being passed to a high-
a
preferred the 1024-bit Oakley Group 2.
subgroup generated by
1024-bit
and precom-
shows
DHE_EXPORT
DH-1024, we get a total cost for the precomputation of about
Individual discrete log time for 512-bit DH.
of
Improved routing-based linear algebra for the number field
reach today for moderately resourced attackers — and 66.1%
g
But if the order of the
most
As such,
W. Geiselmann, H. Kopfer, R. Steinwandt, and E. Tromer.
[50],
and
Figure 3:
Hence, for
[67]
These parallelize well
DHE
CDF of keys
value (
13
A 596-bit factorization takes about 5 core-years,
be the Pollard lambda algorithm.
[17]
the 768-bit Oakley Group 1 — which is within cryptanalytic
classified illustration published by Der Spiegel
actors.
since they have the same asymptotic behavior.
These are valid for both factorization and discrete log,
by computing the discrete log of the corresponding public
Seconds
This
sample of IKEv1 servers, 2.6% of profiled servers preferred
.
and relies on a flaw in the way TLS composes
known to decrease security, as the most efficient attack will
RFC 4419, Mar. 2006.
algebra, this tradeoff is desirable for large inputs.
Media leak. http://www.spiegel.de/media/media-35551.pdf.
within reach for state-level
The attack, which we call Logjam, is depicted in Figure 2
NSA’s VPN decryption infrastructure.
What your mother never told you about SIGDEV analysis.
)
exchange for the secure shell (SSH) transport layer protocol.
35.
In our
Our analysis suggests that 1024-bit discrete log may be
t
y, g
such exponent lengths are not
Since sieving parallelizes better than linear
1
[71]
of 1220, while space complexity will increase by a factor of
Figure 4:
M. Friedl, N. Provos, and W. Simpson. Diffie-Hellman group
algebra step.
,
b
respectively supported Oakley Group 2 (1024-bit).
confidentiality and integrity of application data.
sources.
√
0.5
increase by a factor
p
http://www.spiegel.de/media/media-35520.pdf.
,
support Oakley Group 1 (768-bit) while 86.1% and 91.0%
[16]
group, and thereby break both the
more, thus generating a smaller input matrix to the linear
sidered secure, even against an attacker with moderate re-
scale, with a target of 100,000 per hour [64].
For safe
in time
0
We found that 31.8% of IKEv1 and 19.7% of IKEv2 servers
time complexity will
a
VPN SigDev basics. Media leak.
DHE_EXPORT
less than 1024 bits should not be con-
Usenix Security, 2013.
We can reduce overall time by sieving
no longer Boolean.
[70]
x < t
omit them from the results here.
documents indicate that NSA is recovering ESP keys at large
to use a
Primes of
Fast Internet-wide scanning and its security applications. In
the total
150
2048-bit group.
relies on compromising one of the private exponents (
bits, intended to match the estimated strength of a 1024- or
http://www.spiegel.de/media/media-35527.pdf.
can find
The current best technique for attacking Diffie-Hellman
We consider these hosts “unprofiled” and
Z. Durumeric, E. Wustrow, and J. A. Halderman. ZMap:
tation,
groups.
120
The
connection
stage is many times more difficult, as the matrix entries are
bringing some within range of feasibility today.
DHE
while Pollard lambda [42]
For precompu-
VALIANTSURF – WikiInfo. Media leak.
passed to other systems for storage and analysis [69].
our source address.
and discrete log are similar, the discrete log linear algebra
are as small as 160 or 224
90
[15]
tacks when communicating with servers that still use smaller
is reinjected into TURMOIL processing infrastructure and
increase from the 768- to the 1024-bit case.
[69]
Many of these may be site-to-site VPNs that reject
x
1976.
time can downgrade a regular
groups to at least 1024 bits in order to avoid downgrade at-
effect of dramatically reducing the cost of large-scale attacks,
,
60
While the algorithms for factorization
should raise the minimum accepted size for Diffie-Hellman
cryptography. IEEE Trans. Inform. Theory, 22(6):644–654,
30
768 bits from 2009 [29].
estimated multiplicative factors by which time and space will
logs in real
posal.
From this point, decrypted VPN traffic
coded, or widely shared Diffie-Hellman parameters has the
; commonly suggested sizes for
q
http://www.spiegel.de/media/media-35517.pdf.
in software [68, 69].
Browsers and clients
record at 596 bits [8] and the integer factorization record of
W. Diffie and M. E. Hellman. New directions in
x
(sub)group of order
show how an attacker who can compute 512-bit discrete
gives us
DOI: http://dx.doi.org/10.1145/2810103.2813707.
VALIANTSURF (VS): Capability levels. Media leak.
of Amazon EC2 c4.8xlarge instances.
message regardless of our pro-
[68]
or
we base our estimates on the recent discrete log
to use primes of 2048 bits or larger.
[14]
with a short exponent
To circumvent this, we
time to compute a discrete log in any
NO-PROPOSAL-CHOSEN
N
ACM 978-1-4503-3832-5/15/10.
q
ciphersuites
x
certain primes. In Crypto, 1988.
http://www.spiegel.de/media/media-35526.pdf.
bit case,
Evaluating the formula for 768- and 1024-bit
negotiate export-grade ciphersuites.
ESP traffic is decrypted via hardware accelerators [59]
CCS’15, October 12–16, 2015, Denver, Colorado, USA.
with a
DHE
The majority of the remaining hosts responded
Once keys have been returned, the
g
For the 768-
but modern browsers never
B. den Boer. Diffie-Hellman is as strong as discrete log for
√
owner/author(s).
strategy similar to the one in [6] mentioned above.
TURMOIL VPN processing. Media leak, Oct. 2009.
were generated correctly.
Copyright is held by the
and configure
Alexa Top 1M HTTPS sites,
descent, and about three hours parallelized across 1,800 cores
Feasible with academic power
implementations use ephemeral keys
[67]
one scan.
[13]
using an early-abort
contact the Owner/Author(s).
rithms both take
http://www.spiegel.de/media/media-35528.pdf.
44.2% were willing to accept an offered proposal from at least
handshakes for about 8% of
eight days of wall-clock time on the computer used for the
232,
DHE_EXPORT
For efficiency reasons, some
DH-768:
Perspective. Springer, 2001.
until CES can respond with the recovered ESP keys if they
ization using the CADO-NFS implementation takes about
For all other uses,
Computational
algo-
should disable
The ESP traffic itself is buffered for up to 15 minutes [64],
Of the 80K hosts that responded with a valid IKE packet,
TURMOIL IPsec VPN sessionization. Media leak, Aug. 2009.
all the costs, measured or estimated, in Table 2.
DHE_EXPORT
primes can lead to an attack.
.
Server operators
For purposes of comparison, a single 512-bit RSA factor-
A
choosing such
honored.
= 1
resulting “recovered” ESP session keys [60, 61, 67].
[66]
prefer Oakley Groups 1 and 2.
We summarize
and Pollard rho [42]
efficiently break
Media leak. http://www.spiegel.de/media/media-35513.pdf.
k
and IKEv2 are a lower bound for the number of servers that
confidence, particularly for the 1024-bit case.
sieving — should bring the median time well below a minute.
The baby-step giant-step [45]
however,
R. Crandall and C. B. Pomerance. Prime Numbers:
Increase minimum key strengths.
the ability to compute discrete logs in 512-bit groups could
Copyrights for third-party components of this work must be
known PSKs and the
precomputation
In some real-life configurations,
[12]
gives
vulnerabilities described in this paper.
including a set of
TURMOIL/APEX/APEX high level description document.
Because of this, the percentages we present for IKEv1
tion on the first page.
Given the widespread use of these primes, an attacker with
effective parallelization on the middle phase or additional
practice and susceptible to attack.
our own experiments, but further work is needed for greater
for profit or commercial advantage and that copies bear this notice and the full cita-
tographic values,
possible; this is the most effective long-term solution to the
1024-bit discrete log based on the existing literature and
the Pohlig-Hellman algorithm as an attack.
block Wiedemann algorithm. Math. Comp., 62(205), 1994.
improperly generated groups are sometimes used in
[65]
Chapter 4]
Further optimizations — such as more
scans.
Active Downgrade to Export-Grade DHE
3.2
§3.5,
D. Coppersmith. Solving linear equations over GF(2) via
with at least one sufficiently large subgroup order to rule out
[2,
We recommend transitioning to elliptic curves where
also maintains a database, CORALREEF, that stores cryp-
commonly supported symmetric cipher in our single group
on the middle phase.
log db
classroom use is granted without fee provided that copies are not made or distributed
asymptotic complexity.) We attempt estimates for 768- and
http://www.spiegel.de/media/media-35522.pdf.
well;
SPIN 15 VPN story. Media leak.
we scanned with the 3DES symmetric cipher — the most
cols.
Permission to make digital or hard copies of part or all of this work for personal or
about 20 seconds for descent initialization and the remainder
VAO
as we show in
generates a group
many published estimates are crude extrapolations of the
about 89,000 servers with browser-trusted certificates.
[11]
g
Discrete log descent has a complexity of the same form as
This is divided between
being standardized by the IRTF for use in Internet proto-
When measuring server preference,
[64]
required to generate the ESP session key [61, 62, 67].
However,
critically, the common practice of using standardized, hard-
PKC, 2006.
We found it in use by
gone to understanding 1024-bit factorization, but, even there,
are not necessarily vulnerable, as long as
(Much more attention has
9615.
from 34 to 206 seconds (see Fig. 3).
Oakley Groups 1 and 2.
.
algebra
introduced in version 2.3.0 in 1999.
politics/23nsa-sigint-strategy-document.html.
discrete logarithm problem with the number field sieve. In
More
Ridge National Laboratory, which perform the computation
are
These groups
individual logs took about 70 seconds, but the time varied
A. Commeine and I. Semaev. An algorithm to solve the
.
q
such as Curve25519,
located at NSA Headquarters and in a data center at Oak
It was
http://www.nytimes.com/interactive/2013/11/23/us/
characteristics.
support for obsolete 1990s-era export-grade crypto.
variety of DH groups, with the lowest priority groups being
a collection of high-performance grid computing resources
[10]
.
SIGINT strategy. Media leak.
or 2
we offered servers a
.)
computational
On average, computing
and new curves,
of servers use weak Diffie-Hellman parameters or maintain
= 0
signature-based key-exchange protocol. In Crypto, 2002.
k
going scrutiny,
First, a surprising number
,
p
[63]
E5-2699 CPUs and 128 GB of RAM.
To detect default behavior,
specialized VPN Attack Orchestrator (VAO) system manages
sieving and linear algebra steps, which have very different
mod_ssl
There are two reasons for this.
Within CES, a
when using
http://www.spiegel.de/media/media-35519.pdf.
of this function, i.e., the same function, taking
R. Canetti and H. Krawczyk. Security analysis of IKE’s
complexity of parameter tuning and to tradeoffs between the
We ran the server on a machine with two 18-core Intel Xeon
q
we also found 9 composite
question.
These curves are under-
due in part to the
subgroups have order 2,
[9]
Services (CES) [56, 65] via a secure tunnel.
it frequently offers less security than widely believed.
(Incidentally,
sieving in C, and the final discrete log is deduced in Python.
DHE_EXPORT
known or suspected weaknesses.
POISONNUT – WikiInfo. Media leak.
plexity (the size of the matrix in memory) is the square root
we offered only the single group in
[62]
default used for
groups,
suspicion due to NSA influence on their design, despite no
of ESP ciphertext to NSA’s Cryptanalysis and Exploitation
180 decimal digits, 2014. http://caramel.loria.fr/p180.txt.
key sizes is far from straightforward,
2 was composite.
, so that the only possible
The first and second stages are parallelized and run
The space com-
and deployed with these protocols and find that, in practice,
and C.
http://www.spiegel.de/media/media-35533.pdf.
New record for discrete logarithm in a prime finite field of
We examine how Diffie-Hellman is commonly implemented
q
for individual
Estimating the cost for discrete log cryptanalysis at longer
parameters, those specified by NIST, are now viewed with
complete IKE handshake and may transmit a small amount
/
The second most popular 512-bit prime is the
and linear algebra in the precomputation.
Unfortunately, the most widely supported ECDH
mechanism in SSH and IPsec and a popular option in TLS.
log and factorization, which are both dominated by sieving
certificates.
linear
C. Bouvier, P. Gaudry, L. Imbert, H. Jeljeli, and E. Thomé.
1)
TURMOIL transmits the
LONGHAUL – WikiInfo. Media leak.
We implemented the descent calculation in a mix of Python
Scaling NFS to 768- and 1024-bit DH
for some prime
To test support
p −
q
sieving
[8]
found it in use by about 564,000 servers with browser-trusted
in RAM and returns logs for values passed to it by clients.
923, describes the overall time for both discrete
so,
It is the main key exchange
groups) and which group servers prefer.
are faster.
[61]
4.1
access to VPN, SSH, and TLS traffic.
2010. http://www.spiegel.de/media/media-35515.pdf.
The server maintains the precomputed data
If
in “mod p” Diffie-Hellman, and shared-secret computations
4,800 were not safe, meaning that (
built-in
session keys in Internet protocols.
.
We
Security and Privacy, 2015.
1 = 2
In addition, ECDH keys are shorter than
Groups 1 and 2 (two popular 768- and 1024-bit,
any tasked selector [65].
was used until 2.4.7, which disabled export ciphersuites.
composite state machines of TLS. In IEEE Symposium on
p −
Diffie-Hellman key exchange is widely used to establish
Intro to the VPN exploitation process. Media leak, Sept.
primes seen across both export and non-export TLS scans,
= 1
on unanswered questions about how NSA may be gaining
saging library.
Introduced in 2005 with Apache 2.1.5, it
[60]
precomputation.
We believe that this analysis may help shed light
approximately 70,000 distinct
k
that
mented a client-server architecture using the ZeroMQ mes-
ESP payloads and determining whether the traffic matches
INTRODUCTION
the ZMap UDP probe module to measure support for Oakley
Taming the
Out of
with
In order to save time on individual computations, we imple-
an advantage from
The initial phases of the attack involve collecting IKE and
1.
We used
implementations use “safe” primes, which have the property
sions of Apache.
Zinzindohoue. A messy state of the union:
or AES.
http://www.spiegel.de/media/media-35509.pdf.
other proposed explanations, such as novel breaks on RC4
Innov8 experiment profile. Media leak.
To avoid this, most
crete logs in about a minute for targets in each of these groups.
uses “safe” primes.
methods should be a priority for the Internet community.
This complexity formula,
most popular 512-bit prime was hard-coded into many ver-
initiate an IPsec VPN connection) in May 2015.
C. Fournet, M. Kohlweiss, A. Pironti, P.-Y. Strub, and J. K.
of information through the TURMOIL system
strong curves do not gain as much of
[59]
matches the known capabilities more closely than
Current elliptic curve discrete log algorithms for
small or has many small prime factors.
address space for IKEv1 and IKEv2 (the protocols used to
Not every TLS server
We conclude that moving to stronger key exchange
follows a similar distribution with longer primes.) The
B. Beurdouche, K. Bhargavan, A. Delignat-Lavaud,
nent can hide polynomial factors.
excerpt from one of the documents [67], illustrates the flow
able to run the final descent step to compute individual dis-
http://www.spiegel.de/media/media-35514.pdf.
are practical even for large primes when the group order is
can result in devastating attacks.
indeed,
an
a break.
attacks.
DSA primes with q of 160 bits, this should be divided by 6.4 for 1024 bits, 4.8 for 768 bits, and 3.2 for 512 bits.
DHE
[7]
practice by scanning a 1% random sample of the public IPv4
Once this precomputation was finished, we were
attacks on VPNs are consistent with having achieved such
in Cryptography, 2014.
. (Non-export
We measured how IPsec VPNs use Diffie-Hellman in
GALLANTWAVE@scale. Media leak.
algorithms runs in time exponential in group order, and they
Descent
. For linear algebra, all costs for DH are for safe primes; for
Figure 4,
the intelligence community’s cryptanalytic capabilities, and,
known feasible cryptanalytic
generate Diffie-Hellman primes according to best practices
IKE
close reading of published NSA leaks shows that the agency’s
logs for the descent occupies about 2.5 GB in ASCII format.
DHE_EXPORT
A different family of
D. J. Bernstein and T. Lange. Batch NFS. In Selected Areas
I
this hypothesis is consistent with the published details of
man-in-the-middle attacks on IPsec or IKE.
Failure to
priate parameters avoids all
[58]
Each resulting database of known
for a small number of common 1024-bit groups.
We show that
http://cryptome.org/2013/08/spy-budget-fy13.pdf.
trusted certificates that support
Improperly generated groups
and the sieving region parameter
[6]
tic curve Diffie-Hellman (ECDH) key exchange with appro-
A
Attacks on composite-order subgroups
eavesdropping and does not require message injection or
attacker who had the resources to invest in precomputation
of traffic to 66% of IPsec VPNs and 26% of SSH servers.
slightly over one week.
Transitioning to ellip-
B
FY 2013 congressional budget justification. Media leak.
indicates that this decryption is performed using passive
, and 92.5% of all servers with browser-
to perform an effective man-in-the-middle attack on TLS.
http://cr.yp.to/factorization/smoothparts-20040510.pdf.
has already implemented such a capability.
.
and a second group would allow decryption
DHE_EXPORT
D. J. Bernstein. How to find smooth parts of integers, 2004.
DHE
to evaluate the hypothesis that the National Security Agency
The evidence
allows us to quickly compute 512-bit discrete logs in order
Transition to elliptic curves.
[57]
bits of the smoothness bound
would be subject to widespread compromise by a state-level
In total, the wall-clock time for each precomputation was
mainstream Internet protocols.
HTTPS sites,
at least a factor of three.
that is used to collect and decrypt VPN traffic.
Media leak. http://www.spiegel.de/media/media-35529.pdf.
support
the number of
as they are commonly used,
[5]
In §3.3, we show how exploiting these tradeoffs
The website no longer supports
cently published documents leaked by Edward Snowden [46]
lished by Der Spiegel describe a system named TURMOIL
bit primes account for 92.3% of Alexa Top 1M domains that
Management, 2007.
cover the expected security of Diffie-Hellman as it is used in
we apply this new understanding to a set of re-
computation.
step easier.
indicate that these protocols,
For sieving, we give two important parameters:
group would allow passive eavesdropping on 18% of popular
End-to-end VPN SPIN 9 design review.
We expect that optimizations could bring this cost down by
In this section, we present concrete recommendations to re-
Finally,
Our measurements
.
The documents pub-
descent
Fielded capability:
As shown in Table 1, just two 512-
of servers; performing precomputation for a single 1024-bit
Recommendation for Key
was the third group for which we performed the NFS pre-
corresponding to 60,000 core-hours.
more work in the precomputation makes the final
number of fixed or standardized groups are used by millions
IKE, SSH, and HTTPS.
which
finished in 120 hours,
Estimating costs for factoring and discrete log
suites — may have actually reduced security for many hosts.
have long been embedded in standards and implementations.
Publication 800-57:
one of a handful of primes.
NSA’s VPN exploitation process
[56]
NIST Special
to sunset the use of fixed 1024-bit Diffie-Hellman groups that
used the default 512-bit DH group from OpenSSL,
offering “perfect forward secrecy” over RSA-based cipher-
lar protocols:
Diffie-Hellman parameters, the overwhelming majority use
http://www.spiegel.de/media/media-35671.pdf.
a smaller matrix, making linear algebra cheaper, and doing
Table 2:
A small
the computation
the optional Phase 2 Diffie-Hellman exchange.
While the TLS protocol allows servers to generate their own
For example, sieving more will result in
Est. based on complexity formula and our experiments.
E. Barker, W. Barker, W. Burr, W. Polk, and M. Smid.
),
Until April 2015, this server
DHE-based TLS ciphersuites
and the result of
the impact of a hypothetical DH-1024 break on three popu-
APEX active/passive exfiltration. Media leak, Aug. 2009.
putations are plausible given nation-state resources.
our measurements also indicate that it may be very difficult
[55]
we use Internet-wide scanning to assess
We estimate that even in the 1024-bit case, the com-
.
expense of others.
[4]
nonces,
p
test connections to www.fbi.gov.
surveillance — promotion of
Unfortunately,
flexibility to reduce time on some computational steps at the
the most common Diffie-Hellman parameters.
additional
30 days
DHE_EXPORT
in finite fields of small characteristic. In Eurocrypt, 2014.
connections and used it to decrypt
(
tions from security experts in response to the threat of mass
groups.
In this section,
https://gforge.inria.fr/projects/ecm.
P. Zimmermann et al. GMP-ECM, 2012.
Effects of a 1024-bit Break
the key recommenda-
and 4.9%
heuristic quasi-polynomial algorithm for discrete logarithm
DHE
selection
We go on to consider Diffie-Hellman with 768- and 1024-bit
GF
,
35,000,000
used to attack millions of hosts, due to widespread reuse of
the algorithm allow some
dropper for regular
browsers are being changed to reject short groups.
4.3
The numerous parameters of
of equal size, we observe that a one-time investment could be
R. Barbulescu, P. Gaudry, A. Joux, and E. Thomé. A
Our findings indicate that one of
5.2B
SKEYID
DHE
for linear algebra over
[54]
10,000,000
NFS [1]
[3]
devcentral.f5.com/articles/ssl-profiles-part-5-ssl-options.
we implemented a passive eaves-
the precomputation in practice.
certificates, 23.9% supported
1024-bit group is several times higher than for an RSA key
RECOMMENDATIONS
derived from
non-compromised devices.
In response, major
40
approach, which appears to succeed across a broad swath of
5.
corps finis. PhD thesis, Université de Lorraine, France, 2013.
to 7% of Alexa Top Million HTTPS sites.
Although the cost of the precomputation for a
Of 14.3 million IPv4 HTTPS servers with browser-trusted
is
232) [2], which is much cheaper than
SSL options, 2013. https://
Using the unoptimized implementation from CADO-
As a proof-of-concept,
ful attackers.
a single 512-bit group, allowing us to compromise connections
KEYMAT
ciphersuite.
19
= 6.
R. Barbulescu. Algorithmes de logarithmes discrets dans les
IMAPS, and 454K POP3S servers.
.
.
J. Wagnon. SSL profiles part 5:
a pure cryptographic attack is the generality of the VAO
can hijack connections to approximately 1.6M SMTP, 429K
the vulnerability of their key exchanges to attacks by resource-
DHE
The most compelling argument for
We find that 82% of vulnerable servers use
DH-1024
1
DHE_EXPORT
[53]
n
[2]
Ultimately,
downgrade attack of §3.3, an attacker with modest resources
additional round of Diffie-Hellman.
,
Wiedemann algorithm [11, 49] with parameters m = 18 and
choose a vulnerable
in about a minute.
algorithm, 2014. Release 2.1.1.
and 8.4% supported
In 2nd Usenix Workshop on Electronic Commerce, 1996.
attack described above.
net security protocols — IKE, SSH, and TLS — to determine
Est. based on complexity formula.
this phase includes an
thus appears to be an alternative mechanism to the VAO
group, we can compute arbitrary discrete logs in that group
downgrade attack, an active attacker can force the server to
D. Wagner and B. Schneier. Analysis of the SSL 3.0 protocol.
In light of these results, we examine several standard Inter-
120,000
3
Using our
DHE
cado-nfs, an implementation of the number field sieve
We used the block
[52]
DHE_EXPORT
68.3% supported
A. Kruppa, F. Morain, E. Thomé, and P. Zimmermann.
8.7B
per node, connected with Infiniband FDR.
After a week-long precomputation for a specified 512-bit
close to real time.
/
SMTP, 276K IMAPS, and 245K POP3S servers.
In some circumstances,
the resulting traffic does not require IKE handshakes, and
would be fast enough to break individual key exchanges in
we implement the number field sieve discrete log algorithm.
(AH) [26].
S. Bai, C. Bouvier, A. Filbois, P. Gaudry, L. Imbert,
539,000 HTTPS sites among Top 1M domains, we found that
key agreement with short exponents. In Eurocrypt, 1996.
however, the same documents also note that decryption of
. In this case, as in the
this would affect approximately 1.7M
(1
a 36-node cluster with two 8-core Intel Xeon E5-2650 CPUs
1,000,000
To carry out this attack,
targeted malware is a piece of the collection strategy [60];
p
Of
were compromised,
P. C. Van Oorschot and M. J. Wiener. On Diffie-Hellman
42
any specific discrete log instance within a common group —
lating Security Payload (ESP) [27] or Authenticated Header
[1]
We solved the corresponding linear system on
DHE
If each of the top ten 1024-bit primes used by each protocol
L
[51]
server not selecting
row on average.
All others are passive attacks.
protocol used to protect subsequent traffic, such as Encapsu-
REFERENCES
to “export-grade” Diffie-Hellman.
in the 1024-bit case, the descent time — necessary to solve
The scans took place in March 2015.
18
logarithms. In ACM CCS, 1994.
8.
in TLS that lets a man-in-the-middle downgrade connections
and later to
1024-bit primes accounting for only 4.8% of servers.
RSA-1024
2,157,378 rows and columns, with 113 nonzero coefficients per
For HTTPS, we provide figures with and without downgrade attacks on the chosen ciphersuite.
when the client’s ordering of ciphersuites would result in the
Top 1M domains.
We further show that even
for a cryptographic transport
442) [10],
world servers for which typical connections could be compromised by attackers with various levels of computational resources.
Est. based on [8, 29] and our own experiments.
we obtained a square matrix with
, but with the ten most common
experiments used UCS hardware donated by Cisco.
search with application to hash functions and discrete
,
First, we present Logjam, a novel flaw
An active attack may still be necessary
space and the Alexa
known in the academic literature.
public IPv4 address
P. C. Van Oorschot and M. J. Wiener. Parallel collision
DHE
From this data set,
for the connection.
and several other universities and organizations; additional
than widely believed.
.
require any major algorithmic improvements beyond what is
KEYMAT
We use Internet-wide scanning to estimate the number of real-
).
both the full
would likely require special-purpose hardware, but would not
and 74.9% supporting
and key material,
2 days
1
[50]
compute the discrete log and obtain the TLS session keys
used in popular Internet protocols and find it to be less secure
Estimated impact of Diffie-Hellman attacks.
testbed, which is supported by INRIA, CNRS, RENATER,
,
We investigate the security of Diffie-Hellman key exchange as
ciphersuites and scanned TCP/443 on
Phase 2 establishes the parameters
Some experiments were conducted using the Grid’5000
The precomputation
28,500
algorithm. J. Symbolic Comput., 33(5):757–775, 2002.
with one of these servers, a passive eavesdropper can later
DHE_EXPORT
Table 3:
27
of at most 27 bits (hence bound B from §2 is 2
the resources of state-level attackers.
DHE_EXPORT
3
ABSTRACT
a Phase 2 handshake.
ship.
polynomials and improvement of the block Wiedemann
150M
3,600,000 (25.7%)
ciphersuite
servers supporting
which 28,372,442 were unique, involving 15,207,865 primes
For additional materials and contact information, visit WeakDH.org.
E. Thomé. Subquadratic computation of vector generating
number of 1024-bit groups is plausibly within
DHE
with 8.9% of
is used to encrypt and authenticate
and
ship, and by an Alfred P. Sloan Foundation Research Fellow-
8,000
/
University of Michigan
[49]
SKEYID
for a small
This sufficed to collect 40,003,519 relations of
3,600,000 (25.7%)
(1
Morris Wellman Faculty Development Assistant Professor-
35
is similar,
If a browser negotiates a
DHE
computational resources, and performing precomputations
–
¶
17
be unnecessary.
The resulting
Hellman, we modified the ZMap [15] toolchain to offer
19a7f19686bcdbd689c6fbea31f68a276e62d886/stud.c#L593.
core-hours.
p
POP3S deployment
the Google Ph.D. Fellowship in Computer Security, by the
https://github.com/bumptech/stud/blob/
DH-768
active attacks may
.
primes account for only 5.4% of servers.
relatively widespread use, are now within reach for academic
by
L
corresponding to 21,400
Johns Hopkins
–
To understand how HTTPS servers in the wild use Diffie-
§
by a gift from Supermicro,
The scalable TLS unwrapping daemon, 2012.
ciphersuites.
SSH IPv4
improved the complexity of descent to
. However, the ten most common 1024-bit
SKEYID
Est. based on [29] with less sieving.
Sieving ran for 15 hours,
As we argue below, 768-bit groups, which are still in
In these instances,
stud:
DHE
More recent analyses have
the derivation of
100
hours.
DHE_EXPORT
University of Pennsylvania
726,000 (63.9%)
by the Mozilla Foundation,
.
groups.
safe because most modern TLS clients do not offer or accept
726,000 (63.9%)
[48]
number field sieve for discrete log scales to 768- and 1024-bit
75% supported
this value is incorporated into
DHE
for about 3 hours, which in total corresponds to 7,600 core-
250M
Research Fellowship Program under grant DGE-1256260,
‡
mance of the NFS for discrete logs.
authenticated with a PSK,
by the NSF Graduate
This has been considered
800
Microsoft Research
and
To answer this question we must first examine how the
66,000 (5.8%)
non-export
http://www.sagemath.org.
this may have contributed to misconceptions about the perfor-
selection ran
–
DHE_EXPORT
plexity of this step would equal that of the precomputation;
including symmetric pre-shared keys (PSK); when IKEv1 is
Polynomial
search grant ANR-12-BS02-001-01,
.
Top 1M domains) that used 512-bit or weaker primes for
k
and when applied with stronger groups?
The Sage Development Team, 2015.
37
16
by the French ANR re-
Sandy Bridge.
servers with browser-trusted certificates (and 118 in the
as used in other protocols that do not suffer from downgrade,
IKE provides several authentication mechanisms,
DHE_EXPORT
W. Stein et al. Sage Mathematics Software (Version 6.5).
technical difficulties with descent and reported that the com-
IKEv2 IPv4
For IMAPS, 8.4% of servers supported
INRIA Nancy-Grand Est, CNRS, and Université de Lorraine
Early articles (e.g. [21]) encountered
1,690,000 (66.1%)
CPUs were Intel
1024-bit groups.
Starting Grant 259639 (CRYSP),
We found 2,631
[47]
†
how secure is Diffie-Hellman in broader practice,
RSA-768
group for legacy
.
DHE
INRIA Paris-Rocquencourt
by the ERC
15.5% of SMTP servers used one of the ten most common
For the computations in this paper; may be suboptimal.
SKEYID
.
key exchanges and a 512-bit
1,690,000 (66.1%)
idle time on 2000–3000 CPU cores in parallel, of which most
question:
inside-the-nsa-s-war-on-internet-security-a-1010361.html.
∗
512-bit primes in non-export
In this section we address the following
http://www.spiegel.de/international/germany/
Research under contract N00014-11-1-0470,
ciphers.
64,700 (2.6%)
B
we used
DHE
to derive a value called
10 mins
of unsafe parameters.
–
such as nonces and cookies,
1024-bit group for regular
issues in the DHE configurations used by TLS servers.
Naval
DHE_EXPORT
security. Der Spiegel, Dec 2014.
smoothness bound
selection and sieving steps,
†
IKEv1 IPv4
Paul Zimmermann
and 14.8% supported
the
7.7
side,
For the polynomial
Inside the NSA’s war on Internet
a strong
In our scans, we found several other exploitable security
downgrade connections to export-grade crypto or on the use
by the Office of
importantly,
Other Weak and Misconfigured Groups
However, these attacks rely on the ability to
2.1M
and EFRI-1441209,
TLS servers are still configured with two groups:
1,430,000 (10.0%)
sieving is much easier to parallelize than linear algebra.
polynomial
k
is combined with other cleartext values transmitted by each
Spiegel Staff. Prying eyes:
,
3.5
939,000 (6.56%)
Santiago Zanella-Béguelin
Many
used by TLS.
p
2.5
DHE
CNS-1518741,
most
The shared secret
yield a smaller linear algebra step, which is desirable because
[46]
ported
servers maintain support for backwards compatibility.
¶
CNS-1409505,
46,700 (0.3%)
Second, more sieving relations also
27
genera. In Proc. Sympos. Pure Math., volume 20. 1971.
information, such as passwords and cookies.
cal attacks against Diffie-Hellman key exchange as currently
and,
key exchange to establish a shared secret.
,
Foundation under contracts CNS-1345254,
15
D. Shanks. Class number, a theory of factorization, and
restrictions are no longer in effect, but many libraries and
from a small set of standardized parameters and perform a
The previous sections demonstrate the existence of practi-
41.4% sup-
makes the descent faster.
1,000 (0.0%)
sent by a browser often contains sensitive user authentication
Eric Wustrow
which the client and server select a Diffie-Hellman group
in part upon work supported by the U.S. National Science
We note that this initial data
we eventually obtain a larger database of known logs, which
I
DH-512
¶
,
. The relevant export
STATE-LEVEL THREATS TO DH
HTTPS Trusted
[45]
finite prime fields. Math. Comp., 71(237):363–377, 2002.
sieving region parameter
4.
first, with more relations obtained from sieving,
Timings with default CADO-NFS parameters.
False Start payload at leisure.
This material is based
in
Benjamin VanderSloot
3,410,000 (23.8%)
DHE
STARTTLS
0.33
, the
Each IKE session begins with a Phase 1 handshake,
and serves as a cautionary tale for programmers.
‡
SMTP servers supported
protocol messages are identical to
man-in-the-middle can record the handshake and decrypt the
Martin Thomson, and Eric Rescorla.
I. A. Semaev. Special prime numbers and discrete logs in
mizations:
1,840,000 (12.8%)
In these cases, a
50.7% of
Luke Valenta
4.3M
f
Andrei Popov, Ivan Ristic, Edward Snowden, Brian Smith,
DHE_EXPORT
556,000 (3.9%)
This enabled two opti-
brevity, we will use IKEv1 terminology.
[44]
misconfiguration bug results in a significant loss of security
other respects,
489,000 (3.4%)
For the sake of
.
†
this
by tuning many parameters, including the degree of
0.5
We found that
sieved more than strictly necessary.
57(2):140–147, 2005.
Ron Dreslinski, Tanja Lange, Adam Langley, Kenny Paterson,
This is obtained
The authors wish to thank Michael Bailey, Daniel Bernstein,
In all
HTTPS Trusted w/ active downgrade
29
DHE
sage structure but are conceptually similar.
O. Schirokauer. Virtual logarithms. J. Algorithms,
for IMAPS, POP3S, and SMTP+StartTLS.
For this precomputation, we deliberately
Still,
Emmanuel Thomé
which differ in mes-
¶
We studied 1% samples of the public IPv4 address space
longer than 512 bits.
exponent.
14
.
linear algebra steps.
Acknowledgments
132,000 (24.0%)
dows 10) send False Start data with
[43]
this does not suffice to recover a full
Firefox 35, Chrome 41, and Internet Explorer (Win-
Mathematics, 15(3):331–334, 1975.
for keeping future systems secure.
putation phase includes the polynomial selection, sieving, and
ciphersuites that were restricted to primes no
to fetch received mail, wrap the entire connection in TLS.
Drew Springall
98,500 (17.9%)
RSA-512
and IKEv2 [25],
‡
Numerical
core-time
versions.
As illustrated in Figure 1, the precom-
2/3
ilous gap that separates these communities will be essential
IKEv1 [22]
DHE_EXPORT
POP3S and IMAPS, used by end users
407 (0.1%)
,
Bridging the per-
command.
Start, but their policies on when to enable it vary between
the server’s Finished message.
Precomputation
versions,
p
Nadia Heninger
(log log p)
118 (0.0%)
J. M. Pollard. A Monte Carlo method for factorization. BIT
The times were about the same for each prime.
STARTTLS
[42]
HTTPS Top 1M
with standards efforts and software review.
There are two
¶
of Chrome, Internet Explorer, and Firefox implement False
-bit
core-years
application data that some TLS clients send before receiving
1/3
exp (1.923 + o(1))(log p)
crypto is actually being applied, such as through engagement
significance (corresp.). Trans. Inform. Theory, 24(1), 1978.
Recent versions
below.
J. Alex Halderman
309,000 (56.1%)
n
tablishment protocol used for IPsec VPNs.
rows
refers to False Start [30]
allows a connection to be upgraded to TLS by issuing the
§
384) for
for the server’s Finished message to arrive.
core-years
computing logarithms over GF(p) and its cryptographic
servers,
) =
Internet Key Exchange (IKE) is the main key es-
tographers, for their part, should involve themselves in how
We list the runtime for each stage of the computation
fs
205,000 (37.1%)
Cryp-
,
IKE
45,100 (8.4%)
Data
onds.
S. C. Pohlig and M. E. Hellman. An improved algorithm for
used to relay messages between mail
Matthew Green
B
1/3
application data (such as an HTTP request) without waiting
reduces connection latency by having the client send early
read or modify the contents.
45,100 (8.4%)
for being aware of applicable cryptanalytic attacks.
precomputation to calculate discrete logs at scale.
2
9)
the protocol
after which computing individual logs took a median of 70 sec-
[41]
†
2
/
System builders should take responsibility
n/
tion to evaluate the hypothesis that the NSA is leveraging
HTTPS Top 1M w/ active downgrade
This extension
crete log, the attacker can learn the session key and arbitrarily
log
Precomputation took 7 days for each prime,
Pierrick Gaudry
RFC 2412, Nov. 1998.
SMTP,
key establishment works, we will use the published informa-
¶
ten 1024-bit groups
. Then, by finding the 512-bit dis-
(64
more effectively.
(
TLS is also used to secure email transport.
supports the TLS False Start extension [30].
shown in Table 1.
I
H. Orman. The Oakley key determination protocol.
phers and creators of practical systems need to work together
break the confidentiality of user requests if the client
DHE_EXPORT
Descent
[40]
primes
max
Zakir Durumeric
After reviewing how IPsec
Mail
,
A key lesson from this state of affairs is that cryptogra-
still
primes is sohu.com (ranked 31st globally).
3
one 1024-bit group
length
https://www.olcf.ornl.gov/titan.
DHE_EXPORT
∗
the attack system architecture.
that allows
generates exponents of
force TLS clients to use export-strength DH with any server
/
exchanges that use a few small, widely shared groups.
analytic techniques used, but they do provide an overview of
ciphersuite using one of the two most common 1024-bit
512-bit primes, including the top two
Oak Ridge National Laboratory. Introducing Titan, 2012.
Karthikeyan Bhargavan
, the attacker can
all 768-bit groups
(1
DHE
¶
all 512-bit groups
The documents do not describe the crypt-
sieve discrete log algorithm from §2 and applied it to three
[39]
A man-in-the-middle can
Luckily, since the provider
of Internet communication depends on Diffie-Hellman key
b
David Adrian
p
The Logjam attack.
Linear Algebra
Vulnerable servers, if the attacker can precompute for . . .
operations.
outs and servers do not reuse values for
phers did not appreciate that the security of a large fraction
The most popular site that negotiates a
significant scale.
Digital signature standard, 2013.
We modified CADO-NFS [1] to implement the number field
NIST. FIPS PUB 186-4:
Sieving
Even when clients enforce shorter time-
512-bit Discrete Log Computations
1024-bit prime.
How Diffie-Hellman Fails in Practice
40
cate that NSA is passively decrypting IPsec connections at
Likewise, many cryptogra-
L
Figure 2:
TLS False Start.
Imperfect Forward Secrecy:
The running time of this algorithm is
understood by system builders.
Classified documents published by Der Spiegel [46] indi-
[38]
3.3
passively eavesdropped given the precomputation for a single
a cost of roughly 2