0:00

In this segment, we're gonna look at the Diffie-Hellman protocol, which is our

first practical key exchange mechanism. So let me remind you of the settings. Our

friends here, Alice and Bob, have never met and yet they wanna exchange a shared

secret key that they can then use to communicate securely with one another.

In this segment and the next, we're only gonna be looking at eavesdropping

security. In other words, we only care about eavesdroppers. The attackers are

actually not allowed to tamper with data in the network. They're not allowed to

inject packets. They're not allowed to change packets in any way. All they do is

to just eavesdrop on the traffic. And at the end of the protocol, the key exchange

protocol our friends Alice and Bob should have a shared secret key but the attacker

namely the eavesdropper has no idea what that key's gonna be. In the previous

segment we looked at a key segment called Merkle puzzles. That's just using block

ciphers or hash functions. And I showed you that there that basically the attacker

has a quadratic gap compared to the participants. In other words if the

participants spent time proportional to N the attacker can break the protocol in

time proportional to N squared. And as a result that protocol is to insecure to be

considered practical. In this segment we are going to ask whether we can do the

same thing but now we'd like to achieve an exponential gap between the attacker's

work Ended up in the participant's work. In other words, Alice and Bob might do

work proportional to N, but to break the protocol the attacker is gonna have to do

work proportional to some exponential in N. So now there's an exponential gap

between the participants work and the attacker's work. So as I said in the

previous segment we can't achieve this exponential gap from blog ciphers like AES

or SHA-256. We have to use hard problems that have more structure than just those

symmetric primitives. And so instead what we're gonna do is use a little bit of algebra.

In this segment I'm gonna describe the Diffie-Hellman protocol very

concretely and somewhat informally. When we're gonna come back to Diffie-Hellman next week

and we're gonna describe the protocol more abstractly and we're gonna do a much more

rigorous security analysis of this protocol. Okay, so how does Diffie-Hellman

work? What we're gonna do is, first of all, we're gonna fix some large prime

which I'm gonna call p. Actually p I'll usually use to denote primes. And you

should be thinking of really gigantic primes. Like, primes that are made up of

600 digits are so. And just for those of you who like to think in binary, a 600

digit prime roughly corresponds to about 2000 bits. So just writing down the prime

takes about two kilo bits of data. And then we're also gonna fix an integer g

that happens to live in the range one to p. So these values p and g are parameters

of the Diffie-Hellman protocol. They are chosen once and they're fixed forever. Now

the protocol works as follow. So here's our friends Alice and Bob. So what Alice's

going to do is she's gonna starts off by choosing some random number a in the range 1 to p-1

And then she is gonna compute the number g to the power of a modulo p.

Okay, so she computes this exponention, and reduces the result modular the prime p.

And we're actually going to see how to compute this efficiently the next module,

so for now just believe me that this computation can be done efficiently.

Now, let's call capital A the result of this value. So, what Alice will do is she will

send capital A over to Bob. Now Bob is going to do the same thing. He's going to

choose a random number b in the range 1 to p-1. He's going to compute g to

the b module of p and let's call this number B and he's going to send this

number B over to Alice. So Alice sends A to Bob. Bob sends B. To Alice. And now

they claim that they can generate a shared secret key. So what's a shared secret key?

Well, it's defined as. Let's call it K<u>AB. And it's basically defined as the</u>

value g to the power of a times b. Now the amazing observation of Diffie-Hellman had

back in 1976 is that in fact both parties can compute this value g to the ab.

So let's see, Alice can compute this value because she can take her value B that she

received from Bob. She can take this value B, raise it to the power of a and, let's

see, what she'll get is g to the b to the power of b. And by the rules of

exponentiation, g to the power of b to the power of a is equal to g to the ab. Bob

turns out, can do something similar, so his goal is to compute g to the a to the b,

which again, is g to the ab, so both Alice and Bob will have computed K<u>AB, and</u>

let me ask you, how does Bob actually compute this quantity g to the ab?

Well so all he does is he takes the value A that he received from Alice and he raises it to

his own secret b and that gives him the shared secret g to the ab. So you can see

now that both parties even though they seemingly computed different values. In

