Score:3

RSA signature verification: How is the "integer too large" error in RSASSA-PKCS1-V1_5-VERIFY possible?

sn flag

Step 2 of the PKCS #1 v1.5 signature verification operation as described in RFC 8017 section 8.2.2 reads:

2.  RSA verification:

          a.  Convert the signature S to an integer signature
              representative s (see Section 4.2):

                 s = OS2IP (S).

          b.  Apply the RSAVP1 verification primitive (Section 5.2.2) to
              the RSA public key (n, e) and the signature representative
              s to produce an integer message representative m:

                 m = RSAVP1 ((n, e), s).

              If RSAVP1 outputs "signature representative out of range",
              output "invalid signature" and stop.

          c.  Convert the message representative m to an encoded message
              EM of length k octets (see Section 4.1):

                 EM = I2OSP (m, k).

              If I2OSP outputs "integer too large", output "invalid
              signature" and stop.

The "integer too large" error mentioned in step 2c occurs if and only if $m \geq 256^k$ (see section 4.1), where $k$ is the octet length of the RSA modulus $n$.

But, by construction of the RSAVP1 primitive (see section 5.2.2), $0 \leq m \leq n - 1$, or, equivalently, $0 \leq m < n$.

Because $n < 256^k$, we therefore have $m < 256^k$.

It seems to me that I2OSP could not possibly output "integer too large". But why was this condition included in the specification, if so?

Score:3
ng flag

Indeed, if $k$ agrees with $n$ [that is, if $2^{8k-8}\le n<2^{8k}$ ], and RSAVP1 worked correctly and did not produce an error condition, then the condition I2OSP outputs "integer too large" can not occur, for the reasons in the question.

Why was this condition included in the specification?

I can think of:

  1. I2OSP is a general primitive suitable for various contexts. As such, it has an error condition "integer too large", that occurs in some contexts. This an incentive to include how to handle that condition. I have seen coding rules on the tune of "explicitly test for errors returned even if they can't occur", and many more rules that are harder to justify.
  2. If what to do in case of error was not specified, someone would have asked, not realizing the error shouldn't occur.
  3. The error can occur if $k$ or $m$ was not computed correctly due to some faulty software, or it's value (or the software, or other data) got altered by some hardware fault (cosmic ray, deliberate fault attack).
  4. In the context of signature verification, abundance of checks is unlikely to harm. The only reasons I can discern are a little code bloat, a tiny speed penalty, and possible side channel leakage when the signed message or the signature is secret (but PKCS#1 v2.2 does not address that later concern).
edsq avatar
sn flag
Thanks! I appreciate the sanity check. Would it be unsafe to simply raise the "integer too large" error in the cases you describe? As a user/developer I'd rather have the additional information to debug, but not at the cost of security.
fgrieu avatar
ng flag
@edsq: As long as you can guarantee that "integer error" will not cause the software using the signature verification code to act as if signature verification succeeded, you are fine. Things would be different for decryption, where it can matter that adversaries can't discern the various errors making decryption fail.
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.