Hubbry Logo
Logjam (computer security)Logjam (computer security)Main
Open search
Logjam (computer security)
Community hub
Logjam (computer security)
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Logjam (computer security)
Logjam (computer security)
Logjam (computer security)
View on Wikipedia
from Wikipedia

Logjam is a security vulnerability in systems that use Diffie–Hellman key exchange with the same prime number. It was discovered by a team of computer scientists and publicly reported on May 20, 2015.[1] The discoverers were able to demonstrate their attack on 512-bit (US export-grade) DH systems. They estimated that a state-level attacker could do so for 1024-bit systems, then widely used, thereby allowing decryption of a significant fraction of Internet traffic. They recommended upgrading to at least 2048 bits for shared prime systems.[2][3][4]

Details

[edit]

Diffie–Hellman key exchange depends for its security on the presumed difficulty of solving the discrete logarithm problem. The authors took advantage of the fact that the number field sieve algorithm, which is generally the most effective method for finding discrete logarithms, consists of four large computational steps, of which the first three depend only on the order of the group G, not on the specific number whose finite log is desired. If the results of the first three steps are precomputed and saved, they can be used to solve any discrete log problem for that prime group in relatively short time. This vulnerability was known as early as 1992.[5] It turns out that much Internet traffic only uses one of a handful of groups that are of order 1024 bits or less.

One approach enabled by this vulnerability that the authors demonstrated was using a man-in-the-middle network attacker to downgrade a Transport Layer Security (TLS) connection to use 512-bit DH export-grade cryptography, allowing them to read the exchanged data and inject data into the connection. It affects the HTTPS, SMTPS, and IMAPS protocols, among others. The authors needed several thousand CPU cores for a week to precompute data for a single 512-bit prime. Once that was done, however, individual logarithms could be solved in about a minute using two 18-core Intel Xeon CPUs.[6] Its CVE ID is CVE-2015-4000.[7]

The authors also estimated the feasibility of the attack against 1024-bit Diffie–Hellman primes. By design, many Diffie–Hellman implementations use the same pre-generated prime for their field. This was considered secure, since the discrete logarithm problem is still considered hard for big enough primes even if the group is known and reused. The researchers calculated the cost of creating logjam precomputation for one 1024-bit prime at hundreds of millions of USD, and noted that this was well within range of the FY2012 $10.5 billion U.S. Consolidated Cryptologic Program (which includes NSA). Because of the reuse of primes, generating precomputation for just one prime would break two-thirds of VPNs and a quarter of all SSH servers globally. The researchers noted that this attack fits claims in leaked NSA papers that NSA is able to break much current cryptography. They recommend using primes of 2048 bits or more as a defense or switching to elliptic-curve Diffie–Hellman (ECDH).[1] Claims on the practical implications of the attack were however disputed by security researchers Eyal Ronen and Adi Shamir in their paper "Critical Review of Imperfect Forward Secrecy".[8]

Responses

[edit]

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Logjam (computer security)

View on Grokipedia
from Grokipedia
Logjam is a man-in-the-middle targeting the Diffie-Hellman (DH) key exchange in (TLS) and Secure Sockets Layer (SSL) protocols, allowing attackers to downgrade secure connections to weak 512-bit export-grade cryptography, thereby enabling decryption and potential tampering of transmitted data. The attack exploits legacy support for short DH parameters mandated by historical U.S. export restrictions on , combined with flaws in client-server negotiation that permit forced use of these insecure ephemeral DH (DHE) cipher suites. A related aspect involves computationally feasible breaks of certain 1024-bit DH primes by well-resourced adversaries, undermining in affected systems. Discovered in 2015 by a collaborative team of researchers from institutions including INRIA, , , the , and the , Logjam was publicly disclosed on May 20, 2015, alongside a peer-reviewed paper presented at the ACM Conference on Computer and Communications Security (CCS). At the time, approximately 8.4% of the top one million HTTPS domains supported vulnerable DHE export ciphers, with broader prevalence in protocols like SMTP with StartTLS (14.8% affected) and IMAPS (8.4% affected). The vulnerability's impact extended to potentially millions of servers worldwide, as many TLS implementations retained compatibility with export-grade DH for , exposing users to passive or active man-in-the-middle without failures alerting parties. Mitigations implemented post-disclosure included disabling export cipher suites in servers and clients, adopting stronger 2048-bit or larger DH groups, and updating TLS libraries such as to reject weak parameters. Browsers like Chrome, , and rapidly patched support for vulnerable DH exports, reducing exposure, while server administrators were advised to generate fresh, strong DH parameters to resist precomputation attacks on fixed primes. Logjam highlighted systemic risks in protocol evolution, where lingering legacy features for clashed with modern computational capabilities, prompting broader scrutiny of DH usage in favor of variants.

