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