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