[mpi] Sign not restored using write_binary & read_binary

maxencejded commented

2019-09-20 19:21:55 -05:00

(Migrated from github.com)

Description

Issue request type

[ ] Question
[ ] Enhancement
[X] Bug

Target:
mbedtls-2.9.0 on bignum.h && bignum.c

Issue:
Hello,

Regarding your mpi API. It doesn't properly handle signed numbers i.e mbedtls_mpi_write_binary & mbedtls_mpi_read_binary.
The sign bit isn't restored as it should be.

Thanks in advance for your help

example

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include "mbedtls/bignum.h"
#include "mbedtls/entropy.h"
#include "mbedtls/ctr_drbg.h"
#include "mbedtls/ecdh.h"
#include "mbedtls/error.h"

int main(int argc, char ** argv)
{
    int ret;
    const char custom[] = "ecdh";

    (void)argc;
    (void)argv;

    mbedtls_ecdh_context ctx;
    mbedtls_entropy_context entropy;
    mbedtls_ctr_drbg_context ctr_drbg;
    size_t len;
    char str[256];
    unsigned char buf[92];

    mbedtls_ecdh_init(&ctx);
    mbedtls_ctr_drbg_init(&ctr_drbg);
    mbedtls_entropy_init(&entropy);

    mbedtls_ctr_drbg_seed(&ctr_drbg, mbedtls_entropy_func, &entropy
        , (const unsigned char *)custom
        , sizeof custom
    );

    mbedtls_ecp_group_load(
          &ctx.grp
        , MBEDTLS_ECP_DP_SECP256R1
    );

    mbedtls_ecdh_gen_public(
          &ctx.grp
        , &ctx.d
        , &ctx.Q
        , mbedtls_ctr_drbg_random
        , &ctr_drbg
    );

    memset(str, 0, 256);

    // Enforcing negative point.
    // Q.Y=-17942908608878168716075795076500663303240066149140526344103562419645636906950
    // Qp.Y=0
    // Qp.Y=1
    // ... wrong
    // Qp.Y=17942908608878168716075795076500663303240066149140526344103562419645636906950
    ctx.Q.Y.s = -1;
    //

    mbedtls_mpi_write_string(&ctx.Q.Y, 10, NULL, 0, &len);
    mbedtls_mpi_write_string(&ctx.Q.Y, 10, str, len, &len);
    fprintf(stderr, "Q.Y=%s\n", str);

    memset(str, 0, 256);

    mbedtls_mpi_write_string(&ctx.Qp.Y, 10, NULL, 0, &len);
    mbedtls_mpi_write_string(&ctx.Qp.Y, 10, str, len, &len);
    fprintf(stderr, "Qp.Y=%s\n", str);

    mbedtls_mpi_lset(&ctx.Qp.Y, 1);

    memset(str, 0, 256);

    mbedtls_mpi_write_string(&ctx.Qp.Y, 10, NULL, 0, &len);
    mbedtls_mpi_write_string(&ctx.Qp.Y, 10, str, len, &len);
    fprintf(stderr, "Qp.Y=%s\n", str);

    len = mbedtls_mpi_size(&ctx.Q.Y);

    mbedtls_mpi_write_binary(&ctx.Q.Y, buf, 92);

    for (int i = 0; i < 92; i++) {
        fprintf(stderr, "%02X", buf[i]);
    }
    fprintf(stderr, "\n");
    
    mbedtls_mpi_read_binary(&ctx.Qp.Y, buf, 92); 

    memset(str, 0, 256);

    mbedtls_mpi_write_string(&ctx.Qp.Y, 10, NULL, 0, &len);
    mbedtls_mpi_write_string(&ctx.Qp.Y, 10, str, len, &len);
    fprintf(stderr, "Qp.Y=%s\n", str);

    mbedtls_ecdh_free(&ctx);
    mbedtls_ctr_drbg_free(&ctr_drbg);
    mbedtls_entropy_free(&entropy);

    return 0;
}

/* EOF */

### Description  ### Issue request type  [ ] Question [ ] Enhancement [X] Bug **Target:** mbedtls-2.9.0 on `bignum.h` && `bignum.c` **Issue:** Hello, Regarding your `mpi` API. It doesn't properly handle signed numbers i.e `mbedtls_mpi_write_binary` & `mbedtls_mpi_read_binary`. The sign bit isn't restored as it should be. Thanks in advance for your help example ```c #include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include "mbedtls/bignum.h" #include "mbedtls/entropy.h" #include "mbedtls/ctr_drbg.h" #include "mbedtls/ecdh.h" #include "mbedtls/error.h" int main(int argc, char ** argv) { int ret; const char custom[] = "ecdh"; (void)argc; (void)argv; mbedtls_ecdh_context ctx; mbedtls_entropy_context entropy; mbedtls_ctr_drbg_context ctr_drbg; size_t len; char str[256]; unsigned char buf[92]; mbedtls_ecdh_init(&ctx); mbedtls_ctr_drbg_init(&ctr_drbg); mbedtls_entropy_init(&entropy); mbedtls_ctr_drbg_seed(&ctr_drbg, mbedtls_entropy_func, &entropy , (const unsigned char *)custom , sizeof custom ); mbedtls_ecp_group_load( &ctx.grp , MBEDTLS_ECP_DP_SECP256R1 ); mbedtls_ecdh_gen_public( &ctx.grp , &ctx.d , &ctx.Q , mbedtls_ctr_drbg_random , &ctr_drbg ); memset(str, 0, 256); // Enforcing negative point. // Q.Y=-17942908608878168716075795076500663303240066149140526344103562419645636906950 // Qp.Y=0 // Qp.Y=1 // ... wrong // Qp.Y=17942908608878168716075795076500663303240066149140526344103562419645636906950 ctx.Q.Y.s = -1; // mbedtls_mpi_write_string(&ctx.Q.Y, 10, NULL, 0, &len); mbedtls_mpi_write_string(&ctx.Q.Y, 10, str, len, &len); fprintf(stderr, "Q.Y=%s\n", str); memset(str, 0, 256); mbedtls_mpi_write_string(&ctx.Qp.Y, 10, NULL, 0, &len); mbedtls_mpi_write_string(&ctx.Qp.Y, 10, str, len, &len); fprintf(stderr, "Qp.Y=%s\n", str); mbedtls_mpi_lset(&ctx.Qp.Y, 1); memset(str, 0, 256); mbedtls_mpi_write_string(&ctx.Qp.Y, 10, NULL, 0, &len); mbedtls_mpi_write_string(&ctx.Qp.Y, 10, str, len, &len); fprintf(stderr, "Qp.Y=%s\n", str); len = mbedtls_mpi_size(&ctx.Q.Y); mbedtls_mpi_write_binary(&ctx.Q.Y, buf, 92); for (int i = 0; i < 92; i++) { fprintf(stderr, "%02X", buf[i]); } fprintf(stderr, "\n"); mbedtls_mpi_read_binary(&ctx.Qp.Y, buf, 92); memset(str, 0, 256); mbedtls_mpi_write_string(&ctx.Qp.Y, 10, NULL, 0, &len); mbedtls_mpi_write_string(&ctx.Qp.Y, 10, str, len, &len); fprintf(stderr, "Qp.Y=%s\n", str); mbedtls_ecdh_free(&ctx); mbedtls_ctr_drbg_free(&ctr_drbg); mbedtls_entropy_free(&entropy); return 0; } /* EOF */ ```

👍 1 🎉 1

ciarmcom commented

2019-09-21 00:58:00 -05:00

(Migrated from github.com)

Internal Jira reference: https://jira.arm.com/browse/IOTCRYPT-929

*Internal Jira reference: https://jira.arm.com/browse/IOTCRYPT-929*

👍 2

mu578 commented

2020-05-14 10:35:44 -05:00

(Migrated from github.com)

Hello, @yanesca @athoelke

are there any news / updates about this topic. As per 2.16.6, it is still not addressed.

Thank you.

Hello, @yanesca @athoelke are there any news / updates about this topic. As per 2.16.6, it is still not addressed. Thank you.

👀 1

gilles-peskine-arm commented

2020-05-14 11:03:08 -05:00

(Migrated from github.com)

@moe123 I don't think there is actually a bug here. The documentation of mbedtls_mpi_write_binary states that it writes unsigned binary data. You can't expect to call mbedtls_mpi_write_binary on a negative number and read back a negative number with mbedtls_mpi_read_binary since there's no way to encode a sign.

I do see room for improvement: the documentation should state this in a more explicit way: mbedtls_mpi_write_binary writes the absolute value of the number.

@moe123 I don't think there is actually a bug here. The documentation of `mbedtls_mpi_write_binary` states that it writes **unsigned** binary data. You can't expect to call `mbedtls_mpi_write_binary` on a negative number and read back a negative number with `mbedtls_mpi_read_binary` since there's no way to encode a sign. I do see room for improvement: the documentation should state this in a more explicit way: `mbedtls_mpi_write_binary` writes the absolute value of the number.

👎 1

mu578 commented

2020-05-14 12:17:42 -05:00

(Migrated from github.com)

