Forging RSA-PSS signatures with mbedTLS

This posts describes how to forge public-key signatures computed using mbedTLS’s implementation of RSA-PSS (the RSA-based standard signature scheme). Forging a signature means determining a valid signature of some message without knowing the secret key, but possibly know valid signatures of other messages. A signature scheme—or implementation thereof—is considered insecure if such forgeries are practical.

I reported the alleged bug to ARM more than three months ago. ARM did acknowledge receiving the report but did not follow up, and thus neither confirmed nor denied the vulnerability.

Here’s the thing:

mbedTLS offers the mbedtls_pk_sign() function, which takes arguments including:

• const unsigned char *hash, the message to be signed, which can be a hash of a message or a message of arbitrary size. The data in hash is actually hashed in mbedtls_rsa_rsassa_pss_sign(), the function internally called by mbedtls_pk_sign() to compute an RSA-PSS signature.
• size_t hash_len, the byte length of *hash.
• mbedtls_md_type_t md_alg, the type of hash that was used to create the hash value hash, set to MBEDTLS_MD_NONE if the data isn’t a hash but an arbitrary message.

Note here the confusing naming of variables, where *hash can either be a message or an arbitrary size, not only a hash (said message being hashed prior to computing the actual signature when mbedtls_pk_sign() is called).

Now observe that the function computing an RSA-PSS signature within mbedtls_pk_sign() is mbedtls_rsa_rsassa_pss_sign(), which receives mbedtls_pk_sign()’s hash_len 64-bit length argument as… an unsigned int, long of 32 bits. An integer overflow thus occurs when the message is larger than 4GB.

A forgery attack is thus trivial, if you have access to a system computing PSS signatures using mbedTLS:

1. Request the signature of some message M₁ long of L > 0xffffffff bytes
2. Receive a signature that is a valid signature of the message M₂ of length L mod 2³² consisting of the first L mod 2³² bytes of the long message signed at the first step.

Thus you know a valid signature of M₂, even though what you received is an (alleged) signature of M₁, a different message. mbedTLS’s signature verification will accept the forged signature as a valid signature of M₂.

Conversely, a valid signature of a message of length L < 4GB will get you a signature that mbedTLS will consider as valid for the message of length L + 4GB sharing the same L-byte prefix as the original message.

The fix is easy: use size_t -typed lengths everywhere.

NOTE: This support of arbitrary length input through the MBEDTLS_MD_NONE option is not compliant with the PKCS standard (see RFC 3447), and will likely not be interoperable with other implementations of PSS signatures. Thanks to Jethro Beekman for pointing out this non-standard behavior of mbedTLS.