Study: pk: handle pk_ec() safely

[mpg]

Following #7073 and #7074, when both ECP_LIGHT and USE_PSA are defined, PK contexts for (non-opaque) ECC keys store two copies of the key material: one in and ecp_keypair structure, one in the new priv_id / pub_raw fields.

However, the API contains a problematic function: mbedtls_pk_ec(), which gives user direct access to the ecp_keypair structure - worse, this access is read and write. If the user modifies the content of the ecp_keypair, then the new fields priv_id / pub_raw & Co need to be updated before each operation. OTOH, if the ecp_keypair object is not modified, no updating is needed.

I suggest the following course of action:

• Make mbedtls_pk_ec() depend on ECP_C again - that's the dependency in the last release so we don't it to keep it available in more builds than that.
• Add a new field dirty to pk_context, present when USE_PSA and ECP_C are defined. This filed is initialized to 0, and when mbedtls_pk_ec() is used, it it set to 1 and remains set until the context is freed.
• Add new internal functions mbedtls_pk_ensure_priv_id() / pub_raw() (or better names) that check if dirty is set, and if so, update the material in priv_id (resp. pub_raw & Co). When !USE_PSA || !ECP_C, this function does nothing and is static inline.
• Call the relevant function in all places that use priv_id (except Opaque keys) or pub_raw.
• Remove the calls to mbedtls_pk_update_public_key_from_keypair() (and the priv_id equivalent) from `test_suite_pk.function as they are no longer needed.

[gilles-peskine-arm]

I'm not familiar with the recent evolution of ECP light. Can you please link to how those priv_id and pub_raw fields work?

Add a new field dirty to pk_context, present when USE_PSA and ECP_C are defined

That would seem to defeat the purpose of having another copy of the key, but I don't know what the purpose of that copy is. mbedtls_pk_ec is frequently used for read-only access, and as soon as you do that this forever invalidates the copy. Then why have that copy in the first place?

[mpg]

Good question! The primary motivation for having this copy is to incrementally prepare for a case where it will no longer be copy, but the only way the key material is held. This is to support builds of PK with ECC support but without ECP_LIGHT - in that case we don't want to store key material in an ecp_keypair structure as we don't have any of the functions needed to manipulate that structure.

So, after a bit more work, we'd like to get to a point where things look like:

• if ECP_C is enabled then key material is stored in ecp_keypair and mbedtls_pk_ec() is available (which has to be the case to preserve compatibility);
• if USE_PSA is enabled, then key material is stored in priv_id (private keys) or pub_raw & Co (public keys).

So, with ECP_C && !USE_PSA and with USE_PSA && !ECP_C there's no duplication, but with ECP_C && USE_PSA we have duplication and only ecp_keypair is guaranteed to be up-to-date when mbedtls_pk_ec() has been used.

mbedtls_pk_ec is frequently used for read-only access

Note: this is something we can change. For example, we could introduce a new internal function that only gives a read-only pointer and doesn't invalidate the USE_PSA copy and use that in X.509 and TLS. Actually, I've been looking again at uses of mbedtls_pk_ec() in X.509 and TLS, and found they fall in two categories:

1. TLS 1.2 static ECDH - will be addressed by driver-only ECC: TLS: avoid use of mbedtls_ecp_point_write_binary() (with USE_PSA) #7405 and driver-only ECC: TLS: avoid use of mbedtls_ecp_write_key() (with USE_PSA) #7406 - this is a read-only access and we'll want to access the USE_PSA copy anyway.
2. Checking if the curve is acceptable (X.509 profile, TLS config) - I've been thinking about adding a new function that returns just the group ID. This is something applications might want as well.

Also, I'd really like to mark mbedtls_pk_ec() as deprecated soonish, so that people who are using it have an advanced warning before we remove it in 4.0. This would require removing all uses in the library, which goes in the same direction as the above paragraph.

[mpg]

Note: initially I didn't realise that the existence of mbedtls_pk_ec() meant we have no guarantee that the USE_PSA copy of the key material being valid. So, I agree that things are looking a bit weird at the moment (including the present issue) and there might be a better way.

[valeriosetti]

Add a new field dirty to pk_context, present when USE_PSA and ECP_C are defined. This filed is initialized to 0, and when mbedtls_pk_ec() is used, it it set to 1 and remains set until the context is freed.

The prototype of that function is:
static inline mbedtls_ecp_keypair *mbedtls_pk_ec(const mbedtls_pk_context pk)
which means that the pk structure is copied on the call. This means that the value of pk_ctx is fine and it can be returned (as it is now), but at the same time we cannot access other elements of the original pk_context structure (i.e. the new dirty field) as that copy of structure will be lost on exit.
Since this is a public function, my question is: am I allowed to change the prototype of the function to:
static inline mbedtls_ecp_keypair *mbedtls_pk_ec(const mbedtls_pk_context *pk)?
Otherwise I suspect that we'll have to slightly adjust your proposal

[gilles-peskine-arm]

Indeed mbedtls_pk_ec can't change the PK object. And we can't change its prototype: that was the whole point, if we could change it we'd just remove the function!

[valeriosetti]

Ok, so it seems to me that we have 2 options here:

• always force a sync between the ecp_keypair and the new mechanism before using the key (es: sign, verify, etc)
  • this might require to change the title/purpose of this issue to align with the new target
• use the new mechanism only as alternative to the legacy one
  • in this case this issue can be closed and that part should be solved in Avoid parse/unparse public ECC keys in PK with USE_PSA when !ECP_C #7073 and Avoid parse/unparse private ECC keys in PK with USE_PSA #7074 related PRs

Wdyt?

[gilles-peskine-arm]

always force a sync between the ecp_keypair and the new mechanism before using the key

Doesn't this completely defeat the purpose of having a PSA-friendly copy? It seems to me (but I've only looked at #7073 superficially) that the PSA-friendly copy is effectively a cache, and it's pointless to have a cache that needs to be refreshed each time.

use the new mechanism only as alternative to the legacy one

I'm not sure what that means exactly. But so far I think we can't change how we read the pk context when MBEDTLS_ECP_C is enabled. Only when defined(MBEDTLS_ECP_LIGHT) && !defined(MBEDTLS_ECP_C) because in that case we don't have backward compatibility constraints.

When ECP-light is enabled but not ECP-full, we can either add a PSA copy of the context, or treat the context as a PSA opaque context with mbedtls_pk_get_type returning MBEDTLS_PK_OPAQUE. I don't know which one would be the least painful.

[mpg]

The prototype of that function is:
static inline mbedtls_ecp_keypair *mbedtls_pk_ec(const mbedtls_pk_context pk)
which means that the pk structure is copied on the call.

Ouch, you're right. That kills the whole "dirty bit" approach. And as Gilles says, then it makes little sense to have a cache if it needs refreshing each time.

But again, if we take a step back, having a cache is not the ultimate goal here: the ultimate goal is to have something that works when we remove not only ECP_C but also ECP_LIGHT. I formulated #7073 and #7074 in a way that meant "implement a cache" because I thought that would be both an intermediate step towards the goal, and nice-to-have improvement while at it. Turns out I was wrong.

So, I think indeed we should abandon this caching idea, and re-focus on the larger goal: have something that works when ECP_LIGHT isn't available. We should probably use that version also when ECP_C isn't available, because the only thing that's blocking us from doing so is mbedtls_pk_ec() which we only need to keep when ECP_C is enabled.

When ECP-light is enabled but not ECP-full, we can either add a PSA copy of the context, or treat the context as a PSA opaque context with mbedtls_pk_get_type returning MBEDTLS_PK_OPAQUE. I don't know which one would be the least painful.

I don't think treating the context as opaque is the way to go here. As much as possible, applications should work the same regardless of whether things are provided by drivers or the built-in implementation. We have to make an exception for mbedtls_pk_ec() because it simply isn't practical to keep it without at least ECP_LIGHT, but making mbedtls_pk_get_type() return different results depending on whether ECP_C is enabled or not seems like the kind of change we can easily avoid.

Also, opaque contexts only support private keys for now, and store it in a PSA key slot. I'm not comfortable starting to store all public keys in a PSA key slot, as there are functions that create a large number a PK context holding public keys (for example, mbedtls_x509_crt_parse_path(..., "/etc/ssl/certs") will create more than 100 on my machine), and currently the default value of MBEDTLS_PSA_KEY_SLOT_COUNT is 32.

[gilles-peskine-arm]

Ok, that makes sense. Then we have three cases:

• defined(MBEDTLS_ECP_C), which continues to behave exactly like today.
• No ECC support in any of the code that observes USE_PSA_CRYPTO, which continues to behave like today.
• defined(MBEDTLS_USE_PSA_CRYPTO) && PSA_WANT_KEY_TYPE_ECC_PUBLIC_KEY && !defined(MBEDTLS_ECP_C) (regardless of MBEDTLS_ECP_LIGHT) where mbedtls_pk_ec doesn't exist at all, and all ECC code must use PSA functions exclusively. In that case, the mbedtls_pk_context object should only contain a PSA key id and perhaps some cached metadata, but no pointer to an mbedtls_ecp_keypair since no functions manipulating that type exist when MBEDTLS_ECP_LIGHT is disabled.

[mpg]

Ok, that makes sense. Then we have three cases: [...]

Indeed. That's where we want to get.

Now, we need to find an incremental path towards that. We're not ready to remove mbedtls_pk_ec() when ECP_C is undefined, because it's still used by X.509 and TLS, including in the USE_PSA case. And I'd really like to proceed layer by layer as much as possible: not only does it help avoid overly large PRs, its makes it easier to check we're respecting a contract between layers.

I think probably the easiest way, considering the work that's been done so far, would be to temporarily have a PSA-friendly copy in addition to the ecp_keypair (a "cache that needs refreshing each time"), as I think this makes it easier to migrate in an incremental way: we can have more and more of the code relying only on the PSA-frienly copy (test functions, X.509 and TLS via appropriate internal APIs), and then when nothing relies on mbedtls_pk_ec() and ecp_keypair any more, we simply remove them when ECP_C is disabled, and end up in the three-case situation you described. (That would implement the general migration pattern: first add the new thing, then make everything use it, then remove the old thing.)

@valeriosetti Do you think that works? The first step would be to modify #7554 so that mbedtls_pk_update_public_key_from_keypair() is called every time before accessing the new fields. (The PR's title would need to be changed to reflect reality as well.)

@gilles-peskine-arm Do you have an objection to having temporary states where a PK context can hold two copies of the key material, provided we pay attention to keeping everything functionally correct at each step, and the only problem is memory inefficiency? Of course we'd try to get out of that temporary state ASAP.

[gilles-peskine-arm]

We're not ready to remove mbedtls_pk_ec() when ECP_C is undefined, because it's still used by X.509 and TLS, including in the USE_PSA case

Ok, but then it still needs to be a private function, otherwise we now know that the PSA context isn't usable. And it can only exist if ECP_LIGHT is enabled, otherwise there's no ECP context to extract. So that intermediate stage is what I describe here, right?

(Not sure if we're in violent agreement or if I'm missing something)

[valeriosetti]

@valeriosetti Do you think that works? The first step would be to modify #7554 so that mbedtls_pk_update_public_key_from_keypair() is called every time before accessing the new fields. (The PR's title would need to be changed to reflect reality as well.)

Yes, that should not be a problem. I just pushed my proposal on #7554

[mpg]

Ok, I'm sorry bot not everything is clear in my mind yet, so I have trouble saying whether we're all in agreement or not. Before we discuss what intermediate states are desirable/convenient, I'd like to think again about what we want the final state to look like. Using a modification from this message where I disregard the case with no ECC at all as uninteresting, but instead split the first point depending on whether USE_PSA is enabled or not:

1. ECP_C && !USE_PSA - this remains unchanged, the key is stored only in ecp_keypair allocated as pk_ctx. Functions in pk_wrap use the legacy API.
2. ECP_C && USE_PSA - due to pk_ec(), the key needs to be stored in ecp_keypair (probably allocated as pk_ctx as well). Functions in pk_wrap need to convert that to a PSA-friently format before they do they real work.
3. !ECP_C && USE_PSA && PSA_WANT_KEY_TYPE_ECC_PUBLIC_KEY - thanks to not having pk_ec(), we can directly store the key in a PSA-friendly way (key slot for private keys, import format for public keys). Functions in pk_wrap can directly use the PSA-friendly format.

There's also Opaque keys (private only for now, exist in cases 2 and 3), which store the key in a PSA key slot, that functions in pk_wrap can directly use.

We want to share as much code as possible between cases 2 and 3 and Opaque keys.

What I had in mind before yesterday was that when USE_PSA is defined, pk_context always has PSA-friendly fields (priv_id + pub_raw & Co). Functions that want to use them need to call a function like pk_ensure_psa_fields() which is compile-time no-op in case 3, and in case 2 is a runtime no-op for Opaque keys, but otherwise updates the PSA-friendly fields from the the ecp_keypair. Then pk_wrap functions are identical for cases 2 and 3 and Opaque keys: they always use the PSA-friendly fields and just have this possibly-no-op function call at the beginning.

Now that I write it our explicitly, this is quite suboptimal, it would be better to not use the PSA-friendly fields in case 2 for non-opaque keys - having them while they need updating before each use wastes RAM and is just begging for subtle bugs that would be easy to miss in testing. So, yesterday I change my mind from this being the final state to being an intermediate state. (And now I'm not sure I'm happy with it even as an intermediate state.)

Instead, I think what we should do is that we should have internal functions in pk_wrap.c that take the PSA-friendly fields as arguments. Then for Opaque keys, and non-opaque keys in case 3, the operation wrapper is a thin wrapper around that internal functions (just calls it, passing pk->priv_id and/or pk->pub_raw etc); for non-opaque keys in case 2, the operation wrapper allocates PSA-friendly variables on its stack (priv_id and/or pub_raw buffer etc) then passes them to the internal function, then clears them upon return of the internal function. This achieves code sharing without (in case 2) having two copies of the key material in RAM at all times, one of them potentially out-of-date.

I'm now thinking this can probably be achieved directly without an intermediate step.

[mpg]

I think where we probably want an intermediate state is uses of mbedtls_pk_ec(). Here my current thinking is, as a first step:

1. For use in X.509 and TLS code, provide an internal function mbedtls_pk_get_ec() (guarded only by ECP_LIGHT) that returns a const pointer. (Note: since const is not deep in C, the compiler wouldn't necessarily catch all modifications of the key material through that pointer, but the documented contract of this function would clearly be that modifications are not allowed.) All uses of mbedtls_pk_ec() would be replaced by uses of this new internal function in all cases (including when ECP_C is defined and/or USE_PSA isn't).
2. Test code can use an internal version of mbedtls_pk_ec() like the one you defined in this commit.

So, compared to the current state of #7554, 2 is OK, but for 1 I'd like to add a clear distinction between read-only access and read-write access.

[gilles-peskine-arm]

it would be better to not use the PSA-friendly fields in case 2 for non-opaque keys

I agree. The presence of the extra PSA fields in case 2 has been bothering me ever since you pointed out the problem with mbedtls_pk_ec.

we should do is that we should have internal functions in pk_wrap.c that take the PSA-friendly fields as arguments. Then for Opaque keys, and non-opaque keys in case 3, the operation wrapper is a thin wrapper around that internal functions (just calls it, passing pk->priv_id and/or pk->pub_raw etc); for non-opaque keys in case 2, the operation wrapper allocates PSA-friendly variables on its stack (priv_id and/or pub_raw buffer etc) then passes them to the internal function, then clears them upon return of the internal function.

Indeed I think we have to do that as long as a 3.x-compatible MBEDTLS_ECP_C is enabled.

[valeriosetti]

ECP_C && USE_PSA - due to pk_ec(), the key needs to be stored in ecp_keypair (probably allocated as pk_ctx as well). Functions in pk_wrap need to convert that to a PSA-friently format before they do they real work.

Actually following Gilles' proposal I think that for backward compatibility as long as the user defines ECP_C explicitly the legacy solution should always be used. So we can keep the PSA friendly fields aligned, but not using them.
We can use PSA fields only in point 3, i.e. when !ECP_C && ECP_LIGHT && USE_PSA && PSA_WANT_ECC_KEY_PAIR.

[mpg]

Using the same cases as in my previous comment, trying to make it explicit what it would mean for each field:

1. ECP_C && !USE_PSA - only pk_ctx pointing to an ecp_keypair exists. No PSA-friendly field exists.
2. ECP_C && USE_PSA - pk_ctx pointing to an ecp_keypair exists and is used by all non-Opaque keys. In addition priv_id exists but is only used by Opaque keys. pub_raw & Co don't exist in pk_context (only on the stack of some functions).
3. !ECP_C && USE_PSA && PSA_WANT_KEY_TYPE_ECC_PUBLIC_KEY - pk_ctx remains NULL for all keys (except non-Opaque RSA keys). priv_ctx exists and is used by all ECC private keys (Opaque or not). pub_raw exists and is used by all public ECC keys (Opaque or not). (It's unclear to me if ECC private keys should also populate pub_raw & Co or not. One benefit of doing so is that it becomes easy to perform public-key operations (like verify) with private key with the same wrapper function as public keys.)

[mpg]

Instead, I think what we should do is that we should have internal functions in pk_wrap.c that take the PSA-friendly fields as arguments. Then for Opaque keys, and non-opaque keys in case 3, the operation wrapper is a thin wrapper around that internal functions (just calls it, passing pk->priv_id and/or pk->pub_raw etc); for non-opaque keys in case 2, the operation wrapper allocates PSA-friendly variables on its stack (priv_id and/or pub_raw buffer etc) then passes them to the internal function, then clears them upon return of the internal function. This achieves code sharing without (in case 2) having two copies of the key material in RAM at all times, one of them potentially out-of-date.

Trying to flesh that out with the example of the sign wrapper:

#if defined(MBEDTLS_USE_PSA_CRYPTO)
/* internal function used by wrappers below */
int ecdsa_sign_psa(psa_key_id_t id, ...) {
    // do it by calling psa_sign_hash() + format conversion
}

/* now the actual wrappers to be registered in pk_info structures */

// opaque (cases 2 and 3) + case 3 non-opaque
int ecdsa_sign_wrapper(mbedtls_pk_context_t pk, ... ) {
    return ecdsa_sign_psa(pk->priv_id, ... );
}

// case 2 non-opaque
#if defined(MBEDTLS_ECP_C)
int ecdsa_sign_wrapper(mbedtls_pk_context_t pk, ...) {
    const mbedtls_ecp_keypair *ecp_kp = pk->pk_ctx;
    psa_key_id_t psa_key;
    // populate psa_key from ecp_kp
    ret = ecdsa_sign_psa(psa_key, ...);
    // cleanup: destroy psa_key etc.
    return ret;
}
#endif
#else
// legacy non-PSA wrapper
#endif

[mpg]

For a public operation - if we choose to populate pub_raw & Co for private keys too (Opaque and non-Opaque): (showing only pub_raw for simplicity, of course there would be pub_raw_len etc.)

#if defined(MBEDTLS_USE_PSA_CRYPTO)
/* internal functon used by wrappers below */
int ecdsa_verify_psa(const uint8_t *pub_raw, ...) {
    // do it by doing format conversion + calling psa_verify_hash()
}

/* now the actual wrappers to be registered in pk_info structures */

// opaque (cases 2 and 3) + case 3 non-opaque
int ecdsa_verify_wrapper(mbedtls_pk_context_t pk, ... ) {
    return ecdsa_verify_psa(pk->pub_raw, ... );
}

// case 2 non-opaque
#if defined(MBEDTLS_ECP_C)
int ecdsa_verify_wrapper(mbedtls_pk_context_t pk, ...) {
    const mbedtls_ecp_keypair *ecp_kp = pk->pk_ctx;
    uint8_t pub_raw[MAX_SIZE];
    // populate pub_raw from ecp_kp
    ret = ecdsa_verify_psa(pub_raw, ...);
    // cleanup?
    return ret;
}
#endif
#else
// legacy non-PSA wrapper
#endif

For public operations if we choose not to populate pub_raw for private keys:

#if defined(MBEDTLS_USE_PSA_CRYPTO)
/* internal functon used by wrappers below */
int ecdsa_verify_psa(psa_key_id_t key, ...) {
    // do it by doing format conversion + calling psa_verify_hash()
}

/* now the actual wrappers to be registered in pk_info structures */

// opaque (cases 2 and 3)
int ecdsa_verify_wrapper(mbedtls_pk_context_t pk, ... ) {
    return ecdsa_verify_psa(pk->pub_raw, ... );
}

#if defined(MBEDTLS_ECP_C)
// case 2 non-opaque
int ecdsa_verify_wrapper(mbedtls_pk_context_t pk, ...) {
    const mbedtls_ecp_keypair *ecp_kp = pk->pk_ctx;
    psa_key_id_t psa_key;
    // populate psa_key from ecp_kp
    ret = ecdsa_verify_psa(psa_key, ...);
    // cleanup: destroy psa_key
    return ret;
}
#else /* ECP_C */
// case 3 non-opaque
int ecdsa_verify_wrapper(mbedtls_pk_context_t pk, ...) {
    psa_key_id_t pub_key;
    if (pk->priv_id != PSA_KEY_NONE) {
        return ecdsa_verify_psa(pk->priv_id, ...);
    }
    psa_key_id_t psa_key;
    // populate psa_key from pk->pub_raw etc.
    ret = ecdsa_verify_psa(psa_key, ...);
    // cleanup: destroy psa_key
    return ret;
}
#endif /* ECP_C */
#else /* USE_PSA */
// legacy non-PSA wrapper
#endif /* USE_PSA */

Note: there are two things we want to minimize:

1. Compiled code size in each legal configuration - this impact users.
2. Total source code size to support all legal configurations - this impacts maintainability and testing. (The situation on this front should vastly improve in 4.0, but we have to keep things manageable until then.)

[mpg]

Sorry for the verbosity, I felt I needed to spell things out as precisely as possible first to make sure things were clear in my mind, and hopefully this might help prevent misunderstandings as well.

I want to clarify a secondary goal in this: currently Opaque (PSA-held) keys have a number of limitations (can't write out the key even if the policy allows export, can't do check_pair, can't do public operations) which I'd like to lift. The motivation is that IMO each limitation adds to the conceptual complexity of the module ("Opaque keys allow you to use a PSA key everywhere a PK context is expected... except for a, b, c..." becomes much simpler if we can cut out the "except" clause or at least make the list shorter). By using a wrapper scheme that unifies as much as possible, I think this can be achieved with minimal effort and make things more uniform, hence more maintainable.

[mpg]

We seem to have an agreement on what the final state should be:

• If ECP_C, then pk_ec() is available, and pk_ctx is used for ECC keys, and there is no pub_raw fields. (Note: priv_id is present for the benefit of Opaque keys, but not used by ECC keys.)
• If !ECP_C, then pk_ec() is not present (and neither are internal helpers), pub_raw fields are present, populated and used,
  and pk_ctx is not used by ECC keys (that is, alloc and free functions are NULL in mbedtls_eckey_info, mbedtls_eckeydh_info and mbedtls_ecdsa_info - the field is still present for the benefit of other key types).

The case with ECP_C is how the code looks at present, so nothing changes here. I think implementing the final state for the !ECP_C case might be too much for a single PR. If that's the case, we might need to stop at intermediate steps where both pub_raw/priv_id and pk_ctx are populated and used. Since this only happens in the case where ECP_C is disabled, hence pk_ec() absent, this is safe so it's not a problem to merge things in this intermediate state where we have two copies of the key material.

Based on what's been started so far, I think we could divide the work up as follows:

1. Set mbedtls_pk_ec() as internal function when ECP_C is not defined #7595 fixes the guards on pk_ec() and introduces (temporary) internal functions;
2. Avoid parse/unparse public ECC keys in PK with USE_PSA when !ECP_C #7554 introduces pub_raw, populates and uses it for public (non-opaque) ECC keys when !ECP_C && USE_PSA - for now, pk_ctx is still allocated, but ideally at the end of the PR doesn't need to be populated (though it might still be for now if that's convenient).
3. Avoid parse/unparse private ECC keys in PK with USE_PSA when !ECP_C #7438 starts populating and using priv_id for private (non-opaque) ECC keys when !ECP_C && USE_PSA.
4. Either 7438 or a follow-up PR (depending on the size) removes all remaining uses of pk_ctx and finally changes the alloc/free functions to NULL for the three ECC key types when !ECP_C && USE_PSA.

In the above, it is always assumed that ECP_LIGHT is enabled. Once the above steps are complete, we should be in a good position to address the case !ECP_LIGHT. (Hopefully by that point it will be a simple matter of changing guards in the appropriate places.)

[mpg]

Closing as this has been addressed as part of #7073 and #7074 after all.