Attacking Diffie-Hellman

Part II of the series Diffie-Hellman key exchange.
August 22, 2015

Part I of this series established the conceptual framework for Diffie-Hellman, so now we can turn to more pragmatic matters: attacks on Diffie-Hellman. Naively, the only way to calculate x where a^x\pmod{n} = m is to calculate a^1\pmod{n}\\a^2\pmod{n}\\a^3\pmod{n}\\\ldots\\a^x\pmod{n} until we hit a match. The worst case of this algorithm is \mathcal{O}(n) , which means that the time required to brute-force a shared key grows exponentially with the bitlength of the key.

However, there’s a number of algorithms1 that allow us to compute the discrete log of any finite cyclic group in about \mathcal{O}(\sqrt{n}) time, and modular exponentiation, being a finite cyclic group, is vulnerable to these attacks. Fortunately, this is a square-root of an exponential, so an attacker using these algorithms against a 128-bit key would be about as fast as an attacker using the naive brute-force algorithm against a 64-bit key, which doesn’t seem to be too bad of a tradeoff.

However, there are also index-calculus attacks that offer performance even greater than the aforementioned algorithms, requiring key lengths of 1000-2000 bits in order to slow an attacker armed with this algorithm to the speed of a naive brute-forcer attacking a 64-bit key. And that’s why we see \mathbb{Z}_p^* Diffie-Hellman implemented in the wild with key lengths in the 1000-2000 bit range.

Fortunately, \mathbb{Z}_p^* is not the only finite cyclic group, and as long as we have a finite cyclic group, we can implement Diffie-Hellman with it. Of course, just being a finite cyclic group is mere table stakes for an aspiring Diffie-Hellman cylic group. The real superstar groups, like elliptic curves, have additional properties that make them exempt from certain attacks that affect other groups. I won’t say too much more about elliptic curves, because that would take a whole new post, but understanding the bare mechanics of how they work is fairly straightforward. Basically, we take an elliptic curve defined by:

y^2 = x^3 + ax + b

and define an operation over points on this curve to wrangle finite cyclic group behaviour out of it. Of course, if it behaves like a finite cyclic group, it is a finite cylic group, and we can use this group in Diffie-Hellman. The resulting group is resistant to the aforementioned index-calculus attacks, so the only known attacks are the \cal{O}\sqrt{n} ones, which means we can select key sizes that are an order of magnitude smaller than the ones we used with discrete log Diffie-Hellman, but still maintain comparable resistance to attack.

  1. The giant-step, baby-step algorithm and Pollard’s rho algorithm can calculate the discrete log of any finite cyclic group in about \mathcal{O}(\sqrt{n}) time. They are fairly simple algorithms, and I might write another article analysing them in detail.