crypto/rsa/rsa_ossl.c

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