RSA Signature Verification issue

[maireland]

We have an RSA signature verification implementation that will report a PASS when the ACVP (and CAVS tool too) is expecting a FAIL due to a mismatch in one of the padding bytes rather than any mismatch in the recovered hash. The signature generation appears to have intentionally changed on one of the message padding bytes from 0x00 to 0x44, then generated a valid signature.

The PKCS #1 v2.2 specification contains the following which makes this scenario ambiguous:

In step 4 above, EM and EM’ contain all the padding bytes along with the SHA-256 hash to be checked. Following step 4 as shown, any mismatch in the padding or hash values will result in “invalid signature” or FAIL.

Our implementation uses the alternate method as described in the Note above. This method compares the underlying hash value from EM with the newly computed hash value over the input message. This method will not detect any intentional errors inserted in the message padding by the signer (provided they still generate a valid signature after injecting the errors).

To quickly summarize, our firmware is currently unable to detect a signing issue like the following:

1. Signer hashes the message to be signed
2. Signer pads the 256-bit hash to form a 2048-bit message
3. Signer flips one or more bits in the message padding, leaving the 256-bit hash unchanged
4. Signer applies the RSASP1 (decryption) primitive to the improperly padded message, creating a valid signature

Is there any way for us to proceed in validating our verification implementation? Is an update to the ACVP possible or is there any exception that can be applied in this case?

[celic]

I'll take a look at this. You are right this is what the testing currently does.

[maireland]

Thank you. I realized that there is a cut/paste error in my original post. The excerpt showing step 4 in PKCS #1 v2.2 didn't paste correctly, but it looks like you get the gist anyway. Thanks for taking the time to look into it. Much appreciated.

[smuellerDD]

Can that issue be closed?

[maireland]

There has been no resolution to the issue yet as far as I know so I'd like to keep it open.

[celic]

FIPS 186-4 does state that both methods are valid for verifying a signature.

For RSASSA-PKCS-v1.5, when the hash value is recovered from the encoded message EM during the verification of the digital signature, the extraction of the hash value shall be accomplished by either:
• Selecting the rightmost (least significant) bits of EM, based on the size of the hash function used, regardless of the length of the padding, or
• If the hash value is selected by its location with respect to the last byte of padding, including a check that the hash value is located in the rightmost (least significant) bytes of EM (i.e., no other information follows the hash value in the encoded message).

I will try to address this within the week, but we are looking at the options. I do not like simply removing the test case as it provides helpful assurances. I.e. trying to test against https://nvd.nist.gov/vuln/detail/CVE-2018-15836. Though this case is more relevant to FIPS 186-2 RSA SigVer testing as such an attack relies on using small e values like 3, or 17.

[maireland]

Thank you for the update, Chris.

[celic]

How does the implementation determine the number of bits to grab from the EM? Does it use the algorithm identifier prepended to the digest? Or is it something that needs to be provided?

[maireland]

Our implementation only supports RSA-2048 using SHA-256 for message digest. So, the implementation retrieves the recovered 256-bit hash from a fixed location at the end of EM. We don’t use the algorithm identifier prepended to the digest.

[celic]

Thanks for the information. But as the verifier doesn't have control over which signatures come in, what would happen if someone provided a signature that was generated with SHA-512 for example? Only the last 256-bits of the hash would be taken?

These tests aren't new with ACVP, a form of them existed in CAVS. I am trying to get enough information for a complete picture.

[maireland]

That is correct, only the last 256-bits of the hash would be taken in that case.