Is PKCS #1 v1.5 RSA encryption padding secure under these conditions?

Question

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.

Answer 1

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.