mbedtls_ecp_point_read_binary from compressed fmt

[gstrauss]

Description

mbedtls_ecp_point_read_binary() from MBEDTLS_ECP_PF_COMPRESSED format

Status

READY

Requires Backporting

Yes: mbedtls-2.28

Migrations

NO

Additional comments

While this is a feature, it adds major missing functionality that has cost me days of time troubleshooting and fixing in the hostap test suite. Please backport to mbedtls-2.28 branch.

Todos

• [x] Tests
• [x] Changelog updated
• [ ] Backported (please advise)

[gstrauss]

Related historical issues/PRs which attempted to address this shortcoming in mbedtls: https://github.com/Mbed-TLS/mbedtls/pull/521 https://github.com/Mbed-TLS/mbedtls/issues/861 https://github.com/Mbed-TLS/mbedtls/issues/1616

I hope this PR is small enough that mbedtls team will consider including it.

[gilles-peskine-arm]

Can you please explain why you want to add this feature, which as previously noted has been somewhat deprecated in TLS for several years? Is this for a protocol that's not TLS (which can be a good justification, despite the name “Mbed TLS”, the crypto library is not just for TLS)?

In any case I really don't see any justification for backporting it.

[gstrauss]

Can you please explain why you want to add this feature

As I noted above:

While this is a feature, it adds major missing functionality that has cost me days of time troubleshooting and fixing in the hostap test suite.

More details: hostap test suite uses compressed format in some places. hostap is widely used. hostapd - user space daemon for access points, including, e.g., IEEE 802.1X/WPA/EAP Authenticator for number of Linux and BSD drivers, RADIUS client, integrated EAP server, and RADIUS authentication server wpa_supplicant user space IEEE 802.1X/WPA supplicant (wireless client) for number of Linux, BSD, and Windows drivers

I am attempting to port hostap to be able to use mbedtls https://github.com/openwrt/openwrt/issues/10303 https://github.com/openwrt/openwrt/pull/10727 and the effort has exposed some gaps in mbedtls APIs. This PR is one.

[mpg]

Hi, and thanks for your contribution. Since you've linked to previous issues and PRs, you are aware that this is a feature we have rejected a few times already. Let me sum up the reasons:

