So How Does Padding Work in RSA?

So How Does Padding Work in RSA?

Basically, PKCS#v1.5 is bad, OAEP is good

While the RSA algorithm has required an increasing size of modulus in order to keep up with the advancement of computing hardware, it has continually been affected by the usage of its padding. So, let’s dive in, and see if we can understand why this is the case.

If you’re into cybersecurity, you should hopefully know that symmetric key ciphers often use blocks. With AES, for example, we have a block size of 128 bits (16 bytes), and where we process these blocks to cipher and decipher. But the last block is unlikely to fill all the bytes in this block, and so we add in padding. This padding is typically derived from the number of empty spaces and repeated for the number of spaces left. And so, “hello” is padded with 11 padding values (0b):

h e l l o 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b 0b

This padded version of the block is then ciphered, and deciphered at the other end. Finally the padding is removed to reveal the plaintext message.

But what about RSA? It uses integers and a mathematical ciphering operation of:

C=M^e (mod N)

and where M is an integer value of the message, e is the exponent, and N is the modulus. This modulus is created by multiplying two random prime numbers (p and q). Our modulus will thus limit the size of M that we can have, as we cannot have a value of M greater than N (as it would wrap around — and where two or more inputs will give the same cipher value).

PKCS#v1.5 — Simple padding

The simplest way to pad 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 that showed how the PCKS#v1.5 padding method could be cracked with a chosen cipher attack [here]:

Here is a recent attack:

In fact, Matthew Green puts it best when we said:

“PKCS#1v1.5 is awesome — if you’re teaching a class on how to attack cryptographic protocols. In all other circumstances, it sucks.”

The Bleichenbacker’s attack has been continually compromising some systems for decades, but TLS 1.3 now overcomes it by dropping support for PCKS#v1.5.

Optimal Asymmetric Encryption Padding (OAEP)

The solution to the problems of PKCS#v1.5 is to use Optimal Asymmetric Encryption Padding (OAEP), and was first published by Bellare and Rogaway as [here]:

It has since been standardized in PKCS#1 v2 and RFC 2437 [here]:

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).

We now have X and Y for our padding (M_p). These values can now go into our cipher for:

C=M_p^e (mod N)

and then decrypted with:

P = C^d (mod N)

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

r= Y ⊕ H(X)

and then with r we recover the padded message:

m00…0 = X ⊕ G(r)

We then strip off k_1 zeros from the end of this message and recover m.

Coding

So now let’s implement RSA padding using the crypto Node.js library [here]:

A sample run for a 728-bit modulus is:

Message:  Test
Private key:
 -----BEGIN PRIVATE KEY-----
MIIBzQIBADANBgkqhkiG9w0BAQEFAASCAbcwggGzAgEAAlwAr80iRwDJ/WZpUBw2
XTivRQTlxQ7bGztV5nBZ7IErnosnuYiaqCGLetq7JVcHi56KDm+yfldtVp8kjWzs
KIOTMFYcM6J/14OjHRosUddmnd/YrcRi+ilBCZ8YIwIDAQABAlsZvFP6RPlM6UMd
gSPMPdIarn7cfDJDKEqI84WWg8pY6VIlbQQG/PIoSAEBlF34hkj6hF/mvjaD62CH
nn2t8DRxmUYZPDgBuDvPB6H8yUg8xa7nSMkLKKK4JYUhAi4NouRzlm6DbuCiWFg8
24wFhlXBENXLLc+TAy6n4iRpsrymAQFK4ubuYYPpnkXJAi4M5GRsOTUq73Qm6Tv8
D6jq2b2uFzpHu8sPLppeLerdOPgmJDoJEq4NVh/VH5SLAi4DhwSjpeFWnIL9W+8P
ZxeUgkiCldFIKsSMWgFiqkwTD4pfQtlLvuBP/+e4shmJAi4DYq6kZNl7buo3laP0
6z/WfFt9LghV8hC+6eQLu08jzOQNUBIVc9xVEDrHwsVFAi4C3J5prWD81k0JjYw3
XLl2T35+P0mCM/O0jboMwcdBPB0P2Nxeg84HECBoUb49
-----END PRIVATE KEY-----

Public key:
 -----BEGIN PUBLIC KEY-----
MHcwDQYJKoZIhvcNAQEBBQADZgAwYwJcAK/NIkcAyf1maVAcNl04r0UE5cUO2xs7
VeZwWeyBK56LJ7mImqghi3rauyVXB4ueig5vsn5XbVafJI1s7CiDkzBWHDOif9eD
ox0aLFHXZp3f2K3EYvopQQmfGCMCAwEAAQ==
-----END PUBLIC KEY-----

