155714Skris/* crypto/bn/bn_blind.c */ 2160814Ssimon/* ==================================================================== 3340704Sjkim * Copyright (c) 1998-2018 The OpenSSL Project. All rights reserved. 4160814Ssimon * 5160814Ssimon * Redistribution and use in source and binary forms, with or without 6160814Ssimon * modification, are permitted provided that the following conditions 7160814Ssimon * are met: 8160814Ssimon * 9160814Ssimon * 1. Redistributions of source code must retain the above copyright 10280297Sjkim * notice, this list of conditions and the following disclaimer. 11160814Ssimon * 12160814Ssimon * 2. Redistributions in binary form must reproduce the above copyright 13160814Ssimon * notice, this list of conditions and the following disclaimer in 14160814Ssimon * the documentation and/or other materials provided with the 15160814Ssimon * distribution. 16160814Ssimon * 17160814Ssimon * 3. All advertising materials mentioning features or use of this 18160814Ssimon * software must display the following acknowledgment: 19160814Ssimon * "This product includes software developed by the OpenSSL Project 20160814Ssimon * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 21160814Ssimon * 22160814Ssimon * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 23160814Ssimon * endorse or promote products derived from this software without 24160814Ssimon * prior written permission. For written permission, please contact 25160814Ssimon * openssl-core@openssl.org. 26160814Ssimon * 27160814Ssimon * 5. Products derived from this software may not be called "OpenSSL" 28160814Ssimon * nor may "OpenSSL" appear in their names without prior written 29160814Ssimon * permission of the OpenSSL Project. 30160814Ssimon * 31160814Ssimon * 6. Redistributions of any form whatsoever must retain the following 32160814Ssimon * acknowledgment: 33160814Ssimon * "This product includes software developed by the OpenSSL Project 34160814Ssimon * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 35160814Ssimon * 36160814Ssimon * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 37160814Ssimon * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 38160814Ssimon * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 39160814Ssimon * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 40160814Ssimon * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 41160814Ssimon * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 42160814Ssimon * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 43160814Ssimon * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 44160814Ssimon * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 45160814Ssimon * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 46160814Ssimon * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 47160814Ssimon * OF THE POSSIBILITY OF SUCH DAMAGE. 48160814Ssimon * ==================================================================== 49160814Ssimon * 50160814Ssimon * This product includes cryptographic software written by Eric Young 51160814Ssimon * (eay@cryptsoft.com). This product includes software written by Tim 52160814Ssimon * Hudson (tjh@cryptsoft.com). 53160814Ssimon * 54160814Ssimon */ 5555714Skris/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 5655714Skris * All rights reserved. 5755714Skris * 5855714Skris * This package is an SSL implementation written 5955714Skris * by Eric Young (eay@cryptsoft.com). 6055714Skris * The implementation was written so as to conform with Netscapes SSL. 61280297Sjkim * 6255714Skris * This library is free for commercial and non-commercial use as long as 6355714Skris * the following conditions are aheared to. The following conditions 6455714Skris * apply to all code found in this distribution, be it the RC4, RSA, 6555714Skris * lhash, DES, etc., code; not just the SSL code. The SSL documentation 6655714Skris * included with this distribution is covered by the same copyright terms 6755714Skris * except that the holder is Tim Hudson (tjh@cryptsoft.com). 68280297Sjkim * 6955714Skris * Copyright remains Eric Young's, and as such any Copyright notices in 7055714Skris * the code are not to be removed. 7155714Skris * If this package is used in a product, Eric Young should be given attribution 7255714Skris * as the author of the parts of the library used. 7355714Skris * This can be in the form of a textual message at program startup or 7455714Skris * in documentation (online or textual) provided with the package. 75280297Sjkim * 7655714Skris * Redistribution and use in source and binary forms, with or without 7755714Skris * modification, are permitted provided that the following conditions 7855714Skris * are met: 7955714Skris * 1. Redistributions of source code must retain the copyright 8055714Skris * notice, this list of conditions and the following disclaimer. 8155714Skris * 2. Redistributions in binary form must reproduce the above copyright 8255714Skris * notice, this list of conditions and the following disclaimer in the 8355714Skris * documentation and/or other materials provided with the distribution. 8455714Skris * 3. All advertising materials mentioning features or use of this software 8555714Skris * must display the following acknowledgement: 8655714Skris * "This product includes cryptographic software written by 8755714Skris * Eric Young (eay@cryptsoft.com)" 8855714Skris * The word 'cryptographic' can be left out if the rouines from the library 8955714Skris * being used are not cryptographic related :-). 90280297Sjkim * 4. If you include any Windows specific code (or a derivative thereof) from 9155714Skris * the apps directory (application code) you must include an acknowledgement: 9255714Skris * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 93280297Sjkim * 9455714Skris * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 9555714Skris * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 9655714Skris * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 9755714Skris * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 9855714Skris * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 9955714Skris * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 10055714Skris * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 10155714Skris * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 10255714Skris * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 10355714Skris * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 10455714Skris * SUCH DAMAGE. 105280297Sjkim * 10655714Skris * The licence and distribution terms for any publically available version or 10755714Skris * derivative of this code cannot be changed. i.e. this code cannot simply be 10855714Skris * copied and put under another distribution licence 10955714Skris * [including the GNU Public Licence.] 11055714Skris */ 11155714Skris 11255714Skris#include <stdio.h> 11355714Skris#include "cryptlib.h" 11455714Skris#include "bn_lcl.h" 11555714Skris 116280297Sjkim#define BN_BLINDING_COUNTER 32 117160814Ssimon 118280297Sjkimstruct bn_blinding_st { 119280297Sjkim BIGNUM *A; 120280297Sjkim BIGNUM *Ai; 121280297Sjkim BIGNUM *e; 122280297Sjkim BIGNUM *mod; /* just a reference */ 123238405Sjkim#ifndef OPENSSL_NO_DEPRECATED 124280297Sjkim unsigned long thread_id; /* added in OpenSSL 0.9.6j and 0.9.7b; used 125280297Sjkim * only by crypto/rsa/rsa_eay.c, rsa_lib.c */ 126238405Sjkim#endif 127280297Sjkim CRYPTO_THREADID tid; 128280297Sjkim int counter; 129280297Sjkim unsigned long flags; 130280297Sjkim BN_MONT_CTX *m_ctx; 131280297Sjkim int (*bn_mod_exp) (BIGNUM *r, const BIGNUM *a, const BIGNUM *p, 132280297Sjkim const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx); 133280297Sjkim}; 134160814Ssimon 135238405SjkimBN_BLINDING *BN_BLINDING_new(const BIGNUM *A, const BIGNUM *Ai, BIGNUM *mod) 136280297Sjkim{ 137280297Sjkim BN_BLINDING *ret = NULL; 13855714Skris 139280297Sjkim bn_check_top(mod); 14055714Skris 141280297Sjkim if ((ret = (BN_BLINDING *)OPENSSL_malloc(sizeof(BN_BLINDING))) == NULL) { 142280297Sjkim BNerr(BN_F_BN_BLINDING_NEW, ERR_R_MALLOC_FAILURE); 143280297Sjkim return (NULL); 144280297Sjkim } 145280297Sjkim memset(ret, 0, sizeof(BN_BLINDING)); 146280297Sjkim if (A != NULL) { 147280297Sjkim if ((ret->A = BN_dup(A)) == NULL) 148280297Sjkim goto err; 149280297Sjkim } 150280297Sjkim if (Ai != NULL) { 151280297Sjkim if ((ret->Ai = BN_dup(Ai)) == NULL) 152280297Sjkim goto err; 153280297Sjkim } 154194206Ssimon 155280297Sjkim /* save a copy of mod in the BN_BLINDING structure */ 156280297Sjkim if ((ret->mod = BN_dup(mod)) == NULL) 157280297Sjkim goto err; 158280297Sjkim if (BN_get_flags(mod, BN_FLG_CONSTTIME) != 0) 159280297Sjkim BN_set_flags(ret->mod, BN_FLG_CONSTTIME); 160194206Ssimon 161280297Sjkim /* 162280297Sjkim * Set the counter to the special value -1 to indicate that this is 163280297Sjkim * never-used fresh blinding that does not need updating before first 164280297Sjkim * use. 165280297Sjkim */ 166280297Sjkim ret->counter = -1; 167280297Sjkim CRYPTO_THREADID_current(&ret->tid); 168280297Sjkim return (ret); 169280297Sjkim err: 170280297Sjkim if (ret != NULL) 171280297Sjkim BN_BLINDING_free(ret); 172280297Sjkim return (NULL); 173280297Sjkim} 17455714Skris 17555714Skrisvoid BN_BLINDING_free(BN_BLINDING *r) 176280297Sjkim{ 177280297Sjkim if (r == NULL) 178280297Sjkim return; 17955714Skris 180280297Sjkim if (r->A != NULL) 181280297Sjkim BN_free(r->A); 182280297Sjkim if (r->Ai != NULL) 183280297Sjkim BN_free(r->Ai); 184280297Sjkim if (r->e != NULL) 185280297Sjkim BN_free(r->e); 186280297Sjkim if (r->mod != NULL) 187280297Sjkim BN_free(r->mod); 188280297Sjkim OPENSSL_free(r); 189280297Sjkim} 19055714Skris 19155714Skrisint BN_BLINDING_update(BN_BLINDING *b, BN_CTX *ctx) 192280297Sjkim{ 193280297Sjkim int ret = 0; 19455714Skris 195280297Sjkim if ((b->A == NULL) || (b->Ai == NULL)) { 196280297Sjkim BNerr(BN_F_BN_BLINDING_UPDATE, BN_R_NOT_INITIALIZED); 197280297Sjkim goto err; 198280297Sjkim } 19955714Skris 200280297Sjkim if (b->counter == -1) 201280297Sjkim b->counter = 0; 202237657Sjkim 203280297Sjkim if (++b->counter == BN_BLINDING_COUNTER && b->e != NULL && 204280297Sjkim !(b->flags & BN_BLINDING_NO_RECREATE)) { 205280297Sjkim /* re-create blinding parameters */ 206280297Sjkim if (!BN_BLINDING_create_param(b, NULL, NULL, ctx, NULL, NULL)) 207280297Sjkim goto err; 208280297Sjkim } else if (!(b->flags & BN_BLINDING_NO_UPDATE)) { 209340704Sjkim if (b->m_ctx != NULL) { 210340704Sjkim if (!bn_mul_mont_fixed_top(b->Ai, b->Ai, b->Ai, b->m_ctx, ctx) 211340704Sjkim || !bn_mul_mont_fixed_top(b->A, b->A, b->A, b->m_ctx, ctx)) 212340704Sjkim goto err; 213340704Sjkim } else { 214340704Sjkim if (!BN_mod_mul(b->Ai, b->Ai, b->Ai, b->mod, ctx) 215340704Sjkim || !BN_mod_mul(b->A, b->A, b->A, b->mod, ctx)) 216340704Sjkim goto err; 217340704Sjkim } 218280297Sjkim } 219160814Ssimon 220280297Sjkim ret = 1; 221280297Sjkim err: 222280297Sjkim if (b->counter == BN_BLINDING_COUNTER) 223280297Sjkim b->counter = 0; 224280297Sjkim return (ret); 225280297Sjkim} 22655714Skris 22755714Skrisint BN_BLINDING_convert(BIGNUM *n, BN_BLINDING *b, BN_CTX *ctx) 228280297Sjkim{ 229280297Sjkim return BN_BLINDING_convert_ex(n, NULL, b, ctx); 230280297Sjkim} 231160814Ssimon 232160814Ssimonint BN_BLINDING_convert_ex(BIGNUM *n, BIGNUM *r, BN_BLINDING *b, BN_CTX *ctx) 233280297Sjkim{ 234280297Sjkim int ret = 1; 235160814Ssimon 236280297Sjkim bn_check_top(n); 23755714Skris 238280297Sjkim if ((b->A == NULL) || (b->Ai == NULL)) { 239280297Sjkim BNerr(BN_F_BN_BLINDING_CONVERT_EX, BN_R_NOT_INITIALIZED); 240280297Sjkim return (0); 241280297Sjkim } 242160814Ssimon 243280297Sjkim if (b->counter == -1) 244280297Sjkim /* Fresh blinding, doesn't need updating. */ 245280297Sjkim b->counter = 0; 246280297Sjkim else if (!BN_BLINDING_update(b, ctx)) 247280297Sjkim return (0); 248237657Sjkim 249340704Sjkim if (r != NULL && (BN_copy(r, b->Ai) == NULL)) 250340704Sjkim return 0; 251160814Ssimon 252340704Sjkim if (b->m_ctx != NULL) 253340704Sjkim ret = BN_mod_mul_montgomery(n, n, b->A, b->m_ctx, ctx); 254340704Sjkim else 255340704Sjkim ret = BN_mod_mul(n, n, b->A, b->mod, ctx); 25655714Skris 257280297Sjkim return ret; 258280297Sjkim} 259280297Sjkim 26055714Skrisint BN_BLINDING_invert(BIGNUM *n, BN_BLINDING *b, BN_CTX *ctx) 261280297Sjkim{ 262280297Sjkim return BN_BLINDING_invert_ex(n, NULL, b, ctx); 263280297Sjkim} 264160814Ssimon 265280297Sjkimint BN_BLINDING_invert_ex(BIGNUM *n, const BIGNUM *r, BN_BLINDING *b, 266280297Sjkim BN_CTX *ctx) 267280297Sjkim{ 268280297Sjkim int ret; 26955714Skris 270280297Sjkim bn_check_top(n); 271160814Ssimon 272340704Sjkim if (r == NULL && (r = b->Ai) == NULL) { 273340704Sjkim BNerr(BN_F_BN_BLINDING_INVERT_EX, BN_R_NOT_INITIALIZED); 274340704Sjkim return 0; 275340704Sjkim } 276340704Sjkim 277340704Sjkim if (b->m_ctx != NULL) { 278340704Sjkim /* ensure that BN_mod_mul_montgomery takes pre-defined path */ 279340704Sjkim if (n->dmax >= r->top) { 280340704Sjkim size_t i, rtop = r->top, ntop = n->top; 281340704Sjkim BN_ULONG mask; 282340704Sjkim 283340704Sjkim for (i = 0; i < rtop; i++) { 284340704Sjkim mask = (BN_ULONG)0 - ((i - ntop) >> (8 * sizeof(i) - 1)); 285340704Sjkim n->d[i] &= mask; 286340704Sjkim } 287340704Sjkim mask = (BN_ULONG)0 - ((rtop - ntop) >> (8 * sizeof(ntop) - 1)); 288340704Sjkim /* always true, if (rtop >= ntop) n->top = r->top; */ 289340704Sjkim n->top = (int)(rtop & ~mask) | (ntop & mask); 290340704Sjkim n->flags |= (BN_FLG_FIXED_TOP & ~mask); 291340704Sjkim } 292340704Sjkim ret = BN_mod_mul_montgomery(n, n, r, b->m_ctx, ctx); 293340704Sjkim } else { 294280297Sjkim ret = BN_mod_mul(n, n, r, b->mod, ctx); 295280297Sjkim } 296237657Sjkim 297280297Sjkim bn_check_top(n); 298280297Sjkim return (ret); 299280297Sjkim} 30055714Skris 301238405Sjkim#ifndef OPENSSL_NO_DEPRECATED 302160814Ssimonunsigned long BN_BLINDING_get_thread_id(const BN_BLINDING *b) 303280297Sjkim{ 304280297Sjkim return b->thread_id; 305280297Sjkim} 306160814Ssimon 307160814Ssimonvoid BN_BLINDING_set_thread_id(BN_BLINDING *b, unsigned long n) 308280297Sjkim{ 309280297Sjkim b->thread_id = n; 310280297Sjkim} 311238405Sjkim#endif 312160814Ssimon 313238405SjkimCRYPTO_THREADID *BN_BLINDING_thread_id(BN_BLINDING *b) 314280297Sjkim{ 315280297Sjkim return &b->tid; 316280297Sjkim} 317238405Sjkim 318160814Ssimonunsigned long BN_BLINDING_get_flags(const BN_BLINDING *b) 319280297Sjkim{ 320280297Sjkim return b->flags; 321280297Sjkim} 322160814Ssimon 323160814Ssimonvoid BN_BLINDING_set_flags(BN_BLINDING *b, unsigned long flags) 324280297Sjkim{ 325280297Sjkim b->flags = flags; 326280297Sjkim} 327160814Ssimon 328160814SsimonBN_BLINDING *BN_BLINDING_create_param(BN_BLINDING *b, 329280297Sjkim const BIGNUM *e, BIGNUM *m, BN_CTX *ctx, 330280297Sjkim int (*bn_mod_exp) (BIGNUM *r, 331280297Sjkim const BIGNUM *a, 332280297Sjkim const BIGNUM *p, 333280297Sjkim const BIGNUM *m, 334280297Sjkim BN_CTX *ctx, 335280297Sjkim BN_MONT_CTX *m_ctx), 336280297Sjkim BN_MONT_CTX *m_ctx) 337160814Ssimon{ 338280297Sjkim int retry_counter = 32; 339280297Sjkim BN_BLINDING *ret = NULL; 340160814Ssimon 341280297Sjkim if (b == NULL) 342280297Sjkim ret = BN_BLINDING_new(NULL, NULL, m); 343280297Sjkim else 344280297Sjkim ret = b; 345160814Ssimon 346280297Sjkim if (ret == NULL) 347280297Sjkim goto err; 348160814Ssimon 349280297Sjkim if (ret->A == NULL && (ret->A = BN_new()) == NULL) 350280297Sjkim goto err; 351280297Sjkim if (ret->Ai == NULL && (ret->Ai = BN_new()) == NULL) 352280297Sjkim goto err; 353160814Ssimon 354280297Sjkim if (e != NULL) { 355280297Sjkim if (ret->e != NULL) 356280297Sjkim BN_free(ret->e); 357280297Sjkim ret->e = BN_dup(e); 358280297Sjkim } 359280297Sjkim if (ret->e == NULL) 360280297Sjkim goto err; 361160814Ssimon 362280297Sjkim if (bn_mod_exp != NULL) 363280297Sjkim ret->bn_mod_exp = bn_mod_exp; 364280297Sjkim if (m_ctx != NULL) 365280297Sjkim ret->m_ctx = m_ctx; 366160814Ssimon 367280297Sjkim do { 368280297Sjkim if (!BN_rand_range(ret->A, ret->mod)) 369280297Sjkim goto err; 370280297Sjkim if (BN_mod_inverse(ret->Ai, ret->A, ret->mod, ctx) == NULL) { 371280297Sjkim /* 372280297Sjkim * this should almost never happen for good RSA keys 373280297Sjkim */ 374280297Sjkim unsigned long error = ERR_peek_last_error(); 375280297Sjkim if (ERR_GET_REASON(error) == BN_R_NO_INVERSE) { 376280297Sjkim if (retry_counter-- == 0) { 377280297Sjkim BNerr(BN_F_BN_BLINDING_CREATE_PARAM, 378280297Sjkim BN_R_TOO_MANY_ITERATIONS); 379280297Sjkim goto err; 380280297Sjkim } 381280297Sjkim ERR_clear_error(); 382280297Sjkim } else 383280297Sjkim goto err; 384280297Sjkim } else 385280297Sjkim break; 386280297Sjkim } while (1); 387160814Ssimon 388280297Sjkim if (ret->bn_mod_exp != NULL && ret->m_ctx != NULL) { 389340704Sjkim if (!ret->bn_mod_exp(ret->A, ret->A, ret->e, ret->mod, ctx, ret->m_ctx)) 390280297Sjkim goto err; 391280297Sjkim } else { 392280297Sjkim if (!BN_mod_exp(ret->A, ret->A, ret->e, ret->mod, ctx)) 393280297Sjkim goto err; 394280297Sjkim } 395160814Ssimon 396340704Sjkim if (ret->m_ctx != NULL) { 397340704Sjkim if (!bn_to_mont_fixed_top(ret->Ai, ret->Ai, ret->m_ctx, ctx) 398340704Sjkim || !bn_to_mont_fixed_top(ret->A, ret->A, ret->m_ctx, ctx)) 399340704Sjkim goto err; 400340704Sjkim } 401340704Sjkim 402280297Sjkim return ret; 403280297Sjkim err: 404280297Sjkim if (b == NULL && ret != NULL) { 405280297Sjkim BN_BLINDING_free(ret); 406280297Sjkim ret = NULL; 407280297Sjkim } 408160814Ssimon 409280297Sjkim return ret; 410160814Ssimon} 411