Use a 5-bit comb for some Trust Tokens multiplications. Several of the Trust Tokens multiplications use repeated points (G, H, and the public keys). We can precompute a 5-bit comb for those points and perform only 1/5th as many doubles in the multiplication. Before: Did 483 TrustToken-Exp0-Batch1 generate_key operations in 2017082us (239.5 ops/sec) Did 1449 TrustToken-Exp0-Batch1 begin_issuance operations in 2086097us (694.6 ops/sec) Did 176 TrustToken-Exp0-Batch1 issue operations in 2089640us (84.2 ops/sec) Did 147 TrustToken-Exp0-Batch1 finish_issuance operations in 2027924us (72.5 ops/sec) Did 12284000 TrustToken-Exp0-Batch1 begin_redemption operations in 2000151us (6141536.3 ops/sec) Did 483 TrustToken-Exp0-Batch1 redeem operations in 2063241us (234.1 ops/sec) Did 35000 TrustToken-Exp0-Batch1 finish_redemption operations in 2050694us (17067.4 ops/sec) Did 483 TrustToken-Exp0-Batch10 generate_key operations in 2003222us (241.1 ops/sec) Did 138 TrustToken-Exp0-Batch10 begin_issuance operations in 2000845us (69.0 ops/sec) Did 16 TrustToken-Exp0-Batch10 issue operations in 2010264us (8.0 ops/sec) Did 14 TrustToken-Exp0-Batch10 finish_issuance operations in 2036137us (6.9 ops/sec) Did 12106000 TrustToken-Exp0-Batch10 begin_redemption operations in 2000126us (6052618.7 ops/sec) Did 483 TrustToken-Exp0-Batch10 redeem operations in 2062366us (234.2 ops/sec) Did 35000 TrustToken-Exp0-Batch10 finish_redemption operations in 2023617us (17295.8 ops/sec) Did 1254 TrustToken-Exp1-Batch1 generate_key operations in 2086776us (600.9 ops/sec) Did 3612 TrustToken-Exp1-Batch1 begin_issuance operations in 2052090us (1760.2 ops/sec) Did 420 TrustToken-Exp1-Batch1 issue operations in 2002421us (209.7 ops/sec) Did 378 TrustToken-Exp1-Batch1 finish_issuance operations in 2078074us (181.9 ops/sec) Did 12843000 TrustToken-Exp1-Batch1 begin_redemption operations in 2000068us (6421281.7 ops/sec) Did 1210 TrustToken-Exp1-Batch1 redeem operations in 2083419us (580.8 ops/sec) Did 35000 TrustToken-Exp1-Batch1 finish_redemption operations in 2023704us (17295.0 ops/sec) Did 1239 TrustToken-Exp1-Batch10 generate_key operations in 2060962us (601.2 ops/sec) Did 357 TrustToken-Exp1-Batch10 begin_issuance operations in 2031131us (175.8 ops/sec) Did 42 TrustToken-Exp1-Batch10 issue operations in 2045185us (20.5 ops/sec) Did 36 TrustToken-Exp1-Batch10 finish_issuance operations in 2028604us (17.7 ops/sec) Did 12435000 TrustToken-Exp1-Batch10 begin_redemption operations in 2000084us (6217238.9 ops/sec) Did 1176 TrustToken-Exp1-Batch10 redeem operations in 2023934us (581.0 ops/sec) Did 35000 TrustToken-Exp1-Batch10 finish_redemption operations in 2002899us (17474.7 ops/sec) After: Did 875 TrustToken-Exp0-Batch1 generate_key operations in 2028222us (431.4 ops/sec) [+80.2%] Did 1449 TrustToken-Exp0-Batch1 begin_issuance operations in 2097298us (690.9 ops/sec) [-0.5%] Did 207 TrustToken-Exp0-Batch1 issue operations in 2083578us (99.3 ops/sec) [+18.0%] Did 147 TrustToken-Exp0-Batch1 finish_issuance operations in 2018783us (72.8 ops/sec) [+0.5%] Did 12020250 TrustToken-Exp0-Batch1 begin_redemption operations in 2000036us (6010016.8 ops/sec) [-2.1%] Did 525 TrustToken-Exp0-Batch1 redeem operations in 2077137us (252.8 ops/sec) [+8.0%] Did 35000 TrustToken-Exp0-Batch1 finish_redemption operations in 2006257us (17445.4 ops/sec) [+2.2%] Did 903 TrustToken-Exp0-Batch10 generate_key operations in 2091846us (431.7 ops/sec) [+79.0%] Did 138 TrustToken-Exp0-Batch10 begin_issuance operations in 2006432us (68.8 ops/sec) [-0.3%] Did 19 TrustToken-Exp0-Batch10 issue operations in 2000665us (9.5 ops/sec) [+19.3%] Did 14 TrustToken-Exp0-Batch10 finish_issuance operations in 2045846us (6.8 ops/sec) [-0.5%] Did 12124000 TrustToken-Exp0-Batch10 begin_redemption operations in 2000055us (6061833.3 ops/sec) [+0.2%] Did 525 TrustToken-Exp0-Batch10 redeem operations in 2076637us (252.8 ops/sec) [+7.9%] Did 35000 TrustToken-Exp0-Batch10 finish_redemption operations in 2000072us (17499.4 ops/sec) [+1.2%] Did 2142 TrustToken-Exp1-Batch1 generate_key operations in 2031447us (1054.4 ops/sec) [+75.5%] Did 3633 TrustToken-Exp1-Batch1 begin_issuance operations in 2073265us (1752.3 ops/sec) [-0.4%] Did 504 TrustToken-Exp1-Batch1 issue operations in 2043677us (246.6 ops/sec) [+17.6%] Did 378 TrustToken-Exp1-Batch1 finish_issuance operations in 2086624us (181.2 ops/sec) [-0.4%] Did 12548250 TrustToken-Exp1-Batch1 begin_redemption operations in 2000020us (6274062.3 ops/sec) [-2.3%] Did 1281 TrustToken-Exp1-Batch1 redeem operations in 2067790us (619.5 ops/sec) [+6.7%] Did 35000 TrustToken-Exp1-Batch1 finish_redemption operations in 2012117us (17394.6 ops/sec) [+0.6%] Did 2184 TrustToken-Exp1-Batch10 generate_key operations in 2069977us (1055.1 ops/sec) [+75.5%] Did 357 TrustToken-Exp1-Batch10 begin_issuance operations in 2041930us (174.8 ops/sec) [-0.5%] Did 50 TrustToken-Exp1-Batch10 issue operations in 2063927us (24.2 ops/sec) [+18.0%] Did 36 TrustToken-Exp1-Batch10 finish_issuance operations in 2038115us (17.7 ops/sec) [-0.5%] Did 12693000 TrustToken-Exp1-Batch10 begin_redemption operations in 2000070us (6346277.9 ops/sec) [+2.1%] Did 1281 TrustToken-Exp1-Batch10 redeem operations in 2066940us (619.8 ops/sec) [+6.7%] Did 35000 TrustToken-Exp1-Batch10 finish_redemption operations in 2020506us (17322.4 ops/sec) [-0.9%] Change-Id: Id26600c07401d6567275155aa389839ac0e87013 Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/41124 Commit-Queue: David Benjamin <davidben@google.com> Reviewed-by: Steven Valdez <svaldez@google.com>
diff --git a/crypto/fipsmodule/ec/ec.c b/crypto/fipsmodule/ec/ec.c index 5497aac..89ce64e 100644 --- a/crypto/fipsmodule/ec/ec.c +++ b/crypto/fipsmodule/ec/ec.c
@@ -1070,6 +1070,38 @@ return 1; } +int ec_init_precomp(const EC_GROUP *group, EC_PRECOMP *out, + const EC_RAW_POINT *p) { + if (group->meth->init_precomp == NULL) { + OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + + return group->meth->init_precomp(group, out, p); +} + +int ec_point_mul_scalar_precomp(const EC_GROUP *group, EC_RAW_POINT *r, + const EC_PRECOMP *p0, const EC_SCALAR *scalar0, + const EC_PRECOMP *p1, const EC_SCALAR *scalar1, + const EC_PRECOMP *p2, + const EC_SCALAR *scalar2) { + if (group->meth->mul_precomp == NULL) { + OPENSSL_PUT_ERROR(EC, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + + group->meth->mul_precomp(group, r, p0, scalar0, p1, scalar1, p2, scalar2); + + // Check the result is on the curve to defend against fault attacks or bugs. + // This has negligible cost compared to the multiplication. + if (!ec_GFp_simple_is_on_curve(group, r)) { + OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR); + return 0; + } + + return 1; +} + void ec_point_select(const EC_GROUP *group, EC_RAW_POINT *out, BN_ULONG mask, const EC_RAW_POINT *a, const EC_RAW_POINT *b) { ec_felem_select(group, &out->X, mask, &a->X, &b->X); @@ -1083,6 +1115,15 @@ ec_felem_select(group, &out->Y, mask, &a->Y, &b->Y); } +void ec_precomp_select(const EC_GROUP *group, EC_PRECOMP *out, BN_ULONG mask, + const EC_PRECOMP *a, const EC_PRECOMP *b) { + OPENSSL_STATIC_ASSERT(sizeof(out->comb) == sizeof(*out), + "out->comb does not span the entire structure"); + for (size_t i = 0; i < OPENSSL_ARRAY_SIZE(out->comb); i++) { + ec_affine_select(group, &out->comb[i], mask, &a->comb[i], &b->comb[i]); + } +} + int ec_cmp_x_coordinate(const EC_GROUP *group, const EC_RAW_POINT *p, const EC_SCALAR *r) { return group->meth->cmp_x_coordinate(group, p, r);
diff --git a/crypto/fipsmodule/ec/ec_montgomery.c b/crypto/fipsmodule/ec/ec_montgomery.c index 8e94f30..e9a0958 100644 --- a/crypto/fipsmodule/ec/ec_montgomery.c +++ b/crypto/fipsmodule/ec/ec_montgomery.c
@@ -509,6 +509,8 @@ out->mul_base = ec_GFp_mont_mul_base; out->mul_batch = ec_GFp_mont_mul_batch; out->mul_public = ec_GFp_mont_mul_public; + out->init_precomp = ec_GFp_mont_init_precomp; + out->mul_precomp = ec_GFp_mont_mul_precomp; out->felem_mul = ec_GFp_mont_felem_mul; out->felem_sqr = ec_GFp_mont_felem_sqr; out->felem_to_bytes = ec_GFp_mont_felem_to_bytes;
diff --git a/crypto/fipsmodule/ec/internal.h b/crypto/fipsmodule/ec/internal.h index a30af1c..278c071 100644 --- a/crypto/fipsmodule/ec/internal.h +++ b/crypto/fipsmodule/ec/internal.h
@@ -334,6 +334,52 @@ const EC_RAW_POINT *p1, const EC_SCALAR *scalar1, const EC_RAW_POINT *p2, const EC_SCALAR *scalar2); +#define EC_MONT_PRECOMP_COMB_SIZE 5 + +// An |EC_PRECOMP| stores precomputed information about a point, to optimize +// repeated multiplications involving it. It is a union so different +// |EC_METHOD|s can store different information in it. +typedef union { + EC_AFFINE comb[(1 << EC_MONT_PRECOMP_COMB_SIZE) - 1]; +} EC_PRECOMP; + +// ec_init_precomp precomputes multiples of |p| and writes the result to |out|. +// It returns one on success and zero on error. The resulting table may be used +// with |ec_point_mul_scalar_precomp|. This function will fail if |p| is the +// point at infinity. +// +// This function is not implemented for all curves. Add implementations as +// needed. +int ec_init_precomp(const EC_GROUP *group, EC_PRECOMP *out, + const EC_RAW_POINT *p); + +// ec_point_mul_scalar_precomp sets |r| to |p0| * |scalar0| + |p1| * |scalar1| + +// |p2| * |scalar2|. |p1| or |p2| may be NULL to skip the corresponding term. +// The points are represented as |EC_PRECOMP| and must be initialized with +// |ec_init_precomp|. This function runs faster than |ec_point_mul_scalar_batch| +// but requires setup work per input point, so it is only appropriate for points +// which are used frequently. +// +// The inputs are treated as secret, however, this function leaks information +// about whether intermediate computations add a point to itself. Callers must +// ensure that discrete logs between |p0|, |p1|, and |p2| are uniformly +// distributed and independent of the scalars, which should be uniformly +// selected and not under the attackers control. This ensures the doubling case +// will occur with negligible probability. +// +// This function is not implemented for all curves. Add implementations as +// needed. +// +// TODO(davidben): This function does not use base point tables. For now, it is +// only used with the generic |EC_GFp_mont_method| implementation which has +// none. If generalizing to tuned curves, we should add a parameter for the base +// point and arrange for the generic implementation to have base point tables +// available. +int ec_point_mul_scalar_precomp(const EC_GROUP *group, EC_RAW_POINT *r, + const EC_PRECOMP *p0, const EC_SCALAR *scalar0, + const EC_PRECOMP *p1, const EC_SCALAR *scalar1, + const EC_PRECOMP *p2, const EC_SCALAR *scalar2); + // ec_point_mul_scalar_public sets |r| to // generator * |g_scalar| + |p| * |p_scalar|. It assumes that the inputs are // public so there is no concern about leaking their values through timing. @@ -352,6 +398,10 @@ void ec_affine_select(const EC_GROUP *group, EC_AFFINE *out, BN_ULONG mask, const EC_AFFINE *a, const EC_AFFINE *b); +// ec_precomp_select behaves like |ec_point_select| but acts on |EC_PRECOMP|. +void ec_precomp_select(const EC_GROUP *group, EC_PRECOMP *out, BN_ULONG mask, + const EC_PRECOMP *a, const EC_PRECOMP *b); + // ec_cmp_x_coordinate compares the x (affine) coordinate of |p|, mod the group // order, with |r|. It returns one if the values match and zero if |p| is the // point at infinity of the values do not match. @@ -437,6 +487,15 @@ const EC_SCALAR *g_scalar, const EC_RAW_POINT *p, const EC_SCALAR *p_scalar); + // init_precomp implements |ec_init_precomp|. + int (*init_precomp)(const EC_GROUP *group, EC_PRECOMP *out, + const EC_RAW_POINT *p); + // mul_precomp implements |ec_point_mul_scalar_precomp|. + void (*mul_precomp)(const EC_GROUP *group, EC_RAW_POINT *r, + const EC_PRECOMP *p0, const EC_SCALAR *scalar0, + const EC_PRECOMP *p1, const EC_SCALAR *scalar1, + const EC_PRECOMP *p2, const EC_SCALAR *scalar2); + // felem_mul and felem_sqr implement multiplication and squaring, // respectively, so that the generic |EC_POINT_add| and |EC_POINT_dbl| // implementations can work both with |EC_GFp_mont_method| and the tuned @@ -555,6 +614,12 @@ const EC_RAW_POINT *p0, const EC_SCALAR *scalar0, const EC_RAW_POINT *p1, const EC_SCALAR *scalar1, const EC_RAW_POINT *p2, const EC_SCALAR *scalar2); +int ec_GFp_mont_init_precomp(const EC_GROUP *group, EC_PRECOMP *out, + const EC_RAW_POINT *p); +void ec_GFp_mont_mul_precomp(const EC_GROUP *group, EC_RAW_POINT *r, + const EC_PRECOMP *p0, const EC_SCALAR *scalar0, + const EC_PRECOMP *p1, const EC_SCALAR *scalar1, + const EC_PRECOMP *p2, const EC_SCALAR *scalar2); // ec_compute_wNAF writes the modified width-(w+1) Non-Adjacent Form (wNAF) of // |scalar| to |out|. |out| must have room for |bits| + 1 elements, each of
diff --git a/crypto/fipsmodule/ec/simple_mul.c b/crypto/fipsmodule/ec/simple_mul.c index 02063df..127e2b3 100644 --- a/crypto/fipsmodule/ec/simple_mul.c +++ b/crypto/fipsmodule/ec/simple_mul.c
@@ -167,3 +167,104 @@ ec_GFp_simple_point_set_to_infinity(group, r); } } + +static unsigned ec_GFp_mont_comb_stride(const EC_GROUP *group) { + return (BN_num_bits(&group->field) + EC_MONT_PRECOMP_COMB_SIZE - 1) / + EC_MONT_PRECOMP_COMB_SIZE; +} + +int ec_GFp_mont_init_precomp(const EC_GROUP *group, EC_PRECOMP *out, + const EC_RAW_POINT *p) { + // comb[i - 1] stores the ith element of the comb. That is, if i is + // b4 * 2^4 + b3 * 2^3 + ... + b0 * 2^0, it stores k * |p|, where k is + // b4 * 2^(4*stride) + b3 * 2^(3*stride) + ... + b0 * 2^(0*stride). stride + // here is |ec_GFp_mont_comb_stride|. We store at index i - 1 because the 0th + // comb entry is always infinity. + EC_RAW_POINT comb[(1 << EC_MONT_PRECOMP_COMB_SIZE) - 1]; + unsigned stride = ec_GFp_mont_comb_stride(group); + + // We compute the comb sequentially by the highest set bit. Initially, all + // entries up to 2^0 are filled. + comb[(1 << 0) - 1] = *p; + for (unsigned i = 1; i < EC_MONT_PRECOMP_COMB_SIZE; i++) { + // Compute entry 2^i by doubling the entry for 2^(i-1) |stride| times. + unsigned bit = 1 << i; + ec_GFp_mont_dbl(group, &comb[bit - 1], &comb[bit / 2 - 1]); + for (unsigned j = 1; j < stride; j++) { + ec_GFp_mont_dbl(group, &comb[bit - 1], &comb[bit - 1]); + } + // Compute entries from 2^i + 1 to 2^i + (2^i - 1) by adding entry 2^i to + // a previous entry. + for (unsigned j = 1; j < bit; j++) { + ec_GFp_mont_add(group, &comb[bit + j - 1], &comb[bit - 1], &comb[j - 1]); + } + } + + // Store the comb in affine coordinates to shrink the table. (This reduces + // cache pressure and makes the constant-time selects faster.) + OPENSSL_STATIC_ASSERT( + OPENSSL_ARRAY_SIZE(comb) == OPENSSL_ARRAY_SIZE(out->comb), + "comb sizes did not match"); + return ec_jacobian_to_affine_batch(group, out->comb, comb, + OPENSSL_ARRAY_SIZE(comb)); +} + +static void ec_GFp_mont_get_comb_window(const EC_GROUP *group, + EC_RAW_POINT *out, + const EC_PRECOMP *precomp, + const EC_SCALAR *scalar, unsigned i) { + const size_t width = group->order.width; + unsigned stride = ec_GFp_mont_comb_stride(group); + // Select the bits corresponding to the comb shifted up by |i|. + unsigned window = 0; + for (unsigned j = 0; j < EC_MONT_PRECOMP_COMB_SIZE; j++) { + window |= bn_is_bit_set_words(scalar->words, width, j * stride + i) + << j; + } + + // Select precomp->comb[window - 1]. If |window| is zero, |match| will always + // be zero, which will leave |out| at infinity. + OPENSSL_memset(out, 0, sizeof(EC_RAW_POINT)); + for (unsigned j = 0; j < OPENSSL_ARRAY_SIZE(precomp->comb); j++) { + BN_ULONG match = constant_time_eq_w(window, j + 1); + ec_felem_select(group, &out->X, match, &precomp->comb[j].X, &out->X); + ec_felem_select(group, &out->Y, match, &precomp->comb[j].Y, &out->Y); + } + BN_ULONG is_infinity = constant_time_is_zero_w(window); + ec_felem_select(group, &out->Z, is_infinity, &out->Z, &group->one); +} + +void ec_GFp_mont_mul_precomp(const EC_GROUP *group, EC_RAW_POINT *r, + const EC_PRECOMP *p0, const EC_SCALAR *scalar0, + const EC_PRECOMP *p1, const EC_SCALAR *scalar1, + const EC_PRECOMP *p2, const EC_SCALAR *scalar2) { + unsigned stride = ec_GFp_mont_comb_stride(group); + int r_is_at_infinity = 1; + for (unsigned i = stride - 1; i < stride; i--) { + if (!r_is_at_infinity) { + ec_GFp_mont_dbl(group, r, r); + } + + EC_RAW_POINT tmp; + ec_GFp_mont_get_comb_window(group, &tmp, p0, scalar0, i); + if (r_is_at_infinity) { + ec_GFp_simple_point_copy(r, &tmp); + r_is_at_infinity = 0; + } else { + ec_GFp_mont_add(group, r, r, &tmp); + } + + if (p1 != NULL) { + ec_GFp_mont_get_comb_window(group, &tmp, p1, scalar1, i); + ec_GFp_mont_add(group, r, r, &tmp); + } + + if (p2 != NULL) { + ec_GFp_mont_get_comb_window(group, &tmp, p2, scalar2, i); + ec_GFp_mont_add(group, r, r, &tmp); + } + } + if (r_is_at_infinity) { + ec_GFp_simple_point_set_to_infinity(group, r); + } +}
diff --git a/crypto/trust_token/internal.h b/crypto/trust_token/internal.h index 6c9904d..db9d0cf 100644 --- a/crypto/trust_token/internal.h +++ b/crypto/trust_token/internal.h
@@ -42,6 +42,8 @@ #define PMBTOKEN_NONCE_SIZE 64 typedef struct { + // TODO(https://crbug.com/boringssl/334): These should store |EC_PRECOMP| so + // that |TRUST_TOKEN_finish_issuance| can use |ec_point_mul_scalar_precomp|. EC_AFFINE pub0; EC_AFFINE pub1; EC_AFFINE pubs; @@ -55,8 +57,11 @@ EC_SCALAR xs; EC_SCALAR ys; EC_AFFINE pub0; + EC_PRECOMP pub0_precomp; EC_AFFINE pub1; + EC_PRECOMP pub1_precomp; EC_AFFINE pubs; + EC_PRECOMP pubs_precomp; } PMBTOKEN_ISSUER_KEY; // PMBTOKEN_PRETOKEN represents the intermediate state a client keeps during a
diff --git a/crypto/trust_token/pmbtoken.c b/crypto/trust_token/pmbtoken.c index 0407537..7eca5bb 100644 --- a/crypto/trust_token/pmbtoken.c +++ b/crypto/trust_token/pmbtoken.c
@@ -30,36 +30,70 @@ #include "internal.h" +typedef int (*hash_t_func_t)(const EC_GROUP *group, EC_RAW_POINT *out, + const uint8_t t[PMBTOKEN_NONCE_SIZE]); +typedef int (*hash_s_func_t)(const EC_GROUP *group, EC_RAW_POINT *out, + const EC_AFFINE *t, + const uint8_t s[PMBTOKEN_NONCE_SIZE]); +typedef int (*hash_c_func_t)(const EC_GROUP *group, EC_SCALAR *out, + uint8_t *buf, size_t len); + typedef struct { const EC_GROUP *group; + EC_PRECOMP g_precomp; + EC_PRECOMP h_precomp; EC_RAW_POINT h; - // hash_t implements the H_t operation in PMBTokens. It returns on on success + // hash_t implements the H_t operation in PMBTokens. It returns one on success // and zero on error. - int (*hash_t)(const EC_GROUP *group, EC_RAW_POINT *out, - const uint8_t t[PMBTOKEN_NONCE_SIZE]); - // hash_s implements the H_s operation in PMBTokens. It returns on on success + hash_t_func_t hash_t; + // hash_s implements the H_s operation in PMBTokens. It returns one on success // and zero on error. - int (*hash_s)(const EC_GROUP *group, EC_RAW_POINT *out, const EC_AFFINE *t, - const uint8_t s[PMBTOKEN_NONCE_SIZE]); - // hash_c implements the H_c operation in PMBTokens. It returns on on success + hash_s_func_t hash_s; + // hash_c implements the H_c operation in PMBTokens. It returns one on success // and zero on error. - int (*hash_c)(const EC_GROUP *group, EC_SCALAR *out, uint8_t *buf, - size_t len); + hash_c_func_t hash_c; } PMBTOKEN_METHOD; static const uint8_t kDefaultAdditionalData[32] = {0}; +static int pmbtoken_init_method(PMBTOKEN_METHOD *method, int curve_nid, + const uint8_t *h_bytes, size_t h_len, + hash_t_func_t hash_t, hash_s_func_t hash_s, + hash_c_func_t hash_c) { + method->group = EC_GROUP_new_by_curve_name(curve_nid); + if (method->group == NULL) { + return 0; + } + + method->hash_t = hash_t; + method->hash_s = hash_s; + method->hash_c = hash_c; + + EC_AFFINE h; + if (!ec_point_from_uncompressed(method->group, &h, h_bytes, h_len)) { + return 0; + } + ec_affine_to_jacobian(method->group, &method->h, &h); + + if (!ec_init_precomp(method->group, &method->g_precomp, + &method->group->generator->raw) || + !ec_init_precomp(method->group, &method->h_precomp, &method->h)) { + return 0; + } + return 1; +} + // generate_keypair generates a keypair for the PMBTokens construction. // |out_x| and |out_y| are set to the secret half of the keypair, while // |*out_pub| is set to the public half of the keypair. It returns one on // success and zero on failure. static int generate_keypair(const PMBTOKEN_METHOD *method, EC_SCALAR *out_x, EC_SCALAR *out_y, EC_RAW_POINT *out_pub) { - const EC_RAW_POINT *g = &method->group->generator->raw; if (!ec_random_nonzero_scalar(method->group, out_x, kDefaultAdditionalData) || !ec_random_nonzero_scalar(method->group, out_y, kDefaultAdditionalData) || - !ec_point_mul_scalar_batch(method->group, out_pub, g, out_x, &method->h, - out_y, NULL, NULL)) { + !ec_point_mul_scalar_precomp(method->group, out_pub, &method->g_precomp, + out_x, &method->h_precomp, out_y, NULL, + NULL)) { OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_MALLOC_FAILURE); return 0; } @@ -178,13 +212,15 @@ // Recompute the public key. EC_RAW_POINT pub[3]; EC_AFFINE pub_affine[3]; - const EC_RAW_POINT *g = &group->generator->raw; - if (!ec_point_mul_scalar_batch(group, &pub[0], g, &key->x0, &method->h, - &key->y0, NULL, NULL) || - !ec_point_mul_scalar_batch(group, &pub[1], g, &key->x1, &method->h, - &key->y1, NULL, NULL) || - !ec_point_mul_scalar_batch(group, &pub[2], g, &key->xs, &method->h, - &key->ys, NULL, NULL) || + if (!ec_point_mul_scalar_precomp(group, &pub[0], &method->g_precomp, &key->x0, + &method->h_precomp, &key->y0, NULL, NULL) || + !ec_init_precomp(group, &key->pub0_precomp, &pub[0]) || + !ec_point_mul_scalar_precomp(group, &pub[1], &method->g_precomp, &key->x1, + &method->h_precomp, &key->y1, NULL, NULL) || + !ec_init_precomp(group, &key->pub1_precomp, &pub[1]) || + !ec_point_mul_scalar_precomp(group, &pub[2], &method->g_precomp, &key->xs, + &method->h_precomp, &key->ys, NULL, NULL) || + !ec_init_precomp(group, &key->pubs_precomp, &pub[2]) || !ec_jacobian_to_affine_batch(group, pub_affine, pub, 3)) { return 0; } @@ -357,7 +393,6 @@ const EC_RAW_POINT *S, const EC_RAW_POINT *W, const EC_RAW_POINT *Ws, uint8_t private_metadata) { const EC_GROUP *group = method->group; - const EC_RAW_POINT *g = &group->generator->raw; // We generate a DLEQ proof for the validity token and a DLEQOR2 proof for the // private metadata token. To allow amortizing Jacobian-to-affine conversions, @@ -383,8 +418,9 @@ !ec_random_nonzero_scalar(group, &ks0, kDefaultAdditionalData) || !ec_random_nonzero_scalar(group, &ks1, kDefaultAdditionalData) || // Ks = ks0*(G;T) + ks1*(H;S) - !ec_point_mul_scalar_batch(group, &jacobians[idx_Ks0], g, &ks0, - &method->h, &ks1, NULL, NULL) || + !ec_point_mul_scalar_precomp(group, &jacobians[idx_Ks0], + &method->g_precomp, &ks0, &method->h_precomp, + &ks1, NULL, NULL) || !ec_point_mul_scalar_batch(group, &jacobians[idx_Ks1], T, &ks0, S, &ks1, NULL, NULL)) { return 0; @@ -394,21 +430,21 @@ // to the private metadata value) and pubo (public key corresponding to the // other value) in constant time. BN_ULONG mask = ((BN_ULONG)0) - (private_metadata & 1); - EC_AFFINE pubo_affine; - EC_RAW_POINT pubo; + EC_PRECOMP pubo_precomp; EC_SCALAR xb, yb; ec_scalar_select(group, &xb, mask, &priv->x1, &priv->x0); ec_scalar_select(group, &yb, mask, &priv->y1, &priv->y0); - ec_affine_select(group, &pubo_affine, mask, &priv->pub0, &priv->pub1); - ec_affine_to_jacobian(group, &pubo, &pubo_affine); + ec_precomp_select(group, &pubo_precomp, mask, &priv->pub0_precomp, + &priv->pub1_precomp); EC_SCALAR k0, k1, minus_co, uo, vo; if (// k0, k1 <- Zp !ec_random_nonzero_scalar(group, &k0, kDefaultAdditionalData) || !ec_random_nonzero_scalar(group, &k1, kDefaultAdditionalData) || // Kb = k0*(G;T) + k1*(H;S) - !ec_point_mul_scalar_batch(group, &jacobians[idx_Kb0], g, &k0, &method->h, - &k1, NULL, NULL) || + !ec_point_mul_scalar_precomp(group, &jacobians[idx_Kb0], + &method->g_precomp, &k0, &method->h_precomp, + &k1, NULL, NULL) || !ec_point_mul_scalar_batch(group, &jacobians[idx_Kb1], T, &k0, S, &k1, NULL, NULL) || // co, uo, vo <- Zp @@ -416,8 +452,9 @@ !ec_random_nonzero_scalar(group, &uo, kDefaultAdditionalData) || !ec_random_nonzero_scalar(group, &vo, kDefaultAdditionalData) || // Ko = uo*(G;T) + vo*(H;S) - co*(pubo;W) - !ec_point_mul_scalar_batch(group, &jacobians[idx_Ko0], g, &uo, &method->h, - &vo, &pubo, &minus_co) || + !ec_point_mul_scalar_precomp(group, &jacobians[idx_Ko0], + &method->g_precomp, &uo, &method->h_precomp, + &vo, &pubo_precomp, &minus_co) || !ec_point_mul_scalar_batch(group, &jacobians[idx_Ko1], T, &uo, S, &vo, W, &minus_co)) { return 0; @@ -823,21 +860,30 @@ return 0; } - EC_RAW_POINT S_jacobian, calculated; - // Check the validity of the token. + // We perform three multiplications with S and T. This is enough that it is + // worth using |ec_point_mul_scalar_precomp|. + EC_RAW_POINT S_jacobian; + EC_PRECOMP S_precomp, T_precomp; ec_affine_to_jacobian(group, &S_jacobian, &S); - if (!ec_point_mul_scalar_batch(group, &calculated, &T, &key->xs, &S_jacobian, - &key->ys, NULL, NULL) || - !ec_affine_jacobian_equal(group, &Ws, &calculated)) { + if (!ec_init_precomp(group, &S_precomp, &S_jacobian) || + !ec_init_precomp(group, &T_precomp, &T)) { + return 0; + } + + EC_RAW_POINT Ws_calculated; + // Check the validity of the token. + if (!ec_point_mul_scalar_precomp(group, &Ws_calculated, &T_precomp, &key->xs, + &S_precomp, &key->ys, NULL, NULL) || + !ec_affine_jacobian_equal(group, &Ws, &Ws_calculated)) { OPENSSL_PUT_ERROR(TRUST_TOKEN, TRUST_TOKEN_R_BAD_VALIDITY_CHECK); return 0; } EC_RAW_POINT W0, W1; - if (!ec_point_mul_scalar_batch(group, &W0, &T, &key->x0, &S_jacobian, - &key->y0, NULL, NULL) || - !ec_point_mul_scalar_batch(group, &W1, &T, &key->x1, &S_jacobian, - &key->y1, NULL, NULL)) { + if (!ec_point_mul_scalar_precomp(group, &W0, &T_precomp, &key->x0, &S_precomp, + &key->y0, NULL, NULL) || + !ec_point_mul_scalar_precomp(group, &W1, &T_precomp, &key->x1, &S_precomp, + &key->y1, NULL, NULL)) { return 0; } @@ -952,16 +998,11 @@ if __name__ == "__main__": gen_point(SEED_H) */ -static int pmbtoken_exp0_init_method(PMBTOKEN_METHOD *method) { - method->group = EC_GROUP_new_by_curve_name(NID_secp521r1); - if (method->group == NULL) { - return 0; - } +static int pmbtoken_exp0_ok = 0; +static PMBTOKEN_METHOD pmbtoken_exp0_method; +static CRYPTO_once_t pmbtoken_exp0_method_once = CRYPTO_ONCE_INIT; - method->hash_t = pmbtoken_exp0_hash_t; - method->hash_c = pmbtoken_exp0_hash_c; - method->hash_s = pmbtoken_exp0_hash_s; - +static void pmbtoken_exp0_init_method_impl(void) { static const uint8_t kH[] = { 0x04, 0x01, 0xf0, 0xa9, 0xf7, 0x9e, 0xbc, 0x12, 0x6c, 0xef, 0xd1, 0xab, 0x29, 0x10, 0x03, 0x6f, 0x4e, 0xf5, 0xbd, 0xeb, 0x0f, 0x6b, 0xc0, 0x5c, @@ -977,81 +1018,81 @@ 0xcd, }; - EC_AFFINE h; - if (!ec_point_from_uncompressed(method->group, &h, kH, sizeof(kH))) { + pmbtoken_exp0_ok = pmbtoken_init_method( + &pmbtoken_exp0_method, NID_secp521r1, kH, sizeof(kH), + pmbtoken_exp0_hash_t, pmbtoken_exp0_hash_s, pmbtoken_exp0_hash_c); +} + +static int pmbtoken_exp0_init_method(void) { + CRYPTO_once(&pmbtoken_exp0_method_once, pmbtoken_exp0_init_method_impl); + if (!pmbtoken_exp0_ok) { + OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_INTERNAL_ERROR); return 0; } - ec_affine_to_jacobian(method->group, &method->h, &h); return 1; } int pmbtoken_exp0_generate_key(CBB *out_private, CBB *out_public) { - PMBTOKEN_METHOD method; - if (!pmbtoken_exp0_init_method(&method)) { + if (!pmbtoken_exp0_init_method()) { return 0; } - return pmbtoken_generate_key(&method, out_private, out_public); + return pmbtoken_generate_key(&pmbtoken_exp0_method, out_private, out_public); } int pmbtoken_exp0_client_key_from_bytes(PMBTOKEN_CLIENT_KEY *key, const uint8_t *in, size_t len) { - PMBTOKEN_METHOD method; - if (!pmbtoken_exp0_init_method(&method)) { + if (!pmbtoken_exp0_init_method()) { return 0; } - return pmbtoken_client_key_from_bytes(&method, key, in, len); + return pmbtoken_client_key_from_bytes(&pmbtoken_exp0_method, key, in, len); } int pmbtoken_exp0_issuer_key_from_bytes(PMBTOKEN_ISSUER_KEY *key, const uint8_t *in, size_t len) { - PMBTOKEN_METHOD method; - if (!pmbtoken_exp0_init_method(&method)) { + if (!pmbtoken_exp0_init_method()) { return 0; } - return pmbtoken_issuer_key_from_bytes(&method, key, in, len); + return pmbtoken_issuer_key_from_bytes(&pmbtoken_exp0_method, key, in, len); } STACK_OF(PMBTOKEN_PRETOKEN) * pmbtoken_exp0_blind(CBB *cbb, size_t count) { - PMBTOKEN_METHOD method; - if (!pmbtoken_exp0_init_method(&method)) { + if (!pmbtoken_exp0_init_method()) { return NULL; } - return pmbtoken_blind(&method, cbb, count); + return pmbtoken_blind(&pmbtoken_exp0_method, cbb, count); } int pmbtoken_exp0_sign(const PMBTOKEN_ISSUER_KEY *key, CBB *cbb, CBS *cbs, size_t num_requested, size_t num_to_issue, uint8_t private_metadata) { - PMBTOKEN_METHOD method; - if (!pmbtoken_exp0_init_method(&method)) { + if (!pmbtoken_exp0_init_method()) { return 0; } - return pmbtoken_sign(&method, key, cbb, cbs, num_requested, num_to_issue, - private_metadata); + return pmbtoken_sign(&pmbtoken_exp0_method, key, cbb, cbs, num_requested, + num_to_issue, private_metadata); } STACK_OF(TRUST_TOKEN) * pmbtoken_exp0_unblind(const PMBTOKEN_CLIENT_KEY *key, - const STACK_OF(PMBTOKEN_PRETOKEN) *pretokens, + const STACK_OF(PMBTOKEN_PRETOKEN) * pretokens, CBS *cbs, size_t count, uint32_t key_id) { - PMBTOKEN_METHOD method; - if (!pmbtoken_exp0_init_method(&method)) { + if (!pmbtoken_exp0_init_method()) { return NULL; } - return pmbtoken_unblind(&method, key, pretokens, cbs, count, key_id); + return pmbtoken_unblind(&pmbtoken_exp0_method, key, pretokens, cbs, count, + key_id); } int pmbtoken_exp0_read(const PMBTOKEN_ISSUER_KEY *key, uint8_t out_nonce[PMBTOKEN_NONCE_SIZE], uint8_t *out_private_metadata, const uint8_t *token, size_t token_len) { - PMBTOKEN_METHOD method; - if (!pmbtoken_exp0_init_method(&method)) { + if (!pmbtoken_exp0_init_method()) { return 0; } - return pmbtoken_read(&method, key, out_nonce, out_private_metadata, token, - token_len); + return pmbtoken_read(&pmbtoken_exp0_method, key, out_nonce, + out_private_metadata, token, token_len); } @@ -1097,16 +1138,11 @@ group, out, kHashCLabel, sizeof(kHashCLabel), buf, len); } -static int pmbtoken_exp1_init_method(PMBTOKEN_METHOD *method) { - method->group = EC_GROUP_new_by_curve_name(NID_secp384r1); - if (method->group == NULL) { - return 0; - } +static int pmbtoken_exp1_ok = 0; +static PMBTOKEN_METHOD pmbtoken_exp1_method; +static CRYPTO_once_t pmbtoken_exp1_method_once = CRYPTO_ONCE_INIT; - method->hash_t = pmbtoken_exp1_hash_t; - method->hash_c = pmbtoken_exp1_hash_c; - method->hash_s = pmbtoken_exp1_hash_s; - +static void pmbtoken_exp1_init_method_impl(void) { // This is the output of |ec_hash_to_scalar_p384_xmd_sha512_draft07| with DST // "PMBTokens Experiment V1 HashH" and message "generator". static const uint8_t kH[] = { @@ -1121,90 +1157,90 @@ 0x87, 0xc3, 0x95, 0xd0, 0x13, 0xb7, 0x0b, 0x5c, 0xc7, }; - EC_AFFINE h; - if (!ec_point_from_uncompressed(method->group, &h, kH, sizeof(kH))) { + pmbtoken_exp1_ok = pmbtoken_init_method( + &pmbtoken_exp1_method, NID_secp384r1, kH, sizeof(kH), + pmbtoken_exp1_hash_t, pmbtoken_exp1_hash_s, pmbtoken_exp1_hash_c); +} + +static int pmbtoken_exp1_init_method(void) { + CRYPTO_once(&pmbtoken_exp1_method_once, pmbtoken_exp1_init_method_impl); + if (!pmbtoken_exp1_ok) { + OPENSSL_PUT_ERROR(TRUST_TOKEN, ERR_R_INTERNAL_ERROR); return 0; } - ec_affine_to_jacobian(method->group, &method->h, &h); return 1; } int pmbtoken_exp1_generate_key(CBB *out_private, CBB *out_public) { - PMBTOKEN_METHOD method; - if (!pmbtoken_exp1_init_method(&method)) { + if (!pmbtoken_exp1_init_method()) { return 0; } - return pmbtoken_generate_key(&method, out_private, out_public); + return pmbtoken_generate_key(&pmbtoken_exp1_method, out_private, out_public); } int pmbtoken_exp1_client_key_from_bytes(PMBTOKEN_CLIENT_KEY *key, const uint8_t *in, size_t len) { - PMBTOKEN_METHOD method; - if (!pmbtoken_exp1_init_method(&method)) { + if (!pmbtoken_exp1_init_method()) { return 0; } - return pmbtoken_client_key_from_bytes(&method, key, in, len); + return pmbtoken_client_key_from_bytes(&pmbtoken_exp1_method, key, in, len); } int pmbtoken_exp1_issuer_key_from_bytes(PMBTOKEN_ISSUER_KEY *key, const uint8_t *in, size_t len) { - PMBTOKEN_METHOD method; - if (!pmbtoken_exp1_init_method(&method)) { + if (!pmbtoken_exp1_init_method()) { return 0; } - return pmbtoken_issuer_key_from_bytes(&method, key, in, len); + return pmbtoken_issuer_key_from_bytes(&pmbtoken_exp1_method, key, in, len); } STACK_OF(PMBTOKEN_PRETOKEN) * pmbtoken_exp1_blind(CBB *cbb, size_t count) { - PMBTOKEN_METHOD method; - if (!pmbtoken_exp1_init_method(&method)) { + if (!pmbtoken_exp1_init_method()) { return NULL; } - return pmbtoken_blind(&method, cbb, count); + return pmbtoken_blind(&pmbtoken_exp1_method, cbb, count); } int pmbtoken_exp1_sign(const PMBTOKEN_ISSUER_KEY *key, CBB *cbb, CBS *cbs, size_t num_requested, size_t num_to_issue, uint8_t private_metadata) { - PMBTOKEN_METHOD method; - if (!pmbtoken_exp1_init_method(&method)) { + if (!pmbtoken_exp1_init_method()) { return 0; } - return pmbtoken_sign(&method, key, cbb, cbs, num_requested, num_to_issue, - private_metadata); + return pmbtoken_sign(&pmbtoken_exp1_method, key, cbb, cbs, num_requested, + num_to_issue, private_metadata); } STACK_OF(TRUST_TOKEN) * pmbtoken_exp1_unblind(const PMBTOKEN_CLIENT_KEY *key, - const STACK_OF(PMBTOKEN_PRETOKEN) *pretokens, + const STACK_OF(PMBTOKEN_PRETOKEN) * pretokens, CBS *cbs, size_t count, uint32_t key_id) { - PMBTOKEN_METHOD method; - if (!pmbtoken_exp1_init_method(&method)) { + if (!pmbtoken_exp1_init_method()) { return NULL; } - return pmbtoken_unblind(&method, key, pretokens, cbs, count, key_id); + return pmbtoken_unblind(&pmbtoken_exp1_method, key, pretokens, cbs, count, + key_id); } int pmbtoken_exp1_read(const PMBTOKEN_ISSUER_KEY *key, uint8_t out_nonce[PMBTOKEN_NONCE_SIZE], uint8_t *out_private_metadata, const uint8_t *token, size_t token_len) { - PMBTOKEN_METHOD method; - if (!pmbtoken_exp1_init_method(&method)) { + if (!pmbtoken_exp1_init_method()) { return 0; } - return pmbtoken_read(&method, key, out_nonce, out_private_metadata, token, - token_len); + return pmbtoken_read(&pmbtoken_exp1_method, key, out_nonce, + out_private_metadata, token, token_len); } int pmbtoken_exp1_get_h_for_testing(uint8_t out[97]) { - PMBTOKEN_METHOD method; - if (!pmbtoken_exp1_init_method(&method)) { + if (!pmbtoken_exp1_init_method()) { return 0; } EC_AFFINE h; - return ec_jacobian_to_affine(method.group, &h, &method.h) && - ec_point_to_bytes(method.group, &h, POINT_CONVERSION_UNCOMPRESSED, out, - 97) == 97; + return ec_jacobian_to_affine(pmbtoken_exp1_method.group, &h, + &pmbtoken_exp1_method.h) && + ec_point_to_bytes(pmbtoken_exp1_method.group, &h, + POINT_CONVERSION_UNCOMPRESSED, out, 97) == 97; }