crypto/rsa/rsa_ossl.c

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