Encrypted:  ab7351b332e47882ac0cbcb425c5fd5d92d7750ced2d504c452638e88df1daed6aad4fd82d59579688a48dd9d528181bfc13b3081b6d709abf4b945e3aa8ea44c2695b0c6c89c30ebd551dcce928e34dedc74f14717caaaacc0e17
Encrypted:  q3NRszLkeIKsDLy0JcX9XZLXdQztLVBMRSY46I3x2u1qrU/YLVlXloikjdnVKBgb/BOzCBttcJq/S5ReOqjqRMJpWwxsicMOvVUdzOko403tx08UcXyqqswOFw==

Decrypted:  Test

We can see that the encrypted cipher is much larger than the plaintext message. This is due to the padding involved. A sample run for a 1,024-bit modulus is:

Message:  Test
Private key:
 -----BEGIN PRIVATE KEY-----
MIICeAIBADANBgkqhkiG9w0BAQEFAASCAmIwggJeAgEAAoGBAJ/6CNiZirCuNS0b
6JI/DwZeLzQB5Uk1rX9H37LjMI8WUwlXI5Miwh6pWJQy1snVQrqGWhZ/otkEO9XS
PkFMxM7caZegWC7ljS+MVa+Qdv7SXl53P5SOsXlojyucJtkxMTgMX5/6c6RwFt6z
ylVjnE3Wk4P1IksosHRvngU5CyK1AgMBAAECgYEAk2uNRVTQupn+xM/oFQTpKpwW
cZ2hlkJR3G32VdoIgIM5B+12CfvI2QqDZyYmSp4svMhcMklyXvwIy7TPy8sbvHPL
Bv4p26EFW8hNU0GycYwTb1COrs3qB9gziHbKWTBV7X8Jf7WLQBn1ok3tcv+PB0xB
8fCCa+gz2BMKjaziKyECQQDPFVY47/qL1mF5Tjq9Rc7JsvZOSWW2qoZghylPA1if
crQv7WdgVxaQ0bZptXpuXMS5IBX1+sBFjK0MmvjIViXdAkEAxcQVNmsvcTtHrEPV
OMQXCOyJM8iYpx166aHsyIVs2NfCKiZGFfSZjKeysP6cH+34pMFv9izIxt4KDW4Y
Q9N+uQJBAKwLXgcP2Wg0Q+c0RzjYtmR8eoWwFQEdy2aG5JrwfMB725e19RzlPaoz
kQlh7MWj7Qygy54BJZyis2K1ndtTN0ECQQCdZ74CfDlchHQ9dhgFgH1dCvcBEk39
5QbpYYoW56uEw+W0qpXp768vNmKRYXVeLIhUienVJDwBnMSff9ssUO9xAkAF1NKb
iySvlCtInTH0fQqv9zyibSD5Oe3DlUsY7hK9ivOxfydeXcODUn3rEr6CQka3Ygwt
Tt2qzFJR0Dd86pgX
-----END PRIVATE KEY-----

Public key:
 -----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCf+gjYmYqwrjUtG+iSPw8GXi80
AeVJNa1/R9+y4zCPFlMJVyOTIsIeqViUMtbJ1UK6hloWf6LZBDvV0j5BTMTO3GmX
oFgu5Y0vjFWvkHb+0l5edz+UjrF5aI8rnCbZMTE4DF+f+nOkcBbes8pVY5xN1pOD
9SJLKLB0b54FOQsitQIDAQAB
-----END PUBLIC KEY-----

Encrypted:  715ed78e372833557626358c76604a5a81709b07d260415632bf977aead32eafe0e75263eecb9380ef46297437e2dabb342ab079cafe369b3888542dfcd61f4541e172e4f6c7f726dad3c332f294d8d876dfa6b410a140679d759e6ee95976967993c5d933b40d619e421037f8fafe531938b294b38452d44ae5f2ead8ac1136
Encrypted:  cV7XjjcoM1V2JjWMdmBKWoFwmwfSYEFWMr+XeurTLq/g51Jj7suTgO9GKXQ34tq7NCqwecr+Nps4iFQt/NYfRUHhcuT2x/cm2tPDMvKU2Nh236a0EKFAZ511nm7pWXaWeZPF2TO0DWGeQhA3+Pr+Uxk4spSzhFLUSuXy6tisETY=

Decrypted:  Test

And there you go.

Here is the implementation:

https://asecuritysite.com/node/node_rsa

Conclusions

After over four decades, RSA is still alive and kicking. It is slower than ECC, but it does its encryption without needing to use symmetric key methods. With TLS 1.3 we should hopefully say goodbye to the Bleichenbacher attack, too. For me, I love Feistel networks. If you want to know more about them, try here: