PK: avoid large stack buffers in "to/from PSA" functions #687
No reviewers
Labels
No labels
api-break
approved
bug
component-docs
component-platform
component-test
dependencies
deprecation
DO-NOT-MERGE
enhancement
good first issue
help wanted
needs-adoption
needs-backports
needs-ci
needs-design-approval
needs-info
needs-preceding-pr
needs-review
needs-reviewer
needs-work
priority-high
priority-low
priority-medium
priority-scheduled
priority-very-high
resolved-after-1.1
single-reviewer
size-l
size-m
size-optimisation
size-s
size-xs
No milestone
No assignees
1 participant
Notifications
Due date
No due date set.
Dependencies
No dependencies set
Reference
gh-Mbed-TLS/TF-PSA-Crypto!687
Loading…
Reference in a new issue
No description provided.
Delete branch "pk-psa-large-stack-buffers"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
Description
Fixes https://github.com/Mbed-TLS/TF-PSA-Crypto/issues/476 (together with https://github.com/Mbed-TLS/TF-PSA-Crypto/pull/684 and #679).
Design notes
The design goals are:
I took the approach of deciding at compile time whether to use a stack or a heap buffer, based on whether non-ECC key types are enabled in the build.
I hesitated with an alternative approach where we always have a stack buffer, sized for ECC keys, and (if other key types are enabled) we decide at runtime whether we should use it or allocate a larger buffer. Compared to the approach in the PR, the upside is it avoid a heap allocation when using ECC keys in a build with RSA also enabled. The downside is we always have a stack buffer, even when it's useless. (Edit: I think the compile-time approach taken in this PR also has the advantage of being simpler.)
The common point in both approaches is they're based on the set of key types enabled in PK: namely if it's just ECC, we can function without a heap, otherwise (RSA now, ML-DSA later) we use the heap. That's not the only way, we could differentiate based on a new compile-time option, or piggy-back on the existing
MBEDTLS_PSA_STATIC_KEY_SLOTS. I chose the present approach because it works now without externally-visible change (new option or semantic extension of an existing one) and I don't think it prevents us from adopting another strategy in the future should we choose to do so.PR checklist
Approved for design. The execution needs work.
Note: regarding completeness, I'm assuming that the scope is strictly
pk.c, excluding auxiliary functions e.g. from otherpk*.cfiles.Please add a comment to summarize what this is used for.
I'm not sure “have keys larger than ECC” is the right name. I think it would make more sense to name the macro based on its impact than on its trigger.
Having read how it's used, I think it should be named something like
PK_CAN_EXPORT_KEYS_ON_STACK— with heap being the default case, and small-enough-for-the-stack being an optimization.Is this measurably advantageous over
PSA_EXPORT_KEY_OUTPUT_SIZE?I'm pretty sure this should be
Happens again further down.
Can this code never be called with public keys?
If it can then the array size is too small. But maybe it can't (since this is a fallback for
psa_copy_keyto bypass policy restrictions — but I don't remember without looking it up ifpsa_copy_keybypasses policy restrictions for public keys the same way export does).Note that as of 626a230590be34a484b9c47c1423c4c286f1a2cb,
pk_export_max_sizehas cases for public keys, but its stack counterpart is always sized for private keys.Two problems: stray
*on the array declaration, and wrong length because it doesn't accept public keys.@ -25,6 +25,11 @@#include <limits.h>#include <stdint.h>About the design: I don't like this compile-time selection of stack vs heap much because it's yet another compile-time variation, but of all the solutions I can think of, it's the one I dislike the least.
I prefer this compile-time choice to a runtime choice because the runtime choice means more code size, a compile-time choice anyway so that it's possible to build without malloc, and wasted space on the stack if the heap is going to be used anyway.
I have a slight preference for basing the stack-vs-heap selection on
MBEDTLS_PSA_STATIC_KEY_SLOTS(or a rebranded optionTF_PSA_CRYPTO_WITHOUT_MALLOC), so that we're consistent about using vs avoiding heap throughout the library. But I'm perfectly fine with ECC-only-or-not for now, and we can revise it after 1.1.0.About test coverage: I don't think we're missing testing of code paths. But I'd like some evidence in the outcome analysis that the non-default case is tested. Maybe define the symbol in
pk_internal.hand add cases for it totest_suite_config?@ -716,0 +728,4 @@/* We are exporting from a PK object, so we know key type is valid for PK */#if !defined(PK_EXPORT_KEYS_ON_THE_STACK)key_buffer_size = PSA_EXPORT_KEY_OUTPUT_SIZE(old_type, old_bits);I don't understand why the function takes additional parameters. Under what circumstances could
old_typeandold_bitsdiffer frompsa_get_key_type(attributes)andpsa_get_key_bits(attributes)?Is this fixing a resource leak or missing zeroization on failure?
Aw, embarrassing.
@ -716,0 +728,4 @@/* We are exporting from a PK object, so we know key type is valid for PK */#if !defined(PK_EXPORT_KEYS_ON_THE_STACK)key_buffer_size = PSA_EXPORT_KEY_OUTPUT_SIZE(old_type, old_bits);This function is
static, called from a single place and the called ensures thatold_type == psa_get_key_type(attributes)so that's OK. My problem is I couldn't convince myself that there is any guarantee thatbitsis set in the new attributes, ie thatpsa_get_key_bits(attributes) != 0.So, I mainly wanted to add
old_bitsjust to be sure, and addedold_typefor symmetry.Ah, I'm afraid I just has the brain bug that I implicitly though key pair was the max, while I know very well for ECC it is not, but apparently I just failed to think about it.
I'll double-check if there's any reason this code path can't be reached with public keys, but if there is that's pure luck, not something I had checked. (And if that happens to be the case, I'll add a comment because that's not obvious).
It's not fixing a pre-existing issue, but since we're now doing an allocation earlier in this function, we would have a resource leak (on the error path) without this change.
Hmm, tbh the reason I introduced this is I wasn't aware of
PSA_EXPORT_KEY_OUTPUT_SIZE. I hate to blame my ignorance on other people's naming choices, but the fact that the other macros are calledPSA_KEY_EXPORT_...but this onePSA_EXPORT_KEY_...was probably a factor in me not discovering this macro through completion.Anyway, now that I know it exists... perhaps there is an advantage in code size, as the compiler can skip the paths for key types other than ECC or RSA. Also I guess having a static function makes it easier for have a single copy of the code.
OTOH, I think the pros of using
PSA_EXPORT_KEY_OUTPUT_SIZE()are the usual pros for not re-inventing the wheel: obvious correctness, readability... except code size since it's a macro. (Btw I wonder if we should also have functions for all the non-trivial macros, for use in places that don't require the result to be a compile-time constant. But that's a larger topic and quite out of scope here.)I should probably make measurements so that we can decide based on facts just not thoughts.
Agreed with naming it based on impact rather than trigger. I think I'd be inclined to go the other way though:
PK_NEED_HEAP_FOR_KEY_EXPORT, as the will be more code when using the heap than when using the stack.Which one we see as the default vs an optimisation is mainly in our minds but doesn't really affect how much code is guarded by "if using the heap" vs "if using the stack" and I think I prefer the path with the most code to be guarded with a positive condition (ie,
#if defined(FOO)rather thanif !defined(BAR), though I'm not sure I could explain why.We settled on
PSA_EXPORT_KEY_xxx_SIZEfor the standard macros, I think to follow the general patternupcase(function_name)+thing+_SIZE. For consistency, we should rename the semi-private (visible but no doxygen documentation)PSA_KEY_EXPORT_xxx`.It's been on my mental to-do list (not sure if it's on github) for a long time for many reasons: save code size for the complicated ones, provide a way to use the library with a stable ABI, and maybe enable a tiny extra amount of type safety (not sure there's anything concrete though there since all the arguments are unsigned integers). It's not difficult, but it would take time to churn out the code and tests.
@ -716,0 +728,4 @@/* We are exporting from a PK object, so we know key type is valid for PK */#if !defined(PK_EXPORT_KEYS_ON_THE_STACK)key_buffer_size = PSA_EXPORT_KEY_OUTPUT_SIZE(old_type, old_bits);I think
attributes.bitscan be 0 there. I'd prefer to set it fromold_attributesincopy_into_psa()rather than add more parameters toexport_import_into_psa().By the way, the macro
PSA_EXPORT_ASYMMETRIC_KEY_MAX_SIZEwas only added to the API in 1.3, and we don't define it yet. Now would be a good time to implement it.@ -716,0 +728,4 @@/* We are exporting from a PK object, so we know key type is valid for PK */#if !defined(PK_EXPORT_KEYS_ON_THE_STACK)key_buffer_size = PSA_EXPORT_KEY_OUTPUT_SIZE(old_type, old_bits);That was my first thought as well, but we're taking a
constpointer, and it'sconstall the way to the public functionmbedtls_pk_import_into_psaso I don't think that's really an option.I'll note this is a static function with a single call site, so very likely to get inlined even at
-Osor-Oz. I'm not sure why adding a parameter to it is such a problem. (I agree that adding two while only one is need was probably misguided.)@gilles-peskine-arm If you don't mind I'm going to rewrite the history to fix two compilation failures in the commits that introduced them, then I'll address your other feedback with additional commits.
The commit you reviewed was 626a230590be34a484b9c47c1423c4c286f1a2cb
Fine by me.
Sorry for pushing something that was in such a bad shape (not even compiling in one of the obvious configs of interest) yesterday. What I just pushed at least passes
test_suite_pklocally in the default config and default minus RSA.I haven't addressed all of your comments yet, but I'd like to get CI feedback on this version.
@ -716,0 +728,4 @@/* We are exporting from a PK object, so we know key type is valid for PK */#if !defined(PK_EXPORT_KEYS_ON_THE_STACK)key_buffer_size = PSA_EXPORT_KEY_OUTPUT_SIZE(old_type, old_bits);Ah that's not true, I remember now why I added
old_type: sinceattributesis for the new key, using it to get the type of the old key seems weird enough that IMO it would require adding a comment along the lines of "we're a static function with a single caller who checked that the type in the new attributes match the type of the old key, so this is fine", at which point adding a new parameter with an explicit name frankly looked like a better option.Wdyt?
Building with
I'm getting:
So that's a 188 bytes difference, which IMO is enough to justify the new function. I can add a comment explaining why we're not directly using the macro, though.
If I understand correctly,
PSA_EXPORT_ASYMMETRIC_KEY_MAX_SIZEis just the new name for what we currently callPSA_EXPORT_KEY_PAIR_OR_PUBLIC_MAX_SIZEin which case it seems very easy to add indeed.@ -716,0 +728,4 @@/* We are exporting from a PK object, so we know key type is valid for PK */#if !defined(PK_EXPORT_KEYS_ON_THE_STACK)key_buffer_size = PSA_EXPORT_KEY_OUTPUT_SIZE(old_type, old_bits);The function is copying a key, so it feels very natural to me that old attributes = new attributes unless there was a mistake (the “new attributes” come from the application so we can't trust them). There's just the wrinkle that the new attributes might be incomplete: the type needs to be specified explicitly but not the size.
Wow, that much?
Hmm, what if we remove support for finite-field DSA? (How did that survive so long‽)
Well, I tried. https://github.com/Mbed-TLS/TF-PSA-Crypto/pull/321
After removing DSA, we're left with
I don't think we rely on 0 as the fallback case anywhere, and I doubt that applications do either, but changing that fallback in an LTS would slightly worry me. But in
development, how about simplifying this to fall back to the unstructured case?And we could further optimize in configurations without certain key types by making the construction of the definition more complicated.
With the new definition, the macro has negligible cost over my custom function (like 20 bytes), so let's do that!
@gilles-peskine-arm I believe my last push addresses all of your comments. If the CI is happy with it, then it's ready for re-review.
A couple of niggles, and missing changelog (since this was externally reported), otherwise LGTM
@ -48,0 +64,4 @@#if MBEDTLS_PSA_MAX_EC_KEY_PAIR_LENGTH > PK_EXPORT_KEY_STACK_BUFFER_SIZE#undef PK_EXPORT_KEY_STACK_BUFFER_SIZE#define PK_EXPORT_KEY_STACK_BUFFER_SIZE MBEDTLS_PSA_MAX_EC_KEY_PAIR_LENGTH#endifWhy not
? It would be equivalent now, but would be a safe default if we start to implement a new algorithm.
And come to think of it, I think it would make sense to base
PK_EXPORT_KEYS_ON_THE_STACKon the value ofPSA_EXPORT_ASYMMETRIC_KEY_MAX_SIZE. Likeor
@ -1027,7 +1023,8 @@PSA_KEY_EXPORT_FFDH_PUBLIC_KEY_MAX_SIZE(PSA_VENDOR_FFDH_MAX_KEY_BITS)I think we should mark it as deprecated.
and move to
crypto_compat.h@ -48,0 +64,4 @@#if MBEDTLS_PSA_MAX_EC_KEY_PAIR_LENGTH > PK_EXPORT_KEY_STACK_BUFFER_SIZE#undef PK_EXPORT_KEY_STACK_BUFFER_SIZE#define PK_EXPORT_KEY_STACK_BUFFER_SIZE MBEDTLS_PSA_MAX_EC_KEY_PAIR_LENGTH#endifNot strictly: consider a configuration where ECC and FFDH are enabled, but not RSA. Then from PK's point of view, there are no keys larger than ECC, but from PSA's pov, there are.
I quite like this idea, as from the beginning of this PR I've felt a bit uncomfortable about the condition "if RSA disabled" which will need changing when we add a new key type (though I've been telling myself that when we add a new key, surely we'll add tests cases and surely they would catch the problem if we forgot to update to "if RSA and ML-DSA both disabled" - surely).
This is a very direct way to express what we want (max export size small enough), it's robust when we add new algorithms, including not accidentally reintroducing very large stack buffers (unlike the first suggestion above I think).
The only drawback is that people with FFDH enabled will not get a heapless PK experience. OTOH, I'm not sure there are people who care about getting both a heapless PK and FFDH in their build?
@ -48,0 +64,4 @@#if MBEDTLS_PSA_MAX_EC_KEY_PAIR_LENGTH > PK_EXPORT_KEY_STACK_BUFFER_SIZE#undef PK_EXPORT_KEY_STACK_BUFFER_SIZE#define PK_EXPORT_KEY_STACK_BUFFER_SIZE MBEDTLS_PSA_MAX_EC_KEY_PAIR_LENGTH#endifIndeed. And in 1.1 or 1.2, we'll have MLDSA in PSA but not yet in PK, and ECC+MLDSA but no RSA (or FFDH) seems like a plausible configuration for systems that might want to avoid a heap.
I'm actually swinging back of this because of MLDSA. Heapless PK for ECC only, plus MLDSA with no PK support, will make sense in the medium term, and in particular it may be possible in the 1.1 LTS branch. (Maybe: I don't know yet whether we'll reach this milestone before the 1.1 code freeze.)
If it wasn't about PK, I wouldn't care. I don't think FFDH-but-no-RSA is important enough to optimize for.
@ -48,0 +64,4 @@#if MBEDTLS_PSA_MAX_EC_KEY_PAIR_LENGTH > PK_EXPORT_KEY_STACK_BUFFER_SIZE#undef PK_EXPORT_KEY_STACK_BUFFER_SIZE#define PK_EXPORT_KEY_STACK_BUFFER_SIZE MBEDTLS_PSA_MAX_EC_KEY_PAIR_LENGTH#endifUnless I'm mistaken there's nothing to do here after all.
@ -48,0 +54,4 @@* then we export keys on the stack, and otherwise we use the heap.** Note: add && !ML-DSA when adding support for ML-DSA */#if !defined(PSA_WANT_KEY_TYPE_RSA_PUBLIC_KEY)Should this be PSA_WANT_KEY_TYPE_RSA_KEY_PAIR_BASIC?
Thought I was leaving line comments, but apparently I had inadvertently started a review...
@ -48,0 +54,4 @@* then we export keys on the stack, and otherwise we use the heap.** Note: add && !ML-DSA when adding support for ML-DSA */#if !defined(PSA_WANT_KEY_TYPE_RSA_PUBLIC_KEY)I think
RSA_PUBLIC_KEYis the right one here: it is (in principle*) possible to have builds that only support RSA public keys but not RSA keypairs, while the reverse is prohibited: if RSA keypairs are enabled, then RSA public keys will be auto-enabled. That's not just a temporary thing, it's structural and unlikely to change.*In practice I don't think we test it, so it probably doesn't actually work. But still, that's something that makes sense and that we'd like to support in the future, so code should be written with that in mind.
@ -911,3 +907,3 @@PSA_KEY_TYPE_IS_ECC_PUBLIC_KEY(key_type) ? PSA_KEY_EXPORT_ECC_PUBLIC_KEY_MAX_SIZE(key_bits) : \0u)PSA_BITS_TO_BYTES(key_bits)) /*unstructured; FFDH public or private*/@gilles-peskine-arm Is this change acceptable in 3.6 or should I do something different for the backport?
@ -911,3 +907,3 @@PSA_KEY_TYPE_IS_ECC_PUBLIC_KEY(key_type) ? PSA_KEY_EXPORT_ECC_PUBLIC_KEY_MAX_SIZE(key_bits) : \0u)PSA_BITS_TO_BYTES(key_bits)) /*unstructured; FFDH public or private*/I think removing DSA is fine since you can't actually use a DSA key anywhere in Mbed TLS 3.6. I'm not sure about the fallback to 0, people could have inadvertently rely on it as a weak indicator of an invalid key type. But it wasn't a reliable indicator of an invalid key type (didn't detect invalid types that happen to have a bit pattern that matches the symmetric or unstructured category, didn't follow the library configuration). So I guess it's ok.
2f6f182af8872d391adbed1d67fbb7c0be73b2b2 is approved but there's a trivial (add/add) conflict.
I think it was an add/remove conflict, but anyway, I've resolved it.
There's a conflict again due to the file reorg, so I'll rebase and force-push again.
I only have one potential addition proposal, but otherwise LGTM
@ -927,3 +1007,3 @@status = psa_export_key(key_id, exp_key, sizeof(exp_key), &exp_key_len);status = psa_export_key(key_id, exp_key, exp_key_size, &exp_key_len);}if (status != PSA_SUCCESS) {Question: shouldn't we add usage of this function also in
mbedtls_pk_wrap_psa?@ -927,3 +1007,3 @@status = psa_export_key(key_id, exp_key, sizeof(exp_key), &exp_key_len);status = psa_export_key(key_id, exp_key, exp_key_size, &exp_key_len);}if (status != PSA_SUCCESS) {I think
pk_wrap_psa()already naturally checks the type while determining which info structure it should use: https://github.com/Mbed-TLS/TF-PSA-Crypto/blob/development/extras/pk.c#L173But in the future when we change that (we want to get rid of info structures at some point) then yes we will probably want to use this function in
mbedtls_pk_wrap_psa()as well.