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 "crypto/bn.h" 12 #include "rsa_local.h" 13 #include "internal/constant_time.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 if (rsa->d == NULL) { 325 RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, RSA_R_MISSING_PRIVATE_KEY); 326 BN_free(d); 327 goto err; 328 } 329 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); 330 331 if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx, 332 rsa->_method_mod_n)) { 333 BN_free(d); 334 goto err; 335 } 336 /* We MUST free d before any further use of rsa->d */ 337 BN_free(d); 338 } 339 340 if (blinding) 341 if (!rsa_blinding_invert(blinding, ret, unblind, ctx)) 342 goto err; 343 344 if (padding == RSA_X931_PADDING) { 345 if (!BN_sub(f, rsa->n, ret)) 346 goto err; 347 if (BN_cmp(ret, f) > 0) 348 res = f; 349 else 350 res = ret; 351 } else { 352 res = ret; 353 } 354 355 /* 356 * BN_bn2binpad puts in leading 0 bytes if the number is less than 357 * the length of the modulus. 358 */ 359 r = BN_bn2binpad(res, to, num); 360 err: 361 BN_CTX_end(ctx); 362 BN_CTX_free(ctx); 363 OPENSSL_clear_free(buf, num); 364 return r; 365 } 366 367 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from, 368 unsigned char *to, RSA *rsa, int padding) 369 { 370 BIGNUM *f, *ret; 371 int j, num = 0, r = -1; 372 unsigned char *buf = NULL; 373 BN_CTX *ctx = NULL; 374 int local_blinding = 0; 375 /* 376 * Used only if the blinding structure is shared. A non-NULL unblind 377 * instructs rsa_blinding_convert() and rsa_blinding_invert() to store 378 * the unblinding factor outside the blinding structure. 379 */ 380 BIGNUM *unblind = NULL; 381 BN_BLINDING *blinding = NULL; 382 383 if ((ctx = BN_CTX_new()) == NULL) 384 goto err; 385 BN_CTX_start(ctx); 386 f = BN_CTX_get(ctx); 387 ret = BN_CTX_get(ctx); 388 num = BN_num_bytes(rsa->n); 389 buf = OPENSSL_malloc(num); 390 if (ret == NULL || buf == NULL) { 391 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE); 392 goto err; 393 } 394 395 /* 396 * This check was for equality but PGP does evil things and chops off the 397 * top '0' bytes 398 */ 399 if (flen > num) { 400 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, 401 RSA_R_DATA_GREATER_THAN_MOD_LEN); 402 goto err; 403 } 404 405 /* make data into a big number */ 406 if (BN_bin2bn(from, (int)flen, f) == NULL) 407 goto err; 408 409 if (BN_ucmp(f, rsa->n) >= 0) { 410 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, 411 RSA_R_DATA_TOO_LARGE_FOR_MODULUS); 412 goto err; 413 } 414 415 if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) { 416 blinding = rsa_get_blinding(rsa, &local_blinding, ctx); 417 if (blinding == NULL) { 418 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_INTERNAL_ERROR); 419 goto err; 420 } 421 } 422 423 if (blinding != NULL) { 424 if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) { 425 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE); 426 goto err; 427 } 428 if (!rsa_blinding_convert(blinding, f, unblind, ctx)) 429 goto err; 430 } 431 432 /* do the decrypt */ 433 if ((rsa->flags & RSA_FLAG_EXT_PKEY) || 434 (rsa->version == RSA_ASN1_VERSION_MULTI) || 435 ((rsa->p != NULL) && 436 (rsa->q != NULL) && 437 (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) { 438 if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx)) 439 goto err; 440 } else { 441 BIGNUM *d = BN_new(); 442 if (d == NULL) { 443 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE); 444 goto err; 445 } 446 if (rsa->d == NULL) { 447 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_MISSING_PRIVATE_KEY); 448 BN_free(d); 449 goto err; 450 } 451 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); 452 453 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) 454 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, 455 rsa->n, ctx)) { 456 BN_free(d); 457 goto err; 458 } 459 if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx, 460 rsa->_method_mod_n)) { 461 BN_free(d); 462 goto err; 463 } 464 /* We MUST free d before any further use of rsa->d */ 465 BN_free(d); 466 } 467 468 if (blinding) 469 if (!rsa_blinding_invert(blinding, ret, unblind, ctx)) 470 goto err; 471 472 j = BN_bn2binpad(ret, buf, num); 473 474 switch (padding) { 475 case RSA_PKCS1_PADDING: 476 r = RSA_padding_check_PKCS1_type_2(to, num, buf, j, num); 477 break; 478 case RSA_PKCS1_OAEP_PADDING: 479 r = RSA_padding_check_PKCS1_OAEP(to, num, buf, j, num, NULL, 0); 480 break; 481 case RSA_SSLV23_PADDING: 482 r = RSA_padding_check_SSLv23(to, num, buf, j, num); 483 break; 484 case RSA_NO_PADDING: 485 memcpy(to, buf, (r = j)); 486 break; 487 default: 488 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE); 489 goto err; 490 } 491 RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_PADDING_CHECK_FAILED); 492 err_clear_last_constant_time(1 & ~constant_time_msb(r)); 493 494 err: 495 BN_CTX_end(ctx); 496 BN_CTX_free(ctx); 497 OPENSSL_clear_free(buf, num); 498 return r; 499 } 500 501 /* signature verification */ 502 static int rsa_ossl_public_decrypt(int flen, const unsigned char *from, 503 unsigned char *to, RSA *rsa, int padding) 504 { 505 BIGNUM *f, *ret; 506 int i, num = 0, r = -1; 507 unsigned char *buf = NULL; 508 BN_CTX *ctx = NULL; 509 510 if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) { 511 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_MODULUS_TOO_LARGE); 512 return -1; 513 } 514 515 if (BN_ucmp(rsa->n, rsa->e) <= 0) { 516 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE); 517 return -1; 518 } 519 520 /* for large moduli, enforce exponent limit */ 521 if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) { 522 if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) { 523 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE); 524 return -1; 525 } 526 } 527 528 if ((ctx = BN_CTX_new()) == NULL) 529 goto err; 530 BN_CTX_start(ctx); 531 f = BN_CTX_get(ctx); 532 ret = BN_CTX_get(ctx); 533 num = BN_num_bytes(rsa->n); 534 buf = OPENSSL_malloc(num); 535 if (ret == NULL || buf == NULL) { 536 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, ERR_R_MALLOC_FAILURE); 537 goto err; 538 } 539 540 /* 541 * This check was for equality but PGP does evil things and chops off the 542 * top '0' bytes 543 */ 544 if (flen > num) { 545 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_DATA_GREATER_THAN_MOD_LEN); 546 goto err; 547 } 548 549 if (BN_bin2bn(from, flen, f) == NULL) 550 goto err; 551 552 if (BN_ucmp(f, rsa->n) >= 0) { 553 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, 554 RSA_R_DATA_TOO_LARGE_FOR_MODULUS); 555 goto err; 556 } 557 558 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) 559 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, 560 rsa->n, ctx)) 561 goto err; 562 563 if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx, 564 rsa->_method_mod_n)) 565 goto err; 566 567 if ((padding == RSA_X931_PADDING) && ((bn_get_words(ret)[0] & 0xf) != 12)) 568 if (!BN_sub(ret, rsa->n, ret)) 569 goto err; 570 571 i = BN_bn2binpad(ret, buf, num); 572 573 switch (padding) { 574 case RSA_PKCS1_PADDING: 575 r = RSA_padding_check_PKCS1_type_1(to, num, buf, i, num); 576 break; 577 case RSA_X931_PADDING: 578 r = RSA_padding_check_X931(to, num, buf, i, num); 579 break; 580 case RSA_NO_PADDING: 581 memcpy(to, buf, (r = i)); 582 break; 583 default: 584 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE); 585 goto err; 586 } 587 if (r < 0) 588 RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_PADDING_CHECK_FAILED); 589 590 err: 591 BN_CTX_end(ctx); 592 BN_CTX_free(ctx); 593 OPENSSL_clear_free(buf, num); 594 return r; 595 } 596 597 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) 598 { 599 BIGNUM *r1, *m1, *vrfy, *r2, *m[RSA_MAX_PRIME_NUM - 2]; 600 int ret = 0, i, ex_primes = 0, smooth = 0; 601 RSA_PRIME_INFO *pinfo; 602 603 BN_CTX_start(ctx); 604 605 r1 = BN_CTX_get(ctx); 606 r2 = BN_CTX_get(ctx); 607 m1 = BN_CTX_get(ctx); 608 vrfy = BN_CTX_get(ctx); 609 if (vrfy == NULL) 610 goto err; 611 612 if (rsa->version == RSA_ASN1_VERSION_MULTI 613 && ((ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0 614 || ex_primes > RSA_MAX_PRIME_NUM - 2)) 615 goto err; 616 617 if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) { 618 BIGNUM *factor = BN_new(); 619 620 if (factor == NULL) 621 goto err; 622 623 /* 624 * Make sure BN_mod_inverse in Montgomery initialization uses the 625 * BN_FLG_CONSTTIME flag 626 */ 627 if (!(BN_with_flags(factor, rsa->p, BN_FLG_CONSTTIME), 628 BN_MONT_CTX_set_locked(&rsa->_method_mod_p, rsa->lock, 629 factor, ctx)) 630 || !(BN_with_flags(factor, rsa->q, BN_FLG_CONSTTIME), 631 BN_MONT_CTX_set_locked(&rsa->_method_mod_q, rsa->lock, 632 factor, ctx))) { 633 BN_free(factor); 634 goto err; 635 } 636 for (i = 0; i < ex_primes; i++) { 637 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); 638 BN_with_flags(factor, pinfo->r, BN_FLG_CONSTTIME); 639 if (!BN_MONT_CTX_set_locked(&pinfo->m, rsa->lock, factor, ctx)) { 640 BN_free(factor); 641 goto err; 642 } 643 } 644 /* 645 * We MUST free |factor| before any further use of the prime factors 646 */ 647 BN_free(factor); 648 649 smooth = (ex_primes == 0) 650 && (rsa->meth->bn_mod_exp == BN_mod_exp_mont) 651 && (BN_num_bits(rsa->q) == BN_num_bits(rsa->p)); 652 } 653 654 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) 655 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, 656 rsa->n, ctx)) 657 goto err; 658 659 if (smooth) { 660 /* 661 * Conversion from Montgomery domain, a.k.a. Montgomery reduction, 662 * accepts values in [0-m*2^w) range. w is m's bit width rounded up 663 * to limb width. So that at the very least if |I| is fully reduced, 664 * i.e. less than p*q, we can count on from-to round to perform 665 * below modulo operations on |I|. Unlike BN_mod it's constant time. 666 */ 667 if (/* m1 = I moq q */ 668 !bn_from_mont_fixed_top(m1, I, rsa->_method_mod_q, ctx) 669 || !bn_to_mont_fixed_top(m1, m1, rsa->_method_mod_q, ctx) 670 /* m1 = m1^dmq1 mod q */ 671 || !BN_mod_exp_mont_consttime(m1, m1, rsa->dmq1, rsa->q, ctx, 672 rsa->_method_mod_q) 673 /* r1 = I mod p */ 674 || !bn_from_mont_fixed_top(r1, I, rsa->_method_mod_p, ctx) 675 || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx) 676 /* r1 = r1^dmp1 mod p */ 677 || !BN_mod_exp_mont_consttime(r1, r1, rsa->dmp1, rsa->p, ctx, 678 rsa->_method_mod_p) 679 /* r1 = (r1 - m1) mod p */ 680 /* 681 * bn_mod_sub_fixed_top is not regular modular subtraction, 682 * it can tolerate subtrahend to be larger than modulus, but 683 * not bit-wise wider. This makes up for uncommon q>p case, 684 * when |m1| can be larger than |rsa->p|. 685 */ 686 || !bn_mod_sub_fixed_top(r1, r1, m1, rsa->p) 687 688 /* r1 = r1 * iqmp mod p */ 689 || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx) 690 || !bn_mul_mont_fixed_top(r1, r1, rsa->iqmp, rsa->_method_mod_p, 691 ctx) 692 /* r0 = r1 * q + m1 */ 693 || !bn_mul_fixed_top(r0, r1, rsa->q, ctx) 694 || !bn_mod_add_fixed_top(r0, r0, m1, rsa->n)) 695 goto err; 696 697 goto tail; 698 } 699 700 /* compute I mod q */ 701 { 702 BIGNUM *c = BN_new(); 703 if (c == NULL) 704 goto err; 705 BN_with_flags(c, I, BN_FLG_CONSTTIME); 706 707 if (!BN_mod(r1, c, rsa->q, ctx)) { 708 BN_free(c); 709 goto err; 710 } 711 712 { 713 BIGNUM *dmq1 = BN_new(); 714 if (dmq1 == NULL) { 715 BN_free(c); 716 goto err; 717 } 718 BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME); 719 720 /* compute r1^dmq1 mod q */ 721 if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx, 722 rsa->_method_mod_q)) { 723 BN_free(c); 724 BN_free(dmq1); 725 goto err; 726 } 727 /* We MUST free dmq1 before any further use of rsa->dmq1 */ 728 BN_free(dmq1); 729 } 730 731 /* compute I mod p */ 732 if (!BN_mod(r1, c, rsa->p, ctx)) { 733 BN_free(c); 734 goto err; 735 } 736 /* We MUST free c before any further use of I */ 737 BN_free(c); 738 } 739 740 { 741 BIGNUM *dmp1 = BN_new(); 742 if (dmp1 == NULL) 743 goto err; 744 BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME); 745 746 /* compute r1^dmp1 mod p */ 747 if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx, 748 rsa->_method_mod_p)) { 749 BN_free(dmp1); 750 goto err; 751 } 752 /* We MUST free dmp1 before any further use of rsa->dmp1 */ 753 BN_free(dmp1); 754 } 755 756 /* 757 * calculate m_i in multi-prime case 758 * 759 * TODO: 760 * 1. squash the following two loops and calculate |m_i| there. 761 * 2. remove cc and reuse |c|. 762 * 3. remove |dmq1| and |dmp1| in previous block and use |di|. 763 * 764 * If these things are done, the code will be more readable. 765 */ 766 if (ex_primes > 0) { 767 BIGNUM *di = BN_new(), *cc = BN_new(); 768 769 if (cc == NULL || di == NULL) { 770 BN_free(cc); 771 BN_free(di); 772 goto err; 773 } 774 775 for (i = 0; i < ex_primes; i++) { 776 /* prepare m_i */ 777 if ((m[i] = BN_CTX_get(ctx)) == NULL) { 778 BN_free(cc); 779 BN_free(di); 780 goto err; 781 } 782 783 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); 784 785 /* prepare c and d_i */ 786 BN_with_flags(cc, I, BN_FLG_CONSTTIME); 787 BN_with_flags(di, pinfo->d, BN_FLG_CONSTTIME); 788 789 if (!BN_mod(r1, cc, pinfo->r, ctx)) { 790 BN_free(cc); 791 BN_free(di); 792 goto err; 793 } 794 /* compute r1 ^ d_i mod r_i */ 795 if (!rsa->meth->bn_mod_exp(m[i], r1, di, pinfo->r, ctx, pinfo->m)) { 796 BN_free(cc); 797 BN_free(di); 798 goto err; 799 } 800 } 801 802 BN_free(cc); 803 BN_free(di); 804 } 805 806 if (!BN_sub(r0, r0, m1)) 807 goto err; 808 /* 809 * This will help stop the size of r0 increasing, which does affect the 810 * multiply if it optimised for a power of 2 size 811 */ 812 if (BN_is_negative(r0)) 813 if (!BN_add(r0, r0, rsa->p)) 814 goto err; 815 816 if (!BN_mul(r1, r0, rsa->iqmp, ctx)) 817 goto err; 818 819 { 820 BIGNUM *pr1 = BN_new(); 821 if (pr1 == NULL) 822 goto err; 823 BN_with_flags(pr1, r1, BN_FLG_CONSTTIME); 824 825 if (!BN_mod(r0, pr1, rsa->p, ctx)) { 826 BN_free(pr1); 827 goto err; 828 } 829 /* We MUST free pr1 before any further use of r1 */ 830 BN_free(pr1); 831 } 832 833 /* 834 * If p < q it is occasionally possible for the correction of adding 'p' 835 * if r0 is negative above to leave the result still negative. This can 836 * break the private key operations: the following second correction 837 * should *always* correct this rare occurrence. This will *never* happen 838 * with OpenSSL generated keys because they ensure p > q [steve] 839 */ 840 if (BN_is_negative(r0)) 841 if (!BN_add(r0, r0, rsa->p)) 842 goto err; 843 if (!BN_mul(r1, r0, rsa->q, ctx)) 844 goto err; 845 if (!BN_add(r0, r1, m1)) 846 goto err; 847 848 /* add m_i to m in multi-prime case */ 849 if (ex_primes > 0) { 850 BIGNUM *pr2 = BN_new(); 851 852 if (pr2 == NULL) 853 goto err; 854 855 for (i = 0; i < ex_primes; i++) { 856 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); 857 if (!BN_sub(r1, m[i], r0)) { 858 BN_free(pr2); 859 goto err; 860 } 861 862 if (!BN_mul(r2, r1, pinfo->t, ctx)) { 863 BN_free(pr2); 864 goto err; 865 } 866 867 BN_with_flags(pr2, r2, BN_FLG_CONSTTIME); 868 869 if (!BN_mod(r1, pr2, pinfo->r, ctx)) { 870 BN_free(pr2); 871 goto err; 872 } 873 874 if (BN_is_negative(r1)) 875 if (!BN_add(r1, r1, pinfo->r)) { 876 BN_free(pr2); 877 goto err; 878 } 879 if (!BN_mul(r1, r1, pinfo->pp, ctx)) { 880 BN_free(pr2); 881 goto err; 882 } 883 if (!BN_add(r0, r0, r1)) { 884 BN_free(pr2); 885 goto err; 886 } 887 } 888 BN_free(pr2); 889 } 890 891 tail: 892 if (rsa->e && rsa->n) { 893 if (rsa->meth->bn_mod_exp == BN_mod_exp_mont) { 894 if (!BN_mod_exp_mont(vrfy, r0, rsa->e, rsa->n, ctx, 895 rsa->_method_mod_n)) 896 goto err; 897 } else { 898 bn_correct_top(r0); 899 if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx, 900 rsa->_method_mod_n)) 901 goto err; 902 } 903 /* 904 * If 'I' was greater than (or equal to) rsa->n, the operation will 905 * be equivalent to using 'I mod n'. However, the result of the 906 * verify will *always* be less than 'n' so we don't check for 907 * absolute equality, just congruency. 908 */ 909 if (!BN_sub(vrfy, vrfy, I)) 910 goto err; 911 if (BN_is_zero(vrfy)) { 912 bn_correct_top(r0); 913 ret = 1; 914 goto err; /* not actually error */ 915 } 916 if (!BN_mod(vrfy, vrfy, rsa->n, ctx)) 917 goto err; 918 if (BN_is_negative(vrfy)) 919 if (!BN_add(vrfy, vrfy, rsa->n)) 920 goto err; 921 if (!BN_is_zero(vrfy)) { 922 /* 923 * 'I' and 'vrfy' aren't congruent mod n. Don't leak 924 * miscalculated CRT output, just do a raw (slower) mod_exp and 925 * return that instead. 926 */ 927 928 BIGNUM *d = BN_new(); 929 if (d == NULL) 930 goto err; 931 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); 932 933 if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx, 934 rsa->_method_mod_n)) { 935 BN_free(d); 936 goto err; 937 } 938 /* We MUST free d before any further use of rsa->d */ 939 BN_free(d); 940 } 941 } 942 /* 943 * It's unfortunate that we have to bn_correct_top(r0). What hopefully 944 * saves the day is that correction is highly unlike, and private key 945 * operations are customarily performed on blinded message. Which means 946 * that attacker won't observe correlation with chosen plaintext. 947 * Secondly, remaining code would still handle it in same computational 948 * time and even conceal memory access pattern around corrected top. 949 */ 950 bn_correct_top(r0); 951 ret = 1; 952 err: 953 BN_CTX_end(ctx); 954 return ret; 955 } 956 957 static int rsa_ossl_init(RSA *rsa) 958 { 959 rsa->flags |= RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE; 960 return 1; 961 } 962 963 static int rsa_ossl_finish(RSA *rsa) 964 { 965 int i; 966 RSA_PRIME_INFO *pinfo; 967 968 BN_MONT_CTX_free(rsa->_method_mod_n); 969 BN_MONT_CTX_free(rsa->_method_mod_p); 970 BN_MONT_CTX_free(rsa->_method_mod_q); 971 for (i = 0; i < sk_RSA_PRIME_INFO_num(rsa->prime_infos); i++) { 972 pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); 973 BN_MONT_CTX_free(pinfo->m); 974 } 975 return 1; 976 } 977