1/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2 * All rights reserved. 3 * 4 * This package is an SSL implementation written 5 * by Eric Young (eay@cryptsoft.com). 6 * The implementation was written so as to conform with Netscapes SSL. 7 * 8 * This library is free for commercial and non-commercial use as long as 9 * the following conditions are aheared to. The following conditions 10 * apply to all code found in this distribution, be it the RC4, RSA, 11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 12 * included with this distribution is covered by the same copyright terms 13 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 14 * 15 * Copyright remains Eric Young's, and as such any Copyright notices in 16 * the code are not to be removed. 17 * If this package is used in a product, Eric Young should be given attribution 18 * as the author of the parts of the library used. 19 * This can be in the form of a textual message at program startup or 20 * in documentation (online or textual) provided with the package. 21 * 22 * Redistribution and use in source and binary forms, with or without 23 * modification, are permitted provided that the following conditions 24 * are met: 25 * 1. Redistributions of source code must retain the copyright 26 * notice, this list of conditions and the following disclaimer. 27 * 2. Redistributions in binary form must reproduce the above copyright 28 * notice, this list of conditions and the following disclaimer in the 29 * documentation and/or other materials provided with the distribution. 30 * 3. All advertising materials mentioning features or use of this software 31 * must display the following acknowledgement: 32 * "This product includes cryptographic software written by 33 * Eric Young (eay@cryptsoft.com)" 34 * The word 'cryptographic' can be left out if the rouines from the library 35 * being used are not cryptographic related :-). 36 * 4. If you include any Windows specific code (or a derivative thereof) from 37 * the apps directory (application code) you must include an acknowledgement: 38 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 39 * 40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 50 * SUCH DAMAGE. 51 * 52 * The licence and distribution terms for any publically available version or 53 * derivative of this code cannot be changed. i.e. this code cannot simply be 54 * copied and put under another distribution licence 55 * [including the GNU Public Licence.] */ 56 57#include <openssl/rsa.h> 58 59#include <assert.h> 60#include <limits.h> 61#include <string.h> 62 63#include <openssl/bn.h> 64#include <openssl/err.h> 65#include <openssl/mem.h> 66#include <openssl/thread.h> 67#include <openssl/type_check.h> 68 69#include "internal.h" 70#include "../bn/internal.h" 71#include "../../internal.h" 72#include "../delocate.h" 73 74 75static int check_modulus_and_exponent_sizes(const RSA *rsa) { 76 unsigned rsa_bits = BN_num_bits(rsa->n); 77 78 if (rsa_bits > 16 * 1024) { 79 OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE); 80 return 0; 81 } 82 83 /* Mitigate DoS attacks by limiting the exponent size. 33 bits was chosen as 84 * the limit based on the recommendations in [1] and [2]. Windows CryptoAPI 85 * doesn't support values larger than 32 bits [3], so it is unlikely that 86 * exponents larger than 32 bits are being used for anything Windows commonly 87 * does. 88 * 89 * [1] https://www.imperialviolet.org/2012/03/16/rsae.html 90 * [2] https://www.imperialviolet.org/2012/03/17/rsados.html 91 * [3] https://msdn.microsoft.com/en-us/library/aa387685(VS.85).aspx */ 92 static const unsigned kMaxExponentBits = 33; 93 94 if (BN_num_bits(rsa->e) > kMaxExponentBits) { 95 OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE); 96 return 0; 97 } 98 99 /* Verify |n > e|. Comparing |rsa_bits| to |kMaxExponentBits| is a small 100 * shortcut to comparing |n| and |e| directly. In reality, |kMaxExponentBits| 101 * is much smaller than the minimum RSA key size that any application should 102 * accept. */ 103 if (rsa_bits <= kMaxExponentBits) { 104 OPENSSL_PUT_ERROR(RSA, RSA_R_KEY_SIZE_TOO_SMALL); 105 return 0; 106 } 107 assert(BN_ucmp(rsa->n, rsa->e) > 0); 108 109 return 1; 110} 111 112size_t rsa_default_size(const RSA *rsa) { 113 return BN_num_bytes(rsa->n); 114} 115 116int RSA_encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out, 117 const uint8_t *in, size_t in_len, int padding) { 118 if (rsa->n == NULL || rsa->e == NULL) { 119 OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING); 120 return 0; 121 } 122 123 const unsigned rsa_size = RSA_size(rsa); 124 BIGNUM *f, *result; 125 uint8_t *buf = NULL; 126 BN_CTX *ctx = NULL; 127 int i, ret = 0; 128 129 if (max_out < rsa_size) { 130 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL); 131 return 0; 132 } 133 134 if (!check_modulus_and_exponent_sizes(rsa)) { 135 return 0; 136 } 137 138 ctx = BN_CTX_new(); 139 if (ctx == NULL) { 140 goto err; 141 } 142 143 BN_CTX_start(ctx); 144 f = BN_CTX_get(ctx); 145 result = BN_CTX_get(ctx); 146 buf = OPENSSL_malloc(rsa_size); 147 if (!f || !result || !buf) { 148 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE); 149 goto err; 150 } 151 152 switch (padding) { 153 case RSA_PKCS1_PADDING: 154 i = RSA_padding_add_PKCS1_type_2(buf, rsa_size, in, in_len); 155 break; 156 case RSA_PKCS1_OAEP_PADDING: 157 /* Use the default parameters: SHA-1 for both hashes and no label. */ 158 i = RSA_padding_add_PKCS1_OAEP_mgf1(buf, rsa_size, in, in_len, 159 NULL, 0, NULL, NULL); 160 break; 161 case RSA_NO_PADDING: 162 i = RSA_padding_add_none(buf, rsa_size, in, in_len); 163 break; 164 default: 165 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE); 166 goto err; 167 } 168 169 if (i <= 0) { 170 goto err; 171 } 172 173 if (BN_bin2bn(buf, rsa_size, f) == NULL) { 174 goto err; 175 } 176 177 if (BN_ucmp(f, rsa->n) >= 0) { 178 /* usually the padding functions would catch this */ 179 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE); 180 goto err; 181 } 182 183 if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) || 184 !BN_mod_exp_mont(result, f, rsa->e, rsa->n, ctx, rsa->mont_n)) { 185 goto err; 186 } 187 188 /* put in leading 0 bytes if the number is less than the length of the 189 * modulus */ 190 if (!BN_bn2bin_padded(out, rsa_size, result)) { 191 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); 192 goto err; 193 } 194 195 *out_len = rsa_size; 196 ret = 1; 197 198err: 199 if (ctx != NULL) { 200 BN_CTX_end(ctx); 201 BN_CTX_free(ctx); 202 } 203 if (buf != NULL) { 204 OPENSSL_cleanse(buf, rsa_size); 205 OPENSSL_free(buf); 206 } 207 208 return ret; 209} 210 211/* MAX_BLINDINGS_PER_RSA defines the maximum number of cached BN_BLINDINGs per 212 * RSA*. Then this limit is exceeded, BN_BLINDING objects will be created and 213 * destroyed as needed. */ 214#define MAX_BLINDINGS_PER_RSA 1024 215 216/* rsa_blinding_get returns a BN_BLINDING to use with |rsa|. It does this by 217 * allocating one of the cached BN_BLINDING objects in |rsa->blindings|. If 218 * none are free, the cache will be extended by a extra element and the new 219 * BN_BLINDING is returned. 220 * 221 * On success, the index of the assigned BN_BLINDING is written to 222 * |*index_used| and must be passed to |rsa_blinding_release| when finished. */ 223static BN_BLINDING *rsa_blinding_get(RSA *rsa, unsigned *index_used, 224 BN_CTX *ctx) { 225 assert(ctx != NULL); 226 assert(rsa->mont_n != NULL); 227 228 BN_BLINDING *ret = NULL; 229 BN_BLINDING **new_blindings; 230 uint8_t *new_blindings_inuse; 231 char overflow = 0; 232 233 CRYPTO_MUTEX_lock_write(&rsa->lock); 234 235 unsigned i; 236 for (i = 0; i < rsa->num_blindings; i++) { 237 if (rsa->blindings_inuse[i] == 0) { 238 rsa->blindings_inuse[i] = 1; 239 ret = rsa->blindings[i]; 240 *index_used = i; 241 break; 242 } 243 } 244 245 if (ret != NULL) { 246 CRYPTO_MUTEX_unlock_write(&rsa->lock); 247 return ret; 248 } 249 250 overflow = rsa->num_blindings >= MAX_BLINDINGS_PER_RSA; 251 252 /* We didn't find a free BN_BLINDING to use so increase the length of 253 * the arrays by one and use the newly created element. */ 254 255 CRYPTO_MUTEX_unlock_write(&rsa->lock); 256 ret = BN_BLINDING_new(); 257 if (ret == NULL) { 258 return NULL; 259 } 260 261 if (overflow) { 262 /* We cannot add any more cached BN_BLINDINGs so we use |ret| 263 * and mark it for destruction in |rsa_blinding_release|. */ 264 *index_used = MAX_BLINDINGS_PER_RSA; 265 return ret; 266 } 267 268 CRYPTO_MUTEX_lock_write(&rsa->lock); 269 270 new_blindings = 271 OPENSSL_malloc(sizeof(BN_BLINDING *) * (rsa->num_blindings + 1)); 272 if (new_blindings == NULL) { 273 goto err1; 274 } 275 OPENSSL_memcpy(new_blindings, rsa->blindings, 276 sizeof(BN_BLINDING *) * rsa->num_blindings); 277 new_blindings[rsa->num_blindings] = ret; 278 279 new_blindings_inuse = OPENSSL_malloc(rsa->num_blindings + 1); 280 if (new_blindings_inuse == NULL) { 281 goto err2; 282 } 283 OPENSSL_memcpy(new_blindings_inuse, rsa->blindings_inuse, rsa->num_blindings); 284 new_blindings_inuse[rsa->num_blindings] = 1; 285 *index_used = rsa->num_blindings; 286 287 OPENSSL_free(rsa->blindings); 288 rsa->blindings = new_blindings; 289 OPENSSL_free(rsa->blindings_inuse); 290 rsa->blindings_inuse = new_blindings_inuse; 291 rsa->num_blindings++; 292 293 CRYPTO_MUTEX_unlock_write(&rsa->lock); 294 return ret; 295 296err2: 297 OPENSSL_free(new_blindings); 298 299err1: 300 CRYPTO_MUTEX_unlock_write(&rsa->lock); 301 BN_BLINDING_free(ret); 302 return NULL; 303} 304 305/* rsa_blinding_release marks the cached BN_BLINDING at the given index as free 306 * for other threads to use. */ 307static void rsa_blinding_release(RSA *rsa, BN_BLINDING *blinding, 308 unsigned blinding_index) { 309 if (blinding_index == MAX_BLINDINGS_PER_RSA) { 310 /* This blinding wasn't cached. */ 311 BN_BLINDING_free(blinding); 312 return; 313 } 314 315 CRYPTO_MUTEX_lock_write(&rsa->lock); 316 rsa->blindings_inuse[blinding_index] = 0; 317 CRYPTO_MUTEX_unlock_write(&rsa->lock); 318} 319 320/* signing */ 321int rsa_default_sign_raw(RSA *rsa, size_t *out_len, uint8_t *out, 322 size_t max_out, const uint8_t *in, size_t in_len, 323 int padding) { 324 const unsigned rsa_size = RSA_size(rsa); 325 uint8_t *buf = NULL; 326 int i, ret = 0; 327 328 if (max_out < rsa_size) { 329 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL); 330 return 0; 331 } 332 333 buf = OPENSSL_malloc(rsa_size); 334 if (buf == NULL) { 335 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE); 336 goto err; 337 } 338 339 switch (padding) { 340 case RSA_PKCS1_PADDING: 341 i = RSA_padding_add_PKCS1_type_1(buf, rsa_size, in, in_len); 342 break; 343 case RSA_NO_PADDING: 344 i = RSA_padding_add_none(buf, rsa_size, in, in_len); 345 break; 346 default: 347 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE); 348 goto err; 349 } 350 351 if (i <= 0) { 352 goto err; 353 } 354 355 if (!RSA_private_transform(rsa, out, buf, rsa_size)) { 356 goto err; 357 } 358 359 *out_len = rsa_size; 360 ret = 1; 361 362err: 363 if (buf != NULL) { 364 OPENSSL_cleanse(buf, rsa_size); 365 OPENSSL_free(buf); 366 } 367 368 return ret; 369} 370 371int rsa_default_decrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out, 372 const uint8_t *in, size_t in_len, int padding) { 373 const unsigned rsa_size = RSA_size(rsa); 374 uint8_t *buf = NULL; 375 int ret = 0; 376 377 if (max_out < rsa_size) { 378 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL); 379 return 0; 380 } 381 382 if (padding == RSA_NO_PADDING) { 383 buf = out; 384 } else { 385 /* Allocate a temporary buffer to hold the padded plaintext. */ 386 buf = OPENSSL_malloc(rsa_size); 387 if (buf == NULL) { 388 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE); 389 goto err; 390 } 391 } 392 393 if (in_len != rsa_size) { 394 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN); 395 goto err; 396 } 397 398 if (!RSA_private_transform(rsa, buf, in, rsa_size)) { 399 goto err; 400 } 401 402 switch (padding) { 403 case RSA_PKCS1_PADDING: 404 ret = 405 RSA_padding_check_PKCS1_type_2(out, out_len, rsa_size, buf, rsa_size); 406 break; 407 case RSA_PKCS1_OAEP_PADDING: 408 /* Use the default parameters: SHA-1 for both hashes and no label. */ 409 ret = RSA_padding_check_PKCS1_OAEP_mgf1(out, out_len, rsa_size, buf, 410 rsa_size, NULL, 0, NULL, NULL); 411 break; 412 case RSA_NO_PADDING: 413 *out_len = rsa_size; 414 ret = 1; 415 break; 416 default: 417 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE); 418 goto err; 419 } 420 421 if (!ret) { 422 OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED); 423 } 424 425err: 426 if (padding != RSA_NO_PADDING && buf != NULL) { 427 OPENSSL_cleanse(buf, rsa_size); 428 OPENSSL_free(buf); 429 } 430 431 return ret; 432} 433 434static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx); 435 436int RSA_verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out, 437 const uint8_t *in, size_t in_len, int padding) { 438 if (rsa->n == NULL || rsa->e == NULL) { 439 OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING); 440 return 0; 441 } 442 443 const unsigned rsa_size = RSA_size(rsa); 444 BIGNUM *f, *result; 445 446 if (max_out < rsa_size) { 447 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL); 448 return 0; 449 } 450 451 if (in_len != rsa_size) { 452 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN); 453 return 0; 454 } 455 456 if (!check_modulus_and_exponent_sizes(rsa)) { 457 return 0; 458 } 459 460 BN_CTX *ctx = BN_CTX_new(); 461 if (ctx == NULL) { 462 return 0; 463 } 464 465 int ret = 0; 466 uint8_t *buf = NULL; 467 468 BN_CTX_start(ctx); 469 f = BN_CTX_get(ctx); 470 result = BN_CTX_get(ctx); 471 if (f == NULL || result == NULL) { 472 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE); 473 goto err; 474 } 475 476 if (padding == RSA_NO_PADDING) { 477 buf = out; 478 } else { 479 /* Allocate a temporary buffer to hold the padded plaintext. */ 480 buf = OPENSSL_malloc(rsa_size); 481 if (buf == NULL) { 482 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE); 483 goto err; 484 } 485 } 486 487 if (BN_bin2bn(in, in_len, f) == NULL) { 488 goto err; 489 } 490 491 if (BN_ucmp(f, rsa->n) >= 0) { 492 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE); 493 goto err; 494 } 495 496 if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) || 497 !BN_mod_exp_mont(result, f, rsa->e, rsa->n, ctx, rsa->mont_n)) { 498 goto err; 499 } 500 501 if (!BN_bn2bin_padded(buf, rsa_size, result)) { 502 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); 503 goto err; 504 } 505 506 switch (padding) { 507 case RSA_PKCS1_PADDING: 508 ret = 509 RSA_padding_check_PKCS1_type_1(out, out_len, rsa_size, buf, rsa_size); 510 break; 511 case RSA_NO_PADDING: 512 ret = 1; 513 *out_len = rsa_size; 514 break; 515 default: 516 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE); 517 goto err; 518 } 519 520 if (!ret) { 521 OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED); 522 goto err; 523 } 524 525err: 526 BN_CTX_end(ctx); 527 BN_CTX_free(ctx); 528 if (buf != out) { 529 OPENSSL_free(buf); 530 } 531 return ret; 532} 533 534int rsa_default_private_transform(RSA *rsa, uint8_t *out, const uint8_t *in, 535 size_t len) { 536 if (rsa->n == NULL || rsa->d == NULL) { 537 OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING); 538 return 0; 539 } 540 541 BIGNUM *f, *result; 542 BN_CTX *ctx = NULL; 543 unsigned blinding_index = 0; 544 BN_BLINDING *blinding = NULL; 545 int ret = 0; 546 547 ctx = BN_CTX_new(); 548 if (ctx == NULL) { 549 goto err; 550 } 551 BN_CTX_start(ctx); 552 f = BN_CTX_get(ctx); 553 result = BN_CTX_get(ctx); 554 555 if (f == NULL || result == NULL) { 556 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE); 557 goto err; 558 } 559 560 if (BN_bin2bn(in, len, f) == NULL) { 561 goto err; 562 } 563 564 if (BN_ucmp(f, rsa->n) >= 0) { 565 /* Usually the padding functions would catch this. */ 566 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE); 567 goto err; 568 } 569 570 if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx)) { 571 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); 572 goto err; 573 } 574 575 const int do_blinding = (rsa->flags & RSA_FLAG_NO_BLINDING) == 0; 576 577 if (rsa->e == NULL && do_blinding) { 578 /* We cannot do blinding or verification without |e|, and continuing without 579 * those countermeasures is dangerous. However, the Java/Android RSA API 580 * requires support for keys where only |d| and |n| (and not |e|) are known. 581 * The callers that require that bad behavior set |RSA_FLAG_NO_BLINDING|. */ 582 OPENSSL_PUT_ERROR(RSA, RSA_R_NO_PUBLIC_EXPONENT); 583 goto err; 584 } 585 586 if (do_blinding) { 587 blinding = rsa_blinding_get(rsa, &blinding_index, ctx); 588 if (blinding == NULL) { 589 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); 590 goto err; 591 } 592 if (!BN_BLINDING_convert(f, blinding, rsa->e, rsa->mont_n, ctx)) { 593 goto err; 594 } 595 } 596 597 if (rsa->p != NULL && rsa->q != NULL && rsa->e != NULL && rsa->dmp1 != NULL && 598 rsa->dmq1 != NULL && rsa->iqmp != NULL) { 599 if (!mod_exp(result, f, rsa, ctx)) { 600 goto err; 601 } 602 } else if (!BN_mod_exp_mont_consttime(result, f, rsa->d, rsa->n, ctx, 603 rsa->mont_n)) { 604 goto err; 605 } 606 607 /* Verify the result to protect against fault attacks as described in the 608 * 1997 paper "On the Importance of Checking Cryptographic Protocols for 609 * Faults" by Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. Some 610 * implementations do this only when the CRT is used, but we do it in all 611 * cases. Section 6 of the aforementioned paper describes an attack that 612 * works when the CRT isn't used. That attack is much less likely to succeed 613 * than the CRT attack, but there have likely been improvements since 1997. 614 * 615 * This check is cheap assuming |e| is small; it almost always is. */ 616 if (rsa->e != NULL) { 617 BIGNUM *vrfy = BN_CTX_get(ctx); 618 if (vrfy == NULL || 619 !BN_mod_exp_mont(vrfy, result, rsa->e, rsa->n, ctx, rsa->mont_n) || 620 !BN_equal_consttime(vrfy, f)) { 621 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); 622 goto err; 623 } 624 625 } 626 627 if (do_blinding && 628 !BN_BLINDING_invert(result, blinding, rsa->mont_n, ctx)) { 629 goto err; 630 } 631 632 if (!BN_bn2bin_padded(out, len, result)) { 633 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); 634 goto err; 635 } 636 637 ret = 1; 638 639err: 640 if (ctx != NULL) { 641 BN_CTX_end(ctx); 642 BN_CTX_free(ctx); 643 } 644 if (blinding != NULL) { 645 rsa_blinding_release(rsa, blinding, blinding_index); 646 } 647 648 return ret; 649} 650 651static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) { 652 assert(ctx != NULL); 653 654 assert(rsa->n != NULL); 655 assert(rsa->e != NULL); 656 assert(rsa->d != NULL); 657 assert(rsa->p != NULL); 658 assert(rsa->q != NULL); 659 assert(rsa->dmp1 != NULL); 660 assert(rsa->dmq1 != NULL); 661 assert(rsa->iqmp != NULL); 662 663 BIGNUM *r1, *m1, *vrfy; 664 int ret = 0; 665 666 BN_CTX_start(ctx); 667 r1 = BN_CTX_get(ctx); 668 m1 = BN_CTX_get(ctx); 669 vrfy = BN_CTX_get(ctx); 670 if (r1 == NULL || 671 m1 == NULL || 672 vrfy == NULL) { 673 goto err; 674 } 675 676 if (!BN_MONT_CTX_set_locked(&rsa->mont_p, &rsa->lock, rsa->p, ctx) || 677 !BN_MONT_CTX_set_locked(&rsa->mont_q, &rsa->lock, rsa->q, ctx)) { 678 goto err; 679 } 680 681 if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx)) { 682 goto err; 683 } 684 685 /* compute I mod q */ 686 if (!BN_mod(r1, I, rsa->q, ctx)) { 687 goto err; 688 } 689 690 /* compute r1^dmq1 mod q */ 691 if (!BN_mod_exp_mont_consttime(m1, r1, rsa->dmq1, rsa->q, ctx, rsa->mont_q)) { 692 goto err; 693 } 694 695 /* compute I mod p */ 696 if (!BN_mod(r1, I, rsa->p, ctx)) { 697 goto err; 698 } 699 700 /* compute r1^dmp1 mod p */ 701 if (!BN_mod_exp_mont_consttime(r0, r1, rsa->dmp1, rsa->p, ctx, rsa->mont_p)) { 702 goto err; 703 } 704 705 if (!BN_sub(r0, r0, m1)) { 706 goto err; 707 } 708 /* This will help stop the size of r0 increasing, which does 709 * affect the multiply if it optimised for a power of 2 size */ 710 if (BN_is_negative(r0)) { 711 if (!BN_add(r0, r0, rsa->p)) { 712 goto err; 713 } 714 } 715 716 if (!BN_mul(r1, r0, rsa->iqmp, ctx)) { 717 goto err; 718 } 719 720 if (!BN_mod(r0, r1, rsa->p, ctx)) { 721 goto err; 722 } 723 724 /* If p < q it is occasionally possible for the correction of 725 * adding 'p' if r0 is negative above to leave the result still 726 * negative. This can break the private key operations: the following 727 * second correction should *always* correct this rare occurrence. 728 * This will *never* happen with OpenSSL generated keys because 729 * they ensure p > q [steve] */ 730 if (BN_is_negative(r0)) { 731 if (!BN_add(r0, r0, rsa->p)) { 732 goto err; 733 } 734 } 735 if (!BN_mul(r1, r0, rsa->q, ctx)) { 736 goto err; 737 } 738 if (!BN_add(r0, r1, m1)) { 739 goto err; 740 } 741 742 ret = 1; 743 744err: 745 BN_CTX_end(ctx); 746 return ret; 747} 748 749static int ensure_bignum(BIGNUM **out) { 750 if (*out == NULL) { 751 *out = BN_new(); 752 } 753 return *out != NULL; 754} 755 756/* kBoringSSLRSASqrtTwo is the BIGNUM representation of ⌊2¹⁵³⁵×√2⌋. This is 757 * chosen to give enough precision for 3072-bit RSA, the largest key size FIPS 758 * specifies. Key sizes beyond this will round up. 759 * 760 * To verify this number, check that n² < 2³⁰⁷¹ < (n+1)², where n is value 761 * represented here. Note the components are listed in little-endian order. Here 762 * is some sample Python code to check: 763 * 764 * >>> TOBN = lambda a, b: a << 32 | b 765 * >>> l = [ <paste the contents of kSqrtTwo> ] 766 * >>> n = sum(a * 2**(64*i) for i, a in enumerate(l)) 767 * >>> n**2 < 2**3071 < (n+1)**2 768 * True 769 */ 770const BN_ULONG kBoringSSLRSASqrtTwo[] = { 771 TOBN(0xdea06241, 0xf7aa81c2), TOBN(0xf6a1be3f, 0xca221307), 772 TOBN(0x332a5e9f, 0x7bda1ebf), TOBN(0x0104dc01, 0xfe32352f), 773 TOBN(0xb8cf341b, 0x6f8236c7), TOBN(0x4264dabc, 0xd528b651), 774 TOBN(0xf4d3a02c, 0xebc93e0c), TOBN(0x81394ab6, 0xd8fd0efd), 775 TOBN(0xeaa4a089, 0x9040ca4a), TOBN(0xf52f120f, 0x836e582e), 776 TOBN(0xcb2a6343, 0x31f3c84d), TOBN(0xc6d5a8a3, 0x8bb7e9dc), 777 TOBN(0x460abc72, 0x2f7c4e33), TOBN(0xcab1bc91, 0x1688458a), 778 TOBN(0x53059c60, 0x11bc337b), TOBN(0xd2202e87, 0x42af1f4e), 779 TOBN(0x78048736, 0x3dfa2768), TOBN(0x0f74a85e, 0x439c7b4a), 780 TOBN(0xa8b1fe6f, 0xdc83db39), TOBN(0x4afc8304, 0x3ab8a2c3), 781 TOBN(0xed17ac85, 0x83339915), TOBN(0x1d6f60ba, 0x893ba84c), 782 TOBN(0x597d89b3, 0x754abe9f), TOBN(0xb504f333, 0xf9de6484), 783}; 784const size_t kBoringSSLRSASqrtTwoLen = OPENSSL_ARRAY_SIZE(kBoringSSLRSASqrtTwo); 785 786int rsa_less_than_words(const BN_ULONG *a, const BN_ULONG *b, size_t len) { 787 OPENSSL_COMPILE_ASSERT(sizeof(BN_ULONG) <= sizeof(crypto_word_t), 788 crypto_word_t_too_small); 789 int ret = 0; 790 /* Process the words in little-endian order. */ 791 for (size_t i = 0; i < len; i++) { 792 crypto_word_t eq = constant_time_eq_w(a[i], b[i]); 793 crypto_word_t lt = constant_time_lt_w(a[i], b[i]); 794 ret = constant_time_select_int(eq, ret, constant_time_select_int(lt, 1, 0)); 795 } 796 return ret; 797} 798 799int rsa_greater_than_pow2(const BIGNUM *b, int n) { 800 if (BN_is_negative(b) || n == INT_MAX) { 801 return 0; 802 } 803 804 int b_bits = BN_num_bits(b); 805 return b_bits > n + 1 || (b_bits == n + 1 && !BN_is_pow2(b)); 806} 807 808/* generate_prime sets |out| to a prime with length |bits| such that |out|-1 is 809 * relatively prime to |e|. If |p| is non-NULL, |out| will also not be close to 810 * |p|. */ 811static int generate_prime(BIGNUM *out, int bits, const BIGNUM *e, 812 const BIGNUM *p, BN_CTX *ctx, BN_GENCB *cb) { 813 if (bits < 128 || (bits % BN_BITS2) != 0) { 814 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); 815 return 0; 816 } 817 818 /* Ensure the bound on |tries| does not overflow. */ 819 if (bits >= INT_MAX/5) { 820 OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE); 821 return 0; 822 } 823 824 int ret = 0, tries = 0, rand_tries = 0; 825 BN_CTX_start(ctx); 826 BIGNUM *tmp = BN_CTX_get(ctx); 827 if (tmp == NULL) { 828 goto err; 829 } 830 831 /* See FIPS 186-4 appendix B.3.3, steps 4 and 5. Note |bits| here is 832 * nlen/2. */ 833 for (;;) { 834 /* Generate a random number of length |bits| where the bottom bit is set 835 * (steps 4.2, 4.3, 5.2 and 5.3) and the top bit is set (implied by the 836 * bound checked below in steps 4.4 and 5.5). */ 837 if (!BN_rand(out, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD) || 838 !BN_GENCB_call(cb, BN_GENCB_GENERATED, rand_tries++)) { 839 goto err; 840 } 841 842 if (p != NULL) { 843 /* If |p| and |out| are too close, try again (step 5.4). */ 844 if (!BN_sub(tmp, out, p)) { 845 goto err; 846 } 847 BN_set_negative(tmp, 0); 848 if (!rsa_greater_than_pow2(tmp, bits - 100)) { 849 continue; 850 } 851 } 852 853 /* If out < 2^(bits-1)×√2, try again (steps 4.4 and 5.5). 854 * 855 * We check the most significant words, so we retry if ⌊out/2^k⌋ <= ⌊b/2^k⌋, 856 * where b = 2^(bits-1)×√2 and k = max(0, bits - 1536). For key sizes up to 857 * 3072 (bits = 1536), k = 0, so we are testing that ⌊out⌋ <= ⌊b⌋. out is an 858 * integer and b is not, so this is equivalent to out < b. That is, the 859 * comparison is exact for FIPS key sizes. 860 * 861 * For larger keys, the comparison is approximate, leaning towards 862 * retrying. That is, we reject a negligible fraction of primes that are 863 * within the FIPS bound, but we will never accept a prime outside the 864 * bound, ensuring the resulting RSA key is the right size. Specifically, if 865 * the FIPS bound holds, we have ⌊out/2^k⌋ < out/2^k < b/2^k. This implies 866 * ⌊out/2^k⌋ <= ⌊b/2^k⌋. That is, the FIPS bound implies our bound and so we 867 * are slightly tighter. */ 868 size_t out_len = (size_t)out->top; 869 assert(out_len == (size_t)bits / BN_BITS2); 870 size_t to_check = kBoringSSLRSASqrtTwoLen; 871 if (to_check > out_len) { 872 to_check = out_len; 873 } 874 if (!rsa_less_than_words( 875 kBoringSSLRSASqrtTwo + kBoringSSLRSASqrtTwoLen - to_check, 876 out->d + out_len - to_check, to_check)) { 877 continue; 878 } 879 880 /* Check gcd(out-1, e) is one (steps 4.5 and 5.6). */ 881 if (!BN_sub(tmp, out, BN_value_one()) || 882 !BN_gcd(tmp, tmp, e, ctx)) { 883 goto err; 884 } 885 if (BN_is_one(tmp)) { 886 /* Test |out| for primality (steps 4.5.1 and 5.6.1). */ 887 int is_probable_prime; 888 if (!BN_primality_test(&is_probable_prime, out, BN_prime_checks, ctx, 1, 889 cb)) { 890 goto err; 891 } 892 if (is_probable_prime) { 893 ret = 1; 894 goto err; 895 } 896 } 897 898 /* If we've tried too many times to find a prime, abort (steps 4.7 and 899 * 5.8). */ 900 tries++; 901 if (tries >= bits * 5) { 902 OPENSSL_PUT_ERROR(RSA, RSA_R_TOO_MANY_ITERATIONS); 903 goto err; 904 } 905 if (!BN_GENCB_call(cb, 2, tries)) { 906 goto err; 907 } 908 } 909 910err: 911 BN_CTX_end(ctx); 912 return ret; 913} 914 915int RSA_generate_key_ex(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) { 916 /* See FIPS 186-4 appendix B.3. This function implements a generalized version 917 * of the FIPS algorithm. |RSA_generate_key_fips| performs additional checks 918 * for FIPS-compliant key generation. */ 919 920 /* Always generate RSA keys which are a multiple of 128 bits. Round |bits| 921 * down as needed. */ 922 bits &= ~127; 923 924 /* Reject excessively small keys. */ 925 if (bits < 256) { 926 OPENSSL_PUT_ERROR(RSA, RSA_R_KEY_SIZE_TOO_SMALL); 927 return 0; 928 } 929 930 int ret = 0; 931 BN_CTX *ctx = BN_CTX_new(); 932 if (ctx == NULL) { 933 goto bn_err; 934 } 935 BN_CTX_start(ctx); 936 BIGNUM *totient = BN_CTX_get(ctx); 937 BIGNUM *pm1 = BN_CTX_get(ctx); 938 BIGNUM *qm1 = BN_CTX_get(ctx); 939 BIGNUM *gcd = BN_CTX_get(ctx); 940 if (totient == NULL || pm1 == NULL || qm1 == NULL || gcd == NULL) { 941 goto bn_err; 942 } 943 944 /* We need the RSA components non-NULL. */ 945 if (!ensure_bignum(&rsa->n) || 946 !ensure_bignum(&rsa->d) || 947 !ensure_bignum(&rsa->e) || 948 !ensure_bignum(&rsa->p) || 949 !ensure_bignum(&rsa->q) || 950 !ensure_bignum(&rsa->dmp1) || 951 !ensure_bignum(&rsa->dmq1) || 952 !ensure_bignum(&rsa->iqmp)) { 953 goto bn_err; 954 } 955 956 if (!BN_copy(rsa->e, e_value)) { 957 goto bn_err; 958 } 959 960 int prime_bits = bits / 2; 961 do { 962 /* Generate p and q, each of size |prime_bits|, using the steps outlined in 963 * appendix FIPS 186-4 appendix B.3.3. */ 964 if (!generate_prime(rsa->p, prime_bits, rsa->e, NULL, ctx, cb) || 965 !BN_GENCB_call(cb, 3, 0) || 966 !generate_prime(rsa->q, prime_bits, rsa->e, rsa->p, ctx, cb) || 967 !BN_GENCB_call(cb, 3, 1)) { 968 goto bn_err; 969 } 970 971 if (BN_cmp(rsa->p, rsa->q) < 0) { 972 BIGNUM *tmp = rsa->p; 973 rsa->p = rsa->q; 974 rsa->q = tmp; 975 } 976 977 /* Calculate d = e^(-1) (mod lcm(p-1, q-1)), per FIPS 186-4. This differs 978 * from typical RSA implementations which use (p-1)*(q-1). 979 * 980 * Note this means the size of d might reveal information about p-1 and 981 * q-1. However, we do operations with Chinese Remainder Theorem, so we only 982 * use d (mod p-1) and d (mod q-1) as exponents. Using a minimal totient 983 * does not affect those two values. */ 984 if (!BN_sub(pm1, rsa->p, BN_value_one()) || 985 !BN_sub(qm1, rsa->q, BN_value_one()) || 986 !BN_mul(totient, pm1, qm1, ctx) || 987 !BN_gcd(gcd, pm1, qm1, ctx) || 988 !BN_div(totient, NULL, totient, gcd, ctx) || 989 !BN_mod_inverse(rsa->d, rsa->e, totient, ctx)) { 990 goto bn_err; 991 } 992 993 /* Check that |rsa->d| > 2^|prime_bits| and try again if it fails. See 994 * appendix B.3.1's guidance on values for d. */ 995 } while (!rsa_greater_than_pow2(rsa->d, prime_bits)); 996 997 if (/* Calculate n. */ 998 !BN_mul(rsa->n, rsa->p, rsa->q, ctx) || 999 /* Calculate d mod (p-1). */ 1000 !BN_mod(rsa->dmp1, rsa->d, pm1, ctx) || 1001 /* Calculate d mod (q-1) */ 1002 !BN_mod(rsa->dmq1, rsa->d, qm1, ctx)) { 1003 goto bn_err; 1004 } 1005 1006 /* Sanity-check that |rsa->n| has the specified size. This is implied by 1007 * |generate_prime|'s bounds. */ 1008 if (BN_num_bits(rsa->n) != (unsigned)bits) { 1009 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); 1010 goto err; 1011 } 1012 1013 /* Calculate inverse of q mod p. Note that although RSA key generation is far 1014 * from constant-time, |bn_mod_inverse_secret_prime| uses the same modular 1015 * exponentation logic as in RSA private key operations and, if the RSAZ-1024 1016 * code is enabled, will be optimized for common RSA prime sizes. */ 1017 if (!BN_MONT_CTX_set_locked(&rsa->mont_p, &rsa->lock, rsa->p, ctx) || 1018 !bn_mod_inverse_secret_prime(rsa->iqmp, rsa->q, rsa->p, ctx, 1019 rsa->mont_p)) { 1020 goto bn_err; 1021 } 1022 1023 /* The key generation process is complex and thus error-prone. It could be 1024 * disastrous to generate and then use a bad key so double-check that the key 1025 * makes sense. */ 1026 if (!RSA_check_key(rsa)) { 1027 OPENSSL_PUT_ERROR(RSA, RSA_R_INTERNAL_ERROR); 1028 goto err; 1029 } 1030 1031 ret = 1; 1032 1033bn_err: 1034 if (!ret) { 1035 OPENSSL_PUT_ERROR(RSA, ERR_LIB_BN); 1036 } 1037err: 1038 if (ctx != NULL) { 1039 BN_CTX_end(ctx); 1040 BN_CTX_free(ctx); 1041 } 1042 return ret; 1043} 1044 1045int RSA_generate_key_fips(RSA *rsa, int bits, BN_GENCB *cb) { 1046 /* FIPS 186-4 allows 2048-bit and 3072-bit RSA keys (1024-bit and 1536-bit 1047 * primes, respectively) with the prime generation method we use. */ 1048 if (bits != 2048 && bits != 3072) { 1049 OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_RSA_PARAMETERS); 1050 return 0; 1051 } 1052 1053 BIGNUM *e = BN_new(); 1054 int ret = e != NULL && 1055 BN_set_word(e, RSA_F4) && 1056 RSA_generate_key_ex(rsa, bits, e, cb) && 1057 RSA_check_fips(rsa); 1058 BN_free(e); 1059 return ret; 1060} 1061 1062DEFINE_METHOD_FUNCTION(RSA_METHOD, RSA_default_method) { 1063 /* All of the methods are NULL to make it easier for the compiler/linker to 1064 * drop unused functions. The wrapper functions will select the appropriate 1065 * |rsa_default_*| implementation. */ 1066 OPENSSL_memset(out, 0, sizeof(RSA_METHOD)); 1067 out->common.is_static = 1; 1068 out->flags = RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE; 1069} 1070