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?


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 Jun 20 '18 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 Jun 20 '18 at 20:27

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.