Key Exchange Problems - Computerphile

Key Takeaways

we had a few interesting questions on the diffie-hellman video so let's explore a little bit more about what we can do with diffie-hellman and what we can't do or shouldn't do with tiffy hellmann um so let's talk about man in the middle attacks and how they're a real problem for different helm when it's used on its own and that's where we bring in rsa or public key encryption uh to help us we won't go over too much of diffie-hellman again right plenty of videos on that already but let's remember we've got good ol alice and bob and we have some shared parameters already so a generator g and a large prime number n and they're going to share some information and calculate a shared key so alice is going to generate a private value a bob is going to generate a private value b they're going to share and i'm going to simplify the notation you know a lot here just so we don't spend eight is writing it out but alice broadly speaking will send bob g to the power of a like this so g to the power of a and bob will send g to the power of b and they use that to both calculate g to the a b all mod n right so g to the a b what this allows us to do is share two values in public and use them to calculate with our private value something no one else can do right that's really helpful but what this doesn't do is provide any protection from someone sitting in the middle here and intercepting these messages so let's look at a different version of this where there's someone nefarious in the middle let's call him sean so same again alice and bob and now we have shawn sitting in the middle now sean has control of this network that's the issue right so you can not only read the message but you can also intercept messages transmit messages again you know this kind of stuff so let's say you're a rogue admin or something like this so alice produces her value a right so maybe bob is a server maybe bob is a shop and alice is a client so she's going to send the initial message that says i'd like to talk to you let's establish a shared secret so alice is going to calculate g to the a and send it off to bob now sean doesn't let that through right that's the problem sean intercepts that message and stops it and pretends to be bob from then on so sean comes in here and goes oh yes i'm bob right and he isn't so he generates a private key s and a value g to the s and sends it back and as far as alice knows this is g to the b yeah there's nothing in here that says this is particularly sean bob could have generated the same we're calling it s but it's just a number it could have been progenerated by anyone so he sends this back they perform a normal key exchange and they end up with g to the a s so sean has now an established shared secret with alice so far so good now sean then then knows that alice wanted to talk to bob originally so then sean says my name's alice can i establish a shared secret with you so sean sends g to the s over to bob and bob goes ah brilliant and sends off g to the b back to shawn and they establish a shared secret g to the sb or bs or you know whatever right g to the s b what sean has done by sticking himself in the middle here is calculate two different keys both of which he knows and he can then use them to intercept every single message between alice and bob so alice then sends some actual http traffic or something like this encrypted with a key derived from this sean can immediately decrypt it re-encrypt it with sb send it off to bob and essentially act as a man in the middle every step so every time a message is sent decrypt it read it do whatever you want change it re-encrypt it and send it on right this is a huge problem because diffie-hellman provides no way of stopping this that's not what it's designed for it's designed for two parties i suppose that trust each other to generate a shared secret if you start throwing other people into it the whole thing breaks this is where rsa and other public key cryptographic schemes come in and rescue us to me straight away d helmand is dead in the water right right jeffy helmet's in real trouble here um but luckily it isn't the only public key protocol we've got um so this is what rsa does let's imagine that bob is a server so he has a public key and a private key associate let's say rsa or dsa it's not important so we have alice and bob again i'm going to get tired of naming these i should have just put a and b bob has a a private key and a public key so remember that back to the video that rob did on public and private key and the things we discussed in the past anything you encrypt with key a can only being decrypted with key b like on wannacry and so on the public key is given out freely it's not probably on bob's certificate um the private key he holds back so this time alice wants to talk to bob what we want to do is ensure that no one is sitting in the middle of this conversation also as it happens we'd quite like for bob to verify his identity because we want to make sure we trust the server so we can bring that in as well alice sends g to the a over to bob just as normal we're assuming that the generator and the and the prime number have already been established we're not worrying about this bob is going to send over g to the b but to stop anyone from sitting in the middle he's going to bring his private key and make sure that alice knows only he could have sent that message he sends g to the b as well as a a hash of this message or a digital signature of his message signed with his private key which would be you know something like a hash of g to the b that's too many brackets and then all signed by k private so if he's signed it with his private key the only thing that can decrypt that makes sense of it is his public key yes that's right so what alice will do is something called a signature verification so she will take g to the b perform the exact same process and then apply the public key to his encrypted version and see if they match and if they do she knows that only he could have done that because only he has the private key this is assuming he hasn't given the private key away we hope we like to make that assumption otherwise everything breaks what he does by sending this over is alice still gets g to the b like she did before but she can combine with a to get g to the a b but shawn or any other anyone else nefarious are when the first people are available if they try and use a different value they won't be able to sign it with the private key that bob had right if they can that's a real problem but they can't so bob is able to send a message to alice but not only shares his diffie-hellman parameter which is something that needs to be done anyway as part of the key exchange but also sign it to ensure that only he could have sent that message now this is this is a fundamental part of numerous internet key exchanges so the ike protocol that's used in vpns and the handshake using tls or anytime you see https this is the kind of thing you're going to see i mean in fact if we go to a standard website this is google chrome's security overview that is telling us what the handshaking tls establishes as a cipher suite for our communication with this server and you can see we're using tls 1.2 elliptic curve jeffrey hellman and rsa so we're not using diffie-hellman on its own we're combining it with rsa in this kind of mechanism such that no one can be a man in the middle and intercept our messages and interfere with them it does sound like we are potentially over complicating this i mean if we've got rsa why do we need diffie-hellman um yeah you're right so technically speaking we don't right technically speaking we can use rsa in let's say a tls handshake and historically that's what's been done so what would happen in that situation is alice would generate a shared key and encrypt it with bob's public key such that that way she knew only bob could ever read that secret key and then they'd carry on the conversation the the issue is one of something called perfect forward secrecy so the problem is that if you did this if you if you used only rsa ever to perform encryption right then if anyone ever breaks that rsa key or hacks into the server and obtains it or hardly turns up and gives it away then someone who's been recording messages between the two suddenly can decrypt everything right they've to go for all the handshakes so they can decrypt that symmetric key every time and decrypt every single historic message that's been sent between alice and bob so diffie-hellman is a more of a kind of per session deal right yeah diffie-hellman rsa keys are established and dsa keys are established over a long period of time let's say one or two years and to to save us a real problem if they get broken we don't tend to use that for the actual encryption what we tend to do is generate something called an ephemeral diffie-hellman key ephemeral meaning we do it pretty much every time and um we general we actually use them to generate the shared secret and we use rsa to provide this authenticity right so it's a combination of both diffie-hellman gets us a very quick way to establish a shared secret but it's only used a few times rsa gives us a way of verifying bob's identity and making sure there isn't a man in the middle and we don't tend to use rsa anyway for long-term encryption because it's too slow for a whole message so that's why we use it to derive symmetric keys and use something like aes which is much much faster and this time is 2048 bits so our private key is going to be some this is our a and this here is our g to the a mod n and they're roughly roughly the same size this will be slightly smaller