src/third_party/boringssl/src/crypto/rsa/blinding.c

   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@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@cryptsoft.com).  This product includes software written by Tim
  51  * Hudson (tjh@cryptsoft.com).
  52  *
  53  * Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  54  * All rights reserved.
  55  *
  56  * This package is an SSL implementation written
  57  * by Eric Young (eay@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@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@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@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 }