What's the point of OAEP?

Do we consider RSA+OAEP secure because the number of possible padded representations of a message is some insanely large number, and thus not feasible to bruteforce with current hardware?

No. But a related proposition holds: we would consider RSA+OAEP insecure if the number of possible padded representations of a message was less than some large number, like $2^{80}$ at the very least (which is not "insanely large" by today's measure).

In many practical cases, textbook RSA encryption per $C=M^e\bmod N$ would be insecure if $M$ was directly the plaintext, without some random added in the padding process transforming plaintext to $M$. This is because the adversary is assumed to hold the public key $(N,e)$ and could trivially use it to verify a guess of the plaintext, which matters (e.g. when the goal is to mask from adversaries the result of a coin toss, the name of someone on the class roll, a PIN number..). To resist that, the randomness added by the encryption padding process needs to be kept secret from attackers, and have at least $b$-bit entropy for $b$-bit security. RSAES-OAEP does that (it injects $2b$-bit, typically 256 bits nowadays), as well as other RSA encryption padding schemes like RSAES-PKCS1-v1_5.

But there are other objectives met by OAEP:

• Allowing a security reduction to the RSA problem (which is of finding $M$ from $M^e\bmod N$ for random $M$ with $0\le M<N$). In a nutshell, OAEP padding transforms the plaintext into an $M$ that covers a large fraction of the $[0,N)$ in a random-like way, and allows a strong argument that if we could break RSA+OAEP under CPA or CCA (by this account: CCA1, or CCA2 under the Random Oracle model), we could break RSA or the pseudo-random functions (hash or Mask Generation Function) used in OAEP.
• Mitigating the risk of attacks using side channels in the decryption operation when fed malformed ciphertext (information leak by timing to get an error code, or value thereof). These have the potential to transform something performing the decryption into a decryption engine (see Bleichenbacher's attack on PKCS#1 v1.5 encryption). In a nutshell, OAEP is better protected because the comparison done to decide if a padded plaintext $M$ is valid involves comparing hashes (it also helps that it is CCA-secure).

Conclusion: we consider RSA+OAEP secure because OAEP provides a security reduction to the RSA problem under CPA and CCA, and it helps mitigate implementation attacks.

Solved by user555 (122,419 )
May 07, 2018 at 11:32