The Private Key Mistake! (TLS Key set to "4") - Computerphile Transcript

00:00 So last Wednesday I woke up and I saw in the news something that I genuinely couldn't believe which is that um a certificate authority we'll talk about in a minute what that means use a private key with the value four that is not 400,000 million whatever right the number four how big is a typical private key supposed to be how how many digits do you reckon It's got to be like 32 like bits or something like that.

00:34 >> Yeah. Way more. Way more. Yeah. Uh 300 on the top of my head. 384. Um so that would be about 120ish digits. >> Okay. >> And they decided to use just one >> and lots of zeros maybe. >> And lots of zeros. Yeah. Yeah. Um >> so is this like Sesame Street? Today's episode is brought to you with the number four. >> Yeah, exactly. Yeah. Sesame Street and every Muppet can hack it.

01:00 We'll investigate first of all what the uh consequences are. Uh we can look at uh what could have possibly happened and we're going to look at how can I hack it myself. So let's talk about the public key infrastructure. I know that you have a video on this already uh but it might be worth having a quick recap. Um, so if you want to make a connection, let's say to your bank or to Google or it doesn't even need to be a secure site like the BBC, right?

01:32 You may notice that in your browser you get a little lock symbol and you know, okay, that means the connection is secure. What goes on behind the screen is that it sets up a so-called TLS connection. Now, in order to set up a TLS TLS connection, you need to know the public key of the website that you're talking to. Let's go with the BBC as our example.

01:55 So, that means that if I set up my TLS connection, the BBC will claim to have a key. But now the question is, how do I know that this key really does belong to the BBC and not to a hacker who's pretending to be the BBC? They intercept my connection and they say, "Oh, I'm the BBC. Here's my key." Right? Well, in order to know this, in theory, we could store all the public keys on a computer, right?

02:23 But that's not manageable. So, instead, we can request a so-called certificate. So, what that is is it's basically like a contract and it says BBC.co.uk. So, that means that I know that this is who I want to be talking to. and it has a copy of the public key on it which I can verify is the same public key but then all of that is signed by a so-called certificate authority with their key now perhaps I know this certificate authority but probably not right so how do I then know that I can trust the signature so this is

03:07 an entity who says the public key of BBC is definitely this public key. But how do I know that they are telling the truth? Well, I don't. But they can then again have a certificate that matches the issuer name. So I didn't write it here, but of course there's a name for the issuer. So you write the issuer name. Issuer. That's not readable. Doesn't matter.

03:37 And it has the issuer's key on it. and that is signed by a so-called intermediate authority with their own signature and their own key. Now the question is how do I trust this intermediate certific uh this intermediate uh certifier right? Well it ends with the so-called root certifiers. So they are entities where I do store the public keys on my hard drive.

04:02 So they write their own little certificate for the intermediate with the issuer name. It's got the intermediate key and it is then signed by final caller >> confused the wall. I'm impressed >> by a root. So if we set up the TLS connection, what we get is we get these four entities. We can verify that this public key is in our own memory and that's a so-called root certificate.

04:32 So that means we trust this certificate. We trust whoever signed this. Then we look at the contents and we say okay they say that this key belongs to that intermediate certifier. So that means that I now trust this key which means that I now trust uh the contents of this certificate which are telling me a leaf certifier. So one that only does websites that's their key and then I look at the actual certificate for the website of the BBC which contains the correct key for the BBC.

05:03 And that's how the infrastructure tends to work. Now these chains can be slightly longer or slightly shorter. But this is I would say a typical typical length because we don't want the root certifiers to do too much work. How these signatures work is it's called asymmetric cryptography because it's asymmetric. I know you've had several videos on this topic.

05:23 So the idea is that you have a so-called private key and a public key. Now with this private key you can make a signature which anyone with a public key can verify. Now of course if you give me your private key it means I can now sign stuff on your behalf. Right? So if I somehow manage to obtain your private key it means that I can pretend to be you.

