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