RSA private key DER decode fails without CRT components

[bkommanaboyina]

I'm trying to decode the RSA private key which was DER encoded earlier without p, q, and CRT components (dmp1, dmq1 and iqmp is NULL). I'm using same openssl version for both encoding and decoding, encoding works fine but decode fails. In decode we call EVP_PKCS82PKEY() function, this is failing with below error:

469393408:error:0D078079:asn1 encoding routines:asn1_item_embed_d2i:field missing:crypto/asn1/tasn_dec.c:425:Field=p, Type=RSAPrivateKey

The above error is because field p is NULL, but with same p is NULL encoding is success. Any idea why encode is Success but decode fails?

The openssl version I tested is 1.1.1d.

The sample code:

To Encode RSA private key I used below code:

int encode_priv_key(EVP_PKEY * pkey, unsigned char *data, size_t * len)
{
    BIO *bio = NULL;
    BUF_MEM *bptr = NULL;
    PKCS8_PRIV_KEY_INFO *p8inf = NULL;

    if (NULL == len) {
        printf("%s:%d\n", __FILE__, __LINE__);
        return -1;
    }

    p8inf = EVP_PKEY2PKCS8(pkey);
    if (!p8inf) {
        printf("%s:%d\n", __FILE__, __LINE__);
        goto end;
    }

    bio = BIO_new(BIO_s_mem());
    if (!bio) {
        printf("%s:%d\n", __FILE__, __LINE__);
        goto end;
    }

    if (i2d_PKCS8_PRIV_KEY_INFO_bio(bio, p8inf) < 0) {
		printf("%s:%d\n", __FILE__, __LINE__);
        goto end;
	}

    BIO_get_mem_ptr(bio, &bptr);
    if ((*len < bptr->length) && data) {
        *len = bptr->length;
        printf("%s:%d\n", __FILE__, __LINE__);
        goto end;
	}
    *len = bptr->length;

    if (NULL != data)
        memcpy(data, bptr->data, *len);

    PKCS8_PRIV_KEY_INFO_free(p8inf);
    BIO_free(bio);
    return 0;
end:
    if (p8inf)
        PKCS8_PRIV_KEY_INFO_free(p8inf);
    if (bio)
        BIO_free(bio);
    return -1;
}

For decode we use below code:

EVP_PKEY *decode_priv_key(unsigned char *data, size_t len)
{
    BIO *bio = NULL;
    PKCS8_PRIV_KEY_INFO *p8inf = NULL;
    EVP_PKEY *pkey = NULL;

    bio = BIO_new_mem_buf(data, len);
    if (!bio) {
        printf("%s:%d\n", __FILE__, __LINE__);
        goto end;
    }

    p8inf = d2i_PKCS8_PRIV_KEY_INFO_bio(bio, NULL);
    if (!p8inf) {
        printf("%s:%d\n", __FILE__, __LINE__);
        goto end;
    }

    if (!(pkey = EVP_PKCS82PKEY(p8inf))) {
        printf("%s:%d\n", __FILE__, __LINE__);
        goto end;
    }

    PKCS8_PRIV_KEY_INFO_free(p8inf);
    BIO_free(bio);
    return pkey;

end:
    if (p8inf)
        PKCS8_PRIV_KEY_INFO_free(p8inf);
    if (bio)
        BIO_free(bio);
    if (pkey)
        EVP_PKEY_free(pkey);
    return NULL;
}

EVP_PKCS82PKEY() is failing with error reported above.

[bbbrumley]

Slight correction: parameters p and q are not CRT components.

[bkommanaboyina]

yeah agree, I mean without p and q and missing CRT components.

[davidben]

The "successful" encoding is due to a bug. It is actually outputting ambiguous, unparsable garbage. See #16026. OpenSSL 3.0 will have that bug fixed. Sadly, the bugfix had to be reverted in 1.1.1 because it was discovered that some TPM applications misused the i2d_X509 API to encode a different, non-X.509, structure.

The serialization for RSA private keys is defined here. It only works for RSA keys with CRT parameters. (See how the parameters are not marked OPTIONAL.) RSA keys without CRT parameters are not serializable in any standard format that I'm aware of.
https://datatracker.ietf.org/doc/html/rfc8017#appendix-A.1.2

[bbbrumley]

RSA keys without CRT parameters are not serializable in any standard format that I'm aware of

Yet you might be surprised what variations libraries are prepared to accept, due to the long history. See Tbl 1 and Appx A here.

[davidben]

Hrm. The paper makes some dubious claims about what is standard:

As further discussed in Section 3.4, the standard does not strictly
require implementations to include all the eight parameters during
serialization, nor to invalidate the object during deserialization if one of the
parameters is not included.

Recalling Section 2, an RSA private key is composed by
some redundant parameters while at the same time not all of
them are mandatory per RFC 8017 [55]: “An RSA private
key should be represented”. This implies that cryptography
implementations must deal with RSA private keys that do
not contain all parameters, requiring potentially computing
them on demand.

