crypto/rsa/rsa_ossl.c

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