crypto/rsa/rsa_ossl.c

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