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