Home → Magazine Archive → January 2019 (Vol. 62, No. 1) → Technical Perspective: Attacking Cryptographic Key... → Abstract

Technical Perspective: Attacking Cryptographic Key Exchange with Precomputation

By Dan Boneh

Communications of the ACM, Vol. 62 No. 1, Page 105

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.


No entries found