Implementation of RSA PSS signing and verification not strictly compliant with RFC

[xinyufort]

Please note that this was previously discussed in an email thread with the Mbed TLS security team, and was deemed not security-sensitive. I am opening this GitHub issue for tracking purposes.

Summary

Mbed TLS has a non-compliant implementation of EMSA-PSS-ENCODE (encoding step used in PSS signing) and EMSA-PSS-VERIFY (analogous step during PSS signature verification). Fortunately, this only occurs in corner cases where users try to specify parameter combinations that are allowed, but not RECOMMENDED (RFC 2119 semantics) by RFC 8017 (PKCS #⁠1: RSA Cryptography Specifications Version 2.2). In those specific cases, this results in non-interoperability with OpenSSL.

Specifically, when signing and verifying signatures,

• Section 9.1.1 of RFC 8017 uses the same algorithm Hash for steps 2 and 6 of EMSA-PSS-ENCODE. However, Mbed TLS's implementation does not necessarily use the same algorithm for both steps 2 and 6.
• Likewise, section 9.1.2 dictates that the algorithm Hash be used in both steps 2 and 13 of EMSA-PSS-VERIFY; Mbed TLS does not guarantee that this is the case.

The Mbed TLS PSS signing implementation uses two hash algorithms: md_alg, which I presume is the algorithm used to hash the original message (step 2 in both EMSA-PSS-ENCODE and EMSA-PSS-VERIFY), and ctx->hash_id, which is used for everything else. (The latter is normally set via a call to mbedtls_rsa_set_padding.) The deviation from the RFC occurs when users configure these two algorithms to differ from one another, since Mbed TLS will, instead of using md_alg for step 6 of EMSA-PSS-ENCODE, use ctx->hash_id instead.

• In 3.6, this occurs in the rsa_rsassa_pss_sign_no_mode_check function in rsa.c, at lines 2150 and 2197.
• In 2.28.8, this occurs in rsa_rsassa_pss_sign, at lines 1653 and 1698 in rsa.c

(Aside note: ctx->hash_id is also used as part of the MGF1 hash function (step 9 of EMSA-PSS-ENCODE). While the RFC RECOMMENDS (RFC 2119 semantics) that all hash functions involved in the encoding process be the same (in steps 2, 6, and 9), the Mbed TLS implementation not only does not enforce this rule, but also allows the hash algorithms in steps 2 and 6 to differ (md_alg vs ctx->hash_id), which deviates from the algorithm as described in the RFC.)

Likewise, we see a similar issue with signature verification -- specifically, when doing EMSA-PSS-VERIFY. Here, the two hash algorithms in question are md_alg and mgf1_hash_id. Step 13 of EMSA-PSS-VERIFY is performed using mgf1_hash_id as opposed to md_alg.

• 3.6: see line 2631 in mbedtls_rsa_rsassa_pss_verify_ext in rsa.c
• 2.28: see lines 2111, 2140, 2141, and 2172 in mbedtls_rsa_rsassa_pss_verify_ext in rsa.c

System information

Mbed TLS version (number or commit id): 3.60 and 2.28.0 Operating system and version: Ubuntu 20.04 Configuration (if not default, please attach mbedtls_config.h): default configuration, unmodified from source Compiler and options (if you used a pre-built binary, please indicate how you obtained it):

• I downloaded the Mbed TLS source code and am compiling the code into my C program
• I am using gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0, and am compiling my program using the -g flag

Expected behavior

I would have expected one of the following:

• Mbed TLS should not use ctx->hash_id for step 6 in EMSA-PSS-ENCODE, or mgf1_hash_id for step 13 in EMSA-PSS-VERIFY
• Mbed TLS should check that ctx->hash_id (when signing) or mgf1_hash_id (when verifying) is the same as md_alg, in order to prevent situations that are not RFC compliant
• Mbed TLS should, in its documentation, inform users that it is their responsibility to ensure md_alg and ctx->hash_id/mgf1_hash_id are identical if they want to adhere to the RFC recommendation

Actual behavior

Mbed TLS allows the hash algorithm used to originally hash the data (passed in via the md_alg argument) to differ from the hash algorithm used to perform step 6 in EMSA-PSS-ENCODE or step 13 in EMSA-PSS-VERIFY, which is not allowed by the RFC spec. This leads to non-interoperability with OpenSSL (which also allows users to pass in two different hash algorithms when performing PSS signing or verification).

Steps to reproduce

For brevity, I am only describing the steps to generate a non-compliant signature on 3.6 code. But a similar process applies for 2.28 code, and also for signature verification.

• Download Mbed TLS source code
• Modify line 101 in the rsa_sign_pss.c sample program such that it passes in MBEDTLS_MD_SHA3_256 instead of MBEDTLS_MD_SHA256. This ensures that there is a discrepancy between md_alg and ctx->hash_id
• Compile the modified program. E.g., gcc -g -I mbedtls-3.6.0/include/ mbedtls-3.6.0/library/*.c rsa_sign_pss_modified.c -o rsa_sign_pss_modified
• Run the program -- e.g., ./rsa_sign_pss_modified mykey.pem original_msg -- this will produce original_msg.sig
• Verify the signature with OpenSSL:
  • First hash the input data and save it to a file: cat original_msg | openssl dgst -sha256 -binary -out "myhasheddata.bin"
  • Run `openssl pkeyutl -verify -sigfile "original_msg.sig" -inkey mykey.pem -pkeyopt rsa_padding_mode:pss -pkeyopt "rsa_mgf1_md:sha3-256" -pkeyopt digest:sha256 -in myhasheddata.bin
• Signature fails to validate

Note that if you modify line 2197 in rsa.c to use md_alg as the last argument to hash_prime (instead of hash_id), and re-run the above steps, OpenSSL will successfully validate the signature.

[gilles-peskine-arm]

As discussed in email:

• The library is compliant if you use it in the most natural way. It allows users to deviate from the standard, in a way that is fairly common in implementations but not often used in practice: a different hash algorithm for the message processing and for the sign-the-hash phase (which uses a hash algorithm for two unrelated purposes).
• rsa.h is a low-level interface, so we don't try to prevent misuse.
• In any case, the misuse is still considered secure in practice, even if there is no security proof. You just reduce the security to that of the weakest hash.
• rsa.h will no longer exist as a public interface in the next feature release (Mbed TLS 4.0 or more precisely TF-PSA-Crypto 1.0). The only public interface for RSA-PSS will be PSA_RSA_ALG_PSS which uses the same hash throughout.

As a consequence, we don't consider it a bug that Mbed TLS allows different hash algorithms for the message processing and the hash+salt hashing. At most, we might add a note to the documentation.

[gilles-peskine-arm]

As for the fact that you can't use a different hash for the hash+salt hashing step and for MGF1, this is a limitation, but we aren't going to lift it unless there is a concrete use case. If we do lift it, it would have to be through the PSA API, not through rsa.h, since this will no longer be a public API.

[gilles-peskine-arm]

I am marking this issue as completed because I don't think we need to take any action about it. But if you think it's important to add a warning to the documentation, please make a pull request.