crypto/rsa/rsa_ossl.c

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