TLS False Start. Even when clients enforce shorter timeouts and servers do not reuse values for b, the attacker can
still break the confidentiality of user requests that use TLS
False Start. Recent versions of Chrome, Internet Explorer,
and Firefox implement False Start, but their policies on
when to enable it vary. Firefox 35, Chrome 41, and Internet
Explorer (Windows 10) send False Start data with DHE.
In these cases, a man-in-the-middle can record the handshake and decrypt the False Start payload at leisure.
4. NATION-STATE THREATS TO DIFFIE-HELLMAN
The previous sections demonstrate the existence of practical attacks against Diffie-Hellman key exchange as currently
used by TLS. However, these attacks rely on the ability to
downgrade connections to export-grade cryptography. In
this section we address the following question: how secure
is Diffie-Hellman in broader practice, as used in other protocols that do not suffer from downgrade, and when applied
with stronger groups?
To answer this question we must first examine how the
number field sieve for discrete logarithms scales to 768-
and 1024-bit groups. As we argue below, 768-bit groups in
relatively widespread use are now within reach for academic
computational resources. Additionally, performing precomputations for a small number of 1024-bit groups is plausibly within the resources of nation-state adversaries. The
precomputation would likely require special-purpose hardware, but would not require any major algorithmic improvements. In light of these results, we examine several standard
Internet security protocols — IKE, SSH, and TLS — to determine their vulnerability. Although the cost of the precomputation for a 1024-bit group is several times higher than for an
RSA key of equal size, a one-time investment could be used
to attack millions of hosts, due to widespread reuse of the
most common Diffie-Hellman parameters. Finally, we apply
this new understanding to a set of recently published documents to evaluate the hypothesis that the National Security
Agency has already implemented such a capability.
4. 1. Scaling NFS to 768- and 1024-bit Diffie-Hellman
Estimating the cost for discrete logarithm cryptanalysis at
larger key sizes is far from straightforward due to the complexity of parameter tuning. We attempt estimates up to
1024-bit discrete logarithm based on the existing literature
and our own experiments but further work is needed for
greater confidence. We summarize all the costs, measured
or estimated in Table 2.
DH-768: done in 2016. When the ACM CCS version of this
article was prepared, the latest discrete logarithm record
was a 596-bit computation. Based on that work, and on prior
experience with the 768-bit factorization record in 2009, 12
we made the conservative prediction that it was possible, as
explained in Section 2, to put more computational effort into
sieving for the discrete logarithm case than for factoring, so
that the linear algebra step would run on a slightly smaller
matrix. This led to a runtime estimate of around 37,000 core-years, most of which was spent on linear algebra.
This estimate turned out to be overly conservative, for several reasons. First, there have been significant improvements in our software implementation (Section 3. 3). In
addition, our estimate did not use the Joux-Lercier alternative polynomial selection method, 11 which is specific
to discrete logarithms. For 768-bit discrete logarithms,
this polynomial selection method leads to a significantly
smaller computational cost.
In 2016, Kleinjung et al. completed a 768-bit discrete logarithm computation. 13 While this is a massive computation
on the academic scale, a computation of this size has likely
been within reach of nation-states for more than a decade.
This data is mentioned in Table 2.
DH-1024: Plausible with nation-state resources. Experimentally extrapolating sieving parameters to the 1024-bit
case is difficult due to the trade-offs between the steps of
the algorithm and their relative parallelism. The prior work
proposing parameters for factoring a 1024-bit RSA key is
thin, and we resort to extrapolating from asymptotic complexity. For the number field sieve, the complexity is exp
((k + o( 1))(log N)1/3(log log N)2/3 ), where N is the integer to
factor or the prime modulus for discrete logarithm and k is
an algorithm-specific constant. This formula is inherently
imprecise, since the o( 1) in the exponent can hide polynomial factors. This complexity formula, with k = 1.923,
describes the overall time for both discrete logarithm and
factorization, which are both dominated by sieving and linear algebra in the precomputation. Evaluating the formula
for 768- and 1024-bit N gives us estimated multiplicative factors by which time and space will increase from the 768- to
the 1024-bit case.
Table 2. Estimating costs for factoring and discrete loge.
Sieving Linear Algebra Descent
Log2 B Core-years Rows Core-years Core-time
RSA-512 29 0.3 4.2mn 0.03 Timings with default CADO-NFS parameters.
DH-512 27 2. 5 2.2mn 1. 1 10min For the computations in this paper; may be suboptimal.
RSA-768 37 800 250mn 100 Est. based on Kleinjung and Aoki et al. 12 with less sieving.
DH-768 36 4,000 24mn 920 43hrs Data from, Kleinjung and Diem et al. 13, Table 1.
RSA-1024 42 ≈ 1,000,000 ≈ 8.7bn ≈ 120,000 Crude estimate based on complexity formula.
DH-1024 40 ≈ 5,000,000 ≈0.8bn ≈ 1, 100,000 30 days Crude estimate based on formula and our experiments.
e For sieving, we give one important parameter, which is the number of bits of the smoothness bound B. For linear algebra, all costs for DH are for safe primes; for Digital Signature
Algorithm (DSA) primes with group order of 160 bits, this should be divided by 6. 4 for 1024 bits, 4. 8 for 768 bits, and 3. 2 for 512 bits.