@gilles-peskine-arm ? if you were using a two's complement like rule; there is no issue for encoding sign-bit and restoring it properly; see what openssl does; they null byte prefix for the MSB.

🚀 1

gilles-peskine-arm commented

2020-05-14 13:36:04 -05:00

(Migrated from github.com)

@moe123 It sounds like you want a different pair of functions mbedtls_mpi_{write,read}_binary_twos_complement. Unsigned doesn't mean that negative numbers are represented using two's complement: it means that negative numbers can't be represented at all.

We will not change the existing functions to use two's complement because that would break backward compatibility. mbedtls_mpi_read_binary(X, "\234", 1) sets X to 156, not to -100.

Or maybe you're thinking of ASN.1, which represents non-negative numbers with a leading 0 bit and negative numbers in two's complement. If you want that, use mbedtls_asn1_{get,write}_mpi.

@moe123 It sounds like you want a different pair of functions `mbedtls_mpi_{write,read}_binary_twos_complement`. Unsigned doesn't mean that negative numbers are represented using two's complement: it means that negative numbers can't be represented at all. We will not change the existing functions to use two's complement because that would break backward compatibility. `mbedtls_mpi_read_binary(X, "\234", 1)` sets X to 156, not to -100. Or maybe you're thinking of ASN.1, which represents non-negative numbers with a leading 0 bit and negative numbers in two's complement. If you want that, use `mbedtls_asn1_{get,write}_mpi`.

mu578 commented

2020-05-14 13:56:07 -05:00

(Migrated from github.com)

@gilles-peskine-arm so in essence mbedtls_mpi_read_binary should not be public at all; it is useless and misleading API. MPI can represents many things and the negativeness of things being a natural part of it; especially somehow its = counterpart being the string representation...

P.S: no need to lecture me-self on the unsigned meaning of life; they were suggestions; you affirmed this is not possible to encode sign-bit per see, making it a fraudulent intellectual absolutism; it isn't; that's a parodic stand.

would break backward compatibility. mbedtls_mpi_read_binary(X, "\234", 1) this is not not an argument; it's properly detectable.

@gilles-peskine-arm so in essence `mbedtls_mpi_read_binary` should not be public at all; it is useless and misleading API. MPI can represents many things and the negativeness of things being a natural part of it; especially somehow its = counterpart being the string representation... P.S: no need to lecture me-self on the unsigned meaning of life; they were suggestions; you affirmed this is not possible to encode sign-bit per see, making it a fraudulent intellectual absolutism; it isn't; that's a parodic stand. + would break backward compatibility. mbedtls_mpi_read_binary(X, "\234", 1) this is not not an argument; it's properly detectable.

gilles-peskine-arm commented

2020-05-14 14:09:08 -05:00

(Migrated from github.com)

mbedtls_mpi_read_binary is perfectly fine. The problem is mbedtls_mpi_write_binary, which writes the absolute value of the number and should more properly be called mbedtls_mpi_write_binary_abs. I'll make a note about renaming it in the next major version of the library.

The bignum module in Mbed TLS is there for the sake of the cryptographic modules. It isn't meant to be a general-purpose bignum library. Both mbedtls_mpi_write_binary and mbedtls_mpi_read_binary are used extensively in other library modules, so they're doing their job. There's a good chance that the bignum module will become an internal-only library in Mbed TLS 3.0, although a few functions such as the read/write functions will likely remain public for the sake of importing and exporting key material in formats that the library doesn't support natively.

`mbedtls_mpi_read_binary` is perfectly fine. The problem is `mbedtls_mpi_write_binary`, which writes the absolute value of the number and should more properly be called `mbedtls_mpi_write_binary_abs`. I'll make a note about renaming it in the next major version of the library. The bignum module in Mbed TLS is there for the sake of the cryptographic modules. It isn't meant to be a general-purpose bignum library. Both `mbedtls_mpi_write_binary` and `mbedtls_mpi_read_binary` are used extensively in other library modules, so they're doing their job. There's a good chance that the bignum module will become an internal-only library in Mbed TLS 3.0, although a few functions such as the read/write functions will likely remain public for the sake of importing and exporting key material in formats that the library doesn't support natively.

mu578 commented

2020-05-14 14:10:00 -05:00

(Migrated from github.com)

ok EC curve points can be negative; must not be sake enough; are you aware that with mbedtls many people implement other protocols and it serves as a crypto toolkit backend ; rather than purely a TLS library; a pretty common usage out there; making mpi totally private is a non-sense why not asn.1 parser too; the proof you did implement J-Pake and other unrelated cipher suite.

