# Attacking Diffie-Hellman

*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 ax(modn)=m is to calculate a1(modn)a2(modn)a3(modn)…ax(modn) until we hit a match. The worst case of this algorithm is 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 algorithms^{1} that allow us to compute the discrete log of any finite cyclic group in about O(√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 Z∗p Diffie-Hellman implemented in the wild with key lengths in the 1000-2000 bit range.

Fortunately, 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:

y2=x3+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 O√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.

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