The PKCS #1 v1.5 padding scheme for RSA has been proven to have some weakness when used with TLS for example.

My question is: is it still secure under the following conditions?

Alice sends a message to Bob encrypted with RSA using PKCS #1 v1.5 padding scheme. If Bob figures out that the message is correct, he will send an answering message back to Alice, otherwise, he will discard the message and won't send anything to Alice. Alice cannot know if Bob accepted the message nor how much it took to bob to decrypt it (and this makes timing attacks impossibile) because Bob may decrypt it after one day, one week or one year.

  • $\begingroup$ Your statement "Alice cannot know if Bob accepted the message" does not seem to be well-justified (at least, it does not follow from the rest of your conditions). $\endgroup$
    – D.W.
    Mar 22 '14 at 19:54

Though Bob may potentially delay his response by one year or more, the attacker may probably assume that, in practice, Bob will respond rather promptly. Thus, an active attacker can infer from Bob's response, or lack thereof, whether decryption occurred or not. This is a setup where Bleichenbacher's attack seems to apply.

However, one must take the fine print into account: Bleichenbacher's attack works by knowing whether, upon decryption, Bob found a seemingly correct padding, i.e. one that begins with the two bytes 0x00 0x02. When Bob finds that padding, he will then extract the "message" by removing the leading non-zero bytes (after the 0x02), which are supposed to be random padding bytes, as per PKCS#1 specification. In the case of Bleichenbacher's attack, the message will then be random junk.

If your setup is exactly the following:

  • Bob decrypts the incoming sequences of bytes with the RSA modular exponentiation;
  • if the exponentiation result does not begin with 0x00 0x02, Bob does not respond;
  • otherwise, Bob always respond, possibly with a "Alice, you sent me random junk";

Then Bleichenbacher's attack applies.

However, if Bob does the following:

  • Bob decrypts the incoming sequences of bytes with the RSA modular exponentiation;
  • if the exponentiation result does not begin with 0x00 0x02, Bob does not respond;
  • if the message, after padding removal, does not make any sense, then Bob does not respond;
  • otherwise, Bob always responds;

Then Bleichenbacher's attack may be thwarted, or not, depending on the exact notion of "make sense". For instance, if Bob expects each message to have the format m||SHA-1(m) (concatenation of the message itself and its hash with SHA-1), and won't respond if the hash does not match, then Bleichenbacher's attack won't be feasible.

Note that I do not claim that PKCS#1 v1.5 is secure. To my knowledge, we have no proof of security of PKCS#1 except the usual criterion: the scheme has been widely used from quite some time, and Bleichenbacher's attack is the best attack that has been found. So far.

  • $\begingroup$ Actually, if Bob doesn't manage to decrypt the message, he asks Alice to resend the message but he doesn't specify why he couldn't decrypt the message. So, Alice will never know whether Bob found 0x00 0x02 or not. I think that this makes Bleichenbacher's attack infeasible but I could be wrong. If I am, how OAEP solves this? $\endgroup$
    – Steve
    Mar 22 '14 at 18:18
  • $\begingroup$ @Steve The verification of OAEP includes checking for a hash value over the random padding which twarts Bleichenbachers attack, at least if OAEP is implemented well (i.e. the verification of the padding is an atomic operation). The likelyhood of the hash over the padding being correct by supplying a chosen ciphertext is of course very small indeed. PS ask separate questions instead of asking for more on a given answer. $\endgroup$
    – Maarten Bodewes
    Jun 2 '14 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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