05:48 Here's what happened. This signature here is based on a public key. Now the public key looks normal but behind the scenes there's a private key. So there's a mapping between this key and the private key. So this is the private key. And what is the private key here? It's the number four. So that means that anyone who brute forces this will get it in four attempts.

06:12 Which means they will obtain a private key which means that they can now put signatures as if they are the company in question. Emraudra is the organization responsible for this uh fiasco. I wonder how that happened. I can't imagine. >> I have to fully agree with you. So, I took a little bit of time this weekend to build a script to brute force it. And in doing so, I realized to get the tools that you use to do cryptography to accept for as a private key, you really need to work hard.

06:45 And let's talk about that. So, I downloaded all the uh broken certificates from the internet. If you Google them, you'll be able to find them. So, why don't you select one of the certificates at random and we'll play with it. >> Let's go with the one below the mouse now. That one. >> This one. Okay. So, I'm going to make a copy of this one. So, now I've just renamed the certificates.

07:08 The contents are the same. I just don't want to have to deal with spaces because that's annoying for scripts. Okay. So, this we know that this is broken, but we don't know which value it has. Um, according to the press release, it wasn't just the number four. Also the numbers 56, 151, 66, 155, 156, 230, and 237. None of those being particularly good choices.

07:36 >> What What do you mean by a good choice? Do you mean just a complicated number? Uh so if I picked any element at random um imagine if you picked a number between zero and a million at proper random you would expect it to typically have six digits maybe five but if someone says four you say this is not at random. Now here we're talking about six digits.

07:57 Now imagine the same thing for 120 digits and they say I picked four at random. No you didn't. Um and by not picking it at random it means that you're open to brute force attacks. So let's say that I'm I don't even know that these are broken. I'm just for fun seeing if maybe they are broken, right? Because this is what presumably happened for the discovery.

08:20 Someone just for fun decided to pick random certificates from random people and see if anyone was um dare I say dumb enough, >> foolish enough. >> Foolish enough. Thank you. Um to use silly small keys. Um, so that's exactly what we're going to do. Now, let's first investigate what we have, right? So, we have a file called computer file.c. And we can, for example, open this in notepad.

08:46 And what we see is is basically nonsense, right? Not really readable, right? It says begin certificate. That that bit I understand, an end certificate. Um, and everything else here is so-called base 64 encoding, which means that this is not intended for people, but we can actually read it if we want. So I'm going to use open SSL and I hope that this gives us a readable version of the contents.

09:09 Yes, it does. So it tells you all sorts of information like what are we using for the hashing? What do we use for the public key? Well, this is the relevant information, right? So the public key here is what we suspect is broken. >> So are those hex codes? >> Yes. So the these are hex codes and uh if you add them all up it should come out to 384 bits.

09:35 Um which means that if we look at the private key it will be 0 0 0 0 all of these are zeros 04 right. So that's why it's problematic. So here in text form it has all the information that we just showed in that diagram. Okay. Okay, so we want to extract the public key from here. Uh so we again load the computer file certificate and we simply say uh that we want uh the pub key public key and we want to output that into um so-called PEM file which contains keys.

10:21 Give me a name for a PM file. Um Tim >> Tim. There we go. So now it should have created a folder uh sorry a file called uh tim.pm. Let's refresh this. There we go. And if we then open this in notepad, we see that we have the public key uh followed by the certificate. Um, and that is because I forgot to tell it not to add a certificate at the end, which is what I'm going to do now.

10:53 No out. And now it should if I open it again. So this is the public key which is the same as the value that we saw here. Now in order to demonstrate that we can open that file as well. Open SSL EC and then we want to load tim.pm pen in. Now, by default, it's expecting a private key. So, we need to tell it actually we're just giving you a public key and then we want to display this text and we don't want any other stuff to be output.

11:29 And here we see the key and the algorithm. Now, if we go back up, just remember the first couple of digits 0425 dB and it should match 0425 dB. So we've now successfully exported the public key from the certificate. Now for the brute force algorithm, what I'm going to do is I'm going to generate public private public key pairs with increasing private key.

