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