mbedtls_ecp_group_cmp in test_suite_ecp is fragile

[gilles-peskine-arm]

In test_suite_ecp, there's a function mbedtls_ecp_group_cmp (added in 3.2 but backported to 2.28) which compares two group structures. It compares by value except for T which is compared by reference. This looks wrong.

~The goal of this issue is to compare T by value.~

Actually, diving deeper, I think that comparing T by address is correct, but under some assumption about when mbedtls_ecp_group_cmp is called. T is not a value like the other fields, it's a pointer to a cache. The cache should be shared between all the instances of a mbedtls_ecp_group_cmp structure. Looking at how group structures are constructed:

• Montgomery curves loaded by ecp_use_curve25519 or ecp_use_curve448 set grp->T_size = 0 and grp->T = NULL.
• Weierstrass curves loaded by ecp_load_group set grp->T to a pointer to static data, and grp->T_size = 0 to indicate that the group structure does not own the memory that T points to.

So initially comparing the T pointers is correct. However, after ecp_mul_comb has been called, grp->T may be set to some dynamically allocated memory. After that, grp->T is unique. I don't think mbedtls_ecp_group_cmp is intended to validate the contents of the cache. But now I don't understand how the tests using mbedtls_ecp_group_cmp are passing — shouldn't each group have its own T?

The goal of this issue is to understand what's going on and document it. (And fix if it turns out something needs fixing.)

[bleakprestiger]

Can I Take This Issue ? @gilles-peskine-arm I want to contribute to this issue

[gilles-peskine-arm]

@bleakprestiger Sure, thanks!

[bleakprestiger]

@gilles-peskine-arm, I have opened a PR - (#6715).

[mpg]

The code managing grp->T is more complex than it should be, due to historical baggage that hasn't been cleaned up yet. I've explained a lot of this recently in https://github.com/Mbed-TLS/mbedtls/issues/7601#issuecomment-1549304280 which I recommend reading for context.

Regarding the implications here, it should be noted that the situations in 3.x and 2.28 are very different.

The situation in 3.0

So initially comparing the T pointers is correct. However, after ecp_mul_comb has been called, grp->T may be set to some dynamically allocated memory. After that, grp->T is unique.

Not really. The code that may set grp->T to point to dynamically allocated memory is effectively dead, even if that's not obvious and non-local: it could only be reached if grp->T were NULL which it never is - left as an exercise to the reader: check that none of the xxx_T constants in ecp_curves.c are NULL (did I mention this was neither trivial nor local?). (Confirmed experimentally: the full CI still passes after this patch.)

I fully intend to remove this non-trivially-dead code: not only does it harm readability, it also prevents us from making grp const in several places. But I haven't gotten to it yet (it's not as trivial as it sounds, again see comments on #7601, but I have plans for it, it's just a matter of getting to it).

So, I believe in 3.0 it is fully correct compare T by reference when comparing groups. Currently, it's correct for reasons that are not obvious at all from reading the code, and after I've cleaned up the code, it should be obviously correct: for Montgomery it's always NULL and for Weierstrass it's always a pointer to a static array defined in ecp_curves.c.

The situation in 2.28

In 2.28 we don't have static arrays in ecp_curves.c, so for Weierstrass curves grp->T will be NULL before the first call to ecp_mul() with the conventional base G as the input point, and set to a unique value after that.

From a quick look at the test code, it happens to work only because it's only called on groups that were never used for multiplying G by something, so always have grp->T.

I think in 2.28 we should fix the test code: mbedtls_ecp_group_cmp() should not look at T but instead, we should assert that after calling mbedtls_ecp_group_copy(), we had grp_cpy.T == NULL (ideally even if grp.T isn't for the original group that we copied).