Study: PK including parse/write in ECP-free builds

[mpg]

Currently the PK module does most crypto operations using PSA Crypto in builds with MBEDTLS_USE_PSA_CRYPTO. However, for parsing and writing keys it still relies on ECP functions - for (de)serialization, but also for checking the validity of the data, and also completing key pairs by computing the public part when only the private part was included. Also, it always stores key data in ECP structures, where it can only be accessed using ECP functions.

We want to be able to build, use and test the library without ECP when PSA drivers for ECDH and ECDSA are available. (Note: most of our tests depend on PK parse to load the key material that is required for testing.)

This task is to study how this can be achieve, come up with a plan, and create a series of estimated task achieving that result.

[mpg]

Currently the lifecycle of the key material in PK with USE_PSA_CRYPTO is a bit convoluted:

• When parsing the key with mbedtls_pk_parse(_public)_key(_file)(), after possibly unwrapping a few layers (PEM, PKCS#8 encryption, etc.) we get to a basic format which includes some information such as curve identifier, and an array of bytes what would be suitable to pass to psa_import_key(), but we don't do that, instead we store everything into an mbedtls_ecp_keypair structure.
• When using the key to generate or verify a signature, we use mbedtls_pk_write_key_der() or mbedtls_pk_write_pubkey() to serialize the info from that context and pass it to psa_import_key(), before we perform the actual operation, and then throw away the temporary PSA key.

While it makes some sense in that it allowed implementation of USE_PSA_CRYPTO in PK for sign/verify with minimal changes (entirely contained in pk_parse.c) it (1) feels a bit silly when you look at the big picture, (2) introduces a dependency of PK on PK_WRITE_C that's not natural and that we missed in the past, and more importantly (3) strongly stands in the way of getting PK (including parse and write) to work without ECP.

I can see two alternative approaches:

1. Using actual PSA keys: when parsing, actually psa_import_key() things into a key, then when signing/verifying, directly use that key.
2. Just store serialized key material:
   • While parsing the key, store the group identifier in some form, most probably a (PSA curve family, bitsize) pair, then when we get to the substring that's valid as input to psa_import_key(), save a copy of it in the pk_context (probably after doing a trial import just to validate the input).
   • When generating/verifying a signature, import to a temporary key as is done currently, except we don't to serialize it first.

The big advantage of the first approach is simplicity. However, it might not work if the key attributes can only be determined when doing the operation (TODO: check the code). Also, for public keys it might result in allocating a lot of PSA key slots in some circumstances, such as parsing a large number of X.509 certificates (like the list of trusted roots).

The second approach is a bit more complex but would avoid these issues. It may also be possible to use the first approach for private keys and the second one for public keys.

This is probably not a complete solution to building PK(parse,write) without ECP, but probably an important part of the solution, which I think sounds also nice to have anyway.

@gilles-peskine-arm If you have any thoughts on the topic they're welcome.
Cc @valeriosetti FYI

[gilles-peskine-arm]

Just store serialized key material:
When generating/verifying a signature, import to a temporary key as is done currently, except we don't to serialize it first.

Done in #6389, which needs rebasing and some tweaks around RSA (as it stands now, you can make a configuration without PK_WRITE where the build passes but then PSA exports of RSA keys fail at runtime).

Using actual PSA keys: when parsing, actually psa_import_key() things into a key, then when signing/verifying, directly use that key.
it might not work if the key attributes can only be determined when doing the operation

Indeed, when importing, you can't know what algorithms the key will be used for. For example a TLS 1.2 server might use the same RSA key to decrypt and sign. For ECC keys we might be able to get away with one flavor of ECDSA plus ECDH, but it's clearly a hack which is only possible by abusing the enrollment algorithm feature.

it might result in allocating a lot of PSA key slots in some circumstances

That is also a concern. Especially if PSA is in a secure world keystore and pk is in a normal world with more RAM.

---

This is probably not a complete solution to building PK(parse,write) without ECP

There's also the lack of support for parsing compressed points in PSA. This is a known issue, with no ETA for a solution (it doesn't fit well in the driver interface design, and I'd rather finish implementing the basic design before adding warts).

[mpg]

Just store serialized key material:
When generating/verifying a signature, import to a temporary key as is done currently, except we don't to serialize it first.

Done in #6389, which needs rebasing and some tweaks around RSA (as it stands now, you can make a configuration without PK_WRITE where the build passes but then PSA exports of RSA keys fail at runtime).

Oh, that's great news! I'm adding that PR to this EPIC then.

Indeed, when importing, you can't know what algorithms the key will be used for. For example a TLS 1.2 server might use the same RSA key to decrypt and sign. For ECC keys we might be able to get away with one flavor of ECDSA plus ECDH, but it's clearly a hack which is only possible by abusing the enrollment algorithm feature.

Agreed.

it might result in allocating a lot of PSA key slots in some circumstances

That is also a concern. Especially if PSA is in a secure world keystore and pk is in a normal world with more RAM.

Indeed, so combined with the previous point I think we have rather strong arguments for storing the serialized form of the key and temporarily importing at use time, rather than permanently storing in a key slot.

This is probably not a complete solution to building PK(parse,write) without ECP

There's also the lack of support for parsing compressed points in PSA. This is a known issue, with no ETA for a solution (it doesn't fit well in the driver interface design, and I'd rather finish implementing the basic design before adding warts).

I wouldn't consider that a blocker in the short term. Currently you can only build PK with ECP present and then you get parsing of keys with compressed points. In the near future we can add the option of building without ECP but then you don't get parsing of keys with compressed points (but you still have it in builds that were previously possible, that is with ECP). We just need to be careful and have enough testing (I don't think we're testing compressed points at the pkparse level right now) to make sure we don't break anything that currently works.

In the long term though, that will need to be resolved before we can move to a fully PSA-only world.

[mpg]

Just store serialized key material:

Done in #6389,

Looking at #6389 it's not doing what I had in mind. What I had in mind was to store the serialized key material as an array of bytes in the context, so that when using the key we can directly import() that. What #6389 is doing right now is storing the key material in an ecp_keypair structue, then using low-level ECP/bignum functions (instead of function from pkwrite) to write that to a buffer that's then passed to import().

I think #6389 is a step in the right direction, but not going all the way.

[mpg]

This task is to study how this can be achieve, come up with a plan, and create a series of estimated task achieving that result.

See #7073 and #7074.