What is RSA OAEP & RSA PSS in simple terms

Question

After googling or youtubing, i still cant find any information on RSA OAEP & RSA PSS. Can someone explain it in simple terms to me? I understand RSA is public key and private key. Why is there so many variant like OAEP and PSS?

Answer 1

"Textbook"/"raw"/"unpadded" RSA has an "oops, the real world happened" problem.

Consider any RSA key whose modulus is 4096-bit. It should be nearly impossible for someone to recover a message encrypted under that key, right? Let's assume that this key has a public exponent value (e) of 3.

If Alice uses this public key to encrypt the message "No" to Bob she would do something like

• "No" => ASCII("No") => 0x4E 0x6F => m=0x4E6F.
• c = POW(0x4E6F, 3) MOD n => c = 0x75CCE07084F MOD n.
  • We know that n is a 4096-bit number (given) therefore it's larger than 0x75CCE07084F, so c=75CCE07084F.

Mallory now sees a transmission of [506 0x00s] 07 5C CE 07 08 4F. "Hmm," she thinks, "that was a suspicious amount of zeros". She fires up calc.exe in programmer mode (hex) to input 75CCE07084F, and switches it to decimal (8095174953039). She copy/pastes that to Scientific mode and hits the cube root button (20079). She cackles at the integer solution and does the copy/paste modeswitch dance to get back to hex (0x4E6F). She further checks an ASCII chart and reconstructs that the message was likely the English word "No". Mallory has now recovered this message without the use of the private key.

What went wrong?

The combination of the message and the exponent resulted in the modulus operation not being required. Computing n-th roots isn't pleasant, but it's not an intractable problem.

For e=3 the modulus operation won't be involved for any m whose length is less than one-third the size of the key. For a 4096-bit key this means all m <= 170 bytes are immediately recoverable because the key wasn't relevant.

How to fix it?

One way would be to increase the minimum size of the public exponent. That doesn't solve a secondary problem that textbook RSA has, though: sending the same message encrypted against the same key is the same every time.

Another way is to make it so that m is always "nearly n". One could seemingly accomplish this by taking the normal message and reversing it, but that a) could exceed n, and b) fails when m ends in a lot of 0x00s. (And that still wouldn't solve the determinism problem).

So the solution that was come up with was to always "pad" a message to ensure some high bits are set and that any exponentiation uses the modulus value.

Enter PKCS1 padding

PKCS#1 (encryption) padding looks like

00 02 [a bunch of non-zero random bytes] 00 [the message]

The number of non-zero random bytes is as many as required to make everything perfectly fit in a buffer whose size is (keysize + 7) / 8 bytes (that's divide by 8, round up). The spec says that there's a minimum of 8. This means that the chance of producing the same encrypted value of any message is one in 2^64, which is pretty good odds of uniqueness. And the shorter the message is the less likely a duplicate is.

This message has a "size" of 4096-6=4090 bits. Taking it to the third produces an answer in the realm of 4090*3 = 12270 bits. That will definitely exceed our 4096-bit modulus, so the mod is guaranteed to be involved. We've also solved our original goal of making it so that you can't trivially decrypt the message.

What went wrong this time?

It turns out that wrong answers can "decrypt successfully". Any message C is valid against any 4096-bit key k with odds

1/256 * 1/256 * (255/256)^8 * (1 - (255/256)^502)

("first byte is a zero", "second byte is a 2", "no zeros appear within 8 bytes", "a zero appears eventually")

0.004 * 0.004 * 0.996^8 * (1 - 0.996^502)
0.004 * 0.004 * 0.969 * (1 - 0.140)
0.004 * 0.004 * 0.969 * 0.860
1.27e-5

So approximately 1 in every 78 thousand messages is "valid", but wrong. This can confuse Bob and make him say silly things in response. If Eve (who has more free time than Mallory) wants to she can now start sending Bob clever gibberish and observe when he says he's confused, eventually Eve can figure out what the original message was. (Bleichenbacher attack (Crypto.SE))

Enter OAEP padding

OAEP padding is a lot more complicated (https://www.rfc-editor.org/rfc/rfc3447#section-7.1). It is constructed in such a way that

• A really high bit is still always set
• Randomness is still injected, so the non-determinism is preserved
• The decryption operation can determine if it got the right answer (vs "a maybe right enough" answer)

OAEP depends on a hash algorithm for the "correctness" property, and so as long as a good hash algorithm is used it means that there's no tricky secondary answers.

Okay, so what about signatures?

Similar (but different) arguments get us from textbook RSA to PKCS#1 signature padding.

The PKCS#1 to PSS transition is a bit harder to explain. To quote from RFC 3447:

Two signature schemes with appendix are specified in this document: RSASSA-PSS and RSASSA-PKCS1-v1_5. Although no attacks are known against RSASSA-PKCS1-v1_5, in the interest of increased robustness, RSASSA-PSS is recommended for eventual adoption in new applications. RSASSA-PKCS1-v1_5 is included for compatibility with existing applications, and while still appropriate for new applications, a gradual transition to RSASSA-PSS is encouraged.

PSS adds randomness to the signature generation process, and a methodology for removing/verifying the randomness during verification.

Conclusion

The primitive RSA operations do what they need to do, turn a number into another number which can be turned back into the first one. The important suffix "securely" requires a bit of constraint placed on the inputs to the functions. The padding algorithms provide those constraints (and when new constraints are learned, new padding algorithms get invented).