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 <openssl/bn.h> 112 #include <openssl/mem.h> 113 #include <openssl/err.h> 114 115 #include "internal.h" 116 117 #define BN_BLINDING_COUNTER 32 118 119 struct bn_blinding_st { 120 BIGNUM *A; 121 BIGNUM *Ai; 122 BIGNUM *e; 123 BIGNUM *mod; /* just a reference */ 124 CRYPTO_THREADID tid; 125 int counter; 126 unsigned long flags; 127 BN_MONT_CTX *m_ctx; 128 int (*bn_mod_exp)(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, 129 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx); 130 }; 131 132 BN_BLINDING *BN_BLINDING_new(const BIGNUM *A, const BIGNUM *Ai, BIGNUM *mod) { 133 BN_BLINDING *ret = NULL; 134 135 ret = (BN_BLINDING*) OPENSSL_malloc(sizeof(BN_BLINDING)); 136 if (ret == NULL) { 137 OPENSSL_PUT_ERROR(RSA, BN_BLINDING_new, ERR_R_MALLOC_FAILURE); 138 return NULL; 139 } 140 memset(ret, 0, sizeof(BN_BLINDING)); 141 if (A != NULL) { 142 ret->A = BN_dup(A); 143 if (ret->A == NULL) { 144 goto err; 145 } 146 } 147 if (Ai != NULL) { 148 ret->Ai = BN_dup(Ai); 149 if (ret->Ai == NULL) { 150 goto err; 151 } 152 } 153 154 /* save a copy of mod in the BN_BLINDING structure */ 155 ret->mod = BN_dup(mod); 156 if (ret->mod == NULL) { 157 goto err; 158 } 159 if (BN_get_flags(mod, BN_FLG_CONSTTIME) != 0) { 160 BN_set_flags(ret->mod, BN_FLG_CONSTTIME); 161 } 162 163 /* Set the counter to the special value -1 164 * to indicate that this is never-used fresh blinding 165 * that does not need updating before first use. */ 166 ret->counter = -1; 167 CRYPTO_THREADID_current(&ret->tid); 168 return ret; 169 170 err: 171 if (ret != NULL) { 172 BN_BLINDING_free(ret); 173 } 174 return NULL; 175 } 176 177 void BN_BLINDING_free(BN_BLINDING *r) { 178 if (r == NULL) { 179 return; 180 } 181 182 if (r->A != NULL) 183 BN_free(r->A); 184 if (r->Ai != NULL) 185 BN_free(r->Ai); 186 if (r->e != NULL) 187 BN_free(r->e); 188 if (r->mod != NULL) 189 BN_free(r->mod); 190 OPENSSL_free(r); 191 } 192 193 int BN_BLINDING_update(BN_BLINDING *b, BN_CTX *ctx) { 194 int ret = 0; 195 196 if (b->A == NULL || b->Ai == NULL) { 197 OPENSSL_PUT_ERROR(RSA, BN_BLINDING_update, RSA_R_BN_NOT_INITIALIZED); 198 goto err; 199 } 200 201 if (b->counter == -1) { 202 b->counter = 0; 203 } 204 205 if (++b->counter == BN_BLINDING_COUNTER && b->e != NULL && 206 !(b->flags & BN_BLINDING_NO_RECREATE)) { 207 /* re-create blinding parameters */ 208 if (!BN_BLINDING_create_param(b, NULL, NULL, ctx, NULL, NULL)) { 209 goto err; 210 } 211 } else if (!(b->flags & BN_BLINDING_NO_UPDATE)) { 212 if (!BN_mod_mul(b->A, b->A, b->A, b->mod, ctx)) { 213 goto err; 214 } 215 if (!BN_mod_mul(b->Ai, b->Ai, b->Ai, b->mod, ctx)) { 216 goto err; 217 } 218 } 219 220 ret = 1; 221 222 err: 223 if (b->counter == BN_BLINDING_COUNTER) { 224 b->counter = 0; 225 } 226 return ret; 227 } 228 229 int BN_BLINDING_convert(BIGNUM *n, BN_BLINDING *b, BN_CTX *ctx) { 230 return BN_BLINDING_convert_ex(n, NULL, b, ctx); 231 } 232 233 int BN_BLINDING_convert_ex(BIGNUM *n, BIGNUM *r, BN_BLINDING *b, BN_CTX *ctx) { 234 int ret = 1; 235 236 if (b->A == NULL || b->Ai == NULL) { 237 OPENSSL_PUT_ERROR(RSA, BN_BLINDING_convert_ex, RSA_R_BN_NOT_INITIALIZED); 238 return 0; 239 } 240 241 if (b->counter == -1) { 242 /* Fresh blinding, doesn't need updating. */ 243 b->counter = 0; 244 } else if (!BN_BLINDING_update(b, ctx)) { 245 return 0; 246 } 247 248 if (r != NULL) { 249 if (!BN_copy(r, b->Ai)) { 250 ret = 0; 251 } 252 } 253 254 if (!BN_mod_mul(n, n, b->A, b->mod, ctx)) { 255 ret = 0; 256 } 257 258 return ret; 259 } 260 261 int BN_BLINDING_invert(BIGNUM *n, BN_BLINDING *b, BN_CTX *ctx) { 262 return BN_BLINDING_invert_ex(n, NULL, b, ctx); 263 } 264 265 int BN_BLINDING_invert_ex(BIGNUM *n, const BIGNUM *r, BN_BLINDING *b, 266 BN_CTX *ctx) { 267 int ret; 268 269 if (r != NULL) { 270 ret = BN_mod_mul(n, n, r, b->mod, ctx); 271 } else { 272 if (b->Ai == NULL) { 273 OPENSSL_PUT_ERROR(RSA, BN_BLINDING_invert_ex, RSA_R_BN_NOT_INITIALIZED); 274 return 0; 275 } 276 ret = BN_mod_mul(n, n, b->Ai, b->mod, ctx); 277 } 278 279 return ret; 280 } 281 282 CRYPTO_THREADID *BN_BLINDING_thread_id(BN_BLINDING *b) { return &b->tid; } 283 284 unsigned long BN_BLINDING_get_flags(const BN_BLINDING *b) { return b->flags; } 285 286 void BN_BLINDING_set_flags(BN_BLINDING *b, unsigned long flags) { 287 b->flags = flags; 288 } 289 290 BN_BLINDING *BN_BLINDING_create_param( 291 BN_BLINDING *b, const BIGNUM *e, BIGNUM *m, BN_CTX *ctx, 292 int (*bn_mod_exp)(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, 293 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx), 294 BN_MONT_CTX *m_ctx) { 295 int retry_counter = 32; 296 BN_BLINDING *ret = NULL; 297 298 if (b == NULL) { 299 ret = BN_BLINDING_new(NULL, NULL, m); 300 } else { 301 ret = b; 302 } 303 304 if (ret == NULL) { 305 goto err; 306 } 307 308 if (ret->A == NULL && (ret->A = BN_new()) == NULL) { 309 goto err; 310 } 311 if (ret->Ai == NULL && (ret->Ai = BN_new()) == NULL) { 312 goto err; 313 } 314 315 if (e != NULL) { 316 if (ret->e != NULL) { 317 BN_free(ret->e); 318 } 319 ret->e = BN_dup(e); 320 } 321 if (ret->e == NULL) { 322 goto err; 323 } 324 325 if (bn_mod_exp != NULL) { 326 ret->bn_mod_exp = bn_mod_exp; 327 } 328 if (m_ctx != NULL) { 329 ret->m_ctx = m_ctx; 330 } 331 332 do { 333 if (!BN_rand_range(ret->A, ret->mod)) { 334 goto err; 335 } 336 if (BN_mod_inverse(ret->Ai, ret->A, ret->mod, ctx) == NULL) { 337 /* this should almost never happen for good RSA keys */ 338 uint32_t error = ERR_peek_last_error(); 339 if (ERR_GET_REASON(error) == BN_R_NO_INVERSE) { 340 if (retry_counter-- == 0) { 341 OPENSSL_PUT_ERROR(RSA, BN_BLINDING_create_param, 342 RSA_R_TOO_MANY_ITERATIONS); 343 goto err; 344 } 345 ERR_clear_error(); 346 } else { 347 goto err; 348 } 349 } else { 350 break; 351 } 352 } while (1); 353 354 if (ret->bn_mod_exp != NULL && ret->m_ctx != NULL) { 355 if (!ret->bn_mod_exp(ret->A, ret->A, ret->e, ret->mod, ctx, ret->m_ctx)) { 356 goto err; 357 } 358 } else { 359 if (!BN_mod_exp(ret->A, ret->A, ret->e, ret->mod, ctx)) { 360 goto err; 361 } 362 } 363 364 return ret; 365 366 err: 367 if (b == NULL && ret != NULL) { 368 BN_BLINDING_free(ret); 369 ret = NULL; 370 } 371 372 return ret; 373 } 374 375 static BIGNUM *rsa_get_public_exp(const BIGNUM *d, const BIGNUM *p, 376 const BIGNUM *q, BN_CTX *ctx) { 377 BIGNUM *ret = NULL, *r0, *r1, *r2; 378 379 if (d == NULL || p == NULL || q == NULL) { 380 return NULL; 381 } 382 383 BN_CTX_start(ctx); 384 r0 = BN_CTX_get(ctx); 385 r1 = BN_CTX_get(ctx); 386 r2 = BN_CTX_get(ctx); 387 if (r2 == NULL) { 388 goto err; 389 } 390 391 if (!BN_sub(r1, p, BN_value_one())) { 392 goto err; 393 } 394 if (!BN_sub(r2, q, BN_value_one())) { 395 goto err; 396 } 397 if (!BN_mul(r0, r1, r2, ctx)) { 398 goto err; 399 } 400 401 ret = BN_mod_inverse(NULL, d, r0, ctx); 402 403 err: 404 BN_CTX_end(ctx); 405 return ret; 406 } 407 408 BN_BLINDING *rsa_setup_blinding(RSA *rsa, BN_CTX *in_ctx) { 409 BIGNUM local_n; 410 BIGNUM *e, *n; 411 BN_CTX *ctx; 412 BN_BLINDING *ret = NULL; 413 414 if (in_ctx == NULL) { 415 ctx = BN_CTX_new(); 416 if (ctx == NULL) { 417 return 0; 418 } 419 } else { 420 ctx = in_ctx; 421 } 422 423 BN_CTX_start(ctx); 424 e = BN_CTX_get(ctx); 425 if (e == NULL) { 426 OPENSSL_PUT_ERROR(RSA, rsa_setup_blinding, ERR_R_MALLOC_FAILURE); 427 goto err; 428 } 429 430 if (rsa->e == NULL) { 431 e = rsa_get_public_exp(rsa->d, rsa->p, rsa->q, ctx); 432 if (e == NULL) { 433 OPENSSL_PUT_ERROR(RSA, rsa_setup_blinding, RSA_R_NO_PUBLIC_EXPONENT); 434 goto err; 435 } 436 } else { 437 e = rsa->e; 438 } 439 440 n = &local_n; 441 BN_with_flags(n, rsa->n, BN_FLG_CONSTTIME); 442 443 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) { 444 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, CRYPTO_LOCK_RSA, rsa->n, 445 ctx)) { 446 goto err; 447 } 448 } 449 450 ret = BN_BLINDING_create_param(NULL, e, n, ctx, rsa->meth->bn_mod_exp, 451 rsa->_method_mod_n); 452 if (ret == NULL) { 453 OPENSSL_PUT_ERROR(RSA, rsa_setup_blinding, ERR_R_BN_LIB); 454 goto err; 455 } 456 CRYPTO_THREADID_current(BN_BLINDING_thread_id(ret)); 457 458 err: 459 BN_CTX_end(ctx); 460 if (in_ctx == NULL) { 461 BN_CTX_free(ctx); 462 } 463 if (rsa->e == NULL) { 464 BN_free(e); 465 } 466 467 return ret; 468 } 469