1 /* 2 * Elliptic curves over GF(p): generic functions 3 * 4 * Copyright The Mbed TLS Contributors 5 * SPDX-License-Identifier: Apache-2.0 6 * 7 * Licensed under the Apache License, Version 2.0 (the "License"); you may 8 * not use this file except in compliance with the License. 9 * You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, software 14 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 15 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16 * See the License for the specific language governing permissions and 17 * limitations under the License. 18 */ 19 20 /* 21 * References: 22 * 23 * SEC1 http://www.secg.org/index.php?action=secg,docs_secg 24 * GECC = Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone 25 * FIPS 186-3 http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf 26 * RFC 4492 for the related TLS structures and constants 27 * RFC 7748 for the Curve448 and Curve25519 curve definitions 28 * 29 * [Curve25519] http://cr.yp.to/ecdh/curve25519-20060209.pdf 30 * 31 * [2] CORON, Jean-S'ebastien. Resistance against differential power analysis 32 * for elliptic curve cryptosystems. In : Cryptographic Hardware and 33 * Embedded Systems. Springer Berlin Heidelberg, 1999. p. 292-302. 34 * <http://link.springer.com/chapter/10.1007/3-540-48059-5_25> 35 * 36 * [3] HEDABOU, Mustapha, PINEL, Pierre, et B'EN'ETEAU, Lucien. A comb method to 37 * render ECC resistant against Side Channel Attacks. IACR Cryptology 38 * ePrint Archive, 2004, vol. 2004, p. 342. 39 * <http://eprint.iacr.org/2004/342.pdf> 40 */ 41 42 #include "common.h" 43 44 /** 45 * \brief Function level alternative implementation. 46 * 47 * The MBEDTLS_ECP_INTERNAL_ALT macro enables alternative implementations to 48 * replace certain functions in this module. The alternative implementations are 49 * typically hardware accelerators and need to activate the hardware before the 50 * computation starts and deactivate it after it finishes. The 51 * mbedtls_internal_ecp_init() and mbedtls_internal_ecp_free() functions serve 52 * this purpose. 53 * 54 * To preserve the correct functionality the following conditions must hold: 55 * 56 * - The alternative implementation must be activated by 57 * mbedtls_internal_ecp_init() before any of the replaceable functions is 58 * called. 59 * - mbedtls_internal_ecp_free() must \b only be called when the alternative 60 * implementation is activated. 61 * - mbedtls_internal_ecp_init() must \b not be called when the alternative 62 * implementation is activated. 63 * - Public functions must not return while the alternative implementation is 64 * activated. 65 * - Replaceable functions are guarded by \c MBEDTLS_ECP_XXX_ALT macros and 66 * before calling them an \code if( mbedtls_internal_ecp_grp_capable( grp ) ) 67 * \endcode ensures that the alternative implementation supports the current 68 * group. 69 */ 70 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 71 #endif 72 73 #if defined(MBEDTLS_ECP_C) 74 75 #include "mbedtls/ecp.h" 76 #include "mbedtls/threading.h" 77 #include "mbedtls/platform_util.h" 78 #include "mbedtls/error.h" 79 80 #include "bn_mul.h" 81 #include "ecp_invasive.h" 82 83 #include <string.h> 84 85 #if !defined(MBEDTLS_ECP_ALT) 86 87 #include "mbedtls/platform.h" 88 89 #include "ecp_internal_alt.h" 90 91 #if defined(MBEDTLS_SELF_TEST) 92 /* 93 * Counts of point addition and doubling, and field multiplications. 94 * Used to test resistance of point multiplication to simple timing attacks. 95 */ 96 static unsigned long add_count, dbl_count, mul_count; 97 #endif 98 99 #if defined(MBEDTLS_ECP_RESTARTABLE) 100 /* 101 * Maximum number of "basic operations" to be done in a row. 102 * 103 * Default value 0 means that ECC operations will not yield. 104 * Note that regardless of the value of ecp_max_ops, always at 105 * least one step is performed before yielding. 106 * 107 * Setting ecp_max_ops=1 can be suitable for testing purposes 108 * as it will interrupt computation at all possible points. 109 */ 110 static unsigned ecp_max_ops = 0; 111 112 /* 113 * Set ecp_max_ops 114 */ 115 void mbedtls_ecp_set_max_ops(unsigned max_ops) 116 { 117 ecp_max_ops = max_ops; 118 } 119 120 /* 121 * Check if restart is enabled 122 */ 123 int mbedtls_ecp_restart_is_enabled(void) 124 { 125 return ecp_max_ops != 0; 126 } 127 128 /* 129 * Restart sub-context for ecp_mul_comb() 130 */ 131 struct mbedtls_ecp_restart_mul { 132 mbedtls_ecp_point R; /* current intermediate result */ 133 size_t i; /* current index in various loops, 0 outside */ 134 mbedtls_ecp_point *T; /* table for precomputed points */ 135 unsigned char T_size; /* number of points in table T */ 136 enum { /* what were we doing last time we returned? */ 137 ecp_rsm_init = 0, /* nothing so far, dummy initial state */ 138 ecp_rsm_pre_dbl, /* precompute 2^n multiples */ 139 ecp_rsm_pre_norm_dbl, /* normalize precomputed 2^n multiples */ 140 ecp_rsm_pre_add, /* precompute remaining points by adding */ 141 ecp_rsm_pre_norm_add, /* normalize all precomputed points */ 142 ecp_rsm_comb_core, /* ecp_mul_comb_core() */ 143 ecp_rsm_final_norm, /* do the final normalization */ 144 } state; 145 }; 146 147 /* 148 * Init restart_mul sub-context 149 */ 150 static void ecp_restart_rsm_init(mbedtls_ecp_restart_mul_ctx *ctx) 151 { 152 mbedtls_ecp_point_init(&ctx->R); 153 ctx->i = 0; 154 ctx->T = NULL; 155 ctx->T_size = 0; 156 ctx->state = ecp_rsm_init; 157 } 158 159 /* 160 * Free the components of a restart_mul sub-context 161 */ 162 static void ecp_restart_rsm_free(mbedtls_ecp_restart_mul_ctx *ctx) 163 { 164 unsigned char i; 165 166 if (ctx == NULL) { 167 return; 168 } 169 170 mbedtls_ecp_point_free(&ctx->R); 171 172 if (ctx->T != NULL) { 173 for (i = 0; i < ctx->T_size; i++) { 174 mbedtls_ecp_point_free(ctx->T + i); 175 } 176 mbedtls_free(ctx->T); 177 } 178 179 ecp_restart_rsm_init(ctx); 180 } 181 182 /* 183 * Restart context for ecp_muladd() 184 */ 185 struct mbedtls_ecp_restart_muladd { 186 mbedtls_ecp_point mP; /* mP value */ 187 mbedtls_ecp_point R; /* R intermediate result */ 188 enum { /* what should we do next? */ 189 ecp_rsma_mul1 = 0, /* first multiplication */ 190 ecp_rsma_mul2, /* second multiplication */ 191 ecp_rsma_add, /* addition */ 192 ecp_rsma_norm, /* normalization */ 193 } state; 194 }; 195 196 /* 197 * Init restart_muladd sub-context 198 */ 199 static void ecp_restart_ma_init(mbedtls_ecp_restart_muladd_ctx *ctx) 200 { 201 mbedtls_ecp_point_init(&ctx->mP); 202 mbedtls_ecp_point_init(&ctx->R); 203 ctx->state = ecp_rsma_mul1; 204 } 205 206 /* 207 * Free the components of a restart_muladd sub-context 208 */ 209 static void ecp_restart_ma_free(mbedtls_ecp_restart_muladd_ctx *ctx) 210 { 211 if (ctx == NULL) { 212 return; 213 } 214 215 mbedtls_ecp_point_free(&ctx->mP); 216 mbedtls_ecp_point_free(&ctx->R); 217 218 ecp_restart_ma_init(ctx); 219 } 220 221 /* 222 * Initialize a restart context 223 */ 224 void mbedtls_ecp_restart_init(mbedtls_ecp_restart_ctx *ctx) 225 { 226 ctx->ops_done = 0; 227 ctx->depth = 0; 228 ctx->rsm = NULL; 229 ctx->ma = NULL; 230 } 231 232 /* 233 * Free the components of a restart context 234 */ 235 void mbedtls_ecp_restart_free(mbedtls_ecp_restart_ctx *ctx) 236 { 237 if (ctx == NULL) { 238 return; 239 } 240 241 ecp_restart_rsm_free(ctx->rsm); 242 mbedtls_free(ctx->rsm); 243 244 ecp_restart_ma_free(ctx->ma); 245 mbedtls_free(ctx->ma); 246 247 mbedtls_ecp_restart_init(ctx); 248 } 249 250 /* 251 * Check if we can do the next step 252 */ 253 int mbedtls_ecp_check_budget(const mbedtls_ecp_group *grp, 254 mbedtls_ecp_restart_ctx *rs_ctx, 255 unsigned ops) 256 { 257 if (rs_ctx != NULL && ecp_max_ops != 0) { 258 /* scale depending on curve size: the chosen reference is 256-bit, 259 * and multiplication is quadratic. Round to the closest integer. */ 260 if (grp->pbits >= 512) { 261 ops *= 4; 262 } else if (grp->pbits >= 384) { 263 ops *= 2; 264 } 265 266 /* Avoid infinite loops: always allow first step. 267 * Because of that, however, it's not generally true 268 * that ops_done <= ecp_max_ops, so the check 269 * ops_done > ecp_max_ops below is mandatory. */ 270 if ((rs_ctx->ops_done != 0) && 271 (rs_ctx->ops_done > ecp_max_ops || 272 ops > ecp_max_ops - rs_ctx->ops_done)) { 273 return MBEDTLS_ERR_ECP_IN_PROGRESS; 274 } 275 276 /* update running count */ 277 rs_ctx->ops_done += ops; 278 } 279 280 return 0; 281 } 282 283 /* Call this when entering a function that needs its own sub-context */ 284 #define ECP_RS_ENTER(SUB) do { \ 285 /* reset ops count for this call if top-level */ \ 286 if (rs_ctx != NULL && rs_ctx->depth++ == 0) \ 287 rs_ctx->ops_done = 0; \ 288 \ 289 /* set up our own sub-context if needed */ \ 290 if (mbedtls_ecp_restart_is_enabled() && \ 291 rs_ctx != NULL && rs_ctx->SUB == NULL) \ 292 { \ 293 rs_ctx->SUB = mbedtls_calloc(1, sizeof(*rs_ctx->SUB)); \ 294 if (rs_ctx->SUB == NULL) \ 295 return MBEDTLS_ERR_ECP_ALLOC_FAILED; \ 296 \ 297 ecp_restart_## SUB ##_init(rs_ctx->SUB); \ 298 } \ 299 } while (0) 300 301 /* Call this when leaving a function that needs its own sub-context */ 302 #define ECP_RS_LEAVE(SUB) do { \ 303 /* clear our sub-context when not in progress (done or error) */ \ 304 if (rs_ctx != NULL && rs_ctx->SUB != NULL && \ 305 ret != MBEDTLS_ERR_ECP_IN_PROGRESS) \ 306 { \ 307 ecp_restart_## SUB ##_free(rs_ctx->SUB); \ 308 mbedtls_free(rs_ctx->SUB); \ 309 rs_ctx->SUB = NULL; \ 310 } \ 311 \ 312 if (rs_ctx != NULL) \ 313 rs_ctx->depth--; \ 314 } while (0) 315 316 #else /* MBEDTLS_ECP_RESTARTABLE */ 317 318 #define ECP_RS_ENTER(sub) (void) rs_ctx; 319 #define ECP_RS_LEAVE(sub) (void) rs_ctx; 320 321 #endif /* MBEDTLS_ECP_RESTARTABLE */ 322 323 static void mpi_init_many(mbedtls_mpi *arr, size_t size) 324 { 325 while (size--) { 326 mbedtls_mpi_init(arr++); 327 } 328 } 329 330 static void mpi_free_many(mbedtls_mpi *arr, size_t size) 331 { 332 while (size--) { 333 mbedtls_mpi_free(arr++); 334 } 335 } 336 337 /* 338 * List of supported curves: 339 * - internal ID 340 * - TLS NamedCurve ID (RFC 4492 sec. 5.1.1, RFC 7071 sec. 2, RFC 8446 sec. 4.2.7) 341 * - size in bits 342 * - readable name 343 * 344 * Curves are listed in order: largest curves first, and for a given size, 345 * fastest curves first. 346 * 347 * Reminder: update profiles in x509_crt.c and ssl_tls.c when adding a new curve! 348 */ 349 static const mbedtls_ecp_curve_info ecp_supported_curves[] = 350 { 351 #if defined(MBEDTLS_ECP_DP_SECP521R1_ENABLED) 352 { MBEDTLS_ECP_DP_SECP521R1, 25, 521, "secp521r1" }, 353 #endif 354 #if defined(MBEDTLS_ECP_DP_BP512R1_ENABLED) 355 { MBEDTLS_ECP_DP_BP512R1, 28, 512, "brainpoolP512r1" }, 356 #endif 357 #if defined(MBEDTLS_ECP_DP_SECP384R1_ENABLED) 358 { MBEDTLS_ECP_DP_SECP384R1, 24, 384, "secp384r1" }, 359 #endif 360 #if defined(MBEDTLS_ECP_DP_BP384R1_ENABLED) 361 { MBEDTLS_ECP_DP_BP384R1, 27, 384, "brainpoolP384r1" }, 362 #endif 363 #if defined(MBEDTLS_ECP_DP_SECP256R1_ENABLED) 364 { MBEDTLS_ECP_DP_SECP256R1, 23, 256, "secp256r1" }, 365 #endif 366 #if defined(MBEDTLS_ECP_DP_SECP256K1_ENABLED) 367 { MBEDTLS_ECP_DP_SECP256K1, 22, 256, "secp256k1" }, 368 #endif 369 #if defined(MBEDTLS_ECP_DP_BP256R1_ENABLED) 370 { MBEDTLS_ECP_DP_BP256R1, 26, 256, "brainpoolP256r1" }, 371 #endif 372 #if defined(MBEDTLS_ECP_DP_SECP224R1_ENABLED) 373 { MBEDTLS_ECP_DP_SECP224R1, 21, 224, "secp224r1" }, 374 #endif 375 #if defined(MBEDTLS_ECP_DP_SECP224K1_ENABLED) 376 { MBEDTLS_ECP_DP_SECP224K1, 20, 224, "secp224k1" }, 377 #endif 378 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) 379 { MBEDTLS_ECP_DP_SECP192R1, 19, 192, "secp192r1" }, 380 #endif 381 #if defined(MBEDTLS_ECP_DP_SECP192K1_ENABLED) 382 { MBEDTLS_ECP_DP_SECP192K1, 18, 192, "secp192k1" }, 383 #endif 384 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) 385 { MBEDTLS_ECP_DP_CURVE25519, 29, 256, "x25519" }, 386 #endif 387 #if defined(MBEDTLS_ECP_DP_CURVE448_ENABLED) 388 { MBEDTLS_ECP_DP_CURVE448, 30, 448, "x448" }, 389 #endif 390 #if defined(MBEDTLS_ECP_DP_SM2_ENABLED) 391 /* https://tools.ietf.org/id/draft-yang-tls-tls13-sm-suites-05.html */ 392 { MBEDTLS_ECP_DP_SM2, 41, 256, "sm2" }, 393 #endif 394 { MBEDTLS_ECP_DP_NONE, 0, 0, NULL }, 395 }; 396 397 #define ECP_NB_CURVES sizeof(ecp_supported_curves) / \ 398 sizeof(ecp_supported_curves[0]) 399 400 static mbedtls_ecp_group_id ecp_supported_grp_id[ECP_NB_CURVES]; 401 402 /* 403 * List of supported curves and associated info 404 */ 405 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_list(void) 406 { 407 return ecp_supported_curves; 408 } 409 410 /* 411 * List of supported curves, group ID only 412 */ 413 const mbedtls_ecp_group_id *mbedtls_ecp_grp_id_list(void) 414 { 415 static int init_done = 0; 416 417 if (!init_done) { 418 size_t i = 0; 419 const mbedtls_ecp_curve_info *curve_info; 420 421 for (curve_info = mbedtls_ecp_curve_list(); 422 curve_info->grp_id != MBEDTLS_ECP_DP_NONE; 423 curve_info++) { 424 ecp_supported_grp_id[i++] = curve_info->grp_id; 425 } 426 ecp_supported_grp_id[i] = MBEDTLS_ECP_DP_NONE; 427 428 init_done = 1; 429 } 430 431 return ecp_supported_grp_id; 432 } 433 434 /* 435 * Get the curve info for the internal identifier 436 */ 437 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_grp_id(mbedtls_ecp_group_id grp_id) 438 { 439 const mbedtls_ecp_curve_info *curve_info; 440 441 for (curve_info = mbedtls_ecp_curve_list(); 442 curve_info->grp_id != MBEDTLS_ECP_DP_NONE; 443 curve_info++) { 444 if (curve_info->grp_id == grp_id) { 445 return curve_info; 446 } 447 } 448 449 return NULL; 450 } 451 452 /* 453 * Get the curve info from the TLS identifier 454 */ 455 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_tls_id(uint16_t tls_id) 456 { 457 const mbedtls_ecp_curve_info *curve_info; 458 459 for (curve_info = mbedtls_ecp_curve_list(); 460 curve_info->grp_id != MBEDTLS_ECP_DP_NONE; 461 curve_info++) { 462 if (curve_info->tls_id == tls_id) { 463 return curve_info; 464 } 465 } 466 467 return NULL; 468 } 469 470 /* 471 * Get the curve info from the name 472 */ 473 const mbedtls_ecp_curve_info *mbedtls_ecp_curve_info_from_name(const char *name) 474 { 475 const mbedtls_ecp_curve_info *curve_info; 476 477 if (name == NULL) { 478 return NULL; 479 } 480 481 for (curve_info = mbedtls_ecp_curve_list(); 482 curve_info->grp_id != MBEDTLS_ECP_DP_NONE; 483 curve_info++) { 484 if (strcmp(curve_info->name, name) == 0) { 485 return curve_info; 486 } 487 } 488 489 return NULL; 490 } 491 492 /* 493 * Get the type of a curve 494 */ 495 mbedtls_ecp_curve_type mbedtls_ecp_get_type(const mbedtls_ecp_group *grp) 496 { 497 if (grp->G.X.p == NULL) { 498 return MBEDTLS_ECP_TYPE_NONE; 499 } 500 501 if (grp->G.Y.p == NULL) { 502 return MBEDTLS_ECP_TYPE_MONTGOMERY; 503 } else { 504 return MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS; 505 } 506 } 507 508 /* 509 * Initialize (the components of) a point 510 */ 511 void mbedtls_ecp_point_init(mbedtls_ecp_point *pt) 512 { 513 mbedtls_mpi_init(&pt->X); 514 mbedtls_mpi_init(&pt->Y); 515 mbedtls_mpi_init(&pt->Z); 516 } 517 518 /* 519 * Initialize (the components of) a group 520 */ 521 void mbedtls_ecp_group_init(mbedtls_ecp_group *grp) 522 { 523 grp->id = MBEDTLS_ECP_DP_NONE; 524 mbedtls_mpi_init(&grp->P); 525 mbedtls_mpi_init(&grp->A); 526 mbedtls_mpi_init(&grp->B); 527 mbedtls_ecp_point_init(&grp->G); 528 mbedtls_mpi_init(&grp->N); 529 grp->pbits = 0; 530 grp->nbits = 0; 531 grp->h = 0; 532 grp->modp = NULL; 533 grp->t_pre = NULL; 534 grp->t_post = NULL; 535 grp->t_data = NULL; 536 grp->T = NULL; 537 grp->T_size = 0; 538 } 539 540 /* 541 * Initialize (the components of) a key pair 542 */ 543 void mbedtls_ecp_keypair_init(mbedtls_ecp_keypair *key) 544 { 545 mbedtls_ecp_group_init(&key->grp); 546 mbedtls_mpi_init(&key->d); 547 mbedtls_ecp_point_init(&key->Q); 548 } 549 550 /* 551 * Unallocate (the components of) a point 552 */ 553 void mbedtls_ecp_point_free(mbedtls_ecp_point *pt) 554 { 555 if (pt == NULL) { 556 return; 557 } 558 559 mbedtls_mpi_free(&(pt->X)); 560 mbedtls_mpi_free(&(pt->Y)); 561 mbedtls_mpi_free(&(pt->Z)); 562 } 563 564 /* 565 * Check that the comb table (grp->T) is static initialized. 566 */ 567 static int ecp_group_is_static_comb_table(const mbedtls_ecp_group *grp) 568 { 569 #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1 570 return grp->T != NULL && grp->T_size == 0; 571 #else 572 (void) grp; 573 return 0; 574 #endif 575 } 576 577 /* 578 * Unallocate (the components of) a group 579 */ 580 void mbedtls_ecp_group_free(mbedtls_ecp_group *grp) 581 { 582 size_t i; 583 584 if (grp == NULL) { 585 return; 586 } 587 588 if (grp->h != 1) { 589 mbedtls_mpi_free(&grp->A); 590 mbedtls_mpi_free(&grp->B); 591 mbedtls_ecp_point_free(&grp->G); 592 } 593 594 if (!ecp_group_is_static_comb_table(grp) && grp->T != NULL) { 595 for (i = 0; i < grp->T_size; i++) { 596 mbedtls_ecp_point_free(&grp->T[i]); 597 } 598 mbedtls_free(grp->T); 599 } 600 601 mbedtls_platform_zeroize(grp, sizeof(mbedtls_ecp_group)); 602 } 603 604 /* 605 * Unallocate (the components of) a key pair 606 */ 607 void mbedtls_ecp_keypair_free(mbedtls_ecp_keypair *key) 608 { 609 if (key == NULL) { 610 return; 611 } 612 613 mbedtls_ecp_group_free(&key->grp); 614 mbedtls_mpi_free(&key->d); 615 mbedtls_ecp_point_free(&key->Q); 616 } 617 618 /* 619 * Copy the contents of a point 620 */ 621 int mbedtls_ecp_copy(mbedtls_ecp_point *P, const mbedtls_ecp_point *Q) 622 { 623 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 624 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&P->X, &Q->X)); 625 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&P->Y, &Q->Y)); 626 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&P->Z, &Q->Z)); 627 628 cleanup: 629 return ret; 630 } 631 632 /* 633 * Copy the contents of a group object 634 */ 635 int mbedtls_ecp_group_copy(mbedtls_ecp_group *dst, const mbedtls_ecp_group *src) 636 { 637 return mbedtls_ecp_group_load(dst, src->id); 638 } 639 640 /* 641 * Set point to zero 642 */ 643 int mbedtls_ecp_set_zero(mbedtls_ecp_point *pt) 644 { 645 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 646 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->X, 1)); 647 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Y, 1)); 648 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Z, 0)); 649 650 cleanup: 651 return ret; 652 } 653 654 /* 655 * Tell if a point is zero 656 */ 657 int mbedtls_ecp_is_zero(mbedtls_ecp_point *pt) 658 { 659 return mbedtls_mpi_cmp_int(&pt->Z, 0) == 0; 660 } 661 662 /* 663 * Compare two points lazily 664 */ 665 int mbedtls_ecp_point_cmp(const mbedtls_ecp_point *P, 666 const mbedtls_ecp_point *Q) 667 { 668 if (mbedtls_mpi_cmp_mpi(&P->X, &Q->X) == 0 && 669 mbedtls_mpi_cmp_mpi(&P->Y, &Q->Y) == 0 && 670 mbedtls_mpi_cmp_mpi(&P->Z, &Q->Z) == 0) { 671 return 0; 672 } 673 674 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 675 } 676 677 /* 678 * Import a non-zero point from ASCII strings 679 */ 680 int mbedtls_ecp_point_read_string(mbedtls_ecp_point *P, int radix, 681 const char *x, const char *y) 682 { 683 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 684 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&P->X, radix, x)); 685 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&P->Y, radix, y)); 686 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&P->Z, 1)); 687 688 cleanup: 689 return ret; 690 } 691 692 /* 693 * Export a point into unsigned binary data (SEC1 2.3.3 and RFC7748) 694 */ 695 int mbedtls_ecp_point_write_binary(const mbedtls_ecp_group *grp, 696 const mbedtls_ecp_point *P, 697 int format, size_t *olen, 698 unsigned char *buf, size_t buflen) 699 { 700 int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 701 size_t plen; 702 if (format != MBEDTLS_ECP_PF_UNCOMPRESSED && 703 format != MBEDTLS_ECP_PF_COMPRESSED) { 704 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 705 } 706 707 plen = mbedtls_mpi_size(&grp->P); 708 709 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 710 (void) format; /* Montgomery curves always use the same point format */ 711 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) { 712 *olen = plen; 713 if (buflen < *olen) { 714 return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL; 715 } 716 717 MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary_le(&P->X, buf, plen)); 718 } 719 #endif 720 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 721 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) { 722 /* 723 * Common case: P == 0 724 */ 725 if (mbedtls_mpi_cmp_int(&P->Z, 0) == 0) { 726 if (buflen < 1) { 727 return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL; 728 } 729 730 buf[0] = 0x00; 731 *olen = 1; 732 733 return 0; 734 } 735 736 if (format == MBEDTLS_ECP_PF_UNCOMPRESSED) { 737 *olen = 2 * plen + 1; 738 739 if (buflen < *olen) { 740 return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL; 741 } 742 743 buf[0] = 0x04; 744 MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&P->X, buf + 1, plen)); 745 MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&P->Y, buf + 1 + plen, plen)); 746 } else if (format == MBEDTLS_ECP_PF_COMPRESSED) { 747 *olen = plen + 1; 748 749 if (buflen < *olen) { 750 return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL; 751 } 752 753 buf[0] = 0x02 + mbedtls_mpi_get_bit(&P->Y, 0); 754 MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&P->X, buf + 1, plen)); 755 } 756 } 757 #endif 758 759 cleanup: 760 return ret; 761 } 762 763 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 764 static int mbedtls_ecp_sw_derive_y(const mbedtls_ecp_group *grp, 765 const mbedtls_mpi *X, 766 mbedtls_mpi *Y, 767 int parity_bit); 768 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 769 770 /* 771 * Import a point from unsigned binary data (SEC1 2.3.4 and RFC7748) 772 */ 773 int mbedtls_ecp_point_read_binary(const mbedtls_ecp_group *grp, 774 mbedtls_ecp_point *pt, 775 const unsigned char *buf, size_t ilen) 776 { 777 int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 778 size_t plen; 779 if (ilen < 1) { 780 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 781 } 782 783 plen = mbedtls_mpi_size(&grp->P); 784 785 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 786 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) { 787 if (plen != ilen) { 788 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 789 } 790 791 MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary_le(&pt->X, buf, plen)); 792 mbedtls_mpi_free(&pt->Y); 793 794 if (grp->id == MBEDTLS_ECP_DP_CURVE25519) { 795 /* Set most significant bit to 0 as prescribed in RFC7748 §5 */ 796 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&pt->X, plen * 8 - 1, 0)); 797 } 798 799 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Z, 1)); 800 } 801 #endif 802 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 803 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) { 804 if (buf[0] == 0x00) { 805 if (ilen == 1) { 806 return mbedtls_ecp_set_zero(pt); 807 } else { 808 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 809 } 810 } 811 812 if (ilen < 1 + plen) { 813 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 814 } 815 816 MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary(&pt->X, buf + 1, plen)); 817 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&pt->Z, 1)); 818 819 if (buf[0] == 0x04) { 820 /* format == MBEDTLS_ECP_PF_UNCOMPRESSED */ 821 if (ilen != 1 + plen * 2) { 822 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 823 } 824 return mbedtls_mpi_read_binary(&pt->Y, buf + 1 + plen, plen); 825 } else if (buf[0] == 0x02 || buf[0] == 0x03) { 826 /* format == MBEDTLS_ECP_PF_COMPRESSED */ 827 if (ilen != 1 + plen) { 828 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 829 } 830 return mbedtls_ecp_sw_derive_y(grp, &pt->X, &pt->Y, 831 (buf[0] & 1)); 832 } else { 833 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 834 } 835 } 836 #endif 837 838 cleanup: 839 return ret; 840 } 841 842 /* 843 * Import a point from a TLS ECPoint record (RFC 4492) 844 * struct { 845 * opaque point <1..2^8-1>; 846 * } ECPoint; 847 */ 848 int mbedtls_ecp_tls_read_point(const mbedtls_ecp_group *grp, 849 mbedtls_ecp_point *pt, 850 const unsigned char **buf, size_t buf_len) 851 { 852 unsigned char data_len; 853 const unsigned char *buf_start; 854 /* 855 * We must have at least two bytes (1 for length, at least one for data) 856 */ 857 if (buf_len < 2) { 858 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 859 } 860 861 data_len = *(*buf)++; 862 if (data_len < 1 || data_len > buf_len - 1) { 863 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 864 } 865 866 /* 867 * Save buffer start for read_binary and update buf 868 */ 869 buf_start = *buf; 870 *buf += data_len; 871 872 return mbedtls_ecp_point_read_binary(grp, pt, buf_start, data_len); 873 } 874 875 /* 876 * Export a point as a TLS ECPoint record (RFC 4492) 877 * struct { 878 * opaque point <1..2^8-1>; 879 * } ECPoint; 880 */ 881 int mbedtls_ecp_tls_write_point(const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt, 882 int format, size_t *olen, 883 unsigned char *buf, size_t blen) 884 { 885 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 886 if (format != MBEDTLS_ECP_PF_UNCOMPRESSED && 887 format != MBEDTLS_ECP_PF_COMPRESSED) { 888 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 889 } 890 891 /* 892 * buffer length must be at least one, for our length byte 893 */ 894 if (blen < 1) { 895 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 896 } 897 898 if ((ret = mbedtls_ecp_point_write_binary(grp, pt, format, 899 olen, buf + 1, blen - 1)) != 0) { 900 return ret; 901 } 902 903 /* 904 * write length to the first byte and update total length 905 */ 906 buf[0] = (unsigned char) *olen; 907 ++*olen; 908 909 return 0; 910 } 911 912 /* 913 * Set a group from an ECParameters record (RFC 4492) 914 */ 915 int mbedtls_ecp_tls_read_group(mbedtls_ecp_group *grp, 916 const unsigned char **buf, size_t len) 917 { 918 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 919 mbedtls_ecp_group_id grp_id; 920 if ((ret = mbedtls_ecp_tls_read_group_id(&grp_id, buf, len)) != 0) { 921 return ret; 922 } 923 924 return mbedtls_ecp_group_load(grp, grp_id); 925 } 926 927 /* 928 * Read a group id from an ECParameters record (RFC 4492) and convert it to 929 * mbedtls_ecp_group_id. 930 */ 931 int mbedtls_ecp_tls_read_group_id(mbedtls_ecp_group_id *grp, 932 const unsigned char **buf, size_t len) 933 { 934 uint16_t tls_id; 935 const mbedtls_ecp_curve_info *curve_info; 936 /* 937 * We expect at least three bytes (see below) 938 */ 939 if (len < 3) { 940 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 941 } 942 943 /* 944 * First byte is curve_type; only named_curve is handled 945 */ 946 if (*(*buf)++ != MBEDTLS_ECP_TLS_NAMED_CURVE) { 947 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 948 } 949 950 /* 951 * Next two bytes are the namedcurve value 952 */ 953 tls_id = *(*buf)++; 954 tls_id <<= 8; 955 tls_id |= *(*buf)++; 956 957 if ((curve_info = mbedtls_ecp_curve_info_from_tls_id(tls_id)) == NULL) { 958 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 959 } 960 961 *grp = curve_info->grp_id; 962 963 return 0; 964 } 965 966 /* 967 * Write the ECParameters record corresponding to a group (RFC 4492) 968 */ 969 int mbedtls_ecp_tls_write_group(const mbedtls_ecp_group *grp, size_t *olen, 970 unsigned char *buf, size_t blen) 971 { 972 const mbedtls_ecp_curve_info *curve_info; 973 if ((curve_info = mbedtls_ecp_curve_info_from_grp_id(grp->id)) == NULL) { 974 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 975 } 976 977 /* 978 * We are going to write 3 bytes (see below) 979 */ 980 *olen = 3; 981 if (blen < *olen) { 982 return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL; 983 } 984 985 /* 986 * First byte is curve_type, always named_curve 987 */ 988 *buf++ = MBEDTLS_ECP_TLS_NAMED_CURVE; 989 990 /* 991 * Next two bytes are the namedcurve value 992 */ 993 MBEDTLS_PUT_UINT16_BE(curve_info->tls_id, buf, 0); 994 995 return 0; 996 } 997 998 /* 999 * Wrapper around fast quasi-modp functions, with fall-back to mbedtls_mpi_mod_mpi. 1000 * See the documentation of struct mbedtls_ecp_group. 1001 * 1002 * This function is in the critial loop for mbedtls_ecp_mul, so pay attention to perf. 1003 */ 1004 static int ecp_modp(mbedtls_mpi *N, const mbedtls_ecp_group *grp) 1005 { 1006 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1007 1008 if (grp->modp == NULL) { 1009 return mbedtls_mpi_mod_mpi(N, N, &grp->P); 1010 } 1011 1012 /* N->s < 0 is a much faster test, which fails only if N is 0 */ 1013 if ((N->s < 0 && mbedtls_mpi_cmp_int(N, 0) != 0) || 1014 mbedtls_mpi_bitlen(N) > 2 * grp->pbits) { 1015 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 1016 } 1017 1018 MBEDTLS_MPI_CHK(grp->modp(N)); 1019 1020 /* N->s < 0 is a much faster test, which fails only if N is 0 */ 1021 while (N->s < 0 && mbedtls_mpi_cmp_int(N, 0) != 0) { 1022 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(N, N, &grp->P)); 1023 } 1024 1025 while (mbedtls_mpi_cmp_mpi(N, &grp->P) >= 0) { 1026 /* we known P, N and the result are positive */ 1027 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(N, N, &grp->P)); 1028 } 1029 1030 cleanup: 1031 return ret; 1032 } 1033 1034 /* 1035 * Fast mod-p functions expect their argument to be in the 0..p^2 range. 1036 * 1037 * In order to guarantee that, we need to ensure that operands of 1038 * mbedtls_mpi_mul_mpi are in the 0..p range. So, after each operation we will 1039 * bring the result back to this range. 1040 * 1041 * The following macros are shortcuts for doing that. 1042 */ 1043 1044 /* 1045 * Reduce a mbedtls_mpi mod p in-place, general case, to use after mbedtls_mpi_mul_mpi 1046 */ 1047 #if defined(MBEDTLS_SELF_TEST) 1048 #define INC_MUL_COUNT mul_count++; 1049 #else 1050 #define INC_MUL_COUNT 1051 #endif 1052 1053 #define MOD_MUL(N) \ 1054 do \ 1055 { \ 1056 MBEDTLS_MPI_CHK(ecp_modp(&(N), grp)); \ 1057 INC_MUL_COUNT \ 1058 } while (0) 1059 1060 static inline int mbedtls_mpi_mul_mod(const mbedtls_ecp_group *grp, 1061 mbedtls_mpi *X, 1062 const mbedtls_mpi *A, 1063 const mbedtls_mpi *B) 1064 { 1065 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1066 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(X, A, B)); 1067 MOD_MUL(*X); 1068 cleanup: 1069 return ret; 1070 } 1071 1072 /* 1073 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_sub_mpi 1074 * N->s < 0 is a very fast test, which fails only if N is 0 1075 */ 1076 #define MOD_SUB(N) \ 1077 do { \ 1078 while ((N)->s < 0 && mbedtls_mpi_cmp_int((N), 0) != 0) \ 1079 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi((N), (N), &grp->P)); \ 1080 } while (0) 1081 1082 #if (defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) && \ 1083 !(defined(MBEDTLS_ECP_NO_FALLBACK) && \ 1084 defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) && \ 1085 defined(MBEDTLS_ECP_ADD_MIXED_ALT))) || \ 1086 (defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) && \ 1087 !(defined(MBEDTLS_ECP_NO_FALLBACK) && \ 1088 defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT))) 1089 static inline int mbedtls_mpi_sub_mod(const mbedtls_ecp_group *grp, 1090 mbedtls_mpi *X, 1091 const mbedtls_mpi *A, 1092 const mbedtls_mpi *B) 1093 { 1094 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1095 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(X, A, B)); 1096 MOD_SUB(X); 1097 cleanup: 1098 return ret; 1099 } 1100 #endif /* All functions referencing mbedtls_mpi_sub_mod() are alt-implemented without fallback */ 1101 1102 /* 1103 * Reduce a mbedtls_mpi mod p in-place, to use after mbedtls_mpi_add_mpi and mbedtls_mpi_mul_int. 1104 * We known P, N and the result are positive, so sub_abs is correct, and 1105 * a bit faster. 1106 */ 1107 #define MOD_ADD(N) \ 1108 while (mbedtls_mpi_cmp_mpi((N), &grp->P) >= 0) \ 1109 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs((N), (N), &grp->P)) 1110 1111 static inline int mbedtls_mpi_add_mod(const mbedtls_ecp_group *grp, 1112 mbedtls_mpi *X, 1113 const mbedtls_mpi *A, 1114 const mbedtls_mpi *B) 1115 { 1116 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1117 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(X, A, B)); 1118 MOD_ADD(X); 1119 cleanup: 1120 return ret; 1121 } 1122 1123 static inline int mbedtls_mpi_mul_int_mod(const mbedtls_ecp_group *grp, 1124 mbedtls_mpi *X, 1125 const mbedtls_mpi *A, 1126 mbedtls_mpi_uint c) 1127 { 1128 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1129 1130 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(X, A, c)); 1131 MOD_ADD(X); 1132 cleanup: 1133 return ret; 1134 } 1135 1136 static inline int mbedtls_mpi_sub_int_mod(const mbedtls_ecp_group *grp, 1137 mbedtls_mpi *X, 1138 const mbedtls_mpi *A, 1139 mbedtls_mpi_uint c) 1140 { 1141 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1142 1143 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(X, A, c)); 1144 MOD_SUB(X); 1145 cleanup: 1146 return ret; 1147 } 1148 1149 #define MPI_ECP_SUB_INT(X, A, c) \ 1150 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int_mod(grp, X, A, c)) 1151 1152 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) && \ 1153 !(defined(MBEDTLS_ECP_NO_FALLBACK) && \ 1154 defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) && \ 1155 defined(MBEDTLS_ECP_ADD_MIXED_ALT)) 1156 static inline int mbedtls_mpi_shift_l_mod(const mbedtls_ecp_group *grp, 1157 mbedtls_mpi *X, 1158 size_t count) 1159 { 1160 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1161 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(X, count)); 1162 MOD_ADD(X); 1163 cleanup: 1164 return ret; 1165 } 1166 #endif \ 1167 /* All functions referencing mbedtls_mpi_shift_l_mod() are alt-implemented without fallback */ 1168 1169 /* 1170 * Macro wrappers around ECP modular arithmetic 1171 * 1172 * Currently, these wrappers are defined via the bignum module. 1173 */ 1174 1175 #define MPI_ECP_ADD(X, A, B) \ 1176 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mod(grp, X, A, B)) 1177 1178 #define MPI_ECP_SUB(X, A, B) \ 1179 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mod(grp, X, A, B)) 1180 1181 #define MPI_ECP_MUL(X, A, B) \ 1182 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, X, A, B)) 1183 1184 #define MPI_ECP_SQR(X, A) \ 1185 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mod(grp, X, A, A)) 1186 1187 #define MPI_ECP_MUL_INT(X, A, c) \ 1188 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int_mod(grp, X, A, c)) 1189 1190 #define MPI_ECP_INV(dst, src) \ 1191 MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod((dst), (src), &grp->P)) 1192 1193 #define MPI_ECP_MOV(X, A) \ 1194 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A)) 1195 1196 #define MPI_ECP_SHIFT_L(X, count) \ 1197 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l_mod(grp, X, count)) 1198 1199 #define MPI_ECP_LSET(X, c) \ 1200 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, c)) 1201 1202 #define MPI_ECP_CMP_INT(X, c) \ 1203 mbedtls_mpi_cmp_int(X, c) 1204 1205 #define MPI_ECP_CMP(X, Y) \ 1206 mbedtls_mpi_cmp_mpi(X, Y) 1207 1208 /* Needs f_rng, p_rng to be defined. */ 1209 #define MPI_ECP_RAND(X) \ 1210 MBEDTLS_MPI_CHK(mbedtls_mpi_random((X), 2, &grp->P, f_rng, p_rng)) 1211 1212 /* Conditional negation 1213 * Needs grp and a temporary MPI tmp to be defined. */ 1214 #define MPI_ECP_COND_NEG(X, cond) \ 1215 do \ 1216 { \ 1217 unsigned char nonzero = mbedtls_mpi_cmp_int((X), 0) != 0; \ 1218 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&tmp, &grp->P, (X))); \ 1219 MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign((X), &tmp, \ 1220 nonzero & cond)); \ 1221 } while (0) 1222 1223 #define MPI_ECP_NEG(X) MPI_ECP_COND_NEG((X), 1) 1224 1225 #define MPI_ECP_VALID(X) \ 1226 ((X)->p != NULL) 1227 1228 #define MPI_ECP_COND_ASSIGN(X, Y, cond) \ 1229 MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign((X), (Y), (cond))) 1230 1231 #define MPI_ECP_COND_SWAP(X, Y, cond) \ 1232 MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_swap((X), (Y), (cond))) 1233 1234 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 1235 1236 /* 1237 * Computes the right-hand side of the Short Weierstrass equation 1238 * RHS = X^3 + A X + B 1239 */ 1240 static int ecp_sw_rhs(const mbedtls_ecp_group *grp, 1241 mbedtls_mpi *rhs, 1242 const mbedtls_mpi *X) 1243 { 1244 int ret; 1245 1246 /* Compute X^3 + A X + B as X (X^2 + A) + B */ 1247 MPI_ECP_SQR(rhs, X); 1248 1249 /* Special case for A = -3 */ 1250 if (grp->A.p == NULL) { 1251 MPI_ECP_SUB_INT(rhs, rhs, 3); 1252 } else { 1253 MPI_ECP_ADD(rhs, rhs, &grp->A); 1254 } 1255 1256 MPI_ECP_MUL(rhs, rhs, X); 1257 MPI_ECP_ADD(rhs, rhs, &grp->B); 1258 1259 cleanup: 1260 return ret; 1261 } 1262 1263 /* 1264 * Derive Y from X and a parity bit 1265 */ 1266 static int mbedtls_ecp_sw_derive_y(const mbedtls_ecp_group *grp, 1267 const mbedtls_mpi *X, 1268 mbedtls_mpi *Y, 1269 int parity_bit) 1270 { 1271 /* w = y^2 = x^3 + ax + b 1272 * y = sqrt(w) = w^((p+1)/4) mod p (for prime p where p = 3 mod 4) 1273 * 1274 * Note: this method for extracting square root does not validate that w 1275 * was indeed a square so this function will return garbage in Y if X 1276 * does not correspond to a point on the curve. 1277 */ 1278 1279 /* Check prerequisite p = 3 mod 4 */ 1280 if (mbedtls_mpi_get_bit(&grp->P, 0) != 1 || 1281 mbedtls_mpi_get_bit(&grp->P, 1) != 1) { 1282 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 1283 } 1284 1285 int ret; 1286 mbedtls_mpi exp; 1287 mbedtls_mpi_init(&exp); 1288 1289 /* use Y to store intermediate result, actually w above */ 1290 MBEDTLS_MPI_CHK(ecp_sw_rhs(grp, Y, X)); 1291 1292 /* w = y^2 */ /* Y contains y^2 intermediate result */ 1293 /* exp = ((p+1)/4) */ 1294 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&exp, &grp->P, 1)); 1295 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&exp, 2)); 1296 /* sqrt(w) = w^((p+1)/4) mod p (for prime p where p = 3 mod 4) */ 1297 MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(Y, Y /*y^2*/, &exp, &grp->P, NULL)); 1298 1299 /* check parity bit match or else invert Y */ 1300 /* This quick inversion implementation is valid because Y != 0 for all 1301 * Short Weierstrass curves supported by mbedtls, as each supported curve 1302 * has an order that is a large prime, so each supported curve does not 1303 * have any point of order 2, and a point with Y == 0 would be of order 2 */ 1304 if (mbedtls_mpi_get_bit(Y, 0) != parity_bit) { 1305 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(Y, &grp->P, Y)); 1306 } 1307 1308 cleanup: 1309 1310 mbedtls_mpi_free(&exp); 1311 return ret; 1312 } 1313 1314 /* 1315 * For curves in short Weierstrass form, we do all the internal operations in 1316 * Jacobian coordinates. 1317 * 1318 * For multiplication, we'll use a comb method with countermeasures against 1319 * SPA, hence timing attacks. 1320 */ 1321 1322 /* 1323 * Normalize jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1) 1324 * Cost: 1N := 1I + 3M + 1S 1325 */ 1326 static int ecp_normalize_jac(const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt) 1327 { 1328 if (MPI_ECP_CMP_INT(&pt->Z, 0) == 0) { 1329 return 0; 1330 } 1331 1332 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT) 1333 if (mbedtls_internal_ecp_grp_capable(grp)) { 1334 return mbedtls_internal_ecp_normalize_jac(grp, pt); 1335 } 1336 #endif /* MBEDTLS_ECP_NORMALIZE_JAC_ALT */ 1337 1338 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT) 1339 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 1340 #else 1341 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1342 mbedtls_mpi T; 1343 mbedtls_mpi_init(&T); 1344 1345 MPI_ECP_INV(&T, &pt->Z); /* T <- 1 / Z */ 1346 MPI_ECP_MUL(&pt->Y, &pt->Y, &T); /* Y' <- Y*T = Y / Z */ 1347 MPI_ECP_SQR(&T, &T); /* T <- T^2 = 1 / Z^2 */ 1348 MPI_ECP_MUL(&pt->X, &pt->X, &T); /* X <- X * T = X / Z^2 */ 1349 MPI_ECP_MUL(&pt->Y, &pt->Y, &T); /* Y'' <- Y' * T = Y / Z^3 */ 1350 1351 MPI_ECP_LSET(&pt->Z, 1); 1352 1353 cleanup: 1354 1355 mbedtls_mpi_free(&T); 1356 1357 return ret; 1358 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_JAC_ALT) */ 1359 } 1360 1361 /* 1362 * Normalize jacobian coordinates of an array of (pointers to) points, 1363 * using Montgomery's trick to perform only one inversion mod P. 1364 * (See for example Cohen's "A Course in Computational Algebraic Number 1365 * Theory", Algorithm 10.3.4.) 1366 * 1367 * Warning: fails (returning an error) if one of the points is zero! 1368 * This should never happen, see choice of w in ecp_mul_comb(). 1369 * 1370 * Cost: 1N(t) := 1I + (6t - 3)M + 1S 1371 */ 1372 static int ecp_normalize_jac_many(const mbedtls_ecp_group *grp, 1373 mbedtls_ecp_point *T[], size_t T_size) 1374 { 1375 if (T_size < 2) { 1376 return ecp_normalize_jac(grp, *T); 1377 } 1378 1379 #if defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT) 1380 if (mbedtls_internal_ecp_grp_capable(grp)) { 1381 return mbedtls_internal_ecp_normalize_jac_many(grp, T, T_size); 1382 } 1383 #endif 1384 1385 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT) 1386 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 1387 #else 1388 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1389 size_t i; 1390 mbedtls_mpi *c, t; 1391 1392 if ((c = mbedtls_calloc(T_size, sizeof(mbedtls_mpi))) == NULL) { 1393 return MBEDTLS_ERR_ECP_ALLOC_FAILED; 1394 } 1395 1396 mbedtls_mpi_init(&t); 1397 1398 mpi_init_many(c, T_size); 1399 /* 1400 * c[i] = Z_0 * ... * Z_i, i = 0,..,n := T_size-1 1401 */ 1402 MPI_ECP_MOV(&c[0], &T[0]->Z); 1403 for (i = 1; i < T_size; i++) { 1404 MPI_ECP_MUL(&c[i], &c[i-1], &T[i]->Z); 1405 } 1406 1407 /* 1408 * c[n] = 1 / (Z_0 * ... * Z_n) mod P 1409 */ 1410 MPI_ECP_INV(&c[T_size-1], &c[T_size-1]); 1411 1412 for (i = T_size - 1;; i--) { 1413 /* At the start of iteration i (note that i decrements), we have 1414 * - c[j] = Z_0 * .... * Z_j for j < i, 1415 * - c[j] = 1 / (Z_0 * .... * Z_j) for j == i, 1416 * 1417 * This is maintained via 1418 * - c[i-1] <- c[i] * Z_i 1419 * 1420 * We also derive 1/Z_i = c[i] * c[i-1] for i>0 and use that 1421 * to do the actual normalization. For i==0, we already have 1422 * c[0] = 1 / Z_0. 1423 */ 1424 1425 if (i > 0) { 1426 /* Compute 1/Z_i and establish invariant for the next iteration. */ 1427 MPI_ECP_MUL(&t, &c[i], &c[i-1]); 1428 MPI_ECP_MUL(&c[i-1], &c[i], &T[i]->Z); 1429 } else { 1430 MPI_ECP_MOV(&t, &c[0]); 1431 } 1432 1433 /* Now t holds 1 / Z_i; normalize as in ecp_normalize_jac() */ 1434 MPI_ECP_MUL(&T[i]->Y, &T[i]->Y, &t); 1435 MPI_ECP_SQR(&t, &t); 1436 MPI_ECP_MUL(&T[i]->X, &T[i]->X, &t); 1437 MPI_ECP_MUL(&T[i]->Y, &T[i]->Y, &t); 1438 1439 /* 1440 * Post-precessing: reclaim some memory by shrinking coordinates 1441 * - not storing Z (always 1) 1442 * - shrinking other coordinates, but still keeping the same number of 1443 * limbs as P, as otherwise it will too likely be regrown too fast. 1444 */ 1445 MBEDTLS_MPI_CHK(mbedtls_mpi_shrink(&T[i]->X, grp->P.n)); 1446 MBEDTLS_MPI_CHK(mbedtls_mpi_shrink(&T[i]->Y, grp->P.n)); 1447 1448 MPI_ECP_LSET(&T[i]->Z, 1); 1449 1450 if (i == 0) { 1451 break; 1452 } 1453 } 1454 1455 cleanup: 1456 1457 mbedtls_mpi_free(&t); 1458 mpi_free_many(c, T_size); 1459 mbedtls_free(c); 1460 1461 return ret; 1462 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_JAC_MANY_ALT) */ 1463 } 1464 1465 /* 1466 * Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak. 1467 * "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid 1468 */ 1469 static int ecp_safe_invert_jac(const mbedtls_ecp_group *grp, 1470 mbedtls_ecp_point *Q, 1471 unsigned char inv) 1472 { 1473 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1474 mbedtls_mpi tmp; 1475 mbedtls_mpi_init(&tmp); 1476 1477 MPI_ECP_COND_NEG(&Q->Y, inv); 1478 1479 cleanup: 1480 mbedtls_mpi_free(&tmp); 1481 return ret; 1482 } 1483 1484 /* 1485 * Point doubling R = 2 P, Jacobian coordinates 1486 * 1487 * Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2 . 1488 * 1489 * We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR 1490 * (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring. 1491 * 1492 * Standard optimizations are applied when curve parameter A is one of { 0, -3 }. 1493 * 1494 * Cost: 1D := 3M + 4S (A == 0) 1495 * 4M + 4S (A == -3) 1496 * 3M + 6S + 1a otherwise 1497 */ 1498 static int ecp_double_jac(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1499 const mbedtls_ecp_point *P, 1500 mbedtls_mpi tmp[4]) 1501 { 1502 #if defined(MBEDTLS_SELF_TEST) 1503 dbl_count++; 1504 #endif 1505 1506 #if defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) 1507 if (mbedtls_internal_ecp_grp_capable(grp)) { 1508 return mbedtls_internal_ecp_double_jac(grp, R, P); 1509 } 1510 #endif /* MBEDTLS_ECP_DOUBLE_JAC_ALT */ 1511 1512 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) 1513 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 1514 #else 1515 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1516 1517 /* Special case for A = -3 */ 1518 if (grp->A.p == NULL) { 1519 /* tmp[0] <- M = 3(X + Z^2)(X - Z^2) */ 1520 MPI_ECP_SQR(&tmp[1], &P->Z); 1521 MPI_ECP_ADD(&tmp[2], &P->X, &tmp[1]); 1522 MPI_ECP_SUB(&tmp[3], &P->X, &tmp[1]); 1523 MPI_ECP_MUL(&tmp[1], &tmp[2], &tmp[3]); 1524 MPI_ECP_MUL_INT(&tmp[0], &tmp[1], 3); 1525 } else { 1526 /* tmp[0] <- M = 3.X^2 + A.Z^4 */ 1527 MPI_ECP_SQR(&tmp[1], &P->X); 1528 MPI_ECP_MUL_INT(&tmp[0], &tmp[1], 3); 1529 1530 /* Optimize away for "koblitz" curves with A = 0 */ 1531 if (MPI_ECP_CMP_INT(&grp->A, 0) != 0) { 1532 /* M += A.Z^4 */ 1533 MPI_ECP_SQR(&tmp[1], &P->Z); 1534 MPI_ECP_SQR(&tmp[2], &tmp[1]); 1535 MPI_ECP_MUL(&tmp[1], &tmp[2], &grp->A); 1536 MPI_ECP_ADD(&tmp[0], &tmp[0], &tmp[1]); 1537 } 1538 } 1539 1540 /* tmp[1] <- S = 4.X.Y^2 */ 1541 MPI_ECP_SQR(&tmp[2], &P->Y); 1542 MPI_ECP_SHIFT_L(&tmp[2], 1); 1543 MPI_ECP_MUL(&tmp[1], &P->X, &tmp[2]); 1544 MPI_ECP_SHIFT_L(&tmp[1], 1); 1545 1546 /* tmp[3] <- U = 8.Y^4 */ 1547 MPI_ECP_SQR(&tmp[3], &tmp[2]); 1548 MPI_ECP_SHIFT_L(&tmp[3], 1); 1549 1550 /* tmp[2] <- T = M^2 - 2.S */ 1551 MPI_ECP_SQR(&tmp[2], &tmp[0]); 1552 MPI_ECP_SUB(&tmp[2], &tmp[2], &tmp[1]); 1553 MPI_ECP_SUB(&tmp[2], &tmp[2], &tmp[1]); 1554 1555 /* tmp[1] <- S = M(S - T) - U */ 1556 MPI_ECP_SUB(&tmp[1], &tmp[1], &tmp[2]); 1557 MPI_ECP_MUL(&tmp[1], &tmp[1], &tmp[0]); 1558 MPI_ECP_SUB(&tmp[1], &tmp[1], &tmp[3]); 1559 1560 /* tmp[3] <- U = 2.Y.Z */ 1561 MPI_ECP_MUL(&tmp[3], &P->Y, &P->Z); 1562 MPI_ECP_SHIFT_L(&tmp[3], 1); 1563 1564 /* Store results */ 1565 MPI_ECP_MOV(&R->X, &tmp[2]); 1566 MPI_ECP_MOV(&R->Y, &tmp[1]); 1567 MPI_ECP_MOV(&R->Z, &tmp[3]); 1568 1569 cleanup: 1570 1571 return ret; 1572 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_DOUBLE_JAC_ALT) */ 1573 } 1574 1575 /* 1576 * Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22) 1577 * 1578 * The coordinates of Q must be normalized (= affine), 1579 * but those of P don't need to. R is not normalized. 1580 * 1581 * P,Q,R may alias, but only at the level of EC points: they must be either 1582 * equal as pointers, or disjoint (including the coordinate data buffers). 1583 * Fine-grained aliasing at the level of coordinates is not supported. 1584 * 1585 * Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q. 1586 * None of these cases can happen as intermediate step in ecp_mul_comb(): 1587 * - at each step, P, Q and R are multiples of the base point, the factor 1588 * being less than its order, so none of them is zero; 1589 * - Q is an odd multiple of the base point, P an even multiple, 1590 * due to the choice of precomputed points in the modified comb method. 1591 * So branches for these cases do not leak secret information. 1592 * 1593 * Cost: 1A := 8M + 3S 1594 */ 1595 static int ecp_add_mixed(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 1596 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q, 1597 mbedtls_mpi tmp[4]) 1598 { 1599 #if defined(MBEDTLS_SELF_TEST) 1600 add_count++; 1601 #endif 1602 1603 #if defined(MBEDTLS_ECP_ADD_MIXED_ALT) 1604 if (mbedtls_internal_ecp_grp_capable(grp)) { 1605 return mbedtls_internal_ecp_add_mixed(grp, R, P, Q); 1606 } 1607 #endif /* MBEDTLS_ECP_ADD_MIXED_ALT */ 1608 1609 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_ADD_MIXED_ALT) 1610 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 1611 #else 1612 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1613 1614 /* NOTE: Aliasing between input and output is allowed, so one has to make 1615 * sure that at the point X,Y,Z are written, {P,Q}->{X,Y,Z} are no 1616 * longer read from. */ 1617 mbedtls_mpi * const X = &R->X; 1618 mbedtls_mpi * const Y = &R->Y; 1619 mbedtls_mpi * const Z = &R->Z; 1620 1621 if (!MPI_ECP_VALID(&Q->Z)) { 1622 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 1623 } 1624 1625 /* 1626 * Trivial cases: P == 0 or Q == 0 (case 1) 1627 */ 1628 if (MPI_ECP_CMP_INT(&P->Z, 0) == 0) { 1629 return mbedtls_ecp_copy(R, Q); 1630 } 1631 1632 if (MPI_ECP_CMP_INT(&Q->Z, 0) == 0) { 1633 return mbedtls_ecp_copy(R, P); 1634 } 1635 1636 /* 1637 * Make sure Q coordinates are normalized 1638 */ 1639 if (MPI_ECP_CMP_INT(&Q->Z, 1) != 0) { 1640 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 1641 } 1642 1643 MPI_ECP_SQR(&tmp[0], &P->Z); 1644 MPI_ECP_MUL(&tmp[1], &tmp[0], &P->Z); 1645 MPI_ECP_MUL(&tmp[0], &tmp[0], &Q->X); 1646 MPI_ECP_MUL(&tmp[1], &tmp[1], &Q->Y); 1647 MPI_ECP_SUB(&tmp[0], &tmp[0], &P->X); 1648 MPI_ECP_SUB(&tmp[1], &tmp[1], &P->Y); 1649 1650 /* Special cases (2) and (3) */ 1651 if (MPI_ECP_CMP_INT(&tmp[0], 0) == 0) { 1652 if (MPI_ECP_CMP_INT(&tmp[1], 0) == 0) { 1653 ret = ecp_double_jac(grp, R, P, tmp); 1654 goto cleanup; 1655 } else { 1656 ret = mbedtls_ecp_set_zero(R); 1657 goto cleanup; 1658 } 1659 } 1660 1661 /* {P,Q}->Z no longer used, so OK to write to Z even if there's aliasing. */ 1662 MPI_ECP_MUL(Z, &P->Z, &tmp[0]); 1663 MPI_ECP_SQR(&tmp[2], &tmp[0]); 1664 MPI_ECP_MUL(&tmp[3], &tmp[2], &tmp[0]); 1665 MPI_ECP_MUL(&tmp[2], &tmp[2], &P->X); 1666 1667 MPI_ECP_MOV(&tmp[0], &tmp[2]); 1668 MPI_ECP_SHIFT_L(&tmp[0], 1); 1669 1670 /* {P,Q}->X no longer used, so OK to write to X even if there's aliasing. */ 1671 MPI_ECP_SQR(X, &tmp[1]); 1672 MPI_ECP_SUB(X, X, &tmp[0]); 1673 MPI_ECP_SUB(X, X, &tmp[3]); 1674 MPI_ECP_SUB(&tmp[2], &tmp[2], X); 1675 MPI_ECP_MUL(&tmp[2], &tmp[2], &tmp[1]); 1676 MPI_ECP_MUL(&tmp[3], &tmp[3], &P->Y); 1677 /* {P,Q}->Y no longer used, so OK to write to Y even if there's aliasing. */ 1678 MPI_ECP_SUB(Y, &tmp[2], &tmp[3]); 1679 1680 cleanup: 1681 1682 return ret; 1683 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_ADD_MIXED_ALT) */ 1684 } 1685 1686 /* 1687 * Randomize jacobian coordinates: 1688 * (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l 1689 * This is sort of the reverse operation of ecp_normalize_jac(). 1690 * 1691 * This countermeasure was first suggested in [2]. 1692 */ 1693 static int ecp_randomize_jac(const mbedtls_ecp_group *grp, mbedtls_ecp_point *pt, 1694 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng) 1695 { 1696 #if defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) 1697 if (mbedtls_internal_ecp_grp_capable(grp)) { 1698 return mbedtls_internal_ecp_randomize_jac(grp, pt, f_rng, p_rng); 1699 } 1700 #endif /* MBEDTLS_ECP_RANDOMIZE_JAC_ALT */ 1701 1702 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) 1703 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 1704 #else 1705 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1706 mbedtls_mpi l; 1707 1708 mbedtls_mpi_init(&l); 1709 1710 /* Generate l such that 1 < l < p */ 1711 MPI_ECP_RAND(&l); 1712 1713 /* Z' = l * Z */ 1714 MPI_ECP_MUL(&pt->Z, &pt->Z, &l); 1715 1716 /* Y' = l * Y */ 1717 MPI_ECP_MUL(&pt->Y, &pt->Y, &l); 1718 1719 /* X' = l^2 * X */ 1720 MPI_ECP_SQR(&l, &l); 1721 MPI_ECP_MUL(&pt->X, &pt->X, &l); 1722 1723 /* Y'' = l^2 * Y' = l^3 * Y */ 1724 MPI_ECP_MUL(&pt->Y, &pt->Y, &l); 1725 1726 cleanup: 1727 mbedtls_mpi_free(&l); 1728 1729 if (ret == MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) { 1730 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED; 1731 } 1732 return ret; 1733 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_RANDOMIZE_JAC_ALT) */ 1734 } 1735 1736 /* 1737 * Check and define parameters used by the comb method (see below for details) 1738 */ 1739 #if MBEDTLS_ECP_WINDOW_SIZE < 2 || MBEDTLS_ECP_WINDOW_SIZE > 7 1740 #error "MBEDTLS_ECP_WINDOW_SIZE out of bounds" 1741 #endif 1742 1743 /* d = ceil( n / w ) */ 1744 #define COMB_MAX_D (MBEDTLS_ECP_MAX_BITS + 1) / 2 1745 1746 /* number of precomputed points */ 1747 #define COMB_MAX_PRE (1 << (MBEDTLS_ECP_WINDOW_SIZE - 1)) 1748 1749 /* 1750 * Compute the representation of m that will be used with our comb method. 1751 * 1752 * The basic comb method is described in GECC 3.44 for example. We use a 1753 * modified version that provides resistance to SPA by avoiding zero 1754 * digits in the representation as in [3]. We modify the method further by 1755 * requiring that all K_i be odd, which has the small cost that our 1756 * representation uses one more K_i, due to carries, but saves on the size of 1757 * the precomputed table. 1758 * 1759 * Summary of the comb method and its modifications: 1760 * 1761 * - The goal is to compute m*P for some w*d-bit integer m. 1762 * 1763 * - The basic comb method splits m into the w-bit integers 1764 * x[0] .. x[d-1] where x[i] consists of the bits in m whose 1765 * index has residue i modulo d, and computes m * P as 1766 * S[x[0]] + 2 * S[x[1]] + .. + 2^(d-1) S[x[d-1]], where 1767 * S[i_{w-1} .. i_0] := i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + i_0 P. 1768 * 1769 * - If it happens that, say, x[i+1]=0 (=> S[x[i+1]]=0), one can replace the sum by 1770 * .. + 2^{i-1} S[x[i-1]] - 2^i S[x[i]] + 2^{i+1} S[x[i]] + 2^{i+2} S[x[i+2]] .., 1771 * thereby successively converting it into a form where all summands 1772 * are nonzero, at the cost of negative summands. This is the basic idea of [3]. 1773 * 1774 * - More generally, even if x[i+1] != 0, we can first transform the sum as 1775 * .. - 2^i S[x[i]] + 2^{i+1} ( S[x[i]] + S[x[i+1]] ) + 2^{i+2} S[x[i+2]] .., 1776 * and then replace S[x[i]] + S[x[i+1]] = S[x[i] ^ x[i+1]] + 2 S[x[i] & x[i+1]]. 1777 * Performing and iterating this procedure for those x[i] that are even 1778 * (keeping track of carry), we can transform the original sum into one of the form 1779 * S[x'[0]] +- 2 S[x'[1]] +- .. +- 2^{d-1} S[x'[d-1]] + 2^d S[x'[d]] 1780 * with all x'[i] odd. It is therefore only necessary to know S at odd indices, 1781 * which is why we are only computing half of it in the first place in 1782 * ecp_precompute_comb and accessing it with index abs(i) / 2 in ecp_select_comb. 1783 * 1784 * - For the sake of compactness, only the seven low-order bits of x[i] 1785 * are used to represent its absolute value (K_i in the paper), and the msb 1786 * of x[i] encodes the sign (s_i in the paper): it is set if and only if 1787 * if s_i == -1; 1788 * 1789 * Calling conventions: 1790 * - x is an array of size d + 1 1791 * - w is the size, ie number of teeth, of the comb, and must be between 1792 * 2 and 7 (in practice, between 2 and MBEDTLS_ECP_WINDOW_SIZE) 1793 * - m is the MPI, expected to be odd and such that bitlength(m) <= w * d 1794 * (the result will be incorrect if these assumptions are not satisfied) 1795 */ 1796 static void ecp_comb_recode_core(unsigned char x[], size_t d, 1797 unsigned char w, const mbedtls_mpi *m) 1798 { 1799 size_t i, j; 1800 unsigned char c, cc, adjust; 1801 1802 memset(x, 0, d+1); 1803 1804 /* First get the classical comb values (except for x_d = 0) */ 1805 for (i = 0; i < d; i++) { 1806 for (j = 0; j < w; j++) { 1807 x[i] |= mbedtls_mpi_get_bit(m, i + d * j) << j; 1808 } 1809 } 1810 1811 /* Now make sure x_1 .. x_d are odd */ 1812 c = 0; 1813 for (i = 1; i <= d; i++) { 1814 /* Add carry and update it */ 1815 cc = x[i] & c; 1816 x[i] = x[i] ^ c; 1817 c = cc; 1818 1819 /* Adjust if needed, avoiding branches */ 1820 adjust = 1 - (x[i] & 0x01); 1821 c |= x[i] & (x[i-1] * adjust); 1822 x[i] = x[i] ^ (x[i-1] * adjust); 1823 x[i-1] |= adjust << 7; 1824 } 1825 } 1826 1827 /* 1828 * Precompute points for the adapted comb method 1829 * 1830 * Assumption: T must be able to hold 2^{w - 1} elements. 1831 * 1832 * Operation: If i = i_{w-1} ... i_1 is the binary representation of i, 1833 * sets T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P. 1834 * 1835 * Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1) 1836 * 1837 * Note: Even comb values (those where P would be omitted from the 1838 * sum defining T[i] above) are not needed in our adaption 1839 * the comb method. See ecp_comb_recode_core(). 1840 * 1841 * This function currently works in four steps: 1842 * (1) [dbl] Computation of intermediate T[i] for 2-power values of i 1843 * (2) [norm_dbl] Normalization of coordinates of these T[i] 1844 * (3) [add] Computation of all T[i] 1845 * (4) [norm_add] Normalization of all T[i] 1846 * 1847 * Step 1 can be interrupted but not the others; together with the final 1848 * coordinate normalization they are the largest steps done at once, depending 1849 * on the window size. Here are operation counts for P-256: 1850 * 1851 * step (2) (3) (4) 1852 * w = 5 142 165 208 1853 * w = 4 136 77 160 1854 * w = 3 130 33 136 1855 * w = 2 124 11 124 1856 * 1857 * So if ECC operations are blocking for too long even with a low max_ops 1858 * value, it's useful to set MBEDTLS_ECP_WINDOW_SIZE to a lower value in order 1859 * to minimize maximum blocking time. 1860 */ 1861 static int ecp_precompute_comb(const mbedtls_ecp_group *grp, 1862 mbedtls_ecp_point T[], const mbedtls_ecp_point *P, 1863 unsigned char w, size_t d, 1864 mbedtls_ecp_restart_ctx *rs_ctx) 1865 { 1866 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 1867 unsigned char i; 1868 size_t j = 0; 1869 const unsigned char T_size = 1U << (w - 1); 1870 mbedtls_ecp_point *cur, *TT[COMB_MAX_PRE - 1] = { NULL }; 1871 1872 mbedtls_mpi tmp[4]; 1873 1874 mpi_init_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi)); 1875 1876 #if defined(MBEDTLS_ECP_RESTARTABLE) 1877 if (rs_ctx != NULL && rs_ctx->rsm != NULL) { 1878 if (rs_ctx->rsm->state == ecp_rsm_pre_dbl) { 1879 goto dbl; 1880 } 1881 if (rs_ctx->rsm->state == ecp_rsm_pre_norm_dbl) { 1882 goto norm_dbl; 1883 } 1884 if (rs_ctx->rsm->state == ecp_rsm_pre_add) { 1885 goto add; 1886 } 1887 if (rs_ctx->rsm->state == ecp_rsm_pre_norm_add) { 1888 goto norm_add; 1889 } 1890 } 1891 #else 1892 (void) rs_ctx; 1893 #endif 1894 1895 #if defined(MBEDTLS_ECP_RESTARTABLE) 1896 if (rs_ctx != NULL && rs_ctx->rsm != NULL) { 1897 rs_ctx->rsm->state = ecp_rsm_pre_dbl; 1898 1899 /* initial state for the loop */ 1900 rs_ctx->rsm->i = 0; 1901 } 1902 1903 dbl: 1904 #endif 1905 /* 1906 * Set T[0] = P and 1907 * T[2^{l-1}] = 2^{dl} P for l = 1 .. w-1 (this is not the final value) 1908 */ 1909 MBEDTLS_MPI_CHK(mbedtls_ecp_copy(&T[0], P)); 1910 1911 #if defined(MBEDTLS_ECP_RESTARTABLE) 1912 if (rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0) { 1913 j = rs_ctx->rsm->i; 1914 } else 1915 #endif 1916 j = 0; 1917 1918 for (; j < d * (w - 1); j++) { 1919 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_DBL); 1920 1921 i = 1U << (j / d); 1922 cur = T + i; 1923 1924 if (j % d == 0) { 1925 MBEDTLS_MPI_CHK(mbedtls_ecp_copy(cur, T + (i >> 1))); 1926 } 1927 1928 MBEDTLS_MPI_CHK(ecp_double_jac(grp, cur, cur, tmp)); 1929 } 1930 1931 #if defined(MBEDTLS_ECP_RESTARTABLE) 1932 if (rs_ctx != NULL && rs_ctx->rsm != NULL) { 1933 rs_ctx->rsm->state = ecp_rsm_pre_norm_dbl; 1934 } 1935 1936 norm_dbl: 1937 #endif 1938 /* 1939 * Normalize current elements in T to allow them to be used in 1940 * ecp_add_mixed() below, which requires one normalized input. 1941 * 1942 * As T has holes, use an auxiliary array of pointers to elements in T. 1943 * 1944 */ 1945 j = 0; 1946 for (i = 1; i < T_size; i <<= 1) { 1947 TT[j++] = T + i; 1948 } 1949 1950 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV + 6 * j - 2); 1951 1952 MBEDTLS_MPI_CHK(ecp_normalize_jac_many(grp, TT, j)); 1953 1954 #if defined(MBEDTLS_ECP_RESTARTABLE) 1955 if (rs_ctx != NULL && rs_ctx->rsm != NULL) { 1956 rs_ctx->rsm->state = ecp_rsm_pre_add; 1957 } 1958 1959 add: 1960 #endif 1961 /* 1962 * Compute the remaining ones using the minimal number of additions 1963 * Be careful to update T[2^l] only after using it! 1964 */ 1965 MBEDTLS_ECP_BUDGET((T_size - 1) * MBEDTLS_ECP_OPS_ADD); 1966 1967 for (i = 1; i < T_size; i <<= 1) { 1968 j = i; 1969 while (j--) { 1970 MBEDTLS_MPI_CHK(ecp_add_mixed(grp, &T[i + j], &T[j], &T[i], tmp)); 1971 } 1972 } 1973 1974 #if defined(MBEDTLS_ECP_RESTARTABLE) 1975 if (rs_ctx != NULL && rs_ctx->rsm != NULL) { 1976 rs_ctx->rsm->state = ecp_rsm_pre_norm_add; 1977 } 1978 1979 norm_add: 1980 #endif 1981 /* 1982 * Normalize final elements in T. Even though there are no holes now, we 1983 * still need the auxiliary array for homogeneity with the previous 1984 * call. Also, skip T[0] which is already normalised, being a copy of P. 1985 */ 1986 for (j = 0; j + 1 < T_size; j++) { 1987 TT[j] = T + j + 1; 1988 } 1989 1990 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV + 6 * j - 2); 1991 1992 MBEDTLS_MPI_CHK(ecp_normalize_jac_many(grp, TT, j)); 1993 1994 /* Free Z coordinate (=1 after normalization) to save RAM. 1995 * This makes T[i] invalid as mbedtls_ecp_points, but this is OK 1996 * since from this point onwards, they are only accessed indirectly 1997 * via the getter function ecp_select_comb() which does set the 1998 * target's Z coordinate to 1. */ 1999 for (i = 0; i < T_size; i++) { 2000 mbedtls_mpi_free(&T[i].Z); 2001 } 2002 2003 cleanup: 2004 2005 mpi_free_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi)); 2006 2007 #if defined(MBEDTLS_ECP_RESTARTABLE) 2008 if (rs_ctx != NULL && rs_ctx->rsm != NULL && 2009 ret == MBEDTLS_ERR_ECP_IN_PROGRESS) { 2010 if (rs_ctx->rsm->state == ecp_rsm_pre_dbl) { 2011 rs_ctx->rsm->i = j; 2012 } 2013 } 2014 #endif 2015 2016 return ret; 2017 } 2018 2019 /* 2020 * Select precomputed point: R = sign(i) * T[ abs(i) / 2 ] 2021 * 2022 * See ecp_comb_recode_core() for background 2023 */ 2024 static int ecp_select_comb(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2025 const mbedtls_ecp_point T[], unsigned char T_size, 2026 unsigned char i) 2027 { 2028 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2029 unsigned char ii, j; 2030 2031 /* Ignore the "sign" bit and scale down */ 2032 ii = (i & 0x7Fu) >> 1; 2033 2034 /* Read the whole table to thwart cache-based timing attacks */ 2035 for (j = 0; j < T_size; j++) { 2036 MPI_ECP_COND_ASSIGN(&R->X, &T[j].X, j == ii); 2037 MPI_ECP_COND_ASSIGN(&R->Y, &T[j].Y, j == ii); 2038 } 2039 2040 /* Safely invert result if i is "negative" */ 2041 MBEDTLS_MPI_CHK(ecp_safe_invert_jac(grp, R, i >> 7)); 2042 2043 MPI_ECP_LSET(&R->Z, 1); 2044 2045 cleanup: 2046 return ret; 2047 } 2048 2049 /* 2050 * Core multiplication algorithm for the (modified) comb method. 2051 * This part is actually common with the basic comb method (GECC 3.44) 2052 * 2053 * Cost: d A + d D + 1 R 2054 */ 2055 static int ecp_mul_comb_core(const mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2056 const mbedtls_ecp_point T[], unsigned char T_size, 2057 const unsigned char x[], size_t d, 2058 int (*f_rng)(void *, unsigned char *, size_t), 2059 void *p_rng, 2060 mbedtls_ecp_restart_ctx *rs_ctx) 2061 { 2062 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2063 mbedtls_ecp_point Txi; 2064 mbedtls_mpi tmp[4]; 2065 size_t i; 2066 2067 mbedtls_ecp_point_init(&Txi); 2068 mpi_init_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi)); 2069 2070 #if !defined(MBEDTLS_ECP_RESTARTABLE) 2071 (void) rs_ctx; 2072 #endif 2073 2074 #if defined(MBEDTLS_ECP_RESTARTABLE) 2075 if (rs_ctx != NULL && rs_ctx->rsm != NULL && 2076 rs_ctx->rsm->state != ecp_rsm_comb_core) { 2077 rs_ctx->rsm->i = 0; 2078 rs_ctx->rsm->state = ecp_rsm_comb_core; 2079 } 2080 2081 /* new 'if' instead of nested for the sake of the 'else' branch */ 2082 if (rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->i != 0) { 2083 /* restore current index (R already pointing to rs_ctx->rsm->R) */ 2084 i = rs_ctx->rsm->i; 2085 } else 2086 #endif 2087 { 2088 /* Start with a non-zero point and randomize its coordinates */ 2089 i = d; 2090 MBEDTLS_MPI_CHK(ecp_select_comb(grp, R, T, T_size, x[i])); 2091 if (f_rng != 0) { 2092 MBEDTLS_MPI_CHK(ecp_randomize_jac(grp, R, f_rng, p_rng)); 2093 } 2094 } 2095 2096 while (i != 0) { 2097 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_DBL + MBEDTLS_ECP_OPS_ADD); 2098 --i; 2099 2100 MBEDTLS_MPI_CHK(ecp_double_jac(grp, R, R, tmp)); 2101 MBEDTLS_MPI_CHK(ecp_select_comb(grp, &Txi, T, T_size, x[i])); 2102 MBEDTLS_MPI_CHK(ecp_add_mixed(grp, R, R, &Txi, tmp)); 2103 } 2104 2105 cleanup: 2106 2107 mbedtls_ecp_point_free(&Txi); 2108 mpi_free_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi)); 2109 2110 #if defined(MBEDTLS_ECP_RESTARTABLE) 2111 if (rs_ctx != NULL && rs_ctx->rsm != NULL && 2112 ret == MBEDTLS_ERR_ECP_IN_PROGRESS) { 2113 rs_ctx->rsm->i = i; 2114 /* no need to save R, already pointing to rs_ctx->rsm->R */ 2115 } 2116 #endif 2117 2118 return ret; 2119 } 2120 2121 /* 2122 * Recode the scalar to get constant-time comb multiplication 2123 * 2124 * As the actual scalar recoding needs an odd scalar as a starting point, 2125 * this wrapper ensures that by replacing m by N - m if necessary, and 2126 * informs the caller that the result of multiplication will be negated. 2127 * 2128 * This works because we only support large prime order for Short Weierstrass 2129 * curves, so N is always odd hence either m or N - m is. 2130 * 2131 * See ecp_comb_recode_core() for background. 2132 */ 2133 static int ecp_comb_recode_scalar(const mbedtls_ecp_group *grp, 2134 const mbedtls_mpi *m, 2135 unsigned char k[COMB_MAX_D + 1], 2136 size_t d, 2137 unsigned char w, 2138 unsigned char *parity_trick) 2139 { 2140 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2141 mbedtls_mpi M, mm; 2142 2143 mbedtls_mpi_init(&M); 2144 mbedtls_mpi_init(&mm); 2145 2146 /* N is always odd (see above), just make extra sure */ 2147 if (mbedtls_mpi_get_bit(&grp->N, 0) != 1) { 2148 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 2149 } 2150 2151 /* do we need the parity trick? */ 2152 *parity_trick = (mbedtls_mpi_get_bit(m, 0) == 0); 2153 2154 /* execute parity fix in constant time */ 2155 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&M, m)); 2156 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&mm, &grp->N, m)); 2157 MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign(&M, &mm, *parity_trick)); 2158 2159 /* actual scalar recoding */ 2160 ecp_comb_recode_core(k, d, w, &M); 2161 2162 cleanup: 2163 mbedtls_mpi_free(&mm); 2164 mbedtls_mpi_free(&M); 2165 2166 return ret; 2167 } 2168 2169 /* 2170 * Perform comb multiplication (for short Weierstrass curves) 2171 * once the auxiliary table has been pre-computed. 2172 * 2173 * Scalar recoding may use a parity trick that makes us compute -m * P, 2174 * if that is the case we'll need to recover m * P at the end. 2175 */ 2176 static int ecp_mul_comb_after_precomp(const mbedtls_ecp_group *grp, 2177 mbedtls_ecp_point *R, 2178 const mbedtls_mpi *m, 2179 const mbedtls_ecp_point *T, 2180 unsigned char T_size, 2181 unsigned char w, 2182 size_t d, 2183 int (*f_rng)(void *, unsigned char *, size_t), 2184 void *p_rng, 2185 mbedtls_ecp_restart_ctx *rs_ctx) 2186 { 2187 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2188 unsigned char parity_trick; 2189 unsigned char k[COMB_MAX_D + 1]; 2190 mbedtls_ecp_point *RR = R; 2191 2192 #if defined(MBEDTLS_ECP_RESTARTABLE) 2193 if (rs_ctx != NULL && rs_ctx->rsm != NULL) { 2194 RR = &rs_ctx->rsm->R; 2195 2196 if (rs_ctx->rsm->state == ecp_rsm_final_norm) { 2197 goto final_norm; 2198 } 2199 } 2200 #endif 2201 2202 MBEDTLS_MPI_CHK(ecp_comb_recode_scalar(grp, m, k, d, w, 2203 &parity_trick)); 2204 MBEDTLS_MPI_CHK(ecp_mul_comb_core(grp, RR, T, T_size, k, d, 2205 f_rng, p_rng, rs_ctx)); 2206 MBEDTLS_MPI_CHK(ecp_safe_invert_jac(grp, RR, parity_trick)); 2207 2208 #if defined(MBEDTLS_ECP_RESTARTABLE) 2209 if (rs_ctx != NULL && rs_ctx->rsm != NULL) { 2210 rs_ctx->rsm->state = ecp_rsm_final_norm; 2211 } 2212 2213 final_norm: 2214 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV); 2215 #endif 2216 /* 2217 * Knowledge of the jacobian coordinates may leak the last few bits of the 2218 * scalar [1], and since our MPI implementation isn't constant-flow, 2219 * inversion (used for coordinate normalization) may leak the full value 2220 * of its input via side-channels [2]. 2221 * 2222 * [1] https://eprint.iacr.org/2003/191 2223 * [2] https://eprint.iacr.org/2020/055 2224 * 2225 * Avoid the leak by randomizing coordinates before we normalize them. 2226 */ 2227 if (f_rng != 0) { 2228 MBEDTLS_MPI_CHK(ecp_randomize_jac(grp, RR, f_rng, p_rng)); 2229 } 2230 2231 MBEDTLS_MPI_CHK(ecp_normalize_jac(grp, RR)); 2232 2233 #if defined(MBEDTLS_ECP_RESTARTABLE) 2234 if (rs_ctx != NULL && rs_ctx->rsm != NULL) { 2235 MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, RR)); 2236 } 2237 #endif 2238 2239 cleanup: 2240 return ret; 2241 } 2242 2243 /* 2244 * Pick window size based on curve size and whether we optimize for base point 2245 */ 2246 static unsigned char ecp_pick_window_size(const mbedtls_ecp_group *grp, 2247 unsigned char p_eq_g) 2248 { 2249 unsigned char w; 2250 2251 /* 2252 * Minimize the number of multiplications, that is minimize 2253 * 10 * d * w + 18 * 2^(w-1) + 11 * d + 7 * w, with d = ceil( nbits / w ) 2254 * (see costs of the various parts, with 1S = 1M) 2255 */ 2256 w = grp->nbits >= 384 ? 5 : 4; 2257 2258 /* 2259 * If P == G, pre-compute a bit more, since this may be re-used later. 2260 * Just adding one avoids upping the cost of the first mul too much, 2261 * and the memory cost too. 2262 */ 2263 if (p_eq_g) { 2264 w++; 2265 } 2266 2267 /* 2268 * If static comb table may not be used (!p_eq_g) or static comb table does 2269 * not exists, make sure w is within bounds. 2270 * (The last test is useful only for very small curves in the test suite.) 2271 * 2272 * The user reduces MBEDTLS_ECP_WINDOW_SIZE does not changes the size of 2273 * static comb table, because the size of static comb table is fixed when 2274 * it is generated. 2275 */ 2276 #if (MBEDTLS_ECP_WINDOW_SIZE < 6) 2277 if ((!p_eq_g || !ecp_group_is_static_comb_table(grp)) && w > MBEDTLS_ECP_WINDOW_SIZE) { 2278 w = MBEDTLS_ECP_WINDOW_SIZE; 2279 } 2280 #endif 2281 if (w >= grp->nbits) { 2282 w = 2; 2283 } 2284 2285 return w; 2286 } 2287 2288 /* 2289 * Multiplication using the comb method - for curves in short Weierstrass form 2290 * 2291 * This function is mainly responsible for administrative work: 2292 * - managing the restart context if enabled 2293 * - managing the table of precomputed points (passed between the below two 2294 * functions): allocation, computation, ownership transfer, freeing. 2295 * 2296 * It delegates the actual arithmetic work to: 2297 * ecp_precompute_comb() and ecp_mul_comb_with_precomp() 2298 * 2299 * See comments on ecp_comb_recode_core() regarding the computation strategy. 2300 */ 2301 static int ecp_mul_comb(mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2302 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2303 int (*f_rng)(void *, unsigned char *, size_t), 2304 void *p_rng, 2305 mbedtls_ecp_restart_ctx *rs_ctx) 2306 { 2307 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2308 unsigned char w, p_eq_g, i; 2309 size_t d; 2310 unsigned char T_size = 0, T_ok = 0; 2311 mbedtls_ecp_point *T = NULL; 2312 2313 ECP_RS_ENTER(rsm); 2314 2315 /* Is P the base point ? */ 2316 #if MBEDTLS_ECP_FIXED_POINT_OPTIM == 1 2317 p_eq_g = (MPI_ECP_CMP(&P->Y, &grp->G.Y) == 0 && 2318 MPI_ECP_CMP(&P->X, &grp->G.X) == 0); 2319 #else 2320 p_eq_g = 0; 2321 #endif 2322 2323 /* Pick window size and deduce related sizes */ 2324 w = ecp_pick_window_size(grp, p_eq_g); 2325 T_size = 1U << (w - 1); 2326 d = (grp->nbits + w - 1) / w; 2327 2328 /* Pre-computed table: do we have it already for the base point? */ 2329 if (p_eq_g && grp->T != NULL) { 2330 /* second pointer to the same table, will be deleted on exit */ 2331 T = grp->T; 2332 T_ok = 1; 2333 } else 2334 #if defined(MBEDTLS_ECP_RESTARTABLE) 2335 /* Pre-computed table: do we have one in progress? complete? */ 2336 if (rs_ctx != NULL && rs_ctx->rsm != NULL && rs_ctx->rsm->T != NULL) { 2337 /* transfer ownership of T from rsm to local function */ 2338 T = rs_ctx->rsm->T; 2339 rs_ctx->rsm->T = NULL; 2340 rs_ctx->rsm->T_size = 0; 2341 2342 /* This effectively jumps to the call to mul_comb_after_precomp() */ 2343 T_ok = rs_ctx->rsm->state >= ecp_rsm_comb_core; 2344 } else 2345 #endif 2346 /* Allocate table if we didn't have any */ 2347 { 2348 T = mbedtls_calloc(T_size, sizeof(mbedtls_ecp_point)); 2349 if (T == NULL) { 2350 ret = MBEDTLS_ERR_ECP_ALLOC_FAILED; 2351 goto cleanup; 2352 } 2353 2354 for (i = 0; i < T_size; i++) { 2355 mbedtls_ecp_point_init(&T[i]); 2356 } 2357 2358 T_ok = 0; 2359 } 2360 2361 /* Compute table (or finish computing it) if not done already */ 2362 if (!T_ok) { 2363 MBEDTLS_MPI_CHK(ecp_precompute_comb(grp, T, P, w, d, rs_ctx)); 2364 2365 if (p_eq_g) { 2366 /* almost transfer ownership of T to the group, but keep a copy of 2367 * the pointer to use for calling the next function more easily */ 2368 grp->T = T; 2369 grp->T_size = T_size; 2370 } 2371 } 2372 2373 /* Actual comb multiplication using precomputed points */ 2374 MBEDTLS_MPI_CHK(ecp_mul_comb_after_precomp(grp, R, m, 2375 T, T_size, w, d, 2376 f_rng, p_rng, rs_ctx)); 2377 2378 cleanup: 2379 2380 /* does T belong to the group? */ 2381 if (T == grp->T) { 2382 T = NULL; 2383 } 2384 2385 /* does T belong to the restart context? */ 2386 #if defined(MBEDTLS_ECP_RESTARTABLE) 2387 if (rs_ctx != NULL && rs_ctx->rsm != NULL && ret == MBEDTLS_ERR_ECP_IN_PROGRESS && T != NULL) { 2388 /* transfer ownership of T from local function to rsm */ 2389 rs_ctx->rsm->T_size = T_size; 2390 rs_ctx->rsm->T = T; 2391 T = NULL; 2392 } 2393 #endif 2394 2395 /* did T belong to us? then let's destroy it! */ 2396 if (T != NULL) { 2397 for (i = 0; i < T_size; i++) { 2398 mbedtls_ecp_point_free(&T[i]); 2399 } 2400 mbedtls_free(T); 2401 } 2402 2403 /* prevent caller from using invalid value */ 2404 int should_free_R = (ret != 0); 2405 #if defined(MBEDTLS_ECP_RESTARTABLE) 2406 /* don't free R while in progress in case R == P */ 2407 if (ret == MBEDTLS_ERR_ECP_IN_PROGRESS) { 2408 should_free_R = 0; 2409 } 2410 #endif 2411 if (should_free_R) { 2412 mbedtls_ecp_point_free(R); 2413 } 2414 2415 ECP_RS_LEAVE(rsm); 2416 2417 return ret; 2418 } 2419 2420 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 2421 2422 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 2423 /* 2424 * For Montgomery curves, we do all the internal arithmetic in projective 2425 * coordinates. Import/export of points uses only the x coordinates, which is 2426 * internally represented as X / Z. 2427 * 2428 * For scalar multiplication, we'll use a Montgomery ladder. 2429 */ 2430 2431 /* 2432 * Normalize Montgomery x/z coordinates: X = X/Z, Z = 1 2433 * Cost: 1M + 1I 2434 */ 2435 static int ecp_normalize_mxz(const mbedtls_ecp_group *grp, mbedtls_ecp_point *P) 2436 { 2437 #if defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) 2438 if (mbedtls_internal_ecp_grp_capable(grp)) { 2439 return mbedtls_internal_ecp_normalize_mxz(grp, P); 2440 } 2441 #endif /* MBEDTLS_ECP_NORMALIZE_MXZ_ALT */ 2442 2443 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) 2444 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 2445 #else 2446 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2447 MPI_ECP_INV(&P->Z, &P->Z); 2448 MPI_ECP_MUL(&P->X, &P->X, &P->Z); 2449 MPI_ECP_LSET(&P->Z, 1); 2450 2451 cleanup: 2452 return ret; 2453 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_NORMALIZE_MXZ_ALT) */ 2454 } 2455 2456 /* 2457 * Randomize projective x/z coordinates: 2458 * (X, Z) -> (l X, l Z) for random l 2459 * This is sort of the reverse operation of ecp_normalize_mxz(). 2460 * 2461 * This countermeasure was first suggested in [2]. 2462 * Cost: 2M 2463 */ 2464 static int ecp_randomize_mxz(const mbedtls_ecp_group *grp, mbedtls_ecp_point *P, 2465 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng) 2466 { 2467 #if defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) 2468 if (mbedtls_internal_ecp_grp_capable(grp)) { 2469 return mbedtls_internal_ecp_randomize_mxz(grp, P, f_rng, p_rng); 2470 } 2471 #endif /* MBEDTLS_ECP_RANDOMIZE_MXZ_ALT */ 2472 2473 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) 2474 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 2475 #else 2476 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2477 mbedtls_mpi l; 2478 mbedtls_mpi_init(&l); 2479 2480 /* Generate l such that 1 < l < p */ 2481 MPI_ECP_RAND(&l); 2482 2483 MPI_ECP_MUL(&P->X, &P->X, &l); 2484 MPI_ECP_MUL(&P->Z, &P->Z, &l); 2485 2486 cleanup: 2487 mbedtls_mpi_free(&l); 2488 2489 if (ret == MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) { 2490 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED; 2491 } 2492 return ret; 2493 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_RANDOMIZE_MXZ_ALT) */ 2494 } 2495 2496 /* 2497 * Double-and-add: R = 2P, S = P + Q, with d = X(P - Q), 2498 * for Montgomery curves in x/z coordinates. 2499 * 2500 * http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3 2501 * with 2502 * d = X1 2503 * P = (X2, Z2) 2504 * Q = (X3, Z3) 2505 * R = (X4, Z4) 2506 * S = (X5, Z5) 2507 * and eliminating temporary variables tO, ..., t4. 2508 * 2509 * Cost: 5M + 4S 2510 */ 2511 static int ecp_double_add_mxz(const mbedtls_ecp_group *grp, 2512 mbedtls_ecp_point *R, mbedtls_ecp_point *S, 2513 const mbedtls_ecp_point *P, const mbedtls_ecp_point *Q, 2514 const mbedtls_mpi *d, 2515 mbedtls_mpi T[4]) 2516 { 2517 #if defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) 2518 if (mbedtls_internal_ecp_grp_capable(grp)) { 2519 return mbedtls_internal_ecp_double_add_mxz(grp, R, S, P, Q, d); 2520 } 2521 #endif /* MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT */ 2522 2523 #if defined(MBEDTLS_ECP_NO_FALLBACK) && defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) 2524 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 2525 #else 2526 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2527 2528 MPI_ECP_ADD(&T[0], &P->X, &P->Z); /* Pp := PX + PZ */ 2529 MPI_ECP_SUB(&T[1], &P->X, &P->Z); /* Pm := PX - PZ */ 2530 MPI_ECP_ADD(&T[2], &Q->X, &Q->Z); /* Qp := QX + XZ */ 2531 MPI_ECP_SUB(&T[3], &Q->X, &Q->Z); /* Qm := QX - QZ */ 2532 MPI_ECP_MUL(&T[3], &T[3], &T[0]); /* Qm * Pp */ 2533 MPI_ECP_MUL(&T[2], &T[2], &T[1]); /* Qp * Pm */ 2534 MPI_ECP_SQR(&T[0], &T[0]); /* Pp^2 */ 2535 MPI_ECP_SQR(&T[1], &T[1]); /* Pm^2 */ 2536 MPI_ECP_MUL(&R->X, &T[0], &T[1]); /* Pp^2 * Pm^2 */ 2537 MPI_ECP_SUB(&T[0], &T[0], &T[1]); /* Pp^2 - Pm^2 */ 2538 MPI_ECP_MUL(&R->Z, &grp->A, &T[0]); /* A * (Pp^2 - Pm^2) */ 2539 MPI_ECP_ADD(&R->Z, &T[1], &R->Z); /* [ A * (Pp^2-Pm^2) ] + Pm^2 */ 2540 MPI_ECP_ADD(&S->X, &T[3], &T[2]); /* Qm*Pp + Qp*Pm */ 2541 MPI_ECP_SQR(&S->X, &S->X); /* (Qm*Pp + Qp*Pm)^2 */ 2542 MPI_ECP_SUB(&S->Z, &T[3], &T[2]); /* Qm*Pp - Qp*Pm */ 2543 MPI_ECP_SQR(&S->Z, &S->Z); /* (Qm*Pp - Qp*Pm)^2 */ 2544 MPI_ECP_MUL(&S->Z, d, &S->Z); /* d * ( Qm*Pp - Qp*Pm )^2 */ 2545 MPI_ECP_MUL(&R->Z, &T[0], &R->Z); /* [A*(Pp^2-Pm^2)+Pm^2]*(Pp^2-Pm^2) */ 2546 2547 cleanup: 2548 2549 return ret; 2550 #endif /* !defined(MBEDTLS_ECP_NO_FALLBACK) || !defined(MBEDTLS_ECP_DOUBLE_ADD_MXZ_ALT) */ 2551 } 2552 2553 /* 2554 * Multiplication with Montgomery ladder in x/z coordinates, 2555 * for curves in Montgomery form 2556 */ 2557 static int ecp_mul_mxz(mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2558 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2559 int (*f_rng)(void *, unsigned char *, size_t), 2560 void *p_rng) 2561 { 2562 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2563 size_t i; 2564 unsigned char b; 2565 mbedtls_ecp_point RP; 2566 mbedtls_mpi PX; 2567 mbedtls_mpi tmp[4]; 2568 mbedtls_ecp_point_init(&RP); mbedtls_mpi_init(&PX); 2569 2570 mpi_init_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi)); 2571 2572 if (f_rng == NULL) { 2573 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 2574 } 2575 2576 /* Save PX and read from P before writing to R, in case P == R */ 2577 MPI_ECP_MOV(&PX, &P->X); 2578 MBEDTLS_MPI_CHK(mbedtls_ecp_copy(&RP, P)); 2579 2580 /* Set R to zero in modified x/z coordinates */ 2581 MPI_ECP_LSET(&R->X, 1); 2582 MPI_ECP_LSET(&R->Z, 0); 2583 mbedtls_mpi_free(&R->Y); 2584 2585 /* RP.X might be slightly larger than P, so reduce it */ 2586 MOD_ADD(&RP.X); 2587 2588 /* Randomize coordinates of the starting point */ 2589 MBEDTLS_MPI_CHK(ecp_randomize_mxz(grp, &RP, f_rng, p_rng)); 2590 2591 /* Loop invariant: R = result so far, RP = R + P */ 2592 i = grp->nbits + 1; /* one past the (zero-based) required msb for private keys */ 2593 while (i-- > 0) { 2594 b = mbedtls_mpi_get_bit(m, i); 2595 /* 2596 * if (b) R = 2R + P else R = 2R, 2597 * which is: 2598 * if (b) double_add( RP, R, RP, R ) 2599 * else double_add( R, RP, R, RP ) 2600 * but using safe conditional swaps to avoid leaks 2601 */ 2602 MPI_ECP_COND_SWAP(&R->X, &RP.X, b); 2603 MPI_ECP_COND_SWAP(&R->Z, &RP.Z, b); 2604 MBEDTLS_MPI_CHK(ecp_double_add_mxz(grp, R, &RP, R, &RP, &PX, tmp)); 2605 MPI_ECP_COND_SWAP(&R->X, &RP.X, b); 2606 MPI_ECP_COND_SWAP(&R->Z, &RP.Z, b); 2607 } 2608 2609 /* 2610 * Knowledge of the projective coordinates may leak the last few bits of the 2611 * scalar [1], and since our MPI implementation isn't constant-flow, 2612 * inversion (used for coordinate normalization) may leak the full value 2613 * of its input via side-channels [2]. 2614 * 2615 * [1] https://eprint.iacr.org/2003/191 2616 * [2] https://eprint.iacr.org/2020/055 2617 * 2618 * Avoid the leak by randomizing coordinates before we normalize them. 2619 */ 2620 MBEDTLS_MPI_CHK(ecp_randomize_mxz(grp, R, f_rng, p_rng)); 2621 MBEDTLS_MPI_CHK(ecp_normalize_mxz(grp, R)); 2622 2623 cleanup: 2624 mbedtls_ecp_point_free(&RP); mbedtls_mpi_free(&PX); 2625 2626 mpi_free_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi)); 2627 return ret; 2628 } 2629 2630 #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ 2631 2632 /* 2633 * Restartable multiplication R = m * P 2634 * 2635 * This internal function can be called without an RNG in case where we know 2636 * the inputs are not sensitive. 2637 */ 2638 static int ecp_mul_restartable_internal(mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2639 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2640 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng, 2641 mbedtls_ecp_restart_ctx *rs_ctx) 2642 { 2643 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 2644 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2645 char is_grp_capable = 0; 2646 #endif 2647 2648 #if defined(MBEDTLS_ECP_RESTARTABLE) 2649 /* reset ops count for this call if top-level */ 2650 if (rs_ctx != NULL && rs_ctx->depth++ == 0) { 2651 rs_ctx->ops_done = 0; 2652 } 2653 #else 2654 (void) rs_ctx; 2655 #endif 2656 2657 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2658 if ((is_grp_capable = mbedtls_internal_ecp_grp_capable(grp))) { 2659 MBEDTLS_MPI_CHK(mbedtls_internal_ecp_init(grp)); 2660 } 2661 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2662 2663 int restarting = 0; 2664 #if defined(MBEDTLS_ECP_RESTARTABLE) 2665 restarting = (rs_ctx != NULL && rs_ctx->rsm != NULL); 2666 #endif 2667 /* skip argument check when restarting */ 2668 if (!restarting) { 2669 /* check_privkey is free */ 2670 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_CHK); 2671 2672 /* Common sanity checks */ 2673 MBEDTLS_MPI_CHK(mbedtls_ecp_check_privkey(grp, m)); 2674 MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P)); 2675 } 2676 2677 ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 2678 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 2679 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) { 2680 MBEDTLS_MPI_CHK(ecp_mul_mxz(grp, R, m, P, f_rng, p_rng)); 2681 } 2682 #endif 2683 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 2684 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) { 2685 MBEDTLS_MPI_CHK(ecp_mul_comb(grp, R, m, P, f_rng, p_rng, rs_ctx)); 2686 } 2687 #endif 2688 2689 cleanup: 2690 2691 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2692 if (is_grp_capable) { 2693 mbedtls_internal_ecp_free(grp); 2694 } 2695 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2696 2697 #if defined(MBEDTLS_ECP_RESTARTABLE) 2698 if (rs_ctx != NULL) { 2699 rs_ctx->depth--; 2700 } 2701 #endif 2702 2703 return ret; 2704 } 2705 2706 /* 2707 * Restartable multiplication R = m * P 2708 */ 2709 int mbedtls_ecp_mul_restartable(mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2710 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2711 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng, 2712 mbedtls_ecp_restart_ctx *rs_ctx) 2713 { 2714 if (f_rng == NULL) { 2715 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 2716 } 2717 2718 return ecp_mul_restartable_internal(grp, R, m, P, f_rng, p_rng, rs_ctx); 2719 } 2720 2721 /* 2722 * Multiplication R = m * P 2723 */ 2724 int mbedtls_ecp_mul(mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2725 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2726 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng) 2727 { 2728 return mbedtls_ecp_mul_restartable(grp, R, m, P, f_rng, p_rng, NULL); 2729 } 2730 2731 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 2732 /* 2733 * Check that an affine point is valid as a public key, 2734 * short weierstrass curves (SEC1 3.2.3.1) 2735 */ 2736 static int ecp_check_pubkey_sw(const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt) 2737 { 2738 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2739 mbedtls_mpi YY, RHS; 2740 2741 /* pt coordinates must be normalized for our checks */ 2742 if (mbedtls_mpi_cmp_int(&pt->X, 0) < 0 || 2743 mbedtls_mpi_cmp_int(&pt->Y, 0) < 0 || 2744 mbedtls_mpi_cmp_mpi(&pt->X, &grp->P) >= 0 || 2745 mbedtls_mpi_cmp_mpi(&pt->Y, &grp->P) >= 0) { 2746 return MBEDTLS_ERR_ECP_INVALID_KEY; 2747 } 2748 2749 mbedtls_mpi_init(&YY); mbedtls_mpi_init(&RHS); 2750 2751 /* 2752 * YY = Y^2 2753 * RHS = X^3 + A X + B 2754 */ 2755 MPI_ECP_SQR(&YY, &pt->Y); 2756 MBEDTLS_MPI_CHK(ecp_sw_rhs(grp, &RHS, &pt->X)); 2757 2758 if (MPI_ECP_CMP(&YY, &RHS) != 0) { 2759 ret = MBEDTLS_ERR_ECP_INVALID_KEY; 2760 } 2761 2762 cleanup: 2763 2764 mbedtls_mpi_free(&YY); mbedtls_mpi_free(&RHS); 2765 2766 return ret; 2767 } 2768 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 2769 2770 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 2771 /* 2772 * R = m * P with shortcuts for m == 0, m == 1 and m == -1 2773 * NOT constant-time - ONLY for short Weierstrass! 2774 */ 2775 static int mbedtls_ecp_mul_shortcuts(mbedtls_ecp_group *grp, 2776 mbedtls_ecp_point *R, 2777 const mbedtls_mpi *m, 2778 const mbedtls_ecp_point *P, 2779 mbedtls_ecp_restart_ctx *rs_ctx) 2780 { 2781 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2782 mbedtls_mpi tmp; 2783 mbedtls_mpi_init(&tmp); 2784 2785 if (mbedtls_mpi_cmp_int(m, 0) == 0) { 2786 MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P)); 2787 MBEDTLS_MPI_CHK(mbedtls_ecp_set_zero(R)); 2788 } else if (mbedtls_mpi_cmp_int(m, 1) == 0) { 2789 MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P)); 2790 MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, P)); 2791 } else if (mbedtls_mpi_cmp_int(m, -1) == 0) { 2792 MBEDTLS_MPI_CHK(mbedtls_ecp_check_pubkey(grp, P)); 2793 MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, P)); 2794 MPI_ECP_NEG(&R->Y); 2795 } else { 2796 MBEDTLS_MPI_CHK(ecp_mul_restartable_internal(grp, R, m, P, 2797 NULL, NULL, rs_ctx)); 2798 } 2799 2800 cleanup: 2801 mbedtls_mpi_free(&tmp); 2802 2803 return ret; 2804 } 2805 2806 /* 2807 * Restartable linear combination 2808 * NOT constant-time 2809 */ 2810 int mbedtls_ecp_muladd_restartable( 2811 mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2812 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2813 const mbedtls_mpi *n, const mbedtls_ecp_point *Q, 2814 mbedtls_ecp_restart_ctx *rs_ctx) 2815 { 2816 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 2817 mbedtls_ecp_point mP; 2818 mbedtls_ecp_point *pmP = &mP; 2819 mbedtls_ecp_point *pR = R; 2820 mbedtls_mpi tmp[4]; 2821 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2822 char is_grp_capable = 0; 2823 #endif 2824 if (mbedtls_ecp_get_type(grp) != MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) { 2825 return MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 2826 } 2827 2828 mbedtls_ecp_point_init(&mP); 2829 mpi_init_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi)); 2830 2831 ECP_RS_ENTER(ma); 2832 2833 #if defined(MBEDTLS_ECP_RESTARTABLE) 2834 if (rs_ctx != NULL && rs_ctx->ma != NULL) { 2835 /* redirect intermediate results to restart context */ 2836 pmP = &rs_ctx->ma->mP; 2837 pR = &rs_ctx->ma->R; 2838 2839 /* jump to next operation */ 2840 if (rs_ctx->ma->state == ecp_rsma_mul2) { 2841 goto mul2; 2842 } 2843 if (rs_ctx->ma->state == ecp_rsma_add) { 2844 goto add; 2845 } 2846 if (rs_ctx->ma->state == ecp_rsma_norm) { 2847 goto norm; 2848 } 2849 } 2850 #endif /* MBEDTLS_ECP_RESTARTABLE */ 2851 2852 MBEDTLS_MPI_CHK(mbedtls_ecp_mul_shortcuts(grp, pmP, m, P, rs_ctx)); 2853 #if defined(MBEDTLS_ECP_RESTARTABLE) 2854 if (rs_ctx != NULL && rs_ctx->ma != NULL) { 2855 rs_ctx->ma->state = ecp_rsma_mul2; 2856 } 2857 2858 mul2: 2859 #endif 2860 MBEDTLS_MPI_CHK(mbedtls_ecp_mul_shortcuts(grp, pR, n, Q, rs_ctx)); 2861 2862 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2863 if ((is_grp_capable = mbedtls_internal_ecp_grp_capable(grp))) { 2864 MBEDTLS_MPI_CHK(mbedtls_internal_ecp_init(grp)); 2865 } 2866 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2867 2868 #if defined(MBEDTLS_ECP_RESTARTABLE) 2869 if (rs_ctx != NULL && rs_ctx->ma != NULL) { 2870 rs_ctx->ma->state = ecp_rsma_add; 2871 } 2872 2873 add: 2874 #endif 2875 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_ADD); 2876 MBEDTLS_MPI_CHK(ecp_add_mixed(grp, pR, pmP, pR, tmp)); 2877 #if defined(MBEDTLS_ECP_RESTARTABLE) 2878 if (rs_ctx != NULL && rs_ctx->ma != NULL) { 2879 rs_ctx->ma->state = ecp_rsma_norm; 2880 } 2881 2882 norm: 2883 #endif 2884 MBEDTLS_ECP_BUDGET(MBEDTLS_ECP_OPS_INV); 2885 MBEDTLS_MPI_CHK(ecp_normalize_jac(grp, pR)); 2886 2887 #if defined(MBEDTLS_ECP_RESTARTABLE) 2888 if (rs_ctx != NULL && rs_ctx->ma != NULL) { 2889 MBEDTLS_MPI_CHK(mbedtls_ecp_copy(R, pR)); 2890 } 2891 #endif 2892 2893 cleanup: 2894 2895 mpi_free_many(tmp, sizeof(tmp) / sizeof(mbedtls_mpi)); 2896 2897 #if defined(MBEDTLS_ECP_INTERNAL_ALT) 2898 if (is_grp_capable) { 2899 mbedtls_internal_ecp_free(grp); 2900 } 2901 #endif /* MBEDTLS_ECP_INTERNAL_ALT */ 2902 2903 mbedtls_ecp_point_free(&mP); 2904 2905 ECP_RS_LEAVE(ma); 2906 2907 return ret; 2908 } 2909 2910 /* 2911 * Linear combination 2912 * NOT constant-time 2913 */ 2914 int mbedtls_ecp_muladd(mbedtls_ecp_group *grp, mbedtls_ecp_point *R, 2915 const mbedtls_mpi *m, const mbedtls_ecp_point *P, 2916 const mbedtls_mpi *n, const mbedtls_ecp_point *Q) 2917 { 2918 return mbedtls_ecp_muladd_restartable(grp, R, m, P, n, Q, NULL); 2919 } 2920 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 2921 2922 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 2923 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) 2924 #define ECP_MPI_INIT(s, n, p) {s, (n), (mbedtls_mpi_uint *)(p), 0} 2925 #define ECP_MPI_INIT_ARRAY(x) \ 2926 ECP_MPI_INIT(1, sizeof(x) / sizeof(mbedtls_mpi_uint), x) 2927 /* 2928 * Constants for the two points other than 0, 1, -1 (mod p) in 2929 * https://cr.yp.to/ecdh.html#validate 2930 * See ecp_check_pubkey_x25519(). 2931 */ 2932 static const mbedtls_mpi_uint x25519_bad_point_1[] = { 2933 MBEDTLS_BYTES_TO_T_UINT_8(0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae), 2934 MBEDTLS_BYTES_TO_T_UINT_8(0x16, 0x56, 0xe3, 0xfa, 0xf1, 0x9f, 0xc4, 0x6a), 2935 MBEDTLS_BYTES_TO_T_UINT_8(0xda, 0x09, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd), 2936 MBEDTLS_BYTES_TO_T_UINT_8(0x86, 0x62, 0x05, 0x16, 0x5f, 0x49, 0xb8, 0x00), 2937 }; 2938 static const mbedtls_mpi_uint x25519_bad_point_2[] = { 2939 MBEDTLS_BYTES_TO_T_UINT_8(0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24), 2940 MBEDTLS_BYTES_TO_T_UINT_8(0xb1, 0xd0, 0xb1, 0x55, 0x9c, 0x83, 0xef, 0x5b), 2941 MBEDTLS_BYTES_TO_T_UINT_8(0x04, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86), 2942 MBEDTLS_BYTES_TO_T_UINT_8(0xd8, 0x22, 0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57), 2943 }; 2944 static const mbedtls_mpi ecp_x25519_bad_point_1 = ECP_MPI_INIT_ARRAY( 2945 x25519_bad_point_1); 2946 static const mbedtls_mpi ecp_x25519_bad_point_2 = ECP_MPI_INIT_ARRAY( 2947 x25519_bad_point_2); 2948 #endif /* MBEDTLS_ECP_DP_CURVE25519_ENABLED */ 2949 2950 /* 2951 * Check that the input point is not one of the low-order points. 2952 * This is recommended by the "May the Fourth" paper: 2953 * https://eprint.iacr.org/2017/806.pdf 2954 * Those points are never sent by an honest peer. 2955 */ 2956 static int ecp_check_bad_points_mx(const mbedtls_mpi *X, const mbedtls_mpi *P, 2957 const mbedtls_ecp_group_id grp_id) 2958 { 2959 int ret; 2960 mbedtls_mpi XmP; 2961 2962 mbedtls_mpi_init(&XmP); 2963 2964 /* Reduce X mod P so that we only need to check values less than P. 2965 * We know X < 2^256 so we can proceed by subtraction. */ 2966 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&XmP, X)); 2967 while (mbedtls_mpi_cmp_mpi(&XmP, P) >= 0) { 2968 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&XmP, &XmP, P)); 2969 } 2970 2971 /* Check against the known bad values that are less than P. For Curve448 2972 * these are 0, 1 and -1. For Curve25519 we check the values less than P 2973 * from the following list: https://cr.yp.to/ecdh.html#validate */ 2974 if (mbedtls_mpi_cmp_int(&XmP, 1) <= 0) { /* takes care of 0 and 1 */ 2975 ret = MBEDTLS_ERR_ECP_INVALID_KEY; 2976 goto cleanup; 2977 } 2978 2979 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) 2980 if (grp_id == MBEDTLS_ECP_DP_CURVE25519) { 2981 if (mbedtls_mpi_cmp_mpi(&XmP, &ecp_x25519_bad_point_1) == 0) { 2982 ret = MBEDTLS_ERR_ECP_INVALID_KEY; 2983 goto cleanup; 2984 } 2985 2986 if (mbedtls_mpi_cmp_mpi(&XmP, &ecp_x25519_bad_point_2) == 0) { 2987 ret = MBEDTLS_ERR_ECP_INVALID_KEY; 2988 goto cleanup; 2989 } 2990 } 2991 #else 2992 (void) grp_id; 2993 #endif 2994 2995 /* Final check: check if XmP + 1 is P (final because it changes XmP!) */ 2996 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&XmP, &XmP, 1)); 2997 if (mbedtls_mpi_cmp_mpi(&XmP, P) == 0) { 2998 ret = MBEDTLS_ERR_ECP_INVALID_KEY; 2999 goto cleanup; 3000 } 3001 3002 ret = 0; 3003 3004 cleanup: 3005 mbedtls_mpi_free(&XmP); 3006 3007 return ret; 3008 } 3009 3010 /* 3011 * Check validity of a public key for Montgomery curves with x-only schemes 3012 */ 3013 static int ecp_check_pubkey_mx(const mbedtls_ecp_group *grp, const mbedtls_ecp_point *pt) 3014 { 3015 /* [Curve25519 p. 5] Just check X is the correct number of bytes */ 3016 /* Allow any public value, if it's too big then we'll just reduce it mod p 3017 * (RFC 7748 sec. 5 para. 3). */ 3018 if (mbedtls_mpi_size(&pt->X) > (grp->nbits + 7) / 8) { 3019 return MBEDTLS_ERR_ECP_INVALID_KEY; 3020 } 3021 3022 /* Implicit in all standards (as they don't consider negative numbers): 3023 * X must be non-negative. This is normally ensured by the way it's 3024 * encoded for transmission, but let's be extra sure. */ 3025 if (mbedtls_mpi_cmp_int(&pt->X, 0) < 0) { 3026 return MBEDTLS_ERR_ECP_INVALID_KEY; 3027 } 3028 3029 return ecp_check_bad_points_mx(&pt->X, &grp->P, grp->id); 3030 } 3031 #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ 3032 3033 /* 3034 * Check that a point is valid as a public key 3035 */ 3036 int mbedtls_ecp_check_pubkey(const mbedtls_ecp_group *grp, 3037 const mbedtls_ecp_point *pt) 3038 { 3039 /* Must use affine coordinates */ 3040 if (mbedtls_mpi_cmp_int(&pt->Z, 1) != 0) { 3041 return MBEDTLS_ERR_ECP_INVALID_KEY; 3042 } 3043 3044 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3045 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) { 3046 return ecp_check_pubkey_mx(grp, pt); 3047 } 3048 #endif 3049 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3050 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) { 3051 return ecp_check_pubkey_sw(grp, pt); 3052 } 3053 #endif 3054 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 3055 } 3056 3057 /* 3058 * Check that an mbedtls_mpi is valid as a private key 3059 */ 3060 int mbedtls_ecp_check_privkey(const mbedtls_ecp_group *grp, 3061 const mbedtls_mpi *d) 3062 { 3063 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3064 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) { 3065 /* see RFC 7748 sec. 5 para. 5 */ 3066 if (mbedtls_mpi_get_bit(d, 0) != 0 || 3067 mbedtls_mpi_get_bit(d, 1) != 0 || 3068 mbedtls_mpi_bitlen(d) - 1 != grp->nbits) { /* mbedtls_mpi_bitlen is one-based! */ 3069 return MBEDTLS_ERR_ECP_INVALID_KEY; 3070 } 3071 3072 /* see [Curve25519] page 5 */ 3073 if (grp->nbits == 254 && mbedtls_mpi_get_bit(d, 2) != 0) { 3074 return MBEDTLS_ERR_ECP_INVALID_KEY; 3075 } 3076 3077 return 0; 3078 } 3079 #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ 3080 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3081 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) { 3082 /* see SEC1 3.2 */ 3083 if (mbedtls_mpi_cmp_int(d, 1) < 0 || 3084 mbedtls_mpi_cmp_mpi(d, &grp->N) >= 0) { 3085 return MBEDTLS_ERR_ECP_INVALID_KEY; 3086 } else { 3087 return 0; 3088 } 3089 } 3090 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 3091 3092 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 3093 } 3094 3095 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3096 MBEDTLS_STATIC_TESTABLE 3097 int mbedtls_ecp_gen_privkey_mx(size_t high_bit, 3098 mbedtls_mpi *d, 3099 int (*f_rng)(void *, unsigned char *, size_t), 3100 void *p_rng) 3101 { 3102 int ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 3103 size_t n_random_bytes = high_bit / 8 + 1; 3104 3105 /* [Curve25519] page 5 */ 3106 /* Generate a (high_bit+1)-bit random number by generating just enough 3107 * random bytes, then shifting out extra bits from the top (necessary 3108 * when (high_bit+1) is not a multiple of 8). */ 3109 MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(d, n_random_bytes, 3110 f_rng, p_rng)); 3111 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(d, 8 * n_random_bytes - high_bit - 1)); 3112 3113 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, high_bit, 1)); 3114 3115 /* Make sure the last two bits are unset for Curve448, three bits for 3116 Curve25519 */ 3117 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, 0, 0)); 3118 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, 1, 0)); 3119 if (high_bit == 254) { 3120 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(d, 2, 0)); 3121 } 3122 3123 cleanup: 3124 return ret; 3125 } 3126 #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ 3127 3128 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3129 static int mbedtls_ecp_gen_privkey_sw( 3130 const mbedtls_mpi *N, mbedtls_mpi *d, 3131 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng) 3132 { 3133 int ret = mbedtls_mpi_random(d, 1, N, f_rng, p_rng); 3134 switch (ret) { 3135 case MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: 3136 return MBEDTLS_ERR_ECP_RANDOM_FAILED; 3137 default: 3138 return ret; 3139 } 3140 } 3141 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 3142 3143 /* 3144 * Generate a private key 3145 */ 3146 int mbedtls_ecp_gen_privkey(const mbedtls_ecp_group *grp, 3147 mbedtls_mpi *d, 3148 int (*f_rng)(void *, unsigned char *, size_t), 3149 void *p_rng) 3150 { 3151 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3152 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) { 3153 return mbedtls_ecp_gen_privkey_mx(grp->nbits, d, f_rng, p_rng); 3154 } 3155 #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ 3156 3157 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3158 if (mbedtls_ecp_get_type(grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) { 3159 return mbedtls_ecp_gen_privkey_sw(&grp->N, d, f_rng, p_rng); 3160 } 3161 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 3162 3163 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 3164 } 3165 3166 /* 3167 * Generate a keypair with configurable base point 3168 */ 3169 int mbedtls_ecp_gen_keypair_base(mbedtls_ecp_group *grp, 3170 const mbedtls_ecp_point *G, 3171 mbedtls_mpi *d, mbedtls_ecp_point *Q, 3172 int (*f_rng)(void *, unsigned char *, size_t), 3173 void *p_rng) 3174 { 3175 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 3176 MBEDTLS_MPI_CHK(mbedtls_ecp_gen_privkey(grp, d, f_rng, p_rng)); 3177 MBEDTLS_MPI_CHK(mbedtls_ecp_mul(grp, Q, d, G, f_rng, p_rng)); 3178 3179 cleanup: 3180 return ret; 3181 } 3182 3183 /* 3184 * Generate key pair, wrapper for conventional base point 3185 */ 3186 int mbedtls_ecp_gen_keypair(mbedtls_ecp_group *grp, 3187 mbedtls_mpi *d, mbedtls_ecp_point *Q, 3188 int (*f_rng)(void *, unsigned char *, size_t), 3189 void *p_rng) 3190 { 3191 return mbedtls_ecp_gen_keypair_base(grp, &grp->G, d, Q, f_rng, p_rng); 3192 } 3193 3194 /* 3195 * Generate a keypair, prettier wrapper 3196 */ 3197 int mbedtls_ecp_gen_key(mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key, 3198 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng) 3199 { 3200 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 3201 if ((ret = mbedtls_ecp_group_load(&key->grp, grp_id)) != 0) { 3202 return ret; 3203 } 3204 3205 return mbedtls_ecp_gen_keypair(&key->grp, &key->d, &key->Q, f_rng, p_rng); 3206 } 3207 3208 #define ECP_CURVE25519_KEY_SIZE 32 3209 #define ECP_CURVE448_KEY_SIZE 56 3210 /* 3211 * Read a private key. 3212 */ 3213 int mbedtls_ecp_read_key(mbedtls_ecp_group_id grp_id, mbedtls_ecp_keypair *key, 3214 const unsigned char *buf, size_t buflen) 3215 { 3216 int ret = 0; 3217 3218 if ((ret = mbedtls_ecp_group_load(&key->grp, grp_id)) != 0) { 3219 return ret; 3220 } 3221 3222 ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 3223 3224 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3225 if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) { 3226 /* 3227 * Mask the key as mandated by RFC7748 for Curve25519 and Curve448. 3228 */ 3229 if (grp_id == MBEDTLS_ECP_DP_CURVE25519) { 3230 if (buflen != ECP_CURVE25519_KEY_SIZE) { 3231 return MBEDTLS_ERR_ECP_INVALID_KEY; 3232 } 3233 3234 MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary_le(&key->d, buf, buflen)); 3235 3236 /* Set the three least significant bits to 0 */ 3237 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 0, 0)); 3238 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 1, 0)); 3239 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 2, 0)); 3240 3241 /* Set the most significant bit to 0 */ 3242 MBEDTLS_MPI_CHK( 3243 mbedtls_mpi_set_bit(&key->d, 3244 ECP_CURVE25519_KEY_SIZE * 8 - 1, 0) 3245 ); 3246 3247 /* Set the second most significant bit to 1 */ 3248 MBEDTLS_MPI_CHK( 3249 mbedtls_mpi_set_bit(&key->d, 3250 ECP_CURVE25519_KEY_SIZE * 8 - 2, 1) 3251 ); 3252 } else if (grp_id == MBEDTLS_ECP_DP_CURVE448) { 3253 if (buflen != ECP_CURVE448_KEY_SIZE) { 3254 return MBEDTLS_ERR_ECP_INVALID_KEY; 3255 } 3256 3257 MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary_le(&key->d, buf, buflen)); 3258 3259 /* Set the two least significant bits to 0 */ 3260 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 0, 0)); 3261 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(&key->d, 1, 0)); 3262 3263 /* Set the most significant bit to 1 */ 3264 MBEDTLS_MPI_CHK( 3265 mbedtls_mpi_set_bit(&key->d, 3266 ECP_CURVE448_KEY_SIZE * 8 - 1, 1) 3267 ); 3268 } 3269 } 3270 3271 #endif 3272 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3273 if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) { 3274 MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary(&key->d, buf, buflen)); 3275 3276 MBEDTLS_MPI_CHK(mbedtls_ecp_check_privkey(&key->grp, &key->d)); 3277 } 3278 3279 #endif 3280 cleanup: 3281 3282 if (ret != 0) { 3283 mbedtls_mpi_free(&key->d); 3284 } 3285 3286 return ret; 3287 } 3288 3289 /* 3290 * Write a private key. 3291 */ 3292 int mbedtls_ecp_write_key(mbedtls_ecp_keypair *key, 3293 unsigned char *buf, size_t buflen) 3294 { 3295 int ret = MBEDTLS_ERR_ECP_FEATURE_UNAVAILABLE; 3296 3297 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3298 if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_MONTGOMERY) { 3299 if (key->grp.id == MBEDTLS_ECP_DP_CURVE25519) { 3300 if (buflen < ECP_CURVE25519_KEY_SIZE) { 3301 return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL; 3302 } 3303 3304 } else if (key->grp.id == MBEDTLS_ECP_DP_CURVE448) { 3305 if (buflen < ECP_CURVE448_KEY_SIZE) { 3306 return MBEDTLS_ERR_ECP_BUFFER_TOO_SMALL; 3307 } 3308 } 3309 MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary_le(&key->d, buf, buflen)); 3310 } 3311 #endif 3312 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3313 if (mbedtls_ecp_get_type(&key->grp) == MBEDTLS_ECP_TYPE_SHORT_WEIERSTRASS) { 3314 MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&key->d, buf, buflen)); 3315 } 3316 3317 #endif 3318 cleanup: 3319 3320 return ret; 3321 } 3322 3323 3324 /* 3325 * Check a public-private key pair 3326 */ 3327 int mbedtls_ecp_check_pub_priv( 3328 const mbedtls_ecp_keypair *pub, const mbedtls_ecp_keypair *prv, 3329 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng) 3330 { 3331 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 3332 mbedtls_ecp_point Q; 3333 mbedtls_ecp_group grp; 3334 if (pub->grp.id == MBEDTLS_ECP_DP_NONE || 3335 pub->grp.id != prv->grp.id || 3336 mbedtls_mpi_cmp_mpi(&pub->Q.X, &prv->Q.X) || 3337 mbedtls_mpi_cmp_mpi(&pub->Q.Y, &prv->Q.Y) || 3338 mbedtls_mpi_cmp_mpi(&pub->Q.Z, &prv->Q.Z)) { 3339 return MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 3340 } 3341 3342 mbedtls_ecp_point_init(&Q); 3343 mbedtls_ecp_group_init(&grp); 3344 3345 /* mbedtls_ecp_mul() needs a non-const group... */ 3346 mbedtls_ecp_group_copy(&grp, &prv->grp); 3347 3348 /* Also checks d is valid */ 3349 MBEDTLS_MPI_CHK(mbedtls_ecp_mul(&grp, &Q, &prv->d, &prv->grp.G, f_rng, p_rng)); 3350 3351 if (mbedtls_mpi_cmp_mpi(&Q.X, &prv->Q.X) || 3352 mbedtls_mpi_cmp_mpi(&Q.Y, &prv->Q.Y) || 3353 mbedtls_mpi_cmp_mpi(&Q.Z, &prv->Q.Z)) { 3354 ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA; 3355 goto cleanup; 3356 } 3357 3358 cleanup: 3359 mbedtls_ecp_point_free(&Q); 3360 mbedtls_ecp_group_free(&grp); 3361 3362 return ret; 3363 } 3364 3365 /* 3366 * Export generic key-pair parameters. 3367 */ 3368 int mbedtls_ecp_export(const mbedtls_ecp_keypair *key, mbedtls_ecp_group *grp, 3369 mbedtls_mpi *d, mbedtls_ecp_point *Q) 3370 { 3371 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 3372 3373 if ((ret = mbedtls_ecp_group_copy(grp, &key->grp)) != 0) { 3374 return ret; 3375 } 3376 3377 if ((ret = mbedtls_mpi_copy(d, &key->d)) != 0) { 3378 return ret; 3379 } 3380 3381 if ((ret = mbedtls_ecp_copy(Q, &key->Q)) != 0) { 3382 return ret; 3383 } 3384 3385 return 0; 3386 } 3387 3388 #if defined(MBEDTLS_SELF_TEST) 3389 3390 /* 3391 * PRNG for test - !!!INSECURE NEVER USE IN PRODUCTION!!! 3392 * 3393 * This is the linear congruential generator from numerical recipes, 3394 * except we only use the low byte as the output. See 3395 * https://en.wikipedia.org/wiki/Linear_congruential_generator#Parameters_in_common_use 3396 */ 3397 static int self_test_rng(void *ctx, unsigned char *out, size_t len) 3398 { 3399 static uint32_t state = 42; 3400 3401 (void) ctx; 3402 3403 for (size_t i = 0; i < len; i++) { 3404 state = state * 1664525u + 1013904223u; 3405 out[i] = (unsigned char) state; 3406 } 3407 3408 return 0; 3409 } 3410 3411 /* Adjust the exponent to be a valid private point for the specified curve. 3412 * This is sometimes necessary because we use a single set of exponents 3413 * for all curves but the validity of values depends on the curve. */ 3414 static int self_test_adjust_exponent(const mbedtls_ecp_group *grp, 3415 mbedtls_mpi *m) 3416 { 3417 int ret = 0; 3418 switch (grp->id) { 3419 /* If Curve25519 is available, then that's what we use for the 3420 * Montgomery test, so we don't need the adjustment code. */ 3421 #if !defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) 3422 #if defined(MBEDTLS_ECP_DP_CURVE448_ENABLED) 3423 case MBEDTLS_ECP_DP_CURVE448: 3424 /* Move highest bit from 254 to N-1. Setting bit N-1 is 3425 * necessary to enforce the highest-bit-set constraint. */ 3426 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(m, 254, 0)); 3427 MBEDTLS_MPI_CHK(mbedtls_mpi_set_bit(m, grp->nbits, 1)); 3428 /* Copy second-highest bit from 253 to N-2. This is not 3429 * necessary but improves the test variety a bit. */ 3430 MBEDTLS_MPI_CHK( 3431 mbedtls_mpi_set_bit(m, grp->nbits - 1, 3432 mbedtls_mpi_get_bit(m, 253))); 3433 break; 3434 #endif 3435 #endif /* ! defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) */ 3436 default: 3437 /* Non-Montgomery curves and Curve25519 need no adjustment. */ 3438 (void) grp; 3439 (void) m; 3440 goto cleanup; 3441 } 3442 cleanup: 3443 return ret; 3444 } 3445 3446 /* Calculate R = m.P for each m in exponents. Check that the number of 3447 * basic operations doesn't depend on the value of m. */ 3448 static int self_test_point(int verbose, 3449 mbedtls_ecp_group *grp, 3450 mbedtls_ecp_point *R, 3451 mbedtls_mpi *m, 3452 const mbedtls_ecp_point *P, 3453 const char *const *exponents, 3454 size_t n_exponents) 3455 { 3456 int ret = 0; 3457 size_t i = 0; 3458 unsigned long add_c_prev, dbl_c_prev, mul_c_prev; 3459 add_count = 0; 3460 dbl_count = 0; 3461 mul_count = 0; 3462 3463 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(m, 16, exponents[0])); 3464 MBEDTLS_MPI_CHK(self_test_adjust_exponent(grp, m)); 3465 MBEDTLS_MPI_CHK(mbedtls_ecp_mul(grp, R, m, P, self_test_rng, NULL)); 3466 3467 for (i = 1; i < n_exponents; i++) { 3468 add_c_prev = add_count; 3469 dbl_c_prev = dbl_count; 3470 mul_c_prev = mul_count; 3471 add_count = 0; 3472 dbl_count = 0; 3473 mul_count = 0; 3474 3475 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(m, 16, exponents[i])); 3476 MBEDTLS_MPI_CHK(self_test_adjust_exponent(grp, m)); 3477 MBEDTLS_MPI_CHK(mbedtls_ecp_mul(grp, R, m, P, self_test_rng, NULL)); 3478 3479 if (add_count != add_c_prev || 3480 dbl_count != dbl_c_prev || 3481 mul_count != mul_c_prev) { 3482 ret = 1; 3483 break; 3484 } 3485 } 3486 3487 cleanup: 3488 if (verbose != 0) { 3489 if (ret != 0) { 3490 mbedtls_printf("failed (%u)\n", (unsigned int) i); 3491 } else { 3492 mbedtls_printf("passed\n"); 3493 } 3494 } 3495 return ret; 3496 } 3497 3498 /* 3499 * Checkup routine 3500 */ 3501 int mbedtls_ecp_self_test(int verbose) 3502 { 3503 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 3504 mbedtls_ecp_group grp; 3505 mbedtls_ecp_point R, P; 3506 mbedtls_mpi m; 3507 3508 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3509 /* Exponents especially adapted for secp192k1, which has the lowest 3510 * order n of all supported curves (secp192r1 is in a slightly larger 3511 * field but the order of its base point is slightly smaller). */ 3512 const char *sw_exponents[] = 3513 { 3514 "000000000000000000000000000000000000000000000001", /* one */ 3515 "FFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8C", /* n - 1 */ 3516 "5EA6F389A38B8BC81E767753B15AA5569E1782E30ABE7D25", /* random */ 3517 "400000000000000000000000000000000000000000000000", /* one and zeros */ 3518 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", /* all ones */ 3519 "555555555555555555555555555555555555555555555555", /* 101010... */ 3520 }; 3521 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 3522 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3523 const char *m_exponents[] = 3524 { 3525 /* Valid private values for Curve25519. In a build with Curve448 3526 * but not Curve25519, they will be adjusted in 3527 * self_test_adjust_exponent(). */ 3528 "4000000000000000000000000000000000000000000000000000000000000000", 3529 "5C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C3C30", 3530 "5715ECCE24583F7A7023C24164390586842E816D7280A49EF6DF4EAE6B280BF8", 3531 "41A2B017516F6D254E1F002BCCBADD54BE30F8CEC737A0E912B4963B6BA74460", 3532 "5555555555555555555555555555555555555555555555555555555555555550", 3533 "7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF8", 3534 }; 3535 #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ 3536 3537 mbedtls_ecp_group_init(&grp); 3538 mbedtls_ecp_point_init(&R); 3539 mbedtls_ecp_point_init(&P); 3540 mbedtls_mpi_init(&m); 3541 3542 #if defined(MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED) 3543 /* Use secp192r1 if available, or any available curve */ 3544 #if defined(MBEDTLS_ECP_DP_SECP192R1_ENABLED) 3545 MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, MBEDTLS_ECP_DP_SECP192R1)); 3546 #else 3547 MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, mbedtls_ecp_curve_list()->grp_id)); 3548 #endif 3549 3550 if (verbose != 0) { 3551 mbedtls_printf(" ECP SW test #1 (constant op_count, base point G): "); 3552 } 3553 /* Do a dummy multiplication first to trigger precomputation */ 3554 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&m, 2)); 3555 MBEDTLS_MPI_CHK(mbedtls_ecp_mul(&grp, &P, &m, &grp.G, self_test_rng, NULL)); 3556 ret = self_test_point(verbose, 3557 &grp, &R, &m, &grp.G, 3558 sw_exponents, 3559 sizeof(sw_exponents) / sizeof(sw_exponents[0])); 3560 if (ret != 0) { 3561 goto cleanup; 3562 } 3563 3564 if (verbose != 0) { 3565 mbedtls_printf(" ECP SW test #2 (constant op_count, other point): "); 3566 } 3567 /* We computed P = 2G last time, use it */ 3568 ret = self_test_point(verbose, 3569 &grp, &R, &m, &P, 3570 sw_exponents, 3571 sizeof(sw_exponents) / sizeof(sw_exponents[0])); 3572 if (ret != 0) { 3573 goto cleanup; 3574 } 3575 3576 mbedtls_ecp_group_free(&grp); 3577 mbedtls_ecp_point_free(&R); 3578 #endif /* MBEDTLS_ECP_SHORT_WEIERSTRASS_ENABLED */ 3579 3580 #if defined(MBEDTLS_ECP_MONTGOMERY_ENABLED) 3581 if (verbose != 0) { 3582 mbedtls_printf(" ECP Montgomery test (constant op_count): "); 3583 } 3584 #if defined(MBEDTLS_ECP_DP_CURVE25519_ENABLED) 3585 MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, MBEDTLS_ECP_DP_CURVE25519)); 3586 #elif defined(MBEDTLS_ECP_DP_CURVE448_ENABLED) 3587 MBEDTLS_MPI_CHK(mbedtls_ecp_group_load(&grp, MBEDTLS_ECP_DP_CURVE448)); 3588 #else 3589 #error "MBEDTLS_ECP_MONTGOMERY_ENABLED is defined, but no curve is supported for self-test" 3590 #endif 3591 ret = self_test_point(verbose, 3592 &grp, &R, &m, &grp.G, 3593 m_exponents, 3594 sizeof(m_exponents) / sizeof(m_exponents[0])); 3595 if (ret != 0) { 3596 goto cleanup; 3597 } 3598 #endif /* MBEDTLS_ECP_MONTGOMERY_ENABLED */ 3599 3600 cleanup: 3601 3602 if (ret < 0 && verbose != 0) { 3603 mbedtls_printf("Unexpected error, return code = %08X\n", (unsigned int) ret); 3604 } 3605 3606 mbedtls_ecp_group_free(&grp); 3607 mbedtls_ecp_point_free(&R); 3608 mbedtls_ecp_point_free(&P); 3609 mbedtls_mpi_free(&m); 3610 3611 if (verbose != 0) { 3612 mbedtls_printf("\n"); 3613 } 3614 3615 return ret; 3616 } 3617 3618 #endif /* MBEDTLS_SELF_TEST */ 3619 3620 #endif /* !MBEDTLS_ECP_ALT */ 3621 3622 #endif /* MBEDTLS_ECP_C */ 3623