crypto/rsa/rsa_ossl.c

   1 /*
   2  * Copyright 1995-2021 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         ERR_raise(ERR_LIB_RSA, ERR_R_MALLOC_FAILURE);
 109         goto err;
 110     }
 111
 112     switch (padding) {
 113     case RSA_PKCS1_PADDING:
 114         i = ossl_rsa_padding_add_PKCS1_type_2_ex(rsa->libctx, buf, num,
 115                                                  from, flen);
 116         break;
 117     case RSA_PKCS1_OAEP_PADDING:
 118         i = ossl_rsa_padding_add_PKCS1_OAEP_mgf1_ex(rsa->libctx, buf, num,
 119                                                     from, flen, NULL, 0,
 120                                                     NULL, NULL);
 121         break;
 122     case RSA_NO_PADDING:
 123         i = RSA_padding_add_none(buf, num, from, flen);
 124         break;
 125     default:
 126         ERR_raise(ERR_LIB_RSA, RSA_R_UNKNOWN_PADDING_TYPE);
 127         goto err;
 128     }
 129     if (i <= 0)
 130         goto err;
 131
 132     if (BN_bin2bn(buf, num, f) == NULL)
 133         goto err;
 134
 135     if (BN_ucmp(f, rsa->n) >= 0) {
 136         /* usually the padding functions would catch this */
 137         ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
 138         goto err;
 139     }
 140
 141     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
 142         if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
 143                                     rsa->n, ctx))
 144             goto err;
 145
 146     if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
 147                                rsa->_method_mod_n))
 148         goto err;
 149
 150     /*
 151      * BN_bn2binpad puts in leading 0 bytes if the number is less than
 152      * the length of the modulus.
 153      */
 154     r = BN_bn2binpad(ret, to, num);
 155  err:
 156     BN_CTX_end(ctx);
 157     BN_CTX_free(ctx);
 158     OPENSSL_clear_free(buf, num);
 159     return r;
 160 }
 161
 162 static BN_BLINDING *rsa_get_blinding(RSA *rsa, int *local, BN_CTX *ctx)
 163 {
 164     BN_BLINDING *ret;
 165
 166     if (!CRYPTO_THREAD_write_lock(rsa->lock))
 167         return NULL;
 168
 169     if (rsa->blinding == NULL) {
 170         rsa->blinding = RSA_setup_blinding(rsa, ctx);
 171     }
 172
 173     ret = rsa->blinding;
 174     if (ret == NULL)
 175         goto err;
 176
 177     if (BN_BLINDING_is_current_thread(ret)) {
 178         /* rsa->blinding is ours! */
 179
 180         *local = 1;
 181     } else {
 182         /* resort to rsa->mt_blinding instead */
 183
 184         /*
 185          * instructs rsa_blinding_convert(), rsa_blinding_invert() that the
 186          * BN_BLINDING is shared, meaning that accesses require locks, and
 187          * that the blinding factor must be stored outside the BN_BLINDING
 188          */
 189         *local = 0;
 190
 191         if (rsa->mt_blinding == NULL) {
 192             rsa->mt_blinding = RSA_setup_blinding(rsa, ctx);
 193         }
 194         ret = rsa->mt_blinding;
 195     }
 196
 197  err:
 198     CRYPTO_THREAD_unlock(rsa->lock);
 199     return ret;
 200 }
 201
 202 static int rsa_blinding_convert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind,
 203                                 BN_CTX *ctx)
 204 {
 205     if (unblind == NULL) {
 206         /*
 207          * Local blinding: store the unblinding factor in BN_BLINDING.
 208          */
 209         return BN_BLINDING_convert_ex(f, NULL, b, ctx);
 210     } else {
 211         /*
 212          * Shared blinding: store the unblinding factor outside BN_BLINDING.
 213          */
 214         int ret;
 215
 216         BN_BLINDING_lock(b);
 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         ERR_raise(ERR_LIB_RSA, ERR_R_MALLOC_FAILURE);
 264         goto err;
 265     }
 266
 267     switch (padding) {
 268     case RSA_PKCS1_PADDING:
 269         i = RSA_padding_add_PKCS1_type_1(buf, num, from, flen);
 270         break;
 271     case RSA_X931_PADDING:
 272         i = RSA_padding_add_X931(buf, num, from, flen);
 273         break;
 274     case RSA_NO_PADDING:
 275         i = RSA_padding_add_none(buf, num, from, flen);
 276         break;
 277     default:
 278         ERR_raise(ERR_LIB_RSA, RSA_R_UNKNOWN_PADDING_TYPE);
 279         goto err;
 280     }
 281     if (i <= 0)
 282         goto err;
 283
 284     if (BN_bin2bn(buf, num, f) == NULL)
 285         goto err;
 286
 287     if (BN_ucmp(f, rsa->n) >= 0) {
 288         /* usually the padding functions would catch this */
 289         ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
 290         goto err;
 291     }
 292
 293     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
 294         if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
 295                                     rsa->n, ctx))
 296             goto err;
 297
 298     if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
 299         blinding = rsa_get_blinding(rsa, &local_blinding, ctx);
 300         if (blinding == NULL) {
 301             ERR_raise(ERR_LIB_RSA, ERR_R_INTERNAL_ERROR);
 302             goto err;
 303         }
 304     }
 305
 306     if (blinding != NULL) {
 307         if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) {
 308             ERR_raise(ERR_LIB_RSA, ERR_R_MALLOC_FAILURE);
 309             goto err;
 310         }
 311         if (!rsa_blinding_convert(blinding, f, unblind, ctx))
 312             goto err;
 313     }
 314
 315     if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
 316         (rsa->version == RSA_ASN1_VERSION_MULTI) ||
 317         ((rsa->p != NULL) &&
 318          (rsa->q != NULL) &&
 319          (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
 320         if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
 321             goto err;
 322     } else {
 323         BIGNUM *d = BN_new();
 324         if (d == NULL) {
 325             ERR_raise(ERR_LIB_RSA, ERR_R_MALLOC_FAILURE);
 326             goto err;
 327         }
 328         if (rsa->d == NULL) {
 329             ERR_raise(ERR_LIB_RSA, RSA_R_MISSING_PRIVATE_KEY);
 330             BN_free(d);
 331             goto err;
 332         }
 333         BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 334
 335         if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx,
 336                                    rsa->_method_mod_n)) {
 337             BN_free(d);
 338             goto err;
 339         }
 340         /* We MUST free d before any further use of rsa->d */
 341         BN_free(d);
 342     }
 343
 344     if (blinding)
 345         if (!rsa_blinding_invert(blinding, ret, unblind, ctx))
 346             goto err;
 347
 348     if (padding == RSA_X931_PADDING) {
 349         if (!BN_sub(f, rsa->n, ret))
 350             goto err;
 351         if (BN_cmp(ret, f) > 0)
 352             res = f;
 353         else
 354             res = ret;
 355     } else {
 356         res = ret;
 357     }
 358
 359     /*
 360      * BN_bn2binpad puts in leading 0 bytes if the number is less than
 361      * the length of the modulus.
 362      */
 363     r = BN_bn2binpad(res, to, num);
 364  err:
 365     BN_CTX_end(ctx);
 366     BN_CTX_free(ctx);
 367     OPENSSL_clear_free(buf, num);
 368     return r;
 369 }
 370
 371 static int rsa_ossl_private_decrypt(int flen, const unsigned char *from,
 372                                    unsigned char *to, RSA *rsa, int padding)
 373 {
 374     BIGNUM *f, *ret;
 375     int j, num = 0, r = -1;
 376     unsigned char *buf = NULL;
 377     BN_CTX *ctx = NULL;
 378     int local_blinding = 0;
 379     /*
 380      * Used only if the blinding structure is shared. A non-NULL unblind
 381      * instructs rsa_blinding_convert() and rsa_blinding_invert() to store
 382      * the unblinding factor outside the blinding structure.
 383      */
 384     BIGNUM *unblind = NULL;
 385     BN_BLINDING *blinding = NULL;
 386
 387     if ((ctx = BN_CTX_new_ex(rsa->libctx)) == NULL)
 388         goto err;
 389     BN_CTX_start(ctx);
 390     f = BN_CTX_get(ctx);
 391     ret = BN_CTX_get(ctx);
 392     num = BN_num_bytes(rsa->n);
 393     buf = OPENSSL_malloc(num);
 394     if (ret == NULL || buf == NULL) {
 395         ERR_raise(ERR_LIB_RSA, ERR_R_MALLOC_FAILURE);
 396         goto err;
 397     }
 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_MALLOC_FAILURE);
 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_MALLOC_FAILURE);
 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     num = BN_num_bytes(rsa->n);
 542     buf = OPENSSL_malloc(num);
 543     if (ret == NULL || buf == NULL) {
 544         ERR_raise(ERR_LIB_RSA, ERR_R_MALLOC_FAILURE);
 545         goto err;
 546     }
 547
 548     /*
 549      * This check was for equality but PGP does evil things and chops off the
 550      * top '0' bytes
 551      */
 552     if (flen > num) {
 553         ERR_raise(ERR_LIB_RSA, RSA_R_DATA_GREATER_THAN_MOD_LEN);
 554         goto err;
 555     }
 556
 557     if (BN_bin2bn(from, flen, f) == NULL)
 558         goto err;
 559
 560     if (BN_ucmp(f, rsa->n) >= 0) {
 561         ERR_raise(ERR_LIB_RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
 562         goto err;
 563     }
 564
 565     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
 566         if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
 567                                     rsa->n, ctx))
 568             goto err;
 569
 570     if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
 571                                rsa->_method_mod_n))
 572         goto err;
 573
 574     if ((padding == RSA_X931_PADDING) && ((bn_get_words(ret)[0] & 0xf) != 12))
 575         if (!BN_sub(ret, rsa->n, ret))
 576             goto err;
 577
 578     i = BN_bn2binpad(ret, buf, num);
 579     if (i < 0)
 580         goto err;
 581
 582     switch (padding) {
 583     case RSA_PKCS1_PADDING:
 584         r = RSA_padding_check_PKCS1_type_1(to, num, buf, i, num);
 585         break;
 586     case RSA_X931_PADDING:
 587         r = RSA_padding_check_X931(to, num, buf, i, num);
 588         break;
 589     case RSA_NO_PADDING:
 590         memcpy(to, buf, (r = i));
 591         break;
 592     default:
 593         ERR_raise(ERR_LIB_RSA, RSA_R_UNKNOWN_PADDING_TYPE);
 594         goto err;
 595     }
 596     if (r < 0)
 597         ERR_raise(ERR_LIB_RSA, RSA_R_PADDING_CHECK_FAILED);
 598
 599  err:
 600     BN_CTX_end(ctx);
 601     BN_CTX_free(ctx);
 602     OPENSSL_clear_free(buf, num);
 603     return r;
 604 }
 605
 606 static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
 607 {
 608     BIGNUM *r1, *m1, *vrfy;
 609     int ret = 0, smooth = 0;
 610 #ifndef FIPS_MODULE
 611     BIGNUM *r2, *m[RSA_MAX_PRIME_NUM - 2];
 612     int i, ex_primes = 0;
 613     RSA_PRIME_INFO *pinfo;
 614 #endif
 615
 616     BN_CTX_start(ctx);
 617
 618     r1 = BN_CTX_get(ctx);
 619 #ifndef FIPS_MODULE
 620     r2 = BN_CTX_get(ctx);
 621 #endif
 622     m1 = BN_CTX_get(ctx);
 623     vrfy = BN_CTX_get(ctx);
 624     if (vrfy == NULL)
 625         goto err;
 626
 627 #ifndef FIPS_MODULE
 628     if (rsa->version == RSA_ASN1_VERSION_MULTI
 629         && ((ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0
 630              || ex_primes > RSA_MAX_PRIME_NUM - 2))
 631         goto err;
 632 #endif
 633
 634     if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) {
 635         BIGNUM *factor = BN_new();
 636
 637         if (factor == NULL)
 638             goto err;
 639
 640         /*
 641          * Make sure BN_mod_inverse in Montgomery initialization uses the
 642          * BN_FLG_CONSTTIME flag
 643          */
 644         if (!(BN_with_flags(factor, rsa->p, BN_FLG_CONSTTIME),
 645               BN_MONT_CTX_set_locked(&rsa->_method_mod_p, rsa->lock,
 646                                      factor, ctx))
 647             || !(BN_with_flags(factor, rsa->q, BN_FLG_CONSTTIME),
 648                  BN_MONT_CTX_set_locked(&rsa->_method_mod_q, rsa->lock,
 649                                         factor, ctx))) {
 650             BN_free(factor);
 651             goto err;
 652         }
 653 #ifndef FIPS_MODULE
 654         for (i = 0; i < ex_primes; i++) {
 655             pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
 656             BN_with_flags(factor, pinfo->r, BN_FLG_CONSTTIME);
 657             if (!BN_MONT_CTX_set_locked(&pinfo->m, rsa->lock, factor, ctx)) {
 658                 BN_free(factor);
 659                 goto err;
 660             }
 661         }
 662 #endif
 663         /*
 664          * We MUST free |factor| before any further use of the prime factors
 665          */
 666         BN_free(factor);
 667
 668         smooth = (rsa->meth->bn_mod_exp == BN_mod_exp_mont)
 669 #ifndef FIPS_MODULE
 670                  && (ex_primes == 0)
 671 #endif
 672                  && (BN_num_bits(rsa->q) == BN_num_bits(rsa->p));
 673     }
 674
 675     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
 676         if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock,
 677                                     rsa->n, ctx))
 678             goto err;
 679
 680     if (smooth) {
 681         /*
 682          * Conversion from Montgomery domain, a.k.a. Montgomery reduction,
 683          * accepts values in [0-m*2^w) range. w is m's bit width rounded up
 684          * to limb width. So that at the very least if |I| is fully reduced,
 685          * i.e. less than p*q, we can count on from-to round to perform
 686          * below modulo operations on |I|. Unlike BN_mod it's constant time.
 687          */
 688         if (/* m1 = I moq q */
 689             !bn_from_mont_fixed_top(m1, I, rsa->_method_mod_q, ctx)
 690             || !bn_to_mont_fixed_top(m1, m1, rsa->_method_mod_q, ctx)
 691             /* r1 = I mod p */
 692             || !bn_from_mont_fixed_top(r1, I, rsa->_method_mod_p, ctx)
 693             || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx)
 694             /*
 695              * Use parallel exponentiations optimization if possible,
 696              * otherwise fallback to two sequential exponentiations:
 697              *    m1 = m1^dmq1 mod q
 698              *    r1 = r1^dmp1 mod p
 699              */
 700             || !BN_mod_exp_mont_consttime_x2(m1, m1, rsa->dmq1, rsa->q,
 701                                              rsa->_method_mod_q,
 702                                              r1, r1, rsa->dmp1, rsa->p,
 703                                              rsa->_method_mod_p,
 704                                              ctx)
 705             /* r1 = (r1 - m1) mod p */
 706             /*
 707              * bn_mod_sub_fixed_top is not regular modular subtraction,
 708              * it can tolerate subtrahend to be larger than modulus, but
 709              * not bit-wise wider. This makes up for uncommon q>p case,
 710              * when |m1| can be larger than |rsa->p|.
 711              */
 712             || !bn_mod_sub_fixed_top(r1, r1, m1, rsa->p)
 713
 714             /* r1 = r1 * iqmp mod p */
 715             || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx)
 716             || !bn_mul_mont_fixed_top(r1, r1, rsa->iqmp, rsa->_method_mod_p,
 717                                       ctx)
 718             /* r0 = r1 * q + m1 */
 719             || !bn_mul_fixed_top(r0, r1, rsa->q, ctx)
 720             || !bn_mod_add_fixed_top(r0, r0, m1, rsa->n))
 721             goto err;
 722
 723         goto tail;
 724     }
 725
 726     /* compute I mod q */
 727     {
 728         BIGNUM *c = BN_new();
 729         if (c == NULL)
 730             goto err;
 731         BN_with_flags(c, I, BN_FLG_CONSTTIME);
 732
 733         if (!BN_mod(r1, c, rsa->q, ctx)) {
 734             BN_free(c);
 735             goto err;
 736         }
 737
 738         {
 739             BIGNUM *dmq1 = BN_new();
 740             if (dmq1 == NULL) {
 741                 BN_free(c);
 742                 goto err;
 743             }
 744             BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME);
 745
 746             /* compute r1^dmq1 mod q */
 747             if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx,
 748                                        rsa->_method_mod_q)) {
 749                 BN_free(c);
 750                 BN_free(dmq1);
 751                 goto err;
 752             }
 753             /* We MUST free dmq1 before any further use of rsa->dmq1 */
 754             BN_free(dmq1);
 755         }
 756
 757         /* compute I mod p */
 758         if (!BN_mod(r1, c, rsa->p, ctx)) {
 759             BN_free(c);
 760             goto err;
 761         }
 762         /* We MUST free c before any further use of I */
 763         BN_free(c);
 764     }
 765
 766     {
 767         BIGNUM *dmp1 = BN_new();
 768         if (dmp1 == NULL)
 769             goto err;
 770         BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME);
 771
 772         /* compute r1^dmp1 mod p */
 773         if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx,
 774                                    rsa->_method_mod_p)) {
 775             BN_free(dmp1);
 776             goto err;
 777         }
 778         /* We MUST free dmp1 before any further use of rsa->dmp1 */
 779         BN_free(dmp1);
 780     }
 781
 782 #ifndef FIPS_MODULE
 783     if (ex_primes > 0) {
 784         BIGNUM *di = BN_new(), *cc = BN_new();
 785
 786         if (cc == NULL || di == NULL) {
 787             BN_free(cc);
 788             BN_free(di);
 789             goto err;
 790         }
 791
 792         for (i = 0; i < ex_primes; i++) {
 793             /* prepare m_i */
 794             if ((m[i] = BN_CTX_get(ctx)) == NULL) {
 795                 BN_free(cc);
 796                 BN_free(di);
 797                 goto err;
 798             }
 799
 800             pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
 801
 802             /* prepare c and d_i */
 803             BN_with_flags(cc, I, BN_FLG_CONSTTIME);
 804             BN_with_flags(di, pinfo->d, BN_FLG_CONSTTIME);
 805
 806             if (!BN_mod(r1, cc, pinfo->r, ctx)) {
 807                 BN_free(cc);
 808                 BN_free(di);
 809                 goto err;
 810             }
 811             /* compute r1 ^ d_i mod r_i */
 812             if (!rsa->meth->bn_mod_exp(m[i], r1, di, pinfo->r, ctx, pinfo->m)) {
 813                 BN_free(cc);
 814                 BN_free(di);
 815                 goto err;
 816             }
 817         }
 818
 819         BN_free(cc);
 820         BN_free(di);
 821     }
 822 #endif
 823
 824     if (!BN_sub(r0, r0, m1))
 825         goto err;
 826     /*
 827      * This will help stop the size of r0 increasing, which does affect the
 828      * multiply if it optimised for a power of 2 size
 829      */
 830     if (BN_is_negative(r0))
 831         if (!BN_add(r0, r0, rsa->p))
 832             goto err;
 833
 834     if (!BN_mul(r1, r0, rsa->iqmp, ctx))
 835         goto err;
 836
 837     {
 838         BIGNUM *pr1 = BN_new();
 839         if (pr1 == NULL)
 840             goto err;
 841         BN_with_flags(pr1, r1, BN_FLG_CONSTTIME);
 842
 843         if (!BN_mod(r0, pr1, rsa->p, ctx)) {
 844             BN_free(pr1);
 845             goto err;
 846         }
 847         /* We MUST free pr1 before any further use of r1 */
 848         BN_free(pr1);
 849     }
 850
 851     /*
 852      * If p < q it is occasionally possible for the correction of adding 'p'
 853      * if r0 is negative above to leave the result still negative. This can
 854      * break the private key operations: the following second correction
 855      * should *always* correct this rare occurrence. This will *never* happen
 856      * with OpenSSL generated keys because they ensure p > q [steve]
 857      */
 858     if (BN_is_negative(r0))
 859         if (!BN_add(r0, r0, rsa->p))
 860             goto err;
 861     if (!BN_mul(r1, r0, rsa->q, ctx))
 862         goto err;
 863     if (!BN_add(r0, r1, m1))
 864         goto err;
 865
 866 #ifndef FIPS_MODULE
 867     /* add m_i to m in multi-prime case */
 868     if (ex_primes > 0) {
 869         BIGNUM *pr2 = BN_new();
 870
 871         if (pr2 == NULL)
 872             goto err;
 873
 874         for (i = 0; i < ex_primes; i++) {
 875             pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
 876             if (!BN_sub(r1, m[i], r0)) {
 877                 BN_free(pr2);
 878                 goto err;
 879             }
 880
 881             if (!BN_mul(r2, r1, pinfo->t, ctx)) {
 882                 BN_free(pr2);
 883                 goto err;
 884             }
 885
 886             BN_with_flags(pr2, r2, BN_FLG_CONSTTIME);
 887
 888             if (!BN_mod(r1, pr2, pinfo->r, ctx)) {
 889                 BN_free(pr2);
 890                 goto err;
 891             }
 892
 893             if (BN_is_negative(r1))
 894                 if (!BN_add(r1, r1, pinfo->r)) {
 895                     BN_free(pr2);
 896                     goto err;
 897                 }
 898             if (!BN_mul(r1, r1, pinfo->pp, ctx)) {
 899                 BN_free(pr2);
 900                 goto err;
 901             }
 902             if (!BN_add(r0, r0, r1)) {
 903                 BN_free(pr2);
 904                 goto err;
 905             }
 906         }
 907         BN_free(pr2);
 908     }
 909 #endif
 910
 911  tail:
 912     if (rsa->e && rsa->n) {
 913         if (rsa->meth->bn_mod_exp == BN_mod_exp_mont) {
 914             if (!BN_mod_exp_mont(vrfy, r0, rsa->e, rsa->n, ctx,
 915                                  rsa->_method_mod_n))
 916                 goto err;
 917         } else {
 918             bn_correct_top(r0);
 919             if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx,
 920                                        rsa->_method_mod_n))
 921                 goto err;
 922         }
 923         /*
 924          * If 'I' was greater than (or equal to) rsa->n, the operation will
 925          * be equivalent to using 'I mod n'. However, the result of the
 926          * verify will *always* be less than 'n' so we don't check for
 927          * absolute equality, just congruency.
 928          */
 929         if (!BN_sub(vrfy, vrfy, I))
 930             goto err;
 931         if (BN_is_zero(vrfy)) {
 932             bn_correct_top(r0);
 933             ret = 1;
 934             goto err;   /* not actually error */
 935         }
 936         if (!BN_mod(vrfy, vrfy, rsa->n, ctx))
 937             goto err;
 938         if (BN_is_negative(vrfy))
 939             if (!BN_add(vrfy, vrfy, rsa->n))
 940                 goto err;
 941         if (!BN_is_zero(vrfy)) {
 942             /*
 943              * 'I' and 'vrfy' aren't congruent mod n. Don't leak
 944              * miscalculated CRT output, just do a raw (slower) mod_exp and
 945              * return that instead.
 946              */
 947
 948             BIGNUM *d = BN_new();
 949             if (d == NULL)
 950                 goto err;
 951             BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 952
 953             if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx,
 954                                        rsa->_method_mod_n)) {
 955                 BN_free(d);
 956                 goto err;
 957             }
 958             /* We MUST free d before any further use of rsa->d */
 959             BN_free(d);
 960         }
 961     }
 962     /*
 963      * It's unfortunate that we have to bn_correct_top(r0). What hopefully
 964      * saves the day is that correction is highly unlike, and private key
 965      * operations are customarily performed on blinded message. Which means
 966      * that attacker won't observe correlation with chosen plaintext.
 967      * Secondly, remaining code would still handle it in same computational
 968      * time and even conceal memory access pattern around corrected top.
 969      */
 970     bn_correct_top(r0);
 971     ret = 1;
 972  err:
 973     BN_CTX_end(ctx);
 974     return ret;
 975 }
 976
 977 static int rsa_ossl_init(RSA *rsa)
 978 {
 979     rsa->flags |= RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE;
 980     return 1;
 981 }
 982
 983 static int rsa_ossl_finish(RSA *rsa)
 984 {
 985 #ifndef FIPS_MODULE
 986     int i;
 987     RSA_PRIME_INFO *pinfo;
 988
 989     for (i = 0; i < sk_RSA_PRIME_INFO_num(rsa->prime_infos); i++) {
 990         pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i);
 991         BN_MONT_CTX_free(pinfo->m);
 992     }
 993 #endif
 994
 995     BN_MONT_CTX_free(rsa->_method_mod_n);
 996     BN_MONT_CTX_free(rsa->_method_mod_p);
 997     BN_MONT_CTX_free(rsa->_method_mod_q);
 998     return 1;
 999 }