Blog Archive Projects

Attacking Diffie-Hellman

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 where is to calculate until we hit a match. The worst case of this algorithm is , 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¹ that allow us to compute the discrete log of any finite cyclic group in about 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 Diffie-Hellman implemented in the wild with key lengths in the 1000-2000 bit range.

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

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 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.