Add support for non-standard RSA signature encodings

[misterzed88]

There are use cases when there is a need to encode and decode RSA signature data using odd formats inside the PKCS #1-padding, such as:

• Encoding the raw digest without a DigestInfo structure
• Using a proprietary or invalid AlgorithmIdentifier in the DigestInfo structure

One example is described in https://vcsjones.dev/2019/07/18/sometimes-valid-rsa-dotnet/

In order to support these cases, a proposal for API extension is described below.

Extension in the RSAPrivateKey.sign function:

• The algorithm parameter is allowed to be None, meaning that data is independent of hash algorithm.
• Only supported for some of the paddings (currently only PKCS1v15).
• The data is encoded as the raw signature data (without DigestInfo).

Extension in the RSAPublicKey.verify function:

• Allow None in the algorithm parameter with the same semantics as described for the sign function above.

Add a new function RSAPublicKey.verify_recover:

• Used to recover the digest (or raw signature data).
• Only supported for some of the paddings (currently only PKCS1v15).
• Returns the recovered data as bytes.
• Uses the same parameters as the verify function but removing the data parameter.
• The padding parameter is kept for future extensibility, even though only PKCS1v15 works for now.
• The algorithm parameter can None to return raw signature data (the same semantics as described above).
• When algorithm is a HashAlg, the signature is checked to contain that alg in DigestInfo and only the digest is returned.
• The Prehashed value may be kept as valid input for orthogonality, in which case it is only used as an alias for HashAlg.

From an API user point of view, I think the proposed changes will be simple to understand and to use, without breaking compatibility and introducing too much complexity. This is the best I could come up with for now. It is not straightforward to find a solution which keeps the current nice, simple API while adding the functionality needed. But please feel free to comment or improve the proposal. (For example, should we replace the None algorithm value with a more specific value similar to Prehashed, such as RawData?)

Note that this proposal only goes so far: it does not help if an application uses a a non-standard RSA padding, for example.

Implementation notes:

• OpenSSL handles most of the complexity and error handling of border cases.
• The None algorithm value can simply be mapped to skipping the call to EVP_PKEY_CTX_set_signature_md, in which case OpenSSL uses data without DigestInfo (both during signature creation and during verification).
• OpenSSL returns an error when using a padding (such as PSS) which requires the hash algorithm to be set.
• The None value also works as expected with some of the other algorithms, such as DSA.
• The verify_recover function can be implemented with the EVP_PKEY_verify_recover OpenSSL function.

[reaperhulk]

We've discussed allowing None padding previously, but we haven't been presented many cases where it would be beneficial. RSA is just a series of footguns and we're generally reluctant to make it easier to shoot yourself with textbook RSA, but if we can get a few examples of things that need to be able to sign raw maybe I can wrap my head around UnsafeRawData as a "padding" type. You've provided one, but if we want to add this I'd like to see several more (sorry!).

verify_recover is more straightforward. This seems like a reasonable API to add (given the imperfect RSA world we live in), although I wonder if it's more appropriately just named recover?

[misterzed88]

A minor clarification since you talk about padding: we are really discussing two different aspects here:

1. Using RSA with PKCS Initial commit. Migrates over basic project files, and the OpenSSL bindings #1 v1.5 padding (or just PKCS Initial commit. Migrates over basic project files, and the OpenSSL bindings #1 padding as we used to say in the good old days before version 1.5 of the spec), but where the data to sign/verify is provided in raw form (as a stream of bytes, with or without DigestInfo). The OpenSSL API is RSA_private_encrypt/RSA_public_decrypt with RSA_PKCS1_PADDING.
2. Using RSA without padding is for doing the low-level RSA exponentiation. Its OpenSSL API is RSA_public/private_encrypt/decrypt with RSA_NO_PADDING.

The change proposed here only deals with case 1. Case 2 is only needed for the rare cases where a custom padding is used.

I therefore proposed to keep padding as PKCS1v15 but allow None in the algorithm parameter for allowing raw signature data inside the PKCS #1 padding layer.