ok EC curve points can be negative; must not be `sake` enough; are you aware that with mbedtls many people implement other protocols and it serves as a crypto toolkit backend ; rather than purely a TLS library; a pretty common usage out there; making mpi totally private is a non-sense why not asn.1 parser too; the proof you did implement J-Pake and other unrelated cipher suite.

gilles-peskine-arm commented

2020-05-14 14:29:04 -05:00

(Migrated from github.com)

More precisely, EC points are elements a finite field. Is there a standard format that uses or allows negative representatives? SEC1 defines the export format for prime curves in a way that essentially takes the smallest nonnegative representative.

Mbed TLS is indeed a cryptography library and not just a TLS (and X.509) library. Do you have a concrete use case for exposing low-level bignum functions? If so we'd love to hear about it (on the mailing list, here, or in private if you prefer), since we're currently planning API changes for the next major version.

More precisely, EC points are elements a finite field. Is there a standard format that uses or allows negative representatives? SEC1 defines the export format for prime curves in a way that essentially takes the smallest nonnegative representative. Mbed TLS is indeed a cryptography library and not just a TLS (and X.509) library. Do you have a concrete use case for exposing low-level bignum functions? If so we'd love to hear about it (on the mailing list, here, or in private if you prefer), since we're currently [planning API changes for the next major version](https://developer.trustedfirmware.org/w/mbed-tls/tech-plans-3.0/).

mu578 commented

2020-05-14 14:52:12 -05:00

(Migrated from github.com)

I don't know about standard; the mathematical additive inverse concept yes; some folks make use of it and many other things and properties; not for keys; can't say much.

Do you have a concrete use case for exposing low-level bignum functions?

yes many, however, this can't be made public at this time (I don't think I am alone).

there is nothing low-level speaking in bignum; this is a very high-level software API implementation for big/large/prime numbers representation that can't be hold by any PODs; if you name something low-level because someone used a bit shift operator we definitely do not have the same definition of those words.
In all the threads mentioned there is no such matter discussed; only dropping what
people should not use anymore; i.e backward compatibility SSL within TLS transport
and well known broken ciphers.
About the cert-test, the argument appeal is wonky; just generate your keys for testing on the fly same for certs; done; now, preventing the making of idiots re-using your keys... who cares?
idiots will always find a way to do idiotic things no matter what.

I don't know about standard; the mathematical additive inverse concept yes; some folks make use of it and many other things and properties; not for keys; can't say much. `Do you have a concrete use case for exposing low-level bignum functions?` yes many, however, this can't be made public at this time (I don't think I am alone). + there is nothing low-level speaking in bignum; this is a very high-level software API implementation for big/large/prime numbers representation that can't be hold by any PODs; if you name something low-level because someone used a bit shift operator we definitely do not have the same definition of those words. + In all the threads mentioned there is no such matter discussed; only dropping what people should not use anymore; i.e backward compatibility SSL within TLS transport and well known broken ciphers. + About the cert-test, the argument appeal is `wonky`; just generate your keys for testing on the fly same for certs; done; now, preventing the making of idiots re-using your keys... who cares? idiots will always find a way to do idiotic things no matter what.

maxencejded commented

2020-05-15 08:25:25 -05:00

(Migrated from github.com)

Hello,

First of all thanks for your answers, I changed my code to use mbedtls_asn1_{get,write}_mpi and the function get doesn't restore the sign of the mpi. So the question is why save it if you don't restore it ? Is-it a bug or a new functionality ?

I hope you'll be able to help me, thanks.

Hello, First of all thanks for your answers, I changed my code to use `mbedtls_asn1_{get,write}_mpi` and the function `get` doesn't restore the sign of the `mpi`. So the question is why save it if you don't restore it ? Is-it a bug or a new functionality ? I hope you'll be able to help me, thanks.

mu578 commented

2020-05-15 10:17:43 -05:00

(Migrated from github.com)

@maxencejded, @gilles-peskine-arm , @athoelke, @mpg, @sbutcher-arm, @hanno-arm, @mpg @eliteraspberries, @yanesca

Yes that's because mbedtls_asn1_write_mpi handles well the sign as two's complement however mbedtls_asn1_get_mpi is just a portmanteau to mbedtls_mpi_read_binary the only test made is to know if the tag is an integer; hence yes there is a bug running deep down within this API; sign is never restored in asn.1 parser either; so if the asn.1 parser encounters a signed integer garbage is restored.

We are back to the faulty design of mbedtls_mpi_read_binary, mbedtls_mpi_write_binary either it is an unfinished job by original author or a lack of thoughts? why handling properly sign in writing and not in restore? maybe even at ARM some people get confused about those two calls?
it's like having two different persons writing the set/get calls.

