LogJam Attack - Computerphile

while we're recording so um I believe you owe me a video I owe you a video yep I did make a promise that I would record a video on log Jam I didn't I forgot and then there's Log Jam as well I don't know did we do a video on log Jam if we didn't I'll do a video on logger and here we are we're going to do it we're going to talk about Log Jam um better late than never Log Jam is an attack from 2015 but it's a bit of a classic I suppose in sort of a cryptography uh world I think and it's a really really interesting one Log Jam is a really interesting attack because it actually has a number of parts right so the first part is that you have to do a man in the middle attack on an exchange right and then you have to do a protocol downgrade to convince a server possibly to use a weak diffie-hellman key and then you have to break it using a number field sieve and after you've done that it you're all better off you've got in you've got all of the traffic from then on so if we look at a very very high level overview of how a TLS session works you have someone over here which is called the client and someone over here called the server and this happens every time you go to a website so you go to any online shop that's hopefully encrypted this will happen when you start so the first thing is the client sends over something called a client hello and this says I can do all of these algorithms here's a random number things like this the algorithms that they send are usually pretty good because browsers are not stupidly programmed right so you know they'll say I can do RSA I can do DS DSA but in terms of encryption I can use AES I could use Char Char and at some point during this hello they'll also say I can use diffie-hellman or I can use a thermal diffie-hellman or more recently I can use elliptic curved if your helmet so what happens here is they would send a message that says something like I can do Diffie Hellman ephemeral right now remember this is from 2015 diffie-hellman ephemeral is no longer used we usually use elliptic curved if you heldman right and actually one of the reasons is this attack you know aside from the fact that it's getting a bit old anyway now what we do as an attacker so I'm going to get my malicious purple pen is we intercept this as our man in the middle so we're a man in the middle here and we can read and manipulate any of these messages maybe we're sitting on a motor something like this we say no no we're not having that right we rewrite this message to contain diffie-hellman ephemeral export now for those of you old enough to know export grade security was the rules that the US government put in place in the 90s to limit the spread of powerful encryption so DHE export is a 512-bit diffie-hellman key exchange now that would not be considered strong enough it was still considered not absolutely terrible in 2015 except for the attacks that we talk about in a bit with the number field sieve so the server then sees this client Hello message and goes well this is a bit odd this client only supports DHE export but I suppose you know it's not an absolute disaster we'll go with that and so the server then sends back a server hello and then a number of other messages including their half of the diffie-hellman key exchange so they send a public large prime number P the generator G they send G to the B mod P and and various other things and they also compute a digital signature and that the whole TLS handshake is quite complicated but they send a very weak prime number of only 512 bits because that's what the client asked them to do now they can't actually ask them to send a much better one but the client gets this message and thinks well it's 512 bits it's not terrible all right and they then go okay so it's 512 bits so I'll generate my part of the message and so on we continue like this is the man in the middle just just listening to all this the man in the middle is listening in editing messages where they want but they don't need to edit these messages yet all they've done is they've changed the first message to pretend that the client only accepts or can understand export grade weakened security and the service kind of gone with it and at this point nothing really changes the client never sees that the server downgraded their encryption and certainly in TLS 1.2 that's the case they just noticed that the the P looks a bit small but yeah right you know we we'll move on right so if I continue this and at the end they send two messages one from the client called finished and one from the server also called finished now those are very important because these messages have a summary of both of these sets of messages and the reason that exists is because if they didn't if something like this could happen right if a client has sent DHE but the server received DHE export so their two orders of events are different right so theoretically you shouldn't be able to do this but here's the problem if you can break this key exchange at this point here then you can falsify this finished message and essentially cancel this and send a different finished message that backs up your version that backs up your version of events so the client then thinks that the server saw very well but it was meant to be DHE not export but just sent a rubbish the export key for some other reason fair enough right so the question then becomes how do we break a diffie-hellman key exchange in what is you know fractions of a second right well the first thing is you can't break it in fractions of a second so what you need to do is you need to buy yourself some time in here so what you do is to stop a timer happening you can wait for a little bit of time the server's just busy handling other requests or something he's very slow the server for some reason is on a really weak 3G Mobile connection or something like this so this takes a long time to come through what happens is the man in the middle will send some kind of TLS alerts or other heartbeat messages that kind of keep this connection alive for a little while and that'll buy you maybe a minute or minute and a half and then what you do is you use a number field sieve to break this diffie-hellman key exchange and you have about a minute to do it at which point you can recompute the shared secret and you can falsify the finished message and then you can read everything from then on right and that is a really really big problem for any internet communication and this is true this is a TLS connection but this is essentially the same for the internet key exchange that's used in vpns as part of ipsec as well so there's numerous protocols that could be weakened if you could break this so how do we break it log Jam is an attack on diffie-hellman key exchange basically and usually diffie-hellman key exchange what happens during let's say a TLS which is https uh session or an internet key exchange which happens maybe at the beginning of a VPN or something like this so you know it's quite important on the internet for making sure that we get secret keys that we can use to communicate I mean the board attack is based on this idea if you use something called the number field sieve to break a diffie-hellman key exchange but you can pre-compute a lot of the work ahead of time and that allows you to do a much quicker attack so we should say live so let's think about what diffie-hellman is very briefly and how we could attack it we talked about Diffie Helm before with the colors yes and we also did a bit of the maths as well but the answer is basically you have a function called G to the a b mod P now p is a very very large prime number A and B are secret numbers for Alice and Bob no and G is your generator which is public as well at the beginning of a session you would agree on a g and you would agree on a p now the reason this is hard to break is because you can't take this or any of the other values so for example you also see as an attacker G to the a mod P we can't take this value that's been sent out in the clear on the internet and find out what a was which we could then use with Bob's public value to create this this secret or we could use Bob's little B value to create a secret finding out what a is is cool with discrete logarithm problem and it's thought to at least be very very difficult that's the idea and there are variants of this problem but crop up and cryptography all over the place so for example there's an elliptic curve equivalent now the interesting thing about logjam is a strategy for breaking this right if you could break this then what you could do is you could man in the middle attack something like TLS and basically recompute the secret key they're going to use to encrypt the rest of the session and read everything in the session which you could imagine if you were for example a nation-state doing some sniffing would be quite a helpful thing to do so how would you do this well doing this via brute force or some other method there are various albums that make this a bit easier but none of them make it trivially easy the best album we know is the number field sieve now I don't really know how number field sieve works I don't tend to worry about it too much it's fairly complicated but the important thing to know about the number field sieve is it has four stages right there's polynomial selection there's sieving there's linear algebra and then finally there's descent that's all I know about it right now the important thing though is that you can do various amounts of polynomial selection of sieving and you can do more or less and it will make your later bits harder or easier or bigger or smaller and that means that you can pre-compute some of this and then solve it later much more quickly right key to this is that these first three stages only require the prime P that means you can pre-prepare all of this based on this Prime ahead of time right on the assumption that maybe this diffie-hellman will be using this Prime what you end up with is a giant table of data basically a giant Matrix or data that comes out of these three sections that represents essentially most of the break finally doing a center stage just keep the letters the same so using a and the generator G right so let's assume for a minute that you and I were going to do a diffie-hellman what would happen was we would agree on a g and a p that we were going to use and then we'd produce our private A and B values and we do the diffie-hellman if we knew ahead of time that this was the P we were going to choose then you could pre-compute all this and then just do this quite quickly for a short diffie-hellman key pair maybe we're talking about a week for this and a minute for this right for a much longer key pair we might be talking about a few minutes for this and a year for this on an incredibly expensive server but within reach of you know really well financed attackers exactly how the number Filter Works is not really important actually what's important is that we can pre-compute a load of this attack so that we can run the actual attack on Divi Helman very very quickly almost live right when we see an attack and that helps us do something called a man in the middle when we see a TLS session startup or a key exchange at the beginning of let's say a VPN so how do we link together well if we go back to our diffie-hellman key exchange the problem is that the initial three stages of the number field Steve use p and p has only been sent by the server here but the really interesting thing is everyone always just uses the same P because there's no real added security of using a different one every time and in fact act using the wrong one can lead to other attacks that are also a big problem so in fact it's actually pretty good practice to use similar ones every time for DHE export great security right Apache had one built in right so an Apache web server would use the same Prime every time 512 bits if it was convinced to use DHE export so we given that we knew that Apache would do this we would just pre-compute the first three stages of a number field sieve we'd wait for this message and then while we were keeping this alive we would break this using the last descent stage of the number field sieve which is not trivial you need a lot of cores but you can do it within a minute minute and a half at this point you can break the whole the whole um algorithm on its own this is already an interesting paper but there's a there's another half to this paper which is perhaps even more interesting because actually you can't convince every server to use export grade security even in 2015 90 of servers would say no no we're not using a 512-bit diffie-hellmaki thank you we'll use 768 or we'll use 1024 right now that is much harder to beat so the rest of this paper asks could you beat it though right not with a laptop is the answer to that but how much would it cost and what would the different four stages of a number field look like what kind of server would you need if you were going to do this for a thousand twenty four bit Prime there's two questions really one is you know are most 1024-bit diffie-hellman key exchange is using a similar Prime which means you could pre-compute half of the work or 99 of the work using the number field see if the answer is yes right and then given that how long would it take a server to do this and would anyone even bother right that's what's really interesting about this so let's answer the first question the answer is yes loads and loads at this time loads and loads of um https servers and many many vpns about 80 or 90 of vpns were all using Oakley group two now Oakley group two the group corresponds to the group of numbers modulo this Prime the prime is 2 to the 1024 minus two to the to the nine that's not right 960. right minus one plus two to the 64. Times by 2 to the 8 9 4 times by pi I know it's ridiculous plus 1 2 9 0 9 3. that is a ridiculous prime number and it has a generator of two all right so that's p and that's G now why this has been determined like this is not of any real significance but essentially this is what we call a safe Prime um and perhaps that's for a different video but the point was that many many internet sessions particularly on vpns were using this exact Prime at this time because why wouldn't it was a safe Prime it's a good one it's defined in an IFC IFC which I've got the IFC here it's RFC um and that was me thinking that you remembered all that you know oh yeah I know everyone thinks I can just reel off Oakley group two no no it's the internet key exchange RFC which is defined in RFC 2409 right now it's essentially a standard and there's a few other primes there's maybe two or three that most things were using but huge amounts of vpns particularly we're using this so then big question becomes Okay so we've got this Prime we know that lots of people are using it we know we can pre-compute most of the attack by using this Prime only and then when the actual key exchange happens we can try and do the last bit um how plausible is that well in this paper they calculate roughly how much computational power you would need to do this right to pre-compute The Descent stage to pre-compute all the three stages and then do the Descent stage and they think somewhere around 100 million dollars of a server in the Edward Snowden leagues there was a lot of information about various sort of secret things that were decrypting quite a lot of internet traffic and at the time everyone looked at this and went well you know it doesn't seem plausible you would you would decrypt this amount of traffic right but this paper makes a lot more sense of those documents because it suddenly makes you think well actually a nation state and I'm not particularly single in the NSA out here right any nation state with sufficient budget these are thousand bit diffie-hellman key exchanges are now in reach because they could pre-compute the number field save and then they could just do The Descent stage so what would happen in practice is you would have a bulk sniffing of huge amounts of internet traffic you'd identify VPN data and you'd send the key exchange off to some massive server to do The Descent and work out what was going on while you do this man in the middle attack or you wouldn't even do the man in the middle attack you just because maybe you're not trying to actually inject yourself into the conversation and change all the packets all you want to do is read them so you just bulk collect data bulk break keys and then bulk read all the information and analyze it later right um and so it's plausible you know as a export grade at 512 bits you could do it with a powerful server for sort of seven six eight bits you could do it you know with a very decent cluster of computers but you know sort of a university level could organization could afford it and then for the Thousand bit Keys like Oakley group two you would need nation-state level resources but it's doable this paper was released and obviously they went through proper disclosure but every single browser immediately blocked any export grade encryption Oakley group 2 was no longer used almost immediately and on anything um and we now use 2000 bit diffie-hellman Keys just like that because that's how big a problem this is you know even if no one was doing this even if the changes in budget and stone leaks were completely unrelated had something else to do had to do with something else you've still got this kind of what if though question of it's theoretically possible I always think it's really interesting when you know a paper comes out and says this could be a problem and then you sort of find evidence that actually might already be a problem uh which I think is really interesting now in practice we've moved on a few years it's not been that long actually since 2015 I'm getting a bit old um but since then we don't use modular arithmetic to do diffie-hellman anymore we use elliptic curves and we've talked about that one of the reasons is that the number field sieve in this form doesn't work on elliptic curves right so there are various attacks on modular arithmetic groups but don't work on electric curve groups which is why elliptic curves can get away with smaller keys and makes them more efficient so TLS 1.2 had this vulnerability TLS 1.3 doesn't support these kinds of diffie-hellman and also they added in countermeasures in TLS 1.3 to deal with protocol downgrade attacks where you kind of sneakily change a client hello to say something else the server reports back but that's happened in a way that's very hard for an attacker to avoid so this had a huge impact and changed the algorithms we used on the internet and TLS handshakes and all of these predefined constants because of just how serious a problem this is right even though a thousand bits at that time was seen as to be totally out of reach of anyone so really interesting story so it's sort of a robustness now what's happened is the app has gone in cropped the image down to a much smaller one which takes up less space in memory so like kind of engineeringly type things this one is getting creating removing providing criticizing so like for some reason these types of words

Channel: Computerphile

Views: 150,541

Keywords: computers, computerphile, computer, science

Id: gVtjsd00fWo

Length: 18min 47sec (1127 seconds)

Published: Wed May 03 2023