This is consistent with Windows CryptoAPI CNG, where NULL is used as algorithm ID for this case (https://docs.microsoft.com/en-us/windows/win32/api/bcrypt/ns-bcrypt-bcrypt_pkcs1_padding_info).

In OpenSSL (and BoringSSL), the same thing is accomplished by leaving the signature alg as NULL in the EVP context (by not calling EVP_PKEY_CTX_set_signature_md, see https://www.openssl.org/docs/man1.1.0/man3/EVP_PKEY_CTX_set_signature_md.html).

Allowing raw signature data, while using the PKCS #1 padding layer, is not inherently much less secure, especially if the digest alg is present but maybe with a non-standard deviation from DigestInfo. The latest PKCS #1 specification, in RFC 8017, mentions some cases where there is ambiguity in the DigestInfo encoding (in note 2 of of section 9.2).

Regarding verify_recover: nice that you think it is straightforward. The verify_recover naming comes from PKCS #11 and OpenSSL APIs. Perhaps we should name it recover if you think it's more appropriate.

[misterzed88]

Regarding use cases, in addition to the old Verisign timestamp certificate already mentioned, we also have the same issue with Thawte timestamp certificates: see the function rtCrPkixSignatureRsa_Verify in https://www.virtualbox.org/svn/vbox/trunk/src/VBox/Runtime/common/crypto/pkix-signature-rsa.cpp.

We also have the signed MD5/SHA1 hashes in TLS 1.1 or earlier (RFC 4346, section 4.7).

IKE version 1 also requires signatures without DigestInfo (RFC 2409, section 5.1).

In addition to the well-known cases above, the world is full of custom crypto implementations. For example, the German Signature Alliance (called TeleTrust), uses this format, as described in https://www.teletrust.de/fileadmin/files/oid/oid_DescriptionRsaSignatureWithoutHash.pdf.

But any third-party application can use this functionality, since it is easily available in common crypto APIs:

• Windows Crypto API NG (NULL algorithm ID)
• OpenSSL (skipping call to EVP_PKEY_CTX_set_signature_md)
• PKCS More docs #11 (the CKM_RSA_PKCS mechanism)

[misterzed88]

To summarize the proposal:

• Extend RSAPrivateKey.sign and RSAPublicKey.verify with allowing raw signature data to be used with the PKCS Initial commit. Migrates over basic project files, and the OpenSSL bindings #1 padding type, by setting None in the algorithm parameter.
• Add a function RSAPublicKey.recover for returning the original signature data, also allowing None as algorithm.

I am ready to move forward and propose the implementation changes, when (if?) we have agreed on what to do.

[misterzed88]

Ping: any news or comments on this proposal?

Should I prepare a pull request for both the proposed changes, recover only, or none of them? (You can always tell people to use other crypto libraries if they need this type of functionality).

[reaperhulk]

Let's do recover first and then we can discuss the other items. Your examples are helpful for framing the need for the other features, but recover is an easier first choice.

[reaperhulk]

(Given our recent security issue around RSA GHSA-hggm-jpg3-v476 we're also should be very careful about this)

[tomato42]

(regarding GHSA-hggm-jpg3-v476) The RSA signatures are much less of a foot-gun than RSA encryption/decryption, both from handling-of-errors case and from side-channel resistance case.

And signing with PKCS#1 v1.5 padding, but without DigestInfo is just as safe as signing in DSA or ECDSA: they don't encode the DigestInfo structure either.

[misterzed88]

@tomato42: Good points. The original purpose of DigestInfo was to include the hash algorithm to avoid algorithm ambiguity. There would be no way to know the algorithm used to create a signature, when the signature format supports multiple algorithms with the same digest size. That would open up to signature forgery attacks when one of the algorithms was broken. This attack is mitigated if the digest size uniquely identifies the algorithm used.

[misterzed88]

@reaperhulk: Now that the recovery part is done (in #5573), have you thought any more about extending RSA sign and verify with PKCS #1-padded signatures without DigestInfo? (suggested as using None as hash algorithm).

[tomato42]

hmm, I'd say that the #5573 is missing a test case with a static test vector, like a TLS 1.1 signature that encodes the concatenated MD5 and SHA-1 hash...

[misterzed88]

@tomato42: Agree, it would be good. Since #5573 is merged and closed, I will propose adding the test cases in a future PR.

[reaperhulk]

@misterzed88 Where did we leave off here? I'm happy to review more proposals 😄

[misterzed88]

Great that you are open for further proposals!

The two things which might be of interest are (as proposed above):

1. Extending RSA sign/verify to allow arbitrary PKCS Initial commit. Migrates over basic project files, and the OpenSSL bindings #1-padded data, without DigestInfo.
2. Adding static test vectors from existing protocols, such as TLS 1.1.

[larcho]

Great that you are open for further proposals!

The two things which might be of interest are (as proposed above):

1. Extending RSA sign/verify to allow arbitrary PKCS Initial commit. Migrates over basic project files, and the OpenSSL bindings #1-padded data, without DigestInfo.
2. Adding static test vectors from existing protocols, such as TLS 1.1.

Someone working on 1. ?

[alex]

There are no updates on this effort that are not represented on this issue.

[reaperhulk]

We've added several features here but reading through the issue now it's difficult to understand what features are still under discussion. If there are additional use cases we should consider please open a new issue and we can discuss.