So What Are RSA PCKS#1.5, RSA OAEP and RSA PSS — And Why Is It Important To Pick The Right One?

So, let’s get the acronyms out of the way. With PCKS, we have Public-Key Cryptography Standards, and which are standards that were defined…

So What Are RSA PKCS#1.5, RSA OAEP and RSA PSS — And Why Is It Important To Pick The Right One?

So, let’s get the acronyms out of the way. With PKCS, we have Public-Key Cryptography Standards, and which are standards that were defined by RSA Labs. With PSS, we have Probabilistic Signature Scheme, and OAEP is Optimal Asymmetric Encryption Padding. And, if you don’t know what RSA stands for, you should probably not be reading this article.

The PKCS standards are one of the foundation elements of the Internet and were drafted by RSA Labs. In one of the original specifications for RSA, we saw it defined in PKCS#1:

It contained the methods of PKCS#1.5 and OAEP:

Basically, we have since found that PKCS#1.5 is open to a range of attacks [2] and that the OAEP method was more secure. No one should ever code with PKCS#1.5 in a production environment these days. Then, in 2003, the PKCS#1 standard was upgraded with Version 2.1:

Its main addition was RSA-PSS, and which is based on a paper by Bellare & Rogaway [3]:

It should be noted that OAEP is based on other work by Bellare and Rogaway [1].

RSA — The Rock of Trust

The RSA method is still around and is still used fairly extensively in digital signing — in fact it is the default signing method used with JSON Web Tokens. Also, most of the digital certificates that are used on the Internet still use RSA as their signing method. So while Bitcoin and Ethereum have dumped RSA in favour of ECDSA (and based on ECC — Elliptic Curve Cryptography), RSA is often used in many applications, including with OpenSSL authentication.

RSA signing can be seen as opposite to the encryption process, and where we operate on a hash of the message. In RSA, we have a modulus (N) which is based on two prime numbers (p and q):

N=p.q

We then have a public exponent (e- the verifier) and a private exponent (d — the signer). Initially, we hash the message (msg):

h = hash(msg)

Then, we use the private exponent to determine the signature:

s = h^d (mod N)

To verify we take the public exponent and make sure that:

hash(msg) == s^e (mod N)

Unfortunately, pure RSA signing is open to a number of attacks, and which can be overcome using either RSA-OEAP or RSA-PSS.

PKCS#v1.5 Should Never Been Seen!

The simplest way to pad the input data to RSA is to use PKCS#v1.5. With this, we pad to the start of the message bytes, and where the first two bytes are 0x00 and 0x02, and followed by a number of non-zero bytes. We then add a 0x00 byte to identify the end of the padding and then followed by the message bytes:

0x00 0x02 [some non-zero bytes ] 0x00 [message bytes]

When unpadding, the 0x00, 0x02 sequence is detected, and then we search for the 0x00 byte and take remove all of the preceding bytes. Unfortunately, Daniel Bleichenbacher published a paper [2] that showed how the PKCS#v1.5 padding method could be cracked with a chosen cipher attack: [here]:

The Bleichenbacker’s attack has been continually compromising some systems for decades, but TLS 1.3 now overcomes it by dropping support for PKCS#v1.5. To overcome the weaknesses of PKCS#v1.5, we can either use OAEP (Optimal Asymmetric Encryption Padding) or PSS (Probabilistic Signature Scheme) methods to add padding which can be removed later.

Optimal Asymmetric Encryption Padding (OAEP)

So, the solution to PKCS#1,5 is to use a padding masking method such as Optimal Asymmetric Encryption Padding (OAEP). The method was first published by Bellare and Rogaway in 1994 as [here][1]:

Overall, we operate on n bits at a time, and where n is the number of bits in the modulus (Figure 1). This is based on a Feistel network, and where if we EX-OR sometime with the same value twice, we end up with the original value.

With this — as illustrated in Figure 1 — we have two fixed values of k_0 and k_1. k_1 defines the number of zeros to pad onto the message, and k_0 defines the number of bits in a random number (r). The number of bits we are processing in the message is thus n−k_0−k_1 bits. We then have two hashing functions of G and H. The G function expands the k_0 bits of r into n−k_0 bits, and which is EX-OR with the padded message. This produces X. Next, we take the value and feed it into H, and which hashes the bits to produce k_0 bits. This is then EX-OR (⊕) with r to produce Y (and which has k_0 bits).

Figure 1: Padding and unpadding for RSA OAEP

We now have X and Y for our padding (Mp=X||Y), and where the total number of bits will be n. This can then be operated on with a (mod N) operation. The values of X and Y can now go into our cipher for:

and then decrypted with:

We can now strip off the padding. To recover the message we first recover the random value (r) from:

and then with r we recover the padded message:

We then strip off k1 zeros from the end of this message and recover M. An implementation of OEAP is here:

https://asecuritysite.com/rsa/node_rsa

PSS (Probabilistic Signature Scheme)

Four years after the OEAP paper, Bellare and Rogaway produced their PSS paper [3]:

As we have seen PKCS#v1.5 is weak for its padding, and suffers from many weaknesses:

It is deterministic. With this, we do not have a random element which changes the signature when we sign for the same data.
The hashed value can be extracted from the signature. An intruder can extract the hash from the signature and reveal the hashed value. While this does not reveal the original message, an intruder could eventually match it to a given message.
It has no formal security proof.

RSA-PSS overcomes these weaknesses. It uses randomized signatures for the same message — and is thus probabilistic rather than deterministic. For this we have a random salt value which is added to the signature process. It also stops the message hash from being extracted from the signature. Along with this is has a formal security proof of its security.

As with OAEP, it uses a mask generation function (MGF) and which is pseudorandom. This produces a non-deterministic output signature. With this, we use a salt value to produce the random signature, and where this salt value can be extracted from the signature (or contained in the signature).

The padding method is fully defined in RFC 2447 [here]:

Notice that the end part of the encoding is “0xbc”. This hex value defines the trailer to the encoded data.

The following gives an implementation of PSS mode being used to sign JSON Web Tokens:

https://asecuritysite.com/javascript/jwt2

Conclusions

I repeat … do not use PKCS#1.5. Please use OAEP or PSS in your RSA implementation. If your company uses RSA, please check. If you can, PSS is preferred, as it does not need additional checks for too many preceding zero values in the padding.

References

[1] Bellare, M., & Rogaway, P. (1994, May). Optimal asymmetric encryption. In Workshop on the Theory and Application of Cryptographic Techniques (pp. 92–111). Springer, Berlin, Heidelberg.

[2] Bleichenbacher, D. (1998, August). Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS# 1. In Annual International Cryptology Conference (pp. 1–12). Springer, Berlin, Heidelberg.

[3] Bellare, M., & Rogaway, P. (1998). PSS: Provably secure encoding method for digital signatures. IEEE P1363a: Provably secure signatures.