Attacking Exponential Key Agreement -- Breaking Diffie-Hellman

Today we are going to broadly cover how exponential key agreement is attacked by researchers, and discuss how close the white-hat security world actually is to breaking exponential key agreement.

Since the inception of the Diffie-Hellman key exchange in the 1970's by British intelligence, it has been under a long mathematical siege by researchers, law-enforcement, and state-sponsored clandestine groups. It has been believed to be secure for this entire period as long as the private keys were not given up through other means. It relies on complex mathematics to come up with a mutual number to encrypt data. There are multiple asymmetric algorithms out there that rely on the Diffie-Hellman principal, including modern Elliptic Curve algorithms (believed to be the strongest). Researchers and security experts alike are growing concerned that the time is rapidly approaching where the Discrete Logarithm Problem that exponential key agreement relies on may be becoming weak enough to be broken.

Current attack methods for the Discrete Logarithm Problem:

The best known attack method for breaking Diffie-Hellman handshakes is called the General Number Field Sieve when the prime "p" is large (relative to the secret values "a" and "b"). If the prime "p" is small relative to "a" and "b" then the preferred method is a Function Field Sieve. Either method will work for both cases, but they become inefficient relative to one another as the prime number becomes unfavorable for the method.

The current records for number field sieves are startling. A 6120-bit key has been solved in 749.5 CPU hours (note: CPU-hours is how many hours it would take one CPU to complete the operation, this can be divided among many processors to make the times trivial rather than daunting). A 6168-bit key has been solved in 550 Hours. These cases were both with small prime "p" values, which makes the problem easier. On the Elliptic-Curve front, the current record is a 112-bit Elliptic Curve Key solved using Pollard's Rho Algorithm. The attack took 200 Playstation 3 consoles over 6 months to complete.

The Safety of Exponential Key Agreement -- Extrapolating Risk

It is hard to guess at the relative safety of Diffie-Hellman as a whole. Modern security software selects harder numbers to solve than what have currently been solved. However, it is also clear that the resources doing the research are limited to small groups and budgets. A large agency would have access to specialized hardware and a team of experts spanning both mathematics and computing. It would be easy to speculate that a government agency could be orders of magnitude ahead of the white-hat security community. They could leverage better heuristic methods to simplify problems, have specialized processors that solve pieces of the equation exponentially faster, or simply highly optimized code such as an OpenCL implementation. These factors in combination could make real-world small keys (1024-bit) vulnerable. It is unlikely that a "real-world" 2048-bit key is at risk at this time. There are currently multiple projects working on keys between 768 and 1024-bits with large primes.

Most reputable institutions that are concerned with data security have moved to 2048-bit or beyond to secure their data. I would be weary of any site using 1024-bit plain Diffie-Hellman keys in 2013. We are a small mathematical breakthrough from making breaking 1024-bit keys trivial for a sophisticated attacker. For agencies concerned with secret information, 1024-bit may already be insecure. Advancements in hardware over the last few years have made implementing larger RSA keys trivial for web servers.

Elliptic Curve cryptography is looking a lot better in comparison to plain Diffie-Hellman. With 112-bit being the strongest key solved, the P-521 curve is looking impenetrable at this point (provided that you don't use the NSA-tampered Dual_EC_DRBG number generator). The complexity of the 2,000,000 bit field makes Elliptic Curves much harder to solve mathematically.

Compromised Keys -- Trivial Math

It is crucial to note that all of these deep mathematical analyses are not needed if even one of two secret keys are compromised. This is because if either of the secret keys are known, it is trivial to calculate mutual secret "s" without even worrying about the other secret key. So a breach of "a" or "b" means that the data security is lost entirely. Using our example handshake from the Exponential Key Agreement article we can see how trivial it becomes when a key is compromised.

During a normal handshake, if we had a man-in-the-middle listening to the handshake, the only information revealed is g, p, A, and B. A and B are just remainders left over after g is raised to a power. There are myriad possible answers for each variable that is unknown, and getting the right combination of correct guesses to get the correct matching value for "s" is the subject of cutting edge mathematics.

For example, from that problem we know that g=3, p=37, A=36 , and B=4. We don't know mutual secret s, secret key a, or secret key b.

This leaves a very complicated set of guesswork, which is where index calculus and number sieves come into play.

3a mod 37 = 36 has infinitely many possible answers. If we use some logic, we can say that every number between 1 and 22048 that you can divide by 37 have a 36 remainder is a possible answer. Plugging this into Wolfram Alpha, we get all possible solutions a=9(2n+1) where a < 22048. This means that every number starting at 27 and increased by 18, up to 22048. So the possible values read: 27, 45, 63, 81, 99, 117, 135, 153, 171, 189, 207... up to the maximum value...

That is around 1.79 * 10615 possible answers for that PART of the problem.

This is the complexity that exponential key agreement relies on to stay secure. The mathematical problem is too complicated for even the fastest computers to solve.

If a from our sample problem in the exponential key agreement article was leaked to our attacker somehow (say, by being publicly posted by a VPN provider) this problem becomes: a=81, b=unknown, s=unknown, g=3, p=37, A=36, B=4 for our attacker. Variable s is now trivial because:

Ba mod 37 = s can simply be plugged in. b is not needed.

481 mod 37 = 36

You have gone from a problem that takes many thousands of CPU-hours to solve on a supercomputer, to a problem that can be solved by Wolfram Alpha in less than one second using a cell phone.

< last
next >