Coverage Report

Created: 2024-11-21 07:03

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