PKCS 1 (23 min)

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.