Communications of the ACM
Technical Perspective: Attacking Cryptographic Key Exchange with Precomputation
The Diffie-Hellman key exchange protocol is at the heart of many cryptographic protocols widely used on the Internet. It is used for session setup in HTTPS (TLS), in SSH, in IPsec, and others. The original protocol, as described by Diffie and Hellman, operates by choosing a large prime p and computing certain exponentiations modulo this prime. For the protocol to be secure one needs, at the very least, that the discrete-log problem modulo the prime p be difficult to solve. This problem is quite easy to state: fix a large prime p, and an integer 0 < g < p (a generator). Next, choose an integer 0 < x < p and compute h = gx modulo p. The discrete-log problem is to compute x given only p, g and h. If this problem could be solved efficiently, for most h, then the Diffie-Hellman protocol for the chosen (p, g) would be insecure.
The authors of the following paper show that, in practice, implementations that use Diffie-Hellman tend to choose a universally fixed prime p (and fixed g). For example, many SSH servers and IPsec VPNs use a fixed universal 1,024 bit prime p. The same is true for HTTPS Web servers, although to a lesser extent.
Is it safe to use the same 1,024-bit prime p everywhere? The authors show that the answer is no. The reason is a beautiful precomputation attack on the discrete-log problem modulo a prime. A precomputation attack proceeds in two steps: First, in a one-time offline phase, before trying to attack any particular victim, the attacker works hard to compute a certain table based on the fixed p and g. Then, when attacking a victim session, the attacker uses the precomputed table to quickly compute discrete-log and break the session. The same precomputed table can be used to quickly break many sessions.
Precomputation attacks affect many cryptographic schemes. For example, they are often used to break weak password systems—one first precomputes a rainbow table, and then uses the table to quickly break many hashed passwords. The beautiful insight of this paper is that precomputation can be devastating for systems that use Diffie-Hellman modulo a prime. Precomputation attacks are a real threat and must be taken into account when choosing parameters for real-world cryptography.
The authors speculate that a pre-computation attack on discrete-log modulo a fixed 1,024-bit prime is within reach for a nation state. Because a small number of fixed primes is employed by a large number of websites, a precomputation attack on a few primes can be used to compromise encrypted Internet traffic at many sites.
To make matters worse, the authors show there is no need to break 1,024-bit primes to attack TLS. The reason is a weak TLS cryptography suite called TLS Export. This suite was included in TLS due to export control regulations that were in effect at the time that TLS was designed. TLS Export includes support for 512-bit primes, where discrete-log is woefully insecure. Sadly, TLS Export is still supported by many websites, and many (82%) use a fixed 512-bit prime shipped with the Apache Web server. The precomputation attack is extremely effective against this 512-bit prime. The authors carry out the offline precomputation phase in a few days, and the resulting table enables an online attack on a victim session in just under a minute.
The authors of the following paper show that, in practice, implementations that use Diffie-Hellman tend to choose a universally fixed prime p (and fixed g).
To make matters even worse, the authors describe a new clever attack on TLS 1.2, called logjam, which lets an attacker downgrade a victim connection to TLS Export. The resulting session is then vulnerable to a precomputation attack. Logjam exposes a significant flaw in the design of TLS 1.2.
So, what should we do? The short answer is that websites must migrate to TLS 1.3. TLS 1.3 is a recent significant upgrade to the TLS protocol. Compliant implementations must support Diffie-Hellman using an elliptic curve group called NIST P-256. It is likely that many websites will use Diffie-Hellman in this group. Using a universally fixed group seems as bad as using a universal prime p, however, currently there is no known practical precomputation attack on elliptic curve Diffie-Hellman, so that the precomputation attacks discussed earlier do not apply, as far as we know. One point of concern is NSA's August 2015 announcement recommending that companies stop their transition to elliptic curve cryptography or, if they already have transitioned, use larger elliptic curve parameters. The official reason in the notice is the concern over a quantum computer that can break elliptic curve Diffie-Hellman. One may wonder, however, if there are other reasons behind this announcement. Is there a yet-to-be discovered practical preprocessing attack on P-256? Currently, there is no indication that such an attack exists.
In summary, preprocessing attacks are a real concern in cryptography. It is critically important to take them into account when choosing cryptographic parameters. The following paper is a wonderful illustration of this.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2019 ACM, Inc.