fact they both end up with the same value namely g ab module p. I should mention by

the way that Martie Hellman and Wig Diffiie came up with this protocol back in

1976. Martie Hellman was a professor here at Stanford and Wig Diffie was his

graduate student. They came up with this protocol and this protocol really changed

the world. In that it introduced this new age in cryptography. Where now it's not just

about developing block ciphers but it's actually about designing algebraic

protocols that have properties like the one we see here. So you notice that what

makes this protocol works is basically properties of exponentiation. Namely that,

g to the b to the power of a is the same as g to the a to the power of b, okay?

These are just properties of exponentiations. Now when I describe a

protocol like the one I just showed you. The real question that should be in your

mind is not why the protocol works. In other words, it's very easy to verify

that, in fact, both Alice and Bob end up with the same secret key. The bigger

question is why is this protocol secure? In other words, why is it that an

eavesdropper cannot figure out the same shared key due to the AB that both Alice

and Bob computed by themselves? So let's analyze this a little bit, then, like I

said, we're gonna do a much more in-depth analysis next week. But, let's, for now,

just see intuitively why this protocol is gonna be secure. Well, what does the

eavesdropper see? Well, he sees the prime and the generator. These are just fixed

forever and everybody knows who they are. He also sees the value that Alice sent to

Bob, namely this capital A. And he sees the value that Bob sent to Alice, namely

this capital B. And the question is, can the, can the eavesdropper compute g to the

ab just given these four values? So more generally, what we can do is we can define

this Diffie-Hellman function. So we'll say that the Diffie-Hellman function is defined

based on some value g. And the question is given g to the a, and g to the b. Can you

compute g to the ab? And what we're asking is how hard is it to compute this

function module over very large prime p. Remember p was something like 600 digits.

So the real question we need to answer is how hard is this, is this Diffie-Hellman

function? So let me show you what's known about this. So suppose the prime happens

to be n bits long. Okay, so in our case say n is 2,000 bits. It turns out the best

known algorithm for computing the Diffie–Hellman function. Is actually a

more general algorithm that computes the discrete log function, which we're gonna

talk about next week. But for now, let's just say that this algorithm computes a

Diffie-Hellman function. The algorithm is called a general number field sieve. I'm

not gonna describe how it works, although if you'd want to hear how it works, let me

know, and that could be one of the special topics that we cover at the end of the

course. But the interesting thing is that it's running time is exponential in

roughly the cube root of n. In other words, the running time is roughly e to

the power of o of cube root of n. So in fact the exact expression for the running

time, of this algorithm is much more complicated than this. I'm deliberately

simplifying it here just to kind of get the point across. The point that I want to

emphasize is that in fact, this is not quite an exponential time algorithm.

Exponential would be e to the power of n. This is sometimes called a sub-exponential

algorithm because the exponent is really just proportional to the cube root of n,

as opposed to linear n. What this says is that even though this problem is quite

difficult, it's not really an exponential time problem. The running time in the

exponent is gonna be just proportional to the cube root of n. So let's look at some

examples. Suppose I happen to be looking at a modulus that happens to be about a

thousand bits long. What this algorithm says is that we can solve the

Diffie-Hellman problem in time that's approximately e to the qube root of 1,024.

Now this is not really correct, in fact there are more constants in the exponent.

But again, just to get, the point across, we can say that the running time would be

roughly e to the qube root of 1,024; which is actually very small, roughly e to the 10.

So the simple example shows you that if you have a sub-exponential algorithm,

you see that even if the problem is quite large, like 1,000 bits. Because of the

cube root effect the exponent actually is not that big overall. Now to be honest I'm

actually lying here. General number field sieve actually have many other

constants in the exponents so in fact this is not going to be ten at all. It's

actually going to be something like 80. Because of various constants in the

exponents. But nevertheless but you see the problem is much harder than say 2 to

the 1000. Even though describing it takes 1,000 bits, solving it does not take time

to the 1,000. So here I roll down the table that kind of shows you the rough

difficulty of breaking down the Diffie-Hellman protocol compared to the

difficulty of breaking down a cipher with a appropriate number of bits. For example,