Background

Diffie-Hellman Key Exchange Fundamentals

The protocol enables two parties, typically denoted as , to compute a value over a public channel without directly transmitting it, forming the basis for secure key agreement in cryptographic systems. Invented by and Martin E. Hellman, the method was introduced in their seminal 1976 paper, which outlined public-key distribution systems resistant to . The protocol's core innovation lies in leveraging asymmetric computations to derive symmetric keys, relying on one-way mathematical functions rather than symmetric encryption for the initial exchange. Public parameters consist of a large prime modulus p and a generator g, where g is typically a primitive root modulo p to ensure the order of the generated by g is sufficiently large (ideally p-1). These parameters are agreed upon in advance or negotiated, with p selected to resist known attacks on the underlying group . Alice generates a private exponent a (a random integer, 1 < a < p-1), computes the public value A = g^a mod p, and transmits A to Bob. Similarly, Bob selects private b, computes B = g^b mod p, and sends B to Alice. Both then derive the shared secret K = g^{ab} mod p, verifiable as B^a mod p for Alice and A^b mod p for Bob, since exponentiation is commutative in modular arithmetic. Security stems from the computational intractability of the discrete logarithm problem (DLP) in the finite field: given p, g, and Y = g^x mod p, recovering x requires exponential time with current algorithms for large p (e.g., 2048 bits or more). The protocol's strength further assumes the hardness of the computational Diffie-Hellman problem: deriving g^{ab} mod p directly from g, g^a mod p, and g^b mod p without solving the DLP. No efficient classical algorithm solves these problems for properly chosen parameters, though quantum methods like Shor's algorithm pose threats, motivating post-quantum alternatives. In implementations, ephemeral Diffie-Hellman (DHE) variants use per-session private keys for perfect forward secrecy, ensuring compromised long-term keys do not expose past sessions. Fixed parameters, like standardized moduli in protocols such as , must be vetted for smoothness or subgroup weaknesses to prevent attacks like those exploiting small subgroups or precomputed logs.

Origins of Export-Grade Cryptography Restrictions

In the late Cold War era, the United States classified cryptographic technologies as munitions under the and , primarily to prevent proliferation to adversaries, with commercial export controls enforced by the State Department. These restrictions intensified in the early 1990s amid the rise of and internet software, as the Bush administration in 1991-1992 designated strong encryption exports as controlled items equivalent to military technology, shifting oversight partially to the Commerce Department's Bureau of Export Administration (now ). This policy aimed to balance national security concerns—such as denying encryption tools to foreign intelligence or terrorist groups—with emerging commercial demands, leading to the requirement for "export-grade" variants of software like web browsers that incorporated weakened parameters to comply. Specific limits emerged through proposed regulations in 1992, capping symmetric encryption at 40-bit keys for export (versus 56-bit domestic) and public-key systems, including Diffie-Hellman key exchange, at 512-bit moduli to render them crackable by U.S. intelligence capabilities within feasible computational bounds. These thresholds were codified in Commerce Department rules finalized under the Clinton administration, mandating separate export-compliant ciphersuites in protocols like SSL (precursor to ), which embedded 512-bit Diffie-Hellman groups alongside stronger domestic ones. The 512-bit limit for discrete logarithm-based schemes like Diffie-Hellman was explicitly tied to controlling computation of discrete logs in finite fields exceeding that size, reflecting assessments that such keys could be broken by supercomputers available to the NSA but not readily by others. Pressure from the technology sector, citing billions in lost exports—such as 's browser sales—prompted partial liberalization via President Clinton's 1996 executive order, which decontrolled certain non-military encryption and allowed limited 56-bit exports after review, though 512-bit public-key limits persisted until further easing in 1999-2000 under influences. Despite relaxations, legacy export-grade implementations remained in protocols, as vendors retained compatibility for global markets, inadvertently creating long-term vulnerabilities exploitable decades later. The policy's rationale, articulated in government statements, prioritized law enforcement access and intelligence advantages over unrestricted commerce, though critics argued it undermined U.S. competitiveness without enhancing security, given widespread foreign development of strong crypto.

