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