In this segment I wanna show you how RSA is used in practice and in particular, I wanna tell you about a standard called a Public Key Cryptography standard number one PKCS one. So I've already told you a couple of times that you should never use what's called textbook RSA. You should never directly encrypt the message using RSA because that's insecure. You always have to do something to the message before you actually apply the RSA function. We saw the ISO standard in the previous segment where what we did is we generated a random x, encrypted x using RSA, and then from this x we derived a symmetric encryption key. But that's actually not how RSA is used in practice. In practice things worked a little differently and typically what happens is the system generates a symmetric encryption key and then RSA is asked to encrypt the given symmetric encryption key rather than generating the symmetric key as part of [our same encryption or RSA encryption?]. So in practice as I say, what happens the RSA system is given this input a symmetric encryption key to encrypt for example this could be a, an AES key that would be like 128 bits and then the way this key is actually encrypted is first we take these 128 bits and we expand them into the full modulo size. For example, this would be 2048 bits, and then we apply the RSA function. And so the question is, how should this preprocessing be done? How should we expand the 128 bit AES key that was given to us into a 2048 bit value that can then be applied with RSA. And then furthermore the question is, how do we argue that the resulting system is secure? So in all the way of doing it which is actually very widely deployed in practice is what's called PKCS1 version 1.5, Public Key Cryptography Standard, that's what PKCS stands for. So I wanna show you how this mechanism works and in particular, I'll show you what's called PKCS1 Mode 2. Mode 2 denotes encryption, mode 1 denotes signatures so here we're gonna just focus on the encryption. So the way PKCS1 works is as follows, you take your message, this would be the 128 bit AES key for example, and you put it as a least significant bit of the value that you're creating. The next thing you do is you append sixteen bits of one to it, you know [foreign]. This is sixteen bits of one. And then the next you do is you append the random pad that actually does not contain FF anywhere inside the random pad. So this is basically something like on the order of what is it, 1900 random bits except that there are on FF's inside those random bits and finally at the very top, you put the number 02. This indicates that this plain text has been encoded using PKCS1 mode 2. And then this whole value here, this whole thing that we just created. This is just 2048 bit string is the thing that gets fed into the RSA function and is raised to the power of e modulo N. And the resulting thing is PKCS1 ciphertext. Now the decrypter of course is going to invert the RSA function, He's gonna get back this block, He's gonna look at the most significant bits and he's gonna say there's a 02 in there that means that this PKCS one formatted. Since it's PKCS one formatted, it's gonna remove those 02. It's gonna remove all the random pad up until the FF. And then anything that stays beyond that is the original message which is then used you know to say decrypt the actual body of the ciphertext. And as I said, this mechanism is extremely widely deployed, For example, it's used in HTTPS. Now interestingly, this PKCS1 version 1.5 was designed in the late 80's. There was really no security proof to argue that this mechanism is in fact secure. And as it turns out, it is very common when there is no security proof, it turns out that actually things break and there's a very, very elegant attack due to Bleichenbacher back in 1998, Daniel Bleichenbacher which shows how to attack PKCS1 when it's used for example inside of HTTPS. So let's see how the attack works. So the idea is this, supposed the attacker intercepted a certain ciphertext so this is PKCS1 ciphertext so the point is it's encoded using PKCS1 and then the result is fed into the RSA function. And we call the ciphertext the output of the RSA function. The attacker wants to basically decrypt the ciphertext, So let me show you abstractly what the attacker is gonna do. We're gonna just simplify SSL and just say that the attacker can basically send the ciphertext directly to the web server. The web server is gonna try and decrypt the ciphertext using its secret key. And then what is it gonna do? Well, the first thing it does after the encryption, well, it's gonna ask: is the decryption of the ciphertext PKCS1 encoded? In other words, it's gonna look at the most significant bits and ask: is this 02 in the most significant positions? If they are, it's gonna continue properly decrypting and then continue with the protocol and if there is no 02 in those positions, it's gonna announce an error. So if the most significant bits of the plaintext are 02, it's gonna continue with the protocol as expected, if the most significant bits are not 02 is gonna send back an error message and tell the attacker, hey, you sent in invalid ciphertext. Now the amazing thing is that, this lets the attacker test whether the sixteen most significant bits of the decryption of the given ciphertext are 02 or not. In other words, the attacker can submit whatever ciphertext he wants to the web server. The web server will invert the RSA function and then tell the attacker whether the inversion started with 02 or not. So in some sense gives the attacker an oracle that lets him test whether the inversion of any ciphertext begins with 02 or not. And it turns out that's actually enough to completely decrypt any ciphertext the attacker wants, Just add little bit of information leakage just by properties of RSA lest the attacker completely decrypt a given ciphertext. Also here's what the attacker is gonna do, well, he has a ciphertext that he wants to decrypt so what he'll do is he'll take a cyphertext and of course feed that directly into the web server and ask does it begin with the 02 or not. The next thing he's gonna do is he's gonna chose a random value r and he's gonna build a new ciphertext c prime. Which is (r to the e) c modulo N. Now what does that do? If we pull the r into the RSA function, really what we just did is we multiply the RSA plaintext, you know the PKCS1 including in m, we multiply that by r and that, that whole thing gets raised to the power of e. Okay. So that's the effect of multiplying c by (r to the e). It multiplies the plaintext by r, a value that the attacker controls. And then he's gonna send c prime to the web server and the web server is gonna say yes, this starts with 02 or no, this doesn't start with 02. So now we can abstract this problem to something more general which you can think of as the following so I have this number x in my head. This is the number I'm trying to get The PKCS1 encoding on m. I'm thinking of this number x and then what I let you do is for r, which way r of your choice I will tell you whether r times x mod n starts with 02 or not. And it turns out by asking enough questions it turns out either by million questions of this type, you can basically recover all of x. Just by learning whether r times x begins with 02 or not by asking enough questions, you can actually recover x. So in reality what this means is that the attacker can capture a given ciphertext. This maybe corresponds to a ciphertext where the user enters the credit card number or a password, and now the attacker wants to decrypt the ciphertext. What he would do is he would send about a million ciphertext like this, the web server for each ciphertext is gonna respond whether the plaintext begins with 02 or not and at the end of the attack, the attacker just blocks away with the, decryption of the ciphertext c. So this might seem a little magical to you, how are you able to just from learning whether the most significant bits are 02 or not, how you're able to recover the entire plain text. So let me show you a simple example of this. I'll call those bab y Bleichenbacher just to kinda get the idea across on how this attack might work. So imagine that the attacker is able to send the ciphertext c, the web server is gonna use the secret key to decrypt but let's suppose that instead of checking for 02 or not, all the web server does is he asked is the most significant bit one or not. If the most significant bit is one, the web server says yes. If the most significant bit is not one, the web server is no. Moreover, to simplify things, let's assume that the RSA module is n is a power of two. So n = two^n. Of course, this is not a valid RSA modulus. An RSA modulus used to be a product of two distinct primes. But again, just to keep things simple, let's pretend for a second that n is actually a power of two. So now you realize that by sending the ciphertext c over to the web server, the adversary just learn the most significant bits of the plaintext x. Basically, the servers behavior completely reveals what the most significant is. Now what the attacker can do is he can multiply the ciphertext by two to the e. Now multiplying by two to the e has the effect of multiplying the plaintext x. By two simply multiplying x by two and because we're working mod two to the N, multiplying by two basically means shift left, okay. So now when we shift left in fact we get to learn the most significant bits of 2x which is really the second most significant bit of x, okay. So, again the most significant bit of 2x basically we shift x to the left. And we reduce modulo n. So now, the most significant bit of 2x modulo n is basically the second most significant bit of x. So now we learned another bit of x. And now we're gonna repeat this again. We're gonna query a four to the e c, That corresponds to querying of 4x to the power e. Querying of 4x basically reveals the most significant bit of 4x mod n. 4x four corresponds the shifting by two bits. Which mean now we get to learn the third most significant bit of x. And when we repeat this again, and again, and again for different multip les of c and you can see that after just a few queries, about a 1,000 or 2,000 queries, we'll recover all of x. The reason Bleichenbacher needed about a million queries is because he wasn't testing for one, He was actually testing for 02 or not 02 and that basically means that he needs instead of 2,000 queries he needs actually a million queries but that's still enough to recover all of the plaintext text. Okay? So I hope this is explains why this attack is possible. Why just this little bit of information about the most significant bits of the RSA inverse is enough to completely decrypt RSA. So the bottom line here is that PKCS1 as implemented in web server as up until this attack was discovered was basically insecure because the attacker could essentially decrypt a ciphertext he wants just by issuing enough queries to the web server. So how do we defend against this attack? Well, so the SSL community basically wanted the minimum change in their code that would prevent this attack from working and so if you look at the RFC, what they propose is the following. Well, there's a lot of text here but basically what they propose is to say that if after you apply the RSA decryption, you get a plaintext that's not PKCS1 encoded. In other words it doesn't start with 02. What you're supposed to do is basically choose some random string r. And just pretend that the plaintext is just a random string r and continuous as nothing happened and of course the protocol will fail later on. So to be concrete you see if the PKCS one encoding is not correct, what you would do is you would just say the premaster secret is this random string or that we just picked up off thin air and let's continue the protocol and of course the session set up will fail because the client and the server will end up agreeing on different keys and that will cause the session to terminate. So we actually don't tell the attacker whether the plaintext begins with 02 or not. All we do is just pretend that the plaintext is some random value. So this was a minor code change to many web servers and it was fairly easy to get deployed and in fact most web servers out there today implement this version of PKCS1. However, this kind of raises the question of whether PKCS1 should be changed all together so that we actually are able to prove chosen ciphertext security. And that brings us to a different way of doing encryption using RSA which is called Optimal Asymmetric Encryption Padding, OAEP. And in fact the PKCS standard was updated and PKCS1 version 2.0 actually has support for OAEP which is a better way of doing RSA encryption. So let me explain how OAEP works. So OAEP is due to the Bellare and Rogaway back in 1994. And the way OAEP works is as follows. So you take your message that you wanna encrypt this for example could be the 128 bits AES key. And then the first thing you do is you append a short pad to it. So in this case, you put a 01 in the beginning and then you add a whole bunch of zeroes. How many zeroes is actually depends on the standard but you know that's supposed like they're 128 zeroes in here. And then you also choose a random value so that this whole string is as big as your RSA modulus so let's just say this is 2047 bits. Now before you apply the RSA function, you first of all take the random value that you chose and you feed it into the hash function. This hash function produces a value that's as big as the left hand side of your encoding. You XOR the outputs. You feed the result into another hash function which we call a g. You XOR that with a random value. And then finally, you get these two values that you concatenate together. Okay, So, you concatenate either left side and the right side that gives you something that says is 2047 bits long and that's the thing that you apply the RSA function to. And the result is the RSA encryption. Now there's a theory that was proved in 2001, due to Fujisaki, Okamoto, Pointcheval, and Stern, that shows that in fact if all you do is you, you assume that the RSA function is a Trapdoor permutation, a secure Trapdoor permut ation, but in fact this mode of encrypting using RSA is in fact chosen ciphertext secure but we have to assume that the functions h and g are kind of ideal hash functions as I said these are called random oracles. Basically, we assume that h and g are just random functions from their domains to their range. In practice of course when OAEP is implemented, people just use SHA-256 say for h and g. Why is this called Optimal Asymmetric Encryption Padding? Why is this o? Why does this stands for optimal? Well, the reason is if you look at the ciphertext, you'll notice that the ciphertext is basically as short as it can be. The ciphertext is exactly the length of one RSA output, there are no trailing values that are appended to the ciphertext whereas for example, the ISO standard if you remember even if you had to encrypt a very short message, what you would have to do is you would have to encrypt x using RSA and then append to that x, the encryption with the short message under the symmetric encryption system. So even if you have just to encrypt a 128 bit AES key, with the ISO standard you would get one RSA output plus a symmetric cipher whereas with OAEP, you just get one RSA output and nothing else so in that sense, it's optimal, Optimal in terms of the length of the ciphertext. Interestingly, this theorem here really rely on properties of RSA. And in fact, the theorem is known to be false if you use a general trapdoor permutation. Some other permutation doesn't have the algebraic properties of RSA. So that left this question of if we have a general trapdoor permutation, what is the correct way to do OAEP? And it turns out, there's a minor modification to OAEP which makes the result more general. This is a result due to Shoup back in 2001. Just shows that if you give me a general trapdoor permutation f. It turns out if you replace the fixed pad that's using OAEP by a hash function, this hash function w, which happens to be a hash function of the message m and the randomness r that you're encrypting with, and then during decryption, you actually check that this hash function value is correct. So when you decrypt, you actually check the w of mr is really what's written in this position in the plaintext. If you do that then basically this OAEP called OAEP+. Is in fact CCS secure, Chosen Ciphertext Secure for any trapdoor permutation. You don't have to rely on a specific properties of RSA. There's another result called Simple Asymmetric Encryption Padding, SAEP+ which basically says that if you are gonna rely on properties of RSA, then in particular way with RSA when the public exponent is equal to 3, it turns out you actually don't need the second stage of encryption. The simple padding scheme here again using the function w is actually already enough to guarantee chosen ciphertext security. So these are variants OAEP but they're not really used. I just wanted to mention and to let you know they exist. These are not really used mainly OAEP has been standardized is what's used. Although again in reality, the most common application of RSA for public encryption is in fact this PKCS1 that's standardized in the HTTPS RFC. So just to make sure it is clear in your mind how decryption actually works, let me ask you, how would you decrypt an SAEP ciphertext ct. So here, you're given the ciphertext ct here and the question is which of these three methods is the correct way of decrypting the ciphertext. So the correct answer is the first one and let's see why. Well, given the ciphertext the first thing what we need to do is apply the RSA inverse functions, the ciphertext and that will give us the RSA plaintext which happens to be in this case x and r. So we get this x and r here. The next thing we need to do is we need to hash r using the function h and XOR the result with x and that will give us m and wm, r. And the last we need to do is to make sure that the pad W(m,r) is correct so we check that in fact w is equal to W(m,r) and if so we output m and if not, we output bottom to say that the ciphertext is invalid and the decryption algorithm rejects it. And by the way I'd like to emphasize that this checking of the pad during decryption is crucial in all of the schemes that we just saw. So for example, in both OAEP+ and SAEP+, it's doing decryption. It's very important to check that the pad is in fact correct so that the value of w that you get here during the encryption really is the hash under the capital W of m and r and similarly on OAEP, it's very important to check it during decryption. In fact, the value of the pad is the constant 010000000. And of course if it happens to be not 01000 then you output bottom and you say the ciphertext is invalid. The last thing I wanna point out is that actually implementing OAEP can be quite tricky and let's see why. So supposed you have, you write an OAEP decryption routine that takes the ciphertext as input. The first thing you would do is you would apply the RSA inverse function to the ciphertext and you would say well, you expect to get an n bit value out, you know 2047 bits in the case of 2048 bit RSA modulus and if you get something that's bigger than two to the 2047, you say reject. We say error = one and we go to Exit. The next thing we're gonna do is we're gonna check whether the pad is in fact the correct pad and again if the pad is not the correct pad, then again, we're gonna reject and go to Exit. The problem with this implementation is well by now I hope you kind of guessed it is it's vulnerable to a timing attack, right. So essentially by leaking timing information the attacker can now figure out what caused the error. Was it, that was there an error the RSA decryption happened to be too big or was there an error because the pad happened to be too large? And if the attacker can this distinguish these two errors say by timing. Then it turns out similar to the Bleichenbacher attack, it's possible to completely decrypt any ciphertext of your choice. Just at very, very, very small leak of information would completely allow the attacker to decrypt completely any ciphertext that he wants to. So this shows that if you, even if you implement the mathematics of OAEP decryption correctly, you can very easily mess up and open yourself up to a timing attack which would make your implementation completely insecure. So as usual, the lesson is, don't implement crypto yourself in particular, RSA OAEP is particularly dangerous to implement yourself. Just use one of the standard libraries for example, OpenSSL has an OAEP implementation and of course what they do is very careful to make sure that the running time of OAEP decrypt is always the same no matter what causes the error. Okay, So let's stop here and then in the next segment we'll talk about the security of the RSA trapdoor permutation.