Discovery

Research Timeline and Key Contributors

The Logjam vulnerability was publicly disclosed on May 20, 2015, by a multinational team of researchers who demonstrated a man-in-the-middle downgrade attack exploiting weak Diffie-Hellman (DH) parameters in TLS implementations. This work built on prior analyses of export-grade cryptography weaknesses, such as the FREAK attack reported in March 2015, but introduced a novel protocol-level downgrade mechanism targeting DHE_EXPORT cipher suites to force 512-bit DH keys, which the team broke using precomputed discrete logarithm tables derived via the number field sieve. The researchers scanned over 3.4 million HTTPS servers, finding that 8.4% of the top one million domains supported vulnerable export ciphers, enabling practical decryption of sessions. Key contributors included David Adrian and J. Alex Halderman from the University of Michigan, who led scanning and attack demonstration efforts; Nadia Heninger from the University of Pennsylvania, focusing on discrete logarithm computations for weak primes; Karthikeyan Bhargavan and Santiago Zanella-Béguelin from Inria, analyzing TLS protocol flaws; Matthew Green from Johns Hopkins University, contributing to forward secrecy implications; and Pierrick Gaudry, Emmanuel Thomé, and Paul Zimmermann from CNRS and Inria Nancy-Grand Est, advancing number-theoretic attacks on DH groups up to 1024 bits. Additional team members comprised Zakir Durumeric, Eric Wustrow, Drew Springall, and Benjamin VanderSloot from the University of Michigan; and Luke Valenta from the University of Pennsylvania, with support from Microsoft Research. Their collaborative effort, spanning academic and research institutions, emphasized empirical measurement of real-world DH deployments alongside theoretical breaks, revealing that 7% of servers reused standardized weak primes vulnerable to nation-state computation. The findings were formalized in the peer-reviewed paper "Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice," presented at the 22nd ACM Conference on Computer and Communications Security (CCS) on October 13, 2015, in Denver, Colorado. This timeline reflects coordinated responsible disclosure, with the team notifying affected vendors like browser developers and TLS libraries prior to public release, prompting rapid mitigations such as disabling export ciphers and enforcing minimum DH group sizes of 2048 bits. No earlier internal research milestones were detailed publicly, but the work leveraged open-source tools for internet-wide scans and high-performance computing for log computations, underscoring interdisciplinary expertise in cryptography, systems security, and number theory.

Initial Announcement and Public Disclosure

