rsa padding semantic-security
Updated Wed, 22 Jun 2022 21:03:06 GMT

Is semantic security important in a hybrid cryptosystem?

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.


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.