BTW, by a simple unit-testing policy the issue would have been noticed then a full review of contextual usage would have been engaged, this situation looks like the result of no proper QA at all.

@maxencejded, @gilles-peskine-arm , @athoelke, @mpg, @sbutcher-arm, @hanno-arm, @mpg @eliteraspberries, @yanesca Yes that's because `mbedtls_asn1_write_mpi` handles well the sign as two's complement however `mbedtls_asn1_get_mpi` is just a portmanteau to `mbedtls_mpi_read_binary` the only test made is to know if the tag is an integer; hence yes there is a bug running deep down within this API; sign is never restored in asn.1 parser either; so if the asn.1 parser encounters a signed integer garbage is restored. We are back to the faulty design of `mbedtls_mpi_read_binary`, `mbedtls_mpi_write_binary` either it is an unfinished job by original author or a lack of thoughts? why handling properly sign in writing and not in restore? maybe even at ARM some people get confused about those two calls? it's like having two different persons writing the set/get calls. BTW, by a simple unit-testing policy the issue would have been noticed then a full review of contextual usage would have been engaged, this situation looks like the result of no proper QA at all.

🚀 1

mpg commented

2020-05-18 03:09:20 -05:00

(Migrated from github.com)

In all the threads mentioned there is no such matter discussed

Indeed, there are many more topics to be discussed and threads to be started. This particular topic falls under the general goal "Reduce the surface of the public API" (and partly "Prepare the migration to PSA Crypto" too). It doesn't have its now thread yet; I've made a note, and when I'll start the thread about this I'll be sure to link to this issue (and add a link to the m-l thread in this issue).

> In all the threads mentioned there is no such matter discussed Indeed, there are many more topics to be discussed and threads to be started. This particular topic falls under the general goal "Reduce the surface of the public API" (and partly "Prepare the migration to PSA Crypto" too). It doesn't have its now thread yet; I've made a note, and when I'll start the thread about this I'll be sure to link to this issue (and add a link to the m-l thread in this issue).

mpg commented

2020-05-18 04:09:42 -05:00

(Migrated from github.com)

I think there's indeed a bug in mbedtls_asn1_get_mpi(): it does do handle negative numbers, while its documentation states no such restriction. Since initially the ASN1 parse was written mostly to support the needs of X.509, the restriction was probably intentional, but should have been documented.

The situation with mbedtls_asn1_write_mpi() is clearer: the documentation states that the MPI to write "must be non-negative".

@maxencejded I'd like to take a step back and understand why you wanted to write and read negative MPIs in the first place. I see your code seems to be dealing with ECC, more specifically ECDH. All standards I'm aware of regarding ECDH and ECC in general (over prime fields, which is the only kind of ECC implemented in Mbed TLS, and the only recommended one nowadays) require the coordinates of each point to be represented a integers in the range [0, p) where p is the prime defining the finite field. As such, they never need to encode a negative MPI as bytes.

ok EC curve points can be negative; [...] I don't know about standard; the mathematical additive inverse concept yes

I think there's some confusion here. The set of points on an elliptic curve is an additive group, so each point has an additive inverse indeed. But (1) that doesn't mean that some curve points would "be negative" (2) even it that were the case, that wouldn't mean the coordinates of those points would be negative.

The concept of "being negative" does not come with group structure and additive inverse in general. It also requires that the group be equipped with a total order. Some familiar groups, such as the integers, rationals and real for addition, come with a total order. Since they also have a "0" element from being a group, we can call positive the elements that are greater than 0, and negative those that are less than 0. Some other familiar groups, such as the complex numbers for addition, don't come with a total order, and then there is no concept of "negative" elements. That's the case for two less familiar additive groups discussed here: the group of points on an elliptic curve, and the additive group of integers modulo p (aka (GF(p), +)) - neither of these come with a total order, so neither have a concept of "negative" elements.
For Short Weierstrass curves, ie with equation y^2 = x^3 + ax + b, people sometimes talk of "the sign bit of y" in the context of point compression. That's a shortcut, it doesn't mean that some values of y would be negative (see point above, y is an element of GF(p)). If you look at the details, for example SEC1 Section 2.3.3, point 2.2.1 you'll see that it would be more exact to speak of a "parity bit" as it's indeed the least significant bit of y represented in the [0, p) range. Over the reals, if I pick a point of a given elliptic curve and send you only the value of the x coordinate, then you have two possible value for y, namely +-sqrt(x^3 + a*x + b), and I can disambiguate between the two by telling you the sign of y. Over GF(p), there are also two possible values for y: when both represented in the [0, p) range, one of them is odd and the other is even (is y_1 is a possible value, then p - y_1 is the other and since p is odd...). However, most people are more familiar with the reals than with finite fields, so the slightly improper terminology "sign bit of y" is still often used colloquially - but generally avoided in standards, to prevent any confusion that might understandably arise from it.
Again for Short Weierstrass curves, the additive inverse of the point (x, y) is (x, -y). But of course since y is in GF(p), -y means -y mod p, which (unless y is 0) is actually p-y, again a non-negative number. So if you take two points an a curve that are additive inverses of each other, you can't say that one of them is positive and the other negative, you can just say that one of them has a y coordinate that's odd when represented in the range [0, p) and the other has an even y coordinate.