if your cipher has 80 bit keys. That would be roughly comparable to using 1,000 bit

modules. In other words breaking a cipher with 80 bit keys takes time roughly 2 to the 80

which means that breaking if you have Diffie-Hellman function with a 1,000

bit module will take time 2 to the 80.

If your cipher uses 128 bit keys like AES, you should be really using a 3,000 bit modulus,

even though nobody really does this. In reality people would use 2,000 bit modulus. And

then if your key is very large, like if we're using a 256 bit AES key, then in

fact your modulus needs to be very, very large. Again, you, you can really see the

cube root effect here. We doubled the size of our key and because of the cube root

effect, what that means is we have to increase the size of, of our modulus by a

factor of two cubed, namely a factor of eight, which is where this 15,000 comes from.

from. And again I should mention there's not exactly a factor of eight because of

the extra constants in the exponent. So this is a nice table that shows you that

if you're gonna be using Diffie-Hellman to exchange, a session key. And that session

key is gonna be used for a block cipher with a certain key size, this table shows

you what modular size you need to use so that the security of the key exchange

protocol is comparable to the security of the block cipher you're gonna be using after.

Now this last row should really be disturbing to you. I should tell

you that working with such a large modulus is very problematic. This is actually

gonna be quite slow, and so the question is whether there is anything better that

we can do? And it turns out there is. In fact the way I describe the Diffie-Hellman

function is I describe it at the way Diffie and Hellman described it in 1976

using arithmetic module of primes. The problem with arithmetic modular primes is

that the Diffie-Hellman function is hard to compute, but it's not as hard as you'd

like. There's this cube root effect that makes it a little easier than what you'd

really like. And so the question is can we run the Diffie-Hellman protocol in other

settings. And it turns out the answer is yes. In fact we can literally translate

the Diffie-Hellman protocol from an arithmetic model of primes to a different

type of algebraic object and solving the Diffie-Hellman problem on that other

algebraic object is much, much harder. This other algebraic object is what's

called an elliptic curve. And as I said, computing the Diffie-Hellman function on

these elliptic curves is much harder than computing the Diffie-Hellman modulo primes.

Because the problem is so much harder, now we can use much smaller objects in

particular, you know we'd be using primes that are only a 160 bits or 80 bit keys or

only 512 bits for 256 bit keys. So because these module don't grow as

fast on elliptic curves, there's generally a slow transition away from using module

arithmetic, to using elliptic curves. I'm not going to describe elliptic curves

right now for you, but if this is something you'd like to learn about I can

do that at the very last week of the course, when we discuss more advanced

topics. But in fact when we come back to Diffie-Hellman next week I'm gonna describe it

more abstractly so that it really doesn't matter which algebraic structure you use

whether you use arithmetic model of primes or whether you use a elliptic curve we

can kinda abstract that whole issue away and then use the Diffie-Hellman concept a for

key exchange and for other things as well. And as I said we'll see that more

abstractly next week. So as usual I wanna show that this beautiful protocol that I

just showed you, the Diffie-Hellman protocol, is as is, is actually completely insecure

against an active attack. Namely, it's completely insecure against what's called

the man in the middle attack. We need to do something more than this protocol to

make is secure against man in the middle. And again we're gonna come back to Diffie

Hellman and make it secure against man in the middle next week. Okay. So let's see

why the protocol that I just showed you is insecure against active attacks. Well

suppose we have this man in the middle that's trying to eavesdrop on the

conversation between Alice and Bob. Well so, the protocol starts with Alice sending

g to the a over to Bob. Well, so the man in the middle is gonna intercept that and

he's gonna take the message that Alice sent and he's gonna replace it with his

own message. So it's called A', And let's write that is g to the a'.

Okay? So the man in the middle chooses his own a' and what he sends to Bob is

actually g to the a'. Now poor Bob doesn't know that the man in the middle

actually did anything to this traffic, all he sees is he got the value A'. As

far as he knows, that value came from Alice. So what is he gonna do in response?

Well, he's gonna send back his value B out which is g to the b back to Alice. Well

again the man in the middle is gonna intercept this B. He's gonna generate his

