1 /* 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
59 #include <assert.h>
60 #include <limits.h>
61 #include <string.h>
62
63 #include <openssl/bn.h>
64 #include <openssl/err.h>
65 #include <openssl/mem.h>
66 #include <openssl/thread.h>
67 #include <openssl/type_check.h>
68
69 #include "internal.h"
70 #include "../bn/internal.h"
71 #include "../../internal.h"
72 #include "../delocate.h"
73 #include "../rand/fork_detect.h"
74
75
check_modulus_and_exponent_sizes(const RSA * rsa)76 static int check_modulus_and_exponent_sizes(const RSA *rsa) {
77 unsigned rsa_bits = BN_num_bits(rsa->n);
78
79 if (rsa_bits > 16 * 1024) {
80 OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE);
81 return 0;
82 }
83
84 // Mitigate DoS attacks by limiting the exponent size. 33 bits was chosen as
85 // the limit based on the recommendations in [1] and [2]. Windows CryptoAPI
86 // doesn't support values larger than 32 bits [3], so it is unlikely that
87 // exponents larger than 32 bits are being used for anything Windows commonly
88 // does.
89 //
90 // [1] https://www.imperialviolet.org/2012/03/16/rsae.html
91 // [2] https://www.imperialviolet.org/2012/03/17/rsados.html
92 // [3] https://msdn.microsoft.com/en-us/library/aa387685(VS.85).aspx
93 static const unsigned kMaxExponentBits = 33;
94
95 if (BN_num_bits(rsa->e) > kMaxExponentBits) {
96 OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
97 return 0;
98 }
99
100 // Verify |n > e|. Comparing |rsa_bits| to |kMaxExponentBits| is a small
101 // shortcut to comparing |n| and |e| directly. In reality, |kMaxExponentBits|
102 // is much smaller than the minimum RSA key size that any application should
103 // accept.
104 if (rsa_bits <= kMaxExponentBits) {
105 OPENSSL_PUT_ERROR(RSA, RSA_R_KEY_SIZE_TOO_SMALL);
106 return 0;
107 }
108 assert(BN_ucmp(rsa->n, rsa->e) > 0);
109
110 return 1;
111 }
112
ensure_fixed_copy(BIGNUM ** out,const BIGNUM * in,int width)113 static int ensure_fixed_copy(BIGNUM **out, const BIGNUM *in, int width) {
114 if (*out != NULL) {
115 return 1;
116 }
117 BIGNUM *copy = BN_dup(in);
118 if (copy == NULL ||
119 !bn_resize_words(copy, width)) {
120 BN_free(copy);
121 return 0;
122 }
123 *out = copy;
124 CONSTTIME_SECRET(copy->d, sizeof(BN_ULONG) * width);
125
126 return 1;
127 }
128
129 // freeze_private_key finishes initializing |rsa|'s private key components.
130 // After this function has returned, |rsa| may not be changed. This is needed
131 // because |RSA| is a public struct and, additionally, OpenSSL 1.1.0 opaquified
132 // it wrong (see https://github.com/openssl/openssl/issues/5158).
freeze_private_key(RSA * rsa,BN_CTX * ctx)133 static int freeze_private_key(RSA *rsa, BN_CTX *ctx) {
134 CRYPTO_MUTEX_lock_read(&rsa->lock);
135 int frozen = rsa->private_key_frozen;
136 CRYPTO_MUTEX_unlock_read(&rsa->lock);
137 if (frozen) {
138 return 1;
139 }
140
141 int ret = 0;
142 CRYPTO_MUTEX_lock_write(&rsa->lock);
143 if (rsa->private_key_frozen) {
144 ret = 1;
145 goto err;
146 }
147
148 // Pre-compute various intermediate values, as well as copies of private
149 // exponents with correct widths. Note that other threads may concurrently
150 // read from |rsa->n|, |rsa->e|, etc., so any fixes must be in separate
151 // copies. We use |mont_n->N|, |mont_p->N|, and |mont_q->N| as copies of |n|,
152 // |p|, and |q| with the correct minimal widths.
153
154 if (rsa->mont_n == NULL) {
155 rsa->mont_n = BN_MONT_CTX_new_for_modulus(rsa->n, ctx);
156 if (rsa->mont_n == NULL) {
157 goto err;
158 }
159 }
160 const BIGNUM *n_fixed = &rsa->mont_n->N;
161
162 // The only public upper-bound of |rsa->d| is the bit length of |rsa->n|. The
163 // ASN.1 serialization of RSA private keys unfortunately leaks the byte length
164 // of |rsa->d|, but normalize it so we only leak it once, rather than per
165 // operation.
166 if (rsa->d != NULL &&
167 !ensure_fixed_copy(&rsa->d_fixed, rsa->d, n_fixed->width)) {
168 goto err;
169 }
170
171 if (rsa->p != NULL && rsa->q != NULL) {
172 // TODO: p and q are also CONSTTIME_SECRET but not yet marked as such
173 // because the Montgomery code does things like test whether or not values
174 // are zero. So the secret marking probably needs to happen inside that
175 // code.
176
177 if (rsa->mont_p == NULL) {
178 rsa->mont_p = BN_MONT_CTX_new_consttime(rsa->p, ctx);
179 if (rsa->mont_p == NULL) {
180 goto err;
181 }
182 }
183 const BIGNUM *p_fixed = &rsa->mont_p->N;
184
185 if (rsa->mont_q == NULL) {
186 rsa->mont_q = BN_MONT_CTX_new_consttime(rsa->q, ctx);
187 if (rsa->mont_q == NULL) {
188 goto err;
189 }
190 }
191 const BIGNUM *q_fixed = &rsa->mont_q->N;
192
193 if (rsa->dmp1 != NULL && rsa->dmq1 != NULL) {
194 // Key generation relies on this function to compute |iqmp|.
195 if (rsa->iqmp == NULL) {
196 BIGNUM *iqmp = BN_new();
197 if (iqmp == NULL ||
198 !bn_mod_inverse_secret_prime(iqmp, rsa->q, rsa->p, ctx,
199 rsa->mont_p)) {
200 BN_free(iqmp);
201 goto err;
202 }
203 rsa->iqmp = iqmp;
204 }
205
206 // CRT components are only publicly bounded by their corresponding
207 // moduli's bit lengths. |rsa->iqmp| is unused outside of this one-time
208 // setup, so we do not compute a fixed-width version of it.
209 if (!ensure_fixed_copy(&rsa->dmp1_fixed, rsa->dmp1, p_fixed->width) ||
210 !ensure_fixed_copy(&rsa->dmq1_fixed, rsa->dmq1, q_fixed->width)) {
211 goto err;
212 }
213
214 // Compute |inv_small_mod_large_mont|. Note that it is always modulo the
215 // larger prime, independent of what is stored in |rsa->iqmp|.
216 if (rsa->inv_small_mod_large_mont == NULL) {
217 BIGNUM *inv_small_mod_large_mont = BN_new();
218 int ok;
219 if (BN_cmp(rsa->p, rsa->q) < 0) {
220 ok = inv_small_mod_large_mont != NULL &&
221 bn_mod_inverse_secret_prime(inv_small_mod_large_mont, rsa->p,
222 rsa->q, ctx, rsa->mont_q) &&
223 BN_to_montgomery(inv_small_mod_large_mont,
224 inv_small_mod_large_mont, rsa->mont_q, ctx);
225 } else {
226 ok = inv_small_mod_large_mont != NULL &&
227 BN_to_montgomery(inv_small_mod_large_mont, rsa->iqmp,
228 rsa->mont_p, ctx);
229 }
230 if (!ok) {
231 BN_free(inv_small_mod_large_mont);
232 goto err;
233 }
234 rsa->inv_small_mod_large_mont = inv_small_mod_large_mont;
235 CONSTTIME_SECRET(
236 rsa->inv_small_mod_large_mont->d,
237 sizeof(BN_ULONG) * rsa->inv_small_mod_large_mont->width);
238 }
239 }
240 }
241
242 rsa->private_key_frozen = 1;
243 ret = 1;
244
245 err:
246 CRYPTO_MUTEX_unlock_write(&rsa->lock);
247 return ret;
248 }
249
rsa_default_size(const RSA * rsa)250 size_t rsa_default_size(const RSA *rsa) {
251 return BN_num_bytes(rsa->n);
252 }
253
RSA_encrypt(RSA * rsa,size_t * out_len,uint8_t * out,size_t max_out,const uint8_t * in,size_t in_len,int padding)254 int RSA_encrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
255 const uint8_t *in, size_t in_len, int padding) {
256 if (rsa->n == NULL || rsa->e == NULL) {
257 OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);
258 return 0;
259 }
260
261 const unsigned rsa_size = RSA_size(rsa);
262 BIGNUM *f, *result;
263 uint8_t *buf = NULL;
264 BN_CTX *ctx = NULL;
265 int i, ret = 0;
266
267 if (max_out < rsa_size) {
268 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
269 return 0;
270 }
271
272 if (!check_modulus_and_exponent_sizes(rsa)) {
273 return 0;
274 }
275
276 ctx = BN_CTX_new();
277 if (ctx == NULL) {
278 goto err;
279 }
280
281 BN_CTX_start(ctx);
282 f = BN_CTX_get(ctx);
283 result = BN_CTX_get(ctx);
284 buf = OPENSSL_malloc(rsa_size);
285 if (!f || !result || !buf) {
286 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
287 goto err;
288 }
289
290 switch (padding) {
291 case RSA_PKCS1_PADDING:
292 i = RSA_padding_add_PKCS1_type_2(buf, rsa_size, in, in_len);
293 break;
294 case RSA_PKCS1_OAEP_PADDING:
295 // Use the default parameters: SHA-1 for both hashes and no label.
296 i = RSA_padding_add_PKCS1_OAEP_mgf1(buf, rsa_size, in, in_len,
297 NULL, 0, NULL, NULL);
298 break;
299 case RSA_NO_PADDING:
300 i = RSA_padding_add_none(buf, rsa_size, in, in_len);
301 break;
302 default:
303 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
304 goto err;
305 }
306
307 if (i <= 0) {
308 goto err;
309 }
310
311 if (BN_bin2bn(buf, rsa_size, f) == NULL) {
312 goto err;
313 }
314
315 if (BN_ucmp(f, rsa->n) >= 0) {
316 // usually the padding functions would catch this
317 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
318 goto err;
319 }
320
321 if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ||
322 !BN_mod_exp_mont(result, f, rsa->e, &rsa->mont_n->N, ctx, rsa->mont_n)) {
323 goto err;
324 }
325
326 // put in leading 0 bytes if the number is less than the length of the
327 // modulus
328 if (!BN_bn2bin_padded(out, rsa_size, result)) {
329 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
330 goto err;
331 }
332
333 *out_len = rsa_size;
334 ret = 1;
335
336 err:
337 if (ctx != NULL) {
338 BN_CTX_end(ctx);
339 BN_CTX_free(ctx);
340 }
341 OPENSSL_free(buf);
342
343 return ret;
344 }
345
346 // MAX_BLINDINGS_PER_RSA defines the maximum number of cached BN_BLINDINGs per
347 // RSA*. Then this limit is exceeded, BN_BLINDING objects will be created and
348 // destroyed as needed.
349 #if defined(OPNESSL_TSAN)
350 // Smaller under TSAN so that the edge case can be hit with fewer threads.
351 #define MAX_BLINDINGS_PER_RSA 2
352 #else
353 #define MAX_BLINDINGS_PER_RSA 1024
354 #endif
355
356 // rsa_blinding_get returns a BN_BLINDING to use with |rsa|. It does this by
357 // allocating one of the cached BN_BLINDING objects in |rsa->blindings|. If
358 // none are free, the cache will be extended by a extra element and the new
359 // BN_BLINDING is returned.
360 //
361 // On success, the index of the assigned BN_BLINDING is written to
362 // |*index_used| and must be passed to |rsa_blinding_release| when finished.
rsa_blinding_get(RSA * rsa,unsigned * index_used,BN_CTX * ctx)363 static BN_BLINDING *rsa_blinding_get(RSA *rsa, unsigned *index_used,
364 BN_CTX *ctx) {
365 assert(ctx != NULL);
366 assert(rsa->mont_n != NULL);
367
368 BN_BLINDING *ret = NULL;
369 const uint64_t fork_generation = CRYPTO_get_fork_generation();
370 CRYPTO_MUTEX_lock_write(&rsa->lock);
371
372 // Wipe the blinding cache on |fork|.
373 if (rsa->blinding_fork_generation != fork_generation) {
374 for (unsigned i = 0; i < rsa->num_blindings; i++) {
375 // The inuse flag must be zero unless we were forked from a
376 // multi-threaded process, in which case calling back into BoringSSL is
377 // forbidden.
378 assert(rsa->blindings_inuse[i] == 0);
379 BN_BLINDING_invalidate(rsa->blindings[i]);
380 }
381 rsa->blinding_fork_generation = fork_generation;
382 }
383
384 uint8_t *const free_inuse_flag =
385 OPENSSL_memchr(rsa->blindings_inuse, 0, rsa->num_blindings);
386 if (free_inuse_flag != NULL) {
387 *free_inuse_flag = 1;
388 *index_used = free_inuse_flag - rsa->blindings_inuse;
389 ret = rsa->blindings[*index_used];
390 goto out;
391 }
392
393 if (rsa->num_blindings >= MAX_BLINDINGS_PER_RSA) {
394 // No |BN_BLINDING| is free and nor can the cache be extended. This index
395 // value is magic and indicates to |rsa_blinding_release| that a
396 // |BN_BLINDING| was not inserted into the array.
397 *index_used = MAX_BLINDINGS_PER_RSA;
398 ret = BN_BLINDING_new();
399 goto out;
400 }
401
402 // Double the length of the cache.
403 OPENSSL_STATIC_ASSERT(MAX_BLINDINGS_PER_RSA < UINT_MAX / 2,
404 "MAX_BLINDINGS_PER_RSA too large");
405 unsigned new_num_blindings = rsa->num_blindings * 2;
406 if (new_num_blindings == 0) {
407 new_num_blindings = 1;
408 }
409 if (new_num_blindings > MAX_BLINDINGS_PER_RSA) {
410 new_num_blindings = MAX_BLINDINGS_PER_RSA;
411 }
412 assert(new_num_blindings > rsa->num_blindings);
413
414 OPENSSL_STATIC_ASSERT(
415 MAX_BLINDINGS_PER_RSA < UINT_MAX / sizeof(BN_BLINDING *),
416 "MAX_BLINDINGS_PER_RSA too large");
417 BN_BLINDING **new_blindings =
418 OPENSSL_malloc(sizeof(BN_BLINDING *) * new_num_blindings);
419 uint8_t *new_blindings_inuse = OPENSSL_malloc(new_num_blindings);
420 if (new_blindings == NULL || new_blindings_inuse == NULL) {
421 goto err;
422 }
423
424 OPENSSL_memcpy(new_blindings, rsa->blindings,
425 sizeof(BN_BLINDING *) * rsa->num_blindings);
426 OPENSSL_memcpy(new_blindings_inuse, rsa->blindings_inuse, rsa->num_blindings);
427
428 for (unsigned i = rsa->num_blindings; i < new_num_blindings; i++) {
429 new_blindings[i] = BN_BLINDING_new();
430 if (new_blindings[i] == NULL) {
431 for (unsigned j = rsa->num_blindings; j < i; j++) {
432 BN_BLINDING_free(new_blindings[j]);
433 }
434 goto err;
435 }
436 }
437 memset(&new_blindings_inuse[rsa->num_blindings], 0,
438 new_num_blindings - rsa->num_blindings);
439
440 new_blindings_inuse[rsa->num_blindings] = 1;
441 *index_used = rsa->num_blindings;
442 assert(*index_used != MAX_BLINDINGS_PER_RSA);
443 ret = new_blindings[rsa->num_blindings];
444
445 OPENSSL_free(rsa->blindings);
446 rsa->blindings = new_blindings;
447 OPENSSL_free(rsa->blindings_inuse);
448 rsa->blindings_inuse = new_blindings_inuse;
449 rsa->num_blindings = new_num_blindings;
450
451 goto out;
452
453 err:
454 OPENSSL_free(new_blindings_inuse);
455 OPENSSL_free(new_blindings);
456
457 out:
458 CRYPTO_MUTEX_unlock_write(&rsa->lock);
459 return ret;
460 }
461
462 // rsa_blinding_release marks the cached BN_BLINDING at the given index as free
463 // for other threads to use.
rsa_blinding_release(RSA * rsa,BN_BLINDING * blinding,unsigned blinding_index)464 static void rsa_blinding_release(RSA *rsa, BN_BLINDING *blinding,
465 unsigned blinding_index) {
466 if (blinding_index == MAX_BLINDINGS_PER_RSA) {
467 // This blinding wasn't cached.
468 BN_BLINDING_free(blinding);
469 return;
470 }
471
472 CRYPTO_MUTEX_lock_write(&rsa->lock);
473 rsa->blindings_inuse[blinding_index] = 0;
474 CRYPTO_MUTEX_unlock_write(&rsa->lock);
475 }
476
477 // signing
rsa_default_sign_raw(RSA * rsa,size_t * out_len,uint8_t * out,size_t max_out,const uint8_t * in,size_t in_len,int padding)478 int rsa_default_sign_raw(RSA *rsa, size_t *out_len, uint8_t *out,
479 size_t max_out, const uint8_t *in, size_t in_len,
480 int padding) {
481 const unsigned rsa_size = RSA_size(rsa);
482 uint8_t *buf = NULL;
483 int i, ret = 0;
484
485 if (max_out < rsa_size) {
486 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
487 return 0;
488 }
489
490 buf = OPENSSL_malloc(rsa_size);
491 if (buf == NULL) {
492 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
493 goto err;
494 }
495
496 switch (padding) {
497 case RSA_PKCS1_PADDING:
498 i = RSA_padding_add_PKCS1_type_1(buf, rsa_size, in, in_len);
499 break;
500 case RSA_NO_PADDING:
501 i = RSA_padding_add_none(buf, rsa_size, in, in_len);
502 break;
503 default:
504 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
505 goto err;
506 }
507
508 if (i <= 0) {
509 goto err;
510 }
511
512 if (!RSA_private_transform(rsa, out, buf, rsa_size)) {
513 goto err;
514 }
515
516 CONSTTIME_DECLASSIFY(out, rsa_size);
517 *out_len = rsa_size;
518 ret = 1;
519
520 err:
521 OPENSSL_free(buf);
522
523 return ret;
524 }
525
rsa_default_decrypt(RSA * rsa,size_t * out_len,uint8_t * out,size_t max_out,const uint8_t * in,size_t in_len,int padding)526 int rsa_default_decrypt(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
527 const uint8_t *in, size_t in_len, int padding) {
528 const unsigned rsa_size = RSA_size(rsa);
529 uint8_t *buf = NULL;
530 int ret = 0;
531
532 if (max_out < rsa_size) {
533 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
534 return 0;
535 }
536
537 if (padding == RSA_NO_PADDING) {
538 buf = out;
539 } else {
540 // Allocate a temporary buffer to hold the padded plaintext.
541 buf = OPENSSL_malloc(rsa_size);
542 if (buf == NULL) {
543 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
544 goto err;
545 }
546 }
547
548 if (in_len != rsa_size) {
549 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
550 goto err;
551 }
552
553 if (!RSA_private_transform(rsa, buf, in, rsa_size)) {
554 goto err;
555 }
556
557 switch (padding) {
558 case RSA_PKCS1_PADDING:
559 ret =
560 RSA_padding_check_PKCS1_type_2(out, out_len, rsa_size, buf, rsa_size);
561 break;
562 case RSA_PKCS1_OAEP_PADDING:
563 // Use the default parameters: SHA-1 for both hashes and no label.
564 ret = RSA_padding_check_PKCS1_OAEP_mgf1(out, out_len, rsa_size, buf,
565 rsa_size, NULL, 0, NULL, NULL);
566 break;
567 case RSA_NO_PADDING:
568 *out_len = rsa_size;
569 ret = 1;
570 break;
571 default:
572 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
573 goto err;
574 }
575
576 CONSTTIME_DECLASSIFY(&ret, sizeof(ret));
577 if (!ret) {
578 OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED);
579 } else {
580 CONSTTIME_DECLASSIFY(out, *out_len);
581 }
582
583 err:
584 if (padding != RSA_NO_PADDING) {
585 OPENSSL_free(buf);
586 }
587
588 return ret;
589 }
590
591 static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx);
592
RSA_verify_raw(RSA * rsa,size_t * out_len,uint8_t * out,size_t max_out,const uint8_t * in,size_t in_len,int padding)593 int RSA_verify_raw(RSA *rsa, size_t *out_len, uint8_t *out, size_t max_out,
594 const uint8_t *in, size_t in_len, int padding) {
595 if (rsa->n == NULL || rsa->e == NULL) {
596 OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);
597 return 0;
598 }
599
600 const unsigned rsa_size = RSA_size(rsa);
601 BIGNUM *f, *result;
602
603 if (max_out < rsa_size) {
604 OPENSSL_PUT_ERROR(RSA, RSA_R_OUTPUT_BUFFER_TOO_SMALL);
605 return 0;
606 }
607
608 if (in_len != rsa_size) {
609 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_LEN_NOT_EQUAL_TO_MOD_LEN);
610 return 0;
611 }
612
613 if (!check_modulus_and_exponent_sizes(rsa)) {
614 return 0;
615 }
616
617 BN_CTX *ctx = BN_CTX_new();
618 if (ctx == NULL) {
619 return 0;
620 }
621
622 int ret = 0;
623 uint8_t *buf = NULL;
624
625 BN_CTX_start(ctx);
626 f = BN_CTX_get(ctx);
627 result = BN_CTX_get(ctx);
628 if (f == NULL || result == NULL) {
629 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
630 goto err;
631 }
632
633 if (padding == RSA_NO_PADDING) {
634 buf = out;
635 } else {
636 // Allocate a temporary buffer to hold the padded plaintext.
637 buf = OPENSSL_malloc(rsa_size);
638 if (buf == NULL) {
639 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
640 goto err;
641 }
642 }
643
644 if (BN_bin2bn(in, in_len, f) == NULL) {
645 goto err;
646 }
647
648 if (BN_ucmp(f, rsa->n) >= 0) {
649 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
650 goto err;
651 }
652
653 if (!BN_MONT_CTX_set_locked(&rsa->mont_n, &rsa->lock, rsa->n, ctx) ||
654 !BN_mod_exp_mont(result, f, rsa->e, &rsa->mont_n->N, ctx, rsa->mont_n)) {
655 goto err;
656 }
657
658 if (!BN_bn2bin_padded(buf, rsa_size, result)) {
659 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
660 goto err;
661 }
662
663 switch (padding) {
664 case RSA_PKCS1_PADDING:
665 ret =
666 RSA_padding_check_PKCS1_type_1(out, out_len, rsa_size, buf, rsa_size);
667 break;
668 case RSA_NO_PADDING:
669 ret = 1;
670 *out_len = rsa_size;
671 break;
672 default:
673 OPENSSL_PUT_ERROR(RSA, RSA_R_UNKNOWN_PADDING_TYPE);
674 goto err;
675 }
676
677 if (!ret) {
678 OPENSSL_PUT_ERROR(RSA, RSA_R_PADDING_CHECK_FAILED);
679 goto err;
680 }
681
682 err:
683 BN_CTX_end(ctx);
684 BN_CTX_free(ctx);
685 if (buf != out) {
686 OPENSSL_free(buf);
687 }
688 return ret;
689 }
690
rsa_default_private_transform(RSA * rsa,uint8_t * out,const uint8_t * in,size_t len)691 int rsa_default_private_transform(RSA *rsa, uint8_t *out, const uint8_t *in,
692 size_t len) {
693 if (rsa->n == NULL || rsa->d == NULL) {
694 OPENSSL_PUT_ERROR(RSA, RSA_R_VALUE_MISSING);
695 return 0;
696 }
697
698 BIGNUM *f, *result;
699 BN_CTX *ctx = NULL;
700 unsigned blinding_index = 0;
701 BN_BLINDING *blinding = NULL;
702 int ret = 0;
703
704 ctx = BN_CTX_new();
705 if (ctx == NULL) {
706 goto err;
707 }
708 BN_CTX_start(ctx);
709 f = BN_CTX_get(ctx);
710 result = BN_CTX_get(ctx);
711
712 if (f == NULL || result == NULL) {
713 OPENSSL_PUT_ERROR(RSA, ERR_R_MALLOC_FAILURE);
714 goto err;
715 }
716
717 if (BN_bin2bn(in, len, f) == NULL) {
718 goto err;
719 }
720
721 if (BN_ucmp(f, rsa->n) >= 0) {
722 // Usually the padding functions would catch this.
723 OPENSSL_PUT_ERROR(RSA, RSA_R_DATA_TOO_LARGE_FOR_MODULUS);
724 goto err;
725 }
726
727 if (!freeze_private_key(rsa, ctx)) {
728 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
729 goto err;
730 }
731
732 const int do_blinding = (rsa->flags & RSA_FLAG_NO_BLINDING) == 0;
733
734 if (rsa->e == NULL && do_blinding) {
735 // We cannot do blinding or verification without |e|, and continuing without
736 // those countermeasures is dangerous. However, the Java/Android RSA API
737 // requires support for keys where only |d| and |n| (and not |e|) are known.
738 // The callers that require that bad behavior set |RSA_FLAG_NO_BLINDING|.
739 OPENSSL_PUT_ERROR(RSA, RSA_R_NO_PUBLIC_EXPONENT);
740 goto err;
741 }
742
743 if (do_blinding) {
744 blinding = rsa_blinding_get(rsa, &blinding_index, ctx);
745 if (blinding == NULL) {
746 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
747 goto err;
748 }
749 if (!BN_BLINDING_convert(f, blinding, rsa->e, rsa->mont_n, ctx)) {
750 goto err;
751 }
752 }
753
754 if (rsa->p != NULL && rsa->q != NULL && rsa->e != NULL && rsa->dmp1 != NULL &&
755 rsa->dmq1 != NULL && rsa->iqmp != NULL &&
756 // Require that we can reduce |f| by |rsa->p| and |rsa->q| in constant
757 // time, which requires primes be the same size, rounded to the Montgomery
758 // coefficient. (See |mod_montgomery|.) This is not required by RFC 8017,
759 // but it is true for keys generated by us and all common implementations.
760 bn_less_than_montgomery_R(rsa->q, rsa->mont_p) &&
761 bn_less_than_montgomery_R(rsa->p, rsa->mont_q)) {
762 if (!mod_exp(result, f, rsa, ctx)) {
763 goto err;
764 }
765 } else if (!BN_mod_exp_mont_consttime(result, f, rsa->d_fixed, rsa->n, ctx,
766 rsa->mont_n)) {
767 goto err;
768 }
769
770 // Verify the result to protect against fault attacks as described in the
771 // 1997 paper "On the Importance of Checking Cryptographic Protocols for
772 // Faults" by Dan Boneh, Richard A. DeMillo, and Richard J. Lipton. Some
773 // implementations do this only when the CRT is used, but we do it in all
774 // cases. Section 6 of the aforementioned paper describes an attack that
775 // works when the CRT isn't used. That attack is much less likely to succeed
776 // than the CRT attack, but there have likely been improvements since 1997.
777 //
778 // This check is cheap assuming |e| is small; it almost always is.
779 if (rsa->e != NULL) {
780 BIGNUM *vrfy = BN_CTX_get(ctx);
781 if (vrfy == NULL ||
782 !BN_mod_exp_mont(vrfy, result, rsa->e, rsa->n, ctx, rsa->mont_n) ||
783 !BN_equal_consttime(vrfy, f)) {
784 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
785 goto err;
786 }
787
788 }
789
790 if (do_blinding &&
791 !BN_BLINDING_invert(result, blinding, rsa->mont_n, ctx)) {
792 goto err;
793 }
794
795 // The computation should have left |result| as a maximally-wide number, so
796 // that it and serializing does not leak information about the magnitude of
797 // the result.
798 //
799 // See Falko Strenzke, "Manger's Attack revisited", ICICS 2010.
800 assert(result->width == rsa->mont_n->N.width);
801 if (!BN_bn2bin_padded(out, len, result)) {
802 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
803 goto err;
804 }
805
806 ret = 1;
807
808 err:
809 if (ctx != NULL) {
810 BN_CTX_end(ctx);
811 BN_CTX_free(ctx);
812 }
813 if (blinding != NULL) {
814 rsa_blinding_release(rsa, blinding, blinding_index);
815 }
816
817 return ret;
818 }
819
820 // mod_montgomery sets |r| to |I| mod |p|. |I| must already be fully reduced
821 // modulo |p| times |q|. It returns one on success and zero on error.
mod_montgomery(BIGNUM * r,const BIGNUM * I,const BIGNUM * p,const BN_MONT_CTX * mont_p,const BIGNUM * q,BN_CTX * ctx)822 static int mod_montgomery(BIGNUM *r, const BIGNUM *I, const BIGNUM *p,
823 const BN_MONT_CTX *mont_p, const BIGNUM *q,
824 BN_CTX *ctx) {
825 // Reducing in constant-time with Montgomery reduction requires I <= p * R. We
826 // have I < p * q, so this follows if q < R. The caller should have checked
827 // this already.
828 if (!bn_less_than_montgomery_R(q, mont_p)) {
829 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
830 return 0;
831 }
832
833 if (// Reduce mod p with Montgomery reduction. This computes I * R^-1 mod p.
834 !BN_from_montgomery(r, I, mont_p, ctx) ||
835 // Multiply by R^2 and do another Montgomery reduction to compute
836 // I * R^-1 * R^2 * R^-1 = I mod p.
837 !BN_to_montgomery(r, r, mont_p, ctx)) {
838 return 0;
839 }
840
841 // By precomputing R^3 mod p (normally |BN_MONT_CTX| only uses R^2 mod p) and
842 // adjusting the API for |BN_mod_exp_mont_consttime|, we could instead compute
843 // I * R mod p here and save a reduction per prime. But this would require
844 // changing the RSAZ code and may not be worth it. Note that the RSAZ code
845 // uses a different radix, so it uses R' = 2^1044. There we'd actually want
846 // R^2 * R', and would futher benefit from a precomputed R'^2. It currently
847 // converts |mont_p->RR| to R'^2.
848 return 1;
849 }
850
mod_exp(BIGNUM * r0,const BIGNUM * I,RSA * rsa,BN_CTX * ctx)851 static int mod_exp(BIGNUM *r0, const BIGNUM *I, RSA *rsa, BN_CTX *ctx) {
852 assert(ctx != NULL);
853
854 assert(rsa->n != NULL);
855 assert(rsa->e != NULL);
856 assert(rsa->d != NULL);
857 assert(rsa->p != NULL);
858 assert(rsa->q != NULL);
859 assert(rsa->dmp1 != NULL);
860 assert(rsa->dmq1 != NULL);
861 assert(rsa->iqmp != NULL);
862
863 BIGNUM *r1, *m1;
864 int ret = 0;
865
866 BN_CTX_start(ctx);
867 r1 = BN_CTX_get(ctx);
868 m1 = BN_CTX_get(ctx);
869 if (r1 == NULL ||
870 m1 == NULL) {
871 goto err;
872 }
873
874 if (!freeze_private_key(rsa, ctx)) {
875 goto err;
876 }
877
878 // Implementing RSA with CRT in constant-time is sensitive to which prime is
879 // larger. Canonicalize fields so that |p| is the larger prime.
880 const BIGNUM *dmp1 = rsa->dmp1_fixed, *dmq1 = rsa->dmq1_fixed;
881 const BN_MONT_CTX *mont_p = rsa->mont_p, *mont_q = rsa->mont_q;
882 if (BN_cmp(rsa->p, rsa->q) < 0) {
883 mont_p = rsa->mont_q;
884 mont_q = rsa->mont_p;
885 dmp1 = rsa->dmq1_fixed;
886 dmq1 = rsa->dmp1_fixed;
887 }
888
889 // Use the minimal-width versions of |n|, |p|, and |q|. Either works, but if
890 // someone gives us non-minimal values, these will be slightly more efficient
891 // on the non-Montgomery operations.
892 const BIGNUM *n = &rsa->mont_n->N;
893 const BIGNUM *p = &mont_p->N;
894 const BIGNUM *q = &mont_q->N;
895
896 // This is a pre-condition for |mod_montgomery|. It was already checked by the
897 // caller.
898 assert(BN_ucmp(I, n) < 0);
899
900 if (// |m1| is the result modulo |q|.
901 !mod_montgomery(r1, I, q, mont_q, p, ctx) ||
902 !BN_mod_exp_mont_consttime(m1, r1, dmq1, q, ctx, mont_q) ||
903 // |r0| is the result modulo |p|.
904 !mod_montgomery(r1, I, p, mont_p, q, ctx) ||
905 !BN_mod_exp_mont_consttime(r0, r1, dmp1, p, ctx, mont_p) ||
906 // Compute r0 = r0 - m1 mod p. |p| is the larger prime, so |m1| is already
907 // fully reduced mod |p|.
908 !bn_mod_sub_consttime(r0, r0, m1, p, ctx) ||
909 // r0 = r0 * iqmp mod p. We use Montgomery multiplication to compute this
910 // in constant time. |inv_small_mod_large_mont| is in Montgomery form and
911 // r0 is not, so the result is taken out of Montgomery form.
912 !BN_mod_mul_montgomery(r0, r0, rsa->inv_small_mod_large_mont, mont_p,
913 ctx) ||
914 // r0 = r0 * q + m1 gives the final result. Reducing modulo q gives m1, so
915 // it is correct mod p. Reducing modulo p gives (r0-m1)*iqmp*q + m1 = r0,
916 // so it is correct mod q. Finally, the result is bounded by [m1, n + m1),
917 // and the result is at least |m1|, so this must be the unique answer in
918 // [0, n).
919 !bn_mul_consttime(r0, r0, q, ctx) ||
920 !bn_uadd_consttime(r0, r0, m1) ||
921 // The result should be bounded by |n|, but fixed-width operations may
922 // bound the width slightly higher, so fix it.
923 !bn_resize_words(r0, n->width)) {
924 goto err;
925 }
926
927 ret = 1;
928
929 err:
930 BN_CTX_end(ctx);
931 return ret;
932 }
933
ensure_bignum(BIGNUM ** out)934 static int ensure_bignum(BIGNUM **out) {
935 if (*out == NULL) {
936 *out = BN_new();
937 }
938 return *out != NULL;
939 }
940
941 // kBoringSSLRSASqrtTwo is the BIGNUM representation of ⌊2¹⁵³⁵×√2⌋. This is
942 // chosen to give enough precision for 3072-bit RSA, the largest key size FIPS
943 // specifies. Key sizes beyond this will round up.
944 //
945 // To verify this number, check that n² < 2³⁰⁷¹ < (n+1)², where n is value
946 // represented here. Note the components are listed in little-endian order. Here
947 // is some sample Python code to check:
948 //
949 // >>> TOBN = lambda a, b: a << 32 | b
950 // >>> l = [ <paste the contents of kSqrtTwo> ]
951 // >>> n = sum(a * 2**(64*i) for i, a in enumerate(l))
952 // >>> n**2 < 2**3071 < (n+1)**2
953 // True
954 const BN_ULONG kBoringSSLRSASqrtTwo[] = {
955 TOBN(0xdea06241, 0xf7aa81c2), TOBN(0xf6a1be3f, 0xca221307),
956 TOBN(0x332a5e9f, 0x7bda1ebf), TOBN(0x0104dc01, 0xfe32352f),
957 TOBN(0xb8cf341b, 0x6f8236c7), TOBN(0x4264dabc, 0xd528b651),
958 TOBN(0xf4d3a02c, 0xebc93e0c), TOBN(0x81394ab6, 0xd8fd0efd),
959 TOBN(0xeaa4a089, 0x9040ca4a), TOBN(0xf52f120f, 0x836e582e),
960 TOBN(0xcb2a6343, 0x31f3c84d), TOBN(0xc6d5a8a3, 0x8bb7e9dc),
961 TOBN(0x460abc72, 0x2f7c4e33), TOBN(0xcab1bc91, 0x1688458a),
962 TOBN(0x53059c60, 0x11bc337b), TOBN(0xd2202e87, 0x42af1f4e),
963 TOBN(0x78048736, 0x3dfa2768), TOBN(0x0f74a85e, 0x439c7b4a),
964 TOBN(0xa8b1fe6f, 0xdc83db39), TOBN(0x4afc8304, 0x3ab8a2c3),
965 TOBN(0xed17ac85, 0x83339915), TOBN(0x1d6f60ba, 0x893ba84c),
966 TOBN(0x597d89b3, 0x754abe9f), TOBN(0xb504f333, 0xf9de6484),
967 };
968 const size_t kBoringSSLRSASqrtTwoLen = OPENSSL_ARRAY_SIZE(kBoringSSLRSASqrtTwo);
969
970 // generate_prime sets |out| to a prime with length |bits| such that |out|-1 is
971 // relatively prime to |e|. If |p| is non-NULL, |out| will also not be close to
972 // |p|. |sqrt2| must be ⌊2^(bits-1)×√2⌋ (or a slightly overestimate for large
973 // sizes), and |pow2_bits_100| must be 2^(bits-100).
974 //
975 // This function fails with probability around 2^-21.
generate_prime(BIGNUM * out,int bits,const BIGNUM * e,const BIGNUM * p,const BIGNUM * sqrt2,const BIGNUM * pow2_bits_100,BN_CTX * ctx,BN_GENCB * cb)976 static int generate_prime(BIGNUM *out, int bits, const BIGNUM *e,
977 const BIGNUM *p, const BIGNUM *sqrt2,
978 const BIGNUM *pow2_bits_100, BN_CTX *ctx,
979 BN_GENCB *cb) {
980 if (bits < 128 || (bits % BN_BITS2) != 0) {
981 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
982 return 0;
983 }
984 assert(BN_is_pow2(pow2_bits_100));
985 assert(BN_is_bit_set(pow2_bits_100, bits - 100));
986
987 // See FIPS 186-4 appendix B.3.3, steps 4 and 5. Note |bits| here is nlen/2.
988
989 // Use the limit from steps 4.7 and 5.8 for most values of |e|. When |e| is 3,
990 // the 186-4 limit is too low, so we use a higher one. Note this case is not
991 // reachable from |RSA_generate_key_fips|.
992 //
993 // |limit| determines the failure probability. We must find a prime that is
994 // not 1 mod |e|. By the prime number theorem, we'll find one with probability
995 // p = (e-1)/e * 2/(ln(2)*bits). Note the second term is doubled because we
996 // discard even numbers.
997 //
998 // The failure probability is thus (1-p)^limit. To convert that to a power of
999 // two, we take logs. -log_2((1-p)^limit) = -limit * ln(1-p) / ln(2).
1000 //
1001 // >>> def f(bits, e, limit):
1002 // ... p = (e-1.0)/e * 2.0/(math.log(2)*bits)
1003 // ... return -limit * math.log(1 - p) / math.log(2)
1004 // ...
1005 // >>> f(1024, 65537, 5*1024)
1006 // 20.842750558272634
1007 // >>> f(1536, 65537, 5*1536)
1008 // 20.83294549602474
1009 // >>> f(2048, 65537, 5*2048)
1010 // 20.828047576234948
1011 // >>> f(1024, 3, 8*1024)
1012 // 22.222147925962307
1013 // >>> f(1536, 3, 8*1536)
1014 // 22.21518251065506
1015 // >>> f(2048, 3, 8*2048)
1016 // 22.211701985875937
1017 if (bits >= INT_MAX/32) {
1018 OPENSSL_PUT_ERROR(RSA, RSA_R_MODULUS_TOO_LARGE);
1019 return 0;
1020 }
1021 int limit = BN_is_word(e, 3) ? bits * 8 : bits * 5;
1022
1023 int ret = 0, tries = 0, rand_tries = 0;
1024 BN_CTX_start(ctx);
1025 BIGNUM *tmp = BN_CTX_get(ctx);
1026 if (tmp == NULL) {
1027 goto err;
1028 }
1029
1030 for (;;) {
1031 // Generate a random number of length |bits| where the bottom bit is set
1032 // (steps 4.2, 4.3, 5.2 and 5.3) and the top bit is set (implied by the
1033 // bound checked below in steps 4.4 and 5.5).
1034 if (!BN_rand(out, bits, BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ODD) ||
1035 !BN_GENCB_call(cb, BN_GENCB_GENERATED, rand_tries++)) {
1036 goto err;
1037 }
1038
1039 if (p != NULL) {
1040 // If |p| and |out| are too close, try again (step 5.4).
1041 if (!bn_abs_sub_consttime(tmp, out, p, ctx)) {
1042 goto err;
1043 }
1044 if (BN_cmp(tmp, pow2_bits_100) <= 0) {
1045 continue;
1046 }
1047 }
1048
1049 // If out < 2^(bits-1)×√2, try again (steps 4.4 and 5.5). This is equivalent
1050 // to out <= ⌊2^(bits-1)×√2⌋, or out <= sqrt2 for FIPS key sizes.
1051 //
1052 // For larger keys, the comparison is approximate, leaning towards
1053 // retrying. That is, we reject a negligible fraction of primes that are
1054 // within the FIPS bound, but we will never accept a prime outside the
1055 // bound, ensuring the resulting RSA key is the right size.
1056 if (BN_cmp(out, sqrt2) <= 0) {
1057 continue;
1058 }
1059
1060 // RSA key generation's bottleneck is discarding composites. If it fails
1061 // trial division, do not bother computing a GCD or performing Miller-Rabin.
1062 if (!bn_odd_number_is_obviously_composite(out)) {
1063 // Check gcd(out-1, e) is one (steps 4.5 and 5.6).
1064 int relatively_prime;
1065 if (!BN_sub(tmp, out, BN_value_one()) ||
1066 !bn_is_relatively_prime(&relatively_prime, tmp, e, ctx)) {
1067 goto err;
1068 }
1069 if (relatively_prime) {
1070 // Test |out| for primality (steps 4.5.1 and 5.6.1).
1071 int is_probable_prime;
1072 if (!BN_primality_test(&is_probable_prime, out,
1073 BN_prime_checks_for_generation, ctx, 0, cb)) {
1074 goto err;
1075 }
1076 if (is_probable_prime) {
1077 ret = 1;
1078 goto err;
1079 }
1080 }
1081 }
1082
1083 // If we've tried too many times to find a prime, abort (steps 4.7 and
1084 // 5.8).
1085 tries++;
1086 if (tries >= limit) {
1087 OPENSSL_PUT_ERROR(RSA, RSA_R_TOO_MANY_ITERATIONS);
1088 goto err;
1089 }
1090 if (!BN_GENCB_call(cb, 2, tries)) {
1091 goto err;
1092 }
1093 }
1094
1095 err:
1096 BN_CTX_end(ctx);
1097 return ret;
1098 }
1099
1100 // rsa_generate_key_impl generates an RSA key using a generalized version of
1101 // FIPS 186-4 appendix B.3. |RSA_generate_key_fips| performs additional checks
1102 // for FIPS-compliant key generation.
1103 //
1104 // This function returns one on success and zero on failure. It has a failure
1105 // probability of about 2^-20.
rsa_generate_key_impl(RSA * rsa,int bits,const BIGNUM * e_value,BN_GENCB * cb)1106 static int rsa_generate_key_impl(RSA *rsa, int bits, const BIGNUM *e_value,
1107 BN_GENCB *cb) {
1108 // See FIPS 186-4 appendix B.3. This function implements a generalized version
1109 // of the FIPS algorithm. |RSA_generate_key_fips| performs additional checks
1110 // for FIPS-compliant key generation.
1111
1112 // Always generate RSA keys which are a multiple of 128 bits. Round |bits|
1113 // down as needed.
1114 bits &= ~127;
1115
1116 // Reject excessively small keys.
1117 if (bits < 256) {
1118 OPENSSL_PUT_ERROR(RSA, RSA_R_KEY_SIZE_TOO_SMALL);
1119 return 0;
1120 }
1121
1122 // Reject excessively large public exponents. Windows CryptoAPI and Go don't
1123 // support values larger than 32 bits, so match their limits for generating
1124 // keys. (|check_modulus_and_exponent_sizes| uses a slightly more conservative
1125 // value, but we don't need to support generating such keys.)
1126 // https://github.com/golang/go/issues/3161
1127 // https://msdn.microsoft.com/en-us/library/aa387685(VS.85).aspx
1128 if (BN_num_bits(e_value) > 32) {
1129 OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_E_VALUE);
1130 return 0;
1131 }
1132
1133 int ret = 0;
1134 int prime_bits = bits / 2;
1135 BN_CTX *ctx = BN_CTX_new();
1136 if (ctx == NULL) {
1137 goto bn_err;
1138 }
1139 BN_CTX_start(ctx);
1140 BIGNUM *totient = BN_CTX_get(ctx);
1141 BIGNUM *pm1 = BN_CTX_get(ctx);
1142 BIGNUM *qm1 = BN_CTX_get(ctx);
1143 BIGNUM *sqrt2 = BN_CTX_get(ctx);
1144 BIGNUM *pow2_prime_bits_100 = BN_CTX_get(ctx);
1145 BIGNUM *pow2_prime_bits = BN_CTX_get(ctx);
1146 if (totient == NULL || pm1 == NULL || qm1 == NULL || sqrt2 == NULL ||
1147 pow2_prime_bits_100 == NULL || pow2_prime_bits == NULL ||
1148 !BN_set_bit(pow2_prime_bits_100, prime_bits - 100) ||
1149 !BN_set_bit(pow2_prime_bits, prime_bits)) {
1150 goto bn_err;
1151 }
1152
1153 // We need the RSA components non-NULL.
1154 if (!ensure_bignum(&rsa->n) ||
1155 !ensure_bignum(&rsa->d) ||
1156 !ensure_bignum(&rsa->e) ||
1157 !ensure_bignum(&rsa->p) ||
1158 !ensure_bignum(&rsa->q) ||
1159 !ensure_bignum(&rsa->dmp1) ||
1160 !ensure_bignum(&rsa->dmq1)) {
1161 goto bn_err;
1162 }
1163
1164 if (!BN_copy(rsa->e, e_value)) {
1165 goto bn_err;
1166 }
1167
1168 // Compute sqrt2 >= ⌊2^(prime_bits-1)×√2⌋.
1169 if (!bn_set_words(sqrt2, kBoringSSLRSASqrtTwo, kBoringSSLRSASqrtTwoLen)) {
1170 goto bn_err;
1171 }
1172 int sqrt2_bits = kBoringSSLRSASqrtTwoLen * BN_BITS2;
1173 assert(sqrt2_bits == (int)BN_num_bits(sqrt2));
1174 if (sqrt2_bits > prime_bits) {
1175 // For key sizes up to 3072 (prime_bits = 1536), this is exactly
1176 // ⌊2^(prime_bits-1)×√2⌋.
1177 if (!BN_rshift(sqrt2, sqrt2, sqrt2_bits - prime_bits)) {
1178 goto bn_err;
1179 }
1180 } else if (prime_bits > sqrt2_bits) {
1181 // For key sizes beyond 3072, this is approximate. We err towards retrying
1182 // to ensure our key is the right size and round up.
1183 if (!BN_add_word(sqrt2, 1) ||
1184 !BN_lshift(sqrt2, sqrt2, prime_bits - sqrt2_bits)) {
1185 goto bn_err;
1186 }
1187 }
1188 assert(prime_bits == (int)BN_num_bits(sqrt2));
1189
1190 do {
1191 // Generate p and q, each of size |prime_bits|, using the steps outlined in
1192 // appendix FIPS 186-4 appendix B.3.3.
1193 //
1194 // Each call to |generate_prime| fails with probability p = 2^-21. The
1195 // probability that either call fails is 1 - (1-p)^2, which is around 2^-20.
1196 if (!generate_prime(rsa->p, prime_bits, rsa->e, NULL, sqrt2,
1197 pow2_prime_bits_100, ctx, cb) ||
1198 !BN_GENCB_call(cb, 3, 0) ||
1199 !generate_prime(rsa->q, prime_bits, rsa->e, rsa->p, sqrt2,
1200 pow2_prime_bits_100, ctx, cb) ||
1201 !BN_GENCB_call(cb, 3, 1)) {
1202 goto bn_err;
1203 }
1204
1205 if (BN_cmp(rsa->p, rsa->q) < 0) {
1206 BIGNUM *tmp = rsa->p;
1207 rsa->p = rsa->q;
1208 rsa->q = tmp;
1209 }
1210
1211 // Calculate d = e^(-1) (mod lcm(p-1, q-1)), per FIPS 186-4. This differs
1212 // from typical RSA implementations which use (p-1)*(q-1).
1213 //
1214 // Note this means the size of d might reveal information about p-1 and
1215 // q-1. However, we do operations with Chinese Remainder Theorem, so we only
1216 // use d (mod p-1) and d (mod q-1) as exponents. Using a minimal totient
1217 // does not affect those two values.
1218 int no_inverse;
1219 if (!bn_usub_consttime(pm1, rsa->p, BN_value_one()) ||
1220 !bn_usub_consttime(qm1, rsa->q, BN_value_one()) ||
1221 !bn_lcm_consttime(totient, pm1, qm1, ctx) ||
1222 !bn_mod_inverse_consttime(rsa->d, &no_inverse, rsa->e, totient, ctx)) {
1223 goto bn_err;
1224 }
1225
1226 // Retry if |rsa->d| <= 2^|prime_bits|. See appendix B.3.1's guidance on
1227 // values for d.
1228 } while (BN_cmp(rsa->d, pow2_prime_bits) <= 0);
1229
1230 if (// Calculate n.
1231 !bn_mul_consttime(rsa->n, rsa->p, rsa->q, ctx) ||
1232 // Calculate d mod (p-1).
1233 !bn_div_consttime(NULL, rsa->dmp1, rsa->d, pm1, ctx) ||
1234 // Calculate d mod (q-1)
1235 !bn_div_consttime(NULL, rsa->dmq1, rsa->d, qm1, ctx)) {
1236 goto bn_err;
1237 }
1238 bn_set_minimal_width(rsa->n);
1239
1240 // Sanity-check that |rsa->n| has the specified size. This is implied by
1241 // |generate_prime|'s bounds.
1242 if (BN_num_bits(rsa->n) != (unsigned)bits) {
1243 OPENSSL_PUT_ERROR(RSA, ERR_R_INTERNAL_ERROR);
1244 goto err;
1245 }
1246
1247 // Call |freeze_private_key| to compute the inverse of q mod p, by way of
1248 // |rsa->mont_p|.
1249 if (!freeze_private_key(rsa, ctx)) {
1250 goto bn_err;
1251 }
1252
1253 // The key generation process is complex and thus error-prone. It could be
1254 // disastrous to generate and then use a bad key so double-check that the key
1255 // makes sense.
1256 if (!RSA_check_key(rsa)) {
1257 OPENSSL_PUT_ERROR(RSA, RSA_R_INTERNAL_ERROR);
1258 goto err;
1259 }
1260
1261 ret = 1;
1262
1263 bn_err:
1264 if (!ret) {
1265 OPENSSL_PUT_ERROR(RSA, ERR_LIB_BN);
1266 }
1267 err:
1268 if (ctx != NULL) {
1269 BN_CTX_end(ctx);
1270 BN_CTX_free(ctx);
1271 }
1272 return ret;
1273 }
1274
replace_bignum(BIGNUM ** out,BIGNUM ** in)1275 static void replace_bignum(BIGNUM **out, BIGNUM **in) {
1276 BN_free(*out);
1277 *out = *in;
1278 *in = NULL;
1279 }
1280
replace_bn_mont_ctx(BN_MONT_CTX ** out,BN_MONT_CTX ** in)1281 static void replace_bn_mont_ctx(BN_MONT_CTX **out, BN_MONT_CTX **in) {
1282 BN_MONT_CTX_free(*out);
1283 *out = *in;
1284 *in = NULL;
1285 }
1286
RSA_generate_key_ex(RSA * rsa,int bits,const BIGNUM * e_value,BN_GENCB * cb)1287 int RSA_generate_key_ex(RSA *rsa, int bits, const BIGNUM *e_value,
1288 BN_GENCB *cb) {
1289 // |rsa_generate_key_impl|'s 2^-20 failure probability is too high at scale,
1290 // so we run the FIPS algorithm four times, bringing it down to 2^-80. We
1291 // should just adjust the retry limit, but FIPS 186-4 prescribes that value
1292 // and thus results in unnecessary complexity.
1293 for (int i = 0; i < 4; i++) {
1294 ERR_clear_error();
1295 // Generate into scratch space, to avoid leaving partial work on failure.
1296 RSA *tmp = RSA_new();
1297 if (tmp == NULL) {
1298 return 0;
1299 }
1300 if (rsa_generate_key_impl(tmp, bits, e_value, cb)) {
1301 replace_bignum(&rsa->n, &tmp->n);
1302 replace_bignum(&rsa->e, &tmp->e);
1303 replace_bignum(&rsa->d, &tmp->d);
1304 replace_bignum(&rsa->p, &tmp->p);
1305 replace_bignum(&rsa->q, &tmp->q);
1306 replace_bignum(&rsa->dmp1, &tmp->dmp1);
1307 replace_bignum(&rsa->dmq1, &tmp->dmq1);
1308 replace_bignum(&rsa->iqmp, &tmp->iqmp);
1309 replace_bn_mont_ctx(&rsa->mont_n, &tmp->mont_n);
1310 replace_bn_mont_ctx(&rsa->mont_p, &tmp->mont_p);
1311 replace_bn_mont_ctx(&rsa->mont_q, &tmp->mont_q);
1312 replace_bignum(&rsa->d_fixed, &tmp->d_fixed);
1313 replace_bignum(&rsa->dmp1_fixed, &tmp->dmp1_fixed);
1314 replace_bignum(&rsa->dmq1_fixed, &tmp->dmq1_fixed);
1315 replace_bignum(&rsa->inv_small_mod_large_mont,
1316 &tmp->inv_small_mod_large_mont);
1317 rsa->private_key_frozen = tmp->private_key_frozen;
1318 RSA_free(tmp);
1319 return 1;
1320 }
1321 uint32_t err = ERR_peek_error();
1322 RSA_free(tmp);
1323 tmp = NULL;
1324 // Only retry on |RSA_R_TOO_MANY_ITERATIONS|. This is so a caller-induced
1325 // failure in |BN_GENCB_call| is still fatal.
1326 if (ERR_GET_LIB(err) != ERR_LIB_RSA ||
1327 ERR_GET_REASON(err) != RSA_R_TOO_MANY_ITERATIONS) {
1328 return 0;
1329 }
1330 }
1331
1332 return 0;
1333 }
1334
RSA_generate_key_fips(RSA * rsa,int bits,BN_GENCB * cb)1335 int RSA_generate_key_fips(RSA *rsa, int bits, BN_GENCB *cb) {
1336 // FIPS 186-4 allows 2048-bit and 3072-bit RSA keys (1024-bit and 1536-bit
1337 // primes, respectively) with the prime generation method we use.
1338 if (bits != 2048 && bits != 3072) {
1339 OPENSSL_PUT_ERROR(RSA, RSA_R_BAD_RSA_PARAMETERS);
1340 return 0;
1341 }
1342
1343 BIGNUM *e = BN_new();
1344 int ret = e != NULL &&
1345 BN_set_word(e, RSA_F4) &&
1346 RSA_generate_key_ex(rsa, bits, e, cb) &&
1347 RSA_check_fips(rsa);
1348 BN_free(e);
1349 return ret;
1350 }
1351
DEFINE_METHOD_FUNCTION(RSA_METHOD,RSA_default_method)1352 DEFINE_METHOD_FUNCTION(RSA_METHOD, RSA_default_method) {
1353 // All of the methods are NULL to make it easier for the compiler/linker to
1354 // drop unused functions. The wrapper functions will select the appropriate
1355 // |rsa_default_*| implementation.
1356 OPENSSL_memset(out, 0, sizeof(RSA_METHOD));
1357 out->common.is_static = 1;
1358 }
1359