• This format tends to be optional in standards; for example when ECC support was introduced in TLS 1.0-1.2, only the uncompressed format was mandatory to implement, all others were MAY (not even SHOULD) support, see RFC 4492 sec. 5.1.2.
• This format has since been removed from some standards; for example in TLS is was removed in TLS 1.3, and by RFC 8422 (which obsoletes RFC 4492) which even makes it a MUST NOT (in TLS, obviously, that doesn't prevent non-TLS APIs such as mbedtls_ecp_point_read_binary() from supporting it).
• Supporting this format either adds code to all builds, even for people who are not using it, or needs an additional configuration option, which adds to testing complexity. This price should not be paid if it's not worth it, and the points above suggest it shouldn't be.

However, standards in general and TLS in particular are not everything. If the feature is used widely enough in practice, it might be worth paying the price. You claim this is a major missing feature; I'd like to see that claim substantiated. The fact that this has been requested for the fourth time indeed points in that direction, but I'll note that the 3 links you gave didn't explain why this was needed; there's also #1608 which just said "if it's supported in writing, it should be supported in reading", which IMO is weak. So, your PR is the first one to offer an explanation: you want this in order to pass the hostap test suite.

First, thanks for providing that justification, but I'm afraid I'll answer with a few more questions: why is the hostap test suite using this format? Is it on purpose, or just by happenstance (like, this was the default format of the tool used to generate the test data? I'm unfamiliar with the protocol hostapd implements: is support for this format necessary to interop with other implementations or is there some kind of negotiation where each implementation can advertise what it supports (as in TLS, which is why we never need support for TLS?

Whether we want to support that feature depends on the answers to those questions; for example if it's necessary to interop with other implementations of a widely-used protocol, I'd say that's a clear yes; if it's just to pass a test suite that happens to use it by accident, I think that test suite should be improved instead.

Regardless, I want to state upfront that we are unlikely to accept adding this to 2.28; the bar for adding features to LTS branches is very high and this would require very strong justification.

[gstrauss]

An argument that I can give to you for why this feature should be included in mbedtls in some way is as follows: If I am using mbedtls as a library to provide crypto and TLS support, then I should avoid writing low-level crypto and TLS code outside of the crypto/TLS library. It is generally considered poor security practices to try to reinvent crypto library code if not an expert in crypto, and this is therefore a strong argument (IMHO) why the crypto algorithms should be provided by the mbedtls library.

@mpg wrote:

I think most of the work would be on improving testing and documentation/comments. Perhaps we'll want this to be guarded by a compile-time option as well.

Agreed. What do you suggest for a compile-time option name?

With a compile-time option, perhaps default disabled, there should hopefully be less of an argument about whether or not to include this small amount of additional code in mbedtls to support the optional feature to parse the compressed format, even if it is now deprecated/forbidden by the standards.

Separately, I plan to look further into the hostap code to see if the compressed format is used only in the test suite, or if it might be produced by the widely used hostapd and wpa_supplicant code. In the latter case, if it turns out to be true, then even if the code is modified to cease using the compressed format, there would be existing code out in the wild still using the compressed format. This remains to be determined.

[mpg]

An argument that I can give to you for why this feature should be included in mbedtls in some way is as follows: If I am using mbedtls as a library to provide crypto and TLS support, then I should avoid writing low-level crypto and TLS code outside of the crypto/TLS library. It is generally considered poor security practices to try to reinvent crypto library code if not an expert in crypto, and this is therefore a strong argument (IMHO) why the crypto algorithms should be provided by the mbedtls library.

I think we fully agree on that. But it's a fairly generic argument, which applies to all crypto constructs. We don't want to implement every single crypto alg or format that ever existed (for example, we never had support for binary curves, only primes), so in addition to that general argument, we need some reason to include this format specifically - evidence that it's widely used in production.

Separately, I plan to look further into the hostap code to see if the compressed format is used only in the test suite, or if it might be produced by the widely used hostapd and wpa_supplicant code. In the latter case, if it turns out to be true, then even if the code is modified to cease using the compressed format, there would be existing code out in the wild still using the compressed format. This remains to be determined.

That's the kind of thing I'm talking about. If the format might be produced by hostapd or wpa_supplicant, then as far as I'm concerned that's clearly a very strong argument to support this format. (And I fully agree that the argument holds as soon as it's produced by versions that are still in use, even if not the latest.) If on the other hand it's just the test suite, IMO the argument is much weaker - though I can see that passing existing test suites of widely-used software, even if they're using more than they should, is desirable it itself, as it would have saved you time in your porting effort (but then again, part of me is tempted to argue the test suite would be to blame here, if it had no good reason to use this format).

Agreed. What do you suggest for a compile-time option name?

I don't know. Perhaps MBEDTLS_ECP_READ_COMPRESSED_FORMAT (to highlight that we always support writing this format).

With a compile-time option, perhaps default disabled, there should hopefully be less of an argument about whether or not to include this small amount of additional code in mbedtls to support the optional feature to parse the compressed format, even if it is now deprecated/forbidden by the standards.

As a general principle, we try to avoid adding too many config options, as they tend to add to the testing complexity. However this particular one doesn't seem likely to interact with too many things, so it's probably fine.

PS: there are a few tests failing, in a lot of components. I only had a quick look, but it seems it's mostly negative cases. We can probably just use another value for the first bytes (AFAIK, 0x01 and 0x05 are never valid). Hopefully the same tests are failing in all the components, so just getting make test to pass should fix them all.

[gilles-peskine-arm]

PS: there are a few tests failing, in a lot of components. I only had a quick look, but it seems it's mostly negative cases.

Just for information, because I don't think many people know about this: you can get a list of test cases and their outcomes (pass/fail) in a machine-processable form from the file outcomes.csv which can be downloaded from the Artifacts tab of a build. For example here I can list the test cases that are failing in at least one component:

$ awk -F';' <outcomes.csv '$5=="FAIL" {print $3 ";" $4}' | sort | uniq -c | sort -n
     95 test_suite_ecjpake;ECJPAKE round one: KKP1: unknown first point format
     95 test_suite_ecjpake;ECJPAKE round one: KKP1: unknown second point format
     95 test_suite_ecjpake;ECJPAKE round one: KKP2: unknown first point format
     95 test_suite_ecjpake;ECJPAKE round one: KKP2: unknown second point format
     95 test_suite_ecjpake;ECJPAKE round two client: unknown first point format
     95 test_suite_ecjpake;ECJPAKE round two client: unknown second point format
     95 test_suite_ecjpake;ECJPAKE round two server: unknown first point format
     95 test_suite_ecjpake;ECJPAKE round two server: unknown second point format
     96 test_suite_ecp;ECP read binary #2 (zero, invalid first byte)
     96 test_suite_ecp;ECP read binary #5 (non-zero, invalid first byte)

This confirms that indeed it's only negative cases that need to be adjusted because reading a compressed point is no longer invalid.

[gstrauss]

I have confirmed that hostapd and wpa_supplicant (in hostap repo) produce COMPRESSED format in interface

/**
 * crypto_ecdh_get_pubkey - Retrieve public key from ECDH context
 * @ecdh: ECDH context from crypto_ecdh_init() or crypto_ecdh_init2()
 * @inc_y: Whether public key should include y coordinate (explicit form)
 * or not (compressed form)
 * Returns: Binary data f the public key or %NULL on failure
 */
struct wpabuf * crypto_ecdh_get_pubkey(struct crypto_ecdh *ecdh, int inc_y);

and COMPRESSED format is used in hostapd and wpa_supplicant when the second argument is 0:

wpa_supplicant/pasn_supplicant.c:	pubkey = crypto_ecdh_get_pubkey(pasn->ecdh, 0);
src/rsn_supp/wpa.c:		pub = crypto_ecdh_get_pubkey(sm->fils_ecdh, 1);
src/rsn_supp/wpa.c:		pub = crypto_ecdh_get_pubkey(sm->fils_ecdh, 1);
src/rsn_supp/wpa.c:	pub = crypto_ecdh_get_pubkey(sm->owe_ecdh, 0);
src/rsn_supp/wpa.c:	pub = crypto_ecdh_get_pubkey(sm->owe_ecdh, 0);
src/ap/ieee802_11.c:		pub = crypto_ecdh_get_pubkey(sta->fils_ecdh, 1);
src/ap/ieee802_11.c:		pub = crypto_ecdh_get_pubkey(sta->fils_ecdh, 1);
src/ap/ieee802_11.c:	pubkey = crypto_ecdh_get_pubkey(sta->pasn->ecdh, 0);
src/ap/ieee802_11.c:	pub = crypto_ecdh_get_pubkey(sta->owe_ecdh, 0);
src/ap/ieee802_11.c:		pub = crypto_ecdh_get_pubkey(sta->owe_ecdh, 0);
src/ap/ieee802_11.c:		pub = crypto_ecdh_get_pubkey(sta->owe_ecdh, 0);
src/ap/ieee802_11.c:		pub = crypto_ecdh_get_pubkey(sta->owe_ecdh, 0);
src/common/dpp_crypto.c:	pub = crypto_ecdh_get_pubkey(pfs->ecdh, 0);

I'll try to update the PR this weekend. Thank you for the testing hints, @gilles-peskine-arm

[gilles-peskine-arm]

I have confirmed that hostapd and wpa_supplicant (in hostap repo) produce COMPRESSED format (…)

Thanks for looking into this! Since there's a popular piece of software that produces the compressed format, I agree that it's good for Mbed TLS to accept it.

However, I do not see a justification to add it in the long-time support branch. Mbed TLS 2.28.0 already did not work with hostapd. Hostapd interoperability is a new feature that will require at least Mbed TLS 3.3.

[gstrauss]

Mbed TLS 2.28.0 already did not work with hostapd.

FYI: my prototype in https://github.com/openwrt/openwrt/pull/10727 currently requires

• mbedtls >= 2.27.0 for mbedtls_mpi_random()
• mbedtls >= 2.18.0 for mbedtls_ssl_tls_prf()

I am working my way up the stack and am in the process of implementing mbedtls support for hostap/wpa_supplicant EAP, SAE, and DPP. Lower layers already work with mbedlts 2.28.1 and mbedtls 3.2.1. (The prototype includes support -- outside of mbedtls -- for handling the COMPRESSED point format, and was the basis for this PR.)

[gstrauss]

Tests with invalid point encoding beginning 0x01 and 0x05 now return MBEDTLS_ERR_ECP_BAD_INPUT_DATA instead of MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE

I still need to add some tests beginning with compressed point encodings 0x02 and 0x03 to exercise expected failure cases.

[gstrauss]

Additional tests added and tests pass. Ready for review.

Please note that this PR cherry-picks cleanly onto mbedtls-2.28.1 with the exception of a trivially resolvable merge conflict in tests/suites/test_suite_ecp.data since some Curve448 tests were added between 2.28.1 and 3.x development branch.

The PR is well-contained. It is binary compatible in that it does not expose any new symbols or remove any symbols, and does not change any structure sizes. In Short Weierstrass curves with prime p where p = 3 mod 4, mbedtls_ecp_point_read_binary() handles MBEDTLS_ECP_PF_COMPRESSED binary point format where previously it returned error MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE

[mpg]

and COMPRESSED format is used in hostapd and wpa_supplicant when the second argument is 0:

Thanks for providing that detailed analysis! Indeed I now agree this is something we want to support. Let's finalize this PR then.

Regarding your request to backport to 2.28, it is really rare for us to backport new features to LTS branches (I mean, that's kind of the defining characteristic of LTS branches). For example, over its entire lifetime, 2.16 only got two ChangeLog entries in the Features section:

Features (2.16.8)
   * Support building on e2k (Elbrus) architecture: correctly enable
     -Wformat-signedness, and fix the code that causes signed-one-bit-field
     and sign-compare warnings. Contributed by makise-homura (Igor Molchanov)
     <[email protected]>.
Features (2.16.1)
   * Add MBEDTLS_REMOVE_3DES_CIPHERSUITES to allow removing 3DES ciphersuites
     from the default list (enabled by default). See
     https://sweet32.info/SWEET32_CCS16.pdf.

The first one is arguably more a bug fix than a new feature, and the second one is in response to a security concern.

Over its lifetime, 2.7 only got the above two entries plus:

Features (2.7.2 released 2018-03-16)
   * Extend PKCS#8 interface by introducing support for the entire SHA
     algorithms family when encrypting private keys using PKCS#5 v2.0.
     This allows reading encrypted PEM files produced by software that
     uses PBKDF2-SHA2, such as OpenSSL 1.1. Submitted by Antonio Quartulli,
     OpenVPN Inc. Fixes #1339

Ok, so that would be comparable to your request I guess: we extended an existing feature in order to improve interop with widely-used software. It could be considered a precedent.

@gilles-peskine-arm wdyt?

[gilles-peskine-arm]

@mpg wrote:

Over its lifetime, 2.7 only got the above two entries plus: [extending PKCS#8 for interoperability with OpenSSL 1.1]

Ok, so that would be comparable to your request I guess: we extended an existing feature in order to improve interop with widely-used software. It could be considered a precedent.

This is not a precedent. When 2.7.0 was released, older versions of OpenSSL were still popular and they defaulted to SHA-1. Over the lifetime of the 2.7 LTS, using SHA-2 became much more common. So systems that worked when 2.7.0 was released stopped working because another part of the system had upgraded OpenSSL. This is a good reason for adding a feature to an LTS branch: something that used to work, but no longer does because the rest of the world has changed. We were fixing the bug “Mbed TLS could read keys encrypted with OpenSSL, but no longer can”.

Here I don't see anything similar. 2.28.0 already couldn't interoperate with hostapd when it was released. Adding support for compressed points wouldn't fix something that used to work, but no longer does.

[gstrauss]

@gilles-peskine-arm wrote:

2.28.0 already couldn't interoperate with hostapd when it was released.

I disagree. My patches to hostap work with mbedtls 2.28.1 on my test platform and contradict your statement.

Adding support for compressed points wouldn't fix something that used to work, but no longer does.

While your assessment is reasonable, the impact is that my code in hostap and wpa_supplicant will be larger and messier for the multiple places that I have to #ifdef support for mbedtls 2.x. While I could wrap my calls to mbedtls_ecp_point_read_binary(), I also must wrap other mbedtls calls which themselves call mbedtls_ecp_point_read_binary() under the hood. Were this backported to 2.28.x, I could make 2.28.x a minimum prerequisite. At this moment, I can not impose that mbedtls 3.x be a requirement.

My effort to contribute this here is for the benefit of mbedtls and others. It is already a multi-day sunk cost for me to have discovered this gap and coded workarounds in my patches for hostap.

[mpg]

At this moment, I can not impose that mbedtls 3.x be a requirement.

Can you expand on that? I don't see why not. I mean, it's to be expected that some things will require the latest development version and that the LTS version will not be suitable for everything.

[gstrauss]

At this moment, I can not impose that mbedtls 3.x be a requirement.

Can you expand on that? I don't see why not. I mean, it's to be expected that some things will require the latest development version and that the LTS version will not be suitable for everything.

mbedtls 3.x included a major change to hide many previously-public accessors. While there are solid, defensible reasons for this major change, this major change imposes a particularly large burden on volunteer distro maintainers to push package maintainers to push upstream code to migrate to mbedtls 3.x interfaces. While there are shortcuts for code maintainers to "make things work for now", I have not yet seen (but haven't been looking either) any distro maintainers patch away MBEDTLS_PRIVATE access for the entire distro, nor do I think that a desirable approach.

In short, I think that the migration to mbedtls 3.x will take longer, and so mbedtls 2.28 LTS will be used for a longer period in "latest" distro stable releases.

Some efforts are underway and some appear to have stalled, e.g. alpine linux and gentoo linux https://gitlab-test.alpinelinux.org/alpine/aports/-/merge_requests/22976 https://packages.gentoo.org/packages/net-libs/mbedtls

Even Arch Linux uses 2.x https://archlinux.org/packages/?name=mbedtls

[Neustradamus]

Thanks @gstrauss for your good job!

I hope a merging soon :)

And I think that it is really important to add in 2.28.x branch to have a perfect compatibility with all. It is not a recent request:

• https://github.com/Mbed-TLS/mbedtls/pull/6282#issuecomment-1249043242

You can look here about version used:

• https://repology.org/project/mbedtls/versions

Thanks in advance.