own b' and what he actually sends back to Alice is B' which is g to the b'.

Okay, now what happens? Well Alice is gonna compute her part of the

secret key and she's gonna get g to the ab'. Bob is gonna compute his part of

the secret key and he's gonna get g to the b times a'. Okay, these now you

notice these are not the same keys. In the man in the middle because he knows both A'

and B' he can compute both g to the ab' and g to ba'. Yeah it's

not difficult to see the man in the middle knows both values. And as a result, now he

can basically play this man in the middle and when Alice sends an encrypted message

to Bob the man in the middle can simply decrypt this message because he knows the

secret key that Alice encrypted message with, re-encrypt it using Bob's key. And

then send the message on over to Bob. And this way Alice sent the message, Bob

received the message. Bob thinks the message is secure. But in fact that

message went through the man in the middle. The man in the middle decrypted

it, re-encrypted it for Bob. At the same time he was able to completely read it,

modify it if he wants to, and so on. So, the protocol becomes completely insecure

give n a man in the middle. And so as I said we're gonna have to enhance the

protocol somehow to defend against men in the middle but it turns out that it's

actually not that difficult to enhance and prevent man in the middle attacks.

And we're gonna come back to that and see that in a week or two. The last think I want to

do is show you an interesting property of the Diffie-Hellman protocol. In fact, I

want to show you that this protocol can be viewed as a non-interactive protocol. So,

what do I mean by that? So Imagine we have a whole bunch of users, you know, millions

of users. Let's call them Alice, Bob, Charlie, David and so on and so forth.

Each one of them is going to choose a random, secret value, and then on their

Facebook profiles, they're gonna write down, their contribution to the

Diffie-Hellman protocol. Alright so everybody just writes down you know g to

the a, g to the b, g to the c and so on. Now the interesting thing about this is,

if say Alice and Charlie wanna set up a shared key they don't need to communicate

at all. Basically Alice would go and read Charlie's public profile. Charlie would go

and read Alice's public profile. And now, boom, they immediately have a secret key.

Namely, now, Alice knows, g to the c and a. Charlie knows g to the a and с. And as

a result, both of them can compute п to the ac. So, in some sense, once they've

posted their contributions to the Diffie-Hellman protocol to their public

profiles, they don't need to communicate with each other at all to set up a shared key.

They immediately have a shared key and now they can start communicating

securely through Facebook or not with one another. And notice that this is true for

any Facebook user. So as soon as I read somebody's public profile, I immediately

have a shared key with them without ever communicating with them. This property is

sometimes called a non-interactive property of the Diffie-Hellman. So now, let

me show you an open problem. And this is an open problem that's been open for ages

and ages and ages. So it'd be really cool if one of you can actually solve it. The

question is, can we do this for more than two parties? In other words, say we have

four parties. All of them post their values to their Facebook profiles. And now

we'd like to make it that just by reading Facebook profiles, all of them can set up

a shared secret key. In other words, Alice is, what she'll, she'll do is she'll only

read the public profiles of, the three friends, Bob, Charlie and David. And

already she can compute a shared key with them. And similarly David is just gonna

read the public profile of Charlie. Bob and Alice. And already he has a shared key

with all four of them. Okay, so the question is whether we can kind of setup

non-interactively these, these shared keys for groups that are larger than just two

people. So as I said, for n equals two, this is just a Diffie-Hellman protocol. In

other words, if just two parties want to set up a shared key without communicating

with one another, that's just Diffie-Hellman. It turns out, for N equals

three, we also know how to do it, there's a known protocol, it's called protocol due

to Joux. It already uses very, very fancy mathematics, much more complicated

mathematics than what I just showed you. And for N equals four, or five, or

anything above this, above four, this problem is completely open. Nearly the

case where four people post something to the public profiles and then everybody

else reads the public profile and then they have a joint shared key, this is

something we don't know how to do even for four people. And this is a problem that's

been open for ages and ages, it's kind of a fun problem to think about and so see if

you can solve it, if you will, it's instant fame in the crypto world. Okay, so

I'll stop here, and we'll continue with another key exchange mechanism in the next segment.