crypto/rsa/rsa_eay.c

   1 /* crypto/rsa/rsa_eay.c */
   2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   3  * All rights reserved.
   4  *
   5  * This package is an SSL implementation written
   6  * by Eric Young (eay@cryptsoft.com).
   7  * The implementation was written so as to conform with Netscapes SSL.
   8  *
   9  * This library is free for commercial and non-commercial use as long as
  10  * the following conditions are aheared to.  The following conditions
  11  * apply to all code found in this distribution, be it the RC4, RSA,
  12  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  13  * included with this distribution is covered by the same copyright terms
  14  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  15  *
  16  * Copyright remains Eric Young's, and as such any Copyright notices in
  17  * the code are not to be removed.
  18  * If this package is used in a product, Eric Young should be given attribution
  19  * as the author of the parts of the library used.
  20  * This can be in the form of a textual message at program startup or
  21  * in documentation (online or textual) provided with the package.
  22  *
  23  * Redistribution and use in source and binary forms, with or without
  24  * modification, are permitted provided that the following conditions
  25  * are met:
  26  * 1. Redistributions of source code must retain the copyright
  27  *    notice, this list of conditions and the following disclaimer.
  28  * 2. Redistributions in binary form must reproduce the above copyright
  29  *    notice, this list of conditions and the following disclaimer in the
  30  *    documentation and/or other materials provided with the distribution.
  31  * 3. All advertising materials mentioning features or use of this software
  32  *    must display the following acknowledgement:
  33  *    "This product includes cryptographic software written by
  34  *     Eric Young (eay@cryptsoft.com)"
  35  *    The word 'cryptographic' can be left out if the rouines from the library
  36  *    being used are not cryptographic related :-).
  37  * 4. If you include any Windows specific code (or a derivative thereof) from
  38  *    the apps directory (application code) you must include an acknowledgement:
  39  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  40  *
  41  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  44  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  51  * SUCH DAMAGE.
  52  *
  53  * The licence and distribution terms for any publically available version or
  54  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  55  * copied and put under another distribution licence
  56  * [including the GNU Public Licence.]
  57  */
  58 /* ====================================================================
  59  * Copyright (c) 1998-2018 The OpenSSL Project.  All rights reserved.
  60  *
  61  * Redistribution and use in source and binary forms, with or without
  62  * modification, are permitted provided that the following conditions
  63  * are met:
  64  *
  65  * 1. Redistributions of source code must retain the above copyright
  66  *    notice, this list of conditions and the following disclaimer.
  67  *
  68  * 2. Redistributions in binary form must reproduce the above copyright
  69  *    notice, this list of conditions and the following disclaimer in
  70  *    the documentation and/or other materials provided with the
  71  *    distribution.
  72  *
  73  * 3. All advertising materials mentioning features or use of this
  74  *    software must display the following acknowledgment:
  75  *    "This product includes software developed by the OpenSSL Project
  76  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  77  *
  78  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  79  *    endorse or promote products derived from this software without
  80  *    prior written permission. For written permission, please contact
  81  *    openssl-core@openssl.org.
  82  *
  83  * 5. Products derived from this software may not be called "OpenSSL"
  84  *    nor may "OpenSSL" appear in their names without prior written
  85  *    permission of the OpenSSL Project.
  86  *
  87  * 6. Redistributions of any form whatsoever must retain the following
  88  *    acknowledgment:
  89  *    "This product includes software developed by the OpenSSL Project
  90  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  91  *
  92  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  93  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  94  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  95  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  96  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  97  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  98  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  99  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 100  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 101  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 102  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 103  * OF THE POSSIBILITY OF SUCH DAMAGE.
 104  * ====================================================================
 105  *
 106  * This product includes cryptographic software written by Eric Young
 107  * (eay@cryptsoft.com).  This product includes software written by Tim
 108  * Hudson (tjh@cryptsoft.com).
 109  *
 110  */
 111
 112 #include <stdio.h>
 113 #include "cryptlib.h"
 114 #include <openssl/bn.h>
 115 #include <openssl/rsa.h>
 116 #include <openssl/rand.h>
 117 #include "bn_int.h"
 118 #include "constant_time_locl.h"
 119
 120 #ifndef RSA_NULL
 121
 122 static int RSA_eay_public_encrypt(int flen, const unsigned char *from,
 123                                   unsigned char *to, RSA *rsa, int padding);
 124 static int RSA_eay_private_encrypt(int flen, const unsigned char *from,
 125                                    unsigned char *to, RSA *rsa, int padding);
 126 static int RSA_eay_public_decrypt(int flen, const unsigned char *from,
 127                                   unsigned char *to, RSA *rsa, int padding);
 128 static int RSA_eay_private_decrypt(int flen, const unsigned char *from,
 129                                    unsigned char *to, RSA *rsa, int padding);
 130 static int RSA_eay_mod_exp(BIGNUM *r0, const BIGNUM *i, RSA *rsa,
 131                            BN_CTX *ctx);
 132 static int RSA_eay_init(RSA *rsa);
 133 static int RSA_eay_finish(RSA *rsa);
 134 static RSA_METHOD rsa_pkcs1_eay_meth = {
 135     "Eric Young's PKCS#1 RSA",
 136     RSA_eay_public_encrypt,
 137     RSA_eay_public_decrypt,     /* signature verification */
 138     RSA_eay_private_encrypt,    /* signing */
 139     RSA_eay_private_decrypt,
 140     RSA_eay_mod_exp,
 141     BN_mod_exp_mont,            /* XXX probably we should not use Montgomery
 142                                  * if e == 3 */
 143     RSA_eay_init,
 144     RSA_eay_finish,
 145     0,                          /* flags */
 146     NULL,
 147     0,                          /* rsa_sign */
 148     0,                          /* rsa_verify */
 149     NULL                        /* rsa_keygen */
 150 };
 151
 152 const RSA_METHOD *RSA_PKCS1_SSLeay(void)
 153 {
 154     return (&rsa_pkcs1_eay_meth);
 155 }
 156
 157 static int RSA_eay_public_encrypt(int flen, const unsigned char *from,
 158                                   unsigned char *to, RSA *rsa, int padding)
 159 {
 160     BIGNUM *f, *ret;
 161     int i, num = 0, r = -1;
 162     unsigned char *buf = NULL;
 163     BN_CTX *ctx = NULL;
 164
 165     if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
 166         RSAerr(RSA_F_RSA_EAY_PUBLIC_ENCRYPT, RSA_R_MODULUS_TOO_LARGE);
 167         return -1;
 168     }
 169
 170     if (BN_ucmp(rsa->n, rsa->e) <= 0) {
 171         RSAerr(RSA_F_RSA_EAY_PUBLIC_ENCRYPT, RSA_R_BAD_E_VALUE);
 172         return -1;
 173     }
 174
 175     /* for large moduli, enforce exponent limit */
 176     if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) {
 177         if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
 178             RSAerr(RSA_F_RSA_EAY_PUBLIC_ENCRYPT, RSA_R_BAD_E_VALUE);
 179             return -1;
 180         }
 181     }
 182
 183     if ((ctx = BN_CTX_new()) == NULL)
 184         goto err;
 185     BN_CTX_start(ctx);
 186     f = BN_CTX_get(ctx);
 187     ret = BN_CTX_get(ctx);
 188     num = BN_num_bytes(rsa->n);
 189     buf = OPENSSL_malloc(num);
 190     if (!f || !ret || !buf) {
 191         RSAerr(RSA_F_RSA_EAY_PUBLIC_ENCRYPT, ERR_R_MALLOC_FAILURE);
 192         goto err;
 193     }
 194
 195     switch (padding) {
 196     case RSA_PKCS1_PADDING:
 197         i = RSA_padding_add_PKCS1_type_2(buf, num, from, flen);
 198         break;
 199 # ifndef OPENSSL_NO_SHA
 200     case RSA_PKCS1_OAEP_PADDING:
 201         i = RSA_padding_add_PKCS1_OAEP(buf, num, from, flen, NULL, 0);
 202         break;
 203 # endif
 204     case RSA_SSLV23_PADDING:
 205         i = RSA_padding_add_SSLv23(buf, num, from, flen);
 206         break;
 207     case RSA_NO_PADDING:
 208         i = RSA_padding_add_none(buf, num, from, flen);
 209         break;
 210     default:
 211         RSAerr(RSA_F_RSA_EAY_PUBLIC_ENCRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
 212         goto err;
 213     }
 214     if (i <= 0)
 215         goto err;
 216
 217     if (BN_bin2bn(buf, num, f) == NULL)
 218         goto err;
 219
 220     if (BN_ucmp(f, rsa->n) >= 0) {
 221         /* usually the padding functions would catch this */
 222         RSAerr(RSA_F_RSA_EAY_PUBLIC_ENCRYPT,
 223                RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
 224         goto err;
 225     }
 226
 227     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
 228         if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, CRYPTO_LOCK_RSA,
 229                                     rsa->n, ctx))
 230             goto err;
 231
 232     if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
 233                                rsa->_method_mod_n))
 234         goto err;
 235
 236     /*
 237      * BN_bn2binpad puts in leading 0 bytes if the number is less than
 238      * the length of the modulus.
 239      */
 240     r = bn_bn2binpad(ret, to, num);
 241  err:
 242     if (ctx != NULL) {
 243         BN_CTX_end(ctx);
 244         BN_CTX_free(ctx);
 245     }
 246     if (buf != NULL) {
 247         OPENSSL_cleanse(buf, num);
 248         OPENSSL_free(buf);
 249     }
 250     return (r);
 251 }
 252
 253 static BN_BLINDING *rsa_get_blinding(RSA *rsa, int *local, BN_CTX *ctx)
 254 {
 255     BN_BLINDING *ret;
 256     int got_write_lock = 0;
 257     CRYPTO_THREADID cur;
 258
 259     CRYPTO_r_lock(CRYPTO_LOCK_RSA);
 260
 261     if (rsa->blinding == NULL) {
 262         CRYPTO_r_unlock(CRYPTO_LOCK_RSA);
 263         CRYPTO_w_lock(CRYPTO_LOCK_RSA);
 264         got_write_lock = 1;
 265
 266         if (rsa->blinding == NULL)
 267             rsa->blinding = RSA_setup_blinding(rsa, ctx);
 268     }
 269
 270     ret = rsa->blinding;
 271     if (ret == NULL)
 272         goto err;
 273
 274     CRYPTO_THREADID_current(&cur);
 275     if (!CRYPTO_THREADID_cmp(&cur, BN_BLINDING_thread_id(ret))) {
 276         /* rsa->blinding is ours! */
 277
 278         *local = 1;
 279     } else {
 280         /* resort to rsa->mt_blinding instead */
 281
 282         /*
 283          * instructs rsa_blinding_convert(), rsa_blinding_invert() that the
 284          * BN_BLINDING is shared, meaning that accesses require locks, and
 285          * that the blinding factor must be stored outside the BN_BLINDING
 286          */
 287         *local = 0;
 288
 289         if (rsa->mt_blinding == NULL) {
 290             if (!got_write_lock) {
 291                 CRYPTO_r_unlock(CRYPTO_LOCK_RSA);
 292                 CRYPTO_w_lock(CRYPTO_LOCK_RSA);
 293                 got_write_lock = 1;
 294             }
 295
 296             if (rsa->mt_blinding == NULL)
 297                 rsa->mt_blinding = RSA_setup_blinding(rsa, ctx);
 298         }
 299         ret = rsa->mt_blinding;
 300     }
 301
 302  err:
 303     if (got_write_lock)
 304         CRYPTO_w_unlock(CRYPTO_LOCK_RSA);
 305     else
 306         CRYPTO_r_unlock(CRYPTO_LOCK_RSA);
 307     return ret;
 308 }
 309
 310 static int rsa_blinding_convert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind,
 311                                 BN_CTX *ctx)
 312 {
 313     if (unblind == NULL)
 314         /*
 315          * Local blinding: store the unblinding factor in BN_BLINDING.
 316          */
 317         return BN_BLINDING_convert_ex(f, NULL, b, ctx);
 318     else {
 319         /*
 320          * Shared blinding: store the unblinding factor outside BN_BLINDING.
 321          */
 322         int ret;
 323         CRYPTO_w_lock(CRYPTO_LOCK_RSA_BLINDING);
 324         ret = BN_BLINDING_convert_ex(f, unblind, b, ctx);
 325         CRYPTO_w_unlock(CRYPTO_LOCK_RSA_BLINDING);
 326         return ret;
 327     }
 328 }
 329
 330 static int rsa_blinding_invert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind,
 331                                BN_CTX *ctx)
 332 {
 333     /*
 334      * For local blinding, unblind is set to NULL, and BN_BLINDING_invert_ex
 335      * will use the unblinding factor stored in BN_BLINDING. If BN_BLINDING
 336      * is shared between threads, unblind must be non-null:
 337      * BN_BLINDING_invert_ex will then use the local unblinding factor, and
 338      * will only read the modulus from BN_BLINDING. In both cases it's safe
 339      * to access the blinding without a lock.
 340      */
 341     return BN_BLINDING_invert_ex(f, unblind, b, ctx);
 342 }
 343
 344 /* signing */
 345 static int RSA_eay_private_encrypt(int flen, const unsigned char *from,
 346                                    unsigned char *to, RSA *rsa, int padding)
 347 {
 348     BIGNUM *f, *ret, *res;
 349     int i, num = 0, r = -1;
 350     unsigned char *buf = NULL;
 351     BN_CTX *ctx = NULL;
 352     int local_blinding = 0;
 353     /*
 354      * Used only if the blinding structure is shared. A non-NULL unblind
 355      * instructs rsa_blinding_convert() and rsa_blinding_invert() to store
 356      * the unblinding factor outside the blinding structure.
 357      */
 358     BIGNUM *unblind = NULL;
 359     BN_BLINDING *blinding = NULL;
 360
 361     if ((ctx = BN_CTX_new()) == NULL)
 362         goto err;
 363     BN_CTX_start(ctx);
 364     f = BN_CTX_get(ctx);
 365     ret = BN_CTX_get(ctx);
 366     num = BN_num_bytes(rsa->n);
 367     buf = OPENSSL_malloc(num);
 368     if (!f || !ret || !buf) {
 369         RSAerr(RSA_F_RSA_EAY_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE);
 370         goto err;
 371     }
 372
 373     switch (padding) {
 374     case RSA_PKCS1_PADDING:
 375         i = RSA_padding_add_PKCS1_type_1(buf, num, from, flen);
 376         break;
 377     case RSA_X931_PADDING:
 378         i = RSA_padding_add_X931(buf, num, from, flen);
 379         break;
 380     case RSA_NO_PADDING:
 381         i = RSA_padding_add_none(buf, num, from, flen);
 382         break;
 383     case RSA_SSLV23_PADDING:
 384     default:
 385         RSAerr(RSA_F_RSA_EAY_PRIVATE_ENCRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
 386         goto err;
 387     }
 388     if (i <= 0)
 389         goto err;
 390
 391     if (BN_bin2bn(buf, num, f) == NULL)
 392         goto err;
 393
 394     if (BN_ucmp(f, rsa->n) >= 0) {
 395         /* usually the padding functions would catch this */
 396         RSAerr(RSA_F_RSA_EAY_PRIVATE_ENCRYPT,
 397                RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
 398         goto err;
 399     }
 400
 401     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
 402         if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, CRYPTO_LOCK_RSA,
 403                                     rsa->n, ctx))
 404             goto err;
 405
 406     if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
 407         blinding = rsa_get_blinding(rsa, &local_blinding, ctx);
 408         if (blinding == NULL) {
 409             RSAerr(RSA_F_RSA_EAY_PRIVATE_ENCRYPT, ERR_R_INTERNAL_ERROR);
 410             goto err;
 411         }
 412     }
 413
 414     if (blinding != NULL) {
 415         if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) {
 416             RSAerr(RSA_F_RSA_EAY_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE);
 417             goto err;
 418         }
 419         if (!rsa_blinding_convert(blinding, f, unblind, ctx))
 420             goto err;
 421     }
 422
 423     if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
 424         ((rsa->p != NULL) &&
 425          (rsa->q != NULL) &&
 426          (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
 427         if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
 428             goto err;
 429     } else {
 430         BIGNUM local_d;
 431         BIGNUM *d = NULL;
 432
 433         if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
 434             BN_init(&local_d);
 435             d = &local_d;
 436             BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 437         } else
 438             d = rsa->d;
 439
 440         if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx,
 441                                    rsa->_method_mod_n))
 442             goto err;
 443     }
 444
 445     if (blinding)
 446         if (!rsa_blinding_invert(blinding, ret, unblind, ctx))
 447             goto err;
 448
 449     if (padding == RSA_X931_PADDING) {
 450         BN_sub(f, rsa->n, ret);
 451         if (BN_cmp(ret, f) > 0)
 452             res = f;
 453         else
 454             res = ret;
 455     } else
 456         res = ret;
 457
 458     /*
 459      * BN_bn2binpad puts in leading 0 bytes if the number is less than
 460      * the length of the modulus.
 461      */
 462     r = bn_bn2binpad(res, to, num);
 463  err:
 464     if (ctx != NULL) {
 465         BN_CTX_end(ctx);
 466         BN_CTX_free(ctx);
 467     }
 468     if (buf != NULL) {
 469         OPENSSL_cleanse(buf, num);
 470         OPENSSL_free(buf);
 471     }
 472     return (r);
 473 }
 474
 475 static int RSA_eay_private_decrypt(int flen, const unsigned char *from,
 476                                    unsigned char *to, RSA *rsa, int padding)
 477 {
 478     BIGNUM *f, *ret;
 479     int j, num = 0, r = -1;
 480     unsigned char *buf = NULL;
 481     BN_CTX *ctx = NULL;
 482     int local_blinding = 0;
 483     /*
 484      * Used only if the blinding structure is shared. A non-NULL unblind
 485      * instructs rsa_blinding_convert() and rsa_blinding_invert() to store
 486      * the unblinding factor outside the blinding structure.
 487      */
 488     BIGNUM *unblind = NULL;
 489     BN_BLINDING *blinding = NULL;
 490
 491     if ((ctx = BN_CTX_new()) == NULL)
 492         goto err;
 493     BN_CTX_start(ctx);
 494     f = BN_CTX_get(ctx);
 495     ret = BN_CTX_get(ctx);
 496     num = BN_num_bytes(rsa->n);
 497     buf = OPENSSL_malloc(num);
 498     if (!f || !ret || !buf) {
 499         RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE);
 500         goto err;
 501     }
 502
 503     /*
 504      * This check was for equality but PGP does evil things and chops off the
 505      * top '0' bytes
 506      */
 507     if (flen > num) {
 508         RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,
 509                RSA_R_DATA_GREATER_THAN_MOD_LEN);
 510         goto err;
 511     }
 512
 513     /* make data into a big number */
 514     if (BN_bin2bn(from, (int)flen, f) == NULL)
 515         goto err;
 516
 517     if (BN_ucmp(f, rsa->n) >= 0) {
 518         RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT,
 519                RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
 520         goto err;
 521     }
 522
 523     if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
 524         blinding = rsa_get_blinding(rsa, &local_blinding, ctx);
 525         if (blinding == NULL) {
 526             RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT, ERR_R_INTERNAL_ERROR);
 527             goto err;
 528         }
 529     }
 530
 531     if (blinding != NULL) {
 532         if (!local_blinding && ((unblind = BN_CTX_get(ctx)) == NULL)) {
 533             RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE);
 534             goto err;
 535         }
 536         if (!rsa_blinding_convert(blinding, f, unblind, ctx))
 537             goto err;
 538     }
 539
 540     /* do the decrypt */
 541     if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
 542         ((rsa->p != NULL) &&
 543          (rsa->q != NULL) &&
 544          (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
 545         if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx))
 546             goto err;
 547     } else {
 548         BIGNUM local_d;
 549         BIGNUM *d = NULL;
 550
 551         if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
 552             d = &local_d;
 553             BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 554         } else
 555             d = rsa->d;
 556
 557         if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
 558             if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, CRYPTO_LOCK_RSA,
 559                                         rsa->n, ctx))
 560                 goto err;
 561         if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx,
 562                                    rsa->_method_mod_n))
 563             goto err;
 564     }
 565
 566     if (blinding)
 567         if (!rsa_blinding_invert(blinding, ret, unblind, ctx))
 568             goto err;
 569
 570     j = bn_bn2binpad(ret, buf, num);
 571
 572     switch (padding) {
 573     case RSA_PKCS1_PADDING:
 574         r = RSA_padding_check_PKCS1_type_2(to, num, buf, j, num);
 575         break;
 576 # ifndef OPENSSL_NO_SHA
 577     case RSA_PKCS1_OAEP_PADDING:
 578         r = RSA_padding_check_PKCS1_OAEP(to, num, buf, j, num, NULL, 0);
 579         break;
 580 # endif
 581     case RSA_SSLV23_PADDING:
 582         r = RSA_padding_check_SSLv23(to, num, buf, j, num);
 583         break;
 584     case RSA_NO_PADDING:
 585         memcpy(to, buf, (r = j));
 586         break;
 587     default:
 588         RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
 589         goto err;
 590     }
 591     RSAerr(RSA_F_RSA_EAY_PRIVATE_DECRYPT, RSA_R_PADDING_CHECK_FAILED);
 592     err_clear_last_constant_time(r >= 0);
 593
 594  err:
 595     if (ctx != NULL) {
 596         BN_CTX_end(ctx);
 597         BN_CTX_free(ctx);
 598     }
 599     if (buf != NULL) {
 600         OPENSSL_cleanse(buf, num);
 601         OPENSSL_free(buf);
 602     }
 603     return (r);
 604 }
 605
 606 /* signature verification */
 607 static int RSA_eay_public_decrypt(int flen, const unsigned char *from,
 608                                   unsigned char *to, RSA *rsa, int padding)
 609 {
 610     BIGNUM *f, *ret;
 611     int i, num = 0, r = -1;
 612     unsigned char *buf = NULL;
 613     BN_CTX *ctx = NULL;
 614
 615     if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
 616         RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT, RSA_R_MODULUS_TOO_LARGE);
 617         return -1;
 618     }
 619
 620     if (BN_ucmp(rsa->n, rsa->e) <= 0) {
 621         RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE);
 622         return -1;
 623     }
 624
 625     /* for large moduli, enforce exponent limit */
 626     if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) {
 627         if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
 628             RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT, RSA_R_BAD_E_VALUE);
 629             return -1;
 630         }
 631     }
 632
 633     if ((ctx = BN_CTX_new()) == NULL)
 634         goto err;
 635     BN_CTX_start(ctx);
 636     f = BN_CTX_get(ctx);
 637     ret = BN_CTX_get(ctx);
 638     num = BN_num_bytes(rsa->n);
 639     buf = OPENSSL_malloc(num);
 640     if (!f || !ret || !buf) {
 641         RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT, ERR_R_MALLOC_FAILURE);
 642         goto err;
 643     }
 644
 645     /*
 646      * This check was for equality but PGP does evil things and chops off the
 647      * top '0' bytes
 648      */
 649     if (flen > num) {
 650         RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT, RSA_R_DATA_GREATER_THAN_MOD_LEN);
 651         goto err;
 652     }
 653
 654     if (BN_bin2bn(from, flen, f) == NULL)
 655         goto err;
 656
 657     if (BN_ucmp(f, rsa->n) >= 0) {
 658         RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT,
 659                RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
 660         goto err;
 661     }
 662
 663     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
 664         if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, CRYPTO_LOCK_RSA,
 665                                     rsa->n, ctx))
 666             goto err;
 667
 668     if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx,
 669                                rsa->_method_mod_n))
 670         goto err;
 671
 672     if ((padding == RSA_X931_PADDING) && ((ret->d[0] & 0xf) != 12))
 673         if (!BN_sub(ret, rsa->n, ret))
 674             goto err;
 675
 676     i = bn_bn2binpad(ret, buf, num);
 677
 678     switch (padding) {
 679     case RSA_PKCS1_PADDING:
 680         r = RSA_padding_check_PKCS1_type_1(to, num, buf, i, num);
 681         break;
 682     case RSA_X931_PADDING:
 683         r = RSA_padding_check_X931(to, num, buf, i, num);
 684         break;
 685     case RSA_NO_PADDING:
 686         memcpy(to, buf, (r = i));
 687         break;
 688     default:
 689         RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE);
 690         goto err;
 691     }
 692     if (r < 0)
 693         RSAerr(RSA_F_RSA_EAY_PUBLIC_DECRYPT, RSA_R_PADDING_CHECK_FAILED);
 694
 695  err:
 696     if (ctx != NULL) {
 697         BN_CTX_end(ctx);
 698         BN_CTX_free(ctx);
 699     }
 700     if (buf != NULL) {
 701         OPENSSL_cleanse(buf, num);
 702         OPENSSL_free(buf);
 703     }
 704     return (r);
 705 }
 706
 707 static int RSA_eay_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx)
 708 {
 709     BIGNUM *r1, *m1, *vrfy;
 710     BIGNUM local_dmp1, local_dmq1, local_c, local_r1;
 711     BIGNUM *dmp1, *dmq1, *c, *pr1;
 712     int ret = 0, smooth = 0;
 713
 714     BN_CTX_start(ctx);
 715     r1 = BN_CTX_get(ctx);
 716     m1 = BN_CTX_get(ctx);
 717     vrfy = BN_CTX_get(ctx);
 718
 719     {
 720         BIGNUM local_p, local_q;
 721         BIGNUM *p = NULL, *q = NULL;
 722
 723         /*
 724          * Make sure BN_mod_inverse in Montgomery intialization uses the
 725          * BN_FLG_CONSTTIME flag (unless RSA_FLAG_NO_CONSTTIME is set)
 726          */
 727         if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
 728             BN_init(&local_p);
 729             p = &local_p;
 730             BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
 731
 732             BN_init(&local_q);
 733             q = &local_q;
 734             BN_with_flags(q, rsa->q, BN_FLG_CONSTTIME);
 735         } else {
 736             p = rsa->p;
 737             q = rsa->q;
 738         }
 739
 740         if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) {
 741             if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_p, CRYPTO_LOCK_RSA,
 742                                         p, ctx))
 743                 goto err;
 744             if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_q, CRYPTO_LOCK_RSA,
 745                                         q, ctx))
 746                 goto err;
 747
 748             smooth = (rsa->meth->bn_mod_exp == BN_mod_exp_mont)
 749                      && (BN_num_bits(q) == BN_num_bits(p));
 750         }
 751     }
 752
 753     if (rsa->flags & RSA_FLAG_CACHE_PUBLIC)
 754         if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, CRYPTO_LOCK_RSA,
 755                                     rsa->n, ctx))
 756             goto err;
 757
 758     if (smooth) {
 759         /*
 760          * Conversion from Montgomery domain, a.k.a. Montgomery reduction,
 761          * accepts values in [0-m*2^w) range. w is m's bit width rounded up
 762          * to limb width. So that at the very least if |I| is fully reduced,
 763          * i.e. less than p*q, we can count on from-to round to perform
 764          * below modulo operations on |I|. Unlike BN_mod it's constant time.
 765          */
 766         if (/* m1 = I moq q */
 767             !bn_from_mont_fixed_top(m1, I, rsa->_method_mod_q, ctx)
 768             || !bn_to_mont_fixed_top(m1, m1, rsa->_method_mod_q, ctx)
 769             /* m1 = m1^dmq1 mod q */
 770             || !BN_mod_exp_mont_consttime(m1, m1, rsa->dmq1, rsa->q, ctx,
 771                                           rsa->_method_mod_q)
 772             /* r1 = I mod p */
 773             || !bn_from_mont_fixed_top(r1, I, rsa->_method_mod_p, ctx)
 774             || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx)
 775             /* r1 = r1^dmp1 mod p */
 776             || !BN_mod_exp_mont_consttime(r1, r1, rsa->dmp1, rsa->p, ctx,
 777                                           rsa->_method_mod_p)
 778             /* r1 = (r1 - m1) mod p */
 779             /*
 780              * bn_mod_sub_fixed_top is not regular modular subtraction,
 781              * it can tolerate subtrahend to be larger than modulus, but
 782              * not bit-wise wider. This makes up for uncommon q>p case,
 783              * when |m1| can be larger than |rsa->p|.
 784              */
 785             || !bn_mod_sub_fixed_top(r1, r1, m1, rsa->p)
 786
 787             /* r1 = r1 * iqmp mod p */
 788             || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx)
 789             || !bn_mul_mont_fixed_top(r1, r1, rsa->iqmp, rsa->_method_mod_p,
 790                                       ctx)
 791             /* r0 = r1 * q + m1 */
 792             || !bn_mul_fixed_top(r0, r1, rsa->q, ctx)
 793             || !bn_mod_add_fixed_top(r0, r0, m1, rsa->n))
 794             goto err;
 795
 796         goto tail;
 797     }
 798
 799     /* compute I mod q */
 800     if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
 801         c = &local_c;
 802         BN_with_flags(c, I, BN_FLG_CONSTTIME);
 803         if (!BN_mod(r1, c, rsa->q, ctx))
 804             goto err;
 805     } else {
 806         if (!BN_mod(r1, I, rsa->q, ctx))
 807             goto err;
 808     }
 809
 810     /* compute r1^dmq1 mod q */
 811     if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
 812         dmq1 = &local_dmq1;
 813         BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME);
 814     } else
 815         dmq1 = rsa->dmq1;
 816     if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx, rsa->_method_mod_q))
 817         goto err;
 818
 819     /* compute I mod p */
 820     if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
 821         c = &local_c;
 822         BN_with_flags(c, I, BN_FLG_CONSTTIME);
 823         if (!BN_mod(r1, c, rsa->p, ctx))
 824             goto err;
 825     } else {
 826         if (!BN_mod(r1, I, rsa->p, ctx))
 827             goto err;
 828     }
 829
 830     /* compute r1^dmp1 mod p */
 831     if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
 832         dmp1 = &local_dmp1;
 833         BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME);
 834     } else
 835         dmp1 = rsa->dmp1;
 836     if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx, rsa->_method_mod_p))
 837         goto err;
 838
 839     if (!BN_sub(r0, r0, m1))
 840         goto err;
 841     /*
 842      * This will help stop the size of r0 increasing, which does affect the
 843      * multiply if it optimised for a power of 2 size
 844      */
 845     if (BN_is_negative(r0))
 846         if (!BN_add(r0, r0, rsa->p))
 847             goto err;
 848
 849     if (!BN_mul(r1, r0, rsa->iqmp, ctx))
 850         goto err;
 851
 852     /* Turn BN_FLG_CONSTTIME flag on before division operation */
 853     if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
 854         pr1 = &local_r1;
 855         BN_with_flags(pr1, r1, BN_FLG_CONSTTIME);
 856     } else
 857         pr1 = r1;
 858     if (!BN_mod(r0, pr1, rsa->p, ctx))
 859         goto err;
 860
 861     /*
 862      * If p < q it is occasionally possible for the correction of adding 'p'
 863      * if r0 is negative above to leave the result still negative. This can
 864      * break the private key operations: the following second correction
 865      * should *always* correct this rare occurrence. This will *never* happen
 866      * with OpenSSL generated keys because they ensure p > q [steve]
 867      */
 868     if (BN_is_negative(r0))
 869         if (!BN_add(r0, r0, rsa->p))
 870             goto err;
 871     if (!BN_mul(r1, r0, rsa->q, ctx))
 872         goto err;
 873     if (!BN_add(r0, r1, m1))
 874         goto err;
 875
 876  tail:
 877     if (rsa->e && rsa->n) {
 878         if (rsa->meth->bn_mod_exp == BN_mod_exp_mont) {
 879             if (!BN_mod_exp_mont(vrfy, r0, rsa->e, rsa->n, ctx,
 880                                  rsa->_method_mod_n))
 881                 goto err;
 882         } else {
 883             bn_correct_top(r0);
 884             if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx,
 885                                        rsa->_method_mod_n))
 886                 goto err;
 887         }
 888         /*
 889          * If 'I' was greater than (or equal to) rsa->n, the operation will
 890          * be equivalent to using 'I mod n'. However, the result of the
 891          * verify will *always* be less than 'n' so we don't check for
 892          * absolute equality, just congruency.
 893          */
 894         if (!BN_sub(vrfy, vrfy, I))
 895             goto err;
 896         if (BN_is_zero(vrfy)) {
 897             bn_correct_top(r0);
 898             ret = 1;
 899             goto err;   /* not actually error */
 900         }
 901         if (!BN_mod(vrfy, vrfy, rsa->n, ctx))
 902             goto err;
 903         if (BN_is_negative(vrfy))
 904             if (!BN_add(vrfy, vrfy, rsa->n))
 905                 goto err;
 906         if (!BN_is_zero(vrfy)) {
 907             /*
 908              * 'I' and 'vrfy' aren't congruent mod n. Don't leak
 909              * miscalculated CRT output, just do a raw (slower) mod_exp and
 910              * return that instead.
 911              */
 912
 913             BIGNUM local_d;
 914             BIGNUM *d = NULL;
 915
 916             if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) {
 917                 d = &local_d;
 918                 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
 919             } else
 920                 d = rsa->d;
 921             if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx,
 922                                        rsa->_method_mod_n))
 923                 goto err;
 924         }
 925     }
 926     /*
 927      * It's unfortunate that we have to bn_correct_top(r0). What hopefully
 928      * saves the day is that correction is highly unlike, and private key
 929      * operations are customarily performed on blinded message. Which means
 930      * that attacker won't observe correlation with chosen plaintext.
 931      * Secondly, remaining code would still handle it in same computational
 932      * time and even conceal memory access pattern around corrected top.
 933      */
 934     bn_correct_top(r0);
 935     ret = 1;
 936  err:
 937     BN_CTX_end(ctx);
 938     return (ret);
 939 }
 940
 941 static int RSA_eay_init(RSA *rsa)
 942 {
 943     rsa->flags |= RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE;
 944     return (1);
 945 }
 946
 947 static int RSA_eay_finish(RSA *rsa)
 948 {
 949     if (rsa->_method_mod_n != NULL)
 950         BN_MONT_CTX_free(rsa->_method_mod_n);
 951     if (rsa->_method_mod_p != NULL)
 952         BN_MONT_CTX_free(rsa->_method_mod_p);
 953     if (rsa->_method_mod_q != NULL)
 954         BN_MONT_CTX_free(rsa->_method_mod_q);
 955     return (1);
 956 }
 957
 958 #endif