Long story short:

there is no mathematical concept of "being negative" for points on elliptic curves or elements of GF(p)
points on elliptic curves are represented via their coordinates which are elements of GF(p); elements of GF(p) can always represented as non-negative integers in the range [0, p); all standards I know of rely on this representation for on-the-wire formats.

I think there's indeed a bug in `mbedtls_asn1_get_mpi()`: it does do handle negative numbers, while its documentation states no such restriction. Since initially the ASN1 parse was written mostly to support the needs of X.509, the restriction was probably intentional, but should have been documented. The situation with `mbedtls_asn1_write_mpi()` is clearer: the documentation states that the MPI to write "must be non-negative". @maxencejded I'd like to take a step back and understand why you wanted to write and read negative MPIs in the first place. I see your code seems to be dealing with ECC, more specifically ECDH. All standards I'm aware of regarding ECDH and ECC in general (over prime fields, which is the only kind of ECC implemented in Mbed TLS, and the only recommended one nowadays) require the coordinates of each point to be represented a integers in the range [0, p) where p is the prime defining the finite field. As such, they never need to encode a negative MPI as bytes. > ok EC curve points can be negative; [...] I don't know about standard; the mathematical additive inverse concept yes I think there's some confusion here. The set of points on an elliptic curve is an additive group, so each point has an additive inverse indeed. But (1) that doesn't mean that some curve points would "be negative" (2) even it that were the case, that wouldn't mean the _coordinates_ of those points would be negative. 1. The concept of "being negative" does not come with group structure and additive inverse in general. It also requires that the group be equipped with a [total order](https://en.wikipedia.org/wiki/Total_order). Some familiar groups, such as the integers, rationals and real for addition, come with a total order. Since they also have a "0" element from being a group, we can call positive the elements that are greater than 0, and negative those that are less than 0. Some other familiar groups, such as the complex numbers for addition, don't come with a total order, and then there is no concept of "negative" elements. That's the case for two less familiar additive groups discussed here: the group of points on an elliptic curve, and the additive group of integers modulo p (aka (GF(p), +)) - neither of these come with a total order, so neither have a concept of "negative" elements. 2. For Short Weierstrass curves, ie with equation y^2 = x^3 + ax + b, people sometimes talk of "the sign bit of y" in the context of point compression. That's a shortcut, it doesn't mean that some values of y would be negative (see point above, y is an element of GF(p)). If you look at the details, for example [SEC1 Section 2.3.3, point 2.2.1](https://www.secg.org/sec1-v2.pdf#page=16) you'll see that it would be more exact to speak of a "parity bit" as it's indeed the least significant bit of y represented in the [0, p) range. Over the reals, if I pick a point of a given elliptic curve and send you only the value of the x coordinate, then you have two possible value for y, namely +-sqrt(x^3 + a*x + b), and I can disambiguate between the two by telling you the sign of y. Over GF(p), there are also two possible values for y: when both represented in the [0, p) range, one of them is odd and the other is even (is y_1 is a possible value, then p - y_1 is the other and since p is odd...). However, most people are more familiar with the reals than with finite fields, so the slightly improper terminology "sign bit of y" is still often used colloquially - but generally avoided in standards, to prevent any confusion that might understandably arise from it. 3. Again for Short Weierstrass curves, the additive inverse of the point (x, y) is (x, -y). But of course since y is in GF(p), -y means -y mod p, which (unless y is 0) is actually p-y, again a non-negative number. So if you take two points an a curve that are additive inverses of each other, you can't say that one of them is positive and the other negative, you can just say that one of them has a y coordinate that's odd when represented in the range [0, p) and the other has an even y coordinate. Long story short: - there is no mathematical concept of "being negative" for points on elliptic curves or elements of GF(p) - points on elliptic curves are represented via their coordinates which are elements of GF(p); elements of GF(p) can always represented as non-negative integers in the range [0, p); all standards I know of rely on this representation for on-the-wire formats.

