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. 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. Its CVE ID is . 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). == Responses ==