Remove BIGNUM from uncompressed coordinate parsing.
Compressed coordinates still use BIGNUM. I've moved the curve check to
an EC_FELEM-based ec_point_set_affine_coordinates and implemented a
tighter one than ec_GFp_simple_is_on_curve, which currently needs to
branch on Jacobian vs. affine and potentially leaks information. (A
later CL will make it conservatively always perform a Jacobian check.)
The Trust Tokens implementation will eventually need to deserialize
points, so this avoids needing to allocate EC_POINTs everywhere.
Likewise if we ever get around to adding a better ECDH, this will let us
avoid pulling in BIGNUMs.
Bug: chromium:1014199, 242
Change-Id: I93162ba3680d38cb3c0eacff1eb8f42a445246ea
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/40587
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/ec/ec.c b/crypto/fipsmodule/ec/ec.c
index d32ac7e..2fa1676 100644
--- a/crypto/fipsmodule/ec/ec.c
+++ b/crypto/fipsmodule/ec/ec.c
@@ -811,6 +811,42 @@
return 1;
}
+int ec_point_set_affine_coordinates(const EC_GROUP *group, EC_RAW_POINT *out,
+ const EC_FELEM *x, const EC_FELEM *y) {
+ void (*const felem_mul)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a,
+ const EC_FELEM *b) = group->meth->felem_mul;
+ void (*const felem_sqr)(const EC_GROUP *, EC_FELEM *r, const EC_FELEM *a) =
+ group->meth->felem_sqr;
+
+ // Check if the point is on the curve.
+ EC_FELEM lhs, rhs;
+ felem_sqr(group, &lhs, y); // lhs = y^2
+ felem_sqr(group, &rhs, x); // rhs = x^2
+ ec_felem_add(group, &rhs, &rhs, &group->a); // rhs = x^2 + a
+ felem_mul(group, &rhs, &rhs, x); // rhs = x^3 + ax
+ ec_felem_add(group, &rhs, &rhs, &group->b); // rhs = x^3 + ax + b
+ if (!ec_felem_equal(group, &lhs, &rhs)) {
+ // In the event of an error, defend against the caller not checking the
+ // return value by setting a known safe value: the base point.
+ const EC_POINT *generator = EC_GROUP_get0_generator(group);
+ if (generator) {
+ ec_GFp_simple_point_copy(out, &generator->raw);
+ } else {
+ // The generator can be missing if the caller is in the process of
+ // constructing an arbitrary group. In this case, we give up and use the
+ // point at infinity.
+ ec_GFp_simple_point_set_to_infinity(group, out);
+ }
+ OPENSSL_PUT_ERROR(EC, EC_R_POINT_IS_NOT_ON_CURVE);
+ return 0;
+ }
+
+ out->X = *x;
+ out->Y = *y;
+ out->Z = group->one;
+ return 1;
+}
+
int EC_POINT_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
const BIGNUM *x, const BIGNUM *y,
BN_CTX *ctx) {
@@ -818,21 +854,17 @@
OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS);
return 0;
}
- if (!ec_GFp_simple_point_set_affine_coordinates(group, &point->raw, x, y)) {
+
+ if (x == NULL || y == NULL) {
+ OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER);
return 0;
}
- if (!EC_POINT_is_on_curve(group, point, ctx)) {
- // In the event of an error, defend against the caller not checking the
- // return value by setting a known safe value: the base point.
- const EC_POINT *generator = EC_GROUP_get0_generator(group);
- // The generator can be missing if the caller is in the process of
- // constructing an arbitrary group. In this, we give up and hope they're
- // checking the return value.
- if (generator) {
- ec_GFp_simple_point_copy(&point->raw, &generator->raw);
- }
- OPENSSL_PUT_ERROR(EC, EC_R_POINT_IS_NOT_ON_CURVE);
+ EC_FELEM x_felem, y_felem;
+ if (!ec_bignum_to_felem(group, &x_felem, x) ||
+ !ec_bignum_to_felem(group, &y_felem, y) ||
+ !ec_point_set_affine_coordinates(group, &point->raw, &x_felem,
+ &y_felem)) {
return 0;
}
diff --git a/crypto/fipsmodule/ec/internal.h b/crypto/fipsmodule/ec/internal.h
index 2ac8b83..e3f2156 100644
--- a/crypto/fipsmodule/ec/internal.h
+++ b/crypto/fipsmodule/ec/internal.h
@@ -234,6 +234,13 @@
// (X/Z^2, Y/Z^3) if Z != 0 and the point at infinity otherwise.
} EC_RAW_POINT;
+// ec_point_set_affine_coordinates sets |out|'s to a point with affine
+// coordinates |x| and |y|. It returns one if the point is on the curve and
+// zero otherwise. If the point is not on the curve, the value of |out| is
+// undefined.
+int ec_point_set_affine_coordinates(const EC_GROUP *group, EC_RAW_POINT *out,
+ const EC_FELEM *x, const EC_FELEM *y);
+
// ec_point_mul_scalar sets |r| to |p| * |scalar|. Both inputs are considered
// secret.
int ec_point_mul_scalar(const EC_GROUP *group, EC_RAW_POINT *r,
@@ -282,6 +289,12 @@
point_conversion_form_t form, uint8_t *buf,
size_t len);
+// ec_point_from_uncompressed parses |in| as a point in uncompressed form and
+// sets the result to |out|. It returns one on success and zero if the input was
+// invalid.
+int ec_point_from_uncompressed(const EC_GROUP *group, EC_RAW_POINT *out,
+ const uint8_t *in, size_t len);
+
// Implementation details.
@@ -441,9 +454,6 @@
void ec_GFp_simple_point_init(EC_RAW_POINT *);
void ec_GFp_simple_point_copy(EC_RAW_POINT *, const EC_RAW_POINT *);
void ec_GFp_simple_point_set_to_infinity(const EC_GROUP *, EC_RAW_POINT *);
-int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *, EC_RAW_POINT *,
- const BIGNUM *x,
- const BIGNUM *y);
void ec_GFp_mont_add(const EC_GROUP *, EC_RAW_POINT *r, const EC_RAW_POINT *a,
const EC_RAW_POINT *b);
void ec_GFp_mont_dbl(const EC_GROUP *, EC_RAW_POINT *r, const EC_RAW_POINT *a);
diff --git a/crypto/fipsmodule/ec/oct.c b/crypto/fipsmodule/ec/oct.c
index e8a98a7..a2a0fc8 100644
--- a/crypto/fipsmodule/ec/oct.c
+++ b/crypto/fipsmodule/ec/oct.c
@@ -125,55 +125,58 @@
return output_len;
}
+int ec_point_from_uncompressed(const EC_GROUP *group, EC_RAW_POINT *out,
+ const uint8_t *in, size_t len) {
+ const size_t field_len = BN_num_bytes(&group->field);
+ if (len != 1 + 2 * field_len || in[0] != POINT_CONVERSION_UNCOMPRESSED) {
+ OPENSSL_PUT_ERROR(EC, EC_R_INVALID_ENCODING);
+ return 0;
+ }
+
+ EC_FELEM x, y;
+ if (!ec_felem_from_bytes(group, &x, in + 1, field_len) ||
+ !ec_felem_from_bytes(group, &y, in + 1 + field_len, field_len) ||
+ !ec_point_set_affine_coordinates(group, out, &x, &y)) {
+ return 0;
+ }
+
+ return 1;
+}
+
static int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
const uint8_t *buf, size_t len,
BN_CTX *ctx) {
- BN_CTX *new_ctx = NULL;
- int ret = 0, used_ctx = 0;
-
if (len == 0) {
OPENSSL_PUT_ERROR(EC, EC_R_BUFFER_TOO_SMALL);
- goto err;
+ return 0;
}
point_conversion_form_t form = buf[0];
- const int y_bit = form & 1;
- form = form & ~1U;
- if ((form != POINT_CONVERSION_COMPRESSED &&
- form != POINT_CONVERSION_UNCOMPRESSED) ||
- (form == POINT_CONVERSION_UNCOMPRESSED && y_bit)) {
- OPENSSL_PUT_ERROR(EC, EC_R_INVALID_ENCODING);
- goto err;
- }
-
- const size_t field_len = BN_num_bytes(&group->field);
- size_t enc_len = 1 /* type byte */ + field_len;
if (form == POINT_CONVERSION_UNCOMPRESSED) {
- // Uncompressed points have a second coordinate.
- enc_len += field_len;
+ return ec_point_from_uncompressed(group, &point->raw, buf, len);
}
- if (len != enc_len) {
+ const int y_bit = form & 1;
+ const size_t field_len = BN_num_bytes(&group->field);
+ form = form & ~1u;
+ if (form != POINT_CONVERSION_COMPRESSED ||
+ len != 1 /* type byte */ + field_len) {
OPENSSL_PUT_ERROR(EC, EC_R_INVALID_ENCODING);
- goto err;
+ return 0;
}
+ BN_CTX *new_ctx = NULL;
if (ctx == NULL) {
ctx = new_ctx = BN_CTX_new();
if (ctx == NULL) {
- goto err;
+ return 0;
}
}
+ int ret = 0;
BN_CTX_start(ctx);
- used_ctx = 1;
BIGNUM *x = BN_CTX_get(ctx);
- BIGNUM *y = BN_CTX_get(ctx);
- if (x == NULL || y == NULL) {
- goto err;
- }
-
- if (!BN_bin2bn(buf + 1, field_len, x)) {
+ if (x == NULL || !BN_bin2bn(buf + 1, field_len, x)) {
goto err;
}
if (BN_ucmp(x, &group->field) >= 0) {
@@ -181,30 +184,14 @@
goto err;
}
- if (form == POINT_CONVERSION_COMPRESSED) {
- if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) {
- goto err;
- }
- } else {
- if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) {
- goto err;
- }
- if (BN_ucmp(y, &group->field) >= 0) {
- OPENSSL_PUT_ERROR(EC, EC_R_INVALID_ENCODING);
- goto err;
- }
-
- if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) {
- goto err;
- }
+ if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) {
+ goto err;
}
ret = 1;
err:
- if (used_ctx) {
- BN_CTX_end(ctx);
- }
+ BN_CTX_end(ctx);
BN_CTX_free(new_ctx);
return ret;
}
diff --git a/crypto/fipsmodule/ec/simple.c b/crypto/fipsmodule/ec/simple.c
index fe8386f..19e9ad5 100644
--- a/crypto/fipsmodule/ec/simple.c
+++ b/crypto/fipsmodule/ec/simple.c
@@ -171,24 +171,6 @@
ec_GFp_simple_point_init(point);
}
-int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group,
- EC_RAW_POINT *point,
- const BIGNUM *x,
- const BIGNUM *y) {
- if (x == NULL || y == NULL) {
- OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER);
- return 0;
- }
-
- if (!ec_bignum_to_felem(group, &point->X, x) ||
- !ec_bignum_to_felem(group, &point->Y, y)) {
- return 0;
- }
- OPENSSL_memcpy(&point->Z, &group->one, sizeof(EC_FELEM));
-
- return 1;
-}
-
void ec_GFp_simple_invert(const EC_GROUP *group, EC_RAW_POINT *point) {
ec_felem_neg(group, &point->Y, &point->Y);
}
