1/* 2 * Copyright 2001-2021 The OpenSSL Project Authors. All Rights Reserved. 3 * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved 4 * 5 * Licensed under the Apache License 2.0 (the "License"). You may not use 6 * this file except in compliance with the License. You can obtain a copy 7 * in the file LICENSE in the source distribution or at 8 * https://www.openssl.org/source/license.html 9 */ 10 11/* 12 * ECDSA low level APIs are deprecated for public use, but still ok for 13 * internal use. 14 */ 15#include "internal/deprecated.h" 16 17#include <string.h> 18#include <openssl/err.h> 19 20#include "internal/cryptlib.h" 21#include "crypto/bn.h" 22#include "ec_local.h" 23#include "internal/refcount.h" 24 25/* 26 * This file implements the wNAF-based interleaving multi-exponentiation method 27 * Formerly at: 28 * http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp 29 * You might now find it here: 30 * http://link.springer.com/chapter/10.1007%2F3-540-45537-X_13 31 * http://www.bmoeller.de/pdf/TI-01-08.multiexp.pdf 32 * For multiplication with precomputation, we use wNAF splitting, formerly at: 33 * http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp 34 */ 35 36/* structure for precomputed multiples of the generator */ 37struct ec_pre_comp_st { 38 const EC_GROUP *group; /* parent EC_GROUP object */ 39 size_t blocksize; /* block size for wNAF splitting */ 40 size_t numblocks; /* max. number of blocks for which we have 41 * precomputation */ 42 size_t w; /* window size */ 43 EC_POINT **points; /* array with pre-calculated multiples of 44 * generator: 'num' pointers to EC_POINT 45 * objects followed by a NULL */ 46 size_t num; /* numblocks * 2^(w-1) */ 47 CRYPTO_REF_COUNT references; 48 CRYPTO_RWLOCK *lock; 49}; 50 51static EC_PRE_COMP *ec_pre_comp_new(const EC_GROUP *group) 52{ 53 EC_PRE_COMP *ret = NULL; 54 55 if (!group) 56 return NULL; 57 58 ret = OPENSSL_zalloc(sizeof(*ret)); 59 if (ret == NULL) { 60 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 61 return ret; 62 } 63 64 ret->group = group; 65 ret->blocksize = 8; /* default */ 66 ret->w = 4; /* default */ 67 ret->references = 1; 68 69 ret->lock = CRYPTO_THREAD_lock_new(); 70 if (ret->lock == NULL) { 71 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 72 OPENSSL_free(ret); 73 return NULL; 74 } 75 return ret; 76} 77 78EC_PRE_COMP *EC_ec_pre_comp_dup(EC_PRE_COMP *pre) 79{ 80 int i; 81 if (pre != NULL) 82 CRYPTO_UP_REF(&pre->references, &i, pre->lock); 83 return pre; 84} 85 86void EC_ec_pre_comp_free(EC_PRE_COMP *pre) 87{ 88 int i; 89 90 if (pre == NULL) 91 return; 92 93 CRYPTO_DOWN_REF(&pre->references, &i, pre->lock); 94 REF_PRINT_COUNT("EC_ec", pre); 95 if (i > 0) 96 return; 97 REF_ASSERT_ISNT(i < 0); 98 99 if (pre->points != NULL) { 100 EC_POINT **pts; 101 102 for (pts = pre->points; *pts != NULL; pts++) 103 EC_POINT_free(*pts); 104 OPENSSL_free(pre->points); 105 } 106 CRYPTO_THREAD_lock_free(pre->lock); 107 OPENSSL_free(pre); 108} 109 110#define EC_POINT_BN_set_flags(P, flags) do { \ 111 BN_set_flags((P)->X, (flags)); \ 112 BN_set_flags((P)->Y, (flags)); \ 113 BN_set_flags((P)->Z, (flags)); \ 114} while(0) 115 116/*- 117 * This functions computes a single point multiplication over the EC group, 118 * using, at a high level, a Montgomery ladder with conditional swaps, with 119 * various timing attack defenses. 120 * 121 * It performs either a fixed point multiplication 122 * (scalar * generator) 123 * when point is NULL, or a variable point multiplication 124 * (scalar * point) 125 * when point is not NULL. 126 * 127 * `scalar` cannot be NULL and should be in the range [0,n) otherwise all 128 * constant time bets are off (where n is the cardinality of the EC group). 129 * 130 * This function expects `group->order` and `group->cardinality` to be well 131 * defined and non-zero: it fails with an error code otherwise. 132 * 133 * NB: This says nothing about the constant-timeness of the ladder step 134 * implementation (i.e., the default implementation is based on EC_POINT_add and 135 * EC_POINT_dbl, which of course are not constant time themselves) or the 136 * underlying multiprecision arithmetic. 137 * 138 * The product is stored in `r`. 139 * 140 * This is an internal function: callers are in charge of ensuring that the 141 * input parameters `group`, `r`, `scalar` and `ctx` are not NULL. 142 * 143 * Returns 1 on success, 0 otherwise. 144 */ 145int ossl_ec_scalar_mul_ladder(const EC_GROUP *group, EC_POINT *r, 146 const BIGNUM *scalar, const EC_POINT *point, 147 BN_CTX *ctx) 148{ 149 int i, cardinality_bits, group_top, kbit, pbit, Z_is_one; 150 EC_POINT *p = NULL; 151 EC_POINT *s = NULL; 152 BIGNUM *k = NULL; 153 BIGNUM *lambda = NULL; 154 BIGNUM *cardinality = NULL; 155 int ret = 0; 156 157 /* early exit if the input point is the point at infinity */ 158 if (point != NULL && EC_POINT_is_at_infinity(group, point)) 159 return EC_POINT_set_to_infinity(group, r); 160 161 if (BN_is_zero(group->order)) { 162 ERR_raise(ERR_LIB_EC, EC_R_UNKNOWN_ORDER); 163 return 0; 164 } 165 if (BN_is_zero(group->cofactor)) { 166 ERR_raise(ERR_LIB_EC, EC_R_UNKNOWN_COFACTOR); 167 return 0; 168 } 169 170 BN_CTX_start(ctx); 171 172 if (((p = EC_POINT_new(group)) == NULL) 173 || ((s = EC_POINT_new(group)) == NULL)) { 174 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 175 goto err; 176 } 177 178 if (point == NULL) { 179 if (!EC_POINT_copy(p, group->generator)) { 180 ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB); 181 goto err; 182 } 183 } else { 184 if (!EC_POINT_copy(p, point)) { 185 ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB); 186 goto err; 187 } 188 } 189 190 EC_POINT_BN_set_flags(p, BN_FLG_CONSTTIME); 191 EC_POINT_BN_set_flags(r, BN_FLG_CONSTTIME); 192 EC_POINT_BN_set_flags(s, BN_FLG_CONSTTIME); 193 194 cardinality = BN_CTX_get(ctx); 195 lambda = BN_CTX_get(ctx); 196 k = BN_CTX_get(ctx); 197 if (k == NULL) { 198 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 199 goto err; 200 } 201 202 if (!BN_mul(cardinality, group->order, group->cofactor, ctx)) { 203 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 204 goto err; 205 } 206 207 /* 208 * Group cardinalities are often on a word boundary. 209 * So when we pad the scalar, some timing diff might 210 * pop if it needs to be expanded due to carries. 211 * So expand ahead of time. 212 */ 213 cardinality_bits = BN_num_bits(cardinality); 214 group_top = bn_get_top(cardinality); 215 if ((bn_wexpand(k, group_top + 2) == NULL) 216 || (bn_wexpand(lambda, group_top + 2) == NULL)) { 217 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 218 goto err; 219 } 220 221 if (!BN_copy(k, scalar)) { 222 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 223 goto err; 224 } 225 226 BN_set_flags(k, BN_FLG_CONSTTIME); 227 228 if ((BN_num_bits(k) > cardinality_bits) || (BN_is_negative(k))) { 229 /*- 230 * this is an unusual input, and we don't guarantee 231 * constant-timeness 232 */ 233 if (!BN_nnmod(k, k, cardinality, ctx)) { 234 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 235 goto err; 236 } 237 } 238 239 if (!BN_add(lambda, k, cardinality)) { 240 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 241 goto err; 242 } 243 BN_set_flags(lambda, BN_FLG_CONSTTIME); 244 if (!BN_add(k, lambda, cardinality)) { 245 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 246 goto err; 247 } 248 /* 249 * lambda := scalar + cardinality 250 * k := scalar + 2*cardinality 251 */ 252 kbit = BN_is_bit_set(lambda, cardinality_bits); 253 BN_consttime_swap(kbit, k, lambda, group_top + 2); 254 255 group_top = bn_get_top(group->field); 256 if ((bn_wexpand(s->X, group_top) == NULL) 257 || (bn_wexpand(s->Y, group_top) == NULL) 258 || (bn_wexpand(s->Z, group_top) == NULL) 259 || (bn_wexpand(r->X, group_top) == NULL) 260 || (bn_wexpand(r->Y, group_top) == NULL) 261 || (bn_wexpand(r->Z, group_top) == NULL) 262 || (bn_wexpand(p->X, group_top) == NULL) 263 || (bn_wexpand(p->Y, group_top) == NULL) 264 || (bn_wexpand(p->Z, group_top) == NULL)) { 265 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 266 goto err; 267 } 268 269 /* ensure input point is in affine coords for ladder step efficiency */ 270 if (!p->Z_is_one && (group->meth->make_affine == NULL 271 || !group->meth->make_affine(group, p, ctx))) { 272 ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB); 273 goto err; 274 } 275 276 /* Initialize the Montgomery ladder */ 277 if (!ec_point_ladder_pre(group, r, s, p, ctx)) { 278 ERR_raise(ERR_LIB_EC, EC_R_LADDER_PRE_FAILURE); 279 goto err; 280 } 281 282 /* top bit is a 1, in a fixed pos */ 283 pbit = 1; 284 285#define EC_POINT_CSWAP(c, a, b, w, t) do { \ 286 BN_consttime_swap(c, (a)->X, (b)->X, w); \ 287 BN_consttime_swap(c, (a)->Y, (b)->Y, w); \ 288 BN_consttime_swap(c, (a)->Z, (b)->Z, w); \ 289 t = ((a)->Z_is_one ^ (b)->Z_is_one) & (c); \ 290 (a)->Z_is_one ^= (t); \ 291 (b)->Z_is_one ^= (t); \ 292} while(0) 293 294 /*- 295 * The ladder step, with branches, is 296 * 297 * k[i] == 0: S = add(R, S), R = dbl(R) 298 * k[i] == 1: R = add(S, R), S = dbl(S) 299 * 300 * Swapping R, S conditionally on k[i] leaves you with state 301 * 302 * k[i] == 0: T, U = R, S 303 * k[i] == 1: T, U = S, R 304 * 305 * Then perform the ECC ops. 306 * 307 * U = add(T, U) 308 * T = dbl(T) 309 * 310 * Which leaves you with state 311 * 312 * k[i] == 0: U = add(R, S), T = dbl(R) 313 * k[i] == 1: U = add(S, R), T = dbl(S) 314 * 315 * Swapping T, U conditionally on k[i] leaves you with state 316 * 317 * k[i] == 0: R, S = T, U 318 * k[i] == 1: R, S = U, T 319 * 320 * Which leaves you with state 321 * 322 * k[i] == 0: S = add(R, S), R = dbl(R) 323 * k[i] == 1: R = add(S, R), S = dbl(S) 324 * 325 * So we get the same logic, but instead of a branch it's a 326 * conditional swap, followed by ECC ops, then another conditional swap. 327 * 328 * Optimization: The end of iteration i and start of i-1 looks like 329 * 330 * ... 331 * CSWAP(k[i], R, S) 332 * ECC 333 * CSWAP(k[i], R, S) 334 * (next iteration) 335 * CSWAP(k[i-1], R, S) 336 * ECC 337 * CSWAP(k[i-1], R, S) 338 * ... 339 * 340 * So instead of two contiguous swaps, you can merge the condition 341 * bits and do a single swap. 342 * 343 * k[i] k[i-1] Outcome 344 * 0 0 No Swap 345 * 0 1 Swap 346 * 1 0 Swap 347 * 1 1 No Swap 348 * 349 * This is XOR. pbit tracks the previous bit of k. 350 */ 351 352 for (i = cardinality_bits - 1; i >= 0; i--) { 353 kbit = BN_is_bit_set(k, i) ^ pbit; 354 EC_POINT_CSWAP(kbit, r, s, group_top, Z_is_one); 355 356 /* Perform a single step of the Montgomery ladder */ 357 if (!ec_point_ladder_step(group, r, s, p, ctx)) { 358 ERR_raise(ERR_LIB_EC, EC_R_LADDER_STEP_FAILURE); 359 goto err; 360 } 361 /* 362 * pbit logic merges this cswap with that of the 363 * next iteration 364 */ 365 pbit ^= kbit; 366 } 367 /* one final cswap to move the right value into r */ 368 EC_POINT_CSWAP(pbit, r, s, group_top, Z_is_one); 369#undef EC_POINT_CSWAP 370 371 /* Finalize ladder (and recover full point coordinates) */ 372 if (!ec_point_ladder_post(group, r, s, p, ctx)) { 373 ERR_raise(ERR_LIB_EC, EC_R_LADDER_POST_FAILURE); 374 goto err; 375 } 376 377 ret = 1; 378 379 err: 380 EC_POINT_free(p); 381 EC_POINT_clear_free(s); 382 BN_CTX_end(ctx); 383 384 return ret; 385} 386 387#undef EC_POINT_BN_set_flags 388 389/* 390 * Table could be optimised for the wNAF-based implementation, 391 * sometimes smaller windows will give better performance (thus the 392 * boundaries should be increased) 393 */ 394#define EC_window_bits_for_scalar_size(b) \ 395 ((size_t) \ 396 ((b) >= 2000 ? 6 : \ 397 (b) >= 800 ? 5 : \ 398 (b) >= 300 ? 4 : \ 399 (b) >= 70 ? 3 : \ 400 (b) >= 20 ? 2 : \ 401 1)) 402 403/*- 404 * Compute 405 * \sum scalars[i]*points[i], 406 * also including 407 * scalar*generator 408 * in the addition if scalar != NULL 409 */ 410int ossl_ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 411 size_t num, const EC_POINT *points[], 412 const BIGNUM *scalars[], BN_CTX *ctx) 413{ 414 const EC_POINT *generator = NULL; 415 EC_POINT *tmp = NULL; 416 size_t totalnum; 417 size_t blocksize = 0, numblocks = 0; /* for wNAF splitting */ 418 size_t pre_points_per_block = 0; 419 size_t i, j; 420 int k; 421 int r_is_inverted = 0; 422 int r_is_at_infinity = 1; 423 size_t *wsize = NULL; /* individual window sizes */ 424 signed char **wNAF = NULL; /* individual wNAFs */ 425 size_t *wNAF_len = NULL; 426 size_t max_len = 0; 427 size_t num_val; 428 EC_POINT **val = NULL; /* precomputation */ 429 EC_POINT **v; 430 EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' or 431 * 'pre_comp->points' */ 432 const EC_PRE_COMP *pre_comp = NULL; 433 int num_scalar = 0; /* flag: will be set to 1 if 'scalar' must be 434 * treated like other scalars, i.e. 435 * precomputation is not available */ 436 int ret = 0; 437 438 if (!BN_is_zero(group->order) && !BN_is_zero(group->cofactor)) { 439 /*- 440 * Handle the common cases where the scalar is secret, enforcing a 441 * scalar multiplication implementation based on a Montgomery ladder, 442 * with various timing attack defenses. 443 */ 444 if ((scalar != group->order) && (scalar != NULL) && (num == 0)) { 445 /*- 446 * In this case we want to compute scalar * GeneratorPoint: this 447 * codepath is reached most prominently by (ephemeral) key 448 * generation of EC cryptosystems (i.e. ECDSA keygen and sign setup, 449 * ECDH keygen/first half), where the scalar is always secret. This 450 * is why we ignore if BN_FLG_CONSTTIME is actually set and we 451 * always call the ladder version. 452 */ 453 return ossl_ec_scalar_mul_ladder(group, r, scalar, NULL, ctx); 454 } 455 if ((scalar == NULL) && (num == 1) && (scalars[0] != group->order)) { 456 /*- 457 * In this case we want to compute scalar * VariablePoint: this 458 * codepath is reached most prominently by the second half of ECDH, 459 * where the secret scalar is multiplied by the peer's public point. 460 * To protect the secret scalar, we ignore if BN_FLG_CONSTTIME is 461 * actually set and we always call the ladder version. 462 */ 463 return ossl_ec_scalar_mul_ladder(group, r, scalars[0], points[0], 464 ctx); 465 } 466 } 467 468 if (scalar != NULL) { 469 generator = EC_GROUP_get0_generator(group); 470 if (generator == NULL) { 471 ERR_raise(ERR_LIB_EC, EC_R_UNDEFINED_GENERATOR); 472 goto err; 473 } 474 475 /* look if we can use precomputed multiples of generator */ 476 477 pre_comp = group->pre_comp.ec; 478 if (pre_comp && pre_comp->numblocks 479 && (EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) == 480 0)) { 481 blocksize = pre_comp->blocksize; 482 483 /* 484 * determine maximum number of blocks that wNAF splitting may 485 * yield (NB: maximum wNAF length is bit length plus one) 486 */ 487 numblocks = (BN_num_bits(scalar) / blocksize) + 1; 488 489 /* 490 * we cannot use more blocks than we have precomputation for 491 */ 492 if (numblocks > pre_comp->numblocks) 493 numblocks = pre_comp->numblocks; 494 495 pre_points_per_block = (size_t)1 << (pre_comp->w - 1); 496 497 /* check that pre_comp looks sane */ 498 if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block)) { 499 ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR); 500 goto err; 501 } 502 } else { 503 /* can't use precomputation */ 504 pre_comp = NULL; 505 numblocks = 1; 506 num_scalar = 1; /* treat 'scalar' like 'num'-th element of 507 * 'scalars' */ 508 } 509 } 510 511 totalnum = num + numblocks; 512 513 wsize = OPENSSL_malloc(totalnum * sizeof(wsize[0])); 514 wNAF_len = OPENSSL_malloc(totalnum * sizeof(wNAF_len[0])); 515 /* include space for pivot */ 516 wNAF = OPENSSL_malloc((totalnum + 1) * sizeof(wNAF[0])); 517 val_sub = OPENSSL_malloc(totalnum * sizeof(val_sub[0])); 518 519 /* Ensure wNAF is initialised in case we end up going to err */ 520 if (wNAF != NULL) 521 wNAF[0] = NULL; /* preliminary pivot */ 522 523 if (wsize == NULL || wNAF_len == NULL || wNAF == NULL || val_sub == NULL) { 524 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 525 goto err; 526 } 527 528 /* 529 * num_val will be the total number of temporarily precomputed points 530 */ 531 num_val = 0; 532 533 for (i = 0; i < num + num_scalar; i++) { 534 size_t bits; 535 536 bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar); 537 wsize[i] = EC_window_bits_for_scalar_size(bits); 538 num_val += (size_t)1 << (wsize[i] - 1); 539 wNAF[i + 1] = NULL; /* make sure we always have a pivot */ 540 wNAF[i] = 541 bn_compute_wNAF((i < num ? scalars[i] : scalar), wsize[i], 542 &wNAF_len[i]); 543 if (wNAF[i] == NULL) 544 goto err; 545 if (wNAF_len[i] > max_len) 546 max_len = wNAF_len[i]; 547 } 548 549 if (numblocks) { 550 /* we go here iff scalar != NULL */ 551 552 if (pre_comp == NULL) { 553 if (num_scalar != 1) { 554 ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR); 555 goto err; 556 } 557 /* we have already generated a wNAF for 'scalar' */ 558 } else { 559 signed char *tmp_wNAF = NULL; 560 size_t tmp_len = 0; 561 562 if (num_scalar != 0) { 563 ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR); 564 goto err; 565 } 566 567 /* 568 * use the window size for which we have precomputation 569 */ 570 wsize[num] = pre_comp->w; 571 tmp_wNAF = bn_compute_wNAF(scalar, wsize[num], &tmp_len); 572 if (!tmp_wNAF) 573 goto err; 574 575 if (tmp_len <= max_len) { 576 /* 577 * One of the other wNAFs is at least as long as the wNAF 578 * belonging to the generator, so wNAF splitting will not buy 579 * us anything. 580 */ 581 582 numblocks = 1; 583 totalnum = num + 1; /* don't use wNAF splitting */ 584 wNAF[num] = tmp_wNAF; 585 wNAF[num + 1] = NULL; 586 wNAF_len[num] = tmp_len; 587 /* 588 * pre_comp->points starts with the points that we need here: 589 */ 590 val_sub[num] = pre_comp->points; 591 } else { 592 /* 593 * don't include tmp_wNAF directly into wNAF array - use wNAF 594 * splitting and include the blocks 595 */ 596 597 signed char *pp; 598 EC_POINT **tmp_points; 599 600 if (tmp_len < numblocks * blocksize) { 601 /* 602 * possibly we can do with fewer blocks than estimated 603 */ 604 numblocks = (tmp_len + blocksize - 1) / blocksize; 605 if (numblocks > pre_comp->numblocks) { 606 ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR); 607 OPENSSL_free(tmp_wNAF); 608 goto err; 609 } 610 totalnum = num + numblocks; 611 } 612 613 /* split wNAF in 'numblocks' parts */ 614 pp = tmp_wNAF; 615 tmp_points = pre_comp->points; 616 617 for (i = num; i < totalnum; i++) { 618 if (i < totalnum - 1) { 619 wNAF_len[i] = blocksize; 620 if (tmp_len < blocksize) { 621 ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR); 622 OPENSSL_free(tmp_wNAF); 623 goto err; 624 } 625 tmp_len -= blocksize; 626 } else 627 /* 628 * last block gets whatever is left (this could be 629 * more or less than 'blocksize'!) 630 */ 631 wNAF_len[i] = tmp_len; 632 633 wNAF[i + 1] = NULL; 634 wNAF[i] = OPENSSL_malloc(wNAF_len[i]); 635 if (wNAF[i] == NULL) { 636 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 637 OPENSSL_free(tmp_wNAF); 638 goto err; 639 } 640 memcpy(wNAF[i], pp, wNAF_len[i]); 641 if (wNAF_len[i] > max_len) 642 max_len = wNAF_len[i]; 643 644 if (*tmp_points == NULL) { 645 ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR); 646 OPENSSL_free(tmp_wNAF); 647 goto err; 648 } 649 val_sub[i] = tmp_points; 650 tmp_points += pre_points_per_block; 651 pp += blocksize; 652 } 653 OPENSSL_free(tmp_wNAF); 654 } 655 } 656 } 657 658 /* 659 * All points we precompute now go into a single array 'val'. 660 * 'val_sub[i]' is a pointer to the subarray for the i-th point, or to a 661 * subarray of 'pre_comp->points' if we already have precomputation. 662 */ 663 val = OPENSSL_malloc((num_val + 1) * sizeof(val[0])); 664 if (val == NULL) { 665 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 666 goto err; 667 } 668 val[num_val] = NULL; /* pivot element */ 669 670 /* allocate points for precomputation */ 671 v = val; 672 for (i = 0; i < num + num_scalar; i++) { 673 val_sub[i] = v; 674 for (j = 0; j < ((size_t)1 << (wsize[i] - 1)); j++) { 675 *v = EC_POINT_new(group); 676 if (*v == NULL) 677 goto err; 678 v++; 679 } 680 } 681 if (!(v == val + num_val)) { 682 ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR); 683 goto err; 684 } 685 686 if ((tmp = EC_POINT_new(group)) == NULL) 687 goto err; 688 689 /*- 690 * prepare precomputed values: 691 * val_sub[i][0] := points[i] 692 * val_sub[i][1] := 3 * points[i] 693 * val_sub[i][2] := 5 * points[i] 694 * ... 695 */ 696 for (i = 0; i < num + num_scalar; i++) { 697 if (i < num) { 698 if (!EC_POINT_copy(val_sub[i][0], points[i])) 699 goto err; 700 } else { 701 if (!EC_POINT_copy(val_sub[i][0], generator)) 702 goto err; 703 } 704 705 if (wsize[i] > 1) { 706 if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) 707 goto err; 708 for (j = 1; j < ((size_t)1 << (wsize[i] - 1)); j++) { 709 if (!EC_POINT_add 710 (group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) 711 goto err; 712 } 713 } 714 } 715 716 if (group->meth->points_make_affine == NULL 717 || !group->meth->points_make_affine(group, num_val, val, ctx)) 718 goto err; 719 720 r_is_at_infinity = 1; 721 722 for (k = max_len - 1; k >= 0; k--) { 723 if (!r_is_at_infinity) { 724 if (!EC_POINT_dbl(group, r, r, ctx)) 725 goto err; 726 } 727 728 for (i = 0; i < totalnum; i++) { 729 if (wNAF_len[i] > (size_t)k) { 730 int digit = wNAF[i][k]; 731 int is_neg; 732 733 if (digit) { 734 is_neg = digit < 0; 735 736 if (is_neg) 737 digit = -digit; 738 739 if (is_neg != r_is_inverted) { 740 if (!r_is_at_infinity) { 741 if (!EC_POINT_invert(group, r, ctx)) 742 goto err; 743 } 744 r_is_inverted = !r_is_inverted; 745 } 746 747 /* digit > 0 */ 748 749 if (r_is_at_infinity) { 750 if (!EC_POINT_copy(r, val_sub[i][digit >> 1])) 751 goto err; 752 753 /*- 754 * Apply coordinate blinding for EC_POINT. 755 * 756 * The underlying EC_METHOD can optionally implement this function: 757 * ossl_ec_point_blind_coordinates() returns 0 in case of errors or 1 on 758 * success or if coordinate blinding is not implemented for this 759 * group. 760 */ 761 if (!ossl_ec_point_blind_coordinates(group, r, ctx)) { 762 ERR_raise(ERR_LIB_EC, EC_R_POINT_COORDINATES_BLIND_FAILURE); 763 goto err; 764 } 765 766 r_is_at_infinity = 0; 767 } else { 768 if (!EC_POINT_add 769 (group, r, r, val_sub[i][digit >> 1], ctx)) 770 goto err; 771 } 772 } 773 } 774 } 775 } 776 777 if (r_is_at_infinity) { 778 if (!EC_POINT_set_to_infinity(group, r)) 779 goto err; 780 } else { 781 if (r_is_inverted) 782 if (!EC_POINT_invert(group, r, ctx)) 783 goto err; 784 } 785 786 ret = 1; 787 788 err: 789 EC_POINT_free(tmp); 790 OPENSSL_free(wsize); 791 OPENSSL_free(wNAF_len); 792 if (wNAF != NULL) { 793 signed char **w; 794 795 for (w = wNAF; *w != NULL; w++) 796 OPENSSL_free(*w); 797 798 OPENSSL_free(wNAF); 799 } 800 if (val != NULL) { 801 for (v = val; *v != NULL; v++) 802 EC_POINT_clear_free(*v); 803 804 OPENSSL_free(val); 805 } 806 OPENSSL_free(val_sub); 807 return ret; 808} 809 810/*- 811 * ossl_ec_wNAF_precompute_mult() 812 * creates an EC_PRE_COMP object with preprecomputed multiples of the generator 813 * for use with wNAF splitting as implemented in ossl_ec_wNAF_mul(). 814 * 815 * 'pre_comp->points' is an array of multiples of the generator 816 * of the following form: 817 * points[0] = generator; 818 * points[1] = 3 * generator; 819 * ... 820 * points[2^(w-1)-1] = (2^(w-1)-1) * generator; 821 * points[2^(w-1)] = 2^blocksize * generator; 822 * points[2^(w-1)+1] = 3 * 2^blocksize * generator; 823 * ... 824 * points[2^(w-1)*(numblocks-1)-1] = (2^(w-1)) * 2^(blocksize*(numblocks-2)) * generator 825 * points[2^(w-1)*(numblocks-1)] = 2^(blocksize*(numblocks-1)) * generator 826 * ... 827 * points[2^(w-1)*numblocks-1] = (2^(w-1)) * 2^(blocksize*(numblocks-1)) * generator 828 * points[2^(w-1)*numblocks] = NULL 829 */ 830int ossl_ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx) 831{ 832 const EC_POINT *generator; 833 EC_POINT *tmp_point = NULL, *base = NULL, **var; 834 const BIGNUM *order; 835 size_t i, bits, w, pre_points_per_block, blocksize, numblocks, num; 836 EC_POINT **points = NULL; 837 EC_PRE_COMP *pre_comp; 838 int ret = 0; 839 int used_ctx = 0; 840#ifndef FIPS_MODULE 841 BN_CTX *new_ctx = NULL; 842#endif 843 844 /* if there is an old EC_PRE_COMP object, throw it away */ 845 EC_pre_comp_free(group); 846 if ((pre_comp = ec_pre_comp_new(group)) == NULL) 847 return 0; 848 849 generator = EC_GROUP_get0_generator(group); 850 if (generator == NULL) { 851 ERR_raise(ERR_LIB_EC, EC_R_UNDEFINED_GENERATOR); 852 goto err; 853 } 854 855#ifndef FIPS_MODULE 856 if (ctx == NULL) 857 ctx = new_ctx = BN_CTX_new(); 858#endif 859 if (ctx == NULL) 860 goto err; 861 862 BN_CTX_start(ctx); 863 used_ctx = 1; 864 865 order = EC_GROUP_get0_order(group); 866 if (order == NULL) 867 goto err; 868 if (BN_is_zero(order)) { 869 ERR_raise(ERR_LIB_EC, EC_R_UNKNOWN_ORDER); 870 goto err; 871 } 872 873 bits = BN_num_bits(order); 874 /* 875 * The following parameters mean we precompute (approximately) one point 876 * per bit. TBD: The combination 8, 4 is perfect for 160 bits; for other 877 * bit lengths, other parameter combinations might provide better 878 * efficiency. 879 */ 880 blocksize = 8; 881 w = 4; 882 if (EC_window_bits_for_scalar_size(bits) > w) { 883 /* let's not make the window too small ... */ 884 w = EC_window_bits_for_scalar_size(bits); 885 } 886 887 numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks 888 * to use for wNAF 889 * splitting */ 890 891 pre_points_per_block = (size_t)1 << (w - 1); 892 num = pre_points_per_block * numblocks; /* number of points to compute 893 * and store */ 894 895 points = OPENSSL_malloc(sizeof(*points) * (num + 1)); 896 if (points == NULL) { 897 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 898 goto err; 899 } 900 901 var = points; 902 var[num] = NULL; /* pivot */ 903 for (i = 0; i < num; i++) { 904 if ((var[i] = EC_POINT_new(group)) == NULL) { 905 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 906 goto err; 907 } 908 } 909 910 if ((tmp_point = EC_POINT_new(group)) == NULL 911 || (base = EC_POINT_new(group)) == NULL) { 912 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 913 goto err; 914 } 915 916 if (!EC_POINT_copy(base, generator)) 917 goto err; 918 919 /* do the precomputation */ 920 for (i = 0; i < numblocks; i++) { 921 size_t j; 922 923 if (!EC_POINT_dbl(group, tmp_point, base, ctx)) 924 goto err; 925 926 if (!EC_POINT_copy(*var++, base)) 927 goto err; 928 929 for (j = 1; j < pre_points_per_block; j++, var++) { 930 /* 931 * calculate odd multiples of the current base point 932 */ 933 if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx)) 934 goto err; 935 } 936 937 if (i < numblocks - 1) { 938 /* 939 * get the next base (multiply current one by 2^blocksize) 940 */ 941 size_t k; 942 943 if (blocksize <= 2) { 944 ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR); 945 goto err; 946 } 947 948 if (!EC_POINT_dbl(group, base, tmp_point, ctx)) 949 goto err; 950 for (k = 2; k < blocksize; k++) { 951 if (!EC_POINT_dbl(group, base, base, ctx)) 952 goto err; 953 } 954 } 955 } 956 957 if (group->meth->points_make_affine == NULL 958 || !group->meth->points_make_affine(group, num, points, ctx)) 959 goto err; 960 961 pre_comp->group = group; 962 pre_comp->blocksize = blocksize; 963 pre_comp->numblocks = numblocks; 964 pre_comp->w = w; 965 pre_comp->points = points; 966 points = NULL; 967 pre_comp->num = num; 968 SETPRECOMP(group, ec, pre_comp); 969 pre_comp = NULL; 970 ret = 1; 971 972 err: 973 if (used_ctx) 974 BN_CTX_end(ctx); 975#ifndef FIPS_MODULE 976 BN_CTX_free(new_ctx); 977#endif 978 EC_ec_pre_comp_free(pre_comp); 979 if (points) { 980 EC_POINT **p; 981 982 for (p = points; *p != NULL; p++) 983 EC_POINT_free(*p); 984 OPENSSL_free(points); 985 } 986 EC_POINT_free(tmp_point); 987 EC_POINT_free(base); 988 return ret; 989} 990 991int ossl_ec_wNAF_have_precompute_mult(const EC_GROUP *group) 992{ 993 return HAVEPRECOMP(group, ec); 994} 995