I'm not sure where you got this implication. While Section 3.2 of RFC817 describes two allowed forms of an RSA private key, the RSAPrivateKey ASN.1 structure does not mark the CRT parameters as optional. The only plausible reading is thus that the first RSA private key representation is not serializable.

I agree that the standard insufficiently specifies the deserialization process, particularly around parameter validation. BoringSSL will call RSA_check_key during the deserialization process to avoid some of these issues. (Our RSA_check_key checks most things except primality because that would be too expensive.)

The fuzzing consists of testing the loading of an RSA private key
when some parameters are equal to zero (i.e. empty PKCS #1
parameter).

I do not see anything in ASN.1 or the RFC that supports the notion of zero being how you omit an INTEGER parameter. ASN.1 has a notion of an OPTIONAL parameter, but you encode it by omitting the field altogether (which imposes some conditions on the tagging). If you're unfamiliar with ASN.1, Let's Encrypt has a nice overview here.

Alas, yes, some implementations have non-standard behavior here. I have seen weird things before like folks encoding zeros. I've also seen issues before with OpenSSL's RSA CRT error-check behavior because it silently retries the operation without CRT, rather than reporting an error, if the CRT parameters gave bad values. A couple of projects, in parsing some custom format, managed to swap p and q without realizing it, due to OpenSSL's behavior. (This is another reason to validate on key import.)

[bbbrumley]

I'm not sure where you got this implication.

I don't think it's meant to be taken that way, although I see how you get that.

I read it as "our experiments tell us a lot of code is doing this", rather than "if you're not doing this, your code is wrong".

"An RSA private key should be represented"

If you go back through the history of RFC 8017, you'll notice it pre-dates (by far) "SHOULD" "SHALL" etc considerations from RFC 8174.

Anyway, what a bunch of quacks. I'll send a scathing email to the authors now. Let me go find out who they are.

[levitte]

I think we can all agree that if an RSA key is claimed to be DER serialized according to PKCS#1 / RFC8017, it must serialize the structure of RSAPrivateKey or RSAPublicKey. Otherwise, that serialization is something else, it simply isn't PKCS#1 / RFC8017 compliant.

... and mind you, having other serialization formats is perfectly fine, but then that format should be specified and properly marked.

[bbbrumley]

I think we can all agree that if an RSA key is claimed to be DER serialized according to PKCS#1 / RFC8017, it must serialize the structure of RSAPrivateKey or RSAPublicKey

Totally

I'm derailing the original issue. My apologies, @bkommanaboyina

Please continue like normal

[romen]

@levitte one of the points is exactly that, and the recent discussion at OTC that resulted in reverting #16027 in 1.1.1 (see #16308) is a perfect example. OpenSSL, and many other libraries, often err on the side of legacy compatibility or historical interoperability when faced with bugfixes: this means that buggy or not conformant behavior is tolerated (or even defaulted to) in input and output, and non-standard things become de-facto standards.

The long and twisted story of RSA gave us multiple instances of this as discussed above!

[davidben]

@romen I think you are mixing up parsing vs. serialization, as well as historical errors vs. introducing new errors.

I don't know of any version of that OpenSSL tolerated missing fields when parsing an RSAPrivateKey, so there's not actually a backwards-compatibility problem. While #16027 had to be reverted, that was for serialization. Serialization was broken in old OpenSSL. Fixing that ran into a backwards-compatibility problem in one particular consumer. That one particular consumer was misusing the API in a context that happened to work for their particular use case. It is not a generally applicable strategy. Omitting fields in ASN.1 does not work generally work. It ends up syntactically ambiguous if there is a run of fields with the same tag.

Indeed RSAPrivateKey is one such case. If you delete a field in the middle vs. at the end, there's no way to tell which field was deleted.

[romen]

@davidben I was mixing it deliberately to stay on the general side and reiterate that across libraries and products "uncommon" serialization output and tolerance for "uncommon" encodings on parsing is not that unusual after all, and usually justified by interoperability, legacy baggage, historical reasons, despite what the standards encourage, recommend, mandate or forbid!

[levitte]

Either way, this issue is about decoding, and the example code is correctly demonstrating that OpenSSL serialization could be made to produce utter shite.

The take away lesson here is really, don't misuse OpenSSL bugs 😉

[levitte]

I would say that this issue can be closed at this point. I hope I sprinkled enough response labels...

[t-j-h]

Up to PKCS#1 v1.5 there was additional text included that made it clear what you were meant to do for portability if you did not have the CRT components. Unfortunately this text was omitted in later versions. It makes it exceedingly clear that you aren't expected to omit values or place in substitute values in the ASN1 representation - if you don't have the CRT values you need to calculate them. The syntax explicitly and deliberately requires the CRT values.

An RSA private key logically consists of only the
modulus n and the private exponent d. The presence
of the values p, q, d mod (p-1), d mod (p-1), and
q-1 mod p is intended for efficiency, as
Quisquater and Couvreur have shown [QC82]. A
private-key syntax that does not include all the
extra values can be converted readily to the
syntax defined here, provided the public key is
known, according to a result by Miller [Mil76].