crypto/rsa/rsa_sp800_56b_gen.c

   1 /*
   2  * Copyright 2018-2023 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  */
  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  */
 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  */
 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  *
 232  * SP800-56b key generation always passes a non NULL value for e.
 233  * For other purposes, if e is NULL then it is assumed that e, n and d are
 234  * already set in the RSA key and do not need to be recalculated.
 235  */
 236 int ossl_rsa_sp800_56b_derive_params_from_pq(RSA *rsa, int nbits,
 237                                              const BIGNUM *e, BN_CTX *ctx)
 238 {
 239     int ret = -1;
 240     BIGNUM *p1, *q1, *lcm, *p1q1, *gcd;
 241     BN_CTX_start(ctx);
 242     p1 = BN_CTX_get(ctx);
 243     q1 = BN_CTX_get(ctx);
 244     lcm = BN_CTX_get(ctx);
 245     p1q1 = BN_CTX_get(ctx);
 246     gcd = BN_CTX_get(ctx);
 247     if (gcd == NULL)
 248         goto err;
 249
 250     BN_set_flags(p1, BN_FLG_CONSTTIME);
 251     BN_set_flags(q1, BN_FLG_CONSTTIME);
 252     BN_set_flags(lcm, BN_FLG_CONSTTIME);
 253     BN_set_flags(p1q1, BN_FLG_CONSTTIME);
 254     BN_set_flags(gcd, BN_FLG_CONSTTIME);
 255
 256     /* LCM((p-1, q-1)) */
 257     if (ossl_rsa_get_lcm(ctx, rsa->p, rsa->q, lcm, gcd, p1, q1, p1q1) != 1)
 258         goto err;
 259
 260     /*
 261      * if e is provided as a parameter, don't recompute e, d or n
 262      */
 263     if (e != NULL) {
 264         /* copy e */
 265         BN_free(rsa->e);
 266         rsa->e = BN_dup(e);
 267         if (rsa->e == NULL)
 268             goto err;
 269
 270         BN_clear_free(rsa->d);
 271         /* (Step 3) d = (e^-1) mod (LCM(p-1, q-1)) */
 272         rsa->d = BN_secure_new();
 273         if (rsa->d == NULL)
 274             goto err;
 275         BN_set_flags(rsa->d, BN_FLG_CONSTTIME);
 276         if (BN_mod_inverse(rsa->d, e, lcm, ctx) == NULL)
 277             goto err;
 278
 279         /* (Step 3) return an error if d is too small */
 280         if (BN_num_bits(rsa->d) <= (nbits >> 1)) {
 281             ret = 0;
 282             goto err;
 283         }
 284
 285         /* (Step 4) n = pq */
 286         if (rsa->n == NULL)
 287             rsa->n = BN_new();
 288         if (rsa->n == NULL || !BN_mul(rsa->n, rsa->p, rsa->q, ctx))
 289             goto err;
 290     }
 291
 292     /* (Step 5a) dP = d mod (p-1) */
 293     if (rsa->dmp1 == NULL)
 294         rsa->dmp1 = BN_secure_new();
 295     if (rsa->dmp1 == NULL)
 296         goto err;
 297     BN_set_flags(rsa->dmp1, BN_FLG_CONSTTIME);
 298     if (!BN_mod(rsa->dmp1, rsa->d, p1, ctx))
 299         goto err;
 300
 301     /* (Step 5b) dQ = d mod (q-1) */
 302     if (rsa->dmq1 == NULL)
 303         rsa->dmq1 = BN_secure_new();
 304     if (rsa->dmq1 == NULL)
 305         goto err;
 306     BN_set_flags(rsa->dmq1, BN_FLG_CONSTTIME);
 307     if (!BN_mod(rsa->dmq1, rsa->d, q1, ctx))
 308         goto err;
 309
 310     /* (Step 5c) qInv = (inverse of q) mod p */
 311     BN_free(rsa->iqmp);
 312     rsa->iqmp = BN_secure_new();
 313     if (rsa->iqmp == NULL)
 314         goto err;
 315     BN_set_flags(rsa->iqmp, BN_FLG_CONSTTIME);
 316     if (BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx) == NULL)
 317         goto err;
 318
 319     rsa->dirty_cnt++;
 320     ret = 1;
 321 err:
 322     if (ret != 1) {
 323         BN_free(rsa->e);
 324         rsa->e = NULL;
 325         BN_free(rsa->d);
 326         rsa->d = NULL;
 327         BN_free(rsa->n);
 328         rsa->n = NULL;
 329         BN_free(rsa->iqmp);
 330         rsa->iqmp = NULL;
 331         BN_free(rsa->dmq1);
 332         rsa->dmq1 = NULL;
 333         BN_free(rsa->dmp1);
 334         rsa->dmp1 = NULL;
 335     }
 336     BN_clear(p1);
 337     BN_clear(q1);
 338     BN_clear(lcm);
 339     BN_clear(p1q1);
 340     BN_clear(gcd);
 341
 342     BN_CTX_end(ctx);
 343     return ret;
 344 }
 345
 346 /*
 347  * Generate a SP800-56B RSA key.
 348  *
 349  * See SP800-56Br1 6.3.1 "RSA Key-Pair Generation with a Fixed Public Exponent"
 350  *    6.3.1.1 rsakpg1 - basic
 351  *    6.3.1.3 rsakpg1 - crt
 352  *
 353  * See also FIPS 186-4 Section B.3.6
 354  * "Generation of Probable Primes with Conditions Based on Auxiliary
 355  * Probable Primes."
 356  *
 357  * Params:
 358  *     rsa The rsa object.
 359  *     nbits The intended key size in bits.
 360  *     efixed The public exponent. If NULL a default of 65537 is used.
 361  *     cb An optional BIGNUM callback.
 362  * Returns: 1 if successfully generated otherwise it returns 0.
 363  */
 364 int ossl_rsa_sp800_56b_generate_key(RSA *rsa, int nbits, const BIGNUM *efixed,
 365                                     BN_GENCB *cb)
 366 {
 367     int ret = 0;
 368     int ok;
 369     BN_CTX *ctx = NULL;
 370     BIGNUM *e = NULL;
 371     RSA_ACVP_TEST *info = NULL;
 372     BIGNUM *tmp;
 373
 374 #if defined(FIPS_MODULE) && !defined(OPENSSL_NO_ACVP_TESTS)
 375     info = rsa->acvp_test;
 376 #endif
 377
 378     /* (Steps 1a-1b) : Currently ignores the strength check */
 379     if (!ossl_rsa_sp800_56b_validate_strength(nbits, -1))
 380         return 0;
 381
 382     /* Check that the RNG is capable of generating a key this large */
 383    if (!rsa_validate_rng_strength(RAND_get0_private(rsa->libctx), nbits))
 384         return 0;
 385
 386     ctx = BN_CTX_new_ex(rsa->libctx);
 387     if (ctx == NULL)
 388         return 0;
 389
 390     /* Set default if e is not passed in */
 391     if (efixed == NULL) {
 392         e = BN_new();
 393         if (e == NULL || !BN_set_word(e, 65537))
 394             goto err;
 395     } else {
 396         e = (BIGNUM *)efixed;
 397     }
 398     /* (Step 1c) fixed exponent is checked later .*/
 399
 400     for (;;) {
 401         /* (Step 2) Generate prime factors */
 402         if (!ossl_rsa_fips186_4_gen_prob_primes(rsa, info, nbits, e, ctx, cb))
 403             goto err;
 404
 405         /* p>q check and skipping in case of acvp test */
 406         if (info == NULL && BN_cmp(rsa->p, rsa->q) < 0) {
 407             tmp = rsa->p;
 408             rsa->p = rsa->q;
 409             rsa->q = tmp;
 410         }
 411
 412         /* (Steps 3-5) Compute params d, n, dP, dQ, qInv */
 413         ok = ossl_rsa_sp800_56b_derive_params_from_pq(rsa, nbits, e, ctx);
 414         if (ok < 0)
 415             goto err;
 416         if (ok > 0)
 417             break;
 418         /* Gets here if computed d is too small - so try again */
 419     }
 420
 421     /* (Step 6) Do pairwise test - optional validity test has been omitted */
 422     ret = ossl_rsa_sp800_56b_pairwise_test(rsa, ctx);
 423 err:
 424     if (efixed == NULL)
 425         BN_free(e);
 426     BN_CTX_free(ctx);
 427     return ret;
 428 }
 429
 430 /*
 431  * See SP800-56Br1 6.3.1.3 (Step 6) Perform a pair-wise consistency test by
 432  * verifying that: k = (k^e)^d mod n for some integer k where 1 < k < n-1.
 433  *
 434  * Returns 1 if the RSA key passes the pairwise test or 0 if it fails.
 435  */
 436 int ossl_rsa_sp800_56b_pairwise_test(RSA *rsa, BN_CTX *ctx)
 437 {
 438     int ret = 0;
 439     BIGNUM *k, *tmp;
 440
 441     BN_CTX_start(ctx);
 442     tmp = BN_CTX_get(ctx);
 443     k = BN_CTX_get(ctx);
 444     if (k == NULL)
 445         goto err;
 446     BN_set_flags(k, BN_FLG_CONSTTIME);
 447
 448     ret = (BN_set_word(k, 2)
 449            && BN_mod_exp(tmp, k, rsa->e, rsa->n, ctx)
 450            && BN_mod_exp(tmp, tmp, rsa->d, rsa->n, ctx)
 451            && BN_cmp(k, tmp) == 0);
 452     if (ret == 0)
 453         ERR_raise(ERR_LIB_RSA, RSA_R_PAIRWISE_TEST_FAILURE);
 454 err:
 455     BN_CTX_end(ctx);
 456     return ret;
 457 }