X-Git-Url: https://git.openssl.org/gitweb/?a=blobdiff_plain;f=crypto%2Frsa%2Frsa_ossl.c;h=5d5efdbd69db4ca999308d4a42e402035e4f3c48;hb=19bd1fa1ef17ff0ac071402cb6b002f1c29e37b9;hp=09a65b80b1f1203719b07a26c44c7a01d71f2f27;hpb=bf1605518a085256320ff4a36054445f842d5c1c;p=openssl.git diff --git a/crypto/rsa/rsa_ossl.c b/crypto/rsa/rsa_ossl.c index 09a65b80b1..5d5efdbd69 100644 --- a/crypto/rsa/rsa_ossl.c +++ b/crypto/rsa/rsa_ossl.c @@ -1,119 +1,16 @@ -/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) - * All rights reserved. - * - * This package is an SSL implementation written - * by Eric Young (eay@cryptsoft.com). - * The implementation was written so as to conform with Netscapes SSL. - * - * This library is free for commercial and non-commercial use as long as - * the following conditions are aheared to. The following conditions - * apply to all code found in this distribution, be it the RC4, RSA, - * lhash, DES, etc., code; not just the SSL code. The SSL documentation - * included with this distribution is covered by the same copyright terms - * except that the holder is Tim Hudson (tjh@cryptsoft.com). - * - * Copyright remains Eric Young's, and as such any Copyright notices in - * the code are not to be removed. - * If this package is used in a product, Eric Young should be given attribution - * as the author of the parts of the library used. - * This can be in the form of a textual message at program startup or - * in documentation (online or textual) provided with the package. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * "This product includes cryptographic software written by - * Eric Young (eay@cryptsoft.com)" - * The word 'cryptographic' can be left out if the rouines from the library - * being used are not cryptographic related :-). - * 4. If you include any Windows specific code (or a derivative thereof) from - * the apps directory (application code) you must include an acknowledgement: - * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" - * - * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND - * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE - * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE - * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL - * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS - * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT - * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY - * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF - * SUCH DAMAGE. - * - * The licence and distribution terms for any publically available version or - * derivative of this code cannot be changed. i.e. this code cannot simply be - * copied and put under another distribution licence - * [including the GNU Public Licence.] - */ -/* ==================================================================== - * Copyright (c) 1998-2006 The OpenSSL Project. All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in - * the documentation and/or other materials provided with the - * distribution. - * - * 3. All advertising materials mentioning features or use of this - * software must display the following acknowledgment: - * "This product includes software developed by the OpenSSL Project - * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" - * - * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to - * endorse or promote products derived from this software without - * prior written permission. For written permission, please contact - * openssl-core@openssl.org. - * - * 5. Products derived from this software may not be called "OpenSSL" - * nor may "OpenSSL" appear in their names without prior written - * permission of the OpenSSL Project. - * - * 6. Redistributions of any form whatsoever must retain the following - * acknowledgment: - * "This product includes software developed by the OpenSSL Project - * for use in the OpenSSL Toolkit (http://www.openssl.org/)" - * - * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY - * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE - * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR - * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR - * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; - * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) - * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, - * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) - * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED - * OF THE POSSIBILITY OF SUCH DAMAGE. - * ==================================================================== - * - * This product includes cryptographic software written by Eric Young - * (eay@cryptsoft.com). This product includes software written by Tim - * Hudson (tjh@cryptsoft.com). +/* + * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. * + * Licensed under the Apache License 2.0 (the "License"). You may not use + * this file except in compliance with the License. You can obtain a copy + * in the file LICENSE in the source distribution or at + * https://www.openssl.org/source/license.html */ #include "internal/cryptlib.h" #include "internal/bn_int.h" -#include -#include - -#ifndef RSA_NULL +#include "rsa_locl.h" +#include "internal/constant_time_locl.h" static int rsa_ossl_public_encrypt(int flen, const unsigned char *from, unsigned char *to, RSA *rsa, int padding); @@ -128,7 +25,7 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *i, RSA *rsa, static int rsa_ossl_init(RSA *rsa); static int rsa_ossl_finish(RSA *rsa); static RSA_METHOD rsa_pkcs1_ossl_meth = { - "OpenSSL PKCS#1 RSA (from Eric Young)", + "OpenSSL PKCS#1 RSA", rsa_ossl_public_encrypt, rsa_ossl_public_decrypt, /* signature verification */ rsa_ossl_private_encrypt, /* signing */ @@ -142,19 +39,37 @@ static RSA_METHOD rsa_pkcs1_ossl_meth = { NULL, 0, /* rsa_sign */ 0, /* rsa_verify */ - NULL /* rsa_keygen */ + NULL, /* rsa_keygen */ + NULL /* rsa_multi_prime_keygen */ }; +static const RSA_METHOD *default_RSA_meth = &rsa_pkcs1_ossl_meth; + +void RSA_set_default_method(const RSA_METHOD *meth) +{ + default_RSA_meth = meth; +} + +const RSA_METHOD *RSA_get_default_method(void) +{ + return default_RSA_meth; +} + const RSA_METHOD *RSA_PKCS1_OpenSSL(void) { return &rsa_pkcs1_ossl_meth; } +const RSA_METHOD *RSA_null_method(void) +{ + return NULL; +} + static int rsa_ossl_public_encrypt(int flen, const unsigned char *from, unsigned char *to, RSA *rsa, int padding) { BIGNUM *f, *ret; - int i, j, k, num = 0, r = -1; + int i, num = 0, r = -1; unsigned char *buf = NULL; BN_CTX *ctx = NULL; @@ -183,7 +98,7 @@ static int rsa_ossl_public_encrypt(int flen, const unsigned char *from, ret = BN_CTX_get(ctx); num = BN_num_bytes(rsa->n); buf = OPENSSL_malloc(num); - if (f == NULL || ret == NULL || buf == NULL) { + if (ret == NULL || buf == NULL) { RSAerr(RSA_F_RSA_OSSL_PUBLIC_ENCRYPT, ERR_R_MALLOC_FAILURE); goto err; } @@ -219,8 +134,8 @@ static int rsa_ossl_public_encrypt(int flen, const unsigned char *from, } if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) - if (!BN_MONT_CTX_set_locked - (&rsa->_method_mod_n, CRYPTO_LOCK_RSA, rsa->n, ctx)) + if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, + rsa->n, ctx)) goto err; if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx, @@ -228,46 +143,32 @@ static int rsa_ossl_public_encrypt(int flen, const unsigned char *from, goto err; /* - * put in leading 0 bytes if the number is less than the length of the - * modulus + * BN_bn2binpad puts in leading 0 bytes if the number is less than + * the length of the modulus. */ - j = BN_num_bytes(ret); - i = BN_bn2bin(ret, &(to[num - j])); - for (k = 0; k < (num - i); k++) - to[k] = 0; - - r = num; + r = BN_bn2binpad(ret, to, num); err: - if (ctx != NULL) - BN_CTX_end(ctx); + BN_CTX_end(ctx); BN_CTX_free(ctx); OPENSSL_clear_free(buf, num); - return (r); + return r; } static BN_BLINDING *rsa_get_blinding(RSA *rsa, int *local, BN_CTX *ctx) { BN_BLINDING *ret; - int got_write_lock = 0; - CRYPTO_THREADID cur; - CRYPTO_r_lock(CRYPTO_LOCK_RSA); + CRYPTO_THREAD_write_lock(rsa->lock); if (rsa->blinding == NULL) { - CRYPTO_r_unlock(CRYPTO_LOCK_RSA); - CRYPTO_w_lock(CRYPTO_LOCK_RSA); - got_write_lock = 1; - - if (rsa->blinding == NULL) - rsa->blinding = RSA_setup_blinding(rsa, ctx); + rsa->blinding = RSA_setup_blinding(rsa, ctx); } ret = rsa->blinding; if (ret == NULL) goto err; - CRYPTO_THREADID_current(&cur); - if (!CRYPTO_THREADID_cmp(&cur, BN_BLINDING_thread_id(ret))) { + if (BN_BLINDING_is_current_thread(ret)) { /* rsa->blinding is ours! */ *local = 1; @@ -282,42 +183,34 @@ static BN_BLINDING *rsa_get_blinding(RSA *rsa, int *local, BN_CTX *ctx) *local = 0; if (rsa->mt_blinding == NULL) { - if (!got_write_lock) { - CRYPTO_r_unlock(CRYPTO_LOCK_RSA); - CRYPTO_w_lock(CRYPTO_LOCK_RSA); - got_write_lock = 1; - } - - if (rsa->mt_blinding == NULL) - rsa->mt_blinding = RSA_setup_blinding(rsa, ctx); + rsa->mt_blinding = RSA_setup_blinding(rsa, ctx); } ret = rsa->mt_blinding; } err: - if (got_write_lock) - CRYPTO_w_unlock(CRYPTO_LOCK_RSA); - else - CRYPTO_r_unlock(CRYPTO_LOCK_RSA); + CRYPTO_THREAD_unlock(rsa->lock); return ret; } static int rsa_blinding_convert(BN_BLINDING *b, BIGNUM *f, BIGNUM *unblind, BN_CTX *ctx) { - if (unblind == NULL) + if (unblind == NULL) { /* * Local blinding: store the unblinding factor in BN_BLINDING. */ return BN_BLINDING_convert_ex(f, NULL, b, ctx); - else { + } else { /* * Shared blinding: store the unblinding factor outside BN_BLINDING. */ int ret; - CRYPTO_w_lock(CRYPTO_LOCK_RSA_BLINDING); + + BN_BLINDING_lock(b); ret = BN_BLINDING_convert_ex(f, unblind, b, ctx); - CRYPTO_w_unlock(CRYPTO_LOCK_RSA_BLINDING); + BN_BLINDING_unlock(b); + return ret; } } @@ -341,7 +234,7 @@ static int rsa_ossl_private_encrypt(int flen, const unsigned char *from, unsigned char *to, RSA *rsa, int padding) { BIGNUM *f, *ret, *res; - int i, j, k, num = 0, r = -1; + int i, num = 0, r = -1; unsigned char *buf = NULL; BN_CTX *ctx = NULL; int local_blinding = 0; @@ -360,7 +253,7 @@ static int rsa_ossl_private_encrypt(int flen, const unsigned char *from, ret = BN_CTX_get(ctx); num = BN_num_bytes(rsa->n); buf = OPENSSL_malloc(num); - if (f == NULL || ret == NULL || buf == NULL) { + if (ret == NULL || buf == NULL) { RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE); goto err; } @@ -393,6 +286,11 @@ static int rsa_ossl_private_encrypt(int flen, const unsigned char *from, goto err; } + if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) + if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, + rsa->n, ctx)) + goto err; + if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) { blinding = rsa_get_blinding(rsa, &local_blinding, ctx); if (blinding == NULL) { @@ -411,37 +309,32 @@ static int rsa_ossl_private_encrypt(int flen, const unsigned char *from, } if ((rsa->flags & RSA_FLAG_EXT_PKEY) || + (rsa->version == RSA_ASN1_VERSION_MULTI) || ((rsa->p != NULL) && (rsa->q != NULL) && (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) { if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx)) goto err; } else { - BIGNUM *d = NULL, *local_d = NULL; - - if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { - local_d = d = BN_new(); - if (d == NULL) { - RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE); - goto err; - } - BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); - } else - d = rsa->d; - - if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) - if (!BN_MONT_CTX_set_locked - (&rsa->_method_mod_n, CRYPTO_LOCK_RSA, rsa->n, ctx)) { - BN_free(local_d); - goto err; - } + BIGNUM *d = BN_new(); + if (d == NULL) { + RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, ERR_R_MALLOC_FAILURE); + goto err; + } + if (rsa->d == NULL) { + RSAerr(RSA_F_RSA_OSSL_PRIVATE_ENCRYPT, RSA_R_MISSING_PRIVATE_KEY); + BN_free(d); + goto err; + } + BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx, rsa->_method_mod_n)) { - BN_free(local_d); + BN_free(d); goto err; } - BN_free(local_d); + /* We MUST free d before any further use of rsa->d */ + BN_free(d); } if (blinding) @@ -449,30 +342,26 @@ static int rsa_ossl_private_encrypt(int flen, const unsigned char *from, goto err; if (padding == RSA_X931_PADDING) { - BN_sub(f, rsa->n, ret); + if (!BN_sub(f, rsa->n, ret)) + goto err; if (BN_cmp(ret, f) > 0) res = f; else res = ret; - } else + } else { res = ret; + } /* - * put in leading 0 bytes if the number is less than the length of the - * modulus + * BN_bn2binpad puts in leading 0 bytes if the number is less than + * the length of the modulus. */ - j = BN_num_bytes(res); - i = BN_bn2bin(res, &(to[num - j])); - for (k = 0; k < (num - i); k++) - to[k] = 0; - - r = num; + r = BN_bn2binpad(res, to, num); err: - if (ctx != NULL) - BN_CTX_end(ctx); + BN_CTX_end(ctx); BN_CTX_free(ctx); OPENSSL_clear_free(buf, num); - return (r); + return r; } static int rsa_ossl_private_decrypt(int flen, const unsigned char *from, @@ -480,7 +369,6 @@ static int rsa_ossl_private_decrypt(int flen, const unsigned char *from, { BIGNUM *f, *ret; int j, num = 0, r = -1; - unsigned char *p; unsigned char *buf = NULL; BN_CTX *ctx = NULL; int local_blinding = 0; @@ -499,7 +387,7 @@ static int rsa_ossl_private_decrypt(int flen, const unsigned char *from, ret = BN_CTX_get(ctx); num = BN_num_bytes(rsa->n); buf = OPENSSL_malloc(num); - if (f == NULL || ret == NULL || buf == NULL) { + if (ret == NULL || buf == NULL) { RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE); goto err; } @@ -543,44 +431,47 @@ static int rsa_ossl_private_decrypt(int flen, const unsigned char *from, /* do the decrypt */ if ((rsa->flags & RSA_FLAG_EXT_PKEY) || + (rsa->version == RSA_ASN1_VERSION_MULTI) || ((rsa->p != NULL) && (rsa->q != NULL) && (rsa->dmp1 != NULL) && (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) { if (!rsa->meth->rsa_mod_exp(ret, f, rsa, ctx)) goto err; } else { - BIGNUM *d = NULL, *local_d = NULL; - - if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { - local_d = d = BN_new(); - if (d == NULL) { - RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE); - goto err; - } - BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); - } else - d = rsa->d; + BIGNUM *d = BN_new(); + if (d == NULL) { + RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, ERR_R_MALLOC_FAILURE); + goto err; + } + if (rsa->d == NULL) { + RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_MISSING_PRIVATE_KEY); + BN_free(d); + goto err; + } + BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) - if (!BN_MONT_CTX_set_locked - (&rsa->_method_mod_n, CRYPTO_LOCK_RSA, rsa->n, ctx)) { - BN_free(local_d); + if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, + rsa->n, ctx)) { + BN_free(d); goto err; } if (!rsa->meth->bn_mod_exp(ret, f, d, rsa->n, ctx, rsa->_method_mod_n)) { - BN_free(local_d); + BN_free(d); goto err; } - BN_free(local_d); + /* We MUST free d before any further use of rsa->d */ + BN_free(d); } if (blinding) if (!rsa_blinding_invert(blinding, ret, unblind, ctx)) goto err; - p = buf; - j = BN_bn2bin(ret, p); /* j is only used with no-padding mode */ + j = BN_bn2binpad(ret, buf, num); + if (j < 0) + goto err; switch (padding) { case RSA_PKCS1_PADDING: @@ -593,21 +484,20 @@ static int rsa_ossl_private_decrypt(int flen, const unsigned char *from, r = RSA_padding_check_SSLv23(to, num, buf, j, num); break; case RSA_NO_PADDING: - r = RSA_padding_check_none(to, num, buf, j, num); + memcpy(to, buf, (r = j)); break; default: RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE); goto err; } - if (r < 0) - RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_PADDING_CHECK_FAILED); + RSAerr(RSA_F_RSA_OSSL_PRIVATE_DECRYPT, RSA_R_PADDING_CHECK_FAILED); + err_clear_last_constant_time(1 & ~constant_time_msb(r)); err: - if (ctx != NULL) - BN_CTX_end(ctx); + BN_CTX_end(ctx); BN_CTX_free(ctx); OPENSSL_clear_free(buf, num); - return (r); + return r; } /* signature verification */ @@ -616,7 +506,6 @@ static int rsa_ossl_public_decrypt(int flen, const unsigned char *from, { BIGNUM *f, *ret; int i, num = 0, r = -1; - unsigned char *p; unsigned char *buf = NULL; BN_CTX *ctx = NULL; @@ -645,7 +534,7 @@ static int rsa_ossl_public_decrypt(int flen, const unsigned char *from, ret = BN_CTX_get(ctx); num = BN_num_bytes(rsa->n); buf = OPENSSL_malloc(num); - if (f == NULL || ret == NULL || buf == NULL) { + if (ret == NULL || buf == NULL) { RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, ERR_R_MALLOC_FAILURE); goto err; } @@ -669,8 +558,8 @@ static int rsa_ossl_public_decrypt(int flen, const unsigned char *from, } if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) - if (!BN_MONT_CTX_set_locked - (&rsa->_method_mod_n, CRYPTO_LOCK_RSA, rsa->n, ctx)) + if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, + rsa->n, ctx)) goto err; if (!rsa->meth->bn_mod_exp(ret, f, rsa->e, rsa->n, ctx, @@ -681,8 +570,9 @@ static int rsa_ossl_public_decrypt(int flen, const unsigned char *from, if (!BN_sub(ret, rsa->n, ret)) goto err; - p = buf; - i = BN_bn2bin(ret, p); + i = BN_bn2binpad(ret, buf, num); + if (i < 0) + goto err; switch (padding) { case RSA_PKCS1_PADDING: @@ -692,7 +582,7 @@ static int rsa_ossl_public_decrypt(int flen, const unsigned char *from, r = RSA_padding_check_X931(to, num, buf, i, num); break; case RSA_NO_PADDING: - r = RSA_padding_check_none(to, num, buf, i, num); + memcpy(to, buf, (r = i)); break; default: RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_UNKNOWN_PADDING_TYPE); @@ -702,117 +592,220 @@ static int rsa_ossl_public_decrypt(int flen, const unsigned char *from, RSAerr(RSA_F_RSA_OSSL_PUBLIC_DECRYPT, RSA_R_PADDING_CHECK_FAILED); err: - if (ctx != NULL) - BN_CTX_end(ctx); + BN_CTX_end(ctx); BN_CTX_free(ctx); OPENSSL_clear_free(buf, num); - return (r); + return r; } static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) { - BIGNUM *r1, *m1, *vrfy; - BIGNUM *local_dmp1, *local_dmq1, *local_c, *local_r1; - BIGNUM *dmp1, *dmq1, *c, *pr1; - int ret = 0; + BIGNUM *r1, *m1, *vrfy, *r2, *m[RSA_MAX_PRIME_NUM - 2]; + int ret = 0, i, ex_primes = 0, smooth = 0; + RSA_PRIME_INFO *pinfo; BN_CTX_start(ctx); - local_dmp1 = BN_new(); - local_dmq1 = BN_new(); - local_c = BN_new(); - local_r1 = BN_new(); - if (local_dmp1 == NULL - || local_dmq1 == NULL || local_c == NULL || local_r1 == NULL) - goto err; - r1 = BN_CTX_get(ctx); + r2 = BN_CTX_get(ctx); m1 = BN_CTX_get(ctx); vrfy = BN_CTX_get(ctx); + if (vrfy == NULL) + goto err; - { - BIGNUM *local_p = NULL, *local_q = NULL; - BIGNUM *p = NULL, *q = NULL; + if (rsa->version == RSA_ASN1_VERSION_MULTI + && ((ex_primes = sk_RSA_PRIME_INFO_num(rsa->prime_infos)) <= 0 + || ex_primes > RSA_MAX_PRIME_NUM - 2)) + goto err; + + if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) { + BIGNUM *factor = BN_new(); + + if (factor == NULL) + goto err; /* - * Make sure BN_mod_inverse in Montgomery intialization uses the - * BN_FLG_CONSTTIME flag (unless RSA_FLAG_NO_CONSTTIME is set) + * Make sure BN_mod_inverse in Montgomery initialization uses the + * BN_FLG_CONSTTIME flag */ - if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { - local_p = p = BN_new(); - if (p == NULL) - goto err; - BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME); - - local_q = q = BN_new(); - if (q == NULL) { - BN_free(local_p); - goto err; - } - BN_with_flags(q, rsa->q, BN_FLG_CONSTTIME); - } else { - p = rsa->p; - q = rsa->q; + if (!(BN_with_flags(factor, rsa->p, BN_FLG_CONSTTIME), + BN_MONT_CTX_set_locked(&rsa->_method_mod_p, rsa->lock, + factor, ctx)) + || !(BN_with_flags(factor, rsa->q, BN_FLG_CONSTTIME), + BN_MONT_CTX_set_locked(&rsa->_method_mod_q, rsa->lock, + factor, ctx))) { + BN_free(factor); + goto err; } - - if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) { - if (!BN_MONT_CTX_set_locked - (&rsa->_method_mod_p, CRYPTO_LOCK_RSA, p, ctx) - || !BN_MONT_CTX_set_locked(&rsa->_method_mod_q, - CRYPTO_LOCK_RSA, q, ctx)) { - BN_free(local_p); - BN_free(local_q); + for (i = 0; i < ex_primes; i++) { + pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); + BN_with_flags(factor, pinfo->r, BN_FLG_CONSTTIME); + if (!BN_MONT_CTX_set_locked(&pinfo->m, rsa->lock, factor, ctx)) { + BN_free(factor); goto err; } } - BN_free(local_p); - BN_free(local_q); + /* + * We MUST free |factor| before any further use of the prime factors + */ + BN_free(factor); + + smooth = (ex_primes == 0) + && (rsa->meth->bn_mod_exp == BN_mod_exp_mont) + && (BN_num_bits(rsa->q) == BN_num_bits(rsa->p)); } if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) - if (!BN_MONT_CTX_set_locked - (&rsa->_method_mod_n, CRYPTO_LOCK_RSA, rsa->n, ctx)) + if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, rsa->lock, + rsa->n, ctx)) + goto err; + + if (smooth) { + /* + * Conversion from Montgomery domain, a.k.a. Montgomery reduction, + * accepts values in [0-m*2^w) range. w is m's bit width rounded up + * to limb width. So that at the very least if |I| is fully reduced, + * i.e. less than p*q, we can count on from-to round to perform + * below modulo operations on |I|. Unlike BN_mod it's constant time. + */ + if (/* m1 = I moq q */ + !bn_from_mont_fixed_top(m1, I, rsa->_method_mod_q, ctx) + || !bn_to_mont_fixed_top(m1, m1, rsa->_method_mod_q, ctx) + /* m1 = m1^dmq1 mod q */ + || !BN_mod_exp_mont_consttime(m1, m1, rsa->dmq1, rsa->q, ctx, + rsa->_method_mod_q) + /* r1 = I mod p */ + || !bn_from_mont_fixed_top(r1, I, rsa->_method_mod_p, ctx) + || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx) + /* r1 = r1^dmp1 mod p */ + || !BN_mod_exp_mont_consttime(r1, r1, rsa->dmp1, rsa->p, ctx, + rsa->_method_mod_p) + /* r1 = (r1 - m1) mod p */ + /* + * bn_mod_sub_fixed_top is not regular modular subtraction, + * it can tolerate subtrahend to be larger than modulus, but + * not bit-wise wider. This makes up for uncommon q>p case, + * when |m1| can be larger than |rsa->p|. + */ + || !bn_mod_sub_fixed_top(r1, r1, m1, rsa->p) + + /* r1 = r1 * iqmp mod p */ + || !bn_to_mont_fixed_top(r1, r1, rsa->_method_mod_p, ctx) + || !bn_mul_mont_fixed_top(r1, r1, rsa->iqmp, rsa->_method_mod_p, + ctx) + /* r0 = r1 * q + m1 */ + || !bn_mul_fixed_top(r0, r1, rsa->q, ctx) + || !bn_mod_add_fixed_top(r0, r0, m1, rsa->n)) goto err; + goto tail; + } + /* compute I mod q */ - if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { - c = local_c; + { + BIGNUM *c = BN_new(); + if (c == NULL) + goto err; BN_with_flags(c, I, BN_FLG_CONSTTIME); - if (!BN_mod(r1, c, rsa->q, ctx)) + + if (!BN_mod(r1, c, rsa->q, ctx)) { + BN_free(c); goto err; - } else { - if (!BN_mod(r1, I, rsa->q, ctx)) + } + + { + BIGNUM *dmq1 = BN_new(); + if (dmq1 == NULL) { + BN_free(c); + goto err; + } + BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME); + + /* compute r1^dmq1 mod q */ + if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx, + rsa->_method_mod_q)) { + BN_free(c); + BN_free(dmq1); + goto err; + } + /* We MUST free dmq1 before any further use of rsa->dmq1 */ + BN_free(dmq1); + } + + /* compute I mod p */ + if (!BN_mod(r1, c, rsa->p, ctx)) { + BN_free(c); goto err; + } + /* We MUST free c before any further use of I */ + BN_free(c); } - /* compute r1^dmq1 mod q */ - if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { - dmq1 = local_dmq1; - BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME); - } else - dmq1 = rsa->dmq1; - if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx, rsa->_method_mod_q)) - goto err; - - /* compute I mod p */ - if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { - c = local_c; - BN_with_flags(c, I, BN_FLG_CONSTTIME); - if (!BN_mod(r1, c, rsa->p, ctx)) + { + BIGNUM *dmp1 = BN_new(); + if (dmp1 == NULL) goto err; - } else { - if (!BN_mod(r1, I, rsa->p, ctx)) + BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME); + + /* compute r1^dmp1 mod p */ + if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx, + rsa->_method_mod_p)) { + BN_free(dmp1); goto err; + } + /* We MUST free dmp1 before any further use of rsa->dmp1 */ + BN_free(dmp1); } - /* compute r1^dmp1 mod p */ - if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { - dmp1 = local_dmp1; - BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME); - } else - dmp1 = rsa->dmp1; - if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx, rsa->_method_mod_p)) - goto err; + /* + * calculate m_i in multi-prime case + * + * TODO: + * 1. squash the following two loops and calculate |m_i| there. + * 2. remove cc and reuse |c|. + * 3. remove |dmq1| and |dmp1| in previous block and use |di|. + * + * If these things are done, the code will be more readable. + */ + if (ex_primes > 0) { + BIGNUM *di = BN_new(), *cc = BN_new(); + + if (cc == NULL || di == NULL) { + BN_free(cc); + BN_free(di); + goto err; + } + + for (i = 0; i < ex_primes; i++) { + /* prepare m_i */ + if ((m[i] = BN_CTX_get(ctx)) == NULL) { + BN_free(cc); + BN_free(di); + goto err; + } + + pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); + + /* prepare c and d_i */ + BN_with_flags(cc, I, BN_FLG_CONSTTIME); + BN_with_flags(di, pinfo->d, BN_FLG_CONSTTIME); + + if (!BN_mod(r1, cc, pinfo->r, ctx)) { + BN_free(cc); + BN_free(di); + goto err; + } + /* compute r1 ^ d_i mod r_i */ + if (!rsa->meth->bn_mod_exp(m[i], r1, di, pinfo->r, ctx, pinfo->m)) { + BN_free(cc); + BN_free(di); + goto err; + } + } + + BN_free(cc); + BN_free(di); + } if (!BN_sub(r0, r0, m1)) goto err; @@ -827,14 +820,19 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) if (!BN_mul(r1, r0, rsa->iqmp, ctx)) goto err; - /* Turn BN_FLG_CONSTTIME flag on before division operation */ - if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { - pr1 = local_r1; + { + BIGNUM *pr1 = BN_new(); + if (pr1 == NULL) + goto err; BN_with_flags(pr1, r1, BN_FLG_CONSTTIME); - } else - pr1 = r1; - if (!BN_mod(r0, pr1, rsa->p, ctx)) - goto err; + + if (!BN_mod(r0, pr1, rsa->p, ctx)) { + BN_free(pr1); + goto err; + } + /* We MUST free pr1 before any further use of r1 */ + BN_free(pr1); + } /* * If p < q it is occasionally possible for the correction of adding 'p' @@ -851,10 +849,61 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) if (!BN_add(r0, r1, m1)) goto err; - if (rsa->e && rsa->n) { - if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx, - rsa->_method_mod_n)) + /* add m_i to m in multi-prime case */ + if (ex_primes > 0) { + BIGNUM *pr2 = BN_new(); + + if (pr2 == NULL) goto err; + + for (i = 0; i < ex_primes; i++) { + pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); + if (!BN_sub(r1, m[i], r0)) { + BN_free(pr2); + goto err; + } + + if (!BN_mul(r2, r1, pinfo->t, ctx)) { + BN_free(pr2); + goto err; + } + + BN_with_flags(pr2, r2, BN_FLG_CONSTTIME); + + if (!BN_mod(r1, pr2, pinfo->r, ctx)) { + BN_free(pr2); + goto err; + } + + if (BN_is_negative(r1)) + if (!BN_add(r1, r1, pinfo->r)) { + BN_free(pr2); + goto err; + } + if (!BN_mul(r1, r1, pinfo->pp, ctx)) { + BN_free(pr2); + goto err; + } + if (!BN_add(r0, r0, r1)) { + BN_free(pr2); + goto err; + } + } + BN_free(pr2); + } + + tail: + if (rsa->e && rsa->n) { + if (rsa->meth->bn_mod_exp == BN_mod_exp_mont) { + if (!BN_mod_exp_mont(vrfy, r0, rsa->e, rsa->n, ctx, + rsa->_method_mod_n)) + goto err; + } else { + bn_correct_top(r0); + if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx, + rsa->_method_mod_n)) + goto err; + } /* * If 'I' was greater than (or equal to) rsa->n, the operation will * be equivalent to using 'I mod n'. However, the result of the @@ -863,6 +912,11 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) */ if (!BN_sub(vrfy, vrfy, I)) goto err; + if (BN_is_zero(vrfy)) { + bn_correct_top(r0); + ret = 1; + goto err; /* not actually error */ + } if (!BN_mod(vrfy, vrfy, rsa->n, ctx)) goto err; if (BN_is_negative(vrfy)) @@ -875,47 +929,52 @@ static int rsa_ossl_mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) * return that instead. */ - BIGNUM *local_d = NULL; - BIGNUM *d = NULL; + BIGNUM *d = BN_new(); + if (d == NULL) + goto err; + BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); - if (!(rsa->flags & RSA_FLAG_NO_CONSTTIME)) { - local_d = d = BN_new(); - if (d == NULL) - goto err; - BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME); - } else - d = rsa->d; if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx, rsa->_method_mod_n)) { - BN_free(local_d); + BN_free(d); goto err; } - - BN_free(local_d); + /* We MUST free d before any further use of rsa->d */ + BN_free(d); } } + /* + * It's unfortunate that we have to bn_correct_top(r0). What hopefully + * saves the day is that correction is highly unlike, and private key + * operations are customarily performed on blinded message. Which means + * that attacker won't observe correlation with chosen plaintext. + * Secondly, remaining code would still handle it in same computational + * time and even conceal memory access pattern around corrected top. + */ + bn_correct_top(r0); ret = 1; err: - BN_free(local_dmp1); - BN_free(local_dmq1); - BN_free(local_c); - BN_free(local_r1); BN_CTX_end(ctx); - return (ret); + return ret; } static int rsa_ossl_init(RSA *rsa) { rsa->flags |= RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE; - return (1); + return 1; } static int rsa_ossl_finish(RSA *rsa) { + int i; + RSA_PRIME_INFO *pinfo; + BN_MONT_CTX_free(rsa->_method_mod_n); BN_MONT_CTX_free(rsa->_method_mod_p); BN_MONT_CTX_free(rsa->_method_mod_q); - return (1); + for (i = 0; i < sk_RSA_PRIME_INFO_num(rsa->prime_infos); i++) { + pinfo = sk_RSA_PRIME_INFO_value(rsa->prime_infos, i); + BN_MONT_CTX_free(pinfo->m); + } + return 1; } - -#endif