Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
You have two questions here: (a) is semantic security important, and (b) should we use PKCS #1 1.5 encryption? I suggest you might want to split off (b) into a separate question. –  D.W. Feb 12 '13 at 7:12
    
Your're right, that was a typo - I meant random plaintext as input to the asymmetric cipher. I've changed the question accordingly. Thanks! –  lxgr Feb 12 '13 at 7:32

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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 * 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.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.