1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5 /*
6 * RSA key generation, public key op, private key op.
7 */
8 #ifdef FREEBL_NO_DEPEND
9 #include "stubs.h"
10 #endif
11
12 #include "secerr.h"
13
14 #include "prclist.h"
15 #include "nssilock.h"
16 #include "prinit.h"
17 #include "blapi.h"
18 #include "mpi.h"
19 #include "mpprime.h"
20 #include "mplogic.h"
21 #include "secmpi.h"
22 #include "secitem.h"
23 #include "blapii.h"
24
25 /*
26 ** Number of times to attempt to generate a prime (p or q) from a random
27 ** seed (the seed changes for each iteration).
28 */
29 #define MAX_PRIME_GEN_ATTEMPTS 10
30 /*
31 ** Number of times to attempt to generate a key. The primes p and q change
32 ** for each attempt.
33 */
34 #define MAX_KEY_GEN_ATTEMPTS 10
35
36 /* Blinding Parameters max cache size */
37 #define RSA_BLINDING_PARAMS_MAX_CACHE_SIZE 20
38
39 /* exponent should not be greater than modulus */
40 #define BAD_RSA_KEY_SIZE(modLen, expLen) \
41 ((expLen) > (modLen) || (modLen) > RSA_MAX_MODULUS_BITS / 8 || \
42 (expLen) > RSA_MAX_EXPONENT_BITS / 8)
43
44 struct blindingParamsStr;
45 typedef struct blindingParamsStr blindingParams;
46
47 struct blindingParamsStr {
48 blindingParams *next;
49 mp_int f, g; /* blinding parameter */
50 int counter; /* number of remaining uses of (f, g) */
51 };
52
53 /*
54 ** RSABlindingParamsStr
55 **
56 ** For discussion of Paul Kocher's timing attack against an RSA private key
57 ** operation, see http://www.cryptography.com/timingattack/paper.html. The
58 ** countermeasure to this attack, known as blinding, is also discussed in
59 ** the Handbook of Applied Cryptography, 11.118-11.119.
60 */
61 struct RSABlindingParamsStr {
62 /* Blinding-specific parameters */
63 PRCList link; /* link to list of structs */
64 SECItem modulus; /* list element "key" */
65 blindingParams *free, *bp; /* Blinding parameters queue */
66 blindingParams array[RSA_BLINDING_PARAMS_MAX_CACHE_SIZE];
67 };
68 typedef struct RSABlindingParamsStr RSABlindingParams;
69
70 /*
71 ** RSABlindingParamsListStr
72 **
73 ** List of key-specific blinding params. The arena holds the volatile pool
74 ** of memory for each entry and the list itself. The lock is for list
75 ** operations, in this case insertions and iterations, as well as control
76 ** of the counter for each set of blinding parameters.
77 */
78 struct RSABlindingParamsListStr {
79 PZLock *lock; /* Lock for the list */
80 PRCondVar *cVar; /* Condidtion Variable */
81 int waitCount; /* Number of threads waiting on cVar */
82 PRCList head; /* Pointer to the list */
83 };
84
85 /*
86 ** The master blinding params list.
87 */
88 static struct RSABlindingParamsListStr blindingParamsList = { 0 };
89
90 /* Number of times to reuse (f, g). Suggested by Paul Kocher */
91 #define RSA_BLINDING_PARAMS_MAX_REUSE 50
92
93 /* Global, allows optional use of blinding. On by default. */
94 /* Cannot be changed at the moment, due to thread-safety issues. */
95 static PRBool nssRSAUseBlinding = PR_TRUE;
96
97 static SECStatus
rsa_build_from_primes(const mp_int * p,const mp_int * q,mp_int * e,PRBool needPublicExponent,mp_int * d,PRBool needPrivateExponent,RSAPrivateKey * key,unsigned int keySizeInBits)98 rsa_build_from_primes(const mp_int *p, const mp_int *q,
99 mp_int *e, PRBool needPublicExponent,
100 mp_int *d, PRBool needPrivateExponent,
101 RSAPrivateKey *key, unsigned int keySizeInBits)
102 {
103 mp_int n, phi;
104 mp_int psub1, qsub1, tmp;
105 mp_err err = MP_OKAY;
106 SECStatus rv = SECSuccess;
107 MP_DIGITS(&n) = 0;
108 MP_DIGITS(&phi) = 0;
109 MP_DIGITS(&psub1) = 0;
110 MP_DIGITS(&qsub1) = 0;
111 MP_DIGITS(&tmp) = 0;
112 CHECK_MPI_OK(mp_init(&n));
113 CHECK_MPI_OK(mp_init(&phi));
114 CHECK_MPI_OK(mp_init(&psub1));
115 CHECK_MPI_OK(mp_init(&qsub1));
116 CHECK_MPI_OK(mp_init(&tmp));
117 /* p and q must be distinct. */
118 if (mp_cmp(p, q) == 0) {
119 PORT_SetError(SEC_ERROR_NEED_RANDOM);
120 rv = SECFailure;
121 goto cleanup;
122 }
123 /* 1. Compute n = p*q */
124 CHECK_MPI_OK(mp_mul(p, q, &n));
125 /* verify that the modulus has the desired number of bits */
126 if ((unsigned)mpl_significant_bits(&n) != keySizeInBits) {
127 PORT_SetError(SEC_ERROR_NEED_RANDOM);
128 rv = SECFailure;
129 goto cleanup;
130 }
131
132 /* at least one exponent must be given */
133 PORT_Assert(!(needPublicExponent && needPrivateExponent));
134
135 /* 2. Compute phi = (p-1)*(q-1) */
136 CHECK_MPI_OK(mp_sub_d(p, 1, &psub1));
137 CHECK_MPI_OK(mp_sub_d(q, 1, &qsub1));
138 if (needPublicExponent || needPrivateExponent) {
139 CHECK_MPI_OK(mp_lcm(&psub1, &qsub1, &phi));
140 /* 3. Compute d = e**-1 mod(phi) */
141 /* or e = d**-1 mod(phi) as necessary */
142 if (needPublicExponent) {
143 err = mp_invmod(d, &phi, e);
144 } else {
145 err = mp_invmod(e, &phi, d);
146 }
147 } else {
148 err = MP_OKAY;
149 }
150 /* Verify that phi(n) and e have no common divisors */
151 if (err != MP_OKAY) {
152 if (err == MP_UNDEF) {
153 PORT_SetError(SEC_ERROR_NEED_RANDOM);
154 err = MP_OKAY; /* to keep PORT_SetError from being called again */
155 rv = SECFailure;
156 }
157 goto cleanup;
158 }
159
160 /* 4. Compute exponent1 = d mod (p-1) */
161 CHECK_MPI_OK(mp_mod(d, &psub1, &tmp));
162 MPINT_TO_SECITEM(&tmp, &key->exponent1, key->arena);
163 /* 5. Compute exponent2 = d mod (q-1) */
164 CHECK_MPI_OK(mp_mod(d, &qsub1, &tmp));
165 MPINT_TO_SECITEM(&tmp, &key->exponent2, key->arena);
166 /* 6. Compute coefficient = q**-1 mod p */
167 CHECK_MPI_OK(mp_invmod(q, p, &tmp));
168 MPINT_TO_SECITEM(&tmp, &key->coefficient, key->arena);
169
170 /* copy our calculated results, overwrite what is there */
171 key->modulus.data = NULL;
172 MPINT_TO_SECITEM(&n, &key->modulus, key->arena);
173 key->privateExponent.data = NULL;
174 MPINT_TO_SECITEM(d, &key->privateExponent, key->arena);
175 key->publicExponent.data = NULL;
176 MPINT_TO_SECITEM(e, &key->publicExponent, key->arena);
177 key->prime1.data = NULL;
178 MPINT_TO_SECITEM(p, &key->prime1, key->arena);
179 key->prime2.data = NULL;
180 MPINT_TO_SECITEM(q, &key->prime2, key->arena);
181 cleanup:
182 mp_clear(&n);
183 mp_clear(&phi);
184 mp_clear(&psub1);
185 mp_clear(&qsub1);
186 mp_clear(&tmp);
187 if (err) {
188 MP_TO_SEC_ERROR(err);
189 rv = SECFailure;
190 }
191 return rv;
192 }
193
194 SECStatus
generate_prime(mp_int * prime,int primeLen)195 generate_prime(mp_int *prime, int primeLen)
196 {
197 mp_err err = MP_OKAY;
198 SECStatus rv = SECSuccess;
199 int piter;
200 unsigned char *pb = NULL;
201 pb = PORT_Alloc(primeLen);
202 if (!pb) {
203 PORT_SetError(SEC_ERROR_NO_MEMORY);
204 goto cleanup;
205 }
206 for (piter = 0; piter < MAX_PRIME_GEN_ATTEMPTS; piter++) {
207 CHECK_SEC_OK(RNG_GenerateGlobalRandomBytes(pb, primeLen));
208 pb[0] |= 0xC0; /* set two high-order bits */
209 pb[primeLen - 1] |= 0x01; /* set low-order bit */
210 CHECK_MPI_OK(mp_read_unsigned_octets(prime, pb, primeLen));
211 err = mpp_make_prime(prime, primeLen * 8, PR_FALSE);
212 if (err != MP_NO)
213 goto cleanup;
214 /* keep going while err == MP_NO */
215 }
216 cleanup:
217 if (pb)
218 PORT_ZFree(pb, primeLen);
219 if (err) {
220 MP_TO_SEC_ERROR(err);
221 rv = SECFailure;
222 }
223 return rv;
224 }
225
226 /*
227 * make sure the key components meet fips186 requirements.
228 */
229 static PRBool
rsa_fips186_verify(mp_int * p,mp_int * q,mp_int * d,int keySizeInBits)230 rsa_fips186_verify(mp_int *p, mp_int *q, mp_int *d, int keySizeInBits)
231 {
232 mp_int pq_diff;
233 mp_err err = MP_OKAY;
234 PRBool ret = PR_FALSE;
235
236 if (keySizeInBits < 250) {
237 /* not a valid FIPS length, no point in our other tests */
238 /* if you are here, and in FIPS mode, you are outside the security
239 * policy */
240 return PR_TRUE;
241 }
242
243 /* p & q are already known to be greater then sqrt(2)*2^(keySize/2-1) */
244 /* we also know that gcd(p-1,e) = 1 and gcd(q-1,e) = 1 because the
245 * mp_invmod() function will fail. */
246 /* now check p-q > 2^(keysize/2-100) */
247 MP_DIGITS(&pq_diff) = 0;
248 CHECK_MPI_OK(mp_init(&pq_diff));
249 /* NSS always has p > q, so we know pq_diff is positive */
250 CHECK_MPI_OK(mp_sub(p, q, &pq_diff));
251 if ((unsigned)mpl_significant_bits(&pq_diff) < (keySizeInBits / 2 - 100)) {
252 goto cleanup;
253 }
254 /* now verify d is large enough*/
255 if ((unsigned)mpl_significant_bits(d) < (keySizeInBits / 2)) {
256 goto cleanup;
257 }
258 ret = PR_TRUE;
259
260 cleanup:
261 mp_clear(&pq_diff);
262 return ret;
263 }
264
265 /*
266 ** Generate and return a new RSA public and private key.
267 ** Both keys are encoded in a single RSAPrivateKey structure.
268 ** "cx" is the random number generator context
269 ** "keySizeInBits" is the size of the key to be generated, in bits.
270 ** 512, 1024, etc.
271 ** "publicExponent" when not NULL is a pointer to some data that
272 ** represents the public exponent to use. The data is a byte
273 ** encoded integer, in "big endian" order.
274 */
275 RSAPrivateKey *
RSA_NewKey(int keySizeInBits,SECItem * publicExponent)276 RSA_NewKey(int keySizeInBits, SECItem *publicExponent)
277 {
278 unsigned int primeLen;
279 mp_int p = { 0, 0, 0, NULL };
280 mp_int q = { 0, 0, 0, NULL };
281 mp_int e = { 0, 0, 0, NULL };
282 mp_int d = { 0, 0, 0, NULL };
283 int kiter;
284 int max_attempts;
285 mp_err err = MP_OKAY;
286 SECStatus rv = SECSuccess;
287 int prerr = 0;
288 RSAPrivateKey *key = NULL;
289 PLArenaPool *arena = NULL;
290 /* Require key size to be a multiple of 16 bits. */
291 if (!publicExponent || keySizeInBits % 16 != 0 ||
292 BAD_RSA_KEY_SIZE((unsigned int)keySizeInBits / 8, publicExponent->len)) {
293 PORT_SetError(SEC_ERROR_INVALID_ARGS);
294 return NULL;
295 }
296 /* 1. Set the public exponent and check if it's uneven and greater than 2.*/
297 MP_DIGITS(&e) = 0;
298 CHECK_MPI_OK(mp_init(&e));
299 SECITEM_TO_MPINT(*publicExponent, &e);
300 if (mp_iseven(&e) || !(mp_cmp_d(&e, 2) > 0)) {
301 PORT_SetError(SEC_ERROR_INVALID_ARGS);
302 goto cleanup;
303 }
304 #ifndef NSS_FIPS_DISABLED
305 /* Check that the exponent is not smaller than 65537 */
306 if (mp_cmp_d(&e, 0x10001) < 0) {
307 PORT_SetError(SEC_ERROR_INVALID_ARGS);
308 goto cleanup;
309 }
310 #endif
311
312 /* 2. Allocate arena & key */
313 arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
314 if (!arena) {
315 PORT_SetError(SEC_ERROR_NO_MEMORY);
316 goto cleanup;
317 }
318 key = PORT_ArenaZNew(arena, RSAPrivateKey);
319 if (!key) {
320 PORT_SetError(SEC_ERROR_NO_MEMORY);
321 goto cleanup;
322 }
323 key->arena = arena;
324 /* length of primes p and q (in bytes) */
325 primeLen = keySizeInBits / (2 * PR_BITS_PER_BYTE);
326 MP_DIGITS(&p) = 0;
327 MP_DIGITS(&q) = 0;
328 MP_DIGITS(&d) = 0;
329 CHECK_MPI_OK(mp_init(&p));
330 CHECK_MPI_OK(mp_init(&q));
331 CHECK_MPI_OK(mp_init(&d));
332 /* 3. Set the version number (PKCS1 v1.5 says it should be zero) */
333 SECITEM_AllocItem(arena, &key->version, 1);
334 key->version.data[0] = 0;
335
336 kiter = 0;
337 max_attempts = 5 * (keySizeInBits / 2); /* FIPS 186-4 B.3.3 steps 4.7 and 5.8 */
338 do {
339 PORT_SetError(0);
340 CHECK_SEC_OK(generate_prime(&p, primeLen));
341 CHECK_SEC_OK(generate_prime(&q, primeLen));
342 /* Assure p > q */
343 /* NOTE: PKCS #1 does not require p > q, and NSS doesn't use any
344 * implementation optimization that requires p > q. We can remove
345 * this code in the future.
346 */
347 if (mp_cmp(&p, &q) < 0)
348 mp_exch(&p, &q);
349 /* Attempt to use these primes to generate a key */
350 rv = rsa_build_from_primes(&p, &q,
351 &e, PR_FALSE, /* needPublicExponent=false */
352 &d, PR_TRUE, /* needPrivateExponent=true */
353 key, keySizeInBits);
354 if (rv == SECSuccess) {
355 if (rsa_fips186_verify(&p, &q, &d, keySizeInBits)) {
356 break;
357 }
358 prerr = SEC_ERROR_NEED_RANDOM; /* retry with different values */
359 } else {
360 prerr = PORT_GetError();
361 }
362 kiter++;
363 /* loop until have primes */
364 } while (prerr == SEC_ERROR_NEED_RANDOM && kiter < max_attempts);
365
366 cleanup:
367 mp_clear(&p);
368 mp_clear(&q);
369 mp_clear(&e);
370 mp_clear(&d);
371 if (err) {
372 MP_TO_SEC_ERROR(err);
373 rv = SECFailure;
374 }
375 if (rv && arena) {
376 PORT_FreeArena(arena, PR_TRUE);
377 key = NULL;
378 }
379 return key;
380 }
381
382 mp_err
rsa_is_prime(mp_int * p)383 rsa_is_prime(mp_int *p)
384 {
385 int res;
386
387 /* run a Fermat test */
388 res = mpp_fermat(p, 2);
389 if (res != MP_OKAY) {
390 return res;
391 }
392
393 /* If that passed, run some Miller-Rabin tests */
394 res = mpp_pprime(p, 2);
395 return res;
396 }
397
398 /*
399 * Factorize a RSA modulus n into p and q by using the exponents e and d.
400 *
401 * In: e, d, n
402 * Out: p, q
403 *
404 * See Handbook of Applied Cryptography, 8.2.2(i).
405 *
406 * The algorithm is probabilistic, it is run 64 times and each run has a 50%
407 * chance of succeeding with a runtime of O(log(e*d)).
408 *
409 * The returned p might be smaller than q.
410 */
411 static mp_err
rsa_factorize_n_from_exponents(mp_int * e,mp_int * d,mp_int * p,mp_int * q,mp_int * n)412 rsa_factorize_n_from_exponents(mp_int *e, mp_int *d, mp_int *p, mp_int *q,
413 mp_int *n)
414 {
415 /* lambda is the private modulus: e*d = 1 mod lambda */
416 /* so: e*d - 1 = k*lambda = t*2^s where t is odd */
417 mp_int klambda;
418 mp_int t, onetwentyeight;
419 unsigned long s = 0;
420 unsigned long i;
421
422 /* cand = a^(t * 2^i) mod n, next_cand = a^(t * 2^(i+1)) mod n */
423 mp_int a;
424 mp_int cand;
425 mp_int next_cand;
426
427 mp_int n_minus_one;
428 mp_err err = MP_OKAY;
429
430 MP_DIGITS(&klambda) = 0;
431 MP_DIGITS(&t) = 0;
432 MP_DIGITS(&a) = 0;
433 MP_DIGITS(&cand) = 0;
434 MP_DIGITS(&n_minus_one) = 0;
435 MP_DIGITS(&next_cand) = 0;
436 MP_DIGITS(&onetwentyeight) = 0;
437 CHECK_MPI_OK(mp_init(&klambda));
438 CHECK_MPI_OK(mp_init(&t));
439 CHECK_MPI_OK(mp_init(&a));
440 CHECK_MPI_OK(mp_init(&cand));
441 CHECK_MPI_OK(mp_init(&n_minus_one));
442 CHECK_MPI_OK(mp_init(&next_cand));
443 CHECK_MPI_OK(mp_init(&onetwentyeight));
444
445 mp_set_int(&onetwentyeight, 128);
446
447 /* calculate k*lambda = e*d - 1 */
448 CHECK_MPI_OK(mp_mul(e, d, &klambda));
449 CHECK_MPI_OK(mp_sub_d(&klambda, 1, &klambda));
450
451 /* factorize klambda into t*2^s */
452 CHECK_MPI_OK(mp_copy(&klambda, &t));
453 while (mpp_divis_d(&t, 2) == MP_YES) {
454 CHECK_MPI_OK(mp_div_2(&t, &t));
455 s += 1;
456 }
457
458 /* precompute n_minus_one = n - 1 */
459 CHECK_MPI_OK(mp_copy(n, &n_minus_one));
460 CHECK_MPI_OK(mp_sub_d(&n_minus_one, 1, &n_minus_one));
461
462 /* pick random bases a, each one has a 50% leading to a factorization */
463 CHECK_MPI_OK(mp_set_int(&a, 2));
464 /* The following is equivalent to for (a=2, a <= 128, a+=2) */
465 while (mp_cmp(&a, &onetwentyeight) <= 0) {
466 /* compute the base cand = a^(t * 2^0) [i = 0] */
467 CHECK_MPI_OK(mp_exptmod(&a, &t, n, &cand));
468
469 for (i = 0; i < s; i++) {
470 /* condition 1: skip the base if we hit a trivial factor of n */
471 if (mp_cmp(&cand, &n_minus_one) == 0 || mp_cmp_d(&cand, 1) == 0) {
472 break;
473 }
474
475 /* increase i in a^(t * 2^i) by squaring the number */
476 CHECK_MPI_OK(mp_exptmod_d(&cand, 2, n, &next_cand));
477
478 /* condition 2: a^(t * 2^(i+1)) = 1 mod n */
479 if (mp_cmp_d(&next_cand, 1) == 0) {
480 /* conditions verified, gcd(a^(t * 2^i) - 1, n) is a factor */
481 CHECK_MPI_OK(mp_sub_d(&cand, 1, &cand));
482 CHECK_MPI_OK(mp_gcd(&cand, n, p));
483 if (mp_cmp_d(p, 1) == 0) {
484 CHECK_MPI_OK(mp_add_d(&cand, 1, &cand));
485 break;
486 }
487 CHECK_MPI_OK(mp_div(n, p, q, NULL));
488 goto cleanup;
489 }
490 CHECK_MPI_OK(mp_copy(&next_cand, &cand));
491 }
492
493 CHECK_MPI_OK(mp_add_d(&a, 2, &a));
494 }
495
496 /* if we reach here it's likely (2^64 - 1 / 2^64) that d is wrong */
497 err = MP_RANGE;
498
499 cleanup:
500 mp_clear(&klambda);
501 mp_clear(&t);
502 mp_clear(&a);
503 mp_clear(&cand);
504 mp_clear(&n_minus_one);
505 mp_clear(&next_cand);
506 mp_clear(&onetwentyeight);
507 return err;
508 }
509
510 /*
511 * Try to find the two primes based on 2 exponents plus a prime.
512 *
513 * In: e, d and p.
514 * Out: p,q.
515 *
516 * Step 1, Since d = e**-1 mod phi, we know that d*e == 1 mod phi, or
517 * d*e = 1+k*phi, or d*e-1 = k*phi. since d is less than phi and e is
518 * usually less than d, then k must be an integer between e-1 and 1
519 * (probably on the order of e).
520 * Step 1a, We can divide k*phi by prime-1 and get k*(q-1). This will reduce
521 * the size of our division through the rest of the loop.
522 * Step 2, Loop through the values k=e-1 to 1 looking for k. k should be on
523 * the order or e, and e is typically small. This may take a while for
524 * a large random e. We are looking for a k that divides kphi
525 * evenly. Once we find a k that divides kphi evenly, we assume it
526 * is the true k. It's possible this k is not the 'true' k but has
527 * swapped factors of p-1 and/or q-1. Because of this, we
528 * tentatively continue Steps 3-6 inside this loop, and may return looking
529 * for another k on failure.
530 * Step 3, Calculate our tentative phi=kphi/k. Note: real phi is (p-1)*(q-1).
531 * Step 4a, kphi is k*(q-1), so phi is our tenative q-1. q = phi+1.
532 * If k is correct, q should be the right length and prime.
533 * Step 4b, It's possible q-1 and k could have swapped factors. We now have a
534 * possible solution that meets our criteria. It may not be the only
535 * solution, however, so we keep looking. If we find more than one,
536 * we will fail since we cannot determine which is the correct
537 * solution, and returning the wrong modulus will compromise both
538 * moduli. If no other solution is found, we return the unique solution.
539 *
540 * This will return p & q. q may be larger than p in the case that p was given
541 * and it was the smaller prime.
542 */
543 static mp_err
rsa_get_prime_from_exponents(mp_int * e,mp_int * d,mp_int * p,mp_int * q,mp_int * n,unsigned int keySizeInBits)544 rsa_get_prime_from_exponents(mp_int *e, mp_int *d, mp_int *p, mp_int *q,
545 mp_int *n, unsigned int keySizeInBits)
546 {
547 mp_int kphi; /* k*phi */
548 mp_int k; /* current guess at 'k' */
549 mp_int phi; /* (p-1)(q-1) */
550 mp_int r; /* remainder */
551 mp_int tmp; /* p-1 if p is given */
552 mp_err err = MP_OKAY;
553 unsigned int order_k;
554
555 MP_DIGITS(&kphi) = 0;
556 MP_DIGITS(&phi) = 0;
557 MP_DIGITS(&k) = 0;
558 MP_DIGITS(&r) = 0;
559 MP_DIGITS(&tmp) = 0;
560 CHECK_MPI_OK(mp_init(&kphi));
561 CHECK_MPI_OK(mp_init(&phi));
562 CHECK_MPI_OK(mp_init(&k));
563 CHECK_MPI_OK(mp_init(&r));
564 CHECK_MPI_OK(mp_init(&tmp));
565
566 /* our algorithm looks for a factor k whose maximum size is dependent
567 * on the size of our smallest exponent, which had better be the public
568 * exponent (if it's the private, the key is vulnerable to a brute force
569 * attack).
570 *
571 * since our factor search is linear, we need to limit the maximum
572 * size of the public key. this should not be a problem normally, since
573 * public keys are usually small.
574 *
575 * if we want to handle larger public key sizes, we should have
576 * a version which tries to 'completely' factor k*phi (where completely
577 * means 'factor into primes, or composites with which are products of
578 * large primes). Once we have all the factors, we can sort them out and
579 * try different combinations to form our phi. The risk is if (p-1)/2,
580 * (q-1)/2, and k are all large primes. In any case if the public key
581 * is small (order of 20 some bits), then a linear search for k is
582 * manageable.
583 */
584 if (mpl_significant_bits(e) > 23) {
585 err = MP_RANGE;
586 goto cleanup;
587 }
588
589 /* calculate k*phi = e*d - 1 */
590 CHECK_MPI_OK(mp_mul(e, d, &kphi));
591 CHECK_MPI_OK(mp_sub_d(&kphi, 1, &kphi));
592
593 /* kphi is (e*d)-1, which is the same as k*(p-1)(q-1)
594 * d < (p-1)(q-1), therefor k must be less than e-1
595 * We can narrow down k even more, though. Since p and q are odd and both
596 * have their high bit set, then we know that phi must be on order of
597 * keySizeBits.
598 */
599 order_k = (unsigned)mpl_significant_bits(&kphi) - keySizeInBits;
600
601 /* for (k=kinit; order(k) >= order_k; k--) { */
602 /* k=kinit: k can't be bigger than kphi/2^(keySizeInBits -1) */
603 CHECK_MPI_OK(mp_2expt(&k, keySizeInBits - 1));
604 CHECK_MPI_OK(mp_div(&kphi, &k, &k, NULL));
605 if (mp_cmp(&k, e) >= 0) {
606 /* also can't be bigger then e-1 */
607 CHECK_MPI_OK(mp_sub_d(e, 1, &k));
608 }
609
610 /* calculate our temp value */
611 /* This saves recalculating this value when the k guess is wrong, which
612 * is reasonably frequent. */
613 /* tmp = p-1 (used to calculate q-1= phi/tmp) */
614 CHECK_MPI_OK(mp_sub_d(p, 1, &tmp));
615 CHECK_MPI_OK(mp_div(&kphi, &tmp, &kphi, &r));
616 if (mp_cmp_z(&r) != 0) {
617 /* p-1 doesn't divide kphi, some parameter wasn't correct */
618 err = MP_RANGE;
619 goto cleanup;
620 }
621 mp_zero(q);
622 /* kphi is now k*(q-1) */
623
624 /* rest of the for loop */
625 for (; (err == MP_OKAY) && (mpl_significant_bits(&k) >= order_k);
626 err = mp_sub_d(&k, 1, &k)) {
627 CHECK_MPI_OK(err);
628 /* looking for k as a factor of kphi */
629 CHECK_MPI_OK(mp_div(&kphi, &k, &phi, &r));
630 if (mp_cmp_z(&r) != 0) {
631 /* not a factor, try the next one */
632 continue;
633 }
634 /* we have a possible phi, see if it works */
635 if ((unsigned)mpl_significant_bits(&phi) != keySizeInBits / 2) {
636 /* phi is not the right size */
637 continue;
638 }
639 /* phi should be divisible by 2, since
640 * q is odd and phi=(q-1). */
641 if (mpp_divis_d(&phi, 2) == MP_NO) {
642 /* phi is not divisible by 4 */
643 continue;
644 }
645 /* we now have a candidate for the second prime */
646 CHECK_MPI_OK(mp_add_d(&phi, 1, &tmp));
647
648 /* check to make sure it is prime */
649 err = rsa_is_prime(&tmp);
650 if (err != MP_OKAY) {
651 if (err == MP_NO) {
652 /* No, then we still have the wrong phi */
653 continue;
654 }
655 goto cleanup;
656 }
657 /*
658 * It is possible that we have the wrong phi if
659 * k_guess*(q_guess-1) = k*(q-1) (k and q-1 have swapped factors).
660 * since our q_quess is prime, however. We have found a valid
661 * rsa key because:
662 * q is the correct order of magnitude.
663 * phi = (p-1)(q-1) where p and q are both primes.
664 * e*d mod phi = 1.
665 * There is no way to know from the info given if this is the
666 * original key. We never want to return the wrong key because if
667 * two moduli with the same factor is known, then euclid's gcd
668 * algorithm can be used to find that factor. Even though the
669 * caller didn't pass the original modulus, it doesn't mean the
670 * modulus wasn't known or isn't available somewhere. So to be safe
671 * if we can't be sure we have the right q, we don't return any.
672 *
673 * So to make sure we continue looking for other valid q's. If none
674 * are found, then we can safely return this one, otherwise we just
675 * fail */
676 if (mp_cmp_z(q) != 0) {
677 /* this is the second valid q, don't return either,
678 * just fail */
679 err = MP_RANGE;
680 break;
681 }
682 /* we only have one q so far, save it and if no others are found,
683 * it's safe to return it */
684 CHECK_MPI_OK(mp_copy(&tmp, q));
685 continue;
686 }
687 if ((unsigned)mpl_significant_bits(&k) < order_k) {
688 if (mp_cmp_z(q) == 0) {
689 /* If we get here, something was wrong with the parameters we
690 * were given */
691 err = MP_RANGE;
692 }
693 }
694 cleanup:
695 mp_clear(&kphi);
696 mp_clear(&phi);
697 mp_clear(&k);
698 mp_clear(&r);
699 mp_clear(&tmp);
700 return err;
701 }
702
703 /*
704 * take a private key with only a few elements and fill out the missing pieces.
705 *
706 * All the entries will be overwritten with data allocated out of the arena
707 * If no arena is supplied, one will be created.
708 *
709 * The following fields must be supplied in order for this function
710 * to succeed:
711 * one of either publicExponent or privateExponent
712 * two more of the following 5 parameters.
713 * modulus (n)
714 * prime1 (p)
715 * prime2 (q)
716 * publicExponent (e)
717 * privateExponent (d)
718 *
719 * NOTE: if only the publicExponent, privateExponent, and one prime is given,
720 * then there may be more than one RSA key that matches that combination.
721 *
722 * All parameters will be replaced in the key structure with new parameters
723 * Allocated out of the arena. There is no attempt to free the old structures.
724 * Prime1 will always be greater than prime2 (even if the caller supplies the
725 * smaller prime as prime1 or the larger prime as prime2). The parameters are
726 * not overwritten on failure.
727 *
728 * How it works:
729 * We can generate all the parameters from one of the exponents, plus the
730 * two primes. (rsa_build_key_from_primes)
731 * If we are given one of the exponents and both primes, we are done.
732 * If we are given one of the exponents, the modulus and one prime, we
733 * caclulate the second prime by dividing the modulus by the given
734 * prime, giving us an exponent and 2 primes.
735 * If we are given 2 exponents and one of the primes we calculate
736 * k*phi = d*e-1, where k is an integer less than d which
737 * divides d*e-1. We find factor k so we can isolate phi.
738 * phi = (p-1)(q-1)
739 * We can use phi to find the other prime as follows:
740 * q = (phi/(p-1)) + 1. We now have 2 primes and an exponent.
741 * (NOTE: if more then one prime meets this condition, the operation
742 * will fail. See comments elsewhere in this file about this).
743 * (rsa_get_prime_from_exponents)
744 * If we are given 2 exponents and the modulus we factor the modulus to
745 * get the 2 missing primes (rsa_factorize_n_from_exponents)
746 *
747 */
748 SECStatus
RSA_PopulatePrivateKey(RSAPrivateKey * key)749 RSA_PopulatePrivateKey(RSAPrivateKey *key)
750 {
751 PLArenaPool *arena = NULL;
752 PRBool needPublicExponent = PR_TRUE;
753 PRBool needPrivateExponent = PR_TRUE;
754 PRBool hasModulus = PR_FALSE;
755 unsigned int keySizeInBits = 0;
756 int prime_count = 0;
757 /* standard RSA nominclature */
758 mp_int p, q, e, d, n;
759 /* remainder */
760 mp_int r;
761 mp_err err = 0;
762 SECStatus rv = SECFailure;
763
764 MP_DIGITS(&p) = 0;
765 MP_DIGITS(&q) = 0;
766 MP_DIGITS(&e) = 0;
767 MP_DIGITS(&d) = 0;
768 MP_DIGITS(&n) = 0;
769 MP_DIGITS(&r) = 0;
770 CHECK_MPI_OK(mp_init(&p));
771 CHECK_MPI_OK(mp_init(&q));
772 CHECK_MPI_OK(mp_init(&e));
773 CHECK_MPI_OK(mp_init(&d));
774 CHECK_MPI_OK(mp_init(&n));
775 CHECK_MPI_OK(mp_init(&r));
776
777 /* if the key didn't already have an arena, create one. */
778 if (key->arena == NULL) {
779 arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
780 if (!arena) {
781 goto cleanup;
782 }
783 key->arena = arena;
784 }
785
786 /* load up the known exponents */
787 if (key->publicExponent.data) {
788 SECITEM_TO_MPINT(key->publicExponent, &e);
789 needPublicExponent = PR_FALSE;
790 }
791 if (key->privateExponent.data) {
792 SECITEM_TO_MPINT(key->privateExponent, &d);
793 needPrivateExponent = PR_FALSE;
794 }
795 if (needPrivateExponent && needPublicExponent) {
796 /* Not enough information, we need at least one exponent */
797 err = MP_BADARG;
798 goto cleanup;
799 }
800
801 /* load up the known primes. If only one prime is given, it will be
802 * assigned 'p'. Once we have both primes, well make sure p is the larger.
803 * The value prime_count tells us howe many we have acquired.
804 */
805 if (key->prime1.data) {
806 int primeLen = key->prime1.len;
807 if (key->prime1.data[0] == 0) {
808 primeLen--;
809 }
810 keySizeInBits = primeLen * 2 * PR_BITS_PER_BYTE;
811 SECITEM_TO_MPINT(key->prime1, &p);
812 prime_count++;
813 }
814 if (key->prime2.data) {
815 int primeLen = key->prime2.len;
816 if (key->prime2.data[0] == 0) {
817 primeLen--;
818 }
819 keySizeInBits = primeLen * 2 * PR_BITS_PER_BYTE;
820 SECITEM_TO_MPINT(key->prime2, prime_count ? &q : &p);
821 prime_count++;
822 }
823 /* load up the modulus */
824 if (key->modulus.data) {
825 int modLen = key->modulus.len;
826 if (key->modulus.data[0] == 0) {
827 modLen--;
828 }
829 keySizeInBits = modLen * PR_BITS_PER_BYTE;
830 SECITEM_TO_MPINT(key->modulus, &n);
831 hasModulus = PR_TRUE;
832 }
833 /* if we have the modulus and one prime, calculate the second. */
834 if ((prime_count == 1) && (hasModulus)) {
835 if (mp_div(&n, &p, &q, &r) != MP_OKAY || mp_cmp_z(&r) != 0) {
836 /* p is not a factor or n, fail */
837 err = MP_BADARG;
838 goto cleanup;
839 }
840 prime_count++;
841 }
842
843 /* If we didn't have enough primes try to calculate the primes from
844 * the exponents */
845 if (prime_count < 2) {
846 /* if we don't have at least 2 primes at this point, then we need both
847 * exponents and one prime or a modulus*/
848 if (!needPublicExponent && !needPrivateExponent &&
849 (prime_count > 0)) {
850 CHECK_MPI_OK(rsa_get_prime_from_exponents(&e, &d, &p, &q, &n,
851 keySizeInBits));
852 } else if (!needPublicExponent && !needPrivateExponent && hasModulus) {
853 CHECK_MPI_OK(rsa_factorize_n_from_exponents(&e, &d, &p, &q, &n));
854 } else {
855 /* not enough given parameters to get both primes */
856 err = MP_BADARG;
857 goto cleanup;
858 }
859 }
860
861 /* Assure p > q */
862 /* NOTE: PKCS #1 does not require p > q, and NSS doesn't use any
863 * implementation optimization that requires p > q. We can remove
864 * this code in the future.
865 */
866 if (mp_cmp(&p, &q) < 0)
867 mp_exch(&p, &q);
868
869 /* we now have our 2 primes and at least one exponent, we can fill
870 * in the key */
871 rv = rsa_build_from_primes(&p, &q,
872 &e, needPublicExponent,
873 &d, needPrivateExponent,
874 key, keySizeInBits);
875 cleanup:
876 mp_clear(&p);
877 mp_clear(&q);
878 mp_clear(&e);
879 mp_clear(&d);
880 mp_clear(&n);
881 mp_clear(&r);
882 if (err) {
883 MP_TO_SEC_ERROR(err);
884 rv = SECFailure;
885 }
886 if (rv && arena) {
887 PORT_FreeArena(arena, PR_TRUE);
888 key->arena = NULL;
889 }
890 return rv;
891 }
892
893 static unsigned int
rsa_modulusLen(SECItem * modulus)894 rsa_modulusLen(SECItem *modulus)
895 {
896 unsigned char byteZero = modulus->data[0];
897 unsigned int modLen = modulus->len - !byteZero;
898 return modLen;
899 }
900
901 /*
902 ** Perform a raw public-key operation
903 ** Length of input and output buffers are equal to key's modulus len.
904 */
905 SECStatus
RSA_PublicKeyOp(RSAPublicKey * key,unsigned char * output,const unsigned char * input)906 RSA_PublicKeyOp(RSAPublicKey *key,
907 unsigned char *output,
908 const unsigned char *input)
909 {
910 unsigned int modLen, expLen, offset;
911 mp_int n, e, m, c;
912 mp_err err = MP_OKAY;
913 SECStatus rv = SECSuccess;
914 if (!key || !output || !input) {
915 PORT_SetError(SEC_ERROR_INVALID_ARGS);
916 return SECFailure;
917 }
918 MP_DIGITS(&n) = 0;
919 MP_DIGITS(&e) = 0;
920 MP_DIGITS(&m) = 0;
921 MP_DIGITS(&c) = 0;
922 CHECK_MPI_OK(mp_init(&n));
923 CHECK_MPI_OK(mp_init(&e));
924 CHECK_MPI_OK(mp_init(&m));
925 CHECK_MPI_OK(mp_init(&c));
926 modLen = rsa_modulusLen(&key->modulus);
927 expLen = rsa_modulusLen(&key->publicExponent);
928 /* 1. Obtain public key (n, e) */
929 if (BAD_RSA_KEY_SIZE(modLen, expLen)) {
930 PORT_SetError(SEC_ERROR_INVALID_KEY);
931 rv = SECFailure;
932 goto cleanup;
933 }
934 SECITEM_TO_MPINT(key->modulus, &n);
935 SECITEM_TO_MPINT(key->publicExponent, &e);
936 if (e.used > n.used) {
937 /* exponent should not be greater than modulus */
938 PORT_SetError(SEC_ERROR_INVALID_KEY);
939 rv = SECFailure;
940 goto cleanup;
941 }
942 /* 2. check input out of range (needs to be in range [0..n-1]) */
943 offset = (key->modulus.data[0] == 0) ? 1 : 0; /* may be leading 0 */
944 if (memcmp(input, key->modulus.data + offset, modLen) >= 0) {
945 PORT_SetError(SEC_ERROR_INPUT_LEN);
946 rv = SECFailure;
947 goto cleanup;
948 }
949 /* 2 bis. Represent message as integer in range [0..n-1] */
950 CHECK_MPI_OK(mp_read_unsigned_octets(&m, input, modLen));
951 /* 3. Compute c = m**e mod n */
952 #ifdef USE_MPI_EXPT_D
953 /* XXX see which is faster */
954 if (MP_USED(&e) == 1) {
955 CHECK_MPI_OK(mp_exptmod_d(&m, MP_DIGIT(&e, 0), &n, &c));
956 } else
957 #endif
958 CHECK_MPI_OK(mp_exptmod(&m, &e, &n, &c));
959 /* 4. result c is ciphertext */
960 err = mp_to_fixlen_octets(&c, output, modLen);
961 if (err >= 0)
962 err = MP_OKAY;
963 cleanup:
964 mp_clear(&n);
965 mp_clear(&e);
966 mp_clear(&m);
967 mp_clear(&c);
968 if (err) {
969 MP_TO_SEC_ERROR(err);
970 rv = SECFailure;
971 }
972 return rv;
973 }
974
975 /*
976 ** RSA Private key operation (no CRT).
977 */
978 static SECStatus
rsa_PrivateKeyOpNoCRT(RSAPrivateKey * key,mp_int * m,mp_int * c,mp_int * n,unsigned int modLen)979 rsa_PrivateKeyOpNoCRT(RSAPrivateKey *key, mp_int *m, mp_int *c, mp_int *n,
980 unsigned int modLen)
981 {
982 mp_int d;
983 mp_err err = MP_OKAY;
984 SECStatus rv = SECSuccess;
985 MP_DIGITS(&d) = 0;
986 CHECK_MPI_OK(mp_init(&d));
987 SECITEM_TO_MPINT(key->privateExponent, &d);
988 /* 1. m = c**d mod n */
989 CHECK_MPI_OK(mp_exptmod(c, &d, n, m));
990 cleanup:
991 mp_clear(&d);
992 if (err) {
993 MP_TO_SEC_ERROR(err);
994 rv = SECFailure;
995 }
996 return rv;
997 }
998
999 /*
1000 ** RSA Private key operation using CRT.
1001 */
1002 static SECStatus
rsa_PrivateKeyOpCRTNoCheck(RSAPrivateKey * key,mp_int * m,mp_int * c)1003 rsa_PrivateKeyOpCRTNoCheck(RSAPrivateKey *key, mp_int *m, mp_int *c)
1004 {
1005 mp_int p, q, d_p, d_q, qInv;
1006 mp_int m1, m2, h, ctmp;
1007 mp_err err = MP_OKAY;
1008 SECStatus rv = SECSuccess;
1009 MP_DIGITS(&p) = 0;
1010 MP_DIGITS(&q) = 0;
1011 MP_DIGITS(&d_p) = 0;
1012 MP_DIGITS(&d_q) = 0;
1013 MP_DIGITS(&qInv) = 0;
1014 MP_DIGITS(&m1) = 0;
1015 MP_DIGITS(&m2) = 0;
1016 MP_DIGITS(&h) = 0;
1017 MP_DIGITS(&ctmp) = 0;
1018 CHECK_MPI_OK(mp_init(&p));
1019 CHECK_MPI_OK(mp_init(&q));
1020 CHECK_MPI_OK(mp_init(&d_p));
1021 CHECK_MPI_OK(mp_init(&d_q));
1022 CHECK_MPI_OK(mp_init(&qInv));
1023 CHECK_MPI_OK(mp_init(&m1));
1024 CHECK_MPI_OK(mp_init(&m2));
1025 CHECK_MPI_OK(mp_init(&h));
1026 CHECK_MPI_OK(mp_init(&ctmp));
1027 /* copy private key parameters into mp integers */
1028 SECITEM_TO_MPINT(key->prime1, &p); /* p */
1029 SECITEM_TO_MPINT(key->prime2, &q); /* q */
1030 SECITEM_TO_MPINT(key->exponent1, &d_p); /* d_p = d mod (p-1) */
1031 SECITEM_TO_MPINT(key->exponent2, &d_q); /* d_q = d mod (q-1) */
1032 SECITEM_TO_MPINT(key->coefficient, &qInv); /* qInv = q**-1 mod p */
1033 /* 1. m1 = c**d_p mod p */
1034 CHECK_MPI_OK(mp_mod(c, &p, &ctmp));
1035 CHECK_MPI_OK(mp_exptmod(&ctmp, &d_p, &p, &m1));
1036 /* 2. m2 = c**d_q mod q */
1037 CHECK_MPI_OK(mp_mod(c, &q, &ctmp));
1038 CHECK_MPI_OK(mp_exptmod(&ctmp, &d_q, &q, &m2));
1039 /* 3. h = (m1 - m2) * qInv mod p */
1040 CHECK_MPI_OK(mp_submod(&m1, &m2, &p, &h));
1041 CHECK_MPI_OK(mp_mulmod(&h, &qInv, &p, &h));
1042 /* 4. m = m2 + h * q */
1043 CHECK_MPI_OK(mp_mul(&h, &q, m));
1044 CHECK_MPI_OK(mp_add(m, &m2, m));
1045 cleanup:
1046 mp_clear(&p);
1047 mp_clear(&q);
1048 mp_clear(&d_p);
1049 mp_clear(&d_q);
1050 mp_clear(&qInv);
1051 mp_clear(&m1);
1052 mp_clear(&m2);
1053 mp_clear(&h);
1054 mp_clear(&ctmp);
1055 if (err) {
1056 MP_TO_SEC_ERROR(err);
1057 rv = SECFailure;
1058 }
1059 return rv;
1060 }
1061
1062 /*
1063 ** An attack against RSA CRT was described by Boneh, DeMillo, and Lipton in:
1064 ** "On the Importance of Eliminating Errors in Cryptographic Computations",
1065 ** http://theory.stanford.edu/~dabo/papers/faults.ps.gz
1066 **
1067 ** As a defense against the attack, carry out the private key operation,
1068 ** followed up with a public key operation to invert the result.
1069 ** Verify that result against the input.
1070 */
1071 static SECStatus
rsa_PrivateKeyOpCRTCheckedPubKey(RSAPrivateKey * key,mp_int * m,mp_int * c)1072 rsa_PrivateKeyOpCRTCheckedPubKey(RSAPrivateKey *key, mp_int *m, mp_int *c)
1073 {
1074 mp_int n, e, v;
1075 mp_err err = MP_OKAY;
1076 SECStatus rv = SECSuccess;
1077 MP_DIGITS(&n) = 0;
1078 MP_DIGITS(&e) = 0;
1079 MP_DIGITS(&v) = 0;
1080 CHECK_MPI_OK(mp_init(&n));
1081 CHECK_MPI_OK(mp_init(&e));
1082 CHECK_MPI_OK(mp_init(&v));
1083 CHECK_SEC_OK(rsa_PrivateKeyOpCRTNoCheck(key, m, c));
1084 SECITEM_TO_MPINT(key->modulus, &n);
1085 SECITEM_TO_MPINT(key->publicExponent, &e);
1086 /* Perform a public key operation v = m ** e mod n */
1087 CHECK_MPI_OK(mp_exptmod(m, &e, &n, &v));
1088 if (mp_cmp(&v, c) != 0) {
1089 rv = SECFailure;
1090 }
1091 cleanup:
1092 mp_clear(&n);
1093 mp_clear(&e);
1094 mp_clear(&v);
1095 if (err) {
1096 MP_TO_SEC_ERROR(err);
1097 rv = SECFailure;
1098 }
1099 return rv;
1100 }
1101
1102 static PRCallOnceType coBPInit = { 0, 0, 0 };
1103 static PRStatus
init_blinding_params_list(void)1104 init_blinding_params_list(void)
1105 {
1106 blindingParamsList.lock = PZ_NewLock(nssILockOther);
1107 if (!blindingParamsList.lock) {
1108 PORT_SetError(SEC_ERROR_NO_MEMORY);
1109 return PR_FAILURE;
1110 }
1111 blindingParamsList.cVar = PR_NewCondVar(blindingParamsList.lock);
1112 if (!blindingParamsList.cVar) {
1113 PORT_SetError(SEC_ERROR_NO_MEMORY);
1114 return PR_FAILURE;
1115 }
1116 blindingParamsList.waitCount = 0;
1117 PR_INIT_CLIST(&blindingParamsList.head);
1118 return PR_SUCCESS;
1119 }
1120
1121 static SECStatus
generate_blinding_params(RSAPrivateKey * key,mp_int * f,mp_int * g,mp_int * n,unsigned int modLen)1122 generate_blinding_params(RSAPrivateKey *key, mp_int *f, mp_int *g, mp_int *n,
1123 unsigned int modLen)
1124 {
1125 SECStatus rv = SECSuccess;
1126 mp_int e, k;
1127 mp_err err = MP_OKAY;
1128 unsigned char *kb = NULL;
1129
1130 MP_DIGITS(&e) = 0;
1131 MP_DIGITS(&k) = 0;
1132 CHECK_MPI_OK(mp_init(&e));
1133 CHECK_MPI_OK(mp_init(&k));
1134 SECITEM_TO_MPINT(key->publicExponent, &e);
1135 /* generate random k < n */
1136 kb = PORT_Alloc(modLen);
1137 if (!kb) {
1138 PORT_SetError(SEC_ERROR_NO_MEMORY);
1139 goto cleanup;
1140 }
1141 CHECK_SEC_OK(RNG_GenerateGlobalRandomBytes(kb, modLen));
1142 CHECK_MPI_OK(mp_read_unsigned_octets(&k, kb, modLen));
1143 /* k < n */
1144 CHECK_MPI_OK(mp_mod(&k, n, &k));
1145 /* f = k**e mod n */
1146 CHECK_MPI_OK(mp_exptmod(&k, &e, n, f));
1147 /* g = k**-1 mod n */
1148 CHECK_MPI_OK(mp_invmod(&k, n, g));
1149 cleanup:
1150 if (kb)
1151 PORT_ZFree(kb, modLen);
1152 mp_clear(&k);
1153 mp_clear(&e);
1154 if (err) {
1155 MP_TO_SEC_ERROR(err);
1156 rv = SECFailure;
1157 }
1158 return rv;
1159 }
1160
1161 static SECStatus
init_blinding_params(RSABlindingParams * rsabp,RSAPrivateKey * key,mp_int * n,unsigned int modLen)1162 init_blinding_params(RSABlindingParams *rsabp, RSAPrivateKey *key,
1163 mp_int *n, unsigned int modLen)
1164 {
1165 blindingParams *bp = rsabp->array;
1166 int i = 0;
1167
1168 /* Initialize the list pointer for the element */
1169 PR_INIT_CLIST(&rsabp->link);
1170 for (i = 0; i < RSA_BLINDING_PARAMS_MAX_CACHE_SIZE; ++i, ++bp) {
1171 bp->next = bp + 1;
1172 MP_DIGITS(&bp->f) = 0;
1173 MP_DIGITS(&bp->g) = 0;
1174 bp->counter = 0;
1175 }
1176 /* The last bp->next value was initialized with out
1177 * of rsabp->array pointer and must be set to NULL
1178 */
1179 rsabp->array[RSA_BLINDING_PARAMS_MAX_CACHE_SIZE - 1].next = NULL;
1180
1181 bp = rsabp->array;
1182 rsabp->bp = NULL;
1183 rsabp->free = bp;
1184
1185 /* List elements are keyed using the modulus */
1186 return SECITEM_CopyItem(NULL, &rsabp->modulus, &key->modulus);
1187 }
1188
1189 static SECStatus
get_blinding_params(RSAPrivateKey * key,mp_int * n,unsigned int modLen,mp_int * f,mp_int * g)1190 get_blinding_params(RSAPrivateKey *key, mp_int *n, unsigned int modLen,
1191 mp_int *f, mp_int *g)
1192 {
1193 RSABlindingParams *rsabp = NULL;
1194 blindingParams *bpUnlinked = NULL;
1195 blindingParams *bp;
1196 PRCList *el;
1197 SECStatus rv = SECSuccess;
1198 mp_err err = MP_OKAY;
1199 int cmp = -1;
1200 PRBool holdingLock = PR_FALSE;
1201
1202 do {
1203 if (blindingParamsList.lock == NULL) {
1204 PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
1205 return SECFailure;
1206 }
1207 /* Acquire the list lock */
1208 PZ_Lock(blindingParamsList.lock);
1209 holdingLock = PR_TRUE;
1210
1211 /* Walk the list looking for the private key */
1212 for (el = PR_NEXT_LINK(&blindingParamsList.head);
1213 el != &blindingParamsList.head;
1214 el = PR_NEXT_LINK(el)) {
1215 rsabp = (RSABlindingParams *)el;
1216 cmp = SECITEM_CompareItem(&rsabp->modulus, &key->modulus);
1217 if (cmp >= 0) {
1218 /* The key is found or not in the list. */
1219 break;
1220 }
1221 }
1222
1223 if (cmp) {
1224 /* At this point, the key is not in the list. el should point to
1225 ** the list element before which this key should be inserted.
1226 */
1227 rsabp = PORT_ZNew(RSABlindingParams);
1228 if (!rsabp) {
1229 PORT_SetError(SEC_ERROR_NO_MEMORY);
1230 goto cleanup;
1231 }
1232
1233 rv = init_blinding_params(rsabp, key, n, modLen);
1234 if (rv != SECSuccess) {
1235 PORT_ZFree(rsabp, sizeof(RSABlindingParams));
1236 goto cleanup;
1237 }
1238
1239 /* Insert the new element into the list
1240 ** If inserting in the middle of the list, el points to the link
1241 ** to insert before. Otherwise, the link needs to be appended to
1242 ** the end of the list, which is the same as inserting before the
1243 ** head (since el would have looped back to the head).
1244 */
1245 PR_INSERT_BEFORE(&rsabp->link, el);
1246 }
1247
1248 /* We've found (or created) the RSAblindingParams struct for this key.
1249 * Now, search its list of ready blinding params for a usable one.
1250 */
1251 while (0 != (bp = rsabp->bp)) {
1252 #ifndef UNSAFE_FUZZER_MODE
1253 if (--(bp->counter) > 0)
1254 #endif
1255 {
1256 /* Found a match and there are still remaining uses left */
1257 /* Return the parameters */
1258 CHECK_MPI_OK(mp_copy(&bp->f, f));
1259 CHECK_MPI_OK(mp_copy(&bp->g, g));
1260
1261 PZ_Unlock(blindingParamsList.lock);
1262 return SECSuccess;
1263 }
1264 /* exhausted this one, give its values to caller, and
1265 * then retire it.
1266 */
1267 mp_exch(&bp->f, f);
1268 mp_exch(&bp->g, g);
1269 mp_clear(&bp->f);
1270 mp_clear(&bp->g);
1271 bp->counter = 0;
1272 /* Move to free list */
1273 rsabp->bp = bp->next;
1274 bp->next = rsabp->free;
1275 rsabp->free = bp;
1276 /* In case there're threads waiting for new blinding
1277 * value - notify 1 thread the value is ready
1278 */
1279 if (blindingParamsList.waitCount > 0) {
1280 PR_NotifyCondVar(blindingParamsList.cVar);
1281 blindingParamsList.waitCount--;
1282 }
1283 PZ_Unlock(blindingParamsList.lock);
1284 return SECSuccess;
1285 }
1286 /* We did not find a usable set of blinding params. Can we make one? */
1287 /* Find a free bp struct. */
1288 if ((bp = rsabp->free) != NULL) {
1289 /* unlink this bp */
1290 rsabp->free = bp->next;
1291 bp->next = NULL;
1292 bpUnlinked = bp; /* In case we fail */
1293
1294 PZ_Unlock(blindingParamsList.lock);
1295 holdingLock = PR_FALSE;
1296 /* generate blinding parameter values for the current thread */
1297 CHECK_SEC_OK(generate_blinding_params(key, f, g, n, modLen));
1298
1299 /* put the blinding parameter values into cache */
1300 CHECK_MPI_OK(mp_init(&bp->f));
1301 CHECK_MPI_OK(mp_init(&bp->g));
1302 CHECK_MPI_OK(mp_copy(f, &bp->f));
1303 CHECK_MPI_OK(mp_copy(g, &bp->g));
1304
1305 /* Put this at head of queue of usable params. */
1306 PZ_Lock(blindingParamsList.lock);
1307 holdingLock = PR_TRUE;
1308 (void)holdingLock;
1309 /* initialize RSABlindingParamsStr */
1310 bp->counter = RSA_BLINDING_PARAMS_MAX_REUSE;
1311 bp->next = rsabp->bp;
1312 rsabp->bp = bp;
1313 bpUnlinked = NULL;
1314 /* In case there're threads waiting for new blinding value
1315 * just notify them the value is ready
1316 */
1317 if (blindingParamsList.waitCount > 0) {
1318 PR_NotifyAllCondVar(blindingParamsList.cVar);
1319 blindingParamsList.waitCount = 0;
1320 }
1321 PZ_Unlock(blindingParamsList.lock);
1322 return SECSuccess;
1323 }
1324 /* Here, there are no usable blinding parameters available,
1325 * and no free bp blocks, presumably because they're all
1326 * actively having parameters generated for them.
1327 * So, we need to wait here and not eat up CPU until some
1328 * change happens.
1329 */
1330 blindingParamsList.waitCount++;
1331 PR_WaitCondVar(blindingParamsList.cVar, PR_INTERVAL_NO_TIMEOUT);
1332 PZ_Unlock(blindingParamsList.lock);
1333 holdingLock = PR_FALSE;
1334 (void)holdingLock;
1335 } while (1);
1336
1337 cleanup:
1338 /* It is possible to reach this after the lock is already released. */
1339 if (bpUnlinked) {
1340 if (!holdingLock) {
1341 PZ_Lock(blindingParamsList.lock);
1342 holdingLock = PR_TRUE;
1343 }
1344 bp = bpUnlinked;
1345 mp_clear(&bp->f);
1346 mp_clear(&bp->g);
1347 bp->counter = 0;
1348 /* Must put the unlinked bp back on the free list */
1349 bp->next = rsabp->free;
1350 rsabp->free = bp;
1351 }
1352 if (holdingLock) {
1353 PZ_Unlock(blindingParamsList.lock);
1354 }
1355 if (err) {
1356 MP_TO_SEC_ERROR(err);
1357 }
1358 return SECFailure;
1359 }
1360
1361 /*
1362 ** Perform a raw private-key operation
1363 ** Length of input and output buffers are equal to key's modulus len.
1364 */
1365 static SECStatus
rsa_PrivateKeyOp(RSAPrivateKey * key,unsigned char * output,const unsigned char * input,PRBool check)1366 rsa_PrivateKeyOp(RSAPrivateKey *key,
1367 unsigned char *output,
1368 const unsigned char *input,
1369 PRBool check)
1370 {
1371 unsigned int modLen;
1372 unsigned int offset;
1373 SECStatus rv = SECSuccess;
1374 mp_err err;
1375 mp_int n, c, m;
1376 mp_int f, g;
1377 if (!key || !output || !input) {
1378 PORT_SetError(SEC_ERROR_INVALID_ARGS);
1379 return SECFailure;
1380 }
1381 /* check input out of range (needs to be in range [0..n-1]) */
1382 modLen = rsa_modulusLen(&key->modulus);
1383 offset = (key->modulus.data[0] == 0) ? 1 : 0; /* may be leading 0 */
1384 if (memcmp(input, key->modulus.data + offset, modLen) >= 0) {
1385 PORT_SetError(SEC_ERROR_INVALID_ARGS);
1386 return SECFailure;
1387 }
1388 MP_DIGITS(&n) = 0;
1389 MP_DIGITS(&c) = 0;
1390 MP_DIGITS(&m) = 0;
1391 MP_DIGITS(&f) = 0;
1392 MP_DIGITS(&g) = 0;
1393 CHECK_MPI_OK(mp_init(&n));
1394 CHECK_MPI_OK(mp_init(&c));
1395 CHECK_MPI_OK(mp_init(&m));
1396 CHECK_MPI_OK(mp_init(&f));
1397 CHECK_MPI_OK(mp_init(&g));
1398 SECITEM_TO_MPINT(key->modulus, &n);
1399 OCTETS_TO_MPINT(input, &c, modLen);
1400 /* If blinding, compute pre-image of ciphertext by multiplying by
1401 ** blinding factor
1402 */
1403 if (nssRSAUseBlinding) {
1404 CHECK_SEC_OK(get_blinding_params(key, &n, modLen, &f, &g));
1405 /* c' = c*f mod n */
1406 CHECK_MPI_OK(mp_mulmod(&c, &f, &n, &c));
1407 }
1408 /* Do the private key operation m = c**d mod n */
1409 if (key->prime1.len == 0 ||
1410 key->prime2.len == 0 ||
1411 key->exponent1.len == 0 ||
1412 key->exponent2.len == 0 ||
1413 key->coefficient.len == 0) {
1414 CHECK_SEC_OK(rsa_PrivateKeyOpNoCRT(key, &m, &c, &n, modLen));
1415 } else if (check) {
1416 CHECK_SEC_OK(rsa_PrivateKeyOpCRTCheckedPubKey(key, &m, &c));
1417 } else {
1418 CHECK_SEC_OK(rsa_PrivateKeyOpCRTNoCheck(key, &m, &c));
1419 }
1420 /* If blinding, compute post-image of plaintext by multiplying by
1421 ** blinding factor
1422 */
1423 if (nssRSAUseBlinding) {
1424 /* m = m'*g mod n */
1425 CHECK_MPI_OK(mp_mulmod(&m, &g, &n, &m));
1426 }
1427 err = mp_to_fixlen_octets(&m, output, modLen);
1428 if (err >= 0)
1429 err = MP_OKAY;
1430 cleanup:
1431 mp_clear(&n);
1432 mp_clear(&c);
1433 mp_clear(&m);
1434 mp_clear(&f);
1435 mp_clear(&g);
1436 if (err) {
1437 MP_TO_SEC_ERROR(err);
1438 rv = SECFailure;
1439 }
1440 return rv;
1441 }
1442
1443 SECStatus
RSA_PrivateKeyOp(RSAPrivateKey * key,unsigned char * output,const unsigned char * input)1444 RSA_PrivateKeyOp(RSAPrivateKey *key,
1445 unsigned char *output,
1446 const unsigned char *input)
1447 {
1448 return rsa_PrivateKeyOp(key, output, input, PR_FALSE);
1449 }
1450
1451 SECStatus
RSA_PrivateKeyOpDoubleChecked(RSAPrivateKey * key,unsigned char * output,const unsigned char * input)1452 RSA_PrivateKeyOpDoubleChecked(RSAPrivateKey *key,
1453 unsigned char *output,
1454 const unsigned char *input)
1455 {
1456 return rsa_PrivateKeyOp(key, output, input, PR_TRUE);
1457 }
1458
1459 SECStatus
RSA_PrivateKeyCheck(const RSAPrivateKey * key)1460 RSA_PrivateKeyCheck(const RSAPrivateKey *key)
1461 {
1462 mp_int p, q, n, psub1, qsub1, e, d, d_p, d_q, qInv, res;
1463 mp_err err = MP_OKAY;
1464 SECStatus rv = SECSuccess;
1465 MP_DIGITS(&p) = 0;
1466 MP_DIGITS(&q) = 0;
1467 MP_DIGITS(&n) = 0;
1468 MP_DIGITS(&psub1) = 0;
1469 MP_DIGITS(&qsub1) = 0;
1470 MP_DIGITS(&e) = 0;
1471 MP_DIGITS(&d) = 0;
1472 MP_DIGITS(&d_p) = 0;
1473 MP_DIGITS(&d_q) = 0;
1474 MP_DIGITS(&qInv) = 0;
1475 MP_DIGITS(&res) = 0;
1476 CHECK_MPI_OK(mp_init(&p));
1477 CHECK_MPI_OK(mp_init(&q));
1478 CHECK_MPI_OK(mp_init(&n));
1479 CHECK_MPI_OK(mp_init(&psub1));
1480 CHECK_MPI_OK(mp_init(&qsub1));
1481 CHECK_MPI_OK(mp_init(&e));
1482 CHECK_MPI_OK(mp_init(&d));
1483 CHECK_MPI_OK(mp_init(&d_p));
1484 CHECK_MPI_OK(mp_init(&d_q));
1485 CHECK_MPI_OK(mp_init(&qInv));
1486 CHECK_MPI_OK(mp_init(&res));
1487
1488 if (!key->modulus.data || !key->prime1.data || !key->prime2.data ||
1489 !key->publicExponent.data || !key->privateExponent.data ||
1490 !key->exponent1.data || !key->exponent2.data ||
1491 !key->coefficient.data) {
1492 /* call RSA_PopulatePrivateKey first, if the application wishes to
1493 * recover these parameters */
1494 err = MP_BADARG;
1495 goto cleanup;
1496 }
1497
1498 SECITEM_TO_MPINT(key->modulus, &n);
1499 SECITEM_TO_MPINT(key->prime1, &p);
1500 SECITEM_TO_MPINT(key->prime2, &q);
1501 SECITEM_TO_MPINT(key->publicExponent, &e);
1502 SECITEM_TO_MPINT(key->privateExponent, &d);
1503 SECITEM_TO_MPINT(key->exponent1, &d_p);
1504 SECITEM_TO_MPINT(key->exponent2, &d_q);
1505 SECITEM_TO_MPINT(key->coefficient, &qInv);
1506 /* p and q must be distinct. */
1507 if (mp_cmp(&p, &q) == 0) {
1508 rv = SECFailure;
1509 goto cleanup;
1510 }
1511 #define VERIFY_MPI_EQUAL(m1, m2) \
1512 if (mp_cmp(m1, m2) != 0) { \
1513 rv = SECFailure; \
1514 goto cleanup; \
1515 }
1516 #define VERIFY_MPI_EQUAL_1(m) \
1517 if (mp_cmp_d(m, 1) != 0) { \
1518 rv = SECFailure; \
1519 goto cleanup; \
1520 }
1521 /* n == p * q */
1522 CHECK_MPI_OK(mp_mul(&p, &q, &res));
1523 VERIFY_MPI_EQUAL(&res, &n);
1524 /* gcd(e, p-1) == 1 */
1525 CHECK_MPI_OK(mp_sub_d(&p, 1, &psub1));
1526 CHECK_MPI_OK(mp_gcd(&e, &psub1, &res));
1527 VERIFY_MPI_EQUAL_1(&res);
1528 /* gcd(e, q-1) == 1 */
1529 CHECK_MPI_OK(mp_sub_d(&q, 1, &qsub1));
1530 CHECK_MPI_OK(mp_gcd(&e, &qsub1, &res));
1531 VERIFY_MPI_EQUAL_1(&res);
1532 /* d*e == 1 mod p-1 */
1533 CHECK_MPI_OK(mp_mulmod(&d, &e, &psub1, &res));
1534 VERIFY_MPI_EQUAL_1(&res);
1535 /* d*e == 1 mod q-1 */
1536 CHECK_MPI_OK(mp_mulmod(&d, &e, &qsub1, &res));
1537 VERIFY_MPI_EQUAL_1(&res);
1538 /* d_p == d mod p-1 */
1539 CHECK_MPI_OK(mp_mod(&d, &psub1, &res));
1540 VERIFY_MPI_EQUAL(&res, &d_p);
1541 /* d_q == d mod q-1 */
1542 CHECK_MPI_OK(mp_mod(&d, &qsub1, &res));
1543 VERIFY_MPI_EQUAL(&res, &d_q);
1544 /* q * q**-1 == 1 mod p */
1545 CHECK_MPI_OK(mp_mulmod(&q, &qInv, &p, &res));
1546 VERIFY_MPI_EQUAL_1(&res);
1547
1548 cleanup:
1549 mp_clear(&n);
1550 mp_clear(&p);
1551 mp_clear(&q);
1552 mp_clear(&psub1);
1553 mp_clear(&qsub1);
1554 mp_clear(&e);
1555 mp_clear(&d);
1556 mp_clear(&d_p);
1557 mp_clear(&d_q);
1558 mp_clear(&qInv);
1559 mp_clear(&res);
1560 if (err) {
1561 MP_TO_SEC_ERROR(err);
1562 rv = SECFailure;
1563 }
1564 return rv;
1565 }
1566
1567 SECStatus
RSA_Init(void)1568 RSA_Init(void)
1569 {
1570 if (PR_CallOnce(&coBPInit, init_blinding_params_list) != PR_SUCCESS) {
1571 PORT_SetError(SEC_ERROR_LIBRARY_FAILURE);
1572 return SECFailure;
1573 }
1574 return SECSuccess;
1575 }
1576
1577 /* cleanup at shutdown */
1578 void
RSA_Cleanup(void)1579 RSA_Cleanup(void)
1580 {
1581 blindingParams *bp = NULL;
1582 if (!coBPInit.initialized)
1583 return;
1584
1585 while (!PR_CLIST_IS_EMPTY(&blindingParamsList.head)) {
1586 RSABlindingParams *rsabp =
1587 (RSABlindingParams *)PR_LIST_HEAD(&blindingParamsList.head);
1588 PR_REMOVE_LINK(&rsabp->link);
1589 /* clear parameters cache */
1590 while (rsabp->bp != NULL) {
1591 bp = rsabp->bp;
1592 rsabp->bp = rsabp->bp->next;
1593 mp_clear(&bp->f);
1594 mp_clear(&bp->g);
1595 }
1596 SECITEM_ZfreeItem(&rsabp->modulus, PR_FALSE);
1597 PORT_Free(rsabp);
1598 }
1599
1600 if (blindingParamsList.cVar) {
1601 PR_DestroyCondVar(blindingParamsList.cVar);
1602 blindingParamsList.cVar = NULL;
1603 }
1604
1605 if (blindingParamsList.lock) {
1606 SKIP_AFTER_FORK(PZ_DestroyLock(blindingParamsList.lock));
1607 blindingParamsList.lock = NULL;
1608 }
1609
1610 coBPInit.initialized = 0;
1611 coBPInit.inProgress = 0;
1612 coBPInit.status = 0;
1613 }
1614
1615 /*
1616 * need a central place for this function to free up all the memory that
1617 * free_bl may have allocated along the way. Currently only RSA does this,
1618 * so I've put it here for now.
1619 */
1620 void
BL_Cleanup(void)1621 BL_Cleanup(void)
1622 {
1623 RSA_Cleanup();
1624 }
1625
1626 PRBool bl_parentForkedAfterC_Initialize;
1627
1628 /*
1629 * Set fork flag so it can be tested in SKIP_AFTER_FORK on relevant platforms.
1630 */
1631 void
BL_SetForkState(PRBool forked)1632 BL_SetForkState(PRBool forked)
1633 {
1634 bl_parentForkedAfterC_Initialize = forked;
1635 }
1636