Understand Diffie-Hellman key exchange

Whitfield Diffie and Martin Hellman were outsiders in the field of cryptography when they devised a scheme hitherto unknown: The ability to establish secure communications over public channels between two parties that don’t know each other.

The algorithm they presented in 1976, known as Diffie-Hellman, introduced the general notion of what is now called asymmetric encryption, or public-key cryptography.

The far-ranging and long-lasting impact of this development is impossible to exaggerate. Not only is the algorithm still in use to this day, but it opened up a whole landscape of possibilities that others have expanded into. But what is the Diffie-Hellman algorithm exactly, and how does it fit into the context of online communications as it works today?

A crypto earthquake

Until the 1970s, the development of secure communications entailed ever more sophisticated symmetric ciphers. A key is used to scramble messages, and the same key is used to unscramble them. When Diffie and Hellman first introduced their idea of asymmetric keys, they began their paper with the promise, “We stand today on the brink of a revolution in cryptography.” They meant it, and history has borne them out.

The question is, given two parties without prior arrangement, how do we establish a secure channel and verify identity? As you can readily imagine, such a capability is essential for the fundamental operation of the then-nascent ARPANET, soon to become our ubiquitous internet. Without Diffie-Hellman, it’s difficult to picture what the internet would look like. We might be in the position of having to FedEx a cipher key to each other whenever we wanted to make an online purchase.

The answer in Diffie-Hellman is that, by using one-way functions, two parties can arrive at a secret number that they both know, but that any eavesdropping party cannot determine. This secret is known as a shared secret key. Once the shared secret key is in place, we can switch to traditional symmetric encryption for speed.

The ability to securely establish a key between unknown parties was a cryptographic earthquake. Let’s get a closer look at how it works.

How Diffie-Hellman works: The problem

First, consider the process in theory. In Figure 1 we see the idealized layout of things: Alice and Bob want to talk to each other securely, but they have to assume that a malicious actor, Eve (as in “eavesdropper”) has access to the channel as well. (By the way, these conventional names that are seen in many discussions of cryptography were introduced by the same paper.)

Figure 1. The setup

So the question is, can Alice and Bob talk to each other in a way that will allow them to foil Eve, without first establishing a secret key that only they know? Remember, once a secret key is known to Alice and Bob, but not Eve, a cipher can be used to scramble and unscramble the data.

The answer for several thousand years was: no.

How Diffie-Hellman works: The solution

But Whitfield Diffie, aided by Martin Hellman, got to obsessing over this idea: What if you could find a mathematical function which would allow Alice and Bob to calculate a key that Eve can’t figure out, even though Eve would see everything that moves between Alice and Bob?

This would be done by exchanging some information that it’s OK for the world to see, including the attacker Eve. This information is known as the public key. The use of both a public component and a secret component is why Diffie-Hellman is called asymmetric encryption.

The math for achieving this is not terribly complex, but it is seriously non-obvious as well. How did Diffie arrive at it? Well, he pondered the idea for years before a stroke of genius gave him the answer described below.

The first part of the exchange begins with an agreed-upon function of the form G^a mod P. This formula is known to all parties.

The communicators will agree on the same number to fulfill G and P. P must be a prime number. In real use, these numbers are very large (at least 2048 bits, or 617 digits). The bigger the number, the more difficult it is to crack the exchange using a brute-force attack. In practice these numbers are picked with a pseudo-random generator.

Let’s illustrate this with an example. We’ll use 11 as our base G. This number is known as the generator. For our prime P, let’s use 13.

So the public function becomes 11^a mod 13. It is known to everyone. You can see the situation now in Figure 2.

Figure 2. The public function

And where does the a come from? The answer is that a is part of the secret key. Alice and Bob each choose a secret key privately and run the function. The results are then shared, making them part of the public key.

Let’s say Alice selects 5 and Bob selects 6 (again these would be larger random numbers in real life). You can see the new situation in Figure 3.

Figure 3. The function with secret numbers

Eve doesn’t know what numbers Alice and Bob chose.

Now Alice and Bob run their respective functions with their secret numbers. Alice arrives at 7 (11^5 mod 13) and Bob arrives at 12 (11^7 mod 13).

Now Alice and Bob share these numbers with each other, and (we have to assume) with our attacker, Eve, as well. This scene is depicted in Figure 4.

Figure 4: The public numbers

Even though Eve knows the equation and knows the results, she can’t easily discover the missing numbers. This is the essence of a one-way function: doable in one direction, virtually impossible to reverse.

For example, if Eve wants to find Alice’s hidden number, she would need to solve 11^x mod 13 = 7. How difficult is that? Have a look. The problem comes down to solving the discrete logarithm, a known difficult problem. It is far more difficult than the exponentiation that created the number 7 (with known mathematical approaches).

Arriving at a shared key

Here comes the magical bit. Alice and Bob each run a new function using the result they got from the other, along with their own secret number and the original prime modulus, and arrive at a common shared secret number which Eve cannot determine (again, without solving for the discrete log of the equation).

In our case, as in Figure 5, Alice runs 12^5 mod 13, and Bob runs 7^6 mod 13. Both come up with 12.

Figure 5. The final result with the shared secret key

With this private key in hand, Alice and Bob are free to negotiate a symmetric encryption exchange using something like Advanced Encryption Standard, while Eve can go work on a brute-force attack for around $100 million or so per key.

Note that most modern systems use 2048 encryption—exponentially as strong. An estimate for cracking this means trying 2^2048 numbers. Any calculator will tell you that’s big.

Vulnerabilities

Although Diffie-Hellman has proven to be highly resistant to attack when properly implemented (not bad for an algorithm conceived of almost 50 years ago), there is one advancing technology that may eventually defeat it: quantum computers. Beyond brute force, or a breakthrough in discrete logarithms, or quantum computing, users of Diffie-Hellman could be vulnerable to a handful of attacks that depend on exploiting the computing environment, known as side-channel attacks.

Counterintuitive crypto

The Diffie-Hellman algorithm was a stunning breakthrough in cryptography that flew in the face of the conventional wisdom that keys must be kept fully private to achieve security. Although a similar system was devised a few years earlier by British intelligence, those results were never published nor pursued. That the algorithm remains useful to this day is even more incredible.

In addition, the approach inspired the creation of the RSA algorithm, and opened the way for other more recent innovations like Elliptic Curve Cryptography.

Source link