Score:1

What are the security implications of RSA decryption of ciphertext >= modulus?

vu flag

While reading through the sections about decryption in PKCS#1 v2.2, I noticed that the decryption algorithms are required to output the failure symbol: decryption error when the RSA maths subroutine reports ciphertext representative out of range.

While notes on security consideration says padding removal should be a "poker-face" process, it didn't say anything about ciphertext being out of the decipherable range of the modulus.

What are the actual security considerations on this? What pitfall are there when deciphering arbitrary ciphertext without checking its bounds?

Score:1
in flag

The reason why decryption needs to be poker face is because it is possible to distinguish parts about the key or plaintext after modular exponentiation, when performing the unpadding. The unpadding part is susceptible to padding oracle attacks after all.

Modular operations will map the integer to an arbitrary value within the range [0, N) by simply performing mod N on the input value. That usually the case as this would be the mathematical equivalent - beware that optimized libraries may perform different calculations.

An attacker that is able to change the input message is commonly capable of choosing the equivalent message in the range [0, N) by themselves. As such, the processing of larger or smaller integers shouldn't make any difference to the security of the RSA algorithm.

It would still be a bad idea to remove these checks though:

  • they could be used to try and find a buffer overruns or trigger some other kind of overflow;
  • the size may have been increased to shift other values of the message within the protocol;
  • they might be used to slow down the system as you'd still have the initial modular operation on a number of arbitrary size.

In general: the higher the confidence that the state of the system is within bounds, the higher the security. Pre-conditions and guard statements are relatively cheap ways of making sure that the input is valid and that calculations are not performed using out-of-range values.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.