Secret Key Exchange (Diffie-Hellman) – Computerphile

Secret Key Exchange (Diffie-Hellman) – Computerphile


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.

100 thoughts on “Secret Key Exchange (Diffie-Hellman) – Computerphile”

  1. confused. Why can someone knowing what G is not then (ag-g=a)and (bg-g=b) i now have the private keys that they both use to make abg.

  2. can you please explain the post quantum cryptography, what is the method, what makes them resistant to being deciphered by a quantum computer

  3. It won't matter which order you put the colours in. It's only the ratios that make the difference. You can't say that because you put the blue in first it made that one darker.

  4. On password selection: Would it matter if a site assigned it's users passwords, generated randomly like password salts are, rather than letting them select their own? If it would matter, would it be better or worse?

  5. Watched the defcon presentation from years ago given by the creator of the diffie-helman key exchange… It was absolutely fascinating. Dude is an innovator and pure genius. Seems like a nice guy as well

  6. Instead of stopping at the ridiculously-overpriced-sugar-water-with-some-colouring isle, you could have stepped over to the baking ingredients isle where there is actual food colouring in useful concentrations. Oh well.

  7. Great video and execution. Always I need to know how something in practice works to know if I really need it in my project and then I need to know the math behind to reproduce myself. I just got here again after watching the math video, beause I have to go back to solidify the knowledge.

  8. But he said that often 'g' was already stashed and embedded in standard. Wouldn't it be possible for a hacker to send a request to find out what that standard 'g' is so he could split up the 'ag' and 'bg' messages later? (nevermind I watched the math version)

  9. ᧗ྯ顜硺鷤皘闍뻲Დ᧕낣㽒
    hello whats up

    ᧜࿃預硼鷖盥閻뺪Გᨃ낝㽑瞙啕鐙
    My name is Noodles

  10. if the hacker undoubtedly seized working ,because of a tsunami,why do journalist go in and tell evryone I am the hacker, they are told not to go in, it was not fun

  11. I THINK I UNDERSTAND IT NOW

    Basically it's like this

    Bob and Alice need to prove who they are.

    Bob and Alice agree to each give one another a piece of personal information about themselves in addition to some other publicly-known fact in order to come to the same conclusion.

    Alice needs Bob's information in order to make a true statement

    Bob needs Alice's information in order to make that same true statement

    Mike wants to see what Bob and Alice are talking about, so he intercepts Alice's personal fact and replaces it with his own fact.

    Bob now has Mike's personal fact rather than Alice's, so when he tries to make the statement, it isn't true; they do not match.

    Can anybody fact-check?

  12. Just a word for mac users, doing powers and module on the mac Spotlight Search doesn't (or at least didn't used to) work

    I had a friend over and wanted to show him how sexy DH key exchanges were (yeah we're the coolest kids in town), and … the spotlight app gave wrong results, so at the end of half an hour of explanations, the whole thing didn't work at all … wolframalpha saved the day in the end though

  13. This video teached me more than 9 years in primary school, thank you so much, I'm just getting started in the cyber security field and I honestly can't thank you enough.

    I'm 14 right now and I understood everything clearly, so you are a great guy!!

  14. Dimitriou Chemistry

    Would the key that my phone sends to a server always be the same (my phones part)? Or does my phone generate something new every time I connect to something?

  15. The marker sound annoying. 🙁 Can you use pen in your videos please? a lot of people hates that sound. or at least use a whiteboard.

  16. Okay I got abg on both sides. How do I use it to do stuff that can't be used by anybody else? Do I just apply it to the n I want to send and it gets decrypted using abg on the other side?

    I feel like I'm missing some basic cryptographic understanding :[

  17. You made a huge flaw while trying to explain this, which made the video just an imprecise story..
    I expected at least a question on that note

  18. Awful filming, you could have told him which camera was on and filming so we were not looking at the sides of his face or top of his head. Always best to watch the videos before uploading them.

  19. Dr Mike Pound, you never told us what is N's job. Like it was just sitting there while a b and g was being talked about. I know you mentioned N is a large prime number but is that it?

Leave a Reply

Your email address will not be published. Required fields are marked *