mpg commented

2020-05-18 05:01:15 -05:00

(Migrated from github.com)

Note: I've created an issue to track the bug in mbedtls_asn1_get_mpi(): https://github.com/ARMmbed/mbedtls/issues/3329 - we previously only had an internal ticket about it.

Note: I've created an issue to track the bug in `mbedtls_asn1_get_mpi()`: https://github.com/ARMmbed/mbedtls/issues/3329 - we previously only had an internal ticket about it.

gilles-peskine-arm commented

2020-05-18 05:30:12 -05:00

(Migrated from github.com)

Ah, my bad, I knew but had forgotten that our ASN.1 support does not treat negative numbers correctly.

@moe123 Historically, there was a lot of X.509-related software that assumed that all numbers were positive. I don't know whether the incorrect support of negative numbers mbedtls_asn1_get_mpi was an oversight of this kind, or a deliberate decision for interoperability with software that generates numbers without a leading 0 bit but assumes that they'll be parsed as positive. We've deliberately refrained from changing the behavior so far because it might cause backward compatibility and interoperability problems. We need to do an investigation before we change the behavior.

Until recently ASN.1 didn't have unit tests of its own, and the X.509 unit tests didn't hit many edge cases such as negative numbers. When we added ASN.1 unit tests, we skipped cases of negative numbers where the library behavior currently violates the specification.

Ah, my bad, I knew but had forgotten that our ASN.1 support does not treat negative numbers correctly. @moe123 Historically, there was a lot of X.509-related software that assumed that all numbers were positive. I don't know whether the incorrect support of negative numbers `mbedtls_asn1_get_mpi` was an oversight of this kind, or a deliberate decision for interoperability with software that generates numbers without a leading 0 bit but assumes that they'll be parsed as positive. We've deliberately refrained from changing the behavior so far because it might cause backward compatibility and interoperability problems. We need to do an investigation before we change the behavior. Until recently ASN.1 didn't have unit tests of its own, and the X.509 unit tests didn't hit many edge cases such as negative numbers. When we added ASN.1 unit tests, we skipped cases of negative numbers where the library behavior currently violates the specification.

mu578 commented

2020-05-18 10:41:23 -05:00

(Migrated from github.com)

@mpg then ASN.1 departs from specs; we do not have any involvement with ECDH nor TLS, we deal with ECC, however, it is not related to any of those concerns you iterated. As we previously stated; we cannot make any public statements on what we do or not; 1,2,3 is well know to us; we have negative representations of big-numbers within our set of algorithms; that's it; very happy about that; it involves ECC at some point but certainly not all of it; it's only a partial space projection at T to us; so you know projection, rotation, vector ... manifold and so on.

maxencejded commented

2020-05-18 11:02:52 -05:00

(Migrated from github.com)

@moe123 explain our issue, this is not related with ECDH. Meanwhile, if a big- number (mpi) can be signed; we do expect this behavior to be fully endorsed. I will manage to handle it myself for the time being; if no fix available any time soon. May you keep us updated of any changes regarding this specific API? Thank you for your time and considerations.

👍 1

mpg commented

2020-05-19 02:33:18 -05:00

(Migrated from github.com)

The example code given in the issue description involves ECDH, that's why I mentioned it. I understand it may not be representative of what you're doing as a whole and you can't make more public statements about that.

I agree with Gilles that there is no bug in mbedtls_mpi_read_binary()/mbedtls_mpi_write_binary(): they are working as intended and as their documentation says, so I'm closing this issue.

The bug with the ASN.1 function is tracked in another issue: https://github.com/ARMmbed/mbedtls/issues/3329 and you're welcome to follow that issue if you want to be kept informed.

The example code given in the issue description involves ECDH, that's why I mentioned it. I understand it may not be representative of what you're doing as a whole and you can't make more public statements about that. I agree with Gilles that there is no bug in `mbedtls_mpi_read_binary()`/`mbedtls_mpi_write_binary()`: they are working as intended and as their documentation says, so I'm closing this issue. The bug with the ASN.1 function is tracked in another issue: https://github.com/ARMmbed/mbedtls/issues/3329 and you're welcome to follow that issue if you want to be kept informed.

👎 1

mu578 commented

2020-05-19 11:59:04 -05:00

(Migrated from github.com)

@mpg both are deeply related and interlaced; there is a conceptual design bug running deep thru your API with such inconsistency. If you would just test if the mpi is an absolute value or two complements written, they will not be any issue; indeed, knowing the sign would tell you immediately if in a case of an absolute value expected something is wrong; byte range checking would work too. The ;it's not a bug; it's a feature; narrative is somehow amusing. The first thing when wanting to solve issues properly before moving to a new design; that's to acknowledge them, nobody ever died doing so.

