1// Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#include <openssl/rsa.h>
16
17#include <string.h>
18
19#include <openssl/bn.h>
20#include <openssl/err.h>
21#include <openssl/mem.h>
22
23#include "../../internal.h"
24#include "internal.h"
25
26
27#define BN_BLINDING_COUNTER 32
28
29struct bn_blinding_st {
30  BIGNUM *A;   // The base blinding factor, Montgomery-encoded.
31  BIGNUM *Ai;  // The inverse of the blinding factor, Montgomery-encoded.
32  unsigned counter;
33};
34
35static int bn_blinding_create_param(BN_BLINDING *b, const BIGNUM *e,
36                                    const BN_MONT_CTX *mont, BN_CTX *ctx);
37
38BN_BLINDING *BN_BLINDING_new(void) {
39  BN_BLINDING *ret =
40      reinterpret_cast<BN_BLINDING *>(OPENSSL_zalloc(sizeof(BN_BLINDING)));
41  if (ret == NULL) {
42    return NULL;
43  }
44
45  ret->A = BN_new();
46  if (ret->A == NULL) {
47    goto err;
48  }
49
50  ret->Ai = BN_new();
51  if (ret->Ai == NULL) {
52    goto err;
53  }
54
55  // The blinding values need to be created before this blinding can be used.
56  ret->counter = BN_BLINDING_COUNTER - 1;
57
58  return ret;
59
60err:
61  BN_BLINDING_free(ret);
62  return NULL;
63}
64
65void BN_BLINDING_free(BN_BLINDING *r) {
66  if (r == nullptr) {
67    return;
68  }
69  BN_free(r->A);
70  BN_free(r->Ai);
71  OPENSSL_free(r);
72}
73
74void BN_BLINDING_invalidate(BN_BLINDING *b) {
75  b->counter = BN_BLINDING_COUNTER - 1;
76}
77
78static int bn_blinding_update(BN_BLINDING *b, const BIGNUM *e,
79                              const BN_MONT_CTX *mont, BN_CTX *ctx) {
80  if (++b->counter == BN_BLINDING_COUNTER) {
81    // re-create blinding parameters
82    if (!bn_blinding_create_param(b, e, mont, ctx)) {
83      goto err;
84    }
85    b->counter = 0;
86  } else {
87    if (!BN_mod_mul_montgomery(b->A, b->A, b->A, mont, ctx) ||
88        !BN_mod_mul_montgomery(b->Ai, b->Ai, b->Ai, mont, ctx)) {
89      goto err;
90    }
91  }
92
93  return 1;
94
95err:
96  // |A| and |Ai| may be in an inconsistent state so they both need to be
97  // replaced the next time this blinding is used. Note that this is only
98  // sufficient because support for |BN_BLINDING_NO_UPDATE| and
99  // |BN_BLINDING_NO_RECREATE| was previously dropped.
100  b->counter = BN_BLINDING_COUNTER - 1;
101
102  return 0;
103}
104
105int BN_BLINDING_convert(BIGNUM *n, BN_BLINDING *b, const BIGNUM *e,
106                        const BN_MONT_CTX *mont, BN_CTX *ctx) {
107  // |n| is not Montgomery-encoded and |b->A| is. |BN_mod_mul_montgomery|
108  // cancels one Montgomery factor, so the resulting value of |n| is unencoded.
109  if (!bn_blinding_update(b, e, mont, ctx) ||
110      !BN_mod_mul_montgomery(n, n, b->A, mont, ctx)) {
111    return 0;
112  }
113
114  return 1;
115}
116
117int BN_BLINDING_invert(BIGNUM *n, const BN_BLINDING *b, BN_MONT_CTX *mont,
118                       BN_CTX *ctx) {
119  // |n| is not Montgomery-encoded and |b->A| is. |BN_mod_mul_montgomery|
120  // cancels one Montgomery factor, so the resulting value of |n| is unencoded.
121  return BN_mod_mul_montgomery(n, n, b->Ai, mont, ctx);
122}
123
124static int bn_blinding_create_param(BN_BLINDING *b, const BIGNUM *e,
125                                    const BN_MONT_CTX *mont, BN_CTX *ctx) {
126  int no_inverse;
127  if (!BN_rand_range_ex(b->A, 1, &mont->N) ||
128      // Compute |b->A|^-1 in Montgomery form. Note |BN_from_montgomery| +
129      // |BN_mod_inverse_blinded| is equivalent to, but more efficient than,
130      // |BN_mod_inverse_blinded| + |BN_to_montgomery|.
131      //
132      // We do not retry if |b->A| has no inverse. Finding a non-invertible
133      // value of |b->A| is equivalent to factoring |mont->N|. There is
134      // negligible probability of stumbling on one at random.
135      !BN_from_montgomery(b->Ai, b->A, mont, ctx) ||
136      !BN_mod_inverse_blinded(b->Ai, &no_inverse, b->Ai, mont, ctx) ||
137      // TODO(davidben): |BN_mod_exp_mont| internally computes the result in
138      // Montgomery form. Save a pair of Montgomery reductions and a
139      // multiplication by returning that value directly.
140      !BN_mod_exp_mont(b->A, b->A, e, &mont->N, ctx, mont) ||
141      !BN_to_montgomery(b->A, b->A, mont, ctx)) {
142    OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
143    return 0;
144  }
145
146  return 1;
147}
148