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_AB. And it's basically defined as the
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_AB, and
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.