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