Implement Interruptible ECC Keypair Generation

[paul-elliott-arm]

Following on from the design finalised in #9044, implement the PSA interruptible ECC keypair generation.

This will include a basic driver wrapper layer that will only route to the internal implementation, and nested context structures to facilitate this and any future driver work in this area.

[gilles-peskine-arm]

Do we really need interruptible keypair generation?

ECC private key generation is very fast: it's essentially a symmetric operation. The costly part of ECC key pair generation is calculating the public key. The way Mbed TLS is structured, we don't store the public key, we recalculate it each time it's needed. So we don't need interruptibility for psa_generate_key. The same applies to FFDH.

RSA private key generation is slow, but we have no demand for interruptible RSA. And even if we did, RSA private key generation is so slow that it typically wouldn't be done in contexts where interruptibility is required.

[paul-elliott-arm]

I'm going off the spec sheet on #7293 to be honest - tagging @mpg for further discussion on this.

[yanesca]

The way Mbed TLS is structured, we don't store the public key, we recalculate it each time it's needed.

As far as I can tell we call mbedtls_ecp_gen_key() from PSA, which calculates the public key as well.

[gilles-peskine-arm]

As far as I can tell we call mbedtls_ecp_gen_key() from PSA, which calculates the public key as well.

Ah, indeed. So this ticket should morph into making PSA call code that doesn't waste time calculating the public key. (It wasn't a waste of time when originally written, because back then we kept the public key in memory.) I guess mbedtls_ecp_gen_privkey instead of mbedtls_ecp_gen_key. We should do this for 3.6 too.

[mpg]

I think Andrew has summarized things quite clearly here: ARM-software/psa-api#198

It seems to me that PSA Crypto implementation are free to compute the public key either during keygen or when exporting it (or both, as we're currently doing, though that's silly of course). So, I think the PSA Crypto API needs both interruptible keygen and interruptible export-public in order to preserve implementation freedom.

OTOH, our implementation should indeed be changed to not compute the public key during keygen only to discard it right away. Once that's done, I guess we could choose not to implement interruptible keygen and instead have our documentation say that ECC keygen is fast enough.

However, doing so would create a compatibility constraint: once we promise ECC keygen is fast enough, we're not allowed to change that in a minor release. Otherwise, people who have working code calling non-interruptible keygen would have to change their code in order to start calling interruptible keygen when upgrading, which is contrary to our compatibility promises.

So, in order to avoid imposing that compatibility constraint on ourselves, we might want to implement interruptible keygen right away. The implementation would probably be relatively as complete() would always complete the work the first time it's called. But the documentation would not promise it to be so (and perhaps even include a warning that this may change in the future, in case people notice and start wrongly thinking they can rely on this).

Then we'd be free to change our strategy about when the public part is computed and whether it's stored whenever we please.

Wdyt?

[gilles-peskine-arm]

@mpg Right, at the API level we don't want to commit whether the public key is calculated at generation time or each time it's needed. So there will be both an interruptible generate-key-pair and an interruptible export-public-key.

In Mbed TLS, since we don't keep the public key around (because it makes driver support easier), we should have psa_generate_key call mbedtls_ecp_gen_privkey rather than mbedtls_ecp_gen_key (which dates back from when we were keeping the mbedtls_ecp_keypair object around, instead of just keeping the export form of the key which only contains the private value).