The Logjam vulnerability was publicly disclosed on May 20, 2015, by an international team of researchers from institutions including , , Inria, CNRS, and the University of Michigan. The announcement detailed a man-in-the-middle downgrade attack exploiting Diffie-Hellman key exchange weaknesses in TLS implementations, particularly those supporting export-grade 512-bit keys, allowing attackers to decrypt connections after computationally feasible precomputation. Key contributors included David Adrian, Karthikeyan Bhargavan, Zakir Durumeric, Pierrick Gaudry, Matthew Green, J. Alex Halderman, Nadia Heninger, Drew Springall, Emmanuel Thomé, Luke Valenta, Benjamin VanderSloot, Eric Wustrow, Santiago Zanella-Béguelin, and Paul Zimmermann. The researchers released their findings via the dedicated website weakdh.org, which included a comprehensive analysis, demonstration of the attack on real-world servers, and deployment guides for stronger Diffie-Hellman parameters. This disclosure coincided with the publication of their peer-reviewed paper, "Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice," which was presented at the ACM Conference on Computer and Communications Security (CCS) later that year. The paper quantified the vulnerability's scope, estimating that 8.4% of the top one million HTTPS domains initially supported vulnerable export cipher suites, with broader risks from common 1024-bit primes potentially affecting 18% of such domains under state-level computational resources. Disclosure was coordinated with major vendors and browser developers to facilitate rapid mitigations, including disabling export-grade ciphers and preferring stronger key sizes. The announcement highlighted not only the immediate exploitability of weak keys but also systemic issues in TLS protocol design and historical export restrictions that perpetuated support for insecure cryptography in legacy systems. No prior public warnings had been issued, though the research built on earlier analyses of Diffie-Hellman weaknesses, emphasizing proactive scanning and reconfiguration to prevent passive eavesdropping by nation-state actors.

Technical Mechanism

Downgrade Attack on TLS Handshake

