crypto lesson: Diffie Hellman

This lesson just requires that you know basic algebra.

Diffie Hellman is probably the easiest "public key" algorithm to understand. As we will see, it is a key exchange protocol, and is not used for encryption. El-Gamal is an example of a public key encryption scheme which uses similar principles.

Let's say I have a secret key, which is just some big number, and I want to talk over an encrypted channel with Bob, who also has a secret key.

Neither of us wants to tell the other his secret key, so we need to establish a shared key, that only we know. We can use the shared key to encrypt our communications using any symmetric encryption such as AES.

In order to establish the shared key, we can only communicate over a public channel that anyone can eavesdrop on.

we use some constant number g which everyone knows. g stands for generator, but don't worry what that means.

my secret key = x

Bob's secret key = y

I send Bob g^x. (that means g raised to the power of x)

He sends me g^y

our shared key is g^(xy)

We now share a key, and no one but us should be able to derive the key, and no one, including us, should be able to derive the other's secret key.

If I know x and g^y, I can get g^(xy) by doing (g^y)^x = g^(xy)

It is impossible to derive g^(xy) if all you know is g^x and g^y. g^x * g^y = g^(x+y), which is worthless.

We are assuming that given g^x, an adversary cannot derive x. This is called the discrete logarithm problem. As long as discrete logarithms are hard, this protocol is secure. I left a little about this out. Rather than sending g^x, you would really send g^x mod n, but we don't need to get into that. That's what makes it a discrete logarithm rather than a regular one. There are wikipedia entries for all of these things.

So now you know. It's a pretty simple idea, and discrete logarithms are the basis for most public key encryption, with RSA being an exception which is based on integer factorization instead.

Challenge:

We're assuming that the adversaries can eavesdrop on the channel, but can't drop messages from the channel, or insert spoofed messages into the channel.

If an attacker can do those things, how can he eavesdrop on the encrypted communication without Bob and I knowing?

ttt for modifying messages.

This is the coolest thing I have ever read on this site.
Thanks Andrew.

I'll just answer myself. If the attacker can do a man in the middle attack, he can eavesdrop on the conversation. It would look like this:

Let's say the attacker's key is z.

I send to Bob g^x but the attacker replaces it with g^z.

Bob sends to me g^y but the attacker replaces it with g^z. I compute the shared key g^(xz) and Bob computes the shared key g^(yz).

So both I and Bob think we have a shared key with the other, but really we each have a shared key with the attacker. When I send stuff to Bob, the attacker can decrypt it using the key shared between him and me, and then re-encrypt it using the key shared between him and Bob. Then he would send it to Bob. He could conceivably modify it or do whatever to it before sending it to Bob.

The problem is that standard DH does not provide any authentication. A solution would be if there is a public key infrastructure available, we could sign the keys we send to each other.

If we have a PKI, what's the point of any of this? Why don't we just use public key encryption for everything, rather than agreeing on an temporary symmetric key?

One reason is that if my public/private key pair gets compromised later, the attacker would be able to go back and read all our communication. With authenticated Diffie Hellman key agreement on a temporary key, even if someone cracks my public/private key pair, that doesn't allow him to read my old stuff, because the public key was only used for authentication, not for encryption.

The Cisco CCNP courses assume you can't do math at all. Their analogy is one person has a can of paint, you mix some of the other person's paint, and there you have it.

ttt