We talked a bit about end-to-end encryption already, and a lot of the assumption is that we have some kind of symmetric key that we can use to talk privately. So you and me have some kind of secret key and we use that to talk securely. Diffie-Hellman is how we get that secret key. Diffie-Hellman was first published in 1976 and has become pretty much a staple for any kind of cryptography at all. Whenever we use cryptography, we usually need to have a symmetric key and to get that, we often have to perform some kind of Diffie-Hellman. It’s so prevalent that your phone is probably doing it right now. Right – when you logged on to the browser to watch this video, you performed a Diffie-Hellman key exchange. When you open up your phone and it connects to any server, it’ll almost certainly perform a Diffie-Hellman key exchange. If not now, then in the next few minutes, right? It’s unbelievably important and unbelievably common.
The problem with Diffie-Hellman is it’s quite mathematically complex. It depends on your level of mathematics, so what I’ve thought we do is, I thought we cover the mathematics in the Extra Bits and then we’d look at a kind of example of what actually happens as an overview for those people who’re just not interested in the mathematics because they don’t need to implement it and they don’t really mind.
Ehm, so we’ll do both and in that way, hopefully, there’s something for everyone.
We shall see. So perhaps Diffie-Hellman key exchange is slightly misnamed in the sense that what we don’t actually do is exchange a key.
Because then it would be out in the public and we’d see it.
What we actually do is exchange some public variables and we combine them with some private variables we’ve kept hidden, so that we can both create the same key. Right, so we’re actually creating a key together, in some sense. So, as always, we’ll go back to Alice and Bob for this. So, let’s have Alice over here, and Bob over here.
I’m gonna sort of spread this out a bit because we’re gonna be putting these in and I don’t wanna run out of space.
So Alice and Bob are here, these are their own machines and this is a kind of public area.
So anything that Alice and Bob send to each other or agree on in public is gonna be in this area.
So as an attacker, if we want to break this key exchange, if we want to find out what the secret key is, we have to do these variables to do it, right? And that, hopefully, will explain why that’s difficult to do. Okay. So, the first thing is right at the beginning of a Diffie-Hellman key exchange, Alice and Bob will have to agree to some mathematical parameters that they’re going to use. This is a value “g”, or generator, and a big prime number “n”, right. Now for this example I’m gonna try and use colour mixing to try and explain this. I’m gonna write the letters in as well. n won’t have a colour, for the sake of this analogy. g does. So g is gonna be, ehm, let’s go with yellow.
Right now, I’m gonna sort of squirt this in and hope that it doesn’t go everywhere.
In fact, we kinda need two copies of g, really. So let’s just sort of fill it up here. Up to about… I wanna get them the same. So far so good, so far it’s not all over my desk. Alright, close enough. Alright. Ehm, well it’s kind of yellowy. Often, they’re shared at the very beginning of the handshake. Sometimes, they’re just embedded in the standard or everyone always uses the same one.
It depends on the situation. Ehm, it can take a little time and an extra message to send these things across, so sometimes having them stashed ahead of time is a good idea.
So we got g, right, this is g.
Now, Alice, to begin with, needs to calculate a private key, or private variable.
I’m gonna choose red for Alice. Here we go. I probably could have used more food colour than this kind of pale red. Is that red? Yeah, close enough.
(To Brady) What do you think? Brady: It’s rose-coloured. Mike: Now Bob is gonna do the same thing, he’s gonna have a private value that is going to be blue. Now, I haven’t chosen very interesting colours.
That’s simply because there aren’t that many colours available in the shops for food colouring. Ehm, and I didn’t go to that much effort.
There we go, that’s blue. Now, these two colours are in their private area. This is “a” [red] and this is “b” [blue], so I’m gonna label these. This is little a, this is little b.
Now, the important thing is that these are never shared with anyone. Alice doesn’t share this with the public; Alice doesn’t share this with Bob.
Now the first thing that happens is that we need to combine the private key with the generator [g] to produce a public key. Now the point is that, once we combined them we can’t unmix it, right, that’s why people like to use this colour analogy – once we pour two colours together, it’s difficult to know what colours went in. Because, yes, so if I poor red into yellow it maybe makes orange, but it could be that it was a bit more yellow and a bit less red. Or, you know, it’s difficult to know.
So there’s kind of orange for Alice and Bob’s gonna take his blue, we kinda need them to be the same level really, and it does kind of make green.
This is a bit orangy – let’s not critique me too much.
So, yeah, they’re very different to the originals and the important thing is that we don’t know what went into here, right?
We know g, but we don’t know a and we can’t find out. So this is actually, this public key here is “ag”, in some sense.
It’s got an a in it, it’s got a g in it. This one has got a b in it and it’s got a g in it, and we can’t extract the a’s, we cannot reverse this process. Now, they then are gonna exchange these public variables, but keep the private ones back. So, we’re gonna sort of draw an arrow over here and an arrow over here and they’re gonna switch them like this.
So they get sent out in clear text- These are now in the public area because they’ve been sent in plain text, everyone’s seen them. So now, as an attacker I know bg, or Bobs public part of this key, ag, Alices public component, and g and n, right?
I don’t know anything else. I don’t know what a and b are. Now, this is the final part of Diffie-Hellman.
It’s not actually very long.
You can do all this in just three messages. Alice is going to take the public component that Bob sent her and add her private key. And Bob is gonna take Alices public component and add his private key, so we’re going to get, in essence, a mixture of a and b and g, right?
That’s the idea. So let’s do that now.
Brady: So is that in the private domain? Mike: Uhm, yes, this will be done privately because these are never exchanged. So these go into the private domain now,
I mean I could make a copy of them, let’s not. So Alice is gonna add her red in, so let’s go, let’s just add some red up to about there – doesn’t really work because the red is really faint.
And then Bob adds in his blue which is gonna be like that. And hopefully, this is where it all doesn’t work or does work, these two values are kind of the same. I mean they’re not; they’re pretty close. That’s a little bit darker, perhaps because the blue is a little bit stronger. (Brady) Considering you’ve done that without actually measuring something – (Mike) Yeah. I mean obviously, you would do this normally with mathematical – err, mathematics – mathematical functions that are much more precise than my random squirting of liquids. Now, –
(Brady) So those two are now in the private – (Mike) These? Yeah, this is private.
So Alice has taken Bobs bg and added her a, so that gets “abg”; and Bob takes Alices ag and gets “abg” by putting his b in there. Right. Now the order doesn’t matter.
Remember, just like mixing colours, the mathematics is such that adding b first to g and then we add in a is the same as adding a first.
So these two values are exactly the same.
If you wanted to try and re-create this as an attacker, you can’t do it.
Because you have ag and bg and g. And, so you could mix these two together, and you’d get “abgg”, in some sense. Mathematically, this is a little bit… tenuous but we’ll talk about that in the Extra Bits.
The point is, nothing in this public area can be combined in any way to get this value or this value, which are the same. The only way to do that is to find out what a and b are, and the only way to do that is to split up one of these two public components, which is very, very difficult to do. Alright. And that’s what’s so cool about Diffie-Hellman.
In a few messages, we’ve sent some public numbers around and we’ve used our private numbers to get a shared secret that noone else can know. Ehm, now you’d generally do this at the beginning of every conversation, and you would use this number combined with perhaps some session variables or something like this to derive secret keys to use in things like AES. So this is actually just gonna be a number which will then hash to turn into an AES key or something like that. Now, the mathematics behind Diffie-Hellman is, usually, modular arithmetics. Recall that we have our public numbers g and n; g is often very small – it’s usually a small prime number: n is often very big and needs to be big for the security of this to work.
n is often 2,000 bits long, or 4,000 bits is more common now.