Remove |EC_POINT::Z_is_one|. Having |Z_is_one| be out of sync with |Z| could potentially be a very bad thing, and in the past there have been multiple bugs of this sort, including one currently in p256-x86_64.c (type confusion: Montgomery- encoded vs unencoded). Avoid the issue entirely by getting rid of |Z_is_one|. Change-Id: Icb5aa0342df41d6bc443f15f952734295d0ee4ba Reviewed-on: https://boringssl-review.googlesource.com/6576 Reviewed-by: David Benjamin <davidben@google.com>
diff --git a/crypto/ec/ec_montgomery.c b/crypto/ec/ec_montgomery.c index 62b0d7f..9524323 100644 --- a/crypto/ec/ec_montgomery.c +++ b/crypto/ec/ec_montgomery.c
@@ -79,23 +79,18 @@ ok = ec_GFp_simple_group_init(group); group->mont = NULL; - group->one = NULL; return ok; } void ec_GFp_mont_group_finish(EC_GROUP *group) { BN_MONT_CTX_free(group->mont); group->mont = NULL; - BN_free(group->one); - group->one = NULL; ec_GFp_simple_group_finish(group); } int ec_GFp_mont_group_copy(EC_GROUP *dest, const EC_GROUP *src) { BN_MONT_CTX_free(dest->mont); dest->mont = NULL; - BN_clear_free(dest->one); - dest->one = NULL; if (!ec_GFp_simple_group_copy(dest, src)) { return 0; @@ -110,12 +105,6 @@ goto err; } } - if (src->one != NULL) { - dest->one = BN_dup(src->one); - if (dest->one == NULL) { - goto err; - } - } return 1; @@ -129,13 +118,10 @@ const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { BN_CTX *new_ctx = NULL; BN_MONT_CTX *mont = NULL; - BIGNUM *one = NULL; int ret = 0; BN_MONT_CTX_free(group->mont); group->mont = NULL; - BN_free(group->one); - group->one = NULL; if (ctx == NULL) { ctx = new_ctx = BN_CTX_new(); @@ -152,29 +138,20 @@ OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); goto err; } - one = BN_new(); - if (one == NULL || !BN_to_montgomery(one, BN_value_one(), mont, ctx)) { - goto err; - } group->mont = mont; mont = NULL; - group->one = one; - one = NULL; ret = ec_GFp_simple_group_set_curve(group, p, a, b, ctx); if (!ret) { BN_MONT_CTX_free(group->mont); group->mont = NULL; - BN_free(group->one); - group->one = NULL; } err: BN_CTX_free(new_ctx); BN_MONT_CTX_free(mont); - BN_free(one); return ret; } @@ -218,19 +195,6 @@ return BN_from_montgomery(r, a, group->mont, ctx); } -int ec_GFp_mont_field_set_to_one(const EC_GROUP *group, BIGNUM *r, - BN_CTX *ctx) { - if (group->one == NULL) { - OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED); - return 0; - } - - if (!BN_copy(r, group->one)) { - return 0; - } - return 1; -} - static int ec_GFp_mont_check_pub_key_order(const EC_GROUP *group, const EC_POINT* pub_key, BN_CTX *ctx) { @@ -264,7 +228,6 @@ ec_GFp_mont_field_sqr, ec_GFp_mont_field_encode, ec_GFp_mont_field_decode, - ec_GFp_mont_field_set_to_one, }; return &ret;
diff --git a/crypto/ec/internal.h b/crypto/ec/internal.h index 2b788c1..240d24f 100644 --- a/crypto/ec/internal.h +++ b/crypto/ec/internal.h
@@ -116,7 +116,6 @@ BN_CTX *); /* e.g. to Montgomery */ int (*field_decode)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); /* e.g. from Montgomery */ - int (*field_set_to_one)(const EC_GROUP *, BIGNUM *r, BN_CTX *); } /* EC_METHOD */; const EC_METHOD* EC_GFp_mont_method(void); @@ -141,7 +140,8 @@ int a_is_minus3; /* enable optimized point arithmetics for special case */ BN_MONT_CTX *mont; /* Montgomery structure. */ - BIGNUM *one; /* The value one */ + + BIGNUM one; /* The value one. */ } /* EC_GROUP */; struct ec_point_st { @@ -151,7 +151,6 @@ BIGNUM Y; BIGNUM Z; /* Jacobian projective coordinates: * (X, Y, Z) represents (X/Z^2, Y/Z^3) if Z != 0 */ - int Z_is_one; /* enable optimized point arithmetics for special case */ } /* EC_POINT */; EC_GROUP *ec_group_new(const EC_METHOD *meth); @@ -227,7 +226,6 @@ BN_CTX *); int ec_GFp_mont_field_decode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); -int ec_GFp_mont_field_set_to_one(const EC_GROUP *, BIGNUM *r, BN_CTX *); int ec_point_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point, const BIGNUM *x,
diff --git a/crypto/ec/p224-64.c b/crypto/ec/p224-64.c index 9de6cd4..dac20e0 100644 --- a/crypto/ec/p224-64.c +++ b/crypto/ec/p224-64.c
@@ -1235,8 +1235,7 @@ ec_GFp_simple_field_mul, ec_GFp_simple_field_sqr, 0 /* field_encode */, - 0 /* field_decode */, - 0 /* field_set_to_one */}; + 0 /* field_decode */}; return &ret; }
diff --git a/crypto/ec/p256-64.c b/crypto/ec/p256-64.c index b94e226..629c0c3 100644 --- a/crypto/ec/p256-64.c +++ b/crypto/ec/p256-64.c
@@ -1807,7 +1807,7 @@ ec_GFp_nistp256_points_mul, 0 /* check_pub_key_order */, ec_GFp_simple_field_mul, ec_GFp_simple_field_sqr, - 0 /* field_encode */, 0 /* field_decode */, 0 /* field_set_to_one */ + 0 /* field_encode */, 0 /* field_decode */, }; return &ret;
diff --git a/crypto/ec/p256-x86_64.c b/crypto/ec/p256-x86_64.c index ca967b3..acbf455 100644 --- a/crypto/ec/p256-x86_64.c +++ b/crypto/ec/p256-x86_64.c
@@ -502,7 +502,6 @@ bn_correct_top(&r->X); bn_correct_top(&r->Y); bn_correct_top(&r->Z); - r->Z_is_one = BN_is_one(&r->Z); ret = 1; @@ -576,7 +575,6 @@ ec_GFp_mont_field_sqr, ec_GFp_mont_field_encode, ec_GFp_mont_field_decode, - ec_GFp_mont_field_set_to_one, }; return &ret;
diff --git a/crypto/ec/simple.c b/crypto/ec/simple.c index fc8d1d8..1f35388 100644 --- a/crypto/ec/simple.c +++ b/crypto/ec/simple.c
@@ -92,6 +92,7 @@ BN_init(&group->field); BN_init(&group->a); BN_init(&group->b); + BN_init(&group->one); group->a_is_minus3 = 0; return 1; } @@ -100,12 +101,14 @@ BN_free(&group->field); BN_free(&group->a); BN_free(&group->b); + BN_free(&group->one); } int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) { if (!BN_copy(&dest->field, &src->field) || !BN_copy(&dest->a, &src->a) || - !BN_copy(&dest->b, &src->b)) { + !BN_copy(&dest->b, &src->b) || + !BN_copy(&dest->one, &src->one)) { return 0; } @@ -172,6 +175,14 @@ } group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field)); + if (group->meth->field_encode != NULL) { + if (!group->meth->field_encode(group, &group->one, BN_value_one(), ctx)) { + goto err; + } + } else if (!BN_copy(&group->one, BN_value_one())) { + goto err; + } + ret = 1; err: @@ -228,7 +239,6 @@ BN_init(&point->X); BN_init(&point->Y); BN_init(&point->Z); - point->Z_is_one = 0; return 1; } @@ -243,7 +253,6 @@ BN_clear_free(&point->X); BN_clear_free(&point->Y); BN_clear_free(&point->Z); - point->Z_is_one = 0; } int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src) { @@ -252,14 +261,12 @@ !BN_copy(&dest->Z, &src->Z)) { return 0; } - dest->Z_is_one = src->Z_is_one; return 1; } int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point) { - point->Z_is_one = 0; BN_zero(&point->Z); return 1; } @@ -298,22 +305,19 @@ } if (z != NULL) { - int Z_is_one; - if (!BN_nnmod(&point->Z, z, &group->field, ctx)) { goto err; } - Z_is_one = BN_is_one(&point->Z); + int Z_is_one = BN_is_one(&point->Z); if (group->meth->field_encode) { - if (Z_is_one && (group->meth->field_set_to_one != 0)) { - if (!group->meth->field_set_to_one(group, &point->Z, ctx)) { + if (Z_is_one) { + if (BN_copy(&point->Z, &group->one) == NULL) { goto err; } } else if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) { goto err; } } - point->Z_is_one = Z_is_one; } ret = 1; @@ -531,7 +535,9 @@ */ /* n1, n2 */ - if (b->Z_is_one) { + int b_Z_is_one = BN_cmp(&b->Z, &group->one) == 0; + + if (b_Z_is_one) { if (!BN_copy(n1, &a->X) || !BN_copy(n2, &a->Y)) { goto end; } @@ -552,7 +558,8 @@ } /* n3, n4 */ - if (a->Z_is_one) { + int a_Z_is_one = BN_cmp(&a->Z, &group->one) == 0; + if (a_Z_is_one) { if (!BN_copy(n3, &b->X) || !BN_copy(n4, &b->Y)) { goto end; } @@ -590,7 +597,6 @@ } else { /* a is the inverse of b */ BN_zero(&r->Z); - r->Z_is_one = 0; ret = 1; goto end; } @@ -605,16 +611,16 @@ /* 'n8' = n2 + n4 */ /* Z_r */ - if (a->Z_is_one && b->Z_is_one) { + if (a_Z_is_one && b_Z_is_one) { if (!BN_copy(&r->Z, n5)) { goto end; } } else { - if (a->Z_is_one) { + if (a_Z_is_one) { if (!BN_copy(n0, &b->Z)) { goto end; } - } else if (b->Z_is_one) { + } else if (b_Z_is_one) { if (!BN_copy(n0, &a->Z)) { goto end; } @@ -625,7 +631,7 @@ goto end; } } - r->Z_is_one = 0; + /* Z_r = Z_a * Z_b * n5 */ /* X_r */ @@ -685,7 +691,6 @@ if (EC_POINT_is_at_infinity(group, a)) { BN_zero(&r->Z); - r->Z_is_one = 0; return 1; } @@ -715,7 +720,7 @@ */ /* n1 */ - if (a->Z_is_one) { + if (BN_cmp(&a->Z, &group->one) == 0) { if (!field_sqr(group, n0, &a->X, ctx) || !BN_mod_lshift1_quick(n1, n0, p) || !BN_mod_add_quick(n0, n0, n1, p) || @@ -748,7 +753,7 @@ } /* Z_r */ - if (a->Z_is_one) { + if (BN_cmp(&a->Z, &group->one) == 0) { if (!BN_copy(n0, &a->Y)) { goto err; } @@ -758,7 +763,6 @@ if (!BN_mod_lshift1_quick(&r->Z, n0, p)) { goto err; } - r->Z_is_one = 0; /* Z_r = 2 * Y_a * Z_a */ /* n2 */ @@ -810,7 +814,7 @@ } int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) { - return !point->Z_is_one && BN_is_zero(&point->Z); + return BN_is_zero(&point->Z); } int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, @@ -862,7 +866,7 @@ goto err; } - if (!point->Z_is_one) { + if (BN_cmp(&point->Z, &group->one) != 0) { if (!field_sqr(group, tmp, &point->Z, ctx) || !field_sqr(group, Z4, tmp, ctx) || !field_mul(group, Z6, Z4, tmp, ctx)) { @@ -891,8 +895,6 @@ goto err; } } else { - /* point->Z_is_one */ - /* rh := (rh + a)*X */ if (!BN_mod_add_quick(rh, rh, &group->a, p) || !field_mul(group, rh, rh, &point->X, ctx)) { @@ -941,7 +943,10 @@ return 1; } - if (a->Z_is_one && b->Z_is_one) { + int a_Z_is_one = BN_cmp(&a->Z, &group->one) == 0; + int b_Z_is_one = BN_cmp(&b->Z, &group->one) == 0; + + if (a_Z_is_one && b_Z_is_one) { return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1; } @@ -970,7 +975,7 @@ * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3). */ - if (!b->Z_is_one) { + if (!b_Z_is_one) { if (!field_sqr(group, Zb23, &b->Z, ctx) || !field_mul(group, tmp1, &a->X, Zb23, ctx)) { goto end; @@ -979,7 +984,7 @@ } else { tmp1_ = &a->X; } - if (!a->Z_is_one) { + if (!a_Z_is_one) { if (!field_sqr(group, Za23, &a->Z, ctx) || !field_mul(group, tmp2, &b->X, Za23, ctx)) { goto end; @@ -996,7 +1001,7 @@ } - if (!b->Z_is_one) { + if (!b_Z_is_one) { if (!field_mul(group, Zb23, Zb23, &b->Z, ctx) || !field_mul(group, tmp1, &a->Y, Zb23, ctx)) { goto end; @@ -1005,7 +1010,7 @@ } else { tmp1_ = &a->Y; } - if (!a->Z_is_one) { + if (!a_Z_is_one) { if (!field_mul(group, Za23, Za23, &a->Z, ctx) || !field_mul(group, tmp2, &b->Y, Za23, ctx)) { goto end; @@ -1036,7 +1041,8 @@ BIGNUM *x, *y; int ret = 0; - if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) { + if (BN_cmp(&point->Z, &group->one) == 0 || + EC_POINT_is_at_infinity(group, point)) { return 1; } @@ -1058,7 +1064,7 @@ !EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) { goto err; } - if (!point->Z_is_one) { + if (BN_cmp(&point->Z, &group->one) != 0) { OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR); goto err; } @@ -1117,14 +1123,8 @@ goto err; } } else { - if (group->meth->field_set_to_one != 0) { - if (!group->meth->field_set_to_one(group, prod_Z[0], ctx)) { - goto err; - } - } else { - if (!BN_one(prod_Z[0])) { - goto err; - } + if (BN_copy(prod_Z[0], &group->one) == NULL) { + goto err; } } @@ -1195,16 +1195,9 @@ goto err; } - if (group->meth->field_set_to_one != NULL) { - if (!group->meth->field_set_to_one(group, &p->Z, ctx)) { - goto err; - } - } else { - if (!BN_one(&p->Z)) { - goto err; - } + if (BN_copy(&p->Z, &group->one) == NULL) { + goto err; } - p->Z_is_one = 1; } }