blob: d950d502c3a2e630e736fcbe6e582417b2e1cf34 [file] [log] [blame]
Adam Langley95c29f32014-06-20 12:00:00 -07001/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
2 * All rights reserved.
3 *
4 * This package is an SSL implementation written
5 * by Eric Young (eay@cryptsoft.com).
6 * The implementation was written so as to conform with Netscapes SSL.
7 *
8 * This library is free for commercial and non-commercial use as long as
9 * the following conditions are aheared to. The following conditions
10 * apply to all code found in this distribution, be it the RC4, RSA,
11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
12 * included with this distribution is covered by the same copyright terms
13 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
14 *
15 * Copyright remains Eric Young's, and as such any Copyright notices in
16 * the code are not to be removed.
17 * If this package is used in a product, Eric Young should be given attribution
18 * as the author of the parts of the library used.
19 * This can be in the form of a textual message at program startup or
20 * in documentation (online or textual) provided with the package.
21 *
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
24 * are met:
25 * 1. Redistributions of source code must retain the copyright
26 * notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 * 3. All advertising materials mentioning features or use of this software
31 * must display the following acknowledgement:
32 * "This product includes cryptographic software written by
33 * Eric Young (eay@cryptsoft.com)"
34 * The word 'cryptographic' can be left out if the rouines from the library
35 * being used are not cryptographic related :-).
36 * 4. If you include any Windows specific code (or a derivative thereof) from
37 * the apps directory (application code) you must include an acknowledgement:
38 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
39 *
40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50 * SUCH DAMAGE.
51 *
52 * The licence and distribution terms for any publically available version or
53 * derivative of this code cannot be changed. i.e. this code cannot simply be
54 * copied and put under another distribution licence
55 * [including the GNU Public Licence.] */
56
57#include <openssl/rsa.h>
58
Adam Langley2b2d66d2015-01-30 17:08:37 -080059#include <string.h>
60
Adam Langley95c29f32014-06-20 12:00:00 -070061#include <openssl/bn.h>
62#include <openssl/err.h>
63#include <openssl/mem.h>
64
65#include "internal.h"
66
67
68#define OPENSSL_RSA_MAX_MODULUS_BITS 16384
69#define OPENSSL_RSA_SMALL_MODULUS_BITS 3072
70#define OPENSSL_RSA_MAX_PUBEXP_BITS \
71 64 /* exponent limit enforced for "large" modulus only */
72
73
74static int finish(RSA *rsa) {
75 if (rsa->_method_mod_n != NULL) {
76 BN_MONT_CTX_free(rsa->_method_mod_n);
77 }
78 if (rsa->_method_mod_p != NULL) {
79 BN_MONT_CTX_free(rsa->_method_mod_p);
80 }
81 if (rsa->_method_mod_q != NULL) {
82 BN_MONT_CTX_free(rsa->_method_mod_q);
83 }
84
85 return 1;
86}
87
David Benjamin925fee32014-07-11 14:14:08 -040088static size_t size(const RSA *rsa) {
89 return BN_num_bytes(rsa->n);
90}
91
Adam Langley95c29f32014-06-20 12:00:00 -070092static int encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
93 const uint8_t *in, size_t in_len, int padding) {
94 const unsigned rsa_size = RSA_size(rsa);
Adam Langley95c29f32014-06-20 12:00:00 -070095 BIGNUM *f, *result;
96 uint8_t *buf = NULL;
97 BN_CTX *ctx = NULL;
Adam Langley6887edb2014-06-20 12:00:00 -070098 int i, ret = 0;
Adam Langley95c29f32014-06-20 12:00:00 -070099
100 if (rsa_size > OPENSSL_RSA_MAX_MODULUS_BITS) {
101 OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_MODULUS_TOO_LARGE);
102 return 0;
103 }
104
105 if (max_out < rsa_size) {
106 OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
107 return 0;
108 }
109
110 if (BN_ucmp(rsa->n, rsa->e) <= 0) {
111 OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_BAD_E_VALUE);
112 return 0;
113 }
114
115 /* for large moduli, enforce exponent limit */
116 if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS &&
117 BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
118 OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_BAD_E_VALUE);
119 return 0;
120 }
121
122 ctx = BN_CTX_new();
123 if (ctx == NULL) {
124 goto err;
125 }
126
127 BN_CTX_start(ctx);
128 f = BN_CTX_get(ctx);
129 result = BN_CTX_get(ctx);
130 buf = OPENSSL_malloc(rsa_size);
131 if (!f || !result || !buf) {
132 OPENSSL_PUT_ERROR(RSA, encrypt, ERR_R_MALLOC_FAILURE);
133 goto err;
134 }
135
136 switch (padding) {
137 case RSA_PKCS1_PADDING:
138 i = RSA_padding_add_PKCS1_type_2(buf, rsa_size, in, in_len);
139 break;
140 case RSA_PKCS1_OAEP_PADDING:
Adam Langley6887edb2014-06-20 12:00:00 -0700141 /* Use the default parameters: SHA-1 for both hashes and no label. */
142 i = RSA_padding_add_PKCS1_OAEP_mgf1(buf, rsa_size, in, in_len,
143 NULL, 0, NULL, NULL);
Adam Langley95c29f32014-06-20 12:00:00 -0700144 break;
Adam Langley95c29f32014-06-20 12:00:00 -0700145 case RSA_NO_PADDING:
146 i = RSA_padding_add_none(buf, rsa_size, in, in_len);
147 break;
148 default:
149 OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_UNKNOWN_PADDING_TYPE);
150 goto err;
151 }
152
153 if (i <= 0) {
154 goto err;
155 }
156
157 if (BN_bin2bn(buf, rsa_size, f) == NULL) {
158 goto err;
159 }
160
161 if (BN_ucmp(f, rsa->n) >= 0) {
162 /* usually the padding functions would catch this */
163 OPENSSL_PUT_ERROR(RSA, encrypt, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
164 goto err;
165 }
166
167 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
168 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, CRYPTO_LOCK_RSA, rsa->n,
169 ctx)) {
170 goto err;
171 }
172 }
173
174 if (!rsa->meth->bn_mod_exp(result, f, rsa->e, rsa->n, ctx, rsa->_method_mod_n)) {
175 goto err;
176 }
177
178 /* put in leading 0 bytes if the number is less than the length of the
179 * modulus */
Adam Langley6887edb2014-06-20 12:00:00 -0700180 if (!BN_bn2bin_padded(out, rsa_size, result)) {
181 OPENSSL_PUT_ERROR(RSA, encrypt, ERR_R_INTERNAL_ERROR);
182 goto err;
Adam Langley95c29f32014-06-20 12:00:00 -0700183 }
184
185 *out_len = rsa_size;
186 ret = 1;
187
188err:
189 if (ctx != NULL) {
190 BN_CTX_end(ctx);
191 BN_CTX_free(ctx);
192 }
193 if (buf != NULL) {
194 OPENSSL_cleanse(buf, rsa_size);
195 OPENSSL_free(buf);
196 }
197
198 return ret;
199}
200
201/* MAX_BLINDINGS_PER_RSA defines the maximum number of cached BN_BLINDINGs per
202 * RSA*. Then this limit is exceeded, BN_BLINDING objects will be created and
203 * destroyed as needed. */
204#define MAX_BLINDINGS_PER_RSA 1024
205
206/* rsa_blinding_get returns a BN_BLINDING to use with |rsa|. It does this by
207 * allocating one of the cached BN_BLINDING objects in |rsa->blindings|. If
208 * none are free, the cache will be extended by a extra element and the new
209 * BN_BLINDING is returned.
210 *
211 * On success, the index of the assigned BN_BLINDING is written to
212 * |*index_used| and must be passed to |rsa_blinding_release| when finished. */
213static BN_BLINDING *rsa_blinding_get(RSA *rsa, unsigned *index_used,
214 BN_CTX *ctx) {
215 BN_BLINDING *ret = NULL;
216 BN_BLINDING **new_blindings;
217 uint8_t *new_blindings_inuse;
218 char overflow = 0;
219
220 CRYPTO_w_lock(CRYPTO_LOCK_RSA_BLINDING);
221 if (rsa->num_blindings > 0) {
222 unsigned i, starting_index;
223 CRYPTO_THREADID threadid;
224
225 /* We start searching the array at a value based on the
226 * threadid in order to try avoid bouncing the BN_BLINDING
227 * values around different threads. It's harmless if
228 * threadid.val is always set to zero. */
229 CRYPTO_THREADID_current(&threadid);
230 starting_index = threadid.val % rsa->num_blindings;
231
232 for (i = starting_index;;) {
233 if (rsa->blindings_inuse[i] == 0) {
234 rsa->blindings_inuse[i] = 1;
235 ret = rsa->blindings[i];
236 *index_used = i;
237 break;
238 }
239 i++;
240 if (i == rsa->num_blindings) {
241 i = 0;
242 }
243 if (i == starting_index) {
244 break;
245 }
246 }
247 }
248
249 if (ret != NULL) {
250 CRYPTO_w_unlock(CRYPTO_LOCK_RSA_BLINDING);
251 return ret;
252 }
253
254 overflow = rsa->num_blindings >= MAX_BLINDINGS_PER_RSA;
255
256 /* We didn't find a free BN_BLINDING to use so increase the length of
257 * the arrays by one and use the newly created element. */
258
259 CRYPTO_w_unlock(CRYPTO_LOCK_RSA_BLINDING);
260 ret = rsa_setup_blinding(rsa, ctx);
261 if (ret == NULL) {
262 return NULL;
263 }
264
265 if (overflow) {
266 /* We cannot add any more cached BN_BLINDINGs so we use |ret|
267 * and mark it for destruction in |rsa_blinding_release|. */
268 *index_used = MAX_BLINDINGS_PER_RSA;
269 return ret;
270 }
271
272 CRYPTO_w_lock(CRYPTO_LOCK_RSA_BLINDING);
273
274 new_blindings =
275 OPENSSL_malloc(sizeof(BN_BLINDING *) * (rsa->num_blindings + 1));
276 if (new_blindings == NULL) {
277 goto err1;
278 }
279 memcpy(new_blindings, rsa->blindings,
280 sizeof(BN_BLINDING *) * rsa->num_blindings);
281 new_blindings[rsa->num_blindings] = ret;
282
283 new_blindings_inuse = OPENSSL_malloc(rsa->num_blindings + 1);
284 if (new_blindings_inuse == NULL) {
285 goto err2;
286 }
287 memcpy(new_blindings_inuse, rsa->blindings_inuse, rsa->num_blindings);
288 new_blindings_inuse[rsa->num_blindings] = 1;
289 *index_used = rsa->num_blindings;
290
291 if (rsa->blindings != NULL) {
292 OPENSSL_free(rsa->blindings);
293 }
294 rsa->blindings = new_blindings;
295 if (rsa->blindings_inuse != NULL) {
296 OPENSSL_free(rsa->blindings_inuse);
297 }
298 rsa->blindings_inuse = new_blindings_inuse;
299 rsa->num_blindings++;
300
301 CRYPTO_w_unlock(CRYPTO_LOCK_RSA_BLINDING);
302 return ret;
303
304err2:
305 OPENSSL_free(new_blindings);
306
307err1:
308 CRYPTO_w_unlock(CRYPTO_LOCK_RSA_BLINDING);
309 BN_BLINDING_free(ret);
310 return NULL;
311}
312
313/* rsa_blinding_release marks the cached BN_BLINDING at the given index as free
314 * for other threads to use. */
315static void rsa_blinding_release(RSA *rsa, BN_BLINDING *blinding,
316 unsigned blinding_index) {
317 if (blinding_index == MAX_BLINDINGS_PER_RSA) {
318 /* This blinding wasn't cached. */
319 BN_BLINDING_free(blinding);
320 return;
321 }
322
323 CRYPTO_w_lock(CRYPTO_LOCK_RSA_BLINDING);
324 rsa->blindings_inuse[blinding_index] = 0;
325 CRYPTO_w_unlock(CRYPTO_LOCK_RSA_BLINDING);
326}
327
328/* signing */
329static int sign_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
330 const uint8_t *in, size_t in_len, int padding) {
331 const unsigned rsa_size = RSA_size(rsa);
Adam Langley95c29f32014-06-20 12:00:00 -0700332 uint8_t *buf = NULL;
Adam Langley6887edb2014-06-20 12:00:00 -0700333 int i, ret = 0;
Adam Langley95c29f32014-06-20 12:00:00 -0700334
335 if (max_out < rsa_size) {
336 OPENSSL_PUT_ERROR(RSA, sign_raw, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
337 return 0;
338 }
339
Adam Langley95c29f32014-06-20 12:00:00 -0700340 buf = OPENSSL_malloc(rsa_size);
Adam Langley6bc658d2014-08-18 13:29:45 -0700341 if (buf == NULL) {
Adam Langley95c29f32014-06-20 12:00:00 -0700342 OPENSSL_PUT_ERROR(RSA, sign_raw, ERR_R_MALLOC_FAILURE);
343 goto err;
344 }
345
346 switch (padding) {
347 case RSA_PKCS1_PADDING:
348 i = RSA_padding_add_PKCS1_type_1(buf, rsa_size, in, in_len);
349 break;
350 case RSA_NO_PADDING:
351 i = RSA_padding_add_none(buf, rsa_size, in, in_len);
352 break;
353 default:
354 OPENSSL_PUT_ERROR(RSA, sign_raw, RSA_R_UNKNOWN_PADDING_TYPE);
355 goto err;
356 }
Adam Langley6bc658d2014-08-18 13:29:45 -0700357
Adam Langley95c29f32014-06-20 12:00:00 -0700358 if (i <= 0) {
359 goto err;
360 }
361
Adam Langley6bc658d2014-08-18 13:29:45 -0700362 if (!RSA_private_transform(rsa, out, buf, rsa_size)) {
Adam Langley95c29f32014-06-20 12:00:00 -0700363 OPENSSL_PUT_ERROR(RSA, sign_raw, ERR_R_INTERNAL_ERROR);
364 goto err;
Adam Langley95c29f32014-06-20 12:00:00 -0700365 }
366
367 *out_len = rsa_size;
368 ret = 1;
369
370err:
Adam Langley95c29f32014-06-20 12:00:00 -0700371 if (buf != NULL) {
372 OPENSSL_cleanse(buf, rsa_size);
373 OPENSSL_free(buf);
374 }
Adam Langley95c29f32014-06-20 12:00:00 -0700375
376 return ret;
377}
378
379static int decrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
380 const uint8_t *in, size_t in_len, int padding) {
381 const unsigned rsa_size = RSA_size(rsa);
Adam Langley95c29f32014-06-20 12:00:00 -0700382 int r = -1;
383 uint8_t *buf = NULL;
Adam Langley95c29f32014-06-20 12:00:00 -0700384 int ret = 0;
385
386 if (max_out < rsa_size) {
387 OPENSSL_PUT_ERROR(RSA, decrypt, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
388 return 0;
389 }
390
Adam Langley95c29f32014-06-20 12:00:00 -0700391 buf = OPENSSL_malloc(rsa_size);
Adam Langley6bc658d2014-08-18 13:29:45 -0700392 if (buf == NULL) {
Adam Langley95c29f32014-06-20 12:00:00 -0700393 OPENSSL_PUT_ERROR(RSA, decrypt, ERR_R_MALLOC_FAILURE);
394 goto err;
395 }
396
Adam Langley6bc658d2014-08-18 13:29:45 -0700397 if (in_len != rsa_size) {
398 OPENSSL_PUT_ERROR(RSA, decrypt, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
Adam Langley95c29f32014-06-20 12:00:00 -0700399 goto err;
400 }
401
Adam Langley6bc658d2014-08-18 13:29:45 -0700402 if (!RSA_private_transform(rsa, buf, in, rsa_size)) {
Adam Langley6887edb2014-06-20 12:00:00 -0700403 OPENSSL_PUT_ERROR(RSA, decrypt, ERR_R_INTERNAL_ERROR);
404 goto err;
405 }
Adam Langley95c29f32014-06-20 12:00:00 -0700406
407 switch (padding) {
408 case RSA_PKCS1_PADDING:
Adam Langley6887edb2014-06-20 12:00:00 -0700409 r = RSA_padding_check_PKCS1_type_2(out, rsa_size, buf, rsa_size);
Adam Langley95c29f32014-06-20 12:00:00 -0700410 break;
411 case RSA_PKCS1_OAEP_PADDING:
Adam Langley6887edb2014-06-20 12:00:00 -0700412 /* Use the default parameters: SHA-1 for both hashes and no label. */
413 r = RSA_padding_check_PKCS1_OAEP_mgf1(out, rsa_size, buf, rsa_size,
414 NULL, 0, NULL, NULL);
Adam Langley95c29f32014-06-20 12:00:00 -0700415 break;
Adam Langley95c29f32014-06-20 12:00:00 -0700416 case RSA_NO_PADDING:
Adam Langley6887edb2014-06-20 12:00:00 -0700417 r = RSA_padding_check_none(out, rsa_size, buf, rsa_size);
Adam Langley95c29f32014-06-20 12:00:00 -0700418 break;
419 default:
420 OPENSSL_PUT_ERROR(RSA, decrypt, RSA_R_UNKNOWN_PADDING_TYPE);
421 goto err;
422 }
423
424 if (r < 0) {
425 OPENSSL_PUT_ERROR(RSA, decrypt, RSA_R_PADDING_CHECK_FAILED);
426 } else {
427 *out_len = r;
428 ret = 1;
429 }
430
431err:
Adam Langley95c29f32014-06-20 12:00:00 -0700432 if (buf != NULL) {
433 OPENSSL_cleanse(buf, rsa_size);
434 OPENSSL_free(buf);
435 }
Adam Langley95c29f32014-06-20 12:00:00 -0700436
437 return ret;
438}
439
440static int verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
441 const uint8_t *in, size_t in_len, int padding) {
442 const unsigned rsa_size = RSA_size(rsa);
443 BIGNUM *f, *result;
444 int ret = 0;
Adam Langley6887edb2014-06-20 12:00:00 -0700445 int r = -1;
Adam Langley95c29f32014-06-20 12:00:00 -0700446 uint8_t *buf = NULL;
447 BN_CTX *ctx = NULL;
448
449 if (BN_num_bits(rsa->n) > OPENSSL_RSA_MAX_MODULUS_BITS) {
450 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_MODULUS_TOO_LARGE);
451 return 0;
452 }
453
454 if (BN_ucmp(rsa->n, rsa->e) <= 0) {
455 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_BAD_E_VALUE);
456 return 0;
457 }
458
459 if (max_out < rsa_size) {
460 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
461 return 0;
462 }
463
464 /* for large moduli, enforce exponent limit */
465 if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS &&
466 BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) {
467 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_BAD_E_VALUE);
468 return 0;
469 }
470
471 ctx = BN_CTX_new();
472 if (ctx == NULL) {
473 goto err;
474 }
475
476 BN_CTX_start(ctx);
477 f = BN_CTX_get(ctx);
478 result = BN_CTX_get(ctx);
479 buf = OPENSSL_malloc(rsa_size);
480 if (!f || !result || !buf) {
481 OPENSSL_PUT_ERROR(RSA, verify_raw, ERR_R_MALLOC_FAILURE);
482 goto err;
483 }
484
Adam Langley6bc658d2014-08-18 13:29:45 -0700485 if (in_len != rsa_size) {
486 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
Adam Langley95c29f32014-06-20 12:00:00 -0700487 goto err;
488 }
489
490 if (BN_bin2bn(in, in_len, f) == NULL) {
491 goto err;
492 }
493
494 if (BN_ucmp(f, rsa->n) >= 0) {
495 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
496 goto err;
497 }
498
499 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
500 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, CRYPTO_LOCK_RSA, rsa->n,
501 ctx)) {
502 goto err;
503 }
504 }
505
506 if (!rsa->meth->bn_mod_exp(result, f, rsa->e, rsa->n, ctx,
507 rsa->_method_mod_n)) {
508 goto err;
509 }
510
Adam Langley6887edb2014-06-20 12:00:00 -0700511 if (!BN_bn2bin_padded(buf, rsa_size, result)) {
512 OPENSSL_PUT_ERROR(RSA, verify_raw, ERR_R_INTERNAL_ERROR);
513 goto err;
514 }
Adam Langley95c29f32014-06-20 12:00:00 -0700515
516 switch (padding) {
517 case RSA_PKCS1_PADDING:
Adam Langley6887edb2014-06-20 12:00:00 -0700518 r = RSA_padding_check_PKCS1_type_1(out, rsa_size, buf, rsa_size);
Adam Langley95c29f32014-06-20 12:00:00 -0700519 break;
520 case RSA_NO_PADDING:
Adam Langley6887edb2014-06-20 12:00:00 -0700521 r = RSA_padding_check_none(out, rsa_size, buf, rsa_size);
Adam Langley95c29f32014-06-20 12:00:00 -0700522 break;
523 default:
524 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_UNKNOWN_PADDING_TYPE);
525 goto err;
526 }
527
528 if (r < 0) {
529 OPENSSL_PUT_ERROR(RSA, verify_raw, RSA_R_PADDING_CHECK_FAILED);
530 } else {
531 *out_len = r;
532 ret = 1;
533 }
534
535err:
536 if (ctx != NULL) {
537 BN_CTX_end(ctx);
538 BN_CTX_free(ctx);
539 }
540 if (buf != NULL) {
541 OPENSSL_cleanse(buf, rsa_size);
542 OPENSSL_free(buf);
543 }
544 return ret;
545}
546
Adam Langley6bc658d2014-08-18 13:29:45 -0700547static int private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,
548 size_t len) {
549 BIGNUM *f, *result;
550 BN_CTX *ctx = NULL;
551 unsigned blinding_index = 0;
552 BN_BLINDING *blinding = NULL;
553 int ret = 0;
554
555 ctx = BN_CTX_new();
556 if (ctx == NULL) {
557 goto err;
558 }
559 BN_CTX_start(ctx);
560 f = BN_CTX_get(ctx);
561 result = BN_CTX_get(ctx);
562
563 if (f == NULL || result == NULL) {
564 OPENSSL_PUT_ERROR(RSA, private_transform, ERR_R_MALLOC_FAILURE);
565 goto err;
566 }
567
568 if (BN_bin2bn(in, len, f) == NULL) {
569 goto err;
570 }
571
572 if (BN_ucmp(f, rsa->n) >= 0) {
573 /* Usually the padding functions would catch this. */
574 OPENSSL_PUT_ERROR(RSA, private_transform, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
575 goto err;
576 }
577
578 if (!(rsa->flags & RSA_FLAG_NO_BLINDING)) {
579 blinding = rsa_blinding_get(rsa, &blinding_index, ctx);
580 if (blinding == NULL) {
581 OPENSSL_PUT_ERROR(RSA, private_transform, ERR_R_INTERNAL_ERROR);
582 goto err;
583 }
584 if (!BN_BLINDING_convert_ex(f, NULL, blinding, ctx)) {
585 goto err;
586 }
587 }
588
589 if ((rsa->flags & RSA_FLAG_EXT_PKEY) ||
590 ((rsa->p != NULL) && (rsa->q != NULL) && (rsa->dmp1 != NULL) &&
591 (rsa->dmq1 != NULL) && (rsa->iqmp != NULL))) {
592 if (!rsa->meth->mod_exp(result, f, rsa, ctx)) {
593 goto err;
594 }
595 } else {
596 BIGNUM local_d;
597 BIGNUM *d = NULL;
598
599 BN_init(&local_d);
600 d = &local_d;
601 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
602
603 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
604 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, CRYPTO_LOCK_RSA, rsa->n,
605 ctx)) {
606 goto err;
607 }
608 }
609
610 if (!rsa->meth->bn_mod_exp(result, f, d, rsa->n, ctx, rsa->_method_mod_n)) {
611 goto err;
612 }
613 }
614
615 if (blinding) {
616 if (!BN_BLINDING_invert_ex(result, NULL, blinding, ctx)) {
617 goto err;
618 }
619 }
620
621 if (!BN_bn2bin_padded(out, len, result)) {
622 OPENSSL_PUT_ERROR(RSA, private_transform, ERR_R_INTERNAL_ERROR);
623 goto err;
624 }
625
626 ret = 1;
627
628err:
629 if (ctx != NULL) {
630 BN_CTX_end(ctx);
631 BN_CTX_free(ctx);
632 }
633 if (blinding != NULL) {
634 rsa_blinding_release(rsa, blinding, blinding_index);
635 }
636
637 return ret;
638}
639
Adam Langley95c29f32014-06-20 12:00:00 -0700640static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
641 BIGNUM *r1, *m1, *vrfy;
642 BIGNUM local_dmp1, local_dmq1, local_c, local_r1;
643 BIGNUM *dmp1, *dmq1, *c, *pr1;
644 int ret = 0;
645
646 BN_CTX_start(ctx);
647 r1 = BN_CTX_get(ctx);
648 m1 = BN_CTX_get(ctx);
649 vrfy = BN_CTX_get(ctx);
650
651 {
652 BIGNUM local_p, local_q;
653 BIGNUM *p = NULL, *q = NULL;
654
655 /* Make sure BN_mod_inverse in Montgomery intialization uses the
656 * BN_FLG_CONSTTIME flag (unless RSA_FLAG_NO_CONSTTIME is set) */
657 BN_init(&local_p);
658 p = &local_p;
659 BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
660
661 BN_init(&local_q);
662 q = &local_q;
663 BN_with_flags(q, rsa->q, BN_FLG_CONSTTIME);
664
665 if (rsa->flags & RSA_FLAG_CACHE_PRIVATE) {
666 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_p, CRYPTO_LOCK_RSA, p, ctx)) {
667 goto err;
668 }
669 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_q, CRYPTO_LOCK_RSA, q, ctx)) {
670 goto err;
671 }
672 }
673 }
674
675 if (rsa->flags & RSA_FLAG_CACHE_PUBLIC) {
676 if (!BN_MONT_CTX_set_locked(&rsa->_method_mod_n, CRYPTO_LOCK_RSA, rsa->n,
677 ctx)) {
678 goto err;
679 }
680 }
681
682 /* compute I mod q */
683 c = &local_c;
684 BN_with_flags(c, I, BN_FLG_CONSTTIME);
685 if (!BN_mod(r1, c, rsa->q, ctx)) {
686 goto err;
687 }
688
689 /* compute r1^dmq1 mod q */
690 dmq1 = &local_dmq1;
691 BN_with_flags(dmq1, rsa->dmq1, BN_FLG_CONSTTIME);
692 if (!rsa->meth->bn_mod_exp(m1, r1, dmq1, rsa->q, ctx, rsa->_method_mod_q)) {
693 goto err;
694 }
695
696 /* compute I mod p */
697 c = &local_c;
698 BN_with_flags(c, I, BN_FLG_CONSTTIME);
699 if (!BN_mod(r1, c, rsa->p, ctx)) {
700 goto err;
701 }
702
703 /* compute r1^dmp1 mod p */
704 dmp1 = &local_dmp1;
705 BN_with_flags(dmp1, rsa->dmp1, BN_FLG_CONSTTIME);
706 if (!rsa->meth->bn_mod_exp(r0, r1, dmp1, rsa->p, ctx, rsa->_method_mod_p)) {
707 goto err;
708 }
709
710 if (!BN_sub(r0, r0, m1)) {
711 goto err;
712 }
713 /* This will help stop the size of r0 increasing, which does
714 * affect the multiply if it optimised for a power of 2 size */
715 if (BN_is_negative(r0)) {
716 if (!BN_add(r0, r0, rsa->p)) {
717 goto err;
718 }
719 }
720
721 if (!BN_mul(r1, r0, rsa->iqmp, ctx)) {
722 goto err;
723 }
724
725 /* Turn BN_FLG_CONSTTIME flag on before division operation */
726 pr1 = &local_r1;
727 BN_with_flags(pr1, r1, BN_FLG_CONSTTIME);
728
729 if (!BN_mod(r0, pr1, rsa->p, ctx)) {
730 goto err;
731 }
732
733 /* If p < q it is occasionally possible for the correction of
734 * adding 'p' if r0 is negative above to leave the result still
735 * negative. This can break the private key operations: the following
736 * second correction should *always* correct this rare occurrence.
737 * This will *never* happen with OpenSSL generated keys because
738 * they ensure p > q [steve] */
739 if (BN_is_negative(r0)) {
740 if (!BN_add(r0, r0, rsa->p)) {
741 goto err;
742 }
743 }
744 if (!BN_mul(r1, r0, rsa->q, ctx)) {
745 goto err;
746 }
747 if (!BN_add(r0, r1, m1)) {
748 goto err;
749 }
750
751 if (rsa->e && rsa->n) {
752 if (!rsa->meth->bn_mod_exp(vrfy, r0, rsa->e, rsa->n, ctx,
753 rsa->_method_mod_n)) {
754 goto err;
755 }
756 /* If 'I' was greater than (or equal to) rsa->n, the operation
757 * will be equivalent to using 'I mod n'. However, the result of
758 * the verify will *always* be less than 'n' so we don't check
759 * for absolute equality, just congruency. */
760 if (!BN_sub(vrfy, vrfy, I)) {
761 goto err;
762 }
763 if (!BN_mod(vrfy, vrfy, rsa->n, ctx)) {
764 goto err;
765 }
766 if (BN_is_negative(vrfy)) {
767 if (!BN_add(vrfy, vrfy, rsa->n)) {
768 goto err;
769 }
770 }
771 if (!BN_is_zero(vrfy)) {
772 /* 'I' and 'vrfy' aren't congruent mod n. Don't leak
773 * miscalculated CRT output, just do a raw (slower)
774 * mod_exp and return that instead. */
775
776 BIGNUM local_d;
777 BIGNUM *d = NULL;
778
779 d = &local_d;
780 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
781 if (!rsa->meth->bn_mod_exp(r0, I, d, rsa->n, ctx, rsa->_method_mod_n)) {
782 goto err;
783 }
784 }
785 }
786 ret = 1;
787
788err:
789 BN_CTX_end(ctx);
790 return ret;
791}
792
793static int keygen(RSA *rsa, int bits, BIGNUM *e_value, BN_GENCB *cb) {
794 BIGNUM *r0 = NULL, *r1 = NULL, *r2 = NULL, *r3 = NULL, *tmp;
795 BIGNUM local_r0, local_d, local_p;
796 BIGNUM *pr0, *d, *p;
797 int bitsp, bitsq, ok = -1, n = 0;
798 BN_CTX *ctx = NULL;
799
800 ctx = BN_CTX_new();
801 if (ctx == NULL) {
802 goto err;
803 }
804 BN_CTX_start(ctx);
805 r0 = BN_CTX_get(ctx);
806 r1 = BN_CTX_get(ctx);
807 r2 = BN_CTX_get(ctx);
808 r3 = BN_CTX_get(ctx);
809 if (r3 == NULL) {
810 goto err;
811 }
812
813 bitsp = (bits + 1) / 2;
814 bitsq = bits - bitsp;
815
816 /* We need the RSA components non-NULL */
817 if (!rsa->n && ((rsa->n = BN_new()) == NULL))
818 goto err;
819 if (!rsa->d && ((rsa->d = BN_new()) == NULL))
820 goto err;
821 if (!rsa->e && ((rsa->e = BN_new()) == NULL))
822 goto err;
823 if (!rsa->p && ((rsa->p = BN_new()) == NULL))
824 goto err;
825 if (!rsa->q && ((rsa->q = BN_new()) == NULL))
826 goto err;
827 if (!rsa->dmp1 && ((rsa->dmp1 = BN_new()) == NULL))
828 goto err;
829 if (!rsa->dmq1 && ((rsa->dmq1 = BN_new()) == NULL))
830 goto err;
831 if (!rsa->iqmp && ((rsa->iqmp = BN_new()) == NULL))
832 goto err;
833
834 BN_copy(rsa->e, e_value);
835
836 /* generate p and q */
837 for (;;) {
838 if (!BN_generate_prime_ex(rsa->p, bitsp, 0, NULL, NULL, cb))
839 goto err;
840 if (!BN_sub(r2, rsa->p, BN_value_one()))
841 goto err;
842 if (!BN_gcd(r1, r2, rsa->e, ctx))
843 goto err;
844 if (BN_is_one(r1))
845 break;
846 if (!BN_GENCB_call(cb, 2, n++))
847 goto err;
848 }
849 if (!BN_GENCB_call(cb, 3, 0))
850 goto err;
851 for (;;) {
852 /* When generating ridiculously small keys, we can get stuck
853 * continually regenerating the same prime values. Check for
854 * this and bail if it happens 3 times. */
855 unsigned int degenerate = 0;
856 do {
857 if (!BN_generate_prime_ex(rsa->q, bitsq, 0, NULL, NULL, cb))
858 goto err;
859 } while ((BN_cmp(rsa->p, rsa->q) == 0) && (++degenerate < 3));
860 if (degenerate == 3) {
861 ok = 0; /* we set our own err */
862 OPENSSL_PUT_ERROR(RSA, keygen, RSA_R_KEY_SIZE_TOO_SMALL);
863 goto err;
864 }
865 if (!BN_sub(r2, rsa->q, BN_value_one()))
866 goto err;
867 if (!BN_gcd(r1, r2, rsa->e, ctx))
868 goto err;
869 if (BN_is_one(r1))
870 break;
871 if (!BN_GENCB_call(cb, 2, n++))
872 goto err;
873 }
874 if (!BN_GENCB_call(cb, 3, 1))
875 goto err;
876 if (BN_cmp(rsa->p, rsa->q) < 0) {
877 tmp = rsa->p;
878 rsa->p = rsa->q;
879 rsa->q = tmp;
880 }
881
882 /* calculate n */
883 if (!BN_mul(rsa->n, rsa->p, rsa->q, ctx))
884 goto err;
885
886 /* calculate d */
887 if (!BN_sub(r1, rsa->p, BN_value_one()))
888 goto err; /* p-1 */
889 if (!BN_sub(r2, rsa->q, BN_value_one()))
890 goto err; /* q-1 */
891 if (!BN_mul(r0, r1, r2, ctx))
892 goto err; /* (p-1)(q-1) */
893 pr0 = &local_r0;
894 BN_with_flags(pr0, r0, BN_FLG_CONSTTIME);
895 if (!BN_mod_inverse(rsa->d, rsa->e, pr0, ctx))
896 goto err; /* d */
897
898 /* set up d for correct BN_FLG_CONSTTIME flag */
899 d = &local_d;
900 BN_with_flags(d, rsa->d, BN_FLG_CONSTTIME);
901
902 /* calculate d mod (p-1) */
903 if (!BN_mod(rsa->dmp1, d, r1, ctx))
904 goto err;
905
906 /* calculate d mod (q-1) */
907 if (!BN_mod(rsa->dmq1, d, r2, ctx))
908 goto err;
909
910 /* calculate inverse of q mod p */
911 p = &local_p;
912 BN_with_flags(p, rsa->p, BN_FLG_CONSTTIME);
913
914 if (!BN_mod_inverse(rsa->iqmp, rsa->q, p, ctx))
915 goto err;
916
917 ok = 1;
918
919err:
920 if (ok == -1) {
921 OPENSSL_PUT_ERROR(RSA, keygen, ERR_LIB_BN);
922 ok = 0;
923 }
924 if (ctx != NULL) {
925 BN_CTX_end(ctx);
926 BN_CTX_free(ctx);
927 }
928
929 return ok;
930}
931
932const struct rsa_meth_st RSA_default_method = {
933 {
934 0 /* references */,
935 1 /* is_static */,
936 },
937 NULL /* app_data */,
938
939 NULL /* init */,
940 finish,
941
David Benjamin925fee32014-07-11 14:14:08 -0400942 size,
943
Adam Langley95c29f32014-06-20 12:00:00 -0700944 NULL /* sign */,
945 NULL /* verify */,
946
947 encrypt,
948 sign_raw,
949 decrypt,
950 verify_raw,
951
Adam Langley6bc658d2014-08-18 13:29:45 -0700952 private_transform,
953
Adam Langley95c29f32014-06-20 12:00:00 -0700954 mod_exp /* mod_exp */,
955 BN_mod_exp_mont /* bn_mod_exp */,
956
957 RSA_FLAG_CACHE_PUBLIC | RSA_FLAG_CACHE_PRIVATE,
958
959 keygen,
960};