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