is RSA KTS-OAEP necessary? [duplicate]

Question

Often data is encrypted using Symmetric Ciphers and Symmetric key is shared with recipient by encrypting it with recipient's Asymmetric Public Key. NIST Special Publication 800-56B, Revision 2 section 9 defines RSA KTS-OAEP to establish keying material between sender and receiver. Is it really necessary to use RSA OAEP or RSA KTS-OAEP to establish keying material between sender and receiver?

Since most of the time, symmetric key length is much smaller than asymmetric key length e.g 256 vs 2048. Is it safe to use the textbook RSA to encrypt the symmetric key in a scenario where new symmetric key is randomly generated by the sender for each message?

Since randomly generated symmetric key is not likely to repeat, there is no need to use RSA OAEP and RSA KTS-OAEP?

Answer 1

No, it is not necessary, but:

• you will get (about) the same RSA ciphertext size with any secure scheme;
• the computational overhead of OAEP is minimal anyway;
• using textbook RSA is insecure (see the other answers for that);
• other padding modes may not be as secure (PKCS#1 v1.5 padding is more vulnerable to padding oracle attacks).

But there are other possibilities:

• you can use RSA-KEM - this is basically textbook RSA of a fully random number the size of the modulus, followed by a key derivation;
• it is possible to use an IES scheme such as ECIES - you could include NaCL in this - such schemes can drastically reduce computing resources and data overhead (of the asymmetric crypto).

Especially RSA-KEM could be useful as you only need a random number generator and textbook RSA + some way to derive a key (which could be something as simple as a cryptographic hash).

Answer 2

Since randomly generated symmetric key is not likely to repeat, there is no need to use RSA OAEP and RSA KTS-OAEP?

Adding nondetermanism isn't the only reason we need padding for RSA; we also have to worry about homomorphic attacks - that is, attacks based on the homomorphic property, namely $x^e \cdot y^e = (x \cdot y)^e$.

Here is one way an attacker might try to use it to recover $m$ from $c = m^e$ (given that $m$ is relatively small):

• Compile a list of small integers and raise them all to the public exponent $a_0^e, a_1^e, a_2^e, ... a_k^e$

• Compile a second list of small integers and raise them to the inverse of the public exponent, and multiply them by the ciphertext $c \cdot b_0^{-e}, c \cdot b_1^{-e}, ..., c \cdot b_k^{-e}$

• Scan the two lists; if they have a value in common, say, $a_i^e = c \cdot b_j^{-e}$, then we have $m = a_i \cdot b_j$, we win.

This attack allows us to scan through $k^2$ possible values of the message with $O(k)$ work; even though this attack is not guaranteed to succeed ($m$ might not be a factor of the two entries in the lists), this still does decrease the security we obtain, compared to a good padding method (which voids this style of attack)

Answer 3

Using small public exponents would be off the table for one. Assume a $256$-bit symmetrical key $k$ with $e = 3$ as public exponent. If we naively convert $k$ to an integer, then $k^3$ would be an $\approx 768$-bit number, thus $k^3 \bmod N = k^3$. Then encryption could be trivially undone by anyone able to get their hands on the ciphertext.

Similarly small public exponents would make you vulnerable to Hastad's broadcast attack, if you had sent the same key to too many different recipients - as might happen if you had e.g. used those keys to seed a cluster of workers.

Further, ciphertexts would be malleable, leading to some issues as mentioned above by poncho.

As such this seems ill-advised. All these issues could be worked around - or might not be applicable to a specific system - but I'd much prefer an encryption system with fewer opportunities to shoot myself in the foot.