1 /* ==================================================================== 2 * Copyright (c) 1998-2006 The OpenSSL Project. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in 13 * the documentation and/or other materials provided with the 14 * distribution. 15 * 16 * 3. All advertising materials mentioning features or use of this 17 * software must display the following acknowledgment: 18 * "This product includes software developed by the OpenSSL Project 19 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 20 * 21 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 22 * endorse or promote products derived from this software without 23 * prior written permission. For written permission, please contact 24 * openssl-core (at) openssl.org. 25 * 26 * 5. Products derived from this software may not be called "OpenSSL" 27 * nor may "OpenSSL" appear in their names without prior written 28 * permission of the OpenSSL Project. 29 * 30 * 6. Redistributions of any form whatsoever must retain the following 31 * acknowledgment: 32 * "This product includes software developed by the OpenSSL Project 33 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 34 * 35 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 36 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 37 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 38 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 39 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 40 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 41 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 42 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 43 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 44 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 45 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 46 * OF THE POSSIBILITY OF SUCH DAMAGE. 47 * ==================================================================== 48 * 49 * This product includes cryptographic software written by Eric Young 50 * (eay (at) cryptsoft.com). This product includes software written by Tim 51 * Hudson (tjh (at) cryptsoft.com). 52 * 53 * Copyright (C) 1995-1998 Eric Young (eay (at) cryptsoft.com) 54 * All rights reserved. 55 * 56 * This package is an SSL implementation written 57 * by Eric Young (eay (at) cryptsoft.com). 58 * The implementation was written so as to conform with Netscapes SSL. 59 * 60 * This library is free for commercial and non-commercial use as long as 61 * the following conditions are aheared to. The following conditions 62 * apply to all code found in this distribution, be it the RC4, RSA, 63 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 64 * included with this distribution is covered by the same copyright terms 65 * except that the holder is Tim Hudson (tjh (at) cryptsoft.com). 66 * 67 * Copyright remains Eric Young's, and as such any Copyright notices in 68 * the code are not to be removed. 69 * If this package is used in a product, Eric Young should be given attribution 70 * as the author of the parts of the library used. 71 * This can be in the form of a textual message at program startup or 72 * in documentation (online or textual) provided with the package. 73 * 74 * Redistribution and use in source and binary forms, with or without 75 * modification, are permitted provided that the following conditions 76 * are met: 77 * 1. Redistributions of source code must retain the copyright 78 * notice, this list of conditions and the following disclaimer. 79 * 2. Redistributions in binary form must reproduce the above copyright 80 * notice, this list of conditions and the following disclaimer in the 81 * documentation and/or other materials provided with the distribution. 82 * 3. All advertising materials mentioning features or use of this software 83 * must display the following acknowledgement: 84 * "This product includes cryptographic software written by 85 * Eric Young (eay (at) cryptsoft.com)" 86 * The word 'cryptographic' can be left out if the rouines from the library 87 * being used are not cryptographic related :-). 88 * 4. If you include any Windows specific code (or a derivative thereof) from 89 * the apps directory (application code) you must include an acknowledgement: 90 * "This product includes software written by Tim Hudson (tjh (at) cryptsoft.com)" 91 * 92 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 93 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 94 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 95 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 96 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 97 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 98 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 99 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 100 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 101 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 102 * SUCH DAMAGE. 103 * 104 * The licence and distribution terms for any publically available version or 105 * derivative of this code cannot be changed. i.e. this code cannot simply be 106 * copied and put under another distribution licence 107 * [including the GNU Public Licence.] */ 108 109 #include <openssl/rsa.h> 110 111 #include <string.h> 112 113 #include <openssl/bn.h> 114 #include <openssl/mem.h> 115 #include <openssl/err.h> 116 117 #include "internal.h" 118 #include "../internal.h" 119 120 121 #define BN_BLINDING_COUNTER 32 122 123 struct bn_blinding_st { 124 BIGNUM *A; /* The base blinding factor, Montgomery-encoded. */ 125 BIGNUM *Ai; /* The inverse of the blinding factor, Montgomery-encoded. */ 126 unsigned counter; 127 }; 128 129 static int bn_blinding_create_param(BN_BLINDING *b, const BIGNUM *e, 130 const BN_MONT_CTX *mont, BN_CTX *ctx); 131 132 BN_BLINDING *BN_BLINDING_new(void) { 133 BN_BLINDING *ret = OPENSSL_malloc(sizeof(BN_BLINDING)); 134 if (ret == NULL) { 135 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE); 136 return NULL; 137 } 138 OPENSSL_memset(ret, 0, sizeof(BN_BLINDING)); 139 140 ret->A = BN_new(); 141 if (ret->A == NULL) { 142 goto err; 143 } 144 145 ret->Ai = BN_new(); 146 if (ret->Ai == NULL) { 147 goto err; 148 } 149 150 /* The blinding values need to be created before this blinding can be used. */ 151 ret->counter = BN_BLINDING_COUNTER - 1; 152 153 return ret; 154 155 err: 156 BN_BLINDING_free(ret); 157 return NULL; 158 } 159 160 void BN_BLINDING_free(BN_BLINDING *r) { 161 if (r == NULL) { 162 return; 163 } 164 165 BN_free(r->A); 166 BN_free(r->Ai); 167 OPENSSL_free(r); 168 } 169 170 static int bn_blinding_update(BN_BLINDING *b, const BIGNUM *e, 171 const BN_MONT_CTX *mont, BN_CTX *ctx) { 172 if (++b->counter == BN_BLINDING_COUNTER) { 173 /* re-create blinding parameters */ 174 if (!bn_blinding_create_param(b, e, mont, ctx)) { 175 goto err; 176 } 177 b->counter = 0; 178 } else { 179 if (!BN_mod_mul_montgomery(b->A, b->A, b->A, mont, ctx) || 180 !BN_mod_mul_montgomery(b->Ai, b->Ai, b->Ai, mont, ctx)) { 181 goto err; 182 } 183 } 184 185 return 1; 186 187 err: 188 /* |A| and |Ai| may be in an inconsistent state so they both need to be 189 * replaced the next time this blinding is used. Note that this is only 190 * sufficient because support for |BN_BLINDING_NO_UPDATE| and 191 * |BN_BLINDING_NO_RECREATE| was previously dropped. */ 192 b->counter = BN_BLINDING_COUNTER - 1; 193 194 return 0; 195 } 196 197 int BN_BLINDING_convert(BIGNUM *n, BN_BLINDING *b, const BIGNUM *e, 198 const BN_MONT_CTX *mont, BN_CTX *ctx) { 199 /* |n| is not Montgomery-encoded and |b->A| is. |BN_mod_mul_montgomery| 200 * cancels one Montgomery factor, so the resulting value of |n| is unencoded. 201 */ 202 if (!bn_blinding_update(b, e, mont, ctx) || 203 !BN_mod_mul_montgomery(n, n, b->A, mont, ctx)) { 204 return 0; 205 } 206 207 return 1; 208 } 209 210 int BN_BLINDING_invert(BIGNUM *n, const BN_BLINDING *b, BN_MONT_CTX *mont, 211 BN_CTX *ctx) { 212 /* |n| is not Montgomery-encoded and |b->A| is. |BN_mod_mul_montgomery| 213 * cancels one Montgomery factor, so the resulting value of |n| is unencoded. 214 */ 215 return BN_mod_mul_montgomery(n, n, b->Ai, mont, ctx); 216 } 217 218 static int bn_blinding_create_param(BN_BLINDING *b, const BIGNUM *e, 219 const BN_MONT_CTX *mont, BN_CTX *ctx) { 220 int retry_counter = 32; 221 222 do { 223 if (!BN_rand_range_ex(b->A, 1, &mont->N)) { 224 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); 225 return 0; 226 } 227 228 /* |BN_from_montgomery| + |BN_mod_inverse_blinded| is equivalent to, but 229 * more efficient than, |BN_mod_inverse_blinded| + |BN_to_montgomery|. */ 230 if (!BN_from_montgomery(b->Ai, b->A, mont, ctx)) { 231 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); 232 return 0; 233 } 234 235 int no_inverse; 236 if (BN_mod_inverse_blinded(b->Ai, &no_inverse, b->Ai, mont, ctx)) { 237 break; 238 } 239 240 if (!no_inverse) { 241 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); 242 return 0; 243 } 244 245 /* For reasonably-sized RSA keys, it should almost never be the case that a 246 * random value doesn't have an inverse. */ 247 if (retry_counter-- == 0) { 248 OPENSSL_PUT_ERROR(RSA, RSA_R_TOO_MANY_ITERATIONS); 249 return 0; 250 } 251 ERR_clear_error(); 252 } while (1); 253 254 if (!BN_mod_exp_mont(b->A, b->A, e, &mont->N, ctx, mont)) { 255 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); 256 return 0; 257 } 258 259 if (!BN_to_montgomery(b->A, b->A, mont, ctx)) { 260 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR); 261 return 0; 262 } 263 264 return 1; 265 } 266
