1 /*
2 * Copyright 2018-2021 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright (c) 2018-2019, Oracle and/or its affiliates. All rights reserved.
4 *
5 * Licensed under the Apache License 2.0 (the "License"). You may not use
6 * this file except in compliance with the License. You can obtain a copy
7 * in the file LICENSE in the source distribution or at
8 * https://www.openssl.org/source/license.html
9 */
10
11 #include <openssl/err.h>
12 #include <openssl/bn.h>
13 #include <openssl/core.h>
14 #include <openssl/evp.h>
15 #include <openssl/rand.h>
16 #include "crypto/bn.h"
17 #include "crypto/security_bits.h"
18 #include "rsa_local.h"
19
20 #define RSA_FIPS1864_MIN_KEYGEN_KEYSIZE 2048
21 #define RSA_FIPS1864_MIN_KEYGEN_STRENGTH 112
22
23 /*
24 * Generate probable primes 'p' & 'q'. See FIPS 186-4 Section B.3.6
25 * "Generation of Probable Primes with Conditions Based on Auxiliary Probable
26 * Primes".
27 *
28 * Params:
29 * rsa Object used to store primes p & q.
30 * test Object used for CAVS testing only.that contains..
31 * p1, p2 The returned auxiliary primes for p.
32 * If NULL they are not returned.
33 * Xpout An optionally returned random number used during generation of p.
34 * Xp An optional passed in value (that is random number used during
35 * generation of p).
36 * Xp1, Xp2 Optionally passed in randomly generated numbers from which
37 * auxiliary primes p1 & p2 are calculated. If NULL these values
38 * are generated internally.
39 * q1, q2 The returned auxiliary primes for q.
40 * If NULL they are not returned.
41 * Xqout An optionally returned random number used during generation of q.
42 * Xq An optional passed in value (that is random number used during
43 * generation of q).
44 * Xq1, Xq2 Optionally passed in randomly generated numbers from which
45 * auxiliary primes q1 & q2 are calculated. If NULL these values
46 * are generated internally.
47 * nbits The key size in bits (The size of the modulus n).
48 * e The public exponent.
49 * ctx A BN_CTX object.
50 * cb An optional BIGNUM callback.
51 * Returns: 1 if successful, or 0 otherwise.
52 * Notes:
53 * p1, p2, q1, q2, Xpout, Xqout are returned if they are not NULL.
54 * Xp, Xp1, Xp2, Xq, Xq1, Xq2 are optionally passed in.
55 * (Required for CAVS testing).
56 */
ossl_rsa_fips186_4_gen_prob_primes(RSA * rsa,RSA_ACVP_TEST * test,int nbits,const BIGNUM * e,BN_CTX * ctx,BN_GENCB * cb)57 int ossl_rsa_fips186_4_gen_prob_primes(RSA *rsa, RSA_ACVP_TEST *test,
58 int nbits, const BIGNUM *e, BN_CTX *ctx,
59 BN_GENCB *cb)
60 {
61 int ret = 0, ok;
62 /* Temp allocated BIGNUMS */
63 BIGNUM *Xpo = NULL, *Xqo = NULL, *tmp = NULL;
64 /* Intermediate BIGNUMS that can be returned for testing */
65 BIGNUM *p1 = NULL, *p2 = NULL;
66 BIGNUM *q1 = NULL, *q2 = NULL;
67 /* Intermediate BIGNUMS that can be input for testing */
68 BIGNUM *Xpout = NULL, *Xqout = NULL;
69 BIGNUM *Xp = NULL, *Xp1 = NULL, *Xp2 = NULL;
70 BIGNUM *Xq = NULL, *Xq1 = NULL, *Xq2 = NULL;
71
72 #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
73 if (test != NULL) {
74 Xp1 = test->Xp1;
75 Xp2 = test->Xp2;
76 Xq1 = test->Xq1;
77 Xq2 = test->Xq2;
78 Xp = test->Xp;
79 Xq = test->Xq;
80 p1 = test->p1;
81 p2 = test->p2;
82 q1 = test->q1;
83 q2 = test->q2;
84 }
85 #endif
86
87 /* (Step 1) Check key length
88 * NOTE: SP800-131A Rev1 Disallows key lengths of < 2048 bits for RSA
89 * Signature Generation and Key Agree/Transport.
90 */
91 if (nbits < RSA_FIPS1864_MIN_KEYGEN_KEYSIZE) {
92 ERR_raise(ERR_LIB_RSA, RSA_R_KEY_SIZE_TOO_SMALL);
93 return 0;
94 }
95
96 if (!ossl_rsa_check_public_exponent(e)) {
97 ERR_raise(ERR_LIB_RSA, RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
98 return 0;
99 }
100
101 /* (Step 3) Determine strength and check rand generator strength is ok -
102 * this step is redundant because the generator always returns a higher
103 * strength than is required.
104 */
105
106 BN_CTX_start(ctx);
107 tmp = BN_CTX_get(ctx);
108 Xpo = (Xpout != NULL) ? Xpout : BN_CTX_get(ctx);
109 Xqo = (Xqout != NULL) ? Xqout : BN_CTX_get(ctx);
110 if (tmp == NULL || Xpo == NULL || Xqo == NULL)
111 goto err;
112 BN_set_flags(Xpo, BN_FLG_CONSTTIME);
113 BN_set_flags(Xqo, BN_FLG_CONSTTIME);
114
115 if (rsa->p == NULL)
116 rsa->p = BN_secure_new();
117 if (rsa->q == NULL)
118 rsa->q = BN_secure_new();
119 if (rsa->p == NULL || rsa->q == NULL)
120 goto err;
121 BN_set_flags(rsa->p, BN_FLG_CONSTTIME);
122 BN_set_flags(rsa->q, BN_FLG_CONSTTIME);
123
124 /* (Step 4) Generate p, Xp */
125 if (!ossl_bn_rsa_fips186_4_gen_prob_primes(rsa->p, Xpo, p1, p2, Xp, Xp1, Xp2,
126 nbits, e, ctx, cb))
127 goto err;
128 for (;;) {
129 /* (Step 5) Generate q, Xq*/
130 if (!ossl_bn_rsa_fips186_4_gen_prob_primes(rsa->q, Xqo, q1, q2, Xq, Xq1,
131 Xq2, nbits, e, ctx, cb))
132 goto err;
133
134 /* (Step 6) |Xp - Xq| > 2^(nbitlen/2 - 100) */
135 ok = ossl_rsa_check_pminusq_diff(tmp, Xpo, Xqo, nbits);
136 if (ok < 0)
137 goto err;
138 if (ok == 0)
139 continue;
140
141 /* (Step 6) |p - q| > 2^(nbitlen/2 - 100) */
142 ok = ossl_rsa_check_pminusq_diff(tmp, rsa->p, rsa->q, nbits);
143 if (ok < 0)
144 goto err;
145 if (ok == 0)
146 continue;
147 break; /* successfully finished */
148 }
149 rsa->dirty_cnt++;
150 ret = 1;
151 err:
152 /* Zeroize any internally generated values that are not returned */
153 if (Xpo != Xpout)
154 BN_clear(Xpo);
155 if (Xqo != Xqout)
156 BN_clear(Xqo);
157 BN_clear(tmp);
158
159 BN_CTX_end(ctx);
160 return ret;
161 }
162
163 /*
164 * Validates the RSA key size based on the target strength.
165 * See SP800-56Br1 6.3.1.1 (Steps 1a-1b)
166 *
167 * Params:
168 * nbits The key size in bits.
169 * strength The target strength in bits. -1 means the target
170 * strength is unknown.
171 * Returns: 1 if the key size matches the target strength, or 0 otherwise.
172 */
ossl_rsa_sp800_56b_validate_strength(int nbits,int strength)173 int ossl_rsa_sp800_56b_validate_strength(int nbits, int strength)
174 {
175 int s = (int)ossl_ifc_ffc_compute_security_bits(nbits);
176
177 #ifdef FIPS_MODULE
178 if (s < RSA_FIPS1864_MIN_KEYGEN_STRENGTH) {
179 ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_MODULUS);
180 return 0;
181 }
182 #endif
183 if (strength != -1 && s != strength) {
184 ERR_raise(ERR_LIB_RSA, RSA_R_INVALID_STRENGTH);
185 return 0;
186 }
187 return 1;
188 }
189
190 /*
191 * Validate that the random bit generator is of sufficient strength to generate
192 * a key of the specified length.
193 */
rsa_validate_rng_strength(EVP_RAND_CTX * rng,int nbits)194 static int rsa_validate_rng_strength(EVP_RAND_CTX *rng, int nbits)
195 {
196 if (rng == NULL)
197 return 0;
198 #ifdef FIPS_MODULE
199 /*
200 * This should become mainstream once similar tests are added to the other
201 * key generations and once there is a way to disable these checks.
202 */
203 if (EVP_RAND_get_strength(rng) < ossl_ifc_ffc_compute_security_bits(nbits)) {
204 ERR_raise(ERR_LIB_RSA,
205 RSA_R_RANDOMNESS_SOURCE_STRENGTH_INSUFFICIENT);
206 return 0;
207 }
208 #endif
209 return 1;
210 }
211
212 /*
213 *
214 * Using p & q, calculate other required parameters such as n, d.
215 * as well as the CRT parameters dP, dQ, qInv.
216 *
217 * See SP800-56Br1
218 * 6.3.1.1 rsakpg1 - basic (Steps 3-4)
219 * 6.3.1.3 rsakpg1 - crt (Step 5)
220 *
221 * Params:
222 * rsa An rsa object.
223 * nbits The key size.
224 * e The public exponent.
225 * ctx A BN_CTX object.
226 * Notes:
227 * There is a small chance that the generated d will be too small.
228 * Returns: -1 = error,
229 * 0 = d is too small,
230 * 1 = success.
231 */
ossl_rsa_sp800_56b_derive_params_from_pq(RSA * rsa,int nbits,const BIGNUM * e,BN_CTX * ctx)232 int ossl_rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
233 const BIGNUM *e, BN_CTX *ctx)
234 {
235 int ret = -1;
236 BIGNUM *p1, *q1, *lcm, *p1q1, *gcd;
237
238 BN_CTX_start(ctx);
239 p1 = BN_CTX_get(ctx);
240 q1 = BN_CTX_get(ctx);
241 lcm = BN_CTX_get(ctx);
242 p1q1 = BN_CTX_get(ctx);
243 gcd = BN_CTX_get(ctx);
244 if (gcd == NULL)
245 goto err;
246
247 BN_set_flags(p1, BN_FLG_CONSTTIME);
248 BN_set_flags(q1, BN_FLG_CONSTTIME);
249 BN_set_flags(lcm, BN_FLG_CONSTTIME);
250 BN_set_flags(p1q1, BN_FLG_CONSTTIME);
251 BN_set_flags(gcd, BN_FLG_CONSTTIME);
252
253 /* LCM((p-1, q-1)) */
254 if (ossl_rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1)
255 goto err;
256
257 /* copy e */
258 BN_free(rsa->e);
259 rsa->e = BN_dup(e);
260 if (rsa->e == NULL)
261 goto err;
262
263 BN_clear_free(rsa->d);
264 /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
265 rsa->d = BN_secure_new();
266 if (rsa->d == NULL)
267 goto err;
268 BN_set_flags(rsa->d, BN_FLG_CONSTTIME);
269 if (BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL)
270 goto err;
271
272 /* (Step 3) return an error if d is too small */
273 if (BN_num_bits(rsa->d) <= (nbits >> 1)) {
274 ret = 0;
275 goto err;
276 }
277
278 /* (Step 4) n = pq */
279 if (rsa->n == NULL)
280 rsa->n = BN_new();
281 if (rsa->n == NULL || !BN_mul(rsa->n, rsa->p, rsa->q, ctx))
282 goto err;
283
284 /* (Step 5a) dP = d mod (p-1) */
285 if (rsa->dmp1 == NULL)
286 rsa->dmp1 = BN_secure_new();
287 if (rsa->dmp1 == NULL)
288 goto err;
289 BN_set_flags(rsa->dmp1, BN_FLG_CONSTTIME);
290 if (!BN_mod(rsa->dmp1, rsa->d, p1, ctx))
291 goto err;
292
293 /* (Step 5b) dQ = d mod (q-1) */
294 if (rsa->dmq1 == NULL)
295 rsa->dmq1 = BN_secure_new();
296 if (rsa->dmq1 == NULL)
297 goto err;
298 BN_set_flags(rsa->dmq1, BN_FLG_CONSTTIME);
299 if (!BN_mod(rsa->dmq1, rsa->d, q1, ctx))
300 goto err;
301
302 /* (Step 5c) qInv = (inverse of q) mod p */
303 BN_free(rsa->iqmp);
304 rsa->iqmp = BN_secure_new();
305 if (rsa->iqmp == NULL)
306 goto err;
307 BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME);
308 if (BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL)
309 goto err;
310
311 rsa->dirty_cnt++;
312 ret = 1;
313 err:
314 if (ret != 1) {
315 BN_free(rsa->e);
316 rsa->e = NULL;
317 BN_free(rsa->d);
318 rsa->d = NULL;
319 BN_free(rsa->n);
320 rsa->n = NULL;
321 BN_free(rsa->iqmp);
322 rsa->iqmp = NULL;
323 BN_free(rsa->dmq1);
324 rsa->dmq1 = NULL;
325 BN_free(rsa->dmp1);
326 rsa->dmp1 = NULL;
327 }
328 BN_clear(p1);
329 BN_clear(q1);
330 BN_clear(lcm);
331 BN_clear(p1q1);
332 BN_clear(gcd);
333
334 BN_CTX_end(ctx);
335 return ret;
336 }
337
338 /*
339 * Generate a SP800-56B RSA key.
340 *
341 * See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent"
342 * 6.3.1.1 rsakpg1 - basic
343 * 6.3.1.3 rsakpg1 - crt
344 *
345 * See also FIPS 186-4 Section B.3.6
346 * "Generation of Probable Primes with Conditions Based on Auxiliary
347 * Probable Primes."
348 *
349 * Params:
350 * rsa The rsa object.
351 * nbits The intended key size in bits.
352 * efixed The public exponent. If NULL a default of 65537 is used.
353 * cb An optional BIGNUM callback.
354 * Returns: 1 if successfully generated otherwise it returns 0.
355 */
ossl_rsa_sp800_56b_generate_key(RSA * rsa,int nbits,const BIGNUM * efixed,BN_GENCB * cb)356 int ossl_rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed,
357 BN_GENCB *cb)
358 {
359 int ret = 0;
360 int ok;
361 BN_CTX *ctx = NULL;
362 BIGNUM *e = NULL;
363 RSA_ACVP_TEST *info = NULL;
364
365 #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
366 info = rsa->acvp_test;
367 #endif
368
369 /* (Steps 1a-1b) : Currently ignores the strength check */
370 if (!ossl_rsa_sp800_56b_validate_strength(nbits, -1))
371 return 0;
372
373 /* Check that the RNG is capable of generating a key this large */
374 if (!rsa_validate_rng_strength(RAND_get0_private(rsa->libctx), nbits))
375 return 0;
376
377 ctx = BN_CTX_new_ex(rsa->libctx);
378 if (ctx == NULL)
379 return 0;
380
381 /* Set default if e is not passed in */
382 if (efixed == NULL) {
383 e = BN_new();
384 if (e == NULL || !BN_set_word(e, 65537))
385 goto err;
386 } else {
387 e = (BIGNUM *)efixed;
388 }
389 /* (Step 1c) fixed exponent is checked later .*/
390
391 for (;;) {
392 /* (Step 2) Generate prime factors */
393 if (!ossl_rsa_fips186_4_gen_prob_primes(rsa, info, nbits, e, ctx, cb))
394 goto err;
395 /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
396 ok = ossl_rsa_sp800_56b_derive_params_from_pq(rsa, nbits, e, ctx);
397 if (ok < 0)
398 goto err;
399 if (ok > 0)
400 break;
401 /* Gets here if computed d is too small - so try again */
402 }
403
404 /* (Step 6) Do pairwise test - optional validity test has been omitted */
405 ret = ossl_rsa_sp800_56b_pairwise_test(rsa, ctx);
406 err:
407 if (efixed == NULL)
408 BN_free(e);
409 BN_CTX_free(ctx);
410 return ret;
411 }
412
413 /*
414 * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by
415 * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1.
416 *
417 * Returns 1 if the RSA key passes the pairwise test or 0 it it fails.
418 */
ossl_rsa_sp800_56b_pairwise_test(RSA * rsa,BN_CTX * ctx)419 int ossl_rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx)
420 {
421 int ret = 0;
422 BIGNUM *k, *tmp;
423
424 BN_CTX_start(ctx);
425 tmp = BN_CTX_get(ctx);
426 k = BN_CTX_get(ctx);
427 if (k == NULL)
428 goto err;
429 BN_set_flags(k, BN_FLG_CONSTTIME);
430
431 ret = (BN_set_word(k, 2)
432 && BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx)
433 && BN_mod_exp(tmp, tmp, rsa->d, rsa->n, ctx)
434 && BN_cmp(k, tmp) == 0);
435 if (ret == 0)
436 ERR_raise(ERR_LIB_RSA, RSA_R_PAIRWISE_TEST_FAILURE);
437 err:
438 BN_CTX_end(ctx);
439 return ret;
440 }
441