11:59 So starting at 1 2 3 4 5. Now the way in which this works um is not always true but for this particular algorithm this particular elliptic curve it's true uh that the public key will be uniquely defined by the private key. So that means that if the public key matches this public key we know that we found the correct private key. So we need it to be the case that every private key can only have one possible public key otherwise that test wouldn't be good enough.

12:28 But in this case it is. So that's going to be my test. Here I run into the first problem. Let's say that I want to generate a key. I'm going to look up how do I generate a key asking for help and I notice that there's a function genp key. Okay, so that's probably what I need to use. Open SSL genp key. How do I use you? Asking for help again. And it will tell me what I can do, what I can give.

12:54 Now, noticeably absent from here is the option to introduce a private key. OpenSSL doesn't want me to tell it a private key. It wants to randomly generate a private key because that's how you securely create a private public key pair. So there's no option for me to actually tell it create me the the key pair with private key one. Now this is something I ran into as a problem when I was brute forcing it because I need to tell it it's one.

13:23 But that makes me wonder what on earth did they do over there? They say they used um hardware, specialist hardware to create private public key pairs, which is a good habit, but they must have done something really strange to be able to determine the private key because by default, not just by default, there is typically no option to to supply your own private key.

13:47 Now, I'm going to do a workaround, a workaround that works, but I can't imagine that's what they did. So I really struggle to see how they managed to use four as a private key. Um if you use maybe they programmed their own cryptography tools, I don't know. Um but if you use the existing uh tools, you shouldn't be able to do this. So that's the conclusion from here, right?

14:17 We cannot provide it with a private key. Ah, but let's generate just a random private key and and and see if we can work from there. So, I'm going to use this command open SSL. Uh, and then what was it? Uh, genp key. And then the algorithm we want to use was uh elliptic curve. And the specific uh parameter for it was the curve P 384 which has the name SECP P 384R 1 uh P key op.

15:02 So here we should have all the settings correct to create a private public key pair with the same algorithm and parameters as the key in question. And we see that the key is being output here. Now I actually want to store it on disk. So I'm going to say out um how do you want to call this one? >> Sean. >> Sean. There we go. Uh and that's also a PM file.

15:28 So any private public key, anything can go in a PM file. So now if we investigate that PM file, it should say begin private key and private key, right? >> Whereas this one said public key. That's for us the only noticeable difference. But we know now how we can read the contents of um of the key. So that's exactly what we're going to do. Um so I'm going to load in sea.pam and I'm going to say I want it in a readable format and nothing else.

16:02 And then we see that it actually contains both a private key and a public key. Now, how did I come up with a way to create a private key with the number zero? Well, it turns out that if I remove the public key here and I load in the private key, it actually reconstructs the public key from the private key, which it can do. So, I can actually remove this bit from the certificate manually and it will still fix it and it will work.

16:33 But then I can also change these values with experimentation. We can change a value in shan.pam. Right? Let's say that we changed these three values here to a aaa. And I save the file and I load it back in again. Now what we notice here is that we have a sequence of zeros because the capital a is the base 64 encoding of 0000 0. If we put a bunch of a's, we get a lot of zeros.

17:08 So by trial and error, I've just started replacing these with A's until I've reached the end of the public key. Then realized that because of the rounding, the next character contains just four bits. So that means that there's one of four special possible characters. Um and I've also then determined which bit is the public key, i.e. the bit I can remove.

17:30 Now after having done so, we ended up with this. So if we lo load this key, we see that it's much shorter because I've removed the public key information and we see that there's a bunch of A's, right? So if we load this one in test key3.pam, what we'll see is that this key is all zeros and that means that it's invalid and the public key is zero. And this is the basis for our first script that we're going to look at.

18:03 So here we have something that can only be described as an ugly Python script. Um it doesn't quite brute force all values, but it does uh quite a few of them, more than enough to to crack this. Um so we just looked at this saved file and we said, well, we can modify the uh the private key by changing the individual values. So if I change this K here to let's say Q, there's actually only four valid values I can put in there and I have to cheat.

