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?
-
2So called "textbook RSA", which is the one you know about, is insecure in many ways. OAEP and PSS are technical improvements of RSA. That said, I think this question is more appropriate in Crypto.SE– A. DarwinApr 7, 2018 at 19:58
-
I think you just have to google better. en.wikipedia.org/wiki/Probabilistic_signature_scheme– Tom K.Apr 9, 2018 at 10:22
1 Answer
"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 than0x75CCE07084F
, soc=75CCE07084F
.
- We know that
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).
-
Great answer! Just a quick question, can you point to some applications that use RSA signatures in both padding variants? Thanks!– DanielSep 24, 2018 at 22:41
-
This is a good answer, but it's worth adding that PKCS#1 v1.5 padding includes a block of random bytes only when you encrypt with the public key. For encryption with the private key, a sequence of 00 or FF bytes is added, so the ciphertext is the same every time (not good for security). See RFC2313 for details. May 26, 2020 at 14:58
-
@TomaszP.Szynalski “encrypt” means “with the public key”. Signatures (which are different from “encrypt with the private key semantically, but not necessarily mathematically) are covered with the reference to RFC 3447.– bartonjsMay 26, 2020 at 23:39
-
1@bartonjs I was just trying to suggest a small improvement to your answer, because the current phrasing confused me when I was debugging a PKCS#1 v1.5 padding issue. "Encrypt" doesn't always imply "with the public key". You can encrypt a hash with a private key to create a signature. RFC2313 says: "This section describes the RSA encryption process. (...) For a public-key operation, the integer c shall be an entity's public exponent e; for a private-key operation, it shall be an entity's private exponent d.". Clearly, the authors don't see a contradiction between "private key" and "encryption". May 28, 2020 at 17:18
-
1@TemporaryFix They’re both “the newer RSA padding mode”, one for encryption and one for signing. They have similar structure, but different purpose (and OAEP has a real purpose of use… PSS feels like “let’s take OAEP logic and use it on signatures”)– bartonjsOct 14, 2021 at 0:14