Move more of EC compressed coordinate handling to EC_FELEM Decoding compressed coordinates is not supposed to be timing-sensitive, but the WPA3 folks messed up their PAKE the first time around. Implementations are stuck implementing that one, so make the core of the 3 mod 4 mod_sqrt code for EC constant-time. The next CL will use this in IEEE Std 802.11-2020, Section 12.4.4.2.2. Bug: 525105943 Change-Id: I8330dd06fcb90e9ae3e4d91d89000503d4f1f3ce Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/101187 Auto-Submit: David Benjamin <davidben@google.com> Reviewed-by: Lily Chen <chlily@google.com> Commit-Queue: Lily Chen <chlily@google.com> Presubmit-BoringSSL-Verified: boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com <boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com>
diff --git a/crypto/ec/hash_to_curve.cc b/crypto/ec/hash_to_curve.cc index 8fae618..de7c5d8 100644 --- a/crypto/ec/hash_to_curve.cc +++ b/crypto/ec/hash_to_curve.cc
@@ -242,17 +242,13 @@ return buf[len - 1] & 1; } -[[maybe_unused]] static int is_3mod4(const EC_GROUP *group) { - return group->field.N.width > 0 && (group->field.N.d[0] & 3) == 3; -} - // sqrt_ratio_3mod4 implements the operation described in appendix F.2.1.2 // of RFC 9380. BN_ULONG sqrt_ratio_3mod4(const EC_GROUP *group, const EC_FELEM *Z, const BN_ULONG *c1, size_t num_c1, const EC_FELEM *c2, EC_FELEM *out_y, const EC_FELEM *u, const EC_FELEM *v) { - assert(is_3mod4(group)); + assert(group->field_is_3_mod_4); EC_FELEM tv1, tv2, tv3, y1, y2; ec_felem_sqr(group, &tv1, v); // 1. tv1 = v^2 @@ -283,7 +279,7 @@ const EC_FELEM *c2, EC_JACOBIAN *out, const EC_FELEM *u) { // This function requires the prime be 3 mod 4, and that A = -3. - assert(is_3mod4(group)); + assert(group->field_is_3_mod_4); assert(group->a_is_minus3); EC_FELEM tv1, tv2, tv3, tv4, tv5, tv6, x, y, y1;
diff --git a/crypto/fipsmodule/bn/add.cc.inc b/crypto/fipsmodule/bn/add.cc.inc index 5c48e44..6910089 100644 --- a/crypto/fipsmodule/bn/add.cc.inc +++ b/crypto/fipsmodule/bn/add.cc.inc
@@ -25,6 +25,14 @@ using namespace bssl; +BN_ULONG bssl::bn_add_carry_words(BN_ULONG *rp, const BN_ULONG *ap, + BN_ULONG carry, size_t num) { + for (size_t i = 0; i < num; i++) { + rp[i] = CRYPTO_addc_w(ap[i], 0, carry, &carry); + } + return carry; +} + int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b) { const BIGNUM *tmp; int a_neg = a->neg, ret; @@ -77,10 +85,7 @@ r->width = max + 1; BN_ULONG carry = bn_add_words(r->d, a->d, b->d, min); - for (int i = min; i < max; i++) { - r->d[i] = CRYPTO_addc_w(a->d[i], 0, carry, &carry); - } - + carry = bn_add_carry_words(r->d + min, a->d + min, carry, max - min); r->d[max] = carry; return 1; }
diff --git a/crypto/fipsmodule/bn/internal.h b/crypto/fipsmodule/bn/internal.h index 2fa8ebb..9f2729d 100644 --- a/crypto/fipsmodule/bn/internal.h +++ b/crypto/fipsmodule/bn/internal.h
@@ -221,7 +221,6 @@ // are `num` words long. It returns the carry bit, which is one if the operation // overflowed and zero otherwise. Any pair of `ap`, `bp`, and `rp` may be equal // to each other but otherwise may not alias. - #if defined(BN_ADD_ASM) extern "C" #endif @@ -263,6 +262,13 @@ #endif void bn_sqr_comba4(BN_ULONG r[8], const BN_ULONG a[4]); +// bn_add_carry_words adds `carry` to `ap` and places the result in `rp`. `ap` +// and `rp` are `num` words long and may alias. `carry` must be 0 or 1. It +// returns the carry bit, which is one if the operation overflowed and zero +// otherwise. +BN_ULONG bn_add_carry_words(BN_ULONG *rp, const BN_ULONG *ap, BN_ULONG carry, + size_t num); + // bn_less_than_words returns one if `a` < `b` and zero otherwise, where `a` // and `b` both are `len` words long. It runs in constant time. int bn_less_than_words(const BN_ULONG *a, const BN_ULONG *b, size_t len);
diff --git a/crypto/fipsmodule/ec/ec.cc.inc b/crypto/fipsmodule/ec/ec.cc.inc index ae0e12e..cddebc1 100644 --- a/crypto/fipsmodule/ec/ec.cc.inc +++ b/crypto/fipsmodule/ec/ec.cc.inc
@@ -55,7 +55,7 @@ static void ec_group_set_a_minus3(EC_GROUP *group) { const EC_FELEM *one = ec_felem_one(group); - group->a_is_minus3 = 1; + group->a_is_minus3 = true; ec_felem_neg(group, &group->a, one); ec_felem_sub(group, &group->a, &group->a, one); ec_felem_sub(group, &group->a, &group->a, one); @@ -82,8 +82,9 @@ out->generator.group = out; ec_group_set_a_minus3(out); - out->has_order = 1; - out->field_greater_than_order = 1; + out->field_is_3_mod_4 = false; + out->has_order = true; + out->field_greater_than_order = true; } DEFINE_METHOD_FUNCTION(EC_GROUP, EC_group_p256) { @@ -113,8 +114,9 @@ OPENSSL_memcpy(out->b.words, kP256MontB, sizeof(kP256MontB)); ec_group_set_a_minus3(out); - out->has_order = 1; - out->field_greater_than_order = 1; + out->field_is_3_mod_4 = true; + out->has_order = true; + out->field_greater_than_order = true; } DEFINE_METHOD_FUNCTION(EC_GROUP, EC_group_p384) { @@ -138,8 +140,9 @@ OPENSSL_memcpy(out->b.words, kP384MontB, sizeof(kP384MontB)); ec_group_set_a_minus3(out); - out->has_order = 1; - out->field_greater_than_order = 1; + out->field_is_3_mod_4 = true; + out->has_order = true; + out->field_greater_than_order = true; } DEFINE_METHOD_FUNCTION(EC_GROUP, EC_group_p521) { @@ -163,8 +166,9 @@ OPENSSL_memcpy(out->b.words, kP521MontB, sizeof(kP521MontB)); ec_group_set_a_minus3(out); - out->has_order = 1; - out->field_greater_than_order = 1; + out->field_is_3_mod_4 = true; + out->has_order = true; + out->field_greater_than_order = true; } EC_GROUP *EC_GROUP_new_curve_GFp(const BIGNUM *p, const BIGNUM *a, @@ -252,7 +256,7 @@ group->generator.raw.X = affine.X; group->generator.raw.Y = affine.Y; // `raw.Z` was set to 1 by `EC_GROUP_new_curve_GFp`. - group->has_order = 1; + group->has_order = true; return 1; } @@ -548,16 +552,21 @@ return group->meth->jacobian_to_affine_batch(group, out, in, num); } +static void ec_y_sqr_from_x(const EC_GROUP *group, EC_FELEM *out, + const EC_FELEM *x) { + ec_felem_sqr(group, out, x); // out = x^2 + ec_felem_add(group, out, out, &group->a); // out = x^2 + a + ec_felem_mul(group, out, out, x); // out = x^3 + ax + ec_felem_add(group, out, out, &group->b); // out = x^3 + ax + b +} + int bssl::ec_point_set_affine_coordinates(const EC_GROUP *group, EC_AFFINE *out, const EC_FELEM *x, const EC_FELEM *y) { // Check if the point is on the curve. EC_FELEM lhs, rhs; - ec_felem_sqr(group, &lhs, y); // lhs = y^2 - ec_felem_sqr(group, &rhs, x); // rhs = x^2 - ec_felem_add(group, &rhs, &rhs, &group->a); // rhs = x^2 + a - ec_felem_mul(group, &rhs, &rhs, x); // rhs = x^3 + ax - ec_felem_add(group, &rhs, &rhs, &group->b); // rhs = x^3 + ax + b + ec_felem_sqr(group, &lhs, y); // lhs = y^2 + ec_y_sqr_from_x(group, &rhs, x); // rhs = x^3 + ax + b if (!ec_felem_equal(group, &lhs, &rhs)) { OPENSSL_PUT_ERROR(EC, EC_R_POINT_IS_NOT_ON_CURVE); // In the event of an error, defend against the caller not checking the @@ -576,6 +585,29 @@ return 1; } +int bssl::ec_point_set_compressed_coordinates(const EC_GROUP *group, + EC_AFFINE *out, const EC_FELEM *x, + crypto_word_t y_bit) { + EC_FELEM y2, y; + ec_y_sqr_from_x(group, &y2, x); + if (!ec_felem_sqrt(group, &y, &y2, y_bit)) { + OPENSSL_PUT_ERROR(EC, EC_R_POINT_IS_NOT_ON_CURVE); + // In the event of an error, defend against the caller not checking the + // return value by setting a known safe value. Note this may not be possible + // if the caller is in the process of constructing an arbitrary group and + // the generator is missing. + if (group->has_order) { + out->X = group->generator.raw.X; + out->Y = group->generator.raw.Y; + } + return 0; + } + + out->X = *x; + out->Y = y; + 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) { @@ -610,6 +642,28 @@ return EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx); } +int EC_POINT_set_compressed_coordinates_GFp(const EC_GROUP *group, + EC_POINT *point, const BIGNUM *x, + int y_bit, BN_CTX *ctx) { + if (EC_GROUP_cmp(group, point->group, nullptr) != 0) { + OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + + EC_FELEM x_felem; + EC_AFFINE affine; + if (!ec_bignum_to_felem(group, &x_felem, x) || + !ec_point_set_compressed_coordinates(group, &affine, &x_felem, y_bit)) { + // In the event of an error, defend against the caller not checking the + // return value by setting a known safe value. + ec_set_to_safe_point(group, &point->raw); + return 0; + } + + ec_affine_to_jacobian(group, &point->raw, &affine); + return 1; +} + int EC_POINT_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx) { if (EC_GROUP_cmp(group, r->group, nullptr) != 0 ||
diff --git a/crypto/fipsmodule/ec/felem.cc.inc b/crypto/fipsmodule/ec/felem.cc.inc index c634cc1..e99ad0d 100644 --- a/crypto/fipsmodule/ec/felem.cc.inc +++ b/crypto/fipsmodule/ec/felem.cc.inc
@@ -12,6 +12,7 @@ // See the License for the specific language governing permissions and // limitations under the License. +#include <openssl/bn.h> #include <openssl/ec.h> #include <openssl/err.h> #include <openssl/mem.h> @@ -23,15 +24,14 @@ #include "internal.h" -using namespace bssl; +BSSL_NAMESPACE_BEGIN -const EC_FELEM *bssl::ec_felem_one(const EC_GROUP *group) { +const EC_FELEM *ec_felem_one(const EC_GROUP *group) { // We reuse generator.Z as a cache for 1 in the field. return &group->generator.raw.Z; } -int bssl::ec_bignum_to_felem(const EC_GROUP *group, EC_FELEM *out, - const BIGNUM *in) { +int ec_bignum_to_felem(const EC_GROUP *group, EC_FELEM *out, const BIGNUM *in) { uint8_t bytes[EC_MAX_BYTES]; size_t len = BN_num_bytes(&group->field.N); assert(sizeof(bytes) >= len); @@ -44,16 +44,15 @@ return ec_felem_from_bytes(group, out, bytes, len); } -int bssl::ec_felem_to_bignum(const EC_GROUP *group, BIGNUM *out, - const EC_FELEM *in) { +int ec_felem_to_bignum(const EC_GROUP *group, BIGNUM *out, const EC_FELEM *in) { uint8_t bytes[EC_MAX_BYTES]; size_t len; ec_felem_to_bytes(group, bytes, &len, in); return BN_bin2bn(bytes, len, out) != nullptr; } -void bssl::ec_felem_to_bytes(const EC_GROUP *group, uint8_t *out, - size_t *out_len, const EC_FELEM *in) { +void ec_felem_to_bytes(const EC_GROUP *group, uint8_t *out, size_t *out_len, + const EC_FELEM *in) { EC_FELEM tmp; ec_felem_from_montgomery(group, &tmp, in); size_t len = BN_num_bytes(&group->field.N); @@ -61,8 +60,8 @@ *out_len = len; } -int bssl::ec_felem_from_bytes(const EC_GROUP *group, EC_FELEM *out, - const uint8_t *in, size_t len) { +int ec_felem_from_bytes(const EC_GROUP *group, EC_FELEM *out, const uint8_t *in, + size_t len) { if (len != BN_num_bytes(&group->field.N)) { OPENSSL_PUT_ERROR(EC, EC_R_DECODE_ERROR); return 0; @@ -78,8 +77,7 @@ return 1; } -void bssl::ec_felem_neg(const EC_GROUP *group, EC_FELEM *out, - const EC_FELEM *a) { +void ec_felem_neg(const EC_GROUP *group, EC_FELEM *out, const EC_FELEM *a) { // -a is zero if a is zero and p-a otherwise. BN_ULONG mask = ec_felem_non_zero_mask(group, a); BN_ULONG borrow = bn_sub_words(out->words, group->field.N.d, a->words, @@ -91,22 +89,21 @@ } } -void bssl::ec_felem_add(const EC_GROUP *group, EC_FELEM *out, const EC_FELEM *a, - const EC_FELEM *b) { +void ec_felem_add(const EC_GROUP *group, EC_FELEM *out, const EC_FELEM *a, + const EC_FELEM *b) { EC_FELEM tmp; bn_mod_add_words(out->words, a->words, b->words, group->field.N.d, tmp.words, group->field.N.width); } -void bssl::ec_felem_sub(const EC_GROUP *group, EC_FELEM *out, const EC_FELEM *a, - const EC_FELEM *b) { +void ec_felem_sub(const EC_GROUP *group, EC_FELEM *out, const EC_FELEM *a, + const EC_FELEM *b) { EC_FELEM tmp; bn_mod_sub_words(out->words, a->words, b->words, group->field.N.d, tmp.words, group->field.N.width); } -BN_ULONG bssl::ec_felem_non_zero_mask(const EC_GROUP *group, - const EC_FELEM *a) { +BN_ULONG ec_felem_non_zero_mask(const EC_GROUP *group, const EC_FELEM *a) { BN_ULONG mask = 0; for (int i = 0; i < group->field.N.width; i++) { mask |= a->words[i]; @@ -114,43 +111,42 @@ return ~constant_time_is_zero_w(mask); } -void bssl::ec_felem_select(const EC_GROUP *group, EC_FELEM *out, BN_ULONG mask, - const EC_FELEM *a, const EC_FELEM *b) { +void ec_felem_select(const EC_GROUP *group, EC_FELEM *out, BN_ULONG mask, + const EC_FELEM *a, const EC_FELEM *b) { bn_select_words(out->words, mask, a->words, b->words, group->field.N.width); } -int bssl::ec_felem_equal(const EC_GROUP *group, const EC_FELEM *a, - const EC_FELEM *b) { +int ec_felem_equal(const EC_GROUP *group, const EC_FELEM *a, + const EC_FELEM *b) { return CRYPTO_memcmp(a->words, b->words, group->field.N.width * sizeof(BN_ULONG)) == 0; } -void bssl::ec_felem_mul(const EC_GROUP *group, EC_FELEM *out, const EC_FELEM *a, - const EC_FELEM *b) { +void ec_felem_mul(const EC_GROUP *group, EC_FELEM *out, const EC_FELEM *a, + const EC_FELEM *b) { bn_mod_mul_montgomery_small(out->words, a->words, b->words, group->field.N.width, &group->field); } -void bssl::ec_felem_sqr(const EC_GROUP *group, EC_FELEM *out, - const EC_FELEM *a) { +void ec_felem_sqr(const EC_GROUP *group, EC_FELEM *out, const EC_FELEM *a) { bn_mod_mul_montgomery_small(out->words, a->words, a->words, group->field.N.width, &group->field); } -void bssl::ec_felem_to_montgomery(const EC_GROUP *group, EC_FELEM *out, - const EC_FELEM *a) { +void ec_felem_to_montgomery(const EC_GROUP *group, EC_FELEM *out, + const EC_FELEM *a) { bn_to_montgomery_small(out->words, a->words, group->field.N.width, &group->field); } -void bssl::ec_felem_from_montgomery(const EC_GROUP *group, EC_FELEM *out, - const EC_FELEM *a) { +void ec_felem_from_montgomery(const EC_GROUP *group, EC_FELEM *out, + const EC_FELEM *a) { bn_from_montgomery_small(out->words, group->field.N.width, a->words, group->field.N.width, &group->field); } -void bssl::ec_felem_reduce(const EC_GROUP *group, EC_FELEM *out, - const BN_ULONG *words, size_t num) { +void ec_felem_reduce(const EC_GROUP *group, EC_FELEM *out, + const BN_ULONG *words, size_t num) { // Convert "from" Montgomery form so the value is reduced mod p. bn_from_montgomery_small(out->words, group->field.N.width, words, num, &group->field); @@ -160,8 +156,77 @@ ec_felem_to_montgomery(group, out, out); } -void bssl::ec_felem_exp(const EC_GROUP *group, EC_FELEM *out, const EC_FELEM *a, - const BN_ULONG *exp, size_t num_exp) { +void ec_felem_exp(const EC_GROUP *group, EC_FELEM *out, const EC_FELEM *a, + const BN_ULONG *exp, size_t num_exp) { bn_mod_exp_mont_small(out->words, a->words, group->field.N.width, exp, num_exp, &group->field); } + +// adjust_y negates `y` if its LSB (when converted out of Montgomery form) was +// not `y_bit`. +static void adjust_y(const EC_GROUP *group, EC_FELEM *y, crypto_word_t y_bit) { + EC_FELEM y_from_mont, neg_y; + // `y` is stored in the Montgomery domain. Convert back out to sample the LSB. + ec_felem_from_montgomery(group, &y_from_mont, y); + BN_ULONG lsb_mismatch = (y_bit ^ y_from_mont.words[0]) & 1; + lsb_mismatch = 0u - lsb_mismatch; // All ones or all zeros. + ec_felem_neg(group, &neg_y, y); + ec_felem_select(group, y, lsb_mismatch, &neg_y, y); +} + +int ec_felem_sqrt(const EC_GROUP *group, EC_FELEM *out, const EC_FELEM *a, + crypto_word_t y_bit) { + if (group->field_is_3_mod_4) { + if (!ec_felem_sqrt_secret(group, out, a, y_bit)) { + OPENSSL_PUT_ERROR(EC, EC_R_INVALID_COMPRESSED_POINT); + return 0; + } + return 1; + } + + // Curves that are not 3 mod 4 are messy to implement modular square root. For + // now, fall back to BIGNUM. This case comes up for P-224 and custom curves. + // P-224's prime is particularly inconvenient for compressed coordinates. See + // https://cr.yp.to/papers/sqroot.pdf + UniquePtr<BN_CTX> ctx(BN_CTX_new()); + UniquePtr<BIGNUM> bn(BN_new()); + if (ctx == nullptr || bn == nullptr || + !ec_felem_to_bignum(group, bn.get(), a)) { + return 0; + } + + UniquePtr<BIGNUM> sqrt( + BN_mod_sqrt(nullptr, bn.get(), &group->field.N, ctx.get())); + if (sqrt == nullptr || !ec_bignum_to_felem(group, out, sqrt.get())) { + return 0; + } + + adjust_y(group, out, y_bit); + return 1; +} + +crypto_word_t ec_felem_sqrt_secret(const EC_GROUP *group, EC_FELEM *out, + const EC_FELEM *a, crypto_word_t y_bit) { + BSSL_CHECK(group->field_is_3_mod_4); + + // If `a` is a square, then a^(p+1)/4 is a square root. By Euler's criterion, + // a^(p-1)/2 = 1 for squares, so a^(p+1)/2 = a. p is 3 mod 4, so that exponent + // is even, so we can halve it to find a square root. + const size_t num_exp = group->field.N.width; + BN_ULONG exp[EC_MAX_WORDS]; + bn_rshift_words(exp, group->field.N.d, 2, num_exp); // exp = (p-3)/4 + bn_add_carry_words(exp, exp, /*carry=*/1, num_exp); // exp = (p+1)/4 + ec_felem_exp(group, out, a, exp, num_exp); // out = sqrt(a) + + // Pick the correct (possible) square root. + adjust_y(group, out, y_bit); + + // Check `out^2 = a`. If `a` had a square root, `out` must be one and the + // check will pass. If not, the check cannot pass. + EC_FELEM check; + ec_felem_sqr(group, &check, out); // check = out^2 + ec_felem_sub(group, &check, &check, a); // check = out^2 - a + return ~ec_felem_non_zero_mask(group, &check); +} + +BSSL_NAMESPACE_END
diff --git a/crypto/fipsmodule/ec/internal.h b/crypto/fipsmodule/ec/internal.h index 2261f20..c699001 100644 --- a/crypto/fipsmodule/ec/internal.h +++ b/crypto/fipsmodule/ec/internal.h
@@ -228,6 +228,23 @@ void ec_felem_exp(const EC_GROUP *group, EC_FELEM *out, const EC_FELEM *a, const BN_ULONG *exp, size_t num_exp); +// ec_felem_sqrt sets `out` to the square root of `a` whose least significant +// bit is `y_bit`. It returns one on success and zero on error or if `a` is not +// a square. +int ec_felem_sqrt(const EC_GROUP *group, EC_FELEM *out, const EC_FELEM *a, + crypto_word_t y_bit); + +// ec_felem_sqrt_secret sets `out` to the square root of `a` whose least +// significant bit is `y_bit`. It returns `CONSTTIME_TRUE_W` on success and +// `CONSTTIME_FALSE_W` if `a` is not a square. +// +// This function treats `a`, `y_bit`, and whether `a` is a square, as secret. If +// `a` is not a square, `out` will be set to some arbitrary field element. This +// function is only implemented for curves whose field is 3 mod 4. (In +// particular, it is *not* implemented for P-224.) It aborts on invalid group. +crypto_word_t ec_felem_sqrt_secret(const EC_GROUP *group, EC_FELEM *out, + const EC_FELEM *a, crypto_word_t y_bit); + // Points. // @@ -280,13 +297,19 @@ int ec_jacobian_to_affine_batch(const EC_GROUP *group, EC_AFFINE *out, const EC_JACOBIAN *in, size_t num); -// 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. +// ec_point_set_affine_coordinates sets `out` 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_AFFINE *out, const EC_FELEM *x, const EC_FELEM *y); +// ec_point_set_compressed_coordinates sets `out` to a point with compressed +// coordinates `x` and `y_bit`. 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_compressed_coordinates(const EC_GROUP *group, EC_AFFINE *out, + const EC_FELEM *x, crypto_word_t y_bit); + // ec_point_mul_no_self_test does the same as `EC_POINT_mul`, but doesn't try to // run the self-test first. This is for use in the self tests themselves, to // prevent an infinite loop. @@ -440,11 +463,17 @@ size_t max_out); // 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 +// sets `out` to the result. It returns one on success and zero if the input was // invalid. int ec_point_from_uncompressed(const EC_GROUP *group, EC_AFFINE *out, const uint8_t *in, size_t len); +// ec_point_from_compressed parses `in` as a point in compressed form and sets +// `out` to the result`. It returns one on success and zero if the input was +// invalid. +int ec_point_from_compressed(const EC_GROUP *group, EC_AFFINE *out, + const uint8_t *in, size_t len); + // ec_set_to_safe_point sets `out` to an arbitrary point on `group`, either the // generator or the point at infinity. This is used to guard against callers of // external APIs not checking the return value. @@ -578,16 +607,18 @@ uint8_t oid[9]; uint8_t oid_len; - // a_is_minus3 is one if `a` is -3 mod `field` and zero otherwise. Point - // arithmetic is optimized for -3. - int a_is_minus3; + // a_is_minus3 is whether `a` is -3 mod `field`. Point arithmetic is optimized + // for -3. + bool a_is_minus3; - // has_order is one if `generator` and `order` have been initialized. - int has_order; + // field_is_3_mod_4 is whether `field` is 3 mod 4. + bool field_is_3_mod_4; - // field_greater_than_order is one if `field` is greater than `order` and zero - // otherwise. - int field_greater_than_order; + // has_order is whether `generator` and `order` have been initialized. + bool has_order; + + // field_greater_than_order is whether `field` is greater than `order`. + bool field_greater_than_order; } /* EC_GROUP */; BSSL_NAMESPACE_BEGIN
diff --git a/crypto/fipsmodule/ec/oct.cc.inc b/crypto/fipsmodule/ec/oct.cc.inc index eb33277..04350c5 100644 --- a/crypto/fipsmodule/ec/oct.cc.inc +++ b/crypto/fipsmodule/ec/oct.cc.inc
@@ -69,19 +69,31 @@ int bssl::ec_point_from_uncompressed(const EC_GROUP *group, EC_AFFINE *out, const uint8_t *in, size_t len) { const size_t field_len = BN_num_bytes(&group->field.N); - if (len != 1 + 2 * field_len || in[0] != POINT_CONVERSION_UNCOMPRESSED) { + if (len != 1 /* form */ + 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 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); +} + +int bssl::ec_point_from_compressed(const EC_GROUP *group, EC_AFFINE *out, + const uint8_t *in, size_t len) { + const size_t field_len = BN_num_bytes(&group->field.N); + if (len != 1 /* form */ + field_len || + (in[0] & ~1u) != POINT_CONVERSION_COMPRESSED) { + OPENSSL_PUT_ERROR(EC, EC_R_INVALID_ENCODING); return 0; } - return 1; + crypto_word_t y_bit = in[0] & 1; + EC_FELEM x; + return ec_felem_from_bytes(group, &x, in + 1, field_len) && + ec_point_set_compressed_coordinates(group, out, &x, y_bit); } static int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point, @@ -92,56 +104,18 @@ return 0; } - uint8_t form = buf[0]; - if (form == static_cast<uint8_t>(POINT_CONVERSION_UNCOMPRESSED)) { - EC_AFFINE affine; - if (!ec_point_from_uncompressed(group, &affine, buf, len)) { - // In the event of an error, defend against the caller not checking the - // return value by setting a known safe value. - ec_set_to_safe_point(group, &point->raw); - return 0; - } - ec_affine_to_jacobian(group, &point->raw, &affine); - return 1; - } - - const int y_bit = form & 1; - const size_t field_len = BN_num_bytes(&group->field.N); - form = form & ~1u; - if (form != static_cast<uint8_t>(POINT_CONVERSION_COMPRESSED) || - len != 1 /* type byte */ + field_len) { - OPENSSL_PUT_ERROR(EC, EC_R_INVALID_ENCODING); + const uint8_t form = buf[0]; + EC_AFFINE affine; + bool ok = form == static_cast<uint8_t>(POINT_CONVERSION_UNCOMPRESSED) + ? ec_point_from_uncompressed(group, &affine, buf, len) + : ec_point_from_compressed(group, &affine, buf, len); + if (!ok) { + // In the event of an error, defend against the caller not checking the + // return value by setting a known safe value. + ec_set_to_safe_point(group, &point->raw); return 0; } - - // TODO(davidben): Integrate compressed coordinates with the lower-level EC - // abstractions. This requires a way to compute square roots, which is tricky - // for primes which are not 3 (mod 4), namely P-224 and custom curves. P-224's - // prime is particularly inconvenient for compressed coordinates. See - // https://cr.yp.to/papers/sqroot.pdf - UniquePtr<BN_CTX> new_ctx; - if (ctx == nullptr) { - new_ctx.reset(BN_CTX_new()); - if (new_ctx == nullptr) { - return 0; - } - ctx = new_ctx.get(); - } - - BN_CTXScope scope(ctx); - BIGNUM *x = BN_CTX_get(ctx); - if (x == nullptr || !BN_bin2bn(buf + 1, field_len, x)) { - return 0; - } - if (BN_ucmp(x, &group->field.N) >= 0) { - OPENSSL_PUT_ERROR(EC, EC_R_INVALID_ENCODING); - return 0; - } - - if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) { - return 0; - } - + ec_affine_to_jacobian(group, &point->raw, &affine); return 1; } @@ -197,100 +171,3 @@ *out_buf = buf; return len; } - -int EC_POINT_set_compressed_coordinates_GFp(const EC_GROUP *group, - EC_POINT *point, const BIGNUM *x, - int y_bit, BN_CTX *ctx) { - if (EC_GROUP_cmp(group, point->group, nullptr) != 0) { - OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS); - return 0; - } - - const BIGNUM *field = &group->field.N; - if (BN_is_negative(x) || BN_cmp(x, field) >= 0) { - OPENSSL_PUT_ERROR(EC, EC_R_INVALID_COMPRESSED_POINT); - return 0; - } - - ERR_clear_error(); - - UniquePtr<BN_CTX> new_ctx; - if (ctx == nullptr) { - new_ctx.reset(BN_CTX_new()); - if (new_ctx == nullptr) { - return 0; - } - ctx = new_ctx.get(); - } - - y_bit = (y_bit != 0); - - BN_CTXScope scope(ctx); - BIGNUM *tmp1 = BN_CTX_get(ctx); - BIGNUM *tmp2 = BN_CTX_get(ctx); - BIGNUM *a = BN_CTX_get(ctx); - BIGNUM *b = BN_CTX_get(ctx); - BIGNUM *y = BN_CTX_get(ctx); - if (y == nullptr || !EC_GROUP_get_curve_GFp(group, nullptr, a, b, ctx)) { - return 0; - } - - // Recover y. We have a Weierstrass equation - // y^2 = x^3 + a*x + b, - // so y is one of the square roots of x^3 + a*x + b. - - // tmp1 := x^3 - if (!BN_mod_sqr(tmp2, x, field, ctx) || - !BN_mod_mul(tmp1, tmp2, x, field, ctx)) { - return 0; - } - - // tmp1 := tmp1 + a*x - if (group->a_is_minus3) { - if (!bn_mod_lshift1_consttime(tmp2, x, field, ctx) || - !bn_mod_add_consttime(tmp2, tmp2, x, field, ctx) || - !bn_mod_sub_consttime(tmp1, tmp1, tmp2, field, ctx)) { - return 0; - } - } else { - if (!BN_mod_mul(tmp2, a, x, field, ctx) || - !bn_mod_add_consttime(tmp1, tmp1, tmp2, field, ctx)) { - return 0; - } - } - - // tmp1 := tmp1 + b - if (!bn_mod_add_consttime(tmp1, tmp1, b, field, ctx)) { - return 0; - } - - if (!BN_mod_sqrt(y, tmp1, field, ctx)) { - if (ERR_equals(ERR_peek_last_error(), ERR_LIB_BN, BN_R_NOT_A_SQUARE)) { - ERR_clear_error(); - OPENSSL_PUT_ERROR(EC, EC_R_INVALID_COMPRESSED_POINT); - } else { - OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); - } - return 0; - } - - if (y_bit != BN_is_odd(y)) { - if (BN_is_zero(y)) { - OPENSSL_PUT_ERROR(EC, EC_R_INVALID_COMPRESSION_BIT); - return 0; - } - if (!BN_usub(y, field, y)) { - return 0; - } - } - if (y_bit != BN_is_odd(y)) { - OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR); - return 0; - } - - if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) { - return 0; - } - - return 1; -}
diff --git a/crypto/fipsmodule/ec/simple.cc.inc b/crypto/fipsmodule/ec/simple.cc.inc index 3095ef7..398f6ca 100644 --- a/crypto/fipsmodule/ec/simple.cc.inc +++ b/crypto/fipsmodule/ec/simple.cc.inc
@@ -64,12 +64,11 @@ return 0; } - // group->a_is_minus3 - if (!BN_copy(tmp, a) || - !BN_add_word(tmp, 3)) { + if (!BN_copy(tmp, a) || !BN_add_word(tmp, 3)) { return 0; } group->a_is_minus3 = (0 == BN_cmp(tmp, &group->field.N)); + group->field_is_3_mod_4 = (group->field.N.d[0] & 3) == 3; return 1; }