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