Is OAEP needed when encrypting a session (random) key using RSA?

Question

My question is two parts:

1. when encrypting a session key which is used to encrypt bulk data using a block cipher for example, is padding with OAEP really needed [i'm assuming the key is generated using secure random generator.

2. What benefits does OAEP provide compared to simple padding with random bits up to size $n-1$ where $n$ is the size of RSA.

The answers in How does OAEP improve the security of RSA? are very useful but I'm still wondering about the above questions.

Answer 1

when encrypting a session key which is used to encrypt bulk data using a block cipher for example, is padding with OAEP really needed ?

No if the session key is nearly as wide as the RSA modulus, or is padded with random bits up to that size (save for one bit or few high order bits). Absent other issues, we are safe if the actual session key keeps bits from the result of RSA decryption among those that have been chosen randomly, or is obtained by another key derivation step. That's the principle in RSA-KEM.

But yes, RSAES-OAEP is useful if the session key is directly the payload, and is much smaller than the RSA modulus (which is typical for a session key). OAEP gives a security reduction to the RSA problem under the random oracle model, when direct encryption of a short key with textbook RSA (as $C=K^e\bmod N$ ) is known to be insecure in at least the following two cases.

• If the public exponent $e$ is small (less than about $\displaystyle\frac{\log N}{\log K}$ bits), then decryption reduces to computing the non-modular $e^\text{th}$ root of $C$, yielding $K$. This question asks for a bound for $\log K$ allowing attack, which it is slightly larger than $\displaystyle\frac{\log N}e$.
• If the key $K$ is significantly less that twice as wide as the desired security level, then there's a meet-in-the-middle attack working for the sizable fraction of $K$ that (partially) factor as $K=K_1\cdot K_2$ with $K_1<K_2$ and $K_2$ small enough to be enumerated, requiring $O(K_2)$ time and $O(K_1)$ memory.
  That would be a plausible attack for 128-bit $K$ and 4096-bit RSA with $e=2^{16}+1$.

---

What benefits does OAEP provide compared to simple padding with random bits up to size $n-1$ where $n$ is the size of (the) RSA (public modulus) ?

None that I see beyond

• availability of some secure implementations,
• recognition (including explicit by some security recommendation),
• detection of accidental cryptogram corruption or using unmatched public/private keys.

Beware that implementation of decryption using "simple padding with random bits" is far from foolproof; nothing manipulating secret or private key is. In particular, testing the high-order constant bit(s) leads to disaster by padding oracle attack. Fault attacks may apply (e.g. forcing the session key to be zero with targeted and timed laser pulses). Side channels may be problematic.