Is semantic security important in a hybrid cryptosystem?

Question

RSA doesn't provide semantic security when used unmodified, and neither does the commonly used PKCS#1 v.1.5 padding scheme for encryption.

Is this a problem for hybrid cryptosystems at all?

My suspicion is that it isn't, since the plaintext message of the RSA encryption should be a random string used as an encryption key for the symmetric cipher used to encrypt the actual message, which would make the advantage an attacker could gain by the lack of semantic security pretty neglegible.

I guess that it's still a bad idea to rely on the randomness of the ciphertext in that way, but then again, as far as I understand, more secure padding schemes like OAEP also need a random input to guarantee semantic security, so by encrypting messages without a good entropy source seems to be equally bad in both cases.

To sum up my question:

• Is semantic security necessary if the plaintext is guaranteed to be random for all messages encrypted by an asymmetric encryption scheme?
• When the plaintext turn out to be not as random as expected (e.g. due to a broken RNG), is that worse than the RNG input for a semantically secure padding scheme being predictable?

Additionally, if it is, can anybody explain why PKCS#1 v.1.5 is still commonly used? As far as I know, GnuPG uses it exclusively for RSA encryption, and TLS does so as well for its RSA key exchange in many of its cipher suites.

Answer 1

Yes, semantic security (IND-CPA) is important, even for public-key cryptosystems and for hybrid cryptosystems.

Let's focus on hybrid cryptosystems, where a message $m$ is encrypted by picking a random symmetric key $k$, encrypting $m$ under $k$ with a symmetric-key algorithm, and also encrypting $k$ using a public-key algorithm. In this case, it's important that the symmetric-key algorithm provide semantic security (IND-CPA). It's generally speaking also a good idea to pick a public-key encryption algorithm that provides semantic security (IND-CPA), because then it follows that the hybrid cryptosystem will provide semantic security as well -- which is what actually matters. (Technical nitpick: in some cases I suppose it's possible you might have a proof that the hybrid cryptosystem provides semantic security even if the public-key encryption algorithm is not known to provide semantic security. That would be sufficient, too. The important thing is that the hybrid cryptosystem, taken as a unit, provides semantic security.)

In most applications, you also need/want security against chosen-ciphertext attacks (IND-CCA) too.

Why is PKCS #1 v1.5 still used? As far as I know, it's a combination of (a) inertia, and (b) the attacks aren't serious enough to get people to switch away from it urgently. I wouldn't recommend it for new systems; I would recommend OAEP or some other scheme with a strong proof of security.

Answer 2

Not a complete answer, but since you mentioned "unmodified RSA" I feel it's relevant.

Something stronger than vanilla RSA is necessary, even if it isn't semantic security.

Example: What if you have a public key exponent of 3 and the symmetric key being encrypted is 16 bytes long? Using raw RSA, $m^e$ would be about $128 \times 3 = 384$ bits long and thus smaller than any modern public key modulus would be. Being smaller than the modulus would prevent the calculation from taking advantage of the RSA Assumption, which is the premise of RSA's security. Since $m^e$ is easy to factor simply over the integers all security would be lost. (And this mistake would be somewhat obvious to the attacker because the vast majority of the high bits would all be 0.)