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 * [email protected].
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 * ([email protected]). This product includes software written by Tim
51 * Hudson ([email protected]).
52 *
53 * Copyright (C) 1995-1998 Eric Young ([email protected])
54 * All rights reserved.
55 *
56 * This package is an SSL implementation written
57 * by Eric Young ([email protected]).
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 ([email protected]).
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 ([email protected])"
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 ([email protected])"
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
BN_BLINDING_new(void)132 BN_BLINDING *BN_BLINDING_new(void) {
133 BN_BLINDING *ret = OPENSSL_zalloc(sizeof(BN_BLINDING));
134 if (ret == NULL) {
135 return NULL;
136 }
137
138 ret->A = BN_new();
139 if (ret->A == NULL) {
140 goto err;
141 }
142
143 ret->Ai = BN_new();
144 if (ret->Ai == NULL) {
145 goto err;
146 }
147
148 // The blinding values need to be created before this blinding can be used.
149 ret->counter = BN_BLINDING_COUNTER - 1;
150
151 return ret;
152
153 err:
154 BN_BLINDING_free(ret);
155 return NULL;
156 }
157
BN_BLINDING_free(BN_BLINDING * r)158 void BN_BLINDING_free(BN_BLINDING *r) {
159 if (r == NULL) {
160 return;
161 }
162
163 BN_free(r->A);
164 BN_free(r->Ai);
165 OPENSSL_free(r);
166 }
167
BN_BLINDING_invalidate(BN_BLINDING * b)168 void BN_BLINDING_invalidate(BN_BLINDING *b) {
169 b->counter = BN_BLINDING_COUNTER - 1;
170 }
171
bn_blinding_update(BN_BLINDING * b,const BIGNUM * e,const BN_MONT_CTX * mont,BN_CTX * ctx)172 static int bn_blinding_update(BN_BLINDING *b, const BIGNUM *e,
173 const BN_MONT_CTX *mont, BN_CTX *ctx) {
174 if (++b->counter == BN_BLINDING_COUNTER) {
175 // re-create blinding parameters
176 if (!bn_blinding_create_param(b, e, mont, ctx)) {
177 goto err;
178 }
179 b->counter = 0;
180 } else {
181 if (!BN_mod_mul_montgomery(b->A, b->A, b->A, mont, ctx) ||
182 !BN_mod_mul_montgomery(b->Ai, b->Ai, b->Ai, mont, ctx)) {
183 goto err;
184 }
185 }
186
187 return 1;
188
189 err:
190 // |A| and |Ai| may be in an inconsistent state so they both need to be
191 // replaced the next time this blinding is used. Note that this is only
192 // sufficient because support for |BN_BLINDING_NO_UPDATE| and
193 // |BN_BLINDING_NO_RECREATE| was previously dropped.
194 b->counter = BN_BLINDING_COUNTER - 1;
195
196 return 0;
197 }
198
BN_BLINDING_convert(BIGNUM * n,BN_BLINDING * b,const BIGNUM * e,const BN_MONT_CTX * mont,BN_CTX * ctx)199 int BN_BLINDING_convert(BIGNUM *n, BN_BLINDING *b, const BIGNUM *e,
200 const BN_MONT_CTX *mont, BN_CTX *ctx) {
201 // |n| is not Montgomery-encoded and |b->A| is. |BN_mod_mul_montgomery|
202 // cancels one Montgomery factor, so the resulting value of |n| is unencoded.
203 if (!bn_blinding_update(b, e, mont, ctx) ||
204 !BN_mod_mul_montgomery(n, n, b->A, mont, ctx)) {
205 return 0;
206 }
207
208 return 1;
209 }
210
BN_BLINDING_invert(BIGNUM * n,const BN_BLINDING * b,BN_MONT_CTX * mont,BN_CTX * ctx)211 int BN_BLINDING_invert(BIGNUM *n, const BN_BLINDING *b, BN_MONT_CTX *mont,
212 BN_CTX *ctx) {
213 // |n| is not Montgomery-encoded and |b->A| is. |BN_mod_mul_montgomery|
214 // cancels one Montgomery factor, so the resulting value of |n| is unencoded.
215 return BN_mod_mul_montgomery(n, n, b->Ai, mont, ctx);
216 }
217
bn_blinding_create_param(BN_BLINDING * b,const BIGNUM * e,const BN_MONT_CTX * mont,BN_CTX * ctx)218 static int bn_blinding_create_param(BN_BLINDING *b, const BIGNUM *e,
219 const BN_MONT_CTX *mont, BN_CTX *ctx) {
220 int no_inverse;
221 if (!BN_rand_range_ex(b->A, 1, &mont->N) ||
222 // Compute |b->A|^-1 in Montgomery form. Note |BN_from_montgomery| +
223 // |BN_mod_inverse_blinded| is equivalent to, but more efficient than,
224 // |BN_mod_inverse_blinded| + |BN_to_montgomery|.
225 //
226 // We do not retry if |b->A| has no inverse. Finding a non-invertible
227 // value of |b->A| is equivalent to factoring |mont->N|. There is
228 // negligible probability of stumbling on one at random.
229 !BN_from_montgomery(b->Ai, b->A, mont, ctx) ||
230 !BN_mod_inverse_blinded(b->Ai, &no_inverse, b->Ai, mont, ctx) ||
231 // TODO(davidben): |BN_mod_exp_mont| internally computes the result in
232 // Montgomery form. Save a pair of Montgomery reductions and a
233 // multiplication by returning that value directly.
234 !BN_mod_exp_mont(b->A, b->A, e, &mont->N, ctx, mont) ||
235 !BN_to_montgomery(b->A, b->A, mont, ctx)) {
236 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
237 return 0;
238 }
239
240 return 1;
241 }
242