The example code given in the issue description involves ECDH certainly yes; we choose an arbitrary context to demonstrate the issue? nothing abnormal here; however we never talked about such concern only the fact of having at some point mpi being represented as negative values like the inner api states; + we never affirmed that we were using standardized EC representation; meanwhile, we like generalized form; like most of problems you could do without z-plane; imaginary numbers are useless if you go down this road which is very true in essence.

/*
 * Compare unsigned values
 */
int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
{
    size_t i, j;
    MPI_VALIDATE_RET( X != NULL );
    MPI_VALIDATE_RET( Y != NULL );

    for( i = X->n; i > 0; i-- )
        if( X->p[i - 1] != 0 )
            break;

    for( j = Y->n; j > 0; j-- )
        if( Y->p[j - 1] != 0 )
            break;

    if( i == 0 && j == 0 )
        return( 0 );

    if( i > j ) return(  1 );
    if( j > i ) return( -1 );

    for( ; i > 0; i-- )
    {
        if( X->p[i - 1] > Y->p[i - 1] ) return(  1 );
        if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
    }

    return( 0 );
}

/*
 * Compare signed values
 */
int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
{
    size_t i, j;
    MPI_VALIDATE_RET( X != NULL );
    MPI_VALIDATE_RET( Y != NULL );

    for( i = X->n; i > 0; i-- )
        if( X->p[i - 1] != 0 )
            break;

    for( j = Y->n; j > 0; j-- )
        if( Y->p[j - 1] != 0 )
            break;

    if( i == 0 && j == 0 )
        return( 0 );

    if( i > j ) return(  X->s );
    if( j > i ) return( -Y->s );

    if( X->s > 0 && Y->s < 0 ) return(  1 );
    if( Y->s > 0 && X->s < 0 ) return( -1 );

    for( ; i > 0; i-- )
    {
        if( X->p[i - 1] > Y->p[i - 1] ) return(  X->s );
        if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
    }

    return( 0 );
}

@mpg both are deeply related and interlaced; there is a conceptual design bug running deep thru your API with such inconsistency. If you would just test if the mpi is an absolute value or two complements written, they will not be any issue; indeed, knowing the sign would tell you immediately if in a case of an absolute value expected something is wrong; byte range checking would work too. The ;it's not a bug; it's a feature; narrative is somehow amusing. The first thing when wanting to solve issues properly before moving to a new design; that's to acknowledge them, nobody ever died doing so. `The example code given in the issue description involves ECDH` certainly yes; we choose an arbitrary context to demonstrate the issue? nothing abnormal here; however we never talked about such concern only the fact of having at some point mpi being represented as negative values like the inner api states; + we never affirmed that we were using `standardized` EC representation; meanwhile, we like generalized form; like most of problems you could do without z-plane; imaginary numbers are useless if you go down this road which is very true in essence. ``` /* * Compare unsigned values */ int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y ) { size_t i, j; MPI_VALIDATE_RET( X != NULL ); MPI_VALIDATE_RET( Y != NULL ); for( i = X->n; i > 0; i-- ) if( X->p[i - 1] != 0 ) break; for( j = Y->n; j > 0; j-- ) if( Y->p[j - 1] != 0 ) break; if( i == 0 && j == 0 ) return( 0 ); if( i > j ) return( 1 ); if( j > i ) return( -1 ); for( ; i > 0; i-- ) { if( X->p[i - 1] > Y->p[i - 1] ) return( 1 ); if( X->p[i - 1] < Y->p[i - 1] ) return( -1 ); } return( 0 ); } /* * Compare signed values */ int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y ) { size_t i, j; MPI_VALIDATE_RET( X != NULL ); MPI_VALIDATE_RET( Y != NULL ); for( i = X->n; i > 0; i-- ) if( X->p[i - 1] != 0 ) break; for( j = Y->n; j > 0; j-- ) if( Y->p[j - 1] != 0 ) break; if( i == 0 && j == 0 ) return( 0 ); if( i > j ) return( X->s ); if( j > i ) return( -Y->s ); if( X->s > 0 && Y->s < 0 ) return( 1 ); if( Y->s > 0 && X->s < 0 ) return( -1 ); for( ; i > 0; i-- ) { if( X->p[i - 1] > Y->p[i - 1] ) return( X->s ); if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s ); } return( 0 ); } ```

Rows
Columns

[mpi] Sign not restored using write_binary & read_binary #273

Description

Issue request type