18:38 Those values are K, capital K, lowerase A, lowerase Q, or the number six. >> So is this like machine code for those particular numbers or whatever that we were talking about before? >> No. Um, >> it's just a way that it's encoded. >> It's the way it's encoded. So we we needed four bits from them. >> But the letter here already starts encoding what we see here some of this information.

19:04 >> Okay. >> And because that information is there, we can't lose that. >> And so it's only the first two bytes that are different. So I had to I just manually looked up in the table how do I how do I get gaps of 16? And it turns out those are the four values. So they encode >> the same four bits that way. But then the other two bits are variable. B 64 encoding breaks up bytes not along because a bite is 32 bits.

19:31 But B 64 is 64. So it doesn't break up bytes by bite. And that's why we get leftover bits that we have to deal with. >> Okay. >> Um so here we have to deal with two leftover bits. And that's why there's four possible values. And so Q I believe corresponds to the number two. So let me just reload it. I didn't save it. And we see that now actually we get a public key that's meaningful because it's detected this private key.

19:59 No public key. So it computed the public key and now we can compare this public key to the public key we already have. Right? Um so that is the the three steps. So we have a script that takes a number and outputs a private key as a file. Then the next step is to read that file in open SSL so that it generates the public key. Now to brute force it all we need to do is we need to loop with a good old goto where we call the script to get the private key.

20:32 It will write it to the file. Then we do an open SSL just like we did manually before where it opens the script and takes the public key out and saves it in a separate file. Then we compare the separate file to the public key that we've created. If they match, it will exit. And if they don't match, it will simply increment the number. >> So once the Python scripts opened open SSL with your choice of private key, but no public key, SSL will generate the public key.

21:02 We save that off into some kind of temporary file and then compare that with something that we saved earlier. Is that right? >> Yes. So we created tim.pm PM which was just grabbing the public key from the certificate and saving it in a separate file. >> So it's then comparing the files and not actually the public keys >> because we know that if the public key is the same the files will be the same.

21:26 >> Right. Okay. So, if we brute force it now, that's easy. Brute force and we'll start counting until it hits the number and hopefully it's one of the numbers that matches the broken one. >> Okay, this could be a long uh recording. >> Could be halfway. Ah, we're there. 115. So, that's sort of in the middle. Some numbers were in the 200s and some were in the tens.

21:53 Um, so 115. uh just to verify that is indeed one of the numbers that was reported to be one of the broken >> keys. So that means that if I now want to sign a message, I now have the private key. I can sign a message and then use that certificate to verify it. So now we know that the private key is 115. Um which and we have the corresponding public key.

22:16 That's that's the easy bit. Um, but that means that we can use that private key to sign messages on behalf of Emodra. So if we go back to here, it means we just found the secret key which allows us to create a signature for a lower certificate. And then it will validate that as true because the correct key is used. So that means that I can create a certificate that says uh this is the public key of the BBC but put a fake public key in there, >> one that I have the private key to and then sign it with this private key

22:54 that's just 115. And now someone who receives this certificate will verify it and the verification will pass. The verification will pass because I'm using the correct key. Now, if I were to do this on my computer right now, what do you think will happen if I do the verification? I >> I'm hoping by now it's all been fixed. >> That's right. That's right.

23:14 So, the verification will fail because the higher certificate now no longer acknowledges the lower one. Won't go into details about that. Um, but if I tried this on my computer, the attack would fail because my computer is up to date. If I use a computer that hasn't seen the internet from last week and I did the same thing and I did verify, it would actually pass.

23:35 So this was a dodgy Python script where every operation took about a second when in reality it should take about a millisecond uh at least a thousand times faster than this. But even then I found it relatively quickly. Um and you know if you did it the proper way it would have been a thousand times quicker. It doesn't matter in this case. Um, but I just wanted to point out that even if you did the brute force method, you know, efficiently with a good script thousand times a second, you know, you'd never be able to find

24:06 a properly generated private key in a million lifetimes using as 128 bit key gal counter mode using the key that we just derived and so on. So they're then going to send a finished message and that finished message is going to contain a summary of all of the messages so far encrypted, right? I'm using nip the cake.