In the TLS handshake, the client initiates negotiation by sending a ClientHello message containing a list of supported cipher suites, ordered by preference. Servers supporting ephemeral Diffie-Hellman (DHE) key exchange may offer both strong suites using large prime moduli (typically 2048 bits or more) and legacy export-grade DHE_EXPORT suites restricted to 512-bit moduli, a holdover from U.S. cryptography export controls in the 1990s that mandated weak parameters for international software shipments. A man-in-the-middle (MitM) attacker exploiting Logjam intercepts the ClientHello and selectively removes all non-export cipher suites before forwarding it to the server. If the server prefers stronger suites but falls back to export-grade ones when unavailable—and retains support for them for backward compatibility—it selects a DHE_EXPORT suite in its ServerHello response. The attacker relays this modified response to the client, which proceeds if it supports the weak suite, completing the handshake with compromised parameters. This downgrade evades TLS version checks or downgrade sentinels (like those in TLS 1.2's fallback signaling) because it targets cipher strength rather than protocol version, and export suites were not explicitly deprecated in early TLS standards. The resulting 512-bit DH group uses one of approximately 40 standardized weak primes, enabling attackers to precompute discrete logarithms offline using the number field sieve, thus deriving the premaster secret within minutes on consumer hardware for popular moduli. The attack's feasibility hinged on widespread server support for export ciphers—scanning in May 2015 revealed over 8% of HTTPS servers vulnerable—and client acceptance of fallbacks, though modern clients increasingly reject export suites. It required active MitM positioning, such as via compromised networks or forged certificates, but succeeded against unpatched systems without alerting endpoints during negotiation.

Exploitation of Weak DH Parameters

Weak Diffie-Hellman (DH) parameters, typically consisting of a small prime modulus p (such as 512 bits) and a generator g, undermine the security of the DH key exchange by making the discrete logarithm problem (DLP) computationally tractable. The DLP requires finding an exponent x such that gx ≡ y (mod p), where y is a public DH value; its hardness underpins DH's resistance to key recovery. For export-grade 512-bit p, mandated by U.S. restrictions in the , the general number field sieve (GNFS) achieves subexponential Lp[1/3, (64/9)1/3] ≈ exp(√(ln p ⋅ ln ln p)), rendering solutions feasible with dedicated resources. Attackers exploit these parameters through precomputation tailored to fixed weak primes commonly embedded in software, such as the 512-bit primes in mod_ssl (prime "mod_ssl") and JDK (prime "Sun"). Precomputing a DLP "oracle" for a specific p—involving sieving and linear algebra over a database of relations—costs significant upfront effort (e.g., thousands of core-years for full tables) but enables near-real-time log computations (milliseconds to seconds per query) on consumer hardware thereafter. Researchers in 2015 demonstrated GNFS-based DLP solving for a 512-bit prime in 70 hours using a cluster of ~200 GPUs for sieving and CPUs for descent, highlighting that nation-state actors could amass such capabilities for widespread primes. In a man-in-the-middle (MITM) scenario enabled by cipher suite downgrade, the attacker intercepts the server's ephemeral public key gs (mod p) from the signed ServerKeyExchange message, recovers s via the precomputed , and awaits the client's gc (mod p). The premaster secret gs c (mod p)—used in TLS to derive session keys—is then computed as (gc)s (mod p), allowing decryption of application data without breaking the signing RSA key. This per-connection DLP solve suffices for active impersonation, as the weak parameters' signature by a strong key permits relaying authentic ServerKeyExchange messages while covertly extracting secrets. Precomputation's scalability amplifies impact, as a single covers all connections using the targeted p, affecting servers from major vendors like and runtimes. Beyond export grades, Logjam extends to any sufficiently weak or reused parameters (e.g., 768-bit p or common non-export primes), where GNFS feasibility grows with smaller bit lengths—512-bit breaks in days, 768-bit in months on large clusters—emphasizing the need for unique, large (≥2048-bit) safe primes. Fixed parameters exacerbate risks, as attackers prioritize prevalent ones; scans post-disclosure revealed millions of hosts vulnerable to such precomputation.

Breaking Export-Grade Keys

The core of breaking export-grade keys in the Logjam attack centers on solving the within the modulo a 512-bit prime pp, where the server transmits a public key gamod  pg^a \mod p and the attacker seeks the private exponent aa. This computation yields the gabmod  pg^{ab} \mod p once the client's exponent bb is observed, enabling decryption or impersonation in a man-in-the-middle scenario. The 512-bit modulus size renders the DLP feasible due to its vulnerability to advanced algorithms, unlike larger secure parameters exceeding 2048 bits. The primary algorithm employed is the number field sieve for discrete logarithms (NFS-DL), an adaptation of the general number field sieve that exploits the subexponential complexity L_p[1/3, 1.923] \approx e^{\sqrt{{grok:render&&&type=render_inline_citation&&&citation_id=3&&&citation_type=wikipedia}}{(\ln p)^2 \ln \ln p}} for solving the DLP in prime fields. NFS-DL proceeds in phases: polynomial selection to identify suitable ring homomorphisms, sieving to collect relations between smooth ideals in the rational and algebraic number fields, linear algebra over GF(2) to compute a kernel basis for the relation matrix, and finally individual logarithm descent using precomputed databases for small primes. The initial phases (precomputation) depend solely on the fixed prime pp and generator gg, while the descent phase targets the specific public value gamod  pg^a \mod p. A critical optimization exploits the reuse of standardized 512-bit primes across implementations, such as those in historical TLS libraries compliant with export restrictions. Researchers precomputed NFS-DL databases for the two most common such primes, covering 92.3% of vulnerable servers observed in scans of the Alexa Top 1 Million HTTPS sites. Each precomputation required approximately 89,000 core-hours, comprising 7,600 for polynomial selection, 21,400 for sieving, and 60,000 for linear algebra, executed over 7 days on 2,000 to 3,000 Intel Sandy Bridge cores. Post-precomputation, solving an individual DLP instance averaged 70 seconds (ranging 34 to 206 seconds), rendering real-time attacks viable during TLS handshakes. This feasibility underscores the inadequacy of 512-bit parameters against moderately resourced adversaries, as the one-time precomputation amortizes costs across numerous targets sharing the same prime. Demonstrations confirmed breaks on actual TLS connections, with attackers able to forge responses before legitimate servers reply, exploiting the short DH parameter negotiation window in export cipher suites. Such computations remain accessible via cloud resources; for instance, equivalent efforts have been estimated at under $100 and 12 hours on platforms like Amazon EC2 for non-precomputed instances, though precomputation dominates for widespread primes.

Scope and Impact

Affected Protocols and Systems

The Logjam attack specifically exploits vulnerabilities in the TLS protocol by enabling a man-in-the-middle downgrade to 512-bit export-grade Diffie-Hellman (DHE_EXPORT) , compromising the of encrypted connections. This primarily affects websites where servers advertise support for these weak ciphers, allowing attackers to intercept and decrypt traffic after breaking the reduced key size. Internet-wide scans revealed that 8.4% of the top one million domains were vulnerable to this downgrade, with an additional 17.9% at risk from attacks on common 1024-bit Diffie-Hellman groups used in stronger configurations. Other TLS-dependent services, including SMTP with StartTLS (14.8% of IPv4 servers vulnerable), POP3S (8.9%), and IMAPS (8.4%), face similar risks if they rely on weak or common Diffie-Hellman parameters. Beyond TLS, the underlying flaws in widely reused Diffie-Hellman primes extend to protocols like SSH and VPNs employing IKEv1, where precomputed attacks on 1024-bit groups could enable key recovery. Scans indicated 25.7% of IPv4 SSH servers and 66.1% of IPv4 servers were susceptible to such state-level threats. Any system supporting DHE_EXPORT ciphers in TLS, such as or servers with default or legacy configurations, amplifies exposure, as these ciphers persist in some implementations despite deprecation. Client-side vulnerabilities impacted major web browsers at the time of disclosure, including , Mozilla Firefox, Microsoft Internet Explorer (on and earlier), , and , all of which negotiated export-grade Diffie-Hellman during vulnerable handshakes. TLS libraries like were also affected if they permitted these weak parameters, necessitating updates to enforce minimum key sizes and disable export ciphers.

Computational Resources Required for Attacks

The Logjam attack exploits weak Diffie-Hellman (DH) parameters, primarily 512-bit export-grade primes, by computing discrete logarithms using the number field sieve (NFS) algorithm, which requires significant precomputation for a specific prime followed by faster individual logarithm solutions. For the most common 512-bit prime used in vulnerable TLS servers, precomputation involves polynomial selection (3 hours, approximately 7,600 core-hours), sieving (15 hours, approximately 21,400 core-hours), and linear algebra (120 hours, approximately 60,000 core-hours), totaling about 7 days of wall-clock time on 2,000–3,000 Intel Sandy Bridge cores. Once precomputed, solving an individual 512-bit discrete logarithm takes a median of 70 seconds (ranging from 34 to 206 seconds) on dual 18-core Intel Xeon E5-2699 CPUs with 128 GB RAM, enabling real-time decryption after a man-in-the-middle downgrade. For larger but still vulnerable parameters, such as 768-bit primes found in some non-export DH implementations, precomputation demands around 36,500 core-years, with sieving accounting for about 8,000 core-years and linear algebra 28,500 core-years; individual solutions require roughly 2 core-days thereafter. These costs render 768-bit breaks feasible for well-resourced academic teams but impractical for casual attackers without pre-shared computations. Extending to 1024-bit primes, common in legacy systems, escalates to approximately 45 million core-years for precomputation (10 million for sieving, potentially achievable with 3 million costing around $8 million over one year, and 35 million for linear algebra requiring further massive ASIC investment), followed by 30 core-days per individual logarithm. Such resources align with nation-state capabilities, particularly when targeting reused primes across multiple servers, amplifying the attack's efficiency. These estimates, derived from 2015 implementations using tools like CADO-NFS, highlight how shared weak primes across protocols (e.g., , , ) reduce per-target costs after initial investment, but optimizations in hardware and algorithms since then could lower barriers further for determined adversaries. The NFS complexity, scaling subexponentially as L(q)=eln⁡q×ln⁡ln⁡qL(q) = e^{\sqrt{\ln q \times \ln \ln q}}
Add your contribution
Related Hubs
User Avatar
No comments yet.