rsa: add ossl_ prefix to internal rsa_ calls.
[openssl.git] / crypto / rsa / rsa_sp800_56b_check.c
1 /*
2  * Copyright 2018-2020 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 "crypto/bn.h"
14 #include "rsa_local.h"
15
16 /*
17  * Part of the RSA keypair test.
18  * Check the Chinese Remainder Theorem components are valid.
19  *
20  * See SP800-5bBr1
21  *   6.4.1.2.3: rsakpv1-crt Step 7
22  *   6.4.1.3.3: rsakpv2-crt Step 7
23  */
24 int ossl_rsa_check_crt_components(const RSA *rsa, BN_CTX *ctx)
25 {
26     int ret = 0;
27     BIGNUM *r = NULL, *p1 = NULL, *q1 = NULL;
28
29     /* check if only some of the crt components are set */
30     if (rsa->dmp1 == NULL || rsa->dmq1 == NULL || rsa->iqmp == NULL) {
31         if (rsa->dmp1 != NULL || rsa->dmq1 != NULL || rsa->iqmp != NULL)
32             return 0;
33         return 1; /* return ok if all components are NULL */
34     }
35
36     BN_CTX_start(ctx);
37     r = BN_CTX_get(ctx);
38     p1 = BN_CTX_get(ctx);
39     q1 = BN_CTX_get(ctx);
40     if (q1 != NULL) {
41         BN_set_flags(r, BN_FLG_CONSTTIME);
42         BN_set_flags(p1, BN_FLG_CONSTTIME);
43         BN_set_flags(q1, BN_FLG_CONSTTIME);
44         ret = 1;
45     } else {
46         ret = 0;
47     }
48     ret = ret
49           /* p1 = p -1 */
50           && (BN_copy(p1, rsa->p) != NULL)
51           && BN_sub_word(p1, 1)
52           /* q1 = q - 1 */
53           && (BN_copy(q1, rsa->q) != NULL)
54           && BN_sub_word(q1, 1)
55           /* (a) 1 < dP < (p – 1). */
56           && (BN_cmp(rsa->dmp1, BN_value_one()) > 0)
57           && (BN_cmp(rsa->dmp1, p1) < 0)
58           /* (b) 1 < dQ < (q - 1). */
59           && (BN_cmp(rsa->dmq1, BN_value_one()) > 0)
60           && (BN_cmp(rsa->dmq1, q1) < 0)
61           /* (c) 1 < qInv < p */
62           && (BN_cmp(rsa->iqmp, BN_value_one()) > 0)
63           && (BN_cmp(rsa->iqmp, rsa->p) < 0)
64           /* (d) 1 = (dP . e) mod (p - 1)*/
65           && BN_mod_mul(r, rsa->dmp1, rsa->e, p1, ctx)
66           && BN_is_one(r)
67           /* (e) 1 = (dQ . e) mod (q - 1) */
68           && BN_mod_mul(r, rsa->dmq1, rsa->e, q1, ctx)
69           && BN_is_one(r)
70           /* (f) 1 = (qInv . q) mod p */
71           && BN_mod_mul(r, rsa->iqmp, rsa->q, rsa->p, ctx)
72           && BN_is_one(r);
73     BN_clear(r);
74     BN_clear(p1);
75     BN_clear(q1);
76     BN_CTX_end(ctx);
77     return ret;
78 }
79
80 /*
81  * Part of the RSA keypair test.
82  * Check that (√2)(2^(nbits/2 - 1) <= p <= 2^(nbits/2) - 1
83  *
84  * See SP800-5bBr1 6.4.1.2.1 Part 5 (c) & (g) - used for both p and q.
85  *
86  * (√2)(2^(nbits/2 - 1) = (√2/2)(2^(nbits/2))
87  */
88 int ossl_rsa_check_prime_factor_range(const BIGNUM *p, int nbits, BN_CTX *ctx)
89 {
90     int ret = 0;
91     BIGNUM *low;
92     int shift;
93
94     nbits >>= 1;
95     shift = nbits - BN_num_bits(&bn_inv_sqrt_2);
96
97     /* Upper bound check */
98     if (BN_num_bits(p) != nbits)
99         return 0;
100
101     BN_CTX_start(ctx);
102     low = BN_CTX_get(ctx);
103     if (low == NULL)
104         goto err;
105
106     /* set low = (√2)(2^(nbits/2 - 1) */
107     if (!BN_copy(low, &bn_inv_sqrt_2))
108         goto err;
109
110     if (shift >= 0) {
111         /*
112          * We don't have all the bits. bn_inv_sqrt_2 contains a rounded up
113          * value, so there is a very low probability that we'll reject a valid
114          * value.
115          */
116         if (!BN_lshift(low, low, shift))
117             goto err;
118     } else if (!BN_rshift(low, low, -shift)) {
119         goto err;
120     }
121     if (BN_cmp(p, low) <= 0)
122         goto err;
123     ret = 1;
124 err:
125     BN_CTX_end(ctx);
126     return ret;
127 }
128
129 /*
130  * Part of the RSA keypair test.
131  * Check the prime factor (for either p or q)
132  * i.e: p is prime AND GCD(p - 1, e) = 1
133  *
134  * See SP800-56Br1 6.4.1.2.3 Step 5 (a to d) & (e to h).
135  */
136 int ossl_rsa_check_prime_factor(BIGNUM *p, BIGNUM *e, int nbits, BN_CTX *ctx)
137 {
138     int ret = 0;
139     BIGNUM *p1 = NULL, *gcd = NULL;
140
141     /* (Steps 5 a-b) prime test */
142     if (BN_check_prime(p, ctx, NULL) != 1
143             /* (Step 5c) (√2)(2^(nbits/2 - 1) <= p <= 2^(nbits/2 - 1) */
144             || ossl_rsa_check_prime_factor_range(p, nbits, ctx) != 1)
145         return 0;
146
147     BN_CTX_start(ctx);
148     p1 = BN_CTX_get(ctx);
149     gcd = BN_CTX_get(ctx);
150     if (gcd != NULL) {
151         BN_set_flags(p1, BN_FLG_CONSTTIME);
152         BN_set_flags(gcd, BN_FLG_CONSTTIME);
153         ret = 1;
154     } else {
155         ret = 0;
156     }
157     ret = ret
158           /* (Step 5d) GCD(p-1, e) = 1 */
159           && (BN_copy(p1, p) != NULL)
160           && BN_sub_word(p1, 1)
161           && BN_gcd(gcd, p1, e, ctx)
162           && BN_is_one(gcd);
163
164     BN_clear(p1);
165     BN_CTX_end(ctx);
166     return ret;
167 }
168
169 /*
170  * See SP800-56Br1 6.4.1.2.3 Part 6(a-b) Check the private exponent d
171  * satisfies:
172  *     (Step 6a) 2^(nBit/2) < d < LCM(p–1, q–1).
173  *     (Step 6b) 1 = (d*e) mod LCM(p–1, q–1)
174  */
175 int ossl_rsa_check_private_exponent(const RSA *rsa, int nbits, BN_CTX *ctx)
176 {
177     int ret;
178     BIGNUM *r, *p1, *q1, *lcm, *p1q1, *gcd;
179
180     /* (Step 6a) 2^(nbits/2) < d */
181     if (BN_num_bits(rsa->d) <= (nbits >> 1))
182         return 0;
183
184     BN_CTX_start(ctx);
185     r = BN_CTX_get(ctx);
186     p1 = BN_CTX_get(ctx);
187     q1 = BN_CTX_get(ctx);
188     lcm = BN_CTX_get(ctx);
189     p1q1 = BN_CTX_get(ctx);
190     gcd = BN_CTX_get(ctx);
191     if (gcd != NULL) {
192         BN_set_flags(r, BN_FLG_CONSTTIME);
193         BN_set_flags(p1, BN_FLG_CONSTTIME);
194         BN_set_flags(q1, BN_FLG_CONSTTIME);
195         BN_set_flags(lcm, BN_FLG_CONSTTIME);
196         BN_set_flags(p1q1, BN_FLG_CONSTTIME);
197         BN_set_flags(gcd, BN_FLG_CONSTTIME);
198         ret = 1;
199     } else {
200         ret = 0;
201     }
202     ret = (ret
203           /* LCM(p - 1, q - 1) */
204           && (ossl_rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1,
205                                p1q1) == 1)
206           /* (Step 6a) d < LCM(p - 1, q - 1) */
207           && (BN_cmp(rsa->d, lcm) < 0)
208           /* (Step 6b) 1 = (e . d) mod LCM(p - 1, q - 1) */
209           && BN_mod_mul(r, rsa->e, rsa->d, lcm, ctx)
210           && BN_is_one(r));
211
212     BN_clear(r);
213     BN_clear(p1);
214     BN_clear(q1);
215     BN_clear(lcm);
216     BN_clear(gcd);
217     BN_CTX_end(ctx);
218     return ret;
219 }
220
221 #ifndef FIPS_MODULE
222 static int bn_is_three(const BIGNUM *bn)
223 {
224     BIGNUM *num = BN_dup(bn);
225     int ret = (num != NULL && BN_sub_word(num, 3) && BN_is_zero(num));
226
227     BN_free(num);
228     return ret;
229 }
230 #endif /* FIPS_MODULE */
231
232 /* Check exponent is odd, and has a bitlen ranging from [17..256] */
233 int ossl_rsa_check_public_exponent(const BIGNUM *e)
234 {
235     int bitlen;
236
237     /* For legacy purposes RSA_3 is allowed in non fips mode */
238 #ifndef FIPS_MODULE
239     if (bn_is_three(e))
240         return 1;
241 #endif /* FIPS_MODULE */
242
243     bitlen = BN_num_bits(e);
244     return (BN_is_odd(e) && bitlen > 16 && bitlen < 257);
245 }
246
247 /*
248  * SP800-56Br1 6.4.1.2.1 (Step 5i): |p - q| > 2^(nbits/2 - 100)
249  * i.e- numbits(p-q-1) > (nbits/2 -100)
250  */
251 int ossl_rsa_check_pminusq_diff(BIGNUM *diff, const BIGNUM *p, const BIGNUM *q,
252                            int nbits)
253 {
254     int bitlen = (nbits >> 1) - 100;
255
256     if (!BN_sub(diff, p, q))
257         return -1;
258     BN_set_negative(diff, 0);
259
260     if (BN_is_zero(diff))
261         return 0;
262
263     if (!BN_sub_word(diff, 1))
264         return -1;
265     return (BN_num_bits(diff) > bitlen);
266 }
267
268 /*
269  * return LCM(p-1, q-1)
270  *
271  * Caller should ensure that lcm, gcd, p1, q1, p1q1 are flagged with
272  * BN_FLG_CONSTTIME.
273  */
274 int ossl_rsa_get_lcm(BN_CTX *ctx, const BIGNUM *p, const BIGNUM *q,
275                      BIGNUM *lcm, BIGNUM *gcd, BIGNUM *p1, BIGNUM *q1,
276                      BIGNUM *p1q1)
277 {
278     return BN_sub(p1, p, BN_value_one())    /* p-1 */
279            && BN_sub(q1, q, BN_value_one()) /* q-1 */
280            && BN_mul(p1q1, p1, q1, ctx)     /* (p-1)(q-1) */
281            && BN_gcd(gcd, p1, q1, ctx)
282            && BN_div(lcm, NULL, p1q1, gcd, ctx); /* LCM((p-1, q-1)) */
283 }
284
285 /*
286  * SP800-56Br1 6.4.2.2 Partial Public Key Validation for RSA refers to
287  * SP800-89 5.3.3 (Explicit) Partial Public Key Validation for RSA
288  * caveat is that the modulus must be as specified in SP800-56Br1
289  */
290 int ossl_rsa_sp800_56b_check_public(const RSA *rsa)
291 {
292     int ret = 0, status;
293 #ifdef FIPS_MODULE
294     int nbits;
295 #endif
296     BN_CTX *ctx = NULL;
297     BIGNUM *gcd = NULL;
298
299     if (rsa->n == NULL || rsa->e == NULL)
300         return 0;
301
302 #ifdef FIPS_MODULE
303     /*
304      * (Step a): modulus must be 2048 or 3072 (caveat from SP800-56Br1)
305      * NOTE: changed to allow keys >= 2048
306      */
307     nbits = BN_num_bits(rsa->n);
308     if (!ossl_rsa_sp800_56b_validate_strength(nbits, -1)) {
309         RSAerr(0, RSA_R_INVALID_KEY_LENGTH);
310         return 0;
311     }
312 #endif
313     if (!BN_is_odd(rsa->n)) {
314         RSAerr(0, RSA_R_INVALID_MODULUS);
315         return 0;
316     }
317     /* (Steps b-c): 2^16 < e < 2^256, n and e must be odd */
318     if (!ossl_rsa_check_public_exponent(rsa->e)) {
319         RSAerr(0, RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
320         return 0;
321     }
322
323     ctx = BN_CTX_new_ex(rsa->libctx);
324     gcd = BN_new();
325     if (ctx == NULL || gcd == NULL)
326         goto err;
327
328     /* (Steps d-f):
329      * The modulus is composite, but not a power of a prime.
330      * The modulus has no factors smaller than 752.
331      */
332     if (!BN_gcd(gcd, rsa->n, bn_get0_small_factors(), ctx) || !BN_is_one(gcd)) {
333         RSAerr(0, RSA_R_INVALID_MODULUS);
334         goto err;
335     }
336
337     ret = bn_miller_rabin_is_prime(rsa->n, 0, ctx, NULL, 1, &status);
338     if (ret != 1 || status != BN_PRIMETEST_COMPOSITE_NOT_POWER_OF_PRIME) {
339         RSAerr(0, RSA_R_INVALID_MODULUS);
340         ret = 0;
341         goto err;
342     }
343
344     ret = 1;
345 err:
346     BN_free(gcd);
347     BN_CTX_free(ctx);
348     return ret;
349 }
350
351 /*
352  * Perform validation of the RSA private key to check that 0 < D < N.
353  */
354 int ossl_rsa_sp800_56b_check_private(const RSA *rsa)
355 {
356     if (rsa->d == NULL || rsa->n == NULL)
357         return 0;
358     return BN_cmp(rsa->d, BN_value_one()) >= 0 && BN_cmp(rsa->d, rsa->n) < 0;
359 }
360
361 /*
362  * RSA key pair validation.
363  *
364  * SP800-56Br1.
365  *    6.4.1.2 "RSAKPV1 Family: RSA Key - Pair Validation with a Fixed Exponent"
366  *    6.4.1.3 "RSAKPV2 Family: RSA Key - Pair Validation with a Random Exponent"
367  *
368  * It uses:
369  *     6.4.1.2.3 "rsakpv1 - crt"
370  *     6.4.1.3.3 "rsakpv2 - crt"
371  */
372 int ossl_rsa_sp800_56b_check_keypair(const RSA *rsa, const BIGNUM *efixed,
373                                      int strength, int nbits)
374 {
375     int ret = 0;
376     BN_CTX *ctx = NULL;
377     BIGNUM *r = NULL;
378
379     if (rsa->p == NULL
380             || rsa->q == NULL
381             || rsa->e == NULL
382             || rsa->d == NULL
383             || rsa->n == NULL) {
384         RSAerr(0, RSA_R_INVALID_REQUEST);
385         return 0;
386     }
387     /* (Step 1): Check Ranges */
388     if (!ossl_rsa_sp800_56b_validate_strength(nbits, strength))
389         return 0;
390
391     /* If the exponent is known */
392     if (efixed != NULL) {
393         /* (2): Check fixed exponent matches public exponent. */
394         if (BN_cmp(efixed, rsa->e) != 0) {
395             RSAerr(0, RSA_R_INVALID_REQUEST);
396             return 0;
397         }
398     }
399     /* (Step 1.c): e is odd integer 65537 <= e < 2^256 */
400     if (!ossl_rsa_check_public_exponent(rsa->e)) {
401         /* exponent out of range */
402         RSAerr(0, RSA_R_PUB_EXPONENT_OUT_OF_RANGE);
403         return 0;
404     }
405     /* (Step 3.b): check the modulus */
406     if (nbits != BN_num_bits(rsa->n)) {
407         RSAerr(0, RSA_R_INVALID_KEYPAIR);
408         return 0;
409     }
410
411     ctx = BN_CTX_new_ex(rsa->libctx);
412     if (ctx == NULL)
413         return 0;
414
415     BN_CTX_start(ctx);
416     r = BN_CTX_get(ctx);
417     if (r == NULL || !BN_mul(r, rsa->p, rsa->q, ctx))
418         goto err;
419     /* (Step 4.c): Check n = pq */
420     if (BN_cmp(rsa->n, r) != 0) {
421         RSAerr(0, RSA_R_INVALID_REQUEST);
422         goto err;
423     }
424
425     /* (Step 5): check prime factors p & q */
426     ret = ossl_rsa_check_prime_factor(rsa->p, rsa->e, nbits, ctx)
427           && ossl_rsa_check_prime_factor(rsa->q, rsa->e, nbits, ctx)
428           && (ossl_rsa_check_pminusq_diff(r, rsa->p, rsa->q, nbits) > 0)
429           /* (Step 6): Check the private exponent d */
430           && ossl_rsa_check_private_exponent(rsa, nbits, ctx)
431           /* 6.4.1.2.3 (Step 7): Check the CRT components */
432           && ossl_rsa_check_crt_components(rsa, ctx);
433     if (ret != 1)
434         RSAerr(0, RSA_R_INVALID_KEYPAIR);
435
436 err:
437     BN_clear(r);
438     BN_CTX_end(ctx);
439     BN_CTX_free(ctx);
440     return ret;
441 }