So my question is do padding schemes used in RSA protect it against Least Significant Bit Oracle attack?

The attack I am talking about is described here: RSA least significant bit oracle attack

As far as I know the padding schemes add some random bytes to the end of the block so that it always gives a different value when encrypted. But if it is done this way we can continue doing the LSB oracle attack and get the deciphered block, then easily discard the random bytes. Am i missing something about how padding schemes work?


1 Answer 1


Actually, the "Least Significant Bit Oracle attack" isn't actually an attack.

Instead, it is the observation that, if you were given a magical black box (an Oracle) that is able to take an RSA encrypted ciphertext, and give you the lsbit of the plaintext, you could use that Oracle to decrypt the entire ciphertext.

What we can conclude from that observation is that determining the lsbit of the plaintext is as difficult as doing a full decryption. We use the phrase "hard bit" when discussing this (and similar) situations.

Since we don't actually have such a magical Oracle, we can't actually perform this in practice.

Since this is not specifically an attack (and in fact, is proof that the lsbit is not specifically weak), padding methods don't need to defend against it.

  • $\begingroup$ I know that such oracle does not exist. I was asking if such oracle really existed if we could break RSA even with the Padding schemes. Which I assume we could by your answer, but since it is a hypothetical situation Padding schemes don't need to defend against $\endgroup$
    – Hesher
    Commented Jun 20, 2018 at 17:20
  • $\begingroup$ @Hesher: yes, with such an oracle, we could effectively decrypt the RSA ciphertext, and then remove the padding (using the same procedure that the valid decryptor uses) $\endgroup$
    – poncho
    Commented Jun 20, 2018 at 20:27
  • $\begingroup$ @poncho does a similar attack exists on signatures? $\endgroup$ Commented Mar 31 at 8:38
  • $\begingroup$ @user2284570: if the attacker could ask arbitrary post-padded values to be raw-RSA signed, yes, it would. However, if the attacker is limited to asked specific messages (or specific hash values) to be padded and signed, no it wouldn't - the attacker would not have sufficient flexibility to use this attack. $\endgroup$
    – poncho
    Commented Mar 31 at 11:36
  • $\begingroup$ @poncho so can you give an example for my case crypto.stackexchange.com/q/111270 please? $\endgroup$ Commented Mar 31 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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