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