Debian Codegraph @

external/boringssl/crypto/rsa/blinding.c

raw
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 * [email protected].
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 * ([email protected]). This product includes software written by Tim
51 * Hudson ([email protected]).
52 *
53 * Copyright (C) 1995-1998 Eric Young ([email protected])
54 * All rights reserved.
55 *
56 * This package is an SSL implementation written
57 * by Eric Young ([email protected]).
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 ([email protected]).
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 ([email protected])"
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 ([email protected])"
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
119
120 #define BN_BLINDING_COUNTER 32
121
122 struct bn_blinding_st {
123 BIGNUM *A; /* The base blinding factor, Montgomery-encoded. */
124 BIGNUM *Ai; /* The inverse of the blinding factor, Montgomery-encoded. */
125 unsigned counter;
126 };
127
128 static int bn_blinding_create_param(BN_BLINDING *b, const BIGNUM *e,
129 const BN_MONT_CTX *mont, BN_CTX *ctx);
130
131 BN_BLINDING *BN_BLINDING_new(void) {
132 BN_BLINDING *ret = OPENSSL_malloc(sizeof(BN_BLINDING));
133 if (ret == NULL) {
134 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
135 return NULL;
136 }
137 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
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
169 static int bn_blinding_update(BN_BLINDING *b, const BIGNUM *e,
170 const BN_MONT_CTX *mont, BN_CTX *ctx) {
171 if (++b->counter == BN_BLINDING_COUNTER) {
172 /* re-create blinding parameters */
173 if (!bn_blinding_create_param(b, e, mont, ctx)) {
174 goto err;
175 }
176 b->counter = 0;
177 } else {
178 if (!BN_mod_mul_montgomery(b->A, b->A, b->A, mont, ctx) ||
179 !BN_mod_mul_montgomery(b->Ai, b->Ai, b->Ai, mont, ctx)) {
180 goto err;
181 }
182 }
183
184 return 1;
185
186 err:
187 /* |A| and |Ai| may be in an inconsistent state so they both need to be
188 * replaced the next time this blinding is used. Note that this is only
189 * sufficient because support for |BN_BLINDING_NO_UPDATE| and
190 * |BN_BLINDING_NO_RECREATE| was previously dropped. */
191 b->counter = BN_BLINDING_COUNTER - 1;
192
193 return 0;
194 }
195
196 int BN_BLINDING_convert(BIGNUM *n, BN_BLINDING *b, const BIGNUM *e,
197 const BN_MONT_CTX *mont, BN_CTX *ctx) {
198 /* |n| is not Montgomery-encoded and |b->A| is. |BN_mod_mul_montgomery|
199 * cancels one Montgomery factor, so the resulting value of |n| is unencoded.
200 */
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
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 */
214 return BN_mod_mul_montgomery(n, n, b->Ai, mont, ctx);
215 }
216
217 static int bn_blinding_create_param(BN_BLINDING *b, const BIGNUM *e,
218 const BN_MONT_CTX *mont, BN_CTX *ctx) {
219 BIGNUM mont_N_consttime;
220 BN_init(&mont_N_consttime);
221 BN_with_flags(&mont_N_consttime, &mont->N, BN_FLG_CONSTTIME);
222 int retry_counter = 32;
223
224 do {
225 if (!BN_rand_range(b->A, &mont->N)) {
226 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
227 return 0;
228 }
229
230 /* |BN_from_montgomery| + |BN_mod_inverse_no_branch| is equivalent to, but
231 * more efficient than, |BN_mod_inverse_no_branch| + |BN_to_montgomery|. */
232 if (!BN_from_montgomery(b->Ai, b->A, mont, ctx)) {
233 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
234 return 0;
235 }
236
237 int no_inverse;
238 if (BN_mod_inverse_ex(b->Ai, &no_inverse, b->Ai, &mont_N_consttime, ctx) ==
239 NULL) {
240 /* this should almost never happen for good RSA keys */
241 if (no_inverse) {
242 if (retry_counter-- == 0) {
243 OPENSSL_PUT_ERROR(RSA, RSA_R_TOO_MANY_ITERATIONS);
244 return 0;
245 }
246 ERR_clear_error();
247 } else {
248 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
249 return 0;
250 }
251 } else {
252 break;
253 }
254 } while (1);
255
256 if (!BN_mod_exp_mont(b->A, b->A, e, &mont->N, ctx, mont)) {
257 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
258 return 0;
259 }
260
261 if (!BN_to_montgomery(b->A, b->A, mont, ctx)) {
262 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
263 return 0;
264 }
265
266 return 1;
267 }