1 /* 2 * Copyright 1995-2019 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the OpenSSL license (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9 10 #include "internal/cryptlib.h" 11 #include "internal/bn_int.h" 12 #include "rsa_locl.h" 13 #include "internal/constant_time_locl.h" 14 15 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from, 16 unsigned char *to, RSA *rsa, int padding); 17 static int rsa_ossl_private_encrypt(int flen, const unsigned char *from, 18 unsigned char *to, RSA *rsa, int padding); 19 static int rsa_ossl_public_decrypt(int flen, const unsigned char *from, 20 unsigned char *to, RSA *rsa, int padding); 21 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from, 22 unsigned char *to, RSA *rsa, int padding); 23 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *i, RSA *rsa, 24 BN_CTX *ctx); 25 static int rsa_ossl_init(RSA *rsa); 26 static int rsa_ossl_finish(RSA *rsa); 27 static RSA_METHOD rsa_pkcs1_ossl_meth = { 28 "OpenSSL PKCS#1 RSA", 29 rsa_ossl_public_encrypt, 30 rsa_ossl_public_decrypt, /* signature verification */ 31 rsa_ossl_private_encrypt, /* signing */ 32 rsa_ossl_private_decrypt, 33 rsa_ossl_mod_exp, 34 BN_mod_exp_mont, /* XXX probably we should not use Montgomery 35 * if e == 3 */ 36 rsa_ossl_init, 37 rsa_ossl_finish, 38 RSA_FLAG_FIPS_METHOD, /* flags */ 39 NULL, 40 0, /* rsa_sign */ 41 0, /* rsa_verify */ 42 NULL, /* rsa_keygen */ 43 NULL /* rsa_multi_prime_keygen */ 44 }; 45 46 static const RSA_METHOD *default_RSA_meth = &rsa_pkcs1_ossl_meth; 47 48 void RSA_set_default_method(const RSA_METHOD *meth) 49 { 50 default_RSA_meth = meth; 51 } 52 53 const RSA_METHOD *RSA_get_default_method(void) 54 { 55 return default_RSA_meth; 56 } 57 58 const RSA_METHOD *RSA_PKCS1_OpenSSL(void) 59 { 60 return &rsa_pkcs1_ossl_meth; 61 } 62 63 const RSA_METHOD *RSA_null_method(void) 64 { 65 return NULL; 66 } 67 68 static int rsa_ossl_public_encrypt(int flen, const unsigned char *from, 69 unsigned char *to, RSA *rsa, int padding) 70 { 71 BIGNUM *f, *ret; 72 int i, num = 0, r = -1; 73 unsigned char *buf = NULL; 74 BN_CTX *ctx = NULL; 75 76 if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) { 77 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_MODULUS_TOO_LARGE); 78 return -1; 79 } 80 81 if (BN_ucmp(rsa->n, rsa->e) <= 0) { 82 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_BAD_E_VALUE); 83 return -1; 84 } 85 86 /* for large moduli, enforce exponent limit */ 87 if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) { 88 if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) { 89 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_BAD_E_VALUE); 90 return -1; 91 } 92 } 93 94 if ((ctx = BN_CTX_new()) == NULL) 95 goto err; 96 BN_CTX_start(ctx); 97 f = BN_CTX_get(ctx); 98 ret = BN_CTX_get(ctx); 99 num = BN_num_bytes(rsa->n); 100 buf = OPENSSL_malloc(num); 101 if (ret == NULL || buf == NULL) { 102 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, ERR_R_MALLOC_FAILURE); 103 goto err; 104 } 105 106 switch (padding) { 107 case RSA_PKCS1_PADDING: 108 i = RSA_padding_add_PKCS1_type_2(buf, num, from, flen); 109 break; 110 case RSA_PKCS1_OAEP_PADDING: 111 i = RSA_padding_add_PKCS1_OAEP(buf, num, from, flen, NULL, 0); 112 break; 113 case RSA_SSLV23_PADDING: 114 i = RSA_padding_add_SSLv23(buf, num, from, flen); 115 break; 116 case RSA_NO_PADDING: 117 i = RSA_padding_add_none(buf, num, from, flen); 118 break; 119 default: 120 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, RSA_R_UNKNOWN_PADDING_TYPE); 121 goto err; 122 } 123 if (i <= 0) 124 goto err; 125 126 if (BN_bin2bn(buf, num, f) == NULL) 127 goto err; 128 129 if (BN_ucmp(f, rsa->n) >= 0) { 130 /* usually the padding functions would catch this */ 131 RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, 132 RSA_R_DATA_TOO_LARGE_FOR_MODULUS); 133 goto err; 134 } 135 136 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) 137 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, 138 rsa->n, ctx)) 139 goto err; 140 141 if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx, 142 rsa->_method_mod_n)) 143 goto err; 144 145 /* 146 * BN_bn2binpad puts in leading 0 bytes if the number is less than 147 * the length of the modulus. 148 */ 149 r = BN_bn2binpad(ret, to, num); 150 err: 151 BN_CTX_end(ctx); 152 BN_CTX_free(ctx); 153 OPENSSL_clear_free(buf, num); 154 return r; 155 } 156 157 static BN_BLINDING *rsa_get_blinding(RSA *rsa, int *local, BN_CTX *ctx) 158 { 159 BN_BLINDING *ret; 160 161 CRYPTO_THREAD_write_lock(rsa->lock); 162 163 if (rsa->blinding == NULL) { 164 rsa->blinding = RSA_setup_blinding(rsa, ctx); 165 } 166 167 ret = rsa->blinding; 168 if (ret == NULL) 169 goto err; 170 171 if (BN_BLINDING_is_current_thread(ret)) { 172 /* rsa->blinding is ours! */ 173 174 *local = 1; 175 } else { 176 /* resort to rsa->mt_blinding instead */ 177 178 /* 179 * instructs rsa_blinding_convert(), rsa_blinding_invert() that the 180 * BN_BLINDING is shared, meaning that accesses require locks, and 181 * that the blinding factor must be stored outside the BN_BLINDING 182 */ 183 *local = 0; 184 185 if (rsa->mt_blinding == NULL) { 186 rsa->mt_blinding = RSA_setup_blinding(rsa, ctx); 187 } 188 ret = rsa->mt_blinding; 189 } 190 191 err: 192 CRYPTO_THREAD_unlock(rsa->lock); 193 return ret; 194 } 195 196 static int rsa_blinding_convert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind, 197 BN_CTX *ctx) 198 { 199 if (unblind == NULL) { 200 /* 201 * Local blinding: store the unblinding factor in BN_BLINDING. 202 */ 203 return BN_BLINDING_convert_ex(f, NULL, b, ctx); 204 } else { 205 /* 206 * Shared blinding: store the unblinding factor outside BN_BLINDING. 207 */ 208 int ret; 209 210 BN_BLINDING_lock(b); 211 ret = BN_BLINDING_convert_ex(f, unblind, b, ctx); 212 BN_BLINDING_unlock(b); 213 214 return ret; 215 } 216 } 217 218 static int rsa_blinding_invert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind, 219 BN_CTX *ctx) 220 { 221 /* 222 * For local blinding, unblind is set to NULL, and BN_BLINDING_invert_ex 223 * will use the unblinding factor stored in BN_BLINDING. If BN_BLINDING 224 * is shared between threads, unblind must be non-null: 225 * BN_BLINDING_invert_ex will then use the local unblinding factor, and 226 * will only read the modulus from BN_BLINDING. In both cases it's safe 227 * to access the blinding without a lock. 228 */ 229 return BN_BLINDING_invert_ex(f, unblind, b, ctx); 230 } 231 232 /* signing */ 233 static int rsa_ossl_private_encrypt(int flen, const unsigned char *from, 234 unsigned char *to, RSA *rsa, int padding) 235 { 236 BIGNUM *f, *ret, *res; 237 int i, num = 0, r = -1; 238 unsigned char *buf = NULL; 239 BN_CTX *ctx = NULL; 240 int local_blinding = 0; 241 /* 242 * Used only if the blinding structure is shared. A non-NULL unblind 243 * instructs rsa_blinding_convert() and rsa_blinding_invert() to store 244 * the unblinding factor outside the blinding structure. 245 */ 246 BIGNUM *unblind = NULL; 247 BN_BLINDING *blinding = NULL; 248 249 if ((ctx = BN_CTX_new()) == NULL) 250 goto err; 251 BN_CTX_start(ctx); 252 f = BN_CTX_get(ctx); 253 ret = BN_CTX_get(ctx); 254 num = BN_num_bytes(rsa->n); 255 buf = OPENSSL_malloc(num); 256 if (ret == NULL || buf == NULL) { 257 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE); 258 goto err; 259 } 260 261 switch (padding) { 262 case RSA_PKCS1_PADDING: 263 i = RSA_padding_add_PKCS1_type_1(buf, num, from, flen); 264 break; 265 case RSA_X931_PADDING: 266 i = RSA_padding_add_X931(buf, num, from, flen); 267 break; 268 case RSA_NO_PADDING: 269 i = RSA_padding_add_none(buf, num, from, flen); 270 break; 271 case RSA_SSLV23_PADDING: 272 default: 273 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, RSA_R_UNKNOWN_PADDING_TYPE); 274 goto err; 275 } 276 if (i <= 0) 277 goto err; 278 279 if (BN_bin2bn(buf, num, f) == NULL) 280 goto err; 281 282 if (BN_ucmp(f, rsa->n) >= 0) { 283 /* usually the padding functions would catch this */ 284 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, 285 RSA_R_DATA_TOO_LARGE_FOR_MODULUS); 286 goto err; 287 } 288 289 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) 290 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, 291 rsa->n, ctx)) 292 goto err; 293 294 if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) { 295 blinding = rsa_get_blinding(rsa, &local_blinding, ctx); 296 if (blinding == NULL) { 297 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_INTERNAL_ERROR); 298 goto err; 299 } 300 } 301 302 if (blinding != NULL) { 303 if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) { 304 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE); 305 goto err; 306 } 307 if (!rsa_blinding_convert(blinding, f, unblind, ctx)) 308 goto err; 309 } 310 311 if ((rsa->flags & RSA_FLAG_EXT_PKEY) || 312 (rsa->version == RSA_ASN1_VERSION_MULTI) || 313 ((rsa->p != NULL) && 314 (rsa->q != NULL) && 315 (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) { 316 if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx)) 317 goto err; 318 } else { 319 BIGNUM *d = BN_new(); 320 if (d == NULL) { 321 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE); 322 goto err; 323 } 324 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); 325 326 if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx, 327 rsa->_method_mod_n)) { 328 BN_free(d); 329 goto err; 330 } 331 /* We MUST free d before any further use of rsa->d */ 332 BN_free(d); 333 } 334 335 if (blinding) 336 if (!rsa_blinding_invert(blinding, ret, unblind, ctx)) 337 goto err; 338 339 if (padding == RSA_X931_PADDING) { 340 if (!BN_sub(f, rsa->n, ret)) 341 goto err; 342 if (BN_cmp(ret, f) > 0) 343 res = f; 344 else 345 res = ret; 346 } else { 347 res = ret; 348 } 349 350 /* 351 * BN_bn2binpad puts in leading 0 bytes if the number is less than 352 * the length of the modulus. 353 */ 354 r = BN_bn2binpad(res, to, num); 355 err: 356 BN_CTX_end(ctx); 357 BN_CTX_free(ctx); 358 OPENSSL_clear_free(buf, num); 359 return r; 360 } 361 362 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from, 363 unsigned char *to, RSA *rsa, int padding) 364 { 365 BIGNUM *f, *ret; 366 int j, num = 0, r = -1; 367 unsigned char *buf = NULL; 368 BN_CTX *ctx = NULL; 369 int local_blinding = 0; 370 /* 371 * Used only if the blinding structure is shared. A non-NULL unblind 372 * instructs rsa_blinding_convert() and rsa_blinding_invert() to store 373 * the unblinding factor outside the blinding structure. 374 */ 375 BIGNUM *unblind = NULL; 376 BN_BLINDING *blinding = NULL; 377 378 if ((ctx = BN_CTX_new()) == NULL) 379 goto err; 380 BN_CTX_start(ctx); 381 f = BN_CTX_get(ctx); 382 ret = BN_CTX_get(ctx); 383 num = BN_num_bytes(rsa->n); 384 buf = OPENSSL_malloc(num); 385 if (ret == NULL || buf == NULL) { 386 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE); 387 goto err; 388 } 389 390 /* 391 * This check was for equality but PGP does evil things and chops off the 392 * top '0' bytes 393 */ 394 if (flen > num) { 395 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, 396 RSA_R_DATA_GREATER_THAN_MOD_LEN); 397 goto err; 398 } 399 400 /* make data into a big number */ 401 if (BN_bin2bn(from, (int)flen, f) == NULL) 402 goto err; 403 404 if (BN_ucmp(f, rsa->n) >= 0) { 405 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, 406 RSA_R_DATA_TOO_LARGE_FOR_MODULUS); 407 goto err; 408 } 409 410 if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) { 411 blinding = rsa_get_blinding(rsa, &local_blinding, ctx); 412 if (blinding == NULL) { 413 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_INTERNAL_ERROR); 414 goto err; 415 } 416 } 417 418 if (blinding != NULL) { 419 if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) { 420 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE); 421 goto err; 422 } 423 if (!rsa_blinding_convert(blinding, f, unblind, ctx)) 424 goto err; 425 } 426 427 /* do the decrypt */ 428 if ((rsa->flags & RSA_FLAG_EXT_PKEY) || 429 (rsa->version == RSA_ASN1_VERSION_MULTI) || 430 ((rsa->p != NULL) && 431 (rsa->q != NULL) && 432 (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) { 433 if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx)) 434 goto err; 435 } else { 436 BIGNUM *d = BN_new(); 437 if (d == NULL) { 438 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE); 439 goto err; 440 } 441 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); 442 443 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) 444 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, 445 rsa->n, ctx)) { 446 BN_free(d); 447 goto err; 448 } 449 if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx, 450 rsa->_method_mod_n)) { 451 BN_free(d); 452 goto err; 453 } 454 /* We MUST free d before any further use of rsa->d */ 455 BN_free(d); 456 } 457 458 if (blinding) 459 if (!rsa_blinding_invert(blinding, ret, unblind, ctx)) 460 goto err; 461 462 j = BN_bn2binpad(ret, buf, num); 463 464 switch (padding) { 465 case RSA_PKCS1_PADDING: 466 r = RSA_padding_check_PKCS1_type_2(to, num, buf, j, num); 467 break; 468 case RSA_PKCS1_OAEP_PADDING: 469 r = RSA_padding_check_PKCS1_OAEP(to, num, buf, j, num, NULL, 0); 470 break; 471 case RSA_SSLV23_PADDING: 472 r = RSA_padding_check_SSLv23(to, num, buf, j, num); 473 break; 474 case RSA_NO_PADDING: 475 memcpy(to, buf, (r = j)); 476 break; 477 default: 478 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE); 479 goto err; 480 } 481 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_PADDING_CHECK_FAILED); 482 err_clear_last_constant_time(1 & ~constant_time_msb(r)); 483 484 err: 485 BN_CTX_end(ctx); 486 BN_CTX_free(ctx); 487 OPENSSL_clear_free(buf, num); 488 return r; 489 } 490 491 /* signature verification */ 492 static int rsa_ossl_public_decrypt(int flen, const unsigned char *from, 493 unsigned char *to, RSA *rsa, int padding) 494 { 495 BIGNUM *f, *ret; 496 int i, num = 0, r = -1; 497 unsigned char *buf = NULL; 498 BN_CTX *ctx = NULL; 499 500 if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) { 501 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_MODULUS_TOO_LARGE); 502 return -1; 503 } 504 505 if (BN_ucmp(rsa->n, rsa->e) <= 0) { 506 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE); 507 return -1; 508 } 509 510 /* for large moduli, enforce exponent limit */ 511 if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) { 512 if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) { 513 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE); 514 return -1; 515 } 516 } 517 518 if ((ctx = BN_CTX_new()) == NULL) 519 goto err; 520 BN_CTX_start(ctx); 521 f = BN_CTX_get(ctx); 522 ret = BN_CTX_get(ctx); 523 num = BN_num_bytes(rsa->n); 524 buf = OPENSSL_malloc(num); 525 if (ret == NULL || buf == NULL) { 526 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, ERR_R_MALLOC_FAILURE); 527 goto err; 528 } 529 530 /* 531 * This check was for equality but PGP does evil things and chops off the 532 * top '0' bytes 533 */ 534 if (flen > num) { 535 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_DATA_GREATER_THAN_MOD_LEN); 536 goto err; 537 } 538 539 if (BN_bin2bn(from, flen, f) == NULL) 540 goto err; 541 542 if (BN_ucmp(f, rsa->n) >= 0) { 543 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, 544 RSA_R_DATA_TOO_LARGE_FOR_MODULUS); 545 goto err; 546 } 547 548 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) 549 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, 550 rsa->n, ctx)) 551 goto err; 552 553 if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx, 554 rsa->_method_mod_n)) 555 goto err; 556 557 if ((padding == RSA_X931_PADDING) && ((bn_get_words(ret)[0] & 0xf) != 12)) 558 if (!BN_sub(ret, rsa->n, ret)) 559 goto err; 560 561 i = BN_bn2binpad(ret, buf, num); 562 563 switch (padding) { 564 case RSA_PKCS1_PADDING: 565 r = RSA_padding_check_PKCS1_type_1(to, num, buf, i, num); 566 break; 567 case RSA_X931_PADDING: 568 r = RSA_padding_check_X931(to, num, buf, i, num); 569 break; 570 case RSA_NO_PADDING: 571 memcpy(to, buf, (r = i)); 572 break; 573 default: 574 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE); 575 goto err; 576 } 577 if (r < 0) 578 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_PADDING_CHECK_FAILED); 579 580 err: 581 BN_CTX_end(ctx); 582 BN_CTX_free(ctx); 583 OPENSSL_clear_free(buf, num); 584 return r; 585 } 586 587 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) 588 { 589 BIGNUM *r1, *m1, *vrfy, *r2, *m[RSA_MAX_PRIME_NUM - 2]; 590 int ret = 0, i, ex_primes = 0, smooth = 0; 591 RSA_PRIME_INFO *pinfo; 592 593 BN_CTX_start(ctx); 594 595 r1 = BN_CTX_get(ctx); 596 r2 = BN_CTX_get(ctx); 597 m1 = BN_CTX_get(ctx); 598 vrfy = BN_CTX_get(ctx); 599 if (vrfy == NULL) 600 goto err; 601 602 if (rsa->version == RSA_ASN1_VERSION_MULTI 603 && ((ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0 604 || ex_primes > RSA_MAX_PRIME_NUM - 2)) 605 goto err; 606 607 if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) { 608 BIGNUM *factor = BN_new(); 609 610 if (factor == NULL) 611 goto err; 612 613 /* 614 * Make sure BN_mod_inverse in Montgomery initialization uses the 615 * BN_FLG_CONSTTIME flag 616 */ 617 if (!(BN_with_flags(factor, rsa->p, BN_FLG_CONSTTIME), 618 BN_MONT_CTX_set_locked(&rsa->_method_mod_p, rsa->lock, 619 factor, ctx)) 620 || !(BN_with_flags(factor, rsa->q, BN_FLG_CONSTTIME), 621 BN_MONT_CTX_set_locked(&rsa->_method_mod_q, rsa->lock, 622 factor, ctx))) { 623 BN_free(factor); 624 goto err; 625 } 626 for (i = 0; i < ex_primes; i++) { 627 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); 628 BN_with_flags(factor, pinfo->r, BN_FLG_CONSTTIME); 629 if (!BN_MONT_CTX_set_locked(&pinfo->m, rsa->lock, factor, ctx)) { 630 BN_free(factor); 631 goto err; 632 } 633 } 634 /* 635 * We MUST free |factor| before any further use of the prime factors 636 */ 637 BN_free(factor); 638 639 smooth = (ex_primes == 0) 640 && (rsa->meth->bn_mod_exp == BN_mod_exp_mont) 641 && (BN_num_bits(rsa->q) == BN_num_bits(rsa->p)); 642 } 643 644 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) 645 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, 646 rsa->n, ctx)) 647 goto err; 648 649 if (smooth) { 650 /* 651 * Conversion from Montgomery domain, a.k.a. Montgomery reduction, 652 * accepts values in [0-m*2^w) range. w is m's bit width rounded up 653 * to limb width. So that at the very least if |I| is fully reduced, 654 * i.e. less than p*q, we can count on from-to round to perform 655 * below modulo operations on |I|. Unlike BN_mod it's constant time. 656 */ 657 if (/* m1 = I moq q */ 658 !bn_from_mont_fixed_top(m1, I, rsa->_method_mod_q, ctx) 659 || !bn_to_mont_fixed_top(m1, m1, rsa->_method_mod_q, ctx) 660 /* m1 = m1^dmq1 mod q */ 661 || !BN_mod_exp_mont_consttime(m1, m1, rsa->dmq1, rsa->q, ctx, 662 rsa->_method_mod_q) 663 /* r1 = I mod p */ 664 || !bn_from_mont_fixed_top(r1, I, rsa->_method_mod_p, ctx) 665 || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx) 666 /* r1 = r1^dmp1 mod p */ 667 || !BN_mod_exp_mont_consttime(r1, r1, rsa->dmp1, rsa->p, ctx, 668 rsa->_method_mod_p) 669 /* r1 = (r1 - m1) mod p */ 670 /* 671 * bn_mod_sub_fixed_top is not regular modular subtraction, 672 * it can tolerate subtrahend to be larger than modulus, but 673 * not bit-wise wider. This makes up for uncommon q>p case, 674 * when |m1| can be larger than |rsa->p|. 675 */ 676 || !bn_mod_sub_fixed_top(r1, r1, m1, rsa->p) 677 678 /* r1 = r1 * iqmp mod p */ 679 || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx) 680 || !bn_mul_mont_fixed_top(r1, r1, rsa->iqmp, rsa->_method_mod_p, 681 ctx) 682 /* r0 = r1 * q + m1 */ 683 || !bn_mul_fixed_top(r0, r1, rsa->q, ctx) 684 || !bn_mod_add_fixed_top(r0, r0, m1, rsa->n)) 685 goto err; 686 687 goto tail; 688 } 689 690 /* compute I mod q */ 691 { 692 BIGNUM *c = BN_new(); 693 if (c == NULL) 694 goto err; 695 BN_with_flags(c, I, BN_FLG_CONSTTIME); 696 697 if (!BN_mod(r1, c, rsa->q, ctx)) { 698 BN_free(c); 699 goto err; 700 } 701 702 { 703 BIGNUM *dmq1 = BN_new(); 704 if (dmq1 == NULL) { 705 BN_free(c); 706 goto err; 707 } 708 BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME); 709 710 /* compute r1^dmq1 mod q */ 711 if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx, 712 rsa->_method_mod_q)) { 713 BN_free(c); 714 BN_free(dmq1); 715 goto err; 716 } 717 /* We MUST free dmq1 before any further use of rsa->dmq1 */ 718 BN_free(dmq1); 719 } 720 721 /* compute I mod p */ 722 if (!BN_mod(r1, c, rsa->p, ctx)) { 723 BN_free(c); 724 goto err; 725 } 726 /* We MUST free c before any further use of I */ 727 BN_free(c); 728 } 729 730 { 731 BIGNUM *dmp1 = BN_new(); 732 if (dmp1 == NULL) 733 goto err; 734 BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME); 735 736 /* compute r1^dmp1 mod p */ 737 if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx, 738 rsa->_method_mod_p)) { 739 BN_free(dmp1); 740 goto err; 741 } 742 /* We MUST free dmp1 before any further use of rsa->dmp1 */ 743 BN_free(dmp1); 744 } 745 746 /* 747 * calculate m_i in multi-prime case 748 * 749 * TODO: 750 * 1. squash the following two loops and calculate |m_i| there. 751 * 2. remove cc and reuse |c|. 752 * 3. remove |dmq1| and |dmp1| in previous block and use |di|. 753 * 754 * If these things are done, the code will be more readable. 755 */ 756 if (ex_primes > 0) { 757 BIGNUM *di = BN_new(), *cc = BN_new(); 758 759 if (cc == NULL || di == NULL) { 760 BN_free(cc); 761 BN_free(di); 762 goto err; 763 } 764 765 for (i = 0; i < ex_primes; i++) { 766 /* prepare m_i */ 767 if ((m[i] = BN_CTX_get(ctx)) == NULL) { 768 BN_free(cc); 769 BN_free(di); 770 goto err; 771 } 772 773 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); 774 775 /* prepare c and d_i */ 776 BN_with_flags(cc, I, BN_FLG_CONSTTIME); 777 BN_with_flags(di, pinfo->d, BN_FLG_CONSTTIME); 778 779 if (!BN_mod(r1, cc, pinfo->r, ctx)) { 780 BN_free(cc); 781 BN_free(di); 782 goto err; 783 } 784 /* compute r1 ^ d_i mod r_i */ 785 if (!rsa->meth->bn_mod_exp(m[i], r1, di, pinfo->r, ctx, pinfo->m)) { 786 BN_free(cc); 787 BN_free(di); 788 goto err; 789 } 790 } 791 792 BN_free(cc); 793 BN_free(di); 794 } 795 796 if (!BN_sub(r0, r0, m1)) 797 goto err; 798 /* 799 * This will help stop the size of r0 increasing, which does affect the 800 * multiply if it optimised for a power of 2 size 801 */ 802 if (BN_is_negative(r0)) 803 if (!BN_add(r0, r0, rsa->p)) 804 goto err; 805 806 if (!BN_mul(r1, r0, rsa->iqmp, ctx)) 807 goto err; 808 809 { 810 BIGNUM *pr1 = BN_new(); 811 if (pr1 == NULL) 812 goto err; 813 BN_with_flags(pr1, r1, BN_FLG_CONSTTIME); 814 815 if (!BN_mod(r0, pr1, rsa->p, ctx)) { 816 BN_free(pr1); 817 goto err; 818 } 819 /* We MUST free pr1 before any further use of r1 */ 820 BN_free(pr1); 821 } 822 823 /* 824 * If p < q it is occasionally possible for the correction of adding 'p' 825 * if r0 is negative above to leave the result still negative. This can 826 * break the private key operations: the following second correction 827 * should *always* correct this rare occurrence. This will *never* happen 828 * with OpenSSL generated keys because they ensure p > q [steve] 829 */ 830 if (BN_is_negative(r0)) 831 if (!BN_add(r0, r0, rsa->p)) 832 goto err; 833 if (!BN_mul(r1, r0, rsa->q, ctx)) 834 goto err; 835 if (!BN_add(r0, r1, m1)) 836 goto err; 837 838 /* add m_i to m in multi-prime case */ 839 if (ex_primes > 0) { 840 BIGNUM *pr2 = BN_new(); 841 842 if (pr2 == NULL) 843 goto err; 844 845 for (i = 0; i < ex_primes; i++) { 846 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); 847 if (!BN_sub(r1, m[i], r0)) { 848 BN_free(pr2); 849 goto err; 850 } 851 852 if (!BN_mul(r2, r1, pinfo->t, ctx)) { 853 BN_free(pr2); 854 goto err; 855 } 856 857 BN_with_flags(pr2, r2, BN_FLG_CONSTTIME); 858 859 if (!BN_mod(r1, pr2, pinfo->r, ctx)) { 860 BN_free(pr2); 861 goto err; 862 } 863 864 if (BN_is_negative(r1)) 865 if (!BN_add(r1, r1, pinfo->r)) { 866 BN_free(pr2); 867 goto err; 868 } 869 if (!BN_mul(r1, r1, pinfo->pp, ctx)) { 870 BN_free(pr2); 871 goto err; 872 } 873 if (!BN_add(r0, r0, r1)) { 874 BN_free(pr2); 875 goto err; 876 } 877 } 878 BN_free(pr2); 879 } 880 881 tail: 882 if (rsa->e && rsa->n) { 883 if (rsa->meth->bn_mod_exp == BN_mod_exp_mont) { 884 if (!BN_mod_exp_mont(vrfy, r0, rsa->e, rsa->n, ctx, 885 rsa->_method_mod_n)) 886 goto err; 887 } else { 888 bn_correct_top(r0); 889 if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx, 890 rsa->_method_mod_n)) 891 goto err; 892 } 893 /* 894 * If 'I' was greater than (or equal to) rsa->n, the operation will 895 * be equivalent to using 'I mod n'. However, the result of the 896 * verify will *always* be less than 'n' so we don't check for 897 * absolute equality, just congruency. 898 */ 899 if (!BN_sub(vrfy, vrfy, I)) 900 goto err; 901 if (BN_is_zero(vrfy)) { 902 bn_correct_top(r0); 903 ret = 1; 904 goto err; /* not actually error */ 905 } 906 if (!BN_mod(vrfy, vrfy, rsa->n, ctx)) 907 goto err; 908 if (BN_is_negative(vrfy)) 909 if (!BN_add(vrfy, vrfy, rsa->n)) 910 goto err; 911 if (!BN_is_zero(vrfy)) { 912 /* 913 * 'I' and 'vrfy' aren't congruent mod n. Don't leak 914 * miscalculated CRT output, just do a raw (slower) mod_exp and 915 * return that instead. 916 */ 917 918 BIGNUM *d = BN_new(); 919 if (d == NULL) 920 goto err; 921 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); 922 923 if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx, 924 rsa->_method_mod_n)) { 925 BN_free(d); 926 goto err; 927 } 928 /* We MUST free d before any further use of rsa->d */ 929 BN_free(d); 930 } 931 } 932 /* 933 * It's unfortunate that we have to bn_correct_top(r0). What hopefully 934 * saves the day is that correction is highly unlike, and private key 935 * operations are customarily performed on blinded message. Which means 936 * that attacker won't observe correlation with chosen plaintext. 937 * Secondly, remaining code would still handle it in same computational 938 * time and even conceal memory access pattern around corrected top. 939 */ 940 bn_correct_top(r0); 941 ret = 1; 942 err: 943 BN_CTX_end(ctx); 944 return ret; 945 } 946 947 static int rsa_ossl_init(RSA *rsa) 948 { 949 rsa->flags |= RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE; 950 return 1; 951 } 952 953 static int rsa_ossl_finish(RSA *rsa) 954 { 955 int i; 956 RSA_PRIME_INFO *pinfo; 957 958 BN_MONT_CTX_free(rsa->_method_mod_n); 959 BN_MONT_CTX_free(rsa->_method_mod_p); 960 BN_MONT_CTX_free(rsa->_method_mod_q); 961 for (i = 0; i < sk_RSA_PRIME_INFO_num(rsa->prime_infos); i++) { 962 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); 963 BN_MONT_CTX_free(pinfo->m); 964 } 965 return 1; 966 } 967